CUDA 积分图优化：二维前缀和、平方积分图和 Warp Shuffle
编写时间：2023-04
代码仓库：Plumess/Calculate-integral-image-using-cuda
积分图是这次去雾优化里最“以空间换时间”的部分。它的目的很明确：把区域求和从反复遍历变成一次预处理后的 O(1) 查询。
为什么去雾需要积分图
大气光估计要频繁计算区域均值和标准差：
Guided Filter 也要频繁计算局部窗口均值。两边都需要 box sum，所以积分图可以同时服务多个模块。
二维前缀和
二维积分图定义为：
任意矩形区域求和：
平方积分图只需要把输入换成 I^2。原 CUDA sample shfl_scan（CUDA 11.8） 只适合 0-255 的前缀和，复现时需要改到能承载 255*255 的平方值，否则标准差会不可靠。
CUDA 实现路线
其中行列 scan 内部是经典的并行前缀和（GPU Gems 3, Ch.39），分上扫（reduce，从底向上两两求和）和下扫（down-sweep，从顶向下分发前缀）两阶段。实现时最值得记的不是公式，而是并行前缀和的层级：
| 层级 | 作用 |
|---|---|
| thread | 处理局部元素 |
| warp | 用 shuffle 做快速前缀传播 |
| block | 合并多个 warp 的部分和 |
| grid | 必要时做分块累计修正 |
对去雾递归的意义
原始四叉树递归中，每个候选块都要算 mean - std。有积分图后，候选块的统计量可以直接查表：
这类优化最漂亮的地方是效果不变。算法还是原来的四叉树，还是原来的评分公式，只是把重复求和的成本挪到一次前处理里。
工程经验
- 积分图很吃数据类型，平方和要提前估计范围。
- 图像宽高固定时，可以把内存和 pitch 设计得更激进。
- 多 stream 下，中间 buffer 要按 stream 复用，避免每帧重新申请。
- 如果只优化 kernel 算法、不优化内存布局，速度很容易被 copy 和同步吃掉。
积分图和 Guided Filter 是一组优化：一个解决局部统计如何快，一个解决透射图如何平滑。两者合起来，传统去雾才真正跑进实时范围。