| Abstract | One of the basic building blocks in any point-based registration scheme involves matching feature points that areextracted from a sensed image to their counterparts in a reference image. This leads to the fundamental problem of point
matching: Given two sets of points, find the (affine) transformation that transforms one point set so that its distance from
the other point set is minimized. Because of measurement errors and the presence of outlying data points, it is important
that the distance measure between the two point sets be robust to these effects. We measure distances using the partial
Hausdorff distance. Point matching can be a computationally intensive task, and a number of theoretical and applied
approaches have been proposed for solving this problem. In this paper, we present two algorithmic approaches to the
point matching problem, in an attempt to reduce its computational complexity, while still providing a guarantee of the
quality of the final match. Our first method is an approximation algorithm, which is loosely based on a branch-and-
bound approach due to Huttenlocher and Rucklidge, (Technical Report 1321, Dept. of Computer Science, Cornell
University, Ithaca, 1992; Proc. IEEE Conf. on Computer vision and Pattern Recognition, New York, 1993, pp. 705—706).
We show that by varying the approximation error bounds, it is possible to achieve a tradeoff between the quality of the
match and the running time of the algorithm. Our second method involves a Monte Carlo method for accelerating the
search process used in the first algorithm. This algorithm operates within the framework of a branch-and-bound
procedure, but employs point-to-point alignments to accelerate the search. We show that this combination retains many
of the strengths of branch-and-bound search, but provides significantly faster search times by exploiting alignments. With
high probability, this method succeeds in finding an approximately optimal match. We demonstrate the algorithms’
performances on both synthetically generated data points and actual satellite images.
|
