Vertex-Weighted Hypergraph Learning for Multi-View Object Classification

1 Introduction

Recent advances on computer techniques and graphic hardware have prompted wide applications of 3D objects in various domains [Bimbo and Pala., 2006], such as architecture design, entertainment and the medical industry. Confronting the increasing 3D big data, effective 3D object classification and retrieval techniques [Guo et al., 2014; Chen and Bhanu, 2009] have become an urgent requirement for both the research society and industrial practice. Recently, multi-view based object representation [Chen et al., 2003] has attracted much attention due to its superior performance on visual content description of 3D objects. In multi-view 3D object clas-

.

Figure 1: Three examples of multi-views of 3D objects.

sification, each object is represented by multiple images, and Figure 1 provides three examples of multi-views of 3D objects. In this work, we focus on multi-view 3D object classification.

Existing methods [Wang et al., 2012b; Gao et al., 2012] proposed to train classifiers, or employ graph/manifold structure to predict the object category. Although there have been much attention on this task, it is still an challenging task. The main challenges of multi-view 3D object classification are two-fold, i.e., the relationship modeling among different objects and the possible imbalance training data, which also exists in other applications [Shao et al., 2014]. First, each 3D object is represented by a set of images, leading to much complicated comparison between 3D objects. How to formulate the correlation among 3D objects with multiple views is a hard task. Second, the 3D data from different categories may vary significantly. Here we take the popular Princeton Shape Benchmark (PSB) [Shilane et al., 2004] as an example. With average 11.26 3D objects for each category, the standard deviation of the number of samples for each category is 13.02, indicating a highly imbalance issue. Existing works may work well when the training data for different data categories are comparable but may degrade the performance when they are not.

To formulate the complex correlation among 3D objects, we propose to employ the hypergraph structure for data modelling. In recent years, hypergraph learning [Zhou et al., 2007] has shown superior performance in many computer vision tasks, such as image retrieval [Huang et al., 2010], object segmentation [Huang et al., 2009] and classification [Gao et al., 2012]. However, traditional hypergraph structure cannot handle the data imbalance issue, which can degrade the performance of hypergraph modeling. To this end, we propose a vertex-weighted hypergraph learning algorithm for multi-view 3D object classification, which introduces an updated hypergraph structure considering the vertex weights.

In our method, the correlation among 3D objects is formulated in a hypergraph structure, and the weights for both vertices and hyperedges are associated with the hypergraph. The vertex weights are used to define the influence of different samples on the learning process, and the hyperedge weights are used to generate optimal representation. The learning process is conducted on the vertex-weighted hypergraph and the learned object relevance is used for classification. The proposed method has been evaluated on two public benchmarks, i.e., the National Taiwan University (NTU) 3D model dataset [Chen et al., 2003] and the Princeton Shape Benchmark (PSB) [Shilane et al., 2004]. Experimental results and comparison with the state-of-the-art methods demonstrate the effectiveness of our proposed method.

2 RelatedWork

On multi-view object classification, a manifold-to-manifold distance (MMD) was introduced in [Wang et al., 2012b]. Each group of images can be represented in three levels, i.e., point, subspace and manifold. In this method, the compared multi-views of objects were formulated by manifolds and the corresponding manifold-to-manifold distance was calculated to measure the distance between two groups of images. Huang et al. [Huang et al., 2014] introduced a hybrid metric learning approach to jointly employ heterogenous statistics, i.e., mean, covariance matrix and Gaussian distribution, multi-view classification. Gao et al. [Gao et al., 2012] proposed to employ the hypergraph structure to formulate the relationship among different objects, where the connection among objects were built using view clustering. In this work, multiple hypergraphs were constructed and the relevance among objects and the hypergraph weights were jointly learned. A covariance discriminative learning (CDL) method was introduced in [Wang et al., 2012a]. In this method, the covariance matrix of multiple views was extracted for object representation and the linear discriminant analysis was conducted to measure the distance between two sets of views. Huang et al. [Huang et al., 2015] proposed a LogEuclidean metric learning (LEML) method, which learned a Log-Euclidean metric to transform the matrix logarithms from the raw tangent space of multiple views to a discriminative tangent space for the objects. Regarding the representation of multi-view objects, much research attention has been attracted. Ji et al. [Ji et al., 2014] proposed a compact bag-of-patterns descriptor (CBoP) to mine the discriminative visual patterns from 3D point clouds, which innovatively alleviates the ill-posed pattern configurations from 2D images. It is a breakthrough that such descriptor well address both compactness and discriminativity in multi-view representation.

