策略模式在圖像分割中的應用

1 基本概念
1．1 圖像分割定義
借助集合概念對圖像分割可給出如下的定義：令集合R代表整個圖像區(qū)域，對R的分割可看作將R分成N個子區(qū)域Rl，R2，…RN的過程：
(a)URi=R；
(b)讀所有的i和j，i≠j，有Ri∩Rj=φ；
(c)對i=l，2，…，N，有P(Ri)=TRUE；
(d)對i≠j，有P(Ri∪Rj)=FALSE；
(e)對i=1，2，…，N，Ri是連通的區(qū)域。
其中P(Ri)是對所有在集合Ri元素的邏輯謂詞，φ代表空集。
對圖像的分割總是根據(jù)一些分割準則進行的。條件(a)說明分割必須是完全的；即，每個象素必須屬于一個區(qū)域。條件(b)要求區(qū)域中的點必須與某個預定義的準則相聯(lián)系。條件(c)說明不同區(qū)域必須是不相交的。條件(d)涉及在分割區(qū)域內必須滿足的性質――例如如果所有Ri內的像素有相同的灰度級，則P(Ri)=TRUE。條件(e)說明區(qū)域Ri和Rj對于謂詞P是不同的。
1．2 Strategy模式
按照四人團的說法，Strategy模式的意圖是：定義一系列的算法，把它們一個個封裝起來，并且使它們可相互替換，本模式使算法可獨立于使用它們的客戶而變化。將算法的選擇和算法的實現(xiàn)相分離，讓客戶可以基于場景作出選擇。

2 典型算法
2．1 邊緣檢測邊界閉合法
為將圖像中不同的區(qū)域分開，需要將邊緣象素連接起來組成區(qū)域的封閉邊界。邊緣檢測算子都是并行工作的，如果邊界閉合也能并行完成，則分割基本上可以并行實現(xiàn)。邊緣象素連接的基礎是它們的梯度之間有一定的相似性。用梯度算子對圖象處理可得到象素兩方面的信息：1)梯度的幅度；2)梯度的方向。結合邊緣象素梯度在這兩方面的相似性可把邊緣象素如下連接起來。具體說來如果象素(s，t)在象素(x，y)的領域且它們的梯度幅度和梯度方向分別滿足以下兩個條件(其中T是幅度閾值，A是角度閾值)：

那么就可將(s，t)的象素與在(x，y)的象素連接起來。如對所有邊緣象素都進行這樣的判斷和連接就有希望得到閉合的邊界。
2．2 動態(tài)規(guī)劃輪廓搜索法
動態(tài)規(guī)劃是一個多步?jīng)Q策過程，它通過把一個N步過程化為N個單步過程的方法使算法的復雜性按對數(shù)律降低。根據(jù)動態(tài)規(guī)劃的原理，可將全局最優(yōu)化成局部最優(yōu)之和。動態(tài)規(guī)劃輪廓搜索法是：
令r(n)為從起始結點s出發(fā)經(jīng)過當前結點n到達目標結點g的最小代價通路的估計代價。這個估計代價可以表示成兩個代價之和，即從起始結點s到當前結點n的最小代價通路的估計代價t(n)以及從當前結點n到目標結點g的通路的估計代價h(n)之和：
r(n)=t(n)+h(n)
這里t(n)可取為目前從結點s到結點n的最小代價通路，h(n)可借助某些啟發(fā)性知識得到。常用的啟發(fā)性知識包括通路的方向性(是否指向搜索的終點)，光滑性(可通過曲率計算來估計)以及代價估計。代價的計算可參照前面的方法。根據(jù)r(n)=t(n)+h(n)進行圖搜索的搜索算法(稱為A*算法)由以下幾個步驟構成：
1)將起始結點標記為OPEN并置t(s)=0；
2)如果沒有結點為OPEN，失敗退出，否則繼續(xù)；
3)將r(n)=t(n)+h(n)算得的估計代價r(n)為最小的OPEN結點標記為CLOSE；
4)如果n是目標結點，找到通路退出，否則繼續(xù)；
5)展開結點n，得到它的所有子結點(如果沒有子結點，返回步驟2))；
6)如果某個子結點ni還沒有標記，置r(ni)=t(n)十c(n，ni)，標記它為OPEN并將指向它的指針返回到結點n；