（信号与信息处理专业论文）基于gpu的立体匹配算法研究.pdf

j i i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：童t 盏望 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：龟狴导师签名：论文作者签名：继銎导师签名： 山东大学硕士学位论文 目录 中文摘要i a b s t r a c t i i 缩略语i v 第一章绪论1 1 1 研究背景与选题意义l 1 1 1 立体视觉概论1 1 1 2 并行计算概述3 1 1 3 基于立体视觉的智能驾驶辅助系统概述5 1 1 4 选题意义。6 1 2 研究目标与主要工作6 1 3 本文内容安排7 第二章摄像机标定与图像校准8 2 1 针孔摄像机模型8 2 2 摄像机标定9 2 2 1 单目摄像机标定1 0 2 2 2 立体摄像机标定1 2 2 3 立体图像对极线校准1 3 第三章立体匹配算法概述1 5 3 1 立体匹配基础15 3 1 1 立体匹配规则15 3 1 2 立体匹配算法1 8 3 2 动态规划算法l8 3 3 置信传播算法2 0 3 4 图割算法2 2 第四章基于g p u 的并行算法2 5 4 1g p u 通用计算2 5 4 2c u d a 技术概述一2 8 山东大学硕士学位论文 4 3c u d a 模型2 9 4 3 1c u d a 编程模型2 9 4 3 2c u d a 硬件模型3 0 4 4 基于c u d a 的计算机视觉算法3 1 4 4 1 算法描述3 2 4 4 2 计算机视觉算法c u d a 实现示例3 2 4 5 本章小结3 3 第五章立体匹配算法的c u d a 并行实现3 4 5 1 立体匹配算法c u d a 实现基本思想3 4 5 2 动态规划算法的并行实现一3 5 5 2 1 动态规划算法处理真实图像3 5 5 2 2 基于图像序列的动态规划算法一3 6 5 2 3 动态规划算法的c u d a 实现。3 7 5 3 置信传播算法的并行实现3 8 5 3 1 置信传播算法处理真实图像3 8 5 3 2 图像预处理去除噪声3 9 5 3 3 置信传播算法的c u d a 实现4 l 5 4 实验结果及分析4 2 5 5 本章小结4 3 第六章总结与展望一4 4 参考文献一4 5 致谢5 0 攻读硕士研究生期间发表论文5 l i i 山东大学硕士学位论文 c o n t e n t s c h i n e s ea b s i r a c r 1 a b s t r a c t i i a b b r e v i a t i o n s i v c h a p t e r l i n t r o d u c t i o n l 1 1r e s e a r c hb a c k g r o u n da n ds i g n i f i c a n c e l 1 1 1s t e r e ov i s i o n 1 1 1 2p a r a l l e lc o m p u t a t i o n 3 1 1 3v i s i o nb a s e dd r i v e ra s s i t a n c es y s t e m 5 1 1 4s i g n i f i c a n c e 6 1 2r e s e a r c ho b j e c t i o n sa n dm a i nt a s k 6 1 3a r r a n g e m e n to f t h i st h e s i s 7 c h a p t e r 2c a m e r ac a l i b r a t i o na n di m a g er e c t i f i c a t i o n 8 2 1c a m e r am o d e l s 8 2 2c a m e r ac a l i b r a t i o n 9 2 2 1s i n g l ec a m e r ac a l i b r a t i o n 1 0 2 2 2s t e r e os y s t e mc a l i b r a t i o n 一12 2 3e p i p o l a rr e c t i f i c a t i o n 13 c h a p t e r 3i n t r o d u c t i o no fs t e r e oa l g o r i t h m s 15 ：；1s t e r e om a t c h i n g 15 3 1 1r u l sf o rs t e r e om a t c h i n g 1 5 ：；1 2s t e r e oa l g o r i t h m s 18 3 2d y n a m i cp r o g r a m m i n g a l g o r i t h m 18 3 3b e l i e fp r o p o g a t i o na l g o r i t h m 2 0 3 4g r a p hc u ta l g o r i t h m 2 2 c h a p t e r 4p a r a l e lc o m p u t a t i o nb a s e d o ng p u 2 5 4 1g e n e r a lp u r p o s eg p u c o m p u t a t i o n 2 5 4 2i n t r o d u c t i o no fc u d a 2 8 4 3c u d am o d e l 2 9 1 1 i 山东大学硕士学位论文 4 3 1c u d ap r o g r a m m i n gm o d e l 2 9 4 3 2c u d ah a r d w a r em o d e l 3 0 4 4c o m p u t e rv i s i o na l g o r i t h mb a s e do nc u d a 31 4 4 1a r i t h m e t i cf l o w 3 2 4 4 2e x a m p l e si m p l e m e n t a t i o no i lc u d a 3 2 4 5s u m m a r y 3 3 c h a p t e r 5p a r a l e ls t e r e oa l g o r i t h m sb a s e do nc u d a 3 4 1 ；1s t e r e om a t c h i n gu s i n gc u d a 3 4 5 2p a r a l l e li m p l e m e n t a t i o no fd y n a m i cp r o g r a m m i n g 3 5 5 2 1d pf o rr e a l - w o r l di m a g e s 3 5 5 2 2t e m p o r a lp r o p a g a t i o nb a s e dd p 3 6 5 2 3i m p l e m e n t a t i o nu s i n gc u d a 3 7 5 3p a r a l l e li m p l e m e n t a t i o no fb e l i e fp r o p a g a t i o n 3 8 5 3 1b pf o rr e a l w o r l di m a g e s 3 8 5 3 2i m a g e sp r e p r o c e s s i n gf o rb p 3 9 5 3 3i m p l e m e n t a t i o nu s i n gc u d a 4 1 5 4s i m u l a t i o na n dr e s u l t sa n a l y s i s 4 2 5 5s u m m a r y 4 3 c h a p t e r 6c o n c l u s i o n sa n df u t u r ew o r k 4 4 r e f e r e n c e s 4 5 a c k n o w l e d g e m e n t 5 0 p u b l i c a t i o n sd u r i n gt h er e s e a r c h 5 1 i v 山东大学硕士学位论文 中文摘要 基于立体视觉的汽车辅助驾驶研究涉及图像处理、计算机视觉、电子技术 等关键技术，是计算机科学领域内最近兴起的热门研究方向，该技术模拟人眼 视觉机理，通过一组摄像机获得汽车周围立体道路信息来辅助驾驶，其关键技 术涉及计算机视觉科学重要难点问题研究。汽车驾驶辅助系统要求数据处理必 须与车体高速行驶同步进行，对不同道路环境、复杂路面状况以及变化气候条 件均具有良好适应性，为此研究新的机器视觉算法满足实时和鲁棒性要求是本 课题的目标和困难所在。本文将研究探索立体匹配计算深度图从二维图像恢复 出三维信息，并在g p u 上的并行实现，。以实现路况识别和车辆、障碍物的距离 计算、速度检测，最终获得车辆运行引导信息。与其它引导技术( 如车载雷达) 相比，双目视觉引导有许多优势，它不必在道路上增加设施，能适合来往车辆、 行人、临时设施等。 将立体匹配技术应用于智能驾驶系统时，由于真实图像匹配难度大，故只 能采用效果好，但计算量大的全局优化算法。本文在对立体匹配预备工作，如 摄像机标定、立体图像校准、常用全局优化算法，以及g p u 并行计算做了介绍 之后，重点阐述了如何在g p u 上高效的实现图像的立体匹配和针对真实路面图 像进行预处理以得到更好的匹配效果。具体内容包括以下两个方面： 1 研究了动态规划立体匹配算法。结合真实图像场景信息复杂的特点，提 出了一种基于移动窗口的代价函数计算方法，并且针对图像序列处理时，利用 前一帧图像的代价函数信息来对当前帧进行更新，得到了更加平滑的视差图。 并用g p u 并行实现，达到每秒10 帧。 2 研究了置信传播立体匹配算法。置信传播算法在立体匹配中效果要好于 动态规划，但是对复杂图像的噪声鲁棒性也不如动态规划，同时也耗费更多的 时间。对此，我们对真实图像进行了s o b e l 算子以及r e s i d u a l 图像预处理，有 效的避免了噪声的影响，并用g p u 并行实现，达到每秒4 帧。 最后，对所做研究的成果进行了总结，并提出了将来努力的方向。 关键词：智能辅助驾驶；立体匹配：动态规划；置信传播；g p u 并行运算 山东大学硕士学位论文 a b s t r a c t s t e r e ov i s i o nb a s e dd r i v e ra s s i s t a n c es y s t e m ( d a s ) i sas i g n i f i c a n tt a s ki nt h e f i e l do fc o m p u t e rv i s i o n t h et e c h n i q u es i m u l a t e sh u m a nv i s u a lm e c h a n i s m ， 山东大学硕士学位论文 缩略语 b p ( b e l i e f p r o p a g a t i o n ) 置信传播算法 c u d a ( c o m p u t eu n i f i e dd e v i c ea r c h i t e c t u r e ) 统一计算设备架构 d a s ( d r i v e ra s s i t a n c es y s t e m ) 驾驶辅助系统 d p ( d y n a m i cp r o g r a m m i n g ) 动态规划算法 g c ( g r a p hc u t ) 图割算法 g p g p u ( g e n e r a lp u r p o s eg r a p h i cp r o c e s s i n gu n i t ) 通用图形处理器 g p u ( g r a p h i cp r o c e s s i n gu n i t ) 图形处理器 m i m d ( m u l t i p l ei n s t r u c t i o nm u l t i p l ed a t a ) 多指令多数据 m i s d ( m u l t i p l ei n s t r u c t i o ns i n g l ed a t a ) 多指令多数据 m r f ( m a r k o vr a n d o mf i e l d ) 马尔可夫随机场 s i m d ( s i n g l ei n s t r u c t i o nm u l t i p l ed a t a ) 单指令多数据 s i s d ( s i n g l ei n s t r u c t i o ns i n g l ed a t a ) 单指令单数据 l i p 山东大学硕士学位论文 1 1 研究背景与选题意义 第一章绪论 现代社会，随着经济的发展，人们生活水平的日益提高，交通需求增加， 供需矛盾u 益突出。交通拥堵、交通事故频发、以及其导致的环境和能源等问 题成为世界各国面临的共同问题。据美国公路交通安全管理总署( n h t s a ) 公布 的数据，2 0 0 9 年美国共发生交通事故6 0 2 4 0 0 0 起，造成3 3 9 6 3 人死亡，1 7 1 1 0 0 0 人受伤1 1 1 。在我国，根据公安部交通管理局统计数据，2 0 0 9 年全国共发生道路 交通事故2 3 8 3 5 1 起，造成6 7 7 5 9 人死亡、2 7 5 1 2 5 人受伤，直接财产损失9 1 亿元人民币1 2 】；2 0 0 8 年全国共发生道路交通事故2 6 5 2 0 4 起，造成7 3 4 8 4 人死 亡、3 0 4 9 4 9 人受伤，直接财产损失l o 1 亿元人民1 3 】。面对复杂的道路交通形势， 智能驾驶辅助系统( d a s ) 得到了广泛的研究。 目前国外很过公司如戴姆勒、丰田已经实现智能驾驶辅助系统，但均采用 了雷达、超声探测器等高成本设备，同时也缺乏良好的人机交互界面，容易造 成视觉疲劳，不能友好生动的提示驾驶员。而雷达等探测器只能用于监测前方 物体，却不能识别行人、车辆、或者其他障碍物，而基于视觉的智能驾驶辅助 系统，不仅能够实现深度探测，还可以做车辆行人识别、路标识别、自动跟踪 等。 基于立体视觉的汽车辅助驾驶系统，仿照人类利用双目线索感知距离的方 法实现对三维信息的感知，通过安装在汽车前方的两台摄像机获得汽车前方5 0 米区域内的立体道路信息，通过对视场中的运动物体、障碍物、交通标识进行 分析，为处理器的决策提供依据。 。 1 1 1 立体视觉概论 视觉是人类观察世界、认知世界的重要手段，人类从外界获取的信息约有 7 5 来自视觉系统【4 1 ，随着计算机技术和图像处理技术的发展，二维图像信息己 不能满足人们的需要，因此使计算机具备感知三维信息的能力就变得异常重要。 计算机视觉技术是人工智能研究的一个重要分支，计算机视觉研究的目的 山东大学硕士学位论文 就是要使计算机具有和人类水平相当的视觉能力。讨。算机视觉又是个综合性 的学科，它同时涉及到计算机科学、信号处理、应用数学和统汁学、心理学、 认知科学、神经科学等诸多学科。 虽然计算机视觉技术还处在发展阶段，仍有许多问题没有解决，但是已有技 术已在制造业、文档分析、医疗和军事领域取得了很多的应用。世界经济的发展， 自动化程度的提高也对计算机视觉技术的发展提出了新的要求。 现有的计算机视觉框架中最有影响的应属m a n 5 j 存八十年代提出的视觉理 论框架。m a n 从信息处理的角度综合了图像处理、心理物理学、神经生物学及 临床精神病学的研究成果，提出了第一个较为完善的视觉框架。虽然在细节和主 导思想方面尚存在争议的地方，但是仍对计算机视觉的发展产生了深远的影响。 m a n 将视觉系统研究分为三个层次：计算理论层次、表达与算法层次、硬件实 现层次。 计算理论层次回答了视觉系统的计算目的与计算策略，在这个层次上，系统 输入二维图像，输出三维物体的形状、位置等信息；表达与算法层次进一步回答 了如何表达输入和输出信息，如何实现计算理论层所对应功能的算法；硬件实现 层次中回答了如何用硬件实现上述策略和算法的问题。 m a r r 从视觉计算理论出发，将系统从输入的二维图像数据到输出的3 d 描述 信息分为了自上而下的三个阶段。第一阶段，构建由二维图像中的边缘点、曲线、 纹理等基本几何元素组成的基元图( p r i m a r ys k e t c h ) 。第二阶段，在以观察者为中 心的坐标系中，表达可见区域的方向、深度值和不连续轮廓等不完整的三维信息， 又称为对环境的2 5 维描述。第三阶段，由2 5 维描述最终获得场景中物体的三维 描述，确定三维场景中物体的位置和姿态。 m a r r 视觉理论系统地揭示了用二维图像恢复物体3 d 信息的可能性和基本方 法，使对视觉信息的研究有了明确的内容和较完整的体系，为计算机视觉这一学 科奠定了重要的基础。这一框架虽然在细节上甚至在主导思想上还存在小完备的 方面，许多方面还有很多争议，但至今仍是目前计算机视觉研究的基本框架。此 后，计算机视觉理论和技术已有了很大的进步，但是大部分工作仍可以用他的理 论框架概括。 视觉系统可分为单目视觉系统、双目视觉系统和多目视觉系统。从本质上讲， 真实世界中，场景在摄像机中的成像，随着视角的不同而呈现出各样的2 d 图像， 如图1 1 所示，即视觉成像的多义性。因而单目视觉系统是不能获取三维世界中 2 山东大学硕士学位论文 的物体位置信息的，必须依赖于一定的辅助信息。采用单目视觉系统进行测距总 是依赖于一定的假设条件、先验知识等辅助信息，检测结果直接依赖于假设和信 息的准确性。双目、多目视觉系统根据视差原理测距，检测结果不依赖于任何假 设条件、先验知识等辅助信息的存在。综合以上分析，本文采用视觉系统中的双 目立体视觉系统。 警 ，、 图1 1 场景随着摄像机视角变化产生不同成像 立体视觉是由多幅图像( 一般是两幅) 获取物体三维几何信息的方法。对生物 视觉系统，人们早就注意到，几乎所有具有视觉的生物都有两个眼睛。用两个眼 睛同时观察物体时，会有深度或远近的感觉。立体电影之所以有逼真的深度感， 也是仿造了立体视觉原理。在立体电影拍摄中，用两个摄像机同时拍摄，而在放 映时，将两个摄像机拍摄的图像同时投影到屏幕上，并利用偏振光的原理，使人 的双眼分别看到左右摄像机拍摄的图像，从而使人感到真实三维场景的立体感哺1 。 在计算机立体视觉系统中，也可以利用摄像机从不同角度获取同一景物的两幅图 像，然后利用三维重建原理，由计算机重建景物的三维形状，恢复出物体的空间 位置信息。 1 1 2 并行计算概述 并行计算( p a r a l l e lc o m p u t i n g ) 是指同时使用多种计算资源解决计算问题 的过程。为执行并行计算，计算资源应包括一台配有多处理机( 并行处理) 的 3 咀爹荔， 一一；圳i一 _ ，l；：；黔。； 山东大学硕士学位论文 计算机、一个与网络相连的计算机专有编号，或者两者结合使用。并行计算的 主要目的是快速解决大型且复杂的计算问题。此外还包括：利用非本地资源， 节约成本使用多个“廉价”计算资源取代大型计算机，同时克服单个计算机 上存在的存储器限制。 传统地，串行计算是指在单个计算机( 具有单个中央处理单元) 上执行软 件写操作。c p u 逐个使用一系列指令解决问题，但其中只有一种指令可提供随 时并及时的使用。并行计算是在串行计算的基础上演变而来，它努力仿真自然 世界中的事务状态：一个序列中众多同时发生的、复杂且相关的事件。 为利用并行计算，通常计算问题表现为以下特征： ( 1 ) 将工作分离成离散部分，有助于同时解决； ( 2 ) 随时并及时地执行多个程序指令； ( 3 ) 多计算资源下解决问题的耗时要少于单个计算资源下的耗时。 并行计算是相对于串行计算来说的，所谓并行计算分为时问上的并行和空 间上的并行。时问上的并行就是指流水线技术，而空间上的并行则是指用多个 处理器并发的执行计算。 并行计算科学中主要研究的是空间上的并行问题。空间上的并行导致了两 类并行机的产生，按照f l y n n 7 】的理论分为：单指令流多数据流( s i m d ) ，多指 令流单数据流( m l s d ) 和多指令流多数据流( m i m d ) 。我们常用的串行机也 叫做单指令流单数据流( s i s d ) 。 单指令流单数据流( s i s d ) 的计算机在同一时刻只能执行一条指令( 即只 有一个控制流) 、处理一个数据( 即只有一个数据流) ，所有的冯诺依曼体系结 构的“单处理器计算机”都是这类。 多指令流单数据流( m i s d ) 是一个单一的数据流输入到多个处理单元进行 操作，每个处理单元独立地对数据执行对应的指令。较经典的此类并行运算的 案例是1 9 7 1 年卡梅隆大学发明的c m m p 计算机。 单指令流多数据流( s i m d ) 并行处理机是通过重复设置大量相同的处理单 元p e ( p r o c e s s i n ge l e m e n t ) ，将它们按一定的方式互连，在统一的控制部件c u ( c o n t r o lu n i t ) 控制下，对各自分配来的不同数据并行地完成同一条指令所规定 的操作。它依靠操作一级的并行处理来提高系统的速度。并行处理机的控制部 件中进行的是单指令流，因此与高性能单处理机一样，指令基本上是串行执行， 最多加上使用指令重叠或流水线的方式工作。指令重叠是将指令分成两类，把 4 山东大学硕士学位论文 只适合串行处理的控制和标量类指令留给控制部件自己执行，而把适合于并行 处理的向量类指令“播送”到所有处理单元，控制让处于“活跃”的那些处理单元 并行执行。因此这是一种标量控制类指令和向量类指令的重叠执行。 _ _ - _ o _ - o _ _ _ o _ - _ _ - _ _ _ _ o _ _ o _ _ o o _ _ _ o _ _ _ o _ _ _ - _ o _ _ _ _ 一 m i s dl i n s t r u c t i o np o o l l s i s d i i n s t r u c t i o np o o l l e 囤圃 s i m d 互三亟困m i m d 至五画丑 图1 1f l y n n 计算机分类8 1 多指令流多数据流( m i m d ) 中每个处理单元都有与其对应的独立的指令 流和数据流，从而执行不同的操作，执行不同的数据。这类并行处理结构是最 常见的。 1 1 3 基于立体视觉的智能驾驶辅助系统概述 基于立体视觉的智能驾驶辅助系统( d a s ) 目的是获取汽车前方场景的深 度信息，从中分割出运动区域，对运动区域进行跟踪，预测出运动轨迹，对可 能发生的撞击提前预警，由于汽车处于高速运动状态，所以，系统对算法的可 靠性和实时性有严格的要求，一直以来立体匹配、深度图分割算法都已运算量 巨大著称，并且光照变化还直接影响运算结果。综上所述，本项目的研究重点 5 111l-1lj 囤囤囤囤 一 _ o o 西苗q 一 i 山东大学硕士学位论文 是同时满足实时性与可靠性的立体视觉辅助驾驶系统。 具体而言，实现机器视觉测距包括一系列算法：立体匹配算法、运动特征 点提取算法、运动区域分割算法和摄像机实时标定算法等。传统的立体匹配算 法，大多是基于特征或区域的匹配【9 , 1 0 】，如s i f t 1 1 1 算法或s u r f 1 2 1 算法，由于 特征的稀疏性和不规则性，使用特征匹配只能得到稀疏的视差图和深度图，必 须经过插值计算才能形成致密的深度图，而插值过程本身是个计算复杂度很高 的任务且容易产生较大误差；而基于区域的匹配主要依据为灰度连续性且多是 局部算法，受噪声( 特别是光照) 影响较大，尤其是对交叉摆放的双目c c d 立体视觉系统，左右图像灰度变化不一致，误匹配几率增大。为克服上述问题， 我们采用动态规划算法( d y n a m i cp r o g r a m m i n g ) t ”】和置信传播算法( b e l i e f p r o p a g a t i o n ) 1 4 1 求取深度图，这两种算法同属全局算法效果虽好，然而计算量巨 i 大难以达到实时性要求，故而项目组选用g p u 多核处理器，对两种算法并行化 处理，并采用r e s i d u a l 及s o b e l 边缘检测对图像序列预处理【1 5 , 1 6 】，抑制光照噪 声对匹配的影响，以实现快速准确的视频序列立体匹配技术。 1 1 4 选题意义 智能驾驶辅助系统的研究中，算法的实时性是在实际应用中的重要问题之 一，而现行的立体匹配算法在实时性和准确性上难以兼得。实时性较高的基于 局部的立体匹配算法针对实际采集的真实路面图像的处理效果非常之差，不能 达到识别目的；而准确性较高的基于整体的立体匹配算法虽然能够满足后续工 作比如测距、识别，但是在处理速度上难以达到实时，所以我们采用并行计算 的方法对算法进行加速，从而在实际中得到应用。 1 2 研究目标与主要工作 本文的研究目标是针对立体匹配算法在智能驾驶辅助系统中实际应用存在 的实时性问题研究，对全局算法动态规划算法以及置信传播算法在d a s 真实路面图像匹配时进行改进并在g p u 上实现并行运算。全部研究工作主要包 含以下几部分： 1 熟悉立体匹配技术的基本原理，学习数字图像处理和计算机视觉理 论，奠定研究工作的理论基础。 6 山东大学硕士学位论文 深入学习g p u 并行编程技术，对基于c u d a 平台的并行编程形成 清晰的认识，分析算法流程。同时学习计算机视觉基本算法在 c u d a 上并行实现的基本思想。 大量阅读论文及相关参考文献，深入了解现有立体匹配算法，分析 各种算法的优缺点和适用环境，并针对d a s 真实路面图像对算法 其不足提出改进。 对改进后的全局优化立体匹配算法动态规划算法以及置信传 播算法进行并行算法设计，并在c u d a 平台上实现并行计算。 1 3 本文内容安排 论文全文共分为五章： 第一章“绪论”，简单介绍了计算机立体视觉和智能辅助驾驶系统的相关 背景，指出了其所面临的一些难题，阐明了本研究的意义。 第二章“摄像机标定与图像校准”，简要介绍了摄像机几何模型，包括线 性模型和非线性模型，以及立体匹配之前的预备工作：摄像机标定和立体图像 对的极线校准技术。 第三章“立体匹配算法概述”，介绍了当前在立体视觉中所采用的匹配算 法，分析了各算法中存在的问题，并仿真测试加以比较。 第四章“基于g p u 的并行算法”，介绍了如何使用g p u 进行通用并行计 算，以及c u d a 平台的编程模型和硬件模型，阐述了普通计算机视觉算法如何 在c u d a 上并行实现，并编程验证其与c p u 进行比较。 第五章“立体匹配算法的c u d a 并行实现”，提出了动态规划算法和置信 传播算法在d a s 真实路面图像序列中的应用。并针对真实图像的立体匹配进行 了改进，最终在c u d a 上并行实现，实现实时计算。 第六章“总结与展望”，是对整个论文的总结，简要回顾了论文工作，并 指出了下一步的研究方向。 7 2 3 4 山东大学硕士学位论文 第二章摄像机标定与图像校准 2 1 针孔摄像机模型 在计算机视觉中，摄像机模型解决的是三维场景中的点如何和平面上的点 联系起来的问题。空间任意一点p 在图像上的成像位置可用针孔模型近似表示， 即任何点p 在图像上的投影位置p ，为光心o c 与p 点的连线o c p 与图像平面 的交点，这种关系也称为中心投影或透视投影( 图2 1 ) 。 图2 1 中心透视模型 h ，i v , z w ) 其中点p 在成像平面坐标系下的坐标为o ，力，空间点p 在摄像机坐标系下的 坐标为( 拖，比，z c ) 。因为o c ，p ，p 三点共线，应有q p = 2 q p 九为某个数 季y 三三羹 ，五：j 乏：专：乏 c2t，2z = 五匕 ，五= = 軎= 弓_ ( 2 1 ) 【厂=。 。、 山东大学硕士学位论文 - x - f x2j 了 厶c ，e 。1 音 z f 将上式用齐次坐标与矩阵来表示可以得到 、r x 0000 。 蚓乏 j l - 1 将( 2 1 ) 与( 2 2 ) 代入上式可以得到图像坐标系与世界坐标系之间的关系 7 ： 幺盯 勉 o o ， 0 舱h 辜 m 阵 = x rt p 7 = m p ( 2 2 ) ( 2 3 ) ( 2 4 ) 其中无= ，工= ，= s = 厂( rt ) 称为摄像机的外参数矩阵包括 旋转矩阵r 和平移矩阵t ；( “o ，v o ) 为主点坐标五和 分别是“轴和，轴上的 尺度因子，堤描述两图像坐标轴倾斜程度的参数；k 是3x 3 的矩阵称为内参 数矩阵；m 为3x 4 矩阵称为投影矩阵。式( 2 4 ) 就表达了摄像机成像原理。 2 2 摄像机标定 在立体视觉中，最基本的问题之一就是立体匹配。立体匹配旨在左右相机 采集到的立体图像对中得到场景中物体的深度信息，从而根据相机参数预测前 方与相机的距离。丽首要任务就是通过摄像机标定的方法获取相机参数，最后 通过相机参数映射到真实世界坐标系。 9 ，o o 。l i i 1j x y 。l c z o 厂o ，o o 。l 1，j 山东大学硕士学位论文 2 2 1 单目摄像机标定 1 传统标定方法 所谓传统摄像机标定方法是指用一个结构己知、精度很高的标定板作为空 间参照物，通过空间点和图像点之间的对应关系来建立摄像机模型参数的约束， 然后通过优化算法来求取这些参数。根据参数的计算方法的不同，可分为利用 最优化算法的标定方法【1 7 1 ，利用投影矩阵的方法【t s , 1 9 , 2 0 l 及t s a i 两步标定技术 1 2 1 , 2 2 】。传统标定方法的优点在于可以获得较高的精度，适用于要求的精度高且 摄像机的参数不经常变化的场所。 2 自标定方法 为近年来发展起来的另一类摄像机标定技术，摄像机自标定方法与传统的 摄像机标定方法的显著不同之处在于，摄像机自标定方法不需要借助于任何外 在的特殊标定物或某些三维信息己知的控制点，而是仅仅利用了图像对应点的 信息，直接通过图像来完成标定任务的。正是这种独特的标定思想赋予了摄像 机自标定方法巨大的灵活性，同时也使得计算机视觉技术能够面向范围更为广 阔的应用。众所周知，在许多实际应用中，由于经常需要改变摄像机的参数， 因此经常需要进行实时的、在线的标定，而传统的摄像机标定方法在此类情况 下将由于需要借助于特殊的标定物而变得不再适合。正是因为其应用的广泛性 和灵活性，摄像机自标定技术的研究已经成为近年来计算机视觉研究领域的热 点方向之一。 摄像机自标定方法19 9 2 年由f a u g e r a u s 和m a n y b a n k 2 l 2 4 1 首次提出，并在此 之后不断发展成熟起来。其基本思想是绝对二次曲线( a b s o l u t ec o n i ra c ) ( 或 绝对二次曲面( a b s o l u t eq u a d r i e ) 的像在摄像机做刚体运动时保持不变，其方程 只与摄像机的内参数有关。将绝对二次曲线( 或其对偶) 作为虚拟标定物，通过 不同形式的约束方程求解其在所拍摄图像中的成像方程来实现摄像机标自标定 方法。目前自标定方法主要分类有： 1 ) 基于绝对二次曲线的自标定方法 所谓的绝对二次曲线，是指无穷远平面上的一条与欧氏空间几何性质紧密 相关的特殊二次曲线。绝对二次曲线的像仅仅与摄像机的内参数有关，而与摄 像机的运动、姿态无关。因此，如果确定了绝对二次曲线在图像中的像的位置， 我们便可以获得对摄像机的内参数的约束，从而达到标定摄像机的目的。文献 l o 山东大学硕士学位论文 中首次提出的摄像机自标定方法【2 3 ，2 4 1 便利用了上述性质，在假设摄像机内参数 不变的情况下，给定三幅图像便可以通过求解由绝对二次曲线的对极几何关系 ( e p i p o l a rg e o m e t r y ) 所建立的k r u p p a 方程来标定摄像机的全部5 个内参数。 k r u p p a 方程在形式上和下面所讲的基于绝对二次曲面的自标定方法相似，但是 没有包含无穷远平面的信息，无法保证无穷远平面在所有图像对确定的射影空 间的像的一致性，所以k r u p p a 方程式一个比较弱的约束，一般基于k r u p p a 方 程的自标定算法没有基于绝对二次曲面的算法的鲁棒性好。 2 ) 基于绝对二次曲面的标定方法 所谓的绝对二次曲面( a q ) ，实际上是绝对二次曲线的对偶，是由与绝对二 次曲线相切的空间平面构成的包络二次曲面。与绝对二次曲线类似，绝对二次 曲面的图像也只与摄像机的内参数有关，而与摄像机的刚体运动无关。因此， 类似于绝对二次曲线，我们同样可以利用绝对二次曲面来进行摄像机自标定。 与基于绝对二次曲线的标定方法相比，由于绝对二次曲面另外还包含了无穷远 平面的信息，利用绝对二次曲面进行标定时算法鲁棒性相对要好一些。 3 ) 基于分层重建的标定方法 如果进行摄像机标定的最终目的是要完成欧氏空间的三维重建，我们也可 以采用另类万法来进行标定。实际上，从二维图像空间到三维欧氏空间经历了 射影、仿射和相似一系列变换。因此我们可以逐“层”地进行重建，即先利用 图像信息完成射影空间重建，再通过确定无穷远平面来完成仿射空间重建，最 后再通过摄像机标定实现欧氏空间重建。在仿射重建的基础上进行摄像机标定 的优势在于：如果摄像机的内参数不变，只需采用简单的线性算法就可以完成标 定过程。 3 基于主动视觉的标定方法 基于主动视觉的摄像机标定方法就是根据自主地控制摄像机来获取的图像 数据线性地求解摄像机的模型参数。这种标定方法的主要优点是由于在标定过 程中已知了关于摄像机的运动信息( 包括诸如摄像机在平台坐标系下朝某一方 向平移某一给定量、摄像机的平移运动相互正交等定量信息，以及摄像机仅作 纯平移运动或仅作旋转运动等定性信息) ，所以一般来说，摄像机的模型参数可 以线性求解，且计算简单、鲁棒性较高。基于主动视觉的摄像机标定大体上经 历了两个发展阶段。最初，研究人员主要致力于研制可精确控制的主动视觉平 台，通过精确控制主动视觉平台的运动来对摄像机进行标定。这三维重建和摄 山东大学硕士学位论文 像机标定技术研究方面最具代表性的工作是马颂德研究员于1 9 9 6 年在 i e e e t r a n s r a 上的工作【2 5 1 。使用高精度主动视觉平台进行摄像机标定的不足 是系统的成本较高，不是一般的单位和个人所能承受的。 2 2 2 立体摄像机标定 对与单个摄像机标定的差别是，双目摄像机标定不仅要得出每个摄像机的内 部参数，还需要通过标定来测量两个摄像机之间的相对位置。在双目摄像机标定 中，可以先用单摄像机标定的方法分别得到两个摄像机各自的内外参数。假定摄 像机c l 与世界坐标系相对位置的外部参数为旋转矩阵r l 和平移向量t l ，摄像机 c 2 与世界坐标系相对位置的外部参数为旋转矩阵r 2 和平移向量t 2 。对空间任意 一点p 如它在世界坐标系、摄像机坐标c 1 系和摄像机c 2 坐标系下的非齐次坐标分