硕士论文基于图像分割的快速立体匹配.doc

硕士学位论文基于图像分割的快速立体匹配算法研究Nanjing University of Aeronautics and AstronauticsThe Graduate SchoolCollege of Automation EngineeringResearch on Fast Stereo Matching Algorithm Based on Image SegmentationA Thesis inInstrument Science and TechnologybyXU QingAdvised byProfessor WANG Jing-dongSubmitted in Partial Fulfillmentof the Requirementsfor the Degree ofMaster of EngineeringFeb, 2006承诺书本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人享有著作权的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本人授权南京航空航天大学可以有权保留送交论文的复印件，允许论文被查阅和借阅,可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文。(保密的学位论文在解密后适用本承诺书)作者签名： 日 期： 摘要本文从景象匹配应用的需求出发，对立体匹配算法进行了全面、系统的研究，并实现了一种基于图像分割的快速立体匹配算法。由于计算机视觉基本原理是立体匹配算法的理论基础，本文对针孔相机模型、对极几何关系、三角测量原理、马尔视觉理论（三大约束准则）等都进行了相关研究。接下来我们对目前现有的立体匹配算法作了归纳总结，研究了一些典型算法的实现方法，并结合实验结果分析了它们的优缺点。为了使立体匹配算法同时满足高精度和高实时性的要求，本文着重研究了一种基于图像分割的快速立体匹配算法。该算法基于Tao算法框架，通过图像分割、初始视差值的获取、初始模板计算、区域及模板优化、模板分配等步骤来实现。其中图像分割和初始视差值的获取都采用了国内外一些相关方面的最新研究成果；区域及模板优化的引入使得算法具有更好的鲁棒性；进行模板分配时由于采用了新的评价函数，进一步提高了算法的实时性。由于图像分割算法的优劣对整个算法有较大的影响，我们对所采用的一种基于图论的高效图像分割算法也作了详细分析。为了使得算法在实验平台上具有了更高的运算效率，本文还介绍了在实际编程中采用了一些运算加速技术，包括计算优化，OpenCV及IPP技术，OpenMP并行运算技术，STLport技术等。关键词：立体匹配，图像分割，模板计算，贪婪算法，动态规划，模拟退火AbstractBased on the requirement of scene matching, the stereo matching algorithm is researched deeply in this paper, and a fast stereo matching algorithm based on image segmentation is realized.Because the basic principles of computer vision are the foundation of the stereo matching algorithms, Pinhole Camera Model, Epipolar Geometry, Triangulation Principle and Marrs vision theory (three main constrains) are researched. Then we make a summary of the existing stereo algorithms and present their general steps. Some representative algorithms are researched in detail. Making reference to the experiment results, we analyze the strong points and weak points of these algorithms. In order to meet both demands for high resolution and real time, we mainly propose a fast stereo matching algorithm based on image segmentation. The algorithm bases on Taos algorithm frame and the whole algorithm includes several steps, such as image segmentation, initial disparity acquirement, initial plane fitting, region and plane refinement, and plane labeling. For image segmentation and disparity acquirement, some recent production of related area has been adopted. The region and plane refinement makes our algorithm more robust. New evaluation function which makes our algorithm more efficient has been used during the step of plane labeling. For the image segmentation algorithm affects the result of the whole algorithm a lot, an efficient graph-based image segmentation algorithm is presented in detail.In order to make our algorithm more efficient on the experiment platform, some techniques are used in practical programming. These techniques include computational optimization, OpenCV, IPP, OpenMP, STLport and so on.Key Words: Stereo Matching, Image Segmentation, Plane fitting, Greedy Algorithm, Dynamic Programming, Simulated Annealing目 录第一章 绪论11.1 研究背景及意义11.2 立体匹配技术研究现状和存在的问题21.3 本文的研究内容与创新点31.3.1 本文的研究内容31.3.2本文的创新点4第二章 立体匹配基本原理62.1 成像原理62.1.1 针孔相机模型62.1.2立体视觉与对极几何82.2 三角测量原理112.3 马尔视觉计算理论122.4 算法评判标准142.4.1 评判标准142.4.2 遮挡区域确定方法16第三章 常见立体匹配算法分析与实现183.1 一般步骤183.1.1匹配代价计算及叠加183.1.2 视差获取及优化203.1.3 视差细化213.2 区域立体匹配算法223.2.1 WTA算法223.2.2 Realtime算法243.3 全局立体匹配算法263.3.1 动态规划算法263.3.2模拟退火31第四章 图像分割算法研究344.1 常见图像分割算法介绍344.1.1 灰度阈值分割法344.1.2 区域生长法354.1.3 纹理结构分析364.2 基于图论的高效图像分割算法374.2.1 算法理论介绍374.2.2 算法的实现及运算量分析394.2.3 实验结果40第五章 基于图像分割的快速立体匹配算法435.1 算法概述435.2 模板计算445.2.1视差初始值获取445.2.2初始模板计算465.2.3区域优化和模板优化485.3 贪婪算法进行模板分配495.4 实验结果50第六章 立体匹配算法实时性技术研究536.1 计算优化536.1.1 叠加匹配代价计算536.1.2 高斯滤波546.2 OpenCV及IPP技术556.3 OpenMP并行运算技术576.4 STLport技术59第七章 总结62参考文献64致谢67在学习期间的研究成果68图清单图2.1 针孔相机成像原理.7图2.2 图像形成中的几何坐标系统.8图 2.3 双目视觉示意图.8图 2.4 通用立体相机布局与对极几何.9图2.5 标准立体相机布局.11图2.6 三角测量原理.12图2.7 两个视网膜上投影像的对应关系的不确定性.13图2.8 Tsukuba图的左视图、右视图、标准视差图14图2.9 Tsukuba图的低纹理区域、不连续区域及遮挡区域. 16图2.10 遮挡现象产生的原因17图3.1 Tusukuba图的DSI.19图3.2 BT法求匹配代价.19图3.3 抛物线拟和法示意图.22图3.4 匹配代价计算方法对WTA算法的影响（Tsukuba图）.23图3.5匹配代价计算方法对WTA算法的影响（Venus图）.23图3.6匹配代价计算方法对WTA算法的影响（Sawtooth图）.23图3.7 多窗口配置匹配代价.24图3.8 交叉检验示意图.25图3.9 相似点滤除示意图.25图3.10 动态规划算法的阶段及状态示意图.28图3.11 动态规划算法的状态转移示意图.29图3.12 动态规划算法运算结果图.30图3.13 顺序约束反例示意图.30图3.14 模拟退火算法运算结果图.33图4.1 图像f(x,y)的直方图.35图4.2 区域生长示意图.35图4.3 区域生长简例.36图4.4 由多种纹理区域组成的图像.37图4.5 三类区域合成图及本算法对该图分割效果.38图4.6 检测图片的分割效果图.41图5.1 基于图像分割的快速立体匹配算法流程图.44图5.2 “前景膨胀效应”示意图.45图5.3 Venus图的参考图和视差初始值效果图46图5.4 计算模板匹配代价时边界点的处理.47图5.5 基于图像分割的快速匹配算法对各组检测图的运算效果图.51图6.1 递推式叠加匹配代价计算.53图6.2 IPP性能提升示意图.56图6.3共享任务结构类型.58表清单表3.1 Realtime算法和WTA算法PBM值比较.26表3.2 动态规划算法和WTA算法PBM值比较.29表3.3 模拟退火算法和动态规划算法PBM值比较.32表3.4 本章算法运算时间比较.33表4.1 检测图片图像分割所需时间.42表5.1 算法参数选取.50表5.2 各种全局算法PBM值比较.50表5.3 各种全局算法运算时间比较.52注释表DSI: disparity space image, 等视差相似度分布图WTA: winner-take-all, 胜者为王算法，一种最简单的区域立体匹配算法BT法: 由Birchfield 和Tomasi提出的一种提高匹配代价精度的方法PBM: Percentage of Bad Matching，误匹配像素百分比，一种立体匹配算法评判标准RMS: Root-Mean-Squared error，均方误差，一种立体匹配算法评判标准SA: Simulated Annealing，模拟退火算法DP: Dynamic Programming，动态规划算法Realtime算法: 由Hirschmuller提出的一种精度较高的区域立体匹配算法OpenCV: Open Computer Vision，英特尔的开源计算机视觉库IPP: Integrated Performance Primitives，英特尔的集成性能元件库OpenMP: Open Multi Processing，一种基于共享内存的并行运算技术STLport: 一种高效率的STL版本（Standard Template Library，标准模板库）SAD：Sum of Absolute Differences, 偏差绝对值之和SSD：Sum of Squared Differences，偏差平方和CEP: Circular Error Probablity, 圆概率误差第一章 绪论1.1 研究背景及意义随着科学技术的发展，图像匹配（Image matching）或者景象匹配（Scene matching）技术已成为近代信息处理领域中一项极为重要的技术。所谓图像匹配指的就是把从同一景物录取下来的两幅图像在空间上进行对准，最后计算出两幅图像坐标系之间的相对关系。图像匹配技术的应用范围是相当广泛的，其中包括导弹的地形和地图匹配制导、武器投射系统的末制导和寻的、目标跟踪、医疗诊断、天气预报、文字识别以及景物分析中的变化检测等。该技术是飞行器地图匹配导航定位的一项关键技术，是当今各国竞相发展的精确制导技术之一，大力发展并装备此技术完全可以满足今后乃至2010年前后战术导弹对图像制导技术的需求。图像匹配技术可以追溯到70年代末，美国海军航空电子实验室为巡航导弹研制成功一种“数字式景象匹配区域相关系统（DSMAC）”用于“战斧”BGM-109C和D常规弹头对陆攻击导弹上。DSMAC由下视安装的带图像增强器的CCD摄像机获取修正点景物的光学图像，然后与存贮在弹上的基准图相关，估计出位置修正值，通过卡尔曼滤波修正器修正并校准导航系统。DSMAC离目标约11.212.8公里处开始工作，在整个末制导阶段对惯性系统进行两次修正。DSMAC目前已完成了第二代，正在进行第三代产品的开发。第二代的改进措施是提高了图像分辨率，使制导精度从15米（CEP）提高到6米（CEP）。近十多年来，某些军事技术发达的国家，已成功地将景象匹配辅助制导技术应用于巡航导弹的中制导和末制导阶段，并取得了显著的成效。但是，我国关于景象匹配技术研究还很不成熟。尤其在实际应用中，弹载摄像机可能从任意角度对匹配对象进行拍摄，此时实现实时图与基准图之间的正确匹配就变得非常困难。借助计算机视觉技术来进行景象匹配是解决该问题的一个新思路。该方法先对被攻击对象进行三维重构，并从各个角度对重构后的物体进行投影，进而得到一系列投影图，然后将实时图与这些投影图进行比对，最终得到匹配度最高的一幅投影图，该投影图所处的角度也就是当前巡航导弹所处的角度。这样就从根本上解决了前面所提到的难题。本文研究的就是其中的一项关键技术，即立体匹配技术。所谓立体匹配技术，是指针对同一景物从不同视点拍摄的图片，找到它们像素点之间的对应关系。立体匹配是目前计算机视觉研究中的一个难点和热点，在许多计算机视觉的应用中它都是很关键的一个准备步骤，如三维重构（3D reconstruction）、基于图像的绘制（Image Based Rendering）等。目前，立体匹配技术在低空突防37、机器人导航、虚拟现实38等方面都有着广泛的应用。本文主要研究两幅图像的情况，即双目视觉问题（binocular vision）。在平行光轴布局的立体视觉系统（在某些文献中，这种布局被称为标准立体相机布局）中，对应像素点横坐标之差称为视差，记为，而此时由视差计算深度的解析公式可下式表示：其中为相机距离，为相机焦距，为该点到相机平面的距离。因此如果已经建立了两幅图像像素点间的对应关系，并且两部相机已经校准过，那么利用标准立体相机布局提取深度信息是非常容易、直观的。有了深度信息，借助立体视觉技术来进行景象匹配的后续步骤就可以继续下去了，包括三维重构35,36、投影8、图像匹配4等。1.2 立体匹配技术研究现状和存在的问题70年代末，MIT的Marr教授首次从信息处理的角度综合了图像处理、心理物理学、神经生物学及临床神经病学的研究成果，提出第一个较为完善的视觉系统框架1。计算视觉的理论框架，大大地促进了计算机视觉的发展，并成为这一领域的主流理论，目前常见算法中都明确或隐含的使用了其中的三条匹配规则，即相容性、唯一性和连续性。根据所选用的匹配基元不同，可把立体匹配技术分为两类32：一类是基于点的匹配算法，另一类是基于特征的匹配算法。基于点的立体匹配算法通过比较两幅图之间像素点的灰度相关性来获得所有点的匹配关系，因此算法处理后可直接获得的高密度的视差图。使用这类方法存在的基本问题是，它们直接依赖于图像的灰度信息，所以相对来说缺乏匹配鲁棒性，特别是对于那些差异非常大的图像对来说尤为如此。基于特征的匹配算法的一般流程是先分别提取两幅图中的特征量，如边缘点、拐角点、线段、轮廓线等，再根据形状、灰度、约束条件进行特征量之间的匹配。由于特征量一般较稀疏，这种方法只能获得低密度的视差图，需要后续插值才能获得高密度的视差图，这是一项相当繁重的任务，而且需要在几何上作出一些假设。总之，任何一种方法都有其各自的优、缺点，适用于不同的情况，因此有些研究人员提出一些在二者之间折中的方法，希望发挥它们各自的优势，弥补各自的不足6，这些方法从少数可靠的匹配特征点开始，随后在每一次循环迭代中，利用已经成功匹配的特征点作为约束逐渐增加其它的匹配点，采用这种方案带来的负面影响是增加了算法的复杂性。本文中主要讨论第一类方法，即直接通过点匹配来获得高密度视差图，这也是目前国内外比较流行的方法。点匹配算法中又可以分为两大类：第一类是基于区域（窗口）的算法，另一类是基于全局的算法。基于区域的算法中先选取以匹配点为中心的窗口，然后在两幅图的相应窗口之间进行灰度相关性计算，方法包括SAD(Sum of Absolute Differences),SSD(Sum of Squared Difference)等，其中灰度相关性最好的两个点被称为对应匹配点。这种算法能够很容易地恢复出高纹理区域的视差，但在低纹理区域会造成大量的误匹配，边界处又存在“前景膨胀效应”（foreground fattening effect）17，从而导致边界模糊。第二类是基于全局的算法，该算法一般用相容性约束和平滑性约束来构成一个评价函数，再通过各种最优算法来求得评价函数的最小值，这些最优化算法包括动态规划（dynamic programming）、模拟退火(simulated annealing)、遗传算法(generic algorithm)等。这些传统的基于全局的算法一般都能取得较高的精度，然而它们存在的最大问题是计算量过大，对于实时性要求比较高的情况下不宜采用。1.3 本文的研究内容与创新点1.3.1 本文的研究内容本文首先论述了计算机视觉的一些基本原理，包括针孔相机模型、对极几何关系、三角测量原理、马尔视觉理论（三大约束准则）等。接着对目前常见的立体匹配算法进行了分析研究，通过对比实验充分了解了这些算法的性能和优缺点，为后面对Tao算法7改进从而提出新的算法提供了依据。由于本文研究的目的是为了实现把立体匹配技术应用到景象匹配中以实现末制导阶段多角度的正确匹配，因此对立体匹配算法的精度和实时性都提出了很高的要求，而目前常见的基于区域的算法或基于全局的算法都很难达到这个要求。2001年，H.Tao提出了一种基于彩色图像分割的立体匹配算法框架，该算法框架基于平滑表面假设，即在单一的色彩区域中视差变化是平滑的，这样就可以通过一个平面模板（以下简称平面模板为模板）公式来描述该区域（ 为模板参数）,由该公式计算出来的视差称之为模板视差。基于这个假设，就可以把传统的基于全局算法中对每个点分配最优视差的问题转化为对每个区域分配最优模板的问题，从而大大提高了算法的实时性。 本文中借鉴了Tao算法框架的基本思想，并主要对模板计算和评价函数的选取进行了改进。在Tao的算法中，模板参数为直接对分割后对所有区域进行计算所得，由于分割后存在一些可靠点较少的区域（不可靠区域），使得这些区域计算出来的模板参数并不准确。改进算法先只对可靠点数较多的区域（可靠区域）计算其模板参数，并采用区域融合的方法进行模板优化，从而增强了模板计算的鲁棒性。另外在全局优化过程中，改进算法采用了新的评价函数，使得模板对各区域的相似度匹配代价只需计算一次，进一步降低了算法的计算量。低纹理和边界区域所含的不可靠点很多，往往是误匹配率比较高的区域。在本算法中，这些不可靠点的视差是通过本区域的模板参数间接计算所得的，而模板参数则是由区域内的可靠点计算出来的，可信度较高。正是这个原因保证了本算法的高精度，实验结果也证实了这一点。由于图像分割技术对整个算法有较大影响，因此本文中也进行了相应的研究，并实现了一种基于图论的高效图像分割算法。为了进一步提高算法的实时性，本文还引入了多种技术对算法实现进行加速，包括计算优化、OpenCV及IPP技术、OpenMP并行技术、STLport技术等，对这些技术的特点和使用方法都结合具体实例进行了相关分析和介绍。1.3.2本文的创新点1、实现了一种基于图像分割的快速立体匹配算法从而满足了高精度和高实时性的要求，该算法包括了图像分割、初始视差值的获取、初始模板计算、区域及模板优化、模板分配等步骤。2、基于图论的思想实现了一种高效图像分割算法，为整个立体匹配算法的高精度提供了保证。3、将多种运算加速技术应用到立体匹配算法的实现中，包括计算优化，OpenCV及IPP技术，OpenMP并行运算技术，STLport技术等，从而进一步提高了算法的实时性。4、引入了国际上流行的立体匹配算法评判标准及标准实验图片，为评判各种立体匹配算法的优劣提供了一个客观的依据。第二章 立体匹配基本原理2.1 成像原理 一个典型的计算机视觉系统的输入是一幅或多幅景象的图像数据，其中包含有感兴趣的物体，因此理解如何从三维景物形成二维图像，即图像的形成(Image Formation)，对分析计算机视觉技术来说是一项非常基本的内容。其中针孔相机模型（Pinhole Camera Model）与对极几何（Epipolar Geometry）构成了理解与应用计算机视觉技术的坚实理论基础，接下来两小节将研究这方面的基本知识，并进行一定的分析讨论。2.1.1 针孔相机模型从几何学角度来讲，如图 2.1 所示，图像的形成基于这样一个非常基本的事实，如果从物体表面各点发射出的光线穿过某一平面后都投射到同一固定点上，那么这些光线与平面相交得到的截面图，称为中心透视投影图（central perspective projection），就是物体的图像，而结集光线的固定点称为投影中心（Center of Projection）8。几何学上，上述中心透视投影模型能够很好地模拟一部理想的针孔相机（ideal pinhole camera），它由一个成像平面，一个焦距平面及其上的针孔和一只密封箱组成9，它们之间的区别仅在于针孔相机形成的图像是倒立的，并且图像与物体分别位于焦距平面的两侧。在数学上，如图 2.2 所示，可以抽象出这样一个模型，在成像平面 I（也称视网膜平面）前面距离 f处，有一个焦距平面 F，它们互相平行，如果在焦距平面 F 上挖一个尺寸上无限小的理想的针孔 C，并假设所有光线只有穿过这个小孔 C 才能到达成像平面 I，那么物体表面的每一点，它对应的成像点，以及针孔 C 就构成一条直线。针孔 C 称为光学中心或简称光心（optical center），距离 f 称为光学系统的焦距（注意此处焦距的概念不同于通常相机中光学镜头的焦距），穿过光心 C 并垂直于成像平面 I 的直线称为光轴（optical axis），它与成像平面 I 相交于一点 c，称为主点（principal point）。通常，我们定义这样一个图像坐标系统（c，x，y）：其原点位于主点 c，x 轴平行于相机的水平扫描线，y 轴垂直于x 轴。为了操作处理方便起见，更经常的作法是定义一个像素坐标系（o，u，v）：其原点 o 定在图像的左上角，横轴 u、纵轴 v 分别平行于图像的水平和垂直边框，通常情况下这两条坐标轴并不垂直。另外，为了表达空间一点在三维空间中的位置，定义了一个相机坐标系（C，X，Y，Z）：其原点就是光心 C，Z 轴与光轴一致，指向远离相机一侧为正，其它两轴 X、Y 轴在焦距平面 F 内分别平行于图像坐标系的 x、y 轴。图2.1 针孔相机成像原理 （2.1）上式中的负号由倒立的图像所致。为数学上处理方便，研究人员通常习惯于使用一个虚拟的平面 V 代替成像平面 I，该平面 V 位于焦距平面 F 与物体之间，并且距离也为焦距f。这样一来，公式 2.1 中除了负号被消除外没有其它的变化。 实际使用的相机与上述简单的理想化模型有些偏差，这使问题变得复杂化。对于一架实际的针孔相机，其针孔的尺寸并非是无限小的，从而导致图像中的每个像素点并不是只有一条光线投射，而是由通过针孔的一束锥形光线所形成的，因此各像素点变得模糊了。另外，为了有足够的光线通过针孔以保证图像的亮度，以及减少曝光时间，实际使用的相机通常都安装有光学镜头组，这带来了一些并不希望的影响，诸如几何失真、光学失真、有限景深、图像模糊、以及光谱上的有限带宽等等。但无论如何，上述理想针孔相机模型概括了从三维景象到二维图像的变换，并已经证实它都能作为一种近似计算被许多工程问题所接受。 图2.2 图像形成中的几何坐标系统2.1.2立体视觉与对极几何仔细观察我们周围的自然世界会发现，每一只具有正常视觉系统的动物都长有两只眼睛，这叫做双目视觉（binocular vision），通过这两只眼睛可以同时采集两幅图像，它们互相交迭，但景物在图像中的亮度、对比度以及形状等方面相互间存在着差别（参见图 2.3），这个现象实在太普遍了以致于通常被人们所忽略。而恰恰也正是这一点，说明了双目视觉对生物的重要性。通过双目视觉，不仅可以感知通过单只眼睛就能够感受到的信息，比如物体的阴影、灰度、纹理、颜色、形状等等，而且还可以直接感知相对精确的三维位置和方位信息。图 2.3 双目视觉示意图同样地，在计算机视觉领域诸多视觉信息处理过程中，立体视觉也是非常重要的一项，它着眼于通过处理分析同一景物从不同视点拍摄的两幅或者更多幅图像之间的差别，来恢复景物的三维物理信息10。不同于上面提到的自然界中的双目视觉，立体视觉中的两幅图像不局限于只在同一时刻同一水平线上（这里的水平是指平行于相机的水平扫描线）从不同的两个视点采集，而是可以采用更多的方式拍摄，例如，两幅图像可以使用两部相机从不同视点同时拍摄，也可以使用一部相机从两个视点分别拍摄；拍摄两幅图像的视点和方位可以只有轻微的差别，也可以非常不同；两幅图像可以是同一时刻拍摄的，也可以是间隔任意时间后分别拍摄的，甚至可以是使用不同类型的传感器拍摄的。对于任意一种情况，拍摄两幅图像时的成像条件，如大气的能见度，都是比较重要的因素，尤其是对于拍摄两幅图像之间的时间间隔非常长的情况，可能拍摄条件相差很大而造成两幅图像之间的差别非常巨大，这些都使得后续的信息处理过程尤为困难，甚至是不可能实现。考虑如图 2.4 所示采用两部相机拍摄图像的情形，称为通用立体相机布局（general stereo camera configuration），图中点 C 和 C'分别是左、右侧相机的光学中心，三维景象中的任一点 M 分别投影到左侧相机成像平面（以下简称为左图）中的像素点 m 和右侧相机成像平面（以下简称为右图）中的像素点 m'，这两个像素点就称为一对对应点或匹配点（correspondence），它们在两幅图像内各自的坐标系统中分别有着不同的几何坐标。显而易见，真实世界中同一景物的两幅图像之间这种几何坐标上的差异可以由两部相机之间的相对位置与姿态造成，也可以由一部相机相对于景物的运动引起，还可以由物体自身的运动变化引起，因此在单目成像过程中丢失了的一些信息被隐藏在这种差异之中。这种差异的重要性就体现在，利用它可以由二维投影图像对景象的三维结构信息进行部分重构。 图 2.4 通用立体相机布局与对极几何立体视觉中三维重构的任务就是根据同一景象不同视点的两幅图像中的匹配点信息恢复出景象的三维结构。假定已经确切知道左图中的像素点 m 与右图中的像素点 m'是一对匹配点，单独给定左图中的像素点 m，那么它对应的三维景物点 M 在三维世界中的位置一定被限制在穿过光心 C 和它本身的那条直线 Cm 上，同样的道理，与右图中像素点m'对应的景物点M在三维世界中的位置被限制在穿过光心C'和像素点m'的直线C'm'上，因此，与匹配点 m 和 m'对应的景物点 M 在三维世界中的位置就被唯一地确定在两条直线 Cm 和 C'm'的交点上。点 M、C、C'构成了一个三角形，由这个三角形确定 M 点位置的过程称为三角测量过程（triangulation process）。景物点 M 的三维位置信息包含有两层含义：一方面是点 M 到参考相机（一般为左侧相机）焦距平面的垂直距离，称为深度信息（depth），另一方面是点 M 在成像平面内的二维位置信息（location），点 M 的位置信息正确与否及其精度都受制于它的成像点 m 和 m'匹配关系的正确与否及它们位置的精度。实际上，如果使用如图 2.4 所示呈通用立体布局的两架相机进行拍摄，那么确定点 M 到左侧相机或右侧相机焦距平面的深度信息是非常困难和繁琐的，因为对于这种布局在求解深度信息时，没有简单直接的数学公式可以利用。在下一节，本文将会介绍一种平行轴立体相机布局，利用这种布局可以推导出非常简单实用的深度计算公式。 对极几何（epipolar geometry）31存在于任何由两架相机构成的成像系统当中，两架相机可以任意放置，它描述了两架相机之间的几何关系9。参见图 2.4，直线 CC'称为成像系统的基线（baseline），如果左图中的像素点 m 与右图中的像素点 m'相匹配，并且唯一对应于三维空间中的景物点 M，那么点 m、m'、C、C'一定位于由点 M 和基线 CC'定义的平面内，这个平面称为外极面（epipolar plane），任何一张外极面都将与两张成像平面相交于两条直线 L 和 L'，称为共轭外极线（conjugate epipolar lines），因此，若给定左图中某一外极线 L 上的一点，该点在右图中的匹配点必定被限制在它的共轭外极线 L'上，反之亦然。这是因为任一图像内的任一像素点与相应的光心都唯一确定了一条光线，这条光线在另一相机成像平面内所成的像即是该像素点的外极线。基线 CC'与两张成像平面的交点 e 和 e'称为外极点（epipole），因为所有的外极面都相交于基线 CC'，所以一张成像平面内所有的外极线必定相交于相应的外极点，这种结构是对称的。对极几何的计算意义就在于把寻找匹配点问题从二维搜索空间降低为一维搜索空间。2.2 三角测量原理图2.5表示了一种具有平行光轴布局的立体视觉系统，这种布局被称为标准立体相机布局11。这种布局最大的优点是相匹配的外极线对是在同一条水平线上的。如果参考图中的一点（，）与匹配图中的一点（）相匹配，则应满足以下的对应关系： ， （2.2）式中，用于保证视差始终为非负值。不作特别声明，本文中均选取左视图为参考图，右视图为匹配图，故取1。如果相机不是标准立体相机布局，可以先进行外极线校准，再进行后续处理。这样一来，搜索范围由原来的二维变为一维，将大大提高算法的效率。本文不作特别说明的话均是对校准过的图片进行处理。图2.5 标准立体相机布局图2.6为三角测量原理图，下面根据该图中的几何关系来推导三角测量公式。在图2.6中不难找出如下四个关系式，其中为相机距离，为对应匹配点间的视差，为