(中國科學(xué)院地理科學(xué)與資源研究所 北京 100101) (中國科學(xué)院研究生院 北京 100039）
論文來源：中國測(cè)繪學(xué)會(huì)九屆四次理事會(huì)暨2008年學(xué)術(shù)年會(huì)論文集
摘要:提出了應(yīng)用于曲線矢量壓縮的基于IWT(整數(shù)小波變換)的“458+編碼”方案. 該方案根據(jù)指定容限量化曲線矢量 ,然后計(jì)算一階差分后使用IWT減小矢量分量 ,最后根據(jù)矢量分量大小選擇合適的碼長按位編碼 ,解碼時(shí)可按字節(jié)解碼. 由于IWT計(jì)算機(jī)實(shí)現(xiàn)較快 ,“458+編碼”的編碼解碼速度均…
關(guān)鍵詞: 458+編碼 ; 整型小波變換 ; 曲線矢量壓縮 ; 矢量數(shù)據(jù)壓縮
曲線在CG、CAD中廣泛用于高精度建模 ,曲線可以用參數(shù)方程的形式表示 ,常用的參數(shù)曲線有: Bezier曲線、B樣條曲線非均勻有理B樣條(NURBS)曲線等 ,曲線常用于地形建模(等高線)及光滑的線狀實(shí)體建模. 曲線壓縮對(duì)模型高效存儲(chǔ)及傳輸具有重要意義. 對(duì)曲線進(jìn)行壓縮 ,能夠減小存儲(chǔ)數(shù)據(jù)所需的空間和傳輸數(shù)據(jù)所需的時(shí)間 ,提高圖形系統(tǒng)的性能. 本文提出的方法適用于二維及三維曲線 ,出于簡便考慮本文以二維曲線作為研究對(duì)象.
矢量壓縮算法主要解決三類問題: min ? ε 問題 ,限制壓縮后曲線形態(tài)點(diǎn)數(shù)求得形變最小的壓縮方案; min ? # 問題 ,限制壓縮后最大形變求得形態(tài)點(diǎn)數(shù)最小的方案; min ? rate 問題, 限制壓縮后最大形變求得編碼后碼長最短的方案.[13]-[23] 矢量壓縮可以通過兩種辦法實(shí)現(xiàn): 通過多邊形近似減少形態(tài)點(diǎn)數(shù)目; 對(duì)矢量進(jìn)行量化編碼. 前者可以用于min ? ε 、min ? # 和min ? rate 問題 ,后者只可用于min ? rate 問題. 本文提出的方法屬于量化編碼算法 ,用于解決min ? rate 問題.
min ? rate 問題解決方法存在的問題之一是算法的效率較低 ,不能較好的適用于處理器速度和受限的計(jì)算環(huán)境. 多邊形近似算法最早由Dauglas和Peucker與1973年提出[1] ,后國內(nèi)外一些學(xué)者對(duì)其進(jìn)行了改進(jìn)[2][3] ,近年來Alexander Kolesnikov和Alexander Akimov進(jìn)行了深入研究 ,并取得了較好成果[23].多邊形近似算法中獲得最佳近似多邊形的時(shí)間和空間復(fù)雜度均依賴于最短路徑算法的時(shí)間和空間復(fù)雜度 ,即均為ON2()[23] ,使用動(dòng)態(tài)規(guī)劃算法計(jì)算近似最短路徑可以簡化算法 ,簡化后算法空間復(fù)雜度為ON() ,時(shí)間復(fù)雜度為
ON()~ON( 2 )[13]-[15]. 量化編碼算法的主要研究有Shashi Shekhar等人于2002年提出的聚類算法[24][25]和Alexander Kolesnikov等人于2004年提出的基于動(dòng)態(tài)規(guī)劃的尺度量化算法[22]. 前者算法的空間復(fù)雜度為ON() ,時(shí)間復(fù)雜度大于ON().后者空間復(fù)雜度為ON() ,時(shí)間復(fù)雜度為
ON()~ON( 2 ).
min ? rate 問題解決方法存在的另一個(gè)問題是多邊形近似法和矢量量化法大都采用的熵編碼存在局限 ,如果對(duì)每一條曲線建立一個(gè)概率模型 ,如果曲線點(diǎn)數(shù)不多但曲線條數(shù)較多時(shí) ,數(shù)據(jù)冗余較小 ,熵編碼壓縮效果較差. 如果為所有的曲線建立一個(gè)概率模型, 若使用自適應(yīng)編碼 ,曲線之間建立了關(guān)聯(lián)無法隨機(jī)編碼解碼 ,若不使用自適應(yīng)編碼 ,需要額外空間存儲(chǔ)字典 ,字典有可能較大. 國內(nèi)對(duì)矢量數(shù)據(jù)壓縮算法的研究存在一些缺陷[4]-[8], 如: 誤差控制問題的解決, 有說服力的試驗(yàn)驗(yàn)證算法的壓縮比等.
更多內(nèi)容請(qǐng)查看pdf