Motion Segmentation

Motion segmentation divides a video into parts that move differently: pixels into regions with coherent motion, or tracked points into groups that each follow one motion. It rests on the grouping factor that the Gestalt psychologists called common fate, the tendency to see things that move together as one object (Shi & Malik, 1998), and it is the classical route to finding objects without knowing their appearance in advance. The problem goes by several names: layered motion estimation, when each region is a layer with its own motion and appearance; multibody or 3D motion segmentation, when tracked feature points are grouped by rigid motion; and moving-object segmentation, when the goal is a mask of everything that moves independently of the camera. It extends image segmentation from single images to video. Its main input is optical flow or point trajectories, and it differs from two neighbours: background subtraction finds change against a model of a static camera’s scene, and video object segmentation follows objects whose masks are usually given in the first frame. Motion segmentation needs neither a static camera nor a given mask.

Problem Definition

Given a video, or the trajectories of points tracked through it, assign every pixel or trajectory to one of several motions, and usually estimate those motions as well. The number of motions may be given, as in the Hopkins 155 benchmark, or must be found.

Tron and Vidal (2007) separate two problems. 2D motion segmentation, studied mostly in the 1990s, splits each frame into regions of coherent image motion (optical flow). A rigid scene filmed by a moving camera can then contain several 2D motions, because depth discontinuities, occlusion and perspective make different parts of the image move differently. 3D motion segmentation groups points by their motion in space, so that each object, and the static background seen by the moving camera, is one group however its image motion varies. Tron and Vidal define the 3D problem as clustering $P$ point trajectories according to the $n$ objects that move rigidly relative to the camera.

Modern moving-object segmentation asks a third question: which pixels belong to objects that move independently of the camera, regardless of how many objects there are or what they are. Tokmakov, Alahari and Schmid (2017) define its output as a per-pixel label saying whether the pixel has undergone independent motion, irrespective of camera motion; Dave, Tokmakov and Ramanan (2019) ask for an instance mask of every moving object, including objects of categories never seen in training.

Input and Output

• Input: two or more frames, optical flow between them, or point trajectories from a tracker, either supplied with a benchmark, as in Hopkins 155, or followed through dense flow until the points are occluded (Keuper et al., 2015, §2).
• Output: a label per pixel or per trajectory, the motion model of each group (an affine or projective transformation, or a subspace), and in layered methods an appearance and opacity (alpha) map per layer (Szeliski, 2022, §9.4).

Variants

• Two-frame dense segmentation and layers. The image is explained by a few parametric motions, each with a support map; Wang and Adelson’s layers add an appearance image and alpha mask per layer, accumulated over many frames (Szeliski, 2022, §9.4).
• Sparse trajectory segmentation under an affine camera. Feature trajectories through all frames are clustered by rigid motion, which under affine projection reduces to clustering subspaces (Tron & Vidal, 2007).
• Long-term trajectory segmentation. Dense trajectories that start and end at different frames are grouped by their long-term motion, giving sparse or densified object masks over a whole shot (Keuper et al., 2015).
• Binary moving-object segmentation. Every pixel is labelled moving or static. DAVIS 2016 annotates one foreground per video, and SegTrackv2 and FBMS are commonly scored the same way by merging all their objects into one foreground (Yang et al., 2021, §4.2).
• Moving-instance segmentation. Each moving object gets its own mask and identity (Dave et al., 2019; Xie et al., 2022).
• Transparent motion. Reflections in glass superimpose two motions at the same pixel; Szeliski (§9.4.2) describes additive layer models for this case.

Challenges

• Flow and segmentation depend on each other. Shi and Malik (1998) list why estimating flow first and then looking for its discontinuities proved difficult: flow is unreliable where texture is weak or one-dimensional, and the smoothness constraints used to fill it in require knowing the segmentation, so as not to smooth across motion boundaries.
• How many motions, and where to start. EM-style layered methods must be initialized with a number of models and their positions; Shi and Malik call initialization the principal weakness of that approach. Spectral methods need a model-selection step to choose the number of clusters (Keuper et al., 2015, §1).
• Dependent and degenerate motions. Two objects that rotate alike but translate differently, or the parts of an articulated body, give motion subspaces that partly coincide, which breaks methods that assume independent motions (Tron & Vidal, 2007, §2.2). Degenerate motions, such as the linear and planar motions in most traffic sequences, give subspaces of lower dimension than general motions do, and methods that assume the general dimension misjudge them (§3.3, §4).
• Camera motion and depth. With a moving camera every pixel moves. A static scene with depth variation produces parallax, so a single global transformation does not explain the background (Tron & Vidal, 2007, §1).
• Tracking errors. Occlusion, disocclusion and motion boundaries corrupt trajectories, and trajectories end when points are occluded. Datasets either remove bad trajectories by hand (Hopkins 155) or provide trajectories with missing entries and outliers for robust methods (Elhamifar & Vidal, 2009, §3.4).
• Moving is not the same as object. Objects stop and start; the van in Keuper et al.’s Figure 1 stands still for the first 30 frames, so its trajectories attach to the background (§1). Distinct objects that move together, such as cars driving one after another at the same speed, can end up in one segment (Keuper et al., 2015, §3.1); Xie et al. (2022) re-annotated DAVIS 2017, merging jointly moving objects, for this reason. Water and other “moving stuff” can move independently without being annotated as an object (Tokmakov et al., 2017, §4.1).

Approaches

Parametric motion fitting and robust estimation

