矢量地图数据简化研究进展

张振鑫,张　维,刘　嫔,寇一丹,邓　浩

(1.北京师范大学 地理学与遥感科学学院遥感科学国家重点实验室，北京 100087；2.中南大学 地球科学与信息物理学院,湖南 长沙 410083；3.中南大学 信息科学与工程学院,湖南 长沙 410083)



矢量地图数据简化研究进展

张振鑫1,张维2,刘嫔3,寇一丹1,邓浩2

(1.北京师范大学 地理学与遥感科学学院遥感科学国家重点实验室，北京 100087；2.中南大学 地球科学与信息物理学院,湖南 长沙 410083；3.中南大学 信息科学与工程学院,湖南 长沙 410083)

摘要：从传统矢量数据简化算法及基于并行技术的矢量数据简化算法两方面进行分析，将当前传统的矢量数据简化算法：Douglas-Peuker的简化算法及演化、Li-OpenShaw简化算法及演化、渐进式的简化算法及演化、基于小波理论的简化算法及演化和简化质量的评价，在基于并行技术简化算法研究的基础上，指出矢量数据并行简化和简化算法的智能化、感知化、自动化是矢量数据简化研究发展的趋势。

关键词：矢量数据；简化；算法；并行

矢量数据是GIS领域一种重要的数据[1]，尤其是ESRI公司推出shapefile格式的文件后，矢量数据的应用性和普及性越来越广泛。对矢量数据的可视化是地理信息科学领域研究的一个重要方向[2]，矢量数据的可视化关系到矢量数据应用的广度与深度、关系到决策者的决策能力、关系到科研成果的优劣。矢量数据的简化又是矢量数据可视化中的一个重要研究方向[3]。

从矢量数据简化的实现方式上看，矢量数据简化可分为基于并行计算模式和串行计算模式2种，随着计算机技术的提高及计算机计算能力的增强，以前基于串行的数据处理算法已不能满足科研和应用的需要，因此，基于并行技术的数据处理算法应运而生[4]。本文先对当前传统的、基于串行计算的国内外矢量数据简化算法研究现状进行总结，再对国内外矢量数据并行简化研究现状进行论述，通过本文的研究，可初步获得国内外关于矢量数据简化的研究进展情况，对矢量数据可视化的研究有一定的参考价值。

1传统的矢量数据简化算法

由于计算机发展水平的限制，传统的矢量数据简化算法大多基于串行计算模式。

1.1Douglas-Peuker简化算法及其演化

对矢量地图的简化研究最早开始于1973年，Douglas与Peuker提出了Douglas-Peuker折线简化法，即先将矢量折线首、尾点相连，再计算其他点到该线段的距离，取距离中的最大值，若最大距离不大于阈值，则将该线段中间曲线的其他点舍去，以该条线段代表曲线；若最大距离大于阈值，则将该点与首、尾点各自相连，形成两条新的线段，再以各新形成的线段为基线，递归搜索，直到所有线段间曲线上所有点的距离都在阈值范围内[5]。该算法效率较高，且可保持线要素的重要几何特征。但在简化过程中会导致拓扑关系发生改变，造成简化后的线要素出现拓扑关系不一致，容易导致自相交[6]。Guibas等证明如何在避免自相交的情况下保留尽可能少的点是一个NP-hard问题[7]。Saalfeld在Douglas-Peuker简化算法的基础上，提出拓扑一致性保持的矢量数据简化算法[8]。Mustafa等提出一种基于Douglas-Peuker算法和ε-Voronoi图的简化方法，即通过模板深度缓存，将Voronoi区域渲染到模板缓存中，再通过模板测试，剔除ε-Voronoi区域外的点，保证每个要素简化结果都位于ε-Voronoi区域中，能够一定程度上避免要素间的相交，但不能避免要素内部的自相交，由于ε固定，不具有灵活性和自适应性，简化的区域受地物分布密集程度的限制[9]。

