一种视觉变量相似性驱动的点数据符号化过程模型

吴明光

南京师范大学虚拟地理环境教育部重点实验室,江苏南京 210023

一种视觉变量相似性驱动的点数据符号化过程模型

吴明光

南京师范大学虚拟地理环境教育部重点实验室,江苏南京 210023

首先分析了点数据符号化过程中的视觉变量相似性和绘制流程可重用性。在此基础上提出一种视觉变量相似性驱动的符号化过程模型。该模型将顺序型的地图符号化流程改变为符号化子过程可交叉共享的符号化流程。针对l/O密集的符号图形构造过程,提出图形缓存;针对计算密集的符号图形离散过程,提出扫描线缓存;针对像素操作密集的符号栅格化过程,提出栅格缓存。试验结果表明本文方法能够在保证绘制质量的前提下显著提高点数据的符号化效率。

视觉变量;相似性;地图符号;符号化;过程模型

1 引 言

符号化是空间信息可视化的主要方式。它可以对空间分布、时间过程、顺序等级以及关联、对比、趋势等空间信息进行图形表达,也可用于空间数据可视化检查、分析[1]。符号化是当前空间信息可视化的难点之一:符号化效率低下,影响矢量地图操作体验,难以支持数据量大的全景式地图应用[2]和高更新率的动态地图应用[3-5];符号化过程的I/O、计算、绘图代价高,限制了手机、PDA等设备(CPU低、内存小、电池供电能力弱和显示屏幕小)上矢量地图应用[6-7]。

文献[3]从减少像素采样点、压缩纹理和裁剪剔除扫描线3个方面进行绘制优化,设计了一种硬件加速的矢量图形绘制方法,有利于降低内存占用和减少图形计算。文献[8]采用逐个活性边排序来取代逐像素的扫描线过滤算法,提高绘制效率。文献[9]等基于边的生命周期来建立活性边表,取代逐扫描线建立活性边表,能够显著减少内存占用,提高绘制效率。地图绘制过程中,符号视觉变量使用与符号配置方法会引起地图符号矢量图形之间存在不同程度相似性(如:符号颜色不相同,但符号形状相同;符号尺寸不相同,但符号形状相同)。上述研究均针对通用矢量图形绘制,缺少针对地图符号视觉变量相似性的优化绘制方法。

文献[10]根据地图符号的构图方法,通过设计地图符号数据结构来避免冗余运算以提高地图符号化效率;文献[11]根据矢量数据栅格化过程中矢量、栅格数据结构各自的优势,设计了一种基于栅格技术的矢量数据符号化方法,能够显著提高符号化效率。上述研究均是针对单个地图符号的构图方法与数据结构特征来展开,尚没有顾及地图符号视觉变量之间相似性引起的符号绘制(子)过程的可复用性。

从符号化过程来看,文献[10—11]将符号栅格化过程作为一个黑盒来处理,不具体区分栅格化的子过程。文献[5—7]将视觉变量理论用于地图符号设计、地图符号感受等研究,没有将视觉变量与栅格化过程建立联系。本文将视觉变量引入符号栅格化过程,通过对4种符号化类型中的视觉变量相似性进行分析,将传统顺序型的地图符号化过程改变为符号化子过程可交叉引用的符号化过程,减少符号化代价,提高符号化效率。

2 点状符号绘制类型与视觉变量相似性分析

点状地图符号的主要视觉变量包括:形状、尺寸、方向、颜色[12-14]。点数据符号化方法可分为单一符号化、着色符号化、等级符号化以及比例符号化4种基本类型[15]。单一符号化用同一符号表示同一性质的地理对象,用不同位置的符号来反映该类对象的空间分布。主要包括形状、角度等视觉变量。着色符号化主要通过颜色这一视觉变量来定性区分地理对象的属性特征。等级符号化通过将属性进行分级划分,同一级别类的要素符号尺寸相同,用以表示同类要素之间相近,异类之间相离的属性差异。主要包括形状和尺寸等视觉变量。比例符号化则建立数据量表和符号尺寸之间的函数关系,不同属性值所对应的符号尺寸不同,通过符号大小这一视觉变量的变化,定量地表示地物的属性。