In recent years, there have been successful and serial achievements [Tao et al., 2006; 2007; 2009; Yu et al., 2016] on learning optimal subspace or metric for data modeling. Other works [Liu et al., 2015; Xu et al., 2015; Shao et al., 2016; Liu et al., 2017] further explore the multi-task, multi-view learning algorithms. Recently, hypergraph learning has been widely applied in many applications. Huang et al. [Huang et al., 2010] proposed to employ the hypergraph structure to formulate the relationship among images. In this work, only the vertex relevance was learned for image ranking. Huang et al. [Huang et al., 2009] also proposed to use the hypergraph structure to represent the spatial-temporal neighborhood correlation among image patches. In this method, hypergraph cut was used for object segmentation in videos. Existing hypergraph learning methods only focus on learning the vertex correlation only or joint learning the vertex relevance and the hyperedge weights simultaneously. There is no effort targeting on considering the vertex weighting issue, which is an important direction to further improve the representation ability of hypergraph.

3 The ProposedMethod

In this section, we introduce our vertex-weighted hypergraph learning for multi-view 3D object classification. First, the features are extracted for all images of the 3D objects, and then the pairwise 3D object distance is measured. Based on the distance, a hypergraph is constructed, where the vertex weights are calculated based on the distribution of training samples for each class respectively. Then, the learning process is conducted on the hypergraph to estimate the optimal relevance of each 3D object to each class and the hyperedge weight simultaneously.

3.1 View Feature Extraction and Pairwise Object Distance Measure

For n 3D objects in the database {O1, O2, . . . , On}, each object Oi is represented by a set of views {vi1, vi2, . . . , vini }. Here two features, i.e., Zernike moment and histogram of oriented gradient (HOG), which have been widely used in 3D object analysis tasks, are employed to represent each view in this work. We note that the employed features are flexible and can be replaced/expanded based on the hypergraph structure.

Given two sets of images and corresponding features, we employ the Hausdorff distance to measure the 3D object distance between two objects O1 and O2 . It is noted that other distance measures can be also used here. As we have two types of features for each view, there are two distances for each pair of 3D objects based on Zernike moment and HOG, respectively.

3.2 Hypergraph Construction

Given the 3D object pairwise distances, the relationship among the nt training objects and the testing object is formulated in a hypergraph structure G = (V, E,W). In G, V is the vertex set, where each vertex denotes one object, and there are nt + 1 vertices in total. E is the hyperedge set and W is the matrix of hyperedge weights. To generate the connection among vertices, i.e., hyperedges, each time one vertex is selected as the centroid, and one hyperedge is constructed to connect the centroid and its K nearest neighbors in the corresponding feature space. This process repeats twice for the two types of features and generates 2(nt + 1) hyperedges for G.

An incidence matrix H is then generated to represent the relationship among different vertices. The (a, b)-th entry of the incidence matrix H indicates whether the a-th vertex is connected via the b-th hyperedge to other vertices. The incidence matrix H of hypergraph G = (V, E,W) is gener-

structure, all the vertices are regarded as equal weights. We note that different training samples could have varied importance and those categories with too many training samples may dominate the classification process. Existing hypergraph learning methods fail to deal with the imbalance data issue. To this end, we propose to a vertex weighting matrix U to weight different vertices, where U(v) is the vertex weight of vertex v.

Here, the vertex degree of the a-th vertex va ∈ V and hyperedge degree of the b-th hyperedge eb ∈ E are calculated, respectively, as d (va) = ∑e∈EW(e)H(va, e), and δ(eb) = ∑v∈V U(v)H(v, eb). We note that different from traditional hypergraph structure, where the hyperedge degree is fully determined by the connection fromH, the hyperedge degree δ here takes both the connections on H and the corresponding vertex weights into consideration simultaneously.

