Implementation Techniques for Geometric Branch-and-Bound Matching Methods

Thomas Breuel
Computer Vision and Image Understanding volume 90 number 3, Pages 258-294, Elsevier, 6/2003

Abstract:

Algorithms for geometric matching and feature extraction that work by recursively sub-dividing transformation space and bounding the quality of match have been proposed in a number of different contexts and become increasingly popular over the last few years. This paper describes matchlist-based branch-and-bound techniques and presents a number of new applications of branch-and-bound methods, among them, a method for globally optimal partial line segment matching under bounded or Gaussian error, point match-ing under a Gaussian error model with subpixel accuracy and precise orientation models, and a simple and robust technique for finding multiple distinct object instances. It also contains extensive reference information for the implementation of such matching meth-ods under a wide variety of error bounds and transformations. In addition, the paper contains a number of benchmarks and evaluations that provide new information about the runtime behavior of branch-and-bound matching algorithms in general, and that help choose among different implementation strategies, such as the use of point location data structures and space/time tradeoffs involving depth-first search.

Files:

  ImplementationBranchBound.pdf

BibTex:

@article{ BREU2003,
	Title = {Implementation Techniques for Geometric Branch-and-Bound Matching Methods},
	Author = {Thomas Breuel},
	Month = {6},
	Year = {2003},
	Publisher = {Elsevier},
	Publisher = {90},
	Pages = {258-294},
	Journal = {Computer Vision and Image Understanding},
	Howpublished = {Accepted for publication in it Computer Vision and Image Understanding},
	Number = {3}
}

     
Last modified:: 30.08.2016