EMD-L1: An Efficient and Robust Algorithm for Comparing Histogram-Based Descriptors

Abstract

We propose a fast algorithm, EMD- L _1, for computing the Earth Mover’s Distance (EMD) between a pair of histograms. Compared to the original formulation, EMD- L _1 has a largely simplified structure. The number of unknown variables in EMD- L _1 is O ( N ) that is significantly 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 objective function is also simplified. We prove that the EMD- L _1 is formally equivalent to the original EMD with L _1 ground distance without approximation. Exploiting the L _1 metric structure, an efficient tree-based algorithm is designed to solve the EMD- L _1 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 practically impossible with previous algorithms. We conducted experiments for shape recognition and interest point matching. EMD- L _1 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- L _1-based solutions outperform previously reported state-of-the-art features and distance measures in solving the two tasks.