Fast Block Matching Algorithm Based on the Winner-Update Strategy
Resource
IEEE Transactions on Image Processing 10 (8): 1212-1222
Journal
IEEE Transactions on Image Processing
Journal Volume
10
Journal Issue
8
Pages
1212-1222
Date Issued
2001
Date
2001
Author(s)
Abstract
Block matching is a widely used method for stereo vision, visual tracking, and video compression. Many fast algorithms for block matching have been proposed in the past, but most of them do not guarantee that the match found is the globally optimal match in a search range. This paper presents a new fast algorithm based on the winner-update strategy which utilizes an ascending lower bound list of the matching error to determine the temporary winner. Two lower bound lists derived by using partial distance and by using Minkowski's inequality are described. The basic idea of the winner-update strategy is to avoid, at each search position, the costly computation of the matching error when there exists a lower bound larger than the global minimum matching error. The proposed algorithm can significantly speed up the computation of the block matching because: 1) computational cost of the lower bound we use is less than that of the matching error itself; 2) an element in the ascending lower bound list will be calculated only when its preceding element has already been smaller than the minimum matching error computed so far; 3) for many search positions, only the first several lower bounds in the list need to be calculated. Our experiments have shown 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. Our source codes of the proposed algorithm are available at http://smart.iis.sinica.edu.tw/html/winup.html.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
13.pdf
Size
978.64 KB
Format
Adobe PDF
Checksum
(MD5):b1ab094d73c45c8f0f909e063c1ada0a