Call for Paper - March 2023 Edition
IJCA solicits original research papers for the March 2023 Edition. Last date of manuscript submission is February 20, 2023. Read More

Survey on Block Matching Algorithms for Motion Estimation

Print
PDF
International Journal of Computer Applications
© 2012 by IJCA Journal
Volume 46 - Number 16
Year of Publication: 2012
Authors:
Chittaranjan Pradhan
Dipannita Adak
10.5120/6991-9406

Chittaranjan Pradhan and Dipannita Adak. Article: Survey on Block Matching Algorithms for Motion Estimation. International Journal of Computer Applications 46(16):6-10, May 2012. Full text available. BibTeX

@article{key:article,
	author = {Chittaranjan Pradhan and Dipannita Adak},
	title = {Article: Survey on Block Matching Algorithms for Motion Estimation},
	journal = {International Journal of Computer Applications},
	year = {2012},
	volume = {46},
	number = {16},
	pages = {6-10},
	month = {May},
	note = {Full text available}
}

Abstract

Motion estimation technique is the most vital component of any video coding standard. Therefore, development of an efficient method for fast motion estimation is the basic requirement of the video encoder design. Block based motion estimation algorithms are used to reduce the memory requirements of any video file and also decrease computational complexity. Motivated by the specific requirements of motion estimation, a variety of algorithms have been developed. In this paper, we have discussed the commonly used motion estimation algorithms such as- Full Search (FS), Three-Step Search (TSS), New Three-Step Search (NTSS), Four-Step Search (FSS), Diamond Search Algorithm (DS), and Hexagon Based Search Algorithm (HEXBS). We have also analyzed these techniques by using Peak Signal to Noise Ratio (PSNR) values

References

  • Renxiang Li, Bing Zeng, and Ming L. Liou, "A New Three-Step Search Algorithm for Block Motion Estimation", IEEE Transactions on Circuits and Systems for Video Technology, Vol. 4, No. 4, pp. 438-442, August 1994.
  • Lai-Man Po, Wing-Chung Ma, "A Novel Four-Step Search Algorithm for Fast Block Motion Estimation" , IEEE Transactions on Circuits and Systems for Video Technology, Vol. 6, No. 3, page 313-317, June 1996.
  • Jo Yew Tham, Surendra Ranganath, Maitreya Ranganath, and Ashraf Ali Kassim, "A Novel Unrestricted Center-biased Diamond Search Algorithm for Block Motion Estimation", IEEE Transactions on Circuits and Systems for Video Technology, Vol. 8, No. 4, pp. 369-377, August 1998.
  • Ce Zhu, Xiao Lin, Lap-Pui Chau, Keng-Pang Lim, Hock-Ann Ang, Choo-Yin Ong, "A Novel Hexagon-Based Search Algorithm for Fast Block Motion Estimation ", IEEE, pp. 1593-1596, 2001.
  • Ce Zhu, Xiao Lin, and Lap-Pui Chau, "Hexagon-Based Search Pattern for Fast Block Motion Estimation", IEEE Transactions on Circuits and Systems for Video Technology, Vol. 12, No. 5, pp. 349-355, May 2002.
  • Aroh Barjatya, "Block-Matching Algorithms For Motion Estimation", DIP 6620 Spring 2004 Final Project Paper.
  • S. Immanuel Alex Pandian, Dr. G. Josemin Bala, Becky Alma George,"A Study on Block Matching Algorithms for Motion Estimation", International Journal on Computer Science and Engineering (IJCSE), Vol. 3, No. 1, pp. 34-44, Jan 2011.
  • D. V. Manjunatha, Dr. Sainarayanan, "Comparison and Implementation of Fast Block Matching Motion Estimation Algorithms for Video Compression", International Journal of Engineering Science and Technology (IJEST), Vol. 3, No. 10, pp. 7608-7613, October 2011.
  • John Watkinson, "The MPEG Handbook", 2nd Edition, Chapter 5, Elsevier Ltd. 2004, pp. 230-352.
  • PSNR calculating formula. Available at http://www. chasanc. com/index. php/Coding/PSNR-Calculating-Difference. html.