双目视觉（三）立体匹配算法

系列文章：

1. 双目视觉（一）双目视觉系统
2. 双目视觉（二）双目匹配的困难和评判标准
3. 双目视觉（三）立体匹配算法
4. 双目视觉（四）匹配代价
5. 双目视觉（五）立体匹配算法之动态规划全局匹配
6. 双目视觉（六）U-V视差
7. 【项目实战】利用Ｕ-V视差进行地面检测
8. 【项目实践】U-V视差路面检测之动态规划

1.立体匹配算法

（极线约束、唯一性约束、几何相似性约束）

 1.1立体匹配的步骤

1. 匹配代价计算
2. 匹配代价聚合
3. 视差计算
4. 视差提纯

 1.2立体匹配的分类

1. 稀疏立体匹配
2. 稠密立体匹配

• 稀疏立体匹配

从灰度图像上提取合适的特征点，进行两幅图像的特征匹配。匹配特征包括图像中的角点、线段、轮廓和边缘等。基于特征的匹配算法稳定性强，计算量小，速度快。但也存在一些待改进的地方：

(1)  特征描述比较复杂，需要进行复杂的预处理。 
(2)  特征提取及相似点的搜索策略直接影响匹配精度。 
(3)  提取的匹配特征在图像中的稀疏性使得特征匹配算法难以生成稠密的视差图。

 1.3 稠密立体匹配

1. 局部立体匹配
2. 全局立体匹配
3. 半全局立体匹配

• 局部立体匹配：

步骤：1 => 2 => 3 => (4)，使用winner-take-all(WTA)计算视差

优点：

1. 灵活多变，运算速度快，利于并行计算。

不足：

1. 处理无纹理，弱纹理、重复纹理区域的能力较弱。
2. 在视差不连续的地方出现较大的偏差，因为假设窗口内的像素具有相同的视差。

改进方法：

1. 代价融合，每种代价都有优点和不足，通过不同的代价权重，融合不同的代价，比如AD-census。
2. 基于滤波的方法进行聚合：DT滤波、导向滤波、双边滤波，有一个显著的优点：具有保边特性。
3. 基于树的方法进行聚合：最小生成树、分割树、树滤波等，在无纹理、弱纹理、重复纹理具有独特优势，并具有较好的保边特性，但较难并行化。

• 全局立体匹配：

1 => (2) => 3 => (4)，使用全局优化方法求解能量最优解

优点：

1. 精度高。

缺点：

1. 优化的结果容易局部最优，而非全局最优。
2. 全局能量函数数学模型相对固定，从算法的构造和结构设计上很难像局部算法那么多变和有突破。
3. 计算复杂度也相应的较高，耗时长，难以达到实时性。

 1.4 局部算法 

局部算法基于隐式的平滑假设，认为图像当中一小块区域的像素具有相同的视差。一般可分为基于点、区域和相位的方法。

• 基于点的方法：比如AD代价 

step1:给定左图和右图

step2:在极线上进行搜索最匹配的点。

step3: 计算每次搜索窗口的相似度（基于像素的亮度差的绝对值）

 step4:计算视差（胜者为王）

匹配结果：（这个结果差强人意）

• 基于区域的算法（参考：双目视觉（四）匹配代价）

以基准图像待匹配点为中心像素创建一个n*n的窗口，在第二幅图像中，沿着极线在视差范围内取出与基准点领域同样大小为n*n的领域，依次与匹配点的窗口相比较，通过胜者为王(WTA)选取范围内相似度最高的点作为最终的匹配点。该方法能够快速得到图像的视差图，但在遮挡、弱纹理以及深度不连续区域易出现错误匹配，而且抗噪性能差。

• 基于相位的匹配算法

采用该算法的前提条件是图像对中对应点的局部相位是相等的。由傅立叶平移定理可知，信号在空间域上的平移使得其相位在频率域上成比例平移。因此，通过分析频率域上信号的相位信息得到图像对间的视差。该算法采用相位作为匹配基元，对几何畸变和辐射畸变都有很好的抵抗能力，定位精度高，可得到稠密的视差图。该算法仍有一些待改进的地方，比如当其前提条件不成立时，会产生相位奇点；由于算法的收敛范围与带通滤波器的波长有关，其匹配精度会随着视差范围的增大有所下降。常用的相位匹配方法有相位相关法和相位差-频率法。

• 全局算法 

全局立体匹配没有显式的代价聚合步骤，采用的函数优化的思想对匹配代价进行全局优化

定义：利用图像的全局约束信息，通过构建包括匹配代价的数据项和平滑项的全局能量函数，然后通过对其最小化以求得最终视差图。全局算法一般有置信度传播、图割、动态规划等算法，目前为止全局算法都是在这几种算法的基础上进行改进的。主要用来解决由于遮挡或重复纹理造成的像素误匹配问题，是基于优化理论方法估计视差值。（能量最小化问题）

• 能量函数：数据项+平滑项。

• 数据项：测量像素之间的相似性问题
• 平滑项：平滑像素之间的视差关系，保证相邻像素之间视差的平滑性                  
• 常用方法：模拟退火，动态规划（Dynamic programing），最大流（max-flow），图像分割（graph-cut）

置信传播算法是一种采用概率表达的全局算法，该算法首先将全局立体匹配问题转化为在二维 Markov 网络中寻求像素节点的联合概率最大值，通过迭代的方法把邻域的视差传递给相邻像素点，并计算最大后验概率求取最小能量函数值，得到稠密视差图。该算法综合考虑整幅图像像素点对目标像素的影响，所以在图像弱纹理区域以及视差不连续区域都有较好匹配效果，但算法计算复杂度高，比较耗时的同时，能量函数的数据项和平滑项间简单的求和会使得视差图有空洞现象，所以选取调节系数来平衡数据项和平滑项是对传统置信度传播算法的研究重心。

基于图割的全局立体匹配算法通过将全局能量函数最小值转化为图的最小割问题，采用最小割算法找到一条最优视差割，利用最大流求解最小割得到匹配视差值。Kolmogorov利用图割算法进行优化的能量函数进行正则性，将能量函数转换成适合用图割算法求解的形式，得到效果更好的视差图，实现全局最优，但计算复杂度高，算法比较耗时。

基于动态规划的立体匹配算法：把求解整个图像视差的过程分解为一些子过程，并逐个求解子过程，具体过程为根据外极线顺序约束，通过在视差图像上寻找最小代价路径得到最终视差图，算法简单高效。传统的动态规划算法可以较快速的处理图像遮挡区域和纹理单一区域的误匹配，具有良好的效果，但由于在匹配过程中仅考虑极线上得约束而忽略了极线间视差的约束，导致得到的视差图有条纹瑕疵现象。