﻿ 曲线数据压缩算法的研究及应用
 计算机系统应用  2019, Vol. 28 Issue (5): 150-155 PDF

Study and Application of Curve Data Compression Algorithm
MENG Wei-Dong, LONG Mei-Biao
Nanyue Fuel Injection Systems Co. Ltd, Hengyang 421007, China
Foundation item: Science and Technology Major Program of Hunan Province (2015GK1037); Special Fund for Intellectual Property Strategy Implementation of Hunan Province (2017Z4007G); Science and Technology Plan of Hengyang City (2014C20)
Abstract: Aiming at the insufficiency of the classical Douglas-Peucker data compression algorithm, such as low recursion efficiency and uncertain threshold selection, the study proposes an improved feature point extraction method. The algorithm calculates the frequency of data points by histogram, according to the distance from the data point to the baseline and the turning angle between adjacent data points, considers the "isolation" and frequency of data points, and entropy value method is used to obtain the ultimate evaluation value, the curve data is compressed automatically with the given data compression ratio. The simulation experiments are carried out on MATLAB, and using the self-developed control system platform, incremental self-learning for the flow characteristics of inlet metering valve, the corresponding experiments are carried out on pump test bench and diesel engine test rig. Experimental results show that this algorithm can effectively compress data to meet the data compression requirements of measurement system and control system.
Key words: data compression     curve     feature point     Douglas-Peucker algorithm     compression ratio

1 相关工作

(1)阈值的选取具有不确定性, 如果阈值选取不合理, 可能导致一些特征点被误删除;

(2)选定阈值与数据压缩率没有直接关系, 导致不能事先确定压缩点数;

(3)算法中存在递归分段计算, 对于复杂的曲线, 迭代次数多, 计算量大, 比较耗费时间;

(4)未考虑频数等非空间属性对数据点的影响, 可能导致一些特征点被删除.

2 改进的曲线数据压缩算法

 ${f_k} = \frac{{{R_k}}}{R} \cdot m$

 ${N_2} = {N_1}\sqrt {{{\left( {\frac{{{S_1}}}{{{S_2}}}} \right)}^x}}$
 $\Delta N = {N_1} - {N_2}$

 ${g_i} = \frac{{{L_{{P_{i - 1}}{P_i}}} + {L_{{P_i}{P_{i + 1}}}}}}{{\frac{2}{{n - 1}}\displaystyle\sum\limits_{j = 1}^{n - 1} {{L_{{P_j}{P_{j + 1}}}}} }}$

 图 1 孤独指标的涵义

(1)指标归一化:

 $X_{ij}' = \frac{{{X_{ij}} - \min \left\{ {{X_{2j}},{X_{3j}}, \cdots, {X_{\left( {n - 1} \right)j}}} \right\}}}{{\max \left\{ {{X_{2j}},{X_{3j}}, \cdots, {X_{\left( {n - 1} \right)j}}} \right\} - \min \left\{ {{X_{2j}},{X_{3j}}, \cdots, {X_{\left( {n - 1} \right)j}}} \right\}}}$

(2)计算第 $j$ 项指标下第 $i$ 个数据点占该指标的比重 ${f_{ij}}$ :

 ${f_{ij}} = \frac{{X_{ij}'}}{{\displaystyle\sum\limits_{i = 2}^{n - 1} {X_{ij}'} }}$

(3)计算第 $j$ 项指标的熵值 ${h_j}$ :

 ${h_j} = - k\sum\limits_{i = 2}^{n - 1} {{f_{ij}}\ln \left( {{f_{ij}}} \right)}$

(4)计算各项指标的熵权 ${w_j}$ :

 ${w_j} = \frac{{1 - {h_j}}}{{\displaystyle\sum\limits_{j = 1}^J {{h_j}} }}$

(5)计算各数据点的综合得分 ${s_i}$ :

 ${s_i} = \sum\limits_{j = 1}^J {{w_j}} \cdot {f_{ij}}$

(1)不需要事先设定阈值, 算法自动根据加权修正后的综合得分, 以从小到大顺序, 依次压缩数据;

(2)直接指定数据压缩率, 保证压缩算法运行后结果, 满足测量系统和控制系统的带宽、分辨率和存储量的要求;

(3)取消迭代运算, 对于复杂的曲线, 将有效降低计算量, 减少运算时间;

(4)特征点的确定, 不仅考虑了逻辑相邻和物理相邻关系, 而且同时考虑了频数等非空间属性的影响, 降低了误删除概率.

3 实验分析 3.1 实验数据来源

3.2 实验设计

 图 2 方案一直方图频数分布

 图 3 方案二直方图频数分布

3.3 实验结果及分析 3.3.1 实验一

 图 4 实验一两种算法形态对比

3.3.2 实验二

 图 5 曲线数据压缩率为4%的结果

(1)运行时间: 压缩率为4%时, 本文改进算法运行时间比传统道格拉斯-普克算法减少了68.33%; 压缩率为12%时, 减少了50.13%. 由于道格拉斯-普克算法迭代次数分别为45次和41次, 即使按时间复杂度为 $O\left( {n\log n} \right)$ , 也远大于本文改进算法的时间复杂度为 $O\left( n \right)$ , 导致程序运行时间较长. 输入数据量 $n$ 急剧增加时, 传统道格拉斯-普克算法执行次数的增长次数差异显著增加[20].

 图 6 曲线数据压缩率为12%的结果