1.2Li-OpenShaw简化算法及其扩展

Li-OpenShaw算法是一种基于自然现实的自适应化简算法，可以得到较好的化简结果，这种方法借助于滑动圆，使滑动圆在曲线上滑动，通过对曲线上的节点重采样，得到简化后的采样点，达到矢量数据简化的目的[10]。通过控制滑动圆的大小，来达到不同尺度下的简化结果，这种方法具有多尺度的灵活性，但该方法未考虑极大值的曲线点与多条曲线相交的问题。针对上述问题，朱鲲鹏等提出Li-OpenShaw算法的改进方法，主要解决多条线相交于一条曲线的极大值点问题[11]。Raposo在基于自然原则的Li-Openshaw简化算法基础上，在Nyquist-Shannon采样理论的控制下，生成六边形来完成矢量数据简化，与基于四边形的简化方法相比，这种方法在保持简化目标的形状特征方面有着明显优势，但六边形的生成与处理需要消耗一定时间，在大规模数据的简化方面有一定的限制[12]。

1.3渐进式的简化算法及其演变

郭庆胜提出一种基于线特征的渐进式化简算法，通过查找线结构的极值点、拐点、凸点及单调区间等建立线数据的分层结构特征进行简化[13]。Poorten提出利用Delaunay三角形进行曲线综合简化，利用三角形之间的连通关系，维护曲线简化前后的拓扑一致性[14]。艾廷华等提出一种曲线弯曲程度的二叉树表达方法，提出曲线弯曲层次的概念，以曲线为约束构建三角网，依据三角形与顶点、曲线的关系对三角形进行分类；依据三角形的类型，通过剥皮算法，根据剥皮过程，将曲线划分为二叉树组织结构，再根据弯曲的层次结构，将曲线化简[15]。杜维等提出一种基于组合优化策略的多边形简化方法[16]。操震洲等利用预先存储的节点偏移量化简曲线，利用单调链求交的方式实现多分辨率下化简曲线，从而维护拓扑一致性,达到渐进式曲线化简的目的[17]。

1.4基于小波分析的矢量数据简化算法

利用小波理论也可对矢量数据进行化简。小波分析理论具有多分辨率分析数据的特性，可用于数据的多分辨率分析与表达，且具有正交性、对称性、短支撑性和高阶消失矩等特性[18]。吴纪桃等建立小波理论与矢量数据多尺度简化的关系模型，并从数学角度给出该模型的适用情况[19-20]。一些学者将其他一些理论同小波理论结合协调进行矢量数据简化。Saux将B-spline理论与小波理论结合，对一些待平滑的区域进行平滑简化[21]。吴凡利用小波理论，结合Mallat[22]算法，通过建立尺度一致性约束模型，忽略两个整数尺度间的次要因素，实现任意两个整数比例尺度下线状数据的近视简化[23]。朱长青等基于小波分析理论，针对等高线数据，论述不同尺度下的矢量数据简化、综合的方法，采用Douglas-Peuker简化算法，提取小波变换后的边界特征点，再在数据简化完成后恢复特征点，保持矢量数据间的拓扑一致性[24-25]。王明常等基于小波理论，利用线状要素的极角变化，以达到平滑的方式进行简化，突出简化前后的视觉效果和精度[26]。

1.5矢量数据简化质量评估研究现状

关于矢量数据的简化精度包括两个方面：几何精度和属性精度[27]。武芳等基于化简后曲线几何特征及单点位置变化的特点，提出评价简化质量的方法。几何特征评价指标包括线的长度比、曲折度；点位置变化评价包括位移标准差、位置误差和缓冲区限差等[28]。刘鹏程等提出一种基于对偶面傅立叶形状描述子的相似性评价指标，以傅立叶形状描述子作为一个向量，以向量的欧式距离来度量简化前后向量的相似程度[29]。Weibel研究矢量数据简化中约束条件，包括几何约束(如宽度、长度等)、拓扑约束(如简化前后实体间的拓扑关系一致性等)、结构约束(如简化后道路不要压到实体等)、Gestalt约束(如需要保持平滑的线性地物化简前后要保持平滑一致性等)[30]。朱鲲鹏等在Weibel提出的约束条件基础上，提出一种满足约束条件的矢量数据简化质量评估方法，通过比较简化前后的光滑性、位置和点位位移，定量地得到简化效果的评价指标[31]。

