基于第一特征点的道格拉斯—普克压缩算法

王笑天++吕海洋

摘 要：对传统的道格拉斯-普克压缩算法进行了分析，指出其存在迭代计算，在面对复杂曲线时可能会出现效率较低的情况。提出了曲线第一特征点概念，并基于第一特征点对传统算法进行改进，既保留曲线的基本形状，又避免在算法中出现迭代，以较小的压缩比性能损失为代价，显著提升了算法的计算效率。通过仿真实例验证了改进算法的可行性。

关键词关键词：道格拉斯-普克算法；数据压缩；第一特征点；压缩比；计算效率

DOIDOI：10.11907/rjdk.162052

中图分类号：TP312

文献标识码：A 文章编号文章编号：16727800（2016）011006803

0 引言

数据对于图形系统的重要性不言而喻。随着现代数据采集技术以及存储技术的蓬勃发展，数据的量级也逐步由原先的K、M攀升到G，甚至是T了。对于网络传输和绝大部分界面显示而言，必须预先对数据进行有效压缩，保留必要的特征信息，去除不必要的冗余。而为了保证应用的实时性，数据压缩计算效率也应予以考虑。

传统的道格拉斯-普克算法能够按照预先设定的阈值对曲线图形进行有效压缩[12]，但因其算法中存在迭代，所以面对复杂曲线时可能会出现效率较低的情况。杜婧等[3]提出了一种改进算法，能够避免传统算法中的迭代，但是引入了累积误差，所以不适用于平缓曲线的压缩。王净等[45]针对一些特殊情况，对传统算法进行了改进，拓展了适用场景。赵永清等[67]在阈值自动化设置方面提供了一些解决思路。本文通过定义曲线特征点，对传统算法进行改进，既保留了曲线的基本形状，又避免了在算法中出现迭代，以较小的压缩比性能损失为代价显著提升了算法的计算效率。

1 道格拉斯-普克算法

道格拉斯-普克算法是矢量曲线压缩的经典算法，它从整体角度考虑一条完整曲线。首先选取曲线的两个端点，计算端点之间各点到两个端点所在直线的垂直距离。如果这些点到直线的垂直距离中最大值小于或等于预先设定的阈值，则认为所有这些点都可以丢弃；若最大距离大于预先设定的阈值，则认为该最大距离点为线段上的关键点，需要保留。以此点将原曲线分为两段，对这两段再重复之前的步骤计算垂直距离，分别检查最大距离值是否大于预先设定的阈值，以决定是否存在需要保留的关键点。重复此过程直到曲线上所有点都被检测，以确定是否丢弃或保留。

如图1所示，压缩A、B两点之间的曲线。先分别计算点C、D、E、F、G到直线AB的垂直距离，通过相互比较得到最大值，找出与之对应的极值点为点E。如果该最大值仍小于或等于预先设定的阈值，则AB之间的点都可以丢弃，即在最大误差不超过所设阈值的情况下，A、B两点之间的曲线可以用直线AB近似取代；否则，保留E点，将原曲线分割为AE、EB两段。对这两段曲线重复之前的步骤，即分别计算点C、D到直线AE和点F、G到直线EB的垂直距离，检查最大距离值是否大于预先设定的阈值，以决定是否需要保留相应的极值点。

2 改进算法

2.1 改进算法描述

传统的道格拉斯-普克算法是从整体角度对曲线图形压缩，通过查找曲线中每一段的关键点，确定最终要保留的点序列。该算法虽然能够得到最优的压缩结果，但是面对复杂曲线时可能会因为关键点较多，需要对原曲线进行多次分段求解，从而影响计算效率。

杜婧等[3]提出了一种改进算法，对待检测的曲线数据点按顺序依次进行计算和比较，能够有效避免迭代产生。具体算法如下：先以曲线第1点为起点，第3点为终点，计算第2点到该直线的垂直距离，若垂直距离小于或等于预先设定的阈值，则认为第2点可以丢弃。再以第1点为起点，第4点为终点，按上述方法判断第3点是否可以丢弃；如果第2点到第1、3两点连线的垂直距离大于预先设定的阈值，则认为第2点是关键点，需要保留。再以第2点作为新的起点，第4点作为终点，按上述方法判断第3点是否可以丢弃或保留。重复此过程直到所有点都被检测，确定是否丢弃或保留。该算法虽然能提高计算效率，但由于其总是在相邻点之间计算和比较距离，所以对于缓慢变化的曲线可能会失效，造成压缩结果严重失真。

本文首先定义曲线第一特征点概念，即对于任意曲线，从起点开始依次遍历，若发现曲线中的某点到曲线两端点所在直线的垂直距离大于预先设定阈值，则认为该点是曲线的第一特征点。基于此概念，提出如下改进算法：选取曲线的两个端点，分别记为起点和终点，由起点开始查找该曲线是否存在第一特征点。若存在，则保留该特征点，并以其为新起点，与原曲线的终点组成新曲线，再在新曲线中查找是否存在第一特征点；若不存在，则认为该曲线内除起点和终点外的其余各点皆可丢弃。重复此过程直到所有点都被检测，确定是否可以丢弃或需要保留。

2.2 性能比较

以图2所示曲线AB为例，设置允许的最大误差为3，对传统的道格拉斯-普克算法、杜婧等提出的改进算法以及本文提出的改进算法三者运行结果进行比较。

