马尔科夫相关性质、马尔科夫随机场详解

1、马尔科夫与图像处理马尔科夫n马尔科夫随机过程就是，下一个时间点的状态只与当前的状态有关系，而与以前的状态没有关系，即未来的状态决定于现在而不决定于过去。n其未来由现在决定的程度，使得我们关于过去的知识丝毫不影响这种决定性。这种在已知 “现在”的条件下，“未来”与“过去”彼此独立的特性就被称为马尔科夫性，具有这种性质的随机过程就叫做马尔科夫过程马尔科夫过程0111100,11, ,|,|,nnnnnnnnnnnXnTnTi iiIP XiXiXiP XiXiXnT设有随机过程若对于任意正整数和任意的条件概率满足就称为马尔科夫过程，该随机过程的统计特性完全由条件概率所决定n例如：假定天气是马尔科夫

2、的，其意思就是我们假设今天的天气仅仅与昨天的天气存在概率上的关联，而与前天及前天以前的天气没有关系。其它如传染病和谣言的传播规律，都是马尔科夫的。n荷花池里有N张荷叶，在时刻Tn时，Xn为时刻Tn青蛙所处的状态。nP(Xn+1=j/Xn=i)=Pi,j , 其中，i,j=1,2,N. 表示在Tn时刻青蛙在第i张荷叶上。在下一个时刻Tn+1跳到第j张荷叶上的可能性，又称为从状态i经一步转移到j的概率，简称为一步转移概率。n将这些 Pi,j依序排列起来，就构成一个矩阵，叫做转移概率矩阵。n P11 P12 . P1n P = P21 P22 . P2n n .n Pn1 Pn2 . Pnn马尔科夫

3、预测n例如：A,B,C三个厂生产的电脑上公司在某地区市场上的占有率分别为0.3， 0.2 ，0.5。根据市场调查得知、顾客的流动情况如下： n A B C nA 0.4 0.3 0.3nB 0.6 0.3 0.1nC 0.6 0.1 0.3n市场的初始状态为S(0)=(0.3,0.2,0.5)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),这个月A,B,C电脑的市场占有率为54%,20%,26%nS(2)=S(1)*p=S(0)*P2=(0.492, 0.248, 0.26

4、),下个月A,B,C电脑的市场占有率为49.2%，24.8%，26%隐马尔科夫过程隐马尔科夫过程n与马尔科夫相比，隐马尔科夫模型则是双重随机过程，不仅状态转移之间是个随机事件，状态和输出之间也是一个随机过程n该图上面那行是一个马尔科夫转移过程，X1， X2, XT状态称为隐藏状态，下面这一行则是输出，即我们可以观察到的值，称为观察状态，观察状态的集合表示为 O=O1,O2,O3,OM。n隐马尔科夫也比马尔科夫多了一个假设，即输出仅与当前状态有关，可以用如下公式表示：nP(O1,O2,Ot|S1,S2,St)=P(O1|S1)*P(O2|S2)*.*P(Ot|St)nO1,O2,Ot为从时刻1到

5、时刻t的观测状态序列，S1,S2,St则为隐藏状态序列。n例如：我在不同天气状态下去做一些事情的概率不同，（观察状态）天气状态集合为下雨，阴天，晴天，（隐藏状态）事情集合为宅着，自习，游玩。假如我们已经有了转移概率和输出概率，即P(天气A|天气B)和P(事情a|天气A)的概率都已知道，那么我们可以解决：n假如一周内的天气变化是 下雨-晴天-阴天-下雨-阴天-晴天-阴天，那么我这一周 自习-宅着-游玩-自习-游玩-宅着-自习的概率。n假如一周内的天气变化是 下雨-晴天-阴天-下雨-阴天-晴天-阴天，那我们这一周最有可能的做事序列。n这些可以通过隐马尔科夫模型得到结果。马尔科夫随机场马尔科夫随机场

6、包含两层意思n马尔科夫性质n随机场随机场n当给每一个位置中按照某种分布随机赋予相空间的一个值之后，其全体就叫做随机场。其中有两个概念：位置（site），相空间（phase space）。我们可以拿种地来打个比方。“位置”好比是一亩亩农田；“相空间”好比是要种的各种庄稼。我们可以给不同的地种上不同的庄稼，这就好比给随机场的每个“位置”，赋予相空间里不同的值。所以，随机场就好比是在哪块地里种什么庄稼的事情。 马尔科夫随机场 同样拿种地打比方，如果任何一块地里种的庄稼的种类仅仅与它邻近的地里种的庄稼的种类有关，与其它地方的庄稼的种类无关，那么这些地里种的庄稼的集合，就是一个马尔可夫随机场。 马尔科夫

