MRF圖像分割(增刪)

1、馬爾科夫與圖像處理基于馬爾代夫隨機(jī)場(chǎng)的土象分割馬爾科夫n馬爾科夫隨機(jī)過程就是，下一個(gè)時(shí)間點(diǎn)的狀態(tài)只與當(dāng)前的狀態(tài)有關(guān)系，而與以前的狀態(tài)沒有關(guān)系，即未來(lái)的狀態(tài)決定于現(xiàn)在而不決定于過去。n其未來(lái)由現(xiàn)在決定的程度，使得我們關(guān)于過去的知識(shí)絲毫不影響這種決定性。這種在已知 “現(xiàn)在”的條件下，“未來(lái)”與“過去”彼此獨(dú)立的特性就被稱為馬爾科夫性，具有這種性質(zhì)的隨機(jī)過程就叫做馬爾科夫過程馬爾科夫過程0111100,11, ,|,|,nnnnnnnnnnnXnTnTi iiIP XiXiXiP XiXiXnT設(shè)有隨機(jī)過程若對(duì)于任意正整數(shù)和任意的條件概率滿足就稱為馬爾科夫過程，該隨機(jī)過程的統(tǒng)計(jì)特性完全由條件概率所決

2、定n例如：假定天氣是馬爾科夫的，其意思就是我們假設(shè)今天的天氣僅僅與昨天的天氣存在概率上的關(guān)聯(lián)，而與前天及前天以前的天氣沒有關(guān)系。其它如傳染病和謠言的傳播規(guī)律，都是馬爾科夫的。n荷花池里有N張荷葉，在時(shí)刻Tn時(shí)，Xn為時(shí)刻Tn青蛙所處的狀態(tài)。nP(Xn+1=j/Xn=i)=Pi,j , 其中，i,j=1,2,N. 表示在Tn時(shí)刻青蛙在第i張荷葉上。在下一個(gè)時(shí)刻Tn+1跳到第j張荷葉上的可能性，又稱為從狀態(tài)i經(jīng)一步轉(zhuǎn)移到j(luò)的概率，簡(jiǎn)稱為一步轉(zhuǎn)移概率。n將這些 Pi,j依序排列起來(lái)，就構(gòu)成一個(gè)矩陣，叫做轉(zhuǎn)移概率矩陣。n P11 P12 . P1n P = P21 P22 . P2n n .n Pn1

3、 Pn2 . Pnn馬爾科夫預(yù)測(cè)n例如：A,B,C三個(gè)廠生產(chǎn)的電腦上公司在某地區(qū)市場(chǎng)上的占有率分別為0.3， 0.2 ，0.5。根據(jù)市場(chǎng)調(diào)查得知、顧客的流動(dòng)情況如下： n A B C nA 0.4 0.3 0.3nB 0.6 0.3 0.1nC 0.6 0.1 0.3n市場(chǎng)的初始狀態(tài)為S(0)=(0.3,0.2,0.5)n轉(zhuǎn)移概率P為n 0.4 0.3 0.3n P = 0.6 0.3 0.1 n 0.6 0.1 0.3 n S(1)=S(0)*P=(0.54, 0.20, 0.26),這個(gè)月A,B,C電腦的市場(chǎng)占有率為54%,20%,26%nS(2)=S(1)*p=S(0)*P2=(0.49

4、2, 0.248, 0.26),下個(gè)月A,B,C電腦的市場(chǎng)占有率為49.2%，24.8%，26%n例如：我在不同天氣狀態(tài)下去做一些事情的概率不同，（觀察狀態(tài)）天氣狀態(tài)集合為下雨，陰天，晴天，（隱藏狀態(tài)）事情集合為宅著，自習(xí)，游玩。假如我們已經(jīng)有了轉(zhuǎn)移概率和輸出概率，即P(天氣A|天氣B)和P(事情a|天氣A)的概率都已知道，那么我們可以解決：n假如一周內(nèi)的天氣變化是 下雨-晴天-陰天-下雨-陰天-晴天-陰天，那么我這一周 自習(xí)-宅著-游玩-自習(xí)-游玩-宅著-自習(xí)的概率。n假如一周內(nèi)的天氣變化是 下雨-晴天-陰天-下雨-陰天-晴天-陰天，那我們這一周最有可能的做事序列。n這些可以通過隱馬爾科夫模

