from：https://blog.csdn.net/wintergeng/article/details/51049596

一、概念

        立体匹配算法主要是通过建立一个能量代价函数，通过此能量代价函数最小化来估计像素点视差值。立体匹配算法的实质就是一个最优化求解问题，通过建立合理的能量函数，增加一些约束，采用最优化理论的方法进行方程求解，这也是所有的病态问题求解方法。

二、主要立体匹配算法分类

1）根据采用图像表示的基元不同，立体匹配算法分为：

       A、区域立体匹配算法（可获取稠密视差图。缺点：受图像的仿射畸变和辐射畸变影响较大；像素点约束窗口的大小与形状选择比较困难，选择过大，在深度不连续处，视差图中会出现过度平滑现象；选择过小，对像素点的约束比较少，图像信息没有得到充分利用，容易产生误匹配。）

       B、基于特征的立体匹配算法（可获得稀疏的视差图，经差值估计可获得稠密视差图。可提取点、线、面等局部特征，也可提取多边形和图像结构等全局特征。缺点：特征提取易受遮挡、光线、重复纹理等影响较大；差值估计计算量大）

       C、基于相位立体匹配算法（假定在图像对应点中，其频率范围内，其局部相位是相等的，在频率范围内进行视差估计）

2）依据采用最优化理论方法的不同，立体匹配算法可以分为：

       A、局部的立体匹配算法

       B、全局的立体匹配算法

三、匹配基元（match primitive）

目前匹配算法中所采用的匹配基元可以分成两大类：

1）在所有图象像素点上抽取量测描述子

      A、像素灰度值（最简单、直接，但必须在同一光照条件下获得）

      B、局部区域灰度函数（主要是利用求得在各种大小不同窗口中灰度分布的导数信息，描述像素点周围的结构矢量。）

      C、卷积图象符号（利用各种大小算子与图象进行卷积，用灰度梯度局部极大值或极小值作为特征信息，描述整个图像）

2）图像特征

      A、过零点

      B、边缘（由于边缘是图像特征位置的标志，对灰度值的变化不敏感，边缘是图像匹配的重要特征和描述子）

      C、角点（虽然其没有明确的数学定义，但大家普遍认为角点，即二维图像亮度变化剧烈的点或边缘曲线上曲率极值点）

------------------------------------------------------------------基元-----------------------------------------------------------------------------------------

1. 立体视觉匹配基元：匹配基元是用以进行立体匹配的图像特征，匹配基元的选择，要考虑基元的稳定性、敏感性、可行性和能否表示图像。

   • 点：利用图像的局部特征信息作为匹配基元，表示一个像素，如像素灰度值，角点，边缘，卷积等。

     

   • 块：局部区域内所有像素的灰度、亮度特征值，对区域内所有像素进行变化，如卷积、梯度变换和Censes变换等。

     

   • 线：一般是像素灰度信息发生急剧变化的像素点集，最能体现边缘特征。

     检测边缘的算子如Sobel算子、Canny算子、Log算子和Prewitt算子等。

     

------------------------------------------------------------------基元end------------------------------------------------------------------------------------------

四、区域匹配算法

        基本原理是给定在一幅图像上的某一点，选取该像素点邻域内的一个子窗口，在另一幅图像中的一个区域内，根据某种相似性判断依据，寻找与子窗口图像最为相似的子图，而其匹配的子图中对应的像素点就为该像素的匹配点。

        一般单纯的区域匹配都遇到如下限制：

       1）针对弱纹理或存在重复纹理的区域，匹配结果不好

       2）该算法不适应于深度变化剧烈的场景

       3）对光照、对比度和噪声比较敏感

       4）子窗体的大小很难选择

五、特征匹配算法

        特征的匹配算法，主要是基于几何特征信息（边缘、线、轮廓、兴趣点、角点和几何基元等），针对几何特征点进行视差估计，所以先要提取图像的特征点，尽而利用这些特征点的视差值信息来重建三维空间场景。

        匹配所需要的主要步骤：图像预处理、提取特征、特征点的匹配获取稀疏视差图，如果想得到稠密的视差图，需要采用插值的方法。

