Hierarchical Matching Beats The Non-Wildcard and Interpretation Tree Model Matching Algorithms
Robert Bob Fisher · 1993
In Fisher[1] we introduced a non-wildcard model matching algorithm that has speed advantages over the standard Interpretation Tree model matching algorithm. This paper describes a hierarchical model-matching algorithm that has improved performance over both the standard and non-wildcard algorithms. 1 Introduction The most well-known control algorithm for high-level model matching in computer vision is the Interpretation Tree(IT) expansion algorithm, as used by Grimson and Lozano-Perez[2, 3]. In Fisher[1] we introduced a variation on this algorithm that did not use a wildcard which gave performance advantages of 4-10. Both algorithms search a tree of model-to-data correspondences, such that each node in the tree represents one correspondence and the path of nodes from the current node back to the root of the tree is a set of simultaneous pairings. The non-wildcard algorithm avoids the many matches requiring wildcards and only investigates the single model-to-data pairings once, while s...