因特网传输中矢量数据压缩算法研究-武汉大学硕士学位论文答辩

1、辩论人： *专 业： 地图学与地理信息系统导 师： *教授 因特网传输中 矢量数据压缩算法研究内容提要绪论数据压缩无损压缩算法分析矢量数据无损压缩算法的设计实验分析结论绪 论研究的目的和意义目前矢量数据压缩主要存在以下三个问题：数据压缩通常可分为有损压缩和无损压缩两种。选择 有损压缩还是无损压缩算法是矢量数据压缩首先需要 解决的问题。一个实用的高效压缩编码方案要同时综合考虑各类编 码技术之所长。选取哪种压缩算法是实现矢量数据高 效压缩需解决的问题。目前对矢量数据进行压缩时未考虑其多样性，如何针 对点类和线、多边形类几何文件按照其存储特点采取 不同的几何无损压缩算法是需要解决的问题。研究目标和内

2、容BCA压缩模式选取压缩编码方案几何无损压缩矢量数据多样性有损VS无损内容提要绪论数据压缩无损压缩算法分析矢量数据无损压缩算法的设计实验分析结论数 据 压 缩 无损压缩 数据压缩 有损压缩统计压缩字典压缩算术编码游程编码Huffman编码码LZ77LZWLZ78矢量数据有损压缩栅格数据有损压缩垂距限值法道格拉斯法角度限值法JPEG小波变换内容提要绪论数据压缩无损压缩算法分析矢量数据无损压缩算法的设计实验分析结论无损压缩算法分析无损压缩基于统计概率模型压缩Shannon-FanoHuffmanText第一类字典模型第二类字典模型基于字典模型压缩LZSS算法LZ77算法LZ78算法LZW算法无损压

3、缩算法分析Huffman算法分析编码译码时的唯一性优点：实际编码并不一定是最优缺点：输入符号数受限于可实现的Huffman码表尺寸没有错误保护功能译码复杂度高无损压缩算法分析 LZSS算法分析正文窗口维护方法的改变优点：匹配字符串长度的选取问题缺点：小文件压缩效果不理想实际输出的标记方面无损压缩算法分析LZW算法分析易于硬件实现，压缩效果好优点：实现简单、快速缺点：复杂匹配串的压缩效果受限字典容量的选取与计算机性能存在矛盾算法本身的局限性无损压缩算法分析压缩率文件算法 文本文件二进制文件超文本文件56K230K1096K46K252K1083K70K314K756KHuffman92%78%4

4、9%75%68%43%80%77%71%LZSS67%64%32%62%50%38%45%35%31%LZW61%57%32%55%45%33%44%32%31%无损压缩算法分析压缩速度文件算法文本文件二进制文件超文本文件56K230K1096K46K252K1083K70K314K756KHuffman压缩时间7920398414123592163235641解压时间62250120347250103294328859总耗时141453218718848519531575631500LZSS压缩时间78297128247297101663182661解压时间16471561532125158

5、2250总耗时94344143862329114178234911LZW压缩时间321567826223593847266401解压时间154720315471921636114总耗时4720395277282110063302515内容提要绪论数据压缩无损压缩算法分析矢量数据无损压缩算法的设计实验分析结论矢量数据无损压缩算法的设计设计：第一步：对于包含点、线、多边形的几何数据，针对其在矢量地图中各几何图形要素的不同存储特点，分别对其采用有效的几何压缩算法进行压缩。第二步：将进行完第一步压缩后的几何数据、与几何记录保持一致性的属性数据、拓扑数据均采用改进后的LZW算法进行压缩矢量数据无损压缩算

6、法的设计无损几何坐标压缩的算法步骤1： X坐标序列从小到大排序，保持第一点，其余X坐标数据以长整数表示，并作偏移量代替变换步骤2：保持第一点不变，Y坐标序列从第二点开始从小到大排序，保持第二点，其余Y坐标以长整数表示，并作偏移量代替变换步骤3：对X、Y坐标序列交替采取步骤1，步骤2，至使大局部坐标值缩小为系统设定的某阈值如：190以内点文件：矢量数据无损压缩算法的设计无损几何坐标压缩的算法同一曲线和多边形实体的坐标点列是密集的和顺序的，这决定了前后坐标点列的坐标值大小差异不大步骤1：保持第一点先不变，其余几何数据以长整数表示，并作偏移量代替变换步骤2：分别对X，Y坐标的“+块和“-块求其平均值

7、取整，再以该值与平均数的差值代替原值。线、面文件：步骤数据原始矢量结构步骤1：保持第一点先不变，其余几何数据以长整数表示，并作偏移量代替变换步骤2：分别对X，Y坐标的“+”块和“-”块求其平均值（取整），再以该值与平均数的差值代替原值几何数据点X坐标Y坐标X坐标Y坐标X坐标Y坐标118.02606634.58067618.002606634.58067618.02606634.580676218.02607734.580685119-54318.02608834.580692117-52418.02610034.580699127-12518.02614134.5807134111259618

8、.02618134.5807184024240718.02621134.5807063014145818.02621734.5806977-9-98918.02622234.5806865-11-1161018.02622634.5806754-11-1261118.02623734.58064311-32-5-151218.02624434.5806127-31-9-141318.02624134.580583-3-2910-121418.02623034.580563-11-202-31518.02621234.580546-18-17501618.02618934.580534-23-1

9、21051718.02615734.580527-32-7-19101818.02612534.580530-323-19-141918.02610034.580544-2514-12-32018.02609434.580553-697-82118.02608934.580563-5108-72218.02608534.580574-4119-62318.02607734.580598-824572418.02607134.580622-624772518.02606634.580646-524872618.02606634.5806760301313拓扑关系顺序关系保持顺序关系及以第一个点为