The simplest model gives one region a low-dimensional parametric motion: translation, affine or homography, the models catalogued in the motion models article and estimated globally as described in motion estimation. Segmentation starts when several such models are needed. The usual first step is to find the dominant motion and treat everything that disagrees with it as outliers. Szeliski (2022, §8.1) describes the two standard tools. M-estimators replace the squared residual with a robust penalty and are solved by iteratively reweighted least squares, but with too many outliers they may not reach the global optimum. Random sampling, as in RANSAC or least median of squares, instead fits the model to many small random subsets and keeps the one with the most inliers (or the smallest median residual); Szeliski notes that the inlier threshold is application dependent and often about 1–3 pixels.

Several motions can be found sequentially: fit the dominant motion, remove its inliers, and repeat on the rest. Tron and Vidal (2007, §3.4) evaluate exactly this for trajectories, followed by a final pass that assigns every point to its nearest model. It handles outliers explicitly and copes with partially dependent motions because it fits one motion at a time. But the chance of drawing a sample entirely from one motion falls exponentially with the number of motions, results vary from run to run, and their implementation used a fixed subspace dimension of 4, more points than a degenerate motion needs.

Layered motion

Layers model a scene as a few overlapping regions, each with its own motion and appearance. Wang and Adelson (1994) represented each layer by an intensity map, an alpha map and a parametric velocity map, so that the video is recreated by warping and compositing the layers from back to front (Szeliski, 2022, §9.4, Figure 9.12). Their paper could not be read for this article; Szeliski describes the pipeline as follows. Affine motions are estimated over a collection of non-overlapping patches and clustered with k-means. The method then alternates between assigning pixels to layers and re-estimating each layer’s motion from its pixels, a technique first proposed by Darrell and Pentland (1991). Once each frame has its motions and assignments, the layer images are built by warping and merging the pieces from all frames, with median filtering to make the composites sharp and to infer which layer occludes which. Szeliski shows the result on the flower garden sequence (Figure 9.13).

The idea grew in several directions, all summarized by Szeliski (§9.4). Weiss and Adelson (1996) used a probabilistic mixture model to infer both the number of layers and the pixel assignments, and Weiss (1997) replaced each layer’s affine motion with a smooth per-pixel flow, so that curved surfaces can form one layer. Baker, Szeliski and Anandan (1998) described each layer by a 3D plane plus per-pixel depth offsets (plane plus parallax), initialized with homographies in place of affine motions, and jointly re-optimized colours, opacities, depths and motions to reproduce the video; Torr, Szeliski and Anandan (2001) added Bayesian initialization and selection of the number of layers. Shi and Malik (1998) summarize the shared formulation of that period: with 2D parametric motions (translation, affine or projective), the expectation step of expectation–maximization solves for the layers given the motions, and the maximization step solves for the motions given the layers. Another family alternates between estimating flow and segmenting it into coherent regions, sometimes starting from a segmentation of the colour image (Szeliski, §9.4).

Graph-based grouping

Shi and Malik (1998) avoided the initialization problem by treating segmentation as graph partitioning. They connect each pixel to its neighbours in space and time, describe each pixel by a motion profile, the probability distribution of its image velocity, and weight each edge by the distance between profiles. Normalized cuts then find the most salient partitions of this spatiotemporal graph, and a recursive update carries the segmentation of earlier frames into each new frame for long sequences.

Trajectory clustering and subspace methods

Under an affine camera, which covers orthographic, weak-perspective and paraperspective projection, the image of point $p$ in frame $f$ is $\mathbf{x}_{fp} = A_f \mathbf{X}_p$, with $A_f$ a $2 \times 4$ matrix and $\mathbf{X}_p$ the point in homogeneous coordinates (Tron & Vidal, 2007, §2.1). Stacking the $F$ frames of $P$ trajectories of one rigid object gives a $2F \times P$ matrix that factors into motion and structure:

$$W = \begin{bmatrix} \mathbf{x}_{11} & \cdots & \mathbf{x}_{1P} \\ \vdots & & \vdots \\ \mathbf{x}_{F1} & \cdots & \mathbf{x}_{FP} \end{bmatrix} = \begin{bmatrix} A_1 \\ \vdots \\ A_F \end{bmatrix} \begin{bmatrix} \mathbf{X}_1 & \cdots & \mathbf{X}_P \end{bmatrix},$$

so $\operatorname{rank} W \le 4$: the trajectories of one rigid object lie in a linear subspace of $\mathbb{R}^{2F}$ of dimension 2, 3 or 4. Subtracting each frame’s centroid lowers the bound to 3, the form behind Tomasi and Kanade’s factorization method for a single object, covered in multi-view geometry and structure from motion. Because the last coordinate of every $\mathbf{X}_p$ is 1, Elhamifar and Vidal (2009, §4) point out that the trajectories also lie in an affine subspace of dimension at most 3. With $n$ objects, the columns of $W$ lie in a union of $n$ subspaces, and 3D motion segmentation becomes subspace clustering: find the subspaces and the points that belong to each.

Factorization. Costeira and Kanade (1998) computed a rank-$D$ approximation $W \approx U\Sigma V^\top$ with the singular value decomposition and the shape interaction matrix $Q = VV^\top$. Their paper could not be read; Tron and Vidal (2007, §3.3) describe its key property: when the motions are independent, $Q_{ij} = 0$ whenever points $i$ and $j$ belong to different objects, and the segmentation groups entries of $Q$ accordingly. The property needs independent subspaces, meaning that no two motion subspaces share a direction, and Tron and Vidal report that the procedure is very sensitive to noise. Kanatani’s subspace separation added dimension correction and model selection, and Sugaya and Kanatani’s multi-stage learning (MSL) refined it with three stages of expectation–maximization adapted to degenerate and general motions (Tron & Vidal, §3.3).

