A fast rate-optimized motion estimation algorithm for low-bit-rate video coding

John C.H. Ju, Yen Kuang Chen, S. Y. Kung

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


Motion estimation is known to be the main bottleneck in real-time encoding applications, and the search for an effective motion estimation algorithm (in terms of computational complexity and compression efficiency) has been a challenging problem for years. This paper describes a new block-matching algorithm that is much faster than the full search algorithm and occasionally even produces better rate-distortion curves than the full search algorithms. We observe that a piecewise continuous motion field reduces the bit rate for differentially encoded motion vectors. Our motion estimation algorithm exploits the spatial correlations of motion vectors effectively in the sense of producing better rate-distortion curves. Furthermore, we incorporate such correlations in a multiresolution framework to reduce the computational complexity. Simulation shows that this method is successful because of the homogeneous and reliable estimation of the displacement vectors. In nine out of our ten benchmark simulations, the performance of the full search algorithm and that of our subblock multiresolution method is about the same. In one out of our ten benchmark simulations, our method has improvement.

Original languageEnglish (US)
Pages (from-to)994-1002
Number of pages9
JournalIEEE Transactions on Circuits and Systems for Video Technology
Issue number7
StatePublished - 1999

All Science Journal Classification (ASJC) codes

  • Media Technology
  • Electrical and Electronic Engineering


  • Motion estimation algorithm
  • Multiresolution refinement
  • Neighborhood relaxation


Dive into the research topics of 'A fast rate-optimized motion estimation algorithm for low-bit-rate video coding'. Together they form a unique fingerprint.

Cite this