Citation
S. Justin, R. Rustamov, L. Guibas, A. Butscher. "Earth Mover’s Distances on Discrete Surfaces". ACM Transactions on Graphics (SIGGRAPH), 2014.

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.

Electronic downloads

• w1.pdf · application/pdf · 15271 kbytes

• HTML

  S. Justin, R. Rustamov, L. Guibas, A. Butscher. <a
  href="http://robotics.eecs.berkeley.edu/pubs/19.html"
  >Earth Mover’s Distances on Discrete
  Surfaces</a>, ACM Transactions on Graphics (SIGGRAPH),
  2014.

• Plain text

  S. Justin, R. Rustamov, L. Guibas, A. Butscher. "Earth
  Mover’s Distances on Discrete Surfaces". ACM
  Transactions on Graphics (SIGGRAPH), 2014.

• BibTeX

  @inproceedings{JustinRustamovGuibasButscher14_EarthMoversDistancesOnDiscreteSurfaces,
      author = {S. Justin and R. Rustamov and L. Guibas and A.
                Butscher},
      title = {Earth Mover’s Distances on Discrete Surfaces},
      booktitle = {ACM Transactions on Graphics (SIGGRAPH)},
      year = {2014},
      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.},
      URL = {http://robotics.eecs.berkeley.edu/pubs/19.html}
  }
  

Posted by Ehsan Elhamifar on 7 Jun 2014.
Groups: ehumans
For additional information, see the Publications FAQ or contact webmaster at robotics eecs berkeley edu.