Neural Computation, Vol 9, 1545-1588, Copyright © 1997 by The MIT Press

LETTERS

Shape Quantization And Recognition With Randomized Trees

Yali Amit and Donald Geman

We explore a new approach to shape recognition based on a virtually infinite family of binary features (queries) of the image data, designed to accommodate prior information about shape invariance and regularity. Each query corresponds to a spatial arrangement of several local topographic codes (or tags), which are in themselves too primitive and common to be informative about shape. All the discriminating power derives from relative angles and distances among the tags. The important attributes of the queries are a natural partial ordering corresponding to increasing structure and complexity; semi-invariance, meaning that most shapes of a given class will answer the same way to two queries that are successive in the ordering; and stability, since the queries are not based on distinguished points and substructures. No classifier based on the full feature set can be evaluated, and it is impossible to determine a priori which arrangements are informative. Our approach is to select informative features and build tree classifiers at the same time by inductive learning. In effect, each tree provides an approximation to the full posterior where the features chosen depend on the branch that is traversed. Due to the number and nature of the queries, standard decision tree construction based on a fixed-length feature vector is not feasible. Instead we entertain only a small random sample of queries at each node, constrain their complexity to increase with tree depth, and grow multiple trees. The terminal nodes are labeled by estimates of the corresponding posterior distribution over shape classes. An image is classified by sending it down every tree and aggregating the resulting distributions. The method is applied to classifying handwritten digits and synthetic linear and nonlinear deformations of three hundred L^AT_EX symbols. State-of-the-art error rates are achieved on the National Institute of Standards and Technology database of digits. The principal goal of the experiments on L^AT_EX symbols is to analyze invariance, generalization error and related issues, and a comparison with artificial neural networks methods is presented in this context.

This article has been cited by other articles:

				J. M. Brader, W. Senn, and S. Fusi Learning Real-World Stimuli in a Neural Network with Spike-Driven Synaptic Dynamics Neural Comput., November 1, 2007; 19(11): 2881 - 2912. [Abstract] [Full Text] [PDF]

				W. Li The-more-the-better and the-less-the-better. Bioinformatics, September 15, 2006; 22(18): 2187 - 2188. [Full Text] [PDF]

				T. Hothorn, P. Buhlmann, S. Dudoit, A. Molinaro, and M. J. Van Der Laan Survival ensembles Biostat., July 1, 2006; 7(3): 355 - 373. [Abstract] [Full Text] [PDF]

				G. Blanchard Different Paradigms for Choosing Sequential Reweighting Algorithms Neural Comput., April 1, 2004; 16(4): 811 - 836. [Abstract] [Full Text] [PDF]

				E. C. Gunther, D. J. Stone, R. W. Gerwien, P. Bento, and M. P. Heyes Prediction of clinical drug efficacy by classification of drug-induced genomic expression profiles in vitro PNAS, August 5, 2003; 100(16): 9608 - 9613. [Abstract] [Full Text] [PDF]

				Y. Amit and M. Mascaro Attractor Networks for Shape Recognition Neural Comput., June 1, 2001; 13(6): 1415 - 1442. [Abstract] [Full Text] [PDF]

				Y. Amit and D. Geman A Computational Model for Visual Selection Neural Comput., October 1, 1999; 11(7): 1691 - 1715. [Abstract] [Full Text]