导航电子地图存储格式研究进展-李清泉

1导航数据物理存储格式研究进展武汉大学2009年10月14日李清泉教授2提纲¾导航领域标准研究现状¾主要技术难点¾研究成果与进展¾后续研究一、导航领域标准发展现状2009-10-274导航领域的标准体系国际导航电子地图数据格式国际上流行的导航电子地图数据标准/格式,有以下几种：-GDF(v3.0/4.0)-KIWI(v1.22)-SDAL(v3.0)GDF标准简介•GDF重在对数据的组织和表达，而其物理存储只是简单地采用ASCII码的单文件形式。•GDF对要素属性的定义非常全面，例如，仅对Road的定义中就包括了长度单位、道路材质、道路方向、建筑情况、自然障碍物、（高架）路面高度、平均时速、最高限速、最大承重等20多项，同时还定义了各种要素间的关系。•GDF基于通用的而非特定应用的数据模型，往往并不直接作为与硬件相关联的电子地图数据，而是扮演了作为基础数据交换格式的角色。GDF的要素模型线要素面要素面边点要素结点复杂要素Level-2Level-1要素的集合Level-1添加类型Level-0基本几何图元SDAL格式简介•NavTech公司致力于生产大比例尺的道路网商用数据，包括详细的道路、道路附属物、交通信息等，这些数据主要用于车辆导航应用。•SDAL格式本身提供了对地图快速查询和显示的优化，可提高路径分析和计算速度，并可存储高质量的语音数据为用户提供语音提示。•NavTech公司自有的商用地理数据库的数据格式,需要通过SDAL编译器，把一般的电子地图数据转换为SDAL格式，进而由SDAL程序接口调用SDAL格式数据用于各种车辆导航应用。SDAL数据组织与索引•格式采用划分数据包或数据块的形式来管理数据。•数据包的类型包括空间数据包、非空间数据包和索引数据包。•格式中主要用到几种主要的索引：KD树空间索引B树索引稠密索引POI多层索引KIWI格式简介•专门针对汽车导航的电子地图数据格式，旨在提供一种通用的电子地图数据的存储格式。•支持地图数据快速索引，压缩数据量，并支持扩展。•在结构上采用纵向分层、横向分块的原则，采取将数据物理存储和逻辑结构相结合的机制。•直接与硬件和车载导航应用相关的电子地图格式，其各种特性都完全针对特定的导航应用需求而设计，不具有一般意义上的通用性。KIWI格式数据结构图国内导航物理格式研究现状•目前，导航电子地图开发生产方面的系列标准如下：《车载导航地理数据采集处理技术规程》（GB/T20268-2006）《导航电子地图安全处理技术基本要求》（GB20263-2006）《导航地理数据模型与交换格式》（GB/T19711-2005）《车载导航电子地图产品规范》（GB/T20267-2006）缺少导航电子地图物理存储格式标准。•无法在不同的应用之间共享地理信息。•生产商的成本巨大、用户消费价格高昂。•已无法适应不断发展的市场需求。结论：亟需统一的导航电子地图物理存储国家标准。二、主要技术难点技术难点•导航电子地图数据更新•实时交通信息•交通附属设施及增值服务•空间认知要素的应用；•基于车道的道路数据模型和信息表达；•地址编码方法和技术；•三维实景数据的管理模型和表达；导航电子地图数据更新按照用户需求和现实条件不同，导航电子地图数据的更新可分为三种方法：¾基于全部更新的更新方法；¾基于PC(PersonalComputer)的更新方法;¾基于无线网络的更新方法。2009-10-2716导航电子地图数据更新•欧洲的ActMAP项目于2002至2005年对电子地图数据库进行了动态更新的策略和机制的研究。ActMAP通过把在线更新数据和车辆上已经存在的数据库整合在一起实现数据更新；–利用局部增量更新的策略解决通信带宽的问题；–通过定义标准的中间格式解决对各种私有数据格式的兼容性问题；–根据不同应用对更新延迟要求的不同使用不同的更新策略，比如通过建立缓冲区节约格式转换的开销；–采用更新事务管理机制保证更新前后地图数据的一致性；–建立合适的更新传输链模式以对更新数据进行缓冲管理；–采用基准地图策略以便于导航地图的版本管理。2009-10-2717ActMap框架结构•ActMap是一个开放性的标准，不针对任何特定的导航电子地图格式，故并没有涉及导航电子地图存储格式对增量更新的支持度问题。ActMap存在的限制1）通信的带宽；2）由于更新数据提供者和更新用户都有自己私有的数据格式组织和存储于地图相关的数据，所以标准的更新方法需要提供能够处理多种数据格式的方法；3）对于更新服务的实现来说，更新用户会有时间限制；4）更新用户对实时地图的质量会有要求，所以标准的更新方法需要保证地图的质量；5）标准的更新方法需要参照并兼容各种现有的工业标准，如ISO14825:2004GDF4.0、ISO/NP22953XGDF和ISO/CD17572位置参考等。实时交通信息•动态导航服务已成为世界规模的热点研究课题，各国学术界和企业界开展了许多研究与应用实践工作：VICS系统、G-BOOK（日本）Ali-Scout系统（欧洲）TravTek和ATIS系统（美国）•国内动态导航服务存在如下薄弱的理论与技术问题：1)车辆导航服务与交通信息高效集成的系统架构问题；2)实时交通信息的高效数据组织问题；3)高效实时性动态路径计算问题等。2009-10-2720实时动态交通信息的空间编码•日本和欧美为代表的西方发达国家普遍开展了动态导航相关的研究和应用。日本的VICS、欧洲的RDS-TMC、英国的Smartnav等都已经得到实际应用。•我国的动态导航还处于研究和验证阶段，中欧合作项目DYNASTY、基于动态信息的智能导航软件与应用系统”等正在实施。但是，目前还没有真正满足大众市场的产品出现。•交通信息编码方法目前研究的重点是以路段为主要参考对象，其主要原则有：–路段及节点需要拥有永久唯一的编号；–需要兼容其他主流交通信息发布方式；–具有可扩展性以保证适应未来的动态交通信息发布方式。三、研究成果与进展研究成果¾路网、交通信息一体化模型¾基于服务器\客户端的导航数据动态增量更新策略¾基于动态信息的智能导航系统模型¾基于实时交通信息的动态路径算法¾考虑中国特色因素的属性导航数据动态增量更新策略•为导航数据文件中每个数据单元预留一定的空间•管理“文件碎片”以便回收利用•分而治之，将导航数据文件进行多尺度分割•更新的内容以及更新数据文件的定义•更新文件传输策略•对客户端导航数据文件的更新策略•服务器端数据库设计及更新策略导航数据文件多尺度分割把全国数据分成若干个等级的数据文件，等级高的数据文件仅管理高等级路网，等级最低的数据文件管理其所辖区域所有等级的路网。更新文件传输单一文件方式发送更新数据文件更新文件传输分成小文件发送更新数据文件客户端服务器T1T2更新文件1T3Tn2n………...导航开始前导航过程中更新文件传输交互式发送更新数据文件客户端服务器T1T2更新文件1T3Tn2nT4Tn-1………...导航开始前导航过程中导航完后对客户端导航数据文件的更新策略客户端接收到从服务器段发送过来的更新数据文件以后，首先对更新数据文件进行解析，从中提取出更新数据。更新过程如下图所示：基于实时交通信息的动态路径算法•利用实时交通信息来计算行车最优路径计算。算法主要关注集中在实时性、动态性与实用性三方面。现有路径规划算法，仍然以静态交通地理信息为基础，大多数采用传统迪杰斯特拉算法的改进算法。•郑年波博士，在面向动态导航的交通网络数据模型与应用算法研究(博士学位论文)提出了基于动态交通网络的时间依赖路径规划算法。基于实时交通信息的动态路径算法•提出一种嵌入式环境基于实时交通信息的多层次路径规划算法，该算法很好地适应嵌入式硬件环境的内存小、计算能力弱等特征，可以自动在一定限度内规避拥堵路段，实现交通信息的嵌入式实时规划应用。（方志祥，宋莺.嵌入式环境基于实时交通信息的多层次路径规划算法,武汉大学学报信息科学版，2008。）基于动态信息的智能导航系统模型针对国内动态导航服务存在的薄弱问题，设计出动态导航系统框架，该框架包括：•数据供应层；•网络导航服务中心；•网络通信层和用户层。基于动态信息的智能导航系统模型•数据供应层：导航系统与内容提供商之间的接口层，网络导航的各种内容服务正是通过该层获得。•服务中心：全部导航信息的集散地和处理中心。它以导航地图数据库为基础，实现以导航电子地图和交通流信息为主的数据管理、信息发布、车辆管理、位置服务等综合性的导航服务。•通信层/传输层：服务中心与移动终端之间的纽带，为网络导航提供通信和数据传输的通道。•用户层：相对于服务中心的“客户”。客户可以通过“push”或“pull”等方式，根据需要下载部分必需的数据，因此导航终端能使用最新的导航地图数据，并从导航信息服务中心获取各种导航服务。基于动态信息的智能导航系统模型李清泉，余洋，宋莺等.AModelforIntelligentNavigationSystemBasedonDynamicTrafficInformation,第七届亚太平洋交通运输协会年会,2008.路网、交通信息一体化模型1)目前的导航数据格式(如GDF、KIWI、SDAL)主要考虑了网络的导航特征，普遍缺乏表达时态信息的能力，而且还不支持网络中事件特征的线性参照。2)GIS-T线性数据模型主要是面向交通管理而设计的，对网络的导航特征考虑不足，而更为重要的是，它们基本上不支持动态信息的表达。3)目前的GIS-T时空数据模型大多不是专门针对导航应用而设计，对网络导航特征考虑不充分，如MDLRS模型、FB-NP-Model模型、SBDTN模型等，即使有所考虑，在实现上也存在需要改进的地方，如导航数据整体模型[桂智明,2006]。为实现动态导航，有必要深入研究集成考虑网络导航特征、线性特征以及时态特征的，动态交通信息与道路网一体化的时空数据模型。路网、交通信息一体化模型•提出了一种面向导航应用的、动态交通信息与多尺度道路网一体化的交通网络时空模型——UTN_N模型，并设计了详细的道路网层次数据结构、交通网络时态数据结构以及移动对象逻辑数据结构。（郑年波.面向动态导航的交通网络数据模型与应用算法研究，博士学位论文，2007。）路网、交通信息一体化模型生存期(lifespan)空间随时间变化几何变化拓扑变化空间随尺度变化多重(多尺度)表达属性随空间变化分段属性属性随时间变化时态属性按时间顺序存储为一个链表面向动态导航的一体化交通网络模型(UTN_N)概念框架概念模型交通附属设施及增值服务•道路的属性包括车牌单双号禁行以及车牌属地管制等信息。•POI的存储，考虑到其数量之大，故按中国的省市区划进行分区存储，再按拼音排序。在加速POI搜索的同时，也方便按区划分文件存储。•存储道路附属设施时，以路段为独立对象，并以此路段ID为关键字建立顺序索引。路段的所有道路附属设施存在一个表里，即[道路附属设施表]，每种道路附属设施对应一个编号。在导航电子地图存储格式的设计中，兼顾到道路附属设施以及道路相关增值服务数据的存储，并且充分考虑中国特色因素。交通附属设施编码表序号道路附属设施名称编码1公路桥02铁/公路两用桥13立交桥24人行天桥35建筑中桥46公路隧道57人行地道68人行横道79收费站810公交车停靠站911停车场1012交通广场1113交通信号灯1214护栏1315交通标志牌1416标线1517标柱1618隔离带1719隔音墙1820绿化带1921功能栽植2022路灯212009-10-2739增值服务数据组织POI相关增值服务道路相关增值服务联系电话联系地址网址文字介绍一段语音图片集合多媒体文件动画文件其他数据道路名称道路等级建设单位管理单位一段语音图片集合多媒体文件动画文件其他数据数据项定义表数据项数据项其他类型增值服务行政区增值服务数据行政区增值服务数据行政区增值服务数据时空数据的自适应可视化⎪⎩⎪⎨⎧+−=+−=00000000)(),,,()(),,,(yyyscaleyxyxfxxxscaleyxyxfixixVa