5、型得到結(jié)果。馬爾科夫隨機(jī)場(chǎng)馬爾科夫隨機(jī)場(chǎng)包含兩層意思n馬爾科夫性質(zhì)n隨機(jī)場(chǎng)隨機(jī)場(chǎng)n當(dāng)給每一個(gè)位置中按照某種分布隨機(jī)賦予相空間的一個(gè)值之后，其全體就叫做隨機(jī)場(chǎng)。其中有兩個(gè)概念：位置（site），相空間（phase space）。我們可以拿種地來(lái)打個(gè)比方?！拔恢谩焙帽仁且划€畝農(nóng)田；“相空間”好比是要種的各種莊稼。我們可以給不同的地種上不同的莊稼，這就好比給隨機(jī)場(chǎng)的每個(gè)“位置”，賦予相空間里不同的值。所以，隨機(jī)場(chǎng)就好比是在哪塊地里種什么莊稼的事情。 馬爾科夫隨機(jī)場(chǎng) 同樣拿種地打比方，如果任何一塊地里種的莊稼的種類僅僅與它鄰近的地里種的莊稼的種類有關(guān)，與其它地方的莊稼的種類無(wú)關(guān)，那么這些地里種的莊稼的

6、集合，就是一個(gè)馬爾可夫隨機(jī)場(chǎng)。 馬爾科夫隨機(jī)場(chǎng)與圖像的關(guān)系n一維馬爾科夫隨機(jī)過程很好的描述隨機(jī)過程中某點(diǎn)的狀態(tài)只與該點(diǎn)之前的一個(gè)點(diǎn)的狀態(tài)有關(guān)系。n對(duì)于定義在二維空間上的圖像，也可以將它看為一個(gè)二維隨機(jī)場(chǎng)。那么就存在二維馬爾科夫隨機(jī)場(chǎng),將時(shí)間上的馬爾科夫性轉(zhuǎn)換到空間上，考慮空間的關(guān)系,二維MRF的平面網(wǎng)格結(jié)構(gòu)可以較好的表現(xiàn)圖像中像素之間的空間相關(guān)性。馬爾科夫圖像模型nMRF 將圖像模擬成一個(gè)隨機(jī)變量組成的網(wǎng)格，其中的每一個(gè)變量對(duì)明確的對(duì)其自身之外的隨機(jī)變量組成的鄰近基團(tuán)具有依賴性。該模型考慮每個(gè)像元關(guān)于它的鄰近像元的條件分布，有效地描述圖像的局部統(tǒng)計(jì)特性。基本定義S( , )|1,1MNi ji

7、MjN 設(shè)表示位置的有限格點(diǎn)集即隨機(jī)場(chǎng)中的位置=1,2L，表示狀態(tài)空間，即隨機(jī)場(chǎng)中的相空間 圖像分割問題要求解的是滿足最大后驗(yàn)概率準(zhǔn)則的對(duì)每個(gè)像素的分類標(biāo)號(hào)，我們統(tǒng)一稱為標(biāo)號(hào)場(chǎng)，記為X。nxs ，表示在標(biāo)號(hào)場(chǎng)X上，狀態(tài)空間為的隱狀態(tài)隨機(jī)變量。12*( ,.,)MNsssXx xx在圖像中n格點(diǎn)集S表示像素的位置 nX稱為標(biāo)號(hào)場(chǎng)，也可以表示像素值的集合或圖像經(jīng)小波變換后的小波系數(shù)集合nL表示將圖像分割為不同區(qū)域的數(shù)目，即標(biāo)簽集合鄰域系統(tǒng)n隨機(jī)場(chǎng)（Random Filed）中，利用鄰域系統(tǒng)可以分析空間上的馬爾科夫性。一個(gè)像素點(diǎn)的特性，更可能受它周圍像素的影響，與它距離越遠(yuǎn)的像素，對(duì)它的特性的影響越

