基于边缘块的线段提取方法

申超胜，张敬峰，林靖宇

(广西大学 电气工程学院，南宁 530004)

1 引 言

直线检测是图像处理和计算机视觉的经典问题.直线包含对象的重要信息，特别是在人造场景中直线是常见特征.直线特征应用于很多任务，如图像匹配[1，2]，道路检测[3，4]，三维重建[5，6]等.直线提取方法的优劣将会直接影响到高层次图像处理的效果.

直线特征的检测方法主要分为两类：基于梯度幅值和基于梯度方向.

基于梯度幅值的方法是在边缘图像上进行的，而不是输入图像，所以这类方法首先需要边缘检测器从输入图像中提取到边缘图.Hough变换法正是一种在图像边缘图上实现的方法，该方法对输入图像进行边缘检测，然后进行Hough变换提取直线，最后将直线段分割，得到直线段输出.之后有大量基于Hough 变换法的改进版本出现[7-10].但是基于Hough 变换法的算法，对于有较高边缘密度的图像会得到大量错误结果，而且由于其忽略边缘点方向信息，常常会得到异常方向的直线段.为了解决这些问题，Akinla和Topal[11]提出了一个快速、无参数的线段检测器，命名为EDLines.其优点是运行时间快，抗噪声能力强，但他们是基于边缘段进行的，线段检测结果在很大程度上受到了边缘段检测算法的影响，容易丢失低梯度线段.Xiaohu Lu[12]等人认为，边缘段在检测过程中已经丢失部分重要的信息，应该从原始图像或者是从包含图像的所有结构信息的边缘图中检测线段.因此他们提出了一个基于边缘图的直线检测算法.该方法易于检测低梯度区域的线段，但也会有过滤部分真实短线段的不足，使得图像的局部细节不够完整.

基于梯度方向检测线段的思想最早由Burns[13]等人在1986年提出.该方法计算图像像素点的梯度方向，将具有大致相同梯度方向的像素点进行分组得到直线图像区域.由于只用到梯度方向信息，检测效果并不理想.2010 年，Gioi 等人[14]在Burns 等人[13]的基础上提出了一种快速的线段检测方法，称为LSD算法.他们的方法同时使用了像素点的梯度方向信息和梯度幅值信息，选取梯度幅度极值处的像素点作为种子点，根据梯度角方向开始区域生长，标记这些像素点为已使用，并且更新区域角度，之后将区域近似成矩形候选直线段.LSD算法能精确地检测线段，通过有效地结合梯度方向和亥姆霍兹原理来验证线段，在一定水平上控制错误检测的数量.但是LSD算法的梯度幅度极值是一个安全阈值，会消除一些有用的线段，并且LSD算法会在梯度方向不稳定的区域将长线段分割为多条线段，这就导致了检测结果会出现线段聚集，以及线段方向不正确等情况.

基于上述分析，为了解决由于梯度信息不足而导致线段被消除的问题，本文提出一种基于边缘块的直线检测算法.通过分析边缘图中边缘点本身的连通域性质，将边缘点聚合为边缘块，最大限度的保留了边缘图的信息.之后以邻接矩阵的方式统计边缘块之间的位置信息，根据邻接矩阵和深度优先搜索算法以及直线的几何特征，使得边缘块连接集合能够保留物体的轮廓信息，最后对边缘块连接集合进行拆分处理，从而完成直线检测.本文的代码已经公布在GitHub(1)https：//github.com/GXUVision/LineDetection.

2 基于边缘块的直线检测算法

本文的算法分为以下3个过程：

1)边缘块提取

首先提取图像中的边缘，并将边缘处理为单像素宽度.根据边缘点本身的连通域性质，对边缘点进行标注.通过对标注结果进行分析，将边缘点组合为各种类型的边缘块.

边缘块提取将孤立的边缘点连接成具有方向的边缘块，实现将点特征聚合为块特征.

2)路径提取

边缘块继承了边缘点本身的连通域性质，本文统计每个边缘块之间的位置关系，得到了邻接矩阵.在邻接矩阵上使用深度优先算法(Depth-First-Search，DFS)，得到了初始路径集合.

路径提取将边缘块连接成带有物体几何特征的线条，实现将块特征聚合成线特征.

3)直线检测

对初始路径集合中的路径进行筛选，利用直线的几何定义，将符合直线定义的路径归为直线.对于初始路径集合中不符合直线定义的所有路径，根据每条路径的曲折度，将路径分离为两部分.之后判断分离的部分是否是直线，不符合的部分将再次分离，这样循环分离，直到所有分离的部分都符合直线定义.

图1 论文工作框图Fig.1 Paper work block diagram

本文将在第3节中描述边缘块提取过程，在第4节中描述路径提取过程，在第5节中描述直线检测过程.本文工作框图如图1所示.

