Probabilistic partial-distance fast matching algorithms for motion estimation
- 1 February 2001
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuits and Systems for Video Technology
- Vol. 11 (2), 139-152
- https://doi.org/10.1109/76.905981
Abstract
Motion search is by far the most complex operation to be performed in a video encoder. This paper proposes a novel fast matching algorithm to help speed up the computation of the matching (distance) metric used in the search, e.g., the sum of absolute difference (SAD). Based on a partial distance technique, our algorithm reduces complexity by terminating the SAD calculation early once it becomes clear that, given the partial SAD, it is likely that the total SAD will exceed that of the best candidate encountered so far in the search. The key idea is to introduce models to describe the probability distribution of the total distance given a measured partial distance. These models enable us to evaluate the risk involved in "trusting" a distance estimate obtained from a partial distance. By varying the amount of risk we are willing to take, we ran increase the speed, but we may also eliminate some good candidates too early, and thus increase the distortion of the decoded sequence. Because our approach requires knowledge of the statistical characteristics of the input, we also propose two approaches that allow these models to be obtained online. Our experimental results (based on an actual software implementation of an MPEG encoder) demonstrate that significant gains can be achieved with this approach. For example, reductions in the motion estimation computation time as compared with the original partial-distance search (where computation stops if the partial SAD is already larger than the SAD of the best candidate so far) can be as high as 45% for 2-D log search and 65% for exhaustive full search with a small penalty of 0.1-dB degradation in PSNR of the reconstructed sequences.Keywords
This publication has 31 references indexed in Scilit:
- A low-complexity rate-distortion model for motion estimation in H.263Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- DCT computation based on variable complexity fast approximationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Distortion/decoding time tradeoffs in software DCT-based image codingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- New fast and efficient two-step search algorithm for block motion estimationIEEE Transactions on Circuits and Systems for Video Technology, 1999
- A novel unrestricted center-biased diamond search algorithm for block motion estimationIEEE Transactions on Circuits and Systems for Video Technology, 1998
- Computation-constrained fast MPEG-2 encodingIEEE Signal Processing Letters, 1997
- Multiscale video representation using multiresolution motion compensation and wavelet decompositionIEEE Journal on Selected Areas in Communications, 1993
- Multigrid block-matching motion estimation with an adaptive local mesh refinementPublished by SPIE-Intl Soc Optical Eng ,1992
- Motion-compensated wavelet transform coding for color video compressionIEEE Transactions on Circuits and Systems for Video Technology, 1992
- Interpolative multiresolution coding of advance television with compatible subchannelsIEEE Transactions on Circuits and Systems for Video Technology, 1991