TY - JOUR
T1 - Classification with nonmetric distances: image retrieval and class representation
JF - Pattern Analysis and Machine Intelligence, IEEE Transactions on
Y1 - 2000
A1 - Jacobs, David W.
A1 - Weinshall,D.
A1 - Gdalyahu,Y.
KW - appearance-based
KW - by
KW - classification;image
KW - correlation;correlation
KW - dataspaces;nonmetric
KW - distances;nonmetric
KW - example;
KW - functions;nonmetric
KW - image
KW - inequality;vector
KW - judgments;robust
KW - MATCHING
KW - methods;image
KW - methods;nonmetric
KW - methods;triangle
KW - points;boundary
KW - points;class
KW - representation;exemplar-based
KW - representation;image
KW - retrieval;learning
KW - retrieval;nearest-neighbor
KW - similarity
KW - vision;atypical
AB - A key problem in appearance-based vision is understanding how to use a set of labeled images to classify new images. Systems that model human performance, or that use robust image matching methods, often use nonmetric similarity judgments; but when the triangle inequality is not obeyed, most pattern recognition techniques are not applicable. Exemplar-based (nearest-neighbor) methods can be applied to a wide class of nonmetric similarity functions. The key issue, however, is to find methods for choosing good representatives of a class that accurately characterize it. We show that existing condensing techniques are ill-suited to deal with nonmetric dataspaces. We develop techniques for solving this problem, emphasizing two points: First, we show that the distance between images is not a good measure of how well one image can represent another in nonmetric spaces. Instead, we use the vector correlation between the distances from each image to other previously seen images. Second, we show that in nonmetric spaces, boundary points are less significant for capturing the structure of a class than in Euclidean spaces. We suggest that atypical points may be more important in describing classes. We demonstrate the importance of these ideas to learning that generalizes from experience by improving performance. We also suggest ways of applying parametric techniques to supervised learning problems that involve a specific nonmetric distance functions, showing how to generalize the idea of linear discriminant functions in a way that may be more useful in nonmetric spaces
VL - 22
SN - 0162-8828
CP - 6
M3 - 10.1109/34.862197
ER -