移動計算環(huán)境中曲線數(shù)據(jù)實時壓縮方法

曲線是一種矢量數(shù)據(jù)格式 ,由互相關(guān)聯(lián)的坐標點構(gòu)成 ,柵格數(shù)據(jù)是另一種常用的數(shù)據(jù)格式 ,用矩陣表達. 與柵格數(shù)據(jù)相比 ,矢量數(shù)據(jù)具有數(shù)據(jù)量小、精度高、更容易表示拓撲關(guān)系等特點 ,被廣泛用于圖形系統(tǒng)建模. 曲線表達的模型形狀光滑 ,坐標之間具有較強的相關(guān)性 ,如等高線、NURBS 等 ,本文提出一種減小這種相關(guān)性的方法 ,以達到壓縮數(shù)據(jù)的目的.

移動計算環(huán)境中計算資源有限 , 如當前主流PDA 的處理器頻率約為 512 MHz ,內(nèi)存約為128 MB ,外存儲卡為若干個 GB ,無線網(wǎng)絡標準 802. 11 b 的理論峰值為 11 MbΠs. 壓縮技術(shù)可以在有限計算資源的限制下 ,提高圖形系統(tǒng)處理數(shù)據(jù)的能力. 本文提出一種能夠在移動環(huán)境中實時地壓縮和解壓縮曲線數(shù)據(jù)的方法 ,以實現(xiàn)用軟件的方式提高通信帶寬、內(nèi)存帶寬、存儲容量等目標.

國內(nèi)外相關(guān)研究主要集中在數(shù)字地圖壓縮和模式識別后圖形的簡化 , 研究目標主要分 3 類 : mi n2ε,壓縮后形態(tài)點數(shù)目已知 , 要求形變最小 ; mi n2 # ,壓縮后最大形變已知 , 要求形態(tài)點數(shù)最小 ; mi n2rate , 壓縮后最大形變已知 , 要求數(shù)據(jù)量最小.我們尚未未見到有關(guān)減小壓縮解壓縮時間空間復雜度的研究的文獻 ,本文研究的目標就是減小曲線壓縮方法的時間空間復雜度.

矢量壓縮技術(shù)主要分為近似方法和量化編碼方法 2 類. 近似方法通過減少組成矢量的點進行壓縮 ;量化編碼方法根據(jù)某些方式將矢量坐標量化為相關(guān)性較強的形式 ,然后編碼壓縮.

近似方法由 Douglas 等于 1973 年提出[1 ] ,國內(nèi)外一些學者對其進行了改進 ,這類方法以文獻[229 ]的研究較為深入. 近似方法壓縮過程效率較低 ,時間和空間復雜度為 O( N2 ) [2 ] ,使用動態(tài)規(guī)劃可提高其效率 ,將空間復雜度降為 O ( N ) , 時間復雜度降為O( N) ～O( N2 ) [328 ] .

量化編碼方法的相關(guān)研究主要有 Shekhar 等提出的聚類方法[10211 ] , Kolesnikov 等提出的鏈碼方[12 ] 和基于動態(tài)規(guī)劃的方法[13 ] . 聚類方法的空間復法雜度為 O( N) ,時間復雜度大于 O ( N ) ,并且需要額外空間存儲字典; 動態(tài)規(guī)劃方法空間復雜度為 O( N) ,時間復雜度為 O ( N) ～O ( N2 ) ;鏈碼方法將曲線轉(zhuǎn)化成鏈碼序列 , 然后使用上下文相關(guān)的文本壓縮算法壓縮 ,效率較低 , 當容限較小時 , 鏈碼序列較長 ,壓縮效果較差.

近似方法和量化編碼方法的時間空間復雜度較高 ,不能在移動計算環(huán)境中實時壓縮解壓縮海量數(shù)據(jù). 目前移動計算環(huán)境中常用的曲線壓縮方法是類型轉(zhuǎn)換方法 ,這種方法將坐標由浮點數(shù)轉(zhuǎn)化為整型數(shù)存儲 ,其優(yōu)點是速度可以滿足實時性要求 ,缺點是壓縮程度有限. 本文方法改進了類型轉(zhuǎn)換方法 ,在保證壓縮速度的同時進一步減小壓縮比 , 令壓縮時間和壓縮效果獲得更好的平衡. 曲線坐標的相關(guān)性強于折線坐標 ,本文方法首先使用整型小波變換不斷地計算坐標的高頻分量 , 減小數(shù)據(jù)冗余 , 然后使用FFEP(four. five ,eight . plus) 編碼進行編碼. FFEP編碼專為編碼曲線坐標高頻分量設計的編碼方法 ,該方法使用較短的碼編碼出現(xiàn)頻率較高的符號 ,使用較長的碼編碼出現(xiàn)頻率較低的符號 ,使用變長碼編碼偶爾出現(xiàn)的特殊符號 ,既保證壓縮效果 ,又增強編碼的魯棒性. 整型小波變換和 FFEP 編碼不占用額外內(nèi)存 ,只包含簡單的加減和移位運算 , 效率較高. 壓縮等高線數(shù)據(jù)的實驗表明 ,本文方法能夠在移動計算環(huán)境中實時壓縮曲線數(shù)據(jù).

更多內(nèi)容請查看pdf