Intersecting Manifolds: Detection, Segmentation, and Labeling

Shay Deutsch, Gérard G. MedioniIJCAI 2015

Introduction

In many real-world data scenarios—such as motion segmentation in video or activity classification—data points lie on low-dimensional "manifolds" (surfaces) embedded in high-dimensional space. A significant challenge arises when these manifolds intersect. Existing methods like Sparse Subspace Clustering (SSC) or Spectral Clustering on Multiple Manifolds (SMMC) typically struggle at these junctions. Specifically, when the angle between the tangent spaces of two manifolds is small (less than 45 degrees), these algorithms often "leak" labels across the intersection, leading to poor segmentation. This research addresses the problem by explicitly delineating and resolving these intersection areas rather than ignoring them.

The Proposed Framework

The authors propose a three-stage pipeline to "untangle" intersecting manifolds by leveraging local geometry and global connectivity:

  1. Intersection Delineation: The algorithm first identifies points near an intersection using Tensor Voting (TV). This technique estimates local geometry by having points "vote" for the structures they belong to. Points at intersections receive conflicting votes, resulting in a high "ball component" (an eigenvalue, $\lambda_N$, indicating a lack of a single dominant orientation). These points are temporarily removed to isolate smooth manifold pieces.
  2. Global Clustering of Smooth Parts: With the confusing intersection points removed, the remaining data consists of disjoint smooth segments. The authors build a Tensor Voting Graph (TVG) and apply standard Spectral Clustering to label these clean segments.
  3. Ambiguity Resolution: This core novelty involves iteratively re-incorporating the intersection points. For each unlabeled point near a junction, the algorithm estimates the local tangent space relative to each known manifold and assigns the point to the one that results in the minimum "tangent space variation" (the smoothest fit).
Overview of the proposed three-stage pipeline for manifold clustering and intersection resolution.

Experimental Results

The framework was evaluated on a mix of synthetic "stress tests" and real-world benchmarks, including high-dimensional embeddings (up to 50D), CMU Motion Capture data, and the 155 Motion Segmentation benchmark.

A key synthetic test involved two circles intersecting at a sharp 18° angle. While competing methods like SMMC achieved only 59.09% accuracy at the junction, the proposed method reached 99.22%. The method also demonstrated significant resilience to outliers; in tests with heavy noise (2000 outliers added to 2000 inliers), it maintained over 90% accuracy, whereas competitors dropped to near-random levels.

The 'Two Circles' synthetic test case. The 3D plot illustrates the detection of intersection points via high eigenvalue peaks.

On real-world data, such as the CMU Motion Capture dataset, the method achieved 96.01% accuracy, significantly outperforming SMMC (87.06%). These results confirm that the geometric approach scales well to high-dimensional spaces and complex human activity transitions.

Key Insights and Future Work

The core insight of this work is that intersections are informative rather than purely disruptive. By isolating them first, the algorithm prevents them from "polluting" the global manifold structure. The "Ambiguity Resolution" step relies on the physical intuition that manifolds are smooth; if a point could belong to multiple structures, the one requiring the least "bending" of the tangent space is likely correct.

While the method is robust against outliers, the authors acknowledge that it can struggle with significant "inlier noise" directly within the intersection area, which can obscure the sharp eigenvalue transitions used for detection. Future work includes automating parameter selection and applying the framework to molecular structure analysis in biology.

Summary updated

BibTeX
@inproceedings{deutsch2015intersecting,
  author = {Shay Deutsch and Gérard G. Medioni},
  title = {{Intersecting Manifolds: Detection, Segmentation, and Labeling}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure