A new diamond search algorithm for fast block-matching motion estimation

Author

Zhu, Shan ; Ma, Kai-Kuang

Author_Institution

V-Bits Video Eng. Dept., Cisco Syst. Inc., San Jose, CA, USA

Volume

9

Issue

2

fYear

2000

fDate

2/1/2000 12:00:00 AM

Firstpage

287

Lastpage

290

Abstract

Based on the study of motion vector distribution from several commonly used test image sequences, a new diamond search (DS) algorithm for fast block-matching motion estimation (BMME) is proposed in this paper. Simulation results demonstrate that the proposed DS algorithm greatly outperforms the well-known three-step search (TSS) algorithm. Compared with the new three-step search (NTSS) algorithm, the DS algorithm achieves close performance but requires less computation by up to 22% on average. Experimental results also show that the DS algorithm is better than the four-step search (4SS) and block-based gradient descent search (BBGDS), in terms of mean-square error performance and required number of search points

Keywords

image matching; image sequences; mean square error methods; motion estimation; search problems; video coding; BMME; DS algorithm; computation; diamond search algorithm; fast block-matching motion estimation; image sequences; mean-square error performance; motion vector distribution; performance; Bandwidth; Computational modeling; Image sequences; Motion estimation; Signal processing algorithms; Testing; Transform coding; Video coding; Video compression; Video sequences;

fLanguage

English

Journal_Title

Image Processing, IEEE Transactions on

Publisher

ieee

ISSN

1057-7149

Type

jour

DOI

10.1109/83.821744

Filename

821744