3D Sparse Convolution¶
约 1486 个字 预计阅读时间 5 分钟
前言：处理 3D 点云数据（如自动驾驶 LiDAR）时，面对 99% 都是“空气”的稀疏空间，标准的 3D 卷积（Standard Conv）会浪费巨大的算力在 0 值计算上。
本文深入解剖 Sparse Convolution (稀疏卷积) 的底层工程实现，揭示它是如何通过 Rulebook（规则书） 和 Hash Map 将 \(O(V_{olume})\) 的复杂度降低为 \(O(N_{points})\) 的。
一、 核心痛点与思维转换¶
1. 数据的本质区别¶
- 2D 图像 (Dense)：是一个 \(H \times W\) 的稠密网格。每一个像素都有值，哪怕是黑色的背景。
- 3D 点云 (Sparse)：是一个巨大的空旷房间，只有零星漂浮的灰尘（点）。
- 痛点：如果用标准卷积核 \(3 \times 3 \times 3\) 去扫描，卷积核大部分时间都在和空气（0）做乘法。
- 后果：计算量爆炸，且常规卷积会导致“膨胀”（Dilation），让稀疏的点云变成实心的体素块，撑爆显存。
2. 核心方案¶
Sparse Convolution 的核心逻辑是：“只在有数据的地方计算，绝不碰空气。”
它放弃了“滑动窗口”的物理模拟，改用 “查表（Hash Map）+ 规则映射（Rulebook）” 来实现卷积。
二、 数据预处理：从连续到离散¶
在进入显存之前，原始的点云数据必须经过 Voxelization (体素化)。
- 量化 (Quantization)：将连续的浮点坐标 \((x, y, z)\) 映射到整数网格。 $\(P_{int} = \text{floor}(P_{raw} / \text{voxel\_size})\)$
- 去重 (Hashing)：如果有多个点落入同一个格子，取平均值，合并为一个 Voxel。
- 批次堆叠 (Collating)：
- GPU 需要并行处理 Batch 中的多帧数据。
- 做法：不使用 \(B \times C \times D \times H \times W\) 的张量，而是将所有帧的点拼成一个超长列表。
- 为了区分不同帧，在坐标前增加一维 BatchID。
- 最终数据结构 (Indices Table)：维度 \((N_{total}, 4)\)，每一行是 \((b, z, y, x)\)。
三、 核心算法：Rulebook 与 Implicit GEMM¶
这是 Sparse Conv 的灵魂。卷积不再是“滑窗”，而是分成了两个阶段：建表 和 计算。
Phase 1: 构建规则书 (Rulebook Generation)¶
假设卷积核大小为 \(3 \times 3 \times 3\)（共有 \(K=27\) 个偏移量，即 27 个权重矩阵）。
-
建立 Hash Map：
- 将所有输入坐标 \((b, z, y, x)\) 存入哈希表。
- Key: 坐标 Hash 值；Value: 在输入特征表中的行号 \(Index_{in}\)。
- 目的：实现 \(O(1)\) 时间复杂度的邻居查找。
-
生成 Rulebook：
- 遍历卷积核的每一个偏移量 \(k \in \{0, ..., 26\}\)。
- 对于所有输入点 \(P_{in}\)，计算目标坐标：\(P_{target} = P_{in} + Offset_k\)。
- 查表 (Query)：拿着 \(P_{target}\) 去 Hash Map 中查询。
- 命中：说明该方向有邻居。记录一条规则：
Input[i]的特征需要加到Output[j]。 - 未命中：说明是空气，直接跳过（不产生计算）。
- 命中：说明该方向有邻居。记录一条规则：
产物：一张包含 27 个子表的清单，明确了数据的流向。
Phase 2: 执行计算 (Implicit GEMM)¶
有了 Rulebook，GPU 就可以利用矩阵乘法（GEMM）并行加速了。过程称为 Gather-GEMM-Scatter。
对于每一个卷积核偏移 \(k\)：
- Gather (收集)：根据 Rulebook，将所有参与计算的输入特征“抓”出来，拼成矩阵 \(M_{in}\)。
- GEMM (矩阵乘法)： $\(M_{out} = M_{in} \times W_k\)$
- Scatter (撒回/累加)：将计算结果 \(M_{out}\) 根据 Rulebook 对应的输出索引，累加 (Atomic Add) 到输出特征表中。
四、 两种关键流派：Submanifold vs. Regular¶
在工程落地（如 ResNet Backbone）中，这两种卷积分工明确。
| 特性 | Submanifold Sparse Conv (SSC) | Regular Sparse Conv (SC) |
|---|---|---|
| 核心逻辑 | 极度克制。只计算 Input Hash Map 中已存在的点。 | 允许膨胀。只要卷积核扫到，空气也会变成输出点。 |
| Hash 策略 | 查 Input Map。没查到就丢弃。 | 查 Output Map（若无则新建 Key）。 |
| 输出形状 | Output 坐标完全等于 Input 坐标。 | Output 点数 > Input 点数（稀疏度降低）。 |
| 应用场景 | 主干网络 (Backbone)。堆叠 50 层也不会导致计算量爆炸。 | 下采样 (Downsample) 或初始特征提取。 |
| 直观理解 | “我不生产新点，我只在现有邻居间传递信息。” | “像墨水滴在纸上，会晕染开。” |
五、 进阶机制：Stride, Upsampling 与 Optimization¶
1. 下采样 (Stride > 1)¶
- 坐标变换：\(Coords_{out} = \text{floor}(Coords_{in} / \text{stride})\)。
- 冲突处理：多个输入点可能塌缩到同一个输出点。
- 逻辑：Rulebook 会记录多对一的关系，在 Scatter 阶段自动将特征累加。
2. 上采样 (Sparse Transposed Conv)¶
- 通常用于 U-Net 架构的 Decoder 部分。
- 核心技巧：逆向复用 Rulebook。
- 不需要重新计算邻居关系。
- 直接把 Encoder 阶段（下采样）生成的 Rulebook 倒过来用。
- Input 变成 Output，Output 变成 Input。
- 这使得 Sparse U-Net 的推理速度极快。
3. 内存优化：Z-Order Curve (Morton Code)¶
- 痛点：点云数据在内存中是乱序的，GPU 查表时面临严重的随机访问（Cache Miss）。
- 方案：在建立 Hash Map 前，根据坐标 \((x, y, z)\) 计算 Morton Code 并排序。
- 原理：利用空间填充曲线，保证物理空间相邻的点，在显存地址中也是相邻的。
- 效果：大幅提升显存带宽利用率（
spconv比 naive 实现快的原因之一）。 - 延伸：这也是 Point Transformer V3 (PTv3) 的核心，利用 Z-Order 将 3D 问题转化为 1D 序列问题，从而适配 FlashAttention。
六、 总结：思维模型对比¶
如果用一句话概括 Sparse Conv 与 Standard Conv 的区别：
-
Standard Conv (Pull Mode / 老师收作业)：
- 以输出像素为中心，强制扫描周围所有位置，不管有没有人，按模板求和。
- 计算量与空间体积成正比。
-
Sparse Conv (Push Mode / 快递员送货)：
- 以输入点为中心，主动分发特征给周围的有效邻居（查表）。
- 计算量仅与非空点数量成正比 (\(O(N)\))。
这套机制使得在几万个点的稀疏数据上运行深层卷积网络成为可能，构成了现代 3D 感知算法（如 CenterPoint, VoxelNet）的基石。