Objective

2

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

2

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

2

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

2

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.