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

答辩人： *专 业： 地图学与地理信息系统导 师： *教授,因特网传输中 矢量数据压缩算法研究,内容提要,绪 论,研究的目的和意义,目前矢量数据压缩主要存在以下三个问题：数据压缩通常可分为有损压缩和无损压缩两种。选择 有损压缩还是无损压缩算法是矢量数据压缩首先需要 解决的问题。一个实用的高效压缩编码方案要同时综合考虑各类编 码技术之所长。选取哪种压缩算法是实现矢量数据高 效压缩需解决的问题。目前对矢量数据进行压缩时未考虑其多样性，如何针 对点类和线、多边形类几何文件按照其存储特点采取 不同的几何无损压缩算法是需要解决的问题。,研究目标和内容,压缩模式选取,压缩编码方案,几何无损压缩,矢量数据多样性,有损VS无损,内容提要,数 据 压 缩,无损压缩,数据压缩,有损压缩,统计压缩,字典压缩,算术编码,游程编码,Huffman编码码,LZ77,LZW,LZ78,矢量数据有损压缩,栅格数据有损压缩,垂距限值法,道格拉斯法,角度限值法,JPEG,小波变换,内容提要,无损压缩算法分析,无损压缩,基于统计概率模型压缩,Shannon-Fano,Huffman,Text,第一类字典模型,第二类字典模型,基于字典模型压缩,LZSS算法,LZ77算法,LZ78算法,LZW算法,无损压缩算法分析,Huffman算法分析,编码译码时的唯一性,优点：,实际编码并不一定是最优,缺点：,输入符号数受限于可实现的Huffman码表尺寸,没有错误保护功能,译码复杂度高,无损压缩算法分析,LZSS算法分析,正文窗口维护方法的改变,优点：,匹配字符串长度的选取问题,缺点：,小文件压缩效果不理想,实际输出的标记方面,无损压缩算法分析,LZW算法分析,易于硬件实现，压缩效果好,优点：,实现简单、快速,缺点：,复杂匹配串的压缩效果受限,字典容量的选取与计算机性能存在矛盾,算法本身的局限性,无损压缩算法分析,压缩率,无损压缩算法分析,压缩速度,内容提要,矢量数据无损压缩算法的设计,设计：,第一步：对于包含点、线、多边形的几何数据，针对其在矢量地图中各几何图形要素的不同存储特点，分别对其采用有效的几何压缩算法进行压缩。第二步：将进行完第一步压缩后的几何数据、与几何记录保持一致性的属性数据、拓扑数据均采用改进后的LZW算法进行压缩,矢量数据无损压缩算法的设计,无损几何坐标压缩的算法,步骤1： X坐标序列从小到大排序，保持第一点，其余X坐标数据以长整数表示，并作偏移量代替变换步骤2：保持第一点不变，Y坐标序列从第二点开始从小到大排序，保持第二点，其余Y坐标以长整数表示，并作偏移量代替变换步骤3：对X、Y坐标序列交替采取步骤1，步骤2，至使大部分坐标值缩小为系统设定的某阈值（如：190）以内,点文件：,矢量数据无损压缩算法的设计,无损几何坐标压缩的算法,同一曲线和多边形实体的坐标点列是密集的和顺序的，这决定了前后坐标点列的坐标值大小差别不大步骤1：保持第一点先不变，其余几何数据以长整数表示，并作偏移量代替变换步骤2：分别对X，Y坐标的“+”块和“-”块求其平均值（取整），再以该值与平均数的差值代替原值。,线、面文件：,矢量数据无损压缩算法的设计,几何数据与属性数据关系一致性维护：,对于点类文件来说，由于几何压缩过程中的点的排列位置要变化，因此属性文件记录的位置也一定要做相应变化，最好在排序前就将各个点的几何数据与其对应的属性数据写为一条记录，这样在解压缩时只要将每条记录中的属性数据再依次写入属性文件即可。对于线、多边形类文件来说，由于一条线或一个多边形的各点排列顺序是固定的，在对其几何压缩的过程中，并未改变各坐标点的排列位置，不会影响其几何数据与属性数据的一致性关系。,矢量数据无损压缩算法的设计,LZW压缩算法改进,(1)复杂匹配串的压缩效果受限 (2)检索字典的时间与执行效率存在矛盾,LZW压缩算法缺点：,(1)通过增加字典的大小来加以改进，字典能存储的短语越多越 长，压缩程序的压缩效果就可能越好。 (2)变换代码长度编码,LZW压缩算法改进：,内容提要,实验分析,点文件压缩前后对比：,实验分析,线文件压缩前后对比：,实验分析,面文件压缩前后对比：,实验分析,结果分析：,对点、线、面数据的最高压缩比分别为15.2、17.2、7.5 取得了较高的压缩率。从压缩时间上看，对于几十kb 的小文件，可以达到毫秒级的压缩时间，稍大些的文 件也在几秒钟。无论从压缩率还是从压缩时间上来， 本文所述算法均可达到较好的压缩效率。,实验分析,结果分析：,对随着点文件的增大，压缩比呈增减增减的趋势；随着线文件的增大，压缩比呈先增后减趋势；随着面数据的增大，压缩比呈增减增减的趋势。出现上述趋势的原因：LZW算法中字典的大小及代码长度。,实验分析,结果分析：,对点文件的压缩在对界址点标注（954,713 byte）压缩时压缩比最低，为 1.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）进行