重用图像窗口的计算
方框滤波或局部对比度估计可能查询同一图像的许多重叠矩形。每次从头求和会重复加法。积分图像又称累加面积表,它存储前缀和,使任何有效的轴对齐矩形都可由四个表值查询。
设 为实值图像,具有 个整数行数与列数,索引从一开始。我们先讨论固定图像及精确算术。方框平均并非理想的抗混叠滤波器,这里只把它当作一种廉价的局部统计量。
建立表格
定义 11.1.1
(积分图像(累加面积表))
对 行 列的图像 ,积分图像是数组 ,其哨兵值为 ,并且
因此 是以 及 为角的矩形内所有像素之和。哨兵行及列为零,不代表额外的图像像素。
建表时也可由相邻项得到相同前缀:
上方与左方前缀都计算了重叠部分,所以须减去一次。按行和列递增次序计算,使每个前项都已存在。这个递推式正是下一个结果在矩形只含单个像素时的特例。
命题 11.1.2
(四角矩形和公式)
设 、,并令 为 在 、 上的和。则
证明
(把前缀矩形分成四块)
以 及 为角的前缀矩形,是下列四个互不相交的区块之并:
- 目标矩形 ;
- 其上方的横条 ;
- 其左方的竖条 ;
- 左上角区块 。
用 表示 在区块 上的和;空区块的和为 ,与哨兵值一致。于是
因此公式右边等于
取 、,便得 ,即上面的递推式。
证明透视
四个项从何而来
证明中唯一不显然的一步,是分解为 、、、 四块。减去两个条形前缀 与 ,会把 和 各去掉一次,却把角块 去掉了两次,因为 同时包含在两个前缀之内。最后一项 把它加回一次。这正是对两个重叠区域使用容斥原理。
假设 、,使下标 与 合法;零哨兵把同一公式推广到紧贴上边或左边的矩形,此时 、 或 为空。上界 、 则保证每个角都在表内。
论证只用到不相交区块上的和可以相加、相减,从未用到 是一幅图像,所以同一公式也适用于逐项平方的数组 ,下面的局部方差正需要这一点。
在数组访问及精确算术均为常数时间的前提下,建表需 时间,带哨兵的表占 空间;每次矩形查询只需常数次表格访问和算术运算。这一说法针对固定的预计算图像:改变一个像素,可能改变所有右下角位于其右下方的前缀。
局部平均与方差
对图像
略去零哨兵后,其普通前缀表为
例题 11.1.3
(用递推式建立表格)
第 行与第 列只涉及哨兵。例如 。对内部项,
而最后一项为
两者都与表中数值相符。作为核对, 的全部元素之和为 。
求窗口的平均与方差需要两张前缀表,一张属于 ,一张属于 。下面使用的方差公式是以下恒等式。
命题 11.1.4
(由两个和求方差)
设 为实数,,其和为 ,平方和为 ,平均值为 。则总体方差满足
证明
(展开平方)
把 对 求和:
其中用到 。两边除以 即得恒等式。
例题 11.1.5
(窗口的平均值与方差)
取第 至 行及第 至 列。其和为 ,面积是 ,故平均值为 。由逐项平方的 建立第二张前缀表 ,其对应角值给出平方和 。
这六个样本的总体方差为
这不是分母为 的样本方差约定。精确算术下方差非负;浮点数相减两个接近的数值可能损失精度,实现时须考虑数值精度及所选策略。
例题 11.1.6
(紧贴边界的矩形)
当 或 时,公式读取零哨兵。对第 至 行及第 至 列,
而 的确等于 。只有一行的矩形也允许:对第 行及第 至 列,
与 相符。
常见错误
(角点差一)
若用 与 代替 与 ,就会漏掉矩形的第一行和第一列。对第 至 行及第 至 列,错误公式给出 ,这是由第 行第 至 列组成的较小矩形之和(),而不是所需的 。被减的前缀必须在矩形开始之前截止。
常见错误
(先求和再平方,而不是先平方再求和)
方差需要的是 ,而不是 。对上面的窗口,,平方和却是 ;若用 ,方差会变成 ,但这六个值并不全相等。这正是必须另建由 得出的表 的原因。
边界和更新属于契约
反例模式
两种边界策略给出不同平均值
对此图像左上角像素,以它为中心的 窗口伸出数组。裁剪至四个可用像素,和为 、平均为 ;以零填充缺失位置并对全部九项求平均,则得 。两者不会自动相同,必须指定边界规则及除数。
前缀表能高效查询静态图像的矩形,但不会使更新免费。若像素 改变,所有满足 且 的已存前缀 都改变相同增量。动态更新需要重新计算或改用其他数据结构。对平方和而言,改变像素还会令平方产生相应的差值,一般并不等于原增量。
习题与解答
快速检查
(当 且 ,四角公式得到什么?)
把相同的行和列代入每一项。
解答 · 答案
该像素的值,其余前缀互相抵消,这就是 的递推式。
快速检查
(例子全部像素之和是多少?)
哪一个表项涵盖整张图像?
解答 · 答案
。
快速检查
(哪个除数给出边界例子的 ?)
数一数裁剪后剩下的像素。
解答 · 答案
四,即裁剪后保留的像素数。
快速检查
(修改 后,能否直接沿用旧前缀表?)
哪些前缀包含像素 ?
解答 · 答案
不能。每个非哨兵前缀都含该像素,须更新或重算。
练习 11.1.7
(利用例子中的表 与 ,求第 至 行、第 至 列的窗口之总体方差。)
核心
平方像素表 有 及 。
解答(3)
- 1
由 求窗口之和
的角读取零哨兵,所以
- 2
由 求平方和
同样地
这与 相符。
- 3
应用方差恒等式
依据: 窗口有 个像素,所以 。