Graph signal processing for point cloud sampling and restoration

Point cloud (PC) consists of discrete points that are irregular samples of 2D surfaces of physical objects in 3D space. PCs acquired from consumer-level sensors often have noise corruption and/or lower resolution than desired. Thus, denoising and super-resolution steps are necessary. On the other hand, PC models obtained from high-end devices are often very large in size, which increase the computational burden of subsequent operations. Thus, PC sub-sampling while preserving the PC's geometric structure is important. In this thesis, leveraging recent advances in graph signal processing (GSP), we propose several algorithms to address the aforementioned problems for PC: denoising, super-resolution, and sub-sampling. For PC denoising, we formulate a maximum a posteriori (MAP) optimization problem using a signal prior called signal-dependent feature graph Laplacian regularizer (SDFGLR) that promotes piecewise smoothness (PWS) of surface normals with respect to a similarity graph. The problem is solved using conjugate gradient (CG) or accelerated proximal gradient (APG) depending on noise type, with bounded condition numbers to ensure numerical stability. We propose simple filters to estimate noise variance, used to compute a weight parameter trading off the fidelity term and the SDFGLR prior. For PC super-resolution, we first initialize new points at centroids of locally constructed triangles in the low-resolution PC. Next, we formulate an optimization problem to refine the newly added 3D coordinates to promote PWS of the resulting PC surface using SDFGLR. Finally, for PC sub-sampling, we propose an efficient algorithm to select a point subset while minimizing a global error term. We first show that minimizing a worst-case reconstruction error is equivalent to maximizing the smallest eigenvalue λmin of matrix H^TH + µL, where H is a sampling matrix and L is a symmetric, positive semi-definite matrix computed from a neighborhood graph connecting the 3D points. Instead of maximizing λmin (H^TH + µL), for fast computation, we maximize its lower bound by adapting a recent fast graph sampling algorithm called Gershgorin Disc Alignment Sampling (GDAS) to more general unbalanced signed graphs. Extensive experimental results show that our proposed methods for PC denoising, super-resolution and sub-sampling outperform existing methods qualitatively and quantitatively for a wide range of synthesized and real PC models.