基于遗传算法的图像匹配.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,基于遗传算法的图像匹配,遗传算法理论和特点,1,、,GA,的基本原理,遗传算法首先采用某种编码方式将解空间映射到编码空间,每个编码对应问题的一个解,称为个体或染色体,再随机确定起始的一群个体,称为种群。在后续迭代中,按照适者生存原理,根据适应度大小挑选个体,并借助各种遗传算子对个体进行交叉和变异,生成代表新的解集的种群,该种群比前代更适应环境,如此进化下去直到满足优化准则。此时末代个体,经过解码,可作为问题近似最优解。,2,、,GA,的理论基础,(1),模式定理,定义,1:,出现在模式,H,中的,0,或,1,的数目称为模式,H,的阶,记作,O(H),。如,:O(10*1)=3,。,定义,2:,模式,H,中第一个确定位置和最后一个确定位置之间的距离称为模式,H,的定义距,记作,(H,),。如,:(10*1)=4,。,模式定理,:,具有低阶、短定义距和平均适应度高于种群平均适应度的模式在后代中呈指数增长。,(2),积木块假设,积木块假设,:,遗传算法通过短定义距、低阶和高平均适应度的模式,(,积木块,),在遗传操作下相互结合,最终接近全局最优解。,模式定理保证了遗传算法找到全局最优解的可能性存在,而积木块假设指出了在遗传操作下能生成全局最优解。两者构成了分析遗传算法进化行为的基本理论。,遗传算法的特点,与传统的方法相比，遗传算法以其简单、鲁棒性强、不需很多先验知识等特点，使它能适应于不同的环境、问题，并且在大多数情况下都能得到最优解。遗传算法,具有很强的鲁棒性，这是因为比起普通的优化搜索方法，它采用了许多独特的方法和技术，归纳起来，主要有以下几个方面,:,(1),遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体，遗传算法将待优化问题的原始参数集编码成有限字符集上的有限长字符串，然后以一种通用的方式去找出各编码的类似处。这样做的好处是大大减少了约束条件的限制，如连续性、可导性、单峰性等。因此，遗传算法是一种框架算法，最适合于解决那些很难用表达式表达出来的问题。,(2),遗传算法是同时处理群体中的多个个体，即多点搜索，在很多优化算法中，算法总是按照某种转移准则从参数空间中的一个单点移至下一个单点，这样做很容易在多峰的搜索空间中找到一个非全局最高的峰值，即局部最优值。而遗传算法是从很多点的集合开始同时搜索的，从而减少了陷于局部最优解的风险。,(3),遗传算法仅用适应度函数来指导搜索，以往很多的搜索方法都需要辅助信息才能正常工作。如梯度法需要有关导数的信息才能爬上当前的峰值点，这就要求目标函数可导。而遗传算法则不需要类似的辅助信息，为了有效地搜索越来越好的编码结构，它仅需要与该编码串有关的适应度函数即可。在适应度值的指导下，个体随着进化代数的增大而不断进化，每一代的结果都优异于上,一代，如此逐代进化，直到得出最优化结果或符合要求的结果。整个算法具有自适应环境的能力。,(4),遗传算法采用了概率转移准则而不是确定性规则，与很多方法不同，遗传算法在搜索过程中以概率转移准则来指导它的搜索过程朝着更优化的解区域移动,但使用概率并不是说遗传算法只是简单的随机搜索。遗传算法用随机选择作为工具去指导搜索向着搜索空间中可能的更好的区域进行。,遗传算法适于解决维数很高、总体很大的复杂的非线性问题，如机器学习。遗传算法具有以下优点,:,(1),应用的广泛性,:,易于写出通用算法，求解不同优化问题。,(2),非线性性,:,其他多数算法都需与可导、线性、凸性等性质相联系，遗传算法只需适应度函数为非负，可用于具有高度非线性的问题寻优。,(3),易于修改性,:,遗传算法只需少量改变算法，即可适用于不同问题。,(4),易于并行实现。,标准遗传算法的基本流程,标准遗传求解问题的基本流程如下,:,1.,确定染色体、种群和适应度函数。将问题的解编码成染色体串，如二进制码串，若干个可能解构成一组种群，适应度函数体现了在问题求解过程中染色体求解问题的能力。,2.,基因初始化，即对种群中染色体的各基因,(,二进制子串,),设定初值。,3.,将种群的各染色体置于问题的环境中遗传进化。,（,1,）进化：根据适应度函数，计算每个染色体的适应度。,（,2,）选择,:,选择有较大适应值的染色体进行复制，替代适应值小的染色体。,（,3,）交换和变异,:,其目的在于产生有可能更适应环境的新染色体。,4.,重复,3,直至满足终止条件。这样一代代不断进化，最终将收敛到一个最适应环境的个体上，即问题的最优解。,图,1,描述了标准遗传算法的流程，从图中可以看出,GA,是一种群体型操作，该操作主要以群体中的所有个体为对象。选择、交叉、变异是,GA,的,3,个主要操作算子，它们构成了所谓的遗传操作。,图,1,标准遗传算法流程图,产生初始种群,计算适应度,是否满足终,止条件,输出最优个体,YES,选择,交叉,变异,NO,标准遗传算法的基本要素,GA,具有五个基本要素,:,参数编码、初始群体的设定、适应度函数的设计、遗传操作设计和控制参数设定。它们是设计,GA,时的核心内容。,1,、参数编码,编码机制是遗传算法的基础。在进行参数编码设计时一般都以,DeJong,的编码原理为依据。,经常采用的编码技术主要有一维染色体编码、多参数映射编码、可变染色体长度编码、二维染色体编码、树结构编码等。其中一维染色体编码根据基于不同的符号集又可分为二进制编码、实数编码和字符编码等,;,多参数映射编码主要应用于多参数优化问题中，将不同的参数映射为不同的编码子串，然后进行相应的遗传操作,;,可变染色体长度编码主要以,Golbdegr,等人提出的,MesysGA(mGA,),为代表,;,后两种编码是针对不同应用领域的特点而设计的，分别应用于图像处理，人工智能等特定领域。,2,、初始种群的设定,群体中个体一般是随机产生，当然也可从随机生成的个体中选出最好的个体组成初始群体。但此处有一个关键的问题，就是如何确定群体规模的大小。根据模式定理可知规模,M,越大越好，但,M,过大又会使计算效率降低，并且若使用比例选择，此时会影响群体的多样性。而,M,过小又会造成未成熟收敛。故实际应用中通常取群体规模为几十至几百。,3,、适应度函数的设计,GA,在进化搜索中基本上不用外部信息，仅用适应度函数作为依据引导搜索。,GA,的目标函数不受连续可微的约束且定义域可为任意集合。对目标函数唯一的要求是，针对输入计算出能加以比较的非负结果即可。这使得遗传算法的应用范围非常广泛。个体的适应度值越大，表明该个体的适应能力越大，易于遗传产生后代。,4,、遗传操作的设计,遗传操作主要包括选择、交叉、变异三个算子。这三个算子都是在随机扰动下进行的，但它们同时又是高效有向的，不同于一般随机搜索算法的无向搜索。遗传操作所选用的类型与所采用的编码方案密切相关。常用的选择方法有,:,适应度比例选择法、最佳个体保留法、排序选择法、联赛法、排挤法等,;,采用二进制编码时，交叉操作常用单点、二点、多点交叉及均匀交叉，变异算子常用基本变异、逆转变异、自适应变异、交换变异。,编码时常用算术交叉法、离散交叉，变异操作常用均匀变异、正态变异、非一致性变异、自适应变异、多级变异等。根据经验可知，将几种交叉或变异算子按一定概率混合使用，将会得到很好的效果。,5,、控制参数的设定,控制参数主要是指群体规模、迭代次数和使用遗传操作的概率等。对于传统的,GA,是以交叉操作为主，变异操作为维持群体多样性的一个辅助性算子，即应用时应选择较大的交叉概率，较小的变异概率。对此标准遗传算法都设为固定值。对于改进后的,GA,，选择、交叉和变异的概率则需视情况而定。,基于模板匹配的图像识别方法,模板匹配的基本思想是以已知的某种目标的模型形成一个灰度矩阵，用该矩阵在图像的搜索范围内分别移动计算其与图像上相应区域的相似度，以相似度最大的位置为待识别目标的位置。,基于灰度相关的匹配,基于灰度相关的匹配算法是一种对待匹配图像的像元以一定大小窗口的灰度阵列按某种或几种相似性度量顺次进行搜索匹配的方法。这类算法的性能主要取决于相似性度量及搜索策略的选择上。匹配窗口大小的选择也是该类方法必须考虑的问题，大窗口对于景物中存在遮挡或图像不光滑的情况会出现误匹配的问题，小窗口不能覆盖足够的强度变化，因此可自适应调整匹配区域的大小来达到较好的匹配结果。,假设参考图像,h,的大小为,mxn,，输入图像,f,的大小是,M,、,N,，其中，,Mm,，,Nn,。下面列举两种成熟的算法,:,归一化积相关灰度匹配和序贯相似检测算法,(SSDA),。,（,1,）、归一化积相关灰度匹配,归一化积相关是一种典型的基于灰度相关的算法，具有不受比例因子误差的影响和抗白噪声干扰能力强等优点，它使用的相似性度量定义如下,:,通过比较参考图像和输入图像在各个位置的相关系数，相关值最大的点就是最佳匹配位置。,（,2,）、序贯相似检测算法,序贯相似匹配算法（,SSDA,）是一种快速图像匹配算法，它使用下式作为相似性度量,:,SSDA,以随机不重复的顺序选取像元对,(a,，,b),，在进行上述求和时不需要计算所有像素，只要其和超过某一设定的阈值，则说明当前位置为非匹配位置，停止本次计算，否则进行下一位置的测试，直至找到匹配点为止。,模板匹配识别流程图,输入图像数据和,模板图像数据,计算模板图像,的特征,确定下一个字,图像的位置,计算子图像,的特征,计算子图与模板图,之间的相似度,确定匹配目标,匹配阈值？,NO,YES,基于遗传算法的图像匹配,1,、基于标准遗传算法的图像匹配算法的基本过程,（,1,）、由于匹配位置的搜索空间随待匹配图像的大小而变化，对模式匹配搜索的位置点进行实数编码。编码的每一位等位基因的范围可根据匹配位置的搜索范围设定。,（,2,）、对种群进行随机初始化，即对染色体初始化。,（,3,）、计算种群中个体的适应度值，为进化做准备。,(4),、通过选择、交叉和变异等遗传操作算子对当前种群进行操作，以产生新的染色体。,(5),、判断种群是否收敛，如果收敛则停止进化,;,(6),、判断种群是否达到了规定的繁衍代数，如果达到则算法停止并返回最好的染色体,;,否则返回,(3),继续执行。,确定控制参数，,编码并初始化种群,代数为,1,计算个体适应度,值并归一化,执行选择算子，父带选,择概率正比于适应度,执行交叉算子，以,Pc,概率进行交叉操作,执行变异算子，以,Pb,概率进行变异操作,终止函数,是否进行到,设定代数,代数自增,1,输出最佳匹,配位置,YES,YES,NO,NO,实验结果,基于标准遗传算法图像匹配的实验参数设置,:,总代数为,200,，种群大小为,50,，交叉率,:0.8,，变异率,:0.008,。图,2,是实验用图像，其中,(a),图是匹配模板图像，大小为,145x120,，,(b),图是待匹配图像，大小为,360X360,。为了对比分析，分别用该模板图像和待匹配图像进行了传统的灰度相关匹配、归一化积相关匹配和,SSDA,匹配，以及基于遗传算法的灰度相关匹配、归一化积相关匹配和,SSAD,匹配。,图,a,图,b,传统的匹配算法性能,匹配算法,匹配点,时间（,ms,）,灰度相关,(119,189),16125,归一化相关,(119,189),25547,SSDA,(113,189),12296,匹配算法,匹配点,时间（,ms,）,灰度相关,(118,189),1125,归一化相关,(118,189),5734,SSDA,(116,203),360,基于遗传算法的匹配算法性能,谢谢大家,