Topological Methods for 3D Point Cloud Processing

Abstract

3D point cloud datasets are becoming more common due to the availability of low-cost sensors. Light detection and ranging (LIDAR), stereo, structured light, and time-of-flight (ToF) are examples of sensors that capture a 3D representation of the environment. These sensors are increasingly found in mobile devices and machines such as smartphones, tablets, robots, and autonomous vehicles. As hardware technology advances, algorithms and data structures are needed to process the data generated by these sensors in innovative and meaningful ways. This dissertation develops and applies algebraic topological methods for processing 3D point cloud datasets. The area of topological data analysis (TDA) has matured in recent years allowing researchers to analyze point cloud datasets using techniques that take into account the 'shape' of the data. This includes topological features such as connected components, holes, voids, and higher dimensional analogs. These ideas have been successfully applied to datasets which are naturally embedded in a metric space (such as Euclidean space) where distances between points can be used to form a parameterized sequence of spaces. By studying the changing topology of this sequence we gain information about the underlying data. In the first part of the thesis, we present a fast approach to build a 3D Vietoris-Rips complex which allows us to approximate the topology of a point cloud. The construction of the complex is done in three parallelized phases: nearest neighbors search, edge list generation, and triangle list generation. The edge and triangle lists can then be used for persistent homology computations. In the second part of the thesis, we present approaches to segment 3D point cloud data using ideas from persistent homology theory. The proposed algorithms first generate a simplicial complex representation of the point cloud dataset. Then, the zeroth homology group of the complex which corresponds to the number of connected components is computed. Finally, we extract the clusters of each connected component in the dataset. We show that these methods provide a stable segmentation of point cloud data under the presence of noise and poor sampling conditions, thus providing advantages over contemporary segmentation procedures. In the third part of the thesis, we address an open problem in computational topology by introducing a nearly linear time algorithm for incrementally computing topologically persistent 1-cycles. Further, we develop a second algorithm that utilizes the output of the first to generate a spanning tree upon which non-bounding minimal 1-cycles can be computed. These non-bounding minimal 1-cycles are then used to locate and fill holes in a dataset. Experimental results show the efficacy of our algorithms for reconstructing the surface of 3D point clouds produced by noisy sensor data. In the fourth part of the thesis, we develop a global feature descriptor termed Signature of Topologically Persistent Points (STPP) that encodes topological invariants (zeroth and first homology groups) of 3D point cloud data. STPP is a competitive 3D point cloud descriptor when compared to the state of art and is resilient to noisy sensor data. We demonstrate experimentally that STPP can be used as a distinctive signature, thus allowing for 3D point cloud processing tasks such as object detection and classification. This dissertation makes progress towards effective, efficient, and scalable topological methods for 3D point cloud processing along two directions. We present algorithms with an analysis of their theoretical performance and proof of correctness. We also demonstrate the feasibility and applicability of our results with experiments using publicly available datasets.