上海交通大学随机模拟方法与应用课程论文 上滋充通大粤 随机模拟方法与应用课程论文 论文题目：论文选读 一一基于GA-MCMC的粒子滤波图像恢复算法 学生姓名： 胡卓然 吴迪舟 焦一航 所在院系： 物理与天文系 所在专业： 物理学 所在班级： F1407201 F1407201 F1407202 学生学号： 514072900951407290065140729045 指导教师： 肖柳青 完成时间： 2015年6月 1
上海交通大学随机模拟方法与应用课程论文 1 随机模拟方法与应用课程论文 论文题目： 论文选读——基于GA-MCMC的粒子滤波图像恢复算法 学生姓名： 胡卓然 吴迪舟 焦一航 所在院系： 物理与天文系 所在专业： 物理学 所在班级： F1407201 F1407201 F1407202 学生学号： 5140729009 5140729006 5140729045 指导教师： 肖柳青 完成时间： 2015 年 6 月
上海交通大学随机模拟方法与应用课程论文 目录 摘要 3 1、遗传算法(GA) 3 2、粒子滤波(PF:Particle Filter). 3 2.1概念 3 2.2感性认识 .4 2.3传统的粒子滤波一一贝叶斯滤波.… 5 2.3.1模型 ..5 2.3.2预测过程p(x-Y)→p(x-) ..5 2.3.3更新过程pxY)→p(xY) 6 2.4权重函数 ..6 2.4.1概念… .6 2.4.2权重函数递推.… 2.4.3重要密度函数(qx)的选择. .8 2.5传统的随机模拟方法 3.论文的创新点 8 3.1传统粒子滤波（贝叶斯滤波）的不足 3.2遗传算法与粒子滤波的相似性 8 3.3GA-MCMC粒子重采样… .8 3.3.1重组 ..8 3.3.2变异 .9 3.3.3选择… .9 3.4实验结果及分析 9 4.结论 10 5.自己的看法 .10 2
上海交通大学随机模拟方法与应用课程论文 2 目录 摘要 ...................................................................................................................................... 3 1、遗传算法（GA）..................................................................................................................3 2、粒子滤波(PF: Particle Filter)..................................................................................................3 2.1概念 ................................................................................................................................3 2.2感性认识 ........................................................................................................................4 2.3 传统的粒子滤波——贝叶斯滤波...................................................................................5 2.3.1 模型.............................................................................................................................5 2.3.2 预测过程 1 1 1 ( | ) ( | ) k k k k p x Y p x Y .......................................................................5 2.3.3 更新过程 1 ( | ) ( | ) k k k k p x Y p x Y ............................................................................6 2.4 权重函数 ......................................................................................................................6 2.4.1 概念.............................................................................................................................6 2.4.2 权重函数递推..............................................................................................................7 2.4.3 重要密度函数（qx）的选择.......................................................................................8 2.5传统的随机模拟方法 .....................................................................................................8 3. 论文的创新点 ...................................................................................................................8 3.1传统粒子滤波（贝叶斯滤波）的不足.............................................................................8 3.2 遗传算法与粒子滤波的相似性 ......................................................................................8 3.3GA-MCMC 粒子重采样.......................................................................................................8 3.3.1 重组.............................................................................................................................8 3.3.2 变异.............................................................................................................................9 3.3.3 选择.............................................................................................................................9 3.4 实验结果及分析 ...........................................................................................................9 4. 结论 ..................................................................................................................................10 5. 自己的看法 ......................................................................................................................10
上海交通大学随机模拟方法与应用课程论文 论文选读一一 基于GA-MCMC的粒子滤波图像恢复算法 作者：胡卓然 吴迪舟 焦一航 学号：514072900951407290065140729045 学院：物理与天文系指导教师：肖柳青 摘要 针对粒子滤波的退化和贫化问题，提出一种GA-MCMC粒子滤波图像恢复算法.该算法引 入遗传算法(GA)全局寻优和粒子总数多样性的特性，结合马尔可夫链蒙特卡罗方法(MCMC)的收 敛性，将交叉、变异和选择等操作融人到粒子滤波图像恢复中，提高了粒子滤波的鲁捧性、精 确性和灵活性，实验结果表明，该算法能减少贫化和退化问题，且在对具有混合噪声的真实图 像恢复效果方面显示了其优越性. 关键词：图像恢复：粒子滤波；遗传算法：马尔可夫链蒙特卡洛(MCMC) 1、遗传算法(GA) 遗传算法是模仿生物进化过程中自适应演化的一种优化方法，它也是MCMC思想的一种应 用。该算法产生建议与接受状态的方式比较特殊，其主要方式是将优化问题的所有可行解看作 一群生物个体，对这群个体的基因进行重组、变异、以及选择性复制以繁衍出下一代群体。 遗传算法的三大要素： ·计算机编码方式来表示状态空间 如：固定长度的二进制数位串 父代：10110101010100 母代：10111010 111010 后代：10110101111010 ·定义三种随机算子：变异、重组、选择 ·定义适应度函数 2、粒子滤波(PF:Particle Filter) 2.1概念 粒子滤波的思想基于蒙特卡洛方法(Monte Carlo methods),它是利用粒子集来表示概率，可 以用在任何形式的状态空间模型上。其核心思想是通过从后验概率中抽取的随机状态粒子来表 达其分布，是一种顺序重要性采样法(Sequential Importance Sampling)。简单来说，粒子滤波法 是指通过寻找一组在状态空间传播的随机样本对概率密度函数进行近似，以样本均值代替积分 运算，从而获得状态最小方差分布的过程。这里的样本即指粒子，当样本数量N→∝时可以逼近 任何形式的概率密度分布。 ·本身就是随机模拟过程 2.2感性认识
上海交通大学随机模拟方法与应用课程论文 3 论文选读——基于GA-MCMC的粒子滤波图像恢复算法 作者：胡卓然 吴迪舟 焦一航 学号：5140729009 5140729006 5140729045 学院：物理与天文系 指导教师：肖柳青 摘要 针对粒子滤波的退化和贫化问题，提出一种 GA-MCMC 粒子滤波图像恢复算法．该算法引 入遗传算法(GA)全局寻优和粒子总数多样性的特性，结合马尔可夫链蒙特卡罗方法(MCMC)的收 敛性，将交叉、变异和选择等操作融人到粒子滤波图像恢复中，提高了粒子滤波的鲁捧性、精 确性和灵活性．实验结果表明，该算法能减少贫化和退化问题，且在对具有混合噪声的真实图 像恢复效果方面显示了其优越性． 关键词：图像恢复；粒子滤波；遗传算法；马尔可夫链蒙特卡洛(MCMC) 1、遗传算法（GA） 遗传算法是模仿生物进化过程中自适应演化的一种优化方法，它也是 MCMC 思想的一种应 用。该算法产生建议与接受状态的方式比较特殊，其主要方式是将优化问题的所有可行解看作 一群生物个体，对这群个体的基因进行重组、变异、以及选择性复制以繁衍出下一代群体。 遗传算法的三大要素： •计算机编码方式来表示状态空间 如：固定长度的二进制数位串 父代：10110101 010100 母代：10111010 111010 后代：10110101 111010 •定义三种随机算子：变异、重组、选择 •定义适应度函数 2、粒子滤波(PF: Particle Filter) 2.1 概念 粒子滤波的思想基于蒙特卡洛方法(Monte Carlo methods)，它是利用粒子集来表示概率，可 以用在任何形式的状态空间模型上。其核心思想是通过从后验概率中抽取的随机状态粒子来表 达其分布，是一种顺序重要性采样法(Sequential Importance Sampling)。简单来说，粒子滤波法 是指通过寻找一组在状态空间传播的随机样本对概率密度函数进行近似，以样本均值代替积分 运算，从而获得状态最小方差分布的过程。这里的样本即指粒子,当样本数量 N→∝时可以逼近 任何形式的概率密度分布。 •本身就是随机模拟过程 2.2 感性认识
上海交通大学随机模拟方法与应用课程论文 p(x,IZ,) P(IX) {9,Ww qg,lx4)t 承采样 .VNE ？,w哈 P(xIZ) vL X 上图分为三层，每层分别代表粒子滤波一个循环中的三个重要步骤。在第一层，默认每种 粒子的重要性相同，均为1/N,曲线的峰值代表该粒子出现的几率较大。然而，事实上每种粒 子的重要性并不相同，其中所谓的的重要性极低，是对整体样本起干扰作用的，我们的理想状 态是把所谓的“噪声粒子”从整体样本中挑选出来。 因而，在第二层一一重采样过程，某些重要性较大的具有样本代表性的粒子被挑选出来， 并按照其重要性大小（权重函数w)将粒子不同程度的放大（复制样本）。 第三层，重采样过程得到的粒子又有了相同的重要性，得到某种粒子出现的后验概率。 如此经过N趋向于无穷次的循环，我们不妨将N次循环后的粒子出现的概率视为剔除“噪 声粒子”后粒子的实际分布 以上为传统意义的粒子滤波过程，而本文的创新点在于将GA-MCMC方法应用到重采样过 程。即重采样过程不再是简单的复制重要性大的样本，而是将重要性大的样本作为父本，经过 变异、重组、选择三种算子变换后得到的子代，再对子代进行下一次循环。 23传统的粒子滤波模型一一贝叶斯滤波 2.3.1模型
上海交通大学随机模拟方法与应用课程论文 4 上图分为三层，每层分别代表粒子滤波一个循环中的三个重要步骤。在第一层，默认每种 粒子的重要性相同，均为 1/N，曲线的峰值代表该粒子出现的几率较大。然而，事实上每种粒 子的重要性并不相同，其中所谓的的重要性极低，是对整体样本起干扰作用的，我们的理想状 态是把所谓的“噪声粒子”从整体样本中挑选出来。 因而，在第二层——重采样过程，某些重要性较大的具有样本代表性的粒子被挑选出来， 并按照其重要性大小（权重函数 w）将粒子不同程度的放大（复制样本）。 第三层，重采样过程得到的粒子又有了相同的重要性，得到某种粒子出现的后验概率。 如此经过 N 趋向于无穷次的循环，我们不妨将 N 次循环后的粒子出现的概率视为剔除“噪 声粒子”后粒子的实际分布 以上为传统意义的粒子滤波过程，而本文的创新点在于将 GA-MCMC 方法应用到重采样过 程。即重采样过程不再是简单的复制重要性大的样本，而是将重要性大的样本作为父本，经过 变异、重组、选择三种算子变换后得到的子代，再对子代进行下一次循环。 2.3 传统的粒子滤波模型——贝叶斯滤波 2.3.1 模型
上海交通大学随机模拟方法与应用课程论文 p(yx:) 2 p(xx:-1) 图2.1状态空间模型 在目标跟踪问题中，动态系统的状态空间模型可描述为 x,=f(x-)+“-1 (2.1) =h()+v 其中∫()，()分别为状态转移方程与观测方程，x,为系统状态，y,为观测值，“，为过程 噪声，y,为观测噪声，为了描述方便，用X,=x1=代。，…，x}与Y=八u={,,》} 分别表示0到k时刻所有的状态与观测值。在处理目标跟踪问题时，通常假设目标的状态转 移过程服从一阶马尔可夫模型，即当前时刻的状态x,只与上一时刻的状态x,有关。另外 一个假设为观测值相互独立，即观测值y,只与k时刻的状态x,有关。 2.32预测过程p(x-Y)→p(xY-) 假设已知k-1时刻的概率密度函数为p(x-11Y-),贝叶斯滤波的具体过程如下： (1)预测过程，由p(x-1IY-)得到p(x1Y-) P(x,x-1Y-)=p(x|x-1Y-)P(x-1IY-) 当给定x,时，状态x与Y-相互独立，因此 p(x,x1lY)=p(1-)p(-Y-) 上式两端对x-,积分，可得Chapman-Komolgorov方程 p(x)=[p(xx)p(xY)dx 2.33更新过程px|Y-)→p(xY) 5
上海交通大学随机模拟方法与应用课程论文 5 2.3.2 预测过程 1 1 1 ( | ) ( | ) k k k k p x Y p x Y 2.3.3 更新过程 1 ( | ) ( | ) k k k k p x Y p x Y
上海交通大学随机模拟方法与应用课程论文 获取k时刻的测量y,后，利用贝叶斯公式对先验概率密度进行更新，得到后验概率 p,1y)=P.yp1y (2.5) p(y.IY) 假设y,只由x,决定，即 p(y..Y)=p(yx) (2.6) 因此 p()=p(1)p( 2.7) p(y:IY) 2.4权重函数 2.4.1概念 是利用一系列随机样本的加权和表示后验概率密度，通过求和来近似积分操作。假设可以从 后验概率密度p(xIY)中抽取N个独立同分布的随机样本x,i=1,·,N,则有 P(xlY)≈∑6(x-x) (2.11) N 这里x,为连续变量，6(xx)为单位冲激函数（狄拉克函数），即6(x-,)=0,x≠x,, 且〔6(x)dr=1。当x为离散变量时，后验概率分布P(x1Y)可近似逼近为 I N P(xIY)≈∑6(x-x) (2.12) N台 其中，6(x-x)=1,x=x9:6x-x)=0,x≠x0。 在实际计算中，通常无法直接从后验概率分布中采样，如何得到服从后验概率分布的随 机样本是蒙特卡洛方法中基本的问题之一。重要性采样法引入一个已知的、容易采样的重要 性概率密度函数9(x1Y,),从中生成采样粒子，利用这些随机样本的加权和来逼近后验滤 6
上海交通大学随机模拟方法与应用课程论文 6 2.4 权重函数 2.4.1 概念
上海交通大学随机模拟方法与应用课程论文 波概率密度p(x1Y),如图2.3所示。令{x,w9,i=1,N}表示一支撑点集，其中x0为 是k时刻第i个粒子的状态，其相应的权值为，则后验滤波概率密度可以表示为 P(xY上Σw为(-x) (2.14) 其中， w”P(9y) 9(x1Y) (2.15) 2.4.2权重函数递推 ·假设重要性概率密度函数q(x。4〡y以)可以分解为 9(x0|1)=9(x0-1|y-:)9(x:1xo-1》) 后验概率密度函数的递归形式可以表示为 p(or)=P(y.Iop(oY) p(y.IY) =P(yKY9x(x1ay。D》《y4l:) p(y.: (2.20) =P少比p《1,p)rL:) p(y. 粒子权值w的递归形式可以表示为 w p(x) 9(xg21Y) -P(1)p()1￥’)mf,)LX) 9()1’.￥)9(3：1Y) wP(1)p) (2.21) q(x”1x9,Y) 通常，需要对粒子权值进行归一化处理，即 (2.22) ” 2.4.3重要密度函数(qx)的选择 >
上海交通大学随机模拟方法与应用课程论文 7 2.4.2 权重函数递推 2.4.3 重要密度函数（qx）的选择
上海交通大学随机模拟方法与应用课程论文 选择重要性概率密度函数的-个标准是使得粒子权值(w}:的方差最小。Doucet等给 出的最优重要性概率密度函数为 4)=p(x) p(y,1x”,2)p(x91x2) p(,Ix2) 2.5传统的随机模拟方法 采用Metropolis-Hastings算法，从慨率密度g(.x)中生成粒子的具体步骤为： (1)从[0,1]之间的均匀分布中生成随机数”·U[0,1们； (2)从重要性慨率密度函数中生成采样粒子x·p(x:Ix)； (3)如果v≤min1, (x:)p(xx) (x) 接受x,否则，拒绝xi 3、论文的创新点 3.1传统粒子滤波（贝叶斯滤波）的不足 传统粒子滤波的一个严重缺陷是退化问题，即重要性权值的方差随着时间是递增的.经过 多次迭代后，集中对大多数权值过小的粒子进行计算没有意义，这时要用到重采样技术，基本 思想是抑制或剔除小权值粒子，对于大权值粒子则依其权值大小进行复制，从而把处理资源按 照粒子权值的大小进行分配.但是重采样后保留了大量的大权值粒子，这样就引起了粒子的贫 化，使粒子缺乏多样性. 3.2遗传算法与粒子滤波的相似性 粒子滤波算法和遗传算法在结构上是一致的，将粒子视为染色样本，每个粒子对应的重要 性权值视为染色样本对应的适应度函数，将标准粒子滤波器中的再采样部分改进为遗传算法的 交叉、变异和选择过程，在状态估计问题中朝全局寻优的方向进行，并通过交叉和变异步骤使 得染色样本保持一定程度的多样性， 3.3GA-MCMC粒子重采样 3.3.1重组 算法1：·交叉算法/CROSSOVER算法 若随机数U。max{p(x|x),p(名s| x)》,接受x,否则以以下概率接受 3.3.2变异 p(z)/maxip(),p()). (5) 对x的操作也以同样的方式进行
上海交通大学随机模拟方法与应用课程论文 8 2.5 传统的随机模拟方法 3、论文的创新点 3.1 传统粒子滤波（贝叶斯滤波）的不足 传统粒子滤波的一个严重缺陷是退化问题，即重要性权值的方差随着时间是递增的．经过 多次迭代后，集中对大多数权值过小的粒子进行计算没有意义．这时要用到重采样技术，基本 思想是抑制或剔除小权值粒子，对于大权值粒子则依其权值大小进行复制，从而把处理资源按 照粒子权值的大小进行分配．但是重采样后保留了大量的大权值粒子，这样就引起了粒子的贫 化，使粒子缺乏多样性． 3.2 遗传算法与粒子滤波的相似性 粒子滤波算法和遗传算法在结构上是一致的，将粒子视为染色样本，每个粒子对应的重要 性权值视为染色样本对应的适应度函数，将标准粒子滤波器中的再采样部分改进为遗传算法的 交叉、变异和选择过程，在状态估计问题中朝全局寻优的方向进行，并通过交叉和变异步骤使 得染色样本保持一定程度的多样性． 3.3 GA-MCMC 粒子重采样 3.3.1 重组 3.3.2 变异
上海交通大学随机模拟方法与应用课程论文 算法2：Metropolis-Hastings,/MH变异 Metropolis-Hastings/MH变异步骤如下. ①用建议密度产生候选值y,建议密度为 q(x,y)=g(I x-yl)oc exp[(x-y)2/202]. (6) ②计算接受概率p, p(x,y)=min[x(y)q(y,x)/x(x)q(r,y),1]. (7) 式中：π(y)和π(x)分别为y和x的分布 ③若u≤a(x,y),u~4(0,1),则x+1=y,否 则x1=x. 3.3.3选择 选择，选出适应度佳的N个粒子，适应度函数为 F(xi)=p(/). (8) 3.4实验结果及分析 (a)惊始ena图像 )混台噪声的退化图像 (c)SIR粒子滤波恢复 (dGA-MCMC粒子滤波恢 sw=23.043dB s=25.645dB 图1图像恢复结果 Fig.1 Image restoration results 原始图像及混合噪声污染后的图像如图1()和图1(b)所示.通过对比可以观察到，高斯白
上海交通大学随机模拟方法与应用课程论文 9 3.3.3 选择 3.4 实验结果及分析 原始图像及混合噪声污染后的图像如图 1(a)和图 1(b)所示．通过对比可以观察到，高斯白
上海交通大学随机模拟方法与应用课程论文 噪声造成了图像整体的不清晰，而柯西分布噪声产生了类似于脉冲噪声的影响.柯西噪声成分 的引人，使图像的退化非常严重.图1(c是经过较常用的重要性采样一采样粒子S1R滤波算法4] 恢复处理后得到的结果. 可以看到，S粒子滤波器对于非高斯问题的处理有优越的性能，图像中绝大部分柯西噪声 成分被有效地滤除，脉冲噪点几乎完全消除.但是在图像灰度变化较小的相对平坦区域，仍然 有残留噪声的污染，峰值信噪比为23.043dB.图I(d)是用GA一MCMC粒子滤波恢复的图像， 通过对比重采样中普通SIR粒子总数分布P(图2(a)和GA一MC一MC方法的粒子总数的分布（图 2b)可见，后者既保持了粒子集的多样性，又能将粒子集替换为新的更多样且符合后验分布的 粒子集，有效地减小了退化和贫化问题，由图1()可见恢复效果更清晰，此图的峰值信噪比提 高到了约25.645dB. 0.05 0.05 0.04 0.04 0.03 0.03 0.02 0.02 0.01 0.01 0 0 15-10-5051015 15-10-5051015 采样点数 采样点数 (@)普通粒子滤波重采样分布 b)GA-MCMC重采样分布 图2重采样中粒子总数分布对比图 4、结论 作者针对粒子滤波的退化和贫化问题，利用遗传算法全局寻优的特性和马尔可夫链蒙特卡 罗方法的收敛性，将其融合入重采样中，从而提高粒子滤波的鲁棒性、精确性和灵活性，进而 提出一种GAMC一MC粒子滤波图像恢复算法.实验结果表明了该算法的有效性，对比GA-MCMC 粒子滤波与普通滤波器图像恢复结果表明了该算法的优越性， 5、自己的看法 5.1基于GA-MCMC的粒子滤波图像恢复算法充分利用了遗传算法的优点. 遗传算法同时使用多个搜索点的搜索信息。传统的优化方法往往是从解空间的单个初始点 开始最优解的迭代搜索过程，单个搜索点所提供的信息不多，搜索效率不高，有时甚至使搜索 过程局限于局部最优解而停滞不前。 遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的 个体开始搜索，这是遗传算法所特有的一种隐含并行性，因此遗传算法的搜索效率较高。 5.2基于GA-MCMC的粒子滤波图像恢复算法合理避免了遗传算法的缺点。 有时在遗传算法的运行中，适应度的改善变得越来越慢，似乎该算法己基本粘滞或位于在 局部最优处（或许是全局最优？这有待进一步判断）。这种情况当目前群体中的大部分变成是某 一个个体的复制者（或接近复制者）时常常发生。但根据算法的构造，算法产生的序列是一个 不可约的马尔可夫链，因此只要给予足够的时间，算法迭代会使状态继续转移，找到另一个局 10
上海交通大学随机模拟方法与应用课程论文 10 噪声造成了图像整体的不清晰，而柯西分布噪声产生了类似于脉冲噪声的影响．柯西噪声成分 的引人，使图像的退化非常严重．图 1(c)是经过较常用的重要性采样一采样粒子 SIR 滤波算法[4] 恢复处理后得到的结果． 可以看到，SIR 粒子滤波器对于非高斯问题的处理有优越的性能，图像中绝大部分柯西噪声 成分被有效地滤除，脉冲噪点几乎完全消除．但是在图像灰度变化较小的相对平坦区域，仍然 有残留噪声的污染，峰值信噪比为 23．043 dB．图 l(d)是用 GA—MCMC 粒子滤波恢复的图像， 通过对比重采样中普通 SIR 粒子总数分布 P(图 2(a))和 GA—MC—MC 方法的粒子总数的分布(图 2(b))可见，后者既保持了粒子集的多样性，又能将粒子集替换为新的更多样且符合后验分布的 粒子集，有效地减小了退化和贫化问题，由图 1(d)可见恢复效果更清晰，此图的峰值信噪比提 高到了约 25．645 dB． 4、结论 作者针对粒子滤波的退化和贫化问题，利用遗传算法全局寻优的特性和马尔可夫链蒙特卡 罗方法的收敛性，将其融合入重采样中，从而提高粒子滤波的鲁棒性、精确性和灵活性，进而 提出一种 GA-MC—MC 粒子滤波图像恢复算法．实验结果表明了该算法的有效性，对比 GA-MCMC 粒子滤波与普通滤波器图像恢复结果表明了该算法的优越性． 5、自己的看法 5.1 基于 GA-MCMC 的粒子滤波图像恢复算法充分利用了遗传算法的优点. 遗传算法同时使用多个搜索点的搜索信息。传统的优化方法往往是从解空间的单个初始点 开始最优解的迭代搜索过程，单个搜索点所提供的信息不多，搜索效率不高，有时甚至使搜索 过程局限于局部最优解而停滞不前。 遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的 个体开始搜索，这是遗传算法所特有的一种隐含并行性，因此遗传算法的搜索效率较高。 5.2 基于 GA-MCMC 的粒子滤波图像恢复算法合理避免了遗传算法的缺点。 有时在遗传算法的运行中，适应度的改善变得越来越慢，似乎该算法已基本粘滞或位于在 局部最优处（或许是全局最优？这有待进一步判断）。这种情况当目前群体中的大部分变成是某 一个个体的复制者（或接近复制者）时常常发生。但根据算法的构造，算法产生的序列是一个 不可约的马尔可夫链，因此只要给予足够的时间，算法迭代会使状态继续转移，找到另一个局