Efficient Block Matching Algorithm for Motion Estimation

Motion estimation is a key problem in video processing and computer vision. Optical flow motion estimation can achieve high estimation accuracy when motion vector is small. Three-step search algorithm can handle large motion vector but not very accurate. A joint algorithm was proposed in this paper to achieve high estimation accuracy disregarding whether the motion vector is small or large, and keep the computation cost much lower than full search.

Authors:

• Zong Chen

Keywords:

• Motion estimation
• Block Matching
• Optical flow
• Three step search.

References:

[1] J. R. Jain and A. K. Jain, "Displacement measurement and its application
in interframe image coding," IEEE Trans. Commun., Vol. COM-29, pp.
1799-1808, Dec. 1981.
[2] H. G. Musmann, P. Pirsch and H.-J. Grallert, "Advances in picture
coding," Proc. IEEE, Vol. 73, No. 4, pp. 523-548, 1985.
[3] V. Bashkaran and K. Konstantinides, "Image and video compression
standards: algorithms and architectures," Kluwer Academic Publishers,
1995.
[4] A. Murat Tekalp, "Digital video processing," Prentice-Hall, 1995.
[5] K. R. Rao and J. J. Hwang, "Techniques and standards for image, video
and audio Coding," Prentice-Hall, 1996.
[6] F. Dufaux and F. Moscheni, "Motion estimation techniques for digital
TV: A review and a new contribution," Proc. IEEE, Vol. 83, No. 6, June
1995.
[7] B. D. Lucas and T. Kanade, "An iterative image registration technique
with an application to stereo vision," in Proceedings of DARPA Image
Understanding, pp. 121-130, 1981.
[8] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, T. Ishiguro, "Motioncompensated
interframe coding for video conferencing," Proceedings
NTC'81 (IEEE), pp.5.3.1 - G.5.3.4
[9] A. Singh, "Optical flow: a unified perspective," IEEE Computer Society
Press, Loas Alamitos, CA, 1991.
[10] J.L. Barron, D.J. Fleet, and S.S. Beauchemin, "Performance of Optical
Flow Techniques," in International Journal of Computer Vision,
February 1994, vol. 12(1), pp. 43-77.
[11] P. Anandan, "A computational framework and an algorithm for the
measurement of visual motion," in International Journal of Computer
Vision, Vol. 2, pp. 283-310, January 1989.