Just a Computer Graphics Studio & My Life

積分直方圖 (Integral Histogram)

跟上次介紹的積分影像 (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)

  1. 挺神的東西

    喜歡

發表留言

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s

標籤雲

%d 位部落客按了讚: