立体匹配技术简介

点击“计算机视觉life”关注，置顶更快接收消息！

本文作者唐博，AR行业研究者

概述

立体视觉（也称双目视觉）主要研究的两个相机的成像几何问题，研究内容主要包括：立体标定（Stereo Calibration）、立体校正（Stereo Rectification）和立体匹配（Stereo Matching）。目前，立体标定主要研究的已经比较完善，而立体匹配是立体视觉最核心的研究问题。

在早期的研究中，立体匹配的计算平台主要为计算和内存性能较高的个人电脑。近年来，随着移动计算能力的大幅提升和移动设备（尤其是智能手机）的广泛普及，以及图形处理器（graphics processing unit, GPU）和视觉处理器（visual processing unit，VPU）的集成技术和性能水平的大幅提升，移动测量（Mobile Mapping）已经兴起并进入各大行业及消费者领域。

按照匹配点数目分类，立体匹配可分为稀疏立体匹配（sparse stereo matching）和密集立体匹配（dense stereo matching）。稀疏立体匹配由于匹配点数量稀少，一般很难达到高精度移动测量和环境感知的要求。因此，密集立体匹配是学术界和工业界的主要研究和应用方向。以下如无特殊说明，本项目的立体匹配均指密集立体匹配。

立体匹配的输入是由经过立体校正的基准图像（reference image）和目标图像（target image），输出是与基准图像具有相同分辨率的视差图（DSI，disparity space image，或称深度图：视差与深度是简单的线性变换关系）。即

其中，为基准图像的像素坐标，为目标图像的像素坐标，为视差（，为指定的最大可能视差）。为简化起见，也把基准图像称为左图（left image），目标图像为右图（right image）。

立体匹配须满足极线约束、唯一性约束、几何相似性约束等，并假定满足Lambertian表面假设（即物理世界的成像外观与成像视角无关），逐段平滑假设（piecewise smooth，即物理世界的表面是分段平滑的）等。可以证明，立体匹配问题是一个NP-hard问题。

一般认为，立体匹配包括以下四个部分：

1)        匹配代价计算（matching cost computation）；

2)        代价聚合（cost aggregation）；

3)        视差计算与优化（disparity computation/optimization）；

4)        视差改进（disparity refinement）。

匹配代价计算的常用方法有绝对差和（SAD，sum of absolute difference）、平方差和（SSD，sum of squared difference）、Census变换、正则相关性（NCC，normalized cross-correlation）、BT、MI（mutual information）、LOG(Laplacian of Gaussion)、ASW等。在有些匹配算方法中，匹配代价和代价聚合是糅合的。

根据代价聚合和视差优化方法的不同，传统的立体匹配方法一般可分为局部方法和全局方法。

局部方法（local method，通常也称为基于窗口的方法）一般采用局部的代价聚合，即

其中，为权重滤波，为匹配代价，为代价聚合结果。局部方法的视差计算与优化则十分简单，采用“赢者通吃”（WTA，winner-takes-all）的简单法则。局部方法的关键为如何构造领域以及定义权重。由于局部方法形式灵活多变，利于并行计算，成为近年来的立体匹配算法的主要发展趋势之一。

全局方法一般没有显式的代价聚合步骤，而直接采用全局能量函数的思想：

其中，为所有匹配点的匹配代价（或代价聚合）之和，为平滑约束项，为权重参数。全局方法然后采用全局优化的数学思想，对进行优化求解。常用的全局优化思想有马尔科夫随机场（MRF，Markov random field）、模拟退火（simulated annealing）、图切（graph cut）、动态规划（dynamic programming）等。

近年来，随着立体匹配研究以及学科交叉的深入发展，特别是新的数学方法的引入，涌现出很多新的立体匹配算法，并且突破了局部和全局的界限，大大丰富了立体匹配的算法理论，显著提升立体匹配的精度和速度。我们将比较重要的方法分为：基于树的方法、基于贝叶斯估计的方法、基于联合滤波的方法、基于深度学习的方法等。

国内外研究现状

经过长期的发展，立体匹配的方法已经非常丰富，综述见下，其分别对代价匹配和代价聚合进行了评估。

R. I. Hartley and A. Zisserman. Multiple View Geometry. Cambridge University Press, Cambridge, UK, 2000.

S. T. Barnard and M. A. Fischler. Computational stereo. ACM Comp. Surveys, 14(4):553–572, 1982.

L. G. Brown. A survey of image registration techniques. Computing Surveys, 24(4):325–376, 1992.

