导航电子地图中道路网增量信息的多尺度探测

王艳慧， 尹 川， 丁宇虹

(1.首都师范大学资源环境与地理信息系统北京市重点实验室，北京 100048;2.首都师范大学三维信息获取与应用教育部重点实验室，北京 100048)

向用户提供现势性强的多尺度导航电子地图是移动位置服务系统的重要服务内容之一.多尺度道路网增量更新数据的内业管理和相应的更新发布方法已成为制约位置服务市场发展的瓶颈之一.而利用最新的大比例尺地图依次更新中、小比例尺地图的多尺度地图协同缩编更新作为当前国际GIS界研究的热点问题之一［1］，为多尺度导航电子地图更新提供了可供参考的思路.目前缩编更新主要存在4种模式:直接缩编替代更新、直接缩编叠加更新、增量缩编更新、新旧数据叠加缩编更新［2-3］，相关研究结合不同的应用领域和生产条件，分别选择了不同的更新模式，并针对增量数据提取与更新操作等问题展开研究［2-8］.但这些研究一般都是针对两个特定的比例尺，没有考虑增量变化信息在不同比例尺序列之间的传递及其对多尺度协同更新效率和精度的影响.对采用缩编增量信息来更新旧的小比例尺矢量空间数据(尤其是线状目标)的方法鲜有涉及，该方法理论上具有更新效率高、延续性强、一致性维护方便等特点，更符合位置服务中多尺度导航电子地图的缩编更新需求.

基于上述考虑，本文拟以导航电子地图中的主要地理框架要素——道路网要素作为主要研究对象，研究用增量多尺度缩编协同更新模式解决客户端多尺度空间数据动态同步更新问题的关键技术，实现增量数据以“打补丁”的方式融合到客户端中，为提高服务器端和客户端多尺度空间数据库协同更新的效率和精度，提供相应的技术参考.

1 研究方法

常规基础地图制图及更新一般重点关注路网要素几何表达，而导航电子地图更关注路网要素的拓扑表达.针对位置服务中由道路网新建、拓宽、合并以及废弃等物理变化引起的变化、新增、删除等数据库操作，基于增量信息的道路网多尺度缩编更新实质是采用“差文件”(新旧数据集之差，即增量数据集)思想，将各级比例尺下的增量变化信息以“打补丁”方式融合到客户端各级比例尺数据集中，从而实现数据集内容的一致性.其需要解决的实际问题是联动提取各级比例尺不同版本数据集之间的“差文件”，将“差文件”以可靠的精度“打补丁”入库融合，并保证几何、属性和拓扑数据的一致性和同步性.故此处的增量缩编更新处理过程可简化为增量信息提取、增量信息缩编融合及协调.

总体技术流程为:初始数据包括时刻t0比例尺为S1和S2的道路数据、时刻t1比例尺为S2的道路数据(t1＞t0、S1＞S2).若某时刻某一比例尺下的路网目标表达信息用F(t，S)表示，则增量更新主要包含两个环节:增量信息的提取与缩编传递.

首先，针对常用增量信息提取方法中基于经验阈值确定新旧目标匹配的不足，提出采用基于最大类间方差法自适应确定几何匹配阈值进而探测增量信息，并利用式(1)识别不同时刻同一比例尺道路数据的增量信息ΔF(t1，S1)，

其次，基于文献［9］提出的多比例尺表达目标之间的内连规则，搜寻变化目标对应的目标比例尺的匹配要素，利用插入、删除等数据库操作算子把增量信息集MyUpdateClass中的目标变化信息(ΔF(t1，S1))逐一映射到旧的对应小比例尺数据中，对新产生的数据集重新构建拓扑，并按照目标比例尺S2下的路网选取规则，即基于自适应网眼密度的增量信息选取规则，得到目标比例尺S2下现势性较好的时刻t1的数据.以此类推，一旦增量信息可在不同比例尺之间融合，即可实现它在不同比例尺之间的传递.

