Fast block matching algorithm based on the winner-update strategy

Yong-Sheng Chen*, Yi Ping Hung, Chiou Shann Fuh

*Corresponding author for this work

Research output: Contribution to journalArticle

131 Scopus citations

Abstract

Many fast algorithms for block matching were proposed in the past, but most of them do not guarantee that the match found was the globally optimal match in a search range. A new fast algorithm, named the winner-update algorithm, which can speed up the computation of block matching while still guaranteeing that the minimum matching error can be obtained was proposed. Experiments showed that, when applying to motion vector estimation for several widely-used test videos, 92% to 98% of operations can be saved while still guaranteeing the global optimality. Moreover, the proposed algorithm can be easily modified either to meet the limited time requirement or to provide an ordered list of best candidate matches.

Original languageEnglish
Pages (from-to)1212-1222
Number of pages11
JournalIEEE Transactions on Image Processing
Volume10
Issue number8
DOIs
StatePublished - 1 Aug 2001

Keywords

  • Block matching
  • Fast algorithm
  • Minkowski's inequality
  • Motion estimation
  • Winner-update strategy

Fingerprint Dive into the research topics of 'Fast block matching algorithm based on the winner-update strategy'. Together they form a unique fingerprint.

Cite this