積分圖
積分圖(英語:integral image),又稱總和面積表(英語:summed area table,簡稱SAT)[1],是一個快速且有效的對一個網格的矩形子區域中計算和的數據結構和算法。[2][3][4]
歷史
積分圖是於1984年由富蘭克林·克羅引入計算機圖形學領域,在20年後用於維奧拉-瓊斯目標檢測框架。富蘭克林在設計積分圖時主要是為Mipmap設計,但積分圖並沒有在計算機圖形學領域中被廣泛使用,直至在20年後,積分圖才因維奧拉-瓊斯目標檢測框架的使用而開始普遍起來。然而,從歷史角度來看,富蘭克林對多維度的概率分佈函數研究的理念是眾所周知的,即透過觀察、計算各自的累積分佈函數,以計算出二維 (或N維)概率(面積的概率分佈)。[5]
算法
積分圖的每一點(x, y)的值是原圖中對應位置的左上角區域的所有值得和:[6] [7]
而且,積分圖可以只遍歷一次圖像即可有效的計算出來,因為積分圖每一點的(x, y)值是:
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/e/ee/Prm_VJ_fig3_computeRectangleWithAlpha.png/220px-Prm_VJ_fig3_computeRectangleWithAlpha.png)
一旦積分圖計算完畢,對任意矩形區域的和的計算就可以在常數時間內完成。如右圖中,陰影矩形區域的值:
擴展
這個方法可以自然的擴展到連續空間[8]。
這個方法也可以擴展到高維圖像中[9]。如果該矩形的角是,而是的話,那麼矩形中包含圖像的值的總和就能以下列公式計算:
其中,是於的積分圖,而則是圖像尺寸。與表示法對應的例子有、、、和。以神經影像學作例子,當使用體素或具時間戳記的像素時,神經影像的圖像就會具有或的尺寸。[10]
參考文獻
- ^ 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日).
- ^ Patrick, Cozzi. Summed Area Tables (PDF). University of Pennsylvania. 1984年春 [2013年1月3日]. (原始內容存檔 (PDF)於2016年9月10日).
- ^ Justin, Hensley. Interactive Summed-Area Table (PDF). University of North Carolina at Chapel Hill. 2005年 [2013年1月3日]. (原始內容存檔 (PDF)於2016年3月4日).
- ^ Simon, Green. Summed Area Tables (PDF). NVIDIA. [2013年1月3日]. (原始內容存檔 (PDF)於2016年3月4日).
- ^ Finkelstein, Amir. Double Integrals By Summing Values Of Cumulative Distribution Function. Wolfram Demonstration Project. 2010年 [2013年1月3日]. (原始內容存檔於2012年11月12日).
- ^ 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).
- ^ Viola, Paul; Jones, Michael. Robust Real-time Object Detection (PDF). International Journal of Computer Vision: 年. 2002 [2013年1月3日]. (原始內容存檔 (PDF)於2007年2月24日).
- ^ Finkelstein, Amir. Double Integrals By Summing Values Of Cumulative Distribution Function. Wolfram Demonstration Project. 2010 [2013年1月3日]. (原始內容存檔於2012年11月12日).
- ^ 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.
- ^ Malcom Jeeves (1994). Mind Fields: Reflections on the Science of Mind and Brain. Grand Rapids, MI: Baker Books., p. 21
外部連結
- 關於積分圖的講座視頻