基于扫描线栅格化算法[16],支持反走样[3]的地图数据符号化流程可分为4个步骤:①图形构造,将地图符号中lineto、curveto等绘制指令和坐标数据构造成能够转换为栅格化器可以处理的图形结构;②图形变换,包括缩放、平移等坐标变换,描边、填充等图形变换以及端头、转角等样式处理,步骤①生成的不同图形结构经图形变换后得到与之对应的多边形;③扫描线生成,将步骤②得到的多边形,以栅格大小为扫描间隔,采用扫描线算法离散为水平方向分布的线段,扫描线生成实际上是对矢量图形进行离散的过程,扫描线是着色、反走样的基本单元;④栅格化,对步骤③生成的扫描线进行着色、反走样处理,完成图形栅格化。

地图符号中不仅包括简单折线和多边形,还包括圆弧、Bezier曲线等参数曲线。图1(a)、(b)为两个示例点状地图符号。图1(a)为由一组复杂参数曲线构成的风景区符号,图1(b)为圆点符号。若圆点符号按照图元法来解构,则其由圆形和三角形构成。若圆点符号按照Truetype组织方式解析,由于True Type数据结构中没有Stroke操作,圆点符号被组织为5个多边形采用非零缠绕数规则(none zero winding number rule)填充而成。由于TrueType中的图形单元不包括圆弧,符号中的圆弧由Bezier曲线拟合而成(图1(c))。在连续曲线的栅格化过程中,离散化本身涉及导数、三角函数等计算。为保证离散后参数曲线的光滑特征,离散后数据量显著增大。这两个方面的原因均会降低栅格化的效率。

图1 点状地图符号示例Fig.1 Sample of point symbols

由以上分析可见,符号化过程不仅涉及符号数据的频繁I/O操作,还涉及符号图形离散时的计算与栅格化时的像素操作。上述因素导致地图符号化效率不高,在海量空间数据和复杂图形符号情况下效率降低更为明显。

完整的地图符号化过程包括符号配置和栅格化两个环节。符号配置实现地理要素属性数据、空间数据与地图符号视觉变量之间的关联,栅格化将符号图形结合地理要素的空间位置进行栅格化处理。将n个点要素中,第i个要素的符号化代价记为S(i)。栅格化过程又分为图形构造、扫描线生成以及扫描线栅格化处理等。则对第i个点要素进行栅格化处理的代价C可描述为式中,WL、WS、WR分别为图形构造、扫描线生成和扫描线栅格化3个步骤的权重;CL、CS、CR分别为图形构造、扫描线生成和栅格化3个步骤的代价函数。包含n个点要素的数据集符号化的代价为

式中,K(i)表示第i个点要素栅格化的代价系数;CP为将栅格化结果整体输出的代价。基于第1节的分析,在点要素符号化的4种基本类型中,由于存在视觉变量相似的情况,使得栅格化过程中图形构造、扫描线生成以及扫描线栅格化等几个步骤存在大量重复且可共享的I/O、计算以及像素操作:单一符号化方法中,图形变换、扫描线生成及扫描线栅格化的操作完全一致;着色符号化方法中,所采用的符号相同,符号颜色视觉变量变化,其他视觉变量保持不变,图形构造、扫描线生成操作完全一致。若要素分类结果为同一组,则颜色视觉变量相同,扫描线栅格化操作也完全一致;等级符号化方法中,图形构造操作完全一致;比例符号化方法中,所采用的符号相同,符号尺寸视觉变量变化,其他视觉变量保持不变,图形构造操作完全一致。若地理要素符号属性分类结果为同一组,则尺寸视觉变量相同,扫描线生成操作完全一致。

3 视觉变量相似性驱动的点数据符号化过程模型

结合缓存技术和设计模式中的享元(Flyweight)模式[17],本文提出如图2所示的符号化过程模型:通过符号化过程中的视觉变量相似性分析,针对I/O密集的符号图形构造过程,提出图形缓存。针对计算密集的符号图形离散过程,提出扫描线缓存。针对像素操作密集的符号栅格化过程,提出栅格缓存。不同要素符号化过程中可以细粒度地共享符号图形构造、扫描线计算和扫描线栅格化操作,降低符号化代价,提高符号化效率。

