BibTeX entry

@PHDTHESIS{200611Huaijun_Qiu,
  AUTHOR={Huaijun Qiu},
  TITLE={Spectral Methods for Computer Vision Problems},
  SCHOOL={University of York},
  MONTH=Nov,
  YEAR=2006,
  URL={http://www.bmva.org/theses/2006/2006-qiu.pdf},
}

Abstract

Graph spectral methods are concerned with using the eigenvalues and eigenvectors of the adjacency or Laplacian matrices to characterise graph structure. Applications in computer vision include object recognition, image segmentation and data analysis. Although widely used, most graph spectral algorithms are relatively simple. Most of the current applications are limited to use only one or just a few eigenvalues and eigenvectors of the affinity matrix. Although elegant and concise many valuable properties are also neglected. In this thesis, we focus on exploring more complex uses of the Laplacian spectrum. Our starting point is the Fiedler vector, i.e. the second smallest eigenvector of the Laplacian matrix. Although it has been intensively applied in graph bipartition and image segmentation, its usage is still quite simple and restricted. We aim to further extend its utility to decompose graphs into non-overlapping partitions. By doing so, we will be able to cast inexact graph matching problem into the matching of these subunits and the whole matching process can be realized in a hierarchical framework. Further, the pattern of partitions can be stabilised by incorporating a diffusion process to smooth away the effects of structural errors. The matching criteria is given by two comparable methods: one is dictionarypadding based discrete relaxation and the other one is an edit distance measure. To test our method, we have applied it to both synthetic and real-world images and the results show that it is robust under severe structural corruption and varii ation. Our second contribution in this thesis is to develop spectral methods which are capable of utilising the full Laplacian eigenspectrum effectively. We turn to the commute time (the expected time a random walk takes from node u to node v and return). A theoretical analysis of the commute time demonstrates how it can be used for embedding and clustering. The first application of commute time is to apply it as an energy dissipation measure on nodes of the graph. To simulate a diffusion process, we introduce an extra node as heat source. Then a graph can be divided into several concentric layers based on the heat distribution and graph matching is realized by matching these layers with commute times as attributes on the nodes. The second application of commute time relies on the robustness of the commute time matrix to structural noise. Commute time is a more robust graph representation than the adjacency matrix. As a result, the minimum spanning tree for the commute time of the graph is more stable under structural variation and can be used as a stable structure for inexact graph matching. Our third application of commute time exploits its grouping properties. We propose an image segmentation method based on the recursive bipartition of the smallest eigenvector of the commute time matrix. Finally, a commute time preserving embedding is used to solve the multibody motion tracking problem. We extend the traditional factorisation method of Costeira and Kanade (Costeira and Kanade, 1997; Costeira and Kanade, 1995) by embedding the shape interaction matrix into a subspace. Object points in this space are easily separated by a k-means algorithm.