Premium
An Optimal Transport Approach to Robust Reconstruction and Simplification of 2D Shapes
Author(s) -
de Goes Fernando,
CohenSteiner David,
Alliez Pierre,
Desbrun Mathieu
Publication year - 2011
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2011.02033.x
Subject(s) - delaunay triangulation , bowyer–watson algorithm , constrained delaunay triangulation , computer science , decimation , point cloud , outlier , noise (video) , point (geometry) , algorithm , set (abstract data type) , ranging , triangulation , simplicial complex , geometry processing , mathematical optimization , mathematics , artificial intelligence , computer vision , polygon mesh , image (mathematics) , geometry , combinatorics , computer graphics (images) , telecommunications , filter (signal processing) , programming language
We propose a robust 2D shape reconstruction and simplification algorithm which takes as input a defect‐laden point set with noise and outliers. We introduce an optimal‐transport driven approach where the input point set, considered as a sum of Dirac measures, is approximated by a simplicial complex considered as a sum of uniform measures on 0‐ and 1‐simplices. A fine‐to‐coarse scheme is devised to construct the resulting simplicial complex through greedy decimation of a Delaunay triangulation of the input point set. Our method performs well on a variety of examples ranging from line drawings to grayscale images, with or without noise, features, and boundaries.