Keywords

1 Introduction

In the field of Computer Graphics, 3D models are used to describe the shape of a 3D space object that they represent. Different tools are used to represent these shapes, for example, the surface of curve modeling, constructive solid geometry, voxels, etc. They are used to create primitive shapes that are grouped together to obtain the final model. The most popular way to represent the geometric model is the 3D polygon mesh.

A polygon mesh is defined as a collection of connected polygons (i.e. bounded planar surfaces of different sizes) which approximate the surface of any 3D object. Polygons can be triangles, quadrangles or any kind of polygons. A polygon mesh M consists of a triple of three different kinds of mesh elements {v, e, f}; where v is the set of vertices, e is the set of edges and f is the set of faces.

The information describing the mesh elements consists of the mesh connectivity, mesh geometry and mesh attributes. The mesh connectivity (also referred as topology) describes the incidence relationship between the mesh elements. The incidence relations specify -for each face- the vertices and edges on the bounding loop, for each edge the end vertices and the faces to which the edge is incident, and for each vertex the incident edges and faces. The mesh geometry defines the coordinate values of vertices in 3D space which make up the model. The mesh attributes (also referred as photometry) are such as color, normal and texture coordinates at the vertices that describe the visual appearance of the mesh at rendering time. The problem of mesh segmentation consists of decomposing the polygonal surface of mesh M into a set of different regions S as a connected set of faces or vertices of uniform properties, where S = {M 0 ,…,M k - 1 }.

Mesh segmentation is considered an important process in the field of computer graphics. It is a fundamental process in different applications such as shape reconstruction in reverse engineering, 3D models retrieval, and CAD/CAM applications, etc. Several recent works have studied the problem of 3D mesh segmentation [1–4].

The authors in [5, 6] have introduced the use of the unsupervised clustering techniques of K-means [7] as hard clustering and Fuzzy C-means (FCM) [8, 9] as a Soft/Fuzzy clustering for the segmentation of 2D images. Their work was based on modifying the classic semi-automatic GrabCut [10] segmentation technique for an automatic one. The proposed work of this paper extends the use of the two clustering techniques for the problem of 3D mesh segmentation. Evaluations on a proper benchmark dataset of 19 models are carried out. The proposed segmentation techniques achieved acceptable segmentation results compared to human segmentations.

In the following, Sect. 2 presents the related work to the different approaches of 3D mesh segmentation and introduces the most popular segmentation techniques. Section 3 presents the proposed work achieved for segmenting 3D meshes. Section 4 illustrates the algorithms of K-means and FCM clustering techniques used throughout the paper. Section 5 illustrates the achieved experimental results while presenting the benchmark of the 3D models and the metrics used for evaluating the segmentation techniques. Conclusions and future work are presented in Section 6.

2 Related Work

The 3D mesh segmentation techniques can be categorized as Region Growing techniques, Hierarchical Clustering techniques, Iterative Clustering techniques, Spectral Segmentation techniques, Skeleton Extraction Based Segmentation techniques, Interactive techniques, and Learning Segmentation techniques. Concerning the region growing techniques, they start by selecting a seed element and grow by adding successively compatible elements e.g. vertices which satisfy a given criterion. Then the growing process is repeated with a new seed element each time the previous growing is interrupted. The algorithm stops when all the seed elements are visited.

Zeckerberger et al. [11] have proposed a segmentation method which is based on a region growing algorithm. The algorithm starts by computing the dual graph of the input mesh. Each vertex of the graph represents a face of the mesh, and the edges which connect the vertices represent the adjacency relation between the faces. Then, the algorithm randomly selects a vertex to continue by collecting faces which form a convex patch (or convex region). The process of computing a new patch is launched each time the previous one is interrupted because of the violation of the convexity.

In Lavoué et al. [12] work, the curvature is first calculated for all vertices of the mesh and classified into several clusters. A region growing mechanism then extracts connected regions (associated with similar curvature), starting from several seed-facets.

In the hierarchical clustering, each segment is initially represented by a unique mesh element. Then each pair of adjacent segments is assigned a merging score based on a given criterion e.g. the boundary shape or the region curvature. After that, the merging process is implemented according to the increasing order of scores. Some parameters such as the region size are used to control the size of the clusters and decide if they should continue the merging operation or not.

