# Semantic Segmentation of Human Model Using Heat Kernel and Geodesic Distance

Authors: Huanyu Yang; Kuangrong Hao; Yongsheng Ding
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

A novel approach of 3D human model segmentation is proposed, which is based on heat kernel signature and geodesic distance. Through calculating the heat kernel signature of the point clouds of human body model, the local maxima of thermal energy distribution of the model is found, and the set of feature points of the model is obtained. Heat kernel signature has affine invariability which can be used to extract the correct feature points of the human model in different postures. We adopt the method of geodesic distance to realize the hierarchical segmentation of human model after obtaining the semantic feature points of human model. The experimental results show that the method can overcome the defect of geodesic distance feature extraction. The human body models with different postures can be obtained with the model segmentation results of human semantic characteristics.


---

## Body

## 1. Introduction

The 3D human model is widely used in anthropometry, clothing design, virtual human animation, game, and so on. The corresponding 3D human point cloud model is obtained by the 3D scanner, and then the data is represented as a grid or a surface by method for 3D reconstruction. Model segmentation is the basis of shape analysis. Segmentation of human model is different from other 3D models because of the particularity of the human body; the segmentation of the human model should accord with the human body semantic knowledge. In order to obtain the semantic knowledge of the human body, such as the definition of semantic knowledge related to hand, arm, head, legs, and trunk, it is necessary to obtain the model’s feature points automatically, such as head vertex, neck point, and perineum point.Geodesic distance is a widely used method during detecting human feature points. However, facing the model topology changes, such as the case of hands in hands, geodesic distance method is unable to detect the feature points of the hand. The method to determine the characteristics of human joints according to the proportion of the human body anthropometric value may lead to deviation because the human body model does not meet the standard ratio. Heat kernel signature is a method based on attribute representation model of Laplace-Beltrami operator and heat kernel function. It limits the variables in the time domain which can fully express geometric characteristics of the model. Also it has affine invariance and deformation invariance.In this paper, we propose a segmentation method based on heat kernel signature and geodesic distance. Our key idea is to discover semantic feature points by computing the heat kernel signature of human model. We search the partial maxima of the thermal energy distribution of the model and obtained a set of feature points of the model by calculating the heat kernel signature of the point cloud of human body model. We adopt the method of geodesic distance to realize the hierarchical segmentation of human model after obtaining the semantic feature points of human model. The experimental results show that the algorithm can be used to solve the feature points that geodesic distance method cannot defect. And the human body model with different postures can get the segmentation result which accords with the human semantic feature.The paper is organized as follows. In Section2, we review previous works on shape segmentation and 3D human segmentation, as well as the application of heat kernel descriptors and geodesic distances. The details of heat kernel function and heat kernel signature are given in Section 3. Model landmarks definition is described in Section 4. Our algorithm is presented in Section 5. Then the experiment and the result are presented in Section 6. Eventually, in Section 7, the conclusion and the possible future work are given.


## 2. Related Work

### 2.1. Shape Segmentation

A large amount of work has been done on shape segmentation in the context of shape analysis. According to the similarity of image segmentation, the 3D model segmentation algorithm is based on the ideas and terminology of image segmentation algorithm in a great extent. At present, the main method of point cloud segmentation is as follows.(
1) Method Based on Edge Detection. Edge based detection is a feature-based approach. The geometric features such as the characteristic curve or normal vector and curvature are used as the boundary conditions of the segmentation by calculating to obtain the feature points. The effect of segmentation is largely determined by the results of boundary detection. It is easy to be affected by the noise point, which leads to poor positioning accuracy. Woo et al. [1] used octree to organize grid structure. Also the normal deviation is used as the basis of grid subdivision and feature extraction. Guillaume et al. [2] proposed a method that is similar to curvature region to construct adjacency graph and ensured the effective segmentation of the patches at the “edge.” To achieve the segmentation of the model by calculating the thermonuclear energy point and heat dissipation point of each point of model, Rodrigues et al. [3] proposed a triangular mesh segmentation method based on contour. The main idea is to find the contours of each region first and then determine and collect all of their intrinsic triangles.(
2) Method Based on Region Growing. The segmentation algorithm based on region growing includes two approaches: bottom-to-up and top-to-down. The bottom-to-up algorithm is commonly referred to as the region growing algorithm. Select the seed point first and spread out from seed until there is no continuous set of points in the neighborhood, judging whether the surrounding neighborhood points belong to a surface. Finally, combine the neighborhood composition regions. The key of the algorithm is regional growth strategy. The top-to-down algorithm is also called hierarchical decomposition algorithm. Supposing that all the points belong to the same patch, the decomposition results of different levels of detail are obtained by using the hierarchical subdivision of octree [4] and hierarchical directional bounding box tree (OBBTree) [5].(
3) Method Based on Clustering. The segmentation algorithm based on clustering regards the segmentation of point cloud model as the classification process of data points with certain characteristic parameters. The coordinates of the point cloud data, normal vector, curvature value, heat kernel function value, and so on may be characteristic parameters of clustering analysis. K-means clustering method is used to realize the segmentation of point cloud model in [6]. Katz and Tal [7] use fuzzy clustering method to achieve the segmentation of point cloud model. Zhang et al. [8] adopt the method of hierarchical clustering to achieve the segmentation of point cloud model. Hilaga et al. [9] achieve the segmentation of the model through clustering the curvature of the grid. Skraba et al. [10] calculated the model heat kernel function value using the method of persistent clustering to cluster analysis, which obtained mesh segmentation algorithm of multiscale isometric invariant. Chen et al. [11] obtained the heat kernel signature value of 3D human body model vertex by calculating, then segmenting the model initially by setting segmentation threshold. Gadi [12] realized the grid segmentation of the point cloud model by using minimum rules and spectral clustering.(
4) Method Based on Topological Structure. It can be boiled down to Reeb graph [13, 14], level set method [15], shock graph [16], Laplace-Beltrami operator [17], and so on. based on the shape segmentation method of geometry and topology information. Although they can accurately calculate the global shape features, they cannot effectively solve the problem of preserving local details. Yao et al. [15] proposed a partitioning method for 3D printing model in the framework of multiphase level set. Firstly, six indexes are constructed to evaluate the partition quality: stress load, surface detail, interface aspect, packing size, printing ability, and assembly ability. Then according to the analysis index, we use the level set method to improve the quality of the partition on this basis.(
5) Method Based on Online Learning. In recent years, online learning methods have also been applied in model segmentation. Zhang et al. [18] put forward online learning method to realize shape classification. Several online random forests are used as the training items for weak learning through online multiclass linear programming enhancement algorithm. The training model is regarded as a data item and graph cut optimization algorithm is used to realize the segmentation of 3D model. Shu et al. [19] achieved unsupervised 3D shape segmentation and collaborative segmentation through the depth of learning methods.In addition to the above several methods, we have the classic model segmentation method as well as personal rank algorithm [21], hierarchical mesh segmentation based on fitting primitive [22], normalized segmentation [23], and so on. In recent years, the research on cosegmentation [24–26] has gradually become the hotspot of model segmentation. But in this paper, we do not relate to the content of this research.


### 2.2. 3D Human Segmentation

