当前位置:首页>> >>


三角形约束下影像匹配算法实现.rar

收藏

资源目录
    文档预览:
    编号:20180915222317682    类型:共享资源    大小:666.68KB    格式:RAR    上传时间:2018-09-15
    尺寸:148x200像素    分辨率:72dpi   颜色:RGB    工具:   
    20
    金币
    关 键 词:
    三角形 约束 影像 匹配 算法 实现
    资源描述:
    编号:10009410430南阳师范学院 2014 届毕业生毕业论文(设计)题 目: 三角形约束下影像匹配算法实现 完 成 人: 张迎迎 班 级: 2010-04 学 制: 4 年 专 业: 测绘工程专业 指导教师: 苏 博 完成日期: 2010-03-15 目 录摘要 ∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ (1)1绪 论 ∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ (1)1.1 影像匹配技术描述 ∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ (1)1.2 影像匹配技术研究的意义与现状∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ (2)2基于三角形约束下影像匹配原理 ∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ (2)2.1Delaunay 三角网 ∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ (2)2.2 三角形约束下影像匹配传播算法∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ (3)2.3 三角形约束下影像匹配算法实现数据处理流程 ∙∙∙∙∙∙∙∙∙∙∙∙∙∙ (4)3三角形约束下影像匹配算法实现中的关键问题 ∙∙∙∙∙∙∙∙∙∙∙∙ (4)3.1 数据结构∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ (5)3.2 特征点索引 ∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ (5)3.3 三角形优先级 ∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ (6)3.4 特征点匹配 ∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ (7)4三角形约束下影像匹配算法的效率与实用性试验分析 ∙∙∙∙∙∙ (7)4.1 三角形约束下影相匹配算法的效率与实用性试验分析 ∙∙∙∙∙∙∙∙∙ (7)5结束语 ∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ (9)致谢 ∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ (11)参考文献 ∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ (12)第 0 页 共 13 页三角形约束下影像匹配算法实现作 者:张迎迎指导教师:苏 博摘 要:立体影像匹配是数字摄影测量和计算机视觉的核心技术,被广泛应用于多个领域。可以说,立体影像匹配技术的发展程度决定了数字摄影测量的自动化程度。本文选择了三角网约束下影像匹配技术作为主要的研究内容,围绕着匹配算法和技术流程,对涉及到的方法和理论进行了深入的分析和研究,并在此基础上建立了三角形约束下影像匹配的试验系统。 本文通过对现有立体影像匹配技术的对比、分析和总结,给出了立体影像匹配系统的基本构成形式,在此基础上提出了三角网约束下影像匹配算法,并详细的阐述了该算法的每个部分。首先,介绍了常见的影像匹配算法,然后,从约束条件方面详细的说明了本文提出的匹配系统。最后的实验证明,根据三角形约束下影像匹配方法的基本原理,结合具体实现过程中对时间效率及空间效率两方面的考虑,探讨了算法实现中的关键问题。针对三角形约束下影像匹配方法的实际应用,分析了所采用的数据结构与 Delaunay 三角网动态更新,提出了一种高效的实现算法,实际应用验证了其实现的有效性。实验结果表明这些应用都是成功的,取得了一定的效果。 最后,对本文的主要工作进行了总结并进行了展望。关键词:三角形约束;影像匹配;算法实现;效率1 绪论1.1 影像匹配技术描述影像匹配是影像分析和影像处理研究中的一项重要的技术。在计算机视觉识别过程中,常常需要把不同的传感器或是同一传感器在不同时间、不同成像条件下对同一景物获取的两幅或多幅影像,进行比较找到该组影像中的共有景物,或是根据已知模式到另一幅图中寻找相应的模式,这就叫影像匹配。影像匹配就是将模版与待检测的影像进行比较匹配,并给出一个描述匹配程度的计算结果。如果算法的运算结果显示影像中的某一部分与模版相同或相似大于第 1 页 共 13 页给定的阈值,认为匹配成功。一般来说,由于影像在不同时间、不同传感器、不同视角获得的成像条件不同,因此即使是对同一物体,在影像中所表现出来的几何特性、光学特性、空间位置都会有很大的不同,如果考虑到噪声、干扰等影响会使影像发生很大差异,影像匹配就是通过这些不同之处找到它们的相同点。1.2 影像匹配技术研究意义和现状影像匹配最早是美国70年代从事飞行器辅助导航系统,武器投射系统的末制导及寻地等应用研究中提出的。随着科学技术的快速发展,影像匹配已经成为近代信息处理,尤其是影像信息处理领域中一项极为基本和重要的技术。其应用已逐步扩大到其他领域,如计算机视觉、目标识别与跟踪、测绘、航空摄影测量、资源分析、气象预报、光学和雷达跟踪、机器人视觉、环境检测、地图绘制、文字识别以及景物分析中的变换检测、立体视觉、飞行器巡航制导、遥感、视觉控制、医学图像、视觉运动计算、导弹的地形图和地图匹配、工业流水线的自动监控等多个领域。长期以来立体影像匹配一直都是数字摄影测量的核心问题。朱庆等提出了一种三角形约束下影像匹配方法,利用已知良好匹配点,在Delaunay三角网的约束下,进行纹理特征自适应的匹配传播,因新的匹配点对Delaunay三角网进行动态细化,使得局部几何约束区域的大小自动适应影响纹理特征变化,从而得到更加可靠的匹配结果。因该算法涉及大量影像数据及其特征点的处理,故在具体实现算法时,需要进行优化设计。2基于三角形约束下影像匹配原理2.1 Delaunay 三角网由于 Delaunay 三角形具有易于构建与稳健的特点,本文采用Delaunay 三角形法则构建初始良好点三角网,在每一个三角形中,三个可靠的顶点形成了一个局部的连续约束区域,顶点也是后续匹第 2 页 共 13 页配传播的参考点,在匹配传播过程中,不断获得新的匹配点,并将最新匹配点适时插入三角网中,三角网因此不断被动态更新,直到满足一定的匹配终止条件2.2 三角形约束下影像匹配传播算法影像匹配过程开始于一定数量的良好匹配点所构成的三角网,在每对同名三角形内成功匹配出同名点后,左、右像上的三角网分别在局部得到细化更新,然后继续在每对新的同名三角形内提取出特征点,并选择最优的三角形顶点作为参考点进行新的匹配。显然,三角网的逐步细化自然的适应了影像纹理的分布特征,而且细化后的三角网将在后续匹配的过程中限定了更小的连续性约束和顺序约束区域。这是一个不断迭代的匹配传播过程,匹配的终止条件将决定点的分布和密度,如选择三角形的最小面积或者最大的匹配点数等作为终止条件。匹配算法如图 1 所示:图 1 三角形约束的影像匹配传播流程特别的,如果在某个同名三角形内分别提取出来的两个特征点集合,第 3 页 共 13 页最终未能正确匹配出任何同名点对,那么该同名三角形内的匹配传播过程将自动终止。这一点对于水面或屋面等纹理缺乏区域的匹配具有重要作用,因为在这些区域纹理信息极度贫乏,很难提取出可重复的具有物理意义的特征点,所以在这些区域匹配过程的自动终止能够有效的避免错误的匹配结果及对后续匹配传播过程的不利影响。匹配传播过程的最后结果就是一个与纹理特征相适应的左右影像上的匹配点构成的两个同名 Delaunay TIN,据此就可以通过空间前方交会计算直接得到相应的三维数字表面模型。2.3三角形约束下影像匹配算法实现数据处理流程根据基于三角形约束的影像匹配方法,设计了具体数据处理流程。1.将一定数量的良好匹配点(选取至少三对匹配精度高的同名点)作为初始点,采用 Delaunay 规则,在立体像对上,分别构建初始同名三角网。2.根据三角形特征信息量大小,对其排序以判断各三角形的匹配优先级。3.运用改进的 Harris 特征提取算子,在重叠区域内提取特征点,记录其提取过程中得到的特征值(兴趣值),并根据构成的三角网对其进行索引。4.选择匹配优先级最高的同名三角形,根据相应约束条件,获得匹配可靠度最大的一对同名点。5.利用“插入算法”,将该对同名点分别动态插入到两同名三角网中,并更新特征点索引及三角形匹配优先级。6.继续选取优先级最高的一对有效同名三角形,进行同样的匹配过程,直至满足匹配传播的终止条件。3 三角网约束下影像匹配算法实现中的关键问题立体影像匹配本质上是对大量的灰度角点进行匹配,其计算量相当大。而快速处理影像资源中提取高精度信息进而实现三维重建是当今的热点问题,随着大存储量硬盘设备的发展,空间效率的要求远不如时间效率的要求迫切,因此,在本算法实现过程中,通过预分配较大空间以换取时间效率。如生成初始三角网时,就根据估计的最终同名点数目,而给定一可调整的值 n,预先为三维数据点及三角形存储结构分配空间,由于 n 个点构成的三角形不超过 2n 个,第 4 页 共 13 页三角形个数预分配为 2n,虽然这浪费了一定的空间,但是在逐点插入新的同名点动态更新三角网的过程中,就不需要另外分配空间,从而节省了时间。3.1 数据结构 设计数据结构是实现算法的基础。三角形存储结构是对基本的面结构的扩展,顶点坐标单独存储,三角形节点及拓扑关系存储在同一结构中。Struct Trianglelist{ long ID;long v1,v2,v3;long v12;long v23;long v31;};根据匹配传播的需要,设计了三角形属性结构。Struct Triproperty{ double attribute;double entropy;int * IPointIndex;int IPointNum;int * rPointIndex;int rPointNum;} ;在数据结构 Triproperty 中,entropy 属性用来记录三角形的特征信息量,表明三角形内的纹理复杂程度,可以通过不同的方式来衡量。如三角形的信息熵、三角形顶点的特征值之和。Attribute属性用来控制匹配传播,当某个三角形的 attribute 属性值为-1 时,影相匹配结束。其他四个属性都是用来建立特征点索引的。3.2特征点索引将匹配点动态插入已存在的三角网过程中,匹配点所在的三角形被细分成新的三角形。首先,在该三角网所在影响区域范围内,提取出全部特征点,记录其特征值。然后,对同名三角形内的特征第 5 页 共 13 页点进行匹配,并对特征点建立三角形索引。具体实现过程为:先建立三角形属性数组,与预设三角网中的三角形数目大小相同,并且与三角网中的三角形一一对应。再建立初始三角网,通过三角形的最小外接矩形及面积判断法,确定每个三角形内的特征点,并按照其特征值从大到小的顺序,采用快速排序法对其序号排序。最后根据左右两幅影像同名三角形内的特征点数目,对特征点索引分配空间,将排过顺序的特征点序号,分别存储在动态数组 IPointIndex和 rPointIndex 中。在随后的三角网更新过程中,首先判断出原三角网中被修改的三角形,只需要对原属于这些三角形的特征点重新索引即可。根据新的特征点数对更新的三角形重新分配空间,寻找特征点及排序的过程和初始化索引相同。3.3三角形优先级根据三角形约束下匹配方法的原理,某三角形内纹理特征最明显(即特征值最大)的点总是最先匹配成功的,而且先进行特征丰富区域的影像匹配,进而逐步扩展到特征缺乏区域,使位于特征丰富区域的三角形能够约束特征缺乏区域的匹配,从而提高特征缺乏区域的匹配可靠性。从优先级最高(纹理特征最丰富)的三角形开始匹配,涉及两方面的问题。其一,计算更新三角网后对被修改或新生成的三角形特征信息量。不同灰度的像素点以不同的概率分布填充不同的空间区域,使得不同的影像表现出不同的形状纹理特征,可以用映像的信息熵来描述。对于一个具有 n 个灰度取值可能 g1,g2,……,g n的数字影像,灰度 g1出现的概率为 p1,则该数字影像的信息熵定义为:H [k] =- Σ pilogpi (i=1,2,3……n) (1)三角形的特征信息量可通过三角形区域的信息熵来描述。要读取三角形内各像素点的灰度值,就必须判断出三角形内的点,这里三角形内的每个点都需要统计,因此采用了三角形矢量栅格化的扫描算法。根据三角形的最小外接矩形,从下到上扫描,对于每条水第 6 页 共 13 页平线,首先得到其与三角形相交的最左、最右两个像素点的水平坐标,而该水平线这两个坐标间的像素点都在三角形内,因此可快速计算三角形的特征信息量。其二,确定特征信息量最大的三角形。为避免冗余计算,根据特征量信息的大小对三角形进行排序判断三角形优先级,首先计算初始三角网中各个三角形的特征信息量,据此通过快速排序法对三角形进行排序,将排好序的三角形序号存储在三角形排序数组中,更新后的三角形插入到相应的位置,这样后续的匹配传播直接按照数组顺序选择三角形进行处理即可。新三角网生成后,被修改的三角型与新生成的三角型的处理方式略微不同,被修改的三角形需要首先得到其原在排序数组中的位置,然后比较其特征信息量的变化情况,以确定相应数据的移动方式,排序数组中的有效三角形序号数目不变。而对于新生成的三角形,根据二分法查找得到其插入位置后,该位置及其后的数据都向后移动一位,排序数组中有效三角形序号数目加一。3.4特征点匹配对左像三角形中的特征点,按照相关约束条件,计算右像同名三角形内特征点的匹配可靠度,得到可靠度最大的点,然后进行双向匹配。如果匹配成功,这一对匹配点成为候选同名点。因此,每次细化只是将匹配程度最高的一对同名点插入三角网中,这一对匹配点一定是左、右影像中特征明显的点。由于在一对同名三角形中,特别是初始三角形中,存在大量特征点,并且这些特征点都已经按照特征值从大到小进行过排序,因此只需要在三角形的前十个特征最明显点中进行匹配,找到匹配程度最高的一对即可。由于已对特征点建立三角形索引,因此只需要通过给定待匹配的特征点数(m_LInterestPointNum.m_RInterestPointNum),控制在特征点中匹配同名点的次数即可,这样一方面不会降低可靠性,另一方面节省了大量的特征点匹配时间,提高了算法效率。4三角形约束下影相匹配算法的效率与实用性试验分析第 7 页 共 13 页4.1 三角形约束下影相匹配算法的效率与实用性试验分析为验证三角形约束下影相匹配算法的效率与实用性,选取了几幅比例尺为 1:10000,重叠度为 65%的实际立体影像对分别进行试验。试验运行环境为 CPU 1.7GHz,内存 512M,操作系统为 Windows 2000 Professional。选取 10 对左右均匀分布的匹配良好点建立初始三角网。试验影像如图一所示,其中图 2(a)为城市建筑密集区,图 2(b)为郊区,图 2(c)为高原地区。这些实际立体影像图 2 试验影像大小相当,但具有不同的纹理特征,并提取出不同的特征点数。试验影像参数如表 1 所示,其中 I 表示影像,1 对应图 2(a),2 对应图 2(b),3 对应图 2(c);D 表示影像大小;F 表示焦距;S 表示扫描分辨率;IN 表示特征点数。根据影像特征,在保证匹配可靠度的情况下选取了不同匹配可靠度阈值,图 2(c)两幅影像变形及灰度差异较大,阈值过高将排除大量正确的匹配点,因此图 2(a)、图 2(b)可靠度阈值为 0.8,图 2(c)可靠度阈值为 0.6。表 1 试验影像参数I D/pixel F/m S/μm/pixel IN1 1982×3043 213.734 25 953102 2212×3164 153.645 25 824483 2228×2898 153.710 50 120966由于三角形约束下影像匹配算法约束条件比一般匹配方法多,匹配得到的同名点在两幅影响上都必须是特征点,因此得到的同名点只是大量特征点中的一小部分,但其匹配的结果可靠性高。因此,其
    展开阅读全文
    1
      金牌文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    0条评论

    还可以输入200字符

    暂无评论,赶快抢占沙发吧。

    关于本文
    本文标题:三角形约束下影像匹配算法实现.rar
    链接地址:http://www.gold-doc.com/p-185917.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们
    copyright@ 2014-2018 金牌文库网站版权所有
    经营许可证编号:浙ICP备15046084号-3
    收起
    展开