The Intrinsic Shape of Point Clouds

Information

• Publication Type: PhD-Thesis
• Workgroup(s)/Project(s):
  • Rendering and Modeling
• Date: July 2012
• Date (Start): September 2006
• Date (End): July 2012
• 1st Reviewer: Dr. F. Samavati
• 2nd Reviewer:
  • Dr. T. Bui
  • Dr. P. Grogono
  • Dr. A. Agarwal
• Rigorosum: 12. July 2012
• First Supervisor: Sudhir Mudur
• Keywords: Surface Reconstruction, Manifold Reconstruction, Point Cloud, Shape Boundary, Gestalt, Curve Reconstruction

Abstract

Given a point cloud, in the form of unorganized points, the problem of automatically connecting the dots to obtain an aesthetically pleasing and piecewise-linear closed interpolating boundary shape has been extensively researched for over three decades. In R3 , it is even more complicated to find an aesthetic closed oriented surface. Most previous methods for shape reconstruction exclusively from coordinates work well only when the point spacing on the shape boundary is dense and locally uniform. The problem of shape construction from non-dense and locally non-uniformly spaced point sets is in our opinion not yet satisfactorily solved. Various extensions to earlier methods do not work that well and do not provide any performance guarantees either. Our main thesis in this research is that a point set, even with non-dense and locally non-uniform spacing, has an intrinsic shape which optimizes in some way the Gestalt principles of form perception. This shape can be formally defined as the minimum of an energy function over all possible closed linear piece-wise interpolations of this point set. Further, while finding this optimal shape is NP-hard, it is possible to heuristically search for an acceptable approximation within reasonable time. Our minimization objective is guided by Gestalt’s laws of Proximity, Good Continuity and Closure. Minimizing curvature tends to satisfy proximity and good continuity. For computational simplification, we globally minimize the longest-edge-in-simplex, since it is intrinsic to a single facet and also a factor in mean curvature. And we require a closed shape. Using such an intrinsic criterion permits the extraction of an approximate shape with a linearithmic algorithm as a simplicial complex, which we have named the Minimum Boundary Complex. Experiments show that it seems to be a very close approximation to the desired boundary shape and that it retains its genus. Further it can be constructed locally and can also handle sensor data with significant noise. Its quick construction is due to not being restricted by the manifold property, required in the boundary shape. Therefore it has many applications where a manifold shape is not necessary, e.g. visualization, shape retrieval, shadow mapping, and topological data analysis in higher dimensions. The definition of the Minimum Boundary Complex is our first major contribution. Our next two contributions include new methods for constructing boundary shapes by transforming the boundary complex into a close approximation of the minimum boundary shape. These algorithms vary a topological constraint to first inflate the boundary complex to recover a manifold hull and then sculpture it to extract a Minimum Boundary approximation, which interpolates all the points. In the R3 method, we show how local minima can be avoided by covering holes in the hull. Finally, we apply a mesh fairing step to optimize mean curvature directly. We present results for shape construction in R2 and R3 , which clearly demonstrate that our methods work better than the best performing earlier methods for non-dense and locally non-uniformly spaced point sets, while maintaining competitive linearithmic complexity.

Additional Files and Images

Weblinks

No further information available.

BibTeX

@phdthesis{ohrhallinger-stefan-2012-the,
  title =      "The Intrinsic Shape of Point Clouds",
  author =     "Stefan Ohrhallinger",
  year =       "2012",
  abstract =   "Given a point cloud, in the form of unorganized points, the
               problem of automatically connecting the dots to obtain an
               aesthetically pleasing and piecewise-linear closed
               interpolating boundary shape has been extensively researched
               for over three decades. In R3 , it is even more complicated
               to find an aesthetic closed oriented surface. Most previous
               methods for shape reconstruction exclusively from
               coordinates work well only when the point spacing on the
               shape boundary is dense and locally uniform. The problem of
               shape construction from non-dense and locally non-uniformly
               spaced point sets is in our opinion not yet satisfactorily
               solved. Various extensions to earlier methods do not work
               that well and do not provide any performance guarantees
               either. Our main thesis in this research is that a point
               set, even with non-dense and locally non-uniform spacing,
               has an intrinsic shape which optimizes in some way the
               Gestalt principles of form perception. This shape can be
               formally defined as the minimum of an energy function over
               all possible closed linear piece-wise interpolations of this
               point set. Further, while finding this optimal shape is
               NP-hard, it is possible to heuristically search for an
               acceptable approximation within reasonable time. Our
               minimization objective is guided by Gestalt’s laws of
               Proximity, Good Continuity and Closure. Minimizing curvature
               tends to satisfy proximity and good continuity. For
               computational simplification, we globally minimize the
               longest-edge-in-simplex, since it is intrinsic to a single
               facet and also a factor in mean curvature. And we require a
               closed shape. Using such an intrinsic criterion permits the
               extraction of an approximate shape with a linearithmic
               algorithm as a simplicial complex, which we have named the
               Minimum Boundary Complex. Experiments show that it seems to
               be a very close approximation to the desired boundary shape
               and that it retains its genus. Further it can be constructed
               locally and can also handle sensor data with significant
               noise. Its quick construction is due to not being restricted
               by the manifold property, required in the boundary shape.
               Therefore it has many applications where a manifold shape is
               not necessary, e.g. visualization, shape retrieval, shadow
               mapping, and topological data analysis in higher dimensions.
               The definition of the Minimum Boundary Complex is our first
               major contribution. Our next two contributions include new
               methods for constructing boundary shapes by transforming the
               boundary complex into a close approximation of the minimum
               boundary shape. These algorithms vary a topological
               constraint to first inflate the boundary complex to recover
               a manifold hull and then sculpture it to extract a Minimum
               Boundary approximation, which interpolates all the points.
               In the R3 method, we show how local minima can be avoided by
               covering holes in the hull. Finally, we apply a mesh fairing
               step to optimize mean curvature directly. We present results
               for shape construction in R2 and R3 , which clearly
               demonstrate that our methods work better than the best
               performing earlier methods for non-dense and locally
               non-uniformly spaced point sets, while maintaining
               competitive linearithmic complexity. ",
  month =      jul,
  address =    "Favoritenstrasse 9-11/E193-02, A-1040 Vienna, Austria",
  school =     "Institute of Computer Graphics and Algorithms, Vienna
               University of Technology ",
  keywords =   "Surface Reconstruction, Manifold Reconstruction, Point
               Cloud, Shape Boundary, Gestalt, Curve Reconstruction",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2012/ohrhallinger-stefan-2012-the/",
}