车载GPS导航系统中GPS定位与道路

车载GPS导航系统中GPS定位与道路
匹配方法研究

王密　郭丙轩　雷霆　李德仁

摘　要　对车载GPS导航系统中
GPS定位与道路的匹配方法进行了深入的研究，利用已有的道路网数据，建立了道路网络拓破斯 系，在此基础上提出了基于网络拓扑关系和电子罗盘方位信息的快速道路匹配算法。通过车载试验证明，该算法能够实现GPS定位与道路实时、可靠、高精度的匹配。
关键词　汽车导航；GPS定位；网络拓扑关系；匹配
分类号　P228.42　文献标识码　A
文章编号：1000-050X(2000)03-0248-251

Research on GPS Positioning Matching with Road in
Mobile Navigating System

WANG Mi　GUO Bingxuan　LEI Ting
(National Laboratory for Information Engineering in Surveying，Mapping and Remotte Sensing，
WTUSM，129 Luoyu Road,Wuhan,China,430079)
LI Deren
LI Deren
(Presidential Secretariat，WTUSM，129 Luoyu Road，Wuhan,China,430079)

Abstract　At present,the positioning precision of single GPS can only reach 100 meters.As the limited cost,it is impossible to process the signal of GPS by real-time difference to obtain high positioning precision.Therefore,in car navigating
system,single GPS receiver is generally used to get the position of car in real--time.Because of the effect of American SA technology,the positioning precision of single GPS has only 100 meters.In this case,if we can not adopt suitable method to process
the positioning information in real-time,we can not get better result in car navvigating system.For example,when the car is running along the bridge,because of positioning error the car maybe positioned in the river. As the car always runs on the road
in normal situation and the database of road net has been established in advancee before navigating.So we can use above condi-tions as restricted conditions. Before starting to navigate we can build topology based on thedatabase of road net and get the
initial position of the car on the road.At the same time,because the car is on tthe road,the error in vertical road direction is eliminated automatically.As the error of along-road-direction is concerned,it is not important for navigating.On the other
hand,it maybe be eliminated according to the apparent mark along the road (e.g.ccross_road,megastructure nearby road) by hand.When navigating we can correct the signal of GPS according to the current road that the car is running.It is critical to
process the signal of GPS when the car reaches cross_road.Under this condition,wwe can quickly find several roads that the car will run according to road topology. As the positioning error is 100 meters,we can not decide immediately where the car will
run.Therefore,due to positioning error the car maybe jump from one road to anothher road.Here we can add another restricted condition by using the data of compass installed on the car.As compass can record the driving direction of the car,when the car
come to cross-road nearly we can analyze the acquired data from compass in real--time to decide where the car will go.At the same time,we can calculate every road direction that the car will choose.By road direction matching with the result direction of
analyzed compass data,we can obtain which road the car will go.
Key words　mobile navigation;GPS positioning;network topology;matching

　　目前，在车载GPS导航系统中，由于成本的限制，不可能对接收的GPS卫星信号进行实时时差分来实现高精度的定位，因此，一般都采用单个GPS接收机来实时测量汽车的位置。由于美国SA技术的影响，单机定位的精度只能达到100m。如果不采用适当的方法对定位信息进行实时处理以提
定位精度，就不可能取得好的导航效果。例如，当汽车通过桥梁时，很可能会把汽车定位到到水中。但是由于车辆正常行驶过程中不会脱离道路网，并且导航城市的道路网数据库是预先建立好的，因此，可以根据GPS的定位结果，利用道路网数据库，采用适当的算法，进行实时处理，把汽
的位置“强制”性“拉”回到汽车行驶的道路上来，这样可以消除定位信号与汽车所在道路路垂直方向的误差分量。对沿着道路方向的误差分量，一方面从导航要求的精度来说影响并不大，另一方面可以把道路上比较精确的标志点（如道路交叉口、路边的加油站、大型建筑物等）作为控制
，在导航之前人工加以修正。由于车载GPS导航系统要求对数据进行实时处理，因此数据处览 的速度又是 个重要的因素。基于这些限制条件，在研制车载GPS导航系统过程中，笔者通过对不同数据结构和算法的比较并加以改进，在基于道路拓扑关系的基础上，采取利用电子罗盘所提供的较
精确的汽车行驶方向信息，对数据进行实时处理，在导航过程中取得了很好的效果。

