Computer Science Colloquium, 2008-2009

Abstract:

We present a new metric between histograms such as SIFT descriptors and a linear time algorithm for its computation. It is common practice to use the L2 metric for comparing SIFT descriptors. This practice assumes that SIFT bins are aligned, an assumption which is often not correct due to quantization, distortion, occlusion etc. In this paper we present a new Earth Mover's Distance (EMD) variant. We show that it is a metric (unlike the original EMD [1] which is a metric only for normalized histograms). Moreover, it is a natural extension of the L1 metric. Second, we propose a linear time algorithm for the com- putation of the EMD variant, with a robust ground distance for oriented gradients. Finally, extensive experimental results on the Mikolajczyk and Schmid dataset [2] show that our method outperforms state of the art distances.