💻 computer science

Square Superpixel Generation and Representation Learning via Granular Ball Computing

This paper proposes a square superpixel generation method based on granular ball computing that replaces irregular regions with multi-scale square blocks to enable efficient parallel processing and seamless end-to-end integration into deep learning architectures like GNNs and ViTs.

Original authors: Shuyin Xia, Meng Yang, Dawei Dai, Fan Chen, Shilin Zhao, Junwei Han, Xinbo Gao, Guoyin Wang, Wen Lu

Published 2026-04-01

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Shuyin Xia, Meng Yang, Dawei Dai, Fan Chen, Shilin Zhao, Junwei Han, Xinbo Gao, Guoyin Wang, Wen Lu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to describe a complex painting to a friend over the phone.

The Old Way (Traditional Superpixels):
Currently, most computer vision systems try to break an image into tiny, irregular puzzle pieces called "superpixels." Think of these like a jigsaw puzzle where every piece is a weird, jagged shape. Some are tiny triangles, some are long strips, and some are blobs.

The Problem: Computers are like robots that love grids and squares. They are terrible at handling these weird, jagged puzzle pieces. To process them, the computer has to stop, rearrange them, and do extra math, which slows everything down. It's like trying to fit a square peg into a round hole over and over again.

The New Way (This Paper's Solution):
The authors propose a new way to slice the image. Instead of jagged puzzle pieces, they cut the image into perfectly square blocks, like a grid of tiles on a bathroom floor.

Here is how their "Smart Tiling" system works, using a simple analogy:

1. The "Granular Ball" Concept (The Smart Chef)

Imagine a chef who needs to chop a huge vegetable for a soup.

Traditional methods chop the whole vegetable into tiny, uneven bits immediately.
This paper's method uses a "Granular Ball" approach. The chef looks at the vegetable and asks: "Is this part smooth and uniform, or is it messy and complex?"
- If the part is smooth (like a plain potato skin), the chef cuts a big, square chunk. One big piece covers the whole area.
- If the part is messy (like a spot with a weird root or a leaf), the chef cuts that specific spot into tiny, square pieces to capture the detail.

2. The "Purity Score" (The Quality Check)

How does the computer know if a square block is "smooth" or "messy"? It uses a Purity Score.

Imagine looking at a square block of the image. The computer picks the center color and asks: "Do all the other pixels in this square look like the center?"
If they all look similar (high purity), the computer says, "Great! We can keep this as one big square token."
If they look different (low purity), the computer says, "Too messy! Let's chop this square into four smaller squares and check them again."

3. Why Squares? (The Assembly Line)

Why not just use the jagged pieces that fit the image perfectly?

The Analogy: Think of a factory assembly line. If every product coming down the line is a different, weird shape, the robots have to stop and reconfigure their arms for every single item. It's slow and inefficient.
The Solution: If every product is a perfect square, the robots can move at full speed without stopping. They can process thousands of squares at the exact same time (parallel processing). This paper forces the image into these perfect squares so the computer's "assembly line" (Deep Learning) can run super fast.

4. The Result: A "Smart Token" System

The final output is a collection of square tokens of different sizes:

Big squares for the sky, walls, or empty space (where there is no detail).
Tiny squares for the eyes of a person, the wheels of a car, or complex textures.

This creates a multi-scale view of the image. It's like looking at a map: you see the whole country (big squares) but can zoom in instantly to see the streets (small squares) only where they matter.

What Did They Prove?

The authors tested this on three main tasks:

Classifying Images: Recognizing what an image is (e.g., "That's a cat"). Their method was more accurate than previous methods.
Image-Text Search: Finding a picture based on a text description (or vice versa). Because their squares capture structure better, the computer understood the link between words and images more clearly.
Object Detection: Finding objects in a video (like self-driving cars). They showed that by throwing away the "useless" background squares and keeping only the "important" ones, they could cut the computer's workload in half without losing much accuracy.

The Bottom Line

This paper is about teaching computers to look at pictures like a smart, efficient human: Don't waste energy on the boring, empty parts; focus your energy on the interesting details, and do it in a way that fits the machine's natural rhythm (squares and grids).

It turns a messy, slow process into a clean, fast, and highly accurate one, making AI faster and more efficient for real-world use.

1. Problem Statement

Traditional superpixel algorithms (e.g., SLIC, SEEDS) generate irregularly shaped regions that adhere well to object boundaries but are poorly aligned with modern deep learning operators. This creates several bottlenecks:

Incompatibility with Deep Learning: Irregular shapes hinder parallel processing, batch execution, and end-to-end optimization within Convolutional Neural Networks (CNNs) and Vision Transformers (ViTs).
Computational Overhead: Many methods are non-differentiable or require complex iterative refinement, making them difficult to integrate into learning pipelines.
Token Redundancy: In Transformer-based models (like DETR), processing every pixel or fixed patch as a token leads to quadratic computational complexity ( $O(N^2)$ ) in self-attention, especially for high-resolution images.
Multimodal Misalignment: In image-text tasks, standard pixel/patch tokenization lacks the structural priors needed to align effectively with discrete semantic text units.

The authors aim to develop a superpixel generation method that produces regular, square-shaped regions to enable efficient parallelism, end-to-end training, and structured token pruning.

2. Methodology: Granular Ball Computing (GBC)

The core innovation is adapting Granular Ball Computing (GBC)—a cognitive computing paradigm—to image processing. Instead of using spherical granular units, the authors propose Square Granular Balls (axis-aligned square blocks).

A. Square Superpixel Generation (Coarse-to-Fine)

The method employs a hierarchical, non-iterative, rule-based partitioning strategy:

Multi-Scale Partitioning: The image is divided into a grid of square blocks at multiple scales (from coarse to fine).
Purity Scoring: For each candidate block, a "purity score" is calculated based on pixel-intensity similarity.
- A center statistic (mean intensity of a small central window) is computed.
- The purity is defined as the ratio of pixels within the block that are consistent with this center statistic (within a threshold $\tau$ ).
Hierarchical Selection:
- High Purity: If a coarse block has high purity (homogeneous region), it is retained as a superpixel.
- Low Purity: If a block is heterogeneous, it is subdivided into smaller blocks at the next finer scale.
- Inheritance: A "covered mask" ensures that once a region is selected at a coarse scale, its sub-regions are not re-evaluated, maintaining strict spatial alignment and parent-child inheritance.
Fixed-Cardinality Output: The process continues until a fixed number of tokens is reached or the finest scale is processed, ensuring a consistent number of tokens for batch processing.

B. Integration into Deep Learning

The resulting square superpixels are treated as structured visual tokens:

Feature Extraction: A backbone network (e.g., ResNet) extracts features, which are then aggregated based on the generated masks.
Token Pruning: In Transformer architectures (like RT-DETR), low-purity background tokens are discarded before the self-attention mechanism, significantly reducing computational load.
Compatibility: The square geometry allows the tokens to be seamlessly fed into Graph Neural Networks (GNNs) or Vision Transformers (ViTs) without complex interpolation or irregular graph construction.

3. Key Contributions

Square Superpixel Mechanism: Proposes a novel, non-iterative method to generate square superpixels using Granular Ball Computing, solving the alignment issue between superpixels and standard deep learning operators.
Purity-Driven Tokenization: Introduces a rule-based, purity-scored selection process that dynamically allocates resolution (fine blocks for complex objects, coarse blocks for homogeneous backgrounds) without requiring supervised superpixel annotations.
End-to-End Compatibility: The method is GPU-parallel friendly, differentiable (via the downstream network), and requires no extra learnable generator, making it a "plug-and-play" module.
Efficient Token Pruning: Demonstrates a strategy to reduce the number of tokens in Transformer-based detectors by up to 50% while maintaining detection accuracy, directly addressing the quadratic complexity of self-attention.

4. Experimental Results

The authors validated the method across three distinct vision tasks:

Image Classification (MNIST & CIFAR-10):
- Integrated into Graph Neural Networks (GNNs) and ViG.
- Results: Achieved 99.40% accuracy on MNIST and 93.47% on CIFAR-10 (Large model), outperforming state-of-the-art graph-based methods like ShapeGNN and GAT. The adaptive granularity helped preserve discriminative features while filtering noise.
Image-Text Retrieval (CelebA & MM-CelebA):
- Integrated into the FLIP framework (replacing standard ViT patching).
- Results: Outperformed the baseline FLIP and other models (CLIP, BLIP) in zero-shot and fine-tuned retrieval tasks (Recall@K). The structured tokens improved cross-modal alignment by providing better semantic units than fixed patches.
Object Detection (COCO 2017 with RT-DETR):
- Applied as a token pruning module in the RT-DETR encoder.
- Results:
  - Reducing tokens from 400 to 200 (50% compression) resulted in only a 0.8 AP drop (53.1 $\to$ 52.3).
  - The method showed a "performance plateau," where aggressive pruning of background tokens had minimal impact on accuracy.
  - Large objects were least affected, while small objects benefited from moderate pruning (noise reduction) but suffered under excessive pruning.
  - Theoretical analysis showed a ~75% reduction in encoder self-attention complexity.

5. Significance and Impact

Bridging the Gap: This work successfully bridges the gap between classical region-based representations (superpixels) and modern deep learning architectures (Transformers/GNNs) by enforcing a regular, square geometry.
Efficiency: It offers a practical solution to the computational bottleneck of self-attention in Vision Transformers, enabling real-time, end-to-end detection with significantly reduced token counts.
Generalizability: The "plug-and-play" nature of the module allows it to be applied to various architectures (GNNs, ViTs, DETR) without retraining the entire backbone, making it a versatile tool for improving both accuracy and efficiency in computer vision systems.
Cognitive Inspiration: By leveraging Granular Ball Computing, the method mimics human "global precedence" cognition, processing coarse global information first and refining only necessary details, leading to more robust and interpretable feature representations.