(中国科学院地理科学与资源研究所 北京 100101) (中国科学院研究生院 北京 100039）
论文来源：中国测绘学会九届四次理事会暨2008年学术年会论文集
摘要:提出了应用于曲线矢量压缩的基于IWT(整数小波变换)的“458+编码”方案. 该方案根据指定容限量化曲线矢量 ,然后计算一阶差分后使用IWT减小矢量分量 ,最后根据矢量分量大小选择合适的码长按位编码 ,解码时可按字节解码. 由于IWT计算机实现较快 ,“458+编码”的编码解码速度均…
关键词: 458+编码 ; 整型小波变换 ; 曲线矢量压缩 ; 矢量数据压缩
曲线在CG、CAD中广泛用于高精度建模 ,曲线可以用参数方程的形式表示 ,常用的参数曲线有: Bezier曲线、B样条曲线非均匀有理B样条(NURBS)曲线等 ,曲线常用于地形建模(等高线)及光滑的线状实体建模. 曲线压缩对模型高效存储及传输具有重要意义. 对曲线进行压缩 ,能够减小存储数据所需的空间和传输数据所需的时间 ,提高图形系统的性能. 本文提出的方法适用于二维及三维曲线 ,出于简便考虑本文以二维曲线作为研究对象.
矢量压缩算法主要解决三类问题: min ? ε 问题 ,限制压缩后曲线形态点数求得形变最小的压缩方案; min ? # 问题 ,限制压缩后最大形变求得形态点数最小的方案; min ? rate 问题, 限制压缩后最大形变求得编码后码长最短的方案.[13]-[23] 矢量压缩可以通过两种办法实现: 通过多边形近似减少形态点数目; 对矢量进行量化编码. 前者可以用于min ? ε 、min ? # 和min ? rate 问题 ,后者只可用于min ? rate 问题. 本文提出的方法属于量化编码算法 ,用于解决min ? rate 问题.
min ? rate 问题解决方法存在的问题之一是算法的效率较低 ,不能较好的适用于处理器速度和受限的计算环境. 多边形近似算法最早由Dauglas和Peucker与1973年提出[1] ,后国内外一些学者对其进行了改进[2][3] ,近年来Alexander Kolesnikov和Alexander Akimov进行了深入研究 ,并取得了较好成果[23].多边形近似算法中获得最佳近似多边形的时间和空间复杂度均依赖于最短路径算法的时间和空间复杂度 ,即均为ON2()[23] ,使用动态规划算法计算近似最短路径可以简化算法 ,简化后算法空间复杂度为ON() ,时间复杂度为
ON()~ON( 2 )[13]-[15]. 量化编码算法的主要研究有Shashi Shekhar等人于2002年提出的聚类算法[24][25]和Alexander Kolesnikov等人于2004年提出的基于动态规划的尺度量化算法[22]. 前者算法的空间复杂度为ON() ,时间复杂度大于ON().后者空间复杂度为ON() ,时间复杂度为
ON()~ON( 2 ).
min ? rate 问题解决方法存在的另一个问题是多边形近似法和矢量量化法大都采用的熵编码存在局限 ,如果对每一条曲线建立一个概率模型 ,如果曲线点数不多但曲线条数较多时 ,数据冗余较小 ,熵编码压缩效果较差. 如果为所有的曲线建立一个概率模型, 若使用自适应编码 ,曲线之间建立了关联无法随机编码解码 ,若不使用自适应编码 ,需要额外空间存储字典 ,字典有可能较大. 国内对矢量数据压缩算法的研究存在一些缺陷[4]-[8], 如: 误差控制问题的解决, 有说服力的试验验证算法的压缩比等.
更多内容请查看pdf