Three-Dimensional Shape Recognition and Classification Using Local Features of Model Views and Sparse Representation of Shape Descriptors

1. Introduction

Recently the rapid development of three-dimensional (3D) scanners and sensors as well as graphic accelerated hardware have attracted an enormous amount of interest for 3D image processing and analysis [1]. Nowadays, 3D shape models are used in various fields such as archaeology, cultural heritage, computer-aided design (CAD), medical applications, 3D object classification, and biometrics. For instance, in industrial applications, 3D CAD models are variously used in a new form of prototyping called digital prototyping. Digital prototyping allows for the easy evaluation of industrial components before fabrication. One of the most important applications in the field of medical diagnostic is the automatic analysis and recognition of abnormalities in the anatomic structures. The recognition of abnormalities in 3D images requires automatic representation and the classification of 3D models, which is a challenging issue.

The recognition and classification of 3D models are of great importance in several applications. However, existing approaches for the classification and recognition of 2D images cannot be applied to 3D images directly because of its different nature and characteristic. The recognition and classification of a 3D model require the extraction of global or local characteristics of a 3D shape and its representation in an appropriate approach that is called a 3D shape descriptor or signature. The performance of a 3D shape recognition algorithm highly depends on the appropriateness of a 3D shape descriptor.

Existing algorithms for 3D shape representation can be roughly categorized into feature-based, viewbased and graph-based approaches [2,3]. In feature-based approaches, global or local features of a 3D shape model are used as the descriptors for shape classification. Most early approaches for 3D shape classification employ global features for shape recognition. Global features are easy and fast methods for 3D shape representation; however, they cannot describe the local deformation of a 3D shape. Therefore, the local features have been recently considered as a solution to handle the shortcomings of global features and increase the discriminating power of shape descriptors.

In comparison with feature-based approaches that consider only the geometric characteristic of a 3D shape, graph-based approaches employ the relations and linkages between the various components of a model for the shape representation. In other words, graph-based approaches construct a graph representing the topological information of a 3D object as a descriptor. In general, graph-based approaches are computationally inefficient and their applications are mostly restricted to CAD/CAM models. Two similar 3D models are looked similar from various views, therefore view-based approaches extract the 2D images of a 3D model from various views to describe it. The number of views and the method to combine views have a major impact on the effectiveness of a view-based algorithm.

This study proposes a new approach for 3D shape classification and recognition using 3D local features of model views. The proposed approach can be considered as a combination of view-based and featurebased approaches. The algorithm commences with the normalization of 3D models. This stage makes the extracted views invariant into rotation and scale changes. Then, 2D images of 3D models are captured from various views. In contrast to existing view-based approaches that mostly extract the silhouette of 3D models, we consider the distance of points from the center of mass of 3D models as the intensity of the extracted views. Consequently, the 2D views of the 3D models are stacked over each other to form the view cubes. The algorithm employs the descriptors of 3D local features in the view cube after applying Gabor filters in various directions. To combine the descriptors of local features, various descriptors from different classes of 3D models are saved during the training stage. These descriptors are called the prototype dictionary of local descriptors. To extract an intermediate feature vector, we measure the similarity between the local descriptors of an input model and the local features of the prototype dictionary. We represent the intermediate feature vectors of 3D models in the sparse domain to obtain the final descriptors of models. Finally, support vector machine (SVM) classifiers are used for the recognition of 3D models. In brief, the main contributions of this paper are as follows:

- A new approach is proposed to represent a 3D model as a cube of model views. In contrast to most view-based algorithms that use the silhouette of a shape model as the view image, our algorithm utilizes grey-level images. The pixel intensities of the grey-level images are obtained by the calculation of distances of points from the center of mass of the shape model.

- The proposed approach leverages a new descriptor that is extracted from 3D local descriptors of the view cube. Therefore, the proposed algorithm can be considered as a combination of viewbased and feature-based approaches.

- A new approach is proposed to represent the descriptor in the sparse domain.

