Please wait a minute...
ZJUS-A
Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering)  2006, Vol. 7 Issue (2 ): 13-    DOI: 10.1631/jzus.2006.A0194
    
A fast block-matching algorithm based on variable shape search
Liu Hao, Zhang Wen-jun, Cai Jun
Institute of Image Communication and Information Processing, Shanghai Jiao Tong University, Shanghai 200030, China; Department of Electrical and Computer Engineering, University of Calgary, Calgary, Alberta T2N 1N4, Canada
Download:     PDF (0 KB)     
Export: BibTeX | EndNote (RIS)      

Abstract  Block-matching motion estimation plays an important role in video coding. The simple and efficient fast block-matching algorithm using Variable Shape Search (VSS) proposed in this paper is based on diamond search and hexagon search. The initial big diamond search is designed to fit the directional centre-biased characteristics of the real-world video sequence, and the directional hexagon search is designed to identify a small region where the best motion vector is expected to locate. Finally, the small diamond search is used to select the best motion vector in the located small region. Experimental results showed that the proposed VSS algorithm can significantly reduce the computational complexity, and provide competitive computational speedup with similar distortion performance as compared with the popular Diamond-based Search (DS) algorithm in the MPEG-4 Simple Profile.

Key words： Motion estimation      Block-matching      Variable shape search      MPEG-4 Simple Profile     
Received: 08 October 2004     
CLC:  TN919.81  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Liu Hao
Zhang Wen-jun
Cai Jun
Cite this article:

Liu Hao, Zhang Wen-jun, Cai Jun. A fast block-matching algorithm based on variable shape search. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(2 ): 13-.

URL:

http://www.zjujournals.com/xueshu/zjus-a/10.1631/jzus.2006.A0194     OR     http://www.zjujournals.com/xueshu/zjus-a/Y2006/V7/I2 /13

[1] XIE Chun-lai, CHEUNG Chun-ho, LIU Wei-zhong. A novel adjustable multiple cross-hexagonal search algorithm for fast block motion estimation[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(8): 1304-1310.
[2] SOTELO Miguel-angel, GARCÍA Roberto, PARRA Ignacio, FERNÁNDEZ David, GAVILÁN Miguel, ÁLVAREZ Sergio, NARANJO José-eugenio. Visual odometry for road vehicles—feasibility analysis[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(12): 2017-2020.
[3] WU Xue-dong, SONG Zhi-huan. Gaussian particle filter based pose and motion estimation[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(10): 1604-1613.
[4] Chen Guo-Bin. A fast motion estimation algorithm for mobile communications[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(Supplement 1): 13-18.
[5] Jiang Gang-yi, Yu Mei, Yu Zhou, Ye Xi-en, Zhang Wen-qin, Kim Yong-deak. Multiple description scalable video coding based on 3D lifted wavelet transform[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(5 ): 22-.
[6] CHEN Guo-bin, LU Xin-ning, WANG Xing-guo, LIU Ji-lin. A complexity-scalable software-based MPEG-2 video encoder[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2004, 5(5): 572-578.