1　GPS定位信号与道路匹配


　　在车载GPS导航系统中，通常以现有的城市地图作为背景，然后把汽车的定位信息实时舷允 在背景图上。导航过程中 由于汽车始终在道路上 驶，因此现有的GIS数据库中的道路网数据可以提供先验的道路信息，而用其他信息作为背景显示。在车载导航过程中，要求实时地把汽车定位
在背景图上，而对于一个庞大的城市道路网数据来说，不采用合理的数据结构来组织数据，，不可能满足导航的实时要求。下面介绍两种在导航过程中效果较好的数据结构和与之相适应的算法
1.1　基于分带索引和二分法模糊查找的道路匹配方法
　　如图1所示，该图为分带索引图。所谓分带索引，就是对整个城市的道路网范围，沿着XX方向(或Y方向)按照一定的间隔进行分带，带宽可以根据实际需要而定(例如，可取100m或200m)；然后将每带的起始位置从小到大或从大到小进行存储，同时将每条道路赋予一个惟一的道路标识号(ID
号)，将道路边界矩形(道路的最大最小坐标范围)落在带内道路的ID号与该带的起始坐标对佑 存储，其存储结构如表1所示。



图1　分带索引图
Fig.1　Diagram of Divided Zone Index

表1　分带索引表
Tab.1　Table of Divided Zone Index


带　号 坐标范围/m 道路ID号
第1带 500～600 1，2，3,…
第2带 400～500 25，26，…
第3带 300～400 …
第4带 200～300 …
第5带 100～200 …
第6带 0～100 …

　　基于这种存储结构的道路匹配算法(算法1)如下：
　　1) 将GPS接收汽车的定位信息规划到地图坐标系中来。由于GPS接收机接收的位置信息适且源 地坐标(经、纬度)表示的，而地图坐标是通过高斯投影形成的高斯坐标，因此，需要通过坐标正算将定位信息规划到地图坐标系中。
　　2)
根据规划到地图坐标系中GPS的Y坐标信息(图1是按Y方向分带的)，在表1中用二分法模糊查怂 在的带号。二分法查找的 数具
有以2的指数次方递减的优越性，因此，对于庞大的道路网来说，其查找速度仍然很快，可乙月 足定位的实时性要求。
　　3) 根据步骤2)查找带号，从表1可以查出在该带内的道路ID号，定义为集合A。
　　4) 在集合A中判断汽车的位置信息(X，Y)落在哪些道路的边界矩形内，并记录其ID号，，定义为集合B
　　5) 对于集合B内的道路，计算(X，Y)到落在边界矩形内的道路的最短垂直距离，将(X，，Y)规划到距离最短的道路上去
　　这种算法可以保证定位的实时性，能够消除垂直道路方向的误差分量。对于沿着道路方方向的误差分量可以在导航之前，通过道路附近明显的标志点予以校正。但是，当道路网比较密集或汽车行驶到道路交叉口时，由于只是以距离最小作为判断因子，因此，其可靠性不能得到保证，图
会出现汽车在两条道路间跳动的现象。
1.2　基于网络拓扑结构和电子罗盘方位信息的道路匹配方法
　　上面已经介绍了一种比较简单的GPS信号与道路的匹配方法，虽然可以达到实时定位的乙 求，但可靠性并不高。为了提高其可靠性，加入了道路网的拓 关系和罗盘方向两个判断因子，经过实验证明能够取得良好 效果。
1.2.1　网络拓扑关系的建立
　　在GIS中，为了真实地反映地理实体，记录的数据不仅要包含实体的位置、形状、大小汉 属性，还必须反映实体之间的相互关系，即拓扑关系，它具有在图形连续状态下变形但其性质不变的特性。另外，通过拓扑关系，可以将道路的全局搜索变为局部搜索，可以大幅度地提高数据的搜
索速度，为数据的实时处理提供了良好的数据结构。在车载导航过程中，由于只考虑地图中中的道路网信息，因此，只建立了道路网中的结点与弧段的关联关系
　　如图2所示的一个道路网，其中的1、2…表示道路网每条道路端点(起点和终点)的编号＃籄、B…表示道路的ID号。对图2建立拓扑关系的步骤为：
　　1) 读出第一条道路，对道路的两个端点从1开始进行顺序编号，建立结点链接表，如表表2所示，对单向行驶的道路只在该表中加一条记录，对于双向行驶的道路，还要将该道路的反向加入该表中(图2中所示的都是双线路)