8、小。鄰域系統(tǒng)= ( )|SssS設(shè)是定義在 上的通用鄰域系統(tǒng)的集合，其滿足如下特性：(1) ( )(2)( )(3),( )( )( )s( )ssSsss rS srrsrss則位置稱作 的鄰點(diǎn)，稱作 的鄰點(diǎn)集分階鄰域系統(tǒng)與子團(tuán)在圖像模型中，可以根據(jù)對(duì)象元的距離建立一種分階鄰域系統(tǒng)，定義如下：( )( )( +1)( ) | ( , ),( )0,( )( )nnnsr d s rn rsndnss 式中 為鄰域系統(tǒng)的階次，表示距離函數(shù)，經(jīng)常使用歐氏距離，市區(qū)距離，棋盤距離等函數(shù)。對(duì)滿足特性基團(tuán) S中有不同的鄰域結(jié)構(gòu)，在S上由單個(gè)像元或由象元與其鄰點(diǎn)組成的子集 稱為一個(gè)基團(tuán)。子團(tuán)c的集合用C

9、來(lái)表示。cS分階鄰域系統(tǒng)與基團(tuán)示例SX=x ,s S1PX= 0, x(2) PX =x |,( )X =x |,( )XsssrrssrrXx rsrsPXxrs 設(shè) 為 上的鄰域系統(tǒng)，若隨機(jī)場(chǎng)滿足如下條件：（）x則稱 為以 為鄰域系統(tǒng)的馬爾科夫隨機(jī)場(chǎng)，上式稱為馬爾科夫隨機(jī)場(chǎng)的局部特性馬爾科夫隨機(jī)場(chǎng)MRFssss鄰域系統(tǒng) 的的含義：在任意格點(diǎn) 的其余格點(diǎn)位置上隨機(jī)變量x 取值已知的條件下，隨機(jī)場(chǎng)在格點(diǎn) 處的取值概率只與格點(diǎn) 的 相鄰點(diǎn)有關(guān)。P( )P( | )在圖像中，表示標(biāo)號(hào)場(chǎng)的先驗(yàn)概率，表示鄰域系統(tǒng)標(biāo)號(hào)的局部作用關(guān)系在數(shù)字圖像中，一個(gè)像元的灰度值僅與其鄰域系統(tǒng)內(nèi)各象元的灰度值有關(guān)，因而可

10、以利用馬爾科夫隨機(jī)場(chǎng)來(lái)模擬數(shù)字圖像。當(dāng)鄰域系統(tǒng) 足夠大時(shí)，任何定義在S上的圖像數(shù)據(jù)均可看成馬爾科夫隨機(jī)場(chǎng)的一個(gè)實(shí)現(xiàn)MRF與Gibbs分布的等價(jià)性n 由于Markov 隨機(jī)場(chǎng)是用來(lái)描述圖像的局部性質(zhì)，而 Gibbs 隨機(jī)場(chǎng)由隨機(jī)場(chǎng)的全局性質(zhì)來(lái)刻畫?？梢詫蓚€(gè)隨機(jī)場(chǎng)聯(lián)系起來(lái)。20世紀(jì)80年代Hammersley-Clifford給出了Gibbs分布與MRF關(guān)系。n HarmmersleyHarmmersley-Clifford -Clifford 定理定理：鄰域系統(tǒng) M 在集合 S 中，若 S 上隨機(jī)場(chǎng) X 符合Gibbs 隨機(jī)場(chǎng)，那么 X 也是一個(gè) Markov 隨機(jī)場(chǎng)。 從而用Gibbs分布求

