基于动态划理论的立体匹配算法研究毕业论文.doc

《基于动态划理论的立体匹配算法研究毕业论文.doc》由会员分享，可在线阅读，更多相关《基于动态划理论的立体匹配算法研究毕业论文.doc（29页珍藏版）》请在三一办公上搜索。

1、南京大学本 科 生 毕 业 论 文 （申请学士学位）论文题目 基于动态规划理论的立体匹配算法研究论文题目基于动态规划理论的立体匹配算法研究Title in English（英文题目）The research of Stereo Matching based on Dynamic Programming 姓名：张洋洋南京大学金陵学院信息管理系 Dept. of Information Management，Jinling College, NJU毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知

2、，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名：

3、 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存

4、和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日指导教师评阅书指导教师评价：一、撰写（设计）过程1、学生在论文（设计）过程中的治学态度、工作精神 优 良 中 及格 不及格2、学生掌握专业知识、技能的扎实程度 优 良 中 及格 不及格3、学生综合运用所学知识和专业技能分析和解决问题的能力 优 良 中 及格 不及格4、研究方法的科学性；技术线路的可行性；设计方案的合理性 优 良 中 及格 不及格5、完成毕业论文（设计）期间的出勤情况 优 良 中 及格 不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格

5、2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格建议成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）指导教师： （签名） 单位： （盖章）年 月 日评阅教师评阅书评阅教师评价：一、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良

6、 中 及格 不及格二、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格建议成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）评阅教师： （签名） 单位： （盖章）年 月 日教研室（或答辩小组）及教学系意见教研室（或答辩小组）评价：一、答辩过程1、毕业论文（设计）的基本要点和见解的叙述情况 优 良 中 及格 不及格2、对答辩问题的反应、理解、表达情况 优 良 中 及格 不及格3、学生答辩过程中的精神状态 优 良

7、中 及格 不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格评定成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）教研室主任（或答辩小组组长）： （签名）年 月 日教学系意见：系主任： （签名）年 月 日南京大学金陵学院本科生毕业论文（

8、设计）中文摘要毕业论文题目： 基于动态规划理论的立体匹配算法研究信工院系电子信息科学与技术专业08级本科生姓名：张洋洋指导教师（姓名）： 李扬 随着计算机视觉的发展，双目立体视觉已经成为近期研究的重点，它主要是通过模拟人眼立体成像的机制，利用两台摄像机通过不同位置成像，然后通过后续的处理，主要包括摄像机标定，立体匹配，以即最后3-D重建最终产生三维的图像。然而立体视觉的重点是立体匹配，因此本文对立体匹配做重点的讨论与研究。 对于立体匹配，现如今已经有许多不同的研究成果，包括分为不同流派的研究思路，主要有针对区域的匹配算法和全局的匹配算法的研究并且都取得了很大的进展，其中针对全局路径的立体匹配要

9、优于块匹配，最著名的是基于动态规划的匹配算法，这种传统的匹配算法，仅仅引入单调顺序约束，缺乏全局对于扫描线约束的限制，使得匹配后的视差图像存在大量带状误匹配的情况，针对此现象，本文提出了基于动态规划理论的立体匹配思想，通过加入行扫描线之间的约束条件和列扫描，能够较好的完成图像的匹配与视差的还原。南京大学金陵学院本科生毕业论文（设计）英文摘要 With the development of computer vision, binocular stereo vision is one of the most important area of researching. It mainly dep

10、end on simulating the system of the eyes of human beings, making use of two cameras to acquire two different pictures in diverse location and then dealing with the special procedure. After that the amount of the date of this picture would be disposed, including: camera calibration, stereo matching a

11、nd 3-D reconstruction etc. While the stereo matching is the key module of the stereo vision, so this essay we research the stereo matching as the keynote. The study about the stereo matching during the world acquire lots of research achievements, since. Divided into different schools of thought, mai

12、nly for regional matching and global matching algorithm research,and the global matching of dynamic programming is better than the regional matching. This algorithm only introduce the monotone sequence constraint and ignore the constraint between scanning lines,so the result based on the traditional

