Motion estimation using two-stage predictive search algorithms based on joint spatio-temporal correlation information

Lili Hsieh, Wen Shiung Chen*, Chuan Hsi Liu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)


Motion estimation is one of the major problems in developing a real-time software-based video codec since it has high search complexity. In the motion estimation process, the motion field of the current block can generally be tracked from the motion fields of the neighboring blocks in the spatial and temporal directions. In this paper, two efficient fast motion estimation algorithms with a two-stage predictive search based on joint spatio-temporal correlations are proposed to reduce the search complexity. In the first stage, a rough search from the given motion vectors associated with six spatially and temporally correlated blocks attempts to find a starting point of the adequate search range that is closer to the global optimum. In the second stage, block-based gradient descent search (Liu & Feig, 1996) and predictive partial search (proposed) algorithms are used for fine search to elaborately search the adequate range from the starting point for the best motion vector. Simulation results demonstrate that our algorithms effectively reduce the average number of checked points to only 1.55% and 0.78% as compared to the full search method and yield a great performance improvement in terms of computational complexity, PSNR and bit rates as compared to full search and some well-known fast search methods.

Original languageEnglish
Pages (from-to)11608-11623
Number of pages16
JournalExpert Systems with Applications
Issue number9
Publication statusPublished - 2011 Sept
Externally publishedYes


  • Block-matching algorithm
  • Motion estimation
  • Multimedia communications
  • Predictive search
  • Video codec

ASJC Scopus subject areas

  • General Engineering
  • Computer Science Applications
  • Artificial Intelligence


Dive into the research topics of 'Motion estimation using two-stage predictive search algorithms based on joint spatio-temporal correlation information'. Together they form a unique fingerprint.

Cite this