Efficient algorithms for robust feature matching

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