基于多尺度多分辨率的直线段检测算法

唐守锋，范梦松，赵仁慈，翟少奇

（中国矿业大学信息与控制工程学院，江苏 徐州 221116）

0 引 言

同步定位与地图构建（simultaneous localization and mapping，SLAM）是计算机视觉和机器人领域的热门研究方向，是移动机器人的自主定位导航的关键技术。视觉SLAM需要将观测到的图像信息同环境进行数据关联，其中，点特征经常被用于数据关联。但在具有均匀墙面的室内环境或者较大面积玻璃窗的办公室内等弱纹理场景下，会造成特征点提取失败或者特征点数目不足等情况，导致算法性能下降［1～3］。

为了解决上述问题，一些学者提出：针对弱纹理场景，在点特征的基础上加入线特征，即点线特征融合的视觉SLAM系统。相比于点特征，线特征受纹理重复等环境问题的影响小，在低纹理的环境下数量也足够丰富，同时线特征在人造环境中，可以提供环境的结构信息。近年来，一些新的直线段检测（line segment detector，LSD）算法被提出，比如Gioi R等人［4］提出了一种快速的LSD算法，该算法具有参数自适应能力，并且在检测结果上有了很大的提高，但是在线段检测的过程中，容易产生过度分割情况，导致线段的冗余；Akinlar C 等人［5］提出的边缘绘制直线段（edge drawing lines，EDLines）检测算法能够在非常短的时间内给出比较准确的LSD结果，但存在丢失细节的状况；Almazan E J等人［6］提出的马尔可夫链边缘LSD（Markov chain marginal LSD，MCMLSD）算法能够检测到更为完整的直线段，但该算法运行速度比较慢等。本文提出多尺度多分辨率LSD（multi-scale multi-resolution LSD，MMLSD）算法。该算法对输入图像进行分辨率阈值处理，针对高、低分辨率图像采用不同的方式构造图像金字塔；线段合并阶段，采用一种由粗略尺度到精细尺度的线段替代合并方法，加速短线段合并，提高系统的运行效率。

1 整体算法流程

本文设计的改进算法，主要由3个部分组成：图像阈值判断与金字塔构造、LSD 以及短线段合并。主要的改进在金字塔构造和短线段合并部分。对系统输入的图像进行阈值判断后，将尺度和分辨率有效结合，构建多尺度的图像金字塔，在此基础上进行LSD，然后从高尺度的粗略线段开始逐级向下进行线段的融合，最终输出图像线段提取的效果。

2 MMLSD算法

2.1 多尺度图像空间与图像金字塔构造

MMLSD算法针对单目相机采集的图像序列，执行多尺度空间以及图像金字塔构造。如图1，首先，对系统输入图像进行灰度化处理；然后，对灰度图像的分辨率进行判断，对低分辨图像进行高斯模糊处理，构造多尺度图像空间；对高分辨率图像的处理分为2步，第一步进行高斯模糊处理，第二步进行下采样处理，构造图像金字塔。

图1 多尺度图像空间和金字塔构造流程

2.1.1 低分辨率图像

针对系统输入低分辨率图像，灰度化处理后进行高斯平滑处理，达到模糊图像和消除噪音的效果。图像的高斯尺度空间L（x，y）是由高斯G（x，y）与输入图像I（x，y）的卷积定义的函数组

式中 *为卷积运算符；σ 定义为尺度大小，当σ 越大，尺度越大，即模糊程度越高。

MMLSD算法利用OpenCV中高斯模糊函数处理图像，形成多尺度空间。使用一个大小为5 ×5 的卷积核，其中，σ1＝0.6，σ2＝0.6，σ3＝0.6。根据设定参数，利用高斯函数与输入图像进行卷积，即

得到平滑后图像L1，同理得到图像L2，L3。图1展示了针对低分辨率不同尺度的高斯平滑处理后图像的局部图效果。

2.1.2 高分辨率图像

首先，进行灰度化处理；然后，高斯平滑处理同2.1 节中的步骤；最后，对高斯平滑处理之后的图像进行下采样操作，即构建图像金字塔。由2.1.1 节得到的3张图像L1，L2，L3，将L2，L3分别缩放至原图像的90%，80%（这里的90%，80%的缩放分别意味着x轴和y轴均减少到90%，80%，像素数量减少到81%，64%），这种缩放有助于处理许多图像中存在的混叠和量化伪像（尤其是阶梯效应）。

2.2 LSD

对系统生成的多尺度空间或多尺度多分辨率图像金字塔每层都执行LSD。其具体流程如图2所示。对于梯度计算和区域生长采用与LSD一样的方法。在矩形近似阶段，LSD［7］中将矩形的长度和宽度设置为包含整个线段支持域的最小值，即最小外接矩形。本文算法在最小外接矩形的基础上，另外增加一个矩形，以最小外接矩形的中心为基点，矩形中心如式（3）和式（4）所示，方向为最小外接矩形的方向，定义一个宽度为1像素，长度与最小外接矩形的主方向长度一致，将2 个矩形定义为一组。则在进行验证矩形区域是否为直线段时，本文算法采用2层验证，提高系统的精确度，并为线段合并工作提供基础。

图2 LSD流程

矩形的中心（cx，cy）

式中G（j）为像素点j的梯度大小，j的取值范围为线段支持域R内。

