New Enhanced Hexagon-Based Search Using Point-Oriented Inner Search for Fast Block Motion Estimation

Authors: Lai-Man Po, Chi-Wang Ting, Ka-Ho Ng

Abstract:

Recently, an enhanced hexagon-based search (EHS) algorithm was proposed to speedup the original hexagon-based search (HS) by exploiting the group-distortion information of some evaluated points. In this paper, a second version of the EHS is proposed with a new point-oriented inner search technique which can further speedup the HS in both large and small motion environments. Experimental results show that the enhanced hexagon-based search version-2 (EHS2) is faster than the HS up to 34% with negligible PSNR degradation.

Keywords: Inner search, fast motion estimation, block-matching, hexagon search

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330385

References:

[1] T. Koga, K. Iinuma, A. Hirano, Y. Iijima and T. Ishiguro, "Motion compensated interframe coding for video conferencing," in Proc. Nat. Telecommun, Conf.,NO, L.A., Nov-Dec 1981, pp. G5.3.1-G.5.3.5.
[2] 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.
[3] R. Srinivasan and K. R. Rao, "Predictive coding based on efficient motion estimation," IEEE Trans. Commun., vol. COM-33, pp. 888-896, Aug. 1985.
[4] R. Li, B. Zeng, and M. L. Liou, "A new three-step search algorithm for block motion estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 4, pp. 438-443, Aug. 1994.
[5] L. M. Po and W. C. Ma, "A novel four-step search algorithm for fast block motion estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp. 313-317, June 1996.
[6] L. K. Liu and E. Feig, "A block-based gradient descent search algorithm for block motion estimation in video coding," IEEE Trans. Circuits Syst. Video Technol., vol. 6, no. 4, pp. 419-422, Aug 1996.
[7] J. Y. Tham, S. Ranganath, M. Ranganath and A. A. Kassim, "A novel unrestricted center-biased diamond search algorithm for block motion estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 8, no. 4, pp. 369-377, Aug. 1998.
[8] C. H. Cheung and L. M. Po, "A novel cross-diamond search algorithm for fast block motion estimation", IEEE Trans, Circuits Syst. Video Technol., vol. 12, no. 12, Dec 2002.
[9] C. Zhu, X. Lin, and L. P. Chau, "Hexagon-based search pattern for fast block motion estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 12, pp.349-355, May 2002.
[10] C. Zhu, X. Lin, L. P. Chau, and L. M. Po, "Enhanced hexagonal search for fast block motion estimation," IEEE Trans. on Circuits and Systems for Video Technology, vol. 14, Issue 10, pp. 1210 - 1214, Oct. 2004.