ACCELERATED TEMPLATE MATCHING USING TEMPLATE TREES GROWN BY CONDENSATION

Template trees provide a means of accelerating nearest neighbor searches for problems in which KD-trees and similar data structures do not work well because of the high dimension and/or sophisticated distance function used. Suppose the points for which nearest neighbors are being sought are noisy 16 x 24 images of characters. Each point has 16 x 24 = 384 dimensions. Images which a good distance function would classify as similar may have very different values at a dozen or more randomly chosen pixels. Structures, such as the KD-tree, which classify points based on individual pixel values do not work well in this circumstance. Template trees work directly with the distance function rather than with the 384 components of the points. This paper demonstrates that template trees can be used for rapid nearest neighbor searches in problems of this type. An algorithm is presented for selecting templates from a set of training points, and organizing them into a template tree which is guaranteed to correctly identify all of the training points. The tree construction algorithm is similar in many ways to the condensation algorithm for template selection, although it organizes templates into a tree as it selects them. A tree containing approximately 2000 images of capital letters was constructed using a training set of about 8000 points. Using the tree, an average of only about 140 point to point distance calculations were needed to identify an unknown image. Identification accuracy was comparable to that obtained using 2000 templates without a tree.