双目立体视觉匹配算法的实现与分析

2022-07-20石迪迪

经纬天地 2022年3期

王沁费强石迪迪

（浙江省国土勘测规划有限公司，浙江杭州 310030）

0.引言

摄影测量是指利用相机或其他传感器对地面或物体表面实施拍照，获取包含纹理信息的影像数据，采用相应的处理手段，可以快速获取大量的空间点位信息，是目前应用领域较为广泛的技术方法[1]。摄影测量采用非接触式测量方法，可有效兼顾精度与效率，测量周期短，已经在众多领域得到了广泛的应用[2]。采用非接触测量方式对特定目标或场景进行精确测量，结合特定的技术恢复其三维信息一直是一个研究热点[3]。双目立体视觉测量利用组成立体像对的图像进而实现三维重建。所谓立体像对，就是指具有一定重叠关系的两张影像，可利用两个相机或者一个相机在空间的不同位置实施拍摄获得[4]。双目立体视觉测量技术涉及影像获取、预处理、影像匹配和三维重建等步骤，其中，影像匹配作为关键的技术环节，其优劣性直接影响到后续三维重建质量，而匹配质量又是由匹配效率、精确性和可靠性决定的。目前，影像匹配算法的发展一直是双目立体视图技术的瓶颈。

影像匹配是指在具有重叠关系的立体影像对上进行相似特征点搜索，在剔除误匹配点后，获取最佳的空间相似对应点，以此恢复影像间的空间变化关系[5]。影像匹配的关键是采取一种合适的匹配算法，以求高效性、准确性、稳健性以及时效性[6]。

1.立体匹配原理

结合立体像对的重叠区域，用投射理论表述多个投影点间的变换模型，利用投影点的特征因子计算视差。其最终目的就是根据图像处理和参数优化获取像素点间的视差值。历经多年发展，不断涌现出了多种优质匹配算法，包括局部算法和全局算法。其中，对于任何匹配算法均具备完整的计算流程。首先，根据场景要求确定匹配单元，选择合理的特征提取算法，并对提取的特征进行描述；然后，选择匹配算法，并以相似性度量函数和约束准则完成特征点匹配与提纯；最后，完成视差计算。

各类特征匹配算法在完成视差图获取时，难免会受到影像噪声、阴影遮挡、匮乏纹理、光照强度差异等多种因素的影响，导致匹配结果出现系列问题，因此，需要建立相关的立体匹配评判准则。一般把真实视差图与计算所得的视差图进行对比，将符合限差条件的视为正确结果，否则任务匹配失败。以误匹配率函数为例，设两视差图大小相等，则视差图误差比重如式（1）所示：

式（1）中，N为像素点总数；（i，j）为像素点坐标；dc为待评估视差值；dt为真实视差值；δd为阈值，一般取值为1。误匹配率可以直接描述特征匹配的好坏，下面我们选择三种当前比较流行的影像匹配方法进行相关的研究和分析。

2.三种影像匹配算法的原理

2.1 %半全局匹配算法

半全局匹配算法（Semi-Global Block Stereo Matching,SGBM）是计算机视觉领域的一种影像匹配算法，该算法是采取互信息来描述像点间对应关系的，主要原理是先以互信息为基础，迭代计算像素值，然后以多维方向的约束来模拟二维约束。

SGBM匹配算法是以互信息MI1，2为基础的，互信息MI1，2是通过两张影像的信息阈H1、H2及其联合信息阈H1，2来定义的，其定义如式（2）所示：

单张影像的信息阈H以直方图统计概率分布情况，联合影像的信息阈H1，2则用相互匹配影像的灰度联合分布函数进行计算。经过逐像素匹配计算、用一维约束近似二维约束、视差计算、误匹配剔除等步骤完成。

（1）逐像素匹配计算

采用函数d（xi，yi，IL，IR）判断两个像素点相似程度的大小，进而判断是否为同名像点，如式（3）所示：

式中，xi和yi分别表示左右扫描线上对应的像点。若左扫描线上像点的灰度定义为IL（xi），则通过采样点线性内插计算，可以得到右扫描线上对应的灰度值IR（yi）。

（2）用一维约束近似二维约束

在P的周围，以45°为间隔设置了8个路径。通过8个路径计算最小代价路径，以此来近似二维约束匹配计算。

（3）视差计算

一般采用迭代的方式计算视差，主要包括两种方法：一是结合随机视差影像对右影像进行纠正，而后实施特征匹配，并重新生产出视差影像；二是结合分等级计算方法，先利用半分辨率获得初始视差影像，而后经递归计算得出新的视差影像。

（4）误匹配的剔除

在完成影像匹配后，再次利用右影像对左影像上的点进行同名像点匹配。若两次的匹配结果视差相同，则认为匹配成功，否则视为粗差，将其剔除。

2.2 BM匹配算法

BM（boyer-moore，BM）匹配算法是一种精确字符串匹配算法（区别于模糊匹配），在OpenCV中被用来对图像灰度进行精确匹配，图像灰度匹配也可以认为是字符串的匹配[9]。BM算法应用从右至左进行比较的匹配方法，并引入了坏字符算法和好后缀算法的不同启发式跳转方式，进而计算出模板右移的步长。

