Catalogue of Artificial Intelligence Techniques
Keywords: interpretation tree, matching, pruning
Author(s): H.W. Hughes
If an image contains an unknown object with features, of which are known to correspond to one of known objects (models)
having features, the problem of matching image features to model features can be expressed as an interpretation treeinterpretation tree (IT). The root node of tree for model has
descendants and the complete tree will have levels. The total number of possible interpretations is therefore:
For even quite small numbers of features the interpretation tree quickly becomes too large to handle. Fortunately, very few interpretations in the tree are consistent with the data and by pruning those branches that are inconsistent the tree can be reduced to a more manageable size. The constraints used include the distances between features, the angles between features and the sign of the triple product between corresponding surface normals.
- Grimson, W.E.L., Object Recognition by Computer: the role of geometric constraints, MIT Press, 1990.