EN中文

Journal of Geo-information Science >

2019 , Vol. 21 >Issue 7: 994 - 1008

DOI: https://doi.org/10.12082/dpxxkx.2019.180697

Orginal Article

Integrating SVM and Graph Matching for Identifying Road Markings from Mobile LiDAR Point Clouds

  • FANG Li'na , 1, 2, 3, * ,
  • HUANG Zhiwen 1, 2, 3 ,
  • LUO Haifeng 1, 2, 3 ,
  • CHEN Chongcheng 1, 2, 3
Expand
  • 1. National Engineering Research Centre of Geospatial Information Technology, Fuzhou University, Fuzhou 350002, China
  • 2. Key Laboratory of Spatial Data Mining and Information Sharing of Ministry of Education, Fuzhou University, Fuzhou 350002, China
  • 3. Spatial Information Research Center of Fujian Province, Fuzhou University, Fuzhou 350002, China
*Corresponding author: FANG Li'na, E-mail:

Received date: 2018-12-28

  Request revised date: 2019-03-13

  Online published: 2019-07-25

Supported by

National Natural Science Foundation of China, No.41501493

National Natural Science Foundation of Fujian Province, China, No.2017J01465

China Postdoctoral Science Foundation, No.2017M610391

Science Foundation of Education Commission of Fujian Province, China, No.JAT160078

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

This paper presented a novel method for identifying road markings from mobile LiDAR point clouds by integrating Support Vector Machine (SVM) and graph matching. Firstly, the road surface point cloud was extracted using the scanline method, and then, was used to generate independent marking objects by a marking segmentation method combined with intensity correction. Next, hierarchical classification was conducted to identify smaller size markings as the basic objects for further processing. Considering the shape varieties of different types of marking objects, Hu invariant moments, Solid Shape Context (SSC), the area of Minimum Bounding Rectangle (MBR), and extensibility were extracted to construct the marking shape feature vector. Subsequently, with the shape feature vector of the above-mentioned samples, a training sample set was manually established to fit SVM model parameters. In the classification section, the SVM model was conducted for the preliminary classification, where there were situations including cross misclassification of markings with similar shapes and ambiguity between dotted marking and zebra crossing. Building upon the graph structure including certain types of interactive relationship (e.g., arrangement of road markings, direction relationship, and distance between markings in the local area) and the shape feature of markings, we used the inherent characteristics and spatial neighborhood information of objects to synthetically describe the geometric feature and spatial semantic information of road markings. Since the partial absence of markings' semantic structure, we developed an inexact graph matching method based on the graph structure of markings, which could optimize the preliminary classification result. The refined classification results of all six types of road markings included the straight arrow, the crosswalk warning line, the one-way steering arrow, the two-way steering arrow, the dotted marking, and the zebra crossing. To verify the validity of the proposed method, we conducted experiments using four test data sets acquired from different MLS systems. The verification results show that the six marking types have a respective precision of 100%, 100%, 94.12%, 100%, 94.94%, and 99.25%, and a respective recall rate of 100%, 100%, 88.89%, 100%, 98.21%, and 99%, and a respective F1-Measure value of 100%, 100%, 91.43%, 100%, 96.59%, and 99.12%. The experimental results demonstrate that the proposed method could accurately identify multi-class road markings. In conclusion, our algorithm is superior and robust for extracting road markings in even complicated cases where road markings may exhibit significant shape differences or high similarity (e.g., the straight arrow and linear marking, the dotted line and zebra crossing).

Key words： mobile point clouds; road marking recognition; shape features; SVM; graph structure; graph matching

Cite this article

FANG Li'na , HUANG Zhiwen , LUO Haifeng , CHEN Chongcheng . Integrating SVM and Graph Matching for Identifying Road Markings from Mobile LiDAR Point Clouds[J]. Journal of Geo-information Science, 2019 , 21(7) : 994 -1008 . DOI: 10.12082/dpxxkx.2019.180697

1 引言