Generalized PCA (GPCA). Vidal, Ma and Sastry (2005) fit the union of $n$ subspaces with a polynomial of degree $n$ whose gradient at a point gives a normal vector to the subspace containing it (also read only through Tron and Vidal, §3.1). For motion segmentation the trajectories are first projected to $\mathbb{R}^5$, where each motion subspace of dimension at most 4 lies in a hyperplane $\{\mathbf{w} : \mathbf{b}_i^\top \mathbf{w} = 0\}$. The product $q_n(\mathbf{w}) = \prod_i \mathbf{b}_i^\top \mathbf{w}$ is fitted linearly from the data, and points are clustered by spectral clustering on the similarity $\cos^2$ of the angle between their gradient directions. GPCA is algebraic and fast, and allows subspaces to intersect, but the polynomial has $O(n^4)$ coefficients for $4n$ unknowns, so its least-squares fit degrades as $n$ grows and is sensitive to outliers.

Local subspace affinity (LSA). Yan and Pollefeys fit a local subspace to each point and its nearest neighbours and set the affinity between two points from the principal angles $\theta_m$ between their local subspaces, $S_{ij} = \exp(-\sum_m \sin^2\theta_m)$, followed by spectral clustering (Tron & Vidal, §3.2). Outliers are rarely anyone’s neighbour, which helps, but near the intersection of two subspaces a point’s neighbours can come from the wrong motion.

Sparse subspace clustering (SSC). Elhamifar and Vidal (2009) start from the observation that a point in a union of subspaces can be written as a linear combination of other points from its own subspace, using only as many points as the subspace’s dimension. They look for the sparsest such representation through the convex problem

$$\min_{\mathbf{c}_i} \|\mathbf{c}_i\|_1 \quad \text{subject to} \quad \mathbf{y}_i = Y_{\hat{i}}\, \mathbf{c}_i ,$$

where $Y_{\hat{i}}$ holds all points except $\mathbf{y}_i$. Their Theorem 1 shows that for independent subspaces with points in general position, the solution uses only points from the subspace of $\mathbf{y}_i$. The coefficients define a graph with weights $|C_{ij}| + |C_{ji}|$, and spectral clustering (see clustering) on its Laplacian gives the segmentation. Variants handle affine subspaces with the constraint $\mathbf{c}_i^\top \mathbf{1} = 1$, noise with a Lasso penalty in place of the equality, missing entries by dropping the rows where they are missing, and corrupted entries with an extra sparse error term. For Hopkins 155 they projected the trajectories to $4n$ dimensions with random Gaussian or Bernoulli matrices and kept the four largest coefficients of each point (§4.1). Their journal version (Elhamifar & Vidal, 2013) could not be read for this article.

Perspective cameras. Under perspective projection the trajectories of one motion lie on multilinear varieties rather than subspaces (bilinear for two views, trilinear for three), and Tron and Vidal judged such methods not yet mature enough for a meaningful benchmark in 2007 (§1). The Johns Hopkins group’s project page describes an iterative alternative: given projective depths, rescaled trajectories reduce to the affine case, and given a segmentation, structure from motion recovers the depths, so the algorithm alternates the two.

Long-term trajectory clustering

Brox and Malik (2010) and Ochs, Malik and Brox (2014) based segmentation on the long-term motion of densely tracked points, whose trajectories start and end at different frames, and Ochs et al. introduced the FBMS-59 benchmark (Keuper et al., 2015, §2, §6). Neither paper could be read for this article; Keuper, Andres and Brox (2015), from the same group, describe the pipeline they compare against. Points with some image structure are tracked with large displacement optical flow (Brox and Malik’s 2011 method, cited in optical flow estimation) until they are occluded, detected by comparing forward and backward flow, and new trajectories are started where the sampling becomes too sparse. Two trajectories $A$ and $B$ that share frames are compared by the largest difference of their motion over those frames,

$$d^{\text{motion}}(A, B) = \max_t \frac{\|\partial_t A - \partial_t B\|}{\sigma_t},$$

with $\sigma_t$ the variation of the optical flow. Ochs et al. combine it with the spatial distance into an affinity, cluster with spectral clustering and a model-selection step, and finally merge neighbouring segments whose affine motion subspaces are similar, which reduces oversegmentation (Keuper et al., §4–§5). Keuper et al. note that this distance, which they also use, describes only translational motion, so out-of-plane motion is expected to oversegment objects (§5); Ochs and Brox had also built third-order terms that explain in-plane rotation and scaling (§1.1).

Keuper, Andres and Brox (2015) replaced spectral clustering with a minimum cost multicut on the trajectory graph. Edge costs come from the logit of a cut probability computed from motion, spatial and colour distances, so edges can be repulsive as well as attractive, and the optimal decomposition chooses the number of segments itself, including very small ones that spectral methods, with their preference for balanced partitions, tend to miss. They added edges between trajectories that do not overlap in time when one ends where the other’s extrapolated motion begins, and solved the NP-hard problem with their implementation of the Kernighan–Lin heuristic, in a few seconds on graphs of up to about 6,000 trajectories (§3.2–§4). On the FBMS-59 test set with trajectories sampled every 8 pixels, the F-measure rose from 69.0% for Ochs et al.’s spectral clustering to 75.8% for multicuts on motion alone and 76.5% with the richer graph (Table 1, cut prior 0.5).

Moving objects with a moving camera

With a moving camera, the classical recipe is to estimate and remove the camera’s motion and look for what remains. A single homography or affine transformation removes camera rotation and the motion of a planar background (see motion models for camera-motion compensation in trackers). In our reading of the geometry, scenes with depth leave parallax on static structure, which is why Tron and Vidal frame the problem in terms of 3D rigid motions and why layered methods moved to plane-plus-parallax models. Flow-based object priors offer another route: Papazoglou and Ferrari’s motion-boundary method, described in the video object segmentation article, marks pixels inside closed motion boundaries as likely object pixels. With depth, the 3D motion of every point can be measured directly, the subject of scene flow.