Daniel Scharstein and Richard Szeliski. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International Journal of Computer Vision, 47(1-3):7–42, 2002.

H. Hirschmuller and D. Scharstein. Evaluation of stereo matching costs on images with radiometric differences. IEEE TPAMI, 31(9):1582–1599, 2009.

F Tombari ， S Mattoccia ， LD Stefano ， E Addimanda , Classification and evaluation of cost aggregation methods for stereo correspondence, CVPR, 2008

D. Min, J. Lu, and M. Do, A revisit to cost aggregation in stereo matching: how far can we reduce its computational redundancy? ICCV 2011

以下我们综合代价计算和代价聚合，将立体匹配分为局部方法、全局方法、基于树的方法、基于贝叶斯估计的方法、基于联合滤波的方法、基于深度学习的方法，对国内外研究现状进行描述，并分析优劣。立体匹配的研究文献极其浩繁（尽管已不再是CV的一个学术热点），以下也只是引用了一部分的典型算法。

1. 局部方法

局部方法（基于窗口的方法）是所有方法中最为丰富的方法，并将仍是最具应用潜力和前景的方法之一。典型的早期方法有：采用Census及Hamming作为代价计算，采用不同大小的窗口进行代价聚合，计算自适应支撑权重（ASW）对领域进行代价聚合。这些早期的方法在精度或速度上效果较差。

为解决上述不足，近年来基于滤波的局部方法发展迅速，如DT滤波、导向滤波（guided filter），权重中值滤波，快速双边滤波。滤波的核心思想是按照不同滤波器的思想，构建不同代价聚合的方式，充分反映待匹配点与领域的（几何和色彩）关系。滤波方法的另一个显著优点就是具有很好的保边特性。

局部方法的另一个发展趋势是基于代价融合的方法，其主要思想是：考虑到每一类代价度量都有其优点与不足，将不同的代价度量巧妙融合在一起，取长补短，从而获得更好的深度估计。比较经典的工作有MBM（multiple block matching）、SNCC、AD-Census。通过对简单的匹配代价函数融合，获得了比原有方法的大幅改进的效果。

一方面，局部方法数学理论基础丰富，灵活多变，计算效率高，利于并行化，在移动测量上具备强大的优势。另一方面，局部方法由于只利用某个尺寸窗口的邻域信息，因此它的一个内在的不足就是处理无纹理、弱纹理以及重复纹理区域的能力较弱，在这些区域经常会产生误匹配。这个不足可以通过后处理的联合滤波方式得到一定程度的减缓。

O. Veksler, Fast variable window for stereo correspondence using integral images In Proc. Conf. on Computer Vision and Pattern Recognition (CVPR 2003), pages 556–561, 2003

K.-J. Yoon and I.-S. Kweon. Adaptive support-weight approach for correspondence search. IEEE TPAMI, 28(4):650–656, 2006.

R. Zabih and J. Woodfill. Non-parametric local transforms for computing visual correspondence. In Proc. ECCV, pages151–158, 1994.

Gastal, E.S.L., Oliveira, M.M.: Domain transform for edge-aware image and video processing. SIGGRAPH (2011)

He, K., Sun, J., Tang, X.: Guided image filtering. ECCV (2010)

Ma, Z., He, K., Wei, Y., Sun, J., Wu, E.: Constant time weighted median filtering for stereo matching and beyond. ICCV (2013).

Zhang, Q., Xu, L., Jia, J.: 100+ times faster weighted median filter (wmf). CVPR (2014).

Jonathan T. Barron Ben Poole, The Fast Bilateral Solver, ECCV, 2016

S. Birchfield and C. Tomasi. A pixel dissimilarity measure that is insensitive to image sampling. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(4):401-406, April 1998.

2. 全局方法

全局方法没有显式的代价聚合步骤，而采用函数优化的思想对匹配代价进行全局优化。常见的方法有基于动态规划的方法、基于图切的方法、以及经典的半全局优化方法（Semi-global matching）。基于分割的方法通常也采用全局优化的方法。

近年来全局方法的研究趋缓，主要原因有两方面：首先，全局方法主要基于不同的数学全局优化方法，结果容易落入局部最优而非全局最优；其次，从算法角度看，由于其优化目标函数的数学模型相对固定，全局方法从算法的构造和设计上很难有局部方法那么多的变化和突破，一个显著现象就是这么多年过去了SGM依然是全局方法的标杆；全局方法（包括基于分割的方法）的计算量通常比局部方法要大（尽管有一些简化和加速的变种方法），因此在实时应用中比较受限。