2基于并行计算的矢量数据可视化

基于并行计算的矢量数据简化主要将传统矢量数据简化算法与多核计算机或计算机集群相结合，通过对负载均衡、任务均衡的设计来完成快速并行简化的目的。并行计算的方式包括：基于共享内存的并行方式、基于消息传递的并行方式和数据并行的方式等[32]。

2.1基于共享内存的矢量数据简化算法

随着计算机多核技术的提高，基于共享内存方式的并行越来越普及，与基于消息传递的并行方式相比，基于共享内存的矢量数据简化方法实现效率较高[4]。马劲松等采用单机多核的方式进行Douglas-Peucker简化算法的并行实现研究，并在此基础上完成地图线要素的实时综合，该研究得出，采用多核并行的方式，Douglas-Peucker算法的效率大幅度提高[33]。张立强等基于OpenMP和GPU并行手段，通过对数据加载、数据简化及数据显示的并行策略设计，研究大规模矢量数据的并行可视化方法[34]。

2.2基于消息传递的矢量数据简化算法

基于消息传递的矢量数据简化方式主要采用MPI(Message Passing Interface)[35]并行的方式，基于MPI并行简化的优点是程序移植性好、扩展性高，缺点是开发人员需要控制计算任务的分配与传输，并行实现成本较高。沈婕等基于消息传递方式，采用多种简化方式，对等高线简化的适宜性进行研究，构建基于MPI的等高线并行简化处理过程，论述数据的分发及合并、通信方式与计算过程3个重要问题[36]。

2.3基于数据并行方式的矢量数据简化算法

数据并行即通过对数据的分区，在每个区域内同时执行相同的操作，以完成并行处理的目的[37]。由于这种并行方式需要从数据的本身划分出发，需要考虑划分的均衡性和一致性，大部分数据不适用于这种方式并行实现，因此，相关研究较少。张栋海等利用MapReduce在计算机集群上进行Douglas-Peuker算法的并行实验，算法的核心是数据的划分，通过MapReduce将划分的结果分配到集群的各个节点上。该研究得出，在大数据量、高复杂度情况下利用集群并行简化效率更高[38]。

3矢量数据简化的未来发展方向探讨

3.1矢量数据简化的实时性和实效性不断提高

矢量数据简化中的实时性和实效性是矢量数据可视化优劣的一个重要指标[39-40]。随着数据采集能力的日渐提高，数据量日益增大。对矢量数据可视化对科学研究和工程应用尤为重要[41]。并行技术与矢量数据简化的结合，不仅体现在简化过程的并行，而且还体现在数据输入、处理和输出的并行[34]。通过对并行模式下矢量数据简化的研究，极大地提高了矢量数据可视化的质量与效率，基于并行技术的矢量数据简化难点在于合理、高效的并行方案的设计与实现。基于并行计算的矢量数据简化是矢量数据简化实时性和实效性提高的突破口和途径。

3.2矢量数据的简化与综合向一体化方向发展

矢量数据综合是指根据表达的详细程度，恰当地舍弃不重要的元素，保留重要元素的过程[42]。矢量数据的简化、综合要以数据表现的尺度而定，对不同比例尺下的简化，简化模型要与综合模型相适应，达到简化与综合一体化的表达空间数据的效果，解决这个问题的关键在于研制健全的、多尺度的、基于语义信息和拓扑信息的简化模型，使其不仅能够由复杂数据得到分层次的简化数据，而且能够由简化数据还原回的多层次的较复杂数据，同时，还应探究矢量数据综合程度与简化程度之间的关系。