13、 dynamic programming matching exist large number of articles. In order to overcoming this phenomenon, this essay present the theory of dynamic programming based on the stereo matching-adding the constraint of the among scanning lines and acquire better result.目 录第1章 绪论 .-1 - 1.1 计算机视觉的发展.- 1 - 1.2 双

14、目立体视觉概述.- 2 - 1.3 本文主要研究内容.- 3 -第2章 常用的一些立体匹配的算法.-3- 2.1 视差理论.-4- 2.2 立体匹配常用算法综述.-4-第3章 分层正交动态划匹配算法.-4- 3.1 匹配代价与视差空间.-5- 3.1.1 匹配代价计算.-6- 3.1.2 固定窗口块匹配过程.-7- 3.1.3 滑动窗口匹配.-9- 3.2 动态规划立体匹配.-10- 3.3 分层正交动态规划立体匹配算法.-12- 3.3.1 水平方向最优路径.-12- 3.3.2 水平双向能量函数.-13- 3.3.3 垂直方向最优路径.-13- 第4章 总结与展望第一章 绪论1.1计算机视

15、觉的发展概况 “计算机视觉领域的最突出特点是其多样性和不完善性。这一领域的先驱可追溯到更早的时候，但是直到20世纪70年代后期，当计算机的性能提高到足以处理诸如图像这样的大规模数据时，计算机视觉才得到了正式的关注和发展。然而这些发展往往起源于其他不同领域的需要，因而何谓“计算机视觉问题”始终没有得到正式定义，很自然地，“计算机视觉问题”应当被如何解决也没有成型的公式”。 计算机视觉研究主要有以下几个领域的研究方向相互渗透：人工智能、物理（主要是可见光与红外的成像）、神经生物学。 除了上面提到的领域，很多研究课题同样可被当作纯粹的数学问题。例如，计算机视觉中的很多问题，其理论基础便是统计学，最优

16、化理论以及几何学。如何使既有方法通过各种软硬件实现，或说如何对这些方法加以修改，而使之获得合理的执行速度而又不损失足够精度，是现今电脑视觉领域的主要课题。 当前，随着计算机科学、信号处理、以及人工智能研究的更一步深入，计算机视觉技术越来越多的得到人们的重视与研究，此外计算机视觉的应用也更加的广泛，设计到军事、医疗等方方面面。 如今对于计算机双目立体视觉的研究比较热，也取得了很多进展，本文着重对双目立体视觉中的算法进行高论分析。1.2计算机双目立体视觉近年来计算机视觉研究的重点与热点之一是双目立体视觉。它通过仿生学的原理模拟人类双眼成像的机制原理，利用两个摄像机在不同角度拍的摄同一景物或者物体，

17、通过一个参考空间来计算两幅拍摄图像中的视差，进而获得对应点的三维坐标值信息。 为了便于研究，完整的双目立体视觉通常会被按照不同的步骤按照既定的流程来进行相关的研究，它主要流程是首先是左右图像信息获取，然后根据图像信息进行相关的预处理方便后续进行分析与研究，接着对预处理后的数据进行摄像机标定的过程，随后就是最重要也是最复杂的立体匹配过程，最后完成三维重建，其中立体匹配技术是立体视觉中的重点环节。整个双目立体视觉流程如图1.1所示：图1.1 双目立体视觉的处理流程 由于本文主要研究立体匹配的相关算法，因此不过多对：图像的预处理、相机标定以及三维重建等细节进行相关的研究讨论。立体匹配（stereo

18、matching）：立体匹配作为立体视觉研究的重点，同时问题复杂多样，它主要是针对多幅图像完成在同一副图像的映射关系，这种映射关系通常是特种提取之间的复杂关系，从而得到图像的视差图像。因为现实中的大多图像信息都是三维的，然而摄像机只能将三维的图像信息投射到二维的空间，这就使得三维空间中复杂的信息都只能以单一的像素表现在二维图像中。因此要完成正确、效率比较高的无歧义匹配难度相当的大。所以就目前立体匹配研究的方向来看，无论哪一种立体匹配的算法，其步骤和内容都主要分为三个方面，首先是选取恰当的匹配特种方法，这一点尤为重要。其二是找打这些特征的本质属性加以研究与分析，最后就是建立稳定且高效率的匹配方法