3 边缘块提取

在边缘图中，每条边缘都由大量的边缘点组成，点与点之间的连通关系构成线，而这种连通关系简单的说就是位置的相对关系，存在一定的规律，交叉和重叠会影响这种规律.考虑到边缘图中的边缘点较多，且相互之间的连通域关系并不明显，本文将边缘点聚合成边缘块，以边缘块的形式来代表边缘，能在有效减少重复运算的同时，又能最大限度的保证边缘信息的完整.

以图像的左下角为坐标原点，图像的宽度为X轴正方向，图像的高度为Y轴正方向，每个像素点作为一个坐标值.本文将边缘块分为3类：将平行于X轴的边缘块定义为水平边缘块ehor，将平行于Y轴的边缘块定义为竖直边缘块ever，将由单个边缘点组成的边缘块定义为单个边缘块es：

ehor={(xf，yf)，(xl，yl)|yf=yl}

(1)

ever={(xf，yf)，(xl，yl)|xf=xl}

(2)

es={(xf，yf)，(xl，yl)|xf=xl，yf=yl}

(3)

其中(xf，yf)，(xl，yl)分别表示边缘块中首尾像素点坐标.

边缘块类型如图2所示.

图2 标准边缘块Fig.2 Standard edge block

边缘块提取是基于图像的边缘进行的.在提取图像边缘后，对边缘图进行标注，根据对标注结果进行分析和处理，将经过标注处理的边缘点聚合成边缘块.本文将在3.1节中描述标记过程，在3.2节中描述检测过程.边缘块提取的整体流程效果图如图3所示.

3.1 边缘点标注

边缘点之间存在着本身固有的连通域性质，通过对边缘点进行标注，让连通域性质更好的显现.

首先采用CannyPF算法[12]提取图像的边缘E，在这一过程中为了方便后续处理，在保证每条边缘不断裂的情况下，将每条边缘处理为单像素宽度.之后在每个边缘点八邻域的基础上，定义了3×3-ε邻域：

(4)

其中Ii为3×3-ε邻域中第i个边缘点的灰度值，a0表示为当前边缘点的位置.

(5)

图3 边缘块提取整体流程效果图Fig.3 Process of edge block extraction

在这基础上，开始对边缘点进行初步标注，将lcmp值属于单个边缘块的边缘点标记为-1，属于竖直边缘块的边缘点标记为1，属于水平边缘块的边缘点标记为3.同时将边缘图中不符合3种条件的边缘点标记为-1，将不在边缘上的像素点标注为0.

之后为了更好地区分每个边缘点的界限，在3×3-ε邻域的基础上引入了特征角公式LCN(a0)：

(6)

其中ai的值与公式(4)中定义一样.

遍历边缘图中的所有边缘点，计算每个边缘点的LCN(a0)值.当任意边缘点满足以下两个条件，即其初始标注值为-1，并且满足LCN(a0)>0，则将这个边缘点的标注值修改为9.将不满足条件的边缘点的标注值修改为-1，至此所有边缘点都完成标注.

3.2 边缘点拟合

在这节中，根据3.1节中的标注结果，将边缘图上的边缘点聚成边缘块.从边缘图的左下角开始，按行扫描，对于每个边缘中的边缘点，考虑以下4种情况：

1)若在其3×3-ε邻域中，a1和a3位置上的像素点的标注值为0或9，则将当前边缘点归类为单个边缘块；

2)若在其3×3-ε邻域中，a1位置上像素点的标注值不为0而和a3位置上边缘点的标注值为0，则向当前边缘点的a1方向扫描，遇标记值为0或9的像素点后停止扫描，将当前像素点和扫描期间遇到的像素点整合为一个竖直边缘块；

3)若在其3×3-ε邻域中，a3位置上像素点的标注值不为0而和a1位置上边缘点的标注值为0，则向当前像素点的a3方向扫描，遇标记值为0或9的像素点后停止扫描，将当前像素点和扫描期间遇到的像素点整合为一个水平边缘块；

4)若在其3×3-ε邻域中，a1和a3位置上像素点的标注值都不为0，则分别向当前像素点的a1和a3方向扫描，遇标记值为0的像素点后停止扫描，统计a1和a3方向扫描得到的像素点个数n1、n3，考虑两种情况：

①如果n1≠n3，选择向max{n1，n3}的方向统计边缘块.如果n1较大，则往a1方向统计，将当前像素点和扫描期间遇到的像素点整合为一个竖直边缘块；如果n3较大，则往a3方向统计，将当前像素点和扫描期间遇到的像素点整合为一个水平边缘块.

②如果n1=n3，则计算当前已统计出的水平边缘块和竖直类边缘块的个数mh，mv.若mh>mv，则往a3方向进行统计，将当前像素点和扫描期间遇到的像素点整合为一个水平边缘块.若mh

