The DOI matches its Crossref record; 45 of the 45 references it cites were found in a registry or an index.
An Efficient Earth Mover's Distance Algorithm for Robust Histogram Comparison
Abstract
We propose EMD-L1: a fast and exact algorithm for computing the Earth Mover's Distance (EMD) between a pair of histograms. The efficiency of the new algorithm enables its application to problems that were previously prohibitive due to high time complexities. The proposed EMD-L1 significantly simplifies the original linear programming formulation of EMD. Exploiting the L1 metric structure, the number of unknown variables in EMD-L1 is reduced to O(N) from O(N2) of the original EMD for a histogram with N bins. In addition, the number of constraints is reduced by half and the objective function of the linear program is simplified. Formally, without any approximation, we prove that the EMD-L1 formulation is equivalent to the original EMD with a L1 ground distance. To perform the EMD-L1 computation, we propose an efficient tree-based algorithm, Tree-EMD. Tree-EMD exploits the fact that a basic feasible solution of the simplex algorithm-based solver forms a spanning tree when we interpret EMD-L1 as a network flow optimization problem. We empirically show that this new algorithm has an average time complexity of O(N2), which significantly improves the best reported supercubic complexity of the original EMD. The accuracy of the proposed methods is evaluated by experiments for two computation-intensive problems: shape recognition and interest point matching using multidimensional histogram-based local features. For shape recognition, EMD-L1 is applied to compare shape contexts on the widely tested MPEG7 shape data set, as well as an articulated shape data set. For interest point matching, SIFT, shape context and spin image are tested on both synthetic and real image pairs with large geometrical deformation, illumination change, and heavy intensity noise. The results demonstrate that our EMD-L1-based solutions outperform previously reported state-of-the-art features and distance measures in solving the two tasks.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Distinctive Image Features from Scale-Invariant Keypoints
Lowe, D. G. (2004) · International Journal of Computer Vision · doi:10.1023/b:visi.0000029664.99615.94 · Cited by 55,589
A Combined Corner and Edge Detector
Harris, C., & Stephens, M. (1988) · Procedings of the Alvey Vision Conference 1988 · doi:10.5244/c.2.23 · Cited by 12,901
A performance evaluation of local descriptors
Mikolajczyk, K., & Schmid, C. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.188 · Cited by 6,723
Shape matching and object recognition using shape contexts
Belongie, S., Malik, J., & Puzicha, J. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.993558 · Cited by 6,306
Combinatorial Optimization: Algorithms and Complexity.
Johnson, D. S., Papadimitriou, C. H., & Steiglitz, K. (1984) · The American Mathematical Monthly · doi:10.2307/2322374 · Cited by 5,942
Swain, M. J., & Ballard, D. H. (1991) · International Journal of Computer Vision · doi:10.1007/bf00130487 · Cited by 5,623
Divergence measures based on the Shannon entropy
Lin, J. (1991) · IEEE Transactions on Information Theory · doi:10.1109/18.61115 · Cited by 5,140
A new polynomial-time algorithm for linear programming
Karmarkar, N. (1984) · Combinatorica · doi:10.1007/bf02579150 · Cited by 4,794
The Earth Mover's Distance as a Metric for Image Retrieval
Rubner, Y., Tomasi, C., & Guibas, L. J. (2000) · International Journal of Computer Vision · doi:10.1023/a:1026543900054 · Cited by 4,568
Combinatorial optimization:Algorithms and complexity
Rabiner, L. (1984) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1984.1164450 · Cited by 3,576
PCA-SIFT: a more distinctive representation for local image descriptors
Ke, Y., & Sukthankar, R. (2004) · Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. CVPR 2004. · doi:10.1109/cvpr.2004.1315206 · Cited by 3,237
Using spin images for efficient object recognition in cluttered 3D scenes
Johnson, A. E., & Hebert, M. (1999) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.765655 · Cited by 2,599
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (2011) · Cited by 2,083
QBIC project: querying images by content, using color, texture, and shape:
Niblack, C. W., Barber, R., Equitz, W., Flickner, M. D., Glasman, E. H., Petkovic, D., Yanker, P., Faloutsos, C., & Taubin, G. (1993) · SPIE Proceedings · doi:10.1117/12.143648 · Cited by 1,747
Osada, R., Funkhouser, T., Chazelle, B., & Dobkin, D. (2002) · ACM Transactions on Graphics · doi:10.1145/571647.571648 · Cited by 1,661
The Distribution of a Product from Several Sources to Numerous Localities
Hitchcock, F. L. (1941) · Journal of Mathematics and Physics · doi:10.1002/sapm1941201224 · Cited by 1,609
The pyramid match kernel: discriminative classification with sets of image features
Grauman, K., & Darrell, T. (2005) · Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1 · doi:10.1109/iccv.2005.239 · Cited by 1,481
Freeman, W. T., Pasztor, E. C., & Carmichael, O. T. (2000) · International Journal of Computer Vision · doi:10.1023/a:1026501619075 · Cited by 1,459
A sparse texture representation using local affine regions
Lazebnik, S., Schmid, C., & Ponce, J. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.151 · Cited by 1,123
Shape descriptors for non-rigid shapes with a single closed contour
Latecki, L. J., Lakamper, R., & Eckhardt, T. (2002) · Proceedings IEEE Conference on Computer Vision and Pattern Recognition. CVPR 2000 (Cat. No.PR00662) · doi:10.1109/cvpr.2000.855850 · Cited by 833
Efficient color histogram indexing for quadratic form distance functions
Hafner, J., Sawhney, H. S., Equitz, W., Flickner, M., & Niblack, W. (1995) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.391417 · Cited by 833
1-norm Support Vector Machines
Zhu, J., Rosset, S., Tibshirani, R. J., & Hastie, T. J. (2003) · Cited by 797
Recognizing objects in adversarial clutter: breaking a visual CAPTCHA
Mori, G., & Malik, J. (2003) · 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings. · doi:10.1109/cvpr.2003.1211347 · Cited by 596
The Earth Mover's distance is the Mallows distance: some insights from statistics
Levina, E., & Bickel, P. (2002) · Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001 · doi:10.1109/iccv.2001.937632 · Cited by 562
Sebastian, T. B., Klein, P. N., & Kimia, B. B. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1159951 · Cited by 374
Efficient and Robust Retrieval by Shape Content through Curvature Scale Space
Mokhtarian, F., Abbasi, S., & Kittler, J. (1998) · Series on Software Engineering and Knowledge Engineering · doi:10.1142/9789812797988_0005 · Cited by 364
Empirical Evaluation of Dissimilarity Measures for Color and Texture
Rubner, Y., Puzicha, J., Tomasi, C., & Buhmann, J. M. (2001) · Computer Vision and Image Understanding · doi:10.1006/cviu.2001.0934 · Cited by 321
Shape context and chamfer matching in cluttered scenes
Thayananthan, A., Stenger, B., Torr, P. H. S., & Cipolla, R. (2003) · 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings. · doi:10.1109/cvpr.2003.1211346 · Cited by 308
Perceptual Metrics for Image Database Navigation
Rubner, Y., & Tomasi, C. (2001) · Springer eBooks · doi:10.1007/978-1-4757-3343-3 · Cited by 296
The Monge–Kantorovich Mass Transference Problem and Its Stochastic Applications
Rachev, S. T. (1985) · Theory of Probability and Its Applications · doi:10.1137/1129093 · Cited by 295
A SIFT Descriptor with Global Context
Mortensen, E. N., Deng, H., & Shapiro, L. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.45 · Cited by 256
A Note on Asymptotic Joint Normality
Mallows, C. L. (1972) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177692631 · Cited by 249
Distance sets for shape filters and shape recognition
Grigorescu, C., & Petkov, N. (2003) · IEEE Transactions on Image Processing · doi:10.1109/tip.2003.816010 · Cited by 239
Fast contour matching using approximate Earth mover's distance
Grauman, K., & Darrell, T. (2004) · Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. CVPR 2004. · doi:10.1109/cvpr.2004.1315035 · Cited by 215
Shape Matching and Recognition – Using Generative Models and Informative Features
Tu, Z., & Yuille, A. L. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24672-5_16 · Cited by 195
Computational framework for determining stereo correspondence from a set of linear spatial filters
Jones, D. G., & Malik, J. (1992) · Image and Vision Computing · doi:10.1016/0262-8856(92)90015-u · Cited by 191
A distance metric for multidimensional histograms
Werman, M., Peleg, S., & Rosenfeld, A. (1985) · Computer Vision, Graphics, and Image Processing · doi:10.1016/0734-189x(85)90055-6 · Cited by 170
A unified approach to the change of resolution: space and gray-level
Peleg, S., Werman, M., & Rom, H. (1989) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.192468 · Cited by 170
A sparse texture representation using affine-invariant regions
Lazebnik, S., Schmid, C., & Ponce, J. (2003) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2003.1211486 · Cited by 160
Using the Inner-Distance for Classification of Articulated Shapes
Ling, H., & Jacobs, D. W. (2005) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2005.362 · Cited by 144
Self-citationDeformation invariant image matching
Ling, H., & Jacobs, D. W. (2005) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2005.67 · Cited by 134
Self-citationVideo-rate stereo depth measurement on programmable hardware
Darabiha, A., Rose, J., & Maclean, J. (2003) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2003.1211355 · Cited by 117
Shape representation and recognition through morphological curvature scale spaces
Jalba, A. C., Wilkinson, M. H. F., & Roerdink, J. B. T. M. (2006) · IEEE Transactions on Image Processing · doi:10.1109/tip.2005.860606 · Cited by 98
A computational framework for determining stereo correspondence from a set of linear spatial filters
Jones, D. G., & Malik, J. (1992) · Lecture notes in computer science · doi:10.1007/3-540-55426-2_45 · Cited by 43
EMD-L 1: An Efficient and Robust Algorithm for Comparing Histogram-Based Descriptors
Ling, H., & Okada, K. (2006) · Lecture notes in computer science · doi:10.1007/11744078_26 · Cited by 26
Self-citation
Cited by
Computational Optimal Transport
Peyré, G., & Cuturi, M. (2019) · now publishers, Inc. eBooks · doi:10.1561/9781680835519 · Cited by 847
Robust Part-Based Hand Gesture Recognition Using Kinect Sensor
Ren, Z., Yuan, J., Meng, J., & Zhang, Z. (2013) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2013.2246148 · Cited by 746
Distributionally Robust Stochastic Optimization with Wasserstein Distance
Gao, R., & Kleywegt, A. (2023) · Mathematics of Operations Research · doi:10.1287/moor.2022.1275 · Cited by 630
Cracking a hierarchical chaotic image encryption algorithm based on permutation
Li, C. (2016) · Signal Processing · doi:10.1016/j.sigpro.2015.07.008 · Cited by 173
A New Measure of Congruence: The Earth Mover’s Distance
Lupu, N., Selios, L., & Warner, Z. (2017) · Political Analysis · doi:10.1017/pan.2017.2 · Cited by 105
Metadata
- Authors
- Ling, H., & Okada, K.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2007-05
- Volume
- 29
- Issue
- 5
- Pages
- 840-853
- ISSN
- 0162-8828 (ISSN-L)
- 2160-9292
- OpenAlex
- W2163380389
- Cited by
- 414
- References
- 45
- FWCI
- 27.06
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.