基于动态划理论的立体匹配算法研究毕业论文(编辑修改稿)

基于动态划理论的立体匹配算法研究毕业论文(编辑修改稿)内容摘要：

信息。 为了便于研究，完整的双目立体视觉通常会被按照不同的步骤按照既定的流程来进行相关的研究，它主要流程是首先是左右图像信息获取，然后根据图像信息进行相关的预处理方便后续进行分析与研究，接着对预处理后的数据进行摄像机标定的过程 ，随后就是最重要也是最复杂的立体匹配过程，最后完成三维重建，其中立体匹配技术是立体视觉中的重点环节。 整个双目立体视觉流程如图 所示： 第 7 页 共 29 页 左 图 像 右 图 像预 处 理相 机 标 定立 体 匹 配三 维 重 建 图 双目立体视觉的处理流程 由于本文主要研究立体匹配的相关算法，因此不过多对：图像的预处理、相机标定以及三维重建等细节进行相关的研究讨论。 立体匹配（ stereo matching）：立体匹配作为立体视觉研究的重点，同时问题复杂多样，它主要是针对多幅图像完成在同一副图像的映射关系，这种映射关系通常是特 种提取之间的复杂关系，从而得到图像的视差图像。 因为现实中的大多图像信息都是三维的，然而摄像机只能将三维的图像信息投射到二维的空间，这就使得三维空间中复杂的信息都只能以单一的像素表现在二维图像中。 因此要完成正确、效率比较高的无歧义匹配难度相当的大。 所以就目前立体匹配研究的方向来看，无论哪一种立体匹配的算法，其步骤和内容都主要分为三个方面，首先是选取恰当的匹配特种方法，这一点尤为重要。 其二是找打这些特征的本质属性加以研究与分析，最后就是建立稳定且高效率的匹配方法。 现如今我们看到的主流的算法都是介于这三个不走展开 的，基于这种方法世界各地也提出了很多各具特色的算法匹配，但是由于立体匹配本身复杂多样性，同时涉及的问题复杂繁多，所以至今未有一整套成熟通用的算法去解决问题。 本文主要研究内容 本文主要针对计算机视觉中的双目立体视觉相关算法的研究与实现，并且对立体匹配算法进行了详细的讨论，重点研究了基于动态规划理论的立体匹配算法。 全文安排如下：第一章，主要介绍现代计算机视觉发展的概况以及双目立体 第 8 页 共 29 页 视觉匹配的一些概念。 第二章，主要概述如今常用的一些立体匹配的算法。 第三章，重点分析传统动态规划匹配算法的不足，并根 据不足提出改进的匹配算法即基于动态规划正交立体匹配算法。 第四章对全文进行总结与展望，并提出有待解决的问题。 第二章 立体匹配的常用算法 Scharstein 等提出立体匹配算法可以大致分为四个步骤 [2] ：第一步是初始代价匹配计算；第二步是对初始匹配代价的能量聚合值计算；第三步是视差的计算与优化；最后则是图像校正。 上述步骤的选取与匹配选用的方法有关，对于局部的固定窗口匹配主要是前三步骤即首先计算初始匹配代价，然后根据初始匹配代价选取 适当的块进行最小代价聚合值的筛选，选取最小代价聚合值下的视差值作为当前像素的视差值。 而自适应窗口块匹配算法则将前两部相结合，后续步骤相同。 局部算法具有计算负责度低、算法效率高等特点，它最突出的特点是对于初始匹配代价计算和对匹配代价聚合值的计算，这两个步骤尤为重要，方法是首先确定视差的搜索范围，每个视差值对应一个初始的匹配代价，然后根据这些初始代价利用分块的方法计算每个块中的灰度值之和即匹配代价聚合值，然后选取匹配代价聚合值最小的时候对应的视差作为当前像素的视差，尽管这种方法具有复杂度低于效率高等特点，但是 它仅仅考虑块内的约束条件，缺乏全局的约束，导致匹配的精度较低，误匹配的情况较大。 全局算法在匹配代价函数的基础上，结合根据特定的约束条件建立新的代价函数，从而构成全局能量函数，然后通过选用的特有的不同方法寻查找使得全局能量最小匹配聚合值。 其中， Graph Cut 算法和 Belief propagation 算法是目前公认的效果最好的算法 [3] ，可以获取高精度的稠密视差图，但是这两种算法的时间复杂度高，计算效率低，通常不能用于实时处理。 相对而言，动态规划算法具有计算效率高、匹配效果较好的特点，因此成为实时处理中最常用的算法之一。 视差理论 在研究人体视觉理论中，我们知道，人的双眼可以识别不同景深的物体。 人 第 9 页 共 29 页 的左眼和右眼在观察同一个物体的时候，由于双眼之间总有一定的距离，在观察同一个物体的时候，左眼与右眼总有一定的距离偏移（视差），但在双眼的聚焦点处偏移为零，比较直观的体会是在观察同一个物体的时候，通过分别单独遮挡住一只眼睛，可以发现所观察的事物有一定的视差。 外界事物通过光线反射到达视网膜，视网膜通过视觉神经传送到大脑皮层，经 过相应处理，形成立体的图像。 因此人可以区分不同景深的物体。 因此我们根据人双眼的视觉原理，可以仿照人眼的机制，可以使用多台摄像机或者同一个摄像机通过移动拍摄同一个物体的时候，由于视差距离的存在，可以根据摄像机成像模型以及摄像机之间的几何关系恢复出原有物体的三维信息。 立体匹配常用算法综述 由于采用平行摄像机（同一个摄像机），外极线是水平的，与图像扫描线重合，在进行匹配点搜索时可以大大简化搜索步骤。 然而，实际情况中很少采用平行配置，因此在进行视差匹配前首先需要进行外极线校准的预处理步骤。 鉴于非平 行性下的摄像机配置为题的复杂性，国内外主要针对平行摄像机下的立体匹配做了重点研究，立体匹配的主要的思路就是试图找到左右图像在同一幅图像上对应点。 就目前来看，算法的研究主要分为两类，第一类是是利用局部算法来选取能量函数，进行的算法匹配，典型的有：固定块匹配、滑动窗口匹配等等；另一中是针对整幅图像的一些约束条件，在第一种方法的基础上，利用全局能量函数最小的条件作为约束，从而得到更加准确的视差空间，其中比较典型的算法包括：常规动态规划立体匹配算法、 Belief Propagation 算法等。 表 列出了各类匹配 方法的典型算法。 算法分类 分类描述 具体算法 具体概述 局部匹配 利用如灰度值、平滑、相位约束等作为局部度量的准则。 在固定的块区域进行算法匹配。 固定块匹配 利用固定的窗口大小，使用整幅图像遍历扫描的方法获取左、右图像最小能量函数的视差值。 特征匹配 由于像素可靠性相对较低，特征匹配利用图像的如边缘特征进行算法 第 10 页 共 29 页 匹配。 网格匹配 主要是将图像划分为网格状，通过使用仿射或双线性模型插值的方法在算节点处的视差值的基础上，得到网格内的视差值的方法。 全局匹配 选取最小全局能量函数，获取视差空间。 动态规划 利用动态规划的方法，通过递归，根据外极线约束条件，搜索能量函数最小的最佳路径，从而获取视差值。 Graph Cuts 运用图形中的最大流的最小切割原理来估算视差值。 Belief Propagation 基于马尔可夫随机场构建全局函数，并采用置信传播算法进行函数最优化，计算视差值。 表 立体匹配典型算法 第三章 分层正交动态规划立体匹配算法 匹配代价与视差空间 我们假设：左图像、右图像分别用 LI 和 RI 表示，那么左视差 Ld 就表示左图像上的点 ( , )LI xy 和右图像上点 ( , )RLI x d y 为同一副图像在两幅图像上的映射即两点映射到图像上的同一个位置，可以通俗的讲，这中对应关系中零点的灰度值是相等的。 同样右视差表示 Rd 表示右图像上的点 ( , )RI xy 到左图像上点( , )LRI x d y 的一种映射关系。 那么我们规定如下 ( , , )xyd 为图像的匹配对，我们可以这样定义匹配代价( , , )Cx yd ，它表示的是左图像右图像映射到同一副图像上坐标 x、 y 对应的视差值 d 的一个三维图标信息。 规定如下： 第 11 页 共 29 页 ( , , ) ( ( , ) , ( , ) )LRC x y d f I x y I x d y 通常 函数 f 表示使用区域匹配。 下表 为常用区匹配的函数。 匹配函数 表述公式 NCC ,22,( ( , ) ) ( ( , ) )( ( , ) ) ( ( , ) )L L R RxyL L R RxyI x y I I x y II x y I I x y I     SSD 2, ( ( , ) ( , ) )LRxy I x y I x d j SAD , | ( , ) ( , ) |LRxy I x y I x d y Rank ,( ( , ) ( , ) )( , ) ( , ) ( , )LRxyk k kmnI x y I x d yI x y I m n I x y  表 那么匹配代价 ( , , )Cx yd 的矩阵值就构成了视差空间，图 ，它的三个维度，分别表示图像的高度 H 、宽度 W 以及视差的搜索范围  min max,dd（通常一幅图像的视差范围是不确定的，为了完整的提取出整个图像的视差值，通常我们将范围取的很大，一般 mind 从 0 开始到 maxd ，但是这样严重影响了算法的效率）。 x = 0x。