Three-Dimensional Shape Restoration and Recognition Methods

In this dissertation, we study different methods for recognition, matching, and restoration of three-dimensional shapes and range data. In the first part of the dissertation, a geometric framework for the recognition of three-dimensional objects represented by point clouds is introduced. The proposed approach is based on computing a number of signatures for each point cloud object based on the histograms of various intrinsic measurements on the point cloud, and comparing these signatures with those of other objects. The first method we introduce is the histogram of pairwise diffusion distances between all points on the shape surface. The diffusion distance between two points is related to the probability of traveling from one of the points to the other in a fixed number of random steps. This signature is augmented by the histogram of the pairwise geodesic distances in the point cloud, the distribution of the ratio between these two distances, as well as the distribution of the number of times each point lies on the shortest paths between other pairs of points. These signatures are not only geometric but also invariant to bends. We further augment these signatures by the distribution of a curvature function and the distribution of a curvature weighted distance. A combination of these histograms for each object are compared to those for other objects using the chi 2 or other common distance metrics for distributions. The presentation of the framework is accompanied by theoretical and geometric justification and state-of-the-art experimental results. We also present a detailed analysis of the particular relevance of each proposed histogram-based signature. Finally, we briefly discuss a more local approach where the histograms are computed for a number of overlapping patches from the object rather than the whole shape, thereby opening the door to partial shape comparisons.;In the second part of the dissertation, the problem of non-rigid shape recognition is viewed from the perspective of metric geometry, and the applicability of diffusion distances within the Gromov-Hausdorff framework is explored. The diffusion distance provides an intrinsic distance measure for this application which is robust against topological changes, such as those due to natural non-rigid deformations, as well as acquisition and representation noise. The presentation of the proposed framework is complemented with numerous examples demonstrating that in addition to the relatively low complexity involved in the computation of the diffusion distances between surface points, the performances of recognition and matching based on diffusion distances compare favorably against methods based on the classical geodesic distances, especially in the presence of topological changes between the non-rigid shapes.;In the third part of this dissertation, the problem of denoising and occlusion restoration of 3D range data based on dictionary learning and sparse representations is explored. Sparse signal representations, in particular with learned dictionaries, are widely used for state-of-the-art audio, image, and video restoration. We consider the 3D surface as an image, where the value of each pixel represents the depth of a point on the 3D surface. Having this image, we apply techniques from dictionary learning and sparse representation to enhance the acquired 3D surface. These techniques use the sparse decomposition of the overlapping patches in the image over an adapted overcomplete dictionary. We present experimental results on denoising 3D surfaces following this approach. These experiments are based on range-data obtained from a low-cost structured-light range scanner and other available datasets. We extend the proposed range-data sparse modeling approach, derive an algorithm for filling missing regions on 3D scans, and also apply it to increase the resolution of 3D shapes with non-uniform meshes.