Research On Key Technologies Of Intrinsic Symmetry Detection In3D Geometry Models

Nowadays, geometry processing is currently moving towards high-level shapeanalysis and understanding, aiming at discovering the underlying semantic informationof a3D shape. Symmetry bridges the gap between low level geometry and high levelsemantics. Therefore, symmetry analysis is one of the most important problems ofgeometry processing. Symmetry is widely used in shape analysis tasks such assegmentation, editing, and retrieval. Existing approaches to symmetry detection have sofar been concerning global extrinsic symmetry, global intrinsic symmetry, and partialextrinsic symmetry. Partial intrinsic symmetry is more general in the3D shapes. Itsdetection is harder since it needs to consider both the segmentation and the difficultparameterization issue. Meanwhile, it is difficult to adapt existing symmetry detectionschemes to work on imperfect point clouds with noise and incompleteness. Thus it is ofgreat importance to design an accurate and robust algorithm for intrinsic symmetrydetection.To deal with the major problems of intrinsic symmetry detection on3D shapes, wefocus on the fundamental problems of symmetry representation and detection, andemploy several technologies such as spectral analysis, heat kernel signature, andskeleton based symmetry analysis. The main contributions of this dissertation aresummarized as follows:1. We propose one partial intrinsic symmetry detection algorithm based on iterativecorrespondence refinement. The problem on partial intrinsic symmetry detection ismore difficult due to the complexity of parametric representation and computation.Previous work has studied the detection of partial intrinsic reflectional symmetry. Thealgorithm we present employs symmetry point pairs and voting scheme to obtain partialintrinsic symmetry. Therefore, instead of voting symmetry axis as previous works, werepresent symmetry using a symmetry correspondence matrix which is iterativelyrefined with more generalized partial intrinsic symmetries computed with spectralmethod. Then, we produce meaningful segmentation results guided by the detectedsymmetry.2. We, for the first time, present an definition of multi-scale partial intrinsicsymmetry detection for3D shapes, where the scale of a symmetric region is definedwith intrinsic distances between symmetric points over the region. Symmetry scalereflects important structural information of a3D shape. Based on the definition, wepropose a robust multi-scale partial intrinsic symmetry detection algorithm based onsymmetry point pairs clustering.Symmetry scales increase the search space for multi-scale partial intrinsicsymmetry detection. We decouple scale extraction and symmetry detection by performing two levels of clustering. First, significant symmetry scales are identified byclustering symmetry point pairs from an input shape. We introduce the symmetry scalesignature which estimates the likelihood of two point pairs belonging to symmetries atthe same scale. We obtain the scale clusters with spectral clustering. Then, we performthe second-level spectral clustering, based on a novel point-to-point symmetry affinitymeasure, to extract partial symmetries at that scale. We demonstrate our algorithm oncomplex shapes possessing rich symmetries at multiple scales. Finally, we can naturallyobtain a symmetry driven hierarchical segmentation.3. We propose an intrinsic symmetry detection algorithm based on heat kernelsignature. Shape descriptors are usually used to capture the geometric properties ofshapes, which are usually important in symmetry detection. The heat kernel signature isisometric-invariant, and it can capture geometric properties in multiscale. Therefore, thesignature can be utilized to detect partial intrinsic symmetry detection in multiple scopes.Firstly, the algorithm makes use of heat kernel signature among different time intervalsto catch up the geometric property of shapes, leading to a symmetry correspondencematrix. Finally, we extract partial intrinsic symmetries with signatures in differentscopes using spectral method.4. We present a skeleton-based algorithm for intrinsic symmetry detection onimperfect3D point cloud data. The data imperfections such as noise and incompletenessmake it difficult to reliably compute geodesic distances, which play essential roles inexisting intrinsic symmetry detection algorithms. Previous works have studied thedetection of3D meshes. In this paper, we leverage recent advances in curve skeletonextraction from point clouds for symmetry detection. Our method exploits the propertiesof curve skeletons, such as homotopy to the input shape, approximate isometricinvariance, and skeleton-to-surface mapping.Starting from a curve skeleton extracted from an input point cloud, we firstcompute symmetry electors which are used to vote for symmetric node pairs indicatingthe symmetry map on the skeleton. A symmetry correspondence matrix is constructedfor the input point cloud through transferring the symmetry map from skeleton to pointcloud. The final symmetry regions on the point cloud are detected via spectral analysisover the symmetry correspondence matrix. Experiments on raw point cloudsdemonstrate the robustness of our algorithm. We also apply our method to repairincomplete scans based on the detected intrinsic symmetries. Since the existing skeletonextraction algorithms cannot obtain the map between point cloud and skeleton nodes,we present a practical algorithm to extract skeletons of a3D shape. The core of ouralgorithm is a coupled process of graph contraction and surface clustering. Experimentsdemonstrate that our algorithm obtains a computationally stable and topologicallycorrect skeleton. In addition, More importantly, our algorithmcan result inskeleton-to-surface mapping.