INFORMATION CHANGE THE WORLD

International Journal of Image, Graphics and Signal Processing(IJIGSP)

ISSN: 2074-9074 (Print), ISSN: 2074-9082 (Online)

Published By: MECS Press

IJIGSP Vol.7, No.7, Jun. 2015

Multi Point Search Pattern for Fast Search Motion Estimation of High Resolution Video Coding

Full Text (PDF, 530KB), PP.60-68


Views:66   Downloads:0

Author(s)

Nehal N. Shah, Upena D. Dalal, Priyank H. Prajapati

Index Terms

Motion Estimation;Fast search block matching algorithm;Multi point search; H.265;HD video sequences

Abstract

Block matching algorithm (BMA) based motion estimation (ME) is most accepted method for removal of temporal redundancy between frames in video coding. With recent advancement in resolution of video, the need of search pattern covering most of macroblocks within search area in frame is increasing. Existing search patterns are tiny and take plenty of time to reach at edge or corner of the search window. With aim of covering nearly every probable candidate macroblocks in all direction and to speed up the search process, multipoint search patterns are presented in this paper. Initial candidate macroblocks are chosen on grid of 12x12 and then search progresses like traditional diamond or hexagon search. Due to multipoint, chances of trapping in incorrect direction is very less and method can exhibit better quality of encoding with optimum number of search points.

Cite This Paper

Nehal N. Shah, Upena D. Dalal, Priyank H. Prajapati,"Multi Point Search Pattern for Fast Search Motion Estimation of High Resolution Video Coding", IJIGSP, vol.7, no.7, pp.60-68, 2015.DOI: 10.5815/ijigsp.2015.07.07

Reference

[1]H. Standard, G. J. Sullivan, J. Ohm, W. Han, and T. Wiegand, "Overview of the High Efficiency Video Coding," vol. 22, no. 12, pp. 1649–1668, 2012.

[2]M. E. Rizkalla, P. Salama, M. El-sharkawy, and M. Sushmitha, "Hardware implementation of Block-based Motion Estimation for real time applications," J. VLSI Signal Process., pp. 139–159, 2007.

[3]J. Kim and T. Choi, "A fast Three-step search algorithm with minimum checking points unimodal error surface assumption," IEEE Trans. Consum. Electron., vol. 44, no. 3, pp. 638–648, 1998.

[4]W.-C. M. Lai-Man Po, "A novel Four-step search algorithm for fast block Motion Estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 6, no. 3, pp. 313–317, 1996.

[5]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, 1996.

[6]A. A. K. Jo Yew Tham, Surendra Ranganath, Maitreya Ranganath, "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, 1998.

[7]S. Zhu, "A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation," IEEE Trans. Image Process., vol. 9, no. 2, pp. 287–290, 2000.

[8]C. Zhu, X. Lin, and L. Chau, "Hexagon-Based Search Pattern for Fast Block Motion Estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 5, pp. 349–355, 2002.

[9]C. Cheung and L. Po, "A novel cross-diamond search algorithm for fast block motion estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 12, pp. 1168–1177, Dec. 2002.

[10]H. Jia and L. Zhang, "Directional diamond search pattern for fast block motion estimation," Electron. Lett., vol. 39, no. 22, pp. 2–3, 2003.

[11]C. Cheung and L. Po, "Novel Cross-Diamond-Hexagonal Search Algorithms for Fast Block Motion Estimation," IEEE Trans. Circuits Syst., vol. 7, no. 1, pp. 16–22, 2005.

[12]T. Tsai and Y. Pan, "A Novel 3-D Predict Hexagon Search Algorithm for Fast Block Motion Estimation on H.264 Video Coding," IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 12, pp. 1542–1549, 2006.

[13]X. Jing, L. Chau, and S. Member, "An Efficient Three-Step Search Algorithm for Block Motion Estimation," IEEE Trans. Multimed., vol. 6, no. 3, pp. 435–438, 2004.

[14]Y. Yan and S. Meng, "A New Hybrid Search Scheme for Video Motion Estimation," J. Converg. Inf. Technol., vol. 6, no. 3, pp. 106–112, 2011.

[15]S. Huang, C. Cho, and J. Wang, "Adaptive Fast Block-Matching Algorithm by Switching Search Patterns for Sequences With Wide-Range Motion Content," IEEE Trans. Circuits Syst. Video Technol., vol. 15, no. 11, pp. 1373–1384, 2005.

[16]K. Ng, L. Po, K. Wong, C. Ting, and K. Cheung, "A Search Patterns Switching Algorithm for Block Motion Estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 5, pp. 753–759, May 2009.

[17]Z. Chen, J. Xu, Y. He, and J. Zheng, "Fast integer-pel and fractional-pel motion estimation for H.264/AVC," J. Vis. Commun. Image Represent., vol. 17, no. 2, pp. 264–290, Apr. 2006.

[18]H. J. Hsieh, C. C. Lin, and Y. Lin, "Multi-direction search algorithm for block motion estimation in H.264/AVC," IET Image Process., vol. 3, no. 2, pp. 88–99, Apr. 2009.

[19]W. Hsu, T. Yu, and J. Guo, "Enhanced Block Motion Estimation Based on Threshold-Aware Two-Path Search Method," J. Converg. Inf. Technol., vol. 5, no. 5, pp. 99–110, 2010.

[20]L. Po, K. Ng, K. Cheung, K. Wong, and C. Ting, "Novel Directional Gradient Descent Searches for Fast Block Motion Estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 8, pp. 1189–1195, 2009.

[21]A. Nayak, B. Biswal, and S. K. Sabut, "Evaluation and Comparison of Motion Estimation Algorithms for Video Compression," Int. J. Image, Graph. Signal Process., vol. 4, no. 2, pp. 9–18, 2012.

[22]S. Acharjee and C. Sheli, "Fuzzy Logic Based Four Step Search Algorithm for Motion Vector Estimation .," Int. J. Image, Graph. Signal Process., vol. 4, no. 4, pp. 49–55, 2012.

[23]M. Porto, A. Silva, S. Almeida, E. Costa, and S. Bampi, "Motion Estimation Architecture Using Efficient Adder-Compressors for HDTV Video Coding," J. Integr. Circuits Syst., vol. 5, no. 1, pp. 78–88, 2010.

[24]T.-H. Tsai and Y.-N. Pan, "High Efficiency Architecture Design of Real-Time QFHD for H.264/AVC Block Motion Estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 21, no. 11, pp. 1646–1658, 2011.

[25]J. Vanne, E. Aho, and K. Kuusilinna, "A Configurable Motion Estimation Architecture for Block-Matching Algorithms," IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 4, pp. 466–476, 2009.

[26]O. Ndili and T. Ogunfunmi, "Algorithm and Architecture Co-Design of Hardware-Oriented, Modified Diamond Search for Fast Motion Estimation in H.264/AVC," IEEE Trans. Circuits Syst. Video Technol., vol. 21, no. 9, pp. 1214–1227, 2011.

[27]"YUV video repository." [Online]. Available: http://media.xiph.org/video/derf/.