Block Matching Using Lower Bound Comparison Algorithm

Block matching is frequently used in stereo vision, visual tracking, and video compression. In this technique, the current image frame is partitioned into non-overlapping fixed-size rectangular blocks. The goal here is to estimate the inter-frame motion vector for each block in the current frame by finding the best matching block (according to a matching criterion) in the reference frame, usually the previous frame,, in a computationally efficient manner. In this report, we first give an overview of some of the fast block matching algorithms that have been proposed in the past, then introduce a new fast block matching algorithm.Unlike many block matching algorithms proposed in the past that can only assure a local minimum of matching error for the whole block, this algorithm, which is called "lower bound comparison algorithm" in this report, is an algorithm that significantly speeds up the computation of the block matching while guaranteeing the global optimal match in the search range. To achieve this, the new algorithm uses lower bound comparison strategy which utilizes an ascending lower bound list of the matching error to determine the temporary best match position. What the strategy does is to avoid the costly computation of complete matching error at every search position when a lower bound larger than the global minimum matching error can be used.A set of common test image sequences are used to test the performance of this new algorithm. In this report, its performance is compared with that of several other block matching algorithms by the same benchmarks. Results are discussed in the report.Index terms - Block matching, motion estimation, lower bound comparison strategy...