聚焦︱一种顾及重要性意义和空间分布特征的兴趣点选取方法
The following article is from 地理信息世界GeomaticsWorld Author 地理信息世界
导读
在互联网时代，电子地图应用广泛。兴趣点作为移动地图和网络地图表达的重要内容，承载着用户的目标搜索、属性查看、路线查询等功能，因此兴趣点数据的准确性将影响地图的质量与可用性效果。本文提出一种兼顾重要性和空间分布特征的兴趣点选取方法，既能准确地保持兴趣点群的空间分布特征，又能顾及单个兴趣点的重要性意义，可用于多尺度矢量地图数据库的实际建设中。
点群综合一直是地图综合领域的研究热点，一方面大量的地理现象表达以点群形式呈现，如城市兴趣点、散列的居民点、成群分布的岛屿、湖泊等，选取化简是主要的综合手段；另一方面点群分布上的多尺度表达也是空间分析、数据挖掘等其他领域感兴趣的内容。点群作为制图要素的重要内容，对地图图面表达的详细程度具有较大影响，因此点群综合也是制图综合中重要的方面。在实际的生产过程中点群的数量很大，如果使用人工的方式进行综合，既费时又费力，因此迫切需要进行点群自动综合选取研究。长期以来，人们一直在对点群的综合进行研究，并得到了许多不同的综合模型和算法，取得了一定的成果。
在地图综合中需要考虑地图包含的四类关键信息，即统计信息、拓扑信息、专题信息和几何度量信息。已有的点群选取算法主要分为两类，第一类算法是基于点重要性意义的选取方法，主要是针对居民点选取的，如空间比率算法、分布系数法、重力模型法、圆增长算法等。这些方法的基本思想是通过模型来计算每一个单独点的重要性，然后按照重要性排序被依次选取。这类算法主要考虑了居民地的属性等级与距离关系，虽然可以保持综合后专题信息的正确性，但是在很多情况下可能导致几何和拓扑信息的错误传输。第二类算法是基于点群的分布特征的选取方法，如基于凸壳的点群选取算法、保持空间分布特征的点群化简算法、基于Kohonen网络的点群综合方法等。这些方法虽然考虑了几何和拓扑信息，但是没有顾及到专题信息。Yan提出了一种新的基于Voronoi的算法，虽然同时顾及了四类关键信息，但是并没有结合具体的实例进行深入的分析。
兴趣点数据是一种反映真实地理实体的点状数据，属于空间数据。具有数据量大、覆盖范围广、更新快、精度高等特点。在互联网时代，电子地图应用广泛。而兴趣点作为移动地图和网络地图表达的重要内容，承载着用户的目标搜索、属性查看、路线查询等功能，因此兴趣点数据的准确性将影响地图的质量与可用性效果。但当前兴趣点的表达存在许多问题，尤其是在用户查询特定信息时，由于返回结果数据量较大，会造成显示区域兴趣点的重叠、压盖等现象，进而影响到用户对地理空间的认知，降低地图的可用性。本文在已有方法的基础上，提出一种新的兼顾重要性和空间分布特征的兴趣点选取方法。
兴趣点数据可以看作特殊的点群，在选取的过程中，既要保持整体的空间分布特征，也要顾及个体的重要性意义。根据这一原则，在算法中采用如下的措施：
1）在点群选取过程中，首先要解决的是选取数量的问题，在这里运用著名的基本选取法则来得到兴趣点选取的数量，公式如下：
式中，Nf 是综合后地图上的点数；No 是原始地图上的点数；So是原始地图比例尺分母；Sf 是综合后地图比例尺分母。
2）因为Delaunay三角网及其对偶图Vononoi是邻近分析的有力模型，并且在点群要素选取问题上得到广泛应用。本方法采用Voronoi图来保持空间分布特征，公式如下：
式中，ρi是第i个点的图元密度；Ai是第i点所在的Voronoi多边形的面积。
3）在兴趣点重要性意义方面，主要考虑两方面，一方面是和道路的空间关系，另一方面则是个体点的地理意义，公式如下：
式中，
式中，Ri 为第i点的道路关系权重，Gi 为第i点的专题权重，wi 为第i点量化的重要性值，Δw为量化的重要性值间隔，Vi 为第i点无量纲的重要性权值。
4）每个点的重要性程度与该点所在的Voronoi多边形面积同时被考虑，第i点的选取可能性按照下式计算：
式中，Pi 是指第i个点的选取可能性，Vi 和Vk表示第i个点和第k个点的重要权重值，Ai 和Ak表示第i 个点和第k个点所在的Voronoi多边形的面积。
基于以上的思路，算法有4个步骤：确定点群范围边界、构建新的点群；计算点的重要性权值；Voronoi图动态构建；算法结束、获取最终选取结果。以下结合图1实例对算法进行论述。
图1 实验源数据（共500个点）
1）确定点群范围边界，构建新的点群，步骤如下：在本文中，点群的分布范围边界被认为是不确定的。
①提取边界点：对原始点群构造Delaunay三角网，得到范围多边形并提取边界点，如图2a所示。
②得到新点群：初始范围多边形上的边界向外扩张，新的边界平行于初始边界，扩张距离等于初始边界上边长的平均值，如图2b所示。将原始点群和新的边界点合并为新点群。
2）计算点的重要性权值
根据上文的公式（2），依次计算点群中每个点的重要性权值Vi；其中道路权重Ri 根据点i 和周围道路的空间分析计算得出，专题权重Gi 则根据比率量表和专家打分算出。
3）Voronoi图动态构建化简点群
①构建新点群的Voronoi图，如图2c所示，原始点群中的点有3种状态的取值：“正常”“固定”“删除”。并假设每个初始点的状态都是“正常”的。
②根据公式（4）计算每个点的选取可能性值，然后把这些点按照选取可能性值，升序排列。
③依次找出集合E中“正常”的兴趣点ei，将其状态更新为“删除”，并将其他的邻接结点状态更新为“固定”；当集合E中没有“正常”的点时，把“固定”点改为“正常”点，完成本轮删除。
a 点群分布多边形
b 新点群
c Voronoi图动态化简（红色阴影中的点将被删除）
图2 兴趣点的单次抽样删除
4）判断算法是否结束
若经过某一轮抽样删除后，剩下的“正常”点为Nc个；经上轮抽样删除后留下来的“正常”点有Nt个，选取完成后，根据式（1）的计算，地图上点数的理论值应为Nf个。若Nc大于Nf，则算法未结束，返回第3步继续执行选取。否则，算法结束，比较|Nf-Nc|和|Nf-Nt|的大小，若|Nf -Nc |-|Nf -Nt|>0，则结果图上保留的点集为Nt；反之为Nc。基于上面的算法步骤，整个算法的流程如图3所示。
实验环境由Visual Studio 2010 C#、ESRI ArcEngine10组成，实验数据为中国西南地区某城市的娱乐场所兴趣点数据，原始数据如图4a所示，共1 517个兴趣点。模拟比例尺从1∶10 000综合为1∶20 000，1∶50 000，1∶100 000的过程。其中，根据计算的Wi值，将重要程度分为四级（I、II、III、IIII级），4个级别的重要性权值依次设置为1、2、4、8。按照1.2书中的算法流程，对原始数据展开实验，结果如图4b、图4c、图4d和表1所示。为了更好地对实验结果进行分析，将Voronoi灰度化处理，得到如图5所示的分布密度灰度图。图6为综合选取后，不同比例尺下各级兴趣点的保留情况。
图3 兴趣点选取算法流程图
图4 不同比例尺下兴趣点选取结果
表1 不同比例尺下各级兴趣点数量分布
图6 不同比例尺(横坐标)与各级兴趣点保留比例(纵坐标)变化关系
1）在1∶20 000、1∶50 000、1∶100 000比例尺下综合选取后保留的兴趣点数量非常接近于根据基本选取法则计算得到的点目（由基本选取法则计算得到的点数分别为1 073，678，478，而实验中最后保留的点数分别为996，629，439。）即点群的统计信息传输正确。
2）从图5、图6中可以分析得出，在选取过程中，保持了原始点群的分布范围和原始点群的相对分布密度，即拓扑和几何度量信息传输正确。
3）图6分析了不同比例尺下的各级兴趣点的数量占比情况，表明随着综合的比例尺变小，保留的兴趣点中具有重要性意义的高程点比例越来越大，即专题信息传输正确。
本文以兴趣点的综合选取为出发点，提出了一种顾及重要性意义的兴趣点选取算法，不仅遵循地图综合的基本原则，且顾及了兴趣点的地理特征和地理意义，使得在综合选取过程中，点群的统计、专题、拓扑和度量信息传输均得到有效控制。本文方法中的算法已经通过编码实现，并且使用某市特定范围的实际兴趣点数据进行实验，实验表明本文所提出的方法有如下优点: ①准确地保持了兴趣点群的空间分布特征；②顾及了单个兴趣点的重要性意义。并且实验证明该方法结果合理准确，可用于多尺度矢量地图数据库的实际建设中。本算法的不足之处在于没有考虑点要素的符号化表达，以及在兴趣点的重要性权值方面，没有给出普适性的方案。这些不足之处需要在将来进一步研究、解决。
责任编辑：林冬娜、邓小云
文章来源：地理信息世界GeomaticsWorld