结合拓扑持续性和热扩散理论的3维模型分割
|
摘要
目的针对已有的3维模型分割方法人为设定过多参数的问题,提出了一种基于拓扑持续性和热亲和度矩阵的3维模型分割方法,只需给定分割部件数即可自动完成分割。方法首先通过拓扑持续性处理3维模型的热核签名,选取生存期最长的几个特征点作为模型被分割部件的显著特征点,对于模型躯干等无法通过生长周期选取特征点的部件,则选取热核签名的最小值所对应的顶点作为显著特征点,从而获得模型的初始聚类中心;然后使用不同的扩散时间所对应的热亲和度矩阵进行k-means聚类,并根据聚类中心的偏移距离等参数筛选聚类结果,从而获得3维模型的分割结果。结果选取人体模型进行分割实验,并与其他方法进行对比分析。结果表明,所提出的热亲和度的计算时间明显优于常用的测地距离和幂指数核;相比基于拓扑持续性和基于测地距离的聚类,本文方法可以正确分割模型的各个部件并获得恰当的分割边界。此外,本文方法针对姿态不同的同一非刚体3维模型可以取得一致性的分割结果,而且对模型表面噪声具有较好的鲁棒性。结论和已有方法相比,本文的基于拓扑持续性和热亲和度矩阵的3维模型分割方法可以在给定分割部件的前提下自动选定聚类中心并获得恰当的分割边界,并广泛适用于常见动物模型的分割。
Objective Shape segmentation is a fundamental problem in shape analysis. Automatic shape segmentation contributes to various shape processing and 3 D 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 3 D shape segmentation. A segmentation approach for 3 D 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-Beltramioperators of the 3 D 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 3 D 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 3 D 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 3 D 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 3 D 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.
Objective Shape segmentation is a fundamental problem in shape analysis. Automatic shape segmentation contributes to various shape processing and 3 D 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 3 D shape segmentation. A segmentation approach for 3 D 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-Beltramioperators of the 3 D 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 3 D 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 3 D 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 3 D 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 3 D 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.
引文
[1]Sun X P,Li H.A survey of 3D mesh model segmentation and application[J].Journal of Computer-Aided Design&Computer Graphics,2005,17(8):1647-1655.[孙晓鹏,李华.3维网格模型的分割及应用技术综述[J].计算机辅助设计与图形学学报,2005,17(8):1647-1655.][DOI:10.3321/j.issn:1003-9775.2005.08.001]
[2]Shapira L,Shamir A,Cohen-Or D.Consistent mesh partitioning and skeletonisation using the shape diameter function[J].The Visual Computer,2008,24(4):249-259.[DOI:10.1007/s00371-007-0197-5]
[3]Ma Y Q,Li Z K,Wang X Z,et al.Mesh segmentation algorithm based on volumetric radius function[J].Computer Engineering,2011,37(22):240-242.[马亚奇,李忠科,王先泽,等.基于体半径函数的网格分割算法[J].计算机工程,2011,37(22):240-242.][DOI:10.3969/j.issn.1000-3428.2011.22.080]
[4]Mangan A P,Whitaker R T.Partitioning 3D surface meshes using watershed segmentation[J].IEEE Transactions on Visualization and Computer Graphics,1999,5(4):308-321.[DOI:10.1109/2945.817348]
[5]Pan X,Zhang S Y,Zhang Y,et al.3D model retrieval based topology connection graph[J].Chinese Journal of Computers,2004,27(9):1250-1255.[潘翔,张三元,张引,等.一种基于拓扑连接图的3维模型检索方法[J].计算机学报,2004,27(9):1250-1255.][DOI:10.3321/j.issn:0254-4164.2004.09.015]
[6]Liu R,Zhang H.Segmentation of 3D meshes through spectral clustering[C]//Proceedings of the 12th Pacific Conference on Computer Graphics and Applications.Seoul,South Korea:IEEE,2004:298-305.[DOI:10.1109/PCCGA.2004.1348360]
[7]Golovinskiy A,Funkhouser T.Consistent segmentation of 3D models[J].Computers&Graphics,2009,33(3):262-269.[DOI:10.1016/j.cag.2009.03.010]
[8]Benhabiles H,LavouéG,Vandeborre J P,et al.Learning boundary edges for 3D-mesh segmentation[J].Computer Graphics Forum,2011,30(8):2170-2182.[DOI:10.1111/j.1467-8659.2011.01967.x]
[9]Meng M,Xia J Z,Luo J,et al.Unsupervised co-segmentation for 3D shapes using iterative multi-label optimization[J].Computer-Aided Design,2013,45(2):312-320.[DOI:10.1016/j.cad.2012.10.014]
[10]Xie Z G,Xu K,Liu L G,et al.3D shape segmentation and labeling via extreme learning machine[J].Computer Graphics Forum,2014,33(5):85-95.[DOI:10.1111/cgf.12434]
[11]Shu Z Y,Qi C W,Xin S Q,et al.Unsupervised 3D shape segmentation and co-segmentation via deep learning[J].Computer Aided Geometric Design,2016,43:39-52.[DOI:10.1016/j.cagd.2016.02.015]
[12]Edelsbrunner H,Letscher D,Zomorodian A.Topological persistence and simplification[C]//Proceedings of the 41st Annual Symposium on Foundations of Computer Science.Redondo Beach,CA,USA:IEEE,2002:454-463.[DOI:10.1109/SFCS.2000.892133]
[13]Chazal F,Guibas L J,Oudot S Y,et al.Persistence-based clustering in riemannian manifolds[J].Journal of the ACM,2013,60(6):#41.[DOI:10.1145/2535927]
[14]Sun J,Ovsjanikov M,Guibas L.A concise and provably informative multi-scale signature based on heat diffusion[J].Computer Graphics Forum,2009,28(5):1383-1392.[DOI:10.1111/j.1467-8659.2009.01515.x]
[15]Liu Y J,Chen Z Q,Tang K.Construction of Iso-contours,bisectors,and Voronoi diagrams on triangulated surfaces[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(8):1502-1517.[DOI:10.1109/tpami.2010.221]
[16]Fang Y,Sun M T,Kim M,et al.Heat-mapping:a robust approach toward perceptually consistent mesh segmentation[C]//Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition.Colorado Springs,CO,USA:IEEE,2011:2145-2152.[DOI:10.1109/cvpr.2011.5995695]
[17]Su M,Wan L L,Miao Z J.A non-rigid 3D shape segmentation approach based on diffusion geometry[J].Journal of ComputerAided Design&Computer Graphics,2015,27(4):605-613.[苏梦,万丽莉,苗振江.一种基于扩散几何的非刚体3维形状分割方法[J].计算机辅助设计与图形学学报,2015,27(4):605-613.]
[18]Bronstein A M,Bronstein M M,Kimmel R.Numerical Geometry of Non-Rigid Shapes[M].New York:Springer,2009.[DOI:10.1007/978-0-387-73301-2]
[19]Chen X B,Golovinskiy A,Funkhouser T.A benchmark for 3D mesh segmentation[J].ACM Transactions on Graphics,2009,28(3):#73.[DOI:10.1145/1531326.1531379]
[20]Elad A,Kimmel R.On bending invariant signatures for surfaces[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2003,25(10):1285-1295.[DOI:10.1109/TPAMI.2003.1233902]
[21]Skraba P,Ovsjanikov M,Chazal F,et al.Persistence-based segmentation of deformable shapes[C]//Proceedings of the 2010IEEE Computer Society Conference on Computer Vision and Pattern Recognition.San Francisco,CA,USA:IEEE,2010:45-52.[DOI:10.1109/cvprw.2010.5543285]
[2]Shapira L,Shamir A,Cohen-Or D.Consistent mesh partitioning and skeletonisation using the shape diameter function[J].The Visual Computer,2008,24(4):249-259.[DOI:10.1007/s00371-007-0197-5]
[3]Ma Y Q,Li Z K,Wang X Z,et al.Mesh segmentation algorithm based on volumetric radius function[J].Computer Engineering,2011,37(22):240-242.[马亚奇,李忠科,王先泽,等.基于体半径函数的网格分割算法[J].计算机工程,2011,37(22):240-242.][DOI:10.3969/j.issn.1000-3428.2011.22.080]
[4]Mangan A P,Whitaker R T.Partitioning 3D surface meshes using watershed segmentation[J].IEEE Transactions on Visualization and Computer Graphics,1999,5(4):308-321.[DOI:10.1109/2945.817348]
[5]Pan X,Zhang S Y,Zhang Y,et al.3D model retrieval based topology connection graph[J].Chinese Journal of Computers,2004,27(9):1250-1255.[潘翔,张三元,张引,等.一种基于拓扑连接图的3维模型检索方法[J].计算机学报,2004,27(9):1250-1255.][DOI:10.3321/j.issn:0254-4164.2004.09.015]
[6]Liu R,Zhang H.Segmentation of 3D meshes through spectral clustering[C]//Proceedings of the 12th Pacific Conference on Computer Graphics and Applications.Seoul,South Korea:IEEE,2004:298-305.[DOI:10.1109/PCCGA.2004.1348360]
[7]Golovinskiy A,Funkhouser T.Consistent segmentation of 3D models[J].Computers&Graphics,2009,33(3):262-269.[DOI:10.1016/j.cag.2009.03.010]
[8]Benhabiles H,LavouéG,Vandeborre J P,et al.Learning boundary edges for 3D-mesh segmentation[J].Computer Graphics Forum,2011,30(8):2170-2182.[DOI:10.1111/j.1467-8659.2011.01967.x]
[9]Meng M,Xia J Z,Luo J,et al.Unsupervised co-segmentation for 3D shapes using iterative multi-label optimization[J].Computer-Aided Design,2013,45(2):312-320.[DOI:10.1016/j.cad.2012.10.014]
[10]Xie Z G,Xu K,Liu L G,et al.3D shape segmentation and labeling via extreme learning machine[J].Computer Graphics Forum,2014,33(5):85-95.[DOI:10.1111/cgf.12434]
[11]Shu Z Y,Qi C W,Xin S Q,et al.Unsupervised 3D shape segmentation and co-segmentation via deep learning[J].Computer Aided Geometric Design,2016,43:39-52.[DOI:10.1016/j.cagd.2016.02.015]
[12]Edelsbrunner H,Letscher D,Zomorodian A.Topological persistence and simplification[C]//Proceedings of the 41st Annual Symposium on Foundations of Computer Science.Redondo Beach,CA,USA:IEEE,2002:454-463.[DOI:10.1109/SFCS.2000.892133]
[13]Chazal F,Guibas L J,Oudot S Y,et al.Persistence-based clustering in riemannian manifolds[J].Journal of the ACM,2013,60(6):#41.[DOI:10.1145/2535927]
[14]Sun J,Ovsjanikov M,Guibas L.A concise and provably informative multi-scale signature based on heat diffusion[J].Computer Graphics Forum,2009,28(5):1383-1392.[DOI:10.1111/j.1467-8659.2009.01515.x]
[15]Liu Y J,Chen Z Q,Tang K.Construction of Iso-contours,bisectors,and Voronoi diagrams on triangulated surfaces[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(8):1502-1517.[DOI:10.1109/tpami.2010.221]
[16]Fang Y,Sun M T,Kim M,et al.Heat-mapping:a robust approach toward perceptually consistent mesh segmentation[C]//Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition.Colorado Springs,CO,USA:IEEE,2011:2145-2152.[DOI:10.1109/cvpr.2011.5995695]
[17]Su M,Wan L L,Miao Z J.A non-rigid 3D shape segmentation approach based on diffusion geometry[J].Journal of ComputerAided Design&Computer Graphics,2015,27(4):605-613.[苏梦,万丽莉,苗振江.一种基于扩散几何的非刚体3维形状分割方法[J].计算机辅助设计与图形学学报,2015,27(4):605-613.]
[18]Bronstein A M,Bronstein M M,Kimmel R.Numerical Geometry of Non-Rigid Shapes[M].New York:Springer,2009.[DOI:10.1007/978-0-387-73301-2]
[19]Chen X B,Golovinskiy A,Funkhouser T.A benchmark for 3D mesh segmentation[J].ACM Transactions on Graphics,2009,28(3):#73.[DOI:10.1145/1531326.1531379]
[20]Elad A,Kimmel R.On bending invariant signatures for surfaces[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2003,25(10):1285-1295.[DOI:10.1109/TPAMI.2003.1233902]
[21]Skraba P,Ovsjanikov M,Chazal F,et al.Persistence-based segmentation of deformable shapes[C]//Proceedings of the 2010IEEE Computer Society Conference on Computer Vision and Pattern Recognition.San Francisco,CA,USA:IEEE,2010:45-52.[DOI:10.1109/cvprw.2010.5543285]