Now, two diagonal matrices Dv and De can be generated with every entry along the diagonal corresponds to the vertex degree and hyperedge degree, respectively. Note that all the hyperedges are initialized with an equal weight, e.g., 1.

Traditional hypergraph-based methods do not take the importance of vertices into consideration, which may degrade the representative ability. In our method, we introduce the vertex importance in the hypergraph structure. The main idea for vertex weighting is to enhance the samples that may convey discriminative information and weaken the samples which may be redundancy, such as repeated/closed training samples, and bring in little information but much bias. Before conducting hypergraph learning, we first initialize the vertex weights.

For the ith category, here we let {Ot i1 , Ot i2 , . . . , Ot im} denote all m training data. We can then measure all the pairwise distances do (Ot ia , Ot ib ) between each two objects based on the two features, respectively. The mean distance from Ot ia to all other training samples for the ith category can cal-

vertex weight for the training sample Ot ia can be written as

These vertex weighs are further normalized for each class respectively. This initialization approach can provide higher weights to the samples which are not close to others and lower weights to the samples which are similar to others. In this way, the repeated/close samples will have relatively smaller influence and the individual samples could becomes more important on the hypergraph learning process.

3.3 Vertex-Weighted Hypergraph Learning

Given the hypergraph, the relationship among vertices can be modeled based on how they are connected via hyperedges. The relevance matrix F for hypergraph G = (V, E,W) is the to-be-learned matrix, which indicates the relevance of each object to the categories. In this work, it can be learned from a joint optimization process considering the hypergraph structure regularizer, the empirical loss based on labeled data, and the hyperedge weights simultaneously.

Hypergraph Structure Regularizer

As we have a new structure with vertex weights compared with traditional hypergraph, we need to define the new hypergraph ructure regularizer first. Generally, the more two vertices are connected via hyperedges, the more similar their relevance scores are and vice versa. And, the higher weights of the two vertices, the higher cost will be provided. Based on this, the hypergraph structure regularizer Ω (F) can be written

where F is the to-be-learned relevance matrix, F(:, k) is the k-th column of F, ncate is the number of 3D object categories, and ∆ = U - Θ = U - Dv - 1 2 UHWDe-1HTUDv - 12 is called vertex-weighted hypergraph Laplacian.

Here we note that the hypergraph Laplacian for traditional hypergraph is ∆t = I -Dv - 1 2 HWDe-1HTDv - 12 [Zhou et al., 2007]. By comparing ∆ and ∆t, we can notice that the vertex-weighted hypergraph Laplacian takes the weights of different vertices into account when measuring the cost on hypergraph structure.

Empirical Loss

The empirical loss term is defined similarity as traditional hy-

Y ∈ Rn×ncate is the label matrix and each of its entries denotes the category a subject belongs to, and Y(:, k) is the k-th column of Y. If the a-th vertex belongs to the first category, then the (a, 1)-th and (a, 2)-th entries in Y are set to 1 and 0, respectively.

Hyperedge Weights

To generate better hypergraph representation, different hyperedges should have different influence, and an optimally learned hyperedge weight can help to improve the representation ability of the hypergraph structure. Based on this, we further learn the weights of hyperedges by adding a hyperedge weight regularizer tr(WT W).

Here, the learning task on vertex-weighted hypergraph is composed of three contents, i.e., the hypergraph structure regularizer, the empirical loss and the hyperedge weight regularizer. We can have the following overall cost function:

The objective function for the learning task on vertexweighted hypergraph can be written as

3.4 Solution

To solve the optimization task in Eq. (3), we conduct an alternative strategy. We first fix W, and optimize F as

The objective function in Eq. 4 can be rewritten as

According to [Zhou et al., 2007], F can be solved by F = (I + 1λ (I - Θ))-1 Y. We then fix F, and optimize W as

The objective function in Eq. (3) can be rewritten as

The above optimization task is convex on W and can be solved via quadratic programming. The above optimization procedure repeats until convergence. As the objective function decreases in each step and has a lower bound of 0, the convergence can be guaranteed.

Based on the learned F, the relevance of the testing 3D object to 3D categories can be obtained. The testing data can be classified to the category with highest relevance value.