矩形的角度被设置为与矩阵的最小特征值相关联的特征向量的角度，即

矩形区域内像素点数量k和内点数量p的比值，作为判断矩形区域是否为线段的标准。本文算法使用误报次数（number of false alarm，NFA）判断图像中的候选矩形少于相同位置矩形里的内点的数量的概率，则线段s的NFA定义为

式中NL为图像中可能出现的矩形的数量，γ 为归一化值，B（n，k，p）为二项式的尾部

针对每对矩形计算出2个NFA值，当且仅当一个线段的2个NFA低于给定的阈值时，该线段才被认为是有意义的，最终输出的线段为本文算法定义的矩形。本文算法使用相同的阈值1。

2.3 短线段合并

在图像预处理阶段，得到多尺度图像空间或多尺度多分辨率图像金字塔。对图像进行LSD，系统输入的每一个图像都会得到3组线段集合，即每层图像检测的线段集合。图3直观地表示了线段合并过程。其中，空间线段表示为L（a，b），a为线段的起点，b为线段的终点，其中，L1为在第1层检测出的近似线段；L2，L3和L4为在第0 层检测出的近似线段，从图中直观表示：线段L在第1层检测为一条完整的近似线段，而在第0层出现线段分割现象，所以根据线段替代原则，即将线段L1（a1，b1）的尺寸恢复至第0 层，即L′1（a′1，b′1），以线段L′1的方向为基准做2条平行直线，线宽为2像素，长度与L′1相同，将此区域定义为线段平行区域，根据设置的线段平行区域，寻找分割的线段，图中，L2，L3和L4符合条件，即直接利用L1来取代L2，L3和L4，得到合并之后的真实线段L（a，b）。

利用此方法，按照构建结构逐层进行遍历至0层结束，最终输出提取线段的效果，流程如图4所示。

3 实验与分析

3.1 MMLSD算法实验验证

图5 为不同算法检测直线段的结果，3 幅图选自York［8～10］城市数据集，因为这个数据集具有人工标注，所以将算法检测结果与人工标注进行比较，从图中标注框可以得出：LSD虽然检测到大量的直线段，但存在较为严重的线段分裂现象；EDLines 算法虽然检测到的长线段的效果较好，但容易丢失细节信息；MMLSD 算法在建筑物检测方面，视觉上与人工标注更为一致，既合并了属于同一行、同一列的线段，同时也能够更好地检测低对比度的线条，对于周围环境的细节信息也能够充分检测出来。

图5 不同算法对York城市数据集检测结果

图6选自牛津建筑数据集［11，12］，建筑中存在的细节较多，轮廓不明显并且建筑图像顶部的对比度较低，所以从检测结果可以得出，LSD算法对于建筑物顶部检测效果较差，线段检测失效；EDLines算法虽然检测出线段，但对于建筑物中低对比度的部分，存在错误检测线段的现象。MMLSD算法针对低对比度部分展现了较好的线段检测效果，有效地克服了线段过度分裂的现象，将图像中的结构化部分正确检测出来。

图6 不同算法对牛津建筑数据集检测结果

本文将York城市数据集中的102张图像分成三大类：室内空间场景、室外远景建筑场景、室外近景建筑场景。分别进行线段检测，表1 中的数据为3 种算法检测的线段数量、平均长度、总长度以及系统运行时间。第一组室内场景数据，LSD算法检测到的线段数量最多，但本文算法检测到的线段数量长度最长；室外场景中由于建筑细节以及外围环境的细节增多，EDLines算法与MMLSD算法检测到的数量相当，但就平均长度来说，本文算法优于EDLines 算法，但本文算法的系统运行时间较长。综上所述，相较于LSD和EDLines算法，本文MMLSD算法检测得到的线段平均长度最长，检测效果优于另外两种算法。

表1 不同线段检测算法的输出

3.2 MMLSD算法性能验证

本文使用Cho N G等人创建的测评体系，针对3 种算法进行评估比较，其中包含4个性能指标，分别是平均精度（average precision，AP）、平均召回率（average recall rate，AR）、交并比（intersection over union，IoU）和F值（F-score），将York城市数据集中的102 张图像均使用3 种算法进行线段检测提取。图7给出3种算法的评估数据对比。

图7 算法评估数据对比

在AP上，MMLSD算法取得最高分数0.390 9，较LSD算法提高了13. 1 %；本文算法取得的分数为0.442 7，而LSD算法取得最高分数0.450 1，但它是以牺牲准确率得到的。IoU和F-score是关于精度和召回率的综合指标，本文算法在2个指标上均取得最高分数，所以通过测评体系显示MMLSD算法在线段检测上性能有较大提升。

4 结 论

本文针对LSD 算法易受光照、角度等因素影响，造成提取的直线段过度分割的问题，提出MMLSD 算法。将高分辨率图像与低分辨率图像分开处理，既有效地解决了低分辨率图像下线段检测问题，又有效地解决了高分辨率图像退化成单尺度问题。针对线段分裂问题，通过构建空间图像金字塔，提出短线段合并思想。应用所提出的MMLSD算法在不同环境中进行测试，并与LSD算法、EDLines算法的检测效果进行对比分析，本文算法具有更好的准确性、鲁棒性，相关评价指标得到了较大的提升。