Attene et al. [13] proposed a segmentation algorithm based on fitting primitives. The set of primitives includes plan, sphere, and cylinder. The algorithm generates a binary tree of segments where each segment is fitted to one of the employed primitives. To this end, all possible pairs of adjacent segments are considered (initially each pair of the segment is represented by two adjacent facets), and the pairs that are fitted well with one of the defined primitives, form a new segment.

In the iterative clustering approach, an iterative process begins by K clusters, each one with a representative centroid, where K is a predefined number representing the needed number of segments. Then, each mesh element is added to the closest cluster according to a certain distance function. This distance between the vertex and the each class centroid is measured based on a certain criterion. Once all vertices are added to the different clusters, the centroids are updated, and the iterative process is repeated until the centroids stop changing.

Lai et al. [14] proposed a clustering-based iterative segmentation algorithm dedicated for large models with high connectivity. They first generate a mesh hierarchy suitable for segmentation using a feature sensitive re-meshing algorithm. Then, they apply a clustering algorithm to segment the mesh. To increase the robustness of their method against geometric variations on the regions of the mesh, they introduced a metric which allows efficiently computing the distance between faces for clustering. The metric definition includes geodesic distance, integral invariants related to averaged normal curvature [15], and statistical measures of these invariants characterizing local properties such as geometric texture.

In the spectral segmentation approach, the combinatorial graph partitioning problem is converted into a geometric partitioning problem. In this problem, any mesh is represented as a graph with two A and D matrices, where A is the adjacency matrix and D is the degree matrix. Then, the Laplacian L of the graph is computed as L = D–A. The Laplacian eigenvectors are computed, and the graph is embedded in the R K space using the first K eigenvectors.

Liu et al. [16] have proposed a segmentation algorithm that makes use of spectral space partitioning. They defined a symmetric affinity matrix W \( \in \) R nxn such that for each i, j, 0 ≤ W ij  ≤ 1 encodes the probability that two faces i and j can be grouped in the same segment. The matrix allows avoiding grouping facets which are separated by concave regions. The W matrix can be seen as a graph adjacency matrix A. The spectral analysis of the W matrix (using its first k largest eigenvectors) creates a partitioning which makes a segmentation of the mesh. The authors in [17] have proposed another algorithm which improves the results of their previous one [16] by making use of contour analysis besides the spectral analysis.

In the Skeleton Extraction Based Segmentation approach, an approximate skeleton of the input mesh is computed, and then each critical joint of the skeleton will correspond to a segment. In the segmentation algorithm proposed by Tierny et al. [18], the skeleton is used to restrict the object core and to identify the junction surfaces. Thus, the resulting segmentation is a coarse one which is refined following a hierarchical schema based on the topology of the model. The authors developed their own algorithm that allows computing an enhanced topological skeleton. The algorithm seeks to follow both of topological and geometrical variations of mesh contours computed using a geodesic mapping function.

Another work by Au et al. [19] was developed that differs in the skeleton computation. Their work was base on mesh contraction where a Laplacian smoothing is applied on the mesh to iteratively contract its geometry. The contraction allows removing details from the input mesh and leads to a zero-volume mesh. The conversion is carried out by removing all the collapsed faces from the zero-volume mesh. In order to perform this removal, a sequence of edge-collapse operations is applied using a coast function.

The approach of interactive techniques requires user interaction, where the user draws on the 3D mesh a set of sketches which corresponds to future segments. Each set of vertices traversed by a sketch is assigned a unique label. Then, a queue is filled with the unlabeled vertices where distance is measured between each unlabeled vertex and its direct labeled neighbors. An iterative process is applied where the queue vertex with the minimum distance is assigned to the closest segment. The process stops when the queue is empty.

Generally, the main difference between the proposed methods relies on the definition of the criterion to decide how to merge the mesh elements. For Example, Wu et al. [20] use the angular distance, while Fan et al. [21] use the Gaussian mixture and shape diameter function.

