Current Issue Cover

杨军,张鹏(兰州交通大学电子与信息工程学院, 兰州 730070;兰州交通大学自动化与电气工程学院, 兰州 730070)

摘 要
目的 针对已有的3维模型分割方法人为设定过多参数的问题,提出了一种基于拓扑持续性和热亲和度矩阵的3维模型分割方法,只需给定分割部件数即可自动完成分割。方法 首先通过拓扑持续性处理3维模型的热核签名,选取生存期最长的几个特征点作为模型被分割部件的显著特征点,对于模型躯干等无法通过生长周期选取特征点的部件,则选取热核签名的最小值所对应的顶点作为显著特征点,从而获得模型的初始聚类中心;然后使用不同的扩散时间所对应的热亲和度矩阵进行k-means聚类,并根据聚类中心的偏移距离等参数筛选聚类结果,从而获得3维模型的分割结果。结果 选取人体模型进行分割实验,并与其他方法进行对比分析。结果表明,所提出的热亲和度的计算时间明显优于常用的测地距离和幂指数核;相比基于拓扑持续性和基于测地距离的聚类,本文方法可以正确分割模型的各个部件并获得恰当的分割边界。此外,本文方法针对姿态不同的同一非刚体3维模型可以取得一致性的分割结果,而且对模型表面噪声具有较好的鲁棒性。结论 和已有方法相比,本文的基于拓扑持续性和热亲和度矩阵的3维模型分割方法可以在给定分割部件的前提下自动选定聚类中心并获得恰当的分割边界,并广泛适用于常见动物模型的分割。
Three-dimensional shape segmentation by combining topological persistence and heat diffusion theory

Yang Jun,Zhang Peng(School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China;School of Automation & Electrical Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)

Objective Shape segmentation is a fundamental problem in shape analysis. Automatic shape segmentation contributes to various shape processing and 3D modeling applications, such as shape retrieval, partial matching, reverse engineering, and medical imaging. Although shape segmentation has been an active research area in the past decade, problems remain, such as excessive parameters that are manually set in the existing 3D shape segmentation. A segmentation approach for 3D shape based on topological persistence and heat kernel affinity matrix is presented to solve this problem. This approach requires setting the number of segments without the need to alter other parameters. Method First, Laplace-Beltrami operators of the 3D model are calculated to obtain the first 30 eigenvalues and the corresponding eigenvectors, which are used to compute heat kernel feature and signature. Heat kernel feature and heat kernel signature inherit the invariance under isometric deformations of the Laplace-Beltrami operator. Thus, it could beused to analyze shapes that undergo isometric deformations. Heat kernel feature is the amount of heat that transfers between two vertexes on the model in a given diffusion time; one of the vertexes is the given unit heat source. As heat tends to diffuse slowly at the vertex with positive curvature and faster with negative curvature, the heat kernel signature of a vertex is directly related to the Gaussian curvature of the surface at the vertex for a short diffusion time. Then, a hierarchy of components is obtained after the heat kernel signature of the 3D model is processed through topological persistence. The lifespan of the components is calculated, and the vertex that corresponds to the maximum of the heat kernel signature in the component is the feature point that inherits the hierarchical relationship and lifespan of the component, where it is located. Then, K longest lifespan feature points are selected as critical points of the segmented parts of the model, and K is also the number of segmented parts. The value of heat kernel signature on the torso of the model is generally low; thus, its critical point could not be obtained by topological persistence. The vertex with the minimum of the heat kernel signature is the critical point of the torso of the model. Thus, the initial clustering centers of the 3D models are obtained. The heat kernel affinity matrix is established by the heat kernel feature, and k-means clustering is performed by using the heat kernel affinity matrix that corresponds to different diffusion time periods and the initial clustering centers. Then, the heat kernel signature of the segmentation parts is calculated, and the vertex in the parts whose heat kernel signature value is close to the average value of all vertexes in this part are selected as the second cluster center to perform k-means clustering. Thus, the boundary is optimized in the second clustering. Finally, the clustering results are screened in accordance with the offset distance of the clustering centers and edge value, and the segmentation results of the 3D model are obtained. These screened rules are summarized by various experiments as follows: (1) When the offset distance of the clustering centers is less, the results of model segmentation improve. (2) Within the diffusion time, the values of all vertexes on the edge monotonously decrease first, and then monotonously increase, thereby resulting in a minimum edge value. Thus, the segmentation results are visually accurate with a relatively appropriate boundary after the minimum edge value is achieved. Result Human models are selected to verify the proposed algorithm and compare it with other algorithms. The experimental results show that the computing time of the heat kernel affinity matrix is less than the geodesic distance and exponential kernel, which are typically used for k-means clustering. The computing speed of the heat kernel affinity is 16.25 times that of the exponential kernel and 44.42 times that of the geodesic distance. Compared with the clustering methods based on topological persistence and geodesic distance, the proposed method could obtain accurate segmentation parts and appropriate segmentation boundaries. The clustering method based on topological persistence could not segment the torso of the human model, and the clustering method based on geodesic distance could not obtain an appropriate segmentation boundary. For non-rigid 3D shapes with various postures, the proposed approach could obtain consistent critical points and segmentation results. When the approach is applied to the common quadruped models, it could also achieve acceptable segmentation results. In addition, it is robust to model surface noise. The vertexes of the model are corrupted with different levels of Gaussian noise. When 10% Gaussian noise is added, our approach still obtains appropriate segmentation boundary, and when the Gaussian noise is raised to 20%, the relatively appropriate segmentation parts are still obtained. Conclusion Compared with the existing algorithms, the approach based on topological persistence and heat kernel affinity matrix could automatically select the clustering center under the premise of providing the number of segments. Moreover, the proposed approach exhibits strong robustness to the model surface noise. The computing time of the heat kernel affinity matrix is evidently less than the geodesic distance and exponential kernel. It could also be used extensively for the segmentation of other animal models.