10、参照点，其坐标值不变保持顺序关系及以第一个点为参照点，其坐标值不变；并记录拓扑关系维持信息：（16，11，-13，14）（8 5，-17 11，17 9），其中前一个括号表示X列平均数，个数信息及数列的“+”，“-”信息；后一括号表示Y列平均数，个数信息及数列的“+”，“-”信息。要记录“+”块和“-”块的个数信息，否则无法重构数据。矢量数据无损压缩算法的设计几何数据与属性数据关系一致性维护：对于点类文件来说，由于几何压缩过程中的点的排列位置要变化，因此属性文件记录的位置也一定要做相应变化，最好在排序前就将各个点的几何数据与其对应的属性数据写为一条记录，这样在解压缩时只要将每条记录中的属性数据

11、再依次写入属性文件即可。对于线、多边形类文件来说，由于一条线或一个多边形的各点排列顺序是固定的，在对其几何压缩的过程中，并未改变各坐标点的排列位置，不会影响其几何数据与属性数据的一致性关系。矢量数据无损压缩算法的设计LZW压缩算法改进 (1)复杂匹配串的压缩效果受限 (2)检索字典的时间与执行效率存在矛盾LZW压缩算法缺点： (1)通过增加字典的大小来加以改进，字典能存储的短语越多越 长，压缩程序的压缩效果就可能越好。 (2)变换代码长度编码LZW压缩算法改进：文件算法二进制文件文本文件90K464 K2317 K68 K678 K2032 KLZW-1230 K147 K728 K52 K4

12、99 K1492 KLZW-1326 K117 K568 K49 K450 K1341 KLZW-1426 K97 K447 K45 K385 K1141 K内容提要绪论数据压缩无损压缩算法分析矢量数据无损压缩算法的设计实验分析结论实验分析点文件压缩前后比照：文件名称原文件大小（byte）几何压缩+LZW无损压缩（byte）压缩比压缩时间（ms）宗地点_金湾36,8648,2094.565地质灾害点282,52734,5218.2241界址点标注954,713575,8461.7633地名点3,837,668252,23015.22,092房产界址点6,244,8501,066,9465.93

13、,158文件名称原文件大小（byte）几何压缩+LZW无损压缩（byte）压缩比压缩时间（ms）境界线67,27048,2711.4138道路1,490,818183,2168.1923街道3,837,663219,89317.21,896金湾道路7,488,5087,153,3481.03,553房产25,878,27915,353,0291.78,472实验分析线文件压缩前后比照：实验分析面文件压缩前后比照：文件名称原文件大小（byte）几何压缩+LZW无损压缩（byte）压缩比压缩时间（ms）金湾部分房产数据36,23311,2313.273矿山498,24482,1916.1384航空

14、影像结合表821,829316,7282.6642宗地面11,404,5311,522,7287.52,467房产界址面172,703,96743,829,2153.928,657文件名称原文件大小（byte）几何压缩+LZW无损压缩（byte）压缩比压缩时间（ms）宗地点_金湾36,8648,2094.565地质灾害点282,52734,5218.2241界址点标注954,713575,8461.7633地名点3,837,668252,23015.22,092房产界址点6,244,8501,066,9465.93,158实验分析结果分析：对点、线、面数据的最高压缩比分别为15.2、17.2、

15、7.5 取得了较高的压缩率。从压缩时间上看，对于几十kb 的小文件，可以到达毫秒级的压缩时间，稍大些的文 件也在几秒钟。无论从压缩率还是从压缩时间上来， 本文所述算法均可到达较好的压缩效率。文件名称原文件大小（byte）几何压缩+LZW无损压缩（byte）压缩比压缩时间（ms）境界线67,27048,2711.4138道路1,490,818183,2168.1923街道3,837,663219,89317.21,896金湾道路7,488,5087,153,3481.03,553房产25,878,27915,353,0291.78,472文件名称原文件大小（byte）几何压缩+LZW无损压缩（b

16、yte）压缩比压缩时间（ms）金湾部分房产数据36,23311,2313.273矿山498,24482,1916.1384航空影像结合表821,829316,7282.6642宗地面11,404,5311,522,7287.52,467房产界址面172,703,96743,829,2153.928,657实验分析结果分析：对随着点文件的增大，压缩比呈增减增减的趋势；随着线文件的增大，压缩比呈先增后减趋势；随着面数据的增大，压缩比呈增减增减的趋势。出现上述趋势的原因：LZW算法中字典的大小及代码长度。实验分析结果分析：对点文件的压缩在对界址点标注954,713 byte压缩时压缩比最低，为 1.

17、7，随后在对地名点3,837,668 byte压缩时压缩比最高 ，为15.2； 线文件的压缩在对街道3,837,663 byte压缩时压缩比最高，为17.2，随 后在对金湾街道7,488,508 byte压缩时压缩比最低，为1.0。实验分析结果分析：对界址点标注954,713 byte及地名点3,837,668 byte进行详细分析界址点标注总大小.dbf.prj.sbn.sbx.shp.shp.xml.shx压缩前（kb）932911179250710145压缩后（kb）5621011232343780压缩比1.79.111.511.51.51.8地名点总大小.dbf.prj.sbn.sbx.shp.shp.xml.shx压缩前（kb）3,7373,6391191571817压缩后（kb）24415719133108压缩比15.22312.111.71.82.1 9% 54% 97%1.5%通过进一步研究.shp文件的压缩来进一步提高矢量数据的压缩效率内容提要绪