3.3矢量数据的简化更加智能化、感知化

矢量数据的简化向更加智能化、感知化方向发展[43]，该趋势与机器学习、人工智能、模式识别等学科关系密切。一方面，让计算机根据语义信息、尺度信息、拓扑信息等，判定简化的程度，再根据语义信息、空间信息、拓扑信息等的变化，以满足人类视觉认知需要为出发点，实时地改变简化尺度，这种简化尺度的变化是线性或非线性的。另一方面，采用机器学习和模式识别的方式，将每个线状要素智能化、可认知化，通过对用户使用信息的学习，得到线状要素对象本身的简化经验参数，将经验参数参与到简化中，得到更好的简化效果，这种经验参数包括从简化质量检查中得到的经验(包括错误元素序号、位置、错误元素节点序号、错误类型等)，将简化结果以一种打分的定量化形式，被线性实体所学习，在下一次的简化过程中，这些经验成为约束条件，控制错误的发生。

这种智能感知的简化方式可以应用在未来的无人驾驶和无人机监测等领域中[44]。如在无人驾驶研究中，控制智能汽车通过传感器[45]获知道路实时信息，这些初始获得的数据是栅格形式的，而智能汽车决策行使路线时，基于矢量的线性数据，由栅格数据提取矢量道路特征。而从栅格数据中得到的矢量道路数据复杂度高，包括多个节点、拐点，为满足决策效率的需要，需将这些矢量数据简化，此时，基于智能感知的简化是必不可少的，这种简化需要根据智能汽车对道路实际空间的认知以及已经积累的经验来协同、实时地完成。

4结论

矢量数据简化的效率与数据拓扑关系之间的矛盾。当前，矢量数据的简化大都只考虑矢量数据集的每个个体元素[46]，从个体角度出发，进行个体元素的简化，而没有考虑矢量数据个体间的拓扑关系，但若考虑个体间拓扑的保持，则会导致简化过程较多时间的开销，影响简化效率。这就需要在简化效率与要素间拓扑保持方面寻求平衡，即如何在简化效率影响不大的情况下尽可能地保持要素间的拓扑关系，解决这个问题，需从算法本身和硬件两方面着手，算法本身来说，研制更加高效合理的简化算法；硬件角度来说，利用多核计算机及计算机集群，采用并行计算的模式加以解决。

虽然很多学者对矢量数据的简化已经研究多年，但还不能彻底提出一个适用于各种类型的矢量数据的简化方法，原因如下：

1)数据的复杂性与多样性：矢量数据的空间拓扑关系异常复杂，如多条矢量数据相交、两个地物的多个部分相交等，而这种现象在各种类型的矢量数据中是非常常见的，如立交桥的矢量数据等。

2)受计算机发展及应用水平的限制：虽然并行技术已经相对较成熟，但该技术实现的难度较大，如需要考虑I/O均衡、负载均衡等，缺少一种更加方便的技术模式来支持并行技术在矢量数据简化方面的应用。需要研究一种支持串行与并行兼容的数据结构，减少数据通信时时间的开销，该数据结构需满足低冗余和低数据复杂性，且该数据结构能满足多层次、实时性和易于计算机认知的需要。

参考文献：

[1]龚健雅.地理信息系统基础[M].北京：科学出版社，2001.

[2]Goodchild M F.Geographical information science[J].International Journal of Geographical Information Systems，1992，6(1):31-45.

[3]Zhang L，Zhang L，Ren Y，et al.Transmission and visualization of large geographical maps[J].ISPRS Journal of Photogrammetry and Remote Sensing，2011，66(1):73-80.

[4]陈国良．并行算法的设计与分析[M]．北京：高等教育出版社，2002.

[5]Douglas D H，Peucker T K.Algorithms for the reduction of thenumber of points required to rep resent a digitized line or itscaricature[J].The Canadian Cartographer，1973，10(2):112-122.