Learned methods in outline

Learned methods read optical flow, appearance or both. Tokmakov, Alahari and Schmid (2017) trained an encoder–decoder (MP-Net) entirely on the synthetic FlyingThings3D videos, 2,700 sequences of objects flying along random trajectories filmed by a randomly moving camera, deriving labels of independent motion from the dataset’s 3D coordinates (§5). Trained there with one decoder unit, the network reached a mean IoU of 46.6% on DAVIS from the angle field of the flow and 12.7% from a single RGB frame (Table 1), evidence that the motion pattern carries the signal. On real video, flow errors and moving water hurt, so they weighted the network’s output by an objectness map built from object proposals and refined it with a fully connected CRF. Evaluated on the 50 DAVIS 2016 videos, the full method reached a mean J of 69.7 against 64.1 for NLC, the best unsupervised method in the DAVIS evaluation (Table 3). They also measured how much flow quality matters: on the FlyingThings3D test set, replacing ground-truth flow with LDOF flow dropped the IoU from 85.9% to 58.7% (§6.2). FlowNet 2.0’s authors made the same point from the other side, scoring a trajectory-based segmentation on FBMS-59 with different flow inputs, as the FlowNet article reports.

Later methods removed the need for labels. Yang, Loquercio, Scaramuzza and Soatto (2019) trained a mask generator adversarially against an inpainter that predicts the flow inside a region from the flow around it: the mask is good when the context tells the inpainter nothing about the region, so the object’s motion is independent of the background’s (CIS). Yang, Lamdouar, Lu, Zisserman and Xie (2021) brought back layers: a network with a slot-attention bottleneck decomposes a flow field into a background layer and a foreground layer with opacity masks and is trained only to reconstruct the flow, with an entropy penalty that pushes the masks towards binary values and a consistency loss across flow computed at different frame gaps. Instance normalization in the encoder and decoder is what they call a poor man’s approach to camera-motion compensation: the mean activation is dominated by the large background, so normalizing it helps separate the background’s motion from the foreground’s. The model uses flow alone, runs at 0.012 seconds per frame excluding flow computation, and assigns all moving objects to one layer, a limitation the authors acknowledge (§3, §5.4). Xie, Xie and Zisserman (2022) extended this to several objects with a depth-ordered layered representation: each transformer query owns one object and predicts its amodal (complete) mask through the whole video, the visible masks are composed by layer order, and training uses synthetic videos made by compositing layers, which transfers to real flow because flow hides most of the appearance gap.

Dave, Tokmakov and Ramanan (2019) took the opposite route, starting from instance segmentation. Their two-stream Mask R-CNN combines an appearance stream trained on COCO with a motion stream trained on FlyingThings3D flow, fine-tuned on DAVIS 2016 and part of their YTVOS-Moving set, and links per-frame masks with a simple tracker. Its advantage was largest on objects outside COCO’s categories: on YTVOS-Moving videos with novel objects, a version never trained on YouTube-VOS reached an F-measure of 67.6 against 40.6 for Mask R-CNN and 31.9 for Keuper et al.’s multicuts (Table 9).

Example: clustering trajectories by affine motion

The script renders a 15-frame, $256 \times 256$ video with three motions from scikit-image’s bundled textures: a brick background that drifts and rotates by 0.3° per frame, as a moving camera would make it; a disk of grass (radius 40 pixels) that rotates by 2° per frame while translating; and a square of gravel (side 71 pixels) in front of it that grows by 1.2% per frame while translating. Harris corners are detected in the first frame and tracked by chaining scikit-image’s iterative Lucas–Kanade flow between consecutive frames, so the trajectories carry the noise and the failures of a real tracker. The ground-truth label of a point is the layer on top at its first-frame position, and its true trajectory follows from the known motions.

Each motion is a 2D affine transformation per frame, $\mathbf{x}_f = A_f [x_0, y_0, 1]^\top$, so the trajectories of one layer lie in a 3-dimensional linear subspace of $\mathbb{R}^{30}$, the planar special case of the rank bound above. Four methods are compared:

• Reference, Tron and Vidal’s oracle: fit each subspace to the points of its true group by least squares and reassign every point to the nearest subspace. It needs the answer and shows how well the motion model fits the data.
• Sequential RANSAC: fit a subspace to 3 random trajectories, count the trajectories within an RMS distance $\tau$ per frame, keep the best of 500 samples, remove its inliers and repeat until three subspaces are found, then assign every point to its nearest subspace (Tron & Vidal, §3.4, who used subspaces of dimension 4 rather than the 3 of these planar motions). Seeds 0–9 are run and the mean and range printed. Szeliski’s “often around 1–3 pixels” and Tron and Vidal’s hand-tuning leave the threshold open, so three values are shown.
• Translational affinity with spectral clustering: the pairwise distance is the largest velocity difference over the frames, as in the long-term trajectory methods (without their normalization $\sigma_t$ and spatial term), turned into an affinity $\exp(-d^2 / 2s^2)$ for three scales $s$.
• Sparse subspace clustering, in its noisy linear form: each trajectory is regressed on all others with scikit-learn’s Lasso, and spectral clustering is applied to $|C| + |C|^\top$, for two penalty weights; the share of that matrix’s total weight on pairs from the same true motion is printed as well.

Every method is scored by the misclassification rate of Hopkins 155, after matching clusters to motions one to one with the Hungarian algorithm, on all trajectories and on a cleaned set that keeps only trajectories whose tracking error stays within 2 pixels in every frame, the analogue of Hopkins 155’s manual removal of obviously wrong trajectories. The script runs in about 20 seconds with NumPy 2.3.5, SciPy 1.16.3, scikit-image 0.25.2 and scikit-learn 1.7.2, and gives identical output on repeated runs.

