Matching point sets with respect to the earth mover's distance
The Earth mover's distance (EMD) between two weighted point sets (point distributions) is a distance measure commonly used in computer vision for color-based image retrieval and shape matching. It measures the minimum amount of work needed to transform one set into the other one by weight transportation. The authors study the following shape matching problem: Given two weighted point sets \(A\) and \(B\) in the plane, compute a rigid motion of \(A\) that minimizes its Earth mover's distance to \(B\). No algorithm is known that computes an exact solution to this problem. They present simple FPTASs and polynomial-time \((2+\varepsilon)\)-approximation algorithms for the minimum Euclidean EMD between \(A\) and \(B\) under translations and rigid motions.
- Algorithms – ESA 2005
- An algorithm for matching point sets using the \(l_1\) norm
- Computing and Combinatorics
- ALGORITHMS FOR POINT SET MATCHING WITH k-DIFFERENCES
- Approximating the problem, not the solution: an alternative view of point set matching
- Graph-Based Representations in Pattern Recognition
- Distance measures for point sets and their computation
- Point set pattern matching in \(d\)-dimensions
- Affine matching of two sets of points in arbitrary dimensions
- A Faster Strongly Polynomial Minimum Cost Flow Algorithm
- Algebraic optimization: The Fermat-Weber location problem
- Algorithms and Computation
- Dynamic algorithms for geometric spanners of small diameter: Randomized solutions
- Fast approximations for sums of distances, clustering and the Fermat-Weber problem
- scientific article; zbMATH DE number 437554 (Why is no real title available?)
- scientific article; zbMATH DE number 1803754 (Why is no real title available?)
- scientific article; zbMATH DE number 1808087 (Why is no real title available?)
- scientific article; zbMATH DE number 1305475 (Why is no real title available?)
- scientific article; zbMATH DE number 2062646 (Why is no real title available?)
- scientific article; zbMATH DE number 1424291 (Why is no real title available?)
- Matching Shapes with a Reference Point
- Network flows. Theory, algorithms, and applications.
- The earth mover's distance as a metric for image retrieval
- Using geometry to solve the transportation problem in the plane
- Elastic geometric shape matching for translations under the Manhattan norm
- Selecting a subset of diverse points based on the squared Euclidean distance
- FPTAS for minimizing the earth mover's distance under rigid transformations and related problems
- scientific article; zbMATH DE number 175988 (Why is no real title available?)
- scientific article; zbMATH DE number 2062646 (Why is no real title available?)
- Computing and Combinatorics
- On geometric prototype and applications
- Approximate minimum-weight matching with outliers under translation
- Approximate Map Matching with respect to the Fréchet Distance
- Minimizing the Weighted Directed Hausdorff Distance between Colored Point Sets under Translations and Rigid Motions
- Algorithms – ESA 2005
- ALGORITHMS FOR POINT SET MATCHING WITH k-DIFFERENCES
- Minimizing the weighted directed Hausdorff distance between colored point sets under translations and rigid motions
- A data-dependent approach for high-dimensional (robust) Wasserstein alignment
- Fine-grained complexity of Earth mover's distance under translation
This page was built for publication: Matching point sets with respect to the earth mover's distance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2462736)
