23.5. Motion Segmentation

The theory of structure from motion and motion segmentation has evolved over a set of papers [14, 24, 39, 53, 66, 73, 74]. In this section, we review the essential ideas from this series of work.

A typical image sequence (from a single camera shot) may contain multiple objects moving independently of each other. In the simplest model, we can assume that images in a sequence are views of a single moving object observed by a stationary camera or a stationary object observed by a moving camera. Only rigid motions are considered. In either case, the object is moving with respect to the camera.

The structure from motion problem focuses on recovering the (3D) shape and motion information of the moving object. In the general case, there are multiple objects moving independently. Thus, we also need to perform a motion segmentation such that motions of different objects can be separated and (either after or simultaneously) shape and motion of each object can be inferred.

This problem is typically solved in two stages. In the first stage, a frame to frame correspondence problem is solved which identifies a set of feature points whose coordinates can be tracked over the sequence as the point moves from one position to other in the sequence. We obtain a set of trajectories for these points over the frames in the video. If there is a single moving object or the scene is static and the observer is moving then all the feature points will belong to the same object. Otherwise, we need to cluster these feature points to different objects moving in different directions. In the second stage, these trajectories are analyzed to group the feature points into separate objects and recover the shape and motion for individual objects. In this section we assume that the feature trajectories have been obtained by an appropriate method. Our focus is to identify the moving objects and obtain the shape and motion information for each object from the trajectories.

23.5.1. Modeling Structure from Motion for Single Object

We start with the simple model of a static camera and a moving object. All feature point trajectories belong to the moving object. Our objective is to demonstrate that the subspace spanned by feature trajectories of a single moving object is a low dimensional subspace.

Let the image sequence consist of $F$ frames denoted by $1\le f\le F$. Let us assume that $S$ feature points of the moving object have been tracked over this image sequence. Let $(u_{fs},v_{fs})$ be the image coordinates of the $s$-th point in $f$-th frame. We form the feature trajectory vector for the $s$-th point by stacking its coordinates for the $F$ frames vertically as

$${\mathbf{y}}_s={\left[\begin{array}{ccccccc}{u}_{1s}& v_{1s}& u_{2s}& v_{2s}& \dots & u_{Fs}& v_{Fs}\end{array}\right]}^T.$$

Putting together the feature trajectory vectors of $S$ points in a single feature trajectory matrix, we obtain

$$\mathbf{Y}=\left[\begin{array}{cccc}{\mathbf{y}}_1& {\mathbf{y}}_2& \dots & {\mathbf{y}}_S\end{array}\right].$$

This is the data matrix under consideration from which the shape and motion of the object need to be inferred.

We need two coordinate systems. We use the camera coordinate system as the world coordinate system with the $Z$-axis along the optical axis. The coordinates of different points in the object are changing from frame to frame in the world coordinate system as the object is moving. We also establish a coordinate system within the object with origin at the centroid of the feature points such that the coordinates of individual points do not change from frame to frame in the object coordinate system. The (rigid) motion of the object is then modeled by the translation (of the centroid) and rotation of its coordinate system with respect to the world coordinate system. Let $(a_s,b_s,c_s)$ be the coordinate of the $s$-th point in the object coordinate system. Then, the matrix

$$\begin{array}{r}\left[\begin{array}{cccc}{a}_1& a_2& \dots & a_S\\ b_1& b_2& \dots & b_S\\ c_1& c_2& \dots & c_S\end{array}\right]\end{array}$$

represents the shape of the object (w.r.t. its centroid).

Let us choose an orthonormal basis in the object coordinate system. Let ${\mathbf{d}}_f$ be the position of the centroid and $({\mathbf{i}}_f,{\mathbf{j}}_f,{\mathbf{k}}_f)$ be the (orthonormal) basis vectors of the object coordinate system in the $f$-th frame. Then, the position of the $s$-th point in the world coordinate system in $f$-th frame is given by

$${\mathbf{h}}_{fs}={\mathbf{d}}_f+a_s{\mathbf{i}}_f+b_s{\mathbf{j}}_f+c_s{\mathbf{k}}_f.$$

Assuming orthographic projection and letting ${\mathbf{h}}_{fs}=(u_{fs},v_{fs},w_{fs})$, the image coordinates are obtained by chopping of the third component $w_{fs}$. We define the rotation matrix for $f$-th frame as