图2 视觉变量相似性驱动的点数据符号化过程模型示意图Fig.2 A visual variable similarity-driven symbolization process model for point datasets

本文所提出的符号化过程模型依然包括图形构造、图形变换、扫描线生成以及扫描线栅格化4个步骤。不同之处在于:本文针对矢量数据符号过程中频繁出现的符号数据读取、扫描线生成以及扫描线栅格化3个过程,采用键值对(Key/ value pair)结构[18]构建3类缓存对象。首个要素符号化时,在全局范围内主动构建缓存对象。其他要素符号化时,直接引用共享对象,从而减少内存占用,避免重复的符号数据读取、扫描线计算与扫描线栅格化,降低符号化代价,提高绘制效率。本文采用键值对数据结构来构建3类缓存对象:

(1)图形缓存以符号编号作为键索引,以图形数据作为键值,可表示为Map〈sid,data〉,其中sid表示符号编码,data表示符号数据。借鉴PostScript语言[19]、SVG规范[20]中的图形描述机制,本文采用〈path,stroke,fill〉结构来描述符号数据。

(2)扫描线缓存以符号编号作为键索引,以该符号的扫描线集合作为键值,可表示为Map〈sid, scanlines〉,其中scanlines是符号图形经坐标变换、图形变换以及样式处理,再经扫描线算法处理得到扫描线的集合。

(3)栅格缓存以符号编号作为键索引,以该符号栅格化的结果作为键值,可表示为Map〈sid, image〉,其中image为扫描线经着色和反走样后得到的像素阵列。

位置不同点要素符号化过程均可共享同一个缓存对象,而这个缓存对象可随着地理要素坐标不同而出现在地图坐标系中的不同位置。符号化过程中仅引用而不直接存储和维护图形、扫描线和栅格缓存对象。每一个点要素符号化过程均指向同一个实例,这个实例位于共享对象的共享池中。原本顺序执行的地图栅格化过程,转变为可交叉引用的过程,能够最大限度地避免重复符号数据读取、图形变换、扫描线生成以及栅格化处理。在单一符号化类型中,图形构造、扫描线生成、扫描线栅格化等几个步骤完全一致。利用栅格缓存,在第二个要素符号化时无须再进行图形构造、扫描线生成和扫描线栅格化,而直接引用第一个要素符号化过程中主动形成的栅格缓存结果

单一符号化时,在不考虑栅格化结果整体输出的情况下

式(6)表明,单一符号化时,在不考虑栅格化结果整体输出代价的情况下,符号化效率与数据量、符号图形复杂程度无关。着色符号化中,图形构造、扫描线生成等步骤完全一致,可同时采用图形缓存和扫描线缓存方法;等级符号化中,图形构造步骤完全一致,可采用图形缓存。在同一等级范围内,图形构造、扫描线生成以及扫描线栅格化等步骤完全一致,可取得与单一符号化一致的优化效率;比例符号化中,图形构造、扫描线生成两个步骤重复,可采用图形缓存和扫描线缓存方法。

4 试验验证

选择1973年至2011年间全球范围内地震数据进行模型效率测试。采用ESRI ERS Operations SI符号库作为试验符号库。测试环境:IBM Thinkpad T410s,Inter(R)core(TM)i5 CPU,3 GB内存,Windows 7操作系统。

表1 符号化时间对比Tab.1 Symbolization times for the test datasets ms

对于试验数据,纵向来看,图形缓存方法能够有效减少地图符号数据的读入与图形构造时间,明显提高地图符号化效率,因此,比例符号化的效率要优于直接绘制。扫描线缓存方法能够有效避免对同一图形符号的多次扫描线生成,能够在图形缓存方法的基础上进一步提升绘制效率,因此,着色符号化的效率又优于比例符号化。栅格缓存方法能够在扫描线缓存方法的基础上进一步避免对扫描线的栅格化,能够再次提高栅格效率,因此,单一符号化的效率又优于着色符号化。等级符号化也采用栅格缓存,但是符号化过程中涉及多个栅格缓存的切换与管理,因此,等级符号化的效率要优于着色符号化,但略低于单一符号化。横向来看,随着数据量的增加,直接绘制与本文方法绘制的效率均下降,但是,本文绘制效率的下降幅度要远小于直接绘制。其主要原因是:直接绘制过程中,每个对象的绘制步骤是独立的,本文方法中的关键绘制过程可以交叉引用,可以避免大量的重复I/O、图形计算与像素操作。

