《测绘学报》

构建与学术的桥梁 拉近与权威的距离

做推荐算法有关的毕业设计(论文推荐马超志愿者地理信息中天桥的自动识别方法)(1)

志愿者地理信息中天桥的自动识别方法

马超1, 孙群1, 陈换新2, 徐青1, 杨辉3

1. 信息工程大学地理空间信息学院, 河南 郑州 450000;

2. 96633部队, 北京 100096;

3. 69027部队, 新疆 乌鲁木齐 830002

收稿日期:2016-02-22; 修回日期:2016-11-16

基金项目:国家863项目(2012AA12A404);国家自然科学基金(41571399;41201391;41071297;41201469)

第一作者简介:马超(1988-),男,博士生,主要从事多源空间数据融合处理与数字地图制图研究。

通信作者: 孙群

摘要:基于天桥的几何与属性特征,提出了一种志愿者地理信息中自动识别天桥的方法。天桥从几何结构上可分为主桥和附属设施两个部分,主桥部分特征鲜明,可以视为两类分类问题,依据其几何特征和属性特征构建特征空间,利用支持向量机的方法进行识别;附属设施部分可依据已识别的天桥主桥,按照路段的长度、属性等判定规则进行识别,从而完成整个天桥的自动识别。以北京市OpenStreetMap(osm)数据进行试验验证的结果表明,本文提出的方法能有效地识别出志愿者地理信息中的典型天桥结构,可以为志愿者地理信息道路网的多尺度建模与化简、步行导航等提供帮助。

The Recognition of Overpass in Volunteered Geographic Information

MA Chao1, SUN Qun1, CHEN Huanxin2, XU Qing1, YANG Hui3

Abstract: The paper presents an overpass recognition method in volunteered geographic information based on the geometry and attribute characteristics. The structure of the overpass is divided into the main bridge parts and the affiliated facilities. The main bridge parts with distinctive characters could be treated as a two-class classification problem. The characteristic vectors could build on the foundation of analysis and quantization the geometry and attribute characteristics. Then, the main bridge is recognized automatically through the support vector machine. The affiliated facilities of the overpass are recognized based on the main bridge with some relevant judgment rules. The OpenStreetMap(osm) is selected for the experiment. The results show that the method could effectively recognize the overpass and could provide help for the road simplification and walking guidance.

Key words: overpass structure recognition support vector machine volunteered geographic information

天桥是路口或交通繁忙路线上的跨桥,一般用来供行人或非机动车辆跨越道路。随着我国一线城市交通压力的不断增大,天桥作为一种解决人车矛盾的立体交通分离方式,作用日益突出,成为城市主干道路以及主要交叉路口不可或缺的一部分,也是步行导航、路径规划和可达性分析的重要内容。一般地理数据中天桥数据相对较少且现势性较差,而志愿者地理信息(volunteered geographic information,VGI)[1]却包含了大量的天桥数据。VGI是由广大志愿者自愿上传、维护的地理信息,逐渐成为地理信息数据获取的重要手段之一,能够应用于应急制图、出行导航、基础地理信息更新等诸多领域[2-8]。VGI中天桥的识别与提取对于补充导航数据、深化VGI应用等具有重要的意义。

天桥属于道路网中的微观结构。近几年,道路网数据中微观结构的识别已成为道路网综合的重要研究内容[9-13],研究多集中在道路交叉口、平行路等的识别方面。目前道路交叉口识别的研究较多,文献[14]采用了“定位——识别”的道路交叉口探测思路,首先利用道路交叉口区域节点密度较大的特征进行定位,再根据图形化简的方式进行识别化简;文献[15]则基于图形结构模式识别的思想进行道路交叉口识别,利用有向属性关系图的方法建立交叉口结构库,然后再通过对比的方式进行识别;文献[16]提出了一种基于道路功能分析的VGI交叉口识别方法;文献[17]提出了一种利用道路类别和拓扑关系的立交桥整体识别方法平行路的识别方面,文献[18]提出了一种基于多边形形态分析的平行车道识别方法。

目前还没有关于天桥数据的识别与应用的研究,为此本文提出了一种VGI中天桥的自动识别算法,从天桥的结构特征出发,识别过程分为主桥的识别和附属设施的识别两个步骤。主桥由于特征鲜明,可视为一种两类分类问题;附属设施部分由于与主桥连接,可根据已经识别的主桥按照相关的判定规则进行识别。最后以VGI最成功的项目OpenStreetMap(OSM)数据为试验对象,对所提出的方法进行试验验证。

