积分图

积分图（英語：integral image），又稱总和面积表（英語：summed area table，簡稱SAT）^[1]，是一个快速且有效的对一个网格的矩形子区域中计算和的数据结构和算法。^[2][3][4]

歷史

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

算法

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

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

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

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

 

计算矩形阴影区域的值

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

${\displaystyle \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).}$ 

扩展

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

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

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

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

参考文献

1. Franklin, Crow. (PDF). Computer Sciences Laboratory: Xerox Palo Alto Research Center. 1984年7月 [2013年1月3日]. （原始内容 (PDF)存档于2012年7月22日）. 
2. Patrick, Cozzi. Summed Area Tables (PDF). University of Pennsylvania. 1984年春 [2013年1月3日]. （原始内容 (PDF)于2016年9月10日）.  请检查|date=中的日期值 (帮助)
3. Justin, Hensley. Interactive Summed-Area Table (PDF). University of North Carolina at Chapel Hill. 2005年 [2013年1月3日]. （原始内容 (PDF)于2016年3月4日）. 
4. Simon, Green. Summed Area Tables (PDF). NVIDIA. [2013年1月3日]. （原始内容 (PDF)于2016年3月4日）. 
5. Finkelstein, Amir. Double Integrals By Summing Values Of Cumulative Distribution Function. Wolfram Demonstration Project. 2010年 [2013年1月3日]. （原始内容于2012年11月12日）. 
6. Crow, Franklin. (PDF). SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques: 207–212. 1984年 [2013年1月3日]. （原始内容 (PDF)存档于2011-06-04）. 
7. Viola, Paul; Jones, Michael. Robust Real-time Object Detection (PDF). International Journal of Computer Vision: 年. 2002 [2013年1月3日]. （原始内容 (PDF)于2007年2月24日）.  引文使用过时参数coauthors (帮助)
8. Finkelstein, Amir. Double Integrals By Summing Values Of Cumulative Distribution Function. Wolfram Demonstration Project. 2010 [2013年1月3日]. （原始内容于2012年11月12日）. 
9. Tapia, Ernesto. A note on the computation of high-dimensional integral images. Pattern Recognition Letters. January 2011, 32 (2). doi:10.1016/j.patrec.2010.10.007. 
10. Malcom Jeeves (1994). Mind Fields: Reflections on the Science of Mind and Brain. Grand Rapids, MI: Baker Books., p. 21

外部链接

關於积分图的讲座视频

• 介紹積分圖像的算法背後的入門理論 （页面存档备份，存于互联网档案馆）
• 一個示範積分圖像算法的連續版本，取自胡弗拉姆示範項目 （页面存档备份，存于互联网档案馆）