【立体视觉（五）】之立体匹配与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)$为平滑项，𝜆为可变参数，用来调整平滑项占的比例大小。显然，数据项代表匹配程度，平滑项则是附加约束，与可变参数进行配合，用来使能量函数最小化。

𝑑𝑝代表像素$p$ 的视差， $C(p,d_p)$ 为像素$p$ 在视差为𝑑𝑝时的匹配值，Ω${}_L$代表左图全部像素。

N 为附近像素集合。$s(d_p,d_q)$ 表示为了进行平滑处理，对周围像素的惩罚函数，如果视差相差小，那么相应的惩罚也很小，如果较大，那么惩罚也大。

如果像素$q$ 和像素$p$ 视差相等，那么不进行惩罚，如果不相等，那么进行惩罚。

全局匹配算法根据研究方法可以大致分为三种：
（1）图割(Graph Cut)
图割是典型的全局立体匹配方法。首先建立网格图，然后进行分割求解，最后生成视差图。其中，网格图的建立至关重要，直接影响到后续的图割。图割法得到的结果虽然有较高的精确度，但是计算量很大，因此效率不高。
（2）置信传播(Belief Propagation)
将立体匹配问题转换为马尔科夫随机场问题，用概率的方式进行求解，这就是置信传播方法。能量函数的计算方法如式：

D 表示像素p 代价，W 表示别的像素与p 之间的相关性。
（3）动态规划(Dynamic Programming)
动态规划常用于在二维平面求解最优解。动态规划算法在对单路径的扫描线求取能量函数最小值时，可以达到多项式时间复杂度。立体匹配正是利用这一点寻找视差搜索的最优路径，对应的能量函数的计算方法如式：

𝐸(𝜃)为𝜃范围内的视差值，𝐸(𝜃1, 𝜃2, 𝜃3, ⋯ , 𝜃𝑛 )为𝜃1, 𝜃2, 𝜃3, ⋯ , 𝜃𝑛对应视差。

可以看出，对于全局匹配算法而言，全局能量函数十分重要，由于考虑到了全局信息，得到的结果相对局部算法而言更精确，但是更加耗时，效率不高。

---

半全局立体匹配（在下面展开）
局部匹配算法匹配速度快，但是精度低，与之相反的是，全局匹配算法精度高，但是效率低。学者Hirschmuller在经过认真研究后，结合二者优势，创造性地提出了半全局立体匹配算法。该算法力求在提高精度的同时兼顾效率。实质上该算法是动态规划思想的应用，只是在具体实现上与一般的动态规划思路不同。在进行代价聚合时，其先得到直线路径代价计算的结果，然后对各个路径的结果进行合并，近似代替二维。该算法整体上仍然采用全局算法框架，构建能量函数，实现全局最优。

---

四）评价标准

立体匹配算法的优劣主要是时间及精确度这两个指标。其中，时间严格来说是从摄像机采集图像到输出最终视差图这段时间，但是考虑到不同设备差异带来的时间差，通常假设图像已经采集，因此时间是从左右视图到经过一系列计算获得视差图这段时间，较好量化。然而，对于匹配效果，每个人得到的直观感觉不同，因此有必要通过特定的数据平台去衡量匹配结果。

Middlebury Stereo Evaluation 是由知名学者Scharstein、Szeliski 和Hirschmuller 等共同创建的测试网站，供立体匹配相关研究人员用来评估匹配效果。将改进算法得到的视差图提交到该网站，对照标准视差图评估自身算法，就可以得到算法的错误匹配率，并且可以与其它算法进行比较。其中，衡量结果主要用到均方误差(Root MeanSquare, RMS)和错误匹配率百分比(Percentage of Bad Matching, PBM)方法。

1. 均方误差(RMS)

2. 错误匹配率百分比(PBM)

计算得到的像素点在(𝑥, 𝑦)的的视差是𝑑${}_c$ (𝑥, 𝑦)，该位置对应的标准视差值为𝑑${}_T$ (𝑥, 𝑦)，N 为图像像素总个数，𝛿${}_d$为不匹配的阈值。
RMS 是将研究算法的结果生成的视差对比标准视差图的视差，然后做差，如果超出阈值就是错误匹配，PBM 则是统计匹配错误的像素占全部像素的比率。

---

二、半全局(SGM)立体匹配

SGM 算法结合了局部和全局算法的优势，兼顾精度及效率。SGM 算法严格遵循立体匹配步骤，其中代价计算所使用的互信息及代价聚合采用的一维路径聚合近似代替二维最优是其特色。

该算法的匹配过程：基于互信息的代价计算、多路代价聚合及视差计算及视差优化。

