Full Text:   <1242>

CLC number: TN919.81

On-line Access: 2010-08-02

Received: 2009-03-14

Revision Accepted: 2009-06-04

Crosschecked: 2010-07-01

Cited: 1

Clicked: 2866

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2010 Vol.11 No.8 P.637-644

http://doi.org/10.1631/jzus.C0910561


An adaptive fast search algorithm for block motion estimation in H.264


Author(s):  Cong-dao Han, Ji-lin Liu, Zhi-yu Xiang

Affiliation(s):  Institute of Information and Communication Engineering, Zhejiang University, Hangzhou 310027, China, Zhejiang Provincial Key Laboratory of Information Network Technology, Hangzhou 310027, China

Corresponding email(s):   hancongdao@163.com

Key Words:  Adaptive hexagon and small diamond search (AHSDS), Search pattern, Mean absolute difference (MAD), Optimal point


Cong-dao Han, Ji-lin Liu, Zhi-yu Xiang. An adaptive fast search algorithm for block motion estimation in H.264[J]. Journal of Zhejiang University Science C, 2010, 11(8): 637-644.

@article{title="An adaptive fast search algorithm for block motion estimation in H.264",
author="Cong-dao Han, Ji-lin Liu, Zhi-yu Xiang",
journal="Journal of Zhejiang University Science C",
volume="11",
number="8",
pages="637-644",
year="2010",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C0910561"
}

%0 Journal Article
%T An adaptive fast search algorithm for block motion estimation in H.264
%A Cong-dao Han
%A Ji-lin Liu
%A Zhi-yu Xiang
%J Journal of Zhejiang University SCIENCE C
%V 11
%N 8
%P 637-644
%@ 1869-1951
%D 2010
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C0910561

TY - JOUR
T1 - An adaptive fast search algorithm for block motion estimation in H.264
A1 - Cong-dao Han
A1 - Ji-lin Liu
A1 - Zhi-yu Xiang
J0 - Journal of Zhejiang University Science C
VL - 11
IS - 8
SP - 637
EP - 644
%@ 1869-1951
Y1 - 2010
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C0910561


Abstract: 
Motion estimation is an important issue in H.264 video coding systems because it occupies a large amount of encoding time. In this paper, a novel search algorithm which utilizes an adaptive hexagon and small diamond search (AHSDS) is proposed to enhance search speed. The search pattern is chosen according to the motion strength of the current block. When the block is in active motion, the hexagon search provides an efficient search means; when the block is inactive, the small diamond search is adopted. Simulation results showed that our approach can speed up the search process with little effect on distortion performance compared with other adaptive approaches.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Banh, X.Q., Tan, Y.P., 2004. Adaptive dual-cross search algorithm for block-matching motion estimation. IEEE Trans. Consum. Electron., 50(2):766-775.

[2]Chen, Z., Zhou, P., He, Y., 2006. Fast integer-pel and fractional-pel motion estimation for H.264/AVC. J. Vis. Commun. Image Represent., 17(2):264-290.

[3]Cheung, C.H., Po, L.M., 2002. A novel cross-diamond search algorithm for fast block motion estimation. IEEE Trans. Circ. Syst. Video Technol., 12(12):1168-1177.

[4]Cheung, C.H., Po, L.M., 2003. Adjustable partial distortion search algorithm for fast block motion estimation. IEEE Trans. Circ. Syst. Video Technol., 13(1):100-110.

[5]Chung, K.L., Chang, L.C., 2003. A new predictive search area approach for fast block motion estimation. IEEE Trans. Image Process., 12(6):648-652.

[6]Ghanbari, M., 1990. The cross-search algorithm for motion estimation. IEEE Trans. Commun., 38(7):950-953.

[7]Han, K., Chun, B., 2003. Adaptive Hexagon Search Pattern for Block Motion Estimation. Proc. IEEE Int. Conf. on System, Man and Cybernetics, 2:1406-1409.

[8]Huang, S.Y., Cho, C.Y., Wang, J.S., 2005. Adaptive fast block-matching algorithm by switching search patterns for sequences with wide-range motion content. IEEE Trans. Circ. Syst. Video Technol., 15(11):1373-1384.