(2)位移偏差、面积偏差: 本文改进算法根据数据点多种属性的相对重要性程度进行压缩,当考虑数据的非空间属性, 如频数时, 在较好地保持曲线形状的同时,可能导致位移偏差和面积偏差大于传统道格拉斯-普克算法.

(3)压缩率: 由于道格拉斯-普克算法最佳阈值选取需要多次试探, Prasad DK等[813]采用曲线拟合等阈值优化选取方法, 严重影响压缩计算效率, 很难直接给定压缩率. 本文改进算法自动按照给定数据压缩率进行曲线数据压缩, 容易实现高压缩率与保真效果之间的平衡.

4 结论

 [1] 李帅, 方源敏, 喜文飞. 矢量曲线特征点提取方法的改进. 河南科学, 2011, 29(4): 469-471. DOI:10.3969/j.issn.1004-3918.2011.04.022 [2] 尹志喜, 甄国涌. 曲线数据压缩算法研究与应用. 计算机系统应用, 2010, 19(3): 226-228. DOI:10.3969/j.issn.1003-3254.2010.03.055 [3] Douglas DH, Peucker TK. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization, 1973, 10(2): 112-122. DOI:10.3138/FM57-6770-U75U-7727 [4] 王笑天, 吕海洋. 基于第一特征点的道格拉斯-普克压缩算法. 软件导刊, 2016, 15(11): 68-70. [5] 韩晓霞, 崔浩, 孙钰珊. 顾及曲线走向及局部面积特征的矢量数据压缩算法. 北京测绘, 2017(6): 6-9. [6] Wu ST, Marquez MRG. A non-self-intersection Douglas-Peucker algorithm. Proceedings of the 16th Brazilian Symposium on Computer Graphics and Image Processing. Sao Carlos, Brazil. 2003. 60–66. [7] 于靖, 陈刚, 张笑, 等. 面向自然岸线抽稀的改进道格拉斯—普克算法. 测绘科学, 2015, 40(4): 23-27. [8] Prasad DK, Quek C, Leung MKH, et al. A parameter independent line fitting method. Proceedings of the 1st Asian Conference on Pattern Recognition. Beijing, China. 2011. 441–445. [9] 王晓理, 陈双军, 魏斌, 等. 曲线拟合的Douglas-Peucker算法阈值优化选择. 测绘科学技术学报, 2010, 27(6): 459-462. DOI:10.3969/j.issn.1673-6338.2010.06.017 [10] 周峰, 龚光红, 王露. 道路矢量简化的自动阈值算法研究. 中国体视学与图像分析, 2014, 19(2): 155-161. [11] 李朝奎, 骆文芳, 陈果, 等. 渐进式改进的线要素简化算法探讨. 测绘科学, 2015, 40(11): 123-126. [12] 张志伟, 暴景阳, 肖付民, 等. 基于Ping的Douglas-Peucker法抽稀阈值优化选取. 海洋测绘, 2015, 35(2): 9-12. DOI:10.3969/j.issn.1671-3044.2015.02.003 [13] 赵永清. 自动设置阈值的道格拉斯-普克压缩法. 山西煤炭管理干部学院学报, 2013, 26(3): 120-122. DOI:10.3969/j.issn.1008-8881.2013.03.051 [14] Ai TH, Ke S, Yang M, et al. Envelope generation and simplification of polylines using delaunay triangulation. International Journal of Geographical Information Science, 2017, 31(2): 297-319. DOI:10.1080/13658816.2016.1197399 [15] 乔俊军, 胡冯伟. 一种线状要素深度简化方法. 测绘通报, 2016(7): 48-54. [16] 王丽娜, 江南, 李响, 等. Cartogram表示方法研究综述. 计算机辅助设计与图形学学报, 2017, 29(3): 393-405. DOI:10.3969/j.issn.1003-9775.2017.03.001 [17] 钱海忠, 何海威, 王骁, 等. 采用三元弯曲组划分的线要素化简方法. 武汉大学学报·信息科学版, 2017, 42(8): 1096-1103. [18] 杜佳威, 武芳, 巩现勇, 等. 采用双向斜拉式弯曲划分的曲线渐进化简方法. 中国图象图形学报, 2017, 22(10): 1455-1466. [19] 顾腾, 陈晓勇, 刘成强. 一种Douglas-Peucker与Li-Openshaw结合改进的曲线化简方法. 东华理工大学学报(自然科学版), 2016, 39(4): 396-400. DOI:10.3969/j.issn.1674-3504.2016.04.015 [20] Levitin A. 算法设计与分析基础. 潘彦, 译. 3版. 北京: 清华大学出版社, 2015. 35–132. [21] Kulik L, Duckham M, Egenhofer M. Ontology-driven map generalization. Journal of Visual Languages & Computing, 2005, 16(3): 245-267. [22] 何津, 费立凡. 再论三维Douglas-Peucker算法及其在DEM综合中的应用. 武汉大学学报·信息科学版, 2008, 33(2): 160-163.