The remainder of this paper is organized as follows. In Section 2, a survey of related work is presented. Section 3 introduces the proposed algorithm for 3D shape recognition. Section 4 presents the experimental results and their analysis and we conclude the paper in Section 5.

2. Related Work

Various applications of 3D shape recognition and classification have attracted a large amount of attention from researches during the past decade. Therefore, several approaches have proposed for 3D shape classification during the past decade. Also, several survey papers have discussed various algorithms for 3D shape recognition, classification, and retrieval [3-6]. As mentioned before, early approaches for 3D object representation mostly focused on global features like area, volume and moments of 3D shapes [7-10]. For Instance, Elad et al. [7] calculated moments of 3D shape and represented them as a descriptor for 3D shape retrieval. Osada et al. [8] used shape a distribution sampled from a shape function measuring the global geometric properties of an object as the shape descriptor. An enhanced version of these features was also used in [9].

Some existing approaches for 3D shape recognition employ descriptors based on a spatial map that uses the spatial relations between different sections of a 3D model [11-13]. For instance, Saupe and Vranic [11] used spherical harmonic coefficients as a shape descriptor. The descriptor measures the maximal extent of shape across all rays from the origin. Spatial maps are generally sensitive to the geometric transformations like the scale and rotation of a 3D object; therefore, a pose normalization stage is inevitable. Kazhdan et al. [12] used a spherical harmonic representation that transforms a rotationdependent shape descriptor into the rotation-independent one. However, spherical harmonics that are based on the latitude-longitude parameterization of a sphere result in singularities in the poles. To handle the problem, Laga et al. [13] uniformly sampled points on the sphere and used the wavelet transform to extract the spherical wavelet descriptors that are the extended version of Zernike moments and spherical harmonics.

Recent feature-based approaches for 3D shape representation mostly focus on local features [14-19]. Descriptors based on local features generally give rise to better discrimination for inter-class shape recognition. The main stage of constructing a descriptor based on local features is the detection of salient points in a 3D shape model. Shilane and Funkhouser [14] defined the distinctive regions of a 3D shape as the areas that their shapes are consistent with the objects of the same type and differ from the objects of other types. Inspired by the characteristics of human visual perception, Zhao et al. [15] used two features called retinex-based importance feature (RIF) and relative normal distance (RND) for salient point extraction. Atmosukarto et al. [16] used the histogram of low-level features like Besl–Jain and Gaussian curvatures for salient point extraction by using a trained SVM. Salient points are then transformed into a 2D longitude-latitude spatial map as a descriptor to classify 3D models. In [17], an extension of Harris method is used to extract the salient points of a 3D shape. The method uses an adaptive technique to determine the neighborhood of a vertex to apply Harris operator. Bu et al. [18] employed deep belief networks (DBN) to learn high-level features that are obtained from local descriptors. They adopted a scale-invariant heat kernel signature and average geodesic distance as the local descriptors that are robust against non-rigid and complex shape deformations.

Graph-based approaches are another group of algorithms for 3D shape recognition [20-24]. In contrast to feature-based methods that describe 3D objects using 3D geometrical properties, graph-based algorithms use the topological information and the relation between various parts of the object for 3D shape recognition. A graph shows how various parts of an object are linked together. Various graph representations have been proposed in the literature, such as skeletal graph [20], Reeb graph [21], and spectral Reeb graph [23,24], to name a few. Graph-based algorithms are computationally expensive and sensitive to small topological changes.

Another category of 3D shape recognition algorithms, which are called view-based algorithms, capture several 2D images from various directions of a 3D model [25-27]. In [25], a set of 2D images is automatically generated from a 3D object, by taking the views from uniformly distributed viewpoints. Then, a set of 2D rotation-invariant shape descriptors are extracted for each image. Finally, a similarity measure is used for 3D model retrieval. In [26], convolutional neural networks (CNNs) are used for 3D shape recognition using multiple views of a 3D model. The method first trains a set of CNNs to combine several views as a single and more informative view. Finally, another trained CNN is used to generate the shape descriptor. Most view-based methods can be considered as an extension to global feature-based methods that extract a global descriptor from the view images. However, Ding and Liu [27] used a viewbased descriptor called sphere image for 3D shape retrieval that takes into account the relation between various views by constructing a star graph. In [28], a feature fusion method and multi-modal graph learning are used for view-based 3D object retrieval. After extracting different visual features, including 2D Zernike moments, 2D Fourier descriptors, and 2D Krawtchouk moments, the Hausdorff distance is computed to measure the similarity between two 3D objects with multiple views. Finally, several graphs are employed for the feature fusion task.

