第四章 門檻值決定與區域的分割.

Presentation on theme: "第四章 門檻值決定與區域的分割."— Presentation transcript:

1 第四章 門檻值決定與區域的分割

2 內容 4.1 前言 4.2 統計式門檻值決定法 4.3 消息理論為基礎的門檻值決定法 4.4 動差守恆式的門檻值決定法
4.5 植基於最近配對門檻值決定法 4.6 分離與合併式的區域分割法 4.7 分水嶺式的區域分割法

3 4.1 前言 針對門檻值的決定，介紹下列的四種方法： 統計式 消息理論式 動差守恆式 最佳配對式 針對區域分割，介紹下列的二種方法：
分離與合併式 分水嶺式

4 4.2 統計式門檻值決定法 視覺選取法(Visual Selection) 如圖4.2.1所示，柱狀圖有時也稱作直方圖。
在圖4.2.1中，波谷處(Vally) 很適合選為門檻值。 圖 灰階分佈柱狀圖

5 範例1：舉一個視覺選取法不適合的灰階分佈柱狀圖。
解答：

6 範例1.1：給如下兩張影像： 25 5 35 15 10 40 20 30 45 50 20 15 40 55 50 10 45 5 35 25 30 (a) (b) 若我們想把影像分成兩群，請說明那張影像不適合使用視覺選取法決定門檻值，並分析原因，另外，請指出那張影像適合使用視覺選取法決定門檻值，並且找出其門檻值T*。

7 解答： (a)這張影像不適合用視覺法選取門檻值，而(b)影像因為有單一明顯波谷，所以適合用視覺法選取門檻值，且門檻值 T* 為30。
圖1 圖2 解答： (a)這張影像不適合用視覺法選取門檻值，而(b)影像因為有單一明顯波谷，所以適合用視覺法選取門檻值，且門檻值 T* 為30。 解答完畢

8 Otsu法 條件一： 的決定，使得 和 之間的變異數為最大。 條件二： 的決定，使得 內的變異數加上 內的變異數之和為 最小。
條件一： 的決定，使得 和 之間的變異數為最大。 條件二： 的決定，使得 內的變異數加上 內的變異數之和為 最小。 條件一： 的決定，使得 和 之間的變異數為最大。 條件二： 的決定，使得 內的變異數加上 內的變異數之和為 最小。 以上條件只要任一者成立即可。 圖 二區的例子

9 令影像的大小為N，且灰階值個數為I=256。則灰階值為i的
機率可表示為 內的像素個數佔的比率為  內的像素個數佔的比率為 的期望值為  的期望值為 的變異數為  的變異數為

10 和 內變異數和為  和 間的變異數為 此 表整個原始影像的平均值：

11 圖 窗戶影像 圖 利用Otsu方法得到的黑白影像 Otsu法需花 時間。

12 範例2：已知T*所對應的C1 之期望值為 ，試問如何快速求得T* +1 所對應的期望值 ？
事實上， 的求得必須先求出 和 。我們 可順便記住 和 這兩個值，因此 可在 O(1) 的時間內求得。 解答完畢

13 T* +1所對應的變異數可計算如下： 上式中的 為已知，而 亦為已知。 事實上， 和 在求 的過程中皆可先儲存起來。已知 可在O(1) 時間內完成，故變異數可在O(1) 的時間內完成。

14 範例4：利用Otsu法找出其門檻值T*。 20 120 100 30 40 解答：

15 由上述可知T*=40時， 群間變異數會達到最大，因此40最適合門檻值
解答完畢

16 圖4. 2. 5(a)為台電公司的某一座鐵塔，影像中物件包含鐵塔和天空。利用Otsu方法，我們得到圖4. 2
圖4.2.5(a)為台電公司的某一座鐵塔，影像中物件包含鐵塔和天空。利用Otsu方法，我們得到圖4.2.5(b)的二值化影像，二值化影像中黑色的部份代表鐵塔本身。 (a) 原鐵塔影像 (b) 二值化後的鐵塔 圖4.2.5　將灰階影像轉化為二值化影像的鐵塔實例

17 4.3 消息理論為基礎的門檻值決定法 消息理論 令事件A的機率為P，而事件A帶來的消息量為I(P)，具兩性質： (1) ，(2) 。 
(1) ，(2) 。 消息理論 平均消息量-熵(Entropy)  例如：P(A)=1/4、P(B)=1/8、P(C)=1/8和P(D)=1/2，則事件A的消 息量為I(1/4)=2、B的消息量為I(1/8)=3、C的消息量為I(1/8)=3 和D的消息量為I(1/2)=1。 P(A)×I(1/4)+P(B)×I(1/8)+P(C)×I(1/8)+P(D)×I(1/2) =(1/4)×2+(1/8)×3+(1/8)×3+(1/2)×1= (bits)

18 Kapur法 令 區的百分比為 而 區的百分比為  最佳門檻值 的決定需滿足 (4.3.1) 圖4.2.2 二區的例子
令 區的百分比為 而 區的百分比為  最佳門檻值 的決定需滿足 (4.3.1) 圖 二區的例子 圖 利用Kapur法測得的黑白影像 圖 Otus和Kapur法找到的門檻值 Otsu方法 Kapur方法

19 範例1：在Kapur法中，為何要取兩個熵和之最大值?
解答： 如果選定的門檻值很不錯的話，那麼C1區的分佈和C2區的分佈將呈現比較平滑的情形。機率分佈愈平滑的事件集所表現出來的熵會愈大。 解答完畢

20 範例2：利用Kapur法找出其門檻值T*把影像分成兩群。
200 120 80 150 30 解答：先對影像灰階值做統計且其機率分佈如下

21 解答完畢

