Abstract
Motion estimation accounts for major part of the computational complexity of any video coding standard. In this paper, we present efficient VLSI architecture for the implementation of hexagonal search algorithm for fast motion estimation. The proposed architecture employs sequential processing of pixel data rather than parallel processing in order to reduce the hardware area substantially while achieving the real-time speed. A novel on-chip memory organization is proposed, which reduces the address generation complexity and helps improve the speed. The architecture when implemented in Verilog HDL and mapped to Virtex-5 FPGA achieves a maximum frequency of 340 MHz, while the gate count is calculated to be 3.1 K. Thus, the proposed architecture is considered suitable to be incorporated in commercial devices such as camcorders and smart phones.
Similar content being viewed by others
References
A. Akin, M. Cetin, Z. Ozcan, B. Erbagci, I. Hamzaoglu, An adaptive bilateral motion estimation algorithm and its hardware architecture. IEEE Trans. Consum. Electron. 58(2), 712–720 (2012)
M. Cetin, I. Hamzaoglu, An adaptive true motion estimation algorithm for frame rate conversion of high definition video and its hardware implementation. IEEE Trans. Consum. Electron. 57(2), 923–931 (2011)
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 Proceeding of IEEE International Symposium on Circuits and Systems(ISCAS’02), vol. 2, 2002, pp. 492–495
S.K. Chatterjee, I. Chakrabarti, Low power vlsi architecture for 1-bit transformation based fast motion estimation. IEEE Trans. Consum. Electron. 56(4), 2652–2660 (2010)
S.K. Chatterjee, I. Chakrabarti, Power efficient motion estimation algorithm and architecture based on pixel truncation. IEEE Trans. Consum. Electron. 57(4), 1782–1790 (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, pp. 1–4
R. El-Ashry, M. Rehan, H. El-Kamchouchi, F. Gebali, Performance-optimized fpga implementation for the flexible triangle search block-based motion estimation algorithm, in Proceeding of IEEE Canadian Conference on Electrical and Computer Engineering (CCECE’11), 2011, pp. 640–643
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 vol. 2, 1995, pp. 1228–1231
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, L.G. Chen, 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), 728–733 (2009)
T. Koga, K. Linuma, A. Hirano, T. Ishiguro, Motion-compensated inter frame coding for video conferencing, in Proceedings of National Telecommunications Conference (NTC’81), 1981, pp. 3–5
Y. Lai, L.F. Chen, S.Y. Huang, Hybrid parallel motion estimation architecture based on fast top-winners search algorithm. IEEE Trans. Consum. Electron. 56(3), 1837–1842 (2010)
P. Lakamsani, B. Zeng, M. Liou, An enhanced three step search motion estimation method and its vlsi architecture, in Proceeding of IEEE International Symposium on Circuits and Systems (ISCAS’96), vol. 2, 1996, pp. 754–757
R. Mukherjee, K. Sheth, A.S. Dhar, I. Chakrabarti, S. Sengupta, High performance vlsi architecture for three-step search algorithm. Circuits Syst. Signal Process. 34(5), 1595–1612 (2015)
M. Muzammil, I. Ali, M. Sharif, K.A. Khalil, An Efficient FPGA Architecture for Hardware Realization of Hexagonal Based Motion Estimation Algorithm, in Proceedings of International Conference on Consumer Electronics, 2015, pp. 422-423
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)
C.M. Ou, C.F.L. Le, W.J. Hwang, An efficient vlsi architecture for h.264 variable block size motion estimation. IEEE Trans. Consum. Electron. 51(4), 1291–1299 (2005)
M. Rehan, M. El-Kharashi, P. Agathoklis, F. Gebali, An fpga implementation of the flexible triangle search algorithm for block based motion estimation, in Proceeding of IEEE International Symposium on Circuits and Systems (ISCAS’06), 2006, pp. 521–524
I.E. Richardson, Video Codec Design: Developing Image and Video Compression Systems (John Wiley & Sons, New York, 2002)
M. Sarma, D. Samanta, A.S. Dhar, Vlsi architecture for multi-resolution three step search algorithm, in Proceedings of IEEE 5th International Conference on ASIC, vol. 2, 2003, pp. 918–921
O. Tasdizen, A. Akin, H. Kukner, I. Hamzaoglu, H.F. Ugurdag, High Performance Hardware Architectures for a Hexagon-Based Motion Estimation Algorithm, in Proceedings of 16th IEEE / IFIP International Conference on VLSI—SoC (2008)
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), 1214–1227 (2012)
C.F. Tseng, Y.T. Lai, M.J. Lee, A vlsi architecture for three-step search with variable block size motion vector, in Proceedings of IEEE 1st Global Conference on Consumer Electronics (GCCE’12), 2012, pp. 628–631
Y.L. Xi, C.Y. Hao et al., A fast block-matching algorithm based on adaptive search area and its vlsi architecture for h.264/avc. Signal Process.: Image Commun. 21, 407–416 (2006)
S. Zhu, X. Lin, 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. IEEE Trans. Image Process. 9(2), 287–290 (2000)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mukherjee, R., Biswas, B., Chakrabarti, I. et al. Speed-Area Optimized VLSI Architecture of Hexagonal Search Algorithm for Motion Estimation of \(512 \times 512\) Frames. Circuits Syst Signal Process 36, 640–657 (2017). https://doi.org/10.1007/s00034-016-0315-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00034-016-0315-6