Evaluation and Comparison of Motion Estimation Algorithms for Video Compression

Full Text (PDF, 538KB), PP.9-18

Views: 0 Downloads: 0


Avinash Nayak 1,* Bijayinee Biswal 1 S. K. Sabut 2

1. Ajay Binay Institute of Technology, Odisha, India

2. M.S. Ramaiah Institute of Technology, Bangalore, India

* Corresponding author.

DOI: https://doi.org/10.5815/ijigsp.2013.10.02

Received: 5 Apr. 2013 / Revised: 16 May 2013 / Accepted: 27 Jun. 2013 / Published: 8 Aug. 2013

Index Terms

Video Compression, Motion Estimation, Full Search Algorithm, Adaptive, Rood Pattern Search, Peak Signal to Noise Ratio


Video compression has become an essential component of broadcast and entertainment media. Motion Estimation and compensation techniques, which can eliminate temporal redundancy between adjacent frames effectively, have been widely applied to popular video compression coding standards such as MPEG-2, MPEG-4. Traditional fast block matching algorithms are easily trapped into the local minima resulting in degradation on video quality to some extent after decoding. In this paper various computing techniques are evaluated in video compression for achieving global optimal solution for motion estimation. Zero motion prejudgment is implemented for finding static macro blocks (MB) which do not need to perform remaining search thus reduces the computational cost. Adaptive Rood Pattern Search (ARPS) motion estimation algorithm is also adapted to reduce the motion vector overhead in frame prediction. The simulation results showed that the ARPS algorithm is very effective in reducing the computations overhead and achieves very good Peak Signal to Noise Ratio (PSNR) values. This method significantly reduces the computational complexity involved in the frame prediction and also least prediction error in all video sequences. Thus ARPS technique is more efficient than the conventional searching algorithms in video compression.

Cite This Paper

Avinash Nayak, Bijayinee Biswal, S. K. Sabut,"Evaluation and Comparison of Motion Estimation Algorithms for Video Compression", IJIGSP, vol.5, no.10, pp.9-18, 2013. DOI: 10.5815/ijigsp.2013.10.02


[1]Tekalp A. Digital video processing, Prentice Hall, PTR, 1995.

[2]Richardson I.G. H.264 and MPEG-4 video compression. Wiley, Chichester, England, 2003.

[3]Jain J. and Jain, A. Displacement Measurement and its Application in Interframe Image Coding. IEEE Trans on Communication, COM- 29, 1981: 1799-1808.

[4]Ning-ning, S., Chao, F., Xu, X. An Effective Three-step Search Algorithm for Motion Estimation. IEEE Int Symposium on IT in Medicine & Education, 2009:400- 403.

[5]Netravali A.N. and Robbins J.D. Motion compensated television coding: Part I.‖ Journal of Bell Syst Technical, 1979, 58: 631-670.

[6]Lin Y.C. and Tai S.C. Fast Full-Search Block-Matching Algorithm for Motion- Compensated Video Compression. IEEE Trans on Communications, 1997, 45(5): 527-531.

[7]CCITT SG XV. Recommendation H.261-Video codec for audiovisual services at p*64 kbits/s. Tech. Rep. COM XV-R37-E, 1990.

[8]MPEG ISO CD 11172-2: Coding of moving pictures and associated audio for digital storage media at up to about 1.5 M bits/s, 1991.

[9]Kappagantula S. and Rao K.R. Motion compensated interframe image Prediction. IEEE Trans Commun. COM, 1985, 33: 1011-l015.

[10]Ahmed Z., Hussain, A. J. and Al-Jumeily D. Fast Computations of Full Search Block Matching Motion Estimation (FCFS). IEEE Trans on Communications, 2011: 1-6.

[11]Reoxiang L., Bing Z. and Liou M.L. A new three-step search algorithm for block motion estimation. IEEE Trans on Circuits and Systems for Video Technology,1994, 4: 438-442.

[12]Barjatya A. Block Matching Algorithms for Motion Estimation. DIP 6620 Final Project Paper, 2004.

[13]Cheung C.H and Po L.M. A novel cross-diamond search algorithm for fast block motion estimation. IEEE Trans Circuits Syst Video Technol, 2002, 12: 1168- 1177.

[14]Zhu S. and Ma K.K. A new diamond search algorithm for fast block-matching motion estimation. Proc Int Conf Information Communications and Signal Processing (ICICS), 1997, 9(1): 292–296.

[15]Zhu S. Fast motion estimation algorithms for video coding. M.S. thesis, School Elect Electron Eng, Nanyang Technol Univ, Singapore, 1998.

[16]Zhu S. and Ma K.K. A New Diamond Search Algorithm for Fast Block Matching Motion Estimation. IEEE Trans on Image Processing, 2000, 9(2): 287-290.

[17]Shen J.F., Chen L.G., Chang H.C., Wang T.C. Low power full-search block matching motion estimation chip for H.263+. IEEE International Symposium on Circuits and Systems, 1999, 4:299-302.

[18]Nie Y. and Ma K.K. (2002). Adaptive rood pattern search for fast block-matching motion estimation. IEEE Trans Image Processing, 2002, 11 :1442-1448.

[19]Kaushik M. Comparative Analysis of Exhaustive Search Algorithm with ARPS Algorithm for Motion Estimation. International Journal of Applied Information Systems (IJAIS), 2012: 1(6), 16-19.

[20]Kiran S.V., Prasad K.V., Lalitha N.V. and Rao D.S. Architecture for the ARPS Algorithm. International Journal of Advances in Computer Networks and its Security, 2002: 443-448.