为验证上述方法的可行性，本文实验测试数据源选取某地开发区2007年(时刻t0)和2010年(时刻t1)的1∶10000(比例尺S1)、2007 年1∶50000(比例尺S2)道路网矢量数据，并在前期数据预处理中基于层次语义匹配规则［9］，已建立了同一时态下数据源中的道路目标与需要更新的其它比例尺地图中道路目标之间的映射关系.insert、delete和update数据库操作算子也均已在前期研究中实现［10-11］.下文将重点剖析增量探测和增量信息融合的技术原理及实现细节.

2 路网增量更新信息的探测

增量信息的识别和提取其实是一个目标匹配的过程，匹配精度会直接影响数据更新的准确率.针对路网线状要素，以目标匹配为基础提取更新信息的研究也很多.例如，文献［12-14］基于面积叠置率计算两条线目标的相似度，即通过比较两个道路缓冲区的相互重叠部分的面积占各自总面积的比值与给定阈值的大小关系来探测可能的匹配线对.其中多数学者都是根据制图经验来设定某个相对合理的数值作为阈值，而经验阈值没有考虑不同区域数据集的具体差别，匹配结果在一定程度上存在自适应性弱、误差较大、精度相对较低的缺点［15］.

因此，根据图像阈值分割灰度直方图与数据更新前后路段缓冲区面积迭置率灰度直方图表现出的高度吻合性.本文研究基于最大类间方差Ostu阈值分割算法来实现目标匹配阈值自适应精确计算的方法，尝试在避免几何数据的各种复杂统计量计算情况下，快速构建有效的候选匹配目标集，避免常用经验阈值选取时的精度干扰.

2.1 基本原理与流程

基于Ostu快速构建候选匹配集，进而再采用几何匹配算法，根据各种几何、度量、拓扑统计量的组合判断置信度最高的匹配对，进而从新版本中筛选出与旧版本相匹配的目标集，余下的“差文件”即为所要提取的该比例尺下的增量信息.具体算法流程为:计算同一较大比例尺下两个不同时态的数据集中要素的面积迭置率，根据面积迭置率集合反映的灰度直方图.利用Ostu法算出适合该数据集的最佳阈值e，以此为判据逐一探测几何变化，即遍历同一较大比例尺不同时刻路网要素表达的目标，对目标以一定宽度建立缓冲区，判断缓冲区面积迭置率Ssim(Li，Oi)与几何匹配阈值e的关系，

如果Ssim(Li，Oi)大于给定阈值，则说明两目标关联，则可再根据与之关联的要素个数及Ssim(Li，Oi)值具体确定其变化类型，提取相应的变化信息.确定了匹配的目标集后，再比较目标属性的变化，提取几何和属性变化信息.

2.2 基于Ostu法的类间方差阈值计算

Ostu法又称为或大津阈值分割法，是图像分割领域的一种常用算法.它假设图像的灰度直方图是由对应目标和背景的两个单峰的直方图混合构成，如果二者大小很接近，均值相差较大，且均方差足够小，则其直方图表现为较明显的双峰，如图1(a)所示.Ostu法适用于区分其背景与目标，且可使图像错分概率最小，而最佳阈值是使两个数据集的差异达到最大值［15］.

根据前期不同研究区不同数据集的大量实验研究，发现更新前后道路面积迭置率按大小排序生成的数据集合的灰度直方图(图1(b))与通常的图像阈值分割灰度直方图(如图1(a)所示)表现出高度的吻合性，据此提出用Ostu图像分割的阈值计算方法来实现目标匹配阈值精确计算.

图1 阈值化法图像分割Fig.1 Histogram distributions of the thresholding-based image segmentation