1 天桥的自动识别1.1 天桥特征分析与量化表达

天桥一般由横跨道路的主桥和供上下桥的附属设施构成,主要作用是引导行人安全地穿越道路,而不影响道路中车辆的正常行驶。天桥在OSM数据中以线的方式进行存储。OSM数据包括点、线和关系等3种基本结构,其中线包括非闭合线、闭合线和区域等,由不超过2000个点构成,非闭合线表示铁路、公路等线要素,闭合线表示环形的线要素,如环形地铁、环形交叉口等。OSM数据中并没有针对微观结构的特殊标识,典型的天桥结构如图 1所示。

做推荐算法有关的毕业设计(论文推荐马超志愿者地理信息中天桥的自动识别方法)(2)

图 1 OSM数据中的天桥Fig. 1 An overpass in OSM

天桥作为一种城市道路微观结构,其位置、方向、形状和规模及属性信息等几个方面,具有明显的特征。

(1) 位置和方向。天桥的主桥横跨在道路上,与其横跨的道路方向垂直或近似垂直。天桥一般修建在城市的主干道路上,主干道路在OSM数据中则是多条平行路。天桥的附属设施则与道路方向平行或近似平行。

(2) 形状和规模。位于非交叉口的天桥一般只有一个主桥,形状为“工”、“士”或“王”等。位于交叉口的天桥主桥可能是环形的,或呈现“井”字的形状。主桥长度相对于一般道路而言较小,与道路的宽度相当。

(3) 属性信息。OSM数据不仅包含了天桥的几何信息,还包含了丰富的属性信息,尤其是道路类别,可以作为甄别天桥与其他道路的特征之一。OSM数据中,道路的类别一共有29种,但是天桥的道路类别可能取值只有9种,常见的类别是“footway”。

综上所述,主桥的特征较为明显:与道路方向垂直或近似垂直,长度稍大于道路宽度,道路类别取值范围有限。因此,这些明显的特征可以用来构造特征向量,构成两类分类问题,进而利用机器学习的方法解决主桥的判断问题。本文使用4个指标对主桥的特征进行量化表达,即方向角、横跨度、长度和道路类别,如表 1所示。

表 1 主桥特征的量化表达Tab. 1 The quantitative expression of the main bridge

特征量化描述说明
位置特征方向角 主桥与其横跨道路的夹角
形状特征长度主桥的长度
属性特征道路类别主桥的道路类别

(1) 方向角。方向角指主桥与所跨越道路的夹角。设主桥L1([x1,y1],[x2,y2]),道路段L2([x′1,y′1],[x′2,y′2]),则方向角θ的计算为

(1)

对于圆盘形的天桥主桥,定义其方向角为0°。

(2) 横跨度。主干道路在OSM数据中一般以多条平行路的方式呈现,核心的主干道路一般是4条平行路,次要的主干道路为两条平行路。是否与主干道路相交是识别天桥的特征之一,为了量化表示这种特征,本文提出了横跨度的概念。横跨度指主桥与道路的交点个数。横跨度越大,表示主桥跨越的道路等级越高。横跨度与主桥长度具有一定的相关性:横跨度大的主桥,长度会稍长。但是,横跨度的本质是反映道路的重要程度,这种重要程度不只与道路宽度相关,还与道路的位置、地位相关。

(3) 道路类别。OSM数据中,道路类别以标签对的形式存在,如“highway=tertiary”。与其他特性相比,道路类别的取值为字符串,难以进行比较。本文采用文献[19]中提出的处理方法,将OSM数据中可能是天桥的9种类别合并成一个,取值为1;其他道路类型合并为一个,取值为0。

1.2 利用SVM方法自动提取

支持向量机(support vector machine,SVM)作为一种典型的两类分类算法,具有较强的稳健性,本文采用SVM的方法对VGI数据中的天桥主桥结构进行识别。SVM基本原理如式(2)所示[19]

(2)

式中,||w||为法向量w的范数,XiYi为样本集,N为样本集数量。式(2)可通过引入Lagrange函数转换为对偶问题,如式(3)[19]所示

(3)

式中,sgn为符号函数;a*b*为确定最优分类超平面的参数;K(xi,x)为SVM的核函数,常见的核函数包括线性内核、多项式内核、径向基函数(RBF)和S形内核等,核函数的形式和参数设置决定了SVM分类器的类型和效率。根据上述天桥的特征空间以及测试效果,论文选择径向基函数(RBF)作为核函数。