22 4.4 動差守恆式的門檻值決定法 本節介紹的方法是在 區找一個代表性的灰階值而在 區找另一個代表性的灰階值，以滿足某些動差的守恆性。 令
本節介紹的方法是在 區找一個代表性的灰階值而在 區找另一個代表性的灰階值，以滿足某些動差的守恆性。 令 代表影像的i階動差 代表影像的大小 代表在影像中灰階值為 的個數 一個例子 圖 一個小例子

23 高灰階影像轉換為二階灰階影像，考慮機率和為1的動差守恆的要求
得到四個式子 依下列三個步驟求解 、 、 、 ： 步驟一：解下列2×2的線性系統

24 步驟二：解出一元二次方程式 的根，假設得
出的解為 和 ，此兩解即為 區和 區的灰階代表值。 步驟三：解下列的線性系統 利用前述三步驟的數值解法，我們可解出 、 、 和 。接著我們將原影像中的灰階值小於或等於g的灰階值指定為 ，這 裡的g要滿足 但 。原影像中的灰階值大於g的則 指定 。最後，我們得到只有 和 兩種灰階的影像。這時候，轉換後的二階影像和原影像有同樣的 、 、 和 。

25 範例1：在動差守恆式的門檻值決定法中，考慮K階時，請列出相關的2K個等式。

26 4.5 植基於最近配對門檻值決定法 PNN(Pairwise Nearest Neighbor) 令 i代表灰階值
為所有灰階的總數 圖 N=100的例子

27 PNN合併的量度與條件 這裡採用的量度稱為平方誤差(Square Error)， 和 代表 和 的平均值， 和 合併後得到 。
一開始每個節點(Node)內存 的值並自成一個群(Cluster)。例如，節點0內存(10,10)、節點1內存(25,20)而節點6內存(90,10)。 圖4.5.2 緊緻柱狀圖 PNN合併的量度與條件 這裡採用的量度稱為平方誤差(Square Error)， 和 代表 和 的平均值， 和 合併後得到 。 假如 愈小，則表示 和 的關聯度(Correlation)愈高。

28 (3) 修正合併後的群內資訊及調整對外距離，直到剩下K+1個群。 (1) 找出目前剩餘群組中最短的
(a) 起始 (b) 算出的七個最短距離 (c) 找出最短距離 (d) 合併與修正 圖 第一次合併的模擬 合併的三個步驟： (3) 修正合併後的群內資訊及調整對外距離，直到剩下K+1個群。 (1) 找出目前剩餘群組中最短的 (2) 合併 和

29 i 最近鄰近群 平均灰階值 最大灰階值 最近距離 群內的圖元總數 1 10 1500 2 25 278 20 3 30 234 35 15 4 5 80 94 85 6 90 150 圖4.5.4 (a) 圖4.5.3(b) 的表格表示法

30 i 最近鄰近群 平均灰階值 最大灰階值 最近距離 群內的圖元總數 1 10 1500 2 25 278 20 3 30 234 35 15 4 6 83.75 85 260 90 圖4.5.4 (b) 圖4.5.3(d) 的表格表示法

31 時間複雜度 步驟(1)需花O(m)找到目前群組中最短的距離。步驟(2)需花O(1)的時間修正合併後的群內資訊。步驟(3)需花 的時間來修正每個群和別群的最短距離計算，這裡 。 由於兩群之間的合併會使其中一群不見，所以每次的合併會使群的個數少一。我們從開始的m群出發，一直進行到只剩(k+1)群一共需完成(m-k-1)次的合併動作。一個合併步驟前後又共需三個步驟來完成，所以共需 的時間。 Otsu方法 Kapur方法 PNN方法 K=1 K>1

32 (a)輸入的文件影像 (b)Otsu法執行後的結果 圖 三種方法的比較 (c)Kapur法執行後的結果 (d)PNN法執行後的結果

33 4.6 分離與合併式的區域分割法 四分樹分割 I R1 R2 R3 R4 R41 R42 R43 R44  (a)區塊圖 (b)四分樹結構 圖 區域分割圖 圖 初始的分離狀態 由下往上，從最底層的葉子進行鄰近區塊的查詢，一經找到鄰近的區塊就比較兩者的平均灰階值和變異數，若彼此的差異在誤差內，就進行合併的動作。

34 首先將N×N的影像看成已分離成N×N個小區塊：
另一不同的合併次序 首先將N×N的影像看成已分離成N×N個小區塊： 第一行和第一列，將該區塊和右邊的鄰近區塊比較彼此的平均灰階值差異和變異數差異，若差異過小，則合併成一個區塊。 第二列以後，考慮中位於(i,j)的像素和四個鄰近區塊的平均灰階值和變異數小於門檻值，則進行合併。 圖 四個鄰近區塊

35 範例1:何謂二階段式的區域分割法 解答: a b c d e e d c b a 第一階段的面罩 第二階段的面罩

36

37

38 4.7 分水嶺式的區域分割法 改良式分水嶺區域分割法 圖4.7.1中共有六個局部最小值和五個虛線所示的分水嶺。
兩個分水嶺所夾的區域可視為分割的區域，局部最小值所在乃左右水流匯集之處。 灰階值 位置 圖 區域、局部最小值和分水嶺

39

40 我們再來看看標準差變大導致打糊範圍擴大，其對區域合併的效果。圖4. 7
我們再來看看標準差變大導致打糊範圍擴大，其對區域合併的效果。圖4.7.4為由小變大的四個例子演變圖。給一Lena灰階影像，利用本節介紹的分水嶺式區域分割法，我們實驗後得到圖4.7.5的結果。 圖 標準差逐漸變大的四個演變圖 圖 Lena影像的區域分割效果圖