Block-Matching Motion Estimation Algorithms for Video Processing and Compression: a Brief Overview

Abstract

Humanity created different methods for sharing information. One of the first forms of sharing information and knowledge were images. In the beginning, the process of sharing was relying on static appearances. With the invention of moving pictures by Eadweard Muybridge in the first part of 1870s, this exchange and sharing gained a new quality. Now it was possible to show and preserve motion too. Since that time, technology has changed rapidly. The latest discoveries and improvements from the point of view of technology use computer and IT technologies extensively. Today it is possible for everybody to create and record movies by themselves using affordable and convenient technological devices. 

 

Also the process of sharing evolved rapidly and become cheaper and cheaper. We are now able to record some movies and share them through the Internet or other carriers in real time or near real time. However, this also creates serious problems due to the huge volume of data to be sent through the data lines. Therefore, research has concentrated on methods to decrease the data volume without losing the quality. One way to do that is to create effective CODECs. A major drawback of moving pictures is the motion itself. CODECs have to minimize the size of videos without paying the price of quality losses but have also to reduce the computational complexity. Both of these requirements can be achieved with a solid knowledge of motion estimation among others. This paper gives a general overview and survey of some existing and important approaches without the claim of having a complete overview of the field.

 

References

1. Bovik, Al (ed.). (2000) “Video compression”, handbook of image and Video processing. 555-629, San Diego: Academic Press.
2. Chen, M., Li, G., Chiang, Y. & Hsu, C. (2006). Fast multiframe motion estimation algorithms by motion vector composition for the MPEG-4/AVC/H.264 standard. IEEE Trans. on Multimedia, 8(3), 478-487.
3. Chen, P.H., Chen, H.M, Hung, K.J., Fang, W.H., Shie, M. C. & Lai, F. (2006). Markov model fuzzy-reasoning based algorithm for fast block motion estimation. Journal of Visual Communication and Image Representation, 17(1), 131-142.
4. Hill, P. R., Chiew, T. K., Bull, D. R & Canagarajah, C. N. (2006). Interpolation free subpixel accuracy motion estimation. IEEE Trans. on Circuits and Systems for Video Technology, 16(12), 1519-1526.
5. Huang, S. & Tsai, W. (2004). A simple and efficient block motion estimation algorithm based on full-search array architecture. Signal Processing: Image Communication, 19(10), 975-992.
6. Khan, N.A., Masud, S. & Ahmad, A. (2006). A variable block size motion estimation algorithm for real-time H.264 video encoding. Signal Processing: Image Communication, 21(4), 306-315.
7. Kuo, T.Y. & Chan, C.H. (2006). Fast variable block size motion estimation for H.264 using likelihood and correlation of motion field. IEEE Trans. on Circuits and Systems for Video Technology, 16(10), 1185-1195.
8. Lee, Y.G. & Ra, J.B. (2006). Fast motion estimation robust to random motions based on a distance prediction. IEEE Trans. on Circuits and Systems for Video Technology, 16(7), 869-875.

9. Liang, Y., Ahmad, I., Luo, J., Sun, Y. & Swaminathan, W. (2005). On using hierarchical motion history for motion estimation in H.264/AVC. IEEE Trans. on Circuits and Systems for Video Technology, 15(12), 1594-1603.
10. Meiappane, A., Venkataesan, V. P. & Premanand, V. (2015). Security Enhancement in Shoulder Surfing Attacks using Passpoints for Random Similar Images (PRSIm). International Journal of Computer Networks and Applications (IJCNA), 2(2), 84-91.
11. Montrucchio, B. & Quaglia, D.(2005). New sorting-based lossless motion estimation algorithms and a partial distortion elimination performance analysis. IEEE Trans. on Circuits and Systems for Video Technology, 15(2), 210-220.
12. Namuduri, K. R. (2004). Motion estimation using spatio-temporal contextual information. IEEE Trans. on Circuits and Systems for Video Technology, 14(8), 1111-1115.
13. Po, L.M., Ting, C. W., Wong, K.M. & Ng, K. H. (2007). Novel point-oriented inner searches for fast block motion estimation. IEEE Trans. on Multimedia, 9(1), 9-15.
14. Richardson, I.E. (2002). Video CODEC design. New York: Wiley.
15. Richardson, I.E. (2003). H.264 and MPEG-4 video compression. NewYork: Wiley.
16. Tsai, T. & Pan, Y. (2006). A novel 3-D predict hexagon search algorithm for fast block motion estimation on H.264 video coding. IEEE Trans. on Circuits and Systems for Video Technology, 16(12), 1542-1549.
17. Tu, Y.K., Yang, J.F, Sun, M.T. & Tsai, Y.T. (2005). Fast variable-size block motion estimation for efficient H.264/AVC encoding. Signal Processing: Image Communication, 20(7), 595-623.
18. Yang, W. (2003). An efficient motion estimation method for MPEG-4 video encoder. IEEE Trans. on Consumer Electronics, 49(2), 441-446.
19. Zhou, Z., Xin, J. & Sun, M.T. (2006). Fast motion estimation and Inter-mode decision for H.264/MPEG-4 AVC encoding. Journal of Visual Communication and Image Representation, 17(2), 243-263.