一种基于LSD改进的室内直线特征匹配算法

李玉峰，张 宸

（沈阳航空航天大学电子信息工程学院，沈阳 110000）

0 引言

随着计算机技术的进步发展，计算机视觉凭借其成本低、适用场景多的特点而被国内外广泛关注应用，包括图像检测、图像配准、图像拼接、三维重建技术，上述技术已经被广泛应用到遥感图像、医学图像、自动驾驶等领域。特征检测与匹配在其中起到了不可代替的作用。基于特征的匹配方法可以对有遮挡、旋转、缩放等图片进行快速良好的匹配，因此是目前图像匹配中主流的研究方法。

基于特征的图像匹配方法，是在模板图像和待匹配图像中提取特征，然后根据二者的相似性进行匹配，目前基于特征点匹配的方法有SIFT 算法、SURF 算法、Harris 角点检测法等。其中SIFT 算法可谓是最著名的特征点提取算法之一，但由于其特征提取过程需要大量时间，算法整体运行效率难以满足实时需求。近年提出的ORB 算法不但继承了SIFT 算法的旋转尺度不变性，还对计算流程进行了优化，使得运算效率更高，可更快地完成图像精确匹配，因此ORB 算法被广泛应用到各种计算机视觉实时系统中。但上述这些算法全部是基于点特征对图像进行匹配，如果在室内长廊等弱纹理场景下，通常空间结构简单，点特征难以提取且分布不均匀；相反这些场景存在很多直线，并且这些直线段特征对视角和光照变化具有很好的鲁棒性，通过少量的线段即可勾勒出空间的整体结构。因此直线匹配就成为室内长廊等弱纹理场景中新的研究热点。Bose 等人利用图像的深度信息简化了边缘检测计算量，提高了算法运行效率，但算法过于依赖深度图像，在深度摄像头未普及的情况下很难推广应用。目前主流的直线特征匹配算法是文献［4］提出的LSD算法。其算法通过对图像的灰度进行求导得到的梯度提取出直线，具有良好的特征提取能力。但LSD 仍存在一些问题，如重复提取特征线段、特征线段断连、长度过短的无意义线段。后来Akinlar等又提出了EDLines 算法，基于像素之间的梯度幅度变化进行线段检测，并且可以实时得出结果，适用于需要实时性的系统。但由于EDLines算法中判断线段的机制，导致图像中较长边缘处容易出现特征线段断连的问题。

针对上述问题，研究提出了一种基于LSD改进的算法Light-LSD，通过对线段起始点以及各线段之间距离进行分析，将断连线段重新进行连接，并剔除重复提取的冗余特征线段，最后根据自适应阈值剔除没有特征表现力的低质量线段。实验表明，改进后的算法有效剔除了大量冗余特征线段并能够保留大部分具有特征表现力的线段，减少计算负担提高算法计算效率。

1 LSD算法介绍

1.1 算法思想概述

LSD 是一种可以在线性时间内达到亚像素级别精度的直线检测算法，并且在实际运用中不需要任何参数设置，所以在各种直线检测场景下得到广泛运用。

在LSD 算法中，Gradient 梯度和level-lines是最重要的两个概念，如图1所示。

图1 Gradient和Level-Line

通过计算图像中每个像素的梯度得到每个像素的level-line，进而得到一张由每个像素level-line 构成的图，称之为Level-line Field。如果其中部分level-lines 之间相互的角度差都不大于一个容忍值π，那这些连接组成的区域被叫做line support regions，如图2所示。

图2 line support region与外接矩形

而每一个line support region 又是line segment 的候选，line-support region 的边缘被矩形所包围，其方向由line-support region 的惯性主轴所决定。矩形中level-line 角度与矩形角度差小于容忍值2π 的像素被称为aligned points，如图3 所示。一个line support region 中像素总数量和其中aligned points 的数量被用来评价是否可以被认定为是一个line segment。

图3 Aligned points示意

如果在所有被算法判定为aligned points 的像素外围接一个矩形框，这个矩形框就是被检测出的线段特征。并且LSD 算法还会采用Region Grow 算法对检测出的线段特征进行增长，以确保最大程度提取出图像中的线段特征。Region Grow 会从被标记为UNUSED 的有序像素中取一个像素作为起始点，并将其像素的levelline 角度定义为region angle（区域角度），接着递归地计算其邻居像素的角度和region angle（区域角度）的差值，如果差值小于容忍值τ，那么将该像素标记为USED，并且按照下面公式更新区域角度，其中是在区域范围之内的。

在图4中我们可以看出很多直线特征因为数字图像像素点的缘故都存在锯齿效应，导致检测出的特征出现断连或者漏检测现象。

图4 锯齿效应及其带来的误差

因此LSD 算法对图像像素进行梯度计算之前，还会有一步预处理，通过高斯上采样对图像进行模糊处理，尽量消除锯齿效应带来的影响。图5展示了同样的输入图像在经过高斯上采样处理后算法效果得到了显著提升。

图5 上采样优化后的结果

1.2 LSD算法具体流程

（1）对图像进行二值化处理得到灰度图，并以采样率=0.8对图像进行上采样。

（2）针对图像中每个像素计算其梯度值和方向，然后根据梯度值进行升序排列。

（3）根据设置的阈值，将梯度小于的像素点添加一个USED 状态，其他像素点添加为UNUSED。

（4）根据设置的最大容忍值τ 进行区域生长Region Grow。

（5）计算通过Region Grow 算法得到的新区域的同性点密度

（6）根据截断阈值。如果密度<，重新截断直至满足条件；如果密度>，计算错误控制函数NFA。

（7）根据错误控制阈值，如果<，输出直线段数据。