令待匹配图像的灰度值为文本串T，匹配的图像灰度值为文本串P，并定义为模式串。先将T左对齐于P，而后从右向左进行比较（如图1所示）：

图1 文本串T和模式串P

若采用上述方法，无法完成匹配时，BM匹配算法就会跳转到好后缀算法和坏字符算法两种启发式规则，进而在匹配过程中，逐步计算出上述模式串P的移动步长（如图2所示）：

图2 坏字符与好后缀启发式规则

可见，文本串P与T在进行匹配时，斜体E和B则表示首个不匹配的字符，为坏字符。加粗体CAB表示匹配好的字符，为好后缀。图2中BM算法从右到左的匹配不一致情况，需要根据坏后缀算法，应用两种情况来处理：

（1）假如文本串T中不匹配的字符E没有出现在文本串P中，则可以理解为，从E开始的长度为m的字符串不能匹配P。此时，P可以直接跳到E，并开始接下来内容的匹配。

（2）如果E出现在与文本串P不匹配的字段中，则认为与字符E对齐。

历经两次调整后，再次从右到左执行匹配过程（如图3所示）：

图3 适用好后缀算法的情况

2.3 %GC匹配算法

基于图切（graph-cut，GC）图像分割的方法维持了这样一个假设：场景可以被分割成很多部分，其中每一个部分深度的变化都是细微的，可以和深度大致相同。分割则是基于图像的颜色信息。这种方法要么在匹配时将分割的小平面参数作为约束，要么在匹配时以小平面代替像素作为匹配单元。本文选择基于mean-shift的双目立体视图图像分割匹配算法，具体流程如下：

首先，使用分割算法对图像实施分割后，采取基于窗口的方法计算概略的初始深度图。

其次，使用稳健的最小二乘法解算每个分区的平面模型参数。

冬天，雪精灵欢快飞舞，将大地装点成银装素裹。书包带着我旋转着、飞翔着，我与雪精灵欢快共舞，银铃般的笑声引得地上的雪人也裂开了嘴。

再次，同一簇中的点形成一个深度平面，我们可以采取初始深度图对深度平面的平面模型参数进行计算。在该算法中，深度分配的单位是提取的深度平面，而不是像素。

最后，根据深度图将所有的深度平面转换就得到了整幅转换影像。这样，我们就能定义匹配的代价，如式（4）所示：

其中，第一项表示的是转换后的影像与真实影像之间的差别，定义如式（5）所示：

W（p）表示像素点p在转换影像中的值，而R（p）表示p在真实影像中的值。不相似函数dis（pi，pj）表示颜色三通道绝对差的和。

式（4）右侧的第二项则是对左右图中遮挡区域的惩罚，定义如式（6）所示：

其中，OccR是在右图中被遮挡的点，OccL是左图中被遮挡的点，而λocc则是对于所有遮挡的一个惩罚常数。

3.实验结果与分析

实验计算机采用的是联想公司Y470型笔记本，下面将选取Tsukuba和Satellite Model两组立体像对进行实验，分别运用上述三种算法进行匹配，并对实验结果进行相应的分析。

3.1 Tsukuba立体像对匹配实验

Tsukuba立体像对（如图4所示），图像像素尺寸为384px ×288px，格式为jpg，经过SGBM、BM、GC三种匹配算法处理所得深度图（如图5所示），影像匹配时间（如表1所示）：

图4 Tsukuba立体像对

图5 Tsukuba立体像对匹配结果

表1 Tsukuba立体像对匹配时间表

3.2 %Satellite Model立体像对匹配实验

Satellite Model立体像对（如图6所示），图像像素尺寸为640px × 512px，格式为bmp，经过SGBM、BM、GC三种匹配算法所得深度图（如图7所示），影像匹配时间（如表2所示）：

图6 Satellite Model立体像对

图7 Satellite Model立体像对匹配结果

表2 Satellite Model立体像对匹配时间表

3.3 实验分析

综合比较以上两组实验结果，可以发现：

（1）在处理速度上，BM匹配算法最快；SGBM匹配算法次之，其耗时约是BM匹配算法的3—5倍；GC匹配算法最慢，耗时甚至会达到BM匹配算法的100倍以上。

（2）在处理效果上，BM匹配算法处理的深度图中，场景物体轮廓模糊，表面清晰度差，变形严重，存在较多误匹配区域，效果较差；SGBM匹配算法比BM匹配算法具有更好的处理效果；GC匹配算法成功恢复了场景中对象的形状，尤其是在Satellite Model立体像对中对于卫星模型和火箭模型形状的恢复很成功，场景层次清晰分明，对象轮廓清晰，表面光滑，匹配效果最好。

（3）在应用领域上，BM匹配算法适用于对处理效率期望高但对处理效果要求不严格的情况，可用于实时动态匹配，如移动视觉跟踪和加工制造监控等；SGBM匹配算法适用于对处理效果和处理速度均要求较高的场合，如武器打击系统、医学影像分析、机械制造检测等；GC匹配算法，适用于目标或场景的精细三维建模，如精密器件加工、高精度测绘、高精度仿真建模等。