Graph-Based Hierarchical Video Cosegmentation

Franciele Rodrigues, Pedro Leal, Yukiko Kenmochi, Jean Cousty, Laurent Najman, Silvio Jamil Ferzoli Guimarães, Zenilton Kleber Gonçalves do Patrocínio Jr.ICIAP 2017 · OpenReview

Abstract

The goal of video cosegmentation is to jointly extract common foreground regions and objects from a set of videos. In this paper, we present an approach for video cosegmentation that uses graph-based hierarchical clustering as its basic component. The video cosegmentation problem is transformed into a graph-based clustering problem where clusters represent sets of similar supervoxels across the analyzed videos. Our graph-based Hierarchical Video Cosegmentation method (HVC) is divided into two main parts: (i) supervoxel generation and (ii) supervoxel correlation. The former explores intra-video similarities, while the latter seeks to determine relationships between supervoxels belonging to the same or distinct videos. Experimental results on two well-known datasets show that HVC is highly competitive, outperforming existing methods in accuracy on one dataset and ranking second on the other, while requiring less than 50% of the computational time of any other approach.

Introduction

Video segmentation—the process of partitioning a video into meaningful regions—is a fundamental challenge in computer vision. Video cosegmentation extends this by aiming to jointly segment the same foreground objects across a set of different videos. The core challenge is ambiguity: while a single video might have low contrast between an object and its background, the presence of the same object across multiple videos with varying backgrounds provides a "weakly supervised" hint for foreground identification. Existing methods often suffer from high computational costs, reliance on expensive features like Bag-of-Words, or complex parameter tuning to find the right segmentation scale.

Methodology: The HVC Framework

The proposed Hierarchical Video Cosegmentation (HVC) framework treats cosegmentation as a hierarchical clustering problem. The process is divided into two primary phases:

1. Supervoxel Generation (Intra-video)

Each video is represented as a 3D graph of voxels. HVC employs a hierarchical clustering method to group these voxels into supervoxels. This approach adheres to the principles of causality and location, ensuring that as the hierarchy moves toward coarser segments, object boundaries remain consistent and do not "drift."

2. Supervoxel Correlation (Inter-video)

Once supervoxels are generated for all videos, they are integrated into a single global supervoxel graph. The algorithm identifies similarities across different videos using relatively simple features: color gradients (in Lab color space) and an "objectness measure." This measure generates a heatmap indicating the likelihood of a region containing an object versus background texture.

Overview of the HVC pipeline, illustrating the transition from supervoxel generation to inter-video correlation.

A second hierarchy is constructed on this global graph. Cosegments are identified as the connected components within this hierarchy that represent shared objects. A significant technical advantage of HVC is that it is parameter-free regarding the hierarchical level; specific segmentation levels can be computed directly without processing all finer levels.

Experimental Evaluation

The HVC method was evaluated on two benchmarks: ObMiC (video pairs with common objects like dogs or skaters) and MOViCS (complex sets featuring animals like chickens, giraffes, and tigers).

Performance and Efficiency

HVC demonstrated high efficiency and competitive accuracy. On the MOViCS dataset, HVC achieved the highest average accuracy (Intersection-over-Union) compared to state-of-the-art methods like RMWC and MSG. On the ObMiC dataset, it ranked as the second-best performer.

Qualitative results on the MOViCS dataset (Video 2), showing original frames, intermediate segments, and final cosegmentation.

The most notable advantage of HVC is its speed. It required less than 50% of the processing time of competing approaches. For instance, on the MOViCS dataset, HVC completed in approximately 34 hours, whereas RMWC and MSG took 128 and 76 hours, respectively.

Discussion and Conclusion

HVC proves that simple features, when combined with a robust hierarchical graph structure, can achieve state-of-the-art results in video cosegmentation. The use of the "causality" principle ensures clean object borders across scales.

However, limitations remain. Heavy reliance on color averages can lead to failures when foreground and background colors are similar. Additionally, the current implementation requires manual selection of the number of connected components ($n_{cc}$). Future work will focus on automating component selection and incorporating more robust, lightweight features to handle lighting and texture variations while maintaining the framework's significant speed advantage.

Summary updated

Abstract

The goal of video cosegmentation is to jointly extract the common foreground regions and/or objects from a set of videos. In this paper, we present an approach for video cosegmentation that uses graph-based hierarchical clustering as its basic component. Actually, in this work, video cosegmentation problem is transformed into a graph-based clustering problem in which a cluster represents a set of similar supervoxels belonging to the analyzed videos. Our graph-based Hierarchical Video Cosegmentation method (or HVC) is divided in two main parts: (i) supervoxel generation and (ii) supervoxel correlation. The former explores only intra-video similarities, while the latter seeks to determine relationships between supervoxels belonging to the same video or to distinct videos. Experimental results provide comparison between HVC and other methods from the literature on two well known datasets, showing that HVC is a competitive one. HVC outperforms on average all the compared methods for one dataset; and it was the second best for the other one. Actually, HVC is able to produce good quality results without being too computational expensive, taking less than 50% of the time spent by any other approach.
BibTeX
@inproceedings{rodrigues2017graph,
  author = {Franciele Rodrigues and Pedro Leal and Yukiko Kenmochi and Jean Cousty and Laurent Najman and Silvio Jamil Ferzoli Guimarães and Zenilton Kleber Gonçalves do Patrocínio Jr.},
  title = {{Graph-Based Hierarchical Video Cosegmentation}},
  booktitle = {ICIAP},
  year = {2017},
  url = {https://openreview.net/forum?id=woGHCZmY20},
}
Figure