A Theory of Pattern Rejection
Abstract
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 Fisher's 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1995
- Accession Number
- ADA608372
Entities
People
- Shree K. Nayar
- Simon Baker
Organizations
- Columbia University