A new graph matching method for point-set correspondence using the EM algorithm and Softassign

Abstract

Finding correspondences between two point-sets is a common step in many vision applications (e.g., image matching or shape retrieval). We present a graph matching method to solve the point-set correspondence problem, which is posed as one of mixture modelling. Our mixture model encompasses a model of structural coherence and a model of affine-invariant geometrical errors. Instead of absolute positions, the geometrical positions are represented as relative positions of the points with respect to each other. We derive the Expectation-Maximization algorithm for our mixture model. In this way, the graph matching problem is approximated, in a principled way, as a succession of assignment problems which are solved using Softassign. Unlike other approaches, we use a true continuous underlying correspondence variable. We develop effective mechanisms to detect outliers. This is a useful technique for improving results in the presence of clutter. We evaluate the ability of our method to locate proper matches as well as to recognize object categories in a series of registration and recognition experiments. Our method compares favourably to other graph matching methods as well as to point-set registration methods and outlier rejectors.