一）代价计算

在提出SGM 算法时，考虑到用互信息的很大原因在于互信息对光照变化不敏感，采用这一方法，在后续结果中，可以较少地考虑光线因素，这无疑降低了研究难度。
在讨论图像匹配性时，首先应探究像素之间匹配强度，将像素点视为随机量，这样问题转化为随即量之间匹配强度，在信息论中，这可以用互信息的概念来表达。假设存在随机变量A 和B，互信息是用来反映A 和B 之间的相关性。在图像处理中也会经常用它来表示图像之间的相关性。A 和B 之间的互信息用数学符号表示如式所示。

互信息可以用熵的形式来表示

H 表示熵，一个变量表示该变量对应的熵，两个变量表示二者的联合熵。作为一个抽象概念，其可以简单理解为不确定性的概率表达形式，因为一个随机变量的熵越大，不确定性也越大。

两张图各自的熵及联合熵可以用来表示互信息。熵为一张图包含的信息，联合熵为两张图的全部信息。当两张图包含的公共信息越多，那么联合熵就越小，互信息就越大，两张图片关联性就越大。
用𝐼𝐿和𝐼𝑅分别来表示左右两张图的灰度值。$H_{I_L}$和$H_{I_R}$表示两张图的熵， $H_{I_L,I_R}$ 表示联合熵，则互信息表示为

熵用灰度分布概率P 表达

在使用互信息进行代价计算时，首先需要用其中一张图以视差图为基准进行修正，使得两幅图像的同名点在同一位置。

---

二）代价聚合

SGM 算法思想上与全局匹配算法一致，都是通过建立能量函数，使结果最优，从而在前一步骤的基础上达到聚合的目的。该算法具体的能量函数如式(3-13)所示。

等号右边首先是数据部分，对视差图D 中全部像素的匹配代价值求和即为该项；紧接着是平滑部分，q 为像素p 的邻域𝑁𝑝内的像素，当像素p 与q 相差不大时，对该像素进行力度为P1 的惩罚；第三项也为平滑项，表示像素p 与q 相差较大时进行力度为P2 的惩罚。第三项的惩罚力度P2 要大于第二项惩罚力度P1，P1 适用于与周围像素点视差相比，视差变化较小的情况，即连续的平面，第三项适用于视差变化大的地方，特别是边缘处，因此也被称为边缘约束惩罚因子。在半全局立体匹配算法中，通常将P1 设置为常量，而P2 根据灰度值的变化进行计算，方法如式

$P_2^{\prime }$ 是固定值，𝐼𝑝、𝐼𝑞表示当前像素点的灰度值和与该像素点同一路径的周围像素点的灰度值。对于P1 或者$P_2^{\prime }$ 的取值具有很大的不确定性，通常是根据经验或者重复实验选取合适的数值，而由于处理图像信息不同，对于不同图像，选取的值也不同。这对用同样的方法处理不同数据集，分析实验结果的客观性时有一定影响。一般而言，对于实际场景或物体，视差值变化较大的区域通常是物体的边缘，但是由于光照、噪声等的影响会出现错误匹配，因此，对于惩罚参数通过经验或实验设置都是不合理的。

对式(3-13)进行最优求解是一个非确定性问题。SGM 巧妙地应用一维聚合来实现二维聚合。首先选定某一路径，计算该路径在有效视差范围内的匹配代价，这就是所谓“一维聚合”，然后对所有路径进行类似计算，得到某像素所有路径的匹配代价，将这些匹配代价求和，选取有效视差范围内的最小值，这就是该像素聚合后的匹配代价值。任一像素p 在某条路径r 上的具体计算方法如下所示。

第一项为数据项，C 为匹配代价；第二项为平滑项，将路径代价值与P1 惩罚代价值、P2 惩罚代价值进行比较后，取最小值作为平滑项，第三项是为了防止代价值超过上限而做的调整，每一路径代价上限L：

路径代价总和S ：

路径聚合如图

可以看到，有3 种路径聚合方式，分别为4 路径聚合（黑色箭头）、8 路径聚合（黑色+蓝色箭头）、16 路径聚合（金色箭头），路径数越多，效果越好，但是耗时也越长。通常，为了获得高质量视差图，对8 个方向进行路径聚合就足够了

SGM 匹配算法的代价聚合过程是这个算法最独特的一点，将对像素点的二维求解最优解问题巧妙地转换为一维方向上求解最小匹配代价的问题，将多个路径的匹配代价进行求和，是为了提高邻域像素点对像素点的影响，从而对弱纹理和重复纹理区域等匹配难点情况的匹配精度有一定的提高，且多路径聚合的方式，还可以消除传统动态规划聚合方法所产生的图像上条纹噪声，既能达到全局匹配的匹配精度，又能通过这种巧妙的聚合方式，降低算法的复杂度，提高匹配效率。

