积分图

积分图（Template:Lang en），又稱总和面积表（Template:Lang en，簡稱SAT），是一个快速且有效的对一个网格的矩形子区域中计算和的数据结构和算法。

歷史

积分图是于1984年由富兰克林·克罗引入计算机图形学领域，在20年后用于维奥拉-琼斯目标检测框架。富兰克林在設計积分图時主要是為Mipmap設計，但积分图并没有在计算机图形学领域中被广泛使用，直至在20年后，积分图才因维奥拉-琼斯目标检测框架的使用而開始普遍起來。然而，从历史角度來看，富兰克林對多维度的概率分布函数研究的理念是众所周知的，即透過觀察、計算各自的累积分布函数，以计算出二维 （或N維）概率（面积的概率分布）。

算法

积分图的每一点（x, y）的值是原图中对应位置的左上角区域的所有值得和：

$I(x,y)=\sum _{\begin{array}{c}{x}^{\prime }\le x\\ y^{\prime }\le y\end{array}}i(x^{\prime },y^{\prime })$

而且，积分图可以只遍历一次图像即可有效的计算出来，因为积分图每一点的（x, y）值是：

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

计算矩形阴影区域的值

一旦积分图计算完毕，对任意矩形区域的和的计算就可以在常数时间内完成。如右图中，阴影矩形区域的值：

$\sum _{\begin{array}{c}A(x)<x^{\prime }\le C(x)\\ A(y)<y^{\prime }\le C(y)\end{array}}i(x^{\prime },y^{\prime })=I(C)+I(A)-I(B)-I(D).$

扩展

这个方法可以自然的扩展到连续空间。

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

$\sum _{p\in \{0,1{\}}^d}(-1{)}^{d-\Vert p{\Vert }_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$的尺寸。

外部链接

關於积分图的讲座视频

• 介紹積分圖像的算法背後的入門理論 Template:Wayback
• 一個示範積分圖像算法的連續版本，取自胡弗拉姆示範項目 Template:Wayback