图2　道路网示意图
Fig.2　Schematic Diagram for Road Network
Fig.2　Schematic Diagram for Road Network

　　2) 依次读取剩下的道路，判断该道路的端点是否已经编号，如果已经编号，取原来的浇 点号，否则，对其结点进行新的编号，并将其加入到结点链接表中。
　　3) 对结点链接表的道路起点字段进行排序，排序后的结点链接表如表3所示。
　　4) 将道路起点编号相同的结点进行合并，即可得到结点-弧段拓扑关系，如表4所示。

表2　结点链接表
Tab.2　Table of Node Connection


道路
起点 道路
终点 道路
ID号 道路
起点 道路
终点 道路
ID号
1 2 A 5 3 D
2 1 A 2 5 E
2 3 B 5 2 E
3 2 B 5 6 F
3 4 C 6 5 F
4 3 C 5 7 G
4 3 C 5 7 G
3 5 D 7 5 G

表3　排序后的结点链接表
Tab.3　Table of Node Connection


道路
起点 道路
终点 道路
ID号 道路
起点 道路
终点 道路
ID号
1 2 A 4 3 C
2 1 A 5 3 D
2 3 B 5 2 E
2 5 E 5 6 F
3 2 B 5 7 G
3 4 C 6 5 F
3 5 D 7 5 G

表4　结点-弧段拓扑关系
Tab.4　Topology of Node-Arc


道路结点号 与之连接的道路ID号
1 A
2 A、B、E
3 B、C、D
4 C
5 D、E、F、G
6 G
7 F

1.2.2　基于网络拓扑关系的道路匹配算法
　　首先要对道路网数据进行预处理，对每条道路的属性表添加了两个端点方向属性如表5怂? 。在计算机中， 条道路是按离散点来存储的，为了加 定位点的搜索速度，每条道路按5m的距离将其离散化存储(考虑到导航车辆的大小和实际的导航精度，最坏的情况是定位信号落在相邻两点
连线的垂直平分线上，这时强制纠正的误差为2.5m,用1∶1万的地图导航可以达到导航精度乙??，这样可以减少每次垂线的计算量，提高运算速度，保证很好的实时性。
　　基于网络拓扑关系的道路匹配算法(算法2)如下：
　　1) 将GPS接收的汽车定位信息规划到地图坐标系中来，与算法1相同。
　　2) 确定汽车初始位置道路ID号，这个过程可以用算法1来实现，并且可以自动地消除垂垂直道路方向的误差分量，对于GPS沿着道路方向的漂移误差，可以参考明显的标志(如道路交叉口、明显建筑物)人为加以改正
表5　道路属性表
Tab.5　Attribute Table of Road



道路ID号 道路名称 起点方向/° 终点方向/°
A 广八路 275 95
B 八一路 0 180
C … 0 180
D … 270 90
E … 270 160
F 中南路 340 170
G 中北路 270 90

