SSSC-AM: A unified framework for video co-segmentation by structured sparse subspace clustering with appearance and motion features

Junlin Yao, Frank Nielsen

TL;DR

This paper introduces SSSC-AM, a unified framework for video co-segmentation that combines appearance and motion features. It improves upon existing methods by incorporating an affine subspace constraint for motion and an extra-dimensional signature to handle missing motion trajectories, leading to more robust and accurate object segmentation in videos.

What Problem Does This Paper Address?

Segmenting common objects across multiple videos (video co-segmentation) is a challenging task in computer vision. Existing methods often treat this as a two-step process: first, creating an "affinity matrix" that describes how similar different parts of the videos are, and then using spectral clustering to group similar parts. However, this separation can lead to suboptimal results because the affinity matrix and the final segmentation are not optimized together. Furthermore, motion features in videos can be unreliable due to occlusions or objects leaving the frame, making accurate segmentation difficult. This paper aims to address these limitations by proposing a unified framework that jointly optimizes segmentation and feature representation, while also improving the handling of noisy or incomplete motion data.

Methods

The core of the proposed method, SSSC-AM, is built upon the Structured Sparse Subspace Clustering (S³C) framework. Here's a breakdown of the key techniques:

  • Unified Optimization Framework: Instead of a two-step approach, SSSC-AM integrates the learning of an affinity matrix and the segmentation process into a single optimization problem. This allows for more consistent and accurate results.
  • Appearance and Motion Features: The framework leverages both visual appearance (color histograms) and motion information from video sequences.
  • Temporal Superpixels (TSPs): To reduce computational complexity and maintain salient features, videos are first over-segmented into spatio-temporal units called TSPs. Features are then extracted at this level.
  • Enhanced Motion Features: A novel approach is introduced to improve the robustness of motion features. When trajectories are missing (due to occlusion or objects entering/leaving the frame), an extra-dimensional signature is added to the motion data. This signature encodes the status of the trajectory (e.g., original, missing due to new points, missing due to dead points), helping the clustering algorithm to better distinguish and segment motions.
  • Affine Subspace Constraint: Recognizing that rigid object motion often lies in affine subspaces (rather than strictly linear ones), the S³C algorithm is reformulated to include an affine subspace constraint. This makes the framework more suitable for segmenting motions that can be described by affine transformations, particularly in 3D.
  • Alternating Direction Method of Multipliers (ADMM): The complex optimization problem is efficiently solved using the ADMM algorithm, which is well-suited for distributed and parallel computation.

Datasets

The primary dataset used for evaluation is the Multi-Object Video Co-Segmentation (MOVICS) dataset. This dataset consists of four sets of real videos, each featuring different animal object combinations (e.g., chicken-turtle, giraffe-elephant, zebra-lion, tiger) and presenting challenges like similar appearances, camouflage, lighting variations, and motion blur. The paper also mentions using the Hopkins 155 motion segmentation dataset to specifically evaluate the impact of the affine subspace constraint on motion segmentation.

Key Insights and Ideas

  • The Power of Unification: The paper strongly advocates for a unified optimization framework where segmentation and feature representation are learned jointly. This is a key insight that leads to improved performance over traditional two-step methods.
  • Motion Signatures for Robustness: The idea of adding an "extra-dimensional signature" to motion trajectories to explicitly encode missing data is a clever way to make motion features more informative and less prone to failure when dealing with real-world video challenges.
  • Affine Subspaces for Realistic Motion: Incorporating the affine subspace constraint acknowledges a more realistic model for rigid motion in videos, leading to better segmentation of dynamic scenes.
  • Appearance and Motion Synergy: The experiments highlight that combining both appearance and motion features is crucial for robust segmentation, with each feature type compensating for the weaknesses of the other.

Key Results

  • Superior Performance on MOVICS: SSSC-AM achieved an overall performance of 49.25% on the MOVICS dataset, outperforming two state-of-the-art baselines: VCS (48.75%) and VOCS (46.56%).
  • Top Performance in Specific Cases: The framework produced better results than baselines on the chicken-turtle and tiger video sets, particularly excelling on the tiger video where distinguishing the animal from its surroundings is difficult.
  • Improved Motion Segmentation: On the Hopkins 155 dataset, SSSC-AM (with the affine subspace constraint) showed significantly lower motion segmentation errors compared to S³C (without the constraint), demonstrating the benefit of the affine constraint.
  • Computational Efficiency: The use of Temporal SuperPixels (TSPs) for preprocessing significantly reduces computational costs. SSSC-AM's clustering routine was faster than VCS for three out of four video sets.
  • Robustness to Noise: The framework demonstrated effectiveness even when subjected to significant additive noise (Gaussian and salt-and-pepper), indicating its robustness.

Limitations and Future Work

  • Missing Trajectories Challenge: While the extra-dimensional signature helps, the paper acknowledges that for videos with a very high number of missing trajectories (e.g., giraffe-elephant, zebra-lion), the method can still struggle because the motion information becomes too sparse.
  • Articulated Motion: The current framework assumes rigid-body motion. Handling objects with articulated motion (like human limbs) is identified as a significant future direction. This would require encoding motion information differently to capture the complex, non-rigid movements.
  • Distributed Optimization: The authors suggest extending the work by developing a parallel and distributed optimization algorithm based on ADMM to further improve efficiency for large-scale video co-segmentation problems.

Summary updated

Abstract

Video co-segmentation typically refers to the task to jointly segment common objects existing in a given group of videos. In practice, high-dimensional data such as videos are often conceptually thought of being drawn from a union of subspaces corresponding to multiple categories. Therefore, segmenting data into respective subspaces, known as subspace clustering, has widespread applications in computer vision, including co-segmentation. State-of-the-art methods via subspace clustering seek to solve the problem in two steps: learning an affinity matrix, followed by applying spectral clustering to the affinity matrix. However, it is insufficient to obtain an optimal solution since it does not take into account the interdependence of the affinity matrix and the segmentation. In this paper, we present a new unified video co-segmentation framework inspired by Structured Sparse Subspace Clustering (S <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> C), which yields more consistent segmentation results. In order to improve the detectability of motion features with missing trajectories, we add an extra signature to motion trajectories. Moreover, we reformulate the S <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> C algorithm by adding the affine subspace constraint in order to make it more suitable to segment rigid motions lying in affine subspaces of dimension at most 3. Experiments on MOViCS dataset demonstrate the effectiveness of our approaches and robustness with heavy noise.
BibTeX
@inproceedings{yao2016sssc,
  author = {Junlin Yao and Frank Nielsen},
  title = {{SSSC-AM: A unified framework for video co-segmentation by structured sparse subspace clustering with appearance and motion features}},
  booktitle = {ICIP},
  year = {2016},
  url = {https://openreview.net/forum?id=-9J5SPEqmwC},
}
Figure