基于ε-voronoi图的矢量数据自适应简化方法-张振鑫.pdf

《基于ε-voronoi图的矢量数据自适应简化方法-张振鑫.pdf》由会员分享，可在线阅读，更多相关《基于ε-voronoi图的矢量数据自适应简化方法-张振鑫.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第32卷第1期2016年1月地理与地理信息科学Geography and Geo-Information ScienceV0132 No1January 2016doi：103S6sjissn1672一0504201601006基于一Voronoi图的矢量数据自适应简化方法张振鑫1，邓浩2，寇一丹1，张维2，刘嫔3(1北京师范大学地理学与遥感科学学院遥感科学国家重点实验室，北京100875；2中南大学地球科学与信息物理学院，湖南长沙410083；3中南大学信息科学与工程学院，湖南长沙410083)摘要：针对矢量数据简化的问题，提出一种基于帧缓存和四叉树索引的自适应简化方法，即采用四叉树索引对矢

2、量数据进行区域划分，通过评价各个区域地物实体分布密度的指标，判断各个区域内的矢量数据密度、图幅宽度，得到各区域e-Voronoi图中的e值，再借助帧缓存技术，自适应地简化各个区域内的矢量数据。实验表明，该方法一定程度上提高了简化质量，为矢量数据可视化应用提供一定的基础。关键词：四叉树；帧缓存；自适应；简化中图分类号：P283；P208 文献标识码：A 文章编号：1672一0504(2016)010029一050引言随着硬件平台及相关技术的发展，人们获取空间数据的能力急剧增长，甚至超出计算机存储能力的增长速度。这些数据包含大量的空间矢量数据，对矢量数据的可视化是矢量数据应用的一个重要方面口，矢量

3、数据简化又是空间数据可视化研究的重要内容。矢量数据简化研究源于Douglas与Peuker提出的DouglaS-Peuker折线简化法2|，该方法效率较高，且可保持线要素的重要几何特征，但在简化过程中会导致拓扑关系发生改变，造成简化后的线要素可能出现自相交等拓扑关系不一致错误3。Guibas等4证明：在避免自相交的情况下，保留尽可能少的点是一个NP-hard问题。Estkowskic5等在Douglas-Peuker算法的基础上，采用“绕远之路(detour)”的方式避免简化后的自相交，该算法的时间复杂度最高为0(以3)，且运行速度较慢；Yang等61采用VisvalingamWhyattt算

4、法，并结合约束条件的限制，避免了简化后的自相交，时问复杂度为0(nlogn)，但多分辨率空间编码带有一定的冗余，影响了简化效率。文献7，8采用矢量数据顶点聚类的方式，即选出每个聚类中的一个点来代替每个聚类中的点，但该方法在避免简化后线段间的自相交方面仍显不足。Mustafa等9提出了一种基于eVoronoi图的简化方法，即通过模板深度缓存，将eVoronoi区域渲染到模板缓存中，再通过模板测试，剔除-Voronoi区域外的点，保证每个要素简化结果都位于eVoronoi区域中，定程度上可避免要素间的相交，但不能避免要素内部的自相交，因为每个矢量实体的值固定，该简化方法在灵活性和自适应性方面略有欠

5、缺，且没有考虑待简化区域地物分布密集程度对简化的影响。Yang等10通过引进单调链11I，提出了一种基于帧缓存和eVoronoi图的简化方法，通过剔除模板外不合规线段进行简化，一定程度上避免了简化后要素间的相交和每个要素内部的自相交，但该方法存在以下问题：1)e值灵活性不够，导致不同分布密度的矢量数据都在相同的值下简化，进而导致生成一Voronoi图较困难，甚至一些矢量地物的eVoronoi图将距离较近的其他矢量实体的eVoronoi图完全覆盖，导致简化结果出现拓扑错误；2)借助帧缓存剔除违规线段，当待简化的矢量数据数量较多时，一些矢量数据可能映射到较少甚至几个像素中，会导致剔除违规线段时出现

6、异常，简化结果出现拓扑错误。由于地物空间分布多样性及复杂性，亟须一种根据矢量地物分布疏密程度的自适应简化方法以提高简化质量。本文提出一种基于帧缓存和四叉树的矢量数据自适应简化方法，通过对矢量数据建立四叉树索引，对区域进行划分，在评价每个子区域矢量数据密集程度的基础上，确定每个叶子节点区域的e值，使每个叶子节点区域简化与该区域的矢量实体分布的密集程度相适应，提高简化质量。收稿日期：2015-03-20；修回日期：20151019基金项目：湖南省博士后科研资助专项计划(2014RS4028)；国家自然科学基金项目(41401532)作者简介：张振鑫(1986一)，男，博士研究生，从事空间信息可视化

