積分圖

積分圖（英語：integral image），又稱總和面積表（英語：summed area table，簡稱SAT），是一個快速且有效的對一個網格的矩形子區域中計算和的數據結構和算法。

歷史

積分圖是於1984年由富蘭克林·克羅引入計算機圖形學領域，在20年後用於維奧拉-瓊斯目標檢測框架。富蘭克林在設計積分圖時主要是為Mipmap設計，但積分圖並沒有在計算機圖形學領域中被廣泛使用，直至在20年後，積分圖才因維奧拉-瓊斯目標檢測框架的使用而開始普遍起來。然而，從歷史角度來看，富蘭克林對多維度的概率分布函數研究的理念是眾所周知的，即透過觀察、計算各自的累積分布函數，以計算出二維 （或N維）概率（面積的概率分布）。

算法

積分圖的每一點（x, y）的值是原圖中對應位置的左上角區域的所有值得和：

$I(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i(x',y')$

而且，積分圖可以只遍歷一次圖像即可有效的計算出來，因為積分圖每一點的（x, y）值是：

$I(x,y)=i(x,y)+I(x-1,y)+I(x,y-1)-I(x-1,y-1)\,$

計算矩形陰影區域的值

一旦積分圖計算完畢，對任意矩形區域的和的計算就可以在常數時間內完成。如右圖中，陰影矩形區域的值：

$\sum _{\begin{smallmatrix}A(x)<x'\leq C(x)\\A(y)<y'\leq C(y)\end{smallmatrix}}i(x',y')=I(C)+I(A)-I(B)-I(D).$

擴展

這個方法可以自然的擴展到連續空間。

這個方法也可以擴展到高維圖像中。如果該矩形的角是$x^{p}$，而$p$是$\{0,1\}^{d}$的話，那麼矩形中包含圖像的值的總和就能以下列公式計算：

$\sum _{p\in \{0,1\}^{d}}(-1)^{d-\|p\|_{1}}I(x^{p})\,$

其中，$I(x)$是於$x$的積分圖，而$d$則是圖像尺寸。與表示法$x^{p}$對應的例子有$d=2$、$A=x^{(0,0)}$、$B=x^{(1,0)}$、$C=x^{(1,1)}$和$D=x^{(0,1)}$。以神經影像學作例子，當使用體素或具時間戳記的像素時，神經影像的圖像就會具有$d=3$或$d=4$的尺寸。

外部連結

關於積分圖的講座視頻

• 介紹積分圖像的算法背後的入門理論 （頁面存檔備份，存於網際網路檔案館）
• 一個示範積分圖像算法的連續版本，取自胡弗拉姆示範項目 （頁面存檔備份，存於網際網路檔案館）