一文详解立体匹配（附代码）

作者丨cc.fy@知乎

来源丨https://zhuanlan.zhihu.com/p/458589977

编辑丨计算机视觉life

双目匹配

在双目匹配的范畴里，本次内容主要局限在以下两个小的部分: * SGM(经典) 原理解析 * comparation with monodepth

SGM

半全局匹配算法（SGM）是实时立体视觉里最流行的一个算法，已经大规模的在很多产品里得到了应用。其最早由H. Hirschmuller 在2005年发表于CVPR的文章中被提出 (Accurate and efficient stereo processing by semi-global matching and mutual information)。

立体匹配算法在深度学习算法强势来袭之前，可以分为3大流派，包括局部派（SAD, SSD, NCC, Census-Transform, Mutual Information ...）,全局派 (Graph Cut, Belief Propagation, Dynamic Programming ...), 以及半全局派 (SGM). SGM是半全局领域的代表之作，相对于局部派的简单粗暴，SGM更加优雅复杂，同时也没有全局派那么time-consuming （https://blog.csdn.net/rs_lys/?type=blog）

opencv 接口

cv::Ptrsgbm = cv::StereoSGBM::create(minDisparity, numDisparity, SADWindowSize, p1, p2, diso12MaxDiff,preFilterCap, uniqueRatio, speckleWindowSize, speckleRange, fullDp);
cv::Mat disparity_sgbm;
sgbm->compute(frame->left, frame->right, disparity_sgbm);
disparity_sgbm.convertTo(frame->disparity, CV_32F, 1.0 / 16.0f);

• 参数含义解释 (https://docs.opencv.org/): 1. minDisparity: 最小视差 2. numDisparity: 视差个数(64 / 96 / 128 / 256 ...) 3. SADWindowSize: 灰度相关时的窗口大小 (3 / 5 / 7 ...) 4. p1, p2, 平滑性惩罚系数， 下文会介绍详细含义 5. diso12MaxDiff 左右视差检查中允许的最大差异 6. preFilterCap 预滤波图像像素的截断值 (下文中未用到),主要是图像预处理的操作，用来排除噪声干扰，提高边界的可区分性 7. uniqueRatio 唯一性比值 (ratio test) 8. speckleWindowSize 平滑视差区域的最大尺寸 (过滤一些斑点噪声) 9. speckleRange 连接组件(斑点)内的最大视差变化

样例双目输入与输出

• INPUT

left.png

right.png

• OUTPUT

gray-scale show

color-scale show

可以看到有比较多的空洞和视差不连续的地方，正常的流程中还包括一步视差图滤波后处理(weighted least square filtering)

wls_filter = createDisparityWLSFilter(left_matcher);
wls_filter->filter(left_disp,left,filtered_disp,right_disp);

应用滤波之后:

Reference: "Fast Global Image Smoothing Based on Weighted Least Squares", 大意是使用加权最小二乘算法进行优化，使得图像全局平滑的同时能够进行边缘的保持, 与双边滤波的整体功能相近, 可以看到在经过后处理后，视差图更加平滑，轮廓更加清晰。

利用开源的monodepth,不加任何参数修改的进行训练，然后推断上面图片对应的深度结果(https://github.com/OniroAI/MonoDepth-PyTorch)：

monodepth

从上图中可以看出，在整体表现上，深度学习方法要优于传统方法(The overall performance outperforms by a larger marjin then traditional SGM method)。

SGM整个算法流程

1. Census-Transform 将原始图像转换为census图像，为了便于匹配代价体计算 2. Compute-Cost 通过两幅census图像进行初始的匹配成本计算 3. Cost-Aggregation 代价体聚合， 'key step' 4. Compute-Disparity 基于聚合后的代价体进行每个像素的视差值计算 5. LR-Check 左右视差一致性检查 (optional) 6. Remove-Sparkles 零散的斑点移除(optional) 7. Fill-Holes 空洞填充（optional） 8. Middle-Filter 中值滤波去噪平滑

其中1-4是基本步骤， 5-8为视差优化步骤

分别对每一步进行阐述:

1.census transform

H 老爷子最早的匹配代价选择的是MI(互信息)，但相对于census-transform其计算效率比较低，所以主流方式变成了census变换. 所谓census image就是通过census-transform将原始图像逐像素变换得到的，每个像素的census值是明暗相对关系比较的一个比特串。ok, 以一个例子简单说明，加入选择的census的窗口是3*3, 有这样的一个小的image patch:

那中间像素5的census值为(110100101), 这个二进制比特串所代表的十进制数字421就是对应的census image的像素值. 所有经过census变换后可以分别得到左图的census image和右图的census image ，reference: https://www.cnblogs.com/riddick/p/7295581.html。

2. compute cost 匹配代价成本计算

这一步的过程主要是为了构建初始代价立方体，注意是三维的立方体

print(cost_init_.shape)
    [D, H, W]

其中D为disparity range, H为图像高度，W为图像宽度，ok, 现在的输入是census_left, 一个二维矩阵， census_right, 一个二维矩阵，想要的输出是cost_init, 一个三维矩阵， 如何构造，不失一般性的公式如下：

计算当前像素在每个视差下的汉明距离作为度量，这里汉明距离的计算有个面试点分享给有需要的同学：

int SGMUtils::hamming_dist(const unsigned int census_x, const unsigned int census_y){
      int dist = 0;
      int val = census_x ^ census_y;
      while(val) {
        dist++;
        val &= (val - 1);
      }
      return dist;
    }

代价立方体

横方向代表图像列，纵方向代表图像行，朝里的方向代表深度范围， 当代价体构造好之后，如果不进行关键的代价聚合， 也可以进行视差计算， 这里先跳过代价聚合，直接基于代价体进行视差计算。

4. compute-disparity

视差计算的方法很直观，对于代价体中的每个像素，在视差方向进行遍历，当前像素的视差满足对应的代价最小这一原则，三重循环过后，可以生成相应的视差图，也就是所谓的WTA（winner take all）准则。经过上面简单的几步， 可以获得如下的结果，来自明德学院的经典的左右样图:

3. 代价聚合

现在讨论下最关键的代价聚合步骤，这一步是sgm的灵魂，先看下效果:

目前常用的代价聚合有4path聚合和8path聚合， 4路聚合包括从上到下， 从下到上， 从左往右， 从右往左， 8路聚合增加了45度方向和135度方向的聚合路径，路径聚合的目的就是不仅考虑局部的代价信息， 还要加入全局的平滑信息，只是用多个方向一维的聚合来对二维进行近似，精度相似，效率大幅度提升。以四路聚合为例，会分别得到四个聚合的代价立方体，将其相加得到最终的代价立方体：

for(sint32 i =0;i