计算机视觉主要分为四个步骤：图像获取、图像校正、立体匹配和三维重建。其中，立体匹配的目的是在两个或多个对应同一场景的图像中找到匹配点，生成视差图。视差图可以通过一些简单的几何关系转换成深度图，用于三维重建。立体匹配是计算机视觉领域一个瓶颈问题，其结果的好坏直接影响着三维重建的效果。

立体匹配算法，主要分为特征匹配算法和区域匹配算法。特征匹配算法主要是提取图像特征进行匹配，生成视图。由于只提取局部特征，因此特征匹配算法速度快，但是得到的都是稀疏的视差图，而稀疏的视差图在很多应用中都不适用。

基于特征的匹配主要提取图像特征点进行匹配，例如边缘、轮廓、直线、角点等，具体步骤如图所示。由于这些特征点不受光照、尺度、旋转等变化影响，因此基于特征的匹配对于图像畸变、遮挡等具有一定的鲁棒性。但是它得到的视差图为稀疏视差图，如果需要像素的视差信息没能在稀疏视差图中得以体现，则需要利用已得到的特征点的视差通过拟合、插值、局部生长法等方法将稀疏视差图转成稠密视差图，来得到需要像素的视差信息。这种通过周围特征点插值计算得到的稠密视差图往往不可靠，丧失了大部分表面细节，使得生成的视差图不可靠。

区域匹配算法依据是否使用全局搜索可以分为全局匹配算法和局部匹配算法。全局匹配算法是基于像素的，通常将匹配运算构建在一个能量最小化的框架下，然后使用优化算法来最小化或最大化能量函数，得到视差图。比较经典的全局匹配算法有：置信度传播算法（belief propagation）、图割算法（graph cut）等。全局匹配算法得到的视差图较为准确，但运行时间长。局部匹配算法将像素代价聚集在一个支持窗中，然后选择与其相匹配的支持窗。然而，在这个过程中，选择合适的支持窗是一个困难的问题。

全局匹配将立体匹配关系用一个能量函数表示，如下式所示。能量函数由匹配代价和平滑代价组成，然后使用不同的优化算法来迭代地得到视差图。经典的全局算法有置信度传播算法（belief  propagation）、图割算法(graph  cuts)、动态规划算法（dynamic  programming）等。这些算法虽然能得到比较正确的视差图，但都需要通过多次迭代来获得最终结果，其计算耗时大，效率低。

2006 年 Yoon 提出了自适应权值算法，固定支持窗的大小，赋予支持窗中每个像素不同的权值。Yoon 算法的性能超过了一般的局部算法，甚至可以和全局算法相媲美，因此得到了很多的关注。

计算机视觉的目标是从摄像机得到的二维图像中提取三维信息，从而重建三维世界模型。在这个过程中，获得场景中某一物体的深度，即场景中物体各点相对于摄像机的距离，无疑成为了计算机视觉的研究重点。获得深度图的方法可分为被动测距和主动测距。被动测距是指视觉系统接受来自场景发射或反射的光能量，形成有关场景的二维图像，然后在这些二维图像的基础上恢复场景的深度信息。具体实现方法可以使用两个或多个相隔一定距离的照相机同时获取场景图像，也可使用一台照相机在不同空间位置上分别获取两幅或两幅以上的图像。主动测距与被动测距的主要区别在于视觉系统是否是通过增收自身发射的能量来测距，雷达测距系统、激光测距系统则属于主动测距。主动测距的系统投资巨大，成本太高，而被动测距方法简单，并且容易实施，从而得到了广泛的应用。利用被动测距的计算机视觉主要分为四个步骤，如图所示。

（1）图像获取。一般情况下，人类通过双眼来获得图像，双眼可近似为平行排列，在观察同一场景时，左眼获得左边的场景信息多一些，在左视网膜中的图像偏右；而右眼获得右边场景信息多一些，在右视网膜中的图像偏左。同一场景点在左视网膜上和右视网膜上的图像点位置差异即为视差，也是感知物体深度的重要信息。

计算机视觉的获取图像的原理与人眼相似，是通过不同位置上的相机来获得不同的图像，左摄像机拍摄的图像称为左图像，右摄像机拍摄的图像称为右图像。左图像得到左边的场景信息多一些，右图像得到右边场景的信息多一些，

（2）   图像校准。在图像获取过程中，有许多因素会导致图像失真，如成像系统的象差、畸变、带宽有限等造成的图像失真；由于成像器件拍摄姿态和扫描非线性引起的图像几何失真；由于运动模糊、辐射失真、引入噪声等造成的图像失真。

（3）   立体匹配。在两幅或多幅不同位置下拍摄的且对应同一场景的图像中，建立匹配基元之间关系的过程称为立体匹配。例如，在双目立体匹配中，匹配基元选择像素，然后获得对应于同一个场景的两个图像中两个匹配像素的位置差别，即视差。并将视差按比例转换到0－255 之间，以灰度图的形式显示出来，即为视差图。

（4）三维重建。根据立体匹配得到的像素的视差，如果已知照相机的内外参数，则根据摄像机几何关系得到得到场景中物体的深度信息，进而得到场景中物体的三维坐标。

局部匹配算法主要有自适应支持窗算法（windowwith adaptive size）、自适应权值算法（adaptivesuppot-weight）和多窗口算法（multiple window）。自适应支持窗算法假设支持窗中的像素的视差值是一样的，然后在目标图像的搜索区域中寻找与参考图像支持窗差异最小的支持窗，两个支持窗中的中心像素即为匹配像素，图1.11 中左图像为参考图像，右图像为目标图像，和分别为左图像和右图像支持窗中的中心像素，由于采用水平极线校正的约束，因此，搜索区域为一维，即可能匹配像素的纵坐标y 相同。自适应权值的算法与自适应支持窗的算法不同，它用权值来代表支持窗中的像素对中心像素匹配影响的大小，权值越大，影响越大。多窗口匹配算法，主要是根据一定准则，在事先指定的多个窗口中选择最佳的窗口进行匹配计算。

在国际方面，将现存的立体匹配算法进行了分类和总结，将算法分成四个步骤：匹配代价计算、代价聚集、视差计算、视差精化，但并不是所有匹配算法中都包括这四个步骤，需要哪一步，要根据具体情况而定。还提出了一个专供稠密视差图定量测试的平台（www.middlebury.edu/stereo），得到了广泛的应用。下面将通过这四个步骤分别对国外近些年的立体匹配算法进行总结。

（1）匹配代价计算。若令参考图像中任一像素点为 p ，目标图像中可能匹配像素点为q ，d 为视差范围。最普通的匹配算法有灰度平方差异（squared intensity differences）和灰度绝对值差异（absoluteintensity differences）。

还有一些匹配代价对相机偏移、噪声和光照鲁棒，如基于梯度的一些测量rank 变换和census变换等。rank 变换大致过程为以待匹配像素为中心作一个矩形窗口（rank 窗口），然后统计 rank 窗口中灰度值比中心像素灰度值小的像素的数目，并用这个数代替原来中心像素的灰度值，依次计算，直到被转换成一个整数矩阵，这个整数矩阵称为rank 图像。图 1.12 为 rank 变换的一个示例，红色圈内为待匹配元素，rank 窗口大小为3*3 ，ran