重用影像視窗的計算
方框濾波或局部對比度估計可能查詢同一影像的許多重疊矩形。每次從頭求和會重複加法。積分影像又稱累加面積表,它儲存前綴和,令任何有效的軸對齊矩形可由四個表值查詢。
設 為實值影像,具有 個整數行數與列數,索引從一開始。我們先討論固定影像及精確算術。方框平均並非理想的抗混疊濾波器,這裏只把它當作一種廉價的局部統計量。
建立表格
定義 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
應用方差恆等式
依據: 視窗有 個像素,所以 。