基于轨迹聚类的路网构造-论文.pdf

《基于轨迹聚类的路网构造-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2015年2月吉林师范大学学报(自然科学版)No．1第1期JournalofJilinNormalUniversity(NaturalScienceEdition)Feb．2015基于轨迹聚类的路网构造朱云龙，刘微(1．中国科学院沈阳自动化研究所，辽宁沈阳110016；2．吉林师范大学信息技术学院，吉林四平136000)摘要：随着定位设备的普及以及大规模移动轨迹数据的快速涌现，使得基于移动轨迹的数据挖掘和知识发现研究变得越来越热，其中一个有价值的研究方向是从GPS轨迹中抽取路网结构．然而如何有效地从轨迹数据中探测交叉口并进而构造路网却是一个难以解决的问

2、题，针对此问题提出了一个基于轨迹点聚类的交叉El探测算法，以及在此基础上的路网快速构造方法．实验结果表明，算法能够有效地确定交叉口的位置及数量，且利用探测到的交叉口能够实现路网结构的快速构造．关键词：数据挖掘；聚类算法；GPS轨迹；路网构造中图分类号：TP391文献标识码：A文章编号：1674—3873．(2015)01-0011-070引言传统上用于构造路网的方法多为实地勘测的方式，近年来随着数字图像处理技术的发展以及大范围遥感图像(航空照片或卫星图片)的便宜获取，使得数字地图的自动化／半自动化绘制方法越来越成为地图制作的主要手段之一ll．然而该方法

3、对原始图片的质量要求较高，对低等级道路提取的效果较差，其带来的后果是在自动化提取道路后仍需大量的人工校正．并且由于受季节、气候、大气污染、获取成本等条件的影响，使得高精度遥感图像的获取并不特别容易．另外一种比人工勘测进步的方法是使用测绘车／街景车漫游道路记录GPS轨迹，拍摄街景、路标等．这种方法不仅能使用测量数据构造路网，而且通过分析街景图片能获取路宽、车道、限速等丰富的信息．这种方法能构造信息丰富的高精度路网，然而却需要很多车辆装配大量昂贵设备，而且费时费力．这就迫切需要一种廉价快速的地图生产方法．目前，随着普通GPS设备的普及，大量的GPS定位数据

4、可以从装配有GPS设备的车辆以及智能手机中获取．这些GPS数据在正常条件下拥有6～10m的精度』，蕴含着丰富的道路信息，如路宽、路长、交叉口、弯道、限速等，这就使得从GPS定位数据中导出路网地图成为可能．从GPS轨迹数据中自动获取路网地图，很多学者都已开始了相关研究，并做出了不少成果．然而这些方法大多只考虑道路的连接性或拓扑性，却忽略了路网中的一个重要组成部分——交叉口．交叉口不但体现了各道路问的连接性，而且还反映了路网中的复杂变化情况，比如道路问的连通关系及转向等．如若能获知交叉口的位置和结构，那么通过判断交叉口之间的是否有轨迹经过就能定义交叉口之间

5、的连接性，进而便能定义出拓扑性良好的路网结构．文献[14]是首次通过先探测交叉口再构造路网的算法，它使用机器学习算法训练的分类器来识别道路交叉口．然而，由于该算法需要使用高精地图做基准，需要正负样本来训练分类器，使得算法的应用具有一定的局限性．鉴于此，本文提出了一种基于轨迹点聚类的交叉口探测算法来解决上述问题．其思想为：首先从轨迹中找到车辆转弯点，基于大部分转弯点都分布在交叉口附近的事实，利用聚类算法将转化点划分到各个类簇中，每个类簇就对应一个交叉口．而后，基于探测到的交叉口，检测交叉口之间的车流量，当大于一定阈值时就可以认为有道路存在，连接两个交叉口

6、并以B样条拟合道路形状后即形成路段．最后，通过检测相邻路段问的轨迹方向确定道路转向，即完成了路网构造．收稿日期：2014．11．23基金项目：国家自然科学基金项目(61174164，51205389，61203161)第一作者简介：朱云龙(1967一)，男，江苏省南通市人，现为中国科学院沈阳自动化研究所研究员，博士，博士生导师．研究方向：企业信息决策与管理系统及生物优化方法．·11·(1)首先，由于对数据的概率分布没有任何先验知识，不知道目标区域有多少个交叉口，这就要求所选择的聚类算法能自动确定聚类的个数．(2)其次，由于主干道上轨迹量要与支线道路上的

7、轨迹量相差很大，导致了转弯点的密度分布极不均匀(如图3)，这就要求所选算法既能够识别高密度的交叉口，也能识别低密度值的交叉口．(3)再次，有些转弯点会发生在非交叉口处，这些点对于交叉口识别问题而言可视为噪声点，这就要求算法能够过滤噪声点．(4)最后，由于轨迹数据的海量性，使得算法必须能够快速处理大规模数据．基于以上考虑，可使用基于相对网格密度的聚类方法解决这些问题．对于第一点，可使用基于密度的聚类思想自动确定聚类的数量；第二点则可以使用相对密度的概念来消除高低密度区域之间的差别；对于第三点，可仍使用绝对密度阈值过滤噪声点；第四点可使用网格聚类思想来加快

8、处理速度．交叉口探测过程即是确定交叉口数量和位置的过程．本文首先使用基于相对网格密度的聚类算法