19、。现如今我们看到的主流的算法都是介于这三个不走展开的，基于这种方法世界各地也提出了很多各具特色的算法匹配，但是由于立体匹配本身复杂多样性，同时涉及的问题复杂繁多，所以至今未有一整套成熟通用的算法去解决问题。1.3本文主要研究内容 本文主要针对计算机视觉中的双目立体视觉相关算法的研究与实现，并且对立体匹配算法进行了详细的讨论，重点研究了基于动态规划理论的立体匹配算法。全文安排如下：第一章，主要介绍现代计算机视觉发展的概况以及双目立体视觉匹配的一些概念。第二章，主要概述如今常用的一些立体匹配的算法。第三章，重点分析传统动态规划匹配算法的不足，并根据不足提出改进的匹配算法即基于动态规划正交立体匹配算

20、法。第四章对全文进行总结与展望，并提出有待解决的问题。第二章 立体匹配的常用算法Scharstein等提出立体匹配算法可以大致分为四个步骤：第一步是初始代价匹配计算；第二步是对初始匹配代价的能量聚合值计算；第三步是视差的计算与优化；最后则是图像校正。上述步骤的选取与匹配选用的方法有关，对于局部的固定窗口匹配主要是前三步骤即首先计算初始匹配代价，然后根据初始匹配代价选取适当的块进行最小代价聚合值的筛选，选取最小代价聚合值下的视差值作为当前像素的视差值。而自适应窗口块匹配算法则将前两部相结合，后续步骤相同。局部算法具有计算负责度低、算法效率高等特点，它最突出的特点是对于初始匹配代价计算和对匹配代价

21、聚合值的计算，这两个步骤尤为重要，方法是首先确定视差的搜索范围，每个视差值对应一个初始的匹配代价，然后根据这些初始代价利用分块的方法计算每个块中的灰度值之和即匹配代价聚合值，然后选取匹配代价聚合值最小的时候对应的视差作为当前像素的视差，尽管这种方法具有复杂度低于效率高等特点，但是它仅仅考虑块内的约束条件，缺乏全局的约束，导致匹配的精度较低，误匹配的情况较大。全局算法在匹配代价函数的基础上，结合根据特定的约束条件建立新的代价函数，从而构成全局能量函数，然后通过选用的特有的不同方法寻查找使得全局能量最小匹配聚合值。其中，Graph Cut算法和Belief propagation算法是目前公认的效

22、果最好的算法，可以获取高精度的稠密视差图，但是这两种算法的时间复杂度高，计算效率低，通常不能用于实时处理。相对而言，动态规划算法具有计算效率高、匹配效果较好的特点，因此成为实时处理中最常用的算法之一。2.1视差理论 在研究人体视觉理论中，我们知道，人的双眼可以识别不同景深的物体。人的左眼和右眼在观察同一个物体的时候，由于双眼之间总有一定的距离，在观察同一个物体的时候，左眼与右眼总有一定的距离偏移（视差），但在双眼的聚焦点处偏移为零，比较直观的体会是在观察同一个物体的时候，通过分别单独遮挡住一只眼睛，可以发现所观察的事物有一定的视差。外界事物通过光线反射到达视网膜，视网膜通过视觉神经传送到大脑皮

23、层，经过相应处理，形成立体的图像。因此人可以区分不同景深的物体。 因此我们根据人双眼的视觉原理，可以仿照人眼的机制，可以使用多台摄像机或者同一个摄像机通过移动拍摄同一个物体的时候，由于视差距离的存在，可以根据摄像机成像模型以及摄像机之间的几何关系恢复出原有物体的三维信息。2.2立体匹配常用算法综述由于采用平行摄像机（同一个摄像机），外极线是水平的，与图像扫描线重合，在进行匹配点搜索时可以大大简化搜索步骤。然而，实际情况中很少采用平行配置，因此在进行视差匹配前首先需要进行外极线校准的预处理步骤。鉴于非平行性下的摄像机配置为题的复杂性，国内外主要针对平行摄像机下的立体匹配做了重点研究，立体匹配的主

