Fast block matching algorithm based on the winner-update strategy

Yong-Sheng Chen; Yi Ping Hung; Chiou Shann Fuh

doi:10.1109/83.935037

Fast block matching algorithm based on the winner-update strategy

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

^*Corresponding author for this work

Institute of Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

135 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 language	English
Pages (from-to)	1212-1222
Number of pages	11
Journal	IEEE Transactions on Image Processing
Volume	10
Issue number	8
DOIs	https://doi.org/10.1109/83.935037
State	Published - 1 Aug 2001

Keywords

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

Access to Document

10.1109/83.935037

Cite this

@article{f55ef23e948846d184db3cda098ecdfb,

title = "Fast block matching algorithm based on the winner-update strategy",

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.",

keywords = "Block matching, Fast algorithm, Minkowski's inequality, Motion estimation, Winner-update strategy",

author = "Yong-Sheng Chen and Hung, {Yi Ping} and Fuh, {Chiou Shann}",

year = "2001",

month = aug,

day = "1",

doi = "10.1109/83.935037",

language = "English",

volume = "10",

pages = "1212--1222",

journal = "IEEE Transactions on Image Processing",

issn = "1057-7149",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "8",

}

TY - JOUR

T1 - Fast block matching algorithm based on the winner-update strategy

AU - Chen, Yong-Sheng

AU - Hung, Yi Ping

AU - Fuh, Chiou Shann

PY - 2001/8/1

Y1 - 2001/8/1

N2 - 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.

AB - 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.

KW - Block matching

KW - Fast algorithm

KW - Minkowski's inequality

KW - Motion estimation

KW - Winner-update strategy

UR - http://www.scopus.com/inward/record.url?scp=0035423598&partnerID=8YFLogxK

U2 - 10.1109/83.935037

DO - 10.1109/83.935037

M3 - Article

C2 - 18255538

AN - SCOPUS:0035423598

SN - 1057-7149

VL - 10

SP - 1212

EP - 1222

JO - IEEE Transactions on Image Processing

JF - IEEE Transactions on Image Processing

IS - 8

ER -

Fast block matching algorithm based on the winner-update strategy

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this