[9]ITU-T and ISO/IEC, 2003. Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification. ITU-T Rec. H.264/ISO/IEC 14496-10 AVC. Pattaya, Thailand.

[10]Jung, S.M., Shin, S.C., Baik, H., Park, M.S., 2002. Efficient multilevel successive elimination algorithms for block matching motion estimation. IEE Proc.-Vis. Image Signal Process., 149(2):73-84.

[11]Lengwehasarit, K., Ortega, A., 2001. Probabilistic partial-distance fast matching algorithms for motion estimation. IEEE Trans. Circ. Syst. Video Technol., 11(2):139-152.

[12]Li, R., Zeng, B., Liou, M.L., 1994. A new three-step search algorithm for block motion estimation. IEEE Trans. Circ. Syst. Video Technol., 4(4):438-442.

[13]Nam, J.Y., Seo, J.S., Kwak, J.S., Lee, M.H., Ha, Y.H., 2000. New fast search algorithm for block matching motion estimation using temporal and spatial correlation of motion vector. IEEE Trans. Consum. Electron., 46(4):934-942.

[14]Nie, Y., Ma, K.K., 2002. Adaptive rood pattern search for fast block-matching motion estimation. IEEE Trans. Image Process., 11(12):1442-1449.

[15]Po, L.M., Ma, W.C., 1996. A novel four-step search algorithm for fast block motion estimation. IEEE Trans. Circ. Syst. Video Technol., 6(3):313-317.

[16]Roan, Y.T., Chen, P.Y., 2000. A fuzzy search algorithm for the estimation of motion vectors. IEEE Trans. Broadcast., 46(2):121-127.

[17]Tham, J.Y., Ranganath, S., Ranganath, M., Kassim, A.A., 1998. A novel unrestricted center-biased diamond search algorithm for block motion estimation. IEEE Trans. Circ. Syst. Video Technol., 8(4):369-377.

[18]Tourapis, A.M., Au, O.C., Liou, M.L., 2000. Fast Block-Matching Motion Estimation Using Predictive Motion Vector Field Adaptive Search Technique (PMVFAST). ISO/IEC JTC1/SC29/WG11 MPEG2000/m5866. Noordwijkerhout, NL.

[19]Tsai, T.H., Pan, Y.N., 2004. A Novel Predict Hexagon Search Algorithm for Fast Block Motion Estimation on H.264 Video Coding. Proc. IEEE Conf. on Asia-Pacific Circuits and Systems, 1:609-612.

[20]Tu, Y.K., Yang, J.F., Shen, Y.N., Sun, M.T., 2003. Fast Variable Size Block Motion Estimation Using Merging Procedure with an Adaptive Threshold. Proc. IEEE Int. Conf. on Multimedia and Expo, 2:789-792.

[21]Wong, H.M., Au, O.C., Ho, C.W., Yip, S.K., 2005. Enhanced Predictive Motion Vector Field Adaptive Search Technique (E-PMVFAST)-Based on Future MV Prediction. Proc. IEEE Int. Conf. on Multimedia and Expo, p.1-4.

[22]Zhu, C., Lin, X., Chau, L.P., 2002. Hexagon-based search pattern for fast block motion estimation. IEEE Trans. Circ. Syst. Video Technol., 12(5):349-355.

[23]Zhu, S., Ma, K.K., 2000. A new diamond search algorithm for fast block-matching motion estimation. IEEE Trans. Image Process., 9(2):287-290.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Tang shuhua<hcdhjy20081008@zju.edu.cn>

2010-08-02 22:33:31

An interesting and efficent idea.

zhaizy

2010-08-02 17:17:06

Reviewer: The main idea of this article is contributing fast search algorithms for motion estimation in H.264 video coding. An adaptive algorithm making use of the Hexagon Search and Small Diamond Search is also presented with experimental evaluation. The most important idea of this paper is to propose the differentiation algorithm which determines the block is in active motion or inactive motion. The proposed method is well implemented on H.264 JM14.2 video coding standard. --Editor

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE