留言板

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

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

一种基于平行系数的双线主干道识别方法

张浩 武芳 巩现勇 许俊奎 张俊涛

张浩, 武芳, 巩现勇, 许俊奎, 张俊涛. 一种基于平行系数的双线主干道识别方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(8): 1123-1130. doi: 10.13203/j.whugis20150122
引用本文: 张浩, 武芳, 巩现勇, 许俊奎, 张俊涛. 一种基于平行系数的双线主干道识别方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(8): 1123-1130. doi: 10.13203/j.whugis20150122
ZHANG Hao, WU Fang, GONG Xianyong, XU Junkui, ZHANG Juntao. A Parallel Factor-Based Method of Arterial Two-Lane Roads Recognition[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1123-1130. doi: 10.13203/j.whugis20150122
Citation: ZHANG Hao, WU Fang, GONG Xianyong, XU Junkui, ZHANG Juntao. A Parallel Factor-Based Method of Arterial Two-Lane Roads Recognition[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1123-1130. doi: 10.13203/j.whugis20150122

一种基于平行系数的双线主干道识别方法

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

国家自然科学基金 41471386

国家自然科学基金 41101362

国家自然科学基金 41301524

信息工程大学地理空间信息学院学位论文创新与创优基金 XS201509

详细信息
    作者简介:

    张浩, 硕士, 主要从事制图综合与空间数据更新研究。zhanghaogis@163.com

    通讯作者: 武芳, 博士, 教授, 博士生导师。wufang_630@126.com
  • 中图分类号: P208;P238.7

A Parallel Factor-Based Method of Arterial Two-Lane Roads Recognition

Funds: 

The National Natural Science Foundation of China 41471386

The National Natural Science Foundation of China 41101362

The National Natural Science Foundation of China 41301524

Foundation of Thesis Innovation and Superior, Institute of Geographical Spatial Information, Information Engineering University XS201509

More Information
    Author Bio:

    ZHANG Hao, master, specializes in cartographic generalization and spatial database updating. E-mail: zhanghaogis@163.com

    Corresponding author: WU Fang, PhD, professor, PhD supervisor. E-mail: wufang_630@126.com
图(11) / 表(4)
计量
  • 文章访问数:  845
  • HTML全文浏览量:  47
  • PDF下载量:  407
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-06-02
  • 刊出日期:  2017-08-05

一种基于平行系数的双线主干道识别方法

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

    国家自然科学基金 41471386

    国家自然科学基金 41101362

    国家自然科学基金 41301524

    信息工程大学地理空间信息学院学位论文创新与创优基金 XS201509

    作者简介:

    张浩, 硕士, 主要从事制图综合与空间数据更新研究。zhanghaogis@163.com

    通讯作者: 武芳, 博士, 教授, 博士生导师。wufang_630@126.com
  • 中图分类号: P208;P238.7

摘要: 城市主干道路的识别和提取是路网综合的关键步骤,而双线道路则是大比例尺地图数据中道路综合的难点。针对城市双线主干道识别问题,基于Gestalt视觉准则构建候选双线主干道线对的约束条件,提出了一种基于平行系数的双线主干道识别方法。首先对道路网数据进行拓扑处理,然后借助道路匹配思想,结合Hausdorff(HD)距离匹配方法识别出可能构成双线主干道的候选线对。再对候选线对进行平行系数计算,当平行系数满足阈值条件时,就判定该线对是构成双线主干道的弧段。最后根据构成双线主干道路段间的空间关系,将已识别的弧段连接成整条道路。实验证明,选取典型样本方法正确设置阈值后,该方法能有效地提取道路网中的双线主干道。

English Abstract

张浩, 武芳, 巩现勇, 许俊奎, 张俊涛. 一种基于平行系数的双线主干道识别方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(8): 1123-1130. doi: 10.13203/j.whugis20150122
引用本文: 张浩, 武芳, 巩现勇, 许俊奎, 张俊涛. 一种基于平行系数的双线主干道识别方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(8): 1123-1130. doi: 10.13203/j.whugis20150122
ZHANG Hao, WU Fang, GONG Xianyong, XU Junkui, ZHANG Juntao. A Parallel Factor-Based Method of Arterial Two-Lane Roads Recognition[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1123-1130. doi: 10.13203/j.whugis20150122
Citation: ZHANG Hao, WU Fang, GONG Xianyong, XU Junkui, ZHANG Juntao. A Parallel Factor-Based Method of Arterial Two-Lane Roads Recognition[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1123-1130. doi: 10.13203/j.whugis20150122
  • 在不断变化的城市建筑环境中,道路网结构持续变化时间最长,而能体现城市结构的道路一般是城市主干道[1]。在大比例尺道路数据中,城市主干道主要呈双线模式。道路网的模式识别和提取是面向地图自动综合的空间信息处理的关键技术之一[2],双线主干道模式识别对把握城市结构、多尺度道路网自动更新等具有重要的理论和实际意义。在道路数据属性信息缺乏的条件下,大部分道路都是通过道路的重要性进行等级划分的,包括道路的长度、连通性、介数中心度、临近中心度等[3-6],但这些参数大部分只适用于较小比例尺数据,且处理的道路数据都是以单线形式存储的。杨必胜等通过模式识别将道路等级划分扩展到高精度的大比例尺数据中[7],栾学晨则通过分析道路网眼几何形态指标,采用SVM(support vector machine)方法自动提取城市主干道[8],但是这些方法对道路数据质量要求比较高。

    在大比例尺城市道路数据中,城市主干道大部分由双线道路组合而成,这些双线道路几乎都是一组平行线的组合,其结构特征明显区别于其他线状道路。本文通过分析双线道路的几何特征,首先对城市的道路数据进行匹配分析,利用道路匹配结果找到构成双线道路的候选线对;通过计算候选线对的平行系数来判断平行程度;最后,对识别出的双线道路,根据道路方向一致、连续性等指标将主干道连接起来,实现大比例尺地图中城市主干道路的提取。

    • 道路数据中的双线道路是由多组保持一定距离且近似平行的线对相互连接构成的。如果两条线是构成双线道路的线对,那么这两条线在结构上会十分相似,包括角度、长度、距离等特征量[9]。双线主干道模式识别,其本质是构成双线主干道线对间的相似性判别。构成双线道路的弧段具有不相交(接)、方向相似、长度相似、距离相近等特征,而这些特征符合Gestalt视觉准则[10-12]。本文通过Gestalt视觉准则进行量化计算,主要考虑两弧段间的相似性、方向性、邻近性、同趋势性、连续性等[12]。其中,相似性包括了方向性,主要指弧段间的长度相似性、方向相似性;邻近性体现在两弧段始终保持一定距离关系。基于以上分析,本文构建了双线主干道识别的约束条件,具体包括长度、拓扑关系、方向一致系数、长度相似系数和距离关系等。下面主要对后3种约束条件进行描述。

      1) 方向一致性约束。

      本文用道路整体的方向来描述。如图 1(a)所示,α1α2分别为两条不同道路的首末端点连线相对于水平方向的夹角,若α1α2的差值接近0°或者180°,说明两条道路总体接近平行。设两条道路的首末结点连线对应向量分别为S1S2(图 1(b)),两向量夹角为θ,则:

      $$ \theta = \arccos \frac{{{\boldsymbol{S}_1}\cdot{\boldsymbol{S}_1}}}{{\left| {{\boldsymbol{S}_1}} \right|\left| {{\boldsymbol{S}_2}} \right|}} $$ (1)

      图  1  道路整体方向差异

      Figure 1.  Difference of Roads Overall Direction

      为了统一量化两道路整体方向的差异,提出如式(2) 所示的方向一致系数:

      $$ {\rm{Si}}{{\rm{m}}_O} = 1 - \frac{{2\alpha }}{\pi } $$ (2)

      式中,如果θ>π/2,α=π-θ; 否则,α=θ

      由式(2) 可知,方向一致系数的值域是[0, 1]。当夹角θ接近0°或者180°时,方向一致系数接近1,表明两线要素成双线道路的可能性很大。

      2) 长度相似性约束。

      设两条线要素AB的长度分别为lAlB, 则长度相似系数为:

      $$ {\rm{Si}}{{\rm{m}}_{{l_{AB}}}} = 1 - \frac{{\left| {{l_A} - {l_B}} \right|}}{{\max \left\{ {{l_A},{l_B}} \right\}}} $$ (3)

      式中, SimlAB值域是[0, 1],长度相似系数越大,它们呈双线道路的可能性就越大。

      3) 距离关系约束。

      距离关系特征是最主要的特征约束条件,构成主干道的线对始终保持一定的距离。这是识别可能构成双线道路线对的主要突破点, 将在§2中详细描述。

    • 由于道路数据经过拓扑预处理成结点-弧段型,两组双线道路交叉路口是由两对短线围成的矩形(或者正方形),对于这些短线对,可以先通过长度阈值提取。双线主干道识别主要有两个关键点,一是找到可能构成双线道路的线对;二是判断线段是否满足平行条件。

    • 对同一道路要素集中的数据识别可能构成双线道路的候选线对,本质上是线对的匹配问题,只是参与匹配的参考对象与目标对象都来自于相同的数据源。本文采用较为经典的Hausdorff(HD)距离,对可能构成双线道路的线对进行识别。

      Hausdorff距离最初用来测定点集之间的距离,是一种定义于两个点集上的最大-最小(max-min)距离[13, 14]。假定有两个点集合A={a1, a2, …, an}和B={b1, b2, …, bn},则AB之间的Hausdorff距离定义为:

      $$ {d_H}\left( {A,B} \right) = \max\left( {{d_h}\left( {A,B} \right),{d_h}\left( {B,A} \right)} \right) $$ (4)

      式中,${{d_h}\left( {A,B} \right) = \mathop {\max}\limits_{a \in A} \mathop {\min}\limits_{b \in B} \left\| {a - b} \right\|}$;dh(A, B)表示点集合A中每一个点到点集合B最小距离中的最大值, ${{d_h}\left( {B,A} \right) = \mathop {\max}\limits_{b \in B} \mathop {\min}\limits_{a \in A} \left\| {a - b} \right\|}$。

      一般用距离来测量两个点集的匹配程度,所以曲线之间的距离可以通过HD距离来近似表达。在大比例尺道路网数据中,构成双线道路的线对始终是近似平行的,线对间始终保持一定的距离。通过这种距离关系,可以粗略识别出可能构成双线道路的线对。但由于数据在获取、处理、表达以及道路自身结构等方面的影响,使得构成双线道路的线对描述上存在差异。这些差异会影响线对的识别结果。线对间的距离是初选构成双线道路线对的主要指标。所以为了提高识别双线道路线对的准确率,需要分析影响两线间距离大小的因素。

      一般情况下,造成两线间距离突变的原因有以下几点:① 顶点分布差异,如图 2(a)所示,d3的取值偏大,使最终距离值的准确性难以保证。② 长度不一致,如图 2(b)所示,连接首点的d1明显偏大,在HD距离中顶点最小距离的取值就会偏大,使最终的距离值偏大。③ 形状特征差异,如图 2(c)所示,由于存在局部几何形状突变的情形,使d4取值偏大[15]

      图  2  HD距离度量示例图[15]

      Figure 2.  Example of Distance Measurement

      针对本文的双线主干道识别,由于双线道路形状差异很小,加上长度约束,所以在利用HD距离识别构成双线道路的线对时,主要解决的是线段顶点的分布不一致问题。本文通过利用几何学中的定比分点公式(式(5))计算新增点的坐标,以增加线上结点的数量,改善HD距离过大的情况。

      图 3所示,待增加点P在弧段AB之间,LAPLPBLAB表示线段APPBAB的长度,则点P的坐标根据定比分点公式表达为:

      图  3  定比分点公式图式

      Figure 3.  The Formula on Definite Proportion

      $$ \left\{ \begin{array}{l} x = \frac{{{x_1} + \gamma {x_2}}}{{1 + \gamma }}\\ y = \frac{{{y_1} + \gamma {y_2}}}{{1 + \gamma }} \end{array} \right. $$ (5)

      式中,$\gamma = \frac{{{L_{AP}}}}{{{L_{PB}}}}$;LAP=λdW(λ=1, 2, …,n),dW约为双线道路的宽度,可以通过实验数据量测得到,n为$\frac{{{L_{AB}}}}{{{d_W}}}$的商。

    • 综合上述多个约束条件识别出的线对依然不一定全部是双线主干道,还需进一步确定识别出的候选线对是否趋于平行。概率论中的方差用于度量随机变量与数学期望之间的偏离程度。类比方差思想,本文提出了一种衡量双线间距离波动程度的评价指标——平行系数。平行系数是指利用同一方法获取一组距离值的平均偏离程度。值越小,两线的平行程度越高,反之则越低。度量平行程度的基本思路如下:

      设线要素AB,点集A={a1, a2, …, an},点集B={b1, b2, …, bn},AB的平行系数:

      $$ {P_{AB}} = \frac{1}{m}\sum\limits_{i = 1}^m {\left| {{d_i} - {{\overline d }_A}} \right|} $$ (6)

      式中,${{d_i} = \mathop {\min}\limits_{a \in A,b \in B} \left\| {a - b} \right\|}$,是点集A中每个点到点集B的最小距离;${\overline d _A} = \frac{1}{m}\sum\limits_{i = 1}^m {{d_i}} $(i=1, 2, …, m),是点集A中每个点到点集B最小距离的平均值。

      平行系数PAB反映了点集A中每个点到点集B最小距离的波动情况。PAB小,说明A点集的最小距离波动小,所有距离彼此之间大小差距很小,这能够准确反映平行线的结构特征。为了证明平行系数的有效性,选取4种典型线对(图 4)进行平行系数计算。试验结果见表 1。可以看出,4种情况下的距离均值十分接近,但由图 5则看出,平行系数越小,越可能是平行线对。当PAB为0时,两条线可认为绝对平行。

      图  4  候选线对可能出现的情况

      Figure 4.  The Possible Cases About Candidate Pairs

      表 1  典型线对参数统计

      Table 1.  Typical Pairs Parameters Statistics

      统计项 线对1 线对2 线对3 线对4
      平均值 24.622 174 24.610 101 22.869 523 24.540 678
      最大值 31.435 780 33.030 755 25.027 312 26.298 508
      最小值 16.303 874 16.074 014 18.493 925 22.392 393
      平行系数 3.147 026 5.479 440 1.759 942 0.870 601

      图  5  典型线对平系数对比

      Figure 5.  Typical Pairs Parallel Factor Comparison

      由此可以看出,本文提出的平行系数主要有两个优点:① 资源再利用提高算法效率。di的计算是候选主干道识别算法的关键步骤之一,本文主要是通过HD距离寻找构成双线主干道的线对,在计算HD距离过程中,将点集间的最小距离保存到动态数组中,为后面平行系数计算服务,大大提高了算法的运行效率。② 准确衡量两线的平行程度。4种典型线对平行系数的计算试验已经证明。

    • 结合§2.1和§2.2的方法描述,双线主干道识别步骤(图 6)描述如下。

      图  6  双线主干道识别流程图

      1) 数据预处理。对数据进行拓扑处理,修正拓扑错误,连接或删除悬挂点。

      2) 从任意线段Li开始遍历,其中有4个约束条件:① Li长度约束;② 与Li不邻接、不相交的;③ 与Li方向一致;④ 与Li长度相似。

      3) 计算Li与其他线弧段Lj的HD距离Dij。如果Dij满足设定的阈值,表明LiLj有可能是构成平行道路的线段。

      4) 计算LiLj的平行系数Pij。如果Pij满足阈值,说明LiLj是构成平行道路的弧段。对LiLj分别做标记,表示LiLj是同一主干道的两条单线。

      5) 对因长度约束而过滤的弧段,按以上方法步骤识别。

    • 通过上述方法基本可以识别出大部分的双线主干道线对,但是对于丁字路口处的弧段却无法识别(如图 7中的弧段①~③),这样就破坏了双线主干道的完整性。对于以上问题,本文通过分析弧段间的空间关系,结合Gestalt理论中的同趋势性、连续性准则[12],利用迭代思想来解决。具体方法如下。

      图  7  双线道路丁字路口

      Figure 7.  Double T-Junction Roads

      1) 曲线间邻接关系分析。设以公共点为起点的两曲线夹角为Aij,通过式(1) 计算夹角Aij。分析曲线间的邻接关系。构成双线道路曲线间的邻接关系主要有3种类型,如图 8所示,分别为水平邻接、转向邻接和垂直邻接。根据夹角Aij的大小对3种曲线邻接关系判断作如下约定:水平邻接(165°≤ Aij),转向邻接(105°≤ Aij<165°),垂直邻接(75°≤Aij<105°)。

      图  8  曲线间的邻接关系

      Figure 8.  Adjacency Relation Between Curves

      路段长度更新原则为水平邻接优先,转向邻接次之,最后是垂直邻接。如果有多条曲线满足同一种邻接关系,角度大的优先。该原则基本符合城市主干道分布模式。

      2) 将已经识别的弧段作为种子曲线,该部分算法的关键步骤如下。

      (1) 遍历种子曲线,对任一种子曲线Si,查找邻接的曲线Sj。计算曲线夹角Aij,并判断邻接关系类型。

      (2) 路段长度更新。为了识别出丁字路口处的弧段,暂不考虑垂直邻接关系。(如图 7所示,路段ad和路段bc都满足垂直邻接关系,如果考虑垂直邻接关系,则路段ad和路段bc都分别连接成整体,这样就无法根据邻接关系识别出弧段①、②、③)。如果SiSj满足连接条件,将SiSj连接成新的路段并加入需要遍历的种子曲线;否则选取曲线Si的下一邻接曲线进行判断。

      (3) 待Si连接结束,继续遍历后续的种子曲线,直至结束。

      3) 将步聚2) 得到的迭代结果曲线再作为种子曲线,此时参与计算的曲线还包括未被识别的曲线。采用和步聚2) 相同的方法进行迭代计算,识别出丁字路口处的弧段并连接成整体。

      利用以上方法,不仅识别出了丁字路口处的弧段,还将破碎的单线弧段连接成了整条道路,保持了双线主干道的完整性。如图 7所示,路段a→③→bd→①、c→② 分别了构成整条道路。

    • 为检验上述识别方法的有效性,本文基于ArcEngine设计实现了该算法。为更好说明本文方法的合理性和普适性,使用1:1万的加利福尼亚、香港、太原部分城市道路数据进行试验。试验中双线主干道识别的参数范围有所不同,方向约束参数和长度相似系数范围为[0, 1]。HD距离参数范围是[ab],其中a是试验数据中双线主干道宽度最小值,b是可能构成双线主干道线对候选的最大值。平行系数理论范围是[0,c],其中c是构成双线主干道线对平行系数的最大值。

      表 2是各试验区域对应的试验参数阈值以及数据量信息,图 9所示的是利用本文方法的试验结果,其中深色部分是最终提取的双线主干道,浅色部分是通过多个约束条件过滤的单线路段。图 9上半部分是试验区域的整体试验结果,下半部分是对应的红色圆形区域的局部细节图示。

      表 2  试验参数阈值统计

      Table 2.  Parameters Threshold Statistics

      道路网区域 方向约束 长度约束 距离约束 平行系数 数据量
      加利福尼亚 0.9 0.85 40 2.7 833
      香港 0.9 0.85 43 4.1 585
      太原 0.85 0.8 45 5.3 2 483

      图  9  双线主干道识别结果

      Figure 9.  Arterial Two-Lane Roads Recognition Results

      将本文方法提取出的双线主干道与依据人工目视判别选取的双线主干道进行比较分析,得到图 10所示的3个区域主干道线对识别的统计情况。匹配结果的定量评价指标常用正确率和召回率表示[16],本文也利用这两个指标对3个不同区域的实验结果进行评价分析(表 3)。由表 3可知,本文方法对3个城市区域识别的双线主干道线对正确率分别达到了94.32%、91.59%、90.78%,召回率分别达到了92.66%、94.52%、88.23%。其中太原市召回率较低,主要是因为数据量较大,道路结构较复杂,错误识别出的小路段较多,但这可以利用路段自身长度约束解决。

      图  10  主干道线对识别结果统计图

      Figure 10.  Results of Arterial Roads Pairs Recognition

      表 3  双线主干道识别结果统计表

      Table 3.  Two-Lane Roads Recognition Results Statistics

      试验区域 正确识别 错误识别 未识别 识别结果/%
      正确率 召回率
      加利福尼亚 101 6 8 94.32 92.66
      香港 207 19 12 91.59 94.52
      太原 532 54 71 90.78 88.23

      阈值的大小直接影响双线主干道识别的结果,本文通过人工选取典型样本数据来确定试验区域的参数阈值。具体过程如下:

      1) 通过人工目视判别选取双线道路作为样本数据。为了保证选取的双线主干道样本数据具有代表性,要根据实验区域双线主干道的空间分布特点,结合其自身结构特征选取样本数据。如图 11所示,圆圈处表示选择样本对应的位置,图 11(a)对应的是加利福尼亚试验区域,样本容量为10,图 11(b)对应的是香港试验区域,样本容量为15,图 11(c)对应的是太原试验区域,样本容量为20。样本容量单位是构成双线主干道的线对对数。

      图  11  样本选取示意图

      Figure 11.  Sample Selection

      2) 根据选取的样本计算相关参数。

      3) 统计、分析参数,确定参数阈值。根据上文参数分析,结合参数对实验结果的影响可知:① 方向一致系数越大,长度相似系数越大,线对越可能是构成双线主干道的线对;② HD距离是用来候选双线主干道线对的,当线对的HD距离在某一阈值范围内时就加入候选线对集合;③ 平行系数越小,平行程度越高。因此,为了确定各参数阈值,要分别统计方向一致系数、长度相似系数的最小值,HD距离、平行系数的最大值(表 4)。为了避免漏掉对构成双线主干道的识别,约束参数的阈值并不绝对等于通过样本计算出来的参数阈值,而需要参照样本参数统计结果,微调参数阈值,结合适当的试验测试,最终确定表 2中的参数阈值。

      表 4  样本数据参数统计

      Table 4.  Sample Data Parameter Statistics

      统计区域 方向一致系数 长度相似系数 HD距离 平行系数
      图 11(a) 0.939 3 0.883 5 37.475 6 2.094 8
      图 11(b) 0.936 0 0.876 8 39.106 8 3.688 3
      图 11(c) 0.929 6 0.838 6 41.331 5 4.688 7
    • 大比例尺道路网数据结构复杂,对其进行空间结构描述一直是个难题。本文首先分析了构成双线主干道线对的结构特点,基于Gestalt视觉准则,构建了候选双线道路识别的约束条件。利用几何学中的定比分点公式对道路数据进行结点加密,减少了因HD距离突变带来的影响。通过人工选取典型样本数据判定参数阈值范围,然后将约束条件和HD距离匹配算法相结合,构建双线主干道线对的候选集,再利用平行系数进一步定量描述候选线对集中线对间的平行程度,进而较好地效识别出双线主干道线对。最后对无法识别的丁字路口处的弧段进行了进一步探讨,通过分析弧段间的邻接关系,识别出丁字路口处的弧段,并将所有识别的弧段连接成了整体,保持了双线主干道的整体性。需要进一步研究的问题包括:① 双线主干道识别算法中阈值的自动获取。② 提高构建双线道路线对候选集的准确度。③ 多样式双线道路交叉路口处弧段识别。

参考文献 (16)

目录

    /

    返回文章
    返回