import numpy as np
from scipy.optimize import linear_sum_assignment
from skimage import data, transform, feature
from skimage.registration import optical_flow_ilk
from scipy.ndimage import map_coordinates
from sklearn.cluster import SpectralClustering
from sklearn.linear_model import Lasso

H = W = 256
F = 15                                   # frames


def affine(angle_deg=0.0, scale=1.0, centre=(0, 0), shift=(0, 0)):
    """2x3 matrix: rotate/scale about centre, then shift. Coordinates are (x, y) = (column, row)."""
    a = np.deg2rad(angle_deg)
    R = scale * np.array([[np.cos(a), -np.sin(a)], [np.sin(a), np.cos(a)]])
    c = np.asarray(centre, float)
    return np.hstack([R, (c - R @ c + np.asarray(shift, float))[:, None]])


def motion(k, f):
    if k == 0:   # background seen by a moving camera: slow rotation and drift
        return affine(0.3 * f, 1.0, (128, 128), (0.8 * f, 0.4 * f))
    if k == 1:   # layer A, a grass disk: rotates 2 degrees per frame and translates
        return affine(2.0 * f, 1.0, (80, 90), (1.5 * f, -0.5 * f))
    return affine(0.0, 1.012 ** f, (175, 165), (-1.0 * f, 1.0 * f))   # layer B, a gravel square: grows


def warp(img, M):
    """Render img moved by the 2x3 forward map M (inverse mapping, bilinear)."""
    T = transform.AffineTransform(matrix=np.vstack([M, [0, 0, 1]]))
    return transform.warp(img, T.inverse, order=1, mode="edge")


yy, xx = np.mgrid[0:H, 0:W]
masks = [np.ones((H, W)), ((xx - 80) ** 2 + (yy - 90) ** 2 <= 40 ** 2) * 1.0,
         ((np.abs(xx - 175) <= 35) & (np.abs(yy - 165) <= 35)) * 1.0]
textures = [transform.resize(t(), (H, W), anti_aliasing=True) for t in (data.brick, data.grass, data.gravel)]

frames = []
for f in range(F):                       # composite back to front: background, A, B
    img = np.zeros((H, W))
    for k in range(3):
        m = warp(masks[k], motion(k, f)) > 0.5
        img[m] = warp(textures[k], motion(k, f))[m]
    frames.append(img)

# Features: Harris corners in frame 0; ground-truth label = layer on top at that pixel.
pts = feature.corner_peaks(feature.corner_harris(frames[0]), min_distance=4, threshold_rel=0.005, num_peaks=450)
label0 = np.zeros((H, W), int); label0[masks[1] > 0] = 1; label0[masks[2] > 0] = 2
gt = label0[pts[:, 0], pts[:, 1]]
N = len(pts)

# Track by chaining iterative Lucas-Kanade flow between consecutive frames.
xy = [pts[:, ::-1].astype(float)]
for f in range(F - 1):
    v, u = optical_flow_ilk(frames[f], frames[f + 1], radius=7)
    r, c = xy[-1][:, 1], xy[-1][:, 0]
    du = map_coordinates(u, [r, c], order=1, mode="nearest")
    dv = map_coordinates(v, [r, c], order=1, mode="nearest")
    xy.append(xy[-1] + np.column_stack([du, dv]))
Wm = np.stack(xy, 0).transpose(0, 2, 1).reshape(2 * F, N)   # 2F x N matrix, rows x1, y1, x2, y2, ...

X0 = np.column_stack([pts[:, ::-1], np.ones(N)]).astype(float)
true = np.stack([np.concatenate([motion(k, f) @ x for f in range(F)]) for x, k in zip(X0, gt)], 1)
err = np.linalg.norm((Wm - true).reshape(F, 2, N), axis=1).max(0)
print(f"{N} trajectories over {F} frames, per motion {np.bincount(gt)}; "
      f"{np.sum(err > 2)} gross outliers (tracking error > 2 px), median max error {np.median(err):.2f} px")


def misclassification(pred, gt):
    """Fraction of points misassigned under the best one-to-one matching of clusters to motions."""
    C = np.zeros((max(pred.max(), gt.max()) + 1,) * 2)
    np.add.at(C, (pred, gt), 1)
    r, c = linear_sum_assignment(-C)
    return 1 - C[r, c].sum() / len(gt)


# Affine motion model over all frames: trajectory = A_f [x0, y0, 1]^T, so each motion's trajectories
# span a 3-dimensional linear subspace of R^{2F}. Fit = basis from 3 trajectories or least squares.
def subspace(cols):
    U = np.linalg.svd(cols, full_matrices=False)[0]
    return U[:, :3]


def residual(B, Y):                      # RMS distance per frame from trajectories to a motion subspace
    return np.linalg.norm(Y - B @ (B.T @ Y), axis=0) / np.sqrt(F)


def assign(bases, Y):
    return np.argmin(np.stack([residual(B, Y) for B in bases]), 0)


def seq_ransac(Y, tau, rng, n=3, iters=500):
    remaining, bases = np.arange(Y.shape[1]), []
    for _ in range(n):
        best = None
        for _ in range(iters):
            s = rng.choice(remaining, 3, replace=False)
            inl = remaining[residual(subspace(Y[:, s]), Y[:, remaining]) < tau]
            if best is None or len(inl) > len(best):
                best = inl
        bases.append(subspace(Y[:, best]))
        remaining = np.setdiff1d(remaining, best)
        if len(remaining) < 3:
            break
    return assign(bases, Y)


