Algorithms for Pattern Rejection

Abstract

The efficiency of pattern recognition is particularly crucial in two situations; whenever there are a large number of classes to discriminate, and, whenever recognition must be performed a large number of times. We develop a number of algorithms to cope with the demands of these difficult conditions. The algorithms achieve high efficiency by using pattern rejectors. A pattern rejector is a generalization of a classifier that quickly eliminates a large fraction of the candidate classes or inputs. After applying a rejector the recognition algorithms can concentrate their computational efforts on verifying the small number of remaining possibilities. The generality of our algorithms is established through a close relationship with the Karhunen-Loeve expansion. We experimented on two representative applications, namely, object recognition and feature detection. The results demonstrate substantial efficiency improvements over existing approaches, most notably Fisher's discriminant analysis (1939).