24、要的思路就是试图找到左右图像在同一幅图像上对应点。就目前来看，算法的研究主要分为两类，第一类是是利用局部算法来选取能量函数，进行的算法匹配，典型的有：固定块匹配、滑动窗口匹配等等；另一中是针对整幅图像的一些约束条件，在第一种方法的基础上，利用全局能量函数最小的条件作为约束，从而得到更加准确的视差空间，其中比较典型的算法包括：常规动态规划立体匹配算法、Belief Propagation算法等。表2.1列出了各类匹配方法的典型算法。算法分类分类描述具体算法具体概述局部匹配利用如灰度值、平滑、相位约束等作为局部度量的准则。在固定的块区域进行算法匹配。固定块匹配利用固定的窗口大小，使用整幅图像遍历扫

25、描的方法获取左、右图像最小能量函数的视差值。特征匹配由于像素可靠性相对较低，特征匹配利用图像的如边缘特征进行算法匹配。网格匹配主要是将图像划分为网格状，通过使用仿射或双线性模型插值的方法在算节点处的视差值的基础上，得到网格内的视差值的方法。全局匹配选取最小全局能量函数，获取视差空间。动态规划利用动态规划的方法，通过递归，根据外极线约束条件，搜索能量函数最小的最佳路径，从而获取视差值。Graph Cuts运用图形中的最大流的最小切割原理来估算视差值。Belief Propagation基于马尔可夫随机场构建全局函数，并采用置信传播算法进行函数最优化，计算视差值。表2.1 立体匹配典型算法第三章

26、分层正交动态规划立体匹配算法3.1匹配代价与视差空间 我们假设：左图像、右图像分别用和表示，那么左视差就表示左图像上的点和右图像上点为同一副图像在两幅图像上的映射即两点映射到图像上的同一个位置，可以通俗的讲，这中对应关系中零点的灰度值是相等的。同样右视差表示表示右图像上的点到左图像上点的一种映射关系。 那么我们规定如下为图像的匹配对，我们可以这样定义匹配代价，它表示的是左图像右图像映射到同一副图像上坐标x、y对应的视差值d的一个三维图标信息。规定如下：通常函数表示使用区域匹配。下表3.1为常用区匹配的函数。匹配函数表述公式NCCSSDSADRank表3.1 那么匹配代价的矩阵值就构成了视差空间

27、，图3.1，它的三个维度，分别表示图像的高度、宽度以及视差的搜索范围（通常一幅图像的视差范围是不确定的，为了完整的提取出整个图像的视差值，通常我们将范围取的很大，一般从0开始到，但是这样严重影响了算法的效率）。图3.1 视差空间3.1.1匹配代价计算通常我们使用左右图像对应像素灰度值之差的平法即和差的绝对值来计算初始匹配代价。鉴于算法效率，考虑到时间复杂度，我们采用用于计算匹配代价初始值。由于对于要处理的图像通常是彩色图像，它包括、三种颜色分量，所以的计算公式如下： （3-1）说明：、分别代表图像像素的红、绿、蓝三个颜色分量。对于整个图像所有像素以及对应视差值就构成了初始视差空间。3.1.2固

28、定窗口块匹配过程首先块匹配的基本步骤和方法如下，第一步先进行匹配代价的计算，然后第二步是计算匹配代价聚合（固定窗口内窗口代价之和），最后完成对视差的一些优化，使得图像显示效果更好。A、 匹配代价计算因为一幅图像上视差的范围我们是不确定的，所以这里我们在开始计算的时候往往选取很大的视差值作为最大视差值。从开始到依次计算，我们得到的左右图像的视差值以及相应的、的坐标信息就是匹配代价。具体方法是首先获取左图像和右图像的坐标以及灰度值信息，然后从到遍历，运用公式计算出个视差空间B、 匹配代价聚和值计算以33固定窗口块匹配为例。在前期匹配代价的基础上，以当前右视差的基础上通该点周围9个点（33窗口）计算

