馬爾科夫相關(guān)性質(zhì)、馬爾科夫隨機(jī)場(chǎng)詳解

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

2、的，其意思就是我們假設(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ò)的概率，簡稱為一步轉(zhuǎn)移概率。n將這些 Pi,j依序排列起來，就構(gòu)成一個(gè)矩陣，叫做轉(zhuǎn)移概率矩陣。n P11 P12 . P1n P = P21 P22 . P2n n .n Pn1 Pn2 . Pnn馬爾科夫

3、預(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.492, 0.248, 0.26

4、),下個(gè)月A,B,C電腦的市場(chǎng)占有率為49.2%，24.8%，26%隱馬爾科夫過程隱馬爾科夫過程n與馬爾科夫相比，隱馬爾科夫模型則是雙重隨機(jī)過程，不僅狀態(tài)轉(zhuǎn)移之間是個(gè)隨機(jī)事件，狀態(tài)和輸出之間也是一個(gè)隨機(jī)過程n該圖上面那行是一個(gè)馬爾科夫轉(zhuǎn)移過程，X1， X2, XT狀態(tài)稱為隱藏狀態(tài)，下面這一行則是輸出，即我們可以觀察到的值，稱為觀察狀態(tài)，觀察狀態(tài)的集合表示為 O=O1,O2,O3,OM。n隱馬爾科夫也比馬爾科夫多了一個(gè)假設(shè)，即輸出僅與當(dāng)前狀態(tài)有關(guān)，可以用如下公式表示：nP(O1,O2,Ot|S1,S2,St)=P(O1|S1)*P(O2|S2)*.*P(Ot|St)nO1,O2,Ot為從時(shí)刻1到

5、時(shí)刻t的觀測(cè)狀態(tài)序列，S1,S2,St則為隱藏狀態(tài)序列。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這些可以通過隱馬爾科夫模型得到結(jié)果。馬爾科夫隨機(jī)場(chǎng)馬爾科夫隨機(jī)場(chǎng)

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

7、隨機(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ì)特性?；径xS( , )|1,1MNi jiMjN 設(shè)表示位置的有限格點(diǎn)集即隨機(jī)場(chǎng)中

8、的位置=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ì)它的特性的影響越小。鄰域系統(tǒng)= ( )|SssS設(shè)是定義

9、在 上的通用鄰域系統(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來表示。cS分階鄰域系統(tǒng)與基團(tuán)示例SX=

10、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)，因而可以利用馬爾科夫隨機(jī)場(chǎng)來模擬數(shù)字圖像。當(dāng)鄰

11、域系統(tǒng) 足夠大時(shí)，任何定義在S上的圖像數(shù)據(jù)均可看成馬爾科夫隨機(jī)場(chǎng)的一個(gè)實(shí)現(xiàn)MRF與Gibbs分布的等價(jià)性n 由于Markov 隨機(jī)場(chǎng)是用來描述圖像的局部性質(zhì)，而 Gibbs 隨機(jī)場(chǎng)由隨機(jī)場(chǎng)的全局性質(zhì)來刻畫?？梢詫蓚€(gè)隨機(jī)場(chǎng)聯(lián)系起來。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分布求解MRF中的概率分布，相應(yīng)的 MRF 模

12、型的結(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è)隨機(jī)場(chǎng)是關(guān)于鄰域系統(tǒng)的Gibbs分布，表示

13、為：1exp(|)P(|,( )exp(|)scsrc CsrLcsrxc CV xxxx rsV xxn通過能量函數(shù)確定MRF的條件概率，從而使其在全局上具有一致性。通過單個(gè)像素及其領(lǐng)域的簡單的局部交互，MRF模型可以獲得復(fù)雜的全局行為。即計(jì)算局部的Gibbs分布得到全局的統(tǒng)計(jì)結(jié)果。n上式解決了求MRF中概率分布的難題,使對(duì)MRF的研究轉(zhuǎn)化為對(duì)勢(shì)函數(shù)Vc(x)的研究。貝葉斯公式n用來描述兩個(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ā)生)的條件下的概率，與事件B在事件A的條件下的概率是

