A Fast Block-Matching Motion Estimation Method Based on Difference Search Algorithm

Abstract:

The diamond search (DS) algorithm is one of the most efficient block matching motion estimation algorithms by far and has already been applied in MPEG2/4. Through our research, we found that there is still some redundancy in the algorithm. In this paper, an improved new difference based search (DBS) algorithm is proposed. Simulation results demonstrate that the new algorithm outperforms the well-known diamond search (DS) algorithm and four step-searches (4SS). It obtains almost the same Peak Signal to Noise Ratio (PSNR) while requires less computations than the DS algorithm and 4SS algorithm.

• Periodical: Applied Mechanics and Materials (Volume 610)
• Pages: 686-694
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.610.686
• Online since: August 2014
• Authors: Chang Jiang Liu*, Chao Chen, A Fei Zhang, Xiao Lang Yan
• Keywords: Diamond Search, Difference Based Search, Matching Algorithm, Motion Estimation, Video Coding

References

[1] Jain, J., Jain, A., 1981. Displacement Measurement and Its Application in Interframe Image Coding, Communications, IEEE Transactions on, pp.1799-1808. [doi: 10. 1109/ TCOM. 1981. 1094950].

DOI: 10.1109/tcom.1981.1094950

[2] Xiaobing Lee, Ya-Qin Zhan, 1996. A fast hierarchical mo-tion-compensation scheme for video coding using block feature matching, Circuits and Systems for Video Tech-nology, IEEE Transactions on , pp.627-635. [doi: 10. 1109/76. 544734].

DOI: 10.1109/76.544734

[3] Lurng-Kuo Liu, Feig, E., 1996. A block-based gradient descent search algorithm for block motion estimation in video coding, Circuits and Systems for Video Technology, IEEE Transactions on , pp.419-422. [doi: 10. 1109/76. 510936].

DOI: 10.1109/76.510936

[4] Reoxiang Li, Bing Zeng, Liou, M.L., 1994. A new three-step search algorithm for block motion estimation, Circuits and Systems for Video Technology, IEEE Transactions on , pp.438-442. [doi: 10. 1109/76. 313138].

DOI: 10.1109/76.313138

[5] Lai-Man Po, Wing-Chung Ma , 1996. A novel four-step search algorithm for fast block motion estimation , Circuits and Systems for Video Technology, IEEE Transactions on , pp.313-317. [doi: 10. 1109/76. 499840].

DOI: 10.1109/76.499840

[6] Liu, B., Zaccarin, A., 1993. New fast algorithms for the esti-mation of block motion vectors, Circuits and Systems for Video Technology, IEEE Transactions on , pp.148-157. [doi: 10. 1109/76. 212720].

DOI: 10.1109/76.212720

[7] Puri, A., Hang, H. -M. Schilling, D., 1987. An efficient block-matching algorithm for motion-compensated coding, Acoustics, Speech, and Signal Processing, IEEE In-ternational Conference on ICASSP , pp.1063-1066.

DOI: 10.1109/icassp.1987.1169777

[8] Ghanbari, M., 1990. The cross-search algorithm for motion estimation [image coding], Communications, IEEE Transactions on , pp.950-953. [doi: 10. 1109/26. 57512].

DOI: 10.1109/26.57512

[9] Shan Zhu, Kai-Kuang Ma, 1997. A new diamond search al-gorithm for fast block matching motion estimation, In-formation, Communications and Signal Processing, 1997. ICICS., Proceedings of 1997 International Conference on, pp.292-296.

DOI: 10.1109/icics.1997.647106

[10] Ce Zhu, Xiao Lin, Lap-PuiChau, 2002. Hexagon-based search pattern for fast block motion estimation, Circuits and Systems for Video Technology, IEEE Transactions on , pp.349-355. [doi: 10. 1109/TCSVT. 2002. 1003474].

DOI: 10.1109/tcsvt.2002.1003474

[11] Julian Besag, Spatial Interaction and the Statistical Analysis of Lattice Systems, Journal of the Royal Statistical Society. Series B (Methodological) , Vol. 36, No. 2 (1974), pp.192-236.

DOI: 10.1111/j.2517-6161.1974.tb00999.x

[12] Chun-Ho Cheung, Lai-Man Po, 2002. A novel cross-diamond search algorithm for fast block motion estimation, Circuits and Systems for Video Technology, IEEE Transactions on , pp.1168-1177. [doi: 10. 1109/TCSVT. 2002. 806815].

DOI: 10.1109/tcsvt.2002.806815