C. Lei, J. Selzer, and Y.-H. Yang, “Region-tree based stereo using dynamic programming optimization,” in IEEE Conference on Computer Vision and Pattern Recognition, New York, NY, USA, 17-22 June 2006.

O. Veksler, “Stereo correspondence by dynamic programming on a tree,” in IEEE Conference on Computer Vision and Pattern Recognition, vol. 2, San Diego, CA, USA, June 2005, pp. 384–390.

V. Kolmogorov and R. Zabih, “Computing visual correspondence with occlusions using graph cuts,” in International Conference for Computer Vision, vol. 2, 2001, pp. 508–515.

H. Hirschmuller. Stereo processing by semi-global matching and mutual information. IEEE TPAMI, 30(2):328–341, 2008.

3. 基于树的方法

基于树的方法最早由Yang引入立体匹配。该方法采用最小生成树的数学方法，将每个像素视为节点，其与近邻居像素点（一般是上、下、左、右四个相邻点）的关系视为边，采用灰度相似度量赋予边权重，然后采用生成树（如最小生成树）的方法，获得所有像素点的树形结构。树结构的代价聚合包含从叶节点到根节点、根节点到叶节点的两个过程，然后采用WTA方法获得DSI。最小生成树、分割树、树滤波的方法在此基础上继续发展。

基于树的方法也可以看作是一种滤波方法。但是，与局部的滤波方法显著差别在于：基于树的方法建立了一种特殊的非局部的邻域结构。这种结构与传统的局部方法相比，一般而言具备更强大的表达能力。而且，由于基于树的代价聚合具有递归特点，计算速度也比较快。

从理论和实践都表明，基于树的方法在无纹理、弱纹理以及重复纹理区域具有独特优势，并具有较好的保边性质。基于树的方法较难并行化，仍需进一步研究以在移动平台上实现。

Q. Yang. A Non-Local Cost Aggregation Method for Stereo Matching. In CVPR, pages 1402–1409, 2012.

Segment-tree

Tree-filtering: efficient structure-preserve smoothing with a minimum spanning tree, 2014.

An Improved Non-Local Cost Aggregation Method for Stereo Matching based on color and boundary cue, 2013.

4. 基于贝叶斯估计的方法

基于贝叶斯估计的方法首先由Geiger等人于2011提出。该方法（ELAS）主要思想是：首先获得强匹配的支撑点，并由这些特征点构造最优Delaunay三角形网格；根据Delaunay三角形网格以及支撑点的视差，获得待匹配点的先验视差及变化范围；然后采用某种较为简单快速的立体匹配方法获得待匹配点的条件视差；最后根据Bayesian的优化思想，获得视差的最大后验估计，即为最优视差估计。Radouane Ait-Jellal等人对ELAS进行了改进。

基于贝叶斯估计的方法架构完全不同于传统方法，融合了强匹配的支撑点、Delaunay三角形、Bayesian优化，获得了较好的匹配精度。另外极为重要的是，由于先验视差的存在，每个待匹配点不需要遍历，因此本方法仍是迄今为止最快的方法之一。由于三角网格剖分与物体边缘并不一致，因此保边性质较差；某些像素点的视差可能无法计算。

基于贝叶斯估计的方法之后发展并不好，其潜力仍有待进一步研究。但这类方法有一个特别明显的优势是：所有算法在进行立体匹配之前，都要提取特征点进行在线的立体校正（stereo rectification），这些点往往也可以用作支撑点。因此，此类方法在实际应用中的效率会非常高。

A. Geiger, M. Roser, and R. Urtasun, “Efficient large-scale stereo matching,” in Proceedings of the 10th Asian Conference on Computer Vision - Volume Part I, ser. ACCV’10. Berlin, Heidelberg: Springer-Verlag, 2011, pp. 25–38.

Radouane Ait-Jellal, Manuel Lange, Benjamin Wassermann, Andreas Schilling and Andreas Zell, LS-ELAS: Line Segment based Efficient Large Scale Stereo Matching, 2017.

5. 基于联合滤波的方法

基于联合滤波（Joint Filter）的方法主要思想是：联合初始深度、色彩以及目标信息等，对图像深度图进行优化估计。所有滤波的匹配方法都可以用于联合滤波。基于联合滤波的方法还可以用于视差改进、上采样、深度图超分辨、语义分割等。

联合滤波方法的两个主要优势在于：良好的保边性质及用于深度图上采样，近年来研究较多。

