Study Of Hypergraph Learning Algorithms On Image Feature Extraction And Classification

Image feature extraction and classification are two of the most important tasks in computer vision, pattern recognition and image processing, they have been attracted extensive attentions for decades. They are also the fundamental topics of many other computer vision and image processing tasks, such as image understanding, object detection, image retrieval and medical image analysis, which can directly effect the performances of successive works.The thesis reviews the recent graph and hypergraph learning works in image feature extraction and classification, and analyzes the structural advantage of hypergraph over graph. And then it focuses on studying the hypergraph learning techniques to address the aforementioned computer vision issues from the perspectives of subspace learning, hypergraph construction and attribute learning. The contributions and results of this thesis are as follows:(1) In order to address the issue that Discriminant Locality Preserving Projections(DLPP) only can approximates the category relations of samples via using the geometric similarity between each two homogenous samples, a new supervised subspace learning algorithm named Discriminant Hyper-Laplacian Projections(DHLP), is proposed. DHLP construct a hypergraph in a supervised way to intuitively depict the category relations of samples via using its hyperedges, then it utilize the Laplacian matrix of this hypergraph to replace the original graph-based Laplacian matrix in DLPP to learn a subspace, which can preserve the category relations of samples for addressing the image feature extraction issue. Extensive experiments demonstrate that DHLP can significantly improve the discriminating power of DLPP. Moreover, from the perspective of graph embedding, most of subspace learning algorithms can be reformulated as a graph learning model which is similar to DLPP. In such case, the idea of DHLP can be also applied to enhance these algorithms.(2) In order to mitigate the high computational complexity of DLPP, the Scalable Discriminant Hyper-Laplacian Projections(SDHLP) is proposed. In SDHLP,the model of DHLP is approximately considered as a spectral regression issue, which can be more efficiently solved. SDHLP not only reduces the computational complexity from the cubic times with respect to the dimension of feature to linear, but also achieves a similar performance as DLPP.(3) In order to overcome the drawback that the conventional hypergraph construction method is often not accurate and robust for depicting the data relations, we present an algorithmic framework named Regression-based Hypergraph(RH) to use the regression model to construct the high quality hypergraph, and take Sparse Representation(SR) and Collaborative Representation(CR) as two regression model instances to respectively construct the L1-norm hypergraph and L2-norm hypergraph for tackling the image clustering and classification tasks. The experiments show that they can inherit the merits of SR and CR. More specifically, compared to the conventional hypergraphs, they are more discriminative and more robust to noise and occlusions.(4) The Hypergraph regularized Attribute Predictor(HAP) algorithm is proposed for overcoming the drawback of the traditional attribute learning methods that cannot exploit the correlations of attributes. Inspired by the ideas of DHLP and the hypergraph-based transduction, HAP leverages the attribute labels to construct a supervised hypergraph to intuitively depict the attribute relations of samples(each hyperedge is corresponding to an attribute relation) and considers the attribute prediction problem as a hypergraph partition problem. HAP can preserve the correlations of attributes during the hypergraph partition, since partitioning a vertex set(sample set), which shares a lot of hyperedge, will lead to a heavy penalty. In HAP, the hypergraph cuts are deemed as the attribute predictions of samples. Therefore, the optimal cuts can be learned via minimizing the hypergraph structure loss and attribute prediction errors simultaneously. After obtaining the optimal cuts, the attribute predictors can be derived via learning the mapping from the sample space to the hypergraph embedding space, since these cuts can be deemed as the hypergraph embeddings from the perspective of graph embedding. The experimental results on three popular attribute databases demonstrate that HAP can achieve good performances in the tasks of attribute prediction, Zero/N-shot learning and image data categorization. Moreover, it is also worthwhile to point out that HAP should be the first hypergraph-based classifier that belongs to the supervised learning.(5) In order to flexibly exploit the extra side information during the attribute learning, HAP model is further modified as a multi-graph partition model. In this model, the graphs or the hypergraphs are adopted to depict different categories of side information and then they will be imposed into HAP model as the penalty terms to guarantee the minimizations of the side information losses during the attribute learning. In the thesis, we take the class information as an example to present Class Specific HAP(CSHAP)algorithm which attempts to use class information to further improve the classification ability of HAP. The observations from the experiments verify our assumption.(6) HAP and CSHAP are kernelized to support the nonlinear case. In the real world issues, the relations between samples and attributes are often nonlinear instead of linear. Therefore, such kernelization maybe further improve the performances of algorithms.