The characteristics of human body are similar to those of other kinds of 3D models. Some of the characteristics of the human body are related to changes in the partial geometric quantities (such as normal vector and curvature). However, unlike other types of models, some human characteristics are used in the measurement of garment CAD. Allen et al. [27] adopt the feature points of template matching and positioning; it does not have generality because its accuracy depends on the similarity between the input model and the template. Wuhrer et al. [28] extend the literature [27] method, using a large number of labeled 3D human models to construct a statistical model and detect the feature points of human body of the model. Kalogerakis et al. [29] used conditional random fields for sample learning to labeling and shape segmentation. In the research of human inspect feature points, many existing researches adopt template matching method where its accuracy depends largely on the similarity between the input model and the template. However, the algorithm proposed by researchers in shape feature analysis is suitable for any model without considering human specific domain knowledge. So the segmentation results may be inconsistent with the human structure hierarchy. Reeb graph is a typical shape feature description algorithm that has been used for 3D human body segmentation and feature points extraction [13, 30]. Werghi et al. [13] proposed a 3D human body segmentation algorithm based on Reeb graph, constructing the Reeb graph by selecting the geodesic distance function as the Morse function. The method has robustness to changes in body shape and attitude. But the drawback is the large amount of calculation and the low algorithm efficiency. According to the characteristics of the key points such as axillary points, locating the segmentation position is based on feature method [7, 31–33]. It can achieve the fast segmentation of point cloud model. EU virtual human project [34] uses multiscale fuzzy morphological analysis to locate and segment human body feature points. However, the concave convex geometric features make it difficult to ensure that the segmentation results are consistent with the semantic features of the human body.


### 2.3. Application of Heat Kernel Signature and Geodesic Distances

HKS (heat kernel signature) is a method of using spectral theory to characterize the properties attribute of the model. The descriptor is derived from the heat transfer theory. It can fully express the geometric characteristics of the model and has affine invariance and deformation invariance. Heat kernel signature is widely used in 3D point cloud segmentation, retrieval, model reconstruction, and so on. In Section3, the details of heat kernel function and heat kernel signature are given.In the research field of 3D point cloud model retrieval, it is used for multiscale matching of nonrigid shapes because the heat kernel signature has deformation invariance [35, 36]. Ovsjanikov et al. [37] used HKS to achieve a single point correspondence between the models. Gȩbal et al. [38] used the Laplace-Beltrami operator to construct an ADF (Auto Diffusion Function) similar to HKS to realize the shape analysis of 3D point cloud model. Lovato et al. [20] used ADF to achieve the feature points analysis of the 3D human point cloud model upon the method of [38]. In the research field of 3D point cloud model segmentation, Benjamin et al. [39] calculate the continuous heat kernel value of 3D model. Greedy algorithm is used to analyze the area of heat kernel energy storage, which is the large difference in heat kernel value of the point and its neighbor point. The method of relative entropy analysis is used to obtain the area of thermonuclear diffusion region, which is the area of thermonuclear value with uniform distribution to obtain the final fragmentation of 3D model. Skraba et al. [10] used the method of persistent clustering to analyze the model. Heat kernel function value was calculated to obtain the multiscale invariant mesh segmentation algorithm.In the process of selecting feature points, the widely used method is geodesic distance. The fuzzy hierarchical segmentation algorithm proposed by Katz and Tal [7] adopts geodesic distance to detect feature points. The proposed branch segmentation algorithm in [31], multidimensional scaling, and geodesic distance have been used to detect feature points. The method of using geodesic distance to obtain the feature points of human body is relatively simple, but there are problems too, for example, the precision analysis of geodesic distance and topology change of human body model. If the two hands are together, the geodesic distance method cannot get the characteristic points of the hand.


## 2.1. Shape Segmentation

A large amount of work has been done on shape segmentation in the context of shape analysis. According to the similarity of image segmentation, the 3D model segmentation algorithm is based on the ideas and terminology of image segmentation algorithm in a great extent. At present, the main method of point cloud segmentation is as follows.(
1) Method Based on Edge Detection. Edge based detection is a feature-based approach. The geometric features such as the characteristic curve or normal vector and curvature are used as the boundary conditions of the segmentation by calculating to obtain the feature points. The effect of segmentation is largely determined by the results of boundary detection. It is easy to be affected by the noise point, which leads to poor positioning accuracy. Woo et al. [1] used octree to organize grid structure. Also the normal deviation is used as the basis of grid subdivision and feature extraction. Guillaume et al. [2] proposed a method that is similar to curvature region to construct adjacency graph and ensured the effective segmentation of the patches at the “edge.” To achieve the segmentation of the model by calculating the thermonuclear energy point and heat dissipation point of each point of model, Rodrigues et al. [3] proposed a triangular mesh segmentation method based on contour. The main idea is to find the contours of each region first and then determine and collect all of their intrinsic triangles.(
2) Method Based on Region Growing. The segmentation algorithm based on region growing includes two approaches: bottom-to-up and top-to-down. The bottom-to-up algorithm is commonly referred to as the region growing algorithm. Select the seed point first and spread out from seed until there is no continuous set of points in the neighborhood, judging whether the surrounding neighborhood points belong to a surface. Finally, combine the neighborhood composition regions. The key of the algorithm is regional growth strategy. The top-to-down algorithm is also called hierarchical decomposition algorithm. Supposing that all the points belong to the same patch, the decomposition results of different levels of detail are obtained by using the hierarchical subdivision of octree [4] and hierarchical directional bounding box tree (OBBTree) [5].(
3) Method Based on Clustering. The segmentation algorithm based on clustering regards the segmentation of point cloud model as the classification process of data points with certain characteristic parameters. The coordinates of the point cloud data, normal vector, curvature value, heat kernel function value, and so on may be characteristic parameters of clustering analysis. K-means clustering method is used to realize the segmentation of point cloud model in [6]. Katz and Tal [7] use fuzzy clustering method to achieve the segmentation of point cloud model. Zhang et al. [8] adopt the method of hierarchical clustering to achieve the segmentation of point cloud model. Hilaga et al. [9] achieve the segmentation of the model through clustering the curvature of the grid. Skraba et al. [10] calculated the model heat kernel function value using the method of persistent clustering to cluster analysis, which obtained mesh segmentation algorithm of multiscale isometric invariant. Chen et al. [11] obtained the heat kernel signature value of 3D human body model vertex by calculating, then segmenting the model initially by setting segmentation threshold. Gadi [12] realized the grid segmentation of the point cloud model by using minimum rules and spectral clustering.(
4) Method Based on Topological Structure. It can be boiled down to Reeb graph [13, 14], level set method [15], shock graph [16], Laplace-Beltrami operator [17], and so on. based on the shape segmentation method of geometry and topology information. Although they can accurately calculate the global shape features, they cannot effectively solve the problem of preserving local details. Yao et al. [15] proposed a partitioning method for 3D printing model in the framework of multiphase level set. Firstly, six indexes are constructed to evaluate the partition quality: stress load, surface detail, interface aspect, packing size, printing ability, and assembly ability. Then according to the analysis index, we use the level set method to improve the quality of the partition on this basis.(
5) Method Based on Online Learning. In recent years, online learning methods have also been applied in model segmentation. Zhang et al. [18] put forward online learning method to realize shape classification. Several online random forests are used as the training items for weak learning through online multiclass linear programming enhancement algorithm. The training model is regarded as a data item and graph cut optimization algorithm is used to realize the segmentation of 3D model. Shu et al. [19] achieved unsupervised 3D shape segmentation and collaborative segmentation through the depth of learning methods.In addition to the above several methods, we have the classic model segmentation method as well as personal rank algorithm [21], hierarchical mesh segmentation based on fitting primitive [22], normalized segmentation [23], and so on. In recent years, the research on cosegmentation [24–26] has gradually become the hotspot of model segmentation. But in this paper, we do not relate to the content of this research.


## 2.2. 3D Human Segmentation

The characteristics of human body are similar to those of other kinds of 3D models. Some of the characteristics of the human body are related to changes in the partial geometric quantities (such as normal vector and curvature). However, unlike other types of models, some human characteristics are used in the measurement of garment CAD. Allen et al. [27] adopt the feature points of template matching and positioning; it does not have generality because its accuracy depends on the similarity between the input model and the template. Wuhrer et al. [28] extend the literature [27] method, using a large number of labeled 3D human models to construct a statistical model and detect the feature points of human body of the model. Kalogerakis et al. [29] used conditional random fields for sample learning to labeling and shape segmentation. In the research of human inspect feature points, many existing researches adopt template matching method where its accuracy depends largely on the similarity between the input model and the template. However, the algorithm proposed by researchers in shape feature analysis is suitable for any model without considering human specific domain knowledge. So the segmentation results may be inconsistent with the human structure hierarchy. Reeb graph is a typical shape feature description algorithm that has been used for 3D human body segmentation and feature points extraction [13, 30]. Werghi et al. [13] proposed a 3D human body segmentation algorithm based on Reeb graph, constructing the Reeb graph by selecting the geodesic distance function as the Morse function. The method has robustness to changes in body shape and attitude. But the drawback is the large amount of calculation and the low algorithm efficiency. According to the characteristics of the key points such as axillary points, locating the segmentation position is based on feature method [7, 31–33]. It can achieve the fast segmentation of point cloud model. EU virtual human project [34] uses multiscale fuzzy morphological analysis to locate and segment human body feature points. However, the concave convex geometric features make it difficult to ensure that the segmentation results are consistent with the semantic features of the human body.


