Earth Mover’s Distances on Discrete Surfaces
S. Justin, R. Rustamov, L. Guibas, A. Butscher

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
Citation formats  
  • 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.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.