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