Class representation and image retrieval with non-metric distances

TitleClass representation and image retrieval with non-metric distances
Publication TypeJournal Articles
Year of Publication2000
AuthorsJacobs DW, Weinshall D, Gdalyahu Y
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI)
Pagination1 - 1
Date Published2000///

One of the key problems in appearance-based vision is understanding how to use a set oflabeled images to classify new images. Classification systems that can model human perfor-
mance, or that use robust image matching methods, often make use of similarity judgments that
are non-metric; but when the triangle inequality is not obeyed, most existing pattern recogni-
tion techniques are not applicable. We note that exemplar-based (or nearest-neighbor) methods
can be applied naturally when using a wide class of non-metric 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 for finding class representatives
are ill-suited to deal with non-metric dataspaces.
We then focus on developing techniques for solving this problem, emphasizing two points:
First, we show that the distance between two images is not a good measure of how well one
image can represent another in non-metric spaces. Instead, we use the vector correlation
between the distances from each image to other previously seen images. Second, we show that
in non-metric spaces, boundary points are less significant for capturing the structure of a class
than they are 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 using both synthetic and real images.