7、随机场与图像的关系n一维马尔科夫随机过程很好的描述随机过程中某点的状态只与该点之前的一个点的状态有关系。n对于定义在二维空间上的图像，也可以将它看为一个二维随机场。那么就存在二维马尔科夫随机场,将时间上的马尔科夫性转换到空间上，考虑空间的关系,二维MRF的平面网格结构可以较好的表现图像中像素之间的空间相关性。马尔科夫图像模型nMRF 将图像模拟成一个随机变量组成的网格，其中的每一个变量对明确的对其自身之外的随机变量组成的邻近基团具有依赖性。该模型考虑每个像元关于它的邻近像元的条件分布，有效地描述图像的局部统计特性。基本定义S( , )|1,1MNi jiMjN 设表示位置的有限格点集即随机场中

8、的位置=1,2L，表示状态空间，即随机场中的相空间 图像分割问题要求解的是满足最大后验概率准则的对每个像素的分类标号，我们统一称为标号场，记为X。nxs ，表示在标号场X上，状态空间为的隐状态随机变量。12*( ,.,)MNsssXx xx在图像中n格点集S表示像素的位置 nX称为标号场，也可以表示像素值的集合或图像经小波变换后的小波系数集合nL表示将图像分割为不同区域的数目，即标签集合邻域系统n随机场（Random Filed）中，利用邻域系统可以分析空间上的马尔科夫性。一个像素点的特性，更可能受它周围像素的影响，与它距离越远的像素，对它的特性的影响越小。邻域系统= ( )|SssS设是定义

9、在 上的通用邻域系统的集合，其满足如下特性：(1) ( )(2)( )(3),( )( )( )s( )ssSsss rS srrsrss则位置称作 的邻点，称作 的邻点集分阶邻域系统与子团在图像模型中，可以根据对象元的距离建立一种分阶邻域系统，定义如下：( )( )( +1)( ) | ( , ),( )0,( )( )nnnsr d s rn rsndnss 式中 为邻域系统的阶次，表示距离函数，经常使用欧氏距离，市区距离，棋盘距离等函数。对满足特性基团 S中有不同的邻域结构，在S上由单个像元或由象元与其邻点组成的子集 称为一个基团。子团c的集合用C来表示。cS分阶邻域系统与基团示例SX=

10、x ,s S1PX= 0, x(2) PX =x |,( )X =x |,( )XsssrrssrrXx rsrsPXxrs 设 为 上的邻域系统，若随机场满足如下条件：（）x则称 为以 为邻域系统的马尔科夫随机场，上式称为马尔科夫随机场的局部特性马尔科夫随机场MRFssss邻域系统 的的含义：在任意格点 的其余格点位置上随机变量x 取值已知的条件下，随机场在格点 处的取值概率只与格点 的 相邻点有关。P( )P( | )在图像中，表示标号场的先验概率，表示邻域系统标号的局部作用关系在数字图像中，一个像元的灰度值仅与其邻域系统内各象元的灰度值有关，因而可以利用马尔科夫随机场来模拟数字图像。当邻

11、域系统 足够大时，任何定义在S上的图像数据均可看成马尔科夫随机场的一个实现MRF与Gibbs分布的等价性n 由于Markov 随机场是用来描述图像的局部性质，而 Gibbs 随机场由随机场的全局性质来刻画。可以将两个随机场联系起来。20世纪80年代Hammersley-Clifford给出了Gibbs分布与MRF关系。n HarmmersleyHarmmersley-Clifford -Clifford 定理定理：邻域系统 M 在集合 S 中，若 S 上随机场 X 符合Gibbs 随机场，那么 X 也是一个 Markov 随机场。 从而用Gibbs分布求解MRF中的概率分布，相应的 MRF 模

12、型的结构信息就可以由 Gibbs分布的表达式可以描述。MRF与Gibbs分布的等价关系Gibbs分布：()SX=x ,P()(1 /) exp( )XxXXS( )( )( )cscccCUxxsSXxZU xU xVxVxZe 是定义在上的邻域系统，当且仅当随机场的联合概率分布具有如下形式：则称为吉布斯随机场，式中 是随机场的一“实现”，即在格点集上的一组态。称为能量函数，是仅与子团 内各象元值有关的子团势函数称为配分函数，是一个归一化常数MRF与Gibbs分布的等价关系Gibbs分布与MRF的等价条件：一个随机场是关于邻域系统的MRF，当且仅当这个随机场是关于邻域系统的Gibbs分布，表示

