移动计算环境中曲线数据实时压缩方法

曲线是一种矢量数据格式 ,由互相关联的坐标点构成 ,栅格数据是另一种常用的数据格式 ,用矩阵表达. 与栅格数据相比 ,矢量数据具有数据量小、精度高、更容易表示拓扑关系等特点 ,被广泛用于图形系统建模. 曲线表达的模型形状光滑 ,坐标之间具有较强的相关性 ,如等高线、NURBS 等 ,本文提出一种减小这种相关性的方法 ,以达到压缩数据的目的.

移动计算环境中计算资源有限 , 如当前主流PDA 的处理器频率约为 512 MHz ,内存约为128 MB ,外存储卡为若干个 GB ,无线网络标准 802. 11 b 的理论峰值为 11 MbΠs. 压缩技术可以在有限计算资源的限制下 ,提高图形系统处理数据的能力. 本文提出一种能够在移动环境中实时地压缩和解压缩曲线数据的方法 ,以实现用软件的方式提高通信带宽、内存带宽、存储容量等目标.

国内外相关研究主要集中在数字地图压缩和模式识别后图形的简化 , 研究目标主要分 3 类 : mi n2ε,压缩后形态点数目已知 , 要求形变最小 ; mi n2 # ,压缩后最大形变已知 , 要求形态点数最小 ; mi n2rate , 压缩后最大形变已知 , 要求数据量最小.我们尚未未见到有关减小压缩解压缩时间空间复杂度的研究的文献 ,本文研究的目标就是减小曲线压缩方法的时间空间复杂度.

矢量压缩技术主要分为近似方法和量化编码方法 2 类. 近似方法通过减少组成矢量的点进行压缩 ;量化编码方法根据某些方式将矢量坐标量化为相关性较强的形式 ,然后编码压缩.

近似方法由 Douglas 等于 1973 年提出[1 ] ,国内外一些学者对其进行了改进 ,这类方法以文献[229 ]的研究较为深入. 近似方法压缩过程效率较低 ,时间和空间复杂度为 O( N2 ) [2 ] ,使用动态规划可提高其效率 ,将空间复杂度降为 O ( N ) , 时间复杂度降为O( N) ～O( N2 ) [328 ] .

量化编码方法的相关研究主要有 Shekhar 等提出的聚类方法[10211 ] , Kolesnikov 等提出的链码方[12 ] 和基于动态规划的方法[13 ] . 聚类方法的空间复法杂度为 O( N) ,时间复杂度大于 O ( N ) ,并且需要额外空间存储字典; 动态规划方法空间复杂度为 O( N) ,时间复杂度为 O ( N) ～O ( N2 ) ;链码方法将曲线转化成链码序列 , 然后使用上下文相关的文本压缩算法压缩 ,效率较低 , 当容限较小时 , 链码序列较长 ,压缩效果较差.

近似方法和量化编码方法的时间空间复杂度较高 ,不能在移动计算环境中实时压缩解压缩海量数据. 目前移动计算环境中常用的曲线压缩方法是类型转换方法 ,这种方法将坐标由浮点数转化为整型数存储 ,其优点是速度可以满足实时性要求 ,缺点是压缩程度有限. 本文方法改进了类型转换方法 ,在保证压缩速度的同时进一步减小压缩比 , 令压缩时间和压缩效果获得更好的平衡. 曲线坐标的相关性强于折线坐标 ,本文方法首先使用整型小波变换不断地计算坐标的高频分量 , 减小数据冗余 , 然后使用FFEP(four. five ,eight . plus) 编码进行编码. FFEP编码专为编码曲线坐标高频分量设计的编码方法 ,该方法使用较短的码编码出现频率较高的符号 ,使用较长的码编码出现频率较低的符号 ,使用变长码编码偶尔出现的特殊符号 ,既保证压缩效果 ,又增强编码的鲁棒性. 整型小波变换和 FFEP 编码不占用额外内存 ,只包含简单的加减和移位运算 , 效率较高. 压缩等高线数据的实验表明 ,本文方法能够在移动计算环境中实时压缩曲线数据.

更多内容请查看pdf