We address the problem of simultaneous nonlinear
dimensionality reduction and clustering of data points drawn from
multiple linear and nonlinear manifolds. We focus our investigation on the LLE algorithm, which compute a low-dimensional embedding from the
eigenvectors of a matrix M that depends on local properties of the
data. We show that if the data lives in a disconnected union of m connected manifolds, of which n &le m are subspaces
of dimensions di
, i=1...n, then the null space of M contains
m eigenvectors that give the segmentation of the data and
eigenvectors that give the embedding
coordinates for the subspaces. Therefore, in the case of nonlinear manifolds
(n=0) the segmentation of the data can be obtained directly by looking at
the null space of M. In the case of subspaces (n=m), contrary
to intuition the situation is more difficult, because the nullspace of M contains both segmentation and embedding eigenvectors. We resolve this difficulty by showing that the variance
of the segmentation eigenvectors is always smaller than that of the
embedding eigenvectors. This leads to a new algorithm for clustering
both linear and nonlinear manifolds by solving a generalized eigenvalue problem.
Application to Motion Segmentation
We apply our algorithm to the problem of segmenting multiple rigid-body motions in video. Given N point trajectories in F frames of a video sequence, the goal is to segment these trajectories according to m rigid motions.
Depending on the camera projection models, these point trajectories lies on different manifolds. For affine cameras, there are m subspaces of dimensions 2, 3, or 4. For perspective cameras, there are m multilinear manifolds of dimension 3.
several sequences demonstrate that our algorithm is comparable to
state-of-the-art computer vision algorithms. Please refer to this page
for more details on motion segmentation.
Results for sequences with two and three motions
|Two groups||Two groups||Three groups||Three groups |
|Algorithm ||LLMC 5 ||LLMC 4n ||LLMC 5 ||LLMC 4n|
|Average ||3.62% ||4.44% ||8.85% ||11.02% |
|Median ||0.00% ||0.24% ||3.19% ||6.81%|
Legend for the algorithms' naming scheme
|LLMC 5||Local Linear Manifold Clustering (projection to a space of dimension 5)|
|LLMC 4n||Local Linear Manifold Clustering (projection to a space of dimension 4 times the number of motions)|
Work supported by startup funds from Johns Hopkins University, and by grants NSF CAREER IIS-04-47739, NSF EHS-05-09101 and ONR N00014-05-1083.