考虑到两条相邻的轮廓线会相互影响的情况，再对已经提取的边缘块进行分离.如果组成边缘块的像素点标记值为9，则以9为边界，将大型边缘块划分为多个小型边缘块.

通过以上步骤，点元素被整合成线元素，曲线的边缘块提取完毕.边缘图E可由边缘块表示：

E={e1，e2，…，ek}

(7)

图4 边缘块提取效果图(图(d)为图(a)方框位置放大图)Fig.4 Result of edge block extraction

本文算法边缘块提取的效果如图4所示.

4 路径提取

现有的直线检测方法，如EDLines[11]和CannyLines[12]都是基于梯度信息来将边缘图中的边缘组合成像素链，当梯度信息不足时就会造成连接的边缘不够完整，或者是部分边缘没有连接成功从而导致信息缺失.在这一节中，本文通过分析边缘块之间的连通域信息，提出了一种新的边缘块连接方法.

首先统计边缘块相互之间的位置关系，将所有统计结果以矩阵的形式保留.之后对统计结果进行分析，将多个边缘块连接得到曲线，并将这种曲线定义为路径.本文在4.1节中描述边缘块位置关系的统计过程，在4.2节中描述对统计结果的处理过程.

4.1 邻接矩阵获取

邻接矩阵中存放顶点间关系的数据.在第3节中，本文将边缘点组合为边缘块，边缘块继承了边缘点本身的连通域性质，也是就说每个边缘块之间也存在一定的位置关系，即距离与方向.因此我们可以将每个边缘块视为一个顶点，以邻接矩阵的方式来统计边缘块之间的位置关系.

统计过程如下：从图片左下角开始，按行扫描图片，统计每个边缘块与其他边缘块的位置关系，最终得到邻接矩阵W.

W=[wij]k×k

(8)

其中k为边缘块的个数.

邻接矩阵中的每一个元素wij表示的是边缘块ei与边缘块ej的位置关系.W中每个元素wij的计算公式为：

wij=Re(-1)dij·D8(ei，ej)

(9)

其中D8(ei，ej)表示的是边缘块ei到边缘块ej的棋盘距离.Re(-1)dij表示的是边缘块ei与边缘块ej的方向.Re(·)是取复数实部，dij有3种取值情况，当ej在ei的左上角时，dij=0；当ej在ei的右上角时，dij=1；当ej与ei不相邻时，dij=0.5.

4.2 路径提取

邻接矩阵W可以看作是加权有向图，每个边缘块相当于图中的顶点.顶点的连接过程相当于图的搜索过程，深度优先搜索算法(DFS)是一种将顶点所有分支都统计的搜素算法，因此在这一节中，我们将深度优先搜索算法(DFS)应用到邻接矩阵上，统计邻接矩阵中所有顶点的分支，得到由边缘块组成的像素链，本文将这种像素链称之为路径.

按行扫描邻接矩阵W，当遇到一个非0的元素，即wij≠0时，以此时的邻接矩阵的行数所代表的边缘块ei为DFS算法的起始端点，统计ei在邻接矩阵W中的所有分支.

为了保留更多的信息，算法没有限制每个边缘块被遍历的次数，因此一个边缘块可能会存在于多条路径中，或者是作为多个路径的起点.同时为了避免得到的路径过多且无意义，所以在按行扫描的邻接矩阵时，只考虑没有在任何路径中的边缘块可以作为路径的起点.

在完成扫描后得到了一个路径集合P：

P={P1，P2，…，Pn}

(10)

图5 路径提取效果图(图(d)为图(a)方框位置放大图)Fig.5 Result of path extraction

本文算法路径提取的效果如图5所示.

5 直线检测

由于使用了贪婪算法，深度优先搜索算法，因此初始路径集合中包含着大量重复的信息.本节利用直线的几何特征筛选初始路径中较为明显的直线特征，之后再将筛选后路径集合中的路径进行分离，最终实现直线检测.本文在5.1节中描述路径集合筛选过程，在5.2节中描述路径分离过程.

5.1 路径筛选

假设以ei为起始端点的路径集合为：

(11)

1)计算每个路径的绝对长度，即计算每条路径的第一个边缘块与最后一个边缘块的欧式距离.在所有计算中选择每个边缘块的首尾边缘点坐标的中值作为每个边缘块的坐标.这样我们就得到了一个集合li：

(12)

当路径集合Pi中没有任何路径满足直线定义时，此时的路径集合中剩余的路径只有第一个边缘块相同的路径或者是最后一个边缘块相同的路径，即起点相同的路径或终点相同的路径.

5.2 路径分离

在这一节中我们对上一节中曲折度不符合直线定义的路径进行路径分离.设Po=(er，et，…，ey)，(r，t，…，y)∈(1，2，…，k)，对于任意路径Po的拆分过程分为两个步骤：

