Neighborhood Data Structures, Manifold Properties, and Processing of Point Set Surfaces

Abstract

The PhD thesis, titled “Efficient Coordinates for Point Set Surfaces”, is concerned with point sets acquired by 3D acquisition techniques and their processing. The thesis covers and advances both theoretical and applied aspects of the field.

The first topic concerns notions of neighborhood and corresponding data structures. Despite their advantages in storage space and easy acquisition, the missing neighborhood relation is a significant downside to point set representations. The first part of the thesis establishes a novel neighborhood relation concept that relies on a bilateral weighting between Euclidean point distances and distances in the normal field. Experiments prove the superiority against combinatorial or purely metrical neighborhoods in the presence of noise or outliers. Furthermore, the first part of the thesis is concerned with data structures for the fast computation of neighborhoods. It contains several novel theorems on the neighborhood grid data structure which provides a fast and parallelizable means to compute approximations of neighborhoods. The thesis further contributes to the literature on neighborhood data structures by an accessible discussion of the main theorem on k-d trees.

The second part of the thesis deals with manifold structures for point set surfaces. From a significant amount of real-world objects, while 3D-scanning those, only the surface is acquired for further processing in CAD or other applications. As the surface of the underlying real-world geometry has the structure of a manifold, it can be expected that this structure is reflected by any point set acquired from the geometry. The thesis establishes a scheme to interpret point sets in terms of their implicitly underlying manifolds. It describes a methodology based on the Moving Least Squares (MLS) framework to obtain both local coordinate charts and chart transition maps from a raw point cloud. Furthermore, it translates the approach of Variational Shape Approximation (VSA) to point sets. The most significant contribution at this end is the description of failure-cases of the previous VSA approach and the presentation of a VSA algorithm which terminates for all input cases.

Third and finally, algorithms have to work efficiently and robustly on the input point set. While meshed geometries provide an intuitive and natural weighting by the areas of the faces, point sets can at most work with distances between the points. This introduces a new level of difficulty to be overcome by any point set processing algorithm. The third chapter of the thesis introduces a novel weighting scheme to counteract non-uniformity in point sets. Additionally, it draws from the MLS framework to build a feature detection algorithm with mathematical guarantees. A third application area is the denoising of point sets. In this field, the thesis presents an iterative denoising scheme to efficiently handle both isotropic and anisotropic cases.

In summary, the thesis contributes to all aspects of the point set processing pipeline. Both theoretical advances and practical advances are made. All contributions are practically evaluated in the context of several application areas.