Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

An efficient Earth Mover's Distance algorithm for robust histogram comparison.

Haibin Ling1, Kazunori Okada

  • 1Department of Computer Science and UMIACS, A.V. Williams Building, Univerisity of Maryland, College Park, MD 20742, USA. hbling@umiacs.umd.edu

IEEE Transactions on Pattern Analysis and Machine Intelligence
|March 16, 2007
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Conserved trans-regulatory logic and evolving cis-modules drive the diversification of inducible diterpenoid biosynthetic gene clusters across the Oryzoideae.

Plant & cell physiology·2026
Same author

Genomic Basis of Lifestyle Divergence in Rice-Associated <i>Burkholderia</i>: From Pathogenesis to Plant Growth Promotion.

International journal of molecular sciences·2026
Same author

Rice Genotype-Dependent Phyllosphere Microbiome Assembly and Isolation of Antagonistic <i>Burkholderia</i> for Sheath Blight Biocontrol.

International journal of molecular sciences·2026
Same author

GEOMETRY OF LONG-TAILED REPRESENTATION LEARNING: REBALANCING FEATURES FOR SKEWED DISTRIBUTIONS.

... International Conference on Learning Representations·2026
Same author

Identification of essential residues for the biosynthesis of momilactone intermediate diterpene in wild rice Oryza officinalis.

The Biochemical journal·2026
Same author

Structural characterization of the native oligomerization mode of MvaT proteins in <i>Pseudomonas</i>.

Microbiology spectrum·2026
Same journal

Relation DETR+: Exploring Explicit Position Relation Prior for Dense Prediction.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

RBF++: Quantifying and Optimizing Reasoning Boundaries across Measurable and Unmeasurable Capabilities for Chain-of-Thought Reasoning.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

CAFE: Cross-View Adaptive Fusion and Cluster Center Enhancement for Robust Multi-View Clustering.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

DIVER: Reinforced Diffusion Breaks Imitation Bottlenecks in End-to-End Autonomous Driving.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Ethics-Aware Safe Reinforcement Learning for Rare-Event Risk Control in Interactive Urban Driving.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Learning Shape Anchors for Holistic Indoor Scene Understanding.

IEEE transactions on pattern analysis and machine intelligence·2026
See all related articles

We introduce EMD-L1, a fast algorithm for Earth Mover's Distance (EMD) computation between histograms. This efficient method simplifies EMD calculations and improves performance in tasks like shape recognition and interest point matching.

Area of Science:

  • Computer Vision
  • Machine Learning
  • Computational Geometry

Background:

  • Earth Mover's Distance (EMD) is a powerful metric for comparing probability distributions, often represented as histograms.
  • Traditional EMD computation involves complex linear programming with high time complexity, limiting its application.
  • Existing methods struggle with large datasets and computationally intensive tasks like detailed shape and feature matching.

Purpose of the Study:

  • To develop a novel, efficient, and exact algorithm for computing Earth Mover's Distance (EMD) between histograms.
  • To significantly reduce the computational complexity of EMD calculations.
  • To enable the application of EMD to previously intractable problems in computer vision and pattern recognition.

Main Methods:

Related Experiment Videos

  • Proposed EMD-L1 algorithm, simplifying the linear programming formulation of EMD by exploiting L1 metric structure.
  • Reduced the number of variables to O(N) and constraints by half compared to original EMD.
  • Developed an efficient tree-based algorithm, Tree-EMD, leveraging network flow optimization principles.

    • Main Results:

    • EMD-L1 achieves an average time complexity of O(N^2), a substantial improvement over prior supercubic complexities.
    • The algorithm is proven to be an exact formulation equivalent to EMD with L1 ground distance.
    • Experiments demonstrated superior performance in shape recognition (MPEG7, articulated shapes) and interest point matching (SIFT, shape context, spin images).

    Conclusions:

    • EMD-L1 offers a computationally efficient and accurate solution for histogram comparison.
    • The algorithm significantly enhances performance in demanding computer vision tasks, outperforming state-of-the-art methods.
    • This advancement opens new possibilities for applying EMD in large-scale pattern recognition and data analysis.