SVM的分类过程分为训练阶段和分类阶段两个步骤:首先,需要已知分类结果的样本库对SVM进行训练,得到分类效果较好的分类器。为了提高分类器的正确率,一般的样本训练均采取交叉验证的方式进行,将样本分为训练样本和验证样本两个部分,利用训练样本进行训练,再用验证样本测试训练器分类结果;其次,得到分类器之后,可用于未知分类的样本,根据式(3)中f(X)的值进行判断分类结果:值为1,则为正例(即天桥);反之,则为负例(即非天桥)。

1.3 天桥附属设施的识别

天桥附属设施是指连接天桥主桥两端,供行人上下桥的阶梯。与主桥相比,附属设施的特征不够明显,不适合SVM方法进行自动识别。与天桥主桥相比,附属设施的道路类型取值范围与主桥相同,且附属设施的长度较短,可通过设置一个长度阈值进行判别。因此,附属设施可以通过与已识别主桥的连接关系,依据附属设施的道路类型取值和长度阈值等判断规则进行识别,主要步骤如图 2所示。

做推荐算法有关的毕业设计(论文推荐马超志愿者地理信息中天桥的自动识别方法)(3)

图 2 天桥附属设施判别流程Fig. 2 The judgement flow of the affiliated facilities

(1) 遍历已识别的主桥,对于任一个未标记主桥,查找与其相交的所有路段,构成候选路段集。

(2) 遍历候选路段,对于任一个未标记路段,获取其道路类别,判断是否属于可能是天桥的9种取值:若是,则保留该路段;反之,将其标记为非天桥。

(3) 遍历剩余候选路段,判断其是否存在与之相连接的路段,若有,则将其合并成新的候选路段,继续判断,直到合并其所连接的所有路段;若无相连接的路段,则转入步骤(4)。

(4) 进行附属设施长度判断。设置附属设施长度阈值LM,如果路段长度超过该阈值,则认为该路段不是天桥,将其标记为非天桥;反之,则标记为天桥。

(5) 重复步骤(1)—(4),直到所有主桥的所有候选路段集标记完毕后,结束识别过程。将主桥与其附属设施连接到一起,构成完整的天桥结构。

2 试验与分析2.1 试验数据

用于训练和测试的试验数据选取北京、上海、深圳3个城市部分城区的OSM数据,建立样本集共计500条,其中天桥数据187条,非天桥数据313条。这些样本数据中,天桥附属设施的平均长度为225 m,其中最长为400 m,为保证试验结果,本次试验设长度阈值LM=600 m。部分样本集如表 2所示,其中,特征空间依次为天桥的长度、方向角、横跨度和道路属性,类别1表示该路段属于天桥主桥,类别-1表示该路段不是天桥主桥。

表 2 部分样本数据示例Tab. 2 Examples of some sample data

样本ID样本截图特征空间类别
1{85,90,4,1}1
2{95,88,4,1}1
3{40,91,2,1}1
4{63,29,2,2}-1
5{113,90,2,1}1
6{69,0,4,1}1
7{61,0,4,1}-1
8{79,0,4,2}-1
500{32,90,2,1}-1

2.2 SVM训练与测试

在进行交叉验证时,可将500个样本通过随机的方式分成10组,每组包含50个样本,并随机抽取一组样本用于测试训练结果,其他样本进行训练。为提高分类器的分类正确率,训练过程一共进行10次交叉验证,试验结果如表 3所示。

表 3 试验结果Tab. 3 Experiment results

(%)
试验次数准确率错误率召回率负召回率
192893.3490
2901088.8990.31
39469593.34
4861492.5990.47
592884.6287.5
6861494.8490.33
7901085.7286.21
892888.8990.63
9881287.596.16
1094610090.33
平均值90.49.691.1490.5

试验平均耗时16.3 s,由表 3可得,试验的平均正确率为90.4%,错误率为9.6%,正确率较高还不能表明天桥识别效果较好。为此,需要计算上述分类结果的真正率和真负率。其中,真正率是正类样本被正确分类的比率,真负率是被正确分类的负样本的比率。上述试验结果的真正率和真负率分别为91.14%和90.5%,较高的真正率和真负率表明,该算法能够很好地区分天桥与非天桥。未能正确识别的天桥主要是一些位于复杂道路交叉口的天桥,路段的几何特征与天桥相似,难以进行区分。

2.3 算法的应用