道路标线作为重要的道路交通设施,它能向使用者传递有关道路交通的规则、警告、指引等信息,是交通运营与管理、辅助驾驶和智慧城市等应用领域的重要基础数据[1,2,3]。车载激光扫描系统（Mobile Laser Scanning, MLS）作为近年来快速发展的高新测绘技术,能够高效、精准地获取道路场景的三维空间信息和回波强度信息,为道路标线的识别和更新提供一种新数据源[4,5,6]。
目前,基于车载激光点云数据识别道路标线的方法主要分为2类：① 基于单一特征识别道路标线。Chen等[7]利用Hough变换检测呈现线状空间分布的车道线,但该方法只适用直线型车道线的提取;Riveiro等[8]基于邻域空间内标线的排列方式构建语义特征描述斑马线,有利于提高其检索精度,但难以推广到其它标线;有学者针对标线的规则形状,构建形状特征,利用决策树[9]或模板匹配[10]实现标线的分类,该算法对具有显著形状差异的标线识别效果较好,但其抑制噪声能力弱,对于形状相似标线的识别精度较低。② 结合形状特征和语义信息识别标线。如一些专家联合形状特征和相邻对象的平行关系,实现斑马线和其它标线的区分[11,12];或针对基于形状特征的粗分类结果,根据虚线型标线在同一方向上的等间距排列,精细区分虚线型标线和实线型标线[13]。但这些方法的空间语义信息较为单一,只适用特定标线识别。于是,Yu等[14]针对不同标线采用不同语义特征描述,结合形状特征实现层次分类：首先利用尺寸信息区分大尺寸和小尺寸标线;然后,基于标线与轨迹线、路坎的相对位置关系实现大目标分类,通过将标线栅格化成二值图像并生成对应向量构建形状描述子,采用深玻尔兹曼机（Depp Boltzmann Machine,DBM）进行小目标识别,并结合对象排列方式,进一步细化小目标分类结果。Mario等[15]同样预先采用人工神经网络获得矩形标线、箭头标线和其它标线;基于标线与轨迹线间角度关系、相邻标线排列情况精细划分矩形标线,并利用模板匹配细化箭头标线分类结果。这些方法虽然结合了多种语义信息,并引入机器学习方法提高分类精度,但其基于语义特征的分类方法依赖于大量的人工经验阈值,难以推广。因此,Hervieu等[16]提出结合形状特征与标线间交互关系,利用模型和数据驱动马尔科夫链蒙特卡洛算法构建通用的能量函数,实现标线自动分类。但该方法仅仅基于是否重叠这一情况描述标线间交互关系,难以精确刻画标线的空间结构特性。
针对上述问题,本文提出一种结合SVM与图匹配的车载激光点云标线识别方法。采用多种特征融合的方式构建形状特征向量,结合SVM准确区分具有显著形状差异的标线类别,实现标线的粗分类。针对粗分类结果中形状相似标线识别精度较低的情况,利用图结构精确表征标线空间语义信息,采用图匹配方法优化形状相似标线的分类结果,从而实现多类标线的精确识别。

2 研究方法与数据来源

2.1 车载激光点云道路标线识别主要流程

本文方法对点云数据进行预处理,采用基于扫描线方法提取路面点云[17],引入结合强度校正的标线分割方法生成独立标线对象[9],并通过层次分类获得小尺寸标线作为处理对象[14]。然后,提取标线对象的Hu不变矩、SSC、MBR面积和延展度构建形状特征向量,采用SVM实现标线的粗分类。针对粗分类结果,结合标线对象的邻域空间结构信息构建标线对象的图结构,利用图匹配方法优化粗分类结果,实现道路标线对象的精确识别。该方法主要流程如图1所示。
Fig. 1 Flowchart of the MLS markings classification

图1 车载激光点云标线分类流程

2.2 基于SVM的标线粗分类

2.2.1 标线特征提取
道路标线作为典型人工地物,其形状规则,且大部分不同类别标线形状各异。针对点云数据中存在标线对象因磨损、遮挡存在少量轮廓边界噪声和部分形状缺失,本文提取能够描述全局区域特性的Hu不变矩、兼顾形状区域信息和轮廓信息的SSC以及表征标线几何特征的MBR面积和延展度构建形状特征向量,用于标线的粗分类。
（1）Hu不变矩：不变矩概念由Hu提出,其具有平移、缩放和旋转不变性[18]。本文通过对标线对象进行规则格网剖分,有点的格网赋值1,无点的格网为0,从而生成二值图像。针对二值图像,应用不变矩理论得到7个不变矩 φ k ( k = 1,2 , … , 7 ) 。由于实际中7个不变矩的变化范围较大,因此,通常采用的不变矩 I k 为：
I k = lg | φ k | , k = 1,2 , … , 7 （1）
（2）SSC特征：在复杂道路环境中,一些标线点云对象因磨损、遮挡存在少量轮廓边界噪声和部分形状缺失。本文采用改进后兼顾形状区域信息和轮廓信息的SSC作为标线形状描述子[19]。
如图2（a）所示,首先采用MBR描述标线对象轮廓,并提取MBR 4个顶点作为标线的轮廓特征点,有效表征形状的同时确保算法效率。任意轮廓特征点 P i 的SSC描述即为标线点 Q j 相对于点 P i 角度 θ ij 和对数距离 lg r ij 的直方图分布。针对原始SSC特征不具备旋转不变性,本文以MBR中与 P i 相连的短边 l i 为参考边,计算标线对象中各点 Q j 相对于点 P i 的角度 θ ij ,使其在平移、缩放不变性的基础上增加旋转不变性：
lg r ij = lg ( | | P i - Q j | | ) θ ij = ar cos ( l i ∙ vecto r ij ) （2）
式中： vecto r ij = Q j - P i 。以轮廓特征点中任意一点 P i 为参考坐标原点建立对数极坐标系,分别将 lg R 和 θ ( θ = 90 ∘ ) 进行 S 等分和 T 等分,将空间划分为 S × T 个区域（图2（b）-（e））,其中 R 取MBR对角线长度。
Fig. 2 SSC structure descriptions

图2 SSC结构描述

