An Efficient Earth Mover's Distance Algorithm for Robust Histogram Comparison

By Haibin Ling, Kazunori Okada. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007

498 citations recorded by the source corpus.

Subfields: Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/45faced0ba839d79127a41707b225382ae856210

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

Citations in the corpus

Distributionally Robust Stochastic Optimization with Wasserstein Distance (2016, unknown): “20 Algorithm 1 Greedy Algorithm 1: θ̄← 0. k← 1. pit, pit← 0, d i t←min(|xjit − ξ̂ i t|, |xjit − ξ̂ i t|), ∀i, t. 2: Sort {dit}1≤i≤N,1≤t≤mi in increasing order, denoted by d i(1) t(1) ≤ di(2)t(2) ≤ . . .≤ d i ( ∑N i=1 mi) t ( ∑N i=1 mi) .”
Computational Optimal Transport (2018, methodology): “Highly efficient dedicated simplex solvers have been devised to solve it; see, for instance, [Ling and Okada, 2007].”
Empirical optimal transport on countable metric spaces: Distributional limits and statistical applications (2017, methodology): “Attempts to solve this problem include specialized algorithms (Gottschlich and Schuhmacher, 2014) and approaches leveraging additional geometric structure of the data (Ling and Okada, 2007; Schmitzer, 2016).”
From Word Embeddings To Document Distances (2015, methodology): “The above optimization is a special case of the earth mover's distance metric (EMD) (Monge, 1781; Rubner et al., 1998; Nemhauser & Wolsey, 1988), a well studied transportation problem for which specialized solvers have been developed (Ling & Okada, 2007; Pele & Werman, 2009).”
Subspace Robust Wasserstein distances (2019, methodology): “This fact was already a common concern of the community when these tools were ﬁrst adopted, as can be seen in the use of (cid:96) 1 costs (Ling & Okada, 2007) or in the common practice of thresholding cost matrices (Pele & Werman, 2009).”
Sinkhorn Distances: Lightspeed Computation of Optimal Transport (2013, unknown): “When n ≥ 2 , embeddings of measures can be used to approximate them in linear time (Indyk and Thaper, 2003; Grauman and Darrell, 2004; Shirdhonkar and Jacobs, 2008) and network simplex solvers can be modiﬁed to run in quadratic time (Gudmundsson et al., 2007; Ling and Okada, 2007).”
Hierarchical Matching of Deformable Shapes (2007, unknown): “) time.”
Fast and robust Earth Mover's Distances (2009, methodology): “Our Rubner’s [29] EMD-L1[20] SIFTDIST[26]”
Robust Part-Based Hand Gesture Recognition Using Kinect Sensor (2013, methodology): “References [36] and [37] applied EMD to shape matching and contour retrieval, which represents the contour by a set of local descriptive features and computes the set of correspondences with minimum EMD costs between the local features.”
A Linear Time Histogram Metric for Improved SIFT Matching (2008, methodology): “Finally, we present experimental results for SIFT matching on the Mikolajczyk and Schmid dataset [2] showing that our method outperforms state of the art distances such as L2, EMD-L1 [20], diffusion distance [21] and EMDMOD [22, 23].”