传统的道格拉斯-普克算法运行如下：①依次计算点C、D、E、F、G至AB所在直线的垂直距离分别为3.3、5.3、6、5.3、3.3，根据保留最大垂直距离点的原则判断点E是需要保留的关键点；②将曲线AB分割为曲线AE和曲线EB；③分别计算点C、D至AE所在直线和点F、G至EB所在直线的垂直距离，发现都小于允许的最大误差值3，判断点C、D、F、G都可以丢弃。

杜婧等改进算法运行如下：①计算点C至AD所在直线的垂直距离，发现小于允许的最大误差值3，判断点C可以丢弃；②计算点D至AE所在直线的垂直距离，发现小于允许的最大误差值3，判断点D可以丢弃；③计算点E至AF所在直线的垂直距离，发现小于允许的最大误差值3，判断点E可以丢弃；④计算点F至AG所在直线的垂直距离，发现小于允许的最大误差值3，判断点F可以丢弃；⑤计算点G至AB所在直线的垂直距离，发现小于允许的最大误差值3，判断点G可以丢弃。

本文改进算法运行如下：①计算点C至AB所在直线的垂直距离，发现小于允许的最大误差值3，判断点C可以丢弃；②计算点D至AB所在直线的垂直距离，发现大于允许的最大误差值3，判断点D是曲线AB的特征点，需要保留；③将待压缩曲线的起点更新为点D；④计算点E至DB所在直线的垂直距离，发现小于允许的最大误差值3，判断点E可以丢弃；⑤计算点F至DB所在直线的垂直距离，发现小于允许的最大误差值3，判断点F可以丢弃；⑥计算点G至DB所在直线的垂直距离，发现小于允许的最大误差值3，判断点G可以丢弃。

由上述分析可知，3种不同的算法会得出3种截然不同的运行结果，如图3所示。传统的道格拉斯-普克算法与本文提出的改进算法都能将压缩后的数据误差控制在预先设定的范围内。传统的道格拉斯-普克算法通过分割与遍历查找，能够发现和保留每段曲线内的最值特征点，从而最大限度地保证曲线的基本形状不发生明显改变。本文提出的改进算法虽然也能按照允许误差保留曲线的特征点，但由于每次都用第一特征点对曲线进行重新划分，未对所有特征点进行比较，所以不能保证所保留的特征点是最优组合，有可能导致图形发生一定的形变，损失一定的压缩率。杜婧等提出的改进算法存在误差累积问题，由于只观察相邻数据点之间的波动情况，所以当曲线单向平缓延伸时，使用该算法就会丢失特征点，进而造成压缩结果严重失真。

在计算效率方面，两种改进算法优势较为明显。传统的道格拉斯-普克算法共需要进行9次距离计算和9次数值比较，而改进算法都只需进行5次距离计算和5次数值比较。随着保留关键点的增多，传统算法需要进一步分割曲线，并在分割后的曲线内进行遍历查找，因而其计算量会显著增加。而改进算法均只需对原始曲线内各点进行一次遍历计算，计算量与保留的关键点数量无关，因而不存在类似问题。

3 仿真实例

为进一步检验改进算法的可行性，使用Matlab工具生成两种常见的曲线，如图4所示。

传统算法和改进算法都能根据预设的允许误差实现大幅压缩数据点数的目的。传统的道格拉斯-普克算法通过分割与遍历查找，能够保留每段曲线的最值特征点，从而最大限度地保证图形基本形状不发生明显变化。改进算法由于无法获取特征点的最优组合，所以有可能导致图形发生细微的形变，并且在压缩率上也会略逊一筹。在

计算量方面，传统的道格拉斯-普克算法由于存在迭代计算，其实际计算量会随着原始数据点数和保留数据关键点数的增多而显著增加，改进算法的计算量则始终与原始数据点数在同一数量级上。因此，在面对复杂曲线时，改进算法能够在压缩比性能和计算效率两方面折衷取优。

4 结语

本文介绍了传统的道格拉斯-普克算法原理及其在曲线图形压缩方面的应用。提出曲线第一特征点概念，并基于第一特征点对传统算法进行改进，以较小的压缩比性能损失为代价，显著提升了算法的计算效率。实例仿真证明了改进算法的可行性。

参考文献：

[1] DOUGLAS D，PEUCKER T.Algorithms for the deduction of the number of points required to represent a digitized line or its caricature[J].Cartographer，1973，10（2）：112122.

[2] 王进宝，刘正纲.曲线矢量数据压缩算法实现及评析[J].测绘与空间地理信息，2006，29（2）：122124.

[3] 杜婧，张献州.道格拉斯普克算法的改进及其在管线制图中的应用[J].铁道勘察，2008（4）：2628.

[4] 王净，江刚武，管华.增强型道格拉斯—普克压缩算法的设计与实现[J].北京测绘，2002（3）：1316.

[5] 赵永清，谢传节，乔玉良，等.基于最值点的道格拉斯-普克压缩算法[J].软件导刊，2008，7（11）：6062.

[6] 赵永清.自动设置阈值的道格拉斯普克压缩法[J].山西煤炭管理干部学院学报，2013，26（3）：120122.

[7] 于靖，陈刚，张笑，等.面向自然岸线抽稀的改进道格拉斯—普克算法[J].测绘科学，2015，40（4）：2328.

（责任编辑：杜能钢）