## 2.3. Application of Heat Kernel Signature and Geodesic Distances

HKS (heat kernel signature) is a method of using spectral theory to characterize the properties attribute of the model. The descriptor is derived from the heat transfer theory. It can fully express the geometric characteristics of the model and has affine invariance and deformation invariance. Heat kernel signature is widely used in 3D point cloud segmentation, retrieval, model reconstruction, and so on. In Section3, the details of heat kernel function and heat kernel signature are given.In the research field of 3D point cloud model retrieval, it is used for multiscale matching of nonrigid shapes because the heat kernel signature has deformation invariance [35, 36]. Ovsjanikov et al. [37] used HKS to achieve a single point correspondence between the models. Gȩbal et al. [38] used the Laplace-Beltrami operator to construct an ADF (Auto Diffusion Function) similar to HKS to realize the shape analysis of 3D point cloud model. Lovato et al. [20] used ADF to achieve the feature points analysis of the 3D human point cloud model upon the method of [38]. In the research field of 3D point cloud model segmentation, Benjamin et al. [39] calculate the continuous heat kernel value of 3D model. Greedy algorithm is used to analyze the area of heat kernel energy storage, which is the large difference in heat kernel value of the point and its neighbor point. The method of relative entropy analysis is used to obtain the area of thermonuclear diffusion region, which is the area of thermonuclear value with uniform distribution to obtain the final fragmentation of 3D model. Skraba et al. [10] used the method of persistent clustering to analyze the model. Heat kernel function value was calculated to obtain the multiscale invariant mesh segmentation algorithm.In the process of selecting feature points, the widely used method is geodesic distance. The fuzzy hierarchical segmentation algorithm proposed by Katz and Tal [7] adopts geodesic distance to detect feature points. The proposed branch segmentation algorithm in [31], multidimensional scaling, and geodesic distance have been used to detect feature points. The method of using geodesic distance to obtain the feature points of human body is relatively simple, but there are problems too, for example, the precision analysis of geodesic distance and topology change of human body model. If the two hands are together, the geodesic distance method cannot get the characteristic points of the hand.


## 3. Heat Kernel Function and Heat Kernel Signature

### 3.1. Definition of Heat Kernel Signature

Heat kernel operator and heat kernel function are from the thermal diffusion theory of Riemann manifold. The heat equation is used to describe the variation of heat distribution with time. For compact Riemann manifoldsM, the M thermal diffusion process can be described by the heat equation [35].(1)αΔM+∂∂tux,t=0,where ΔM is the Laplacian operator over a Riemannian manifold M, u(x,t) is the heat distribution at a point x and at time t, and α is thermal diffusivity (typically α=1). Given M has boundary, it should meet the Dirichlet boundary condition, for all point at time t:x∈∂M, u(x,t)=0.Given an initial heat distribution functionf:M→R, where Ht(f) is the heat distribution at time t, when t approaches to zero, limt→0⁡Ht(f)=f, Ht(·) is called heat kernel operator. ΔM and Ht(·) satisfy Ht=e-tΔM. These two operators have the same feature vector; their eigenvalues are λ and e-λt, respectively. Therefore, for any manifold M, there is a function kt(x,y):R+×M×M→R such that the following equation holds.(2)Htfx=∫Mktx,yfydy,which satisfies the smallest function kt(x,y) called heat kernel function. Heat kernel equation is the fundamental solution to the heat equation on a specified domain with appropriate boundary conditions; its physical significance is the amount of heat transferred from x to y at time t. Because the conduction of heat is associated with surface shape of the model, heat kernel function built over the surface of model is relevant to the model’s geometric properties. It is also one of the main tools in the study of the properties of the Laplace operator over Riemannian manifold M. As a heat kernel function over a compact Riemannian manifold M, the eigen decomposition of it is expressed as(3)ktx,y=∑i=0∞e-λitϕixϕiy,where λi is the eigenvalue. And ϕi is the feature vector of Laplace-Beltrami operator, respectively.Paper [35] puts forward a method to simplify heat kernel function, that is, to build HKS according to heat kernel function and to confine the vector of heat kernel function in a specified time domain and sample it over the vertex x on the model to build a heat kernel function vector. This vector is called HKS (heat kernel signature).For vertexx over Riemannian manifold M, its HKS can be described as(4)SHKSx,t=ktx,x=∑i=0∞e-λitϕix2.Heat kernel takes up most of heat kernel function’s merit property. But in order to reduce the complexity of heat kernel and reduce redundant information, it converts two vectors in heat kernel function into one, making its HKS more concise and easy to calculate and compare.


### 3.2. Properties of Heat Kernel

Heat kernel has many good geometric properties, such as invariant isometric transformation, affine invariant, multiple scale, and stability. The following are some of the main properties of heat kernel.


#### 3.2.1. Invariant Isometric Transformation

Heat kernel is invariant under isometric transformations. Givenf:M→N as the isometric transformation from Riemannian manifold M to N, where all x,y∈M and all t>0,(5)ktMx,y=ktNTx,Ty.With isometric transformation between manifold M and manifold N, the property of heat kernel remains invariant; therefore, heat kernel is only determined by the inner geometric property of manifold.


#### 3.2.2. Affine Invariant

From (5) you can see that metric spaces (M,kt) and (N,kt) are isometric isomorphism. According to Matsu-Magnolia theorem, isometric isomorphism on normed vector spaces whose coefficients are real numbers must be affine transformations. Therefore, heat kernel has in addition to offset thermonuclear metric invariance, with affine invariance.Due to the above two characteristics of heat kernel, it has nothing to do with attitude of the model. Therefore, heat kernel is widely used in model retrieval [20], model block with independent attitude [10, 39], skeleton extraction of the model with independent attitude [37], and other fields.


#### 3.2.3. Multiple Scale Property

The vertexx of model on heat kernel kt is a function that associated with diffusion time t. When the value of time t is very small, the value of heat kernel kt(x,y) mainly depends on the geometrical characteristics of the x small adjacent area. With the growth of time, the scope of the adjacent region will grow. That means, when the value of t is small, heat kernel kt(x,y) reflects the characteristics of the partial geometric model. When the value of t is large, it reflects global geometric properties.The ADF [38] method was used to extract the feature points of human model in literature [20]. The ADF method is developed by the heat kernel (HKS). It is also associated with the diffusion function of time t similar to heat kernel. The influence of the value of t on the extraction of human feature points is analyzed in literature [20]. When the value t is larger, because the ADF value reflects the global characteristics of the model, the detection of the human body is less, but the accuracy is high. When the value t is small, because the ADF value reflects the partial characteristics of the model, the detection of the human body is more, but the accuracy is lower.In the analysis of algorithm experimental results of Section5.1, in order to consider the partial characteristics of the human model and the influence of the global characteristics on the feature points, we carried out a number of values to t and the corresponding analysis.


#### 3.2.4. Stability

Stability means heat kernel function is stable over the noise of model, insensible to weak disruption. Heat kernelkt(x,y) equates to the average length of the whole path from x to y with time t. When there is noise over the model, only those passing the noise would be affected; therefore, heat kernel is relatively stable.Both [10, 39] analyzed the stability of heat kernel function, adopted heat kernel function to divide the model, and introduced noise to the model. Basically, it would not affect the result of destructing the model.