如图1(b)所示的一个研究区测算结果，横坐标表示面积叠置率，纵坐标表示面积叠置率取值的累计个数，可以看出数据呈明显的双峰分布，中间部分出现了一个较明显的峰谷拐点.进一步与实际数据比对，发现叠置率取值在拐点前的要素是由多条相交线段结点缓冲区重合引起的叠加分析误差及地图数据本身的误差造成.叠置要素之间不存在匹配关系，而叠置率取值在拐点后的要素则由存在匹配关系的两条线要素造成此分布特征.由此可以推断该数据集存在两类情况:一类为由非匹配关系产生的冗余数据，另一类为由匹配关系产生的有效匹配数据.因此，根据不同要素集表现出的叠置率直方图分布特征，可用Ostu法计算出直方图的分割阈值作为此要素集几何匹配的最佳阈值，把图像(待匹配数据集)的目标信息(匹配要素)和背景信息(非匹配要素)区分开来，从而达到根据不同数据集自身结构特点缩小候选匹配目标集合、提高几何匹配精度的目的.

2.3 实验验证

根据前文方法与某典型研究区数据源，进行目标匹配时先建立道路网拓扑关系，进行断链处理，然后度量面积叠置率，判断道路是否存在几何匹配关系.当缓冲区面积叠置率大于Ostu法所得阈值时，认为路段存在几何匹配关系.并以人工匹配为参照，在不同阈值下抽样统计不同条数的道路，验证匹配准确率.如表1所示，选取不同的实验阈值t，对应的匹配准确率也不相同，而采用本文Ostu法计算得到的阈值(t=29)时，无论是与经验阈值(t=30)相比，还是与其它随机选配阈值相比，匹配准确率均较高.由此可判断t=29为当前条件下的最佳阈值.

表1 不同阈值匹配精度Tab.1 Matching accuracy at different thresholds

为验证该方法的有效性和可行性，利用增补4个研究区的样本数据进行目标匹配准确度比较.计算结果表明匹配准确率在87% ～91%之间，均优于传统经验阈值匹配精度.

3 增量信息的多尺度缩编传递

由于新增道路信息中可能包含低等级道路，相对于小比例尺制图需求，可能存在许多不符合目标比例尺要求的冗余数据，需予以舍弃.选取数量、选取目标及选取道路的合理性和有效性，都是增量信息缩编更新过程中需要研究的问题.因此，本文考虑增量路段在整个目标比例尺图幅中的重要程度以及图幅负载量的总体控制，模拟缩编更新过程中人的思维过程，完善基于道路网眼密度的增量路段渐进式选取算法.

3.1 基本原理与流程

基于层次语义匹配规则［9］，建立源比例尺与目标比例尺地图中各路网目标之间的映射关系.基于遗传算法、连通性、网眼密度等道路选取方法［3，8］，经验证存在不能表达出不同区域的路网密度差异、难以用于复杂路网环境、本身算法较为复杂［16］的问题.因此，本文借鉴和集成扩展现有方法，综合考虑道路等级、长度、连通性、网眼面积、道路密度、是否为悬挂链等选取因素，分析相互之间的联系及优先顺序，以网眼作为选取单元，以网眼密度作为衡量路段密集程度的依据.根据不同的区域密度设置不同的网眼密度，逐级选出适合目标比例尺的路网增量目标，在此基础上，实现多尺度变化信息不同尺度之间的垂直传播和无缝融合.

图2所示为缩编流程，逐一遍历较大比例尺的增量数据文件包中的路网要素.若它为变化(删除、几何或属性变更)道路，则所有较小比例尺下与之对应的路网表达目标都要做出相应更改;若它是新增加的道路，则所有较小比例尺上的对应位置都增加该道路，从而达到联动更新的目的.当然，在此过程中，部分增量信息可能由于重要性较低而难以在小比例尺地图上表达出来，因此，还需基于网眼密度渐进式循环迭判，逐一剥离重要程度最低的道路.使得每次循环在满足网眼密度条件的情况下删除该区域内重要性最低的道路［16］，并完成与邻接网眼的合并.

