Call for Paper - November 2022 Edition
IJCA solicits original research papers for the November 2022 Edition. Last date of manuscript submission is October 20, 2022. Read More

Performance Analysis of Fast Block Matching Motion Estimation Algorithms

Print
PDF
International Journal of Computer Applications
© 2015 by IJCA Journal
Volume 122 - Number 6
Year of Publication: 2015
Authors:
Nasir Mahmud Khokhar
Wail Harasani
10.5120/21704-4817

Nasir Mahmud Khokhar and Wail Harasani. Article: Performance Analysis of Fast Block Matching Motion Estimation Algorithms. International Journal of Computer Applications 122(6):15-20, July 2015. Full text available. BibTeX

@article{key:article,
	author = {Nasir Mahmud Khokhar and Wail Harasani},
	title = {Article: Performance Analysis of Fast Block Matching Motion Estimation Algorithms},
	journal = {International Journal of Computer Applications},
	year = {2015},
	volume = {122},
	number = {6},
	pages = {15-20},
	month = {July},
	note = {Full text available}
}

Abstract

Motion Estimation (ME) is an integral part of any video encoder and a large number of Block Matching Motion Estimation (BMME) Algorithms are proposed to cope the computational complexity and increase quality of ME process requirement. Therefore, it is necessary to evaluate the performance of these ME algorithms for different motion activities. In this paper five fast famous BMME algorithms are considered to evaluate their performance on the basis of ME time, search points, PSNR and Means Square Error (MSE). The algorithms evaluated in this paper are considered for state of the art video compression standards like MPEG 1, to MPEG4 and H. 261 to H. 264. Results show that the PSNR of Diamond Search (DS) is best for all test video sequences, whereas, Hardware Modified DS takes maximum number of search points to calculate motion vector. Moreover, hexagon search algorithm takes minimum number of search points but its PSNR is considerably lower than the other algorithms.