3. Proposed Method

This study aims to classify 3D objects using the local features of model views and the sparse representation of the extracted features. Fig. 1 shows the general block scheme of the proposed algorithm. The proposed method includes two parts comprising training and testing phases. The proposed algorithm is a combined feature and view-based approach that utilizes the 3D local features of model views to construct the required features for 3D shape classification. Both training and testing phases start with the normalization of 3D models. This stage makes the extracted views invariant into the rotation and scale changes. Then a set of 2D images is extracted from 3D shapes by taking views from uniformly distributed viewpoints. Consequently, the 2D views of the 3D models are stacked over each other to form view cubes. We use 2D Gabor filters in companion with a 3D max filter to extract proper characteristics of the view images and take into account the relation between various views. In the training phase of the system, we select some 3D local features from the training set of 3D models as the prototype dictionary of local features. Both in the training and testing phases, the intermediate features of 3D models are computed by calculating the similarity between 3D patches of a 3D model and the prototype dictionary of local features. We use sparse representation to calculate the final descriptors for the classification. The sparse representation of descriptors needs the selection of appropriate basic signals or atoms. This stage that is called dictionary learning is conducted during the training phase. This dictionary is then used to obtain the final descriptors for 3D shape classification via sparse representation. Then the trained SVM classifiers are used for 3D shape recognition.

3.1 Pose Normalization

The 3D shape models may contain and an arbitrary scale, orientation, and position. To make the extracted features robust against the scale, rotation, and position of a model, a pose normalization stage is used before the feature or view extraction. Pose normalization algorithms aim to transform a 3D shape into a new canonical coordinate frame where the representation of the shape is independent of its scale, orientation, and position. Various normalization algorithms such as weighted principal component analysis (PCA) [29], continuous PCA [30] and PCA on the normals of the model (NPCA) [31] have been proposed in the literature. We use the weighted PCA [29] approach for the pose normalization.

In the weighted PCA, the mean vector and covariance matrix of vertex coordinates are calculated as follows:

where n is the number of vertices in a 3D shape model, [TeX:] $$\mathbf{v}_{i}$$ are the coordinates of the shape vertices and [TeX:] $$\mathbf{m}_{V} \text { and } \mathbf{C}_{V}$$ are the mean vector and covariance matrix of the vertex coordinates, respectively. Here [TeX:] $$\omega_{i}$$ is the weight of vertex [TeX:] $$\mathbf{v}_{i}$$ that is defined as the proportion of the sum of surfaces of all triangles that have [TeX:] $$\mathbf{v}_{i}$$ as a vertex to the sum of surfaces of all triangles in the shape. Let A be a matrix consisting of the ordered eigenvectors of the covariance matrix [TeX:] $$\mathbf{C}_{V},$$ as the row vectors. The normalized coordinates of the vertices are then calculated as follows:

3.2 View Cube Construction

After the normalization of 3D shape models, different views of the shape models are extracted to construct view cubes. To build a view cube, a set of 2D images is extracted from a 3D shape by taking views from uniformly distributed viewpoints. The view cube is constructed by stacking of various views of a shape model. The aim of constructing a view cube is to take into account the relation between various views of a shape model for the extraction of the shape descriptor. In the proposed approach, not only the 3D information of a view cube is used in the filtering steps, but also the intermediate features are based on the 3D information of adjacent views. Fig. 3 shows the extracted views and the constructed view cube for a typical 3D shape model with nine views. In contrast to the most view-based algorithms that use the silhouette of a shape model as a view image, we use the distances of points from the center of mass as the intensities of pixels of a view image. This feature provides us the capability of using intensity-based filters such as Gabor filter to extract the proper characteristics of a shape model from its view images.

