查看“︁积分图”︁的源代码

'''积分图'''（{{lang en|'''integral image'''}}），又稱总和面积表（{{lang en|'''summed area table'''}}，簡稱'''SAT'''）<ref>
{{cite web
  | first = Crow
  | last = Franklin
  | publisher = Computer  Sciences Laboratory: Xerox  Palo  Alto Research  Center
  | title = Summed-Area Tables for Texture Mapping
  | date = 1984年7月
  | url = http://classes.soe.ucsc.edu/cmps160/Fall05/papers/p207-crow.pdf
  | accessdate = 2013年1月3日
  | archive-url = https://web.archive.org/web/20120722020229/http://classes.soe.ucsc.edu/cmps160/Fall05/papers/p207-crow.pdf
  | archive-date = 2012年7月22日
  | dead-url = yes
  }}
</ref>，是一个快速且有效的对一个网格的矩形子区域中计算和的数据结构和算法。<ref>{{cite web
 |first        = Cozzi
 |last         = Patrick
 |publisher    = University of Pennsylvania
 |title        = Summed Area Tables
 |date         = 1984年春
 |url          = http://www.seas.upenn.edu/~cis565/Lectures2011/Lecture15_SAT.pdf
 |accessdate   = 2013年1月3日
 |archive-date = 2016年9月10日
 |archive-url  = https://web.archive.org/web/20160910201527/http://www.seas.upenn.edu/~cis565/Lectures2011/Lecture15_SAT.pdf
 |dead-url     = no
}}</ref><ref>{{cite web
 |first        = Hensley
 |last         = Justin
 |publisher    = University of North Carolina at Chapel Hill
 |title        = Interactive Summed-Area Table
 |date         = 2005年
 |url          = http://developer.amd.com/wordpress/media/2012/10/SATsketch-siggraph05.pdf
 |accessdate   = 2013年1月3日
 |archive-date = 2016年3月4日
 |archive-url  = https://web.archive.org/web/20160304190542/http://developer.amd.com/wordpress/media/2012/10/SATsketch-siggraph05.pdf
 |dead-url     = no
}}</ref><ref>{{cite web
  | first =  Green
  | last =  Simon
  | publisher =  NVIDIA
  | title =  Summed Area Tables
  | date =  
  | url =  http://www.nvidia.com/docs/IO/8227/GDC2003_SummedAreaTables.pdf
  | accessdate =  2013年1月3日
  | archive-date =  2016年3月4日
  | archive-url =  https://web.archive.org/web/20160304111216/http://www.nvidia.com/docs/IO/8227/GDC2003_SummedAreaTables.pdf
  | dead-url =  no
  }}</ref>

==歷史==
积分图是于1984年由[[富兰克林·C·克罗|富兰克林·克罗]]引入计算机图形学领域，在20年后用于[[维奥拉-琼斯目标检测框架]]。富兰克林在設計积分图時主要是為[[Mipmap]]設計，但积分图并没有在计算机图形学领域中被广泛使用，直至在20年后，积分图才因维奥拉-琼斯目标检测框架的使用而開始普遍起來。然而，从历史角度來看，富兰克林對多维度的概率分布函数研究的理念是众所周知的，即透過觀察、計算各自的累积分布函数，以计算出二维 （或N維）概率（面积的概率分布）。<ref>{{cite conference
  | first = Amir
  | last = Finkelstein
  | authorlink = 
  | coauthors = 
  | title = Double Integrals By Summing Values Of Cumulative Distribution Function
  | booktitle = Wolfram Demonstration Project
  | pages = 
  | year = 2010年
  | url = http://demonstrations.wolfram.com/DoubleIntegralsBySummingValuesOfACumulativeDistributionFunct/
  | accessdate = 2013年1月3日
  | archive-date = 2012年11月12日
  | archive-url = https://web.archive.org/web/20121112102416/http://demonstrations.wolfram.com/DoubleIntegralsBySummingValuesOfACumulativeDistributionFunct/
  | dead-url = no
  }}</ref>

==算法==