将上述分类器应用到未知分类的OSM数据中。试验数据为北京市城区部分(异于样本集中的数据),采用ArcGIS10.2.2 Visual Studio 2010 Matlab 2009a进行编程实现,设置长度阈值LM=600 m,识别后的部分运行效果如图 3所示。

做推荐算法有关的毕业设计(论文推荐马超志愿者地理信息中天桥的自动识别方法)(4)

图 3 算法应用效果Fig. 3 The application result of the algorithm

经过实地考察论证,该区域一共有25座天桥,分布在8条道路上。该算法能够识别22座,错误识别2座,未能识别3座。该试验结果的召回率为90.9%,该结果与SVM分类器训练测试的结果基本一致。其中部分未能正确识别的具体情况如图 4所示。

做推荐算法有关的毕业设计(论文推荐马超志愿者地理信息中天桥的自动识别方法)(5)

图 4 未能正确识别的天桥Fig. 4 The incorrect recognized overpass in the experiment

图 4(a)是未能识别的天桥,未能识别的原因是该天桥结构较为特殊,主桥成圆形,该种类型的天桥往往位于道路交叉口处,容易与环形的道路混淆(如表 2中的样本5),并且该种类型的天桥样本数量较少(SVM训练样本中,只有1个圆盘形天桥的样本),因此在SVM分类时,没有成功识别;图 4(b)属于过度识别的情况,主桥部分识别没有问题,但是在识别附属设施时,错误地将附属设施所连接的非天桥路段识别为天桥,表明上述附属设施的判别规则还存在一定的不足;图 4(c)展示了一种错误将非天桥路段识别为天桥的情况,由于该路段与天桥特征极为相似,经实地考察证实,该路段实际为一部分步行道。

上述试验结果表明,对于一般形态的天桥,本文算法识别正确率较高;对于位于道路交叉口位置的天桥,如果主桥由不同的桥段构成(如样本5),算法在识别时将其作为多个不同的天桥进行识别,正确率也较高。但是对于圆盘形的主桥,主桥形态较为特殊,与环形道路交叉口路段几何特征类似,且该种类型天桥较少,因此难以有效识别。

2.4 与现有算法的比较

本文研究的范围属于道路结构的微观识别问题,与道路交叉口的识别问题本质相同,因此有必要与现有的道路交叉口识别方法进行比较。文献[15]提出了一种基于属性关系图的道路交叉口识别方法,是比较典型的道路交叉口识别算法。从适用范围上讲,本文方法主要利用天桥的几何结构特征和属性特征进行识别,适用于各种形状的天桥,而文献[15]的方法则依赖于模板库的完整性,仅能够识别已定义好的天桥结构。但是如果模板定义良好,可以识别较复杂的天桥结构,并且能够保证识别结果的准确性。两种方法的比较如表 4所示。

表 4 两种方法对比Tab. 4 The comparison of the two methods

特征本文方法文献[15
适用范围典型天桥结构典型天桥结构
识别原理先识别主桥,再附属设施结构描述与比较
优点能够适应各种不同的天桥结构能够保证识别结果的正确性
缺点无法识别圆盘形等复杂天桥结构不能有效识别模板库以外的天桥结构

上述两种方法各有优缺点,应用时可以互相补充,可利用本方法识别一般的天桥结构,对于诸如圆盘形等本文方法无法识别的天桥结构,可利用文献[15]的方法定义这些天桥的结构模板库,并进行识别。

3 结 论

天桥作为一种重要的道路设施,在步行导航、可达性分析中占有重要地位,但是目前天桥数据匮乏、现势性差,因此研究VGI中天桥数据的识别与提取具有重要的理论意义和实用价值[20-21]。本文提出的基于SVM分类思想的天桥识别方法,首先利用SVM识别特征较为明显的主桥,然后再利用附属设施与主桥连接的特性对其进行识别,从而完成天桥的整体识别。试验结果表明,本文提出的方法能够较好地识别VGI数据中典型的天桥结构,但是对于特殊结构的天桥,如不是横跨主干道的天桥、主桥为圆盘形的天桥等,还不能很好地自动识别,还存在将数据中类似于天桥结构的路段错误地识别为天桥的情况。未来的研究应该继续挖掘天桥的更多特征,提高特殊天桥结构的识别能力。

【引文格式】马超,孙群,陈换新,等。 志愿者地理信息中天桥的自动识别方法[J]. 测绘学报,2017,46(2):246-252. DOI: 10.11947/j.AGCS.2017.20160070

,