Robust motion segmentation with unknown correspondences

Motion segmentation can be addressed as a subspace clustering problem, assuming that the trajectories of interest points are known. However, establishing point correspondences is in itself a challenging task. Most existing approaches tackle the correspondence estimation and motion segmentation problems separately. In this paper, we introduce an approach to performing motion segmentation without any prior knowledge of point correspondences. We formulate this problem in terms of Partial Permutation Matrices (PPMs) and aim to match feature descriptors while simultaneously encouraging point trajectories to satisfy subspace constraints. This lets us handle outliers in both point locations and feature appearance. The resulting optimization problem can be solved via the Alternating Direction Method of Multipliers (ADMM), where each subproblem has an efficient solution. Our experimental evaluation on synthetic and real sequences clearly evidences the benefits of our formulation over the traditional sequential approach that first estimates correspondences and then performs motion segmentation.