基于GEP算法的遥感数字图像匹配

维普资讯 http://www.cqvip.com 计算机与数字工程　第３５卷　基于ＧＥＰ算法的遥感数字图像匹配　吴晓虹陈小辉刘兵　（桂林工学院桂林５４１００４）　摘要基因表达式程序设计（简称ＧＥＰ）是一种新型的遗传算法，它继承了遗传程序设计（简称ＧＰ）和遗传算法（　简称ＧＡ）的优点并且具有更高效和更强的搜索能力，是借鉴生物选择和进化机制发展起来的一种高度并行、随机、自适应　的搜索算法。特别适合于处理像遥感数字图像这样复杂和非线性的问题，尤其是遥感图像匹配问题更是用普通方法难以　解决，介绍表达式程序设计，实现ＧＥＰ算法在遥感数字图像匹配中的函数发现。　关键词基因表达式程序设计（ＧＥＰ）　数字图像处理ＴＰ１８１　图像匹配　中图分类号１　引言　ＧＥＰ是葡萄牙科学家Ｃａｎｄｉｄａ　Ｆｅｒｒｅｉｒａ借鉴生　方法，但在计算和实现上都很困难。　下面介绍一种基于ＧＥＰ算法的图像纹理匹配　的方法。假设图像经过位移、旋转或变形，其主要　物遗传的基因表达规律提出的一种知识发现新技　术。ＧＥＰ作为一种通用的自适应式随机搜索算　法，能够在缺乏先验知识，不了解事物内部机制，只　有实验数据的情况下挖掘出较为准确的公式，以其　的特征和纹理却没有改变，把图像的特殊纹理位置　当作样品点，如图１所示。　较强的普适性和较高的精确度在很多应用领域都　取得了很好的实际效果。它提供自动程序设计的　一种可行方法并且继承了遗传程序设计和遗传算　图１遥感变易扭曲图　法的优点，具有更简单的编码表示方法、更强大的　遗传算子（遗传算子的种类和数量不存在任何限　制）、更易于遗传操作、能产生更高级别的复杂度　的能力，具有更强的解决问题的能力。　近年来，ＧＥＰ已开始用于自动控制、人工智　能、图像处理和模式识别等方面。图像匹配是图像　２　基因表达式程序设计　２．１　ＧＥＰ基因结构及编码　在ＧＥＰ中，基因是由头部和尾部两部分组成。　处理中一个重要的课题，在计算机视觉、运动目标　跟踪与识别、航空航天技术、医学图像处理等领域　头部是由终结符和函数符号组成，而尾部则只能是　由终结符组成。假设头部的长度为ｈ，尾部的长度　为ｔ，则它们之间的关系为：　ｔ＝ｈ　（ｒｌ一１）＋１　（１）　有广阔的应用前景。图像相关性在提高图像匹配　的精度和计算速度一直是研究的热点。传统的序　贯相似性检测算法（ＳＳＤＡ）是将模板在图上逐像素　平移并计算相关值，相关值最大处即为匹配最好　处．该方法匹配精度高，算法稳定，但计算量大，难　以用于实时性要求高的场合。近年来改进的算法　在快速性方面效果并不明显。一些学者还提出了　其中：ｒｌ表示在函数符号集中所需变量数最多　的函数的参数个数。在公式（１）中，由于尾部与头　部所具有的特殊关系，使得ＧＥＰ的基因在任何遗　传算子的作用下都不会产生句法上不正确的个体。　假设有如下函数表达式：　口，ｂ）＝√６（口一ｂ）　ｂ　（２）　快速傅立叶变换（ＦＦＴ）的相关算法，和小波变换的　收到本文时间：２００７年６月１３日　基金项目：国家“９７３”计划项目“大型矿集区识别与预测”（编号：２００１ＣＤ４０９８０９）资助。　作者简介：吴晓虹，女，硕士研究生，研究方向：遗传算法与数据挖掘。陈晓辉，男，高级工程师：研究方向：图像处理　与数据挖掘。刘兵，男，硕士研究生：研究方向：数字图像处理与机器学习。　维普资讯 http://www.cqvip.com 第３５卷（２００７）第１０期　计算机与数字工程　９３　显然，公式（２）的函数符号集Ｆ＝｛＋，一，　，　Ｑ｝，终结符集Ｔ＝｛ａ，ｂ｝，１１＝２。它可以被编码成　一精度小于或等于０．Ｏ１时，可以认为它等于０。在　ＧＥＰ中基于误差的适应度计算普遍采用公式（５）。　个Ｋ一树表达式：＋Ｑ　一ｂａｂｂ　（３）　若设式（３）中头部长度ｈ＝４，则尾部长度ｔ＝　４，所以，这个基因的长度为９。如式（４）所示：　＋Ｑ：ｌ：一ｂａｂｂａ　（４）　３　数据采集与参数设置　３．１抽样数据采集　在式（４）中，黑体是填充部分，在原来表达式　中并不存在，在编码成基因时根据终结符集中的符　号随机产生；前面一部分则是有效部分，通过遍历　在相应的纹理曲线处选取２０个特殊的样品　点，作为图像校准的基准点。如岩石的断裂点、高　点或溶洞。因为这些数据点是地质变化的特殊位　置，一般不会随图像的变动而失去特性，在取得数　表达式树而得到的符号序列。式（３）可以被描述　成一个表达式树，如图２所示。　把Ｋ一树表达式转换　成表达式树时，从左至右，　按层遍历表达式树即可。　２．２　ＧＥＰ的遗传算子　２．２．１选择算子　利用适应度函数来选　图２式（２．３）的表达式树择那些具有较好适应度的　个体复制到下一代。　２．２．２变异算子　在遗传操作过程中，变异算子可以发生在染色　体的任何位置。　２．２．３重组算子　ＧＥＰ中的重组算子也有三种：单点重组、两点　重组和基因重组。　２．２．４转换和插入序列元素　ＧＥＰ中有Ｉｓ转换元素、ＲＩＳ转换元素和基因　转换。　２．３　ＧＥＰ的适应度函数　适应度是通过适应度函数来得到的，不同问题　所选用的适应度函数不一定相同。在ＧＥＰ中，为　了解决符号回归，Ｆｅｒｒｅｉｒａ，Ｃ．提出了两种适应度　函数：公式（５）是基于绝对误差的，（５）则是基于相　对误差。　ＣＩ　＝荟（　一Ｉ　ｃ（口）一　Ｉ）　（５）　＝　（　一Ｉ　Ｉ）　（６）　Ｊ　（Ｊ）　其中：Ｍ是一个常数，表示种群的选择范围，　在这个范围内种群开始初始化；Ｃ　表示第ｉ个染　色体利用函数关系式在第ｊ个样本中的变量数据　所求得的函数值；Ｔｊ表示第ｊ个样本包含实际测量　值，则Ｃ（　）＝ｆ（ｘｌ，ｙ１），Ｔ　＝ｚ１）；Ｃ　表示样本数　目。显然，当Ｃ　，）＝Ｔ　寸，适应度函数取得最大值　ｔ—ｆｍ　一ｃ　Ｍ。在实际应用中，当Ｉ　ｃ㈨）一Ｔ　的　据中对应ｘ轴方向和Ｙ轴方向的变换，其函数的　对应关系如图３所示：　１５００　纹理曲线图　１０ｏ０　黎５００　０　１　３　５　７　９　１１　１３　１５　１７　１９　样品点数　１５００　ｔ　１０００　黎５００　０１　３　５　７　９　１１　１３　１５　１７　１９　样品点数　图３纹理曲线图　３．２图像匹配关系函数的设置　经大量试验测试，对ＧＥＰ参数进行设定如表１。　表１　ＧＥＰ参数值表　参数名称　参数值　适应值函数　绝对值类型　Ｅｖｏｌｕｔｉｏｎ　Ｓｔｒａｔｅｇｙ　（Ｕ＋入）入＝１０　Ｓｅｌｅｃｔｉｏｎ　Ｓｔｒａｔｅｇｙ　Ｒｏｕｌｅｔｔｅ　Ｗｈｅｅｌ　Ｐｏｐｕｌａｔｉｏｎ　Ｓｉｚｅ　２００　Ｇｅｎｅｒａｔｉｏｎ　１００００　函数集　＋，～，　，／，ｅｘｐ（）　（），ｓｆｍ（），ＣＯＳ（），ｓｑｒｔ（）　基因参数　基因数＝２；头长＝２；身长＝１１　同源基因：头长＝１；身长＝３　遗传操作算子参数　ＩＳＴｒａｎｓＲａｔｅ＝Ｏ．１：ＲｌＳＴｒａｎｓＲａｔｅ＝Ｏ．１：　ＧｅｎｅＴｒａｎｓＲａｔｅ＝Ｏ．１：　１～ｐｏｉｎｔＲｅｃＲａｔｅ＝０．１：　２一ｐｏｉｎｔＲｅｃＲａｔｅ＝０．１：　ＧｅｎｅＲｅＲａｔｅ＝Ｏ．１：　ＭｕｔａｔｉｏｎＲａｔｅ＝０．４　４　实验结果与关系发现　运用ＧＥＰ程序对样品点进行对应的ｘ轴纹理　图像的校准函数关系发现，得到如下函数关系式：　适应值：６３６．６７共有２个基因　０：＝Ｌｎ（Ｌｎ（Ｓｉｎ（Ｅｘｐ（（ａ一（ａ／Ｓｉｎ（ａ）））））））　１：＝Ｌｎ（（（ａ／Ｌｎ（（Ｓｑｒｔ（（（（一８．２１２２３）＋ａ）　一（８、３５４４￣・）））＋Ｃｏｓ（Ｓｑｒｔ（ａ）））））＋（一８．　维普资讯 http://www.cqvip.com

