留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

利用路段分类识别复杂道路交叉口

马超 孙群 陈换新 温伯威

马超, 孙群, 陈换新, 温伯威. 利用路段分类识别复杂道路交叉口[J]. 武汉大学学报 ● 信息科学版, 2016, 41(9): 1232-1237. doi: 10.13203/j.whugis20160073
引用本文: 马超, 孙群, 陈换新, 温伯威. 利用路段分类识别复杂道路交叉口[J]. 武汉大学学报 ● 信息科学版, 2016, 41(9): 1232-1237. doi: 10.13203/j.whugis20160073
MA Chao, SUN Qun, CHEN Huanxin, WEN Bowei. Recognition of Road Junctions Based on Road Classification Method[J]. Geomatics and Information Science of Wuhan University, 2016, 41(9): 1232-1237. doi: 10.13203/j.whugis20160073
Citation: MA Chao, SUN Qun, CHEN Huanxin, WEN Bowei. Recognition of Road Junctions Based on Road Classification Method[J]. Geomatics and Information Science of Wuhan University, 2016, 41(9): 1232-1237. doi: 10.13203/j.whugis20160073

利用路段分类识别复杂道路交叉口

doi: 10.13203/j.whugis20160073
基金项目: 

国家863计划 2012AA12A404

国家自然科学基金 41571399

国家自然科学基金 41201391

国家自然科学基金 41071297

国家自然科学基金 41201469

详细信息
    作者简介:

    马超, 博士生, 主要从事多源空间数据融合处理与数字地图制图研究。jielong018@126.com

  • 中图分类号: P208;P283.1

Recognition of Road Junctions Based on Road Classification Method

Funds: 

The National 863 Program of China 2012AA12A404

the National Natural Science Foundation of China 41571399

the National Natural Science Foundation of China 41201391

the National Natural Science Foundation of China 41071297

the National Natural Science Foundation of China 41201469

More Information
    Author Bio:

    MA Chao, PhD candidate, specializes in multi-sourced spatial data fusion and digital mapping. E-mail: jielong018@126.com

图(7) / 表(3)
计量
  • 文章访问数:  1960
  • HTML全文浏览量:  62
  • PDF下载量:  472
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-02-29
  • 刊出日期:  2016-09-05

利用路段分类识别复杂道路交叉口

doi: 10.13203/j.whugis20160073
    基金项目:

    国家863计划 2012AA12A404

    国家自然科学基金 41571399

    国家自然科学基金 41201391

    国家自然科学基金 41071297

    国家自然科学基金 41201469

    作者简介:

    马超, 博士生, 主要从事多源空间数据融合处理与数字地图制图研究。jielong018@126.com

  • 中图分类号: P208;P283.1

摘要: 道路网数据中微观结构的识别对于多尺度路网建模、步行导航等至关重要。复杂道路交叉口是重要的道路微观结构之一,针对目前道路复杂交叉口基于几何形状描述与图形匹配识别方法存在的不足,从复杂交叉口识别与化简的角度出发,提出了一种利用路段分类进行复杂道路交叉口识别与化简的方法。该方法首先通过点密度聚类的方法对道路交叉口进行定位,然后利用路段的规模、形状和属性等特征构建特征空间,将交叉口的识别作为一种区分主干路段与辅助路段的两类分类问题,利用支持向量机的方法对交叉口区域内的路段进行分类,从而完成交叉口的识别与化简。利用开放街道地图(Open Street Map)数据进行实验,结果表明,该方法能够有效地识别道路交叉口。

English Abstract

