齐次马尔可夫链

马尔可夫链&马尔可夫随机场概述I.马尔可夫过程II.马尔可夫链III.标记问题IV.马尔可夫随机场马尔可夫过程•时间：tn状态：xn即为过程X(tn)的所有可能取值状态空间：I={x1,x2,……xn-1,xn}•马尔可夫过程具有如下属性（马尔可夫性）n+1n+1nnn-1n-111n+1n+1nn12n-1nn+1P{X(t)=x|X(t)=x,X(t)=x,,X(t)=x}=P{X(t)=x|X(t)=x}Wherettttt马尔可夫过程分类马尔可夫链马尔可夫序列纯不连续马尔可夫过程连续马尔可夫过程马尔可夫链马尔可夫链•离散的时间对应离散的状态•状态空间I={i1,i2,……in-1,in}•n时刻Xn的概率分布向量P{Xn=i}•P{Xn=j|Xn-1=in-1}一步转移概率n1122n-1n-1nn-1n-1P{X=j|X=i,X=i,,X=i}=P{X=j|X=i}n=1,2,3,齐次马尔可夫链•齐次马尔可夫链:如果转移概率与所处的时刻n无关:�Pij≡P{Xn=j|Xn-1=i}例子晴天阴天下雨晴天0.500.250.25阴天0.3750.250.375下雨001分析1.初始分布:假设第一天出现三种天气的概率相等P0=()2.Pij:表示天气从状态i转到j的概率111,,3330.375•转移概率矩阵•状态转移图1230.250.2510.50.500.250.250.3750.250.375001A0.25303PPA•第四天天气概率分布•如果An趋向于定值,马氏链具有稳定状态基本定义iif•路径：经过一系列的转变状态i可以到状态j•可达：两状态间有一条路径•连通：两状态间互连•吸收态：只能出去不能进来•不可约链：处处连通隐马尔可夫模型Markov链（,A）随机过程（B）状态序列观察值序列q1,q2,...,qTo1,o2,...,oTHMM的组成示意图总述•状态和时间的概念•当前状态是一个向量P(k)转移概率矩阵AP(k+1)=P(k)*A•吸收状态标记问题映射•集合S＝{1,2,……，m}集合L＝{l1，,l2，……，ln}•映射S－L•扩展S={(i,j)|1≤i，j≤n}图形学中标记的应用•格局（Configuration）•图像切割L={edge,non-edge}•图像的各个像素值的概率分布P(X)＝P(X1＝i1，X2＝i2，……Xn＝in)马尔可夫随机场马尔可夫性的拓展•马尔可夫双向性P{fi|……，fi-2,fi-1,fi+1,fi+2……}=P{fi|fi-n,……fi-1,fi+1,……fi＋n}•时间－空间P(fi|fs-{i})=P(fi|fNi)DCXABX********X212111223333邻域系统''2'{|[(,)],}iiiNiSdistpixelpixelrii5544454444541-order2-order•集簇(cliques):C1={i}C2={i,i’}C3={i,i’,i’’}问题的根源－贝叶斯估计(|)()(|)()PXYPYPYXPXX为现有图像P(X)?Y为目标图像P(Y)?()/(,),agraph,,thevariables,1Pr(),thecliquesofCCCvvVExTVGVExxeZCG,CijiijiEJxxmHx应用去除噪音图像切割Astate-of-the-artimagesegmentationalgorithm(S.-C.Zhu)InputSegmentationSynthesisfrommodelI~p(I|W*)不足•计算量大