Authors: Vassilis Athitsos, Jonathan Alon, and Stan Sclaroff
Title: Efficient Nearest Neighbor Classification Using a Cascade of
Approximate Similarity Measures
Date: March 16, 2005
Abstract:
Nearest neighbor classification using shape context can yield highly
accurate results in a number of recognition problems. Unfortunately,
the approach can be too slow for practical applications, and thus
approximation strategies are needed to make shape context
practical. This paper proposes a method for efficient and accurate
nearest neighbor classification in non-Euclidean spaces, such as the
space induced by the shape context measure. First, a method is
introduced for constructing a Euclidean embedding that is optimized
for nearest neighbor classification accuracy. Using that embedding,
multiple approximations of the underlying non-Euclidean similarity
measure are obtained, at different levels of accuracy and
efficiency. The approximations are automatically combined to form a
cascade classifier, which applies the slower approximations only to
the hardest cases. Unlike typical cascade-of-classifiers approaches,
that are applied to binary classification problems, our method
constructs a cascade for a multiclass problem. Experiments with a
standard shape data set indicate that a two-to-three order of
magnitude speed up is gained over the standard shape context
classifier, with minimal losses in classification accuracy.