Linearized multidimensional earth-mover's-distance gradient flows

This paper presents the first framework capable of performing active contour segmentation using Earth Mover's Distance (EMD) to measure dissimilarity between multidimensional feature distributions. EMD is the best known and understood cross-bin histogram distance measure, and as such it allows for meaningful comparisons between distributions, unlike bin-to-bin measures that only account for discrepancies on a bin-to-bin basis. Because EMD is obtained with linear programming techniques, its differential structure with respect to variations in bin weights as the active contour evolves is expressed through sensitivity analysis. Euler-Lagrange equations are then derived from the computed sensitivity at every iteration to produce gradient descent flows. We validate our approach with color image segmentation, in comparison with state-of-the-art Bhattacharyya (bin-to-bin) and 1D EMD (cross-bin) active contours. Some unique advantages of cross-bin comparison are highlighted in our segmentation results: better perceptual value and increased robustness with respect to the initialization.