积分图的每一点（''x'',&nbsp;''y''）的值是原图中对应位置的左上角区域的所有值得和：<ref>{{cite conference
 |first        = Franklin
 |last         = Crow
 |authorlink   = 
 |coauthors    = 
 |title        = Summed-area tables for texture mapping
 |booktitle    = SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques
 |pages        = 207–212
 |year         = 1984年
 |url          = http://www.soe.ucsc.edu/classes/cmps160/Fall05/papers/p207-crow.pdf
 |accessdate   = 2013年1月3日
 |archive-url  = https://web.archive.org/web/20110604205527/http://www.soe.ucsc.edu/classes/cmps160/Fall05/papers/p207-crow.pdf
 |archive-date = 2011-06-04
 |dead-url     = yes
}}</ref>
<ref>{{cite conference
  | first = Paul
  | last = Viola
  | authorlink = 
  | coauthors = Jones, Michael
  | title = Robust Real-time Object Detection
  | booktitle = International Journal of Computer Vision
  | pages = 年
  | year = 2002
  | url = http://research.microsoft.com/~viola/Pubs/Detect/violaJones_IJCV.pdf
  | accessdate = 2013年1月3日
  | archive-date = 2007年2月24日
  | archive-url = https://web.archive.org/web/20070224120909/http://research.microsoft.com/~viola/Pubs/Detect/violaJones_IJCV.pdf
  | dead-url = no
  }}</ref>
 
: <math> I(x,y) = \sum_{\begin{smallmatrix} x' \le x \\ y' \le y\end{smallmatrix}} i(x',y')</math>

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

: <math> I(x,y) = i(x,y) + I(x-1,y) + I(x,y-1) - I(x-1,y-1)\,</math>
[[File:Prm VJ fig3 computeRectangleWithAlpha.png|thumb|right|计算矩形阴影区域的值]]

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

: <math>\sum_{\begin{smallmatrix} A(x) < x' \le C(x) \\ A(y) < y' \le C(y) \end{smallmatrix}} i(x',y') = I(C) + I(A) - I(B) - I(D).</math>

==扩展==
这个方法可以自然的扩展到连续空间<ref>{{cite conference
  | first = Amir
  | last = Finkelstein
  | authorlink = 
  | coauthors = 
  | title = Double Integrals By Summing Values Of Cumulative Distribution Function
  | booktitle = Wolfram Demonstration Project
  | pages = 
  | year = 2010
  | url = http://demonstrations.wolfram.com/DoubleIntegralsBySummingValuesOfACumulativeDistributionFunct/
  | accessdate = 2013年1月3日
  | archive-date = 2012年11月12日
  | archive-url = https://web.archive.org/web/20121112102416/http://demonstrations.wolfram.com/DoubleIntegralsBySummingValuesOfACumulativeDistributionFunct/
  | dead-url = no
  }}</ref>。

这个方法也可以扩展到高维图像中<ref>{{cite journal|last=Tapia|first=Ernesto|title=A note on the computation of high-dimensional integral images|journal=Pattern Recognition Letters|volume=32|issue=2|doi=10.1016/j.patrec.2010.10.007|date=January 2011}}</ref>。如果該矩形的角是<math>x^p</math>，而<math>p</math>是<math>\{0,1\}^d</math>的話，那麼矩形中包含圖像的值的總和就能以下列公式計算：

: <math> \sum_{p\in\{0,1\}^d }(-1)^{d-\|p\|_1} I(x^p) \,</math>

其中，<math>I(x)</math>是於<math>x</math>的積分圖，而<math>d</math>則是圖像尺寸。與表示法<math>x^p</math>對應的例子有<math>d=2</math>、<math>A=x^{(0,0)}</math>、<math>B=x^{(1,0)}</math>、<math>C=x^{(1,1)}</math>和<math>D=x^{(0,1)}</math>。以[[神經影像學]]作例子，當使用[[體素]]或具時間戳記的像素時，神經影像的圖像就會具有<math>d=3</math>或<math>d=4</math>的尺寸。<ref>Malcom Jeeves (1994). ''Mind Fields: Reflections on the Science of Mind and Brain''. Grand Rapids, MI: Baker Books., p. 21</ref>

==参考文献==
{{reflist}}

==外部链接==
; 關於积分图的讲座视频:
* [http://www.youtube.com/watch?v=mM5JY-Q6hiM 介紹積分圖像的算法背後的入門理論] {{Wayback|url=http://www.youtube.com/watch?v=mM5JY-Q6hiM |date=20110826234153 }}
* [http://www.youtube.com/watch?v=-SI117NdjJ8 一個示範積分圖像算法的連續版本，取自胡弗拉姆示範項目] {{Wayback|url=http://www.youtube.com/watch?v=-SI117NdjJ8 |date=20150704205412 }}

[[Category:數位幾何學]]
[[Category:計算機圖形數據結構]]