空间填充曲线

简要介绍

希耳伯特曲线

Z 序曲线

扫描曲线

逐行或者逐列扫描

这几个“空间填充曲线（space-filling curves）”的概念在高维数据映射、序列建模、点云处理、视觉Transformer输入编码等地方都被广泛使用。下面我会系统地介绍它们的几何定义、区别，以及它们在**序列建模（Sequence Modeling）**中的典型应用。

---

🌀 一、基本概念与几何直觉

1. 希尔伯特曲线（Hilbert Curve）

• 定义：一种递归定义的空间填充曲线，由数学家 David Hilbert 于 1891 年提出。

• 性质：

  • 将一个二维（或更高维）空间连续映射到一维区间；

  • 保持局部性（locality-preserving）：相邻的点在二维平面上也大多相邻；

  • 递归结构，可定义为任意阶次的曲线（order n Hilbert curve）。

• 直观理解：

  • 它通过“U”形或“反U”形的递归嵌套不断细化，把整个平面密集填充；

  • 例如在图像上扫描像素，可以保持二维空间中邻近像素在一维序列中仍相对接近。

➡️ 优点： 保持空间局部性最强。
➡️ 缺点： 构造复杂，不易计算索引。

---

2. Z序曲线（Z-Order Curve / Morton Order）

• 定义：把多维坐标的二进制位交错（interleave）组成一个整数序号。

  • 比如二维坐标 ((x, y))，取它们二进制形式交错排列得到索引：
    [
    \text{Z-order}(x,y) = \text{bit_interleave}(x, y)
    ]

• 几何外观：像字母“Z”那样在网格中折返遍历。

• 性质：

  • 容易计算；

  • 也有一定的局部性；

  • 但相比Hilbert曲线，空间邻近保持性较弱（存在“跳跃”）。

➡️ 优点： 计算简单，常用于数据库索引（例如 Morton code）。
➡️ 缺点： 局部性差于 Hilbert。

---

3. 扫描曲线（Raster Scan / Row-major order）

• 定义：最简单的扫描方式，逐行扫描，比如从左到右、从上到下。

• 性质：

  • 线性映射最简单；

  • 局部性最差：二维邻近点在一维中可能相距较远（例如换行处）。

➡️ 优点： 简单直接；
➡️ 缺点： 空间局部性保持极差。

---

🧩 二、在序列建模（Sequence Modeling）中的使用

序列建模（如 Transformer、Mamba、RNN）通常要求一维有序输入。
而图像、点云、体素、甚至视频都是多维数据。
所以我们需要一种“空间 → 序列”的映射方式，使模型在时间维上处理它。

空间填充曲线提供了一个自然的解决方案。

---

1. 图像建模（Image as Sequence）

在像 ViT (Vision Transformer)、MambaVision、Sparse Mamba3D 等模型中：

• 把图像分成 patch；

• 然后以**某种顺序（扫描顺序）**展开成 token 序列；

• 不同扫描顺序会影响模型的注意力、感受野与空间关系保持。

曲线类型	序列建模效果	应用举例
Raster Scan	简单但空间关系差	ViT 原始版本
Z-order Curve	较好局部性，易计算	一些轻量ViT、3D CNN转序列模型
Hilbert Curve	最优局部性保持	局部敏感注意力 (Local attention)、图像压缩、MambaVision 可参考的空间顺序

🔍 例如：
《Hilbert Attention for Vision Transformers》(ICLR 2023 workshop) 发现：
采用 Hilbert 曲线的 patch 排列能提升局部相关性建模性能。

---

2. 点云 / 3D体素建模

在 3D 点云中，常常需要把三维点投影或序列化，以便送入 Transformer 或 Mamba 模型。
此时可使用：

• Morton (Z-order) 编码为点云索引；

• 或 Hilbert order 提高局部邻域一致性。

例如：

• Point Transformer / PointNeXt 类方法中邻域构造时有用 Morton/Hilbert 排序；

• Mamba3D / Sparse Mamba3D 可通过空间填充曲线构造有序 token 流，方便连续建模。

---

3. 视频与时空建模

对视频帧（t,x,y），可用 3D Hilbert/Z-order 曲线把时空体素映射成单序列。
Mamba 等连续状态空间模型（SSM）在这种情况下特别适合，因为它能：

• 在序列维度处理长依赖；

• 利用空间填充顺序维持邻近时空关系。

---

📊 三、简单比较总结

曲线	局部性保持	计算复杂度	应用
Hilbert Curve	✅ 最强	❌ 较高	高精度空间映射、局部敏感建模
Z-order Curve	⚙️ 中等	✅ 快速	点云/数据库索引
Raster Scan	❌ 差	✅ 最快	普通ViT、CNN flatten输入

---

🚀 四、在序列模型中的具体好处

在 Mamba、Transformer 这种序列结构中使用空间曲线映射的核心好处是：

1. 序列依赖符合空间邻域结构；

2. 减少模型长距离注意负担；

3. 加快收敛，增强泛化；

4. 适配连续状态建模（SSM/Mamba）：曲线序列化使其自然对应于一维连续状态更新。

---