title: Local distance functions: a taxonomy, new algorithms, and an evaluation.
abstract: 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 overfitting. 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.
authors.affiliation: University of California Irvine, 3019 Donald Bren Hall, Irvine, CA 92697-3435, USA. dramanan@ics.uci.edu
authors.forename: Deva
authors.initials: D
authors.lastname: Ramanan
authors.forename: Simon
authors.initials: S
authors.lastname: Baker
mesh_terms: D000465:Algorithms; D001699:Biometry / Q000379:methods*; D005145:Face / Q000033:anatomy & histology*; D006801:Humans; D007089:Image Enhancement / Q000379:methods; D007091:Image Processing, Computer-Assisted / Q000379:methods*; D010363:Pattern Recognition, Automated / Q000379:methods*