[6]Zhan H S,Li G X.Progressive transmission of vectormap data basedon polygonal chain simplification[J].Lecture Notes in ComputerScience，2006，4282:908-917.

[7]GUIBAS L J，HERSHBERGER J，MITCHELL J，etal．Approximating polygons and subdivisions with minimum linkpaths[J]．Lecture Notes in Computer Science，1993，3：383—415.

[8]Saalfeld A.Topologically consistent line simplification with the Douglas-Peuckeralgorithm[J].Cartography and Geographic Information Science，1999，26(1):7-18.

[9]Mustafa N，Krishnan S，Varadhan G，etal. Dynamic simplification and visualization of large maps[J].International Journal of Geographical Information Science，2006，20(3):273-302.

[10] Li Z，Openshaw S.Algorithms for automated line generalization based on a natural principle of objective generalization[J].International Journal of Geographical Information Systems，1992，6(5):373-389.

[11] 朱鲲鹏，武芳，王辉连，等.Li-Openshaw算法的改进与评价[J].测绘学报，2007，36(4):450-456.

[12] Raposo P.Scale-specific automated line simplification by vertex clustering on a hexagonal tessellation[J].Cartography and Geographic Information Science，2013 (ahead-of-print):1-17.

[13] 郭庆胜.线状要素图形综合的渐进方法研究[J].武汉测绘科技大学学报，1998，23(1):52-56.

[14] Poorten P，Jones C B.Customisable line generalization using delaunay triangulation[C]//CD-Rom Proceedings of the 19th ICC，Ottawa，Section.1999，8.

[15] 艾廷华，郭仁忠，刘耀林.曲线弯曲深度层次结构的二叉树表达[J].测绘学报，2001，30(4):343-348.

[16] 杜维，艾廷华，徐峥.一种组合优化的多边形化简方法[J].武汉大学学报(信息科学版)，2004，29(6):548-550.

[17] 操震洲，李满春，程亮，等.适用于网络渐进传输的多分辨率曲线生成算法[J].计算机应用，2013，33(3):688-690.

[18] 崔锦泰，程正兴.小波分析导论[M].西安：西安交通大学出版社，1995.

[19] 吴纪桃,王桥.小波分析在 GIS 线状数据图形简化中的应用研究[J].测绘学报，2000，29(1):71-75.

[20] 吴纪桃,王桥.小波理论用于地图数据处理中若干理论问题的探讨[J].测绘学报，2002，31(3):245-248.

[21] SAUX E.B-spline functions and wavelets for cartographic line generalization[J].Cartography and geographic information science，2003，30(1):33-50.