吴晓虹等：基于ＧＥＰ算法的遥感数字图像匹配　第３５卷　２１２２３）））　关系函数中的ａ代表样品点的ｘ坐标，得出　关系式子为：　Ｘ　＝Ｅｘｐ（Ｌｎ（（（Ｘ。／Ｌｎ（（Ｓｑｒｔ（（（（一８．　２１２２３）＋Ｘ）一（８．３５４４４．）））＋Ｃｏｓ（Ｓｑｒｔ（Ｘ）））））　＋（一８．２１２２３））））　表２基因表达式运算拟合结果表　同源基因：＝Ｅｘｐ（１）　原始串ＬＬＳＥ—ａ／ａＳａａＱ／ａａａａａａ？ａ？ａａ？ａａＬ　＋／？ａＬ＋Ｑｃ—Ｑ＋？ａ？ａａ？ａａａａａａ？ａａＥ１／　Ｅ１１Ｏ００　同理，根据样品点　Ｙ轴的坐标，运行ＧＥＰ　程序得到如下式子：　０：＝（（ａ＋Ｓｉｎ（（ａ　＋ａ）））＋（（（ａ，ｌ：ａ）／　（ａ＋ａ））＋（Ｓｑｒｔ（ａ）＋　（ａ＋ａ））））＝２／７ａ＋　Ｓｉｎ２ａ＋　１：＝Ｃｏｓ（Ｅｘｐ（Ｓｉｎ　（（（０．２８５９６）＋ａ））））　同源基因：：（０一　（Ｓｑ￣（Ｏ）／１））　则得到样品点Ｙ坐标的函数关系式子为：　Ｙ１＝２／７　Ｙ。＋Ｓｉｎ２　ｙｏ＋　一　参考文献　［１］Ｆｅｒｒｅｉｒａ　Ｃ．Ｇｅｎｅ　ｅｘｐｒｅｓｓｉｏｎ　ｐｒｏｇｒａｍｍｉｎｇ［Ｍ］．Ｐｏｒｔｕｇａｌ，　Ａｎｇｒａ　ｄｏ　Ｈｅｒｏｉｓｍｏ，２００２　Ｃｏｓ（Ｅｘｐ（Ｓｉｎ（（（０．２８５９６）＋Ｙ０）））））／　Ｃｏｓ（Ｅｘｐ（Ｓｉｎ（（（Ｏ．２８５９６）＋Ｙ））））　（７）　［２儿日］玄光男，程润传．遗传算法与工程设计［Ｍ］．北京：　科学出版社，２０００　［３］龚文引，蔡之华．基因表达式程序设计的原理及应用　５　结束语　实验结果表明，用这种方法进行图像匹配不但　［Ｊ］．微计算机信息，２００５，２２：１６９—１７１　［４］黄晓冬，唐常杰．基于ＧＥＰ的函数关系挖掘及其在数据　滤波中的应用［Ｊ］．四川大学学报，２００４，４：１６—２２　［５］张国柱、王程、王润生．基于小波变换的多分辨图像匹　配方法［Ｊ］．计算机工程与应用，２００１，１３：１１３—１１４　［６］万胜前，杨坤涛．基于区域分割与嫡差匹配相结合的帧　解决了图像变化的非线形运算，还可以对图像歪斜　等变化很大的图像变化也适应。该方法在图像匹　配过程中要进行样品点的采集，对于图像的分辨率　高低会有一定影响，样品点的采集方法也会产生一　定误差。但基本可以控制在误差范围以内，能满足　误差限制的要求。在这种无线形关系的图像匹配　间预测编码方法研究［Ｊ］．２１世纪教育前沿，２００５，１５　（１２０）：１９—２１　中，ＧＥＰ算法有着强大的优势，在进行误差评价的　结果中效果良好，它解决了运算速度和正确性的要　求。是图像匹配中新方法的探索。　［７］楼兵军，樊来耀基于区域的图像匹配算法的关键技术研　究［Ｄ］．西安电子科技大学硕士学位论文，２ＯＯ６，２：２８—３７　［８］ＳＨ７７６０．ｐｄｆ．Ｈｉｔａｃｈｉ　ＳｕｐｅｒＨ　ＲＩＳＣ　ｅｎｇｉｎｅ　ＳＨ７７６０　Ｈａｒｄ—　ｗａｒｅ　Ｍａｎｕａ１．Ｒｅｎｅｓａｓ　Ｉｎｃ，２００３　（上接第８８页）　［４］Ｒ２—０６２４５６．Ｅｍａｉｌ　ｄｉｓｃｕｓｓｉｏｎ“Ｉｎｆｏｒｍａｔｉｏｎ　ｏｆ　ｐｒｅａｍｂｌｅ　ｆｏｒ　ｕｎｓｙｎｃｈｒｏｎｉｚｅｄ　ｒａｎｄｏｍ　ａｃｃｅｓｓ”．ＬＧ　Ｅｌｅｃｔｒｏｎｉｃｓ．３　ＧＰＰ　ＴＳＧ　ＲＡＮ　ＷＧ２　Ｍｅｅｔｉｎｇ＃５４，Ｔａｌｌｉｎｎ，Ｅｓｔｏｎｉａ，２８　ｏｆ　Ａｕ．　ｇｕｓｔ一１　ｏｆ　Ｓｅｐｔｅｍｂｅｒ，２００６　Ｍｅｅｔｉｎｇ，Ａｔｈｅｎｓ，Ｇｒｅｅｃｅ，２７—３１　Ｍａｒ，２００６　　ｌ７　ｌ　Ｒ２—０６１９９０．Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｃｏｌｌｉｓｉｏｎ　Ｐｒｏｂａｂｉｌｉｔｙ　ａｎｄ　Ｌｏａｄ　Ｅｓｔｉｍａｔｅｓ．Ｍｏｔｏｒｏｌａ．３　ＧＰＰ　ＴＳＧ—ＲＡＮ　ＷＧ２　ＬＴＥ　ＡＨ，Ｃａｎｎｅｓ，Ｆｒａｎｃｅ，Ｊｕｎｅ　２７—３０，２００６　［８］Ｒ１—０６２１７６．Ｃｏｌｌｉｓｉｏｎ　ｐｒｏｂａｂｉｌｉｔｙ　ａｎａｌｙｓｉｓ　ｏｆ　ＡＣＨ　ｗｉＲｔｈ　ｃｏｎｔｒｏｌ　ｉｆｏｒｎｍａｔｉｏｎ．ＴＳＧ—ＲＡＮ　ＷＧ１　Ｍｅｅｔｉｎｇ＃４６．　Ｔａｌｌｉｎｎ，Ｅｓｔｏｎｉａ，Ａｕｇｕｓｔ　２８～Ｓｅｐｔｅｍｂｅｒ　１，２００６　［５］Ｉｔ２—０６２３９４．Ｉｎｉｔｉａｌ　ａｃｃｅｓｓ　ａｎｄ　Ｃ—ＲＮＴＩ　ａｌｌｏｃａｔｉｏｎ　ｆｏｒ　ＴＤＤ．ＣＡＴＹ，３ＧＰＰ　ＴＳＧ　ＲＡＮ　ＷＧ２＃５４，Ｔａｌｌｉｎｎ，Ｅｓｔｏｎｉ．　ａ．２８　Ａｕｇｕｓｔ一１。‘Ｓｅｐｔ　２００６　［９］蒋守宁．ＬＴＥ接入技术研究报告［ｃ］．大唐移动通信设　备有限公司　［６］Ｒ１—０６０９３２．ＥＵＴＲＡ　ＴＤＤ　Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｐｒｏｃｅｄｕｒｅ．　ＣＡＴｒ，ＲＩＴＩ＂，ＴＤ—Ｔｅｃｈ，３ＧＰＰ　ＴＳＧ　ＲＡＮ　ＷＧ１＃４４ｂｉｓ