孙道辉　孙丽君　陈天飞

摘要：双目立体匹配是三维重建、多视点视频编码、目标跟踪等研究领域的研究热点。首先介绍平行相机模型，分析归纳双目立体匹配原理、规律及一般步骤，然后对现有经典立体匹配算法进行分类，并对不同类型的算法进行剖析，最后基于OpenCV实现10种典型的双目立体匹配算法，在匹配误差和时间复杂度上进行比较，分析相关算法优缺点，总结立体匹配算法未来研究方向。

关键词：计算机视觉；双目立体匹配； OpenCV；匹配误差；时间复杂度

DOIDOI：10.11907/rjdk.181985

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2018）009009203

英文标题Binocular Stereo Matching Approach Based on OpenCV

——副标题

英文作者SUN Daohui，SUN Lijun，CHEN Tianfei

英文作者单位（School of Electrical Engineering， Henan University of Technology， Zhengzhou 450001， China）

英文摘要Abstract：Binocular stereo matching is a hot topic in the 3D reconstruction research， multi-view video coding， and target tracking. Firstly， the parallel camera model is introduced， and the principle， law and general steps of binocular stereo matching are summarized. Then the existing classical stereo matching algorithms are classified， and different types of algorithms are analyzed. Finally， based on OpenCV， 10 algorithms are implemented. A typical binocular stereo matching algorithm is compared in the matching error and time complexity. The advantages and disadvantages of the related algorithms are analyzed， and the further research directions of the stereo matching algorithm are summarized.

英文关键词Key Words：computer vision；binocular stereo matching；OpenCV；matching error；temporal complexity

0引言

人类对周围信息约80%是通过视觉感知得到的[1]。随着数字技术和机器人技术的发展，迫切需要计算机和机器人具有图像获取、图像处理及视觉理解能力。20世纪四五十年代，以计算机视觉的方法进行二维图像处理与研究为计算机视觉理论的发展奠定了基础。20世纪60年代Roberts[2]使用积木世界理论开创了以三维场景计算为目的的实验研究。1982年Marr提出计算机视觉理论，详细介绍了视觉计算理论与方法，论述了计算机视觉的主要研究内容是使计算机具有从二维图像认知三维环境信息的能力，目的是利用二维信息实现三维重建，标志计算机视觉成为一门新的学科。立体匹配是计算机视觉的一个重要领域和方向，其基本原理是从两个视点中观察同一场景以获取立体图像对，匹配对应点像素，计算出视差图及对应深度[3]。

由于双目立体匹配是二维平面图像恢复三维深度信息的逆问题，存在很多影响恢复深度信息的不确定因素。目前国内外对双目立体匹配积累了大量研究，Barnard[4]介绍了立体匹配原理及主要立体匹配算法，并制定了算法性能评价标准，后续算法大都采用该标准。Scharstein等[5]提出对双目图像产生稠密视差的立体匹配算法分类，提供了算法测试实验平台及算法性能评估方法，为立体匹配研究创造了良好的条件。大连理工大学白明等[6]对当前双目立体匹配算法进行了归纳总结，分析了立体匹配存在的难题，并论述了可能的解决方案。南京理工大学郭龙源等[7]在理论研究基础上对计算机视觉与立体匹配算法进行了试验验证。但是面对立体匹配的病态问题，国内外还没有统一、高性能的解决算法。

立体匹配是计算机视觉的一个重要领域和方向，其基本原理是從两个视点中观察同一场景获取立体图像对，匹配对应点的像素，计算出视差图以及对应深度[8]。通过双目摄像头获取立体匹配图像对，实现基于OpenCV的双目立体匹配算法，对双目立体匹配技术具有重要意义。

1双目立体视觉模型

在双目视觉中，因视向不同，左眼看到物体左边物点，右眼看到物体右边物点，同一物体在在两个视网膜上得到不同的两个视像，两者之差称为视差[9]。双目立体匹配原理即通过对人眼成像的模拟进而获取深度信息。

根据人眼成像获得视差与深度信息的原理，双目立体匹配通常采用平行相机模型，原理示意如图1所示。

根据三角形相似原理，可以得到：

PlB2+x=fZPrB2-x=fZ （1）

通过公式（1）可以得到视差：

d=Pl-Pr=BfZ（2）

其中d为视差，Pl、Pr分别为空间中物体在左右投影平面上的点，B为基线即两摄像机光心之间的距离，f为摄像机焦距，x为空间点P的横坐标。

2立体匹配算法

根据立体匹配的几何约束和场景约束，匹配算法可以分为基于局部、全局、半全局的匹配算法。

2.1基于局部的匹配算法