（8）查看排序表是否还有UNUSED 的点，如果有，跳转至步骤（4），否则结束程序。

2 Light-LSD算法设计与实现

2.1 改进算法重要概念

在新提出的改进算法中，有一些概念至关重要。

如图6所示，由于室内长廊的空间线条多为竖直方向的，所以设定Y表示线段特征的与竖直方向的偏离程度，已知线段起点坐标为（,），终点为（,），那么new gradient由下式计算得出。

图6 Gradient计算图示

如图7 设定坐标值较小的线段为低位线段，坐标值较大的线段为高位线段，且线段的方向皆是从低位到高位，如图7所示。

图7 高低位线段

new distance 表示两特征线段之间的竖直距离，如图8所示。

图8 new distance示意

在后续处理中还需要判断两条线段特征是否重叠，在改进算法中我们依照图9 规定重叠情况。

图9 两线段排列的三种方式

如果符合图中情况（a），两特征线段在Y 轴上的投影没有重合部分，我们称两特征线段不相交；如果符合情况（b），两特征线段在Y 轴上的投影有部分重叠，我们称两特征线段相交；如果符合情况（c），其中一特征线段在Y 轴上的投影被另一特征线段在Y 轴上的投影完全覆盖，我们称两特征线段相包含。

特征线段的可信率代表线段是有效线段的概率，由下式计算得出：

其中为当前特征线段长度，max 为最长特征线段。可信率越高，代表特征线段长度越长，越有可能是一条完整描述物体特征的线段；可信率越低，代表特征线段很短，越有可能是一条对物体特征描述不完整的短线段。根据反复实验中产生的经验阈值0.75 进行筛选，所得线段能较好地描述图像中物体特征。

2.2 Light-LSD算法设计思想

针对室内长廊场景下存在大量垂直线段特征，改进算法的主要任务就是用尽可能少的线段特征描述出室内结构，原版LSD 造成大量冗余线段特征的原因是大量长短不一的短线段描述了图像中的同一处线特征。如图10 所示，原版LSD 会在图像中物体边缘处产生多条短线段，但理想情况下只应该有一条长线段紧紧贴合物体边缘处完整地描述物体的边缘。

图10 LSD算法效果和理想效果对比

Light-LSD 是在LSD 算法的基础上，对LSD提取出的特征线段进行合并、剔除处理，以求达到用少量必要的线段描述出完整的物体边缘特征。对于LSD 提取出的大量聚集堆叠在一起的特征线段，首先两两计算线段的距离和角度，如果距离很近角度方向相似，那么判定两条线段在描述同一个物体边缘特征，对其进行合并、剔除操作。对LSD 提取出的所有线段进行如上操作，最终一束聚集的短线段会被合并成一条完整的长线段，大大减少了特征线段的数量，为下一步特征匹配减轻了资源消耗，进而提升算法整体效率。

2.3 Light-LSD算法流程

（1）计算各个特征线段的竖直梯度Y（new gradient）；

（2）取第一个特征线段作为线段，依次计算和其他特征线段的距离和角度差；

（3）如果距离小于阈值且角度差也小于阈值，那么进入步骤（4），否则跳至步骤（9）；

（4）判断、两线段的重叠程度，如果是情况1，进入步骤（5）；如果是情况2，进入步骤（6）；如果是情况3，进入步骤（7）；

（5）将低位线段的终点重新赋值成高位线段的终点值，并删除高位线段；

（6）将低位线段的终点重新赋值成高位线段终点值，并删除高位线段；

（7）直接删除高位线段；

（8）对所剩线段计算可信率，并根据可信率由高到低排序；

（9）根据可信率阈值进行最终筛选；

（10）输出特征线段进行剩余匹配流程。

3 实验结果

3.1 数据集介绍

本实验采用自建数据集进行实验，其中图片来自于酒店或写字楼室内走廊拍摄视频中截取的多帧图像。这些图片中的场景大多包含明显的线特征，并且有着不同的色彩、角度和光照条件，便于测试对比两种算法的效果。如图11所示。

图11 部分数据集展示

3.2 实验结果

图12是原版LSD对于图像的特征匹配效果。

图12 LSD实验结果

图13是改进后的LSD特征匹配结果。

图13 Light-LSD实验结果

可以看出LSD 提取出了大量的线特征，但在门框边缘处，存在着大量的长度相似，距离接近的线段。如下图所示截取了对比实验结果图的左下角部分，可以看出有多条特征线段被描绘在门框边缘，这些线段描绘的是同一条空间特征，属于重复描述。并且这些线段长度并未完全覆盖门框特征，也属于不完整描述。图14 为算法改进前后的同一处细节结果，通过对比观察可以明显看出，改进LSD 提取出的特征线段更长、更简洁，可以用数量更少、质量更高的线段描述出门框的特征。

图14 实验结果局部对比

图15 展示了更多实验结果中的局部特征提取效果对比。

图15 部分对比实验结果

此外在实验中还统计对比了原LSD 和改进LSD的运行效率，如表1所示。

表1 LSD与Light-LSD算法在部分实验图像上的性能对比

冗余特征消除比例按照下式计算，其中代表原版LSD 提取特征数量，代表改进LSD提取特征数量。

效率提高比例按照下式计算，其中代表 原 版LSD 计算 时 间，代 表改进LSD计算时间。

4 结语

本文提出了基于LSD 改进的线特征提取算法Light-LSD，实验表明该算法在室内长廊等场景下运行效果良好，能完整地提取出图片中主要的线段特征，并且相较于原版LSD，Light-LSD能剔除60%～80%的冗余线段特征，减少匹配过程中的计算资源消耗，在特定场景下的算法运行效率可提升高达30%，对SLAM等依赖特征匹配算法的研究领域有重要影响意义。