传统去雾算法中的递归计算优化：四叉树、均值方差和积分图

编写时间：2023-03

大气光估计是传统去雾里值得单独拆出来的计算环节。它看起来只是一个小函数，但在 1080P 视频去雾里会被反复调用，里面的均值和标准差如果每次都遍历像素，代价很快就会堆起来。

原始递归过程

大气散射模型还是：

I(x)=J(x)t(x)+A(1-t(x))

算法要先找全局大气光 A，思路来自 Kim et al. JVCIR 2013。原始方法是从整张图开始，把当前区域 R_k 切成四个子区域，对每个子区域计算：

S(R)=\mu(R)-\sigma(R)

均值越高，越可能接近大气光；标准差越小，越说明区域更均匀，可能是雾区域。每次把区域分成四块，选分数最高的一块继续递归，直到区域足够小，再取最亮像素作为 A。

Mermaid Loading...

问题在于：每一层都要对四个子区域遍历像素。虽然递归只选一个分支继续走，但每层的四个候选区域都要算一遍。大图上这部分不优雅，也不适合频繁做。

区域均值：

\mu(R)=\frac{1}{|R|}\sum_{x\in R} I(x)

区域标准差可以写成：

\sigma(R)=\sqrt{\frac{1}{|R|}\sum_{x\in R}I(x)^2-\mu(R)^2}

所以其实只需要两个东西：区域像素和、区域平方像素和。只要能快速拿到这两个值，就不用每次扫区域。

先对整张亮度图构建积分图 Sum 和平方积分图 SqSum：

Sum(x,y)=\sum_{i\le x,j\le y}I(i,j)

任意矩形区域 (x1,y1)-(x2,y2) 的求和可以 O(1) 得到：

Total = S(x_2,y_2)-S(x_1,y_2)-S(x_2,y_1)+S(x_1,y_1)

平方积分图同理。于是每个子块的 mean/std/score 都变成少量查表和加减法。

Mermaid Loading...

优化后的递归逻辑没有变：仍然四叉树、仍然 mean - std、仍然选最高分区域。变化在统计量的计算方式。

这类优化的好处是“不改算法效果，只改计算路径”。对博客来说也很清楚：传统算法并不等于慢，慢的是没有把可复用的统计量缓存起来。

在 CUDA 版本里，这个优化和 guided filter 的 box filter 是同一类思想：把局部窗口统计变成前缀和查询，把重复求和变成一次预处理。整条去雾链路才能从 24ms 级压到 10ms 以内。