---

三）视差计算

SGM 算法作为半全局匹配算法，在视差计算，选择和局部匹配算法一样的赢家通吃(WTA) 算法：当某像素点的所有视差值的匹配代价聚合之后，选择累加代价的最小值对应的点作为为同名匹配点，而该匹配点对应的视差值即为该像素点的最终视差，从而进行相应位置上的存储，这样，视差图便是一个大小与左图像一样的矩阵，每个像素点对应的位置为该像素点的视差值，这便是算法得到的初始视差图。

---

四）视差优化

得到了初始视差图后，视差优化将进行进一步的处理。因为初始视差图会因为受到噪声影响，出现许多错误视差点，还因为遮挡或者深度不连续性导致的明显的离群点，或者重复纹理区域，出现明显的误匹配点或者视差空洞等情况。
视差优化通常会采用左右一致性法对错误匹配点进行检测。这需要利用了立体匹配中的唯一性约束，即其中一幅图像上的各个像素点只能与另一幅图像上的唯一一个像素点匹配，这样，每一对同名点之间都是一一对应的关系。 将左右图像顺序交换，也同样步骤的计算匹配代价和代价聚合，从而得到右图像对应的视差图，之后再将其与左图对应的初始视差图做阈值比较，找到每个像素点对应的初始视差图上的视差值与右图视差图上的视差值，如果两者之间的差值大于一个像素点的阈值，则该点判为误匹配点，剔除掉即可。

对于小区域内明显的小块误匹配区域或者离群点，视差优化采用剔除小连通区域法，将明显误匹配连通区域内的视差值或离群点视差值，与邻域内的像素点的视差值做比较，并设置阈值，以判断该小块连通区域是否为误匹配，如差值大于阈值则将其剔除。剔除小连通区域法操作较简单，但是将大大地提高视差图的质量，从而提高匹配精度。

SGM 算法在视差优化阶段，对无效视差的填充，分为两种情况进行填充。

1. 误匹配产生的无效视差，与其邻域像素点的视差值作比较，将邻域像素的中值作为该无效视差点的视差值，即通过中值滤波完成视差填充。
2. 由于遮挡产生的无效视差，遮挡区域通常也是视差不连续区域，也就是说，会存在前后景的区别，前景离相机近，即深度较小，视差值较大，相反，后景则视差值较小，所以，可以通过在左右一致性法检测像素点时，加入视差值判断，若在左视差图上出现了多个匹配点的视差大于右视差图上相应像素点的视差值时，则说明这几个匹配点更接近后景，所以可以将它们判断为遮挡区内。对其邻域的像素点视差值作比较，选择次小值，作为这些遮挡区内的无效视差点的视差值。这一步，可以有效地优化视差图，特别对遮挡区的匹配精度，可以明显提高。

---

三、深度图或三维点云计算

在前文有提到，极线校正就是经过一系列变换把双目立体视觉几何结构校正为平视双目标准几何结构，即左右相机的成像平面在同一个平面上且是垂直对齐的，如下图所示。

---

一）通过视差计算深度

获得视差图后，可以根据视差与深度的转换关系计算出深度图以及三维点云。
视差与深度之间，存在转换关系：
$$D=\frac{Bf}{d+(x_{0r}-x_{0l})}$$
D为深度，d为视差，B为基线长度，$x_{0r}$和$x_{0l}$分别为左右视图主点的列坐标，大多情况下，主点列坐标相同，所以有
$$D=\frac{Bf}{d}$$

---

二）通过深度计算点云

$$\{\begin{array}{l}Z=D\\ X=\frac{D(x-x_{0l})}{f}\\ Y=\frac{D(y-y_{0l})}{f}\end{array}$$

这几个关系都可以根据上面的图，由相似三角形关系推导出来。

---

参考
[1] 高聪聪. 基于SGM的立体匹配算法研究[D].西安电子科技大学,2022
[2] 吴玉晗. 基于双目立体视觉的立体匹配算法研究[D].电子科技大学,2022
[3] 立体匹配入门指南（8）：视差图、深度图、点云
[4] 【立体视觉（一）】之成像原理与相机畸变
[5] 【立体视觉（二）】之对极几何与关键矩阵
[6] 【立体视觉（三）】之张正友标定法原理篇
[7] 【立体视觉（四）】之极线校正与双目视觉