【作者】 姜巍；

【导师】 金士尧；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2013， 博士

【摘要】 当今数字几何处理研究对象正逐步从低层次的几何属性向高层次的语义属性跨越。三维几何模型的对称性是关联模型低层次几何信息与高层次语义信息的重要桥梁。对称性分析是几何处理领域的重要问题，广泛应用于三维几何模型的分割、编辑、检索等领域。当前，三维几何模型的对称检测工作主要集中在全局外蕴对称检测，局部外蕴对称检测以及全局内蕴对称检测。局部内蕴对称在三维几何体中更具一般性，但由于需要考虑对称和分割以及内蕴变换难以参数化而更为复杂，局部内蕴对称检测仍是三维形状分析领域的难点问题。此外，已有的内蕴对称检测方法不能处理有噪声及数据缺失的点云模型。针对此类数据，研究鲁棒的内蕴对称检测算法具有一定的理论和实际意义。本文针对三维几何模型内蕴对称检测的难点问题，利用谱分析、热核描述符、基于骨架的对称性分析等方法，针对三维几何模型内蕴对称检测的基础性问题展开研究，主要工作和创新点如下：1、提出一种三维几何模型局部内蕴对称检测方法。局部内蕴对称难以参数化表示，且求解复杂，已有算法只能处理局部反射对称。本文利用对称点对表征模型的局部内蕴对称，采用选举策略获取对称。但不同于直接选举反射对称轴的方法，本方法不局限于反射对称，而是将复杂的局部对称变换以对称对应关系矩阵的形式表示，并采用谱分析方法和迭代精化方法提取模型的对称。对于复杂的三维几何模型，本算法可以有效的检测出局部内蕴对称。更进一步，利用对称性得到三维模型的有意义分割。2、本文首次提出了多尺度局部内蕴对称检测问题。在本文中，对称尺度是根据对称部分之间的内蕴距离定义的，反映模型重要的结构属性。已有的对称检测算法未考虑对称的尺度信息。以多尺度局部内蕴对称的定义为基础，本文提出了一种基于对称点对聚类的三维几何模型多尺度对称检测算法。多尺度局部内蕴对称检测在求解过程中加入了对称尺度信息，增大了对称搜索空间。本文将对称尺度获取过程与局部内蕴对称检测过程分离。首先利用选举方法获取表征模型局部内蕴对称的对称点对，建立与对称尺度相关的对称点对描述符。根据描述符差距对对称点对进行聚类，获取模型的对称尺度。然后根据每个聚类中的对称点对分别采用谱方法获取模型在该尺度上的局部内蕴对称，最终得到三维几何模型多个尺度上的局部内蕴对称。最后，基于多尺度对称得到三维模型的层次分割。3、提出一种基于热核描述符的三维几何模型内蕴对称检测算法。对称检测过程中通常采用一种描述符获取模型的局部几何属性，并根据描述符的差距获取初始的对应关系。描述符考虑不同范围，对对称检测结果有重要影响。热核描述符可以度量模型上不同范围的几何属性，并具有等距变换不变性，可以应用于局部内蕴对称检测。本文利用两个时间范围的热核描述符度量模型的局部几何属性，分别构建对称对应关系矩阵，得到了三维几何模型在不同范围描述符下的局部内蕴对称。4、针对有噪声和数据缺失的三维点云模型，本文提出一种基于骨架的内蕴对称检测算法。三维点云模型通常包含噪声以及遮挡引起的数据缺失，难以准确计算模型表面点之间的测地距。而测地距是大多数内蕴对称检测算法的基础，因此现有的对称检测方法通常只能处理网格模型。骨架是三维模型的紧致、精简表示，包含了模型的重要几何属性和拓扑属性，同时具有不易受噪声和数据缺失影响的特点。此外，骨架结点与模型表面顶点的对应关系可实现基于骨架的表面模型对称性分析。对于给定的三维点云模型，首先提取其曲线骨架。以选举方法获取反映模型表面点间对称性的骨架点对，并根据这些骨架点对将对称扩展到模型表面顶点。借助骨架获取有噪声和数据缺失点云模型的对称，进而通过对称对应关系矩阵和谱方法获取点云模型上的对称区域。实验表明本文算法可以检测三维点云模型的内蕴对称，对于噪声和数据缺失具有较好的鲁棒性。此外，该对称检测结果还可用于修补具有缺失部分的三维扫描点云数据。由于以往的点云模型骨架提取算法通常不能直接获取骨架结点与模型表面顶点的对应关系，本文提出了一种实用的骨架提取算法，其核心是迭代的图收缩和模型表面顶点聚类。该方法计算稳定、可得到拓扑正确的骨架，同时可得到模型表面顶点与骨架结点的对应关系。更多还原

【Abstract】 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.更多还原