基于Edline线特征的图像快速匹配算法∗

张 震 王永雄

（上海理工大学光电信息与计算机工程学院 上海 200093）

1 引言

图像匹配是根据不同视角或者不同传感器获得的图像，提取图像中的相关信息，如纹理、灰度、结构等的相似性，通过一定的匹配算法将两幅或者多幅图像进行匹配。图像匹配是计算机视觉领域中的研究热点，高精度的图像匹配和低的时间计算成本能够更好地应用在行为识别［1～3］与 VSLAM［4～7］（Visual Simultaneous Localization And Mapping）等算法当中。图像匹配算法主要可分为以灰度［8］和特征［9］为基础的图像匹配方法。其中基于特征的匹配算法，对图像中的物体旋转、光照变化和遮挡等方面具有更好的鲁棒性。基于灰度信息的图像匹配算法，一般通过利用相关函数、协方差函数等测量极值进行匹配，能够获得较高的匹配精度。由于灰度信息对光照变化敏感，因此基于特征的图像匹配作为主要的研究方法。

SIFT［10］由于其旋转和尺度不变性等，受到研究者们广泛的关注，常用于特征的图像匹配，但是在SIFT特征点提取过程中占用了很长的时间，因此导致匹配时间较长，难以进行实时性的应用。最近提出的ORB［9］特征点，不仅具有SIFT的旋转、尺度不变性等性质，而且具有较低的时间成本，能够快速地得到精确图像匹配对，因此研究者们将其应用在VSLAM当中，得到很好的效果。但是针对于点特征，当环境中特征点缺乏或者分布不均匀时，难以提取到能够准确代表环境信息的高质量的特征，这样使得无法获得高精度的图像匹配，难以在实际中得到应用。而且目前大多数的基于特征的图像匹配算法难以同时满足较高的实时性和准确性，且随着光照的变化和特征分布不均匀的场景的出现，图像匹配出现较高的错误率，难以在实际应用中得到良好的表现。

由于在室内环境中包含丰富的线特征，并且检测的边缘和线段特征对于自然界的光照变化并不敏感。为了在一些低纹理环境中如光滑的走道墙壁等，能够得到高精度的图像匹配，李海丰等［11］使用了点和面特征来进行图像匹配，而这种方法在平面环境中会有较好的表现，但是在非平面环境中，错误率很高。近几年，很多研究将边缘［12～14］信息应用在图像匹配中，例如Bose L［12］等提出利用一种基本的边缘检测算法，首先对先前深度图像进行深度边缘检测，所获取到的信息来确定当前深度图像边缘的区域，虽然这种方法与在整个深度图像上进行边缘检测搜索相比，节省大量计算成本，但是边缘检测完全依赖于所获得的深度图像。虽然室内环境中包含丰富的线特征，但是难以提取到高质量的线段信息，因此大多数线特征便只能应用在激光扫描仪［15］上。为了能检测和提取到高质量的线段信息，大多数线段匹配的研究发现使用一些策略交叉线段以形成交叉点，利用这种交点和线段之间的关系进行匹配，会得到不错的匹配效果。例如Zhang等［16］利用外观相似性和几何约束来进行线段匹配，Li K等分别提出一种Ray-Point-Ray［17］结构描述符和 Line-Junction-Line［18］结构描述符进行线段的匹配，均取得很高准确度的匹配效果，但是，这些线段提取和匹配方法，提取过程复杂，而且具有很高的时间计算成本。因此，为了降低时间成本，同时能够得到更多的高精度图像匹配对，在实际应用中有良好的效果，提取高质量的线特征至关重要。

综上所述，本文针对以上问题，对图像匹配提出一种基于Edline线特征的图像快速匹配算法。首先利用边缘检测算法进行边缘绘制，产生像素链，从像素链中进行线段的提取，并通过设置线段长度进行阈值参数，来构建完整连通的线特征，并利用RANSAC［19］算法去除掉异常线特征，以此减少计算时间。构造线段描述符进行匹配。通过与LSD（Line Segment Detector）［20］和 LBD（Lind Band Descriptor）［21］线段提取的方法在时间和效果上进行对比，本方法不仅在低纹理和结构化场景中能够获取高精度的图像匹配，而且在实时性上均有良好的表现，可在行为识别或VSLAM中得到良好的应用效果。

2 算法原理