### 3.3. Calculation of Heat Kernel Signature

Heat kernel functionkt(x,y) has the same eigenvector and eigenvalue as ΔM, the operator of Laplace-Beltrami. Therefore, the solution of heat kernel signature becomes the solution of the discretization and feature system of the Laplace-Beltrami operator. HKS algorithm is detailed as follows.Step 1 (the discretization of the Laplace-Beltrami operator).
Let manifoldM be the triangle net discretization, shown as M=(V,E,F). V is the vertex on the model; E is the edge of the model. The discrete Laplace-Beltrami operators are usually shown as follows:(6)ΔM=∑j∈NiwijVi-Vj,wij=ωij∑i,k∈Eωik,where N(i) is the set of the neighboring vertexes of vertex Vi and ωij is the edge weight of vi and vj. As heat diffuses along the net according to the change of time, a suitable edge weight can control the pace of heat diffusion well and also can counteract the effects that irregular sampling caused to the discretization. Equation (4) can be expressed in the form of a matrix as follows.(7)L~=B-1L.
Ifωij=1 is the uniform operator of Laplacian, the settings for cotangent weighting method [40] applied in this article are the following:(8)L=ωij=cot⁡αij+cot⁡βij2j∈Ni-∑k∈Niωi,ki=j0others,B=θr+θs2j∈Ni∑k∈Niθk6i=j0others,where θr and θs are the two triangles which share the edges (i,j) and θr is the area of the triangle θr. αij and βij are the diagonals of the two triangles which share the edges (i,j).Step 2 (calculation of eigenvalueλ and eigenvector ϕ).
Characteristic system of(L,B) satisfies the following equation: (9)LΦ=ΛBΦ,where Λ is the diagonal matrix of n×n; the diagonal elements are eigenvalue λ1,…,λn; Φ is the matrix of N×n; the eigenvectors of Φ are ϕ1,…,ϕn.Step 3 (calculation of the heat kernel signature value).
Equation (4) can be expressed in the form of a matrix as follows:(10)Ht=XDtXT,where X=ϕ1,…,ϕn, Dt=diag(e-λ1t,…,e-λnt). The heat kernel signature of each matrix of the model can be calculated through (10).


## 3.1. Definition of Heat Kernel Signature

Heat kernel operator and heat kernel function are from the thermal diffusion theory of Riemann manifold. The heat equation is used to describe the variation of heat distribution with time. For compact Riemann manifoldsM, the M thermal diffusion process can be described by the heat equation [35].(1)αΔM+∂∂tux,t=0,where ΔM is the Laplacian operator over a Riemannian manifold M, u(x,t) is the heat distribution at a point x and at time t, and α is thermal diffusivity (typically α=1). Given M has boundary, it should meet the Dirichlet boundary condition, for all point at time t:x∈∂M, u(x,t)=0.Given an initial heat distribution functionf:M→R, where Ht(f) is the heat distribution at time t, when t approaches to zero, limt→0⁡Ht(f)=f, Ht(·) is called heat kernel operator. ΔM and Ht(·) satisfy Ht=e-tΔM. These two operators have the same feature vector; their eigenvalues are λ and e-λt, respectively. Therefore, for any manifold M, there is a function kt(x,y):R+×M×M→R such that the following equation holds.(2)Htfx=∫Mktx,yfydy,which satisfies the smallest function kt(x,y) called heat kernel function. Heat kernel equation is the fundamental solution to the heat equation on a specified domain with appropriate boundary conditions; its physical significance is the amount of heat transferred from x to y at time t. Because the conduction of heat is associated with surface shape of the model, heat kernel function built over the surface of model is relevant to the model’s geometric properties. It is also one of the main tools in the study of the properties of the Laplace operator over Riemannian manifold M. As a heat kernel function over a compact Riemannian manifold M, the eigen decomposition of it is expressed as(3)ktx,y=∑i=0∞e-λitϕixϕiy,where λi is the eigenvalue. And ϕi is the feature vector of Laplace-Beltrami operator, respectively.Paper [35] puts forward a method to simplify heat kernel function, that is, to build HKS according to heat kernel function and to confine the vector of heat kernel function in a specified time domain and sample it over the vertex x on the model to build a heat kernel function vector. This vector is called HKS (heat kernel signature).For vertexx over Riemannian manifold M, its HKS can be described as(4)SHKSx,t=ktx,x=∑i=0∞e-λitϕix2.Heat kernel takes up most of heat kernel function’s merit property. But in order to reduce the complexity of heat kernel and reduce redundant information, it converts two vectors in heat kernel function into one, making its HKS more concise and easy to calculate and compare.


## 3.2. Properties of Heat Kernel

Heat kernel has many good geometric properties, such as invariant isometric transformation, affine invariant, multiple scale, and stability. The following are some of the main properties of heat kernel.


### 3.2.1. Invariant Isometric Transformation

Heat kernel is invariant under isometric transformations. Givenf:M→N as the isometric transformation from Riemannian manifold M to N, where all x,y∈M and all t>0,(5)ktMx,y=ktNTx,Ty.With isometric transformation between manifold M and manifold N, the property of heat kernel remains invariant; therefore, heat kernel is only determined by the inner geometric property of manifold.


### 3.2.2. Affine Invariant

From (5) you can see that metric spaces (M,kt) and (N,kt) are isometric isomorphism. According to Matsu-Magnolia theorem, isometric isomorphism on normed vector spaces whose coefficients are real numbers must be affine transformations. Therefore, heat kernel has in addition to offset thermonuclear metric invariance, with affine invariance.Due to the above two characteristics of heat kernel, it has nothing to do with attitude of the model. Therefore, heat kernel is widely used in model retrieval [20], model block with independent attitude [10, 39], skeleton extraction of the model with independent attitude [37], and other fields.


### 3.2.3. Multiple Scale Property

The vertexx of model on heat kernel kt is a function that associated with diffusion time t. When the value of time t is very small, the value of heat kernel kt(x,y) mainly depends on the geometrical characteristics of the x small adjacent area. With the growth of time, the scope of the adjacent region will grow. That means, when the value of t is small, heat kernel kt(x,y) reflects the characteristics of the partial geometric model. When the value of t is large, it reflects global geometric properties.The ADF [38] method was used to extract the feature points of human model in literature [20]. The ADF method is developed by the heat kernel (HKS). It is also associated with the diffusion function of time t similar to heat kernel. The influence of the value of t on the extraction of human feature points is analyzed in literature [20]. When the value t is larger, because the ADF value reflects the global characteristics of the model, the detection of the human body is less, but the accuracy is high. When the value t is small, because the ADF value reflects the partial characteristics of the model, the detection of the human body is more, but the accuracy is lower.In the analysis of algorithm experimental results of Section5.1, in order to consider the partial characteristics of the human model and the influence of the global characteristics on the feature points, we carried out a number of values to t and the corresponding analysis.


### 3.2.4. Stability

Stability means heat kernel function is stable over the noise of model, insensible to weak disruption. Heat kernelkt(x,y) equates to the average length of the whole path from x to y with time t. When there is noise over the model, only those passing the noise would be affected; therefore, heat kernel is relatively stable.Both [10, 39] analyzed the stability of heat kernel function, adopted heat kernel function to divide the model, and introduced noise to the model. Basically, it would not affect the result of destructing the model.


## 3.2.1. Invariant Isometric Transformation

Heat kernel is invariant under isometric transformations. Givenf:M→N as the isometric transformation from Riemannian manifold M to N, where all x,y∈M and all t>0,(5)ktMx,y=ktNTx,Ty.With isometric transformation between manifold M and manifold N, the property of heat kernel remains invariant; therefore, heat kernel is only determined by the inner geometric property of manifold.


## 3.2.2. Affine Invariant

