Fast Computation of Content-Sensitive Superpixels and Supervoxels Using Q-Distances

Zipeng Ye, Ran Yi, Minjing Yu, Yong-Jin Liu, Ying He

Introduction

In computer vision, superpixels and supervoxels serve as fundamental building blocks, grouping similar pixels into atomic regions to reduce computational complexity for downstream tasks like object tracking and 3D reconstruction. A major challenge in this field is generating Content-Sensitive Superatoms (CSS)—regions that adapt their density based on image detail, becoming small and dense in complex areas (e.g., textures) and large in homogeneous regions (e.g., sky).

While state-of-the-art methods achieve this by treating images as high-dimensional manifolds and calculating geodesic distances, they typically rely on Dijkstra’s algorithm. This results in $O(N \log N)$ complexity, creating a significant bottleneck for high-resolution video processing. This paper introduces qd-CSS, a novel algorithm that achieves linear $O(N)$ time complexity, running up to 8 times faster than previous manifold-based leaders.

Methodology: The qd-CSS Framework

The qd-CSS algorithm improves upon the Geodesic Centroidal Voronoi Tessellation (GCVT) framework through several key innovations.

Manifold Mapping and Initialization

The process begins by mapping images or videos into higher-dimensional spaces (e.g., $\mathbb{R}^5$ for color images). In this embedding, the manifold's local area or volume directly corresponds to the information density of the original content. To ensure a high-quality initial distribution of superpixel centers, the authors employ a modified $K$-means++ seeding strategy on this manifold.

Conceptual overview of mapping an image to a high-dimensional manifold for content-sensitive tessellation.

The Q-Distance Breakthrough

The core innovation is the replacement of priority-queue-based distance calculations (Dijkstra) with a simple First-In-First-Out (FIFO) queue, termed the "q-distance." This shift reduces the computational complexity from $O(N \log N)$ to a true linear $O(N)$.

While q-distances may not always represent the absolute shortest path in a single pass, the authors demonstrate that the iterative nature of the Voronoi tessellation naturally corrects these minor inaccuracies. If a region is initially mislabeled, the algorithm compensates in subsequent iterations by placing more generators in complex areas, eventually converging to an accurate representation.

Experimental Evaluation

The authors conducted an extensive evaluation of qd-CSS against 31 superpixel methods and 8 supervoxel methods across multiple datasets, including BSDS500, NYUV2, and BuffaloXiph.

Performance and Accuracy

  • Speed: qd-CSS demonstrates a massive efficiency gain, running 6–8 times faster than IMSLIC and 4–5 times faster than the deep-learning-based SEAL.
  • Scalability: Due to its $O(N)$ complexity, the method scales linearly with pixel count, making it exceptionally well-suited for high-definition video where other methods falter.
  • Visual Quality: On the BSDS500 benchmark, qd-CSS achieved the lowest Under-segmentation Error (UE) among traditional methods. As shown in visual comparisons, the method effectively concentrates superpixels in high-detail regions like the hay while maintaining large, efficient regions in the sky.
Visual comparison of qd-CSS (Ours) against other superpixel methods, highlighting its superior content sensitivity and boundary adherence.

Conclusion

qd-CSS represents a significant step forward in efficient image and video segmentation. By proving that "good enough" local distances are sufficient for global convergence in an iterative framework, the authors have unlocked linear-time performance for content-sensitive superatoms. While current mappings are hand-crafted for color and depth, future research may explore deep-learning-based manifold embeddings to capture even more complex semantic features.

Summary updated

Abstract

State-of-the-art researches model the data of images and videos as low-dimensional manifolds and generate superpixels/supervoxels in a content-sensitive way, which is achieved by computing geodesic centroidal Voronoi tessellation (GCVT) on manifolds. However, computing exact GCVTs is slow due to computationally expensive geodesic distances. In this paper, we propose a much faster queue-based graph distance (called q-distance). Our key idea is that for manifold regions in which q-distances are different from geodesic distances, GCVT is prone to placing more generators in them, and therefore after few iterations, the q-distance-induced tessellation is an exact GCVT. This idea works well in practice and we also prove it theoretically under moderate assumption. Our method is simple and easy to implement. It runs 6-8 times faster than state-of-the-art GCVT computation, and has an optimal approximation ratio O(1) and a linear time complexity O(N) for N-pixel images or N-voxel videos. A thorough evaluation of 31 superpixel methods on five image datasets and 8 supervoxel methods on four video datasets shows that our method consistently achieves the best over-segmentation accuracy. We also demonstrate the advantage of our method on one image and two video applications.
BibTeX
@inproceedings{ye2019fast,
  author = {Zipeng Ye and Ran Yi and Minjing Yu and Yong-Jin Liu and Ying He},
  title = {{Fast Computation of Content-Sensitive Superpixels and Supervoxels Using Q-Distances}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2019},
  doi = {10.1109/iccv.2019.00387},
}
Figure