为进一步分析符号图形复杂程度对不同缓存方法的影响,选择如图3所示方形符号(a)和ESRI ERS Operations SI符号库中的地震中心符号(b)来对比试验。符号尺寸统一设为3 mm。采用1973—2011年地震数据。符号化时间试验结果如图4所示。

图3 测试符号Fig.3 Tested samples for map symbols

图4 符号化时间对比Fig.4 Symbolization times for the sample symbols

相对(a)符号而言,(b)符号中包含多段Bezier曲线。由试验结果可知,扫描线缓存方法能够有效避免重复的Bezier曲线离散过程,在符号化效率上有明显提升。采用栅格缓存方法后两种符号的绘制时间非常相近。这一试验数据验证了式(6)中关于优化比与符号图形复杂度之间关系的分析。

5 结 论

地图绘制过程一般是直接引用GDI、Cairo等图形绘制接口,符号绘制的过程是一个黑盒,绘制代价与效率是当前地图制图的一个瓶颈问题。视觉变量理论引起了广泛的讨论,但主要还是应用在符号的构造方法、图形感受等方面。本文将符号绘制过程分解为图形构造、扫描线生成、扫描线栅格化等环节,试图通过符号化过程中的视觉变量相似性分析,实现绘制过程中各对象绘制流程的重用。本文从点符号视觉变量和符号化过程分析出发,提出一种包含图形缓存、扫描线缓存和栅格缓存方法的符号化过程模型。该模型允许在不同点要素符号化过程中可以细粒度地共享符号图形构造、扫描线计算和栅格化操作,从而将顺序型的地图符号化流程改变为符号化子过程可交叉引用的符号化流程,减少符号化代价,提高符号化效率。3种缓存方法均会带来额外的存储资源占用,但均在常用地图显示设备的资源配置范围内。试验表明:3种缓存方法均能够显著提高点数据符号化效率。图形缓存方法有利于减少符号数据I/O与图形构造,适用于内存较小的地图应用设备;扫描线缓存方法有利于减少复杂符号的扫描线生成,特别有利于绘制包含参数曲线的复杂图形符号,适用于低CPU计算能力的地图应用设备;栅格缓存方法能进一步减少扫描线的着色操作,适用于低CPU计算能力、低内存的地图应用设备。

[1] ROBINSON A C,PEZANOWSKI S,TROEDSON S.SymbolStore.org:A Web-based Platform for Sharing Map Symbols[J].Cartography and Geographic Information Science,2013,40(5):415-426.

[2] PAUL A,MICHAEL G.Geographic Information Systems and Science[M].New York:John Wiley and Sons Press,2001.[3] SWIEN TY O,ZH A NG M,REICH ENBACH ER T.Establishing a Neurocognition-based Taxonomy of Graphical Variables for Attention-guiding Geovisualisation[C]∥Proceedings of SPIE.Nanjing:SPIE,2007.

[4] NIVAN F,POCO J,VOHUY T.Visual Exploration ofBig Spatio-temporal Urban Data:A Study of New York City Taxi Trips[J].IEEE Transactions on Visualization and Computer Graphics,2013,19(12):2149-2158.

[5] ZHANG Chuanrong,LI Weidong.The Roles of Web Feature and Web Map Services in Real-time Geospatial Data Sharing for Time-critical Applications[J].Cartography and Geographic Information Science,2005,32(4): 269-297.

[6] MOLLER A T,STROM J.Graphics for the Masses:A Hardware Rasterization Architecture for Mobile Phones [J].ACM Transaction of Graphics,2003,22(3): 801-808.

[7] NOGUERA J M,SEGURA R J,OGAYAR C J.A Scalable Architecture for 3D Map Navigation on Mobile Devices [J].Personal and Ubiquitous Computing,2013,17(7): 1487-1502.

[8] KILHYUNG C,DAEWOONG K,SOO-LK C.An Optimized Rendering Algorithm for Hardware Implementation of Open VG 2D Vector Graphics[C]∥Proceedings of SoC Design Conference.Busan:[s.n.],1995:338-341.