当路径集合中的所有路径都完成拆分后，这样我们就完成了直线检测，得到了一个直线集合：

L={l1，l2，…，ln}

(13)

6 实验结果

为了验证算法的有效性，将本文提出的算法与LSD[14]算法、EDLines[11]算法、CannyLines[12]算法进行对比.

本文的算法只包含两个参数，即直线定义中的距离阈值δ以及边缘检测算法CannyPF[12]中关于梯度幅值的阈值λv.在理论中，直线上的点到直线的距离为0，考虑到数字图像是经过离散化的结果以及图像成像时会受到噪声的影响，因此我们在直线定义中设定了距离阈值δ.当δ设定的过于严苛时，我们在分离步骤中就会得到较多细碎的线段，当δ设定过大时，我们得到的线段就会带有一定的弧度.经过在多张图片上进行尝试，本文将距离阈值δ设置为1.5个像素大小，这样可以在一定程度上保证线段的长度以及轮廓的完整性.

在CannyLines算法中其选择的梯度幅值阈值λv为70，这样保证了边缘图不会过度分割也不会过度检测，本文选择将λv设置为与CannyLines算法中所设置的一样.对于LSD算法、EDLines算法、CannyLines算法的参数设置，本文采取了其提供的代码中的参数设置.本文选用YorkUrbanDB[15]数据集中48张室内照片与48张室外照片用于实验测试的图像数据集.

图6 实验结果对比Fig.6 Experimental results of line segment extraction

直线检测的结果如图6所示.直观的来看，4个算法都具有较好的检测效果.对于建筑物外观图像的检测结果中，可以看出LSD算法在玻璃窗户以及对比度不明显的建筑物轮廓处的检测效果较好，能得到建筑物的局部细节较多，但是LSD算法容易在对比度不高的地方使得线段聚.EDLines算法与CannyLines算法，在局部细节的表现不如LSD算法，但不会像LSD算法一样会出现线段聚集的情况，能够较好的检测出物体轮廓中的直线，其不足之处在于依然会丢失部分物体的轮廓信息.在建筑物室内图像的检测结果中，4个算法的检测效果主观上很相近.在涉及到天花板等对比度不明显的地方时，LSD算法与EDLines算法在检测效果上不如CannyLines算法以及本文的算法.

之后对检测结果的局部细节进行对比，对比结果如图7所示.

对比中发现，LSD算法，CannyLines算法会出现线段方向不正确，如大楼顶部的弧形曲线直接被直线代替，使得大楼的轮廓信息发生了改变.并且LSD算法和EDLines算法丢失了部分轮廓信息，如楼顶左侧的线段未被检测出来.实验结果验证了本文算法的直线检测效果能完整的保留物体的轮廓信息.不会出现物体轮廓信息不完整以及形变的情况，对于玻璃窗户以及对比度不明显的建筑物轮廓处的检测效果也有着较好的效果，且不会出现线段聚集的情况.

图7 局部效果对比图(图(b)为图(a)方框位置放大图)Fig.7 Result of local effect comparison

为了更好地验证算法的有效性，本文选择以平均召回率(AR)，平均精确度(AP)，F-值来综合的评估算法.在实验中我们认为正样本为：对于检测的直线中的任意一个像素点，如果其八邻域内存在真实样本的像素点，就认为这个像素点为正样本.同时为了避免检测的线条越多，则正样本数量越多，实验中每个像素点只被判断一次.实验结果如表1和表2所示.

表1 室内线段检测结果Table 1 Line detection results of indoor iamges

表1中的数据显示，在室内线段检测结果中本文的算法与EDLine算法具有最高的召回率，说明本文检测出直线大部分为真实样本中所设定的.同时本文的算法与CannyLine算法采用相同的边缘检测方法，在3个评估数据中，本文的算法都是优于CannyLine算法，验证了我们边缘连接方法的有效性，能够保留大部分的轮廓信息.表2中的数据显示，在室外线段检测结果中本文的算法与EDLine算法具有最高的精确度，即误检测的直线最少，验证了本文算法的有效性.

表2 室外线段检测结果Table 2 Line detection results of outdoor iamges

7 结 论

本文针对传统直线检测算法在梯度信息不足时出现的检测结果不完整的问题，提出了基于边缘块的线段检测算法.结合边缘点的连通域性质，将边缘点聚合成边缘块，根据边缘块之间的位置关系，提出一种新的边缘连接方式，解决了之前算法只关注图像中的梯度信息，而忽略了边缘本身连通域信息，从而导致检测结果中物体轮廓不够完整的问题.本文提出的算法能在最大程度上保留被检测物体的轮廓，且具有较好的局部细节，有利于后续的直线特征应用.