Feature correspondence with constrained global spatial structures

In this paper, we consider the feature correspondence task as a graph matching problem. Our approach tends to maximize a similarity objective function, which consists of not only the feature vectors but also their corresponding constrained global spatial structures, by a new polynomial-time approximate optimization algorithm. This algorithm allows every node in a smaller graph to potentially be linked with any node in a larger graph, and thus it can handle one-to-one, many-to-one, and no match cases. Especially, our approach does not necessarily require a training set. We test on the ¿hotel¿ and ¿house¿ sequences. Matching a pair of frames takes on average 1.24 and 1.22 seconds respectively using a Matlab implementation without any optimization (over an order of magnitude speedup compared to), and with a 2-frame interval our errors are merely 0.07% and 0.09% respectively. Even going up to a 25-frame gap, errors are only 5.66% and 5.00% respectively.