【立体视觉（五）】之立体匹配与SGM算法_sgm立体匹配

立体视觉是指利用物体或场景的平面信息得到三维信息，即实现“立体”的结果。维度信息的变换决定了其复杂性。因此，得到精确的结果需要经过一系列严格的步骤。在进行立体匹配之前，需要熟悉相机成像模型，进行相机标定和图像校正。为了简化问题，这里以依然最简单的双目立体视觉进行学习。

主要参考两本硕士学位论文进行学习，建议看原文，文献在文末。

---

一、立体匹配

立体匹配是立体视觉的中间关节，也是核心环节。采集的图像在经过摄像机标定，图像校正等预处理步骤后，立体匹配直接对预处理结果进行处理。
根据立体匹配基础理论可知，立体匹配就是寻找同一点在不同投影面的投影点，根据极线形成的约束可知，某一投影点对应的匹配点必定位于该点对应的极线上。

在同一场景中，左摄像机拍摄得到的视图整体偏右，右摄像机拍摄得到的视图整体偏左，因此根据左视图寻找右视图对应的匹配点的寻找方向应偏左。通常设定视差搜索范围 $d_{max}$，搜索过程在$[0,d_{max}]$ 范围内进行。

在立体匹配之前，需要满足两个基本条件。

（1）唯一性。一个视图的每个点在另一个视图中最多只有一个点与之对应，也就是视差值唯一。
（2）连续性。图像中大部分点的视差平滑，表现在视差就是连续的。

---

一）基本步骤

由于实际场景的复杂性，在立体匹配过程中，会受到遮挡、光线、噪声、弱纹理等诸多因素的影响，这给相关研究带来了诸多不便。学者们经过潜心研究，将立体匹配算法进行系统总结，并分为四个基本步骤来研究。

（1）代价计算：根据图像属性特征，如像素值，色彩等信息，计算出点和点之间的相似度。两个点越相似，说明是匹配点的可能性越大。
（2）代价聚合：代价聚合是立体匹配中十分重要的一个步骤。在初步的代价计算后，得到的结果不够准确，因此需要考虑邻近像素间的关系，涉及的范围不同，累加的方式不同，立体匹配的效率及效果都会不同。
（3）视差计算：对于选定的视差范围，会对应着不同的匹配代价值，从中选取最小的值作为最优解，这就是对应的匹配点。
（4）视差优化：确定视差后，可以根据邻近视差值通过曲线拟合方式细化视差，剔除匹配错误点，然后根据相邻像素灰度值相似原理进行填充，让视差图更加平滑。

根据匹配像素的考虑范围可以将匹配方法大致分为局部(Local Matching)、全局(Global Matching)和半全局(Semi-Global Matching)立体匹配。

• 代价计算
  计算匹配代价阶段，是沿着极线，在参考图像上搜索该极线上的像素点，并计算其不同的视差值与待匹配像素点之间的匹配代价值，直到视差值搜索范围达到最大视差值，并将得到的匹配代价值存储到一个三维的匹配代价矩阵中，这个矩阵也称为视差空间图，图中每个三维坐标点代表着各个匹配代价$C(x,y,d)$。

• 代价聚合
  全局立体匹配由于在匹配代价阶段以及后续的视差计算阶段做了较为复杂的处理，加上视差计算是通过最优化理论以选择最优视差值，所以不需要进行代价聚合这一步。代价聚合是局部立体匹配算法关键步骤，特别是基于区域的匹配算法。
  通常是将待匹配像素点作为中心像素，将其邻域像素点的匹配代价作为一定的约束条件，或者累加后取均值赋值与该像素点，作为该像素点的匹配代价，这便是代价聚合过程，其实是增加了邻域像素点的约束，相比于单个像素点信息，增加了图像的信息，便相当于增加了匹配代价的鲁棒性。
  

• 视差计算
  视差计算阶段，全局匹配算法和局部匹配算法是不同的。
  全局匹配算法：由于前期的匹配代价阶段，是采用的计算较复杂、可靠性较高的相似性测度函数，就单个像素点的匹配代价来说，相比局部匹配算法，匹配代价鲁棒性更强，所以在视差计算阶段，是直接利用最优化理论知识，对匹配代价函数取最小值，以求得视差值。
  局部匹配算法：代价聚合阶段之后，采用赢家通吃(WTA，Winner takes all) 的思想：在匹配代价空间中，选择累加代价的最小值对应的点作为为同名匹配点，而该匹配点对应的视差值即为该像素点的最终视差。
  

• 视差优化
  因为过程中受到的噪声干扰等因素影响，导致得到的视差图质量不高，或者因为匹配算法的限制产生许多误匹配点等。视差优化可以通过左右一致性检测、小连通区域检测、视差填充、中值滤波等方式，对视差图做进一步优化平滑处理，从而提高匹配精度。

---

二）局部立体匹配

在计算某一像素的匹配代价时，以该像素为中心选择一个局部范围，考虑局部范围内所有像素，采用某一规则计算该像素对应的匹配代价，在有效视差范围内，对于不同视差，对应着不同的匹配代价，最小的匹配代价对应的视差即为中心像素的视差。

$d(x_0,y_0)$ 为坐标$(x0,y0)$ 的像素对应的视差，$d_{max}$ 为视差搜索范围的上限，$W$ 为选择的局部范围，$cost$ 为代价函数，对于不同的计算规则，代价函数形式不同。
该类型算法的匹配流程:

局部匹配在进行代价计算时，假设整张图片颜色相似，完全忽略了光线的影响，而当光线变化大时，得到的整张图亮度有很明显的差异，从而对颜色有较大的影响。在进行代价聚合时，假设邻近区域视差相近或相同，这对前后背景相差太大或明显出现断层的区域不成立。

匹配代价的大小可以采用数学方法（主要是函数）进行衡量。采取的方法不同，得到的精度及结果都会不同，因此有必要根据图像属性选择合适的度量方法。

设 $W$ 为待匹配窗口，$d$ 代表视差，$I_L$和$I_R$表示某点在相应图中对应的灰度值，$C(x,y,d)$代表在位置$(x,y)$视差为$d$ 时候的匹配值。

• 代价计算最简单的方式就是像素绝对差(Absolute Difference, AD)算法
  

常用的其它数学度量方法还有：

• 绝对差和(Sum of Absolute Difference, SAD)
  
• 差平方和(Sum of Squared difference, SSD)
  
• 归一化互相关(NCC)

绝对差和与差平方和都是通过像素的灰度信息计算代价，计算简便，实现简单，但是光线条件会极大地影响匹配结果。归一化互相关属于归一化度量法，在灰度基础上增加了归一化的约束，这可以有效地降低噪声的影响，但是相应地，平方和开方增加了大量的运算，而且四舍五入会影响结果的精度。效果较好的局部匹配算法有自适应归一化互相关算法，大范围立体匹配，引导图像滤波等。

---

三）全局立体匹配

局部匹配算法侧重于计算局部范围内像素相关性，选取最小视差作为最终视差，与其不同的是，全局匹配算法不进行代价聚合，它是在匹配代价的基础上，加入平滑约束条件，通过全局能量函数的形式将二者结合，然后对该函数求最优解来获取视差。 能量函数的通用表达式如:

$D$ 为视差函数，$E$ 为最终结果值， $E_{data}(D)$ 为数据项， $E_{smooth}(D)$为平滑项，