29、匹配代价之和（即为匹配代价聚合值），选取个视差空间中能够使当前窗口代价之和最小的点的视差值作为当前该点的视差值。C、视差图像 将整个图像完整的、的坐标信息以及对应点最小的匹配代价聚和值时对应的视差用画图显示。D、实验结果图像 左图像 右图像 33固定窗口匹配 55固定窗口匹配 77固定窗口匹配 真实视差图像C、 结果分析局部算法的重点是关于匹配代价聚合值的计算，局部算法具有很多的优点，它的计算复杂度低，计算速度快，但同时它还有很大的缺点，例如缺乏整体性约束，它的匹配精度较低，会造成误匹配。从上面实验结果中我们不难看到：窗口尺寸选取的不同会对实验结果造成很大不同，当窗口选取的较小时，图像中会出现

30、许多的噪声的小斑点，而且平滑的效果比较差，但是物体的轮廓是最清晰的；当窗口尺寸增大后（一定的限度）噪点会大幅度下降，使得平滑的效果也比较理想，但是物体的轮廓也会逐渐的模糊。所以匹配窗口的选择非常重要，窗口尺寸的大小会直接影响我们整个视差图的质量。3.1.3滑动窗口块匹配滑动窗口算法的实现，以33 滑动窗口为例，下图所示，以当前像素点（黑色像素点）为中心构造33 窗口，再分别以窗口中的每个像素点为中心滑动窗口并计算此窗口的均值，最后选择9个滑动窗口中最小的均值作为当前像素点的值。为了提高速度，33滑动窗口滤波器的实现可以分为两步：第一步使用33固定窗口滤波器；第二步使用33 最小值查找滤波器。滑

31、动窗口示意图33滑动窗口匹配 55滑动窗口匹配左图像 右图像 77滑动窗口匹配 真实视差图像结果分析：实验使用的左图像、右图像作为测试图像，对其实行滑动窗口块匹配算法，匹配效果如图上面所示。从上面的图像可知，和固定窗口匹配一样窗口的大小选择同样影响视差图像的质量，当窗口尺寸较小时，误匹配的噪声斑点块小而且密集，当尺寸选择较大的时候效果比较理想，边缘信息也相对差一点。与固定窗口块匹配效果相比，滑动窗口算法所得视差图的边缘信息更为精确，尤其是窗口较大时，有效降低了匹配算法对窗口尺寸的敏感度。3.2动态规划立体匹配A、动态规划理论 如果把动态规划的求解过程看成一个工厂的生产线，阶段就是生产某个商品的

32、不同的环节，状态就是工件当前的形态，决策就是对工件的操作。显然不同阶段是对产品的一个前面各个状态的小结，有一个个的小结构成了最终的整个生产线。每个状态间又有关联（下一个状态是由上一个状态做了某个决策后产生的）。因此我们可以知道，动态规划算法是一种解决降低全局优化问题的算法，主要的思想是将整个问题分解成相似的小问题，然后利用递归的方法去解决复杂的问题。 它的基本思路如下： 将整个复杂的问题划分为类似的最小的问题去解决，在求解整个复杂问题是分阶段进行，通过组合子问题去解决整个问题。具体流程是： 首先通过抽象描述最优解的结构，然后利用递归的方法去定义这种结构方法，最后就是从下到上计算出最优解的值。B

33、、传统动态规划立体匹配过程 动态规划思想应用到立体匹配过程主要思路是，通过立体匹配的一些约束来降低复杂度，本文主要使用左右一致性约束（左右一致性约束是指当左图像上的具体某一点通过搜索匹配到右图像上某一点时，那么右图像上对应的该点也可以通过搜索匹配到左图像上的改点上来），通过行扫描线，自左向右计算累积的匹配代价，查找最小全局能量函数作为该扫描线路经的终点，然后从右往左寻找出整条路经的视差，此处的能量函数是指匹配代价和遮挡代价。C、实验结果图像 左图像 右图像 动态规划算立体匹配的视差图D、实验结果分析 从动态规划立体匹配的视差图来看，基于传统动态规划算法实现的立体匹配过程，基本上可以较好的完成整

