【泡泡图灵智库】基于线段的高效大规模立体匹配（ICRA）

会员服务 ·

【泡泡图灵智库】基于线段的高效大规模立体匹配（ICRA）

2019 年 5 月 3 日 泡泡机器人SLAM

泡泡图灵智库，带你精读机器人顶级会议文章

标题：LS-ELAS: Line Segment based Efficient Large Scale Stereo Matching

作者：Radouane Ait-Jellal, Manuel Lange, Benjamin Wassermann, Andreas Schilling and Andreas Zell

来源：ICRA 2017

编译：李鑫

审核：夏友杰

欢迎个人转发朋友圈；其他机构或自媒体如需转载，后台留言申请授权

摘要

大家好，今天为大家带来的文章是——LS-ELAS: Line Segment based Efficient Large Scale Stereo Matching, 该文章发表于ICRA 2017。

本文提出了LS-ELAS，它是ELAS算法基于线段的扩展，提高了算法的性能和鲁棒性。LS-ELAS是一种双目稠密立体匹配算法，它在恒定的时间内计算图像的大部分像素的视差和在线性时间内计算一小部分像素点（支撑点，support points）。作者的方法是基于线段来确定支撑点，而不是在图像中均匀的选择支撑点。通过这种方法，作者找到了信息丰富的并且提供了不同深度值的支撑点。贝叶斯立体匹配方法的先验则是基于一组线段和一组支撑点。这两个集合都被插入到一个带约束的Delaunay三角剖分中，用来生成一个三角剖分网格，这个网格能够感知可能的深度值。同时作者采用自适应方法对边缘线段上的候选点进行采样，进一步提高了精度。

主要贡献

1. 提出了一个高效的边缘提取算法，同时提供了边缘之间的连通性；

2. 提出了一种新的基于边缘特征的支撑点匹配计算方法；

3. 提出了一种新的基于贝叶斯先验的推理方法。本文的先验更好地表示了给定支持点集、线段集和观测值的视差概率分布；

4. 提出了一种自适应的基于线段的支撑点采样方法。

算法流程

图1 本文线段提取的中间步骤。（b）图是dirMap（表示了梯度方向）；（c）图是边缘图；（d）图表示的是最终的边缘集合。

在这部分中，作者详细描述了提出的算法。首先介绍了他们算法中提取线段的部分和计算支撑点集以及线段集的计算方法。然后介绍了立体问题的贝叶斯方法的数学推导。

1. 快速线段检测

在ELAS中候选支撑点的选取是从整幅图像中均匀选取的。用这种方法的原因是希望可以得到一种高效的计算支撑点的方法。在本文中，作者提出了一种新的基于线特征来提取候选支撑点的新方法。这种方法源于作者高效的边缘提取方法。作者表明他们计算支撑点匹配的方法鲁棒并且高效。除此之外，这种方法还可以利用两个连续支撑点之间的线段来生成一个更好的三角剖分结果。

作者快速线段检测的方法和Canny线段检测的方法很类似，（这里不赘述Canny线段检测的方法了，如果有想了解的可以详细看论文）但是传统的Canny算法只提供了一个没有边缘成分连接的像素边缘图。作者希望有一个可以提供线段分类特征的包含所有像素点的数据结构。所以作者对Canny算法进行了如下的改进：

1）在Canny算法的第三步中需要知道每个像素的梯度方法。在快速算法中计算出8中可能的领域像素的粗略近似值。然后这些信息将被存储在一个映射表中以供后续使用。

2）在作者的方法中，所有低于低阈值的边缘响应都被标记在一个边缘映射中。超过高阈值的边缘响应都被存储在一个种子列表之中。

3）Canny算法中的滞后边界跟踪被替换成了联通边缘分量搜索。

图2 （a）图是Middleburry数据集中的一张图片，选择红色的部分做后续讨论；（d）是红色区域；（b）是用本文方法提取的线段；（c）（e）（f）显示了候选支撑点（红色和绿色）和有效支撑点（绿色）；（c）图是使用本文算法的结果；（e）（f）是使用ELAS方法分别使用10和5个像素点的结果

2. 快速支撑点匹配

