Combined central and subspace clustering for computer vision applications

Le Lu, René Vidal

In the world of unsupervised learning, practitioners usually have to pick a side: should data points be grouped because they are physically close to each other (Central Clustering), or because they align along the same low-dimensional structure like a line or a plane (Subspace Clustering)?

In their 2006 paper, Le Lu and René Vidal argue that for many real-world computer vision tasks, choosing one approach over the other is a recipe for failure. Instead, they propose a unified framework that simultaneously performs both.

The Core Concept

This paper introduces a hybrid clustering algorithm that simultaneously minimizes the distance of data points to cluster centers and their distance to underlying subspaces. By combining these two metrics into a single objective function, the authors solve common "failure modes" where traditional methods struggle—such as when data points sit at the intersection of two planes, or when clusters from different planes overlap in space.

What Problem Does This Paper Address?

High-dimensional visual data—like a sequence of video frames or images of a face under different lighting—rarely fills up the entire high-dimensional space. Instead, it usually lives on lower-dimensional structures called subspaces (imagine a 2D sheet of paper floating in a 3D room).

Standard clustering tools have specific blind spots when dealing with this kind of data:

  1. Central Clustering (e.g., K-means): Fails when two different subspaces pass through the same region of space. It sees two distinct groups as one "blob" simply because they are spatially close.
  2. Subspace Clustering (e.g., GPCA): Fails when data points are near the intersection of two subspaces. The algorithm cannot decide which "plane" the point belongs to because the distance to both is nearly zero.
Comparison of clustering methods on a 3D toy problem.

The authors tackle the challenge of clustering data that is distributed around $m$ centers within each of $n$ subspaces, effectively resolving the ambiguities that trip up isolated clustering methods.

Methods

The core contribution is a new objective function that combines the "within-class variance" of K-means with the "subspace distance" of K-subspaces.

The Objective Function

The algorithm seeks to minimize a cost function where each point's error is the sum of:

  • The squared distance to its assigned subspace (hyperplane).
  • The squared distance to its assigned cluster center within that subspace.

The Algorithm

The authors use a coordinate descent approach, which iterates through three main steps until the assignments stop changing:

  1. Membership Assignment: Each point is assigned to the (subspace, center) pair that minimizes the combined distance.
  2. Center Update: The new cluster center is calculated as the mean of the points in that cluster, projected onto the current subspace.
  3. Subspace Update: The orientation of the subspace (its normal vector) is updated by solving an eigenvector problem based on the points assigned to it.

This approach is a natural generalization: if you have only one subspace, it becomes K-means; if you have only one center per subspace, it becomes K-subspaces.

Key Insights and Ideas

  • Resolving Ambiguity: By adding a spatial "center" constraint, the algorithm can correctly assign points at the intersection of two planes. Even if the distance to both planes is zero, the point will be pulled toward the closer cluster center.
  • Piecewise Linear Manifolds: The authors show that video data often forms complex, curved "manifolds." Their method effectively approximates these curves using a collection of small, flat subspace patches, providing a more accurate structural representation than K-means' "spherical blobs."
  • Geometric Projection: A key "aha" moment in the derivation is that the optimal cluster center isn't just the average of the points; it's the average projected onto the plane. This ensures the model remains physically consistent with the subspace assumption.

Key Results

The authors validated their approach using synthetic data, the Yale Face Database B, and video sequences for shot segmentation.

  • Superior Accuracy: On synthetic data with noise, the combined method consistently outperformed K-means, GPCA, and Mixture of Probabilistic PCA (MPPCA) in both clustering error and the accuracy of the estimated plane directions.
Clustering and normal estimation errors under varying noise ratios.
  • Face Clustering: The method successfully separated different individuals even when their respective illumination subspaces intersected—a scenario where subspace-only methods like GPCA failed.
  • Video Segmentation: In complex video sequences, K-means incorrectly split single shots into multiple clusters based on spatial proximity. The combined method correctly identified shots by respecting the underlying manifold structure of the video.

Limitations and Future Work

  • Model Selection: The algorithm requires the user to specify the number of subspaces ($n$) and the number of centers per subspace ($m$) in advance. While the authors suggest using separate model selection tools sequentially, a unified way to pick these numbers remains an open challenge.
  • Hyperplane Assumption: Much of the detailed derivation assumes "co-dimension one" subspaces (hyperplanes). While the paper provides a remark on extending this to any dimension, the implementation complexity increases for more general cases.
  • Future Directions: The authors propose extending this framework to recognize complex curved manifolds across different videos, such as identifying which movie a specific frame belongs to based on its underlying structural geometry.

Summary updated

Abstract

Central and subspace clustering methods are at the core of many segmentation problems in computer vision. However, both methods fail to give the correct segmentation in many practical scenarios, e.g., when data points are close to the intersection of two subspaces or when two cluster centers in different subspaces are spatially close. In this paper, we address these challenges by considering the problem of clustering a set of points lying in a union of subspaces and distributed around multiple cluster centers inside each subspace. We propose a generalization of Kmeans and Ksubspaces that clusters the data by minimizing a cost function that combines both central and subspace distances. Experiments on synthetic data compare our algorithm favorably against four other clustering methods. We also test our algorithm on computer vision problems such as face clustering with varying illumination and video shot segmentation of dynamic scenes.
BibTeX
@inproceedings{lu2006combined,
  author = {Le Lu and René Vidal},
  title = {{Combined central and subspace clustering for computer vision applications}},
  booktitle = {International Conference on Machine Learning},
  year = {2006},
  doi = {10.1145/1143844.1143919},
}
Figure