在完成空间区域划分后,以短边为起始边,长边为终止边,由内而外对各区域进行编码,并记录标线对象在各个区域 bi n i ( k ) 的点分布数目 h i ( k ) , h i ( k ) 即为当前轮廓特征点 P i 的SSC特征,计算公式如下：
h i ( k ) = { Q ∈ bi n i ( k ) } , k = 1,2 , … , S × T （3）
计算和融合每个轮廓特征点的SSC,并归一化生成标线对象的SSC：
F _ SSC = ∑ i = 1 4 h i ( k ) / ∑ k = 1 S × T ∑ i = 1 4 h i ( k ) （4）
（3）几何特征：考虑到标线尺寸规范,计算标线对象的MBR面积 Area 和延展度 U 描述标线的几何形状：
Area = L × W U = L / W （5）
式中： L 和 W 分别为标线对象MBR的长和宽。
通过上述特征计算,生成标线形状特征 F _ shape 如下所示：
F _ shape = [ I k , F _ SSC , Area , U （6）
2.2.2 基于SVM的标线粗分类
SVM作为机器学习邻域极为重要的发展成果之一,在解决非线性、高维模式识别等问题表现出许多独有的优势[20,21,22]。鉴于虚线型标线与斑马线均呈现线状分布,基于形状特征难以对其进行有效区分,在粗分类阶段,本文将二者统一视作线状标线类别。因此,粗分类类别包括人行横道预告标识线、单向转向标线、双向转向标线、直行箭头、线状标线以及其它类六类目标。本文通过人工构建训练样本集,将上文获得的形状特征向量 F _ shape 作为SVM的输入特征,选择应用最广泛的径向基函数作为核函数,采用粒子群优化算法进行惩罚因子 C 及核函数参数 γ 寻优。最后通过SVM的训练与分类,实现道路标线的粗分类。

2.3 基于图匹配的分类结果优化

针对粗分类结果中存在形状相似标线难以区分的情况,如部分直行箭头与线状标线存在交叉错分（图3）,以及线状标线中存在2种未被区分的标线：虚线型标线和斑马线。本文提出利用图结构精确表征标线空间语义信息,采用图匹配方法优化粗分类结果,从而实现标线的精确识别。
Fig. 3 Cross misclassification between linear markings and straight arrows

图3 线状标线与直行箭头交叉错分情况

2.3.1 图结构构建
图作为一种对目标语义结构具有强大描述能力的数据结构[23,24],基于图结构的图匹配方法广泛应用于计算机视觉[25,26]和模式识别[27]。针对道路标线规范的邻域空间分布特性（如排列、方向、距离）,本文基于标线邻域空间结构信息建模成由参考对象指向邻域对象的有向图 G = { V , E } , V 和 E 分别为节点集合和边集合。如图4中（a）和（b）所示,黑实心点为标线的抽象节点,有向边用于可视化参考对象的邻域情况。图4（b）表示邻域结构的关系图,图结构可以表示为 V = { v 0 , v 1 , v 2 } , E = e 1 < v 0 , v 1 > , e 2 < v 0 , v 2 > 。使用 R vk = F _ shap e k 表示节点属性,即节点 v k ( k = 0,1 , 2 ) 对应标线对象的形状特征;采用 R el 表示邻域对象与参考对象之间的空间结构关系：
R el = [ Dir e l 0 , Dis t l 0 , Po s l 0 ] , l = 1,2 （7）
Dir e l 0 = area ( N W 0 ⋂ v l ) area ( v l ) area ( N 0 ⋂ v l ) area ( v l ) area ( N E 0 ⋂ v l ) area ( v l ) area ( W 0 ⋂ v l ) area ( v l ) area ( O 0 ⋂ v l ) area ( v l ) area ( E 0 ⋂ v l ) area ( v l ) area ( S W 0 ⋂ v l ) area ( v l ) area ( S 0 ⋂ v l ) area ( v l ) area ( S E 0 ⋂ v l ) area ( v l ) （8）
Dis t l 0 = min p t i ∈ v 0 p t j ∈ v l | | p t i - p t j | | （9）
Po s l 0 = abs ( e → l · e → 0 ) （10）
式中： Dir e l 0 为方向矩阵[28],用于描述邻域对象与参考对象之间的方向关系（图4（c））, Dis t l 0 为二者间最短欧式距离（图4（d））, Po s l 0 为二者的姿态差异,单位向量 e → l 为节点 v l 对应对象的主方向,以标线对象的坐标构建矩阵,通过求解矩阵最大特征对应的特征向量获得（图4（e））。
Fig. 4 Graph structure construction diagram(take the straight arrow as an example)

图4 图结构构建示意（以直行箭头为例）

2.3.2 结合BBS算法的匹配节点获取
图匹配主要研究2个模型节点集合的最优映射关系,即寻找图模型间节点匹配关系。针对少数标线空间语义结构存在部分缺失,本文提出采用允许一定属性和结构差异的非精确匹配方法,通过融合节点属性 R vk 与边属性 R el 构建综合属性 R vel 描述邻域对象对应节点（式（11））,将图匹配问题转化成分配问题进行处理。
针对分配问题,如图5（b）所示,建立模板图 G = { V , E } 与待测对象邻域结构图 G ' = { V ' , E ' } 间节点的全连接,生成关联矩阵 S （式（12））。基于关联矩阵 S ,利用Best-Buddies Similarity（BBS）算法[29,30]提取二者最优相似点对作为匹配点对（图5（c））。
R vel = [ R vk , R el ] , k = l = 1,2 , … , n （11）
S = S v 1 ' v 1 S v 1 ' v 2 ⋯ S v 1 ' v n S v 2 ' v 1 S v 2 ' v 2 ⋯ S v 2 ' v n ⋮ ⋮ ⋱ ⋮ S v m ' v 1 S v m ' v 1 ⋯ S v 2 ' v n （12）
式中： S v i ' v j = ( S Shape ij + S Dire ij + S Dist ij + S Pos ij ) / 4 ( i = 1 , ⋯ , m , j = 1 , ⋯ , n ) 为模板图与待测图之间节点综合属性 R vel 的相似性, m 和 n 分别为待测图与模板图的邻接节点数量。 S Shape ij 、 S Dist ij 、 S Pos ij 分别为对应节点间综合属性中形状特征、距离特征、姿态特征的相似性（式（13））, S Dire ij 为对应节点间方向相似度,取值区间为[0, 1],值越接近1,二者方向关系越相似。Northwest-Corner作为运筹学中一种平衡运输问题求解方法,在平衡运输表中,从西北向东南逐个分配求解[31]。矩阵间相似性度量与平衡运输问题有一定共性,因此本文引入Northwest-Corner方法计算从源方向关系矩阵转换成目的方向关系矩阵的最小代价,即源方向关系矩阵中非零元素沿着邻域分区的路径移动到目的方向关系矩阵中非零元素位置的距离,以此获得方向矩阵间相似度。
S F ij = exp ( - | | F i - F j | | 2 ) , F ∈ { F _ shape , Dist , Pos } （13）
Fig. 5 Graph node matching processes based on BBS algorithm

图5 基于BBS算法的图节点匹配过程

2.3.3 匹配结果输出
基于获得的匹配点对,构建映射矩阵 Y ∈ { 0,1 } m × n ,匹配点对所在位置元素值为1,其它为0。从而获得模板图与待测图之间的相似度 S ( G ' , G , Y ) （式（14））,并通过遍历计算模板库中所有模板与待测图之间的相似度,取最大相似度对应模板图作为最终匹配结果 G * （式（15））,完成待测对象的识别。
S ( G ' , G , Y ) = α · S v 0 ' v 0 + β × ( ∑ S v i v j / ∑ Y ) （14）
G * = arg G i max ( S ( G ' , G i , Y i ) ) , i = 1,2 , ⋯ , N G （15）
式中： S v 0 ' v 0 为二者参考对象间的形状相似性, N G 为模板容量; α + β = 1 为调和系数。

2.4 实验数据

本文采用4份不同道路场景车载激光点云数据进行实验（图6）。其中数据1为Lynx Mobile Mapper系统采集的街区环境数据,场景中标线类别多样,其中虚线型类别种类繁多（图6(a)局部细节图①）,且部分标线因磨损存在部分缺失（图6(a)局部细节图②）;图6(b)为Trimble系统获取的街区场景数据,由于路面磨损以及其它因素影响,场景中标线存在部分缺失,影响识别（图6(b)局部细节图②）;图6(c)为StreeMapper系统采集的街区场景数据,场景中无斑马线,主要包含不同类别的虚线型标线以及异形转向标线（图6(c)局部细节图①）;图6(d)为StreeMapper系统获取的高速公路场景,场景为辅道与主道分离区域,其中无斑马线,主要包含大量虚线型标线（图6(d)局部细节图③）。
Fig. 6 Overview of the test datasets of four road scenarios

图6 4份不同道路场景的实验数据

由于目前没有现成的训练样本集,因此本文通过人工提取不同完整度、不同形状的人行横道预告标识线、单向转向箭头、双向转向箭头、直行箭头、线状标线作为基础正训练样本,部分如表1中正训练样本所示。同时提取其它地物作为负训练样本,部分如表1中负训练样本所示。通常扫描系统获取的点云位置信息较为精准,虽然受限于惯导精度、行驶速度,可能存在数据采集的畸变,但该畸变并不影响标线对象的整体形状结构。但鉴于部分标线对象因磨损、遮挡导致标线轮廓噪声和标线部分缺失,本文通过旋转、缩放、随机添加点噪声以及人工构建残缺标线等操作扩增训练样本总体容量,最终建立一个适用大部分情况的训练样本集（表2）。
Tab. 1 Manually established training samples(for preliminary classification of markings)

表1 人工构建训练样本（用于标线粗分类）

Tab. 2 Training sample set(for preliminary classification of markings) （个）

表2 训练样本集（用于标线粗分类）

直行箭头 人行横道预告标识线 单向转向箭头 双向转向箭头 线状标线 负样本
数量 554 746 770 480 866 560
由于目前没有可用于图匹配的模板样本集,本文依据道路标线国家标准GB5768-2009,为直行箭头、斑马线、虚线型标线3类标线对象构建多种不同邻域空间结构的模板样本。如表3所示,直行箭头共构建了5类模板,主要基于直行箭头邻域内特定标线对象的存在,如单向转向箭头;斑马线共有6套模板,主要根据其邻域中对象的排列方式,如在道路中央区域,斑马线邻域内至少存在3条互相平行的线状标线;虚线型标线共有9份模板,主要依据不同长度（ Len ）目标与不同间距（ Gap ）的排列方式,以及与特定目标的空间关系。
Tab. 3 Matching template samples(for fined classification of markings)

表3 匹配模板样本集（用于标线精细分类）

3 实验结果及分析

3.1 实验结果

为了减少道路环境中其他地物对标线提取的影响,本文预先采用扫描线快速提取路面点云。并结合基于强度校正的标线分割方法生成独立标线对象,利用Yu的层次分类方法提取小尺寸标线作为处理对象,结果如图7所示。
Fig. 7 Segmentation results of target markings (individual objects denoted in different colors)

图7 待分类标线对象分割结果（按分割后独立对象赋色）

如标线分割结果所示,大部分标线得到有效分割,生成独立标线对象,但仍然存在部分标线提取不完整,如图1(a)②中的#1,人行横道预告标识线由于道路磨损,只被提取出部分对象。针对上述分割结果,本文基于以上研究方法,采用如表4的参数设置,实现4份实验数据标线对象的精确识别。
Tab. 4 Parameter settings for road markings classification

表4 道路标线分类实验参数设置

参数 width S T α β
参数描述 格网宽度/m 距离上分区数目 角度上分区数目 参考对象属性权重 邻域空间结构权重
参数值 0.02 6 2 1/3 2/3
图8为不同格网宽度生成的图像结果。点云数据转换为图像受规则格网宽度大小影响：若格网尺寸设置过大,易造成图像中标线区域边界锯齿化、部分角点位置形状信息模糊（图8（e）、图8（f））;反之,易造成图像中标线区域出现较多空洞,影响形状区域信息描述（图8（b））。由于本文利用生成的图像进行区域形状特征Hu不变矩提取,部分空洞并不影响整体形状结构,因此图8（c）和图8（d）生成的图像能够满足基本要求。同时综合考虑算法效率,本文采用宽度 width 为0.02 m的规则格网剖分标线对象,生成二值图像（图8（d））,从而构建Hu不变矩。
Fig. 8 Estimation of the regular grid width about Hu invariant moments

图8 Hu不变矩特征相关规则格网宽度估计

以MBR提取的轮廓特征点为原点构建对数极坐标系,在对数距离上,将空间区域由内而外划分6等份,以与当前轮廓特征点相交的短边为起始边,长边为终止边,依据角度将空间区域划分2等份,基于各区域标线点分布情况,构建SSC。并结合MBR面积 Area 和延展度 U ,生成21维的形状特征向量描述标线对象,以此作为SVM输入数据进行模型的训练和对象的粗分类,结果如图9所示。
Fig. 9 Preliminary classification results of road markings based on SVM

图9 基于SVM的标线粗分类结果

从标线粗分类结果可以看出,大部分标线均能被正确识别。该方法不仅对完整的标线对象具有较好分类效果,同时对部分因磨损导致点云缺失的目标也能准确识别。如图9(a)②中的#5所示,缺失了一半的人行横道预告标识线亦能被正确识别。且对存在异形目标的单向转向标线提取较为鲁棒（如图9(c)①中的#4所示）。但由于直行箭头与线状标线在整体结构上较为相似,二者存在部分交叉错分情况（如图9(a)①中的#3和图9(b)③中的#1,图9(b)中②的#2）。此外,同为线状标线的虚线型标线与斑马线并未得到细分（图9(b)中的①）。
因此,本文针对粗分类结果中的直行箭和线状标线,依据模板图尺寸确定标线邻域,基于其邻域空间结构信息构建待测图,融合节点属性与边属性作为邻接节点的综合属性。并利用加权平均方法联合综合属性中各特征的相似度构建关联矩阵,依据关联矩阵,采用BBS算法实现节点匹配。并综合考虑参考对象间形状和邻域空间结构的相似性,设定调和系数 α 和 β 分别为1/3和2/3,计算出模板图与待测图的相似度,通过遍历提取最大相似度对应模板图作为最终匹配结果,实现标线的精细分类。
从图10精细分类结果中可以观察到,交叉错分的受损直行箭头（图10(b)③中的#1）和线状标线（图10(a)①中的#3和图10(b)②中的#2）得到有效纠正。并且,该优化方法能够有效识别粗分类结果中形状相似的斑马线和虚线型标线（图10(b)①）,同时,对于不同尺寸虚线型标线的识别具有较强鲁棒性（图10(a)①）。
Fig. 10 Refined classification results of road markings based on graph matching

图10 基于图匹配的标线精细分类结果

3.2 实验结果分析与精度评价

基于本文形状特征能较好识别具有显著形状差异的标线,但对形状相似标线的识别精度较低。为进一步分析基于图结构的图匹配方法对于形状相似标线识别的有效性,本文从4份数据中选取了3个典型场景的粗分类结果、图匹配情况以及优化结果作为分析数据（图11）。如图11（a）、图11（b）所示,受损直行箭头与线状标线形状相似,二者发生交叉错分,本文基于直行箭头两侧分别存在单向转向箭头这一语义结构特性,采用图结构建模描述,利用图匹配方法优化其分类结果。图11（d）所示,受损直行箭头图结构与其它类别模板图存在明显差异,相似度较低,而与所属类别对象相似度较高,从而实现受损直行箭头的精确识别（图11（g））。图11（h）所示,图匹配方法不仅可以有效解决线状标线错分情况,还能细化线状标线分类结果,精细区分虚线型标线与斑马线。图11（f）所示,错分虚线型标线（图11（c）中的#3）与长度、间隔均为3 m的模板图相似度最大,表明该方法能够精确识别不同尺寸目标、间距分布的虚线型标线。
Fig. 11 Shaped-smilar road markings misclassification optimization processes based on graph matching

图11 基于图匹配的形状相似标线错分情况优化过程

然而,本文方法仍存在部分误分类情况。如由于路面磨损,导致双向转向箭头对象发生过分割,保留了标线主要形状信息的部分被正确识别,但形状信息缺失较为严重的部分被误分为其它类（图12(a)）;部分过分割的单向转向箭头,一部分被错分为其它类,一部分由于形似线状标线,且在空间排列上与斑马线相似,因此被错分为斑马线（图12(b)）;部分小尺寸斑马线不呈现线状分布,在粗分类过程中被错分为其它类,从而无法进行图匹配优化（图12(c)）;此外,部分非线状标线由于形态结构与线状标线相似,且邻域空间结构同虚线型标线相似,导致其被错分为虚线型标线（图12(d)）。
Fig. 12 Road markings classification errors of intergrating SVM and graph matching

图12 结合SVM和图匹配的标线错误分类结果

由于实验数据中未提供真实参考数据,本文采用人工标定的方式,从场景点云数据中人工标定出本文待识别的6类道路标线。将单个独立对象视为质量评价参考对象,采用准确率（Precision）、召回率（Recall）以及综合评价指标F1-Measure值作为评价指标,统一分析4份数据中标线的识别精度：
Precision = TP TP + FP （16）
Recall = TP TP + FN （17）
F 1 - Measure = 2 × Precision × Recall Pr ecision + Recall （18）
式中： TP 为正确识别的数量; FP 为错误识别的数量; FN 为未被识别的数量。
如表5所示,基于形状特征的分类方法能够识别出大部分标线,特别是针对具有显著形状差异的标线拥有精确的检索效果。例如人行横道预告标识线、双向转向箭头的正确率、召回率以及F1-Measure值均达到100%;对比表5与表6可以发现,直行箭头的准确率、召回率和F1-Measure值分别从84.61%、91.67%、87.99%提升到100%,表明结合空间语义信息的图匹配方法,能够有效解决粗分类中受损直行箭头的错分问题。如表6所示,虚线型标线和斑马线准确率分别达到94.94%、99.25%,召回率分别达到98.21%和99.00%,F1-Measure值分别达到96.59%、99.12%,说明该方法能够有效区分形状相似的线状标线,准确识别虚线型标线和斑马线。此外,实验数据中单向转向标线分类精度相对较低,这是由于在标线分割过程中,部分标线因磨损严重导致过分割和欠分割,从而使得其发生错分。
Tab. 5 Accuracy of road markings' preliminary classification results based on SVM

表5 基于SVM的标线粗分类结果精度

类别 TP FP FN 精度/% 召回率/% F1-Measure/%
直行箭头 11 3 1 84.61 91.67 87.99
人行横道预告标识线 25 0 0 100 100 100
单向转向箭头 16 1 2 94.12 88.89 91.43
双向转向箭头 5 0 0 100 100 100
线状标线 1053 38 17 96.61 98.41 97.5
Tab. 6 Accuracy of road markings' refined classification results based on graph matching

表6 基于图匹配的标线精细分类结果精度

类别 TP FP FN 精度/% 召回率/% F1-Measure/%
直行箭头 12 0 0 100 100 100
人行横道预告标识线 25 0 0 100 100 100
单向转向箭头 16 1 2 94.12 88.89 91.43
双向转向箭头 5 0 0 100 100 100
虚线型标线 658 35 12 94.94 98.21 96.59
斑马线 396 3 4 99.25 99 99.12
为进一步说明本文实验效果,采用文献[14]中标线识别方法与本文方法进行对比,对比结果如表7所示。从表中可以看出,二者针对人行横道预告标识线和双向转向箭头的识别效果皆较为精准,说明二者对具有显著形状差异标线的区分能力较强。然而,与本文方法相比,文献方法对于直行箭头的识别效果较差,这是因为直行箭头与线状标线形状较为相似,而文献方法中构建的空间语义结构只适用于线状标线。相对而言,本文构建的图结构能较好描述直行箭头的空间结构模式,从而有效识别直行箭头。此外,本文方法针对虚线型标线和斑马线的精细区分效果相比文献方法较好：二者识别虚线型标线的准确率基本一致,但本文方法的召回率、F1-Measure值均高于文献方法。这是因为文献方法中基于语义信息的分类方法,依赖人工经验阈值,且空间语义结构较为单一,对存在部分空间结构缺失的目标识精度较低。而本文基于非精确匹配的图匹配方法,能够较好地识别存在属性、结构差异的目标。
Tab. 7 Quantitative evaluation of the markings classification performance of Yu methods and ours

表7 Yu方法与本文方法标线分类对比精度

方法 类别 精度/
%		 召回率/
%		 F1-Measure/%
Yu方法[14] 直行箭头 75 100 85
人行横道预告标识线 100 100 100
单向转向箭头 88.89 88.89 88.89
双向转向箭头 100 100 100
虚线型标线 93.24 97.89 95.51
斑马线 99.46 92.73 95.97
本文方法 直行箭头 100 100 100
人行横道预告标识线 100 100 100
单向转向箭头 94.12 88.89 91.43
双向转向箭头 100 100 100
虚线型标线 94.94 98.21 96.59
斑马线 99.25 99.00 99.12

4 结论

本文利用Hu不变矩、SSC、MBR面积以及延展度构建能够综合描述标线对象全局区域特性和轮廓信息的形状描述子,利用SVM实现标线对象的粗分类。该方法能够准确的区分形状差异较大的标线类别（如实验中人行横道预告标识线、双向转向箭头的分类精度均达到100%）,但是,难以区分直行箭头和线状标线等形状相似的标线类别。
针对粗分类结果中难以有效区分的直行箭头和线状标线,本文提出基于标线的形状特征及其与邻域中对象的空间拓扑关系进行图结构建模,利用图匹配方法有效优化受损直行箭头与线状标线的交叉错分结果,同时精细区分线状标线中的虚线型标线与斑马线。从实验结果中可以观察到,相较于现有方法,本文方法关于空间语义信息的运用独立于人工阈值,同时,采用允许一定属性、结构差异的非精确匹配方法进行标线识别能够很好地适用于存在标线残缺、磨损、遮挡的复杂道路环境,方法更具稳健性。
目前,本文方法主要针对直行箭头、线状标线进行研究,在后续的学习工作中将结合现有的问题进一步研究,为更多标线类别构建模板样本库,扩展算法的适用范围,以构建一种适用于大部分类别的统一的标线特征结构。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Wu T, Ranganathan A.A practical system for road marking detection and recognition[C]. Intelligent Vehicles Symposium, 2012:25-30.

[2]
Mathibela B, Newman P, Posner I.Reading the road: Road marking classification and interpretation[J]. IEEE Transactions on Intelligent Transportation Systems, 2015,16(4):2072-2081.

DOI

[3]
Danescu R, Nedevschi S.Detection and classification of painted road objects for intersection assistance applications[C]. International IEEE Conference on Intelligent Transportation Systems, 2010:433-438.

[4]
Guan H, Li J, Yu Y, et al.Using mobile laser scanning data for automated extraction of road markings[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014,87:93-107.

DOI

[5]
Guan H, Li J, Yu Y, et al.Using mobile LiDAR data for rapidly updating road markings[J]. IEEE Transactions on Intelligent Transportation Systems, 2015,16(5):2457-2466.

DOI

[6]
Guan H, Li J, Yu Y, et al.Automated road information extraction from mobile laser scanning data[J]. IEEE Transactions on Intelligent Transportation Systems, 2015,16(1):194-205.

DOI

[7]
Chen X, Kohlmeyer B, Stroila M, et al.Next generation map making:geo-referenced ground-level LIDAR point clouds for automatic retro-reflective road feature extraction[C]. ACM Sigspatial International Symposium on Advances in Geographic Information Systems, Acm-Gis 2009, November 4-6, 2009, Seattle, Washington, Usa, Proceedings, 2009:488-491.

[8]
Riveiro B, González-Jorge H, Martínez-Sánchez J, et al.Automatic detection of zebra crossings from mobile LiDAR data[J]. Optics & Laser Technology, 2015,70:63-70.

[9]
Cheng M, Zhang H, Wang C, et al.Extraction and classification of road markings using mobile laser scanning point clouds[J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2017,10(3):1182-1196.

DOI

[10]
Yang M, Wan Y, Liu X, et al.Laser data based automatic recognition and maintenance of road markings from MLS system[J]. Optics & Laser Technology, 2018,107:192-203.

[11]
Jaakkola A, Hyyppä J, Hyyppä H, et al.Retrieval algorithms for road surface modelling using laser-based mobile mapping[J]. Sensors, 2008,8(9):5238.

DOI

[12]
Mancini A, Frontoni E, Zingaretti P.Automatic road object extraction from Mobile Mapping Systems[C]. Ieee/asme International Conference on Mechatronics and Embedded Systems and Applications, 2012:281-286.

[13]
Yang B, Fang L, Li Q, et al.Automated extraction of road markings from mobile LIDAR point clouds[J]. Photogrammetric Engineering & Remote Sensing, 2012,78(4):331-338.

[14]
Yu Y, Li J, Guan H, et al.Learning hierarchical features for automated extraction of road markings from 3-D mobile LiDAR point clouds[J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2015,8(2):709-726.

DOI

[15]
Soilán M, Riveiro B, Martínez-Sánchez J, et al.Segmentation and classification of road markings using MLS data[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2017,123:94-103.

DOI

[16]
Hervieu A, Soheilian B, Brédif M. Road marking extraction using a model& data-Driven Rj-Mcmc[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2015,II-3/W4:47-54.

[17]
Yang B, Fang L, Li J.Semi-automated extraction and delineation of 3D roads of street scene from mobile laser scanning point clouds[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2013,79:80-93.

DOI

[18]
Hu M.Visual pattern recognition by moment invariants[J]. Information Theory Ire Transactions on, 1962,8(2):179-187.

[19]
Premachandran V, Kakarala R.Perceptually motivated shape context which uses shape interiors[J]. Pattern Recognition, 2013,46(8):2092-2102.

DOI

[20]
罗海峰,方莉娜,陈崇成.车载激光扫描数据路坎点云提取方法[J].地球信息科学学报,2017,19(7):861-871.

[ Luo H F, Fang L N, Chen C C.Curb point clouds extraction from vehicle-borne laser scanning data[J]. Journal of Geo-information Science, 2017,19(7):861-871. ]

[21]
彭晨,余柏蒗,吴宾,等.基于移动激光扫描点云特征图像和SVM的建筑物立面半自动提取方法[J].地球信息科学学报,2016,18(7):878-885.<p>建筑物立面是城市地物的重要组成部分,而移动激光扫描是获取城市地物三维信息的重要手段之一。本文提出了一种基于移动激光扫描点云的建筑物立面半自动提取算法。该方法首先构建研究区水平网格;然后计算局部点云几何特征,并且将特征投影到水平网格生成点云特征图像;接着基于支持向量机（Support Vector Machine,SVM）对建筑物立面网格进行粗提取;最后使用网格属性（形状系数、网格面积、最大高程）对粗提取结果进行过滤,并将结果反投影到三维空间中得到精确的建筑物立面。以卡内基梅隆大学的移动激光扫描点云进行试验后表明,本算法能够较好地提取出建筑物立面,提取精度为84%,召回率为90%,数据修正后精度为88%,召回率为91%。通过与现有算法对比,本文提出的算法具有较高精度。</p>

DOI

[ Peng C, Yu B L, Wu B, et al.A method for semiautomated segmentation of building facade from mobile laser scanning point cloud based on feature images and SVM[J]. Journal of Geo-information Science, 2016,18(7):878-885. ]

[22]
熊伟成,杨必胜,董震.面向车载激光扫描数据的道路目标精细化鲁棒提取[J].地球信息科学学报,2016,18(3):376-385.<p>精确的三维道路信息,对于交通运输,城市规划,道路网建设,三维道路建模等具有重要意义.车载移动测量系统作为一项高新测绘技术能快速,准确地获取三维激光点云,适用于大场景的道路提取与建模.本文提出了一种从车载激光点云中快速精细化提取三维道路及其边界的方法.该方法首先利用车载激光点云的空间特征对点云进行自适应分段,然后利用先验知识与规则提取候选的道路及其边界,并根据道路边界的线状特征,对所提取的道路边界进行跟踪及矢量化,最后得到道路的参数.为了验证本方法的有效性,试验采用了3组不同道路场景的数据进行验证,结果表明提取结果的准确度,完整度及检测质量都达到了90%以上.定量与定性的结果分析表明,本文方法对于不同复杂场景下不同点密度的数据具有很好的适应性,能快速,鲁棒地提取大场景内的道路及其边界.</p>

DOI

[ Xiong W C, Yang B C, Dong Z.Refining and robust extraction of roads from mobile laser scanning point clouds[J]. Journal of Geo-information Science, 2016,18(3):376-385. ]

[23]
Foggia P, Percannella G, Vento M.Graph matching and learning in pattern recognition in the last 10 years[J]. International Journal of Pattern Recognition & Artificial Intelligence, 2014,28(1):1450001.

[24]
项英倬,谭菊仙,韩杰思,等.图匹配技术研究[J].计算机科学,2018,45(6):33-37,51.

[Xiang Y Z, Tan J X, Han J S. Survey of graph matching algorithms[J]. Computer Science, 2018,45(6):33-37,513. ].

[25]
Hartley R, Zisserman A.Multiple view geometry in computer vision[M]. UK: Gambridge University Press,2003.

[26]
Szegedy C, Vanhoucke V, Ioffe S, et al.Rethinking the Inception Architecture for Computer Vision[C]. Computer Vision and Pattern Recognition, 2016:818-2826.

[27]
Wold S.Pattern recognition by means of disjoint principal components models[J]. Pattern Recognition, 1976,8(3):127-139.

DOI

[28]
陈占龙,周林.基于方向关系矩阵的空间方向相似性定量计算方法[J].测绘学报,2015,44(7):813-821.<p>介绍了一种多尺度空间对象的方向关系表达模型以及基于该模型的方向相似度度量方法。该方向关系模型对方向关系矩阵模型进行了改进,根据空间对象的形状定量描述空间对象之间的方向关系;借鉴平衡传输问题的解决方法计算方向矩阵间最小转换代价,即方向矩阵间的距离,从而量化方向对间的差异,最终获得任意尺度空间对象的方向相似度并对其进行比较。对不同尺度空间对象的方向相似性的试验表明,该方法简单可行且不失精度,结果符合人类认知。</p>

DOI

[ Chen Z L, Zhou L, et al. A quantitative calculation method of spatial direction similarity based on direction relation matrix[J]. Acta Geodaetica et Cartographica Sinica, 2015,44(7):813-821.].

[29]
Dekel T, Oron S, Rubinstein M, et al.Best-Buddies Similarity for robust template matching[C]. Computer Vision and Pattern Recognition, 2015.2021-2029.

[30]
王刚,孙晓亮,尚洋,等.一种基于最佳相似点对的稳健模板匹配算法[J].光学学报,2017(3):274-280.

[ Wang G, Sun X L, S Y,et al. A robust template matching algorithm based on eest-buddies similarity[J]. Acta Optica Sinica,2017(3):274-280. ]

[31]
Dangerfield J.Linear programming and its applications by J. K. Strayer[J]. Mathematical Gazette,1990,74(470):402-403.

DOI

Options
Outlines

/

〈 〉