def translational_spectral(Y, c):
    """Pairwise distance = max over frames of the velocity difference (Brox-Malik / Ochs style)."""
    n = Y.shape[1]
    vel = np.diff(Y.reshape(F, 2, n), axis=0)
    D = np.linalg.norm(vel[:, :, :, None] - vel[:, :, None, :], axis=1).max(0)
    A = np.exp(-D ** 2 / (2 * (c * np.median(D)) ** 2))
    return SpectralClustering(3, affinity="precomputed", random_state=0).fit_predict(A)


ssc_share = []                           # share of |C| + |C|^T on pairs from the same true motion


def ssc(Y, alpha, g):
    """Each trajectory as a sparse (Lasso) combination of the others, then spectral clustering."""
    n = Y.shape[1]
    Y = Y / W
    Cm = np.zeros((n, n))
    for i in range(n):
        o = np.delete(np.arange(n), i)
        Cm[o, i] = Lasso(alpha=alpha, fit_intercept=False, max_iter=10000).fit(Y[:, o], Y[:, i]).coef_
    A = np.abs(Cm) + np.abs(Cm).T
    ssc_share.append(A[g[:, None] == g[None, :]].sum() / A.sum())
    return SpectralClustering(3, affinity="precomputed", random_state=0).fit_predict(A)


clean = err <= 2                         # Hopkins-style set: obviously wrong tracks removed
sets = [(Wm, gt), (Wm[:, clean], gt[clean])]
print(f"\nMisclassification rate          all {N}      clean {clean.sum()}")


def row(name, method):
    print(f"{name:26s}" + "".join(f"{100 * misclassification(method(Y, g), g):10.1f}%" for Y, g in sets))


row("Reference (oracle fit)", lambda Y, g: assign([subspace(Y[:, g == k]) for k in range(3)], Y))
for tau in (1.0, 2.0, 4.0):
    cells = []
    for Y, g in sets:
        e = [misclassification(seq_ransac(Y, tau, np.random.default_rng(s)), g) for s in range(10)]
        cells.append(f"{100 * np.mean(e):4.1f}% ({100 * min(e):.1f}-{100 * max(e):.1f})")
    print(f"{'RANSAC, tau=%.0f px' % tau:26s}" + "   ".join(cells))
for c in (0.25, 0.5, 1.0):
    row(f"Translational, s={c:.2f}xmed", lambda Y, g: translational_spectral(Y, c))
for alpha in (0.001, 0.01):
    ssc_share.clear()
    row(f"SSC, alpha={alpha}", lambda Y, g: ssc(Y, alpha, g))
    print(f"{'  |C| share, own motion':26s}" + " ".join(f"{m:10.2f}" for m in ssc_share))

# Why SSC struggles here: principal angles between the true motion subspaces.
from scipy.linalg import subspace_angles
B = [subspace(true[:, gt == k]) for k in range(3)]
for i, j in [(0, 1), (0, 2), (1, 2)]:
    print(f"angles between motions {i} and {j}:", ", ".join(f"{a:.2f}" for a in np.rad2deg(subspace_angles(B[i], B[j]))), "degrees")

215 trajectories over 15 frames, per motion [128  44  43]; 48 gross outliers (tracking error > 2 px), median max error 0.45 px

Misclassification rate          all 215      clean 167
Reference (oracle fit)           8.4%       0.0%
RANSAC, tau=1 px          11.2% (9.8-16.3)    3.1% (0.6-16.2)
RANSAC, tau=2 px          30.6% (25.6-34.4)   19.8% (19.8-19.8)
RANSAC, tau=4 px          40.5% (40.5-40.5)   36.5% (36.5-36.5)
Translational, s=0.25xmed       24.2%       9.0%
Translational, s=0.50xmed       23.7%      10.2%
Translational, s=1.00xmed       41.4%       7.2%
SSC, alpha=0.001                54.4%      52.7%
  |C| share, own motion         0.71       0.77
SSC, alpha=0.01                 51.6%      50.3%
  |C| share, own motion         0.64       0.68
angles between motions 0 and 1: 28.59, 0.77, 0.09 degrees
angles between motions 0 and 2: 30.92, 0.10, 0.01 degrees
angles between motions 1 and 2: 59.17, 0.65, 0.20 degrees

The tracker is the first source of error. Half of the trajectories stay within 0.45 pixels of the truth in every frame, but 48 of 215, about 22%, drift by more than 2 pixels. The oracle misclassifies 8.4% of all trajectories but none once the drifted ones are removed, so the affine model fits every well-tracked point. SSC’s full formulation has an explicit term for such corrupted entries.

The three motion subspaces nearly coincide: between every pair, two of the three principal angles are below 1°. In our reasoning, this follows from the scene’s design. Every motion has a constant drift per frame and only a small rotation or scaling, so to first order each trajectory is a straight line traversed at constant speed, $\mathbf{x}_f \approx \mathbf{x}_0 + f\,\mathbf{v}$. All such trajectories lie in one 4-dimensional space (two coordinates for $\mathbf{x}_0$, two for $\mathbf{v}$), and two 3-dimensional subspaces that both lie close to the same 4-dimensional space must nearly share two directions; only the curvature that rotation and growth add over 15 frames separates them. The scene is therefore a hard case for subspace methods by construction, and by the same reasoning longer sequences or changing velocities would separate the subspaces further (not run here). Within this scene the RANSAC threshold matters a great deal. With $\tau = 1$ pixel, sequential RANSAC comes close to the oracle on the cleaned set, although the worst of the ten seeds did much worse. With $\tau = 2$ or 4 pixels, the first model’s inlier band is wide enough to take in points of other motions, and on the cleaned set every seed gives the same error.

The translational affinity does worse than RANSAC with a tight threshold on the cleaned set (7.2–10.2%) and much worse on all trajectories, where its result also depends on the scale $s$. Rotation and growth make velocities vary within a layer: by our arithmetic, at 2° per frame points on opposite sides of the grass disk move about 2.8 pixels per frame apart, comparable to the differences between the three motions. This is the weakness of translational pairwise terms that Keuper et al. point out for long-term trajectory methods.

