Hardware Design of Hexagonal Search Algorithm | ||
| Menoufia Journal of Electronic Engineering Research | ||
| Article 3, Volume 20, Issue 2, July 2010, Pages 171-183 | ||
| Document Type: Original Article | ||
| DOI: 10.21608/mjeer.2010.66515 | ||
| Authors | ||
| Imbaby I. Mahmoud1; Sherief M. Hashimaa1; Atef A. Elazm2 | ||
| 1Eng. Dept, NRC, Atomic Energy Authority, Inshas, Egypt. | ||
| 2Faculty of Electronic Engineering, Menoufiya University, Menouf, Egypt | ||
| Abstract | ||
| Motion Estimation (ME) is vital element in video coding as it reduces temporal redundancy. Given that the motion estimation stage is very complex in terms of computational effort, a hardware implementation on a reconfigurable circuit is crucial for the requirements of different real time multimedia applications. Hexagonal search algorithm is one of Fast Block Matching Algorithms (FBMAs) which belongs to block based motion estimation. This paper presents a hardware design of hexagonal search algorithm and its implementation on FPGA. We specified, simulated and synthesized the design with VHDL description. The proposed design is implemented on a "virtex5" FPGA using xc5vlx30-3ff676 component. Our simulations confirm the functionality of the algorithm using Modelsim (version XE 6.3.4) simulator. When our design was synthesized on xc5vlx30-3ff676, we obtained the following results for area and clock frequency: 6810 LUT and 65,892MHz respectively. | ||
| Keywords | ||
| Motion Estimation (ME); HEXagonal Based Search algorithm (HEXBS); Fast Block Matching Algorithm (FBMA); Sum Absolute Difference (SAD); Processing Element (PE) | ||
| References | ||
|
[1] H.Loukil, F.Ghozzi, A.Samet, M.A.Benayed, and N.Masmoudi, "Hardware Implementation of Block Matching Algorithm with FPGA Technology", the proceedings of the 16thICM Conf, pp.542-546, Tunis, TUNISIA, December, 2004.
[2] Baek,Oh, and Lee,"an efficient block matching criterion for motion estimation and its VLSI implementation", IEEE, KOREA,1996.
[3] G.Robert, "Reoresentation of codage de sequences video par hybridation de fractals et d' elements finis", these/Phd, NPG, Grenoble, Dec, 2000.
[4] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion Compensated Interframe Coding for Video Conferencing”, in Proc. Nat. Telecommunication Conf, pp. G5.3.1–G5.3.5., 1981.
[5] J. R. Jain and A. K. Jain, “Displacement measurement and its application in Inter frame image coding,” IEEE Trans. Commun, vol. 29, pp.1799-1808, Dec. 1981.
[6] M. Ghanbari, “The cross search algorithm for motion estimation,” IEEE Trans. Commun., Vol. COM-38, pp. 950-953, Jul. 1990.
[7] R.li,B.zeng,and M.L.liou,"A New Three –Step search algorithm for block motion eatimation", IEEE trans on circuits and systems for video technology, vol 4.August, 1994.
[8] L. M. Po and W. C. Ma, “A novel four-step search algorithm for fast block Motion estimation,” IEEE Trans,Circuits Syst. Video Technol., vol. 6, pp. 313– 317, June 1996.
[9] Shan Zhu, and Kai-Kuang Ma, “A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation”, IEEE Trans. Image Processing, vol 9,no.2, pp. 287-290, February. 2000.
[10] C. Zhu, X. Lin, and L. P. Chau, “Hexagon-Based Search Pattern For Fast Block Motion Estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 5, pp. 349–355, May 2002.
[11] L. K. Liu and E. Feig, “A block-based gradient descent search algorithm for block Motion estimation in video coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp. 419–423, August. 1996.
[12] L.Man Po, C.W.Ting and Ka-Ho Ng,” Enhanced Diamond Search Using Four-Corner-Based Inner Search For Fast Block Motion Estimation", IEEE, 2006.
[13] J.Song, B.Li, D.Jiang, and C.Wang ,” Large Diamond and Small Pentagon Search Patterns for Fast Motion Estimation” ICNC 2006, Part II, pp. 608 – 616, 2006. Springer-VerlagBerlin Heidelberg 2006.
[14] T.G.Venkatesh and S.strinivasan, "A pruning based Fast Rate Control Algorithm for MPEG Coding",ICCIMA, INDIA,pp.403-407,1999.
[15] Rajesh T.N Rajram, "Optimization of Fast Search Block Matching Motion Estimation Algorithms and Their VLSI Implementation", thesis work for the degree of master of science (by research),Department of electrical engineering, Indian institute of Technology ,Madras,June,1999.
[16] S.Ramachandran, S.Srinivasan, "FPGA Implementation of a Novel Fast Motion Estimation Algorithm for Real-Time Video Compression", FPGA 2001, pp.213-219,California,USA,February,2001.
[17] S.Y.Huang, C.Y.Cho, and J.S.Wang, "Adaptive Fast Block –Matching Algorithm by Switching Search Patterns for Sequences With Wide-Range Motion Content" ,IEEE trans on circuits and systems for video technology, Vol. 15,No.11.November 2005.
[18] R.Iqbal, "Hardware bidirectional real time motion estimator on a Xilinix Virtex ΠProFPGA", M.SC, Technical university, Braunscheig, Germany. April, 2006.
[19] NA KA HO ,"Highly Efficient Motion Estimation Algorithms in Video Coding", M.SC thesis ,City University Of HONG KONG, March 2008.
[20] Bo-Sung Kim* and Jun-Dong Cho, VLSI Architecture for Low Power Motion Estimation using High Data Access Reuse, IEEE conference on ASIC, Asia pacific,1999.
[21] C. Sanz, M. J. Garrido and J. M. Meneses, "VLSI Architecture for Motion Estimation using the Block-Matching Algorithm", Proceedings of the European Design & text cnference, 1996. | ||
|
Statistics Article View: 139 |
||