7、算法研究。Email：zhenxin066163corn万方数据第30页 地理与地理信息科学 第32卷1矢量数据区域划分通过建立矢量数据的四又树索引进行区域划分。首先，设定四叉树叶子节点中矢量地物数目阈值，而后以每个矢量地物(polyline或polygon)的最小外包矩形(MBR)中心点为四叉树划分的基本点，进行四叉树区域划分。为更好地评价各个子区域的分布密度，需要保证每个叶子节点区域的范围一致，因此，本研究采用完全四叉树的方式进行区域划分。设每个叶子节点中实体数目的阈值为m，矢量数据完全四叉树构建的步骤如下：1)遍历矢量数据，统计位于各个子节点矢量数据MBR中心点的数量y。2)如果位于所有

8、子节点矢量数据的数目)，都小于m，则完全四叉树构建完毕；反之，四叉树深度增加，各个子节点分裂成4个新的子节点，重复执行步骤1)，直到所有子节点中矢量实体的数目都小于m，四叉树构建完毕，将对应的矢量实体划归到各个四叉树叶子节点中。图1是阈值为2的完全四叉树的区域划分结果。鉴黜 酒 匾 墨Sf 曩Ka坦 匝善 圈 烂f匿 L上： 艮k L煳K。KT】I点，外NW NE SW SE瓜爪瓜。瓜5 3 4 9 nJiiio 7 nj 8“1nli 2i 3 aul图1矢量数据的四叉树划分Fig1 Dividing the vector data by Quadtree2基于帧缓存简化21 矢量实体的毛-

9、Voronoi图定义ei-Voronoi图即具有距离约束条件i的Voronoi图，每个ei-Voronoi图内的点到其矢量数据对象的最小距离不大于e，值。设矢量数据集合G是由，z个矢量实体组成，即91，92，岛G，定义gi的eiVoronoi图(简称Ei-V(gi)为所有到蟹的距离不大于ei的点的集合，即eiV(臻)一P dist(P，gi)dist(P，g，)，dist(P，g：)ei，iJ，歹一1，2，r)，则G的iVoronoi图的集合为iV(G)一1一V(91)，e2一V(92)，。一V(g。)，如图2所示，s1、s2、3形成3条矢量地物实体的ei-Voronoi图的集合。22自适应参

10、数；值的计算本文的自适应简化方法是通过四叉树叶子区域的道路分布密度、叶子节点区域宽度和参数自适应地确定iVoronoi图中i值实现的，过程如下：图2 e，一Voronoi图不意n蛋2 qVoronoi珊蹿隋m首先，设计衡量各个叶子节点区域矢量数据密度(盯j)的方法：西一罢聂i1 其中：k：代表第i个叶子节点包含的所有矢量数据映射到帧缓存后各个矢量数据对应像素的数目总和；Si代表第i个叶子节点区域映射到帧缓存后该区域所覆盖的像素数目；惫拙是第i个叶子节点进一步四分后(图3虚线分割后的区域)各个子区域像素数目的最大值；是袖是第i个叶子节点四分后，子区域中地物投影到帧缓存后像素数目的最小值。-，i

11、奴j-,J彗j孓1图3叶子节点四分,-Ix意Fi0 Lear nodes of the quad-tree接着取各个nr子节点区域密度的最大值，再将每个叶子节点区域的密度与的比值作为每个叶子节点区域的相对密度艿i，即：aa堕m (2)这样，每个叶子节点中的各矢量元素的。值为：E，一菇diX口 (3)口表示提前设定的参数，d：是第i个叶子节点的图幅宽度。盈越大，表示地物越密集。图4是不同叶子节点下的矢量数据分布密度示意图。23矢量数据的简化矢量数据简化的步骤如下：将矢量数据进行完全四叉树索引构建，矢量数据区域被划分成各个叶子区域，计算各叶子节点的。值；遍历所有叶子节点，依次将各叶子节点的矢量数据

12、映射到帧缓存，依万方数据第1期 张振鑫等：基于e Voronoi图的矢量数据自适应简化方法 第31页矗墨一。一 蟹度潮 圃_ 翰霞图l 叶子节点矢量地物分布密度不意rig4 1l托density of vt凹曲tain吼dIkafI-ode据每个叶子节点的i值生成ej-Voronoi图，对各叶子节点执行以下步骤：1)单调链的生成。单调链的定义10如下：对于一条折线，存在一个方向，此方向用直线乙表示，使折线z满足：对于如上任意一条垂线与折线Z的交点至多有一个(图5)。将一条矢量线要素拆分成单调链，首先，需定义两个向量间的夹角，设两个向量分别为芗和茸，若此角由芗向虿逆时针旋转得到，则可直接定义为声

