On the design of pattern-based block motion estimation algorithms

Jang Jer Tsai*, Hsueh-Ming Hang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


Pattern-based block motion estimation (PBME) is a critical element in the contemporary video coding system because it typically dominates the coding efficiency and the computing power. Therefore, many proposals have been suggested to reduce its computational complexity, but most of them are devised based on experimental data or heuristic ideas. In this letter, we look into every component of a typical PBME algorithm and fine tune the major components systematically to achieve the optimal or nearly optimal results. Our methodology is developed based on our proposed analytical model together with statistical tools. First, we use the analytic model to analyze and design effective genetic-algorithm-based search patterns. Moreover, we propose an adaptive switching strategy that dynamically switches between two search patterns. Second, we extend our PBME model to evaluate the efficiency of starting (initial search) points. A near optimal set of starting points is progressively identified. Last, we study the early termination threshold technique and suggest a metric in selecting an effective threshold. An accurate threshold mechanism is thus constructed. Combining all these techniques, we develop a PBME algorithm that outperforms most popular algorithms.

Original languageEnglish
Article number5159403
Pages (from-to)136-143
Number of pages8
JournalIEEE Transactions on Circuits and Systems for Video Technology
Issue number1
StatePublished - Jan 2010


  • Early termination
  • Genetic pattern searches
  • Modeling
  • Motion estimation
  • Starting points

Fingerprint Dive into the research topics of 'On the design of pattern-based block motion estimation algorithms'. Together they form a unique fingerprint.

Cite this