Transitivity-based removal of correspondence outliers for motion analysis

In this paper we address the problem of removing correspondence outliers in a sequence of images. The input to the system is a set of putative matches which are based upon image-feature similarity. Classical methods for outlier removal, such as RANSAC-based approaches, assume consistency and rigidity in the scene motion between two or three frames in the sequence. Here we propose a novel method for removing correspondence outliers that does not depend on such assumptions. Our method is based on the observation that correspondence is an equivalence relation, and, hence, transitivity must hold between corresponding features in different frames. We impose consistency on the transitivity by representing the matching information as a weighted graph with positive and negative edge-weights. Consistency is then enforced by partitioning the nodes in the graph so as to remove edges corresponding to false-positive correspondences. The clustering algorithm is of spectral nature and can handle graphs whose edge-weights are non-positive. Our method is a general one that can be used for purposes of outlier removal from correspondences between any entities whose putative matches imply equivalence relations. We illustrate the utility of the method for purposes of outlier removal on a real-world image sequence and compare our results with those yield using an alternative. © 2006 IEEE.