From (5) you can see that metric spaces (M,kt) and (N,kt) are isometric isomorphism. According to Matsu-Magnolia theorem, isometric isomorphism on normed vector spaces whose coefficients are real numbers must be affine transformations. Therefore, heat kernel has in addition to offset thermonuclear metric invariance, with affine invariance.Due to the above two characteristics of heat kernel, it has nothing to do with attitude of the model. Therefore, heat kernel is widely used in model retrieval [20], model block with independent attitude [10, 39], skeleton extraction of the model with independent attitude [37], and other fields.


## 3.2.3. Multiple Scale Property

The vertexx of model on heat kernel kt is a function that associated with diffusion time t. When the value of time t is very small, the value of heat kernel kt(x,y) mainly depends on the geometrical characteristics of the x small adjacent area. With the growth of time, the scope of the adjacent region will grow. That means, when the value of t is small, heat kernel kt(x,y) reflects the characteristics of the partial geometric model. When the value of t is large, it reflects global geometric properties.The ADF [38] method was used to extract the feature points of human model in literature [20]. The ADF method is developed by the heat kernel (HKS). It is also associated with the diffusion function of time t similar to heat kernel. The influence of the value of t on the extraction of human feature points is analyzed in literature [20]. When the value t is larger, because the ADF value reflects the global characteristics of the model, the detection of the human body is less, but the accuracy is high. When the value t is small, because the ADF value reflects the partial characteristics of the model, the detection of the human body is more, but the accuracy is lower.In the analysis of algorithm experimental results of Section5.1, in order to consider the partial characteristics of the human model and the influence of the global characteristics on the feature points, we carried out a number of values to t and the corresponding analysis.


## 3.2.4. Stability

Stability means heat kernel function is stable over the noise of model, insensible to weak disruption. Heat kernelkt(x,y) equates to the average length of the whole path from x to y with time t. When there is noise over the model, only those passing the noise would be affected; therefore, heat kernel is relatively stable.Both [10, 39] analyzed the stability of heat kernel function, adopted heat kernel function to divide the model, and introduced noise to the model. Basically, it would not affect the result of destructing the model.


## 3.3. Calculation of Heat Kernel Signature

Heat kernel functionkt(x,y) has the same eigenvector and eigenvalue as ΔM, the operator of Laplace-Beltrami. Therefore, the solution of heat kernel signature becomes the solution of the discretization and feature system of the Laplace-Beltrami operator. HKS algorithm is detailed as follows.Step 1 (the discretization of the Laplace-Beltrami operator).
Let manifoldM be the triangle net discretization, shown as M=(V,E,F). V is the vertex on the model; E is the edge of the model. The discrete Laplace-Beltrami operators are usually shown as follows:(6)ΔM=∑j∈NiwijVi-Vj,wij=ωij∑i,k∈Eωik,where N(i) is the set of the neighboring vertexes of vertex Vi and ωij is the edge weight of vi and vj. As heat diffuses along the net according to the change of time, a suitable edge weight can control the pace of heat diffusion well and also can counteract the effects that irregular sampling caused to the discretization. Equation (4) can be expressed in the form of a matrix as follows.(7)L~=B-1L.
Ifωij=1 is the uniform operator of Laplacian, the settings for cotangent weighting method [40] applied in this article are the following:(8)L=ωij=cot⁡αij+cot⁡βij2j∈Ni-∑k∈Niωi,ki=j0others,B=θr+θs2j∈Ni∑k∈Niθk6i=j0others,where θr and θs are the two triangles which share the edges (i,j) and θr is the area of the triangle θr. αij and βij are the diagonals of the two triangles which share the edges (i,j).Step 2 (calculation of eigenvalueλ and eigenvector ϕ).
Characteristic system of(L,B) satisfies the following equation: (9)LΦ=ΛBΦ,where Λ is the diagonal matrix of n×n; the diagonal elements are eigenvalue λ1,…,λn; Φ is the matrix of N×n; the eigenvectors of Φ are ϕ1,…,ϕn.Step 3 (calculation of the heat kernel signature value).
Equation (4) can be expressed in the form of a matrix as follows:(10)Ht=XDtXT,where X=ϕ1,…,ϕn, Dt=diag(e-λ1t,…,e-λnt). The heat kernel signature of each matrix of the model can be calculated through (10).


## 4. Model Landmarks Definition

### 4.1. Definition of Human Body Model Semantic Feature Point

According to different data processing needs, human body model has different semantic feature point definitions. Inside the human body model, human body level structures are basically decided by the semantic feature points of body parts such as perineum point and waist line point. Human body model semantic feature point definitions are shown in Table1. The corresponding position on the human body model of each feature point is displayed in Figure 1.Table 1
Definition of human semantic feature points.
Feature points number
Located part
Feature points’ semantic and meaning
f
p
1
Limbs
Left hand
f
p
2
Left elbow
f
p
3
Left underarm
f
p
4
Right hand
f
p
5
Right elbow
f
p
6
Right underarm
f
p
7
Left foot
f
p
8
Left knee
f
p
9
Right foot
f
p
10
Right knee
f
p
11
Body
Perineum point
f
p
12
Waist line point
f
p
13
NeckFigure 1
Definition of semantic feature point.


### 4.2. Segmentation Structure of the Human Body

According to the definition of human body model semantic feature point from Table1 and Figure 1, the division of human body model level structure is based on the following definition:(11)PS=PSlarm_l,PSlarm_u,PSrarm_l,PSrarm_u,PSlleg_l,PSlleg_u,PSrleg_l,PSrleg_u,PStorso_l,PStorso_u,PShead,where PS is the set of segmentation part. The correlation of the meaning and feature point of each minor part is shown in Table 2.Table 2
Segmentation structure of the human body.
Level division order
Curved surface names
Meanings
Corresponding feature points
(1)
P
S
l
a
r
m
_
l
Left lower arm
f
p
1, fp2
(2)
P
S
l
a
r
m
_
u
Left upper arm
f
p
2, fp3
(3)
P
S
r
a
r
m
_
l
Right lower arm
f
p
4, fp5
(4)
P
S
r
a
r
m
_
u
Right upper arm
f
p
5, fp6
(5)
P
S
l
l
e
g
_
l
Left lower leg
f
p
7, fp8
(6)
P
S
l
l
e
g
_
u
Left thigh
f
p
8, fp11
(7)
P
S
r
l
e
g
_
l
Right lower leg
f
p
9, fp10
(8)
P
S
r
l
e
g
_
u
Right upper leg
f
p
10, fp11
(9)
P
S
t
o
r
s
o
_
l
Buttock
f
p
11, fp12
(10)
P
S
t
o
r
s
o
_
u
Upper body
f
p
12, fp13
(11)
P
S
h
e
a
d
Head
f
p
13


## 4.1. Definition of Human Body Model Semantic Feature Point

According to different data processing needs, human body model has different semantic feature point definitions. Inside the human body model, human body level structures are basically decided by the semantic feature points of body parts such as perineum point and waist line point. Human body model semantic feature point definitions are shown in Table1. The corresponding position on the human body model of each feature point is displayed in Figure 1.Table 1
Definition of human semantic feature points.
Feature points number
Located part
Feature points’ semantic and meaning
f
p
1
Limbs
Left hand
f
p
2
Left elbow
f
p
3
Left underarm
f
p
4
Right hand
f
p
5
Right elbow
f
p
6
Right underarm
f
p
7
Left foot
f
p
8
Left knee
f
p
9
Right foot
f
p
10
Right knee
f
p
11
Body
Perineum point
f
p
12
Waist line point
f
p
13
NeckFigure 1
Definition of semantic feature point.


## 4.2. Segmentation Structure of the Human Body