[9] DAEWOONG K,KILH YUNG C,SOO-LK C A Highperformance Open VG Accelerator with Dual-scanline Filling Rendering[J].IEEE Transactions on Consume Electron,2008,54(3):1303-1311.

[10] WU Xiaofang,DU Qingyun,XU Zhiyong.Design and Algorithm Optimization of Complex Linear Symbol[J].Geomatics and Information Science of Wuhan University, 2006,31(7):623-635.(吴小芳,杜清运,徐智勇.复杂线状符号的设计及优化算法研究[J].武汉大学学报:信息科学版,2006,31(7):623-635.)

[11] CAI Xianhua,WU Li.Study of Symbol Library Data Structure and Algorithm Based on Property Unit[J].Acta Geodaetica et Cartographica Sinica,2004,33(3):269-273.(蔡先华,武利.基于特征元的符号库数据结构及算法探讨[J].测绘学报,2004,33(3):269-273.)

[12] COMENETZ J.Cognitive Geometry for Cartography[J].Cartographic Journal,2002,39(1):65-77.

[13] BERTIN J.Semiology of Graphics:Diagrams,Networks, Maps[M].Madison:University of Wisconsin Press,1983.[14] CAO Yani,JIANG Nan,ZHANG Yajun,et al.Constitution Variables and Generation Modes of Electronic Map Symbols[J].Acta Geodaetica et Cartographica Sinica, 2012,41(5):784-490.(曹亚妮,江南,张亚军,等.电子地图符号构成变量及其生成模式[J].测绘学报,2012, 41(5):784-490.)

[15] MACEACHREN A M.How Maps Work:Representation, Visualization,and Design[M].New York:The Guilford Press,1995.

[16] RICE D.Open VG Specification Version 1.0.1[EB/OL].[2006-01-26].http:∥www.khronos.org/files/openvgquick-reference-card.pdf.

[17] GAMMA E,HELM R,JOHNSON R.Design Patterns: Elements of Reusable Object-oriented Software[M].Boston:Addison-Wesley,1995.

[18] BLACK P E.Entry for Data Structure in Dictionary of Algorithms and Data Structures[EB/OL].[2009-05-21].http:∥xlinux.nist.gov/dads/.

[19] Adobe Systems Inc.PostScript Language Reference Manual [M].Boston:Addison-Wesley,1999.

[20] W3C Recommendation.Scalable Vector Graphics(SVG) Full 1.2 Specification[EB/OL].[2010-07-01].http:∥www.w3.org/TR/SVG12.

(责任编辑:宋启凡)

A Visual Variable Similarity-driven Symbolization Process Model for Point Datasets

WU Mingguang
Key Laboratory of Virtual Geographic Environment of Ministry of Education,Nanjing Normal University,Nanjing 210023,China

The visual variable similarity and drawing process reusability was analyzed in the process of point data symbolization.Then,a symbolic process model driven by visual variable similarity was proposed.Compared with the sequential symbolization process,the subprocess of symbolization could be shared in this model.For l/O-intensive symbol graphical construction process,graphic cache was proposed.For compute-intensive symbol graphical discretization process,scan line cache was proposed.For pixel-operation-intensive symbol rasterization process,raster cache was proposed.Under the precondition that drawing quality is ensured,the experimental results show that the method presented can significantly improve the symbolic efficiency for point datasets.

visual variable;similarity;map symbol;symbolization;process model

P283

A

1001-1595(2014)11-1274-06

国家自然科学基金(41271446)

2013-12-16

吴明光(1979—),男,副教授,主要研究方向为空间数据模型、空间信息可视化、空间信息服务。

WU Mingguang.A Visual Variable Similarity-driven Symbolization Process Model for Point Datasets[J].Acta Geodaetica et Cartographica Sinica,2014,43(11):1274-1279.(吴明光.一种视觉变量相似性驱动的点数据符号化过程模型[J].测绘学报,2014,43 (11):1274-1279.)

10.13485/j.cnki.11-2089.2014.0185

修回日期:2014-03-24

Author:WU Mingguang(1979—),male,associate professor,majors in spatial data model,spatial information visualization and spatial information service.

E-mail:wmg＠njnu.edu.cn