4 Experiments

4.1 Testing Datasets and Settings

We have conducted experiments on the National Taiwan University (NTU) 3D model dataset [Chen et al., 2003] and the Princeton Shape Benchmark (PSB) [Shilane et al., 2004]. The NTU dataset consists of 549 3D objects from 46 categories, e.g., bed, bike, boat, and table. The PSB dataset contains 1,814 3D models from 161 categories. For each 3D object, 60 virtual cameras are employed to capture multiple views, which are located at the vertices of a polyhedron with the same structure with Buckminsterfullerene (C60). Thus, each 3D object has a group of 60 images. The distributions of sample numbers for each class on the two datasets are shown in Figure 2, from which we can notice that the difference among classes is significant.

For these two datasets, we further generate three subsets by removing small categories. Here, the standard deviation std of the number of samples for different categories is used to measure the class imbalance. The number of object category ncate and the number of objects nall for each subset and corresponding std are provided in the top rows of Table 1 and Table 2, from where we can notice large variance for the original datasets and corresponding subsets.

In the classification task, 10% to 80% samples for each class are randomly selected as the training data and all left samples are used as the testing data. This procedure repeats 10 times and the average classification accuracy is reported.

The following methods are employed for comparison.

1. Manifold-to-Manifold distance (MMD) [Wang et al., 2012b].
2. Covariance Discriminative Learning with Partial Least Squares (CDL PLS) [Wang et al., 2012a].
3. Log-Euclidean Metric Learning (LEML) [Huang et al., 2015].
4. Traditional hypergraph learning (HL) [Zhou et al., 2007].
5. Hypergraph learning with hyperedge weight update (HL-E) [Gao et al., 2012].
6. Vertex-weighted hypergraph learning (V-HL), i.e., the proposed method without hyperedge weight update.
7. Vertex-weighted hypergraph learning with hyperedge weight update (V-HL-E), i.e., the proposed method. In all hypergraph-based methods, the number of selected neighbors for hyperedge generation is set as 10, λ is set as 10, and µ is set as 1, respectively.

Here, MMD, CDL PLS and LEML are the state-of-the-art methods on object classification based on multi-views. HL and HL-E are traditional hypergraph learning methods for comparison.

4.2 Experimental Results

Experimental results are demonstrated in Figure 3 and Figure 4, respectively. We also compare our V-HL method with traditional HL method on the subsets for the NTU and the PSB datasets, respectively, and the results are demonstrated in Table 1 and Table 2. From these results, we can have the following observations.

1. The proposed V-HL and V-HL-E methods outperform all other compared approaches. Here we take the results with 20% data for training as an example. V-HL-E achieves gains of 72.37%, 19.78%, and 52.10% compared with MMD, CDL PLS and LEML on the NTU dataset, where the improvements are 22.23%, 88.43%, and 66.74% on the PSB dataset, respectively.
2. The vertex weights on hypergraph leads to improvement of the classification performance. On the NTU dataset, V-HL outperforms HL by 13.4%, 16.3%, 12.1%, and 16.9% when 10%, 30%, 50%, and 70% samples are used as training data, respectively. Similar results can be observed when compare V-HL-E with HL-E. These results can justify that the proposed vertex-weighted hypergraph structure can have better representation for object relevance modeling.
3. Hyperedge weight learning can improve the classification performance. For example, V-HL-E outperforms VHL by 2.3% and 4.4% when 10% and 50% samples are used as training data on the NTU dataset.

The better performance of our proposed method can be attributed to the following two reasons. First, the hypergraph structure is able to explore complex relationship among 3D objects, which leads to the superior performance of all hypergraph-based methods over other methods. Second, our vertex-weighted hypergraph structure takes the vertex impact into consideration. In our work, we aim to reduce the influence of repeated training data which could be redundancy and illy dominate the classification process. In this way, even the minority of the training samples in the original dataset can have better impact on the classification decision. When some classes have too more samples than others, giving equal weights for all samples will focus more on the huge classes and decrease the classification performance. Compared with traditional hypergraph which ignores the vertex weights, the proposed method is able to measure a more optimal hypergraph Laplician and accordingly generate a better data correlation. We note that the proposed method is a general extension of traditional hypergraph learning methods, and it can be used in other tasks besides 3D object classification.

