Fast rigid motion segmentation via incrementally-complex local models

The problem of rigid motion segmentation of trajectory data under orthography has been long solved for non-degenerate motions in the absence of noise. But because real trajectory data often incorporates noise, outliers, mo-tion degeneracies and motion dependencies, recently pro-posed motion segmentation methods resort to non-trivial representations to achieve state of the art segmentation ac-curacies, at the expense of a large computational cost. This paper proposes a method that dramatically reduces this cost (by two or three orders of magnitude) with minimal accu-racy loss (from 98.8 % achieved by the state of the art, to 96.2 % achieved by our method on the standard Hopkins 155 dataset). Computational efficiency comes from the use of a simple but powerful representation of motion that explicitly incorporates mechanisms to deal with noise, outliers and motion degeneracies. Subsets of motion models with the best balance between prediction accuracy and model com-plexity are chosen from a pool of candidates, which are then used for segmentation. 1. Rigid Motion Segmentation Rigid motion segmentation (MS) consists on separating regions, features, or trajectories from a video sequence into spatio-temporally coherent subsets that correspond to in-dependent, rigidly-moving objects in the scene (Figure 1.b or 1.f). The problem currently receives renewed attention, partly because of the extensive amount of video sources and applications that benefit from MS to perform higher level computer vision tasks, but also because the state of the art is reaching functional maturity. Motion Segmentation methods are widely diverse, but most capture only a small subset of constraints or alge-braic properties from those that govern the image formation process of moving objects and their corresponding trajec-tories, such as the rank limit theorem [9, 10], the linear in-dependence constraint (between trajectories from indepen-dent motions) [2, 13], the epipolar constraint [7], and the reduced rank property [11, 15, 13]. Model-selection based (a) Original video frames (b) Class-labeled trajectories (c) Model support region (d) Model inliers and control points (e) Model residuals (f) Segmentation resul