1 引 言

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

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

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

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

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

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

地图符号中不仅包括简单折线和多边形，还包括圆弧、Bezier曲线等参数曲线。图 1(a)、(b)为两个示例点状地图符号。图 1(a)为由一组复杂参数曲线构成的风景区符号，图 1(b)为圆点符号。若圆点符号按照图元法来解构，则其由圆形和三角形构成。若圆点符号按照Truetype组织方式解析，由于TrueType数据结构中没有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可描述为

点击浏览公式

点击浏览公式

结合缓存技术和设计模式中的享元(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为扫描线经着色和反走样后得到的像素阵列。

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

点击浏览公式

点击浏览公式

定义符号化代价比I

点击浏览公式

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

点击浏览公式

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

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

分别在4种符号化类型下，以符号为例进行绘制。单一符号化绘制时，符号尺寸统一为3mm，颜色统一为红色，采用栅格缓存方法；着色符号化时，符号尺寸统一为3mm，符号颜色依据地震等级不同而设计为红、橙、黄3种颜色，采用扫描线缓存方法；等级符号化时，颜色统一为红色，依据地震等级，将符号尺寸分解为3个等级，符号尺寸分别为3mm、5mm、8mm，采用栅格缓存(每个等级一个栅格缓存)方法；比例符号化时，颜色统一为红色，符号尺寸从3～8mm变化，采用图形缓存方法。采用3个时间段的数据进行试验，每次试验进行10次，取符号化时间平均值。测试结果如表 1所示。

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

为进一步分析符号图形复杂程度对不同缓存方法的影响，选择如图 3所示方形符号(a)和ESRI ERS Operations SI符号库中的地震中心符号(b)来对比试验。符号尺寸统一设为3mm。采用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)中关于优化比与符号图形复杂度之间关系的分析。

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