Logo PTI
Polish Information Processing Society
Logo RICE

Annals of Computer Science and Information Systems, Volume 10

Proceedings of the Second International Conference on Research in Intelligent and Computing in Engineering

An Overview of Block Matching Algorithms for Motion Vector Estimation

, , ,

DOI: http://dx.doi.org/10.15439/2017R85

Citation: Proceedings of the Second International Conference on Research in Intelligent and Computing in Engineering, Vijender Kumar Solanki, Vijay Bhasker Semwal, Rubén González Crespo, Vishwanath Bijalwan (eds). ACSIS, Vol. 10, pages 217–222 ()

Full text

Abstract. In video compression technique, motion estimation is one of the key components because of its high computation complexity involves in finding the motion vectors (MV) between the frames. The purpose of motion estimation is to reduce the storage space, bandwidth and transmission cost for transmission of video in many multimedia service applications by reducing the temporal redundancies while maintaining a good quality of the video. There are many motion estimation algorithms, but there is a trade-off between algorithms accuracy and speed. Among all of these, block-based motion estimation algorithms are most robust and versatile. In motion estimation, a variety of fast block based matching algorithms has been proposed to address the issues such as reducing the number of search/checkpoints, computational cost, and complexities etc. Due to its simplicity, the block-based technique is most popular. Motion estimation is only known for video coding process but for solving real life applications many researchers from the different domain are attracted towards block matching algorithms for motion vector estimation.This paper is a review of various block matching algorithms based on shapes and patterns as well as block matching criteria used for motion estimation.