SSC fails with both penalties and on both sets; on all trajectories it does worse than putting every point into one cluster, which would misclassify the 87 points of the two layers, 40.5% (our arithmetic from the printed counts). Its guarantee (Theorem 1) assumes independent subspaces, whose dimensions add up when they are combined (to 9 here); three subspaces lying close to one 4-dimensional space are far from that, although no two of them coincide exactly. Most of each point’s coefficient weight still falls on its own motion, against about 0.44 if the weight were spread in proportion to the motions’ sizes (our arithmetic), but enough crosses between motions that spectral clustering on $|C| + |C|^\top$ does not recover the groups. This illustrates the conditions SSC needs, not its performance on Hopkins 155, where Elhamifar and Vidal reported the lowest errors of their comparison (see below). Their published method also differs from this sketch: it uses the affine constraint, a random projection, and only the four largest coefficients per point.

The first run of the script printed only the column for all trajectories, with SSC’s coefficient share, and no principal angles. After it showed 48 gross outliers and SSC failing, we added the cleaned column; diagnostic runs, not shown, then computed the principal angles between the true motion subspaces, and the printout of those angles was added to explain the SSC result. The print layout was then tidied, and that rewrite dropped the coefficient-share line, which fact-checking restored for both sets. The numbers in the first column did not change.

Datasets and Benchmarks

Hopkins 155 (Tron & Vidal, 2007) was built because earlier methods had each been tested on a handful of different sequences. Its authors collected 50 videos with two or three motions and split each three-motion video into three two-motion subsets as well, giving 155 sequences: 120 with two motions and 35 with three (§4). There are three categories: 104 indoor checkerboard sequences filmed with a handheld camera, the pattern ensuring many tracked points; 38 outdoor traffic sequences filmed by a moving handheld camera, most of them with degenerate linear or planar motions; and 13 articulated or non-rigid sequences, such as arms, people walking and head motion. Sequences have 39 to 556 points and 15 to 100 frames, with averages of 266 points and 30 frames for two motions and 398 points and 29 frames for three (Table 1). Except for sequences taken from earlier datasets, trajectories were tracked with an OpenCV-based tool, and an operator removed obviously wrong trajectories and assigned every point to its motion by hand, so the data contain noise but no missing entries or outliers (Elhamifar & Vidal, 2009, §4.1). The background typically has about twice as many points as a moving object. As of November 2026 the dataset page also offers 16 further sequences with missing data, or missing data and outliers, and more than three motions (Hopkins 155+16); SSC’s authors tested on twelve sequences with missing or corrupted entries taken from earlier work, for 167 sequences in all.

The benchmark paper compared GPCA, LSA, MSL and sequential RANSAC with the oracle Reference, running RANSAC 1,000 times per sequence and hand-tuning thresholds on a couple of sequences (§5). Average misclassification rates over all sequences, from its Tables 2 and 4 and from Tables 1 and 2 of the SSC paper, which repeats the earlier numbers and adds ALC (agglomerative lossy compression) and SSC:

Method	2 motions (120)	3 motions (35)
Reference (oracle)	2.03%	5.08%
GPCA	4.59%	28.66%
LSA, projection to $4n$	3.45%	9.73%
MSL	4.14%	8.23%
RANSAC	5.56%	22.94%
ALC	2.40%	6.69%
SSC, Bernoulli projection	0.75%	3.55%
SSC, Normal projection	0.82%	2.45%

Several patterns stand out. On average every practical method fell short of the oracle in 2007, Tron and Vidal putting the gap for the best ones at about 1.5% to 5%, and they concluded that the affine camera model itself was adequate for nearly all sequences. Three motions were much harder for GPCA and RANSAC, as their analyses predict. The ranking depended on the category: LSA was best on checkerboards; for traffic and articulated scenes the paper’s text names GPCA, which its tables bear out for two motions, while with three motions MSL had the lowest errors there (Tables 2 and 4). Computation differed by orders of magnitude: on two motions, GPCA averaged 324 ms per sequence and RANSAC 175 ms, LSA about 7 s, and MSL 11 hours, and MSL averaged more than two days on the three-motion checkerboard sequences (Tables 3 and 5). SSC’s paper reports errors below every earlier method in every category; its text quotes 0.75% for two motions and 2.45% for three, which come from the two different projections in its table. The Johns Hopkins results page lists the Normal-projection values for SSC alongside further methods. The SSC paper reports a mean of 1.24% over all 155 sequences (Table 3). SSC’s errors are below those of the 2007 oracle, which in our reading shows that the oracle, a least-squares fit per group followed by reassignment, is a reference rather than a lower bound.

BMS-26 and FBMS-59. Brox and Malik’s Berkeley Motion Segmentation dataset has 26 videos with ground-truth object masks for a selection of frames; Tokmakov et al. note that ten of them were later excluded in one evaluation because their annotations did not correspond to independently moving objects (§5). The Freiburg–Berkeley Motion Segmentation dataset, FBMS-59, extends it to 59 sequences split into 29 for training and 30 for testing (Keuper et al., 2015, §6). Yang et al. (2021) count 720 annotated frames, every 20th frame, at widely varying resolutions, with several moving objects in many sequences, some of which stand still for a while. Dave et al. (2019) note that prior work evaluated on the whole dataset, which leaves no FBMS sequence free for training. FBMS’s official site was not consulted for this article; the descriptions here come from the papers that use it, and the video object segmentation article gives the count of 139 objects that YouTube-VOS’s authors report for it.

