基于形状特征点的改进道格拉斯—普克压缩算法

肖亚楠

【摘 要】 本文通过对传统的矢量数据压缩算法的分析发现，道格拉斯-普克压缩算法在处理复杂线要素时，存在错误删除特征点、存在自相交等问题；而垂距法则注重局部判断处理，没有从宏观角度对整体线要素进行分析处理。基于此对道格拉斯-普克压缩算法进行了改进，首先根据各顶点处的形状参数大小，提取特征点，然后以各特征点为分界点对线要素进行分段，最后使用道格拉斯普克算法对各分段进行处理。文中使用矢量数据对算法进行了验证，并与传统矢量压缩算法的处理结果进行了比较，发现改进后的算法在处理复杂线要素时具有更高的准确性。

【关键词】 矢量数据 数据压缩 道格拉斯-普克压缩算法 形状特征点

1 引言

地理数据的有效获取与处理，一直以来都是进行GIS工程建设以及地图制图的重要基础性工作，地理数据的数量以及处理质量将直接影响后续的数据分析与应用工作。

本文分析了传统矢量数据压缩算法的优缺点，融入了线要素形状特征的思想，对道格拉斯-普克算法进行了改进，并对改进后的算法进行了实验验证。

2 传统矢量数据压缩算法

矢量数据压缩是在保证信息量的前提下，尽可能的减少表达信息所需要的数据量。矢量数据压缩的方法一是降低数据精度，二是减少构成线要素的数据点。前者在精度要求较高的应用中不适用，后者常见算法有间隔点删除法、光栏法、垂距法，以及最为经典的道格拉斯-普克算法（Douglas-Peucker algorithm）。

间隔点删除法没有考虑各顶点之间的关系，仅按照间隔进行数据删除，精度保持效果较差；垂距法和光栏法均为局部算法，仅考虑局部顶点之间的位置关系，没有考虑到线要素的整体性，并且在数据量大的情况下，对精度的保持效果有所下降。

道格拉斯-普克算法综合考虑了线要素的整体特征，通过计算线要素各中间顶点到首尾顶点连线的距离，比较最大距离值与阈值的大小，若小于阈值，则删除所有中间点；若大于阈值，则以距离最大点为分界点，将线要素分割为前后两段。对分段后的线要素重复上述操作，直到线要素无法再分割为止。具体实现如图1所示。

道格拉斯-普克算法的原理简单、操作效率高，且从线要素整体入手，考虑了线要素的整体特性，利用特征点对线要素进行分段处理，在一定程度上同时兼顾了线要素的局部特征，在矢量数据压缩中有很强的可取性。但是在处理复杂线要素时，可能会出现自相交、线要素形状难以保持等情况，压缩效果不佳。

3 基于形状特征点的道格拉斯-普克压缩算法

3.1 曲率等形状参数及其相关概念

曲率用于衡量几何体的不平坦程度[2]。从数学角度上讲，曲率表示曲线偏离直线的程度，是曲线上某一点的切线方向角对弧长的转动率。通过微分定义，即W=dC/dL，其中W表示曲线上某一点的曲率，dC表示该点处切线与其临近点处切线的夹角，dL表示该点与其临近点间的弧长。

在矢量数据空间中，曲线由若干个顶点表示，无法使用一般意义上的曲率定义表示，本文参照数学定义，将Pi点处的转角和曲率分别定义为

C=arccos，公式（1）

W=C/L，公式（2）

其中，Pi-1、Pi+1分别为与Pi点相邻的前、后顶点，C为Pi点处的转角，W为Pi点处的曲率，L为、Pi-1、Pi、Pi+1间的弧长（即两线段总长）。曲率同时考虑了转角大小与对应弧段的长度，是曲线在某一点处弯曲程度的定量表示[3]，其值越大，表示曲线的弯曲程度越大。

弯曲度和顶点形状指数也是描述现状物体弯曲程度的重要参数。弯曲度为观测线长与两端点间距离的比值，即

Bi=Li/Si，公式（3）

公式（4）

Bi为曲线的弯曲度，Li为观测点到相邻两点间的距离和，Si為与观测点相邻的两点间距离[1]。Ji为观察顶点的形状指数，W为该点处转角。弯曲度越大，表示曲线性越好，反之则直线性越好；当顶点处的转角一定时，与其相邻的两端臂长越长，则形状指数越大，表示对区域范围内的曲线影响越大，也即形状贡献率越高。