[22] MALLAT S G.A theory for multiresolution signal decomposition:the wavelet representation[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，1989，11(7):674-693.

[23] 吴凡.基于小波分析的线状特征数据无级表达[J].武汉大学学报(信息科学版)，2004，29(6):488-491.

[24] 朱长青，王玉海，李清泉，等.基于小波分析的等高线数据压缩模型[J].中国图像图形学报，2004，9(7)：841-845.

[25] 王玉海，朱长青.基于小波分析的线状要素压缩优化的综合性研究[J].武汉大学学报(信息科学版)，2007，32(7):630-632.

[26] 王明常，谷兰英，王宇，等.小波变换理论的线状要素制图综合研究[J].吉林大学学报(地球科学版)，2005(S1).

[27] 史文中.空间数据与空间分析不确定性原理[M].北京：科学出版社，2005.

[28] 武芳，朱鲲鹏.线要素化简算法几何精度评估[J].武汉大学学报(信息科学版)，2008，33(6):600-603.

[29] 刘鹏程，罗静，艾廷华，等.基于线要素综合的形状相似性评价模型[J].武汉大学学报(信息科学版)，2012，37(1):114-117.

[30] WEIBEL R.Generalization of spatial data:Principles and selected algorithms[M]//Algorithmic foundations of geographic information systems.Springer Berlin Heidelberg，1997:99-152.

[31] 朱鲲鹏，武芳，陈波，等.基于约束条件的线要素化简算法质量评估[J].测绘科学，2007,32(3):28-30.

[32] 安虹，陈崚.并行算法实践[M].北京：高等教育出版社，2004.

[33] 马劲松，沈婕，徐寿成.利用 Douglas-Peucker并行算法在多核处理器上实时综合地图线要素[J].武汉大学学报(信息科学版)，2011，36(12):1423-1426.

[34] 张立强，徐翔，谭继强.基于并行技术的大规模矢量地图可视化方法[J].地理与地理信息科学，2013，29(4):9-12.

[35] 张武生，薛巍，李建江，等.MPI并行程序设计实例教程[M].北京：清华大学出版社，2009.

[36] 沈婕，郭立帅，朱伟，等.消息传递接口环境下等高线简化并行计算适宜性研究[J].测绘学报，2013，42(4):621-628.

[37] LIN C，SNYDER L.Principles of parallel programming[M].Addison-Wesley Publishing Company，2008.

[38] 张栋海，黄丽娜，刘晖，等.基于MapReduce的多机并行 DP 算法与实验分析[J].地球信息科学学报，2013(1):55-60.

[39] CORCORAN P，MOONEY P，WINSTANLEY A.Planar and non-planar topologically consistent vector map simplification[J].International Journal of Geographical Information Science，2011，25(10):1659-1680.

[40] YANG B，PURVES R，WEIBEL R.Efficient transmission of vector data over the Internet[J].International Journal of Geographical Information Science，2007，21(2):215-237.

[42] 毋河海.地图综合基础理论与技术方法研究[M].北京：测绘出版社，2004.

[43] 王家耀.地图制图学与地理信息工程学科发展趋势[J].测绘学报，2010，39(2):115-119.

[44] BISHOP C M，NASRABADI N M.Pattern recognition and machine learning[M].New York:springer，2006.

[45] 李德仁，龚健雅，邵振峰.从数字地球到智慧地球[J].武汉大学学报(信息科学版)，2010(2):127-132.

[46] 温永宁，闾囯年，陈旻.矢量空间数据渐进传输研究进展[J].地理与地理信息科学，2011，27(6):6-12.

[47] 姚静.基于ArGIS的大比例尺矢量电子地图制图研究[J].测绘与空间地理信息，2015,38(6)：135-136.

[48] 周琛，陈振杰，黄秋昊，等.多核并行环境中矢量数据格式的转换算法[J].测绘科学，2015，40(7)：118-122+130.

[责任编辑：李铭娜]

An overview of vector map data simplification researchZHANG Zhenxin1，ZHANG Wei2，LIU Bin3，KOU Yidan1，DENG Hao2

(1.State Key Laboratory of Remote Sensing Science，School of Geography，Beijing Normal University，Beijing 100875,China;2.School of Geosciences and Info-Physics，Central SouthUniversity，Changsha 410083,China;3.School of Information Science and Engineering,Central South University,Changsha 410083,China)

Abstract：Vector data simplification is an important content of its visualization.In this paper，the traditional vector data simplification algorithms and paralleled vector data simplification algorithms are analyzed，and the present traditional vector data algorithms include:Douglas-Peukersimplification algorithm and its evolutionary，Li-OpenShawsimplification algorithm and its evolution，progressive simplification and its evolution，and wavelet-based theory and its evolution and simplification quality value.Based on parallel simplification algorithm，it points out that the parallel simplification and intelligence，perception，and automation of simplification are the tendency of vector data simplification development.

Key words：vector data；simplification；algorithm；parallel

中图分类号：P283；P208

文献标识码：A

文章编号：1006-7949(2016)06-0010-05

作者简介：张振鑫(1986-)，男，博士研究生.

基金项目：国家自然科学基金资助项目(41401532)

收稿日期：2015-03-27；修回日期：2015-08-04