Efficient Deep Space Filling Curve

Wanli Chen, Xufeng Yao, Xinyun Zhang, Bei YuICCV 2023 · DOI

Abstract

Space-filling curves (SFCs) are fundamental tools for linearizing multi-dimensional data while preserving spatial locality. While traditional SFCs like the Hilbert curve are data-independent, recent research has shifted toward data-adaptive curves that align with image content. This paper introduces an efficient, deep-learning-based framework for generating data-adaptive SFCs. By introducing an Efficient-GCN (EGCN) module and a Siamese learning scheme to bypass non-differentiable operations, the proposed method achieves state-of-the-art performance in data compression and transmission with significantly reduced computational overhead.

Introduction

Space-filling curves (SFCs) flatten multi-dimensional structures into 1D sequences, a process critical for image compression, database indexing, and efficient data transmission. The goal is to maintain "locality," ensuring that points near each other in the original space remain close in the 1D sequence.

Traditional SFCs, such as Hilbert or Z-curves, follow a fixed, data-agnostic pattern. While robust, they do not account for the specific features of the data being processed. Data-adaptive SFCs aim to improve locality preservation by following the natural contours, edges, and textures of an image. However, existing deep-learning approaches for adaptive SFCs often suffer from high computational complexity and optimization challenges due to non-differentiable steps like Minimum Spanning Tree (MST) generation.

Methodology

The proposed framework addresses these challenges through three primary innovations:

1. Efficient-GCN (EGCN)

Standard Graph Convolutional Networks (GNNs) are computationally expensive for image grids due to the size of the adjacency matrices. The authors observe that in a 4-connected grid graph, the adjacency matrix is sparse and structured. They replace traditional matrix multiplication with an element-shifting module that moves feature maps in four cardinal directions. This approach reduces memory usage from 104M to 32M and latency from 11ms to 4ms compared to standard GCNs.

2. Multi-Stage MST

To capture both fine-grained textures and high-level structural information, the model extracts features from multiple stages of a ResNet backbone. By generating candidate MSTs at different levels of abstraction and finding their intersection, the resulting curve is more stable and representative of the global image context.

3. Siamese Learning Scheme

The MST algorithm is inherently non-differentiable, making it difficult to train via standard backpropagation. The authors utilize a Siamese/Teacher-Student framework. A "Main Network" processes the original image, while a "Siamese Network" processes a noisy version. The network achieving a better task-specific score (e.g., compression efficiency) acts as a teacher, guiding the other network to mimic its output via KL-divergence.

Key Insights and Ideas

The central insight of this work is the exploitation of grid symmetry to optimize graph operations. By treating graph edges as spatial shifts, the model gains the representational power of GNNs without the associated overhead. Furthermore, the Siamese learning scheme provides a robust way to optimize discrete algorithms within a deep learning pipeline.

Comparison of traditional Hilbert curves versus the proposed data-adaptive curves on MNIST and natural images.

As shown in the figure above, the proposed curves "bend" around image features, whereas the Hilbert curve remains static. This adaptation leads to higher autocorrelation in the resulting 1D string, which is highly beneficial for downstream tasks.

Experimental Results

The model was evaluated on MNIST, Fashion-MNIST, and Tiny-ImageNet. Key findings include:

  • Compression Efficiency: On MNIST, the LZW code length was reduced to 158.3 bytes, outperforming the Hilbert curve (182.7 bytes).
  • Data Transmission: The method achieved an autocorrelation score of 0.625 on MNIST, significantly higher than the Hilbert curve’s 0.475.
  • Computational Performance: Training time per epoch was reduced from 1867 seconds (previous SOTA) to just 72 seconds.

Conclusion

This paper presents a significant step forward in making data-adaptive space-filling curves practical for real-world applications. By combining efficient grid-based convolutions with a clever self-learning optimization strategy, the authors provide a scalable and high-performance alternative to traditional mathematical curves. Future work will focus on scaling these methods to higher resolutions and exploring applications in 3D point cloud compression.

Summary updated

BibTeX
@inproceedings{chen2023efficient,
  author = {Wanli Chen and Xufeng Yao and Xinyun Zhang and Bei Yu},
  title = {{Efficient Deep Space Filling Curve}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2023},
  doi = {10.1109/iccv51070.2023.01607},
}
Figure