原文地址(英文)
积分图 是 [Crow(1984 年)] 提出的用于提高多尺度透视投影中纹理的渲染速度的一种技术. 积分图最流行的应用是 快速归一化互相关 (fast normalized cross-correlation), Viola-Jones 目标检测框架, SURF 变换( Speeded Up Robust Feature).
本章介绍的是积分图在基本的块统计滤波器中的应用.
均值
随机变量 (X={x_1,dots,x_n}) 的离散分布的均值 (mu(X)) 定义为:
[egin{equation}
egin{aligned}
mu=sum_{i=1}^np_ix_i
end{aligned}
end{equation}
]
如果 X 是一个矩形块中的像素值, 并且每个像素值的概率相同 (p_i=frac{1}{n}), 那么:
[egin{equation}
egin{aligned}mu=frac{1}{n}sum_{i=1}^nx_i
end{aligned}
end{equation}
]
这个求和可以通过 (I(vec{x})) 的积分图求解. 对于一个二维图像, 在单个 loop 中, 积分图计算会平均使用 1 次乘积和 3 次求和, 每个像素数据访问需要 5 次求和. 使用积分图, 任意矩形块的像素值的均值都可以在常数时间内计算, 即计算时需要 1 次乘积和 3 次求和, 数据访问需要 2 次乘积和 6 次求和.
方差
随机变量 (X={x_1,dots,x_n}) 的离散分布的方差 ( ext{Var}(X)) 定义为:
[egin{equation}
egin{aligned}
ext{Var}(X) = sum_{i=1}^np_i(x_i-mu)^2 quad ext{with}quad mu=sum_{i=1}^np_ix_i
end{aligned}
end{equation}
]
如果 X 是一个矩形块中的像素值, 并且每个像素值的概率相同 (p_i=frac{1}{n}), 那么:
[egin{equation}
egin{aligned}
ext{Var}(X) = frac{1}{n}sum_{i=1}^n(x_i-mu)^2 quad ext{and}quad mu=frac{1}{n}sum_{i=1}^nx_i
end{aligned}
end{equation}
]
展开公式可得:
[egin{equation}
egin{aligned}
ext{Var}(x) &= frac{1}{n}sum_{i=1}^nleft(x_i^2-2x_imu+mu^2
ight) \
&= frac{1}{n}sum_{i=1}^nx_i^2 - frac{1}{n}sum_{i=1}^n2x_imu + mu^2 \
&= frac{1}{n}sum_{i=1}^nx_i^2 - frac{1}{n}sum_{i=1}^n2x_imu + frac{1}{n^2}left(sum_{i=1}^nx_i
ight)^2\
&= frac{1}{n}sum_{i=1}^nx_i^2 - frac{2mu}{n}sum_{i=1}^nx_i + frac{1}{n^2}left(sum_{i=1}^nx_i
ight)^2\
&= frac{1}{n}sum_{i=1}^nx_i^2 - frac{2}{n^2}left(sum_{i=1}^nx_i
ight)^2 + frac{1}{n^2}left(sum_{i=1}^nx_i
ight)^2\
&= frac{1}{n}sum_{i=1}^nx_i^2 - frac{1}{n^2}left(sum_{i=1}^nx_i
ight)^2\
&= frac{1}{n}sum_{i=1}^nx_i^2 - left(frac{1}{n}sum_{i=1}^nx_i
ight)^2\
&= frac{1}{n}left(sum_{i=1}^nx_i^2 - frac{1}{n}left(sum_{i=1}^nx_i
ight)^2
ight)\
end{aligned}
end{equation}
]
每一个求和都可以使用两个积分图: (I(vec{x})) 和 (I(vec{x})^2). 对于一个二维图像, 在单个 loop 中, 积分图计算会平均使用 1 次乘积和 6 次求和, 每个像素数据访问需要 5 次求和. 使用积分图, 任意矩形块的像素值的方差都可以在常数时间内计算, 即计算时需要 3 次乘积和 9 次求和, 数据访问需要 2 次乘积和 6 次求和.
使用积分图进行块匹配(Block Matching)
考虑这样一种场景: 两张部分重叠的图像区域 X 和 Y 可能在图像亮度和对比度上有所不同, 使用简单的估计器 (simple estimator), 比如 Mean Square Error (MSE) 并不能测量两个图像区域的相似度, 因为 MSE 对于线性变换不是固定不变的.
此时, 我们需要一种线性相关的测量方法. 皮尔森乘积矩相关系数 (PMCC, Pearson Product-Moment Correlation Coefficient) (
ho_{X,Y}) 就是一种线性相关的测量方法:
[egin{equation}
egin{aligned}
ho_{XY} = frac{sigma_{XY}}{sigma_{X}sigma_{Y}}
end{aligned}
end{equation}
]
其中, 对 X 进行 n~elements 的有限采样, 那么每一个样本的相关系数 (r_{XY}) 为:
[egin{equation}
egin{aligned}
r_{XY} = frac{sum_{i=1}^n(x_i-mu_X)(y_i-mu_Y)}{sqrt{sum_{i=1}^n(x_i-mu_X)^2}sqrt{sum_{i=1}^n(y_i-mu_Y)^2}}quad ext{其中,}quadmu_X = frac{1}{n}sum_{i=1}^nx_i
end{aligned}
end{equation}
]
可以将公式的分子变形为:
[egin{equation}
egin{aligned}
sum_{i=1}^n(x_i-mu_X)(y_i-mu_Y) &= sum_{i=1}^nx_iy_i-sum_{i=1}^nx_imu_Y-sum_{i=1}^ny_imu_X+sum_{i=1}^nmu_Xmu_Y \
&= sum_{i=1}^nx_iy_i-mu_Ysum_{i=1}^nx_i-mu_Xsum_{i=1}^ny_i+nmu_Xmu_Y\
&= sum_{i=1}^nx_iy_i-frac{1}{n}sum_{i=1}^ny_isum_{i=1}^nx_i
end{aligned}
end{equation}
]
对于整个分式乘以 (frac{n}{n}):
[egin{equation}
egin{aligned}
r_{XY} &= frac{sum_{i=1}^nx_iy_i-frac{1}{n}sum_{i=1}^ny_isum_{i=1}^nx_i}{sqrt{sum_{i=1}^n(x_i-mu_X)^2}sqrt{sum_{i=1}^n(y_i-mu_Y)^2}} \
&= frac{nsum_{i=1}^nx_iy_i-sum_{i=1}^ny_isum_{i=1}^nx_i}{nsqrt{sum_{i=1}^n(x_i-mu_X)^2}sqrt{sum_{i=1}^n(y_i-mu_Y)^2}} \
&= frac{nsum_{i=1}^nx_iy_i-sum_{i=1}^ny_isum_{i=1}^nx_i}{sqrt{nsum_{i=1}^n(x_i-mu_X)^2}sqrt{nsum_{i=1}^n(y_i-mu_Y)^2}}
end{aligned}
end{equation}
]
根据上面的推导, 可得:
[egin{equation}
egin{aligned}
nsum_{i=1}^n(x_i-mu_X)^2 &= nsum_{i=1}^n(x_i^2-2x_imu_X+mu_X^2) \
&= nsum_{i=1}^nx_i^2 - 2nmu_Xsum_{i=1}^nx_i + left(sum_{i=1}^nx_i
ight)^2\
&= nsum_{i=1}^nx_i^2 - 2left(sum_{i=1}^nx_i
ight)^2 + left(sum_{i=1}^nx_i
ight)^2\
&= nsum_{i=1}^nx_i^2 - left(sum_{i=1}^nx_i
ight)^2
end{aligned}
end{equation}
]
因此:
[egin{equation}
egin{aligned}
r_{XY} = frac{nsum_{i=1}^nx_iy_i - sum_{i=1}^nx_isum_{i=1}^ny_i}{sqrt{nsum_{i=1}^nx_i^2 - left(sum_{i=1}^nx_i
ight)^2}sqrt{nsum_{i=1}^ny_i^2 - left(sum_{i=1}^ny_i
ight)^2}}
end{aligned}
end{equation}
]
由公式可以看出, 我们计算图像上固定偏移处的每个 block 的 (r_{XY}) 时, 都只需要计算 5 个 summed-area tables, 即 (x_iy_i, x_i, y_i, x_i^2, y_i^2), 因此算法复杂度是常数.
在一些求极值的问题中, 我们可以估计出 (r_{XY}^2) 和 (r_{XY}) 的符号(即分子的符号)即可. 这样就可以避免计算开根号来提高效率.
[egin{equation}
egin{aligned}
r_{XY}^2 = frac{a^2}{left(nsum_{i=1}^nx_i^2 - left(sum_{i=1}^nx_i
ight)^2
ight)left(nsum_{i=1}^ny_i^2 - left(sum_{i=1}^ny_i
ight)^2
ight)}
end{aligned}
end{equation}
]
with
[egin{equation}
egin{aligned}
a = nsum_{i=1}^nx_iy_i - sum_{i=1}^nx_isum_{i=1}^ny_iquad ext{and}quad{}sgn(r_{XY}) = sgn(a)
end{aligned}
end{equation}
]
参考资料
[1]: Integral Image Filter
[2]: Crow, Franklin C. (1984). "Summed-area tables for texture mapping". Proceedings of the 11th annual conference on Computer graphics and interactive techniques: 207–212, ACM. doi:10.1145/800031.808600.
[3]: Lewis, J. P. (1995). "Fast template matching". Vision Interface 95: 120–123, Canadian Image Processing and Pattern Recognition Society.
[4]: Viola, Paul & Jones, Michael J. (2004), "Robust Real-Time Face Detection", International Journal of Computer Vision 57 (2): 137–154
[5]: Bay, Herbert; Ess, Andreas & Tuytelaars, Tinne et al. (2008), "SURF: Speeded Up Robust Features", Computer Vision and Image Understanding (CVIU) 110 (3): 346–359