DAVIS-Moving and YTVOS-Moving. Dave et al. (2019) built two benchmarks on which every moving object is labelled and static objects are not. DAVIS-Moving keeps 22 of the 30 DAVIS 2017 validation videos, leaving out those with labelled static objects or unlabelled moving ones; YTVOS-Moving selects YouTube-VOS videos the same way and holds out 100 of them for evaluation. Xie et al. (2022) built DAVIS2017-motion by re-annotating DAVIS 2017 so that objects moving together form one group.

Binary benchmarks. Self-supervised methods are usually compared on DAVIS 2016 (see video object segmentation), SegTrackv2 (14 sequences, 976 annotated frames) and FBMS-59, and on MoCA, 141 videos of camouflaged animals annotated with boxes every fifth frame, of which Yang et al. keep 88 that show locomotion (Yang et al., 2021, §4.1).

Reported results on the binary benchmarks, mean J (IoU) from Yang et al. (2021, Table 2) and Xie et al. (2022, Table 2), for methods that use no manual annotation in training:

Method	Input	DAVIS 2016	SegTrackv2	FBMS-59
CIS (Yang et al., 2019), no post-processing	RGB and flow	59.2	45.6	36.8
CIS, with post-processing	RGB and flow	71.5	62.0	63.5
Motion grouping (Yang et al., 2021)	flow	68.3	58.6	53.1
OCLR (Xie et al., 2022), trained on synthetic layers	flow	72.1	67.6	65.4
OCLR with test-time adaptation on RGB	RGB and flow	80.9	72.3	69.8

CIS’s post-processing averages over several flow steps and crops and adds temporal smoothing and CRFs, which Yang et al. put at more than 10 seconds in total (§5.2, Table 2). MP-Net’s 69.7 is not in the table: it was averaged over all 50 DAVIS 2016 videos, whereas Yang et al. average over the test set (§4.2); the two papers’ different values for NLC (64.1 and 55.1) reflect the same difference, in our reading.

Evaluation Metrics

Misclassification rate. Hopkins 155 scores each sequence by the fraction of points assigned to the wrong motion, $\#\text{misclassified points} / \#\text{points}$, and reports its average and median over sequences, separately for two and three motions and per category (Tron & Vidal, 2007, eq. 11). Clusters must first be matched to motions; the example above uses the best one-to-one matching.

FBMS measures. The FBMS evaluation, as Keuper et al. and Dave et al. describe it, matches predicted regions to ground-truth objects one to one so as to maximize the summed F-measure (with the Hungarian algorithm) and reports average precision, recall and F-measure over the matched pairs, the number of objects segmented with an F-measure above 75%, and the density of the labelled points, since sparse methods label only their trajectories. Oversegmentation does not raise recall under this matching (Keuper et al., §6). Dave et al. (2019, §4) found that the official measure ignores predicted segments that match no object and leaves unlabelled pixels out of the evaluation, so false positives cost nothing. Their proposed variant counts unmatched predictions as false positives and includes all pixels. The difference is large. Their appearance-only stream, which segments static objects as well, scored F 84.3 on the FBMS-59 test set under the official measure and 70.3 under theirs, while their joint motion–appearance model scored 78.2 and 76.3; Keuper et al.’s multicuts scored 77.9 and 65.0 (Tables 5 and 6). Keuper et al. also report the variation of information between segmentation and ground truth, split into a part that grows with oversegmentation and a part that grows with undersegmentation (§6).

Region similarity J and contour accuracy F. Binary moving-object segmentation is scored like DAVIS: the mean intersection over union of masks (J), and for multi-object sets also the boundary measure F; the video object segmentation article defines both. On MoCA, where only boxes exist, the mask’s bounding box is scored by the detection success rate averaged over IoU thresholds from 0.5 to 0.9 (Yang et al., 2021, §4.2).

Applications

• Video representation and editing. Layers give a compact description of a video and model the pixels near motion boundaries accurately, which suits image-based rendering and object-level video editing (Szeliski, 2022, §9.4); Szeliski adds that segmenting videos into coherent objects supports editing such as removing and inserting objects (§9.4.3; see image editing).
• Preprocessing for other tasks. Tron and Vidal (2007) name tracking, action recognition and surveillance among the applications that motivated motion segmentation; separating independently moving points from the background also matters for structure from motion and visual odometry, where moving objects violate the static-scene assumption.
• Open-world perception. Dave et al. (2019) motivate moving-object segmentation by robot autonomy: a self-driving car must detect obstacles and debris of categories it was never trained on (see autonomous driving perception).
• Camouflage. When an animal matches its background, motion may be the only cue; on MoCA, Yang et al.’s flow-only model outperformed the self-supervised CIS and also COSNet, a supervised method that relies on appearance alone (Yang et al., 2021, §5.3), and Xie et al. found that adapting their model with appearance features hurt on MoCA while helping elsewhere.

Open Problems

• Many objects, occlusion and objects that stop. Flow-only models assign all moving objects to one layer or lose objects that stop moving; Xie et al.’s amodal layers address occlusion, but on DAVIS2017-motion their flow-only model reached J&F 55.1 against 78.7 for a DINO-based propagation method that is given the first-frame masks (Xie et al., 2022, Table 3).
• What counts as an object. Motion alone cannot split objects that move together or reject moving water; methods add objectness or appearance, and Yang et al. (2021) suggest that existing video segmentation models may already lean too heavily on appearance.
• Evaluation. The FBMS measure does not penalize false positives, the binary benchmarks merge all objects into one foreground, and the multi-object sets are small and built by selecting videos (Dave et al., 2019).
• Beyond affine cameras and rigid motion. Hopkins 155 assumes affine projection, rigid motions and complete trajectories; perspective effects, non-rigid motion and long trajectories with missing entries remain harder, and the 2007 comparison called for fast methods that work with three or more motions.