Circular Earth Mover's Distance for the comparison of local features

Many computer vision algorithms make use of local features, and rely on a systematic comparison of these features. The chosen dissimilarity measure is of crucial importance for the overall performances of these algorithms and has to be both robust and computationally efficient. Some of the most popular local features (like SIFT [4] descriptors) are based on one-dimensional circular histograms. In this contribution, we present an adaptation of the Earth Mover's Distance to one-dimensional circular histograms. This distance, that we call CEMD, is used to compare SIFT-like descriptors. Experiments over a large database of 3 million descriptors show that CEMD outperforms classical bin-to-bin distances, while having reasonable time complexity.