跟上次介紹的積分影像 (Integral Image)很像，積分直方圖 (Integral Histogram)有異曲同工之妙，都是dynamic programming的一種計算值的方法，可重複利用過去已計算過的值，來獲得未來所需要的值，這種DP技巧可以減少相當多的計算量，進而達到加速的目的。
我們簡單看上圖解釋，x軸為gray level，值介於[0, 255]，y軸為occurrence，值也就是出現次數。
以此圖為例，H(10, 10)代表從(0, 0)到(10, 10)的直方圖，後面的數字occurrence[6 10 13 9 13 11 10 8 9 11]表示gray level[0 1 2 3 4 5 6 7 8 9]在區域裡出現的次數。
以下給兩個例子，讓我們的目的明朗化：
我們可以明顯從顏色瞭解計算過程，藍底區域就是我們的目標積分直方圖 (Integral Histogram)，虛線顏色區域表示為已知積分直方圖，經加加減減後得到藍底區域。
時間複雜度為O(1)，因為4個積分直方圖查表即可獲得！
那麼我們該如何建立「表」？
跟積分影像 (Integral Image)一樣使用dynamic programming技巧，逐步（row major或col major都可）處理整張影像每個pixel。
很感謝葉梅珍老師辛苦做出來的投影片，把概念表達得相當清楚！
參考：多媒體系統設計投影片 – Generic object detection。
逍遙文工作室 
Comments on: "積分直方圖 (Integral Histogram)" (1)
挺神的東西
讚讚