3.3 Gabor and Max Filtering

The use of distances of points from the mass center of shape models as the intensity of view images provides us the capability of utilizing filters such as Gabor filter for the texture-based feature extraction. Inspired by the biological characteristics of the human visual system, Gabor filters are found to be appropriate for texture representation and discrimination. The weights of 2D Gabor filter are defined as follows:

where denotes the direction of the Gabor filter, is the aspect ratio, is effective width and is wavelength. Our approach for texture representation using Gabor filter is based on the method of [32]. We apply 11×11 pixels 2D Gabor filters to all 2D images of view cube in 16 directions and select the maximum value in 16 directions as the output of Gabor filter. Taken all form [32], , , and

After applying the 2D Gabor filter to the images of the view cube, 3D local max filter is employed to take into account the relations between various view images. To this intent, a 3D local max filter with the dimension of 5×5×5 pixels is experimentally used in this study.

3.4 Extracting Intermediate Features

After applying Gabor and max filtering, the intermediate features are calculated by comparing all 3D local patches in the view cube by some previously-stored local patches, i.e., the prototype dictionary of local features. To this end, in the training stage, we randomly select [TeX:] $$N_{i}$$ 3D local patches with a size of 16×16×3 pixels. By comparing all the 3D local patches in view cube with the prototype dictionary of local features, intermediate features are calculated using the following algorithm:

Select a 3D patch from the prototype dictionary of local features, [TeX:] $$\text { i.e., } \mathbf{p}^{\mathrm{j}}, \mathrm{j}=1,2, \ldots, N_{i}$$

Slide a 3D window with a size of 16×16×3 pixels in the view cube.

Compare the 3D local patches of the view cube with [TeX:] $$\mathbf{p}^{j}$$ as follows: [TeX:] $$r_{i}^{j}=\exp \left(\left\|\mathbf{x}_{i}-\mathbf{p}^{j}\right\|\right)$$ where [TeX:] $$\mathbf{x}_{i}$$ defines i-th 3D local patch in the view cube and [TeX:] $$\| \|$$ denotes 2-norm.

Calculate the max difference [TeX:] $$r m^{j}$$ as follows: [TeX:] $$r m^{j}=\max \left(r_{i}^{j}\right)$$

Construct the intermediate feature vector, [TeX:] $$\text { i.e., } \mathbf{r}=\left[r m^{1}, r m^{2}, \ldots, r m^{N_{i}}\right]^{T}.$$

3.5 Sparse Representation

In this study, the sparse representations of intermediate features are used as the descriptors for 3D shape recognition. In the sparse representation, a feature vector [TeX:] $$\mathbf{r}_{i} \in R^{N_{i}},$$ which denotes an intermediate feature vector, is represented as follows:

where [TeX:] $$\boldsymbol{\alpha}_{i} \in R^{k}$$ is the sparse representation of the feature [TeX:] $$\mathbf{r}_{i}, \mathbf{D} \in R^{N_{i} \times k}$$ is the dictionary or basic signals and [TeX:] $$\mathbf{e}_{i} \in R^{N_{i}}$$ is the error vector. Here k is the number of atoms or basic signals in the dictionary. The sparse representation of an intermediate feature vector [TeX:] $$\mathbf{r},$$ can be obtained by solving an underdetermined system of linear equations as follows:

where [TeX:] $$\|\|_{0}$$ denotes the number of nonzero elements in a vector. To make the solution of the Eq. (8) more feasible, the sparse representation problem may be expressed as:

