绪论
计算机视觉是一门通过研究使用计算机来模拟人的视觉系统的学科。“一图胜千言”，人类对于图像中的信息感知效率远超文字等其他媒介，人类获取的信息总量中更是有高达80%依靠视觉系统[1]。相对于人类高效的图像信息提取能力，计算机在图像信息的理解上仍然效率低下。
计算机视觉作为一门交叉学科，综合了生物学，心理学，数学，计算机科学等学科，从20世纪60年代至今其在科学研究领域中的大量成果已经应用于工程领域，并影响了我们每个人生活的方方面面。
双目立体视觉是计算机视觉领域的重要分支，它通过模拟人的双眼视觉系统来处理现实世界。以机器人，无人汽车导航为例，由于双目立体匹配在非接触测量中的优秀性能，视觉测量在探月工程，火星探测工程中起到了重要作用[2]，如图所示的我国嫦娥探月工程的巡航车就配备了立体视觉导航系统如图1-1，来进行行进间的运动控制和路径规划[3]。
图1-1 嫦娥三号巡航车立体视觉系统[4]
Figure 1-1 Stereo Cameras equipped on the lunar rover
1.1 研究背景与意义
立体匹配是一种从平面图像中恢复深度信息的技术。由于双目立体匹配系统通过模拟人眼视觉感知原理，仅需要两台数字摄像机安装在同一水平线上，经过立体矫正就可以投入使用。具有实现简单，成本低廉，并且可以在非接触条件下测量距离等优点。在机器人制导系统中可以用于导航判断、目标拾取，在工业自动化控制系统中可用于零部件安装、质量检测，环境检测，在安防监控系统中可用于人流检测，危害报警。
近年来，随着社会的科技进步，立体匹配技术的发展日新月异，随着匹配算法精度与速度的提高，其应用场景进一步扩大。在此背景下，研究立体匹配变的意义非凡。
立体匹配作为三维重建、立体导航、非接触测距等技术的关键步骤通过匹配两幅或者多幅图像来获取深度信息。并且广泛应用于，工业生产自动化、流水线控制、无人驾驶汽车（测距，导航）、安防监控、遥感图像分析、机器人智能控制等方面。虽然立体匹配应用广泛但是还有很多尚未解决的难题因此该技术成为了近年来计算机视觉领域广泛关注的难点和热点。
立体匹配作为一种工程化问题，在实施过程中有多种因素影响其精度与速度，并没有一种复杂算法可以完整的处理立体匹配的整个流程，本文所述算法主要针对立体匹配中图像像素匹配并计算视差这一核心步骤。
通常根据立体匹配算法所采用的约束，可以将其分为两大类算法[5]：第一类为基于区域约束的局部匹配算法。如采用匹配窗的代价聚合算法（平方差算法SSD，绝对差算法SAD，归一化算法NCC等）；采用特征点的匹配算法；采用相位匹配的的匹配算法。这些算法的优点是算法整体的计算量小，能够快速恢复出纹理丰富区域的视差。缺点是在低纹理区域会造成误匹配[5]，得到的视差图不致密，需要在后期通过插值算法来进行修正。第二类为基于全局约束的优化算法，如图割算法(Graph
Cuts, GC)，人工智能算法（如遗传算法，多层神经网络），置信传播算法(Belief
Propagation, BP)，动态规划算法(Dynamic Programming,
DP)。这些算法虽然运算时间较长并且会产生一些误匹配，但是基本上能够获得所有的视差信息从而生成稠密的视差图。
1.2 国内外研究现状
国外在计算机立体视觉上的研究开展较早，Roy[7]最早将图割算法应用于立体匹配，并通过实验表明，图割算法能有效克服其他全局优化算法的缺点（如动态规划算法等生成视差图产生的横向条纹瑕疵），避免了视差在临近极线处不连续的问题。但该算法生成的视差图轮廓边缘模糊，视差层的区分度低。Geiger等[8]，针对高分辨率图像立体匹配运算时间长的问题，创造性的提出了使用强约束点（纹理或特征信息较为丰富）作为支撑点，在强约束点之间通过三角剖分对视差图进行插值计算，结合OpenMP技术在通用CPU上实现了并行计算，操作简单易于搭建环境，在通用微型计算机上实现了实时立体匹配，但是匹配效果和基于全局优化的匹配算法有一定差距。
国内对于立体视觉的研究起步较晚，早期主要采用基于特征点匹配的方法，随着技术的进步，后序对立体匹配的改进工作主要集中在对全局优化算法性能和准确度的提升上。其中大部分方法采用对待匹配图像进行图像分割后，再结合能量最优化的方法进行立体匹配。如尹等[9]首先采用均值平移算法将参考图像根据颜色信息快速聚类；之后计算初始视差图；最后采用图割算法并将分割结果作为独立的一项计算能量函数最小值。此种基于图像分割的立体匹配方法的理论基础认为，分割区域块内的视差变化是平滑的。因此与其他基于图像分割的立体匹配算法相比，此类算法[9]可有效地处理大块低纹理区域，匹配精度高，更有利于估计视差图的边界。并且上述算法通过分割减少了匹配基元，使得运算速度更快，能够很好的解决的边界模糊和低纹理区域的误匹配问题。
立体匹配技术在工程领域的应用十分广泛，比如在我国嫦娥探月工程中，王等[4]改进了勇气号机遇号火星车复杂的定位技术，对嫦娥3号月面巡航器的视觉导航系统，采用SIFT(scale-invariant
feature transform)
匹配、相关系数匹配、最小二乘匹配和光束法平差等多项技术融合，实现了相邻站间月面巡视器的导航定位。实验表明该系统视觉定位相对精度优于4%。
朱[10]使用双目立体视觉的方法进行工件的自动定位、识别与抓取，首先根据采集到图像的SIFT特征，从SIFT特征集合模板中匹配工件进行识别。其次，去除噪声后对图像进行二值化并获取质心坐标进行定位。最后，结合双目立体视觉标定技术，使用最小二乘法求得工件质心的世界坐标，为机器人抓取工件提供信息。
顾等[11]为实现统计实时人流，提出一种基于立体视觉的人头检测算法。该方法对双目相机采集的图像通过运动目标检测分离出运动人员所在区域，利用视差的连续性只对强纹理点进行绝对误差累积(SAD)匹配，其余点只进行视差验证，因此能够得到稠密的视差图，再由三角投影关系计算出深度图。由于双目立体成像得到的深度图中人员与场景的深度分布不同，采用深度分层的方法将存在人头信息的深度层提取出来，并通过几何形态来确定人的头部，该算法可以很好地适应复杂场景下的人头检测，并且由于采用了基于局部优化的匹配算法结合插值计算等手段所以其在精度、速度上都有很好的实时特性。
Yang等[12]提出了基于最小生成树的代价聚合方案，采用像素间的相似性作为边的权值，通过无向连通图构建最小生成树，使得局部像素点获取了全局的信息。该算法对于低纹理，无纹理，光照变化等区域的匹配效果达到甚至超越了全局优化算法的水平。针对采集的待匹配图像可能带有噪声或者复杂纹理的问题，Yang等在上述算法的基础上进行了系统化的流程设计与改进[13]，利用左右交叉检验精确更新代价聚合中稳定和不稳定的点的代价，提升了算法精度。
近年来立体匹配技术的实时性需求日益高涨，随着硬件的发展，立体匹配围绕如何快速获取稠密视差图以及将匹配算法并行化进行了卓有成效的研究，通过将图像分割替换为运算效率更高的保边滤波器，Yang等[14]，利用双边滤波器性质并加以改进，融合并行计算技术，达到了平均每秒60帧左右的匹配结果。Qingqing
Yang等[15]针对另一种保边滤波器——导向滤波，提出了新的代价聚合方案，采用自适应窗口融合滤波进行代价聚合，在局部匹配算法中取得了不错的精度，并且该算法经过并行化处理后可以在GPU上进行运算，相对于CPU取得了平均30倍的加速[16]。
1.3本文研究内容
本文针对双目立体视觉中基于图论的立体匹配算法进行研究。主要研究以下几个方面的内容：
1.通过研究立体匹配算法的发展历史和分类准则，在对前人文献阅读的基础上根据文献的实验结果评价算法质量，从中选取一到两个有意义且实用性强的研究切入点。
2.研究图割算法及其应用，主要包括：基本思想，算法流程，能量函数的构造，以及能量最小化等相关内容。
3.根据对立体匹配应用场景的分析，本文提出一种基于交互式图像分割的立体匹配方法。针对大多数场景中只需计算特定目标视差的需求，通过有效利用网络图先后完成了图像分割和立体匹配的工作，降低了算法的空间复杂度和内存占用，并且减少了运算时间。
4.针对全局优化算法运算时间缓慢，局部优化算法结果不精确的问题。本文利用最小生成树取代局部优化算法的匹配窗，为匹配基元添加了全局特性，并通过OpenMP，SIMD等技术在通用处理器上对算法进行扩展优化，达到了实时计算的标准。
5.介绍了本文算法试验系统的软硬件配置，阐述并详细分析了实验结果，对双目立体视觉未来的研究方向，研究热点进行了预测与展望。
1.4论文结构
本文针对上述研究内容，共包含五章：
第一章：绪论，介绍了研究立体匹配的背景与意义，根据国内外文献的实验结果和原理阐述各类立体匹配方法的优缺点，总结本文的基于图论的立体匹配算法研究内容，描述文章框架。
第二章：立体匹配基础，首先介绍了双目视觉的基础理论，立体匹配的基础——视差理论。其次介绍了立体匹配算法设计中需要注意的各类约束，主要包括：极线，相容性，唯一性，连续性等约束。最后介绍了立体匹配的几种主要算法，立体匹配后处理中遮挡问题的处理。
第三章：基于交互式图像分割的立体匹配方法，提出了一种基于图割算法的立体匹配方法，其流程充分利用了网络图资源，有效降低了内存占用提高了算法运行时间。本章主要介绍了图割算法中的网络流问题，能量函数的优化问题。详细介绍了图割算法中立体匹配网络图的构造，基于图割算法的交互式图像分割与立体匹配的融合过程。介绍了本章算法的优秀效果，基于Middlebury学院提供的标准图像库对原始图割算法进行了对比实验，并给出了分析。
第四章：基于最小生成树的实时立体匹配算法，针对带有非局部特性的立体匹配方法，根据局部算法特性，将匹配窗的代价聚合方式替换为拥有全局特性的树形结构的代价聚合，介绍了在树形结构上进行代价聚合的两种方式，提出了一种可移植的通用并行化加速扩展方案，通过此方法将原有串行算法的运算速度提升为实时运算。
第五章：总结与展望，对本文工作进行了总结，展望了立体匹配算法今后的发展方向。
参考文献
马颂德,张正友. 计算机视觉—计算理论与算法基础[M].北京:科学出版社,1997.
邸凯昌. 勇气号和机遇号火星车定位方法评述[J]. 航天器工程, 2009, 18(5):1-5.
吴伟仁, 王大轶, 邢琰,等. 月球车巡视探测的双目视觉里程算法与实验研究[J].
中国科学:信息科学, 2011(12):1415-1422.王保丰, 周建亮, 唐歌实,等. 嫦娥三号巡视器视觉定位方法[J].
中国科学：信息科学, 2014, 04期(04):452-460.白明, 庄严, 王伟. 双目立体匹配算法的研究与进展[J]. 控制与决策, 2008,
23(7):721-729.张令涛, 曲道奎, 徐方. 一种基于图割的改进立体匹配算法[J]. 机器人, 2010,
32(1):104-108.Roy S, Cox I J. A maximum-flow formulation of the n-camera stereo
correspondence problem[A]// IEEE International Conference on Computer
Vision[A], 1998 January 4-7, Bombay India:492-499.Geiger A, Roser M, Urtasun R. Efficient large-scale stereo
matching[M]//Computer Vision–ACCV 2010. Springer Berlin Heidelberg, 2011:
25-38.尹传历, 刘冬梅, 宋建中. 改进的基于图像分割的立体匹配算法[J].
计算机辅助设计与图形学学报, 2008, 20(6):808-812.朱代先. 基于双目视觉的工件定位与抓取研究[J]. 计算机测量与控制, 2015,
19(1):92-94.顾骋, 钱惟贤, 陈钱,等. 基于双目立体视觉的快速人头检测方法[J]. 中国激光,
2014(1):150-155.Yang Q. A non-local cost aggregation method for stereo matching[C]//
Proceedings / CVPR, IEEE Computer Society Conference on Computer Vision and
Pattern Recognition. IEEE Computer Society Conference on Computer Vision and
Pattern Recognition. 2012:1402-1409.Yang Q. Stereo Matching Using Tree Filtering[J]. Pattern Analysis & Machine
Intelligence IEEE Transactions on, 2015, 37(4):834-846.Yang Q. Hardware-efficient bilateral filtering for stereo matching[J].
Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2014,
36(5): 1026-1032.Yang Q, Li D, Wang L, et al. Full-Image Guided Filtering for Fast Stereo
Matching[J]. IEEE Signal Processing Letters, 2013, 20(3):237-240.Yang Q, Ji P, Li D, et al. Fast stereo matching using adaptive guided
filtering[J]. Image and Vision Computing, 2014, 32(3): 202-211.
