"Local Distance Functions: A Taxonomy, New Aglorithms, and an Evaluation

paper

We present a taxonomy for local distance functions where most existing algorithms can be regarded as approximations of the geodesic distance defined by a metric tensor. We categorize existing algorithms by how, where, and when they estimate the metric tensor. We also extend the taxonomy along each axis. How: We introduce hybrid algorithms that use a combination of techniques to ameliorate over-fitting. Where: We present an exact polynomial time algorithm to integrate the metric tensor along the lines between the test and training points under the assumption that the metric tensor is piecewise constant. When: We propose an interpolation algorithm where the metric tensor is sampled at a number of references points during the offline phase. The reference points are then interpolated during the online classification phase. We also present a comprehensive evaluation on tasks in face recognition, object recognition, and digit recognition.


D. Ramanan, S. Baker. "Local Distance Functions: A Taxonomy, New Algorithms, and an Evaluation" International Conference on Computer Vision (ICCV) Kyoto, Japan, Sept. 2009.

PDF Supplementary Results


References for datasets and feature vector construction

Datasets

MultiPIE Data Caltech 101 Data MNIST Data Readme



To allow comparisons with our work, we are making computed feature vectors, class membership data, and training-test partitions of our experimental evaluation available in the above links. We gladly acknowledge the original authors of the above datasets - Gross et al., Fei-Fei at al., and Lecun and Cortes. We also gladly acknowledge Killian Weibgerger for providing code for Large Margin Nearest Neighbors (LMNN) and Svetlana Lazebnik for providing code for spatial pyramid kernels.