当前位置： >>
基于双目视觉三维重建方法研究
分类号：TP391单位代码：10110 学 号：s中 北 大 学硕 士 学 位 论 文基 于 双 目 视 觉 三 维 重 建 方 法 研 究基于双目视觉三维重建方法研究中 北 大 学硕士研究生 指导教师马 韩燮莉 教授马 莉学科专业计算机软件与理论2012年 6 月 3 日图书分类号 UDCTP391密级非密硕士学位论文基于双目视觉三维重建方法研究马莉指导教师（姓名、职称） 申请学位级别 专业名称 论文提交日期 论文答辩日期 学位授予日期 论文评阅人 答辩委员会主席 田卫萍
年 年 年 6 6 月 月 月韩燮教授工学硕士 计算机软件与理论 5 3 日 日 日张国荣、潘广贞2012 年 6 月 5 日中北大学学位论文原 创 性 声 明本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。论文作者签名：日期：关于学位论文使用权的说明本人完全了解中北大学有关保管、使用学位论文的规定，其中包括： ①学校有权保管、并向有关部门送交学位论文的原件与复印件；②学校可 以采用影印、缩印或其它复制手段复制并保存学位论文；③学校可允许学 位论文被查阅或借阅；④学校可以学术交流为目的，复制赠送和交换学位 论文；⑤学校可以公布学位论文的全部或部分内容（保密学位论文在解密 后遵守此规定） 。签名：日期： 日期：导师签名：中北大学学位论文基于双目视觉三维重建方法研究 摘要双目视觉技术是计算机视觉领域的热点研究内容，它利用计算机的软、硬件对动物 的双眼视觉进行模拟仿真。 双目视觉根据三角几何原理获取物体的深度信息并进行三维 重建，实现了非接触式测量。因而，它可应用于逆向工程、影视动画，医学，虚拟现实 及机器人视觉等诸多领域中。双目视觉不但在理论研究方面有着很大的价值，而且在实 际应用方面也有着不可小觑的作用。 本文以如何建立一个高效、快速、精确并且实用性强的三维重建系统为原则。分析 国内外的已有成果，参照 Marr 视觉理论步骤，主要对双目视觉系统中的图像获取技术、 相机标定技术、特征点提取方法、立体匹配以及三维重建等关键技术进行了深入细致的 研究。主要工作如下： （1）首先搭建了一个包含双目相机、光学镜头以及计算机的简单硬件平台； （2）研究了标定双目相机的理论基础和原理，采用比较经典的棋盘标定法获得了相 机的内外参数； （3）根据特征点的立体匹配方法，应用 SIFT 匹配算法和改进的基于 SURF 的立体 匹配算法进行了立体匹配； （4）利用实验室的 Bumblebe 双目视觉相机，获取两幅图像并求出二维图像的视差 图，通过计算得到物体的深度信息，获得物体真实的空间三维坐标，为物体的三维重建 提供了数据支持。关键词：三维重建，特征点检测，立体匹配，SIFT 算法，SURF 算法中北大学学位论文Research of the method of 3D Reconstruction Based on Binocular Stereo Vision AbstractIn the field of computer vision research, binocular vision technology is a hotspot reseaching content that make use of computer software and hardware to simulate the binocular vision of animals. According to the triangular geometric principles binocular vision obtains the object depth information, then reconstructs three-dimensional model of object. It can be applied in many areas such as reverse engineering, television animation, medicine, virtualreality, robot vision and so on. Binocular vision technology has a great value in the theoey research and practical applications.The main work is as follows: (1) First build a hardware platform, including of binocular camera, optical len and computer. (2) Based on the principles of the calibration binocular camera employ chessboard calibration method to obtain the internal and external parameters of Camera. (3) According to stereo matching method of feature points, make use of SIFT matching algorithm and SURF matching algorithm to match the corresponding pionts between two images. (4) Making use of the Bumblebe binocular camera, obtains two-dimensional images and calculates the disparity map of the two images, then acquires the depth information of the object.Key words: three-dimensional reconstruction, feature point detection, Stereo matching,SIFT algorithm, SURF algorithm中北大学学位论文目 1 绪论录1.1 三维重建技术的课题背景及研究意义 ................................. 1 1.1.1 课题背景 ................................................... 1 1.1.2 研究意义 ................................................... 1 1.2 计算机视觉 ....................................................... 2 1.2.1 计算机视觉的概念 ............................................ 2 1.2.2 计算机视觉的三个阶段 ....................................... 3 1.3 计算机视觉国内外研究现状以及技术难点 ............................. 4 1.3.1 计算机视觉国外研究现状 ...................................... 4 1.3.2 计算机视觉国内研究现状 ...................................... 5 1.4 课题的提出和结构安排 ............................................. 6 1.4.1 课题的提出及主要研究内容 .................................... 6 1.4.2 结构安排 ................................................... 72 基于双目视觉三维重建系统的构建2.1 系统硬件平台的构建 ............................................... 8 2.1.1CCD 双目相机 ................................................ 8 2.1.2 实验室计算机................................................ 9 2.1.3 实验平台的搭建............................................. 10 2.2 系统软件的设计 ................................................. 10 2.3 本章小结 ....................................................... 123 双目相机标定3.1 引言 ............................................................ 13 3.2 相机标定基本原理的介绍 .......................................... 13 3.2.1 相机标定过程用到的坐标系及它们之间的相互转换关系 ........... 13 3.2.2 摄像机针孔模型以及其光学成像过程 ........................... 16I中北大学学位论文 3.3 摄像机的标定方法 ................................................ 19 3.3.1 传统的相机标定方法 ......................................... 19 3.3.2 自标定法 .................................................. 23 3.3.3 基于主动视觉的摄像机标定法 ................................. 23 3.4 本实验中相机标定过程 ............................................ 24 3.4.1 角点提取算法............................................... 25 3.4.2 棋盘标定法 ................................................ 30 3.4.3 本实验相机标定的步骤和结果 ................................. 34 3.5 本章小结 ........................................................ 384 基于不变性特征算子的立体匹配方法4.1 引言 ............................................................ 39 4.2 几种常用匹配算法的介绍 .......................................... 39 4.2.1 基于图像区域的立体匹配算法 ................................. 39 4.2.2 基于图像相位的立体匹配算法 ................................. 40 4.2.3 基于特征的立体匹配算法 ..................................... 40 4.3 基于尺度不变特征变换（SIFT）的立体匹配算法 ...................... 42 4.3.1 引言 ...................................................... 42 4.3.2 SIFT 算子的特点及建立主要步骤 .............................. 42 4.3.3 SIFT 算法实现的详细步骤 .................................... 43 4.3.4 SIFT 特征提取法的实验 ...................................... 50 4.4 改进 SIFT 算法---基于 SURF 的匹配算法 ............................. 52 4.4.1 积分图像 .................................................. 52 4.4.2 SURF 特征点的检测.......................................... 53 4.4.3 特征点方向的确定 ........................................... 57 4.4.4 形成特征描述子............................................. 58 4.5 特征点匹配 ..................................................... 61 4.6 实验结果以及分析 ................................................ 62II中北大学学位论文 4.7 本章小结 ........................................................ 655 空间点坐标的三维重建5.1 引言 ............................................................ 67 5.2 基于双目视觉三维重建系统的原理 .................................. 67 5.3 利用最小二乘法求空间点的三维坐标（双目相机不平行）............... 68 5.4 平行双目相机空间点坐标的求解---视差法 ........................... 69 5.5 空间点三维坐标的生成以及深度图像的生成实验 ...................... 71 5.6 本章小结 ........................................................ 736 总结与展望6.1 本文总结 ........................................................ 74 6.2 今后的工作及展望 ................................................ 75参考文献 攻读硕士学位期间发表的论文 致 谢III中北大学学位论文1 绪论1.1 三维重建技术的课题背景及研究意义 1.1.1 课题背景 视觉是人类获取外界信息的重要途径，在人类的生产生活中起着不可忽略的作用。 因此，近几十年来以模拟人类双眼为原理的计算机视觉得到了前所未有的快速发展。不 成熟的技术不断得到的改进，新的技术不断涌现，并已经应用到虚拟现实、物体跟踪识 别以及工业生产和医学监测等领域中。 因此， 计算机视觉越来越受到人们的关注和重视， 成为如今最热门的研究领域之一[1]。 双目技术是计算机视觉领域的主要研究内容， 基于双目视觉的三维重建技术利用双 目相机模仿人类的双眼来捕获外界信息，再将捕获的信息输入计算机中[2]。利用计算机 软件实现对人类大脑的模拟和仿真， 就可以使计算机像人类大脑一样对输入的信息进行 筛选和处理。再根据三角几何原理得到目标物体的深度信息，从而进行三维重建，实现 对目标场景和物体的三维恢复。 1.1.2 研究意义 现实世界中，所有物体和环境都是三维的。而普通相机只能把三维的立体信息变成 平面的二维信息展示给人类，把物体重要的深度信息丢掉了。虽然二维信息图具有获取 容易、便于计算等优点，但是它并不能很好反应环境的真实状况，不便于人们进行学习 和研究。因此，越来越多的人加入了对三维重建技术进行研究的行列。基于双目视觉的 三维重建技术实现了非接触式测量[3]。 而且比起传统的三维重建方法， 它具有更加精确、 更加便利、不需要大量硬件支持等优点。 基于双目视觉的重建技术已经被广泛的应用于医学技术研究、精准零件的制造、虚 拟现实技术、目标定位、特征识别以及军事研究等方面。由此可知，双目视觉不但在理 论研究方面有着很大的价值，而且在实际应用方面也有着不可小觑的作用[4]。1中北大学学位论文1.2 计算机视觉 1.2.1 计算机视觉的概念 计算机视觉研究领域中最为热门的一个研究方向就是双目视觉技术。 双目视觉技术 利用两个相机同时从不同的角度和位置对物体进行拍照， 并将所得图像传输给与之相连 的计算机。两个相机分别模拟人类的两只眼睛对外界信息进行捕获，计算机用来模拟人 类大脑对输入的图像进行处理。近年来随着科技水平的不断提高，基于双目视觉的三维 重建的技术也得到了不断的改进和发展， 在相机标定， 平滑去噪， 场景边缘特征的提取， 特征点的立体匹配等方面都取得了很大的进展[5,6,7]。 三维重建技术在国外的研究起步比较早。最早的计算机视觉的工作是从 20 世纪 60 年代开始的，美国 MIT 的 Roberts 首次完成了三维景物的信息提取工作，把对景物的 研究由过去的二维平面研究推广到三维立体研究，计算机视觉随之诞生了。并且在随后 的几十年中有了迅猛的发展，形成了一门独立的学科。其中，最为经典的就是 20 世纪 80 年代的美国麻省理工学院人工智能实验室的 Marr 视觉理论， Marr 成功的将人工智能、 神经生理学、 模式识别、 图像处理等不同的方面综合在一起进行研究， 最终提出了 Marr 视觉理论，并且将提出的理论应用到双目视觉系统中。诚然 Marr 视觉理论并不是最完 善的，大量漏洞和欠缺不断的被后人发现并且完善。但不可否认的是，他的理论是经典 的。现在双目视觉研究大多数都是以他的理论作为指导思想，并在他的基础上不断的改 进。因此，Marr 视觉理论在计算机视觉方面是经典的，它已经成为计算机视觉研究的 指导思想， 对计算机视觉的发展起着引导作用[8]。Marr 认为对计算机视觉的研究主要可 以概括为三个大的层次和方面： 1.计算理论（computation theory） ：此层次的主要目的就是研究系统各个部分的主 要职能，以及各个部分的输入、输出信息之间有什么制约及联系。Marr 规定双目视觉 系统的输入信息为两幅二维图像，最后的输出结果为目标物的三维重建结果。 2.表达与算法（representation and algorithm） ：这个层次是详细的介绍系统每一部分 的输入输出过程，以及过程中限制条件和涉及到的算法。详细介绍这些算法的实现，包 括描述输入输出信息的算法以及对信息进行处理的算法。2中北大学学位论文 3.实现（implementation） ：一个系统的实现一般都包括两个方面，从硬件和软件两 个方面分别进行描述。 Marr 视觉理论的这三个层次之间是相互联系密不可分的，其中最重要的就是计算 理论这个层次。因为这个层次是系统最主要的理论指导，是构成整个计算机视觉系统的 基础。只有有了正确的理论指导，才可能开发出一个健壮准确的系统[9]。 1.2.2 计算机视觉的三个阶段 Marr 根据计算机视觉理论，将整个立体视觉系统的实现自开始（输入原始二维图 像对）到结束（输出目标物体的真实三维信息）分成了三个阶段[10,11]。 第一阶段也叫做初级视觉阶段就是将二维图像中的角点、边缘、边界等重要轮廓信 息提取出来，这些被提取出的重要信息集合就被称为要素图（或者基元图） ； 第二阶段也叫做中级视觉。建立一个以实验者为中心的坐标系，利用输入的二维图 像和上一步中得到的要素图，提取可见场景的深度信息。但是对于没有被拍摄到的场景 就不能恢复其深度信息。这只是部分恢复，而不能恢复整个场景的实貌，所以这个阶段 得到的结果被称为 2.5 维图；2.5 维图是不全面的，要想得到更加精确更加完整的重建 结果，就必须进一步进行研究和改进，把这个过程归结为立体视觉系统的第三个阶段。 第三阶段就是要通过输入的两幅二维图像，要素图和上一步所得到的 2.5 维图来进行 更深层次的恢复，但是仍然不能得到整个场景的三维形状，得到的只是这个场景独立空 间点的 3D 表达。获 取 图 像 要素图早期视 觉 处理中期视 觉 处理后期视 觉 处理三 维 模 型2.5 维简图 图 1.1 计算机视觉的三个阶段Marr 提出的视觉理论是后来全世界计算机视觉理论研究的根基和指导。但是这个 理论也存在着不少的漏洞，并不是十分的健壮。在后续的研究过程中陆续显现出了一些3中北大学学位论文 不足和缺陷。这些不足和缺陷主要可以归结为以下两个方面[12,13,14]： （1）系统的运行是按照从第一阶段到第三阶段的顺序进行的，没有信息的反馈， 所以导致系统的鲁棒性比较低； （2）由于立体视觉系统其实就是成像系统的逆过程。然而在成像过程中不可避免 的加入了一些噪音和畸变。使得整个立体视觉系统的第一阶段的输入就是不准确的，继 而影响到了整个三维重建的过程。 1.3 计算机视觉国内外研究现状以及技术难点 1.3.1 计算机视觉国外研究现状 计算机视觉现在在全球越来越受到人们的关注。 目前在计算机视觉领域国际上有著 名的三大会议，它们被统称为 ICE 。这三个国际会议分别是：国际计算机视觉会议 （ICCV） ，英文全称为 International Comference on Computer Vision，这个会议是重点中 的重点，被全世界认为是计算机视觉领域最高级最有权威的会议，每两年召开一次；国 际计算机视觉与模式识别会议（ CVPR ） ，英文全称为 International Conference on Computer Vision and Pattern Recognition，每年都会在美国召开这个会议；欧洲计算机视 觉会议（ECCV） ，英文全称为 Europeon Conference on Computer Vision，这个会议也是 在欧洲举办的；除此之外还有一些比较重要会议。包括：亚洲计算机视觉会议（ACCV） 和国际模式识别会议（ICPR）等。而且同时也有大量的服务于计算机视觉研究方向的 杂志及刊物[15,16,17]。 计算机视觉在国外已经发展的相当迅速，并且已经获得了比较成熟健壮的结果。美 国华盛顿大学联合微软研制了一种名叫“探测者”的外星探测系统，这个探测系统其实 就是一个基于双目视觉的三维重建系统。原理就是用一个相机在“探测者”上从不同位 置的各个角度对同一个目标物体进行拍摄。根据所得到的二维图像对获取视差图，继而 获得目标物体的深度信息，最终得到真实目标物体的三维坐标值。便于人们对目标物体 进行更好的研究和开发[18,19]。 一个稳健的智能交通传感系统现在在美国得到了广泛的应 用，这个系统是美国麻省理工大学的 Fang 开发的，这个系统的原理就是利用双目视觉 系统获取运动目标物体的深度信息，同时使用图像分割算法，就可以实现精确的把正在4中北大学学位论文 高速运动的物体提取和分割出来[20]。日本大阪大学的 Minoru 研究并且开发出一套鲁棒 性更强的可以主动适应的双目视觉系统， 这个系统的基本原理仍然是基于双目视觉的三 维重建原理。选取出所得二维图像对中相对静止的三个目标信息，这样就可以计算出相 应的雅可比矩阵中的所有参数， 继而就可以利用这个已知的雅可比矩阵来估算目标物体 的下一步的运动信息，实现了可以智能的对运动着的物体进行实时跟踪[21,22]。 1.3.2 计算机视觉国内研究现状 国内计算机视觉的研究虽然开始的比国外晚。但是随着科技的不断进步，国内计算 机视觉的研究也迈上了一个新的台阶。清华大学、北京航空航天大学、国防科技大学、 西安电子科技大学以及中科院研究所等研究机构都加入到了计算机视觉的研究中， 并显 示出了巨大的发展潜力[23,24]。 哈尔滨工业大学开发了全自主足球机器人导航系统。 在机器人的顶部安装一个固定 的不可旋转及移动的摄像机， 在机器人中下部安装一个可以进行水平扫描和旋转的摄像 机，实现了同时从不同方位获取物体的全景信息。改进了传统算法只可对部分场景进行 三维恢复的缺陷。根据双目视觉的原理以及各个系统的协调作用，实现机器人在视觉范 围内进行精确导航和机器人对物体的准确抓取[25]。 浙江大学的左爱秋从获取的两幅图像对中抽取出重要特征点， 在三角几何原理的指 导下求取这些点的空间坐标值， 从而实现了对可以多个方向自由运动的机械装置进行动 态的和精确的检测跟踪[26]。这个系统的精确性高，而且对信息的获取和处理都非常快， 非常适用于对系统实时性要求较高产业[27]。 东南大学的管业鹏开发出一套可以对不规则的目标物体进行三维重建的系统， 这套 系统可以利用一种叫做灰度相关多峰值视差绝对值极小化立体匹配的新方法对不规则 的物体进行非接触式测量， 这个系统在现实的生产生活中有着更加广泛的应用[28]。 天津 大学的研究出一套可以准确测试汽车生产工业中实时的对车身长度进行监测的系统， 这 个技术已经同国外先进的技术进行接轨。此系统由多个摄像机以及一些处理设备构成。 每一个摄像机都选取车身长度上的一个关键点进行三维信息恢复， 最后将所有摄像头恢 复出来的信息进行综合比对，并且转换到世界坐标系当中，得到精确的测量结果[29]。 正如前文所述， 计算机视觉领域的研究虽然近几十年在全球范围内越来越引起学者5中北大学学位论文 的关注和重视，也取得了比较大的进展。但是计算机视觉的研究仍然任务艰巨，还有比 较多的漏洞和难点没有解决，这将是一个长时间的探索的过程，不可能很快的解决[30]。 就目前来说，计算机视觉领域主要解决的难点可以归结为以下几个方面[31,32,33]： （1）两个摄像头由于旋转平移等不稳定因素造成摄像头获取的图像会出现不同程 度的畸变、平移、旋转以及遮挡； （2）由于获取二维图像时，摄像头会受到光照和空气质量等外界因素的干扰，导 致实验结果不准确； （3）在摄像头的成像过程中会有各种各样的噪声影响，降低获取的图像的质量。 所以从目前的状况看，得到一个精准的、鲁棒性高的、可以在生产生活中发挥重大 作用的双目视觉系统，可以对以下几个方面进行重点改进和研究[34,35]： （1）大量学习已有的成果，并且探索一套更加精准完备的理论系统； （2）将并行化思想应用到算法中，增强算法的鲁棒性和实用性； （3）研究一种新型的智能感知系统，可以对整个场景进行全方位的跟踪检测。并 且可以判断目标物体的下一步运动趋势，提高算法的可靠性和严密性。 1.4 课题的提出和结构安排 1.4.1 课题的提出及主要研究内容 当今世界正处于一个科技飞速发展的黄金时期， 信息技术的快速变革给我们传统的 生活和生产带来很大的冲击的同时也产生了巨大的推动力。 主要表现为科技竞争日益激 烈， “时间就是金钱”这个说法在现代社会中被阐释的淋漓尽致。某个企业或者商家能 否在市场激烈的竞争中处于不败之地就取决于它对市场的灵敏度和对商机的快速反应 度，因此在当代社会“快速成形”这个名词就应用而生了[36,37]。而对一种新产品进行快 速模型构建，就需要一个精准、稳健、快速的三维重建系统。 而且，现在芯片的生产技术也在日新月异的进步着，芯片的质量在不断的提高而芯 片的价格在不断的降低。这也为计算机视觉的广泛发展和研究提供了可靠的硬件保障。 因此，本课题的研究目标就是建立一个基于简单硬件设备的三维重建系统，要求系 统准确度高、耗时短、可以适用在生产生活中。6中北大学学位论文 本课题的主要研究内容包括实验平台的构建、双目相机的标定、特征点的提取及匹 配，图像深度信息以及目标物体三维信息的获取。 1.4.2 结构安排 本文共分为六章，具体内容安排如下： 第一章 引言。主要介绍三维重建系统的研究背景及研究意义。简单介绍了计算机 视觉的几个步骤。同时对双目视觉系统的国内外发展现状进行了阐述。最后介绍了本课 题的提出背景和主要研究内容。 第二章 基于双目视觉三维重建系统的构建。主要介绍了系统硬件平台的搭建过程 和计算机软件系统的设计步骤。 第三章 双目相机的标定。主要介绍双目相机标定的基本理论和原理，并且应用了 现在比较经典的棋盘标定法来获得相机的内外参数。 第四章 特征点的立体匹配。本章主要介绍了立体匹配的基本原理和几种比较常用 的匹配方法。着重介绍了基于 SIFT 的立体匹配算法和经过改进的基于 SURF 的立体匹 配算法。 第五章 空间点三维坐标值的恢复。使用实验室的双目视觉相机对几个实验物体进 行二维图像对的拍摄，利用图像对之间的关系得到视差图，再利根据视差图获取目标物 体的深度图，最终求取目标物体的三维坐标值，实现对物体的三维重建。 第六章 总结与展望。7中北大学学位论文2 基于双目视觉三维重建系统的构建基于双目视觉的三维重建技术就是利用双目相机模拟人类的双眼进行图像采集， 并 且将获取的图像传输给计算机。 计算机就像人类的大脑一样对相机传来的图像进行处理 和计算，最终将目标物的三维坐标值输出。因此，双目视觉系统的构建分为硬件平台的 构建和计算机软件系统的设计开发。 2.1 系统硬件平台的构建 搭建一个简易的双目视觉实验平台，需要的硬件设备有双目相机、光学镜头、相机 固定架、计算机以及棋盘模板和目标物。 2.1.1CCD 双目相机 本实验使用了 PointGrey Bumblebee 三目相机作为图像的采集设备，相机外形如下 图所示。图 2.1 PointGrey Bumblebee 三目相机相机的参数规格如下表所示：表 2.1 PointGrey Bumblebee 三目相机相机的参数规格 图像传感器： 基线距离（b） ： 焦距（f） ： 模数转换器： 帧频： 接口： SONY1/3″逐行扫描传感器 12cm 或者 24cm 3.8mm 2bit A/D 15fps 2 个 9 针 IEEE-1394a 接口，用于控制和图像数 据传输8中北大学学位论文 续表 2.1电压： 尺寸： 重量： 工作温度： 8-32 伏 276× 36× 41.8mm 505g 0° C-45° C本实验为了使图像获取更加的精确和方便，将 PointGrey Bumblebee 三目相机固定 于一个相机支架上。相机可以任意方向旋转，不影响相机对场景拍摄的灵活性。下图为 本实验使用图像采集设备的实物图。图 2.2 实验室的三目相机以及支架实物图2.1.2 实验室计算机 双目相机采集的图像都要传输给计算机这个“大脑”，由计算机对图像进行筛选处 理和计算，最终才可以得到目标物体的三维坐标值。 本实验中的所使用计算机如下图所示：图 2.3 实验室计算机实物图9中北大学学位论文 这台计算机的性能指标如下表所示：表 2.2 实验所用计算机性能 系统 显示器屏幕 屏幕比例 CPU 内存 Windows XP Professional 24 寸 宽屏 3.73Hz 2.00GB2.1.3 实验平台的搭建 首先搭建一个小型的摄影棚，将标定物或者目标物放置于摄影棚中进行图像采集， 以获取受噪声影响最小的图像。将双目相机放置于相机支架上使其正对摄影棚。连接计 算机和双目相机，使计算机可以实时地接收双目相机采集到的图像。整个实验系统平台 的搭建如下图所示：图 2.4 实验室系统平台搭建实物图2.2 系统软件的设计 当双目相机将拍摄到的图像传输给计算机后，就要设计一个软件系统可以对输入的 二维图像进行处理和计算，并且根据三角几何原理将目标物的三维坐标值求出，完成对 目标物的三维重建。设计软件的具体步骤如下图所示：10中北大学学位论文实验平台 的搭建棋盘模板目标物确 定棋 盘上 角点 的世界坐 标 （一般都选棋盘的左上角作为 世界坐标系的原点）相机左眼相机右眼相机左眼相机右眼图像采集图像采集棋盘图像采集棋盘图像采集A/D 转换A/D 转换A/D 转换A/D 转换计算机计算机左图特征 点提取右图特征 点提取棋盘左图 Harris 角点提取棋盘右图 Harris 角点提取特征点匹配获取视差图标定摄像机， 获得摄像机的 内外参数获取深度图获得空间点的三维坐标值 2.5 系统软件设计的步骤图示本实验中，软件系统的设计使用了 Matlab 编程语言，在 Malab7.1 软件环境中进行11中北大学学位论文 开发和调试。 2.3 本章小结 本章介绍了双目视觉系统硬件平台的构建过程和计算机软件系统的设计步骤。对实 验中所用双目相机以及计算机等硬件设备进行了简单介绍， 并且搭建了一个简易的硬件 平台。 接着给出了计算机软件系统设计的具体步骤。 整个软件的设计包括三个大的方面： 双目相机标定、图像特征点的提取和匹配、空间点的三维重建。将在后面的三章中分别 进行详细的介绍。12中北大学学位论文3 双目相机标定3.1 引言 双目视觉通过二维图像对目标物空间坐标值进行恢复。 而光学成像则是将空间物变 为二维平面图像进行存储。因此基于双目视觉三维重建过程其实就是光学成像的逆过 程。任意空间点和它投影到二维图像时所对应像点之间都有一个变换关系，这个变换关 系就是利用两幅二维图像对目标物进行三维坐标恢复的“桥梁” 。这个变换关系是由双 目相机之间的位置关系和相机本身内部参数决定的。 将两台相机之间的位置变换叫做双 目相机的外部参数，而相机本身的内部参数就叫做相机的内参。双目相机内参和外参求 解的过程叫做双目相机的标定[38,39]。 3.2 相机标定基本原理的介绍 3.2.1 相机标定过程用到的坐标系及它们之间的相互转换关系 将空间中的目标点与它们在二维图像上的对应像点进行联系， 涉及到了二维图像坐 标系和空间三维坐标系之间的相互转换[40]。 在双目相机标定过程中所涉及到的坐标系主 要有 4 个：图像像素坐标系、图像物理坐标系、摄像机坐标系和世界坐标系。 （1）图像像素坐标系：一幅图像其实是由一个一个像素点构成的。整幅图像是以一 个二维数组的形式存储在计算机中的， 每一个像素点坐标都分别对应图像中一个具体位 置。在二维数组中每个元素的坐标值就表示这个元素在图像中的具体位置，像素点的横 坐标值 u 和纵坐标值 v 分别代表它在图像中所处的行数和列数。像素坐标系的原点 O0 点一般都选在图像的左上角，坐标用（u，v）表示，像素坐标系的基本单位是像素。 （2）图像物理坐标系： 图像坐标系的原点 O1 规定在整幅图像的中心处，横轴（x 轴）平行于图像的水平边，纵轴（y 轴）平行于图像的垂直边。其中每个元素的坐标表 示为（x，y） ，物理坐标系的基本单位是毫米。如图 3.1 所示，图像像素坐标系和图像 物理坐标系的关系：13中北大学学位论文 O0uO1x （u0，v0）vy图 3.1 图像像素坐标系与图像物理坐标系如图所示，假设图像物体坐标系的原点 O1 在像素坐标系中的位置为 O1（u0，v0） ， 且两个相邻像素点之间的物理距离就是物理坐标系横轴（x 轴）和纵轴（y 轴）的单位 长度 dx 和 dy，那么图像中任意一个点在两个坐标系中的坐标之间有如下的转化关系：x ? u ? ?u0 ? dx ? ? ?v ? y ? v 0 dy ? ?（式 3.1）式子（3.1）还可以用矩阵变换的关系进行表示，如下所示即为矩阵表示：?u ? ?v ? ? ? ? ?1 ? ?? 1 ? dx ? ?? 0 ? ? 0 ? ? ?0 1 dy 0u? 0? ? ?x ? ? ? y? v0 ? ? ? ?? ?1 ? ? 1 ? ? ?（式 3.2）（3）摄像机坐标系：摄像机坐标系把原点 Oc 的位置规定为摄像机镜头的光心处， 坐标系的横轴（Xc 轴）和坐标系的纵轴（Yc 轴）分别和图像坐标系的横轴（x 轴）纵轴 （y 轴）分别平行，摄像机坐标系还有一条 Zc 轴，Zc 轴通过摄像机镜头的光心处，方 向垂直图像平面。摄像机坐标系中元素的坐标表示为（Xc，Yc，Zc） 。其中 OcO1 的长度14中北大学学位论文 就是摄像机的焦距 f。如图 3.2 所示为摄像机坐标系： Zc O0 O1 v Oc Yc图 3.2 摄像机坐标系u xy Xc（4）世界坐标系：在进行双目视觉实验时，双目相机可以放在空间中的任何位置。 因此世界坐标系就是在空间中任意选取一点作为世界坐标系的原点 Ow，用这个点作为 原点就可以将摄像机在空间中相对原点的位置和空间中任意一点位置用一个三维坐标 P（Xw，Yw，Zw）进行表示。如图 3.3 所示为世界坐标系：PZc u Ow x YwZwO0P1XwO1 v Oc Yc图 3.3 世界坐标系y Xc点 P 在世界坐标系下的表示（Xw，Yw，Zw）和点 P 在摄像机坐标系下的表示（Xc， Yc，Zc）之间存在着如下的变换关系：15中北大学学位论文? X c? ? X w? ? ? ? ? ? R ?Y c ? ?Y w ? ? T ? ? ? ? ?Z c ? ?Z w ?界坐标系之间的变换关系[41]。 3.2.2 摄像机针孔模型以及其光学成像过程（式 3.3）其中，R 为一个旋转矩阵，T 为一个平移矩阵，这两个矩阵描述了相机坐标系和世用双目相机对目标物体进行二维信息采集时，有一个成像过程，为了使成像过程更 加明了简洁，就用一个简化摄像机几何模型代替复杂的成像模型。目前，常用的成像模 型主要有线性成像模型和非线性成像模型[42]。 在现实生活中，经常用摄像机将三维物体存储为二维信息进行永久性的保存，这个 过程就是将空间三维点投影成平面二维点。为了方便研究，15 世纪 Brunelleschi 提出了 用一个简单的针孔模型代替复杂的摄像机成像模型。 针孔模型就是物理学中的小孔成像 的模型。针孔模型虽然简单的描述了摄像机的成像过程但是准确，所以在相机标定时， 一般都使用简便准确的针孔模型。针孔模型的几何关系如图 3.4 所示：Yc OW y XW P YW P1ZWO f xO1ZcXc图 3.4 相机成像的针孔模型16中北大学学位论文 如图，点 P 是一个空间点，它投影到二维图像平面上对应的二维点为 P1。其中 OWXW YWZW 为以空间任意一点为原点建立的世界坐标系。Oc-XcYcZc 为以相机镜头光心处 为原点的一个三维坐标系。而平面 O1-xy 为摄像机成像的二维平面，OO1 之间的距离就 是摄像机的焦距 f。将空间三维点与图像平面二维点进行变换，需要经过以下的几个步 骤[43]： （1）首先把空间点 P 从世界坐标（XW，YW，ZW）变换到相机坐标（Xc，Yc，Zc） 。 由于相机不但可以平移还可以进行旋转，所以要到用如下所示的矩阵变换关系：? X c? ? ? ?Y c ? ? R ? ???0 ?Z c ? ? ? ? ?1 ?? X w? ? ? t ? ?Y w ? ? 1? ? Z ? w ? ? ? ? ?1 ?（式 3.4）其中，矩阵 R 为一个 3*3 的旋转矩阵，T 为摄像头的平移向量。 （2）将得到的相机坐标系中坐标值（Xc，Yc，Zc）变换到图像物理坐标系中，得 到此点在图像物理坐标系中对应点 P1（x，y）的坐标值。因为从相机坐标系变换到图 像坐标系就是相机的成像过程，用简单的针孔模型代替，所以根据针孔模型的中心投影 原理即可以得到如下的变换关系：?x ? ? f ? ? ? Z c ? y? ? ? 0 ? ?1 ? ? ? ?00 f 0? X c? 0 0? ? ? ? Yc ? 0 0? ? ?? Z c ? ? 1 0? ? ? ?1 ? ?（式 3.5）其中， （Xc，Yc，Zc）为点在相机坐标中的坐标值， （x，y）为对应点在图像物理坐 标系下的坐标值，f 为所用相机的焦距。 （3）最后完成从图像物理坐标（x，y）到图像像素坐标系（u，v）之间的变换，这 是一个比较简单的变换。17中北大学学位论文? ? ?u ? ? ?v ? ? ? ? ? ? ? ? 1 ? ? ? ? ? ?1 dx 0 00 1 dy 0u? ? ? ?x ? ? y? v0 ? ?? ? ?? ?1 ? ? 1 ? ? ?0（式 3.6）其中， （x，y）为对应点在物体图像坐标下的坐标值， （u，v）相应点在像素坐标下 的坐标值，dx，dy 分别表示两个相邻像素点之间的单位距离，图像物体坐标系的原点 O1 在像素坐标系中的坐标值为（u0，v0） 。 将（式 3.4）和（式 3.5）带入（式 3.6）中，得到（式 3.7） ：? 1 ? d u ? ? ? x ? ? ? Z c ?v ? ? ? 0 ? ? ?1 ? ? ? 0 ? ? ?f ? x ?? 0 ? ? 0 ? ss 1uyd0? ? ?? f ?? v0 ? ? 0 ??0 ? 1? ? ?00 f 0? X c? ? X w? 0 0? ? ? ? ? ?Y c ? ? R t ? ?Y w ? ? 0 0? ? ? ? 0 1? ? ? ? ? ?Z w ? Z c ? ? 1 0? ? ? ? ?1 ? ? ?1 ? ?（式 3.7）f0yu v0 01? X w? 0? ? ? R t ? ? ? ? ? Y w 0? ? ? ? ? ? ? 0 1? Z w ? ? 0? ? ? ?1 ? ??f ? dx ? N ?? 0 其中令 ? ? 0 ? ?若将 ?x0 f dy 0u v1000? ? ? 0? ? 0? ? ?（式 3.8）?? f?y dx 与?? f0 ?y 0dy代入式子（式 3.8）中，那么得到：0 0??x ? N ??0 ? ?0u v1810? ? 0? 0? ?（式 3.9）中北大学学位论文 但像素坐标系中的横轴（u 轴）和纵轴（v 轴）并不能严格保证是正交垂直的。所 以为了保证实验的准确性，引入了不垂直矫正因子 s，这样便得到（式 3.10） ：? ?x ? N ??0 ? ?0s ?y 0u v0 010? ? 0? 0? ?（式 3.10）这个矩阵 N 就是摄像机的内部参数，也叫做透视变换参数，简称为摄像机内参。?R T ? 令M ?? ? ，矩阵 M 就是摄像机相对世界坐标系进行旋转和平移的参数，也就 ?0 1?是摄像机的外部参数，简称为摄像机外参； 式子（式 3.7）可以简写为：? X w? ? ? ?u ? ? ??A R T Yw ??M s? v ? ?? ? ? ? ?Z w ? ? ?1 ? ? ? ?1 ? ?? X w? ? ? ?Y w ? ? ? ?Z w ? ? ?1 ? ?（式 3.11）其中，s 为比例矫正因子；A 表示摄像机的内部参数矩阵；R 表示摄像机的外部旋 转矩阵；T 表示两个相机之间的平移向量；矩阵 M 就是摄像机的投影矩阵，是内参矩 阵和外参矩阵的乘积，也是在摄像机标定这一章中所要标定的内容。 3.3 摄像机的标定方法 计算机视觉的研究目的就是利用空间中某点在两幅二维图像中的投影像点恢复这 个点的深度信息，进而得到点的三维坐标。所以相机标定是十分关键的一步，如果相机 标定不准确，就一定会影响到后续的重建过程。因此许多学者都在寻找一种简便、准确 的相机标定方法。相机标定方法比较成熟的有传统相机标定方法，相机的自主标定法， 张氏相机标定法。 3.3.1 传统的相机标定方法 传统的相机标定法比较容易理解，将一个立体模型（一般使用形状比较规则的棋19中北大学学位论文 盘）作为目标物体，在标定物上选择一些边界点和角点。因为标定物是规则的，所以点 和点之间的几何距离是已知的，因此在已经规定好的世界坐标系中，这些点的三维坐标 值是可以通过测量得出的。将这些选取出来的点投影到图像平面上，并且求出它们对应 投影点的二维坐标值， 通过建立点的世界坐标和图像坐标之间的关系就可以反求出投影 矩阵（摄像机内参数和摄像机外参数） 。但有时只从一个角度位置拍摄棋盘不足以求出 相机所有参数，所以要将相机放在不同角度和不同位置对标定物进行拍摄。 但是在某些比较复杂的外界情况下，放置一个规则标定物是很困难的，此时传统的 相机标定法就不能使用了，这就是传统相机标定方法的弊端。但是，传统相机标定的优 点在于标定结果精确，所以当环境允许而且要求实验精度较高时，还是首选传统摄像机 标定算法。传统的摄像机标定方法一般分为三大类：直接线性标定法，非线性优化标定 法和 Tsai 两步标定法。 （1）直接线性变换法 在传统的摄像机线性标定法中， 一般选择一个规则的标定物。 假如说一个正方体 （每 一个面上都分成大小一致的方格） ，这是选取正方体的长宽高三条垂直线段的延长线分 别作为世界坐标系的 Xw，Yw 和 Zw 轴，这样正方体上所有点的世界坐标都是精确可知 的。再使用角点提取方法，获取这些角点的对应像点在二维平面图像上的坐标值，这样 就可以根据图像坐标和世界坐标之间的变换关系求解出图像的投影矩阵， 也就是我们要 求的相机参数。 假设空间中的一点 I，这个点的世界坐标为（Xwi，Ywi，Zwi） ，对应的图像上像点 的坐标为（ui，vi） ，M 为摄像机的投影矩阵。那么根据式子（3.7）可得：?u i ? ? ? ? ? m11 Z ci ?v i ? ? ?m 21 ?1 ? ? ? ? ? m 31m m m m m m12 22 3213 23 33? X wi ? ? ? m14 ? ? ?Y ? m 24 ? ? wi ? ? Z wi ? m34 ? ?? ?1 ? ?（式 3.12）根据上述矩阵变换可以得到方程组：20中北大学学位论文? Z ciu i ? m11 X wi ? m12Y wi ? m13Z wi ? m14 ? ? ? Z civ i ? m 21 X wi ? m 22Y wi ? m 23Z wi ? m 24 ? ? ? Z ci ? m 31 X wi ? m 32Y wi ? m 33Z wi ? m 34（式 3.13）将方程组中的第三个式子分别带入第一个式子和第二个式子当中消去 Zci 后得到 （式 3.14） ：? ? X wi m11 ? Y wi m12 ? Z wi m13 ? m14 ? u i X wi m31 ? u iY wi m32 ? u i Z wi m33 ? u im 34 （式 3.14） ? ? ? ? ? ? ? ? ? ? X wi m 21 Y wi m 22 Z wi m 23 m 24 v i X wi m31 v iY wi m32 v i Z wi m 33 v im 34可知，一个空间点可以得到两个等式。那么如果有 N 个空间点，就可以对应的得 到 2N 个等式。用矩阵形式表示这 2N 个等式的等量关系就得到矩阵关系（式 3.15） ：? X w1 ? ? 0 ? ? ? ? ? X wn ? 0 ?Y Zw1w100 ... ...wnY Zwn00?1 0 ... ... ?1 00w10w10w1X Y Z... ... 0 ... ... 00 ?u 1 X w1 ?u 1Y w1 ?1 ?v1 X w1 ?v1Y w10wnX Y Zwn wn0 ?u 1 X wn ?u 1Y wn ?1 ?v1 X wn ?v1Y wn? ? 1 w1 ? ? ? ? u1Z wn ?? v1Z wn ??uZ vZ1w1? m11 ? ? u 1m 34 ? ? ? ? ? ? m12 ? ? v1m 34 ? ? m13 ? ? ... ? ? ? ? ? ? m14 ? ? ... ? ? ? ? ... ? ? m 21 ? ? ? ? m 22 ? ? ? ... ? （式 3.15） ? ? ? ... ? ? m 23 ? ? ? ? m 24 ? ? ... ? ? ? ? ? ? m 31 ? ? ... ? ? m 32 ? ?u n m 34 ? ? ? ? ? ? ? m 33 ? ? ? ? v n m 34 ? ?若令上述矩阵中的元素 m34 =1，并且移到等式左边得到矩阵的简写：AM ? U（式 3.16）其中 A 和 U 为两个已知矩阵；M 为一个未知向量，其维数为 11；因此，当点数的 2 倍大于未知数个数 11 时 （即 2N&11） ， 再利用最小二乘法就可以得到未知向量 M 的解：M??K K ? K UT?1 T（式 3.17）因此，利用六个空间点世界坐标和图像坐标就求解出了摄像机的内部参数。但在实 际应用中，一般都会选取 10 个以上的点进行计算，这样就可以得到更加精确的值，从 而降低算法的误差和不准确率，提高了算法的鲁棒性。21中北大学学位论文 （2）非线性优化标定法： 直接线性标定法虽然相对运算速度较快而且可以进行摄像机参数的实时确定， 但是 它忽略了摄像机镜头本身的非线性畸变，在某些精确度要求高的实验中就不适用了，因 此可以使用将畸变因素考虑在内的非线性优化标定法。 非线性优化可以考虑到在成像过程中的各种噪声和畸变，使用了大量的未知数，因 此，代价非常高，而且耗时较长，但是可以得到比较准确的结果。 因为非线性优化相对直接线性法来说，引入了畸变因子，因此，非线性优化时空间 点的世界坐标和二维图像上对应点的坐标关系就变为式（式 3.18） ：? p ? p ? p ? p14 ?u ? ? u ? u ? X w 11 Y w 12 Z w 13 ? X w p 31 ? Y w p 32 ? Z w p 33 ? p 34 ? ? ? X w p 21 ? Y w p 22 ? Z w p 23 ? p 24 ?v ? ? v ? v ? ? X w p 31 ? Y w p 32 ? Z w p 33 ? p 34 ?（式 3.18）其中， u, v 是引入畸变因子后的二维图像上对应点的坐标，? u, v ? 是未考虑镜头畸 变因素时二维图像上对应点的坐标， 而 ? u 和 ? v 就是在成像过程中空间点投影到二维图 像上时由于镜头畸变而产生的误差[44]。 上述方程（式 3.18）就可以利用非线性优化方法进行求解，非线性优化方法求解 过程就是通过拟线性化的方法将非线性化方程迭代成为线性化方程。 再用逐次渐近的方 法进行求解，这样就将非线性化问题转换成了线性化问题，使问题得以求解。 但非线性优化方法考虑的成像过程较复杂， 而且用时较长， 不适于进行实时的检测， 代价较大，因此也不是摄像机标定中的首选方法。 （3）Tsai 两步标定法： 因为线性标定法和非线性优化标定算法都有着各自的优缺点， 而且二者之间的优缺 点刚好互补。 若将以上两种方法进行整合， 设计一个可以兼备线性法和非线性法的优点， 而又不具有以上二者缺点的方法，这就是两步标定法[45]。 两步标定法中最为经典的就是 Tsai 在 80 年代的中期提出的基于径向排列约束 （Radial Alignment Constraint，简称为 RAC）两步摄像机标定算法，这种方法可以得到 比较精确的结果。? ?22中北大学学位论文 第一步就是先利用最小二乘法超线性方程求解出摄像机成像过程的外部参数。 因为 畸变是摄像机镜头本身引起的，所以求解外部参数时就可以先不考虑摄像机镜头的畸 变。 第二步分两种情况进行考虑，如果实验精度要求不是很高，可以忽略掉摄像机镜头 的畸变因素，那么只要利用一个超定线性方程就可以得到摄像机的内部参数；如果对所 得结果的精度要求较高， 那么就要考虑摄像机镜头在成像过程中所产生的径向畸变因素 所带来的影响，那么这种情况下就要通过优化搜索方法来寻求最优解[46]。 3.3.2 自标定法 传统的标定算法，不管是直接线性标定法还是非线性优化迭代法抑或是两步标定 法，它们都有同样缺点那就是都需要一个规则的标定物。这样才可以建立起空间点和二 维图像上对应点的二维坐标之间的关系，进而才可以解出摄像机的内外参数。但是如果 在某些环境下不允许放置标定物，传统的标定方法就失去了效力，因此出现了自标定算 法。自标定算法不需要在摄像机前放置规则的标定物，直接就是利用两幅二维图像对应 点之间的约束关系对摄像机的参数进行求解。 摄像机的自标定法主要原理是利用 Krupp 方程为摄像机建立绝对二次曲线曲面方 程或者绝对二次曲面方程进行求解。但是从摄像机自标定的基本原理上讲，自标定算法 与摄像机怎样平移和怎样进行旋转并没有关系。 摄像机的自标定法主要就是利用摄像机 内部本身参数之间的关系建立方程，所以摄像机的自标定法对实验环境的要求简单，并 且运算速度快。但是摄像机自标定法的缺点在于鲁棒性不和所得结果的精确度不高。因 此在一些实时性要求较高而精确度要求不是很高的系统中就可以使用摄像机的自标定 方法[47]。 3.3.3 基于主动视觉的摄像机标定法 由于摄像机的传统标定方法和摄像机的自标定法都存在着一些不足之处， 所以提出 了基于主动视觉的自标定方法。主动视觉标定法与摄像机的自主标定算法是一样的，它 们都不需要放置一个规则标定物并且知道标定物的精确空间三维信息， 都是利用二维图 像点的对应建立关系。 区别就在于基于主动视觉的摄像机标定法需要知道摄像机的运动23中北大学学位论文 规律，而且必须是某种规则的运动（比如说旋转或者平移） ，根据摄像机有规律的运动 方式求得摄像机的参数。 基于主动视觉的摄像机标定算法得到的结果精确度高而且算法 的鲁棒性强。 该算法虽然具有运算简单、耗时短、精确度高、鲁棒性强等优点，但该算法所需要 的硬件设备价格昂贵，所以也不是一般的实验或者是工业制造中可以使用的[48]。 3.4 本实验中相机标定过程 本实验综合考虑各种因素， 选择了当下比较流行的张氏棋盘标定法作为相机定标的 方法。棋盘标定法的具体步骤如下图所示：棋盘模板确定棋盘上角点的世界坐标（一般都选作图像 的左上角作为世界坐标系的原点）相机左眼相机右眼棋盘图像采集棋盘图像采集A/D 转换A/D 转换计算机 棋盘左图角点提取 棋盘右图角点提取标定摄像机，获得摄像 机的内外参数 图 3.5 摄像机标定步骤实验中图像像点坐标值的获取采用了角点提取法， 下一小节将对角点提取的算法进 行介绍。24中北大学学位论文3.4.1 角点提取算法 在本实验所使用相机标定算法中，用的标定物是一个平面棋盘模板，因此令棋盘上 各点的 Zw=0。而棋盘点的 Xw，Yw 值则可以通过测量获得。棋盘各点对应像点坐标值 用角点提取法获取。目前比较流行的角点提取法主要有 SUSAN 角点提取法和 Harris 角 点提取法。 （1）SUSAN 角点检测算法 英国牛津大学的 Smith 和 Brady 在 1997 年提出了一种现在比较流行的利用图像灰 度信息进行角点提取的算法，名为 SUSAN （ Smallest Univalue Segment Assimilating Nucleus）角点检测算法。这个算法运算速度快，实现简单，比较容易掌握和使用，而 且得到的结果精度高，能满足大多数实验的要求[49]。 SUSAN 角点检测算法依据的原理是：图像在角点处一般会产生比较强的灰度值变 化。设计一个形状接近于圆的模板，将位于该圆形模板中心位置的点叫做核心点，这个 核心点就是在角点检测的过程中要进行比对的点。 把核心点周围所有其它像素点构成的 集合叫做该核心点的邻域。 在这些像素点中挑选出那些灰度值与核心点灰度值近似的像 素点，并将这些符合条件像素点构成的集合叫做核值相似区 USAN（Univalue Segment Assimilating Nucleus）[50]。USAN 值的大小决定着核心点是否为角点，因此 USAN 可以 分为以下三种情况进行讨论。图 3.6 USAN 的三种常见情况由上图可以得到 USAN 一般出现的三大类情况。USAN 区域的大小与核心点是否 为角点的关系如下表所示。25中北大学学位论文表 3.1 USAN 区域值与核心点的关系 USAN 所占区域的大小 USAN 所占区域的大小〉圆形模板区域的一半 USAN 所占区域的大小≈圆形模板区域的一半 USAN 所占区域的大小&圆形模板区域的四分之一 核心点的位置 核心点处在图像比较平滑的位置 核心点处于图像直线的边界处 核心点处可能为角点对表进行分析,可以得到信息：USAN 所占区域值越小，对应核心点成为图像角点 的几率就越大。因此，SUSAN 角点检测算法的关键就是寻找 USAN 值最小的核心点作 为图像的角点。 USAN 角点提取算法一般分为以下几步进行[51]： 第一步，首先要选取一个大小适中，形状接近圆形的图形作为角点检测的模板。模 板大小的选取不会影响到实验的精度值。 因为大模板虽然可以更精确的判定核心点是否 为真正的角点，但大模板所包含的范围也大，角点数目也会相应的多，因而增加了计算 的复杂度，导致算法精度的降低。图 3.7 USAN 的近似圆形的模板示意图第二， 要用一个具体的计算公式来衡量模板内所包含像素点的灰度值与核心点灰度 值之间的相似度。计算相似度的函数如下所示：? ? I ? I 0 ?6 ? C ? r , r0 ? ? exp ? ? ? ? ? t ? ? ? ? ? ?（式 3.19）其中，r 表示核心像素点的位置，r0 表示邻域内其它像素点的位置，I 表示核心像素 点的灰度值，I0 表示其它像素点的灰度值，t 表示灰度差阈值。 第三，对邻域内所有像素点的相似度进行叠加，累加结果值记为 n。26中北大学学位论文n ? ? C? , r 0r ?r（式 3.20）第四，将所有像素点相似度的累加结果与一个预先设定好的阈值参数 g 作比较，来 决定该核心点是否为角点。这个计算过程叫做计算像素点的角点响应函数值。? ? g ? n r0 CRF r0 ? ? ? ?0? ?? ?若n r0 其他? ?g（式 3.21）其中，g 为一个事先设定好的阈值，为了保证算法的准确性和时效性，一般将 g 的 值选取为整个圆形模板面积的二分之一。 对每一个邻域内的像素点都计算它的角点响应函数值，当函数值取得最大（相似度 累加和 n 最小）并且最大值不为零时，该核心点一般就是图像的角点。图 3.8 SUSAN 角点的提取灰度差阈值 t 的选取会直接影响到角点的检测。因为灰度差阈值 t 决定了角点选取 的精确程度和角点的明显程度，限制了角点选取时最小的对比度，也就是对噪声进行忽 略的最大能力。t 值选取的越大，那么就越难从噪声大的不清晰的图像中提取出角点， 因为 t 值越大，对图像角点的要求越高，所提取出的角点个数就会越少；反之，t 值越 小，越能从分辨率不高的图像中获取角点，所提取出的角点的个数也比较多，但是精确 度会降低。 因此在实验过程中要进行综合分析， 对于不同的实验要求， 不同的图像质量， 设定不同的 t 值进行角点的提取。因此，SUSAN 角点提取算法就有了一定的局限性[52]，27中北大学学位论文 由于 t 值选取的不稳定性，造成了 SUSAN 算法提取到的角点结果并不精确。 （2）Harris 角点检测算法 1988 年 C.Harris 和 M.J. Stephens 在对传统的角点提取算法 Moravec 进行改进的基 础上提出了一种基于图像信号变化特征的角点提取算法，叫做 Harris 角点检测算法。 Harris 算法具有较高的稳定性，而且算法简单易于理解和实现，算法也同时具备了耗时 短， 检测到的特征点分布均匀等优点。 因此，Harris 在角点点提取中是比较常用的算法。 Harris 算法首先要设计一个大小合适的正方形模板窗口，将此窗口在局部区域内的 各个方向上进行缓慢的移动，检测窗口内平均能量值的变化。在图像光滑的区域内，检 测窗口内不会出现能量的跳跃变化，但是在图像的边界处，尤其是角点处，检测窗口内 的能量值会出现比较大的波动[53]。 当窗口在图像的各个方向上进行移动时， 窗口平均能量值的变化大致可以分为三大 类，如下表所示。表 3.2 窗口能量值变化和窗口所处位置的关系 窗口平均能量在水平和垂直方向上均没有明显的改变 窗口平均能量只在水平方向或者垂直方向的值有改变 窗口能量在水平方向和垂直方向上均有较大幅度改变 说明窗口处于图像的平滑区 说明窗口处于图像的边界处 说明窗口处于图像的角点处那么，Harris 角点的提取算法具体步骤如下： 第一，设计一个大小合适（一般为 3*3 或者 5*5）的正方形窗口，针对某个像素点， 在各个方向上进行微小移动，来计算窗口平均能量值的变化。窗口能量改变值根据下面 公式进行计算。E ? x,y ? ? ?Wu ,v I x ?u , y ?v ? I x ? yu ,v2? ?I ? ?I ? ?Wu ,v ? x ? y ? O ? x 2 ? y 2 ?? ?y u ,v ? ?x ?2? Ax2 ? 2Cxy ? By? 1 ? 其中， Wu ,v ? exp ? ? ? u 2 ? v 2 ? ? 2 ? 为一个高斯滤波器。 ? 2 ?（式 3.22）而 A，B，C 分别为一阶梯度值的乘积（也就是二阶微分）的近似：28中北大学学位论文? A ? X2 ? W ? 2 ?B ? Y ? W ?C ? X Y ? W ?X，Y 为图像像素点在水平方向和垂直方向的一阶梯度：（式 3.23）?1 ? 0 ? 1 ? ? X ? ?I ?x ? I ? ? T ?1 ? 0 ? 1 ? ?Y ? ?I ?y ? I ?则 Hessian 矩阵 M 可以写为如下的形式：（式 3.24）? A ? x, y ? C ? x , y ? ? M ? x, y ? ? ? ? ? C ? x, y ? B ? x , y ? ?上式可以写为如下形式：（式 3.25）E? x , y ? ?? x?y?x ? M? ? ? y?（式 3.26）计算矩阵 M 的行列式的值 Det(M)和矩阵 M 的迹 Tr(M)：2 ? ? Det ( M ) ? AB ? C ? ? ?Tr ( M ) ? A ? B（式 3.27）最后，计算灰度相关变化系数的值：R ? x, y ? ? Det ? M ? ? k ?TrM ? ? AB ? C 2 ? k ? A ? B ?2 2（式 3.28）其中 k 的取值影响到角点的选取，所以综合考虑各种情况，Harris 一般推荐取 k=0.04。 当 R(x，y)值变化较大时，就说明灰度相关系数有较大的变化，也就是窗口在垂直 和水平方向的能量变化都比较明显，说明这个点就是要选取的角点。 Harris 以其稳定性强、算法简单、便于实现和理解等优点，赢得了人们的信任，被 大量的应用于角点提取系统当中。但是 Harris 也有缺点，那就是 Harris 对于尺度变化比 较敏感，不具有尺度不变性[54]。29中北大学学位论文图 3.9 Harris 角点提取本实验在对摄像机进行标定的过程中，求取棋盘图像角点坐标值时采用了 Harris 角点提取算法。 3.4.2 棋盘标定法 由于传统标定方法都需要一个标定物放置在摄像机前， 并且知道标定物的精确的三 维立体信息才可以进行标定，但是传统的标定方法对实验室环境要求较高，并且算法的 耗时较长。相对于传统的标定方法来说，摄像机的自主标定方法对环境要求较低，而且 不需要规则的标定物，只依靠两幅二维图像对应点之间的关系来求解摄像机的内部参 数，但是这个算法的鲁棒性不高，精确度也不高。基于主动视觉的摄像机标定法虽然没 有了摄像机自主标定算法的缺点，但是对于设备要求高，所以也不是首选。根据实验室 的环境，实验选取了处于传统摄像机标定算法和自主标定算法之间的一个算法---张氏 棋盘标定算法[55]。 张氏棋盘标定算法就是利用多幅不同角度拍摄的二维图像进行摄像机标定的算法， 用多幅图像可以提高算法的精确度和鲁棒性，而且算法简单容易操作，只要从不同角度 拍摄二维图像即可，因此张氏棋盘标定算法得到了大多数人的认可，并且在摄像机的标 定中得到了最广泛的应用。张氏棋盘标定算法一般分为以下几个步骤进行。 第一步，计算出单应矩阵 H： 根据针孔模型， 知道了空间中一点的世界坐标和在二维图像中对应点的二维坐标之30中北大学学位论文 间的变换关系为：? X w? ? ? ?u ? ?Y w ? ? ? s ?v ? ? A ? R t ? ? ?r 1 ? ? A? Z w ? ? ? ? 1 ? ? ? ?1 ? ?r r23? X w? ? ? ?Y w ? t? ?? ? ?Z w ? ? ?1 ? ?（式 3.29）其中，A 矩阵就是摄像机的内部参数矩阵，R 是摄像机的旋转矩阵，T 是表示摄像 机的平移向量。 但是因为实验使用的是一个棋盘标定板，是一个二维的平面，所以实验中，可以将 世界坐标系的原点选定在棋盘左上角的顶点处，又因为棋盘是一个二维的平面，所以世 界坐标系的 Zw 值可以设为 0， 棋盘上两条垂直的边分别作为世界坐标系的 Xw 和 Yw 轴。 这样就可以大大的减少运算量，节约了运算时间。此时就得到了式子（式 3.30） ：? X w? ?u ? ? ? ? ? ? Y w ? s ?v ? ? A ? R t ? ? A? ?r 1 ?0 ? ? ? ? ? ?1 ? ? ?1 ? ?r r23? X w? ? ? ? ? ? A? Y w t? ?r 1 ?? 0 ? ? ? ? ?1 ? ?r2? X w? ? X w? ? ? ? ? t? ? ?Y w ? ? H ?Y w ? （式 3.30） ?1 ? ?1 ? ? ? ? ?其中，H 矩阵就被叫做单应矩阵（Homography） ，这个单应矩阵就是棋盘上任意一 个点的世界坐标和二维图像上对应点的二维坐标之间转换的桥梁， 这个矩阵有时也叫做 投影矩阵。令 M ??X wYw1?T，m ??u v 1?T，则上式就可以写为式： （式 3.31）s m? H M因为世界坐标已经建立，所以棋盘上所有点的世界坐标都是精确已知的，对于相机 拍摄后所得到的棋盘的二维平面图像上点的坐标， 可以通过上一章中讲到的角点提取算 法来得到相应点的二维平面坐标值，这样，只要棋盘上的点选定了，那么矩阵 m 和矩 阵 M 就都是已知的，所以就可以求解单应矩阵 H[56]。矩阵关系（式 3.31）可用方程组 （式 3.32）代替：? s u? h1 1 X? h 1 2Y ? ? ? ? ? s v? h 2 1 X? h 2 2Y ? ?1 ? 2 ? s ? h 3 1X ? h 3 Yh h1 3 2 3（式 3.32）31中北大学学位论文进行变换后得：? ? h1 1X ? h Y 1 2 h ?u ? ?1 ? h 3 1X ? h Y 3 2 ? X ?h Y ? ?v ? h 2 1 2 2 h ? ?1 h 3 1X ? h Y 3 2 ?1 3（式 3.33）2 3将两个等式去分母后就可以得到：u ? X Y 1? ?u Xh 3 1? u Y ? h 3? h 1? h 2 1 2h ? v ? X Y 2? ? h 3? h 2? h 2 1 2h ?v Xh 3 1? v Y令h ? ? ?h11 得到：'1 3 2 3（式 3.34）h h h12 1321h22h23h h3132? ?? X Y 1 0 0 0 ?uX ? 0 0 0 X Y 1 ?vX ??uY ?vY?u ? ' h ?0 ?v ? ?（式 3.35）上式可以简写为 Sh’= 0， 在继续求解使得 STS 矩阵取得最小值的时候所对应的特征 向量，这就是最小二乘法。讲求得的特征向量进行单位化得到的单位向量就是 h’，从而 得到单应矩阵 H。 第二步，摄像机内参数和外参数的求解； 单应矩阵求出以后就要根据单应矩阵来求摄像机的内外参数了。因为在实验中，摄 像机镜头的畸变是不可以忽略的，所以式子（式 3.35）可以改写为如下形式：? ?h1h h? ?r r ? ? ?A?2 3 12t? ?（式 3.36）其中， ? 是一个比例因子，由于 r1 和 r2 是单位正交向量，因此可以得到：T T ? ?r 1 r 1 ? r 2 r 2 ? 1 ? T ? ?r 1 r 2 ? 0（式 3.37）将（式 3.37）代入（式 3.36）得：T ?T ?1 ? ?h1 A A h 2 ? 0 ? T ?T ?1 T ?T ?1 ? ?h1 A A h1 ? h 2 A A h 2（式 3.38）令矩阵 B 为下式子：32中北大学学位论文B?A A??T?1? B11 ? ? ? B 21 ?B ? 31B B B12 22 32B B B13? ? 23 ? ? 33 ?? 1 ? 2 ? ? ? ? ? ?? ? 2 ? ? ? ? ? v 0? ? u 0? ? 2 ? ? ? ???2??? ? v 0? ? u 0? ??2 1 ? 2 2 2 ?? ??2?20 ? v2?? ? 2 ? ?? ? ? ? v 0? ? u 0? ? v 0 ? ? ? 2 ? 2 2 ? ? ? ? ? 2 ?v 0? ? u 0? ? ? v 02 ? 1? ? 2 ?2 ? ? ?2 ? ? v0? ? u 0?（式 3.39）其中，B 表示一个绝对二次曲线方程。 再令向量 hi ? ? ?hi1h hi2i3? ? 为单应矩阵 H 的第 i 列向量代入（式 3.38）可得：ThT iBh i ? V ijbi1 j2 i2 j1 i2 j2 i3 j1 i1 j3 i3 j1 i3（式 3.40）j3 i3其中，V ij ? ?hi1h j1 ?h h ?h h h h h h ?h h h h ?h h h hT ? ? V 12 ? T ?b ? 0 T ? ? ?V 11 V 22 ? ?? j3?T因此可将式子（3.40）写为如下方程的形式： （式 3.41）那么推广到一般的 n 幅图像的情况下可以得到如下关系：Vb ? 0参数。2 ? ? ? c12c13 ? c11c 23 ? c11c 22 ? c 12 ?v 0 ? ? 2 ? ?? ? c 33 ? ?c13 ? v 0 ? c12c13 ? c11c 23 ? ? ? ? f x ? ? c11 ? ? 2 ? f y ? ? c11 c11c 22 ? c12 ? 2 ?s ? ? c12 f u f v ? ? 2 ? ? sv 0 f v ? c13 f ? ? u ?u 0（式 3.42）现在就把问题又转换成为较熟悉的线性方程的求解了， 最后得到摄像机的五个内部??c11（式 3.43）??再根据内部参数和单应矩阵就可以求得摄像机的外部参数。33中北大学学位论文? ? ? ?1h K 1 ?r 1 ?1 ? ?r 2 ? ? K h 2 ? ?r 3 ? r 1 ? r 2 ? ?1 ? ?T ? ? K h 3其中， ? ? 1 第三步，处理径向畸变；（式 3.44）Kh-1i。在上述标定过程中，并没有考虑摄像机镜头的畸变因素，但是对于精度要求较高的 系统，径向畸变是不可以忽略的，因此要将畸变因素考虑进来，采用极大似然估计算法 优化得到的结果，使算法具备更好的鲁棒性[57]。 3.4.3 本实验相机标定的步骤和结果 第一步，实验采用了标准的 7*9 且每个小正方形都是 30mm*30mm 规格方格图纹， 采用专业的数码相片冲印的方式。因为有时打印的标定板，不是很清晰，造成了摄像机 的标定不准确， 再将冲印出的纸片贴到一个坚硬并且平整的塑料标定板上。 如下图所示。图 3.10 棋盘示意图第二步，移动标定板，使双目像机可以从不同的位置同时对标定板进行拍照，多拍 摄几对图像可以减少误差，为了提高实验结果的准确性，本实验一共采集了从不同角度 所拍摄到的 15 对图像对。34中北大学学位论文图 3.11 左相机所拍摄到的图像图 3.12 右相机所拍摄到的图像35中北大学学位论文 第三步，采用 Harris 角点检测法对角点进行检测并且获得角点的二维坐标。图 3.13 对左相机所拍摄到的图像进行 Harris 角点检测图 3.14 对右像机所拍摄到的图像进行 Harris 角点检测第四步，对相机内参数进行标定所得结果如下：左相机内参： 焦距 主点f ? left ? 24.48632 ? 2.02341c ? left ? ?198.148? ? ? 2.92? k ? left ? ? ?0.198 0.06 0.00000? ? ?0.96 0.45 0.00000?畸变36中北大学学位论文右相机内参： 焦距 主点f ? left ? 24.42341 ? 3.88698c ? left ? ?170.130? ? ?1.87? k ? left ? ?0.352 0.99 0.00000? ? ?0.69 0.53 0.00000?畸变第五步，对相机外参数进行标定所得结果为：旋转向量 平移向量R ? ?0.97 ?0.00061? ? ?0.08 0.00009? T ? ?6.31 ?0.01691? ? ?0.32 0.00639?第六步，验证误差。 得到实验结果后，为了对结果进行验证，证明实验结果的精确性和这个算法的可行 性，用一个定量的值 EW 来进行衡量[58]。EW 值的计算方法如下所示：EW?? ?Xi ?1N? X i ? ? ?Y ti ? Y i ? ti22N（式 3.45）其中，EW 表示平均绝对误差， （X i，Y i）表示棋盘角点投影在二维图像时的精确的 真实坐标，而（Xti，Yti）表示通过摄像机标定算法求得到的坐标。比较真实坐标值和 计算出的测量坐标值，看所得误差是否在允许的范围之内。下图就是实验中所有角点的 误差分布：37中北大学学位论文图 3.15 提取角点的误差分布图从上图可以看出，二维像素坐标的横坐标和纵坐标误差都在 0.4 之内，所以证明该 算法是精确的可行的。 3.5 本章小结 在双目视觉系统中，双目相机的标定是对最后重建结果精度影响比较大的一项。所 以本章细致的研究了相机标定原理，相机标定模型，相机标定方法等基本理论和概念。 再结合实验室的具体情况，综合考虑各种因素，选择了比较流行的张氏棋盘标定法作为 本实验相机定标的方法。实验结果证明，张氏棋盘标定法精确度较高，符合实验要求。38中北大学学位论文4 基于不变性特征算子的立体匹配方法4.1 引言 图像配准是双目视觉系统中最为关键的一步。近几十年，研究学者对图像配准算法 的研究从没有停止过，虽然越来越准确的算法一直不断的产生，但是丝毫没有削弱人们 对图像配准算法研究的热度。 图像配准就是使用双目相机从不同位置同时对目标物体进 行拍摄得到两幅二维图像，两幅图像分别叫做基准图和待匹配图。接下来寻找空间点分 别在两幅图像上对应的像点，并将两个对应像点进行匹配，得到空间点在这两幅图像中 对应像点的视差值，利用这个视差值和三角几何原理就可以进一步得到空间点的深度 值，最后得到空间点的三维坐标值，实现了对三维场景的重建[58]。 本章首先对常用的立体匹配算进行了介绍。 着重对 SIFT 匹配算法以及改进的 SURF 立体匹配算法进行介绍， 并且引入了三个不同的实验验证两个算法在不同外界条件下进 行立体匹配的精度和效率。 4.2 几种常用匹配算法的介绍 随着科学技术的飞速发展以及计算机技术的大面积应用， 已经产生了很多比较成熟 的图像配准方法。 但是这些方法在不同的评价评价标准下还是存在着各种各样的不足之 处。因此，图像配准的研究从没有停止过，图像配准的技术也在不断的更新。立体匹配 常用的算法主要分为以下几个大的类别：根据区域进行匹配的算法，根据相位进行匹配 的算法，根据特征点进行匹配的算法[59]。 4.2.1 基于图像区域的立体匹配算法 基于双目视觉的三维重建系统就是用双目相机从不同的位置对同一个目标物体进 行拍摄。因为是对同一个场景进行拍摄，所以所拍摄的图像在大体上都是相似的。如果 可以把图像根据其灰度特征分割成一个一个的小块， 那么两幅图像中对应部分的相似程 度就会更高。因此，基于图像区域的立体匹配算法的实质就是选取一个像素点作为中心39中北大学学位论文 点，并为这个中心点设计一个大小适度的模板，用这个中心点周围邻域内的其它像素点 的灰度值对这个中心点进行表示；同时在另一幅图像中，寻找这个点的对应点，如果在 另外一幅图像中逐个对每一个小的区域进行遍历， 区域的大小与上幅图中所选定的模版 区域大小相同（与上一幅图像进行相同的分割） ，选出一个区域内所有像点灰度值与前 一幅图像模版区域中所有像点灰度值最为相似的区域， 并将这个区域内中心点与上一幅 图像模板区域内中心点作为一对对应的匹配点。基于灰度区域的匹配算法比较简单，易 于理解和实现。但是此算法的鲁棒性不强。由于要对图像进行分割，如果分割的尺度过 大就会造成信息过多，计算量大；如果分割的尺度过小就会造成灰度信息不足，不能进 行判断。 4.2.2 基于图像相位的立体匹配算法 Kuglni 和 Hnies 在“两幅对应图像对应像素点之间的局部相位应该是相等的”这 个假定条件下提出了基于图像相位的立体匹配算法。 就是利用两幅图像对应点和对应区 域的相关系数来对两个像素点进行衡量的一种算法。 这个衡量通过傅里叶变换方法来实 现，因为傅里叶变换函数在其频率域具有平移、缩放和旋转的对称性。因此，如果函数 进行了平移，缩放或者旋转，那么在傅里叶变换函数的频率域中都有相应的体现。 对于平移变换，傅里叶函数在计算两幅图像之间的关系系数（也就是功率谱）时就 可以通过脉冲的形式体现出来。而对于旋转，则可以利用极坐标将旋转转换为平移，再 利用傅里叶变换方法来计算旋转角度。 基于图像相位的立体匹配算法的匹配基元是相位， 而相位本身就表示着信号的结构 信息。因此，采用相位匹配算法，可以抵抗图像的高频噪声。基于相位的匹配算法具有 抗噪能力比较强、精度达到亚像素级别并且适用于并行处理系统等优点。但是，这个算 法最大的缺点在于不可以广泛的适用。因为当“两幅对应图像之间的对应像素点之间的 局部相位应该是相等的”这个假设不成立时，此匹配方法就失去了效力。 4.2.3 基于特征的立体匹配算法 基于特征点的匹配算法是立体匹配算法中研究最多的算法。因为特征点就是一些比40中北大学学位论文 较特殊的像素点，这些像素点虽然不多，但是这些特征点包含了图像中最重要的信息。 由于这些特征点是将图像的灰度信息进行抽象所提取出来的特征表示， 而不是图像的灰 度值，所以特征点的匹配算法一般都具有良好的稳定性，可以将噪声的影响降到最低。 同时特征点的提取也不受光照，天气等外界环境的影响，因此基于特征点的匹配算法是 人们进行特征匹配的首选。 基于特征点的立体匹配方式有很多种， 但是根据匹配基元的不同大体可以分为三大 类， 匹配的基元可以是点、 线、 面， 也可以是具有整体特性的某些具体的区域的中心点， 或者是某个物体的重心处。 选好了特征匹配的基元后， 就要对所选出的特征点进行描述， 生成特征描述符。特征描述符（Featrue Descriptors）就是一个将特征点的信息进行组合 而形成特征向量。 特征向量易于计算而且稳定性较好， 为后面特征点的匹配奠定了基础。 下表为基于特征点匹配的四个步骤[60]。表 4.1 特征点匹配的步骤 第一，图像 预处理 第二，确定 特征点 第三，特征 点的描述 图像预处理就是对摄像机拍摄所获得的图像进行除噪，平滑，尽量纠正成像 过程中所产生的畸变，确保了特征点的精确提取和图像匹配的顺利进行。 选择匹配所需要的特征点，一般选取包含信息较为丰富的点，比如角点，边 界点等等。也可以使用匹配方法自己的兴趣算子。 为特征点建立特征描述符，特征描述符要将重要的特征信息进行整合，摒弃 不重要的特征信息，形成稳定性强的特征描述符，这样就可以将光照，摄像 机畸变等影响降到最低。 第四，特征 点的匹配 第五，消除 错 误 的 匹 配，使算法 更 加 的 稳 健。 对上一步骤中产生的特征向量进行匹配，这时候就需要用一个衡量它们特征 向量相似度的评判标准，用各种距离函数来进行衡量是最常用的方法。 因为不管选取的特征点有多稳定，但是错配的存在是再所难免的。因此，匹 配结束以后还要使用各种几何约束和光学约束去衡量所选出的匹配点是否正 确。如有错配立刻去掉，以提高整个算法的稳健性和鲁棒性。在本实验中， 使用的几何约束方法是比较流行的极限几何约束法， 同时利用 RANSAC 方法 来去掉外点。41中北大学学位论文4.3 基于尺度不变特征变换（SIFT）的立体匹配算法 4.3.1 引言 David. Low 在 1999 年对当时已有的一些稳定的特征匹配方法中的匹配算子进行综 合的基础上提出了现在比较流行的基于尺度不变特征变换（ Scale Invariant Feature Transform）算法，命名为 SIFT 算法，并且 David. Low 又于 2004 年对 SIFT 算子进行了 进一步的改进和完善。SIFT 算子以其独特的稳定性受到了人们的追捧，因为 SIFT 算子 除了对光照，平移，畸变等噪声具有良好的稳定性和抵抗性外，更重要的是 SIFT 算子 是在尺度空间这个概念基础上提出来的，使 SIFT 算子具有良好的缩放不变性和旋转不 变性。 因此当两幅图像之间的差异较大时， 用 SIFT 算法也可以实现立体匹配， 所以 SIFT 算法更加的实用，更适合大范围的应用[61]。 4.3.2 SIFT 算子的特点及建立主要步骤 SIFT 算法的特点主要有以下几点： （1）因为 SIFT 算子是在空间尺度上比较寻求极值而得到的特征点，所以 SIFT 算 法有着别的算法没有的优点，那就是 SIFT 算法除了对光照，平移，以及成像噪声有很 好的识别能力，同时对于放射变换，旋转变换，缩放变换都有很好的稳定性。 （2）SIFT 算子使用特征描述符来表示的，特征描述符不但稳定性好而且包含了大 量的丰富信息，使得在大数量的特征点中寻找匹配点变得更加容易。 （3）SIFT 算子具有多量性的优点，即使在目标物体比较少的情况下也可以提取到 大量的特征点。 （4）SIFT 特征描述向量可以很方便的和别的特征向量进行结合，具有很好的可扩 展性。42中北大学学位论文利用高 斯差分 以及图 像金字 塔来寻 找尺度 空间的 极值。 准确 亚像 级的 度上 特征 的位 确定 来。 在 素 精 将 点 置 出 建立一 个窗口， 在窗口 内利用 图像的 梯度值 来确定 特征点 的方向。 建 立 特 征 点 的 描 述 向量， 也 就 是 描 述子。图 4.1 SIFT 算子的建立过程4.3.3 SIFT 算法实现的详细步骤 第一步，检测尺度空间极值。 在尺度空间中检测极值，首先要利用高斯差分法作用于原图像得到图像金字塔，接 着再求图像金字塔中的极值。 尺度空间就是用来描述图像在不同尺度下的特点。SIFT 特征算子的提取就是在图 像可能出现的所有尺度空间中进行的，使提取出的算子具有尺度不变性。Koenderink 和 Lindeberg 证明了高斯核是唯一的线性核。利用高斯核作用于原始图像生成这幅图像的 尺度空间金字塔， 接着就可以在尺度空间金字塔中提取出稳定的不受尺度变化影响的特 征算子[62]。 对于输入的二维图像 I ? x, y ? ，尺度空间的定义如下：L ? x, y, ? ? ? G ? x, y, ? ? ? I ? x, y ?其中， ? 表示尺度因子， G ? x, y, ? ? 代表高斯函数，G ? x, y , ? ? ? 1 2??2（式 4.1）e? x2 ? y?2?2?2（式 4.2）因此，G ? x, y, ? ? ? I ? x, y ? 表示将输入图像与高斯函数进行卷积，就可以得到这幅二 维图像在不同尺度下的图像，其中（x，y）表示原图像中像素点的位置。尺度因子 ? 控 制图像的模糊清晰程度，通俗的说就是图像放大缩小的程度，? 选取的越大，图像被平? 选取的越小， 滑掉的信息越多， 只剩下图像的大概特征； 图像被平滑掉的信息就越少，43中北大学学位论文 这种情况下就可以对图像的细节特征进行研究。? 增大的方向图 4.2 尺度因子增大时图像的变化为 了 提 取 更 加 稳 定 的 特 征 点 ， 又 引 进 了 高 斯 尺 度 差 分 空 间 DoG （difference-of-Gaussian） ，DoG 是由图像高斯函数的差再与图像进行二次卷积生成的。D ? x, y, ? ? ? ? G ? x, y, k? ? ? G ? x, y, ? ? ? ? I ? x, y ? ? L ? x, y, k? ? ? L ? x, y, ? ?其中，k 为高斯模糊尺度。 发现，高斯差分函数 DoG 与归一化拉普拉斯算子 LoG（Laplacian of Gaussian）是 相似的，那么它们之间的关系可以如（式 4.4）所示： （式 4.3）??2G ?可以简写为：, y ,? k? ? ? G ,x?,y ? ?G G ? x ? ?? k? ? ?（式 4.4）G ? x, y, k? ? ? G ? x, y, ? ? ? ? k ? 1? ? 2?2G一副图像的 DoG 值可以由下图示意得出：（式 4.5）44中北大学学位论文图 4.3 图像 DoG 空间的生成为了构造 DoG 图像金字塔首先要构造出金字塔图像的第一阶，也就是金字塔中第 一组图像。将输入的原始图像和尺度因子 ? 进行卷积得到第一组中的第一幅图像，再用 尺度因子的倍数 k ? 分别对原始图像进行卷积，得到在不同尺度因子下的图像组，也就 是这幅图像在不同尺度空间中的图像组。 继续将得到的图像组的每一幅图像分别与高斯 函数进行二次卷积，这样做的目的是对图像组进行高斯滤波的处理，也就是对图像进行 预处理，使得图像更加清晰提取到的特征点更加地准确快速。这一组由原图像和不同适 度因子进行卷积得到不同尺度的图像后再和高斯函数进行二次卷积滤波后所生成的新 的图像组就是高斯金字塔中的第一阶图像。就是上图中的左边的图像。 得到高斯金字塔第一阶的图像后就要生成金字塔中剩余其它组的图像， 将原始图像 按 2k 倍像素的距离进行采样得到的新的图像分别作为金字塔中其它组中的第一幅图像。 再按照第一步的方法生成各自组内的高斯尺度空间图像组。 将得到的每组高斯尺度空间图像之间进行差分就得到了高斯差分尺度空间图像组 DoG（difference-of-Gaussian） ，就是上图中右侧的图像序列组。尺度空间中，阶数用 o （octave）表示，层数用 s（scale）表示。 SIFT 算法在选取特征点时，是在 DoG 尺度空间中对于任意一个像素点，不但要它 和它所在平面的 8 个像素点进行比较， 而且还要将这个点和上下层尺度空间中的点进行 比较（上层和下层每层各有 9 个点） 。因此这个点要和总共 9+9+8=26 个点都进行比较，45中北大学学位论文 只有此点比这 26 个点都大或者都小时，这个点才能算是尺度空间的极值点，同时记录 下这个候选特征点的位置和所在的尺度，也就是我们所要检测的候选特征点。SIFT 算 子在尺度空间中进行检测，可以保证选取的特征点具有尺度不变性，对于缩放旋转等差 别较大的图像也可以进行准确的配准。这个比较过程如图 4.4 所示。图 4.4 尺度空间中选取极值点时需要进行比较的点第二步，尺度空间特征点的精确定位。 这样选出来的只是差分尺度空间的候选特征点，还不能确定为图像匹配的特征点。 因为 DoG 算法本身对噪声和边缘点比较敏感。因此还要验证此候选特征点是否为边缘 点或者噪声点，如果是那么就去掉；如果不是，那么说明这个候选特征点就是要选取的 特征点，接着就要对该特征点的位置进行精确的定位，达到亚像素级别的精度[63]。 除去对比度比较低的噪声点。Lowe 和 Brown 在 2002 年提出将提取出了将局部极 值点和三维二次函数进行拟合来过滤掉噪声的方法。 令 D(x)表示特征点的空间尺度位置， 且 X ? ? x, y, ? ? ， 那么 D(x)的泰勒展开极数如T（式 4.6）所示：?DT 1 T ?2 D D ? x? ? D ? X? X X ?X 2 ?X 2（式 4.6）46中北大学学位论文?D ? ?D 其中 ? ?X ? ? ?x?D ?y? ?2 D ? ?x 2 ? 2 ? D ? ?2 D ?D ? ，且 ?? ?X 2 ? ?yx ?? ? ? ? ?2 D ? ? ? ?? x?2 D ?xy ?2 D ?y 2 ?2 D ?? y?2 D ? ?? ? ? 2 ? D? ? ?y? ? ?2 D ? ? ?? 2 ? ?下面，利用函数求导的方法来求在同一尺度空间中极值点的位置，令函数 D(x)一 阶导数值为 0 处就是极值点 Xmax 的位置。因此可得 Xmax 的值，如下式所示：X中可得：? ? 2 D ? ?D ? ? ? 2 ? m a x ? ?X ? ?x?1（式 4.7）求出 Xmax 后， 再求这个极值点的差分尺度空间函数值， 将 Xmax 带入式子 （式 4.6）1 ?DT D ? X max ? ? D ? X max 2 ?x值 D(Xmax)来进行判断， 在 Low 的论文中约定当极值点的空间函数值 D ? X max ? 就认为这个极值点是低对比度的点而作为噪声点被去除。（式 4.8）那么要判断这个极值点是否为特征点就可以通过这个极值点的差分尺度空间函数0.03 时，对于边缘点可以通过求这个极值点的主曲率来进行判断。因为如果是边缘点的话， 它垂直方向的曲率会比较小，根据这点就可以将边缘点区分出来。本文利用 Hessian 矩 阵来计算极值点的主曲率。? Dxx H ?? ? Dyx?2 D ?2 D tr ? H ? ? ? ?x 2 ?y 2Dxy ? Dyy ? ?（式 4.9）接着对矩阵 H 求出它的行列式值和它的迹的值： （式 4.10）det ? H ? ??2 D ?2 D ?2 D ?2 D ? ?x 2 ?y 2 ?x?y ?y?x（式 4.11）47中北大学学位论文 令 S ? det ? H ? ? ctr 2 ? H ? ，这样就可以通过 S 的值判断所选出的极值点是不是边缘 点了，c 是一个设定的值，一般令 c = 0.08，将上文求出的矩阵 H 的迹的值和矩阵 H 的 行列式的值代入求出 S 的值，若 S&0，那么就认为这个极值点位于图像的边缘处，不是 特征点，就要舍去。反之，认为这个点不是边缘点，进行保留。 如果选出来的极值点既不是噪声点也不是边缘点，那么认为该点就是特征点，确定 了特征点的位置以后就可以为特征点确定方向。 第三步，特征点方向的确定。 为了保持特征点的旋转不变性， 特征点的方向特征可以利用特征点邻域内所有像素 点的梯度方向特性来计算特征点的方向，这样特征点的方向才更加的稳定，才能具有旋 转不变性。首先利用下面两个公式计算特征点的梯度模值和方向参数：m ? x, y ? ? ? L ? x ? 1, y ? ? L ? x ? 1, y ? ? ? ? L ? x, y ? 1? ? L ? x, y ? 1? ?22（式 4.12） （式 4.13）? ? x, y ? ? tan ?1 ? L ? x, y ? 1? ? L ? x, y ?1? L ? x ? 1, y ? ? L ? x ?1, y ??其中函数 L 代表特征点的尺度空间函数。接着利用特征点邻域内其它像素点的方向特征来反应特征点的方向特征， 其它像素 点的方向特征用梯度方向直方图法来进行统计， 梯度直方图范围为从 0° ---360° ， 以 10° 大小作为单位长度，这样就分成了 36 份，计算特征点邻域内所有点的特征方向，并标 记每个点落入上述直方图中的哪个区间， 但是并不是所有点的方向对特征点方向具有相 同的约束力， 因为其它像素点对特征点方向的贡献度和这个点与特征点之间的距离成正 比关系。最后，将直方图峰值所对角度定为特征点的主方向，再将剩下强度值较大的直 方柱所对的方向定为特征点的副方向。48中北大学学位论文图 4.5 由梯度直方图确定特征点的主方向第四步，特征点描述子的生成 虽然已经确定了特征点的位置和方向，但是为了能更加精确的描述特征点的特征， 使匹配计算更为方便，就要为每一个特征点建立一个特征描述子。特征描述子的建立分 为四步： （1）对图像主轴的方向进行调整，使其与特征点的主方向保持一致，只有这样才 可以保证图像特征点提取的旋转不变性。 （2）将关键点作为中心，创建一个大小为 16*16 的窗口，如下图所示。正方形中 心的点就是特征点，这个窗口可以分成 128 个大小一致的小正方形，其中每一个小的正 方形就表示特征点邻域中的一个像素点， 每个像素点的梯度方向的值和梯度模值都可以 通过上文中提到的公式进行计算， 然后将小方格中的箭头的方向表示这个像素点梯度方 向，长度就表示这个像素点的梯度模值。由于特征点周围邻域内的像素点对于特征点的 贡献是不同的，离特征点距离越近的点贡献越大，也就是它们的高斯加权值不同，如图 4.6 中所示用一个圆形来模拟特征点周围邻域点的高斯加权值和这个邻域点离中心特征 点距离的关系。49中北大学学位论文图 4.6 由邻域点像素梯度信息生成特征向量（3）将上述的 16*16 窗口进行分割，分割成 16 个 4*4 的小窗口，将每个小窗口内 所有像素点的梯度方向和梯度模值分别进行加权叠加运算。 然后将最后得到的结果绘制 到相应的梯度直方图中，这样就生成了一个种子点。 （4）因为分成了 16 个小块，所以就会得到 16 个种子点。而每一个种子点都带着 8 个特征方向信息，将这 16 个种子点进行叠加就得到了一个 16*8=128 维的向量，这个 向量就是描述特征点的特征向量。 这样就得到了 SIFT 算子的特征向量描述符。特征描述符具有旋转不变性，缩放不 变性等优点。但是 SIFT 算法也有一定的缺点，那就是特征描述符的维数过大，造成计 算过于复杂，耗时长。 4.3.4 SIFT 特征提取法的实验 下面的三组实验则说明了 SIFT 特征点提取算法对输入的两幅图像在亮度上有较大 变化，尺度上有较大变化和输入的图像进行了旋转时特征点提取的稳定性和健壮性。实 验结果分别见图 4.7（a） ，4.7（b）和 4.7（c） 。50中北大学学位论文图 4.7（a）SIFT 特征提取算法在光照变化较大时提取的特征点图 4.7（b）SIFT 特征提取算法在尺度缩放时提取的特征点图 4.7（c）SIFT 特征提取算法在图像发生旋转时提取的特征点51中北大学学位论文4.4 改进 SIFT 算法---基于 SURF 的匹配算法 基于 SIFT 的匹配算法虽然具有光照不变形，缩放不变性，旋转不变形等优点，但 是由于 SIFT 算子的特征描述向量是 128 维的，所以造成了特征点进行匹配时计算比较 复杂并且耗时较长，造成了算法的实时性差，显然不能满足现代科技对于“快速成形” 的需要。因此，对 SIFT 算法进行了改进，提出了基于主成分分析的 SIFT 匹配算法 （PCA-SIFT） ， PCA-SIFT 算法对 SIFT 特征描述符进行了降维处理， 减少匹配的计算量， 缩短了匹配所占用的时间， 满足了实时性的需求， 但是匹配的精度却降低了。 Herbert Bay 等人于 2006 年提出了基于快速鲁棒特征（SURF）的图像匹配技术，该算法不但具有光 照不变性，缩放不变性，旋转不变形等优点，而且也满了实时性的需求。被广泛的应用 于智能机器人导航，卫星定位等实时性较高系统当中[65]。 4.4.1 积分图像 对于任何一幅图像都可以对其图像进行积分运算，对图像中任意一个矩形区域都 可以快速求得其面积，也就是可以快速求得矩形区域内所有像素点的灰度值的和。因为 对一幅图像进行积分运算，就是求出这个图像中所有像素点与原点构成的矩形的面积 值。如图所示，对于图像中点 X（x，y）进行积分运算就是求出这个点和原点 O 之间 的矩形面积。计算方法如（式 4.14）所示：I?? x, y ?? ?? I ? x, y ?i ?0 j ?0i? x j ? y（式 4.14）那么如图所示，想要得到矩形 ABCD 的面积值就可以简单的用 A，B，C，D 点的 积分值进行加减即可，大大减少了计算的重复性和复杂性，所以就节约了时间。图 4.8 积分图像构建52