11、解MRF中的概率分布，相應(yīng)的 MRF 模型的結(jié)構(gòu)信息就可以由 Gibbs分布的表達(dá)式可以描述。MRF與Gibbs分布的等價(jià)關(guān)系Gibbs分布：()SX=x ,P()(1 /) exp( )XxXXS( )( )( )cscccCUxxsSXxZU xU xVxVxZe 是定義在上的鄰域系統(tǒng)，當(dāng)且僅當(dāng)隨機(jī)場(chǎng)的聯(lián)合概率分布具有如下形式：則稱為吉布斯隨機(jī)場(chǎng)，式中 是隨機(jī)場(chǎng)的一“實(shí)現(xiàn)”，即在格點(diǎn)集上的一組態(tài)。稱為能量函數(shù)，是僅與子團(tuán) 內(nèi)各象元值有關(guān)的子團(tuán)勢(shì)函數(shù)稱為配分函數(shù)，是一個(gè)歸一化常數(shù)MRF與Gibbs分布的等價(jià)關(guān)系Gibbs分布與MRF的等價(jià)條件：一個(gè)隨機(jī)場(chǎng)是關(guān)于鄰域系統(tǒng)的MRF，當(dāng)且僅當(dāng)這個(gè)隨

12、機(jī)場(chǎng)是關(guān)于鄰域系統(tǒng)的Gibbs分布，表示為：1exp(|)P(|,( )exp(|)scsrc CsrLcsrxc CV xxxx rsV xxn通過能量函數(shù)確定MRF的條件概率，從而使其在全局上具有一致性。通過單個(gè)像素及其領(lǐng)域的簡(jiǎn)單的局部交互，MRF模型可以獲得復(fù)雜的全局行為。即計(jì)算局部的Gibbs分布得到全局的統(tǒng)計(jì)結(jié)果。n上式解決了求MRF中概率分布的難題,使對(duì)MRF的研究轉(zhuǎn)化為對(duì)勢(shì)函數(shù)Vc(x)的研究。貝葉斯公式n用來(lái)描述兩個(gè)條件概率之間的關(guān)系，比如 P(A|B) 和 P(B|A)。按照乘法法則：P(AB)=P(A)*P(B|A)=P(B)*P(A|B)。n事件A在事件B(發(fā)生)的條件下

13、的概率，與事件B在事件A的條件下的概率是不一樣的。nP(A)是A的先驗(yàn)概率或邊緣概率。所以稱為先驗(yàn)是因?yàn)樗豢紤]任何B方面的因素。nP(A|B)是已知B發(fā)生后A的條件概率，也被稱作A的后驗(yàn)概率。nP(B|A)是已知A發(fā)生后B的條件概率，也被稱作B的后驗(yàn)概率。nP(B)是B的先驗(yàn)概率或邊緣概率，也作標(biāo)準(zhǔn)化常量。n按這些術(shù)語(yǔ)，按這些術(shù)語(yǔ)，Bayes法則可表述為：法則可表述為：n后驗(yàn)概率 = (似然度 * 先驗(yàn)概率)/標(biāo)準(zhǔn)化常量n也就是說，后驗(yàn)概率與先驗(yàn)概率和似然度的乘積成正比?；贛RF的圖像分割模型n我們把圖像的的分割問題轉(zhuǎn)化為圖像的標(biāo)記問題。n標(biāo)記場(chǎng)是用來(lái)對(duì)待測(cè)對(duì)象的像素進(jìn)行跟蹤標(biāo)記，特征場(chǎng)是

14、擬合原始的觀測(cè)數(shù)據(jù)，盡可能準(zhǔn)確的反映每一個(gè)像素位置的特征信息，使圖像分割的結(jié)果中能夠保留更多的細(xì)節(jié)信息。 根據(jù)貝葉斯估計(jì)準(zhǔn)則和最大后驗(yàn)概率準(zhǔn)則，將后驗(yàn)概率轉(zhuǎn)換為先驗(yàn)概率與似然函數(shù)的乘積，似然函數(shù)同城是一個(gè)高斯分布，而先驗(yàn)概率通過MRF轉(zhuǎn)換為Gibbs分布得到，最后更新標(biāo)號(hào)場(chǎng)使得成績(jī)最大，得到最佳分割。基于MRF的圖像分割模型MAP基于馬爾科夫隨機(jī)場(chǎng)模型的圖像分割算法假設(shè)待分割圖像的像素只與其鄰域內(nèi)的像素相關(guān)，與鄰域外的像素?zé)o關(guān)；基于該假設(shè)我們能定量計(jì)算圖像局部的先驗(yàn)結(jié)構(gòu)信息，并根據(jù)最大后驗(yàn)概率準(zhǔn)則（），有效的利用像素間結(jié)構(gòu)信息分割圖像。M*NYy ,x ,X=x ,1,2,LY= ,iiiii