六、全局匹配算法

        全局立体匹配算法主要是采用了全局的优化理论方法估计视差，建立全局能量函数，通过最小化全局能量函数得到最优视差值。

        全局匹配算法得到的结果比较准确，但是其运行时间比较长，不适合实时运行。主要的算法有图割（graph cuts）、信念传播（belief propagation）、动态规划等算法。

七、局部匹配算法（个人觉得跟区域匹配类似，角度不同而已）

        主要是采用局部优化方法进行视差值估计，局部立体匹配算法有 SAD，SSD 等算法，与全局立体匹配算法一样，也是通过能量最小化方法进行视差估计，但是，在能量函数中，只有数据项，而没有平滑项。

       主要分为三类：自适应窗体立体匹配算法、自适应权值的立体匹配算法和多窗体立体匹配算法。

八、立体匹配约束

1）极线约束
2）唯一性约束

3）视差连续性约束

4）顺序一致性约束

5）相似性约束

----------------------------------------------------------------匹配约束--------------------------------------------------------------------------------------

1. 约束准则具有缩小匹配搜索的范围，降低误匹配，同时提高匹配效率的功能。

   • 极线约束：

     如图所示，三维空间的一个映射点，其匹配点必定在另一图像的极线上，理想情况下，匹配点对位于同一水平线上即坐标y值相同。故只需在对应的水平线上搜素匹配点，大大提高了匹配效率。

     

   • 唯一性约束：

     三维空间点至多只一个图像上的映射点（遮挡则没有映射点），匹配时左右图像上只有唯一一个匹配点。

     

   • 连续性约束：

     三维空间中物体表面是光滑的，匹配得到的视差图大部分情况下是连续且光滑变化的。一般使用较小的视差梯度降低匹配的搜索范围和待匹配点的数量以提高匹配速度。

     

   • 相似性约束：

     三维空间中的物体在不同视角下投影产生的匹配基元（点、块、线）必须要有相同或相似的属性。由于光照等因素的影响，相似性约束具有局限性。

     

   • 顺序一致性约束：

     三维空间中物体上的点的位置信息在映射到两幅图像上的位置顺序不会改变。这是不透明物体表面投影的几何学必然性。

     

   • 平滑性约束：

     假设三维空间中物体表面是平滑的，则视差图上除物体边界位置会有大的视差波动以外，其他位置上匹配视差的变化很小。

     

   • 左右一致性约束：

     如图所示，参考图上像素点p点在匹配图上的点是q，则参考图上像素点q在匹配图上是p。如果两次搜索的结果不对应，则改点不可靠。常用于遮挡区域的检测。

     

   • 视差范围约束：

     两台摄像机之间具有一定的距离，在沿极线搜索时，搜索的范围应小于一定的阈值。视差范围约束限制了搜索的范围。

     

-----------------------------------------------------------------匹配约束end----------------------------------------------------------------------------------

九、相似性判断标准

1）像素点灰度差的平方和，即 SSD

2）像素点灰度差的绝对值和，即 SAD

3）归一化交叉相关，简称 NCC

4） 零均值交叉相关，即 ZNCC

5）Moravec 非归一化交叉相关，即 MNCC

6） Kolmogorov-Smirnov 距离，即 KSD

7）Jeffrey 散度

8）Rank 变换（是以窗口内灰度值小于中心像素灰度值的像素个数来代替中心像素的灰度值）

9）Census 变换（是根据窗口内中心像素灰度与其余像素灰度值的大小关系得一串位码，位码长度等于窗口内像素个数减一）

各类代码实现参考：https://blog.csdn.net/liyingjiang22/article/details/53156331

十、评价参数

        立体匹配算法是一个病态问题，一般通过建立能量函数，利用最小化能量函数，和一些约束条件，采用最优化理论方法进行求解方程。

        公认的定量评价参数有：均方根误差(Root-mean-squared)和误匹配率(percentage of bad matching pixels)