13、和茸的夹角。若此角由声向审顺时针旋转得到，则取其负值，故此角区间落入(-180。，180。对于一条矢量道路线要素z定义为z一(v0，u1，可2，Vn)。向量u一鬲和罚的夹角被定义为舅，所有边与U07)1夹角所成的序列为00，01，“，六一l，则00o。设一max(00，0l，六一1)、i。=min(岛，0l，六一1)，Chandru证明Z为单调的条件：当且仅当一180。，亦即只要满足一口(口180。)，所得的链是单调链，当一口时，在定点ui处打断此条线，就可得出一条单调链。再在ui处重新开始计算，重复上述步骤，直到最后一个定点。2)基于帧缓存的i-Voronoi图的构建。帧缓存包括颜色缓存、深

14、度缓存、模板缓存、积累缓存和多重采样缓存9。采用文献12中的Voronoi图绘制方法，在模板缓存里渲染I-Voronoi区域。该方法在深度缓存的帮助下，可以避免复杂的几何计算，迅速在模板缓存中绘制出。一图5单调链示意Fig5 Monotone chain diagramVoronoi图，并使每个单调链的e；-Voronoi区域具有区别于其他单调链的唯一一个模板缓存值。3)生成初始线段集。采用DouglasPeuker2算法生成初始线段集。首先，连接矢量数据的第一个顶点和最后一个顶点，生成第一条线段。然后，从第二个顶点到倒数第二的顶点中，选取到第一条线段距离最大的点，连接此顶点和第一个顶点，生成

15、第二条线段，连接此顶点和最后一个顶点，生成第三条线段。迭代求距第二条线段最大的点，并将此点分别与第二条线段的首末点相连。第三条线段也进行同样的迭代操作，迭代持续到线段的首末点中没有其他顶点为止。4)剔除违规线段，得到简化结果。线段完全位于ei-Voronoi区域，则称为合规线段，否则，称为违规线段(图6)。下面以单调链z。为例说明剔除违规线段的过程。设l，的ei-Voronoi区域模板缓存值为i，由步骤3)生成初始线段集后，将线段集中的各线段渲染到颜色缓存中，每条线段对应唯一颜色标识，同时，开启模板测试。由于z。的。一Voronoi区域内所有像素的模板值都为i，为了找到区域外的像素，设置当前测

16、试不等于i时，模板测试才能通过。合规线段完全位于ei-Voronoi区域内，故无法通过模板测试，不能被渲染；超出，一Voronoi区域的违规线段才能被渲染到颜色缓存中。线段集中所有线段被渲染完成后，读取颜色缓存，如果一像素的颜色存储值不为0，将该颜色对应的线段从线段集中剔除。完成该操作后，线段集中对应的线段都为合规线段。对每个单调链，连接线段集中的合规线段，得到最后的简化结果。连接步骤如下：从第一个顶点出发，在所有连接的线段中，寻找另一顶点距最远的线段，然后，连接和此顶点，再从此顶点开始，重复上述步骤，直到连接到最后一个顶点。最后，连接简化后的单调链，以得到最终简化后的线要素。图7为线要素的简

17、化过程。图6 rVoronoi图区域、合规线段(短虚线)和违规线段(长虚线)Fig6 sI一、oronoi diagram，compliance line and irregular line万方数据第32页 第32卷a J原要素 c_1)单凋链的FVi)r1l|oi区域 It最终简化结果(粗体黑线J图?线要素的简化过程Fig7 The pr日唧lmm of IiI硷object simplification3实验验证与分析31数据集表1是本研究所采用的数据集，该数据集的空间分布存在一定差异性，要素之间存在着较为复杂的拓扑几何关系。表1数据集Table l Datesets32与其他方法对比采

18、用本文方法得到简化结果，并与文献10的方法进行对比(图8、图9)。本文方法的四叉树阈值设为100，口初始值设为0005。本方法(图8b)与采用文献10的方法(图8c)得到的简化结果相比，更好地保持了简化前的拓扑关系，在文献10的方法下，一些较复杂区域的简化出现简化后相交的拓扑错误问题，本文方法可很好地保持原始数据的拓扑关系。对数据集2(图9a)，在立交桥区域，与文献10的方法(图9c)得到的结果相比，本文方法(图9b)能够更好地保持立交桥的原始形态特征及道路间的连通关系，得到更高质量的简化结果。注a为啜冈-I)、r分别为本丈方法剐文献m中，i、缁刮的J rji剐孔i】图8数据集l的简化结果及对

