Square Superpixel Generation and Representation Learning via Granular-ball Computing

Shilin Zhao, Dawei Dai, Guolai Jiang, Fenglin Yu, Chengfang Zhang, Shuyin Xia2025 · DOI

TL;DR

This paper introduces a novel "square superpixel" generation method that uses granular ball computing to create compact, grid-aligned visual tokens. This approach overcomes limitations of traditional irregular superpixels, enabling seamless integration into deep learning models like Vision Transformers for improved efficiency and performance in tasks like image classification, retrieval, and object detection.

What Problem Does This Paper Address?

Current computer vision systems often struggle with computational overhead and a lack of robustness and interpretability, especially in complex scenes. Superpixels offer a way to reduce this by grouping pixels into meaningful regions, preserving object boundaries. However, most existing superpixel algorithms produce irregular shapes that don't play well with the grid-based nature of modern deep learning architectures like convolutions and Vision Transformers. This forces superpixel generation to be an offline, separate step, hindering end-to-end optimization and parallel processing. The paper aims to bridge this gap by creating superpixels that are both effective at representing image structures and compatible with modern deep learning pipelines.

Methods

The core innovation is a "square superpixel" generation method inspired by Granular Ball Computing (GBC). Instead of irregular shapes, it uses axis-aligned square blocks of varying sizes. The process is hierarchical and coarse-to-fine:

  1. Multi-Granularity Partitioning: The image is divided into square blocks at multiple scales.
  2. Purity Score: For each block, a "purity score" is calculated based on pixel intensity similarity to the block's center. This score indicates how homogeneous a region is.
  3. Selection and Refinement: High-purity blocks are selected as superpixels. Less pure regions are further subdivided at finer scales. This process ensures a fixed number of superpixel tokens and maintains parent-child inheritance across scales.
  4. Structured Tokenization: These square superpixels are then treated as structured visual tokens, directly usable by Graph Neural Networks (GNNs) or Vision Transformers (ViTs).

This approach avoids non-differentiable steps and complex iterative refinement, making it GPU-parallel friendly and suitable for end-to-end integration.

Datasets

The paper evaluates its method on several standard datasets:

  • Image Classification: MNIST, CIFAR-10.
  • Image-Text Retrieval: CelebA, MM-CelebA.
  • Object Detection: MS COCO 2017.

No new datasets were introduced.

Key Insights and Ideas

  • Square Superpixels for Deep Learning: The key insight is that by forcing superpixels into a square, grid-aligned format, they become directly compatible with the computational structures of modern deep learning models, enabling true end-to-end integration.
  • Purity as a Quality Metric: Using a "purity score" based on local intensity similarity is an effective, rule-based way to identify meaningful image regions without requiring complex learned objectives or iterative optimization.
  • Coarse-to-Fine Hierarchy: The hierarchical, coarse-to-fine generation process allows the method to adaptively capture both large homogeneous regions and fine-grained details in complex areas, leading to a more robust representation.
  • Token Pruning Efficiency: The structured, fixed-cardinality nature of these superpixel tokens makes them ideal for token pruning strategies in Transformers, significantly reducing computational cost with minimal accuracy loss.

Key Results

  • Image Classification: Achieved state-of-the-art or competitive results on MNIST (99.40% accuracy) and CIFAR-10 (up to 93.47% accuracy) when integrated with GNNs/ViTs.
  • Image-Text Retrieval: Outperformed baselines like FLIP in zero-shot retrieval on CelebA and MM-CelebA, demonstrating improved cross-modal alignment.
  • Object Detection: When integrated into RT-DETR, the method achieved competitive performance with significantly reduced token counts (e.g., 52.3 AP with 50% token reduction), showcasing a favorable accuracy-efficiency trade-off. The method demonstrated robustness to aggressive pruning, with performance plateauing even when halving the tokens.

Limitations and Future Work

  • Computational Complexity: While efficient and GPU-parallel, the method's complexity is O(LN), where L is the number of stages. The paper notes that while this is not asymptotically better than linear, its practical advantages lie in structured, budget-controllable tokenization.
  • Future Work: The authors plan to extend their method to more ViT-based vision tasks and systematically evaluate its effectiveness across different tasks and architectures. They also suggest further exploration of how these superpixel structural priors can enhance model generalization.

Summary updated

Abstract

Superpixels, known for their advantages in reducing computational complexity and preserving image boundaries, have been widely utilized in the visual domain. However, existing superpixel generation methods typically produce irregularly shaped superpixels, which limit their adaptability to convolutional learning. Consequently, most superpixel generation methods are confined to being independent preprocessing steps, further hindering parallel processing and end-to-end training of images. Inspired by the adaptive representation and coverage capabilities of the granular-ball computing, we propose a square superpixel generation method. Specifically, this approach approximates superpixels using square blocks of varying sizes, effectively overcoming the computational limitations imposed by irregular shapes, thereby enabling parallelism and learnable features. Additionally, the method calculates the intensity similarity of pixels to generate a purity score for each square block, using these scores to select optimal superpixel blocks. Furthermore, we integrate these superpixel blocks as nodes in graph neural networks and tokens in Vision Transformers, enabling the effective extraction of multi-scale information and structured representation of visual features. Experimental results demonstrate that this method significantly enhances computational efficiency and model performance in downstream tasks, validating the effectiveness of the square superpixel generation approach.
BibTeX
@misc{zhao2025square,
  author = {Shilin Zhao and Dawei Dai and Guolai Jiang and Fenglin Yu and Chengfang Zhang and Shuyin Xia},
  title = {{Square Superpixel Generation and Representation Learning via Granular-ball Computing}},
  year = {2025},
  doi = {10.1109/cisat66811.2025.11181937},
}
Figure