摘要动态规划是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量。 

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

毕业论文关键词：动态规划；立体匹配；匹配代价；OPENCV；全局匹配

毕业设计说明书（论文）外文摘要

Title    The stero matching based on dynampic programming

Abstract Dynampic method is widely used in subjects，such as Maths，Computer science and economics，the method is using the way that decompose the original problem into serval simple subproblem. In fact,If we want to solve the problem,we need to solve the subproblem first，in order to get the answer to the original problem.Subproblems are usually the same，so we only need to resolve the same subproblem once，and it can reduce our calculation.

   The dynamic planning thought applied to stero  matching is using some constraints to reduce complexity.This passage mainly used  Left-right consistency constraint,by using scanning line to calculate from to left the matching cost,find the smallest global energy as a function of the scanning line by the end of,then from right to left to get the  parallax of the whole way.The energy function means the matching cost and occlusion cost.

   Keywords :Dynampic planning,stero matching ,matching cost,opencv,global matching

目 录

1 绪论 1

1.1 论文选题依据 1

1.2 计算机视觉的五大研究内容 2

1.3 计算机视觉与相关学科的关系 2

1.4 Marr视觉计算理论 3

1.5 本文的主要内容安排 5

2. 立体匹配算法的相关概念 5

2.1   立体视觉匹配原理 5

2.2  局部立体匹配算法 6

2.3  基于全局的约束算法 7

2.4  立体匹配的研究重点和发展的相关趋势 8

3. 立体匹配代价计算及视差图 9

3.1  影响立体匹配的几个因素 9

3.2 匹配代价计算 13

3.3  OPENCV3种求立体匹配求视差图算法总结 15

4. 动态规划的基本知识和算法 19

4.1 动态规划思想