A Theory of Pattern Rejection
COLUMBIA UNIV NEW YORK DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
The efficiency of pattern recognition is critical when there are a large number of classes to be discriminated, or when the recognition algorithm must be applied a large number of times. We propose and analyze a general technique, namely pattern recognition, that leads to great efficiency improvements in both cases. Rejectors are introduced as algorithms that very quickly eliminate from further consideration, most of the classes or inputs depending on the setting. Importantly, a number of rejectors may be combined to form a composite rejector, which performs far more effectively than any of its component rejectors. Composite rejectors are analyzed, and conditions derived which guarantee both efficiency and practicality. A general technique is proposed for the construction of rejectors, based on a single assumption about the pattern classes. The generality is shown through a close relationship with the Karhunen-Loeve expansion. Further, a comparison with Fishers discriminant analysis is included to illustrate the benefits of pattern recognition. Composite rejectors were constructed for two applications, namely, object recognition and local feature detection. In both cases, a substantial improvement in efficiency over existing techniques is demonstrated.
- Test Facilities, Equipment and Methods