
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Novel Block Matching Algorithm for Motion Estimation
Yankang WANG Yanqun WANG Hideo KURODA
Publication
IEICE TRANSACTIONS on Communications
Vol.E81B
No.3
pp.575585 Publication Date: 1998/03/25 Online ISSN:
DOI: Print ISSN: 09168516 Type of Manuscript: PAPER Category: Source Encoding Keyword: motion estimation, block matching, PeanoHilbert scanning, binary search,
Full Text: PDF(798KB)>>
Summary:
Conventional fast blockmatching algorithms, such as TSS and DSWA/IS, are widely used for motion estimation in the lowbitrate video coding. These algorithms are based on the assumption that when searching in the previous frame for the block that best matches a block in the current frame, the difference between them increases monotonically when a matching block moves away from the optimal solution. Unfortunately, this assumption of global monotonicity is often not valid, which can lead to a high possibility for the matching block to be trapped to local minima. On the other hand, monotonicity does exist in localized areas. In this paper, we proposed a new algorithm called PeanoHilbert scanning search algorithm (PHSSA). With the PeanoHilbert image representation, the assumption of global monotonicity is not necessary, while local monotonicity can be effectively explored with binary search. PHSSA selects multiple winners at each search stage, minimizing the possibility of the result being trapped to local minima. The algorithm allows selection of three parameters to meet different search accuracy and process speed: (1) the number of initial candidate intervals, (2) a threshold to remove the unpromising candidate intervals at each stage, and (3) a threshold to control when interval subdivision stops. With proper parameters, the multiplecandidate PHSSA converges to the optimal result faster and with better accuracy than the conventional block matching algorithms.

