1 引 言
化简是地图综合的一类基本算法，现有的大部分化简算法是针对线要素提出的[1]。线要素化简算法很多，依据化简的约束范围和类型，线要素化简算法可以分为5类：① 无约束类，如第N点选取法；② 局部约束类，如文献[2]提出的弧比弦化简算法和文献[3]提出的垂比弦化简算法；③ 扩展局部无约束类，如文献[4]提出的RW带状选点法和文献[5]提出的ZS袖子选点法；④ 扩展局部约束类，如文献[6]提出的约束带状选点法和文献[7]提出的Lang化简法；⑤ 全局约束类，如文献[8]提出的DP化简算法和文献[9]提出的面积化简法。结合制图学要求，线要素化简是在尽量保持线要素节点位置精度、几何形态结构与地理分布特征的前提下，尽可能多地剔除线要素上冗余或次要的节点，减少线要素的数据存储量[10]。因此，位置精度和形态结构特征保持是线要素化简算法的设计和需要考虑的重要因素。
近年来，地图综合算法评价已受到广泛关注[11]。现有地图要素化简算法评价指标大多通过对比化简前后地图要素的位移和变形或者对比算法的时间与空间效率来建立[12]。然而，地图作为空间信息的图形语言，是地理空间信息的载体和传递工具，这亦表明地图综合的过程实质上是地理空间信息的传递过程[13]。因此，从信息传递能力的角度评价地图综合算法符合地图制图内在需要。为此，本文以线要素化简为例，从信息传递的角度，研究建立基于层次信息量传递比的线要素化简算法定量评价指标。
对于线要素化简算法评价的研究有很多，并且亦建立了一些定量评价指标。其中具有代表性的有文献[14]提出的矢量位移和面积偏差指标，这两个指标通过量化化简产生的位移而建立，是现阶段应用最为广泛的评价指标。文献[12]从曲线位置不确定性角度研究并提出了线要素化简算法的质量评估方法。文献[15]建立了线要素化简算法评价的分形指标，并基于分形理论对DEM进行了精度评估。文献[16]研究了线要素化简算法的误差传递模型，从几何精度、空间关系、结构形态和适用范围4个方面评价线要素化简算法，提出了基于约束条件的评估方法[17, 18]。文献[19]引入线要素形状描述子，进而建立了基于形状相似度的线要素综合算法评价指标。
分析可以发现，现有线要素化简算法评价指标要么侧重其局部的位置精度，要么侧重线要素整体形态结构描述。过分强调局部位置精度可能导致线要素基本结构失真，而强调整体形态结构特征描述则无法保证算法在局部形态保真方面的性能，因此，分别从这两方面建立的评价指标难以准确全面地评价线要素化简算法的性能。例如，在一些情况下用户可能更关注化简算法在线要素整体结构和走势方面的保持能力，而在另一些情况下用户更关注某些关键点或者关键弯曲的保持能力，现有评价指标难以解决这些问题。
2.2 本文研究策略从信息传递的角度，线要素化简可以视为从较大比例尺地图到较小比例尺地图的线要素信息传递过程。鉴于此，线要素化简算法的评价一方面要平衡视觉差异、几何变形、算法效率等的优化，另一方面也要兼顾线要素空间特征的保持能力。为此，本文从地图信息传递的角度，首先采取层次策略将线要素信息划分为元素、邻域、整体3个层次，其中元素层次信息量对应节点重要性程度，邻域层次信息量对应局部弯曲形态，而整体层次信息量对应线密度。进而，建立各个层次空间特征定量描述指标，并采用基于特征的信息量计算模型计算得到各个层次的信息量。在此基础上，建立线要素化简算法在各个层次信息量的保持能力评价指标。其中，元素层次节点信息量保持能力用于对应算法的关键点选取能力；邻域层次弯曲信息量保持能力对应局部弯曲形状保持能力；整体层次线密度信息量对应线要素整体结构保持能力。具体研究策略如图 1所示。
|
| 图 1 线要素化简算法的层次信息量评价指标 Fig. 1 Performance evaluation method of line simplification algorithms based on hierarchical information content |
地图信息产生的本质特征是要素及其分布特征的多样性与差异性[20]，而地图信息量大小则由这种多样性和差异性程度决定。也就是说，地图上要素及其分布特征的多样性与差异性越大，则相应的信息量也越大，这与Shannon信息熵[21]在均衡状态下信息量最大具有相反的趋势。进而，建立基于特征的地图信息量计算模型[20, 22]，表达为
式中,wi为特征w上第i个标准化的定量描述值；Iw为由特征w产生的信息量；底数为2时信息量单位为bit。由于定量描述不同特征的指标的量纲和取值范围不同，为规范式(1)中信息量的计算，需要对特征描述值的量纲和取值范围进行规范化处理。首先，将其转化为无量纲量，常用的方法是用特征描述值除以特征描述值的最大值或平均值，从而得到的标准化特征定量描述值wi的无量纲量，且取值范围亦得以规范。这种情况下，不仅同类的信息量之间具有良好的可比性，同时相互独立的信息量分量具有可加性。
3.2 线要素层次信息的构成分析线要素的特征则由构成线要素的节点和弯曲以及线要素的整体形态反映。从地图要素描述的角度，不同的观察粒度下，构成线要素的几何结构单元不同。观察粒度较小时，可以发现线要素由有序节点依次连接而成；观察粒度较大时，可以发现线要素由一组有序的弯曲构成；而从整体上观察，一条线要素则对应一个地图要素独立的基本单元，其整体形态结构反映空间要素的整体特征。
从线要素信息量的角度，上述3个视角分别对应线要素的元素层次、邻域层次和整体层次的信息量。元素层次以节点为基本单元构成线要素，这个层次的线要素信息量由节点的空间特征决定，主要表现为单个的节点使线要素在一定范围内产生的曲折程度。邻域层次以弯曲为基本单元构成线要素，这个层次上线要素的信息量取决于弯曲的空间特征，主要表现为弯曲程度和弯曲大小。整体层次上线要素的信息量由线要素整体形态特征决定，主要表现为线要素的分布密度。分析可知，基于不同粒度层次对线要素的描述是完备的，并且所描述的空间特征亦不相同。因此，线要素在元素层次、邻域层次和整体层次上的信息量不相关，同时这种划分亦是对线要素信息量的一个完备划分和表达。下面分别探讨线要素3个层次信息量的度量方法，并分析各层次的信息量在线要素化简算法评价中的作用。
3.3 基于元素层次信息量的关键点保持能力评价在元素层次，线要素的信息量取决于构成线要素的节点在表达线要素整体形态上的重要性程度。重要性程度越大，则信息量越大。通过定量分析化简前后线要素元素层次信息量的传递状况，可以有效评价化简算法在节点选取中关键点的保持能力。
线要素上节点的重要性通常由该节点与和它相邻的两个节点间的关系决定。如图 2所示，A、B、C为线要素的节点，若删去点B，则弧ABC变成线段AC，由此可见，节点B的重要性取决于它与相邻节点A、C间的关系。于是，可以选取节点到相邻两节点连线的垂距与相邻两节点连线段长度的比值作为节点重要性程度的描述指标。考虑到线要素上的毛刺情形，本文在垂线弦长比的基础上引进支撑域，即以节点为中心、以相邻节点距离均值为半径的一个圆。若相邻节点连线段与支撑域有交点，则用此交点代替相邻节点参与弦长和垂距的计算。如图 2所示，虚线圆即为支撑域，A′、C′分别为支撑域与AB、CB的交点，D为过B点作A′C′垂线的垂足，计算BD与A′C′长度的比值，即可作为节点B的重要性程度值。
|
| 图 2 线要素节点重要性程度度量 Fig. 2 Importance measurement of the vertices of a linear feature |
对于线要素的一个节点pi，可以计算该节点的重要性程度Importance(pi)为
式中,n为线要素的节点个数；Vertical(pi)为节点pi到相邻两个节点(或替换点)连线间的垂线距离；Chord(pi)为其相邻两个节点(或替换点)连线的长度。对于每条线要素Lj，将Importance(pi)代入式(1)，则可以得到线要素元素层次信息量为
进而整个线组要素在元素层次的信息量可表达为
式中,m为线组中线要素条数。对比化简前后线要素元素层次信息量，即可评价化简算法关键点保持能力。
3.4 基于邻域层次信息量的弯曲几何形态保持能力评价在邻域层次，线要素的信息量取决于构成线要素的弯曲几何形态的差异性或多样性程度，弯曲几何形态差异性或多样性程度越大，线要素的信息量越大。通过定量分析化简前后线要素邻域层次信息量的传递状况，能有效评价化简算法的局部弯曲保持能力。
下面，首先基于拐点对线要素进行弯曲剖分[23]，得到线要素的弯曲序列。如图 3所示，线要素可剖分为一组有序弯曲的集合c1,c2,…,c5。常用的弯曲度量指标包括弯曲长度、弯曲底线宽度、弯曲面积、弯曲度等，这些指标主要用来描述和区分不同弯曲之间的形状和大小差异。对于一个弯曲ci，它的弯曲度主要用来度量弯曲的曲折程度。考虑到实际线要素不同弯曲的弯曲度可能存在较大差异，本文定义弯曲度为弯曲长度length(ci)与弯曲底线宽度width(ci)的比值，表达为
式中,f(ci)为弯曲ci的弯曲度，取值范围为(1，∞)。该指标的大小不随图形的缩放而改变，也就是说，如果两个弯曲形状相同，它们的弯曲度亦相同。因此，该指标不能区分存在大小差异的弯曲。本文使用另一个描述和区分弯曲大小差异的度量指标，即弯曲面积比，它是指一个弯曲的面积Areaci与线要素弯曲序列中最大弯曲面积max(Areaci)的比值，表达为
式中,r(ci)为弯曲ci的相对面积比值。进而，可以将线要素的弯曲表达为两个指标值序列，分别为弯曲度序列{f(c1),f(c2),...,f(cn)}和弯曲面积比序列{r(c1),r(c2),...,r(cn)}。于是，弯曲ci的信息量为
式中，HNL(ci)为线要素邻域层次弯曲ci的信息量。进而，线组要素邻域层次信息量表达为
式中,nj为第j个线要素的弯曲数量；m为线要素的条数。由此，对比线要素化简前后邻域层次的信息量，即可评价化简算法的局部弯曲保持能力。
|
| 图 3 基于拐点的线要素弯曲序列识别 Fig. 3 Identification of the bends of a linear feature based on inflection points |
在整体层次，线要素化简中整体走势保持能力可以通过分析整体层次的信息量来评价。地理学中，河川密度定义为单位流域面积上河流的长度[24]。类似的，定义线要素密度等于线要素的总长度除以线要素的缓冲区面积。化简过程中保留点数相当时，线要素密度越大，线要素的蜿蜒曲折越多，说明线要素整体走势保持越好。为此，本文采用线要素密度作为度量整体层次信息量的特征指标。缓冲区宽度的选取是线要素密度计算的关键问题。通过试验表明，选取3倍最小位移限差作为缓冲区宽度时，线要素密度计算结果稳定性较好。于是，下面使用3倍最小位移限差为缓冲区宽度，其中最小位移限差可以根据编图规范确定。进而，线要素密度Density(Li)可以表达为
式中，Length(Li)为线要素的长度；Area(Buffer(Li))为以3倍最小位移限差为宽度的线要素缓冲区面积。类似的，整体层次上线要素的信息量HWL表达为
式中，m为线要素的条数。由此，对比线要素化简前后在整体层次上的信息量，即可评价化简算法的整体形态保持能力。
综上所述，通过对比线要素化简前后在元素层次、邻域层次和整体层次的信息量变化则可进行线要素化简算法性能的评价。其中，通过对比元素层次信息量可以评价算法的关键点选取能力；通过对比邻域层次信息量可以评价算法的局部弯曲保持能力；通过对比整体层次信息量可以评价算法的整体走势保持能力。由此可见，信息量的评价指标能够从不同的视角全面地评价线要素化简算法的性能，与现有仅考虑局部位置偏差或者整体形态相似性描述的指标相比较，更具全面性、合理性和实用性。此外，信息量的计算并不复杂，仅需要通过基本的点集运算即可。
4 试验设计与结果分析本试验主要选取具有代表性的面积法、DP法、RW法和Lang法的化简为例进行算法评价，采用VS2008.net+ArcEngine9.3进行二次开发实现。为了测试层次信息量指标评价线要素化简算法的合理性和有效性，分别设计了两组试验。试验数据来源于我国西南部1∶100万河网水系数据，总流域面积250余万平方千米，包含18条河流线要素，总数据量为166 KB。
4.1 试验1：信息量评价指标合理性验证首先选取试验区一条河流线要素，分别采用上述4种化简算法对其进行不同程度的化简。该线要素化简前后线要素元素层次、邻域层次和整体层次的信息量的计算结果如图 4所示。化简到原始数据10%的数据量时与原始线要素叠加的效果如图 5所示，其中虚线表示原始线要素，实线表示化简后结果。
|
| 图 4 4种算法不同化简比例的评价指标计算结果 Fig. 4 Results of evaluation indicators obtained by four simplification algorithms under different simplification ratios |
|
| 图 5 不同算法对单条线化简到原始数据量10%的结果 Fig. 5 The results obtained by four simplification algorithms for an individual line with 10 percent of original data |
对照化简结果，结合4种化简算法的原理则可分析发现它们存在的不足，具体为：
(1) 面积法根据相邻的3个节点围成的面积来决定节点的取舍，这一方面使得化简算法在线要素的整体趋势上能有较好的保持，另一方面亦可能导致与相邻节点距离较近或张角较小的关键点被舍弃，同时局部弯曲也将被平滑。因此，采用面积法化简时可能导致关键点和弯曲的保持性能存在不足，如图 5(b)所示。
(2) Lang化简法以节点与化简段两端节点连线的垂直距离决定节点的取舍，将可能出现两个问题，一是选取节点对化简段的依赖性强，这将导致整体形态不能得到较好的保持；二是当化简段两端点连线与线要素本身相交时，处于化简段中间的关键点有可能被舍弃，当连续的关键点在这种情形下被舍弃时，局部弯曲也将被缩减。如图 5(d)所示，在关键点、局部弯曲和整体形态的保持性能都存在一定的不足。
(3) RW法根据起始两节点构建条带区域覆盖确定舍弃的节点，对于近起始端的张角敏感性较弱，而对于远端张角敏感性较强，取舍过程中对于关键点和局部弯曲的控制较弱。同时，该算法结果依赖于起始节点的确定。从图 5(e)可以看出，化简结果的关键点和局部弯曲保持性能较差，而整体形态保持性能最差。
(4) DP法逐次选取备选节点中垂直偏离最远的点，在一定程度上保证了每次迭代的节点都是最优选择，同时整体形态亦将得到很好的保持。不足之处是由于节点选取中没有参考局部形态，从而可能产生局部弯曲被掩埋的现象。从图 5(c)可以看出，DP法的关键点和整体形态保持性能比较优越，而局部弯曲保持性能略有不足。
对照图 4中4种算法化简结果在元素层次、邻域层次和整体层次上的信息量，可以看出计算结果与各种化简算法在关键点、局部弯曲和整体走势的保持能力方面是保持一致的。由此可见，本文提出的线要素3个层次的信息量评价指标是合理的。
4.2 试验2：信息量评价指标优越性验证第2组试验选取信息量评价结果较优的DP法和面积法对试验区域整个河网数据(数据量166KB)进行化简，并分别采用本文提出的信息量指标和现有的位移偏移均值和面积偏差值指标对化简结果进行评价,得到不同化简程度下各层次信息量评价指标值的折线图，如图 6所示。
|
| 图 6 两种算法不同化简程度的评价指标计算结果 Fig. 6 Results of evaluation indicators obtained by two simplification algorithms under different simplification |
从图 6中可以看出，两种化简算法中，线要素各层次的信息量随着化简比例增大而不断减小，化简程度越大，减小速度越快。在面积法中，由于边长或者垂距的增长都能带来相邻节点围成面积的增加，因而随着化简程度的增加，关键点、局部弯曲和整体走势保持能力下降速度增大，图 6中3个层次信息量指标下降趋势符合这一规律。然而，经典的矢量位移均值和面积偏差评价指标计算结果均随着化简程度的加剧而增大，其取值范围是不明确的，因而该评价指标与信息量这种有界指标相比，其参考价值较小。从图 6中还可以看出，在化简程度增加的过程中，面积偏差指标值出现负增长现象，这显然与化简过程相违背，即评价结果不够客观，而信息量评价指标不存在这种现象。
综上分析，层次信息量评价指标能够有效地评价线要素化简算法，并且相对经典评价指标具有优越性，同时亦能弥补现有指标普遍对线要素关键点、局部弯曲和整体走势保持能力评价的不足。
5 结 论鉴于地图具有载负信息和传递信息的基本功能，从地图要素信息量的角度来评价地图要素综合算法既有合理性，也存在必要性。本文遵循线要素化简原则，从信息传递的角度，提出了一组基于层次信息量的线要素化简算法评价的指标，并以水系河网数据为例进行了试验验证，发现基于层次信息量的评价指标在评价线要素的关键点、局部弯曲和形态保持能力方面具有优势。未来进一步的研究工作将集中在两个方面：一方面尝试利用层次信息量评价指标作为指导，发展线要素化简新算法；另一方面完善现有的地图综合评价指标体系，解决线要素化简算法的自动选取问题，以进一步实现线要素的自动综合。
| [1] | LI Z L. Algorithmic Foundation of Multi-Scale Spatial Representation [M]. Beijing:CRC Press, 2007:20-23. |
| [2] | NAKO B, MITTROPOULOS V. Local Length Ratio as a Measure of Critical Point Detection for Line Simplification [C]//The Symposium of the 5th ICA Workshop on Progress in Automated Map Generalization.[S.l.]:ICA, 2003:28-30. |
| [3] | TEH C, CHIN R. On the Detection of Dominant Points on Digital Curves [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 11(8): 859-872. |
| [4] | REUMANN K, WITKAM A. Optimizing Curve Segmentation in Computer Graphics [J]. Proceedings of International Computing Symposium, 1974(31): 467-472. |
| [5] | ZHAO Z, SAALFELD A. Linear-time Sleeve-fitting Polyline [J]. Auto Carto 13 ACSM/ASPRS’97 Technical Papers, 1997, 5: 214-223. |
| [6] | OPHEIM H. Fast Data Reduction of a Digitized Curve [J]. Geo-Processing, 1982, 2: 33-40. |
| [7] | LANG T. Rules for Robot Draughtsman [J]. Geographical Journal, 1969, 42(1): 50-51. |
| [8] | DOUGLAS D, PEUCKER T. Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature [J]. Canadian Cartographer, 1973, 10(5): 112-122. |
| [9] | VISVALINGAM M, WHYATT J. Line Generalization by Repeated Elimination of Points [J]. The Cartographic Journal, 1993, 30(7): 46-51. |
| [10] | WEIBEL R. Generalization of Spatial Data: Principles and Selected Algorithms [C]//Algorithmic Foundations of Geographic Information Systems. [S.l.]: Springer-Verlag,1997:99-152. |
| [11] | WU Fang, ZHU Kunpeng, DENG Hongyan. On Quality Analysis and Evaluating Criterion of Automatic Map Generalization[J]. Journal of Zhengzhou Institute of Surveying and Mapping, 2007, 24(3): 160-163. (武芳, 朱鲲鹏, 邓红艳. 地图自动综合质量分析与评价标准探析[J]. 测绘科学技术学报, 2007, 24(3): 160-163.) |
| [12] | SHI W Z, CHEUNG C K. Performance Evaluation of Line Simplification Algorithms for Vector Generalization [J]. The Cartographic Journal,2006, 43(5): 27-44. |
| [13] | DENG Min, XU Zhen, ZHAO Binbin,et al. A Transmission Model of Geometrical Information for Individual Spatial Objects in Cartographic Generalization [J]. Journal of Geo-Information Science, 2010, 12(5): 655-661. (邓敏, 徐震, 赵彬彬,等. 地图概括中空间目标几何信息传递模型研究[J]. 地球信息科学学报, 2010, 12(5): 655-661.) |
| [14] | WHITE E. Assessment of Line Generalization Algorithms Using Characteristics Points [J]. The American Cartographer, 1985, 12 (1): 17-27. |
| [15] | WANG Guangxia, CUI Kai, DAI Jun. The Accuracy Evaluation of DEM Based on Fractal Analysis [J]. Journal of Institute of Surveying and Mapping, 2005, 22(2): 107-109.(王光霞, 崔凯, 戴军. 基于分形的DEM精度评估[J]. 测绘学院学报, 2005, 22(2): 107-109.) |
| [16] | ZHU Kunpeng, WU Fang. Error Propagation Model of Linear Features’ Simplification Algorithms [J]. Geomatics and Information Science of Wuhan University, 2007, 32(10): 932-935.(朱鲲鹏, 武芳. 线要素化简算法的传递误差模型[J]. 武汉大学学报:信息科学版, 2007, 32(10): 932-935.) |
| [17] | CHEN Bo, ZHU Kunpeng, XUE Benxin. Quality Assessment of Linear Features Simplification Algorithms [J]. Journal of Zhengzhou Institute of Surveying and Mapping, 2007, 24(2): 121-124. (陈波, 朱鲲鹏, 薛本新. 线状要素化简算法的分析与评估[J]. 测绘科学技术学报. 2007, 24(2): 121-124.) |
| [18] | WU Fang, ZHU Kunpeng. Geometric Accuracy Assessment of Linear Features’ Simplification Algorithms[J]. Geomatics and Information Science of Wuhan University, 2008, 33(6): 600-603. (武芳, 朱鲲鹏. 线要素化简算法几何精度评估[J]. 武汉大学学报:信息科学版, 2008, 33(6): 600-603.) |
| [19] | LIU Pengcheng, LUO Jing, AI Tinghua, et al. Evaluation Model for Similarity Based on Curve Generalization [J]. Geomatics and Information Science of Wuhan University, 2012, 37(1): 114-117. (刘鹏程, 罗静, 艾廷华,等. 基于线要素综合的形状相似性评价模型[J]. 武汉大学学报:信息科学版, 2012, 37(1): 114-117.) |
| [20] | LIU Huimin, FAN Zide, DENG Min, et al. A Hierarchical Approach to Measuring the Information Content of the Contours in a Map [J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(5): 777-783. (刘慧敏, 樊子德, 邓敏,等. 地图上等高线信息度量的层次方法研究[J]. 测绘学报, 2012, 41(5): 777-783.) |
| [21] | SHANNON C E. A Mathematical Theory of Communication [J]. The Bell System Technical Journal, 1948, 27(1): 379-423. |
| [22] | WHELAN B M, MCBRATNEY A B. Prediction Uncertainty and Implications for Digital Map Resolution [C]//Proceedings of the Fourth International Conference on Precision Agriculture. Madison:[s.n.], 1998: 1185-1196. |
| [23] | GUO Qingsheng, HUANG Yuanlin, ZHANG Liping, et.al. The Method of Curve Bend Recognition [J]. Geomatics and Information Science of Wuhan University, 2008, 33(6): 596-599.(郭庆胜, 黄远林, 章莉萍,等. 线要素的弯曲识别方法研究[J]. 武汉大学学报:信息科学版, 2008, 33(6): 596-599.) |
| [24] | GREGORY E T, RAFAEL L B. Hillslope Processes, Drainage Density, and Landscape Morphology [J]. Water Resources Research, 1998, 34(10):2751-2764. |