14、不一樣的。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ù)語，按這些術(shù)語，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)是用來對(duì)待測(cè)對(duì)象的像素進(jìn)行跟蹤標(biāo)記，特征場(chǎng)是擬合原始的觀測(cè)數(shù)據(jù)，盡可能準(zhǔn)確的反映每一

15、個(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)使得成績最大，得到最佳分割。基于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= ,iiiiiiSxLy iS對(duì)于一幅給定的的圖像 ，

16、其中任意一個(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 Cciip Y X p XV xp xV xx

17、x對(duì)于一幅給定的圖像， 已知，所以 (Y)為常數(shù)，故上式等價(jià)于:由于隨機(jī)場(chǎng) 是，具有正概率性和性。由與分布的等價(jià)性可知(X)=式中V是包含 的基團(tuán) 的勢(shì)函數(shù)， 是所有基團(tuán)的集合勢(shì)函數(shù)n選擇 MLL （多級(jí)邏輯模型）為勢(shì)函數(shù)的參考模型。n對(duì)于單點(diǎn)子團(tuán)，函數(shù)依賴于已經(jīng)分配的標(biāo)簽值：n n對(duì)于成對(duì)點(diǎn)子團(tuán)勢(shì)，勢(shì)函數(shù)為：nJ為像素點(diǎn)i鄰域內(nèi)的點(diǎn)， 為耦合系數(shù)，表示領(lǐng)域內(nèi)相鄰像素的懲罰程度。n根據(jù)上面的式子，我們可以求出P(X)( )()ccslV xV xV ()ijciijifxxxifxx特征場(chǎng)模型建立n接下來是求P(Y|X),表示給定標(biāo)記場(chǎng) X=xi 一個(gè)實(shí)現(xiàn)的條件下，特征場(chǎng) Y=yi 的聯(lián)合分布

18、 。n擬合原始的觀測(cè)數(shù)據(jù)，盡可能的反映出每一個(gè)分類的特征信息 ，使分割結(jié)果保留更多的細(xì)節(jié)信息。假設(shè)則圖像的觀測(cè)數(shù)據(jù)可以視為多個(gè)高斯函數(shù)的加權(quán)來表現(xiàn)其特征。即P(Y|X)服從高斯分布，即： 其中，y表示該點(diǎn)的灰度值；m=1,2,，n 表示觀測(cè)區(qū)域的類別標(biāo)記狀態(tài)； 表示圖像中標(biāo)記為 k 類像素的個(gè)數(shù)占整幅圖像的像素個(gè)數(shù)的比重。即0 11(|)(|)mnkP Y Xf y xmmmnf(Y|X=m)表示對(duì)應(yīng)類別的高斯概率密度函數(shù)，即：n其中， 和分 別表示標(biāo)記為m區(qū)域的均值和方差。m2221()(|)2exp()2mmmyuP Y Xm參數(shù)估計(jì)n根據(jù)每一個(gè)像素位置(標(biāo)記分類)直接計(jì)算出該像素的每一個(gè)

19、參數(shù)。 為圖像中被標(biāo)記為 m類像素的個(gè)數(shù)，N為整幅圖像的像素個(gè)數(shù)，y 為像素的灰度值。1mmx myN221()mmmx myuNmNmNmN根據(jù)上面得到的P(X)和P(Y|X)的計(jì)算公式，采用最大后驗(yàn)估計(jì)來得到圖像標(biāo)號(hào)的分布，即求得最優(yōu)分割結(jié)果 ，即完成圖像的分割過程。x Markov 隨機(jī)場(chǎng)分割算法1.對(duì)圖像進(jìn)行預(yù)分割，將分割后的圖像根據(jù)灰度直方圖設(shè)定一個(gè)閾值T。2.假設(shè) W表示觀測(cè)圖像的標(biāo)記場(chǎng)，根據(jù)閾值 T 對(duì)圖像進(jìn)行初始標(biāo)記分類 3. 。 w 是像素的標(biāo)記。4.計(jì)算當(dāng)前狀態(tài) 的每個(gè)像素的標(biāo)記場(chǎng)能量函數(shù)：U1(w) ，其中k=n，n 為分割的次數(shù)。5.假設(shè)F表示觀測(cè)圖像的特征場(chǎng)，求得似然