where [TeX:] $$\|\|_{1}$$ refers to the L1 norm. Since both D and α in the Eq. (8) is unknown, the sparse representation of local descriptors consists of two different stages: 1- dictionary learning and 2- the calculation of sparse codes. The aim of dictionary learning is the selection of appropriate basic signals or atoms. We use the K-SVD algorithm [33] in the training stage of the proposed algorithm to learn a dictionary for sparse representation. To learn a dictionary for the sparse representation, we use the intermediate feature vectors of the training shape models. Let [TeX:] $$\mathbf{R}_{t}$$ denote the intermediate feature vectors of the training shape models and [TeX:] $$\mathbf{A}_{t}$$ represent the corresponding sparse coefficients of [TeX:] $$\mathbf{R}_{t}$$ \mathbf{R}_{t}

where [TeX:] $$n_{t}$$ is the total number of training 3D shape models. The calculation of matrix D, i.e., dictionary using the K-SVD algorithm comprises the following steps:

Step 1. Initialize dictionary D with [TeX:] $$\mathrm{L}_{2}$$ normalized columns.

Step 2. Calculate sparse coefficients using the following equation:

Step 3. Update the dictionary as:

Step 4. Repeat steps 2 and 3 until the convergence.

After the calculation of the dictionary, the feature-sign search algorithm [34] is used to calculate the sparse coefficients for intermediate features as the descriptors of 3D shape models.

3.6 Classification

In this study, SVM classifiers are used to classify 3D shape models using the extracted descriptors. An SVM is a binary classifier that categorizes an input feature vector by evaluating the classifier function [TeX:] $$f(\mathbf{x})$$ as follows [35]:

where [TeX:] $$\mathbf{x}$$ is the feature vector, b and [TeX:] $$\omega$$ are the bias and vector of SVM coefficients respectively, [TeX:] $$\varphi$$ defines a kernel function, and sgn denotes the sign function. Since an SVM is inherently a binary classifier, one against one approach is used in this study to create a multi-class SVM classifier for 3D shape classification.

4. Experimental Results

The proposed algorithm was implemented in MATLAB environment and evaluated with two different 3D shape datasets comprising the McGill 3D shape benchmark (MSB) [36] and Princeton Shape Benchmark (PSB) databases [37]. Fig. 4 shows examples of 3D shape models for the MSB database. This database consists of 19 different kinds of 3D objects with the emphasis is on including models with articulating parts. Fig. 5 illustrates samples from the PSB database. This benchmark contains a database of 3D polygonal models collected from the World Wide Web. This dataset includes 1,814 models divided into three levels of classification. In our experiment, we used the [TeX:] $$3^{\mathrm{rd}}$$ level classification of the PSB database to assess the performance of the proposed algorithm and compare its results with those of other methods.

To construct a view cube, we use a set of nine 2D images with a resolution of 150×200 pixels. These images are extracted from 3D shapes by taking views from uniformly distributed viewpoints. In this study, the prototype dictionary of local features comprises 5,000 local patches of size 16×16×3 pixels.

Fig. 6 shows the correct classification rate of the proposed algorithm on the MSB database. Our experimental results demonstrate that an SVM classifier with linear kernel function results in better classification accuracy. Therefore, one against one linear SVM classifiers are used in the experiments to create a multi-class SVM classifier. Fig. 6 illustrates the percentage of correct classification for the various dimensions of the sparse representation, i.e., k values. Since the MSB database does not specify test and train shape models for the classification, we use 190 random object models for the training and the remaining models for the test. The experiments are repeated ten times and the average classification rates are reported in the figure. The results of Fig. 6 demonstrate that the maximum allowable dimension of sparse representation, i.e., k=190, results in the maximum percentage of correct classification. Table 1 shows the correct classification rate for various classes of the MSB database using k=190. The results of Table 1 show the average classification rate of 83.7% and 100% for seven and 19 classes of the MSB database, respectively. Table 2 illustrates the confusion matrix for the classification of 3D objects in the MSB database. As the results of Table 2 demonstrate, some sources of errors for the proposed algorithm are related to the misclassification of airplanes as birds, tables as chairs and dinosaurs as four-limbs, to name a few. We also tested the proposed algorithm for 3D shape classification with and without the sparse representation. Table 3 compares the percentage of correct classification for the proposed algorithm with and without the sparse representation. The results of Table 3 show that the sparse representation of intermediate features enhances the classification rate up to 6.4%.