$$\begin{array}{r}{\mathbf{R}}_f\triangleq \left[\begin{array}{ccc}{\mathbf{i}}_f& {\mathbf{j}}_f& {\mathbf{k}}_f\end{array}\right]=\left[\begin{array}{c}{\underset{―}{\mathbf{i}}}_f\\ {\underset{―}{\mathbf{j}}}_f\\ {\underset{―}{\mathbf{k}}}_f\end{array}\right]\end{array}$$

where ${\underset{―}{\mathbf{i}}}_f$, ${\underset{―}{\mathbf{j}}}_f$, ${\underset{―}{\mathbf{k}}}_f$ are the row vectors of ${\mathbf{R}}_f$. Let ${\mathbf{x}}_s=(a_s,b_s,c_s,1)$ be the homogeneous coordinates of the $s$-th point in object coordinate system. We can write the homogeneous coordinates in camera coordinate system as

$$\begin{array}{r}\left[\begin{array}{c}{\mathbf{h}}_{fs}\\ 1\end{array}\right]=\left[\begin{array}{cc}{\mathbf{R}}_f& {\mathbf{d}}_f\\ {\mathbf{0}}_{1\times 3}& 1\end{array}\right]{\mathbf{x}}_s.\end{array}$$

If we write ${\mathbf{d}}_f=(d_{fi},d_{fj},d_{fk})$, then, the data matrix $\mathbf{Y}$ can be factorized as

$$\begin{array}{r}\mathbf{Y}=\left[\begin{array}{ccc}{u}_{11}& \dots & u_{1S}\\ v_{11}& \dots & v_{1S}\\ ⋮& \dots & ⋮\\ ⋮& \dots & ⋮\\ u_{F1}& \dots & u_{FS}\\ v_{F1}& \dots & v_{FS}\end{array}\right]=\left[\begin{array}{cc}{\underset{―}{\mathbf{i}}}_1& d_{1i}\\ {\underset{―}{\mathbf{j}}}_1& d_{1j}\\ ⋮& ⋮\\ ⋮& ⋮\\ {\underset{―}{\mathbf{i}}}_F& d_{Fi}\\ {\underset{―}{\mathbf{j}}}_F& d_{Fj}\end{array}\right]\left[\begin{array}{ccc}{\mathbf{x}}_1& \dots & {\mathbf{x}}_S\end{array}\right].\end{array}$$

We rewrite this as

$$\mathbf{Y}=\mathbb{M}\mathbb{S}$$

where $\mathbb{M}$ represents the motion information of the object and $\mathbb{S}$ represents the shape information of the object. This factorization is known as the Tomasi-Kanade factorization of shape and motion information of a moving object. Note that $\mathbb{M}\in {\mathbb{R}}^{2F\times 4}$ and $\mathbb{S}\in {\mathbb{R}}^{4\times S}$. Thus the rank of $\mathbf{Y}$ is at most 4. Thus the feature trajectories of the rigid motion of an object span an up to 4-dimensional subspace of the trajectory space ${\mathbb{R}}^{2F}$.

23.5.2. Solving the Structure From Motion Problem

We digress a bit to understand how to perform the factorization of $\mathbf{Y}$ into $\mathbb{M}$ and $\mathbb{S}$. Using SVD, $\mathbf{Y}$ can be decomposed as

$$\mathbf{Y}=\mathbf{U}\mathrm{\Sigma }{\mathbf{V}}^T.$$

Since $\mathbf{Y}$ is at most rank $4$, we keep only the first 4 singular values as

$$\mathrm{\Sigma }=\text{diag}({\sigma }_1,{\sigma }_2,{\sigma }_3,{\sigma }_4).$$

Matrices $\mathbf{U}\in {\mathbb{R}}^{2F\times 4}$ and $\mathbf{V}\in {\mathbb{R}}^{S\times 4}$ are the left and right singular matrices respectively.

There is no unique factorization of $\mathbf{Y}$ in general. One simple factorization can be obtained by defining:

$$\hat{\mathbb{M}}=\mathbf{U}{\mathrm{\Sigma }}^{\frac{1}{2}},\hat{\mathbb{S}}={\mathrm{\Sigma }}^{\frac{1}{2}}{\mathbf{V}}^T.$$

But for any $4\times 4$ invertible matrix $\mathbf{A}$,

$$\mathbb{M}=\hat{\mathbb{M}}\mathbf{A},\mathbb{S}={\mathbf{A}}^{-1}\hat{\mathbb{S}}$$

