Abstract
Motion estimation (ME) plays a vital role in performance of any video codec as it addresses the temporal redundancies existing within consecutive frames in any video sequence. The computational complexity of the ME unit is major with respect to the other blocks in the video codec. Researchers and practitioners prefer to use block matching algorithm for performing ME as it is efficient and simultaneously easy to implement. Some ME algorithms follow fixed search patterns, while the others are adaptive and tries to explore the correlation existing within neighbouring blocks of a video frame. This paper presents a new motion estimation algorithm named half-way stop adaptive pattern search algorithm (HAPSA) that reduces the computation of ME by lowering search points, using a proposed half-way stop technique and adaptive search pattern that can explore both fast and slow motion content in a video frame. The proposed HAPSA applies dual-threshold technique—one for classifying the block between zero motion and nonzero motion vector block and another for checking the accuracy of the motion vector. This helps in optimizing the clock cycle requirement and hardware utilization during VLSI design. The proposed VLSI system demonstrates architectural innovation that supports multiple dataflow models with high data throughput. The principal driving force behind the hardware architecture is an output stationary dataflow model wherein 16 reference frame pixels are broadcasted to all the processing elements every clock cycle. Working at a frequency of 357 MHz, the proposed architecture can process a 422 full HD (1920 × 1080) frames per second. The overall gate count of the design turns to be 49 K gate equivalent. The appreciable results with respect to some of the recent works can motivate one to include the proposed system in portable consumer video devices.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Data Availability
The datasets analysed during the current study are available in the VIPSL Database: Images & Video Clips (2), (https://see.xidian.edu.cn/vipsl/database_Video.html).
References
B. Biswas, R. Mukherjee, I. Chakrabarti, Efficient architecture of adaptive rood pattern search technique for fast motion estimation. Microprocess. Microsyst. 39(3), 200–209 (2015)
B. Biswas, R. Mukherjee, I. Chakrabarti, P.K. Dutta, A.K. Ray, A high-speed VLSI architecture for motion estimation using modified adaptive rood pattern search algorithm. Circuits Syst. Signal Process. 37, 4548–4567 (2018)
A.C. Bovik, The essential guide to video processing (Academic Press, 2009)
W.M. Chao, C.W. Hsu, Y.C. Chang, L.G. Chen, A novel hybrid motion estimator supporting diamond search and fast full search, in IEEE International Symposium on Circuits and Systems, 2002, ISCAS 2002, Vol. 2, pp. II–II (IEEE, 2002)
S.K. Chatterjee, I. Chakrabarti, Low power VLSI architectures for one bit transformation based fast motion estimation. IEEE Trans. Consum. Electron. 56(4), 1 (2010)
S.K. Chatterjee, I. Chakrabarti, Power efficient motion estimation algorithm and architecture based on pixel truncation. IEEE Trans. Consum. Electron. 57(4), 1 (2011)
Y. Ding, X.L. Yan, Parallel architecture of motion estimation for video format conversion with center-biased diamond search, in International Conference on Information Engineering and Computer Science, 2009. ICIECS 2009, pp. 1–4. (IEEE, 2009)
Z. He, M.L. Lieu, P.C.H. Chan, R. Li, An efficient VLSI architecture for new three-step search algorithm. In Proceedings of the 38th Midwest Symposium on Circuits and Systems, 1995, vol. 2, pp. 1228–1231. (IEEE, 1995)
Y.S. Jehng, L.G. Chen, T.D. Chiueh, An efficient and simple VLSI tree architecture for motion estimation algorithms. IEEE Trans. Signal Process. 41(2), 889–900 (1993)
H.M. Jong, T.D. Chiueh, Parallel architectures for 3-step hierarchical search block-matching algorithm. IEEE Trans. Circuits Syst. Video Technol. 4(4), 407–416 (1994)
J. Kim, T. Park, A novel VLSI architecture for full-search variable block-size motion estimation. IEEE Trans. Consum. Electron. 55(2), 1 (2009)
T. Koga, Motion-compensated interframe coding for video conferencing, In Proceedings of NTC 81, pp. C9–6 (1981)
P. Lakamsani, B. Zeng, M. Liou, An enhanced three step search motion estimation method and its VLSI architecture. In IEEE International Symposium on Circuits and Systems, 1996 ISCAS’96, Connecting the World, 1996, vol. 2, pp. 754–757 (IEEE, 1996)
R. Li, B. Zeng, M.L. Liou, A new three-step search algorithm for block motion estimation. IEEE Trans. Circuits Syst. Video Technol. 4(4), 438–442 (1994)
D.X. Li, W. Zheng, M. Zhang, Architecture design for H 264/AVC integer motion estimation with minimum memory bandwidth. IEEE Trans. Consum. Electron. 53(3), 1 (2007)
L.K. Liu, E. Feig, A block-based gradient descent search algorithm for block motion estimation in video coding. IEEE Trans. Circuits Syst. Video Technol. 6(4), 419–422 (1996)
S. Metkar, S. Talbar, Fast motion estimation using modified orthogonal search algorithm for video compression, in Motion Estimation Techniques for Digital Video Coding, pp. 33–45 (Springer, 2013)
S. Metkar, S. Talbar, Motion estimation techniques for digital video coding (Springer, 2013)
R. Mukherjee, B. Biswas, I. Chakrabarti, P.K. Dutta, S. Sengupta, A.K. Ray, Speed-area optimized VLSI architecture of hexagonal search algorithm for motion estimation of 512× 512 frames. Circuits Syst. Signal Process. 36(2), 640–657 (2017)
R. Mukherjee, P. Saha, I. Chakrabarti, P.K. Dutta, A.K. Ray, Fast adaptive motion estimation algorithm and its efficient VLSI system for high definition videos. Expert Syst. Appl. 101, 159–175 (2018)
R. Mukherjee, K. Sheth, A.S. Dhar, I. Chakrabarti, S. Sengupta, High performance vlsi architecture for three-step search algorithm. Circuits Systems Signal Process. 34(5), 1595–1612 (2015)
R. Mukherjee, I. Vinod, I. Chakrabarti, P.K. Dutta, A.K. Ray, Hexagon based compressed diamond algorithm for motion estimation and its dedicated VLSI system for HD videos. Expert Syst. Appl. 141, 1 (2020)
O. Ndili, T. Ogunfunmi, Algorithm and architecture co-design of hardware-oriented, modified diamond search for fast motion estimation in H. 264/AVC. IEEE Trans. Circuits Syst. Video Technol. 21(9), 1214–1227 (2011)
Y. Nie, K.K. Ma, Adaptive rood pattern search for fast block-matching motion estimation. IEEE Trans. Image Process. 11(12), 1442–1449 (2002)
L.M. Po, W.C. Ma, A novel four-step search algorithm for fast block motion estimation. IEEE Trans. Circuits Syst. Video Technol. 6(3), 313–317 (1996)
R.K. Purwar, N. Rajpal, A fast block motion estimation algorithm using dynamic pattern search. SIViP 7(1), 151–161 (2013)
A.C. Tsai, K. Bharanitharan, J.F. Wang, K.I. Lee, Effective search point reduction algorithm and its VLSI design for HDTV H. 264/AVC variable block size motion estimation. IEEE Trans. Circuits Syst. Video Technol. 22(7), 981–988 (2012)
C.F. Tseng, Y.T. Lai, M.J. Lee, A VLSI architecture for three-step search with variable block size motion vector, in IEEE 1st Global Conference on Consumer Electronics (GCCE), 2012, pp. 628–631 (IEEE, 2012)
Y.L. Xi, C.-Y. Hao, Y.Y. Fan, H.Q. Hu, A fast block-matching algorithm based on adaptive search area and its VLSI architecture for H 264/AVC. Signal Process.: Image Commun. 21(8), 626–646 (2006)
S. Yao, H.J. Guo, L. Yu, K. Zhang, A hardware implementation for full-search motion estimation of AVS with search center prediction. IEEE Trans. Consum. Electron. 52(4), 1 (2006)
S.Y. Yap, J.V. McCanny, A VLSI architecture for variable block size video motion estimation. IEEE Trans. Circuits Syst. II Express Briefs 51(7), 384–389 (2004)
H. Yin, D.S. Park, X.Y. Zhang, Buffer structure optimized VLSI architecture for efficient hierarchical integer pixel motion estimation implementation. J. Real-Time Image Proc. 11(3), 507–525 (2016)
N. Yu, W. Jia, M. Gu, D. Wang, G. Xi, Y. Zheng, A high-performance configurable VLSI architecture for integer motion estimation in H. 264, in 2011 13th International Symposium onIntegrated Circuits (ISIC), pp. 55–58 (IEEE, 2011).
C. Zhu, X. Lin, L.P. Chau, Hexagon-based search pattern for fast block motion estimation. IEEE Trans. Circuits Syst. Video Technol. 12(5), 349–355 (2002)
S. Zhu, K.K. Ma, A new diamond search algorithm for fast block matching motion estimation, in Proceedings of 1997 International Conference on Information, Communications and Signal Processing, 1997, ICICS, vol. 1, pp. 292–296 (IEEE, 1997)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Mukherjee, R., Biswas, B. & Vinod, I.G. Half-Way Stop Adaptive Pattern Search Algorithm for Motion Estimation and Dedicated VLSI Architecture. Circuits Syst Signal Process 42, 1617–1638 (2023). https://doi.org/10.1007/s00034-022-02182-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00034-022-02182-5