According to the definition of human body model semantic feature point from Table1 and Figure 1, the division of human body model level structure is based on the following definition:(11)PS=PSlarm_l,PSlarm_u,PSrarm_l,PSrarm_u,PSlleg_l,PSlleg_u,PSrleg_l,PSrleg_u,PStorso_l,PStorso_u,PShead,where PS is the set of segmentation part. The correlation of the meaning and feature point of each minor part is shown in Table 2.Table 2
Segmentation structure of the human body.
Level division order
Curved surface names
Meanings
Corresponding feature points
(1)
P
S
l
a
r
m
_
l
Left lower arm
f
p
1, fp2
(2)
P
S
l
a
r
m
_
u
Left upper arm
f
p
2, fp3
(3)
P
S
r
a
r
m
_
l
Right lower arm
f
p
4, fp5
(4)
P
S
r
a
r
m
_
u
Right upper arm
f
p
5, fp6
(5)
P
S
l
l
e
g
_
l
Left lower leg
f
p
7, fp8
(6)
P
S
l
l
e
g
_
u
Left thigh
f
p
8, fp11
(7)
P
S
r
l
e
g
_
l
Right lower leg
f
p
9, fp10
(8)
P
S
r
l
e
g
_
u
Right upper leg
f
p
10, fp11
(9)
P
S
t
o
r
s
o
_
l
Buttock
f
p
11, fp12
(10)
P
S
t
o
r
s
o
_
u
Upper body
f
p
12, fp13
(11)
P
S
h
e
a
d
Head
f
p
13


## 5. Algorithm

### 5.1. Feature Point Detection

Feature point detection is a very important process in the fields of partition, simplification, rebuild, and retrieval for 3D model. We will give definition to an expanded HKS descriptor.(12)DHKStix=HKStx-HKStxi,where xi∈Nii=1,2,…,k,N(i) is k neighbor of x.Let(13)ptx=∑i∈1,2,…,kDHKStixHKStx.The bigger the value pt(x) is, the more likely it is the local maximum point, and we think its carried features are more obvious.As the analysis of the features of heat kernel in Section3.2, heat kernel signature is a corresponding function of the expanding time t. We chose 4 random points in the model; Figure 2 reflects the trend of heat kernel signature changes at the 4 points under different t. We found that when t value is bigger than a certain value, heat kernel signature and expanding time t will show linear variation. We found that when t is greater than a certain value, heat kernel description value and diffusion time t will show a linear change. There is no correlation between the features of the model. Therefore, we will limit a certain range of values to t. The literature [35] pointed out that the heat kernel function has logarithm characteristics and changes with time. The literature [20, 35] limited the value of t in a certain range tmin,tmax. Among them, λi is the i eigenvalue of the Laplacian matrix. In the literature, the value t is also limited to the range tmin,tmax.Figure 2
The result of HKS in the case of different diffusion timet.When the timet value is small, the heat kernel function kt(x,y) value is mainly decided by the geometric feature of point x′ very small local part of point x. The range of the nearby area increases along with the increase of time. This means that, when t is relatively small, the heat kernel function kt(x,y) reflects the model’s partial geometric feature. When t is relatively big, it reflects the model’s global geometric feature. Figure 3 shows the human body model feature points collected under different conditions of expanding time t. Figure 3(a) is the model feature point collected when t=0.1, Figure 3(b) is the model feature point collected when t=1. It can be seen that there are the different feature points which have been collected when t value is different from Figure 3. Therefore, when collecting the feature points, we need to consider not only the model’s global geometric feature, but also its partial geometric feature. Consequently, we collected the model’s many thermonuclear descriptors under many different expanding time t conditions and then calculated the corresponding feature points set according to the above feature extracting arithmetic. Concentrated feature points will display the redundancy of the feature points. Apply the similarities merge method [41] and feature division method [20] to remove the redundant points from the concentrated feature points, in order to get accurate feature points set to reflect the feature of the model. However, consider the high complexity of the human body curved surface; sometimes even if the feature points carry obvious curved feature, it will not affect the result of human body division. Therefore, this paper will only pick the semantic feature points from the feature points set that correspond with the definitions in Table 1 and Figure 1.Figure 3
The result of feature point extraction in the case of different diffusion timest. (a) t=0.1, k=5. (b) t=1, k=5.
(a)
(b)According to the above analysis, the detailed arithmetic that uses the heat kernel signature to detect the human body model feature points is the following.Step 1.
Chooset∈tmin,tmax, according to the calculation procedure in Section 3.3, and calculate the heat kernel signature HKSt(x) of each point x in the calculation model.Step 2.
According to (12) and (13), calculate every calculation model’s point x′ expanding HKS value DHKSti(x), to get pt(x).Step 3.
Descend orderpt(x) to get pt′(x).Step 4.
Set threshold valuel; let the first l points inside pt′(x) become the set qtl(x);Step 5.
Choose manyt, repeat the steps from 1 to 4, to get many points set qtl(x), and combine all the many qtl(x), to finally get the initial feature points set Q(x).Step 6.
Remove the redundant points from the feature points set, and pick out the human body semantic feature points which correspond with the definitions in Table1 and Figure 1, to get the final feature points set Q′(x).


### 5.2. The Method for Segmentation

After we get the human body model semantic feature points, we use the geodesic distance method to divide the levels in human body model. The definition of geodesic distance is the length of the shortest path between two points that are on the surface of a body [42]. The three-dimension geodesic distance has very good deformation stability; it also has a good descriptive nature to both rigid bodies and nonrigid bodies. Therefore, the three-dimension geodesic distance can be used in many aspects such as the three-dimensional body’s deformation process and matching three-dimensional bodies. For a three-dimensional net graph, one can establish an undirected graph by the method of setting every point of the body as a node and the corresponding edge as the weight; get the result by using the arithmetic of the shortest path. In this article, we use the method in [43] to calculate the geodesic distance.Segmentation of the human body model by the order of the minor parts of the curved surface is defined in Table2. For example, to divide the PSlarm_l in the left lower arm, collect the left hand feature point fp1 and left elbow feature point fp2 by using the method in Section 5.1.(14)geodfi,fp1<geodfp1,fp2,fi∈PS,where geod(fi,fp1) is the geodesic distance between the left hand feature point and the triangular patch. geod(fp1,fp2) is the geodesic distance between two feature points.The following is the detailed arithmetic which used the geodesic distance to divide the levels:Step 1.
Initialize the triangular setsmain=TS, and resolve the result set to get PS={Pmain}.Step 2.
Collect feature pointsfp1 and fp2 from set Pmain.Step 3.
According to (14), separate the triangular patch set from set smain to get the left lower arm part PSlarm_l.Step 4.
According to the order of human body level division that is defined in Table2, as the same in Step 2, collect feature points fpj and fpk from the set Pmain; the division order and correspondence are shown in Table 2.Step 5.
According to the order of human body level division that is defined in Table2, the same as in Step 3, separate the triangular patch set from set smain to get the curved surface patch PSi (according to (14)). Let set PSmain=PSmain-PSi, until PSi=PStorso_u, PShead=PSmain-PStorso_u. Otherwise, repeat Step 4.


## 5.1. Feature Point Detection

