模糊控制与智能控制控制论.doc

基于互信息理论遗传算法的图像匹配一 遗传算法原理：遗传算法是一种仿生优化算法，该算法的基本思想来源于达尔文的进化论。遗传算法的基本原理是首先对问题的可行性进行编码，然后随机生成一定规模的初代种群，接着按照适者生存和优胜劣汰的原理，逐代进行进化。在每一代进化中，根据问题域中个体的适应度大小择优挑选个体，并按照一定的概率进行基因交叉和基因变异操作，生成新一代种群。像自然界进化一样，遗传算法的后代种群会比前代种群具有更大的适应度，更加适应环境，即更加接近问题的最优解。最后，对末代种群的最优个体进行编码，即可以作为问题的近似最优解。 图1.遗传算法流程图1.1基因交叉交叉是指对选择出来的优良个体通过基因交叉的方法以便生成与父代种群不同的个体，交叉式遗产算法产生新个体的主要手段。其主要的交叉方法有三种：单点交叉、多点交叉、均匀交叉。单点交叉：令N为个体的基因个数，则单点交叉的实现过程如下：首先产生一个区间为1，N-1的随机整数，该随机数就是交叉点，然后以交叉点为界，交换两个个体的基因。假设两个父个体为：交叉点为3，则交叉后生成的新个体为：交叉概率大小直接影响遗传算法的收敛性和有效性；越大，产生新个体的速度就越快，但遗传模式被破坏的可能性就越大，具有较高适应度的个体基因会很快被破坏。越小，搜索速度就越慢，对于本函数可使用自适应交叉概率，其表达式如下： （1）多点交叉多点交叉的实现过程与单点交叉类似，不同的是多点交叉有若干个交叉点，在各交叉点间间断地进行两个个体的基因交换。均匀交叉：均匀交叉与多点交叉类似，不同的是均匀交叉把每个点都作为潜在的交叉点，其实现过程是：随机的产生与个体基因长度相等的掩码，由掩码决定哪个父个体向子个体提供基因。通常约定掩码中的1辨识由父个体1提供基因，掩码0表示由父个体2提供基因。 父个体1： 1 0 1 0 1 1 0 0 1 0 父个体2： 0 1 0 1 1 0 0 1 0 1随机产生掩码为: 1 0 1 1 1 0 0 1 0 0 则交叉后生成的新个体为： 子个体1： 1 1 1 0 1 0 0 0 0 11.2基因变异变异是指对交叉后的个体的基因以很小的概率发生改变，通过基因变异同样可以产生与父代种群不同的个体，变异是遗传算法产生新个体的次要手段。变异的实质是一种局部随机搜索，变异概率不能太大，否则遗传算法就退化为随机搜索法。采用自适应变异概率，其计算表达式为： （2）表示每代种群的平均适应度值，表示每代种群的最大适应度值，表示待变异个体的适应度值1.3个体选择选择是指从父代种群中挑选出优良的个体。当确定了父代种群中的全部个体后，需要通过选择操作来挑选其中的较优个体，以提供后续的交叉和变异使用。由于选择操作时根据个体的适应度进行的，因此在选择前需要计算父代种群全部个体的适应度。其中，三种常用的选择方法为：轮盘赌选择法、随机遍历抽样法、锦标赛选择法。本文主要介绍轮盘赌选择法：首先根据父代种群中全部个体的适应度计算每个个体的选择概率和积累概率，然后进行若干轮选择。每一轮产生一个范围为0,1的随机数，接着将该随机数作为选择指针与积累概率进行比较，指针所在位置对应的个体即为被选中。如，从10个个体中挑选5个个体。10个个体的适应度（Fit）、选择概率（SP）、和积累计算公式如下： （3）1.4编码和解码由于变量均为实数且连续，故编码采用二进制编码方案，即个体的基因由一系列0,1 组成的二进制串表示，串的长度由变量长度及求解精度决定。设区间长为，精度要求到小数点后n位，则串长CL的计算公式为： （4）若要精确到小数点后5为，则需要串长至少为21位。解码时编码的逆操作，即将二进制转换为十进制数。对应的十进制数x可由下列公式计算： （5）1.5计算适应度适应度是遗传算法中个体进化的驱动力，是进行自然选择的唯一依据。个体质量的优劣完全由它的适应度高低唯一地评价。适应度越高，则表明个体质量越好，其生存的机会就越大；反之，若适应度越低，则表明个体质量越差，其生存的机会就越小，而被淘汰的机会却增加，本文详细的论述了采用互信息量作为衡量待配准图像和参考图像的相似度的度量，在遗传算法中我们就可以把其作为衡量各个个体适应度的函数。1.6初始种群的产生一般来说，种群数目P的取值范围为10到160之间，若P太大虽然可以搜索到更多解，更容易找到全局最优个体，但会增加搜索时间。收敛速度与遗传代数N的选择有关，N越大，收敛速度越慢，N过小，则无法得到最优个体。初始种群的产生一般都是随机完成的，有时产生的个体可能离实际最优个体距离甚远，导致搜索时间增大，收敛速度变慢。在这里，初始种群在一个固定的范围内随机产生，这个固定的范围根据经验值估计设定，三个待确定参数的范围分别为：旋转角度为度到度之间，平移范围为个像素到个像素之间。 1.7优化准则优化准则决定算法何时终止，通常的判优准则有：世代数超过预先设定值，种群个体的最大适应度超过预设值，种群个体的平均适应度超过预设值。本文采用世代数作为优化准则。二 互信息的基本概念互信息用来测量一个随机变量包含另一个随机变量的信息量的总和或者是两个随机变量间的统计相关性，应用到图像配准中用来测量一幅图像包含另一幅图像的信息的总量。如果和是两个随机变量，边缘概率分布和，联合概率分布是，如果边缘概率分布和联合概率分布满足 （6）A 和B 是统计独立的。互信息的定义为： （7）H(A)和H(B)分别是A 和B 的熵，H(A,B)是A 和B 的联合熵，H(A|B)和H(B|A)分别是给定B 的A的条件熵和给定A 的B 的条件熵。熵是统计学的一个基本概念，是随机变量不确定度的测度，随机变量的随机性越大，它的熵越大，定义如下： （8） （9） （10）互信息可以通过测量联合分布和完全独立相关分布之间的距离衡量A和B之间的独立度，具体计算通过Kullback-Leibler测量： （11）三互信息的计算方法3.1直方图法互信息的计算都是用非参数估计方法计算图像灰度的概率分布，因此，根据概率分布计算方法的不同，互信息计算可分为：直方图法和Parzen窗法。本实验用直方图法。参考图像 在位置的灰度为，测量图像 在相对应的变换位置的灰度为，是由参数确定的应用到图像的变换模型。联合灰度直方图可以通过 矩阵来表达： （12）其中 M，N 分别为测量图像和参考图像的最大灰度值，h(x,y)是测量图像中灰度值为x，参考图像中对应点灰度值为y 的像素对的总个数。边缘和联合概率分布可以通过对联合直方图归一化方法进行计算： （13）3.2基于pv插值的直方图法PV（partial Volume）插值法是一种专门针对两幅图像的联合直方图的更新而设计的插值技术，它并不是真正意义上的插值方法，因此通过PV插值法并不能计算出反向变换点的灰度值。其计算过程如下：图中为反向变换得到的一个浮点数点，其四个最近邻像素点分别为，。设参考图像为，浮动图像为，则他们的联合直方图函数可由下式统计得到： （14） （15）四 最大互信息的理论依据如果两幅图像已经配准，则他们的互信息达到极大值。假设参考图像A的概率分布函数为，浮动图像B的概率分布为，图像A和B的联合概率分布函数为，则他们的互信息由2.1式决定。在图像配准过程中，参考图像A保持不变，故也不变；浮动图像B不断变化，也随之变化，但由于图像B总的像素数量不变，灰度级值仅有少量变化，主要因为图像边缘区域出界和灰度级插值引起，故的值将在较小范围内变化；而的值在较大范围内变化。当图像A，B配准时，它们的联合熵达到极小值，互信息达到极大值。 五改进的遗传算法5.1.算法具体步骤：设A为参考图像，B为浮动图像，A与B之间的变换为刚体变换，浮动图像B沿X，Y轴的平移分别为，旋转角度为。 图 2 改进的基于遗传算法的图像匹配流程图并采用浮点数编码方法对刚体变换参数空间的参数按(，)的顺序进行编码。定义适应度函数为两幅图像的互信息量。即： （16）规定范围内随机产生初始种群，三个待确定参数的范围分别为：旋转角度为；x轴y轴平移范围为个像素之间；确定当算法运行到预先设置的遗传代数N时，终止算法的运行。这时得到种群的最优个体即为问题的最终解。计算个体适应性，按公式(16)计算种群中每个个体相应的目标函数值，即适应值选择按最优保存策略把每一代种群中适应度最高的个体直接复制到下一代，对剩下的(N-1)个个体采用轮盘赌法进行选择。若迭代次数达到设置的遗传代数N时，认为收敛指标已满足，求得的解，即为最优解，否则继续搜索，直到求得最优解。5.2配准算法实验结果：本实验用Matlab编写配准算法实现程序，验证了算法的可行性，这里以2维CT图像作为参考图像，待配准图像如图3所示。最佳配准几何变换为：x坐标为-0.32405；y坐标为0.28845；变换角度为10.03409度。程序运行时间为：69.630秒。 图三 图像融合后配准图像 经过实验观察和分析，该算法具有较强稳定性，基于互信息量的适应函数可在图像配准时达到最大值，从而验证了该理论的正确性。 参考文献： 1 李伟 杨少清.基于改进自适应遗传算法的图像配准算J.2 陈国良 王煦法 庄镇泉遗传算法以及应用M北京：人民邮电出版社3 曹蹊渺基于互信息的图像配准算法研究D北京：北京交通大学，20084 罗述谦 吕维雪.医学图像配准技术J国外医学：生物医学工程分册，1999 22(1)5 马政德 杜云飞 周海芳 刘衡竹. 图像配准中互信息的计算方法研究6 Lisa Gottesfeld Brown, A survey of image registration techniques, ACM Computing S