Feature grouping by 'relocalisation' of eigenvectors of the proximity matrix

Abstract

We describe a widely applicable method of grouping -or clustering -image features (such as points, lines, corners, flow vectors and the like).It takes as input a "proximity matrix" H -a square, symmetric matrix of dimension N (where N is the number of features).The element i,j of H is an initial estimate of the "proximity" between the ith and yth features.As output it delivers another square symmetric matrix S whose i-)th element is near to, or much less than unity according as features i and j are to be assigned to the same or different clusters.To find S we first determine the eigenvalues and eigenvectors ofH and re-express the features as linear combinations of a limited number of these eigenvectors -those with the largest eigenvalues.The cosines between the resulting vectors are the elements ofS.We demonstrate the application of the method to a range of examples and briefly discuss various theoretical and computational issues.