Feature point detection is a very important process in the fields of partition, simplification, rebuild, and retrieval for 3D model. We will give definition to an expanded HKS descriptor.(12)DHKStix=HKStx-HKStxi,where xi∈Nii=1,2,…,k,N(i) is k neighbor of x.Let(13)ptx=∑i∈1,2,…,kDHKStixHKStx.The bigger the value pt(x) is, the more likely it is the local maximum point, and we think its carried features are more obvious.As the analysis of the features of heat kernel in Section3.2, heat kernel signature is a corresponding function of the expanding time t. We chose 4 random points in the model; Figure 2 reflects the trend of heat kernel signature changes at the 4 points under different t. We found that when t value is bigger than a certain value, heat kernel signature and expanding time t will show linear variation. We found that when t is greater than a certain value, heat kernel description value and diffusion time t will show a linear change. There is no correlation between the features of the model. Therefore, we will limit a certain range of values to t. The literature [35] pointed out that the heat kernel function has logarithm characteristics and changes with time. The literature [20, 35] limited the value of t in a certain range tmin,tmax. Among them, λi is the i eigenvalue of the Laplacian matrix. In the literature, the value t is also limited to the range tmin,tmax.Figure 2
The result of HKS in the case of different diffusion timet.When the timet value is small, the heat kernel function kt(x,y) value is mainly decided by the geometric feature of point x′ very small local part of point x. The range of the nearby area increases along with the increase of time. This means that, when t is relatively small, the heat kernel function kt(x,y) reflects the model’s partial geometric feature. When t is relatively big, it reflects the model’s global geometric feature. Figure 3 shows the human body model feature points collected under different conditions of expanding time t. Figure 3(a) is the model feature point collected when t=0.1, Figure 3(b) is the model feature point collected when t=1. It can be seen that there are the different feature points which have been collected when t value is different from Figure 3. Therefore, when collecting the feature points, we need to consider not only the model’s global geometric feature, but also its partial geometric feature. Consequently, we collected the model’s many thermonuclear descriptors under many different expanding time t conditions and then calculated the corresponding feature points set according to the above feature extracting arithmetic. Concentrated feature points will display the redundancy of the feature points. Apply the similarities merge method [41] and feature division method [20] to remove the redundant points from the concentrated feature points, in order to get accurate feature points set to reflect the feature of the model. However, consider the high complexity of the human body curved surface; sometimes even if the feature points carry obvious curved feature, it will not affect the result of human body division. Therefore, this paper will only pick the semantic feature points from the feature points set that correspond with the definitions in Table 1 and Figure 1.Figure 3
The result of feature point extraction in the case of different diffusion timest. (a) t=0.1, k=5. (b) t=1, k=5.
(a)
(b)According to the above analysis, the detailed arithmetic that uses the heat kernel signature to detect the human body model feature points is the following.Step 1.
Chooset∈tmin,tmax, according to the calculation procedure in Section 3.3, and calculate the heat kernel signature HKSt(x) of each point x in the calculation model.Step 2.
According to (12) and (13), calculate every calculation model’s point x′ expanding HKS value DHKSti(x), to get pt(x).Step 3.
Descend orderpt(x) to get pt′(x).Step 4.
Set threshold valuel; let the first l points inside pt′(x) become the set qtl(x);Step 5.
Choose manyt, repeat the steps from 1 to 4, to get many points set qtl(x), and combine all the many qtl(x), to finally get the initial feature points set Q(x).Step 6.
Remove the redundant points from the feature points set, and pick out the human body semantic feature points which correspond with the definitions in Table1 and Figure 1, to get the final feature points set Q′(x).


## 5.2. The Method for Segmentation

After we get the human body model semantic feature points, we use the geodesic distance method to divide the levels in human body model. The definition of geodesic distance is the length of the shortest path between two points that are on the surface of a body [42]. The three-dimension geodesic distance has very good deformation stability; it also has a good descriptive nature to both rigid bodies and nonrigid bodies. Therefore, the three-dimension geodesic distance can be used in many aspects such as the three-dimensional body’s deformation process and matching three-dimensional bodies. For a three-dimensional net graph, one can establish an undirected graph by the method of setting every point of the body as a node and the corresponding edge as the weight; get the result by using the arithmetic of the shortest path. In this article, we use the method in [43] to calculate the geodesic distance.Segmentation of the human body model by the order of the minor parts of the curved surface is defined in Table2. For example, to divide the PSlarm_l in the left lower arm, collect the left hand feature point fp1 and left elbow feature point fp2 by using the method in Section 5.1.(14)geodfi,fp1<geodfp1,fp2,fi∈PS,where geod(fi,fp1) is the geodesic distance between the left hand feature point and the triangular patch. geod(fp1,fp2) is the geodesic distance between two feature points.The following is the detailed arithmetic which used the geodesic distance to divide the levels:Step 1.
Initialize the triangular setsmain=TS, and resolve the result set to get PS={Pmain}.Step 2.
Collect feature pointsfp1 and fp2 from set Pmain.Step 3.
According to (14), separate the triangular patch set from set smain to get the left lower arm part PSlarm_l.Step 4.
According to the order of human body level division that is defined in Table2, as the same in Step 2, collect feature points fpj and fpk from the set Pmain; the division order and correspondence are shown in Table 2.Step 5.
According to the order of human body level division that is defined in Table2, the same as in Step 3, separate the triangular patch set from set smain to get the curved surface patch PSi (according to (14)). Let set PSmain=PSmain-PSi, until PSi=PStorso_u, PShead=PSmain-PStorso_u. Otherwise, repeat Step 4.


## 6. Results

The arithmetic in this article is on a computer featured with 1.60 GHz CPU and 4.0 GB memory space; the tool that is used is the MATLAB software.


### 6.1. Parameter Selection

The input of the arithmetic in this article is the triangular net model; the experiment data is mainly the human body model from the data base TOSCA. In order to apply KNN arithmetic to get theDHKSti(x) value, it is necessary to determine the neighborhood of x and k. After analyzing the experiment, we found that the value of k has little effect on the final result of the arithmetic. Figure 4 has shown the result of feature point extraction in the case of different neighbor number when expanding time t=1. Figure 4(a) shows the result of the value k=5, Figure 4(b) shows the result of the value k=10, and Figure 4(c) shows the result of the value k=20. As in Figure 4, we can tell that the key feature points that are from the extracted initial feature points set are basically the same. To reduce the complexity to calculation, we set k=5 in all of the following experiments.Figure 4
The result of feature point extraction in the case of different neighbor numberk. (a) t=1, k=5, (b) t=1, k=10, and (c) t=1, k=20.
(a)
(b)
(c)Let the number of feature points extracted bel. When l is relatively big, there are relatively more concentrated points of the feature points. There will also be redundancy of the feature points; the bigger the points set, the more the redundancy. When l is relatively small, there is smaller concentrated redundancy at the feature points, which is smaller noise at the feature points, but there might be omissions at some feature points. Figure 5 has shown the result of feature point extraction in the case of different number l. Figure 5(a) shows the result of the value l=20, Figure 5(b) shows the result of the value l=50, and Figure 5(c) shows the result of the value l=100. When l=100, there is a lot of redundancy. Therefore, we chose l=50 as the threshold of the feature points set in the experiment.Figure 5
The result of feature point extraction in the case of different numberl. (a) l=20, (b) l=50, and (c) l=100.
(a)
(b)
(c)


### 6.2. Comparison of the Feature Points Collecting Method

The shape of the model using the ADF descriptor which is produced from expanding in the HKS method is described in [38]. ADF is the value that is generated from HKS. Literature [20] used the following equation which is based on [38] to collect the feature points of the three-dimensional model.(15)HKStx>HKStxixi∈Ni,where xi are all the neighboring vertexes around x, which is the neighboring point of x.Lett=0.1; in Figure 6, (a) is the feature point collected by using the method from literature [20] and (b) is the feature point collected by using the method in this chapter. We found that when using the first method, there is more redundancy of the feature point. However, the feature point that is collected through the method in this article is almost not affected by its neighborhood, and through controlling the value of the threshold l, there is relatively small redundancy produced.Figure 6
Comparison result of feature point extraction. (a) The result of methods in [20]; (b) the result of our method.
(a)
(b)


### 6.3. The Extraction and Hierarchical Segmentation Results of Semantic Feature Points of Human Model

