Matching point sets with respect to the earth mover's distance (Q2462736)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Matching point sets with respect to the earth mover's distance |
scientific article |
Statements
Matching point sets with respect to the earth mover's distance (English)
0 references
3 December 2007
0 references
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.
0 references
geometric optimization
0 references
approximation algorithms
0 references
shape matching
0 references
earth mover's distance
0 references
weighted point sets
0 references
rigid motions
0 references