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

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

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

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

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

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

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

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

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