§5.1 GPS车辆导航系统的总体设计
车辆导航系统，是为解决移动单元用户的移动导航要求而开发的，是为个人用户开发的一个导航系统。其基本功能是准确的定位和实时跟踪车辆的位置，并显示车辆周围的道路情况，考虑到导航的效果，还要有良好的显示界面，要具有基本的路径选择、道路指引等智能辅助功能，另外考虑到车辆和用户的安全问题，导航系统还应该具有一定的安全保卫和报警的功能。
GPS实验室开发的GPS车辆导航系统将GPS全球卫星定位技术与导航电子地图GIS技术相结合，利用GPS定位高精度、全天候、实时性好的特点，实时准确地跟踪车辆的位置。利用电子地图GIS技术，将车辆的定位信息显示在电子地图的背景上，从而使用户得到自己准确的位置，并获知自己附近的道路情况。系统结构如下图4.1.1所示:
导航软件主要由三个部分组成：串口数据解析模块、导航地图GIS平台和智能决策模块。如图5.1.2所示:
车辆导航软件的各模块功能如下：
串口数据解析模块：分析电脑串口读入的GPS接收机数据，从中解算出车辆位置、速度、方向等定位信息；
导航地图GIS平台：作为整个车辆导航系统的显示背景，显示车辆当前所处的位置和附近的道路情况，提供导航矢量地图和GIS数据库的各种操作。
智能决策模块：结合导航地图GIS平台，跟踪并动态校正车辆的位置，实现路径寻优、导航信息提示和车辆报警等功能。它是整个车辆导航系统中最重要的一个模块。智能决策模块功能具体如下图：
§5.2.1 定位和跟踪
定位和跟踪是车辆导航系统的基本功能，以GIS向量地图为背景，实时显示、记录运动情况，使用户能直接了解车辆的位置，以及周围的道路情况。在车辆位置的显示模式中，我们设定了跟踪模式和非跟踪模式。在跟踪模式中，电子地图始终以车辆所在位置为中心进行显示；在非跟踪模式中，用户可以自由地漫游和察看地图的任何位置。
§5.2.2 地图的操作
车辆导航系统以矢量电子地图为显示背景，矢量电子地图平台为导航系统提供了灵活、强大的地图操作功能，整个矢量电子地图可以灵活地放大、缩小和漫游，还可以选择某个特定的区域进行放大，使得用户可以迅速地了解某个特定区域的详细情况。另外，用户还可以使用测量功能，测量地图中两点或者所选取路线的长度，这也是车辆导航需要的一个辅助功能。
§5.2.3 查询功能
我们提供了方便的查询功能够让用户访问地图GIS数据库中的各种信息。打开查询面板，用户单击地图上的道路、区域和点标志，查询面板中就会显示出该目标的详细信息。另外，用户还可以直接访问GIS数据库，在数据库中查找道路、单位等信息，并可以在地图上进行定位。我们也提供了模糊查找的搜索方式，方便用户在不了解确切信息时依然可以查询相关的信息。
§5.2.4 路线指引与信息提示
通过概貌窗口和导航信息提示窗口，我们提供用户路线指引和信息提示的导航功能。在用户选取航程后，打开概貌窗口，该窗口会实时指示前方路况及转向，在交叉道口等位置提示前方道路名称等导航信息。利用这些导航信息，用户可以了解附近道路的情况，以及在交叉路口的转向，该功能还与报警功能相联系，在偏离指定道路时，概貌窗口中会出现报警信息，从而使用户不至于迷路或者误入歧途。导航信息提示窗口中，显示的是前方道路情况等导航信息，又可能的话，还可以作为交通状况、天气状况等信息的显示窗口，提供用户更好的导航服务。
§5.2.5 路径寻优
现在的城市道路越来越复杂，“路径寻优”，即根据给定的起点和终点，迅速找到从起点到终点的最优路径。路径寻优把用户从错综复杂的道路网络中解脱出来，成为导航系统一个非常重要的功能。我们这里所说的“优”，首先考虑的是路程的长短，这也是最实际最好衡量的“优化”指标。除了“路程最优”外，还应该考虑“时间最优”，但是，由于影响“时间最优”的因素很多，比如道路长短、道路宽窄、车流量大小等，而车流量的大小是一个实时变化的数据，在没有相应的车流量监控网络和无法有效获取车流数据的情况下，我们只能根据经验对道路的“时间因子”进行估计和近似，这样得到“时间较优”的道路
§5.2.6 轨迹记录和回放
记录行车轨迹，并能回放重现行车过程。如下图所示。
§5.2.7 报警和安全
安全保障是车辆导航系统的一个重要功能，一方面我们提供了误入歧途时声像提醒的报警功能，另一方面，在安装了和配备了手机插件后，我们还可以让程序在遇到车祸、劫持、被盗等危险情况时，自动拨打110以及其他用户设定的电话号码进行报警，有效地保障用户和车辆的安全。
§5.3 导航系统中的智能决策
车辆导航系统作为一个高新技术产品，综合了GPS、GIS和计算机技术，在基本的跟踪定位功能之外，应当发挥计算机强大的计算和信息处理能力，实现路径寻优等智能决策功能，辅助用户达到更好的导航效果，这也是多数导航系统必备的功能之一。本章主要讨论我们开发的两项智能决策功能。
§5.3.1 路径寻优
GPS（全球卫星定位系统）和GIS（地理信息系统）技术在车辆导航和监控领域有着广泛的应用。在车辆导航和监控系统软件中，一个基本的辅助决策功能即寻找两点间的最短路径。在复杂的城市道路网络中，如何快速准确地找到出发点和目标点之间的最短路径，取决于不同的路径寻优算法和矢量地图的数据结构。
最短路径问题（Pathfinding or Shortest Path Algorithms）是一种计算机图形搜索算法，即在出发点和目标点之间找出总代价最低的路径。路径寻优算法一方面要完成探索最低代价的路径，另一方面要做到尽可能快，尽可能少占用内存，即尽可能降低算法的时间复杂度和空间复杂度。
最短路径的寻优有很多不同的实现方法，包括Dijkastra（迪杰斯特拉）算法，BFS（最好优先）算法，A*算法等。其中A*算法是一种非常有效的路径寻优算法。
我们利用A*算法结合矢量地图的结构在车辆导航系统中实现了最短路径的寻优（如图5.3.1，图中较粗的路线即为选出的最短路径），而且寻优的速度很快，只要2-3秒。在完成基本的以长度为基准的路径寻优后，我们又把长度寻优的基本思想加以扩充，研究以时间为基准的路径寻优。在时间寻优中，因为道路长短、道路宽窄、车流量大小等多种因素都会影响“时间最优”的结果，其中，车流量的大小还是一个实时变化的数据，而且，各种因素的度量标准也不同。综合考虑各种因素以及算法的简便有效，我们根据道路宽度、车流量估计值和经验定义了道路的“时间因子”，当然这只是一种估计和近似。然后，在时间寻优中，我们定义道路“虚拟长度”等于“道路实际长度×时间因子”，再利用虚拟长度进行长度路径寻优。我们认为，这样得到的路线是“时间较优”的。这样利用时间因子，我们把不好衡量的时间指标转化为容易衡量的长度指标。“时间较优”的路径寻优结果和“路程最优”的路径寻优结果见图5.3.2 和图5.3.3。
§5.3.2车辆轨迹的动态校正
因为GPS信号和矢量地图制作过程中不可忽略的误差，给导航和定位带了一定的影响。这里主要讨论一下我们提出的“车辆轨迹的动态校正算法”。
一、 校正算法的意义
注意到GPS导航或监控系统的基本原理不难发现：作为位置传感器，GPS总会存在随机定位偏差，特别是大城市中高楼大厦引起的GPS信号多径传播误差，而作为定位基准参照系的矢量地图也不可能绝对准确。目前国内外车辆监控中心普遍存在的所谓“车在路外跑”的现象从实践中向我们提出了研究本课题的重要性。在导航或监控软件中，特别加进了我们在矢量地图结构基础上独创的智能型车辆运行轨迹实时校正功能模块。该模块同时修正了GPS定位偏差与交通矢量地图精度误差的影响，使移动单元位置在地图道路上的真实位置得以确认、准确显示和实现动态决策。
在GPS个人导航或GPS交通监控中心操作系统软件中加入车辆行驶轨迹的实时动态校正，这不仅是同类系统中我们的独创，而且在学术上提出一个有待不断深化的研究课题。所谓智能型车辆运行轨迹实时校正功能，就是对车辆行进的历史轨迹进行动态滤波，结合车辆进入交叉路口时的GPS方向信息对车辆轨迹进行智能化的动态平滑与预测。它在本质上是修正GPS定位偏差与交通矢量地图精度误差的综合影响，并通过某种自适应算法实现高度智能化的GPS先进车辆定位（AVL）。
特别值得一提的是本课题如下的潜在价值：使用带有智能型车辆运行轨迹实时校正功能的导航或监控软件允许所使用的交通矢量地图降低精度，因而大大降低交通矢量地图的制造成本。这对加速我国GPS导航与监控产业的发展具有极为重要的潜在价值。
二、算法分析
当车行驶在道路上时，存在三个状态信息，速度、方向和当前所在街道。不难理解三个事实:当车辆远离交叉路口时，它不可能从一条街“跳”到另一条街；连续两次从GPS信号得到的方向绝对差总小于某个小量，除非它在交叉路口转向；当车辆行驶在道路上时，偶尔较大偏离道路的信号应该忽略。概括来说，就是利用车辆轨迹的连续性和矢量电子地图的拓扑结构，将车辆轨迹和道路网格进行匹配，从而过滤GPS信号的定位误差，更形象一些，可以说是根据GPS信号将车辆“拉”到道路上来。因此，修正算法应该涉及车辆当前和以前的方向及街道的拓扑索引。
我们作出以下定义：
1） 定义阈值MaxError，当GPS信号提供的位置到最近弧的垂直距离小于MaxError时，认为车没有偏离道路，并且从这个最近的弧上选取一个最近的点作为修正后的位置。
2） 方向角范围为正北方向做顺时针旋转0度~360度。因为GPS信号存在的误差，必须对小于45度和大于315度的方向值做滤波处理。为了消除正北方向的边界偏差，必须考虑到前一次方向角LastDirection。
a)if 当前方向Direction < 45。 and LastDirection > 315。 Then
LastDirection = LastDirection –360;If Direction > 315 and LastDirection < 45 then LastDirection + 360;
b)LastDirection = ( ( SmoothCount - 1 ) * LastDirection + Direction ) div SmoothCount.
c) if LastDirection > 360 then LastDirection = LastDirection - 360;
if LastDirection < 0 then LastDirection = LastDirection +360;
其中，SmoothCount是经验值，通常取2或3。
3） 定义本次最临近(Road)和上次所在弧(LastRoad)的索引分别为RoadIndex和LastRoadIndex
三、 校正算法
整个校正算法的步骤可以描述如下：
Step1. 在阈值MaxError允许范围内，从LastRoad上寻找最近邻的点作为修正后的位置;计算出Direction和LastDirection间的绝对差Difference;
Step2. 如果Difference大于60度或找不到最近临点，转至Step 3;否则，进行Step1，然后跳转至Step3;
Step3. 寻找最近邻的弧。如果找着，用新的RoadIndex取代LastRoadIndex，并通过Step1调整位置;否则，LastRoadIndex保持不变，车辆位置不做调整。
Step4. 利用Direction和LastDirection，根据定义2>对LastDirection滤波。
我们对上述算法做了大量实验，特别是对即将通过交叉口时的车辆。当行驶车辆距离最近临交叉口的距离大于GPS位置偏差时，车辆的轨迹是一个平滑的曲线。但在交叉口处存在等待现象WAIT，即车辆光标在交叉口处静止一段时间后，突然跳至另一个路上。GPS误差是导致此类WAIT现象的直接原因，因为当GPS误差偏大时，MaxError也相应调大，而且只有GPS位置与交叉口的距离大于MaxError时，Step3 才可能进行，否则不断重复着Step1的操作而保持最近临交叉口位置不变。
四、 校正算法在矢量电子地图下的实现
在矢量地图的基础上我们实现了车辆轨迹的实时动态校正，图5.3.4是合肥市导航地图的一部分截图，图中代表车辆的位置，+ 代表接收到的GPS定位信号。
上图给出采用轨迹实时动态校正算法前后的车辆偏离道路情况对比。从图中我们看到，该算法确实有效地修正了GPS定位的误差。
参考文献
[1] 鲍远律，夏冰，鲍远慧，GPS车辆监控系统开发的关键技术，中国公路-交通信息产业，p42-44, 总第9期，N0.3, 2001.5
[2] 鲍远律，“走下神坛的GPS”，电脑报，第51期(总第51期)第一版，p.1-2，2001.12.24
[3] 鲍远律，GPS车辆监控系统的总体设计，《世界GPS接收机购买手册》，1998，中国GPS信息中心，航空航天工业部出版社，p167-183
[4] 段凌宇、鲍远律、张旺生，"GPS Vehicle Navigation System"，南京航空航天大学学报（英文版），1998，15（2），p.172-178
[5] 李德仁，数字地球与3S技术,地理信息系统论坛，2001, www.gischina.com
[6] 郭杰华、姚振旺、鲍远律、张旺生, "矢量地图的一种自动校正算法", 中国图像图形学报, 第4卷第5期，p.423-426,1999.5
[7] Sheng-Guo Wang and Yuanlu Bao, “New Intelligent Method to Generate Vector Maps for GPS Navigation, IFAC World Congress b'02, Paper number: 157, Barcelona http://ifac2002.dit.upm.es/ifac2002/
[8] Yuanlu Bao, Wang Guojiang, Ye Jiaming, "Overall Design of Xiamen City GPS Intelligent Vehicle Monitoring System", TPL01-2, Proceedings of 2002 International Conference on Control and Automation, Xiamen, China, p.887-891, June 16-19, 2002.
[9] Jiaming Ye, Yuanlu Bao, Aiping Liu, "Road Extraction from Color City Map", MAP06-2, Proceedings of 2002 International Conference on Control and Automation, Xiamen, China, p.260-264, June 16-19, 2002.
[10] Haitao Wang， Zhenwang Yao and Lingyu Duan，“Automatic Generation of Vector Map”，in Proceedings of 1997 China-Japan Joint Symposium on Advanced Energy and Transportation Engineering， pp. 392-397
[11] Yuanlu Bao， Wangsheng Zhang ，Ming Zhu ，etc. ，“USTC GPS Vehicle Monitoring System”，in Proceedings of 1997 China-Japan Joint Symposium on Advanced Energy and Transportation Engineering， pp. 339-347
[12] 张旺生、黄晓纲、鲍远律、史久根,“矢量电子地图的自动生成”，微电子学与计算机,1999.8，第16卷 第4期，p.30-32
[13] 陆慧凤、赵树芗，“矢量地图图形的多功能显示”，微电子学与计算机,
1994年第一期， p.31-34
[14] 莫凡，“一种新的基于矢量地图数据的地表纹理制作”，测绘学院学报，2002年3月，第19卷第一期
[15] 刘志清，“基于GIS技术的城市基本图数据库建设的几个问题”，北京测绘，1994年，第四期
[16] 赵霈生,杨崇俊，“Web-GIS的设计与实现”，中国图象图形学报，2000年第一期
[17] 李伯楠,沈志纲，“数字地球”体系下GIS-T技术的应用”， 交通标准化，2000年第一期
[18] 赫建忠,陈军，“数字地球”时代GIS的发展”，工程勘察，2001年第二期
[19] 洪锋,顾志康，“GIS在车辆导行系统中的应用交通与计算机”，2002年第一期
[20] 袁峰,周涛发,岳书仓，“我国GIS产业的现状、面临的挑战与发展对策探讨合”肥工业大学学报(社会科学版)2002年第二期
[21] 张书毕,刘作才，“基于GIS的GPS车辆监控系统设计与实现”，测绘通报，2002年第六期
[22] 王刚,吕海宝,颜树华,“GIS的发展方向——Web GIS”，中国测绘。2002年第二期
[23] Donald Hearn ,M.Pauline Baker ,《Computer Graphics》,电子工业出版社，1998
[24] David F.Rogers,《计算机图形学的算法基础》，机械工业出版社，2002
[25] 蒲保明，蒋继光，胡淑礼，《拓扑学》，高等教育出版社，1985
[26] 徐祖舰，《GIS入门与提高》，重庆大学出版社，2001
[27] 《GPS全球定位系统技术及其应用》，洪大永/编著，厦门大学出版社
[28] 王广运等，《差分GPS定位技术和应用》，电子工业出版社，1996
[29] 《C环境下地图图像矢量化及图形编辑技术与实例》，林春蔚等，海洋出版社，1993
[30] 段凌宇，“城市车辆联网监控系统的设计和实现”，硕士论文，1999
[31] 夏冰，”GPS车辆导航系统的总体规划和六城市的示范实现”，硕士论文，2001
[32] 姚振旺，“GIS环境矢量电子地图生成校正平台的设计和实现”，学士论文
[33] 王蔚然，“GPS车辆监控系统的总体设计”，学士论文，1997
[34] 王跃明，“点阵地图中道路的识别和提取”，学士论文，2000
[35] 鲍远律，“高科技研制及成果推广应用中的难点——从中国科大GPS实验室研制智能车辆监控系统谈起”，安徽软科学研究，12期（107），p6-10，1997.12
[36] 朱民，鲍远律，张旺生，“GPS军用车载卫星地球站天线自动定位系统”，《自动化与仪表》，第13卷，第5期，p54-56、65，1998.9
[37] 蔡季冰《系统辨识》北京.北京理工大学出版社 1991.
[38] D.E.Knuth ,《the art of computer programming》,国防工业出版社，1980
[39] 《数据结构》，严蔚敏，吴伟民等编著。清华大学出版社，1992年
[40] 《工程最优化》，孙德敏编著。中国科学技术大学出版社，1997年
[41] 《Delphi 3.0 从入门到精通》，李维，宇航出版社，1998
[42] 李寅，“面向对象的技术在系统开发中的应用”，学士论文，1997
[43] 《面向对象的Windows编程技术》，王培杰，大连理工大学出版社，1994
[44] 《算法与复杂性》，卢开澄，高等教育出版社，1995
[45] Joffrey Richter ，《Windows 95 Windows NT 3.5 高级编程技术》，清华大学出版社，1996
[46] http://www.gis.com
[47] http://www.gpsworld.com
[48] http://www.chinainfo.gov.cn
[49] http://www.gischina.com
[50] http://www.mapinfo.com
[51] http://www.gps.org.cn/
[52] http://www.21cn-highway.com
附录: 硕士期间发表的学术论文
[1] Yuanlu Bao, Wang Guojiang, Ye Jiaming, "Overall Design of Xiamen City GPS Intelligent Vehicle Monitoring System", TPL01-2, Proceedings of 2002 International Conference on Control and Automation, Xiamen, China, p.887-891, June 16-19, 2002.