Using the method of literature [44], we can realize the segmentation of human model based on the semantic feature points of human body. In the literature, the geodesic distance is used to detect the feature points. There are two problems with the method. First, in the situation of hand in hand of model, the geodesic distance method cannot detect the feature points of the hand. Figure 7 shows the comparison of geodesic distances between different feature points of the human body model. The red line represents the geodesic distance between two points. When the hands are apart, the feature points of two hands are the two points farthest from the geodesic distance. But when the hands are held, the distance between the points of the two hands is very close. Second is to use the geodesic distance to detect the joint feature points of the human model. In the literature [44], set the ratio of 3 : 7 distance from the neck point to the head and the distance to the perineum point. However, the human model is complex and changeable; also not everybody can meet the standard human body proportion. Therefore, the method may show larger deviation in the detection of joint feature points.Figure 7
Change of geodetic distance of model.Figure8 shows the results of feature point extraction from four different human body models. The blue points as feature point are extracted by using heat kernel signature. We do not need so many human features in human segmentation due to the complex body curved surface. Therefore, we defined thirteen human semantic feature points according to the characteristics of the human body in Section 4.1. The selection of semantic feature points is related to the semantic definition of the model and the semantic feature is defined by users. So the method of user interaction is adopted to select the semantic feature points from the feature points. In Figure 8, we use the red circle to indicate the extracted feature points, extracting results through the human model feature in Figure 8(c). We can see that, even in the hands-holding of the model, the hand can also detect a large number of feature points. By using the method of this chapter, the feature points of the human body with different postures are extracted according to the curved surface feature.Figure 8
Results of feature points extraction from human model in different attitudes.
(a)
(b)
(c)
(d)Clustering method is one of the common methods for 3D model segmentation.K-means clustering method [6] is used to achieve the four postures of the human body model segmentation results as shown in Figure 9. Here we choose K-means clustering into 10 categories. It can be seen from the results that the model segmentation does not conform to the semantic definition of the human model. Moreover, when the posture of human body model changes, the result of model segmentation is wrong.Figure 9
Different gesture of the human body model segmentation results usingK-means clustering.
(a)
(b)
(c)
(d)According to the semantic features of the four kinds of gestures in Figure8, the method of hierarchical segmentation based on feature points is used to realize the segmentation results of human body with four kinds of postures, as shown in Figure 10. We can see from the figure that the segmentation results are consistent with the characteristics of the human model. Even if the posture of human body model changes, the model segmentation results are still consistent with the semantic features of the human model.Figure 10
Segmentation results of the human body model under different postures using heat kernel and geodesic distance.
(a)
(b)
(c)
(d)


## 6.1. Parameter Selection

The input of the arithmetic in this article is the triangular net model; the experiment data is mainly the human body model from the data base TOSCA. In order to apply KNN arithmetic to get theDHKSti(x) value, it is necessary to determine the neighborhood of x and k. After analyzing the experiment, we found that the value of k has little effect on the final result of the arithmetic. Figure 4 has shown the result of feature point extraction in the case of different neighbor number when expanding time t=1. Figure 4(a) shows the result of the value k=5, Figure 4(b) shows the result of the value k=10, and Figure 4(c) shows the result of the value k=20. As in Figure 4, we can tell that the key feature points that are from the extracted initial feature points set are basically the same. To reduce the complexity to calculation, we set k=5 in all of the following experiments.Figure 4
The result of feature point extraction in the case of different neighbor numberk. (a) t=1, k=5, (b) t=1, k=10, and (c) t=1, k=20.
(a)
(b)
(c)Let the number of feature points extracted bel. When l is relatively big, there are relatively more concentrated points of the feature points. There will also be redundancy of the feature points; the bigger the points set, the more the redundancy. When l is relatively small, there is smaller concentrated redundancy at the feature points, which is smaller noise at the feature points, but there might be omissions at some feature points. Figure 5 has shown the result of feature point extraction in the case of different number l. Figure 5(a) shows the result of the value l=20, Figure 5(b) shows the result of the value l=50, and Figure 5(c) shows the result of the value l=100. When l=100, there is a lot of redundancy. Therefore, we chose l=50 as the threshold of the feature points set in the experiment.Figure 5
The result of feature point extraction in the case of different numberl. (a) l=20, (b) l=50, and (c) l=100.
(a)
(b)
(c)


## 6.2. Comparison of the Feature Points Collecting Method

The shape of the model using the ADF descriptor which is produced from expanding in the HKS method is described in [38]. ADF is the value that is generated from HKS. Literature [20] used the following equation which is based on [38] to collect the feature points of the three-dimensional model.(15)HKStx>HKStxixi∈Ni,where xi are all the neighboring vertexes around x, which is the neighboring point of x.Lett=0.1; in Figure 6, (a) is the feature point collected by using the method from literature [20] and (b) is the feature point collected by using the method in this chapter. We found that when using the first method, there is more redundancy of the feature point. However, the feature point that is collected through the method in this article is almost not affected by its neighborhood, and through controlling the value of the threshold l, there is relatively small redundancy produced.Figure 6
Comparison result of feature point extraction. (a) The result of methods in [20]; (b) the result of our method.
(a)
(b)


## 6.3. The Extraction and Hierarchical Segmentation Results of Semantic Feature Points of Human Model

Using the method of literature [44], we can realize the segmentation of human model based on the semantic feature points of human body. In the literature, the geodesic distance is used to detect the feature points. There are two problems with the method. First, in the situation of hand in hand of model, the geodesic distance method cannot detect the feature points of the hand. Figure 7 shows the comparison of geodesic distances between different feature points of the human body model. The red line represents the geodesic distance between two points. When the hands are apart, the feature points of two hands are the two points farthest from the geodesic distance. But when the hands are held, the distance between the points of the two hands is very close. Second is to use the geodesic distance to detect the joint feature points of the human model. In the literature [44], set the ratio of 3 : 7 distance from the neck point to the head and the distance to the perineum point. However, the human model is complex and changeable; also not everybody can meet the standard human body proportion. Therefore, the method may show larger deviation in the detection of joint feature points.Figure 7
Change of geodetic distance of model.Figure8 shows the results of feature point extraction from four different human body models. The blue points as feature point are extracted by using heat kernel signature. We do not need so many human features in human segmentation due to the complex body curved surface. Therefore, we defined thirteen human semantic feature points according to the characteristics of the human body in Section 4.1. The selection of semantic feature points is related to the semantic definition of the model and the semantic feature is defined by users. So the method of user interaction is adopted to select the semantic feature points from the feature points. In Figure 8, we use the red circle to indicate the extracted feature points, extracting results through the human model feature in Figure 8(c). We can see that, even in the hands-holding of the model, the hand can also detect a large number of feature points. By using the method of this chapter, the feature points of the human body with different postures are extracted according to the curved surface feature.Figure 8
Results of feature points extraction from human model in different attitudes.
(a)
(b)
(c)
(d)Clustering method is one of the common methods for 3D model segmentation.K-means clustering method [6] is used to achieve the four postures of the human body model segmentation results as shown in Figure 9. Here we choose K-means clustering into 10 categories. It can be seen from the results that the model segmentation does not conform to the semantic definition of the human model. Moreover, when the posture of human body model changes, the result of model segmentation is wrong.Figure 9
Different gesture of the human body model segmentation results usingK-means clustering.
(a)
(b)
(c)
(d)According to the semantic features of the four kinds of gestures in Figure8, the method of hierarchical segmentation based on feature points is used to realize the segmentation results of human body with four kinds of postures, as shown in Figure 10. We can see from the figure that the segmentation results are consistent with the characteristics of the human model. Even if the posture of human body model changes, the model segmentation results are still consistent with the semantic features of the human model.Figure 10
Segmentation results of the human body model under different postures using heat kernel and geodesic distance.
(a)
(b)
(c)
(d)


## 7. Conclusion and Future Work

In this paper, we introduce a method of human model segmentation based on feature points. The local maxima of thermal energy distribution of the model are found by calculating the heat kernel signature of the point clouds of human body model. A set of feature points of human model under different postures is obtained. Select the feature points which accord with the semantic features of human body and realize the hierarchical segmentation of human model by calculating geodesic distance between feature points. We can detect different postures of the human model feature points through the experimental analysis. The segmentation results of human model based on feature points are consistent with the definition of the semantic features of the model. However, there are some problems in the algorithm proposed in the literature. For example, in the process of feature extraction, the amount of feature points extracted from the human model is large, but most of the feature points are meaningless. We only selected thirteen of them for human segmentation. Therefore, how to improve the accuracy of feature points extraction and reduce the redundancy of feature points is the research content in the future.



---

*Source: 7974340-2018-02-20.xml*