19、比Fig8 The r幅llIt aIld咖盯4，面s帅of simplification about dataset 1上述是从直观、可视的角度进行的对比，为了全面评价两种方法的简化结果，首先，对简化后的数据出现拓扑异常的情况进行说明，即简化后各个简化实体内部或实体间与简化前不一致，称之为异常。接着，对简化后矢量数据发生拓扑异常的实体数目和简化后的实体节点数目总和进行统计(表2)。从表2可以看出，本文方法分别对数据集1和数据集2简化后出现的拓扑异常实体数目为33和920，文献10的方法对数据集1和数据集2简化后出现的拓扑异常实体数目为420和3 370，本文方法在保持实体简化拓扑正确性方面有

20、明显优势；在简化后剩余节点数方面，本文方法对数据集1和数据集2简化后的实体节点数目总和分别为423 500和507 873，而文献10的方法对数据集1和数据集2简化后的实体节点数目总和分别为366 321和429 564，再结合图8b和图9b可以看出，本文方法简化后保留更多节点以避免发生拓扑异常。膏腻一图9数据集2的简化结果及对比Fig)he resull and comparison of simplification for dataset 2表2两种方法简化结果的统计对比Fable!Statistical c11nflpfirison of simplification results

21、usmg two metl0ds33算法效率本算法测试的硬件环境为：Intel Core i74770，cpu：34 GHz和8 G的RAM。软件环境：操万方数据第1期 张振鑫等：基于e-Voronoi图的矢量数据自适应简化方法 第33页作系统为32位的Windows 7，集成开发环境是Visual C+2010。对本方法的效率进行了测试，对数据集1的简化时间为143 S，数据集2的简化时间为119 S，以上测试是在单机串行的环境下进行的。34参数的敏感性测试算法测试采用两组参数，第一组：四叉树划分阈值分别为50、100、150、200，口为0005；第二组：四叉树划分阈值为100，a分别为0

22、003、0005、0007、0009。本次测试以简化后矢量数据拓扑的正确率为测试标准，这里，矢量数据出现简化拓扑错误有以下几种情况：简化前数据间相交，简化后不相交；简化前数据间不相交，简化后相交；简化前数据内部不相交，简化后相交；简化前数据内部相交，简化后不相交。从图10可以看出，当四叉树索引阈值为100时，得到较高的简化正确率，说明这两套数据在四叉树索引阈值是100时，简化效果较好。从图11可得，随着口值的增大，简化后具有正确拓扑关系的矢量数据逐渐减少，这是由于随着口值增加，Ei值随之增加，导致较少的线段被判断为违规线段，简化程度较大，出现简化后拓扑错误的矢量数据数目也随之增加。图10不同四

23、叉树划分阈值下的正确率测试Fig10 Accuracy rate test in differentthresholds of Quadtree construction图11不同a值下的正确率测试Fig1 1 Accuracy rate test in different a value4结论本研究基于矢量数据的完全四叉树索引构建子区域，提出了叶子节点子区域的数据分布密度评价指标，各个叶子节点区域根据各自的密度进行自适应简化，并通过与前人的方法对比可以看出，在简化质量上，本文方法有一定的提高，尤其是对空间分布差异较大的数据简化效果更好。后续工作将考虑采用并行方式，通过对并行简化框架的设计，将

24、本方法进行并行化实验，进一步提高简化效率。参考文献：E1GOODCI-IILD M E Geographical information SciJIntermtionaJounml of Geographical Information Systems，1992，6(1)：31-45E2DOUGLAS D HPEUCKER T K Algorithms for the reductionof the number of points required to rep resent a digitized line orits caricatureJThe Canadian Cartographe

