[交通运输]基于Harris和QGA的航空遥感图像配准张博

基于基于Harris和和QGA的航空的航空遥感图像配准遥感图像配准答 辩 人：张 博指导教师：井元伟 教授绪论第二部分：章节名称航空遥感图像配准实验Northeastern University Nov 12,2008Harris角点自动提取并行算法基于QGA的特征点匹配结论与展望Northeastern University Nov 12,2008绪论 传感器技术、航空航天技术、光学技术以及通讯技术快速发展，遥感技术已经进入一个能够动态、快速、准确提供多种对地观测数据的新阶段；遥感技术在环境监测、国土资源勘探、军事侦察以及考古等许多领域中发挥着越来越重要的作用，因而航空遥感图像的配准也就日显重要；飞行高度以及摄像设备等各种因素的限制，在研究区域较大时，需要多幅遥感图像才能覆盖的情况，这需要将覆盖研究区域的那些数字图像进行拼接，便于进行统一的处理、解译、研究和分析工作。课题的研究背景及意义Northeastern University Nov 12,2008定义：对取自不同时间、不同传感器或不同视角的同一景物的两 幅图像或多幅图像进行匹配、叠加的过程。目的：精确找出相邻两幅图像中重叠部分的位置,然后确定两幅图 像的变换关系，建立变换模型，为图像融合作准备。图像配准的概念目的输入图像预处理图像配准建立图像变换模型统一坐标变换图像融合全景图像图1.1 图像拼接基本流程 Northeastern University Nov 12,2008 基于图像特征的图像配准：基于图像特征的图像配准：利用图像的明显特征来估计图像之间的变换,而不是利用图像的全部信息。比如图像的特征点（角点或关键点）、轮廓和一些不变矩等。控制点配准算法自动角点检测配准算法基于轮廓特征的配准算法基于SIFT（尺度不变特征变换）基于区域的图像配准：基于区域的图像配准：首先直接利用整幅图像的灰度度量两幅图像之间的相似性,然后利用搜索方法寻找使相似性度最大或最小值点,从而确定两幅图像之间的变换模型参数。对数极坐标变换方法相关法最大互信息配准法 图像配准的相关方法基于特征的图像配准是目前较成熟的配准方法，有三大优点：计算量小；配准精度高；适应能力强。该方法的关键问题是：提高配准的效率，增强实时性要求；提高配准的精度，增强实地性要求。本文的解决办法：缩小特征点搜索区域，均匀提取特征点；采用量子遗传算法进行寻优。Northeastern University Nov 12,2008本文的出发点Northeastern University Nov 12,2008Harris角点自动提取并行算法Northeastern University Nov 12,2008 角点检测方法主要有两类：基于图像边缘的方法和基于图像灰度的方法，多使用基于图像灰度的方法。提取算子主要有：Moravec算子、Hannah算子、Dreschler算子、Forstner算子、Harris算子等。基本思想：在图像中设计一个局部检测窗口，当该窗口沿各个方向作微小移动时，考察窗口的平均能量变化，当该能量变化超过设定的阈值时，就将窗口的中心像素点提取为角点。角点检测公式为 (2.1)Harris算子检测原理2T,EwIIx yu vu vxu yvxyMxyNortheastern University Nov 12,2008其中 (2.2)其中，；。E 描述了自相关函数在原点的形状，设 和 分别是M 的2个特征值。和 与局部自相关函数的主曲率成比例，构成一个对M 的旋转不变数。通过判断 和 的值的情况来判断平坦区、角点和边沿。均很小，则平坦；一个大一个小，则为边沿；均很大，则为角点Harris算子检测原理22IIIxxyMIIIxyy(1,0,1)IIIxx 2IIIxxx2IIIyyy121212Northeastern University Nov 12,2008 所以Harris角点可定义为下式的局部区域最大值，即角点/边缘响应函数：(2.3)Harris算子在进行角点提取时缺点如下：依靠人的经验选取阈值T；角点分布不均匀。因此，本文采用划分粗细网格的方法来缩小搜索区域，进而 提高角点提取的效率和精度。算法如下：(1)划分粗细网格 平均分配粗网格，将剩余的粗网格按照细网格数目进行平均分配。Harris并行提取算法222222()xyxyxyRIII Ik IINortheastern University Nov 12,2008比如设图像大小为 像素，粗网格大小为 像素，细网格大小为 像素，粗细网格划分如表2.1所示，分配到各节点上的网格如表2.2。表2.1 各节点网格分配 表2.2 图像粗细网格划分 Harris并行提取算法8 8160 9632 32 1P2PnP1N2N3N4N21nN2nN211112()nNnn1N2N3N13N14N15N11n22n12n21n212122()nNnn211112()nNnnNortheastern University Nov 12,2008 (2)每个处理节点计算本地细网格的熵 在本地每个粗网格中先择一个熵最大的细网格。将剩余部分的熵发送到Master结点。计算节点发送给Master结点的消息结构如图2.1所示。图2.1 消息结构图0 2.43 5.78 1.021 0.37 6.191P1N12n21n22n12n11n1P21nNHarris并行提取算法Northeastern University Nov 12,2008 (3)Master结点在剩余的细网格中选择熵较大的部分细网格。首先判断是否在同一节点上处理，对于分配到多个处理节点的粗网格，Master结点首先在这个粗网格中选择一个细网格，然后将剩余的所有细网格排序，选择较大的部分细网格，而后平均分配细网格。(4)每个处理节点在Master结点进行步骤(3)的同时在本地的细网格中选择角点。接收到消息后，在剩余细网格中选择角点，最后将选择的角点传送到 Master结点。划分粗细网格提取角点优点：角点分配均匀；角点位置信息精确。Harris并行提取算法Northeastern University Nov 12,2008基于QGA的特征点匹配Northeastern University Nov 12,2008 量子遗传算法(Quantum Genetic Algorithm,QGA)是一种基于概率的遗传算法，是量子理论与遗传算法相结合的产物，由韩国学者Kuk-Hyun Han等人于20世纪末提出。相比CGA优点如下：种群规模小；更好的种群多样性和全局寻优能力；进化过程利用了个体进化的历史信息，搜索速度快。(1)量子比特编码 (3.1)其中，和 可以是复数，表示相应状态的概率幅，且满足下列归一化条件：量子遗传算法算法理论01Northeastern University Nov 12,2008(3.2)表示 的概率，表示 的概率。类似于遗传算法的二进制编码，k 个量子比特表示 个状态的基因。(3.3)其中，代表第 t 代、第 j 个个体的染色体，m 为染色体的基因个数，k 为编码每一个基因的量子比特数。比如量子个体量子遗传算法算法理论2k121211122122121211122122kkmmmktjkkmmmkqtjq1202232122Q2212021Northeastern University Nov 12,2008表示：即它代表态 、的概率分别为0、0、0、0、。它用三个量子比特代表示了8个状态。(2)量子旋转门 CGA采用交叉、变异来保持种群多样性，QGA利用量子力学的叠加、纠缠、干涉特性设计量子交叉，采用量子逻辑门作用于量子态概率幅的方式保持种群多样性。量子旋转门U(t)是染色体更新的主要手段，如下所示：量子遗传算法算法理论26260 0000010 0100110 1001010 110111444400000101001110010111011118381838Northeastern University Nov 12,2008 (3.4)其中为 染色体的第 i 个量子比特，为旋转角，其大小和方向根据一个事先设计的调整策略而确定。(3)量子变异 量子变异的作用主要在于阻止未成熟收敛和提供局部搜索能力。通过量子非门 设计量子变异。(3.5)量子遗传算法算法理论cos()sin()sin()cos()iiiiiiiiiiinotU0110iiiiiiiinotUNortheastern University Nov 12,2008确定实际问题参数集初始化种群Q(T)测量Q(T)得状态P(T)评价P(T)量子遗传操作群体Q(T+1)1）位串解码得到参数2）计算目标函数值3）函数值向适应度值射4）适应度调整三个基本算子：1）叠加2）交叉3）变异 结束否是量子遗传算法算法流程图记录最佳个体状态是否满足终止条件图3.1 量子遗传算法流程图 文献36伴随图像的增大，存储加大、寻优效率降低。(1)解的遗传矩阵编码及有效性修复策略 (3.4)若参考图像中角点 i 与待配准图像中角点 j 匹配成功，则 ;否则，。针对某一行 i 有如下修复操作：若该行有两个或两个以上的“1”，任取一个“1”，其位置为 则将对应的 i 行和 j 列的其它“1”变为“0”。重复该操作，直至各行各列最多有一个元素“1”。Northeastern University Nov 12,2008基于QGA的特征点匹配1111nnnnaaAaa0ija1ijaija 每个个体由一个 的编码矩阵组成，用一个量子比特位表达一个基因，由 ，表示，则原编码矩阵扩展为能使用叠加规则 的矩阵：(3.5)其中，代表基因比特位ij测量值为 的概率，代表测量值为 的概率。测量时，对每一个 ，如在0,1中产生一个随机数 ，对应的基因为1，否则取0，如 取1，则 为0，那么基因比特位为状态“0”，的矩阵转化为的 矩阵，实现了解码。Northeastern University Nov 12,2008基于QGA的特征点匹配n n()Tijij(1,)i jn2n n111211112121222212221212.nnntnjnnnnnnnnq2|ij|02|ij|12|ij2|ijr2|ij2|ij2n nn n (2)选取适应度函数 适应度函数是评估当前染色体的优劣程度、也是检验两个角点子集的匹配程度的函数。(3.5)其中，表示角点 i 与 j 的欧氏距离，用 H 来对不存在匹配的点给予惩罚。角点间的相似度估计采用归一化相关法：(3.6)Northeastern University Nov 12,2008基于QGA的特征点匹配(0)(0)(0)(0)ijija aijijijddif aand adHif aor aijd22(,)(,)(,)(,)(,)jkkjkiijjkkkkkiikkkW xyuW xyuW xyuNCC i jW xyu 程序更关心角点间的匹配程度，因此用H 对存在明显差异的匹配对给予处罚，表示为(3.7)建立的适应度函数如下：(3.8)其中，、表示权参数。、和 H 都是固定参数，其数值可以随着实验的过程逐步调整。m 为参考图像角点子集中的角点数目。Northeastern University Nov 12,2008基于QGA的特征点匹配00(,)ijijijijifHifNCC i jgggg12111mijmmiijij ifgd 1212 (3)量子叠加操作 该操作是促进种群朝目前所得到的最好个体演化。量子旋转门坐标图和本文采用的旋转门操作的角度参照表如下所示。表3.1 旋转门操作的角度参照表 1 -1 1 -1图3.2 量子旋转门坐标图Northeastern University Nov 12,2008基于QGA的特征点匹配参考个体各基因位值旋转角度0000000000000010101010 xb 本文采用模糊实时控制对旋转角度优化规则模糊化，及时、自适应地调整旋转角的大小。选取的输入量如下：(3.9)其中 、为每代群体的最大、最小适应度值，为每代群体中的平均适应值。旋转角为输出量。本文采用单输入单输出的模糊控制。解模糊化的过程选取重心法。(4)量子交叉操作 一方面进行种群内部整个信息交流，另一方面尽可能保留相对较好基因块。交叉后代 的第 i 行第1对几率幅值为(3.10)avgf基于QGA的特征点匹配maxmaxminavgeffffmaxfminf211111121111-()()()()2)()iiiiiCCqqC1C第 i 行第2对几率幅值为 (3.11)第 i 行最后一对几率幅值为(3.12)若 Nn 就直接向前循环。对于交叉后代的第 i 行第1对几率幅值为(3.13)重复该操作，直到取得N 个交叉后代为止。212122232121-()()()()2)()iiiiiCCqqC基于QGA的特征点匹配211111-()()()()2)()ininninnininCCqqC221212131211()()()()2()iiiiiCCqqC (5)量子变异操作 以一定的概率 从种群中选取若干个体，并对选中的个体按确定的概率确定一个或多个变异位，对选中的变异位的量子比特执行量子非门操作。对于每个评测、变异修复值，提取出角点匹配排列并且计算它的互相关度。然后从其中最大的 三个相关度中选取3个染色体再在其它染色体中任意选取一个，形成新的种群，并且得到一个最优解。整个过程重复进行，直到达到终止条件，得到满意解。基于QGA的特征点匹配mPNortheastern University Nov 12,2008 文36中，选取 ，而变异概率的设置采取一定的自适应策略，本文算法选取 ，种群规模取为4,编码为 。针对如下给出的 二维相关值矩阵 ，可得性能比较如下：表3.2 QGA与CGA优化性能比较 由表3.2可以看出，本文的量子遗传算法在种群规模只有4的初始条件下，全局寻优能力增强，收敛速度加快；精度大幅提高，测试10次的可靠性也较传统遗传算法有一定的提高。二者的匹配适应度变化情况如图3.3和图3.4所示。性能分析maxT400.8cp maxT200.4cp 8 88 8fV测试项 最优解种群规模最大迭代次数最优解开始迭代代测试10次的方差平均寻优时间(ms)QGA 0.680391420100.078256328 CGA 0.5460373040130.119460459性能分析24681012141618200.20.250.30.350.40.450.50.55generationaverage fitness 24681012141618200.20.250.30.350.40.450.50.550.60.650.7generationaverage fitness图3.3 CGA匹配过程适应度变化情况图3.4 QGA匹配过程适应度变化情况性能分析群体大小遗传代数正确率(%)41079.2102380.5153082.7编码大小遗传代数正确率(%)878.21178.71379.244表3.3 不同种群尺寸下的遗传代数及正确率表3.4 不同编码长度下的遗传代数及正确率6 68 8Northeastern University Nov 12,2008航空遥感图像配准实验图4.1 航空遥感图像 图 a 图 b 图a为参考图像,小为 像素素，图b 为待配准大小 像素。对两幅图像依据重叠 区域进行剪切，图 a 右下部分 像素；图b取左上部分 为 像素。分别对剪切图像进行粗细网格划分，运行并行角点提取算法。335 472306 386300 420260 36050100150200250300501001502002503003504005010015020025050100150200250300350图4.2 角点检测结果图图 c图 d24681012141618200.350.40.450.50.550.60.650.7genetationaverage fitness图4.3 QGA匹配过程适应度变化情况图4.4 航空遥感图像的配准结果Northeastern University Nov 12,2008结论与展望 本文主要结论：通过对相邻时刻两幅图像划分粗细网格进行Harris角点提取提取结果均匀分布，即保证了信息量丰富区域图像配准精度，又保证了匮乏区域配准的精确度，同时大幅提高了配准的效率。QGA运用于角点匹配的寻优过程，在小的种群的初始条件下，达到比CGA性能更优的结果，仿真验证了本文算法的可行性与有效性。展望 通过改变量子比特编码形式减少存储量，提高更新速度；如何在处理大幅图像时改进量子遗传算法。Northeastern University Nov 12,2008