马超, 孙群, 陈换新, 温伯威. 利用路段分类识别复杂道路交叉口[J]. 武汉大学学报 ● 信息科学版, 2016, 41(9): 1232-1237. doi: 10.13203/j.whugis20160073
引用本文: 马超, 孙群, 陈换新, 温伯威. 利用路段分类识别复杂道路交叉口[J]. 武汉大学学报 ● 信息科学版, 2016, 41(9): 1232-1237. doi: 10.13203/j.whugis20160073
MA Chao, SUN Qun, CHEN Huanxin, WEN Bowei. Recognition of Road Junctions Based on Road Classification Method[J]. Geomatics and Information Science of Wuhan University, 2016, 41(9): 1232-1237. doi: 10.13203/j.whugis20160073
Citation: MA Chao, SUN Qun, CHEN Huanxin, WEN Bowei. Recognition of Road Junctions Based on Road Classification Method[J]. Geomatics and Information Science of Wuhan University, 2016, 41(9): 1232-1237. doi: 10.13203/j.whugis20160073
  • 道路网数据是地理信息数据的重要组成部分,能够为智能导航、位置服务、拥堵分析等提供重要信息[1]。虽然我国已经建立了全国基础道路网多尺度数据库系统,但是不同尺度数据之间的建模依然存在一些问题[2-5]。道路网多尺度建模包括道路网的选取和局部结构的简化两个方面的内容[6]。经过多年的研究,道路网的选取获得了较大的进展,而道路网中局部结构的识别与化简近几年成为了道路网综合的重要研究内容。

    目前为止,一些学者已经初步开展了道路网局部结构识别方面的研究,关于道路交叉口识别的研究,文献[7]提出了一种基于道路结点密度的非结构化探测方法,利用道路结点密度定位道路交叉口,采用图化简的方式进行化简。该方法简单方便,但是只能识别道路网中的结点密集区,难以识别交叉路口。文献[8]提出了一种基于有向属性关系图及图匹配的交叉口识别方法,利用有向属性关系图描述交叉口结构,并通过构建典型结构模板库进行识别,但是对于非典型的交叉口却不能有效识别。文献[9]提出了一种基于道路功能分析的自发地理信息数据交叉口识别方法,却依赖属性信息中的道路功能字段,对于缺乏这种属性信息的数据不能有效识别。文献[10]提出了一种利用道路类别和拓扑关系的立交桥整体识别方法,根据道路类别及数量建立典型立交桥结构模板库,通过与模板库的结构对比来识别新的图形结构,对于模板库中没有的新结构的识别效果不够理想。

    综上所述,目前的方法基本都属于整体识别的方法,通过一定的方法对交叉口进行数学描述,建立典型交叉口的形状模板库,然后再通过图形匹配的方法进行识别。该方法对于典型的交叉口具有很好的识别能力,但由于复杂交叉口形态多样,难以进行精确描述和建立模板库,识别效果较差。此外,利用这类方法仅识别了交叉口的空间位置,对路段的归类没有进行有效识别,不能对进一步的化简处理提供有用信息。属性信息中包含了道路类型等重要信息,与几何数据相结合可以大大增强算法的识别能力。但是,上述方法只充分利用了几何信息,对于属性信息的利用不足。

    针对复杂交叉口的识别问题,本文从交叉口化简的角度出发,寻找新的解决方案。不同尺度下的交叉口形态如图 1所示。

    图  1  不同尺度的交叉路口形态

    Figure 1.  Different Shape of Road Junctions at Different Scales

    图 1中,相对于大比例尺数据,小比例尺数据仅保留了交叉口的主干路段,删除了辅助路段。因此,从数据化简的角度,复杂交叉口识别除了对交叉口进行空间位置的识别以外,还应该能够进一步区分交叉口区域的主干路段与辅助路段。根据这个思想,本文提出了一种基于路段类别的复杂交叉口识别方法。首先,通过点密度聚类的方法对交叉口区域进行初步定位;然后,利用路段的几何与属性特征构建特征空间,通过分类算法对交叉口区域的路段进行分类,从而完成对交叉口的识别;最后,通过实验验证本文所提出的方法。

    • 复杂交叉口是指大尺度道路网数据中的立交桥和环形交叉口,这些交叉口包含上下行交叉道路、匝道,以及其他辅助连接道路[5]。因此,复杂交叉口一般会有较多的道路结点,可以通过统计道路结点来对道路交叉口进行初步的定位。主要步骤如下。

      1)遍历所有的道路结点,以某个点为中心建立一定距离的缓冲区,为了与路网密集的区域区分,位于长路段的缓冲距大于短路段的缓冲距。

      2)若该缓冲区内有其他结点,则以这些结点为中心建立同样大小的缓冲区,并且将这些有交集的缓冲区域进行合并,直到不再有新的结点落入缓冲区为止,进入步骤3)。如果缓冲区内没有其他结点,则继续寻找新的结点。

      3)统计该区域内结点数量Dm,如果Dm大于阈值C,则该区域为交叉口区域,落入该区域的路段为待分类的路段集;反之,则不是交叉口。

      4)为了更完整地覆盖交叉口区域相关路段,需要计算区域的中心点。设某交叉口区域内的所有点构成点集P,计算P内任一点到其他所有点的距离之和Di,定义Di最小的点为点集的中心点,并以该点为圆心,以最大距离为半径建立缓冲区,构成交叉口区域,完成交叉口区域的初步定位。

      5)重复上述步骤,直到所有结点标记完毕。算法主要流程见图 2

      图  2  定位算法流程图

      Figure 2.  Flowchart of Location Algorithm

    • 落入交叉口区域内的路段分为主干路段和辅助路段两种,这是典型的两类分类问题。为了对这些路段进行分类,需要首先考察这些路段的特点,找出与路段类别归属相关的若干个特征,并针对每个特征制定一个数量化指标,从而将一个分类对象转化为可以用N维向量表达的形式。本文使用长度、面积、紧凑度、平行度、对称性和道路类型等6个指标对路段特征进行量化表达,具体描述如表 1所示。

      表 1  交叉口特征的量化表达

      Table 1.  Quantitative Expression of the Road Junction

      特征 量化描述 说明
      规模 长度 路段的长度
      面积 路段围成的面积(将路段首尾相连)
      形状 紧凑度 路段的弯曲程度
      平行度 路段的笔直程度
      对称性 对称度 相似形状的数量
      属性 道路类型 路段的道路类型属性

      其中,部分特征的量化方法如下。

      1)紧凑度与平行度。道路交叉口中的辅路,尤其是立交桥的匝道,多呈现弧形,而主干道路多呈现直线,因此路段形状是区分主干路段与辅助路段的一个重要指标。曲线的曲率是一个局部值,不能反映曲线的整体形状。为了从整体上量化路段形状特征,本文引入了紧凑度和平行度的概念。紧凑度是区域形状特征的一种测量度,反映了区域空间分布的紧凑程度:

      (1)

      式中,C表示紧凑度; AP分别表示多边形的面积和周长。圆的紧凑度为1,是最紧凑的平面形状,接近直线的面的紧凑度为0,是最不紧凑的形状。紧凑度越大,则属于辅助路段的可能性越大。此外,本文引入了平行度的概念来量化路段的笔直程度,其定义是多边形最小外包矩形与多边形周长的比值[11],平行度越高,说明形状越直,则属于主干路段的可能性越大。当路段为直线时,定义其平行度为1。平行度与紧凑度一起度量路段的形状特征。

      2)对称度。文献[8]根据道路网规划的具体规定,给出了18种典型交叉口的图形库,这些交叉口结构具有的共同特征之一就是或整体结构对称,或存在形状相似的弧段。其实交叉口的这种对称性不难理解,为了保证各个方向具有同等的通行能力,至少相对的两个方向会具有相互连接的匝道,而很少只有单独一个方向存在匝道。如图 1(a)所示,交叉口不同方向的匝道或辅路具有相似的形状,可以作为区分主干路段与辅助路段的重要特征,这种辅助路段的对称性可以用交叉口范围形状相似路段的数量进行量化,称之为对称度。图 1(a)中弧形匝道的对称度为3,表明有3条路段与其形状相同或类似。为了计算路段形状的相似性,利用了文献[12]提出的基于曲线树的曲线描述和比较方法,本文不再赘述。

      3)道路类别。道路类别属于标称型变量,其值为字符串,没有数量或排序意义,不能直接应用于分类计算,必须采取一定的转换方法。本文采用文献[13]中提出的处理方法,将标称型标量转换为高维空间的单位向量。如数据道路类型一共有m种,构建一个m维空间Rm,在该空间中建立由m个单位正交向量组成的坐标系,将这m种取值分别对应这m个单位向量即可。

    • 由于支持向量机(support vector machine, SVM)在解决小样本、非线性及高维模式识别中具有独特的优势,本文采用SVM方法解决交叉口路段的分类问题。利用SVM进行分类的基本思想是在原空间寻找两类样本的最优分解超平面,如果样本是线性不可分的,则通过非线性映射将样本映射到高维空间。设样本集S(xi, yi)由N个包含m种特征的样本构成,其中,i=1, …, NxRmy∈{1,-1},C为惩罚系数,ε为惩罚参数,问题可由式(2)描述[13]

      (2)

      式中,‖w‖为法向量w的范数,与几何间隔成反比。目前该模型的求解基本思想是通过引入Lagrange函数,转换为对偶问题的求解,得到的最优分类函数为[13]

      (3)

      式中,sgn为符号函数;a*b*为确定最优分类超平面的参数;K(xi, x)为核函数。

      利用SVM进行交叉口路段分类时,首先需要利用已知正确分类的样本对SVM进行训练,可以通过人工采集的方法获取实验数据的样本库,包括正例样本和负例样本。然后指定SVM的核函数,本文选用径向基函数(RBF)进行转化,该核函数适用于特征向量之间呈现非线性关系的问题。随后利用二次规划的方法求解目标函数式(3)的最优解,得到最优Lagrange乘子a*,再利用样本库的一个支持向量x,代入(3),得到偏差值b*,此时训练阶段结束。在进行判断时,输入待分类的样本x*,然后利用训练好的Lagrange乘子a*b*,代入式(3),求解判别函数f(x),根据f(x)的值进行分类。值为1,则为正例(即主干路段);反之,则为负例(即辅助路段)。

    • SVM训练与测试数据选取北京市部分城区的开放街道地图(OpenStreetMap)数据,可以在其官网上免费下载。本文实验采集了100个交叉口共1 630条路段,其中主干道路路段642条,辅助道路路段988条。部分样本集如表 2所示。

      表 2  部分样本数据示例

      Table 2.  Examples of Sample Data

      样本ID 特征空间 类别
      1 {85, 90, 0.04, 0.87, 2} 1
      2 {95, 238, 0.64, 0.14, 5} -1
      3 {40, 0, 0, 1, 3} 1
      1 630 {32, 0, 0, 1, 2} -1

      表 2中,特征空间依次为长度、面积、紧凑度、平行度、对称度和道路属性。类别1表示主干路段,类别-1表示辅助路段。

      本文SVM的训练与测试基于Matlab 2009a中的SVM工具箱进行。为了防止出现过拟合的情况,采用交叉验证的方式进行。将1 630个样本随机分成10组,每组163个样本,其中9组用于训练,1组用于测试,一共进行10次训练和测试,实验结果如图 3所示。

      图  3  实验结果

      Figure 3.  Experiment Results

      实验的平均正确率为89.23%,错误率为10.77%,表明交叉口路段分类效果较好。但是正确率包含了主干路段的识别和正辅助路段的识别两种情况,还不能够有效说明各自的识别效果。为此,计算了实验的召回率和负召回率。召回率是样本中的主干路段正确识别的比率,实验的平均召回率为88%,表明有88%的主干路段被正确识别,12%的样本错误地将主干路段识别为辅助路段。负召回率是指辅助路段正确识别的比率,实验平均负召回率为90.3%,表明有90.3%的辅助路段被正确识别,有9.7%辅助路段被识别为主干路段。

    • 为了检测上述分类器在实际应用中的表现,将上述模型训练结果应用到未知分类的OpenStreetMap数据中,并与文献[8]中的方法进行对比。数据为北京市城区部分(异于样本集中的数据),设置缓冲距为30 m,上述样本数据中,交叉口区域内的结点平均数量为32,本文实验中设阈值C=40。部分运行效果如图 4所示。

      图  4  算法应用效果

      Figure 4.  Application Result of the Algorithm

      该区域一共有15个复杂交叉口,其中包含主干路段116个,辅助路段175个。将上述SVM训练结果应用到这些交叉口的路段中,识别结果如图 5所示。

      图  5  算法应用分类结果

      Figure 5.  Classification Results of the Algorithm

      上述实验的召回率和负召回率分别为87.07%和86.86%,这与SVM训练测试结果相符,表明该算法在实际应用中也具有较好的分类能力。其中,识别错误的主要原因是在某些交叉口中,主干道路呈现弧形,与辅助道路形状极为相似,或辅助道路与主干道路平行,导致算法无法准确判断其所属类别,需进一步判断,如图 6所示。

      图  6  错误识别的辅助路段

      Figure 6.  Wrong Recognized Auxiliary Road

      将上述数据利用文献[8]的方法进行识别,利用其提供的18种典型交叉口模板库进行实验,能够识别四叉型交叉口116个,r型交叉口92个,T型交叉口151个,Y型交叉口39个。但是由于该数据的一些道路为多线路,出现在多线路上的典型交叉口没有能够被成功识别, 如图 7所示。在添加了多线路四叉型交叉口模板后,能够识别这种类型的交叉口16个,但是复杂的交叉口均不能够有效识别。

      图  7  多线路上的典型交叉口

      Figure 7.  Typical Road Junctions on the Multi-line Road

    • 由于算法的适用范围不同,导致了两种算法的识别结果差别较大,本文算法对大型的复杂交叉口识别效果较好,但是无法识别基本的典型交叉口,而文献[8]的方法对典型交叉口识别效果较好,由于复杂交叉口处于多线路上,其结构库中不存在这样的结构,因此识别效果较差。两种方法的比较如表 3所示。

      表 3  两种方法对比

      Table 3.  Comparison of Two Methods

      特征 本文方法 文献[8]方法
      适用范围 复杂交叉口 典型交叉口
      识别原理 先定位,再分类 结构描述与比较
      优点 能够定位和区分
      路段类型
      能够保证识别
      结果的正确性
      缺点 无法定位简单交叉口 模板库以外的交叉口
      结构识别效果差

      在实际应用中,可以将两种方法结合进行,利用本文方法识别复杂的交叉口,而利用文献[8]的方法识别其他的交叉口。

    • 随着路径规划、精细化导航的需要,对地理信息数据的细节层次要求也越来越高。道路交叉口作为重要的道路设施,在路径导航、可达性分析中占有重要地位,研究道路交叉口的识别与化简具有重要的理论意义和实用价值。本文提出了一种基于SVM分类的复杂交叉口识别方法,根据交叉口路段的几何与属性特征区分出主干路段和辅助路段,进而删除辅助路段、保留主干路段,完成交叉口的识别与化简。与基于数学描述的方法相比,本文方法不仅能够较好地定位复杂交叉口,还能够进一步识别交叉口路段的属性归类,为下一步的交叉口化简提供有效信息。实验结果表明,该方法能够较好地识别交叉口路段,但是部分交叉口路段根据上述特征识别效果较差,需要进一步结合拓扑关系等其他特征进行识别,这也是下一步的研究重点。此外,本文方法仅适用于具有复杂结构的交叉口,对于简单结构的交叉口,难以通过点聚类的方法进行定位。在实际操作中,可以将本文的方法与基于数学描述的方法相结合,两种方法互相补充,更好地完成交叉口的识别。

参考文献 (13)

目录

    /

    返回文章
    返回