积分图

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

歷史

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

算法

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

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

计算矩形阴影区域的值

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

扩展

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

这个方法也可以扩展到高维图像中[9]。如果該矩形的角是,而的話,那麼矩形中包含圖像的值的總和就能以下列公式計算:

其中,是於的積分圖,而則是圖像尺寸。與表示法對應的例子有。以神經影像學作例子,當使用體素或具時間戳記的像素時,神經影像的圖像就會具有的尺寸。[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. (PDF). University of Pennsylvania. 1984年春 [2013年1月3日]. (原始内容存档 (PDF)于2016年9月10日).
  3. Justin, Hensley. (PDF). University of North Carolina at Chapel Hill. 2005年 [2013年1月3日]. (原始内容存档 (PDF)于2016年3月4日).
  4. Simon, Green. (PDF). NVIDIA. [2013年1月3日]. (原始内容存档 (PDF)于2016年3月4日).
  5. Finkelstein, Amir. . . 2010年 [2013年1月3日]. (原始内容存档于2012年11月12日).
  6. Crow, Franklin. (PDF). : 207–212. 1984年 [2013年1月3日]. (原始内容 (PDF)存档于2011-06-04).
  7. Viola, Paul; Jones, Michael. (PDF). : 年. 2002 [2013年1月3日]. (原始内容存档 (PDF)于2007年2月24日).
  8. Finkelstein, Amir. . . 2010 [2013年1月3日]. (原始内容存档于2012年11月12日).
  9. Tapia, Ernesto. . 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

外部链接

關於积分图的讲座视频
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.