3.2 路网增量目标自动选取密度阈值的确定

运用网眼密度来进行路网增量目标的缩编选取，关键是确定密度阈值.与目标几何匹配阈值的设定类似，传统方法采用制图比例尺规范中最小制图分辨率作为经验阈值，虽具有通用性，但没有考虑不同区域道路网数据集的具体分布状况，针对性较低.因此，为了体现不同区域的路网密度差别，本文借鉴样图统计法［3-4］，根据不同等级道路网的网眼密度分布趋势来动态调整密度阈值.即针对不同研究区的数据源，以网眼边界上路段的最低等级为标准，将网眼分成不同类型，对不同等级类型的网眼设置不同的密度阈值，分别统计分析研究区内相同等级路网密度及对应道路网条数的分布规律，据此确定不同道路等级的网眼密度阈值.

图3(a)和(b)分别为研究区2010年1∶10000和1∶50000主干道和支干道的网眼密度分布图.图3(a)两条线的走势大致相同，说明1∶10000地图的主干道路在1∶50000地图中多数被保留下来.同时根据1∶50000地图制图规范的要求，人眼能够分辨的最大密度为0.074 m/m2，故以此作为主干道选取阈值.图3(b)两条线走势差别较大，在密度0.010 ～0.350 之间，相同网眼密度下1∶10000地图的路网数目小于1∶50000地图的路网数目，其原因是较大比例尺下网眼合并后，密度较小的网眼增多;而在0.350～0.074之间则相反，相同网眼密度下1∶10000地图的路网数目大于1∶50000地图的网眼数目，同样是由于在较大比例尺下删除路段合并了网眼，导致网眼减少，密度同时变小.分界线在两条线的交点0.038 m/m2处，小比例尺制图需 选取密度大于此值的路网目标，即此值为密度阈值.

图2 增量信息多尺度缩编更新流程Fig.2 Flowchart of multi-scale generalization for incremental information

3.3 实验验证

在 Windows 7/CPU 1.25 GHz、ArcGIS Engine SDK/Visual Studio.NET 2008环境下，进行增量信息的缩编提取.增量文件包中共有路段234条(见图4)，结点数14458个，整个实验用时823 s.用更新得到的1∶50000新数据(图5(a))，与已有的2010年1∶50000现势数据进行对比(图5(b))，重要度较高的高等级路网目标全部选中，可以满足路网数据更新的结构选取需求.与2.3节增量探测相对应，增补其它4组样区的实验，并定量论证了多尺度组合探测增量选取算法的可行性.

图3 道路网眼密度分布Fig.3 Mesh density distributions of roads

图4 增量数据Fig.4 The incremental representation data

图5 更新的1∶50000地图及对应的现势1∶50000地图Fig.5 The updated and the corresponding current 1∶50000 maps

4 结束语

基于多尺度缩编协同更新模式，实现多尺度道路网增量数据的提取和融合是导航电子地图更新的研究热点之一.本文提出基于Ostu法计算最佳阈值进而探测增量目标，并基于不同等级道路网的网眼密度分布趋势动态调整密度阈值，完善了基于道路网眼密度的增量变化目标渐进式选取算法.通过实验验证了该方法的可行性，为聚焦候选匹配目标集及提高增量缩编更新精度提供了可行的技术参考.本研究未考虑道路网与电子地图中其它兴趣点(例如居民点)的连通情况，对可能是通向居民点唯一道路的特殊情况未进行特殊处理;且当两个数据集的面积叠置率直方图存在差异较大的峰谷时，有必要更客观地定义选取规则，进一步增强算法的实用性.

［1］YE Y，CHEN B，WAN B，et al.MMS-IU model for incremental update of spatial database:geo-informatics in resource management and sustainable ecosystem［M］.Berlin:Springer Heidelberg，2013:359-370.

