积分图像（Integral image）

1 问题起源

给定一幅灰度图像，其灰度值如下图所示，

要计算图中深色区域的所有像素点的灰度值之和。

最直接，简单的方法就是将这9个像素值直接相加。

如果深色区域扩大，里面包含成千上万个像素，这种算法的时间复杂度也会呈线性增加。

积分图像的提出正好解决了这个问题。

2 积分图像

积分图像顾名思义，就是求和，完整的意思是每一个像素点的灰度值等于在该像素点之前

所有像素点灰度值之和。

从上方图中抽取4个像素：

这4个像素点对应的在积分图像中的值为：

其关系为：

将1中的图像转换为积分图像，如下图所示：

深色区域的灰度值之和就是：

120-42-21+6=63

其计算原理如下：

上图为一张原始图像，其标示了四个区域：A, B , C ,D

1 处像素点对应的在积分图像中的值为：sum(A);

2 处像素点对应的在积分图像中的值为：sum(A+B);

3 处像素点对应的在积分图像中的值为：sum(A+C);

4 处像素点对应的在积分图像中的值为：sum(A+B+C+D);

则：

区域D所有的像素点灰度值之和为：

sum(A+B+C+D) - sum(A+C) - sum(A+B) + sum(A)