References

  1. S. Kamble, N. Thakur, L. Malik, P. Bajaj, “Color video compression based on fractal coding using quad-tree weighted finite automata,” Information system design and intelligent application, Proceedings of Second International Conference INDIA 2015, volume 2, advances in intelligent system and computing, Springer India, volume 340, pp. 649-658, 2015.
  2. S. Kamble, N. Thakur, L. Malik, P. Bajaj, “Quad-Tree Partitioning and Extended Weighted Finite Automata Based Fractal Color Video Coding,” Int. J. Image Mining, vol. 2, no. 1, pp. 31-56, 2016.
  3. H. Surrah and M. Haque, “A Comparative Approach for Block Matching Algorithms used for Motion Estimation,” IJCSI, volume 11, no. 3, pp. 562-568, 2014.
  4. E. Chan and S. Panchanathan, “Review of Block Matching Based Motion Estimation Algorithms for Video Compression, International Journal of Scientific & Engineering Research, vol. 1, no. 3, pp. 151-153, 1993.
  5. Aw. Hussain, L. Knight, D. Al-Jumeily, P. Fergus, and H. Hamdan, “Block Matching Algorithms for Motion Estimation–A Comparison Study”, International Journal of Scientific & Engineering Research, vol. 264, no. 2, pp. 356-369, 2014.
  6. S. Kamble, N. Thakur and P. Bajaj, “A Review on Block Matching Motion Estimation and Automata Theory based Approaches for Fractal Coding”, International Journal of Interactive Multimedia and Artifical Intelligence, volume 4, no.2, pp.91-104, 2016.
  7. T. Koga, K. Iinuma, “Motion Compensated Inter frame Coding for Video Conferencing,” in proceedings of the NTC, pp. 230-236, 1981.
  8. R. Li, B. Zeng, and M. L. Liou,“A new Three-Step Search Algorithm for Block Motion Estimation,”IEEE Trans .on Circuits and Systems for Video Technology,volume 4, no. 4, pp. 438-442.
  9. Xuan Jing and Chau Lap-Pui, “An Efficient New Three-Step Search algorithm for block motion estimation,” IEEE Transactions on multimedia, vol. 6, no.3, pp. 435-438, 2004.
  10. L. Po and W. 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, pp. 313-317, 1996.
  11. D. Xu, C. Bailey and R. Sotudeh, “An Improved Three Step Search Block Matching Algorithm for Low Bit Rate Video Coding Applications,” International Symposium on Signals, Systems, & Electronics Conference in proceedings of Pisa, no. 10,pp. 178-181, 1998.
  12. Humaira Nisar and T. Choi, “An Advanced Center Biased Three Step Search Algorithm for Motion Estimation,” IEEE International Conference on Multimedia and Expo in proceedings of Latest Advances in the Fast Changing World of Multimedia, vol. 1, no. 10, pp. 95-98, 2000.
  13. N. Verma, T. Sahu and P. Sahu, “Efficient Motion Estimation by Fast Three Step Search Algorithms,”International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering, volume 1, no. 5, pp. 380-385, 2012.
  14. JianhuaLuandMingL.Liou,“ASimple and Efficient Search Algorithm for Block-Matching Motion Estimation,” IEEE Transactions onCircuits and Systems for Video Technology, volume 7, no. 2, pp. 429-433, 1997.
  15. S. Zhu and K. Ma, “A new Diamond Search Algorithm for Fast Block Matching Motion Estimation,” IEEE Transaction on Image Processing, vol. 9, no. 2, pp. 287-290, 2000.
  16. C. Hong and L. M. Po, “ A Novel Small-Cross-Diamond Search Algorithm for Video Coding and Videoconferencing Applications,” IEEE Trans. on Circuits and Systems for Video Technology, volume 12, no. 12, pp. 681-684, 2002.
  17. YunCheng,Xine You,MinlianXiao,“A Modified Diamond Search Algorithm,” IEEE International Symposium on IT in Medicine & Education, Cuangzhou, pp. 481-485, 2011.
  18. K. Singh and S. Ahamed, “Modified Small-Cross Diamond Search Motion Estimation Algorithm for H.264/AVC,” IEEE India Conference, pp. 1-5, 2013.
  19. Y. Nie, “Adaptive Rood Pattern Search for Fast Block-Matching Motion Estimation,” IEEETransactions on Image Processing, vol. 11, no. 12, pp. 1442-1448, 2002.
  20. C. Cheung and L. Po, “Normalized Partial Distortion Search Algorithm for Block Motion Estimation,” IEEE Trans. on Circuits and Systems for Video Technology, volume 10, no. 3, pp. 417-422, 2000.
  21. Ce Zhu, Xiao Lin , Lap-Pui Chau ,Keng-PangLim , Hock-Ann Ang Choo-Yin Ong, “A novel hexagon-based search algorithm for fast block motion estimation” IEEE International Conference Acoustics, Speech, and Signal Processing Proceedings. (ICASSP '01), 2001.
  22. Li Hong-ye “Cross-Hexagon-based motion estimation algorithm using motion vector adaptive search technique,” IEEE transaction 978-1-4244-5668, 2009.
  23. CE Zhu, Xiao Lin, Lappui Chau &Lai Man Po “Enhanced hexagonal search for fast block motion Estimation,” IEEE Transaction on circuits &system for video technology volume 14, no. 10, 2004.
  24. Chorng-Yann Su, Yi-Pin Hsu, and Cheng-Tao Chang “Efficient Hexagonal Inner Search For Fast Motion Estimation” IEEE transaction on multimedia7803-9134-9 volume 4, 2005.
  25. Chun-Ho Cheung, Lai-Man Po, “Novel Cross-Diamond-Hexagonal Search Algorithms for Fast Block Motion Estimation,” IEEE Transactions on Multimedia, volume 7, no. 1, February, pp. 16-22, 2005.
  26. Kamel Belloulata, Shiping Zhu, and ZaikuoWang “A Fast Fractal Video Coding Algorithm Using Cross-Hexagon Search for Block Motion Estimation,” International Scholarly Research Network ISRN Signal Processing, Volume 2011, Article ID 386128, 2011.
  27. S. Kamble, N. Thakur, L. Malik and P. Bajaj, “Fractal Video Coding using Modified Three-Step Search Algorithm for Block Matching Motion Estimation,” Computational Vision & Robotics in Proceedings of International Conference on Computer Vision & Robotics, Advance in Intelligent Systems & Computing, volume 332, pp. 151-162, 2015.
  28. Han–Ting Lin & Jen Shiun Chiang “A new diamond Arch- Hexagon Search algorithm for fast block motion estimation “ IEEE International symposiumon signal processing and information Technology,pp.811-816, 2006.
  29. Dongkyun Park, Young Jang, and JongHwa Lee, “A new Fast Three Step Search Motion Estimation Algorithm in H.264,”IEEE transactions on circuits and systems for video technology,978-1-4244-3589 pp. 541-544, 2007.
  30. Mean-Hom Ho, Jan-Jun Huang, Shang-Chiang Chin and Chun-Lung Hsu “High Efficient NTSS-Based Parallel Architecture for Motion Estimation in H.264”IEEE transaction978-1-4244-2064, vol.3, pp. 679-683, 2008.
  31. Man F. So and Angus Wu “Four-Step Genetic Search for Block Motion Estimation”IEEE transaction0-7803-4428-6138, pp.1393-1396, 1998.
  32. Tsung-Han Tsai and Yu-Nan Pan, “A Novel 3-D Predict Hexagon Search Algorithm for Fast Block Motion Estimation on H.264 Video Coding,” IEEE transactions on circuits and systems for video technology, volume 16, no. 12, pp.1542 -1547, 2006.
  33. Obianuju Ndili and Tokunbo Ogunfunmi “Algorithm and Architecture Co-Design of Hardware-Oriented, Modified Diamond Search for Fast Motion Estimation in H.264/AVC,” IEEE Transactions on Circuits and Systems for Video Technology, volume 21, no. 9, 2011.
  34. S. Kamble, N. Thakur and P. Bajaj, “Modified Three-Step Block Matching Motion Estimation and Weighted Automata based Fractal video Compression”, International Journal of Interactive Multimedia and Artifical Intelligence, vol. 4, no.4, pp.27-39, 2017.