is also a possible solution since $\mathbb{M}\mathbb{S}=\hat{\mathbb{M}}\hat{\mathbb{S}}=\mathbf{Y}$. Remember that $\mathbb{M}$ is not an arbitrary matrix but represents the rigid motion of an object. There is considerable structure inside the motion matrix. These structural constraints can be used to compute an appropriate $\mathbf{A}$ and thus obtain $\mathbb{M}$ from $\hat{\mathbb{M}}$. To proceed further, let us break $\mathbf{A}$ into two parts

$$\mathbf{A}=\left[\begin{array}{cc}{\mathbf{A}}_R& {\mathbf{a}}_t\end{array}\right]$$

where ${\mathbf{A}}_R\in {\mathbb{R}}^{4\times 3}$ is the rotational component and ${\mathbf{a}}_t\in {\mathbb{R}}^4$ is related to translation. We can now write:

$$\mathbb{M}=\left[\begin{array}{cc}\hat{\mathbb{M}}{\mathbf{A}}_R& \hat{\mathbb{M}}{\mathbf{a}}_t\end{array}\right]$$

Rotational constraints

Recall that ${\mathbf{R}}_f$ is a rotation matrix hence its rows are unit norm and orthogonal to each other. Thus every row of $\hat{\mathbb{M}}{\mathbf{A}}_R$ is unit norm and every pair of rows (for a given frame) is orthogonal. This yields following constraints.

$$\begin{array}{rl}& {\hat{\mathbf{m}}}_{2f-1}{\mathbf{A}}_R{\mathbf{A}}_R^T{\hat{\mathbf{m}}}_{2f-1}^T=1\\ & {\hat{\mathbf{m}}}_{2f}{\mathbf{A}}_R{\mathbf{A}}_R^T{\hat{\mathbf{m}}}_{2f}^T=1\\ & {\hat{\mathbf{m}}}_{2f-1}{\mathbf{A}}_R{\mathbf{A}}_R^T{\hat{\mathbf{m}}}_{2f}^T=\mathbf{0}\end{array}$$

where ${\hat{\mathbf{m}}}_k$ are rows of matrix $\hat{\mathbb{M}}$ for $1\le f\le F$. This over-constrained system can be solved for the entries of ${\mathbf{A}}_R$ using least squares techniques.

Translational constraints

Recall that the image of a centroid of a set of points under an isometry (rigid motion) is the centroid of the images of the points under the same isometry. The homogeneous coordinates of the centroid in the object coordinate system are $(0,0,0,1)$. The coordinates of the centroid in image are

$$(\frac{1}{S}\sum _s{u}_{fs},\frac{1}{S}\sum _s{v}_{fs}).$$

Putting back, we obtain

$$\begin{array}{r}\frac{1}{S}\left[\begin{array}{c}\sum _s{u}_{1s}\\ \sum _s{v}_{1s}\\ ⋮\\ \sum _s{u}_{Fs}\\ \sum _s{v}_{Fs}\end{array}\right]=\left[\begin{array}{cc}\hat{\mathbb{M}}{\mathbf{A}}_R& \hat{\mathbb{M}}{\mathbf{a}}_t\end{array}\right]\left[\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right]=\hat{\mathbb{M}}{\mathbf{a}}_t.\end{array}$$

A least squares solution for ${\mathbf{a}}_t$ is straight-forward.

23.5.3. Modeling Motion for Multiple Objects

The generalization of modeling of motion of one object to multiple objects is straight-forward. Let there be $K$ objects in the scene moving independently 1. Let $S_1,S_2,\dots ,S_K$ feature points be tracked for objects $1,2,\dots ,K$ respectively for $F$ frames with $S=\sum _k{S}_k$. Let these feature trajectories be put in a data matrix $\mathbf{Y}\in {\mathbb{R}}^{2F\times S}$. In general, we don’t know which feature point belongs to which object and how many feature points are there for each object. There is at least one feature point for each object (otherwise the object isn’t being tracked at all). We could permute the columns of $\mathbf{Y}$ via an (unknown) permutation $\mathrm{\Gamma }$ so that the feature points of each object are placed contiguously giving us

$${\mathbf{Y}}^{\ast }=\mathbf{Y}\mathrm{\Gamma }=\left[\begin{array}{cccc}{\mathbf{Y}}_1& {\mathbf{Y}}_2& \dots & {\mathbf{Y}}_K\end{array}\right].$$

