Premium
A new fast block matching algorithm based on complexity‐distortion optimization
Author(s) -
Tai Pol Lin,
Liu Chii Tung,
Wang Jia Shung
Publication year - 2002
Publication title -
international journal of imaging systems and technology
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.359
H-Index - 47
eISSN - 1098-1098
pISSN - 0899-9457
DOI - 10.1002/ima.10012
Subject(s) - block (permutation group theory) , distortion (music) , computational complexity theory , algorithm , matching (statistics) , computer science , motion vector , set (abstract data type) , mathematical optimization , mathematics , artificial intelligence , image (mathematics) , amplifier , computer network , statistics , geometry , bandwidth (computing) , programming language
Most fast block matching algorithms ignore the efficiency in motion compensation within each checking step. In order to achieve better‐compensated performance, the limited computational complexity should be allocated more carefully into each block. It means that the fast block matching algorithm can be viewed as a kind of rate‐distortion optimization problem. The complexity‐distortion optimal fast block matching algorithm should find the maximized quality of the compensated image under a target computational complexity. In order to approach the optimal complexity‐distortion solution, some strategies are developed. For example, a domination‐based motion vector prediction technique is developed to set the initial motion vector for each block. A predictive complexity‐distortion benefit list is established to predict the compensated benefit for each block. Also, a three‐level pattern searching is employed to check the candidate motion vector. Experimental results show that our proposed algorithm outperforms significantly the three‐step search. For example, in “Salesman,” the average checkpoints for one block is 33 by using the three‐step search. The average checkpoint is 1.75 by using our proposal algorithm under the same average PSNR condition. © 2002 Wiley Periodicals, Inc. Int J Imaging Syst Technol 12, 63–67, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ima.10012