Semantic Single Video Segmentation with Robust Graph Representation

Handong Zhao, Yun Fu

Abstract

Traditional video segmentation often struggles to distinguish between multiple semantic classes within a single video, typically defaulting to binary foreground-background separation. This paper introduces a novel framework for semantic segmentation of multiple object classes in a single video sequence. The approach combines motion-aware object proposals with a robust low-rank graph representation to filter out noisy data (outliers) and group foreground objects into distinct, meaningful categories. Experimental results on the MOViCS and ObMiC datasets demonstrate significant improvements over existing image cosegmentation and video segmentation baselines.

Introduction

Video segmentation is a fundamental task in computer vision, yet most existing methods are limited to binary segmentation or require large collections of videos to learn semantic patterns. Performing semantic segmentation on a single video is particularly challenging because the algorithm lacks external references for class definitions. Furthermore, graph-based models commonly used in this domain are sensitive to "outliers"—superpixels that bridge object boundaries or background noise.

Methodology

The proposed framework utilizes a four-step pipeline to achieve robust semantic labeling without external training data.

Overview of the proposed four-step pipeline for semantic video segmentation.
  1. Object-like Region Generation: Candidate object regions (proposals) are generated for every frame.
  2. Motion-Aware Scoring: Proposals are evaluated using a novel motion metric based on forward and backward optical flow consistency. Regions moving consistently across frames receive higher scores, while erratic motions are penalized.
  3. Robust Graph Construction via Low-Rank Representation (LRR): To handle noisy proposals, the authors employ LRR with an $l_{2,1}$-norm regularizer. This assumes that "clean" data (true object regions) resides on a low-dimensional subspace, allowing the model to isolate and remove sparse outliers before clustering.
  4. Spectral Clustering & Completion: Spectral clustering is applied to the cleaned graph to group proposals into semantic classes. A final post-processing step ensures temporal continuity by filling gaps in frames where objects might have been missed.

Experimental Evaluation

The method was evaluated on two challenging multi-class datasets: MOViCS (e.g., "lion and zebra") and ObMiC (e.g., humans and dogs).

Key Results

The proposed method consistently outperformed state-of-the-art Image Cosegmentation (ICS) and Video Segmentation (VS) baselines.

Qualitative comparison of the proposed method against Image Cosegmentation (ICS) and Video Segmentation (VS) baselines.
  • Intersection-over-Union (IoU): On the MOViCS dataset, the method achieved an average IoU of 0.610, compared to 0.433 for the VS baseline. Overall performance improved by an average of 24.17% across both datasets.
  • F-measure: The method reached an average F-measure of 0.695, significantly higher than ICS (0.610) and VS (0.497).
  • Ablation Study: Comparing the full model against a version without outlier detection confirmed that low-rank outlier removal is critical for maintaining accuracy in noisy environments.

Discussion and Insights

The core strength of this approach lies in its ability to exploit the "intrinsic structure" of foreground motion. By treating outlier detection as a low-rank optimization problem, the system can uncover true relationships between object parts even when superpixels are corrupted. This proves that spatial-temporal information within a single video is often sufficient to distinguish classes like a giraffe from an elephant, provided the model is robust to noise.

However, limitations remain. Performance can degrade when objects are very small or exhibit significant internal appearance variation (e.g., a person wearing multi-colored clothing). Additionally, the reliance on motion means static objects are harder to identify as distinct semantic units.

Conclusion

This research demonstrates a robust path forward for single-video semantic segmentation. By integrating motion-aware proposals with low-rank graph cleaning, the framework successfully bridges the gap between simple binary segmentation and complex multi-video learning, offering a powerful tool for analyzing diverse scenes in isolation.

Summary updated

Abstract

Graph-based video segmentation has demonstrated its influential impact from recent works. However, most of the existing approaches fail to make a semantic segmentation of the foreground objects, i.e. all the segmented objects are treated as one class. In this paper, we propose an approach to semantically segment the multi-class foreground objects from a single video sequence. To achieve this, we firstly generate a set of proposals for each frame and score them based on motion and appearance features. With these scores, the similarities between each proposal are measured. To tackle the vulnerability of the graph-based model, low-rank representation with l2,1-norm regularizer outlier detection is proposed to discover the intrinsic structure among proposals. With the "clean" graph representation, objects of different classes are more likely to be grouped into separated clusters. Two open public datasets MOViCS and ObMiC are used for evaluation under both intersection-over-union and F-measure metrics. The superior results compared with the state-of-the-arts demonstrate the effectiveness of the proposed method.
BibTeX
@inproceedings{zhao2015semantic,
  author = {Handong Zhao and Yun Fu},
  title = {{Semantic Single Video Segmentation with Robust Graph Representation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure