CMU-CS-02-161Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-02-161
Shyjan Mahamud December 2002 Ph.D. Thesis
CMU-CS-02-161.ps
Keywords: Object detection, nearest neighbor search, optimal
distance measure, efficient search, discrimination
A distance measure that minimizes the mis-classification risk for the 1-nearest neighbor search can be shown to be the probability that a pair of input measurements belong to different classes. This pair-wise probability is not in general a metric distance measure. Furthermore, it can out-perform any metric distance, approaching even the Bayes optimal performance. In practice, we seek a model for the optimal distance measure that combines the discriminative powers of more elementary distance measures associated with a collection of simple feature spaces that are easy and efficient to implement; in our work, we use histograms of various feature types like color, texture and local shape properties. We use a linear logistic model combining such elementary distance measures that is supported by observations of actual data for a representative discrimination task. For performing efficient nearest neighbor search over large training sets, the linear model was extended to discretized distance measures that combines distance measures associated with discriminators organized in a tree-like structure. The discrete model was combined with the continuous model to yield a hierarchical distance model that is both fast and accurate. Finally, the nearest neighbor search over object parts was integrated into a whole object detection system and evaluated against both an indoor detection task as well as a face recognition task yielding promising results. 139 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |