齐次马尔可夫链ppt课件.ppt

马尔可夫链&马尔可夫随机场,概述,马尔可夫过程马尔可夫链标记问题IV.马尔可夫随机场,马尔可夫过程,时间：tn 状态：xn 即为过程X(tn)的所有可能取值 状态空间：I=x1,x2,xn-1,xn 马尔可夫过程具有如下属性（马尔可夫性）,马尔可夫过程分类,马尔可夫链,马尔可夫序列,纯不连续马尔可夫过程,连续马尔可夫过程,马尔可夫链,马尔可夫链,离散的时间对应离散的状态 状态空间 I=i1,i2,in-1,in n时刻Xn的概率分布向量 PXn=i PXn=j|Xn-1=in-1 一步转移概率,齐次马尔可夫链,齐次马尔可夫链:如果转移概率与所处的时刻n无关:Pij PXn=j|Xn-1=i,例子,晴天 阴天 下雨晴天 0.50 0.25 0.25阴天 0.375 0.25 0.375下雨 0 0 1,分 析,初始分布:假设第一天出现三种天 气的概率相等P0=()2.Pij:表示天气从状态i转到j的概率,转移概率矩阵,状态转移图,1,2,3,0.5,0.25,第四天天气概率分布,如果An趋向于定值,马氏链具有稳定状态,基本定义,路径：经过一系列的转变状态i可以到状态j 可达：两状态间有一条路径 连通：两状态间互连 吸收态：只能出去不能进来 不可约链：处处连通,隐马尔可夫模型,Markov链（,A）,随机过程（B）,状态序列,观察值序列,q1,q2,.,qT,o1,o2,.,oT,HMM的组成示意图,总述,状态和时间的概念 当前状态是一个向量P(k)转移概率矩阵A P(k+1)=P(k)*A 吸收状态,标 记 问 题,映射,集合S1,2,，m 集合Ll1，,l2，ln映射 S L扩展 S=(i,j)|1i，j n,图形学中标记的应用,格局（Configuration）,图像切割 L=edge,non-edge图像的各个像素值的概率分布 P(X)P(X1i1，X2i2，Xnin),马尔可夫随机场,马尔可夫性的拓展,马尔可夫双向性 P fi|，fi-2,fi-1,fi+1,fi+2=P fi|fi-n,fi-1,fi+1,fin 时间 空间 P(fi|f s-i)=P(fi|fNi),D,C,X,A,B,X,*,*,*,*,*,*,*,*,X,2,1,2,1,1,1,2,2,3,3,3,3,邻 域 系 统,5,5,4,4,4,5,4,4,4,4,5,4,1-order,2-order,集簇(cliques):C1=i C2=i,i C3=i,i,i,问题的根源贝叶斯估计,X 为现有图像 P(X)?Y 为目标图像 P(Y)?,应用,去除噪音,图像切割,A state-of-the-art image segmentation algorithm(S.-C.Zhu),Input Segmentation Synthesis from model I p(I|W*),不足,计算量大,