Spectral Representation for Matching and Recognition

In this thesis, we aim to use the spectral graph theory to develop a framework to solve the problems of computer vision. The graph spectral methods are concerned with using the eigenvalues and eigenvectors of the adjacency matrix or closely related Laplacian matrix. In this thesis we develop four methods using spectral techniques: (1) We use a Hermitian property matrix for point pattern matching problem; (2) We use coefficients of symmetric polynomials to cluster similar human poses using the skeletal representation acquired from Microsoft Kinect; (3) We use coefficients of the elementary symmetric polynomials to make the direction of the eigenvectors of the proximity matrices consistent with each other for the problem of correspondence matching; (4) We use commute time embedding to construct a 3D shape descriptor for the purpose of 3D shape classification. In Chapter 3 we address the problem of correspondence matching. We extend the Laplacian matrix to the complex domain by constructing a Hermitian property matrix. We construct a Hermitian property matrix from the spatial locations of the 2D feature points extracted from a pair of images and the angular information associated with these feature points. We construct the Hermitian property matrix in a way that reflects the Laplacian matrix. The complex eigenvectors of the Hermitian matrix is then used to find the correspondences between pairs of points across two images. We embed the complex eigenvectors of the Hermitian property matrix in the iterative alignment EM algorithm developed by Carcassoni and Hancock to make it robust to rotation, noise and point-position jitter. Experimental results on both synthetic and real world data have been presented. Chapter 4 develops a clustering method using four different type of feature vectors constructed from the complex coefficients of the elementary symmetric polynomials. These polynomials are computed from the eigenvalues and the complex eigenvectors of a Hermitian property matrix. The feature vectors are embedded into a pattern-space using Principal Component Analysis (PCA) and Multidimensional Scaling (MDS) to cluster similar human poses acquired using the Microsoft Kinect device for Xbox 360. The Hermitian property matrix is constructed from the length of the limbs and the angles subtended by each pair of limbs using the three-dimensional skeletal data produced by the Kinect device. The given skeleton is converted to its equivalent line graph to compute the angles between pairs of limbs. The joints locations are used to compute the limb lengths. In Chapter 5, we describe a method to correct the sign of eigenvectors of the proximity matrix for the problem of correspondence matching. The signs of the eigenvectors of a proximity matrix are not unique and play an important role in computing the correspondences between a set of feature points. We use the coefficients of the elementary symmetric polynomials to make the direction of the eigenvectors of the two proximity matrices consistent with each other. Chapter 6 describes a 3D shape descriptor that is robust to changes in pose and topology. The descriptor is based on the D2 shape descriptor developed by Osada et al, which is essentially the frequency distribution of the Euclidian distance between randomly selected points on the surface of the 3D shape. We use the commute-time distance instead of using the Euclidian distance between randomly selected points. A new and completely unsupervised mesh segmentation algorithm is proposed, which is based on the commute time embedding of the mesh and k-means clustering using the embedded mesh vertices.