3.2 形状特征点的提取

曲率等形状参数可以用来衡量图形局部变化程度，则形状特征点就是复杂图形局部变化剧烈的顶点，这些顶点在矢量数据压缩时应该保留。为了曲率特征点的提取过程如下：

1对线要素的构成顶点进行排序，并依次计算各顶点的曲率Wi、弯曲度Li及形状指数Ji，并计算其平均值Wc、Lc、Jc。

2从曲率、弯曲度、形状指数三个方面对顶点进行观察：首先将Wc作为曲率阈值，比较选定顶点曲率值与阈值的大小，若大于阈值，则保留该顶点；其次将Lc作为弯曲度阈值，比较选定顶点弯曲度值与阈值的大小，若大于阈值，则保留该顶点；最后将Jc作为形状指数的阈值，比较选定顶点形状指数与阈值的大小，若大于阈值，则保留该顶点。若曲率、弯曲度、形状指数均小于阈值，则舍弃该顶点。全部顶点处理完成后得到初步形状特征点集。

3提取的特征点中有变化微小的顶点，这些顶点的存在对于曲线形状的贡献不大，需要剔除。具体做法为：连接选定特征点的两相邻特征点，计算该特征点到该连线的距离，若大于阈值则保留；为避免数据压缩后出现自相交的情况，可以判断各特征点相邻顶点的连线与其后所有相邻顶点的连线的相交情况，如果相交，则需要保留该顶点；若以上条件均不符合，则移除该特征点。全部处理完成后得到最终的特征点集。

3.3 基于形状特征点的道格拉斯-普克算法

提取形状特征点的目的是为了保持复杂图形在数据压缩后的形状特征，并避免出现自相交现象。提取完成后，以特征点为分界点，将曲线分割成若干段，并对分割之后的曲线段依次进行道格拉斯-普克算法压缩处理，也即基于形状特征点的道格拉斯-普克算法。

4 实验结果分析

笔者在Visual Studio 2013平台上，使用C#语言对传统道格拉斯-普克算法以及基于形状特征点的道格拉斯-普克算法进行了对比实现，并在ArcGIS Desktop平台上采集矢量线数据作为试验数据，分别使用传统道格拉斯-普克算法以及基于形状特征点的道格拉斯-普克算法对数据进行处理，结果如图2所示。

从压缩结果的形状也正方面分析，传统道格拉斯-普克算法对于阈值的变化更为敏感，而基于形状特征点的算法则对阈值的敏感度。由于先提取了待处理线段的形状特征点，为线段构建了线段“骨架”，故无论阈值如何变化，数据压缩结果都能保持线段的原始形状变化特征。

从算法效率方面分析，基于形状特征点的道格拉斯-普克算法尽管先进行了形状特征点的提取，增加了额外的数据處理时间，但将原始线段根据提取的特征点进行分段划分处理，降低了道格拉斯-普克算法的迭代深度，提高了算法的时间效率。

5 结论与展望

本文分析了传统道格拉斯-普克算法的优势及不足之处，并综合考虑图形的形状特性，提取出形状特征点集，然后以特征点为分界将图形曲线分割为若干子曲线，并依次对其执行道格拉斯-普克算法处理。实验证明，该算法能够有效解决道格拉斯-普克算法在处理复杂图形时存在的自相交及形状失真的情况，并且在时间效率上也存在一定的优势。

【参考文献】

[1] ZHANG xinchang， ZENG guanghong， ZHANG qingnian. Urban Geographic Information System[M].Beijing：Science Press，2013. （张新长， 曾广鸿， 张青年.城市地理信息系统[M]. 北京： 科学出版社， 2013. ）.

[2] GUO qingshen， YANG zuqiao， FENG ke. Extracting Topographic Characteristic Line from Contours[J].Geomatics and Information Science of Wuhan University，2008，33（3），253-256. （郭庆胜， 杨族桥， 冯科. 基于等高线提取地形特征线的研究[J]. 武汉大学学报·信息科学版， 2008， 33（3）， 253-256. ）.

[3] HU peng， YOU lian， YANG chuanyong. Map Algebra[M].Wuhan：Wuhan University Press，2002. （胡鹏， 游涟， 杨传勇， 等. 地图代数[M] . 武汉：武汉大学出版社， 2002）.