［2］陈军，胡云岗，赵仁亮，等.道路数据缩编更新的自动综合方法研究［J］.武汉大学学报:信息科学版，2007，32(11):1022-1027.CHEN Jun，HU Yungang，ZHAO Renliang，et al.Road data updating based on map generalization［J］.Geomatics and Information Science of Wuhan University，2007，32(11):1022-1027.

［3］胡云岗，陈军，李志林，等.基于网眼密度的道路选取方法［J］.测绘学报，2007，36(3):351-357.HU Yungang，CHEN Jun，LI Zhilin，et al.Selective omission of road features based on mesh density for digitalmap generalization［J］.Acta Geodaetica et Cartographica Sinica，2007，36(3):351-357.

［4］赵彬彬.多尺度矢量地图空间目标匹配方法及其应用研究［D］.长沙:中南大学，2011.

［5］GAVRILA D M， BAYESIAN A. Exemplar-based approach to hierarchical shape matching［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29(8):1-14.

［6］SAMAL A，SETH S，CUETO K.A feature-based approach to conflation of geospatial sources［J］.International Journal of Geographical Information Science，2004，18(5):459-489.

［7］邓敏，徐凯，赵彬彬，等.基于结构化空间关系信息的结点层次匹配方法［J］.武汉大学学报:信息科学版，2010，35(8):913-917.DENG Min， XU Kai， ZHAO Binbin， etal. A hierarchical approach for nodes matching based on structural spatial relations［J］. Geomatics and Information Science ofWuhan University， 2010，35(8):913-917.

［8］邓红艳，武芳，翟仁建，等.基于遗传算法的道路网综合模型［J］.武汉大学学报:信息科学版，2006，31(2):164-167.DENG Hongyan，WU Fang，ZHAI Renjian，et al.A generalization model of road networks based on genetic algorithm［J］.Geomatics and Information Science of Wuhan University，2006，31(2):164-167.

［9］王艳慧，李小娟，刘晓萌.路网要素多尺度表达目标的层次关系分析［J］.中国图象图形学报，2007，12(8):1451-1456.WANG Yanhui， LI Xiaojuan， LIU Xiaomeng. On hierarchical relation among road multi-scale representation［J］. Journal of Image and Graphics，2007，12(8):1451-1456.

［10］尹川.导航电子地图更新中道路网增量信息的提取与发布［D］.北京:首都师范大学，2012.

［11］丁宇红.导航电子地图中道路网增量缩编更新信息的提取［D］.北京:首都师范大学，2013.

［12］应申，李霖，刘万增，等.版本数据库中基于目标匹配的变化信息提取与数据更新［J］.武汉大学学报:信息科学版，2009，34(6):752-755.YING Shen，LI Lin，LIU Wanzeng，et al.Changeonly updating based on object matching in version databases［J］.Geomatics and Information Science of Wuhan University，2009，34(6):752-755.

［13］QIAN H Z，ZHU Q，GUO M，et al.Oriented road network macrostructure matching algorithm［J］.Physical and Numerical Simulation of Geotechnical Engineering，2011，3:18-21.

［14］MASUYAMA A. Methodsfordetectingapparent differences between spatial tessellations at different time points［J］.International Journal of Geographical Information Science，2006，20(6):633-648.

［15］尹川，王艳慧.路网增量更新中基于OSTU的目标几何匹配阈值计算［J］.武汉大学学报:信息科学版，2014，39(9):1061-1067.YIN Chuan， WANG Yanhui. Targetgeometry matching threshold in incremental updating of road network based on OSTU［J］. Geomatics and Information Science ofWuhan University， 2014，39(9):1061-1067.

［16］张小朋，尹路明，王鹏波，等.地图数据缩编更新中的道路自动选取研究［J］.测绘工程，2012，21(5):13-16.ZHANG Xiaopeng，YIN Luming，WANG Pengbo，et al.A study of road automatic selection in map data generalization based updating［J］. Engineering of Surveying and Mapping，2012，21(5):13-16.