基于Edline线特征的图像匹配算法主要由Edline线段的提取描述和匹配。Edline线段提取描述分为：线段的检测和提取，利用LBD描述子对所提取的线段进行描述和匹配。其结构流程图如图1所示。虽然对于在低纹理和结构化场景中，线特征表现丰富，但是线特征往往会存在线段稳定性和连通性较低的问题，因此利用线段长度阈值参数设置，来增强线特征的连通性和完整性，以此提升在图像匹配中的性能。

图1 结构流程图

3 Edline线特征提取算法

在低纹理场景下线特征表现优异，但是当缺少线特征之间的关联信息差异时，会产生很多异常的线段，从而影响图像的匹配效果。为了得到良好的匹配效果，本文提出了一种改进的低计算量的线段提取方法，首先利用边缘检测，再利用边缘检测算法进行边缘绘制，并产生连续的像素链；其次通过最小二乘线拟合的方法，从连续的像素链中提取线段；最后利用设置线段长度阈值参数和RANSAC算法消除错误的线段。其过程如图2所示。

传统的线段提取算法，通常提取出独立、不相交、不连续的线段。Edline线段提取算法：首先对平滑处理后的图像计算其图像的梯度大小和方向。某一像素点上的总梯度大小为

图2 线特征提取过程

其中Gx，Gy分别表示水平和垂直方向的梯度值。

通过比较在每个像素的水平和垂直的梯度大小来定义锚点，阈值的设置间接的反应锚点的数量，以及边缘的绘制。通过连接锚点构造像素链，算法过程如下：首先初始选择一个起始点（x，y），当水平边缘通过该点时，通过比较（x，y+1），（x，y），（x，y-1）三点处的像素梯度值，最大点定义为锚点（X，Y）；若水平边缘通过该点（X，Y），则比较（X-1，Y+1），（X-1，Y），（X-1，Y-1）处的像素梯度值，选择最大值，与（X，Y）相连，直到点（Xi，Yi）不是边缘像素时。

对构建的像素链，利用最小二乘线拟合的方法，进行线段的拟合提取，采用偏差绝对值之和最小的原则进行拟合：

其中xi，yi是像素点坐标。对拟合的线段，计算线段长度，以及线段端点的位置，通过计算两条相邻线段端点的欧式距离，并设置阈值参数，来构建完整连通的线段，使用RANSAC算法来剔除异常线段，同时根据两线段在方向和距离上的差异，通过设置线段中点间的距离阈值，以及方向差大小来合并两条线段。

4 构造描述子

对线段进行提取后，构造线特征描述子，采用LBD描述符进行匹配，进行线特征的匹配，首先对提取的特征进行预处理，消除无法匹配的线特征，降低匹配的维度，其过程分为：条带表示线段支持域和条带描述子的构建。首先对图像构建尺度空间金字塔，在每层尺度空间提取线段。通过检测几何属性以及局部外观相似性，来减少匹配的维度，加快匹配的速度。在每一层空间中都能获得一组线段，将尺度空间中线段进行重组，相对应的线段在同一LineVec中。

4.1 线段支持域

线段描述符由线段支持域计算得到，利用条带{B1;B2;…;Bm}的形式表示，m为条带的数目，w是每个条带的宽度。引入构成局部二维坐标系dl，d⊥，将线段支持域中的点像素的梯度投影局部二维坐标系：

其中g为像素点梯度，g'为局部坐标系中的投影像素。引入全局高斯函数来缓和在线段垂直方向上微小变化的敏感度，以及引入局部高斯函数降低边缘效应，避免描述符的突变。

4.2 构造条带描述符

利用定义的线段条带构建条带描述子，计算每一个条带的描述符BDj，由它的两个相邻条带Bj-1和Bj+1构成。LBD描述子由条带的描述子{BDj}组成：

其中条带的描述子BDj是条带Bj的第k行像素的梯度值，对于条带中某一行，累积该行中四个方向上像素的梯度：

k表示在条带 Bj的第k行；高斯权重 λ=fg（k）fl（k），则某一行像素有四个方向的梯度，通过累计条带条带Bj相关联的所有行的梯度信息，构造第j个条带的描述符矩阵，计算BDj由BDMj矩阵的平均向量Mj和标准方差向量Sj，通过对LBD的均值和标准方差部分分别进行归一化，同时对每个LBD维度进行约束，得到单元LBD。

5 实验结果和分析

5.1 数据集