25、r，1973，10(2)：1121223ZHAN H S，LI G)(Progressive transmission of vector map data based on polygonal chain simp lificationJLecture Notes inComputer Science，2006，4282：9089174GUIPAS L J，HERSHBERGER J，MITCHELL J，et a1Approximath polygons and subdivisions with minilTlUlTl link pathsJLee-ture Notes in Compu

26、terScience，1993(3)：383-4155ESTKOWSKI N，MITCHELL J s B sII】plj蛳ng a polygonal subdivision while keeping it simpleAPro碱s of the 17th ACMSymp0Sium on Computational GeometryC200140一49r6 YANG B，PURVES R，WE3EL R Efficient transmission of vectordata over the IntemetJInternational Journal of Geographical In

27、formation Science，2007，21(2)：2152377RAPOSO PScale-specific automated line simplification by vertex clustering on a hexagonal tessellationJCartography andGeographic Information Science，2013，40(5)：427-44383李进，马劲松，沈婕，等一种基于顶点聚类的线要素简化算法改进口测绘科学技术学报，2013，30(5)：525-5299MUSTAFA N，KRISHNAN S，VARADHAN G，et a1D

28、ynamicsimplification and visualization of large maps-JInternational Jour-nal of Geographical Information,Science，2006，20(3)：273-30210YAdG L，ZI-IAdG L，MA J，et aL Effident simplification of largevector maps rendered onto 3D landscapesJComputer Graphicsand Applications，I口院，2011，31(2)：142311 CHANDRU V，R

29、AJAN V T，swAMINATHAN R Monotonepieces of chainsJORSA Journal on Computing，1992，4(4)：439446123 HOFF III K E，KEYSER J，LIN M，et a1Fast computation ofgeneralized Voronoi diagrams using graphics hardwareAProceedings of the 26th Annual Conference on ComputerGraphics and Interactive TechniquescACM PressAdd

30、ison-Wesley Publishing Co，1999277286(下转第59页)万方数据第1期 沈忱等：基于FSFDP-BoV模型的遥感影像检索 第59页信息，2006，24：242614LOWg D GDistinctive image features from scale-invariant keypointsJInternational Journal of Computer Vision，2004，60(2)：9111015 MOLINIER M，LAAKSONEN J，HAME TDetecting man-made structures and changes in sa

31、tellite imagery with a contentbased information retrieval system built on self-organizingmapsJTransaction on Geosciences and Remote Sensing，2007，45(4)：86187416李士进，仇建斌，於慧基于视觉单词选择的高分辨率遥感影像飞机目标检测J数据采集与处理，2014，29(1)：60一65173 ZHONG s Efficient online spherical Kmeans clusteringAProcof the 2005 IEEE Intem

32、ational Joint Conference on Neural NetworksCMontrealCanada，20053180一318518BOLOVINOU A，PRATIKAKIS I，PERANTONIS SBag ofspatio-visual words for context inference in scene classification口Pattern Recognition，2013，46(3)：1039105319PHILBIN JScalable Object Retrieval in Very Large Image CollectionsDUniversit

33、y of Oxford，201020WANG J，WANG J，KE Q，et a1Fast approximate Kmeansvia cluster closuresAMultimedia Data Mining and AnalyticsMSpringer International Publishing，2015373-39521wU J，REHG J眦Beyond the Euclidean distance：Creating effective visual codebooks using the histogram intersection kernelJComputer Vis

34、ion IEEE International Conference on，2009，30(2)：630637223 ODONE F，BARLA A，VERRI八Building kernels from binary strings for image matchingJImage Processing，IEEETransactions on，2005，14(2)：16918023ZHENG Y T，ZHAO M，NI如S Y，et a1Visual synset：Towards ahigher-levd visual representationAComputer Vision and Pa

35、ttern Recognition，2008cCVPR 2008，20081-8Remote Sensing Image Retrieval Research Based on ESFDP-BoV ModeISHEN Chen，QI Kunlun，LIU Wenxuan，WU Huayi(State Key Laboratory of Information Engineering in Surveying，Mapping and Remote Sensing，Wuhan University，Wuhan 430079，China)Abstract：In order to improve th

36、e accuracy of retrieval of high-resolution remote sensing images，this paper proposes an improved Bag of Visual Wbrd(BoV)model based on clustering by Fast Search and Find of Density Peaks(RiFI)P)Taking theadvantages that the result of clustering by FSFDP is highly accurate and that the clustering par

37、ameters are easy to choose，thismodel enhances the stability and reliability of feature quantification in BovKey words：remote sensing images；retrieval；Bag of Visual words；density peaks clustering(上接第33页)An Adaptive Simplification Method on Vector Data Based on z-VoronoiZHANG Zhenxinl，DENG Ha02，KOU Yi

38、danl，ZHANG Wei2，LIU Bin3(1State Key Laboratory of Remote Sensing Science，School of Geography and RS，Beij ing Normal University，Beijing 100875；2School of Geosciences and Info-Physics，Central South University，Changsha 410083；3School of Information Science and Engineering，Central South University，Chang

39、sha 410083，China)Abstract：In this paper，all adaptive method that performs simplification of vector data using frame buffer and quadtree index ispresentedFirstly，indicators to evaluate vector data density are proposed，then the tolerance parameter(e)of e-Voronoi diagramis gotten by the vector data den

40、sity and width of each regionIn the end，the vector data is adaptively simplified with the technology of frame bufferThe result of experiment indicates that our method improves the quality of simplification quality，and provides some bases for visualization of vector dataKey words：quadtree；frame buffer；adaptive；simplification万方数据