Maximal cliques based rigid body motion segmentation with a RGB-D camera

Motion segmentation is a key underlying problem in computer vision for dynamic scenes. Given 3D data from a RGB-D camera, this paper presents a novel method for motion segmentation without explicitly estimating motions. Building up from a recent literature [1] that proposes a similarity measure between two 3D points belonging to a rigid body, we show that identifying rigid motion groups corresponds to a maximal clique enumeration problem of the similarity graph. Using efficient maximal clique enumeration algorithms we show that it is practically feasible to find all the unique candidate motion groups in a deterministic fashion. We investigate the relationship to traditional hypothesis sampling and show that under certain conditions the inliers to a hypothesis form a clique in the similarity graph. Further, we show that identifying true motions from the candidate motions can be cast as a minimum set cover problem (for outlier-free data) or a max k-cover problem (for data with outliers). This allows us to use the greedy algorithm for max k-cover to segment the motion groups. Presented results using synthetic and real RGB-D data show the validity of our approach.