计算支撑点的过程如图2所示。作者首先使用线段来采样候选支撑点。一个候选支撑点包括来像素坐标（u，v）还有视差d。然后如图3所示，使用一个32位的特征向量对特征点进行描述。之后使用绝对值误差来进行匹配，同时使用左右一致性来滤除外点。

关于候选支撑点的采样方法，作者提出来两种不同的方法来采样候选支撑点。在作者第一种方法中，他们沿着边缘均匀的采样候选支撑点。一个固定的步长被分隔成两个连续的候选支撑点。这个固定的步长是从图像的对角线长度中计算出来的。作者还提出了一种更优雅的采样支撑点的方法。这种采样方法是一种自适应的方法。因此作者在曲线部分比在直线部分采样更多的点。作者使用一个迭代的处理过程，沿着边缘采样并且考虑以最近采样的候选支撑点为开始以当前的点为终点的直线。当”弯曲“（任意一个从当前选中部分选取的点到位于当前起始点和当前点之间的直线上的投影距离）超过某个阈值，则设置一个新的候选支撑点。这个点则是下一个步长的新开始。当曲率较低的情况下，作者也使用一个固定步长设置新的候选支撑点。过程如图4所示。

图3 特征向量中32个不同的元素在X方向的Sobel梯度图（左图）和Y方向的Sobel梯度图（右图）中的位置。候选支撑点在图像的中心。

图4 自适应采样方法的示例。

3. 视差图的贝叶斯推论

3.1 基于带约束的Delaunay三角剖分的先验

作者通过在概率模型中加入直线段的约束扩展了Geiger等人在ELAS中提出的贝叶斯的方法。两个连续的匹配上的支撑点之间的曲线被近似成直线段。将匹配上的支撑点集合和线段集合插入到带约束的Delaunay三角剖分算法中，用来计算一个三角网格。图5是本文方法生成的网格的示例。

图5 （a）是使用本文的方法生成的2D网格；（b）是使用本文的算法（LS-ELAS）生成的视差图

3.2 最大后验估计

深度图的最大后验估计由下面的方程给出

深度是基于支撑点集S、线段集L和目标图像的观测o。

主要结果

1. 在Middlebury数据集上评估算法

作者在Middlebury双目评估数据集上进行实验来评估本文提出的LS-ELAS算法，评估的结果标注为LS-ELAS，用来和其他算法进行比较。

表1 在Middlebury双目数据集上的表现评估，Bad 2.0

表2 在Middlebury双目数据集上的表现评估，时间s/MP

表3 在Middlebury双目数据集上的表现评估，LS-ELAS和ELAS的比较

2.LS-ELAS和ELAS的比较

作者先在支撑点匹配部分比较了两种算法，然后在MiddleBurt基线上比较了整个算法，具体的表现如下图、表所示：

图6 X轴：不同的数据集，Y轴：计算支撑点花费的时间(ms)

图7 在不同分辨率下计算支撑点需要的平均时间(ms)

表4 有效支撑点的比例

Abstract

We present LS-ELAS, a line segment extensionto the ELAS algorithm, which increases the performance androbustness. LS-ELAS is a binocular dense stereo matchingalgorithm, which computes the disparities in constant timefor most of the pixels in the image and in linear time for asmall subset of the pixels (support points). Our approach isbased on line segments to determine the support points insteadof uniformly selecting them over the image range. This waywe find very informative support points which preserve thedepth discontinuity. The prior of our Bayesian stereo matchingmethod is based on a set of line segments and a set of supportpoints. Both sets are plugged into a constrained Delaunaytriangulation to generate a triangulation mesh which is awareof possible depth discontinuities. We further increased theaccuracy by using an adaptive method to sample candidatepoints along edge segments.

如果你对本文感兴趣，想要下载完整文章进行阅读，可以关注【泡泡机器人SLAM】公众号。

点击阅读原文，即可获取本文下载链接。

欢迎来到泡泡论坛，这里有大牛为你解答关于SLAM的任何疑惑。

有想问的问题，或者想刷帖回答问题，泡泡论坛欢迎你！

泡泡网站：www.paopaorobot.org

泡泡论坛：http://paopaorobot.org/bbs/