本实验采用了视觉SLAM领域中权威数据集中的多帧图像进行实验，有KITTI，TUM RGB-D。KITTI是目前国际上最大的自动驾驶场景下的计算机视觉算法评测数据集。该数据集用于评测立体图像（stereo），光流（optical flow），视觉测距（visual odometry），3D物体检测（object detection）和3D跟踪（tracking）等计算机视觉技术在车载环境下的性能。包含市区、乡村和高速公路等场景采集的真实图像数据，每张图像中最多达15辆车和30个行人，还有各种程度的遮挡与截断。整个数据集由389对立体图像和光流图，39.2 km视觉测距序列以及超过200k 3D标注物体的图像组成。TUM RGB-D是包含了RGB-D数据和地面实况数据的大型数据集，为视觉测距和视觉SLAM系统的评估建立新的基准，并且包含Microsoft Kinect传感器沿着地面实况轨迹的颜色和深度信息，全帧速率30Hz，传感器分辨率为640×480，提供不同类别的图像数据：手持式SLAM，结构与纹理，动态对象，三维物体重建等。如样本（a）是TUM RGB-D是数据集中的一帧图像，记录一个办公场景办公桌环境，有一张桌子，一台传真机，一台固定电话，一个键盘等，其中场景特征丰富。样本（b）是TUM RGB-D数据集中一帧图像，记录室内墙壁环境，包含三脚架，墙壁等，其中特征缺乏。样本（c）是KITTI数据集中的一帧图像，记录室外道路上场景，包含建筑物，马路，树木等，特征分布丰富。

5.2 实验分析

光照条件的变化、无纹理表面等都将影响视觉SLAM中的匹配。为了证明本方法能够在低纹理和特征不丰富的场景中有效地进行匹配运算，我们将本方法应用于多个数据集进行验证，所用实验设备为Inter Core i7-6500U和16 Gib RAM。我们采用了KITTI和TUM中的数据，选取有一定角度视差的两帧图像，分别在点特征丰富和特征不丰富情况下进行实验。匹配效果如图3所示。

图3 线匹配

由上述匹配结果可以看出，在特征丰富的环境如图3（a）中，线特征能够很好地提取和匹配，能够得到精确的线匹配对。在一些结构化特征不丰富的场景（如图3（b））中，当遇到空白的墙壁时，难以提取到特征，但是在三脚架上仍然能够得到精确的匹配对。低质量的特征提取与匹配将降低VSLAM的性能，匹配数量如表1。为了验证提出的方法计算复杂度，表2、表3列出不同场景中所用时间数据。

表1 特征提取匹配对数量对比

表2 特征提取、描述和匹配时间占比

表3 不同检测匹配时间对比

从以上3个表格中可以看出：在样本（a）中，线特征相对丰富，检测匹配方法在样本（a）中能获得足够的匹配对数，但所需时间为47.66ms，相比使用ORB特征点、LSD+LBD中缩短了10.67%、54.79%。特别在样本（b）中，本文的方法不仅能够提取到比ORB更多的精确匹配对数，此时难以提取到足够的点特征，而且在时间上缩短了5.15%。在样本（c）中，虽然时间上有所增加，但是同样能够获得足够的精确匹配对数。在样本（b）当中，由于点特征的缺乏，无法提取和获得足够多的特征点匹配对数，但是线特征能够良好地检测和匹配出来，能够在样本（b）中获得足够的线特征匹配对数，并且相比较使用传统的LSD+LBD的方法，无论在运行时间还是匹配对数上均表现优势。通过这些比较，验证了我们方法的实时性，能够大幅地提高图像匹配能力，有利于提高视觉SLAM的后续定位和建图。

综上，本文提出的方法对于特征丰富的场景实时有效，在一些低纹理和特征不丰富的场景中，难以提取到足够的点特征，此时能够生成足够高质量的线特征匹配对，并且在实时性上明显优于传统的线特征方法。

6 结语

本文针对非结构化和点特征缺失场景中提出了一种改进的Edline线特征的图像快速匹配算法。该方法弥补低纹理和特征分布不均匀环境下点特征的不足。采用Edline线特征可应用在低纹理环境或者复杂结构场景下，通过使用RANSAC算法和线段长度参数阈值设置，构建完整的线段，优化了匹配算法，提升了算法实时性。利用稳健的LBD描述子，能够获得高准确度的图像匹配效果，并在实时性上达到了良好效果。