门槛值决定与区域的分割.ppt

* 時間複雜度 步驟(1)需花O(m)找到目前群組中最短的距離。步驟(2)需花O(1)的時間修正合併後的群內資訊。步驟(3)需花 的時間來修正每個群和別群的最短距離計算，這裡 。 由於兩群之間的合併會使其中一群不見，所以每次的合併會使群的個數少一。我們從開始的m群出發，一直進行到只剩(k+1)群一共需完成(m-k-1)次的合併動作。一個合併步驟前後又共需三個步驟來完成，所以共需 的時間。 Otsu方法 Kapur方法 PNN方法 K=1 K1 * (a)輸入的文件影像 (b)Otsu法執行後的結果 (c)Kapur法執行後的結果 (d)PNN法執行後的結果 圖4.5.5 三種方法的比較 * 4.6 分離與合併式的區域分割法 I R1 R2 R3 R4 R41 R42 R43 R44 (a)區塊圖 (b)四分樹結構 圖4.6.1 初始的分離狀態 圖4.6.2 區域分割圖 ? 四分樹分割 由下往上，從最底層的葉子進行鄰近區塊的查詢，一經找到鄰近的區塊就比較兩者的平均灰階值和變異數，若彼此的差異在誤差內，就進行合併的動作。 * 圖4.6.3 四個鄰近區塊 另一不同的合併次序 首先將N×N的影像看成已分離成N×N個小區塊： ?第一行和第一列，將該區塊和右邊的鄰近區塊比較彼此的平均灰階值差異和變異數差異，若差異過小，則合併成一個區塊。 ?第二列以後，考慮中位於(i,j)的像素和四個鄰近區塊的平均灰階值和變異數小於門檻值，則進行合併。 範例1:何謂二階段式的區域分割法解答: * a b c d e e d c b a 第一階段的面罩 第二階段的面罩 * * * 4.7 分水嶺式的區域分割法 圖4.7.1 區域、局部最小值和分水嶺 位置 灰階值 改良式分水嶺區域分割法 圖4.7.1中共有六個局部最小值和五個虛線所示的分水嶺。 兩個分水嶺所夾的區域可視為分割的區域，局部最小值所在乃左右水流匯集之處。 * * 圖4.7.4 標準差逐漸變大的四個演變圖 圖4.7.5 Lena影像的區域分割效果圖 我們再來看看標準差變大導致打糊範圍擴大，其對區域合併的效果。圖4.7.4為由小變大的四個例子演變圖。給一Lena灰階影像，利用本節介紹的分水嶺式區域分割法，我們實驗後得到圖4.7.5的結果。 * 第四章門檻值決定與區域的分割 * 內容 4.1 前言 4.2 統計式門檻值決定法 4.3 消息理論為基礎的門檻值決定法 4.4 動差守恆式的門檻值決定法 4.5 植基於最近配對門檻值決定法 4.6 分離與合併式的區域分割法 4.7 分水嶺式的區域分割法 * 4.1 前言 針對門檻值的決定，介紹下列的四種方法： 統計式 消息理論式 動差守恆式 最佳配對式 針對區域分割，介紹下列的二種方法： 分離與合併式 分水嶺式 * 4.2 統計式門檻值決定法 視覺選取法(Visual Selection) 如圖4.2.1所示，柱狀圖有時也稱作直方圖。 在圖4.2.1中，波谷處(Vally) 很適合選為門檻值。 圖4.2.1 灰階分佈柱狀圖 * 範例1：舉一個視覺選取法不適合的灰階分佈柱狀圖。 解答： * 範例1.1：給如下兩張影像： 20 15 40 55 50 10 45 10 5 45 35 40 25 45 20 10 15 20 35 55 50 55 45 25 50 15 40 30 5 40 15 20 10 45 15 50 25 5 35 15 10 40 10 40 20 30 40 15 45 15 5 25 10 35 50 30 45 20 50 30 30 45 15 25 5 20 10 25 40 35 50 45 (a) (b) 若我們想把影像分成兩群，請說明那張影像不適合使用視覺選取法決定門檻值，並分析原因，另外，請指出那張影像適合使用視覺選取法決定門檻值，並且找出其門檻值T*。 * 圖1 圖2 解答： (a)這張影像不適合用視覺法選取門檻值，而(b)影像因為有單一明顯波谷，所以適合用視覺法選取門檻值，且門檻值 T* 為30。 解答完畢 * 條件一： 的決定，使得 和 之間的變異數為最大。 條件二： 的決定，使得 內的變異數加上 內的變異數之和為 最小。 條件一： 的決定，使得 和 之間的變異數為最大。 條件二： 的決定