Barron, Jonathan T., and Ben Poole. "The Fast Bilateral Solver." european conference on computer vision (2016): 617-632.

He, Kaiming, Jian Sun, and Xiaoou Tang. "Guided image filtering." european conference on computer vision (2010): 1-14.

Park, Jaesik, et al. "High quality depth map upsampling for 3D-TOF cameras." international conference on computer vision (2011): 1623-1630.

Kopf, Johannes, et al. "Joint bilateral upsampling." international conference on computer graphics and interactive techniques 26.3 (2007).

Zhang, Yinda, and Thomas A. Funkhouser. "Deep Depth Completion of a Single RGB-D Image." computer vision and pattern recognition (2018): 175-185.

6. 基于深度学习的方法

深度学习是近几年计算机视觉领域发展极为迅速的一种主流机器学习方法，在许多跟踪、检测、识别等方面大幅优于传统的机器学习方法。

基于深度学习的方法首先由Jure Zbontar和Yann LeCuny于2015年将卷积神经网络（CNN, convolutional neural networks）应用于立体匹配，引起了广泛关注。当前基于深度学习的方法主要有三种：

• 匹配代价学习：该方法利用深度学习训练匹配代价函数，之后采用传统的代价聚合、视差计算、视差改进等步骤；

• 正则学习（平滑学习）：该方法基于立体匹配的平滑假设，利用深度学习训练超像素，通过估计超像素的深度获得所有像素点的深度；

• 端到端视差学习：该方法的输入为左右图，直接利用多层网络结构训练深度图，因此完全摆脱了传统的立体匹配的四步骤架构。

基于深度学习的方法与传统方法相比，还存在一定的劣势，主要表现为：首先，当训练样本与测试样本的场景差异很大时，基于深度学习的方法性能会大幅下降，因此无法适应复杂多变的场景；训练适应复杂多变场景的学习网络则可能导致网络复杂度太高，或者网络训练收敛效果差甚至无法收敛。其次，当前的深度学习方法在精度和速度方面与传统方法相比并无显著优势，应用于移动测量尚需时日。再次，所有基于CNN的深度学习方法的一个明显缺陷是鲁棒性差。目前工业界应用的立体匹配仍以传统方法为主。

2015 Stereo matching by training a convolutional neural network to compare image patches

W. Luo, A. G. Schwing, and R. Urtasun. Efficient deep learning for stereo matching. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5695–5703, 2016.

F. Guney and A. Geiger. Displets: Resolving stereo ambiguities using object knowledge. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4165–4175, 2015.

A. Kendall, H. Martirosyan, S. Dasgupta, P. Henry, R. Kennedy, A. Bachrach, and A. Bry. End-to-end learning of geometry and context for deep stereo regression. arXiv preprint arXiv:1703.04309, 2017

Cascade Residual Learning: A Two-stage Convolutional Neural Network for Stereo Matching

此外，特别值得一提的是，立体视觉有一个常常被忽略而又十分重要的方面，就是立体校正。立体校正对左右图对齐精度影响甚大，从而显著影响了立体匹配的数据输入质量。可以说，对于立体校正精度很高的数据，采用较为简单的立体匹配方法也可以获得很好的效果（大家一个直观体验就是，对于同一个算法，Middlebury数据集的测试效果往往较KITTI数据集的效果更好，主要的原因就是Middlebury数据集的立体校正精度更高）。目前OpenCV（3.0版本等）集成的立体校正方法效果并不好。立体校正研究涉及到特征点选择、数学模型、优化算法三个方面。以下两个近期的立体校正工作可供参考。

Fusiello, Andrea, and Luca Irsara. "Quasi-Euclidean epipolar rectification of uncalibrated images." machine vision applications 22.4 (2011): 663-670.

Ko, Hyunsuk, et al. "Robust uncalibrated stereo rectification with constrained geometric distortions (USR-CGD)." Image and Vision Computing (2017): 98-114.

最后，出于严谨的学术角度考虑，读者需要注意的是：首先，以上综述可能并未涵盖立体匹配的所有方法；其次，以上分类系个人观点，与经典的两类分法（见Scharstein and Szeliski, 2002）已相去甚远，仁者见仁，请读者自行鉴别。

推荐阅读

深度相机原理揭秘--双目立体视觉

如何从零开始系统化学习视觉SLAM？

欢迎关注公众号：计算机视觉life，一起探索计算机视觉新世界~

觉得有用，给个好看啦~