The limitation of the proposed method lies in the computational load from the relevance learning and hyperedge weight learning procedure when dealing with large datasets. It is noted that both effectiveness and efficiency are important in practice. In this work, we mainly focus on building a robust learning framework towards better effectiveness and put efficiency as our future work. Confronting the computational cost issue, there are two possible solutions. First, data downsampling can be conducted to reduce the data size before hypergraph learning. Second, besides conducting hypergraph learning directly, it is possible to investigate hierarchical hypergraph learning strategy which regards the data in a pyramid structure. Thus, each layer can have less data and the computational cost can be reduced accordingly. We also note that 3D object classification is just one application of the proposed vertex-weighted hypergraph learning method and it can be used in other tasks too.

On Hyperedge Generation

In this subsection, we evaluate the influence of the number K of selected neighbors for hyperedge generation. We vary K from 3 to 50, and the experimental results are shown in Figure 5. As shown in the results, the performance is steady when K varies in a large range. When K is too small or too large, the performance becomes slightly worse. When K is too small, such as K = 3, each hyperedge connects too few vertices and the relationship among vertices cannot be fully explored. When K is too large, such as K = 50, each hyperedge connects too many vertices and the discriminative ability of the hypergraph structure may be limited. Both small and large K values will degenerate the representation ability of the hypergraph structure.

On the Weights of Regularizers

In our framework, there are two parameters that control the relative impact of different regularizers in the objective function, i.e., λ on empirical loss and µ on hyperedge weights, respectively.

To evaluate the influence of λ and µ on the object classification performance, we first keep µ as 1 and vary λ from 0.01 to 1000, and then keep λ as 10 and vary µ from 0.01 to 1000, respectively. Experimental results are demonstrated in Figure 6 to Figure 7. As shown in these results, the proposed method can achieve steady performance when λ and µ vary in a large range. When λ and µ are too small or too large, the corresponding regulariers will either dominate the objective function or have quite little influence on the results, which could degrade the performance.

4.3 Comparison with Deep LearningMethod

The previous experiments have demonstrated that the proposed method with traditional features (Zernike Moments and HOG) can outperform the existing methods. We note that deep learning methods have been investigated in many computer vision tasks in recent years. Su et al. [Su et al., 2015] introduced a 3D shape recognition method (MVCNN) using multi-view convolutional neural networks. Different from the deep learning methods, which serve as an end-to-end classification framework, the proposed method mainly works as a classification method, indicating that the output of the deep learning algorithm, such as MVCNN in [Su et al., 2015] can be used as one feature for processing. We have conducted experiments on the NTU dataset with 10% to 30% training data to compare the proposed method with deep learning features with MVCNN [Su et al., 2015]. Experimental results are demonstrated in Figure 8, from which we can notice that 1) MVCNN works much better than existing methods, and 2)

the proposed method with deep learning features can achieve better performance compared with MVCNN [Su et al., 2015]. The improvement compared with MVCNN is not very significant as MVCNN has already achieved very high accuracy.

5 Conclusion and FutureWork

In this paper, we propose a vertex-weighted hypergraph learning approach for multi-view 3D object classification. Our method formulates the correlation among 3D objects in a hypergraph structure to explore the high-order relationship underneath the multi-view data. By introducing vertex weights, our method is able to explore the vertex importance in the hypergraph structure and the learning process on hypergraph can be more optimal for object classification, especially when the training data for different categories are not balanced.

To evaluate the proposed method, experiments are conducted on the NTU and the PSB datasets. The proposed method using traditional features, such as Zernike Moments and HOG, shows superior performance compared with both the state-of-the-art methods and traditional hypergraph methods. We have also tested the proposed method with the deep learning features. The experiments demonstrate that the proposed method with deep learning features can achieve better performance compared with the deep learning method.

Acknowledgments

This work was supported by National Natural Science Funds of China (61671267,61527812), National Science and Technology Major Project (No. 2016ZX01038101), MIIT IT funds (Research and application of TCN key technologies) of China, and The National Key Technology R&D Program (No. 2015BAG14B01-02).