Title :
A line-diamond parallel search algorithm for block motion estimation
Author :
Ding, Guiguang ; Dai, Qionghai
Author_Institution :
Dept. of Autom., Tsinghua Univ., Beijing, China
Abstract :
The widespread use of block matching motion estimation (BMME) in video coding is due to its effectiveness and simplicity of implementation. This paper presents a novel fast BMME algorithm called the line-diamond parallel search (LDPS). The algorithm is based on the following two properties: the special directionality of the SAD distribution and the characteristics of the center-biased motion vector distribution. In addition, in order to increase the speed of search, the parallel processing idea is used in LDPS. That is to say LDPS realizes the coarse orientation and the accurate search in the same step. Our experimental results show that not only the processing speed of the LDPS algorithm is much higher than that of other fast algorithms, but also its accuracy of motion compensation is as nearly good as that of full search (FS).
Keywords :
image matching; motion compensation; motion estimation; parallel algorithms; search problems; video coding; block matching motion estimation; center-biased motion vector distribution; coarse orientation; full search algorithm; line-diamond parallel search algorithm; motion compensation; sum of absolute difference distribution; video coding; Automation; Broadband communication; Electronic mail; Hardware; Image motion analysis; Motion compensation; Motion estimation; Nonlinear optics; Parallel processing; Video coding;
Conference_Titel :
Image and Graphics (ICIG'04), Third International Conference on
Conference_Location :
Hong Kong, China
Print_ISBN :
0-7695-2244-0
DOI :
10.1109/ICIG.2004.7
