Predictive fine granularity successive elimination for fast optimal block-matching motion estimation
- 17 January 2005
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Image Processing
- Vol. 14 (2), 213-221
- https://doi.org/10.1109/tip.2004.840702
Abstract
Given the number of checking points, the speed of block motion estimation depends on how fast the block matching is. A new framework, fine granularity successive elimination (FGSE), is proposed for fast optimal block matching in motion estimation. The FGSE features providing a sequence of nondecreasing fine-grained boundary levels to reject a checking point using as little computation as possible, where block complexity is utilized to determine the order of partitioning larger subblocks into smaller subblocks in the creation of the fine-grained boundary levels. It is shown that the well-known successive elimination algorithm (SEA) and multilevel successive elimination algorithm (MSEA) are just two special cases in the FGSE framework. Moreover, in view that two adjacent checking points (blocks) share most of the block pixels with just one pixel shifting horizontally or vertically, we develop a scheme to predict the rejection level for a candidate by exploiting the correlation of matching errors between two adjacent checking points. The resulting predictive FGSE algorithm can further reduce computation load by skipping some redundant boundary levels. Experimental results are presented to verify substantial computational savings of the proposed algorithm in comparison with the SEA/MSEA.Keywords
This publication has 16 references indexed in Scilit:
- Adjustable partial distortion search algorithm for fast block motion estimationIEEE Transactions on Circuits and Systems for Video Technology, 2003
- Fast full search motion estimation algorithm using early detection of impossible candidate vectorsIEEE Transactions on Signal Processing, 2002
- Fast full-search block matchingIEEE Transactions on Circuits and Systems for Video Technology, 2001
- Normalized partial distortion search algorithm for block motion estimationIEEE Transactions on Circuits and Systems for Video Technology, 2000
- A multilevel successive elimination algorithm for block matching motion estimationIEEE Transactions on Image Processing, 2000
- Fast motion vector estimation using multiresolution-spatio-temporal correlationsIEEE Transactions on Circuits and Systems for Video Technology, 1997
- A novel four-step search algorithm for fast block motion estimationIEEE Transactions on Circuits and Systems for Video Technology, 1996
- New adaptive pixel decimation for block motion vector estimationIEEE Transactions on Circuits and Systems for Video Technology, 1996
- A block-based gradient descent search algorithm for block motion estimation in video codingIEEE Transactions on Circuits and Systems for Video Technology, 1996
- Successive elimination algorithm for motion estimationIEEE Transactions on Image Processing, 1995