積分影像

積分影像（integral image），又稱面積和表（summed-area table），是一種預先計算，讓你能以常數時間加總任意矩形內的像素值，無論矩形多大。樸素地說，加總一個 100×100 的區域意味著相加一萬個數字，而在許多位置與尺度上這麼做慢得令人卻步。積分影像的技巧把每個這樣的矩形和化約成恰好四次查找與三次加法，這正是讓即時特徵偵測（Viola-Jones 人臉偵測、SURF）在 2000 年代初期硬體上變得可行的單一最關鍵優化。

它的建構只需一趟。積分影像是一個與原影像同樣大小的新陣列，其中某位置的值，是它左上方（含自身）所有原始像素的總和。你可以用一個遞迴在單次掃描中填完它：每個項等於原始像素，加上方的項，加左方的項，再減去左上對角的項（這個減法修正了被加了兩次的重疊）。在這個一次性的成本之後，矩形查詢就不再需要原始影像。

查詢才是優雅之處。任意軸對齊矩形內的像素和，可用其在積分影像中的四個角以排容原理求得：取右下角的值，減去矩形正上方與正左方角落的值，再加回左上角的值（它被減了兩次）。四次記憶體讀取，無論矩形是 4 個像素還是四百萬個像素。這個 O(1) 的矩形和，驅動了級聯偵測器中的類 Haar 特徵（亮矩形減暗矩形之和），以及 SURF 中對高斯導數的盒狀濾波器近似。

同樣的構想可自然延伸。對像素值平方的積分影像，讓你能以常數時間計算任意矩形內的變異數（對自適應門檻與正規化有用）。在不同梯度方向上的多張積分影像給出積分直方圖（integral histogram），可加速密集 HOG。也存在更高維的面積和表，以及旋轉（45 度）積分影像，用於特殊化的特徵。唯一要當心的是數值問題：積分值隨影像面積增長，對大型或高位元深度影像可能溢出 32 位元整數，因此實作會用 64 位元整數或浮點數，並可能把超大影像分塊處理。