To show the effectiveness of the proposed algorithm, we also compared the results of the proposed algorithm on the MSB database with those of method of Atmosukarto et al. [16]. This method uses the histogram of low-level features like Besl–Jain and Gaussian curvatures for salient point extraction. Salient points are then transformed into a 2D longitude-latitude spatial map as a descriptor to classify 3D models. Fig. 7 illustrates the correct classification rate of method of Atmosukarto et al. [16] on the MSB database using K nearest neighbors (KNN) classifier with various K values. The results of Fig. 7 show the maximum correct classification ratio of 65.47% for K=1. Table 4 illustrates the confusion matrix for the classification of 3D objects in the MSB database using Atmosukarto et al. method. A comparison between the results of Tables 2 and 4 shows the effectiveness of the proposed algorithm.

Fig. 8 shows the correct classification rate of the proposed algorithm on the PSB database. SVM classifiers with linear kernel function are experimentally used in this experiment as well. Fig. 8 illustrates the percentage of correct classification for the various dimensions of the sparse representation, i.e., k values. In this experiment, 907 objects are used to train the classifiers as well as obtaining the dictionary for sparse representation. The 907 remaining objects are also utilized to test the proposed algorithm. The results of Fig. 8 demonstrate that the maximum allowable dimension of sparse representation, i.e., k=907, results in the maximum percentage of correct classification.

Table 5 shows the correct classification rate of the proposed algorithm on the PSB database with and without applying the sparse representation stage on intermediate features. The results of Table 5 show that the sparse representation of intermediate features increases the correct classification rate of the proposed algorithm up to 16.99%.

We also compared the results of applying the proposed algorithm on the PSB database with the methods of Bu et al. [18] and Hamid and Nakajima [38]. Bu et al. [18] leveraged the geodesics-aware bag-offeatures (GA-BoF) as the initial features. Then DBNs were used for dimensionality reduction and 3D shape classification. They also reported the results of shape classification using GA-BoF features and some of other dimensionality reduction algorithms such as PCA, multidimensional scaling (MDS), linear discriminant analysis (LDA), and locally linear embedding (LLE) algorithms. Table 6 compares the results of the proposed algorithm on the PSB database with GA-BoF features with DBNs and some other dimensionality reduction algorithms as well as the method of Hamid and Nakajima [38]. The results of this table demonstrate the higher performance of the proposed algorithm.

5. Conclusions

This study reports a new approach for 3D shape recognition using 3D local features of model views. In comparison with the existing view-based approaches that mostly extract the silhouette of 3D models, we consider the distances of the points from the center of mass of a 3D model as the intensities of the pixels of extracted views. Then, we use Gabor-based filters to extract proper features for shape classification. To take into account the relationships between various views, we use a new approach for 3D local feature extraction by the construction of view cubes. Additionally, we describe intermediate features in the sparse domain to enhance the accuracy of classification.

Experimental results on both the PSB and MSB databases demonstrate the effectiveness and higher performance of the proposed method on the classification of 3D objects. Additionally, the comparisons of the results generated by the proposed method with those of other state-of-the-art approaches show that more reliable results could be obtained using the proposed method.

The experimental results also show that the sparse representation of intermediate features increases the accuracy of the proposed algorithm. Our experiments using SVM classifiers with a radial basis function (RBF) as a kernel demonstrate that the correct classification rate decreases with an RBF kernel function. This effect shows that the sparse representation of intermediate features makes them linearly separable.

According to the results obtained by the proposed approach, the increase in the number of coefficients for the sparse representation enhances the performance of the proposed approach. In the proposed approach, we experimentally used the maximum number of allowable coefficients in the training phase, i.e., the number of intermediate features of shape models. This effect indicates the scalability for the proposed algorithm, because by increasing the number of classes and shape models it is possible to increase the number of coefficients for the sparse representation.