Fast block matching using prediction and rejection criteria

In this paper, we present a fast block matching algorithm by making use of the correlation between layers of the sum pyramid for a block. To speed our method, an algorithm is also developed to predict the initial motion vector for a template block. Using the elimination criteria and predicted motion...

Full description

Saved in:
Bibliographic Details
Published in:Signal processing 2009-06, Vol.89 (6), p.1115-1120
Main Authors: Liaw, Yi-Ching, Lai, Jim Z.C, Hong, Zuu-Chang
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Block matching
Blocking
Computational efficiency
Computing time
Degradation
Exact sciences and technology
Image processing
Information, signal and communications theory
Matching
Miscellaneous
Motion estimation
Noise levels
Prediction
Searching
Signal processing
Sum pyramid
Telecommunications and information theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we present a fast block matching algorithm by making use of the correlation between layers of the sum pyramid for a block. To speed our method, an algorithm is also developed to predict the initial motion vector for a template block. Using the elimination criteria and predicted motion vector, our method can further reduce the computational complexity significantly. Compared with the full search block matching algorithm, our approach can reduce the computing time by a factor of 9.9–28.2 with the peak signal-to-noise ratio (PSNR) degradation of 0.00–0.03 dB. Compared to WinUpMI, which is the fastest block matching algorithm preserving global optimality as far as we know, our method can reduce the computing time by 4.9–52.5% with the PSNR degradation of 0.00–0.03 dB. Our method can reduce the computing time of predictive search area approach for fast block motion estimation (PSAFBME) by 50–96% with about the same PSNR.
ISSN:0165-1684
1872-7557
DOI:10.1016/j.sigpro.2008.12.012