13、为：1exp(|)P(|,( )exp(|)scsrc CsrLcsrxc CV xxxx rsV xxn通过能量函数确定MRF的条件概率，从而使其在全局上具有一致性。通过单个像素及其领域的简单的局部交互，MRF模型可以获得复杂的全局行为。即计算局部的Gibbs分布得到全局的统计结果。n上式解决了求MRF中概率分布的难题,使对MRF的研究转化为对势函数Vc(x)的研究。贝叶斯公式n用来描述两个条件概率之间的关系，比如 P(A|B) 和 P(B|A)。按照乘法法则：P(AB)=P(A)*P(B|A)=P(B)*P(A|B)。n事件A在事件B(发生)的条件下的概率，与事件B在事件A的条件下的概率是

14、不一样的。nP(A)是A的先验概率或边缘概率。所以称为先验是因为它不考虑任何B方面的因素。nP(A|B)是已知B发生后A的条件概率，也被称作A的后验概率。nP(B|A)是已知A发生后B的条件概率，也被称作B的后验概率。nP(B)是B的先验概率或边缘概率，也作标准化常量。n按这些术语，按这些术语，Bayes法则可表述为：法则可表述为：n后验概率 = (似然度 * 先验概率)/标准化常量n也就是说，后验概率与先验概率和似然度的乘积成正比。基于MRF的图像分割模型n我们把图像的的分割问题转化为图像的标记问题。n标记场是用来对待测对象的像素进行跟踪标记，特征场是拟合原始的观测数据，尽可能准确的反映每一

15、个像素位置的特征信息，使图像分割的结果中能够保留更多的细节信息。 根据贝叶斯估计准则和最大后验概率准则，将后验概率转换为先验概率与似然函数的乘积，似然函数同城是一个高斯分布，而先验概率通过MRF转换为Gibbs分布得到，最后更新标号场使得成绩最大，得到最佳分割。基于MRF的图像分割模型MAP基于马尔科夫随机场模型的图像分割算法假设待分割图像的像素只与其邻域内的像素相关，与邻域外的像素无关；基于该假设我们能定量计算图像局部的先验结构信息，并根据最大后验概率准则（），有效的利用像素间结构信息分割图像。M*NYy ,x ,X=x ,1,2,LY= ,iiiiiiSxLy iS对于一幅给定的的图像 ，

16、其中任意一个像素分割后对应的标记为定义两个随机场：是图像分割后的类别标号场，表示分割成 个区域，但其类别状态不能直接观察到。是可观测的随机场，即图像的观测灰度场，那么分割问题可以描述为：1arg12arg2,1,2,*arg(|) ()Xargmax(|)argmax( )iiiXXitetitetyYxxX iMNLitetLp Y X p Xp X Yp Y根据贝叶斯准则，最优分割准则为：*111Ypargmax(|) ()XMRFMarkovMRFGibbsexp( )p( )exp( )( )cCiXM NciM Nc CiiLicixc Cciip Y X p XV xp xV xx

17、x对于一幅给定的图像， 已知，所以 (Y)为常数，故上式等价于:由于随机场 是，具有正概率性和性。由与分布的等价性可知(X)=式中V是包含 的基团 的势函数， 是所有基团的集合势函数n选择 MLL （多级逻辑模型）为势函数的参考模型。n对于单点子团，函数依赖于已经分配的标签值：n n对于成对点子团势，势函数为：nJ为像素点i邻域内的点， 为耦合系数，表示领域内相邻像素的惩罚程度。n根据上面的式子，我们可以求出P(X)( )()ccslV xV xV ()ijciijifxxxifxx特征场模型建立n接下来是求P(Y|X),表示给定标记场 X=xi 一个实现的条件下，特征场 Y=yi 的联合分布

18、 。n拟合原始的观测数据，尽可能的反映出每一个分类的特征信息 ，使分割结果保留更多的细节信息。假设则图像的观测数据可以视为多个高斯函数的加权来表现其特征。即P(Y|X)服从高斯分布，即： 其中，y表示该点的灰度值；m=1,2,，n 表示观测区域的类别标记状态； 表示图像中标记为 k 类像素的个数占整幅图像的像素个数的比重。即0 11(|)(|)mnkP Y Xf y xmmmnf(Y|X=m)表示对应类别的高斯概率密度函数，即：n其中， 和分 别表示标记为m区域的均值和方差。m2221()(|)2exp()2mmmyuP Y Xm参数估计n根据每一个像素位置(标记分类)直接计算出该像素的每一个

19、参数。 为图像中被标记为 m类像素的个数，N为整幅图像的像素个数，y 为像素的灰度值。1mmx myN221()mmmx myuNmNmNmN根据上面得到的P(X)和P(Y|X)的计算公式，采用最大后验估计来得到图像标号的分布，即求得最优分割结果 ，即完成图像的分割过程。x Markov 随机场分割算法1.对图像进行预分割，将分割后的图像根据灰度直方图设定一个阈值T。2.假设 W表示观测图像的标记场，根据阈值 T 对图像进行初始标记分类 3. 。 w 是像素的标记。4.计算当前状态 的每个像素的标记场能量函数：U1(w) ，其中k=n，n 为分割的次数。5.假设F表示观测图像的特征场，求得似然