Software

Fast Block Matching Algorithm

Program

C code download

Publication

"Fast block matching algorithm based on the winner-update strategy,"
IEEE Transactions on Image Processing, vol. 10, no. 8, pp. 1212-1222, Aug. 2001.
Yong-Sheng Chen, Yi-Ping Hung, and Chiou-Shann Fuh
[Download: ]

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. We present 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 used in this work. The basic idea of the winner-update strategy is to avoid, at each search position, the costly computation of 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; and (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.

Fast k-Nearest Neighbor Search Algorithm

Program

C code download

Publication

"Fast algorithm for nearest neighbor search based on a lower bound tree,"
Proceedings of the 8th International Conference on Computer Vision, Vancouver, Canada, Jul. 2001, vol. 1, pp. 446-453.
Yong-Sheng Chen, Yi-Ping Hung, and Chiou-Shann Fuh
[Download: ]

Abstract

We present a fast and versatile algorithm which can rapidly perform a variety of nearest neighbor searches. Efficiency improvement is achieved by utilizing the distance lower bound to avoid the calculation of the distance itself if the lower bound is already larger than the global minimum distance. At the preprocessing stage, the proposed algorithm constructs a lower bound tree (LB-tree) by agglomeratively clustering all the sample points to be searched. Given a query point, the lower bound of its distance to each sample point can be calculated by using the internal node of the LB-tree. To reduce the amount of lower bounds actually calculated, the winner-update search strategy is used for traversing the tree. For further efficiency improvement, data transformation can be applied to the sample and the query points. In addition to finding the nearest neighbor, the proposed algorithm can also (i) provide the $k$-nearest neighbors progressively; (ii) find the nearest neighbors within a specified distance threshold; and (iii) identify neighbors whose distances to the query are sufficiently close to the minimum distance of the nearest neighbor. Our experiments have shown that the proposed algorithm can save substantial computation, particularly when the distance of the query point to its nearest neighbor is relatively small compared with its distance to most other samples (which is the case for many object recognition problems).