In the Learning Segmentation approach, the problem is defined as an optimization problem where an objective function is learned using a set of geometric features from a collection of labeled training meshes of ground truth segmentations. These ground truth segmentation databases have given the opportunity to quantitatively analyze and learn the mesh segmentations. The work proposed by Kalogerakis et al. [22] allows to simultaneously segment and label the input mesh. The problem consists in optimizing a Conditional Random Field (CRF). The algorithm has demonstrated its efficiency through the improvement of the results over the state-of-the-art of mesh segmentation.

3 Clustering Techniques

This section describes the algorithms of K-means clustering technique as hard segmentation approach and FCM clustering technique as a soft segmentation approach that are used throughout the paper.

3.1 K-means

K-means is one of the most popular and well used hard clustering algorithms. The standard algorithm was first proposed by Stuart Lloyd in 1982 [7]. The algorithm works as follows:

  1. 1.

    Select the number of desired clusters k and assign the k cluster centers randomly to different initial mesh vertices.

  2. 2.

    For the remaining mesh vertices, assign each mesh vertex to the cluster whose center is the closest i.e. the cluster which it is most similar to, using a measure of distance or similarity.

  3. 3.

    Recompute the cluster centers by getting the average coordinates of the mesh vertices that make up the cluster.

  4. 4.

    Go to step 2 until no more changes occur, i.e. the cluster centers remain the same, or a maximum number of iterations is reached.

3.2 FCM

Fuzzy C-means (FCM) [11, 12] is considered one of the famous clustering approaches for segmentation. The algorithm works as follows:

  1. 1.

    Initialize the fuzzy centroids C k randomly for K = 1, …,nc where nc is the number of clusters.

  2. 2.

    Repeat for N iterations:

  3. 3.

    Compute the fuzzy membership U (k) = [uij], which is the membership of data point i to cluster j using

    $$ u_{ij} = \frac{{\left( {\frac{1}{{\left\| {x_{i} - c_{j} } \right\|}}} \right)^{{\frac{1}{m - 1}}} }}{{\sum\nolimits_{j = 1}^{nc} {\left( {\frac{1}{{\left\| {x_{i} - c_{j} } \right\|}}} \right)^{{\frac{1}{m - 1}}} } }} $$
    (1)
  4. 4.

    Update the fuzzy centroids using the computed fuzzy memberships, where m is the fuzzy parameter and n is the number of data points.

    $$ c_{j} = \frac{{\sum\nolimits_{i = 1}^{n} {\left( {u_{ij} } \right)^{m} x_{i} } }}{{\sum\nolimits_{i = 1}^{n} {\left( {u_{ij} } \right)^{m} } }} $$
    (2)
  5. 5.

    If ||U (k) – U (k−1)|| < ε, then STOP, else continue iterations.

  6. 6.

    Determine membership cutoff. For each data point x i , assign x i to cluster j where u ij is the maximum among U (k) for K = 1, …,nc, or u ij  > α

4 Proposed Work

A benchmark for 3D mesh segmentation is used for quantitative evaluation of the proposed clustering-based 3D mesh segmentation techniques. The benchmark includes 3D meshes from the Watertight Track of the 2007 SHREC Shape-based Retrieval Contest provided by Daniela Giorgi [23]. The dataset contains 380 models spread evenly among a broad set of 19 object categories including human bodies, furniture, mechanical CAD parts, animals, tools, etc. These models exhibit different shape variability within each category and are represented in a form that most segmentation algorithms are able to use as input.

All models of the benchmark dataset are considered as closed manifold triangular meshes with only one connected component. A mesh M is called manifold if every vertex v has a neighborhood homeomorphic to a disk or half a disk. A closed mesh is the one that does not contain any boundary edges which has only one adjacent face f.

In addition to the 3D mesh models, the benchmark dataset includes ground truth segmentations that are collected using manual segmentation from human subjects. Figure 1 shows one example of the human ground truth segmentations provided for each category.

Fig. 1.
figure 1

Examples of the human ground truth segmentations provided for 19 categories of the benchmark dataset for 3D mesh models. Colors distinguish the different segments.

Full size image

Since the process of 3D mesh segmentation is interested in clustering the mesh faces into different segments, the mesh face is considered the pivot mesh element for the clustering technique. For this reason, the algorithm starts by computing the dual graph of the input mesh. In the dual representation, each vertex of the original mesh is considered as a face in the dual mesh. Two vertices in the dual mesh are connected by an edge if their original faces were adjacent.

