With the rapid development of the computer science and technology, the amount of image data produced and accumulated is dramatically increased. How to analysis these image data effectively becomes a hot research top in computer vision and machine learning area. Image feature matching and recognition are two fundamental problems and tasks in computer vision. Effective image match-ing is also basic and beneficial for image recognition task. Besides, the feature matching problem itself is also worth to study in both theory and application.In this dissertation, we focus on image matching and recognition methods by exploring graph and sparse models. Based on analysis of observation on (1) ignorance of the structure information in image representation and recognition and (2) inherent sparse property (sparsity) of feature matching problem, this dissertation focus on image structure representation, matching and recognition with graph theory and sparse constraint models.As a kind of popular methods, graph based image structure representations have drawn more and more attentions. A robust graph representation of images is usually useful and also important for image feature matching problem. Here, the key point of robust graph representation is to design robust graph models. Due to imperfect imaging process and variance of image contents, the struc-ture information of images usually contains some uncertainly information. Thus, traditional graph models can not be adapted well to represent this kind of uncer-tainly data. This motivated us to explore random graphs instead of traditional graph models for image structure representation. In this dissertation, we present a new random graph, called geometric-edge random graph (G-E random graph) for image representation, matching and analysis. G-E random graph has a de- sired uncertainly and evolutionary structure, and thus can be adopted suitably to uncertainly structure information representation (extraction) for images. We present the detail analysis of G-E graph model, including model construction, representation, matching and vectorization. Also, we apply G-E graph and as-sociated matching technique for image representation, matching and recognition tasks.In additional to robust graph models, effective matching algorithms also play an important role for image feature matching problem. The matching problem is discrete in nature and thus NP-hard. Thus, approximate methods and solutions are required. Many works have been proposed to firstly develop a continuous problem for this problem and then try to find some continuous approximate solutions for this problem. One drawback is that this kind of approximation entirely ignores the discrete constraint in general and thus may lead to weak local optimal. Indeed, the optimal solution for matching problem is discrete and thus nonnegative sparse in nature. The sparse constraint can be seen as a close approximation for discrete constraint. This motivated us to develop some sparse models for graph matching problem and try to obtain some sparse solutions for the problem. Compared with traditional methods, the main benefit of the proposed sparse matching model is that it can generate a sparse optimal solution for the matching problem and thus approximates the original discrete solution closely. Recently, sparse theory and methods is a hot research topic in computer vision area. These research results provide some basic ideas and methods for our sparse matching model development and computation.Using image feature matching technique, we can obtain a kind of similar-ity (or distance) measurement between images. The similarity of images can also been obtained using some kernel techniques. Indeed, the similarities of im-ages provide a kind of structure information between images. This structure can be represented by some graph models. However, many methods such as principal component analysis (PCA), nonnegative matrix factorization (NMF), et.al. generally ignore to explore this kind of geometric structure information. In this dissertation, based on PCA and graph Laplacian embedding, we present graph-Laplacian PCA (gLPCA) method. The key point of gLPCA method is that it further incorporates the structure information between images in the low-dimensional representation of PCA and thus increases the robustness of P-CA method. We have applied gLPCA to image reconstruction, low-dimensional embedding and image recognition tasks and obtained promising experimental results. |