基于Harris和QGA的航空遥感图像配准张博.ppt

基于Harris和QGA的航空 遥感图像配准,答 辩 人：张 博 指导教师：井元伟 教授,绪论,第二部分：章节名称,航空遥感图像配准实验,Northeastern University Nov 12, 2008,Harris角点自动提取并行算法,基于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, 2008,Harris角点自动提取并行算法,Northeastern University Nov 12, 2008,角点检测方法主要有两类：基于图像边缘的方法和基于图像灰度的方法，多使用基于图像灰度的方法。 提取算子主要有：Moravec算子、Hannah算子、Dreschler算子、Forstner算子、Harris算子等。 基本思想：在图像中设计一个局部检测窗口，当该窗口沿各个方向作微小移动时，考察窗口的平均能量变化，当该能量变化超过设定的阈值时，就将窗口的中心像素点提取为角点。 角点检测公式为 (2.1),Harris算子检测原理,Northeastern University Nov 12, 2008,其中 (2.2) 其中， ； ； 。 E 描述了自相关函数在原点的形状，设 和 分别是M 的2个特征值。 和 与局部自相关函数的主曲率成比例，构成一个对M 的旋转不变数。通过判断 和 的值的情况来判断平坦区、角点和边沿。 均很小，则平坦； 一个大一个小，则为边沿； 均很大，则为角点,Harris算子检测原理,Northeastern University Nov 12, 2008,所以Harris角点可定义为下式的局部区域最大值，即角点/边缘响应函数： (2.3) Harris算子在进行角点提取时缺点如下： 依靠人的经验选取阈值T ； 角点分布不均匀。 因此，本文采用划分粗细网格的方法来缩小搜索区域，进而 提高角点提取的效率和精度。算法如下： (1) 划分粗细网格 平均分配粗网格，将剩余的粗网格按照细网格数目进行平均分配。,Harris并行提取算法,Northeastern University Nov 12, 2008,比如设图像大小为 像素，粗网格大小为 像素，细网格大小为 像素，粗细网格划分如表2.1所示，分配到各节点上的网格如表2.2。 表2.1 各节点网格分配 表2.2 图像粗细网格划分,Harris并行提取算法,Northeastern University Nov 12, 2008,(2) 每个处理节点计算本地细网格的熵 在本地每个粗网格中先择一个熵最大的细网格。将剩余部分的熵发送到Master结点。计算节点发送给Master结点的消息结构如图2.1所示。 图2.1 消息结构图,Harris并行提取算法,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) 其中， 和 可以是复数，表示相应状态的概率幅，且满足下列归一化条件：,量子遗传算法算法理论,Northeastern University Nov 12, 2008,(3.2) 表示 的概率， 表示 的概率。 类似于遗传算法的二进制编码，k 个量子比特表示 个状态的基因。 (3.3) 其中， 代表第 t 代、第 j 个个体的染色体，m 为染色体的基因个数，k 为编码每一个基因的量子比特数。 比如量子个体,量子遗传算法算法理论,Northeastern University Nov 12, 2008,表示： 即它代表态 、 、 、 、 、 、 、 的概率分别为0、 、0、 、0、 、0 、 。它用三个量子比特代表示了8个状态。 (2) 量子旋转门 CGA采用交叉、变异来保持种群多样性，QGA利用量子力学的叠加、纠缠、干涉特性设计量子交叉，采用量子逻辑门作用于量子态概率幅的方式保持种群多样性。量子旋转门U(t)是染色体更新的主要手段，如下所示：,量子遗传算法算法理论,Northeastern University Nov 12, 2008,(3.4) 其中为 染色体的第 i 个量子比特， 为旋转角，其大小和方向根据一个事先设计的调整策略而确定。 (3) 量子变异 量子变异的作用主要在于阻止未成熟收敛和提供局部搜索能力。通过量子非门 设计量子变异。 (3.5),量子遗传算法算法理论,Northeastern University Nov 12, 2008,结束,否,是,量子遗传算法算法流程图,是否满足 终止条件,图3.1 量子遗传算法流程图,文献36伴随图像的增大，存储加大、寻优效率降低。 (1) 解的遗传矩阵编码及有效性修复策略 (3.4) 若参考图像中角点 i 与待配准图像中角点 j 匹配成功，则 ; 否则， 。 针对某一行 i 有如下修复操作： 若该行有两个或两个以上的“1”，任取一个“1”，其位置为 则将对应的 i 行和 j 列的其它“1”变为“0”。重复该操作，直至各 行各列最多有一个元素“1”。,Northeastern University Nov 12, 2008,基于QGA的特征点匹配,每个个体由一个 的编码矩阵组成，用一个量子比特位表 达一个基因，由 ， 表示，则原编码矩阵扩展为能 使用叠加规则 的矩阵： (3.5) 其中， 代表基因比特位ij测量值为 的概率， 代表测量值 为 的概率。测量时，对每一个 ，如在0,1中产生一个随机 数 ，对应的基因为1，否则取0，如 取1，则 为0，那 么基因比特位为状态“0”， 的矩阵转化为的 矩阵，实现 了解码。,Northeastern University Nov 12, 2008,基于QGA的特征点匹配,(2) 选取适应度函数 适应度函数是评估当前染色体的优劣程度、也是检验两个角 点子集的匹配程度的函数。 (3.5) 其中， 表示角点 i 与 j 的欧氏距离，用 H 来对不存在匹配的点 给予惩罚。 角点间的相似度估计采用归一化相关法： (3.6),Northeastern University Nov 12, 2008,基于QGA的特征点匹配,程序更关心角点间的匹配程度，因此用H 对存在明显差异的 匹配对给予处罚，表示为 (3.7) 建立的适应度函数如下： (3.8) 其中， 、 表示权参数。 、 和 H 都是固定参数，其数值可 以随着实验的过程逐步调整。m 为参考图像角点子集中的角点数 目。,Northeastern University Nov 12, 2008,基于QGA的特征点匹配,(3) 量子叠加操作 该操作是促进种群朝目前所得到的最好个体演化。量子旋转 门坐标图和本文采用的旋转门操作的角度参照表如下所示。 表3.1 旋转门操作的角度参照表 1 -1 1 -1 图3.2 量子旋转门坐标图,Northeastern University Nov 12, 2008,基于QGA的特征点匹配,本文采用模糊实时控制对旋转角度优化规则模糊化，及时、 自适应地调整旋转角的大小。选取的输入量如下： (3.9) 其中 、 为每代群体的最大、最小适应度值， 为每代群体 中的平均适应值。旋转角为输出量。本文采用单输入单输出的模 糊控制。解模糊化的过程选取重心法。 (4) 量子交叉操作 一方面进行种群内部整个信息交流，另一方面尽可能保留相 对较好基因块。交叉后代 的第 i 行第1对几率幅值为 (3.10),基于QGA的特征点匹配,第 i 行第2对几率幅值为 (3.11) 第 i 行最后一对几率幅值为 (3.12) 若 Nn 就直接向前循环。对于交叉后代的第 i 行第1对几率幅值 为 (3.13) 重复该操作，直到取得N 个交叉后代为止。,基于QGA的特征点匹配,(5) 量子变异操作 以一定的概率 从种群中选取若干个体，并对选中的个体按 确定的概率确定一个或多个变异位，对选中的变异位的量子比特 执行量子非门操作。 对于每个评测、变异修复值，提取出角点匹配排列并且计算 它的互相关度。然后从其中最大的 三个相关度中选取3个染色体 再在其它染色体中任意选取一个，形成新的种群，并且得到一个 最优解。整个过程重复进行，直到达到终止条件，得到满意解。,基于QGA的特征点匹配,Northeastern University Nov 12, 2008,文36中，选取 ， ，而变异概率的设置采取一定的自适应策略，本文算法选取 ， ，种群规模取为4,编码为 。针对如下给出的 二维相关值矩阵 ，可得性能比较如下： 表3.2 QGA与CGA优化性能比较 由表3.2可以看出，本文的量子遗传算法在种群规模只有4的初始条件下，全局寻优能力增强，收敛速度加快；精度大幅提高，测试10次的可靠性也较传统遗传算法有一定的提高。二者的匹配适应度变化情况如图3.3和图3.4所示。,性能分析,性能分析,图3.3 CGA匹配过程适应度变化情况,图3.4 QGA匹配过程适应度变化情况,性能分析,表3.3 不同种群尺寸下的遗传代数及正确率,表3.4 不同编码长度下的遗传代数及正确率,Northeastern University Nov 12, 2008,航空遥感图像配准实验,图4.1 航空遥感图像,图 a,图 b,图a为参考图像,小为 像素素，图b 为待配准大小 像素。对两幅图像依据重叠 区域进行剪切，图 a 右下部分 像素；图b取左上部分 为 像素。分别对剪切图像进行粗细网格划分，运行并行角点提取算法。,图4.2 角点检测结果图,图 c,图 d,图4.3 QGA匹配过程适应度变化情况,图4.4 航空遥感图像的配准结果,Northeastern University Nov 12, 20