In order to achieve meaningful comparisons, the number of initial cluster centroids of both implementations of the K-means and FCM is set to the exact number of K segments equal to the corresponding human ground truth segmentation. These K cluster centroids are selected randomly among the set of dual mesh vertices. The Euclidean distance is used as a measure of distance between all remaining mesh vertices and the cluster centroids. Equation 3 shows the formula used for computing the Euclidean distance d between two vertices p and q in the 3D space.

$$ d\left( {p,q} \right) = \sqrt {\left( {p_{1} - q_{1} } \right)^{2} + \left( {p_{2} - q_{2} } \right)^{2} + \left( {p_{3} - q_{3} } \right)^{2} } $$
(3)

5 Results and Discussions

In the carried out experiment of applying the clustering-based 3D mesh segmentation techniques, one object of each dataset category is used for evaluation. This results in a total of 19 different meshes. As the results of both the K-means and the FCM clustering techniques are affected by the initial selection of centroids, five different implementations of each technique are applied to each mesh model and the average result is selected.

For quantitative evaluations of the proposed techniques, two well-known performance accuracy measures [24–26] are used from literature. These metrics are appropriate for measuring the degree of refinement, similarity and consistency and provide meaningful comparisons between segmentation results and ground truth images [24, 27]. These metrics include:

  1. 1

    The Rand Index (RI) [25], counts the fraction of pairs of pixels whose labels are consistent between the computed segmentation and the ground truth [28]. The RI range is [0, 1], where the higher value is better. In other words, the score of ‘zero’ indicates the labeling of the test image is totally opposite to the ground truth segmentation and ‘one’ indicates that they are the same on every pixel pair.

  2. 2

    The Global Consistency Error (GCE) [24], measures the degree of overlap of regions. In other words, it measures the extent to which one segmentation can be viewed as a refinement of the other [28]. These related segmentations are considered to be consistent since they represent the same natural image segmented at different scales. The GCE range is [0, 1], where the lower value is better.

Table 1 illustrates the achieved results of K-means-based and FCM-based 3D mesh segmentation techniques for the selected dataset of mesh models including the RI and GCE accuracy measures. The last row shows the average RI and GCE calculated for the entire dataset over all categories for each technique. The second column shows the number of segments used for segmenting each mesh model. Figure 2 shows the visual segmentation results for both techniques for the 19 mesh models.

Table 1. Experimental results of the clustering-based 3D mesh segmentation techniques
Full size table
Fig. 2.
figure 2

Visual 3D segmentation results achieved for the 19 category models. The first row of each model shows the results of the K-means-based clustering while the second row shows the results of the FCM-based clustering technique

Full size image

It can be observed from Table 1 that the FCM-based 3D segmentation technique managed to increase the average rate of RI and decrease the average rate of GCE on the dataset used. Since the higher RI value is the best and the lower GCE value is best, it is concluded that the FCM-based segmentation technique outperforms the K-means-based one. This illustrates the higher efficiency of the FCM-based segmentation technique in terms of achieving more accurate segmentations compared to human segmentations. According to the achieved results, the FCM-based managed to increase the average rate of the RI accuracy measure by 138 % and decrease the average rate of the GCE accuracy measure by 50.9 %.

6 Conclusions and Future Work

The paper introduced the development of 3D mesh segmentation techniques that are based on the use of the unsupervised clustering of K-means and FCM for segmentation. The proposed techniques were evaluated against a dataset of 19 different models representing different categories from the benchmark of SHREC with human ground truths. The Rand Index (RI) measure and the Global Consistency Error (GCE) are used for evaluating the segmentation results.

The FCM-based technique managed to achieve an average RI rate of 0.254 and an average GCE rate of 0.132 compared to 0.187 and 0.259 achieved by the K-means-based clustering technique respectively. On other words, it managed to increase the RI rate by 138 % while decreasing the GCE rate by 50.9 %. These results showed that the FCM-based mesh segmentation technique outperformed the K-means-based technique in terms of accuracy and consistency. This work of clustering-based 3D segmentations would be considered a step toward applications of mesh deformations and reconstruction for future work.