Spectral approximation to point set similarity metric

In a variety of problems, objects are represented as a collection of feature points f_k and their spatial positions p_k. In some cases, feature points doesn't carry enough discriminating information to identify objects so as to raise the question of point set verification, i.e., matching two point sets to identify whether they are match or not. Point set verification problem involves two challenges. The first challenge is to identify a one-to-one mapping between two point sets and the second is to measure the similarity between the two aligned point sets. The first challenge is a well-known one-to-one mapping problem in computer vision with a combinatorial nature and computationally expensive. However, we are able to avoid the computation of one-to-one mapping by directly giving a matching similarity score. The second challenge is attacked with lots of solutions, which shares two disadvantages, i.e., sensitive to both outliners and affine transform. These two challenges are solved simultaneously by our eigenvalue approximation solution. In this work, the point sets are modeled as affinity matrix and the distances between affinity matrices of two point sets are lower bounded by eigenvalue distance. This affinity representation is invariant to scale, translation and rotation and insensitive to outliners and affine transforms. Experiments on both synthetic data and real data shows that this method outperforms both statistics based and geometry based methods.