Abstract

We propose a fast algorithm, EMD-L1 , for computing the Earth Mover’s Distance (EMD) between a pair of histograms. Compared to the original formulation, EMD-L1 has a largely simplified structure. The number of unknown variables in EMD-L1 is O(N ) that is signifi- cantly less than O(N 2 ) of the original EMD for a histogram with N bins. In addition, the number of constraints is reduced by half and the ob jec- tive function is also simplified. We prove that the EMD-L1 is formally equivalent to the original EMD with L1 ground distance without ap- proximation. Exploiting the L1 metric structure, an efficient tree-based algorithm is designed to solve the EMD-L1 computation. An empirical study demonstrates that the new algorithm has the time complexity of O(N 2 ), which is much faster than previously reported algorithms with super-cubic complexities. The proposed algorithm thus allows the EMD to be applied for comparing histogram-based features, which is practi- cally impossible with previous algorithms. We conducted experiments for shape recognition and interest point matching. EMD-L1 is applied to compare shape contexts on the widely tested MPEG7 shape dataset and SIFT image descriptors on a set of images with large deformation, illumination change and heavy noise. The results show that our EMD-L1 - based solutions outperform previously reported state-of-the-art features and distance measures in solving the two tasks.