　　3) 根据起始道路ID号，利用表2确定该道路的起始结点、终止结点的编号和该条道路的的空间坐标数据(预处理后的5m采样间隔离散的道路坐标数据)和属性数据
　　4) 计算GPS定位信息(X，Y)到该条道路上最近的点，汽车即定位在该点上。在计算时采采用的判断准则为：min(｜X-Xi｜+｜Y-Yi｜)，其中，(X，Y)为GPS定位信息；(Xi，Yi)为道路的坐标点位
　　5)
道路交叉口的特殊处理。如果步骤4)搜索到的点是道路的结点(起始或终止结点)，说明汽车车已经到达道路的交叉口，通过结点和弧段的拓扑关系(表4)，根据结点编号找到与该结点相连接的道路，此时根据定向罗盘提供的方位信息，找出道路方位角与罗盘方位最接近的道路，则该道路为
车将要行驶的道路，在该条道路上按照步骤4)搜索与GPS信号最近的定位点。如果步骤4)搜怂鞯 点不是道路的结点，重复步骤4)搜索定位点。
　　通过试验表明，利用该算法在导航中避免了算法1在道路交叉口和道路密集区导航可靠行 差的缺点，同时利用道路网拓扑关系的数据结构保证了实时性和准确性，取得了很好的导航 果。
2　试验结果与结论

　　在GPS车载导航系统中，GPS信号与道路匹配是其中的核心技术，而评价匹配结果好坏的的标志取决于所采用算法的实时性、可靠性及匹配精度的高低。经过数次导航的试验，基于网络拓扑结构和道路方向的道路匹配方法在导航过程中的确可以取得很好的效果。试验结果如图3(a)、图3(b
所示。
　　从试验结果可以看出，算法1和算法2对于汽车在路中间行驶时，定位结果基本上没有势
服了算法1的局限性，实现了GPS与道路实时的高精度、高可靠性的匹配。




图3　基于算法1、2的定位结果
Fig.3　The Positioning Result Based on Algorithms 1 and 2

国家自然科学基金重点资助项目，编号49631050。
王密，男，25岁，博士生。现主要从事车载系统和影像数据库系统的研究。WANG Mi,male,225,doctoral candidate.His major research orientations are mobile system and image database system.
E-mail:wangmi@rcgis.wtusm.edu.cn
作者单位：王密（武汉测绘科技大学测绘遥感信息工程国家重点实验室，武汉市珞喻路129汉牛?30079）
　　　　　郭丙轩（武汉测绘科技大学测绘遥感信息工程国家重点实槭遥?浜菏戌笥髀?229号，430079）
　　　　　雷霆（武汉测绘科技大学测绘遥感信息工程国家重点实验室，武汉市珞喻路129汉牛?30079）
　　　　　李德仁（武汉测绘科技大学校长办公室，武汉市珞喻路129号，430079）

参　考　文　献

［1］徐爱功.智能交通系统的建立及其与GPS、GIS相关关键技术研究:［学位论文］.武汉: 武汉测绘科技大学,1998
［2］边馥苓，朱国宾，余　洁，等.地理信息系统原理和方法.北京:测绘出版社，1996
［3］刘基余，李征航，王跃虎，等.全球定位系统原理及其应用.北京:测绘出版社，1993
［4］陈小明.高精度GPS动态定位的理论与实践:［学位论文］.武汉:武汉测绘科技大学，19997

收稿日期：1999-11-23


国家自然科学基金重点资助项目，编号49631050。
王密，男，25岁，博士生。现主要从事车载系统和影像数据库系统的研究。WANG Mi,male,2
E-mail:wangmi@rcgis.wtusm.edu.cn
作者单位：王密（武汉测绘科技大学测绘遥感信息工程国家重点实验室，武汉市珞喻路129
　　　　　郭丙轩（武汉测绘科技大学测绘遥感信息工程国家重点实验室，武汉市珞喻路12
　　　　　雷霆（武汉测绘科技大学测绘遥感信息工程国家重点实验室，武汉市珞喻路129
　　　　　李德仁（武汉测绘科技大学校长办公室，武汉市珞喻路129号，430079）

参　考　文　献

［1］徐爱功.智能交通系统的建立及其与GPS、GIS相关关键技术研究:［学位论文］.武汉:魏牛?30079）
［2］边馥苓，朱国宾，余　洁，等.地理信息系统原理和方法.北京:测绘出版社，1996
［3］刘基余，李征航，王净ⅲ??全球定位系统原理及其应用.北京:测绘出版社，1993
［4］陈小明.高精度GPS动态定位的理论与实践:［学位论文］.武汉:武汉测绘科技大学，19