Name
Abstract | ||
|---|---|---|
We introduce a novel method for computing the earth mover's distance (EMD) between probability distributions on a discrete surface. Rather than using a large linear program with a quadratic number of variables, we apply the theory of optimal transportation and pass to a dual differential formulation with linear scaling. After discretization using finite elements (FEM) and development of an accompanying optimization method, we apply our new EMD to problems in graphics and geometry processing. In particular, we uncover a class of smooth distances on a surface transitioning from a purely spectral distance to the geodesic distance between points; these distances also can be extended to the volume inside and outside the surface. A number of additional applications of our machinery to geometry problems in graphics are presented. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2601097.2601175 | ACM Trans. Graph. |
Keywords | Field | DocType |
earth mover's distance,convex programming,geometric algorithms, languages, and systems,geometric median,finite elements,wasserstein metric,optimal transportation,earth mover s distance | Discretization,Mathematical optimization,Earth mover's distance,Computer science,Geometry processing,Finite element method,Probability distribution,Wasserstein metric,Geometric median,Geodesic | Journal |
Volume | Issue | ISSN |
33 | 4 | 0730-0301 |
Citations | PageRank | References |
14 | 0.52 | 34 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Justin Solomon | 1 | 827 | 48.48 |
| Raif M. Rustamov | 2 | 251 | 19.58 |
| Leonidas J. Guibas | 3 | 13084 | 1262.73 |
| Adrian Butscher | 4 | 423 | 13.41 |