References

  • I. Ali, M. Muzammil and G. Raja, 2012 "performance analysis of motion estimation algorithms based on motion activity in video sequences" Pakistan Journal of Science Vol. 64 No. , pp no. 39-45
  • I. Ali, G. Raja, M. Muzammil; A. K. Khan, 2014 "Adaptive Modified Hexagon Based Search Motion Estimation algorithm," 2014 IEEE Fourth International Conference on Consumer Electronics Berlin (ICCE-Berlin), pp. 147-148.
  • A. Ahmadi, M. M. Azadfar, 2008 "Implementation of fast motion estimation algorithms and comparison with full search method in H. 264" IJCSNS International Journal of Computer Science and Network Security, Vol. 8 No. 3, pp 139-143.
  • Multimedia Processing, Video Coding and Motion Estimation (module 7, Lesson 21) IIT Kharagpur course material, available on-line at, http://nptel. iitm. ac. in/courses/Webcourse-contents/IIT Kharagpur/Multimedi Processing/pdf/ssg_m7l21. pdf
  • Aroh Barjatya, 2004 "Block Matching Algorithms for Motion Estimation". DIP 6620, Final project paper.
  • S. Radicke, J. -U. Hahn, Wang Qi and C. Grecos, 2014, "Bi-predictive motion estimation for HEVC on a graphics processing unit (GPU)," IEEE Transactions on Consumer Electronics, vol. 60, no. 4, pp. 728-736.
  • S. R. Subramanya Hiral Patel Ilker Ersoy, 2004, "Performance Evaluation of Block-Based Motion Estimation Algorithms and Distortion Measures" IEEE Int. Conf. Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'04). Vol. 2 , pp. 2-7.
  • R. A. Manap, S. S. S. Ranjit, A. A. Basari, and B. H. Ahmad, 2010, "Performance Analysis of Hexagon-Diamond Search Algorithm for Motion Estimation" IEEE Int. Conf. Computer Engineering and Technology (ICCET) Vol. 3, pp no. V3-155 - V3-159.
  • T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, 1981, "Motion compensated inter frame coding for video conferencing," in Proc. NTC 81, pp. C9. 6. 1-9. 6. 5, New Orleans, LA.
  • Renxiang Li, Bing Zeng, and Ming L. Liou, 1994, "A New Three-Step Search Algorithm for Block Motion Estimation" IEEE Transactions on Circuits and Systems for Video Technology, Vol. 4, No. 4.
  • Jianhua Lu and Ming L. Liou, 1997, "A Simple and Efficient Search Algorithm for Block-Matching Motion Estimation" IEEE Transactions on Circuits and Systems for Video Technology, Vol. 7, No. 2, pp no 429-433.
  • Lai-Man Po, and Wing-Chung Ma, 1996, "A Novel Four-Step Search Algorithm for Fast Block Motion Estimation", IEEE Trans. Circuits and Systems for Video Technology, Vol. 6, no. 3, pp. 313-317.
  • Shan Zhu, and Kai-Kuang Ma, 2000, "A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation", IEEE Trans. Image Processing, vol 9, no. 2, pp. no. 287-290.
  • G. Sanchez, D. Noble, M. Porto and L. Agostini, 2011, "A Real-Time HDTV Motion Estimation Architecture for the New MPDS Algorithm," in EUROCON International conference on computer as a tool, Lisbon.
  • Yao Nie, and Kai-Kuang Ma, 2002, "Adaptive Rood Pattern Search for Fast Block-Matching Motion Estimation", IEEE Trans. Image Processing, vol. 11, no. 12, pp. 1442-1448.
  • Chun-Ho Cheung, and Lai-Man Po, 2002, "A Novel Cross-Diamond Search Algorithm for Fast Video Coding and Video Conferencing Applications", IEEE Transactions on Circuits and Systems for Video Technology, Vol. 12, No. 12, pp 1168-1177.
  • Efficient Architecture for Variable block size Motion Estimation of H. 264 Video Encoder, 2012, International Conference on Solid-State and Integrated Circuit (ICSIC 2012) IPCSIT vol. 32, IACSIT Press, Singapore
  • Ljubomir Jovanov, Aleksandra Pi?zurica, Stefan Schulte, 2009, "Combined Wavelet-Domain and Motion-Compensated Video Denoising Based Video Codec Motion Estimation Methods" IEEE transactions on circuits and systems for video technology, Vol. 19, No. 3.
  • Vasiljevic, J. ; Ye, A. G. , 2012, "Effect of scaling on the area and performance of the H. 264/AVC full-search fractional motion estimation algorithm on field-programmable gate arrays," IET. Computers & Digital Techniques, vol. 6, no. 2, pp. 95-104.
  • Coding of moving pictures and audio, 1999, ISO/IEC JTC1/SC29/WG11N2932.
  • Sourabh Rungta, Dr. Neeta Tripathi and Prof Anupam Shukla, 2011, "Hexagonal Based Search Pattern for Motion Estimation in H. 264/AVC," World of Computer Science and Information Technology Journal (WCSIT), vol. 1, no. 2221-0741, pp. 162- 166.
  • Ce Zhu, Xiao Lin, Lap-Pui Chau, Keng-Pang Lim, Hock-Ann Ang, Choo-Yin Ong, 2001, "A Novel Hexagon-Based Search Algorithm for Fast Block Motion Estimation" IEEE Conference on Acoustics, Speech, and Signal Processing vol. 3 pp no. 1593-1596.
  • Ce Zhu, Xiao Lin, and Lap-Pui Chau, 2002, "Hexagon-Based Search Pattern for Fast Block Motion Estimation" IEEE Transactions on Circuits and Systems for Video Technology, Vol. 12, NO. 5, pp no 340-355.
  • Thou-Ho Chen, Yi-Fan Li, 2004, "A novel flatted hexagon search pattern for fast block motion estimation" International Conference on Image Processing, (ICIP 2004), vol. 3, no. , pp. 1477-1480 Vol. 3, 24-27.
  • Available online at: https://media. xiph. org/video/derf/
  • G. Raja, M. J. Mirza and T. Song, 2008, H. 264/AVC deblocking filter based on motion activity in video sequences. IEICE Electronics Express J. , 5:809-814.