Clearly, each submatrix ${\mathbf{Y}}_k$ ($1\le k\le K$) which consists of feature trajectories of one object spans an (up to) 4 dimensional subspace. Now, the problem of motion segmentation is essentially separating $\mathbf{Y}$ into ${\mathbf{Y}}_k$ which reduces to a standard subspace clustering problem.

Let us dig a bit deeper to see how the motion shape factorization identity changes for the multi-object formulation. Each data submatrix ${\mathbf{Y}}_k$ can be factorized as

$${\mathbf{Y}}_k={\mathbf{U}}_k{\mathrm{\Sigma }}_k{\mathbf{V}}_k^T={\mathbb{M}}_k{\mathbb{S}}_k={\hat{\mathbb{M}}}_k{\mathbf{A}}_k{\mathbf{A}}_k^{-1}{\hat{\mathbb{S}}}_k.$$

${\mathbf{Y}}^{\ast }$ now has the canonical factorization:

$$\begin{array}{r}{\mathbf{Y}}^{\ast }=\left[\begin{array}{ccc}{\mathbb{M}}_1& \dots & {\mathbb{M}}_K\end{array}\right]\left[\begin{array}{ccc}{\mathbb{S}}_1& \dots & 0\\ ⋮& \ddots & ⋮\\ 0& \dots & {\mathbb{S}}_K\end{array}\right].\end{array}$$

If we further denote :

$$\begin{array}{r}\mathbb{M}=\left[\begin{array}{ccc}{\mathbb{M}}_1& \dots & {\mathbb{M}}_K\end{array}\right]\\ \hat{\mathbb{M}}=\left[\begin{array}{ccc}{\hat{\mathbb{M}}}_1& \dots & {\hat{\mathbb{M}}}_K\end{array}\right]\\ \mathbb{S}=\left[\begin{array}{ccc}{\mathbb{S}}_1& \dots & 0\\ ⋮& \ddots & ⋮\\ 0& \dots & {\mathbb{S}}_K\end{array}\right]\\ \hat{\mathbb{S}}=\left[\begin{array}{ccc}{\hat{\mathbb{S}}}_1& \dots & 0\\ ⋮& \ddots & ⋮\\ 0& \dots & {\hat{\mathbb{S}}}_K\end{array}\right]\\ A=\left[\begin{array}{ccc}{A}_1& \dots & 0\\ ⋮& \ddots & ⋮\\ 0& \dots & A_K\end{array}\right]\\ U=\left[\begin{array}{ccc}{U}_1& \dots & U_K\end{array}\right]\\ \mathrm{\Sigma }=\left[\begin{array}{ccc}{\mathrm{\Sigma }}_1& \dots & 0\\ ⋮& \ddots & ⋮\\ 0& \dots & {\mathrm{\Sigma }}_K\end{array}\right]\\ V=\left[\begin{array}{ccc}{V}_1& \dots & 0\\ ⋮& \ddots & ⋮\\ 0& \dots & V_K\end{array}\right],\end{array}$$

then we obtain a factorization similar to the single object case given by

$$\begin{array}{r}{Y}^{\ast }=\mathbb{M}\mathbb{S}=\hat{\mathbb{M}}A{A}^{-1}\hat{\mathbb{S}}\\ \mathbb{S}=A^{-1}\hat{\mathbb{S}}=A^{-1}{\mathrm{\Sigma }}^{\frac{1}{2}}{V}^T\\ \mathbb{M}=\hat{\mathbb{M}}A=U{\mathrm{\Sigma }}^{\frac{1}{2}}A.\end{array}$$

Thus, when the segmentation of $Y$ in terms of the unknown permutation $\mathrm{\Gamma }$ has been obtained, (sorted) data matrix $Y^{\ast }$ can be factorized into shape and motion components as appropriate.

23.5.4. Limitations

Our discussion so far has established that feature trajectories for each moving object span a 4-dimensional space. There are a number of reasons why this is only approximately valid: perspective distortion of camera, tracking errors, and pixel quantization. Thus, a subspace clustering algorithm should allow for the presence of noise or corruption of data in real life applications.

---

1

Our realization of an object is a set of feature points undergoing same rotation and translation over a sequence of images. The notion of locality, color, connectivity etc. plays no role in this definition. It is possible that two visually distinct objects are undergoing same rotation and translation within a given image sequence. For the purposes of inferring an object from its motion, these two visually distinct object are treated as one.