15、iSxLy iS對(duì)于一幅給定的的圖像 ，其中任意一個(gè)像素分割后對(duì)應(yīng)的標(biāo)記為定義兩個(gè)隨機(jī)場(chǎng)：是圖像分割后的類別標(biāo)號(hào)場(chǎng)，表示分割成 個(gè)區(qū)域，但其類別狀態(tài)不能直接觀察到。是可觀測(cè)的隨機(jī)場(chǎng)，即圖像的觀測(cè)灰度場(chǎng)，那么分割問題可以描述為：1arg12arg2,1,2,*arg(|) ()Xargmax(|)argmax( )iiiXXitetitetyYxxX iMNLitetLp Y X p Xp X Yp Y根據(jù)貝葉斯準(zhǔn)則，最優(yōu)分割準(zhǔn)則為：*111Ypargmax(|) ()XMRFMarkovMRFGibbsexp( )p( )exp( )( )cCiXM NciM Nc CiiLicixc Cci

16、ip Y X p XV xp xV xxx對(duì)于一幅給定的圖像， 已知，所以 (Y)為常數(shù)，故上式等價(jià)于:由于隨機(jī)場(chǎng) 是，具有正概率性和性。由與分布的等價(jià)性可知(X)=式中V是包含 的基團(tuán) 的勢(shì)函數(shù)， 是所有基團(tuán)的集合勢(shì)函數(shù)n選擇 由Potts模型有：，則()( ,) 1ciijiV xx xjN() ( ,) 1iiiciiijcj Nu xVxx x C1( ,)0ijijijxxx xxx觀測(cè)量似然概率n在給定類別標(biāo)號(hào) 時(shí)，通常認(rèn)為像素強(qiáng)度值服從參數(shù)為 高斯分布ix ,i 222( | )1 2exp( () 2 )iiiP y xyn基于最大后驗(yàn)概率(MAP)準(zhǔn)則的圖像分割，就是求標(biāo)記集

17、，使得關(guān)于的后驗(yàn)概率分布最大。考慮計(jì)算效率問題，采用條件迭代模式（ICM）方法。ICM算法是一個(gè)迭代算法，通過逐元的最大化條件概率實(shí)現(xiàn)像元值更新，即：1,2,.,arg max,iiiiiiNxCxf y xf x xiSICM迭代算法n1.對(duì)要計(jì)算的每一個(gè)點(diǎn)的狀態(tài)進(jìn)行初始化，狀態(tài)記為 w0 取 k=0；n2.從像素1到像素MN,計(jì)算每個(gè)像素點(diǎn)在取不同狀態(tài)的局部能量值，選擇能使局部能量值達(dá)到最小的狀態(tài)作為該點(diǎn)的當(dāng)前狀態(tài)值。n3.比較每個(gè)點(diǎn)取不同狀態(tài)的局部能量值，選擇能使局部能量達(dá)到最小的狀態(tài)最為該點(diǎn)的當(dāng)前狀態(tài)值。n4，重復(fù)23，直至收斂。Step1：給定圖像初始分割（通過閾值法或聚類方法）；Step2：由當(dāng)前分割更新 ， 和 分別是當(dāng)前第 類區(qū)域的均值和標(biāo)準(zhǔn)方差；Step3：由當(dāng)前圖像參數(shù)和上次迭代的分割結(jié)果，并根據(jù)ICM 式計(jì)算每