跳转到内容

积分图

维基百科,自由的百科全书

积分图(英语:integral image),又称总和面积表(英语:summed area table,简称SAT[1],是一个快速且有效的对一个网格的矩形子区域中计算和的数据结构和算法。[2][3][4]

历史

[编辑]

积分图是于1984年由富兰克林·克罗引入计算机图形学领域,在20年后用于维奥拉-琼斯目标检测框架。富兰克林在设计积分图时主要是为Mipmap设计,但积分图并没有在计算机图形学领域中被广泛使用,直至在20年后,积分图才因维奥拉-琼斯目标检测框架的使用而开始普遍起来。然而,从历史角度来看,富兰克林对多维度的概率分布函数研究的理念是众所周知的,即透过观察、计算各自的累积分布函数,以计算出二维 (或N维)概率(面积的概率分布)。[5]

算法

[编辑]

积分图的每一点(xy)的值是原图中对应位置的左上角区域的所有值得和:[6] [7]

而且,积分图可以只遍历一次图像即可有效的计算出来,因为积分图每一点的(xy)值是:

计算矩形阴影区域的值

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

扩展

[编辑]

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

这个方法也可以扩展到高维图像中[9]。如果该矩形的角是,而的话,那么矩形中包含图像的值的总和就能以下列公式计算:

其中,是于的积分图,而则是图像尺寸。与表示法对应的例子有。以神经影像学作例子,当使用体素或具时间戳记的像素时,神经影像的图像就会具有的尺寸。[10]

参考文献

[编辑]
  1. ^ Franklin, Crow. Summed-Area Tables for Texture Mapping (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日). 
  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. Summed-area tables for texture mapping (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日). 
  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

外部链接

[编辑]
关于积分图的讲座视频