34、个视差图像的提取，但是。3.3 分层正交动态规划立体匹配算法 针对传统动态规划立体匹配存在由于仅采用行单独的行扫描线来寻找最小的全局能量函数，缺乏全局整体性约束，使得实验后的图像存在横向条纹，存在一定的误匹配的现象，并且当匹配图像中出现垂直方向图形比较细小时候，这种算法的误匹配概率明显上升，因此我们提出基于动态规划的分层正交立体匹配的算法思想。 该思想主要是就对通过固定利用二维平面进行第一轮扫描，并且每次处理一行扫描线，并根据动态规划的方法搜索出最佳的全局路径，第二轮在第一轮的基础上，通过垂直方向进行路径扫描。3.3.1 水平方向的最优路径 由于模型对处理视差跳变有良好的效果，我们在以行为单位

35、的每行匹配代价聚合值的基础上加上模型函数，固定值对视差空间图中的平面进查找行路径。模型函数定义如下：我们引出公式如下： 其中函数代表匹配代价聚合值。3.3.2水平双向能量函数 由于传统动态规划的方法是通过行扫描线，自左向右计算累积的匹配代价，查找最小全局能量函数作为该扫描线路经的终点，然后从右往左寻找出整条路经的视差，并且由于第二次处理是垂直方向的，所有引入水平双向的能量函数。给出公式如下：说明：矩阵为从左到右累积匹配代价，同理表示从右到左的累积匹配代价矩阵，而表示当前像素处最小的累积匹配代价。3.3.3垂直方向最优路径 考虑到水平方向缺乏相关性约束，单纯进行的匹配，使得当前行扫描对后续行扫描

36、进行匹配有着严重的影响，有一定的误匹配。结果导致带了明显的带状条纹。为解决此问题，我们根据行接的相关约束性，提出垂直方向的最优路径。类比于水平方向的最优路径，我们固定，利用二维平面进行处理，进行列的最优化查找公式如下：说明：表示从左到右的累积匹配代价加上从右到左的累积匹配代价减去匹配代价聚合值。通过分层正交动态规划算法，经过水平与垂直方向两轮扫描后，就图像进行了算法的实验，结果如下：如图 左图像 右图像 第一轮水平方向扫描 第二轮垂直方向扫描结果分析：经过第一轮水平方向的扫描可以看出视差图已呈现，但是由于缺少行间的约束，存在误匹配，行间带状条纹明显，通过引入第二轮垂直方向的扫描之后带状条纹基本

37、消失，而且视差层次清晰，边缘也格外分明，所有本文提出的基于动态规划的正交立体匹配算法较原有传统动态规划立体匹配算法对于视差的提取具有较好的效果，是可行的。第4章 总结与展望本文主要针对现有的立体匹配算法，进行分析与总结，包括优缺点的分析，包括区域匹配和全局的匹配，并重点分析了全局算法中的动态规划算法，针对传统动态规划立体匹配存在由于仅采用行单独的行扫描线来寻找最小的全局能量函数，缺乏全局整体性约束，使得实验后的图像存在横向条纹，存在一定的误匹配的现象，并且当匹配图像中出现垂直方向图形比较细小时候，这种算法的误匹配概率明显上升，因此我们提出基于动态规划的分层正交立体匹配的算法思想。 该思想主要是

38、就对通过固定利用二维平面进行第一轮扫描，并且每次处理一行扫描线，并根据动态规划的方法搜索出最佳的全局路径，第二轮在第一轮的基础上，通过垂直方向平面进行路径扫描，此方法能够较好的对水平带状条纹进行过滤，并且能够达到较好的处理效果。 但是由于匹配算法的复杂性，针对遮挡代价等没有做较好的处理，同时算法效率也不是很高，没有做好算法复杂度的优化，并且虽然本文提出的方法较传统方法有明显的优点，但是还是存在少量的带状条纹产生。如何彻底的消除这些误匹配，还有待于进一步研究。参考文献1 维基百科 zh.wikipedia.org/wiki/计算机视觉2 Scharstein D. and Szeliski R., A taxonomy and evaluation of dense two-frame stereo correspondence algorithmsJ, IJCV, 2002, 47(1-3): 742.3