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

基于第一特征点的道格拉斯―普克压缩算法 　　摘 要：对传统的道格拉斯-普克压缩算法进行了分析，指出其存在迭代计算，在面对复杂曲线时可能会出现效率较低的情况。提出了曲线第一特征点概念，并基于第一特征点对传统算法进行改进，既保留曲线的基本形状，又避免在算法中出现迭代，以较小的压缩比性能损失为代价，显著提升了算法的计算效率。通过仿真实例验证了改进算法的可行性。 　　关键词关键词：道格拉斯-普克算法；数据压缩；第一特征点；压缩比；计算效率 　　DOIDOI：10.11907/rjdk.162052 　　中图分类号：TP312 　　文献标识码：A 文章编号文章编号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为例