基于局部的匹配方法分为基于区域、基于特征、基于相位3类[10]。基于区域的匹配算法按照一定的相似度测度函数进行局部代价聚合计算。基于特征的匹配算法通常采用图像特征点、线等匹配基元进行特征匹配。基于相位的匹配算法是对图像空域信息经过傅里叶平移变换后的频域相位信息进行处理、计算出视差。在实际工程精度要求不高的场合中，通常采用基于区域的匹配算法进行硬件实现。公式（3）-（5）列出了3种常见的相似度测量函数。Il和Ir分别为参考图和匹配图，d为视差搜索范围，S为匹配区域。

灰度差的绝对值和（Sum of Absolute Differences，SAD）：

C（x，y，d）=∑x∈S|Il（x，y）-Ir（x+d，y）|（3）

灰度差的平方和（Sum of Squared Differences，SSD）：

C（x，y，d）=∑x∈S（Il（x，y）-Ir（x+d，y））2（4）

归一化交叉相关（Normalized Cross Correlation，NCC）：

C（x，y，d）=∑x∈S（Il（x，y）-l）·（r（x，y）-r）∑x∈SIl（x，y）2·∑x∈SIr（x+d，y）2（5）

2.2基于全局的匹配算法

基于全局的匹配算法[11]是将对应点的匹配问题转化为寻找某一能量函数的全局最优问题，能量函数由数据项和平滑项组成，见公式（6）。基于全局的匹配算法包括：动态规划算法[1213]（Dynamic Programming， DP）、图割算法[14]（Graph Cuts， GC）、置信传播算法[15]（Belief Propagation， BP）及群智能算法，如遗传算法、神经网络算法、协作算法[16]等。

E（d）=Edata（d）+λEsmooth（d）（6）

其中，E表示能量函数，Edata是数据项，Esmooth是平滑项，λ是惩罚因子，d为视差。全局匹配算法在能量E最小的情况下求得视差d。

2.3基于半全局的匹配算法

局部匹配算法快速简单，但是得到的视差图粗糙，易造成匹配且对噪声敏感；全局匹配算法精度高，计算复杂。半全局匹配算法[1718]（Semiglobal Matching，SGBM）试图结合二者的优点，使算法性能在视差精度和计算复杂度上达到一个折中的、可接受的效果，其基本思想是利用多个一维搜索路径的局部寻优过程，近似二维图像的全局寻优过程。半全局是在全局能量函数基础上加入额外的平滑约束[19]，见公式（7）。

E（d）=∑pC（p，dp）+∑q∈NpP1T[|dp-dq|=1]+

∑q∈NpP2T[|dp-dq|>1]（7）

式中，右侧第一项为基于视差d的所有像素匹配代价和，表示数据项；后两项为平滑项，P1、P2为像素点p在邻域Np的惩罚系数。

3实验结果与分析

实验使用Microsoft Visual Studio 2010软件调用OpenCV，采用C++语言编程实现基于SAD、SSD、ZSSD、NCC、Census变换的区域匹配算法、半全局SGBM算法及基于全局的的DP、GC算法。测试图像采用Middlebury大学提供的测试集中的Tsukuba图像。图2为实验所用的两幅双目立体匹配测试灰度图像以及参考视差。

从视觉效果上看，GC算法视差图清晰、准确，效果最佳，5种区域匹配算法的视差图都有残缺破损、不完整的情况，DP算法视差图像出现了垂直方向的模糊条纹，半全局算法视差图像效果不及GC算法，但是明显好于区域匹配算法。

根据算法运行时间，比较各算法计算深度图的快慢，进行定量分析，从参考视差图对比计算的总误匹配像素比和计算时间两方面比较各算法性能，见表1和表2。

从表1可看出，BM算法运行速度快，但总误匹配像素比最大。GC算法总误匹配像素比非常小，与真实视差图几乎相同，但计算复杂度太高，难以在实际硬件中实现。SGBM在算法时间、复杂度和计算结果精度方面处于折中，为立体匹配提供了新的算法思想。

表2數据表明，基于局部的立体匹配算法总误匹配像素比相近，该类算法有较多误匹配像素，总误匹配像素较高，在算法运行时间上Census变换算法最快。另外，与OpenCV自封装算法相比，调用OpenCV库函数实现的算法运行时间更长。

4结语

立体匹配是计算机视觉领域中的难点。本文首先利用摄像机成像原理，分析了双目立体匹配的平行相机模型，推导出深度值与摄像机参数之间的数学关系；然后介绍了开源计算机视觉库OpenCV接口及其功能，并重点介绍了视觉模块；最后利用OpenCV实现了经典立体匹配算法，并对算法性能进行分析比较，指出了各类算法优缺点，对双目立体匹配在实际应用以及算法理论的进一步研究具有重要意义。

参考文献参考文献：

[1]马颂德，张正友.计算机视觉—计算理论与算法基础[M].北京：科学出版社，1997.