Earth Mover’s Distances on Discrete Surfaces

摘要

We introduce a novel method for computing the earth mover’s distancern(EMD) between probability distributions on a discrete surface.rnRather than using a large linear program with a quadraticrnnumber of variables, we apply the theory of optimal transportationrnand pass to a dual differential formulation with linear scaling. Afterrndiscretization using finite elements (FEM) and development ofrnan accompanying optimization method, we apply our new EMDrnto problems in graphics and geometry processing. In particular,rnwe uncover a class of smooth distances on a surface transitioningrnfrom a purely spectral distance to the geodesic distance betweenrnpoints; these distances also can be extended to the volume insidernand outside the surface. A number of additional applications of ourrnmachinery to geometry problems in graphics are presented.