一種二維矢量數據的壓縮方法

2023-07-25 09:53:01

專利名稱：一種二維矢量數據的壓縮方法
技術領域：
本發明涉及信息處理領域，特別是一種二維矢量數據的壓縮方法。
背景技術：
1.GIS中二維矢量數據的特點及對其進行壓縮的必要性二維空間矢量數據是當前地理信息系統所管理和應用的主要數據類型之一，具有數據量大、分布不均勻、拓撲關係複雜等特點。GIS中矢量數據一般由坐標串的形式表示，其中的坐標數據一般為浮點格式，隨著獲取數據的能力提高以及用戶對數據精度的要求，為了更好地表達現實地理世界，GIS矢量數據量極為龐大，需要大量的存儲和傳輸資源。在地理信息的網絡服務(參見文獻[1])等新興的GIS應用領域，矢量數據需要經由帶寬受限和不穩定的Internet連接傳送給用戶，需要傳送的矢量數據的數據量大小成為決定應用成敗的關鍵，直接採用原始的坐標數據作為二維空間矢量數據的載體無法滿足要求。
在圖像、視頻和音頻等多媒體數據領域，目前均有成熟的國際標準，如JPEG、JPEG2000、MPEG1/2/4、H.263/4等等。這些標準在提供了一種對龐大的多媒體數據的有效的具備高壓縮比和高性能的壓縮方法的同時，也提供了巨大的商業機會，使得基於這些多媒體數據的在線瀏覽和實時應用成為可能。對GIS矢量數據，目前還沒有這樣一種專門的壓縮方法能夠在不損失矢量數據所蘊涵的地理信息的前提下有效地減小矢量數據的數據量。這不僅影響了空間數據的存儲和管理效率，也成為地理信息網絡服務的瓶頸，大大阻礙了地理信息系統與Internet分布式應用的結合。
在這一背景之下，通過對二維空間矢量數據內部的複雜性分析和信息構成的分解以及對現有多媒體壓縮技術的利用和在矢量數據壓縮方面的革新，本發明提出了對二維矢量數據進行基於塊變換編碼的壓縮方法。
2.二維矢量數據的特點分析及壓縮方案選擇與圖像數據相比，二維矢量數據具有複雜的內部結構。矢量數據文件由位於地圖繪製範圍內部所有感興趣的矢量對象構成，這些矢量對象內部的點的排列是有序的，然而矢量對象在矢量數據文件內部的排列則是無序的。
眾所周知，在圖像數據中，其冗餘的一個主要表現形式就是相鄰象素之間灰度值上的相關性。現行的圖像壓縮國際標準採用了塊變換編碼方法，通過將圖像數據從空間域變換為頻率域近似不相關的變換係數，然後對變換係數進行獨立的標量量化來利用這種相關性。這一方法避免了直接採用理論上最優的但是計算量太大的矢量量化方法，同時也有效利用了原始數據內部的相關性，是一種實際的「最優」方案。
我們發現，在構成矢量數據的採樣點坐標序列數據中也存在著很強的長序列相關性，因而也存在著大量的冗餘。作為現實地理世界的數位化表示，這些坐標序列表明了地理對象(如河流、道路等)的變化趨勢。由於平緩性變化和周期性變化在地理對象中的大量存在，使得矢量數據內部採樣點坐標數據序列也具有了相應的特點並表現出我們前面所說的相關性，也表明對矢量數據進行壓縮是可行的。
對矢量數據進行壓縮並不是直接將成熟的圖像數據壓縮算法移植到矢量數據上那麼簡單。無論數據量多麼大的圖像數據都可以看成一個具有若干個分量(如RGB)的二維矩陣，而這種規則的內部結構是矢量數據所不具備的。因此，尋求矢量數據的有效壓縮表示，必須充分考慮到矢量數據的結構對壓縮算法和壓縮性能的影響。
在選擇矢量數據壓縮方案中所採用的線性變換時，如眾多圖像壓縮算法一樣我們也採用了DCT(離散餘弦變換，英文縮寫)變換。儘管從去相關的意義上講KL變換(Kahunen-Loéve)是最優的線性變換[2]，但是KL變換的變換矩陣與所需要進行處理的數據的統計特徵有關，不能事先確定，並且其計算到目前為止尚不存在快速算法。理論證明對一階Markov信號，當其相關係數ρ接近於1時DCT變換是對KL變換的良好的近似。實驗表明對矢量數據採用一階Markov過程進行建模時其相關係數確實很接近於1，並且由於DCT變換矩陣可以事先確定，其計算有多種快速算法，因此從理論上到實踐上採用DCT變換對矢量數據進行壓縮都是可行的。
3.量化與二維矢量數據壓縮的失真量化過程會產生精度的損失，儘量減少失真是二維矢量數據壓縮追求的目標之一。目前在多媒體數據的有損壓縮中多採用MSE(Mean Square Error，均方誤差)作為失真度量[3]，也有其它的準則，這些準則各有其優缺點。如MSE準則，它具有計算簡單，物理意義明確、便於進行優化等優點，它突出的缺點則是在某些方面與人類感知特性不符合，較大的MSE值不一定對應了較差的感知質量。此外，MSE體現了一種「平均」的效果，即整體的失真達到了所給定的標準，因此，MSE無法對單個象素或者音頻採樣值的誤差進行局部的控制，可能在重建圖像或者重建音頻中有個別的數據誤差較顯著，但是整體上卻是符合失真控制的要求的。
對矢量數據的DCT變換係數，採用不同的量化表進行均勻量化會得到不同的壓縮結果，得到不同的失真。本專利申請，不特別指定量化表，也不特別指定失真的度量標準。
4.矢量數據的漸進壓縮和傳輸漸進壓縮和傳輸是近年來應用於多媒體數據的一項新興的技術，其特點是根據用戶的要求以及網絡帶寬、顯示和計算設備的能力等因素，傳輸合適大小的數據給用戶。這一傳輸過程隨時可以由用戶所中止，而所獲得的數據則構成了原多媒體數據的一個壓縮的表示。這一技術的優點在於用戶可以實時地獲得原始數據的壓縮表示，而不必等待整個數據傳輸完成，這對於低帶寬的用戶是尤其重要的。這一技術的運用需要對多媒體數據進行內在的組合，JPEG2000圖像壓縮標準對這一技術提供了良好的支持(參見文獻[4])。
對於矢量數據，很多研究者提出的漸近傳輸方案僅限於對空間數據點的取捨和傳輸，也就是說僅限於空間域的漸進表示，它與矢量數據現有的原始的存儲方式密切相關的。由於沒有深入的矢量數據頻率域表示方式作為支撐，因此這些漸進傳輸方案無法涉及到在矢量數據頻率域表示基礎上開展的頻率域漸進傳輸方式。
綜合以上來看，將變換編碼方法應用於二維空間矢量數據的壓縮，其技術關鍵在於矢量數據的頻率域分析、冗餘分析、矢量數據壓縮失真的評定、適合於矢量數據編碼的碼率分配算法、矢量數據頻率域漸近傳輸等等。就以上這些問題，目前研究者還沒有提出完整的解決方案，只是在對空間資料庫、空間數據網絡服務、WebGIS等等的研究中有所涉及，但是沒有進行深入的研究，更加沒有形成系統的方法。

發明內容
本發明所要解決的技術問題是通過對二維空間矢量數據的頻率域分析和信息構成的分解，借鑑多媒體壓縮技術，提出矢量數據壓縮方案，提供一種基於變換編碼的新型二維空間矢量數據壓縮方法，實現二維矢量數據的快速和有效的存儲、管理和傳輸。
本發明解決上述技術問題的技術方案是將二維矢量數據分塊後，使用基於DCT變換的編碼方法對二維矢量數據進行有損壓縮，並輸出為指定格式的二進位位流。
本發明提出的對二維矢量數據進行基於變換編碼的壓縮方法，具有以下顯著的效果其一.經過測試，在對等高線、道路網、水系等範圍廣泛的自然形成的矢量數據達到了近20的壓縮比的情況下，其信噪比高達60dB，最大絕對失真僅為原矢量數據動態範圍的10-5數量級左右；其二.對二維空間矢量數據的自適應分塊在不破壞空間數據自身的複雜結構的同時生成了適合於塊變換編碼的矢量數據塊；其三.採用合適的量化方法，可以控制重建誤差，從而控制壓縮過程中所產生的失真；其四.結合空間域和頻率域的漸進壓縮技術，為靈活和高效的矢量數據漸近傳輸提供技術基礎。通過結合空間域和頻率域矢量數據的表示所提出的新的更加高效的漸近傳輸方案可以更好地滿足用戶的需求。


圖1本發明壓縮方法的基本流程2分塊算法框圖，其中N為2n，n為壓縮前指定。
圖3矢量數據壓縮主程序框圖。
圖4按照給定精度將壓縮矢量數據塊進行分節示意圖。
圖5jvg壓縮文件結構。
圖6壓縮前的數據。
圖7壓縮後解壓得到的數據。
圖8壓縮前和壓縮後數據的重疊顯示。其中壓縮前為黑色，壓縮後為灰色，灰色線旁邊的黑色點以及短線為失真導致的不完全一致。
圖9放大3倍後的一個局部數據重疊顯示。
圖10放大8倍後的一個局部數據重疊顯示。
具體實施例方式
下面結合實例及附圖對本發明作進一步說明。
本發明是一種二維空間矢量數據的壓縮方法，具體是首先將原始矢量數據劃分為矢量數據塊，再按照兩種模式之一對矢量數據塊進行基於DCT變換的有損壓縮，然後對得到的DCT變換係數進行熵編碼得到壓縮矢量數據塊，最後將所有壓縮矢量數據塊組織為指定格式的二進位位流，圖1是本發明中壓縮方法的基本流程圖。
本發明採用如下步驟對二維矢量數據壓縮。
一.二維矢量數據集分割為矢量數據塊(簡稱分塊)1.二維矢量數據的整理本發明所處理的原始矢量數據是一個包含一個或多個幾何對象(一般是多個)的數據集，可以是一個文件，也可以是二進位或文本數據流。一個幾何對象由一個或者多個獨立的部分組成(例如，帶有島的多邊形、河流的分叉等)，每個部分由數量不等的點按照存儲的順序連接而成。
如果要壓縮的數據不符合上述模型，採用本發明技術前，必須預先進行整理，或者在實施壓縮的過程中實時整理為指定的格式。
2.二維矢量數據集劃分為矢量數據塊將二維矢量數據劃分為矢量數據塊的過程就是將每個幾何對象分別按照壓縮算法的需要劃分為相同大小的多個矢量數據塊。為了便於進行DCT變換的快速計算，每個矢量數據塊中都含有2n個二維數據點，n為大於1的整數，在壓縮前指定。
為了與矢量數據的原有結構相一致，分塊在矢量對象內部進行。幾何對象(及其各個部分)中存儲的點的數目不可能都是2n的倍數，從各個部分順序提取矢量數據塊後，對各個部分剩餘的點，人為補充足夠數量的點以構成一個完整的矢量數據塊，分塊算法見圖2。圖2中的N為2n。分塊算法依次遍歷一個幾何對象的每個部分，按點的原始順序提取2n大小的矢量數據塊，其中所有點完全來自某一個部分的矢量數據塊，稱為GDB(GeometryData Block)。對每個部分提取GDB後剩餘的不足2n的點，人為補充足夠數量的點後再構成一個完整的矢量數據塊，稱為GSDB(Geometry Supplement Data Block)。補充的點的坐標等於GSDB中原有的所有點的坐標的平均值。對GDB和GSDB兩種矢量數據塊的壓縮是一樣的，但是在形成的壓縮矢量數據文件中，壓縮矢量數據塊的頭部包含了指示該塊的類型以及該塊中實際包含的數據點的數量的信息。
二.基於DCT變換的有損壓縮(簡稱編碼)參見圖3，採用下述步驟對矢量數據壓縮。
1.DCT變換對所有矢量數據塊，選擇兩種模式之一對x和y坐標數據分別進行一維DCT變換。第一種模式是首先對矢量數據塊的數據進行量化，然後對量化數據進行無損的整數DCT變換；第二種模式是直接使用有損的浮點DCT變換，變換之後進行量化，如果不考慮浮點運算中的捨入誤差，浮點DCT變換也可以看成是無損的，但是後續的對變換係數的量化則是有損的。
一維序列x(i)，i＝0，1，ΛN-1的DCT變換及逆變換為X(k)=cki=0N-1x(i)cos(2i+1)k2N]]>x(i)=k=0N-1ckX(k)cos(2i+1)k2N]]>其中c0=1/N,ck=2/N,1kN-1.]]>整數DCT變換由浮點DCT變換推導而得，具體可以參見文獻[6]。本專利並不限制具體使用的整數DCT變換的類型以及其中的參數，只要正向整數DCT變換(Forward IntegerDCT)和逆向整數DCT變換(Inverse Integer DCT)相互對應即可。
2.量化及其重建第一種模式中的量化，以x分量的均勻量化為例，其方法是假定當前的矢量數據在x方向的範圍為[XMIN，XMAX]，指定x數據的量化步長為Δx，那麼對所有矢量數據塊中的x數據進行以下的量化 其中 是向下取整運算，後繼的變換和編碼對qx(i)進行，並且是無損的。
對壓縮矢量數據文件解壓後得到了qx(i)，將其重建為原量化區間中點，也就是x^(i)=qx(i)x+XMIN]]>第二種模式中的量化，以x分量的均勻量化為例，其方法是假設當前的矢量數據經過浮點DCT變換後的DCT係數是X(k)，k＝0，1，Λ，N-1，指定量化步長為Δix，那麼對所有X(k)進行以下的量化 其中 是向下取整運算，後繼的編碼對Qx(k)，k＝0，1，Λ，N-1進行，並且是無損的。要注意此時對於x坐標數據的不同的變換係數其量化步長一般是不同的，而不象直接對坐標數據進行量化那樣只有一個量化步長。
同樣地，對壓縮矢量數據文件解壓後得到QX(k)，將其重建為原量化區間中點，也就是X^(k)=QX(k)kX]]>注意無論是第一種模式還是第二種模式，對矢量數據塊的有損壓縮都得到了一組整數DCT變換係數。在後繼的無損熵編碼(第一層編碼)中將不再區分這兩種模式，而統一地將這些係數稱為整數DCT變換係數。對於有損量化，本專利並不特別指定量化的步長和量化失真的度量，不同的量化步長會產生不同的量化失真，在不同的失真度量下壓縮效果也不盡相同。如何通過設定失真度量和優化量化方法，是本專利的壓縮技術框架下開放的內容。
量化的參數一般是隨矢量數據的不同而不同的，不同的量化參數將產生不同的量化變換係數和最後的壓縮效果，因此本專利也不特別限定特別的量化參數，專利的用戶可以根據需要選擇量化參數或選擇參數的方法。
3.DC係數的處理DCT變換係數可以分為兩類，第一個係數稱為DC係數，是參加變換的所有數據的均值；其它的係數稱為AC係數。由於DC係數直接與矢量數據塊的位置相關，因此同一個幾何對象的所有矢量數據塊的DC係數之間往往具有很強的相關性，適合於採用預測編碼來進行壓縮。在本發明中，在一個幾何對象(包括其多個部分)中，除了第一個矢量數據塊中的DC係數之外，對所有後繼矢量數據塊的DC係數均計算其與前一個壓縮數據塊的DC係數的差值，然後對該差值進行霍夫曼編碼。
差值霍夫曼編碼表的示例見附表1。該表的第一列是行號，第三列是該行的霍夫曼碼字，每行包含整數區間(-(2i-1)，+(2i-1))，但是不包含中間區間(-(2i-1-1)，+(2i-1-1))。對差值進行編碼的碼字包括兩個部分，第一部分為該差值所在行的一元霍夫曼碼字；第二部分是該差值的二進位反碼(不需要符號位)。對於一個幾何對象中第一個矢量數據塊中的DC係數，直接使用該表進行編碼。該編碼方法可以參見文獻[6]。DC係數的差值霍夫曼編碼可舉例說明如下。假定當前幾何對象中第一個矢量數據塊的DC係數為1787，第二個矢量數據塊的DC係數為1783，對第一個矢量數據塊的DC係數進行直接編碼得到111111110|11011111011，第二個矢量數據塊中實際編碼的是這兩者之間的差值-4，編碼為100|011。
4.第一層編碼對每個矢量數據塊，經過第一種模式或者第二種模式的有損壓縮後都將得到兩個整數DCT變換係數塊(分別對應於x和y坐標數據)。該塊的第一個分量是DC係數，其處理已經在前面論述，剩下的所有AC係數按照如下方式進行無損的遊程霍夫曼編碼。
首先將AC係數塊分割為(非零係數，零遊程長度)對。零遊程長度表示在該非零係數前面為零的AC係數的個數。對每個對，首先找到非零係數在差值霍夫曼編碼表中的行數R，然後在遊程霍夫曼編碼表中找到對應於Z/R(Z為行號，R為列號)位置的碼字，其中Z為零遊程的長度。在該表中，R從1開始計數，Z從0開始計數。該碼字後面加上非零係數的反碼(不需要符號位)就是這個對的編碼。AC係數塊最後的一串零(個數不定，也可能是0個)以EOB(End Of Block，塊結束)表示。遊程霍夫曼編碼表包括了(零遊程長度，非零係數所在行)對和EOB的霍夫曼碼字。一個遊程霍夫曼編碼表的示例見附表2。AC係數塊的遊程霍夫曼編碼可舉例說明如下。假定DCT變換塊的尺寸N＝16，欲編碼的AC係數塊為10，0，0，2，0，0，0，0，0，0，0，0，0，0，0，那麼該塊被劃分為2個(非零係數，零遊程長度)對和一個EOB。第一個非零係數10的前面沒有零係數，它位於差值霍夫曼編碼表中第4行，因此在遊程霍夫曼編碼表中其對應的碼字是在0/4處的1011，其編碼為1011|110。同樣得到後面的非零係數2的編碼為11111001|10。最後這串AC係數被編碼為101111011111001101010其中最後的1010是EOB的編碼。
此外，零遊程的長度不得超出15，如果超出則用一個碼字ZRL來表示之，並重新開始對零遊程長度計數。舉例來說，假如兩個非零AC係數之間有17個零AC係數，那麼被分割為一個ZRL和一個零遊程長度為2的(非零係數，零遊程長度)對。
5.第二層編碼假如在第一層編碼結束後直接將得到的位流輸出為二進位文件，那麼所得到的壓縮矢量文件將具有唯一的精度。只有將整個文件解壓縮之後，才能得到具有給定精度的解壓矢量文件，而僅僅解壓一部分壓縮位流則得不到對原矢量文件的有意義的表示。通過對壓縮位流的重新組織，可以使壓縮位流進行部分解壓後，得到較低精度或者較小範圍的解壓矢量文件。而如果用戶需要更高精度或者更大範圍的矢量數據，則可以進一步對剩下的壓縮位流進行解壓直至結尾。這一組織方式使得壓縮位流具有漸進性質，用戶可以按照其需要選擇相應的位流進行解壓，而不必一定要對整個文件進行解壓才可以使用。上述按照矢量數據的精度或者範圍對壓縮位流進行組織以使得輸出位流具有近似的漸進性質的過程稱為第二層編碼。
第二層編碼通過對壓縮矢量數據塊的分割實現。假定原壓縮矢量數據所達到的精度為εtotal，該εtotal指解壓後的所有數據點與原數據點之間在x方向和y方向誤差不超出的某一事先給定的閾值(例如，10-5)。給定一組S個從低到高的精度等級{ε1，ε2，Λ，εS}，其中εS＝εtotal。那麼所有壓縮矢量數據塊都將被分割為S節，使得當僅解壓第1節時，解壓數據達到了ε1的精度等級，依次類推。同樣地，對整個壓縮矢量數據文件，當將其中所有的壓縮矢量數據塊都解壓到第k(1≤k≤S)個精度等級時，整個解壓矢量數據文件也達到了第k個精度等級。因此將壓縮矢量文件(或者其某個範圍，在下文中說明)的所有壓縮矢量數據塊中屬於第k節的壓縮位流的集合稱為該壓縮矢量文件(或者其某個範圍)的第k段。在分割單個壓縮矢量數據塊後形成的節中包含了若干個(非零係數，零遊程長度)對的編碼，也可能是零個，但是分割不能打斷(非零係數，零遊程長度)對的編碼。形成節之後在這些節的最後必須加上EOB的碼字(在上面的例子中，是1010)，假如該節是空的，那麼直接用EOB表示該節。一個具有五個精度等級的分割的示意圖見圖4。精度等級的確定以及根據確定的精度等級對壓縮矢量數據塊進行分割的方式都可以由應用所指定，不是本專利的內容。
本發明中對矢量數據進行第二層編碼有兩種方式，分別是精度優先方式以及範圍優先方式。在精度優先方式中，整個矢量數據的低精度版本首先被解壓，然後解壓的數據將逐步提高整個矢量數據的精度。在範圍優先方式中，首先將整個矢量數據分割為幾個範圍，所有範圍互不重疊，都是由若干個幾何對象組成。然後對每個範圍實行精度優先的組織。範圍的劃分由應用確定，不是本專利的內容。由於精度優先方式也可以看作是將整個文件視為一個範圍，因此可以認為壓縮矢量數據位流由一個或者多個範圍組成，而一個範圍則由一個或者多個段組成。
下面舉例說明這兩種第二層編碼方式。假定有矢量數據A中包含了三個幾何對象A1，A2，A3。所有幾何對象都被按照三個精度層次劃分為三節，即Aiji，j＝1，2，3，表示第i個幾何對象的第j節。在範圍優先方式下A被分割為兩個範圍，分別包含幾何對象A1，A2和幾何對象A3。如果按照精度優先方式，那麼在壓縮文件中所有節的排列方式為A11，A21，A31，A12，A22，A32，A13，A23，A33如果按照範圍優先方式，那麼在壓縮文件中所有節的排列方式為A11，A21，A12，A22，A13，A23，A31，A32，A33三.壓縮矢量數據的輸出對所有壓縮矢量數據塊，在給定的編碼方式下添加各種標記和控制信息並進行組織後就形成了最後的矢量數據壓縮文件，稱為jvg文件，由文件頭和文件體組成(見圖5)。下面對jvg文件的格式作詳細的說明。所有的字節均具有Intel平臺上使用的littleendian字節順序(最顯著位在字節的最後面)。
參見附表3，壓縮文件的文件頭包含了如下的兩部分第一部分是關於壓縮矢量數據文件整體以及所採取的壓縮算法的信息。
這一部分是必需的。這裡以及在後續碼流的形成中用到的標記由兩個字節組成，其中第一個字節為0XFF，第二個字節在除了0X00和0XFF(即全0和全1的字節)之外的範圍內取值，具體見附表3。
第二部分是壓縮算法所需要的表，包括DCT變換係數量化表、對DC係數差值和AC係數進行無損熵編碼的編碼表。
這一部分是可選的。如果不給出這些表，那麼可能由壓縮和解壓程序從另外的默認途徑獲得。具體說明如下首先是DCT變換係數量化表的定義。量化表的定義由標記DQT(參見附表4)開始，第一種方式下定義的量化表由一個雙精度浮點常數C和N(N為DCT變換塊尺寸)個整數組成，每個DCT變換係數的對應量化步長為C乘以對應位置的整數；第二種方式下定義的量化表由N個雙精度浮點數組成，這些數即為對應DCT變換係數的量化步長。
然後是DC係數差值霍夫曼編碼表的定義。為了保存該表，首先給出一個一字節無符號整數表示該表的行數R，每行包含的差值可以直接由該行的行號計算得到，因此不需要保存。接下來是R個一字節無符號整數，表示每行所對應的霍夫曼碼字的長度。霍夫曼碼字的長度不允許超過16。最後將所有碼字按照順序各以兩個字節進行保存，真正的碼字位於這兩個字節的低端，由於碼字長度不允許超過16，因此兩個字節是足夠的。以附表1為例，首先保存的字節為0X11(17的十六進位表示)，然後是下面17個字節，表示各個碼字的長度0X02，0X03，0X03，…接下來的34個字節為0X00，0X00，0X00，0X02，0X00，0X03…最後是AC係數遊程霍夫曼編碼表。為了保存該表，首先給出兩個一字節無符號整數表示該表的行數R和列數Z。R代表了非零AC係數在DC係數差值霍夫曼編碼表中的最大行數，Z代表了非零AC係數前面的零遊程的最大長度。然後，接下來再按照行優先的順序保存該表中的RZ個碼字，並在(0，0)位置(也就是表的開頭)插入保存EOB的碼字，在(0，15)處插入保存ZRL的碼字。共計RZ+2個碼字。保存這些碼字時，同樣首先保存RZ+2個表示對應碼字長度的一字節無符號整數，然後將所有碼字按照順序各以兩個字節保存。
如果上述的量化表和編碼表均在壓縮文件中給出，那麼將有六個表(分別對應x和y坐標數據)。
jvg文件的文件體包含了實際的壓縮矢量數據。如果為第一層編碼，那麼該部分僅有一個壓縮矢量數據段，該段由一到多個壓縮矢量數據塊組成。如果為第二層編碼，那麼該部分有一到多個範圍，每個範圍由一到多個段組成，每個段按照順序由一到多個壓縮矢量數據塊的節組成。在文件體中，需要一些標記以表示不同的範圍和段的開始和結束，而每個節均由EOB結尾。
下面首先就第一層編碼中的壓縮矢量數據塊作一些說明。由前面的分塊算法可知壓縮矢量數據塊可能由GDB或者GSDB處理而來，而該GDB或者GSDB又可能位於一個幾何對象中不同的部分，這些信息需要在壓縮矢量數據塊中加以保存。為此在每個壓縮矢量數據塊的開頭附加兩個比特，其意義如附表5所示，如果該壓縮矢量數據塊由GSDB壓縮而來則下一個字節保存該壓縮矢量數據塊中的實際包含的點數。由於一個GDB或者GSDB將產生兩個壓縮矢量數據塊(分別對應x和y坐標數據)，並且這兩個塊總是相繼的，因此僅在前一個塊的開頭保存這些信息。由塊頭部信息以及GSDB中包含的點數信息即可重建由多個部分組成的幾何對象。此外如果將一個壓縮矢量數據塊根據精度要求劃分為多個節，那麼僅在第一節中保存原塊頭部信息。
在確定了採用第一層還是第二層編碼以及具體將整體矢量數據分割為範圍以及將各個範圍內的壓縮矢量數據塊分割為節並組合為段的方式之後即可將所有位流組織為文件體。附圖5是文件體的一個示例。在壓縮文件中難以發現各個幾何對象之間的邊界，但是在解壓時可根據各個壓縮矢量數據塊的頭部信息將解壓後的坐標點列組合為幾何對象。
最後還有兩點需要說明。一是jvg文件中各個編碼單元(如壓縮矢量數據塊或者分割該塊所形成的節)都必須是字節對齊的，因此如果編碼單元的位數不是8的整數倍，那麼必須在該編碼單元最後補充足夠的0以使其位數為8的整數倍。二是為了避免混淆編碼單元中的位流和壓縮文件中的標記(見前面的定義)，規定假如編碼單元中如果出現了0XFF字節(也就是一個全為1的字節)，那麼在該字節後面插入一個全為0的字節。因此如果解碼器遇到一個0XFF字節，如果其後面的字節為0X00，那麼應當直接拋棄這個字節，如果不是，那麼應當解釋將這兩個字節解釋為一個標記並根據該標記的值採取相應的動作。圖6至圖10是一個用本專利技術壓縮實際河流數據的例子，採用第一層編碼，壓縮前的大小為5,831,572位元組(5.56M)，壓縮後的大小為269,716位元組(264kB)，包括了文件頭和量化表、編碼表等，壓縮比達到了21.6。
附表附表1差值霍夫曼編碼表示例

附表2AC係數遊程霍夫曼編碼表示例

附表3 jvg文件頭

附表4jvg文件中所使用的標記

附表5 壓縮矢量數據塊頭部信息

參考文獻[1]H.Wu，Hanwu Zhang，Xiaojing Liu，Xia Sun，Adaptive Architecture of GeospatialInformation Service over the Internet with QoGIS Embedded，inISPRS Workshopon Service and Application of Spatial Data Infrastructure，XXXVI(4/W6)，Oct14-16，2005，Hangzhou，China[2]胡廣書.數位訊號處理——理論、算法與實現.北京清華大學出版社，1997[3]A.Ortega and K.Ramchandran，Rate Distortion Methods for Image and VideoCompression，IEEE Signal Proc.Magazine，pp.23-49，Nov.1998. M.Rabbani and R.Joshi，An Overview of the JPEG2000 Still Image CompressionStandard，Signal ProcessingImage Communication，vol.17，issue.1，pp.3-48，Jan.2002. V.K.Goyal，Theoreticai Foundations of Transform Coding，IEEE SignalProcessing Magazine，pp.9-21，Sept.2001. Y.Zeng，L.Cheng，G.Bi，and A.C.Kot，Integer DCTs and Fast Algorithms.IEEETransactions on Signal Processine，vol.49，no.11，pp.2774-2782，Nov.2001. David Salomon[美]著，吳樂南等譯，數據壓縮原理與應用.北京電子工業出版社，200權利要求
1.一種二維空間矢量數據的壓縮方法，其特徵是將二維矢量數據分塊後，使用基於DCT變換的編碼方法對二維矢量數據進行有損壓縮，並輸出為指定格式的二進位位流，DCT是離散餘弦的英文縮寫；具體步驟如下(1)將二維矢量數據劃分為矢量數據塊，後續的編碼過程針對每個矢量數據塊單獨地進行，這一步稱為分塊，(2)對每個矢量數據塊中的x和y坐標數據進行基於DCT變換的有損壓縮，這一步稱為編碼，(3)對所有編碼得到的壓縮數據塊添加各種標記和控制信息形成壓縮位流，輸出到二進位的壓縮矢量數據文件，這一步稱為輸出。
2.根據權利要求1所述的二維矢量數據的壓縮方法，其特徵是採用以下步驟分塊對所處理的二維矢量數據，以矢量數據內部所包含的矢量對象為單位，按照壓縮算法的需要劃分為相同大小的矢量數據塊；每個矢量數據塊中都含有2n個二維數據點，為了與矢量數據的原有結構相一致，分塊在矢量對象內部進行，不足2n個數據點的矢量數據塊人為補充一些數據點後構成一個完整矢量數據塊；n為大於1的整數，在壓縮前指定。
3.根據權利要求1所述的二維矢量數據的壓縮方法，其特徵是採用以下步驟編碼a.對所有矢量數據塊，選擇兩種模式之一對x和y坐標數據分別進行一維DCT變換；第一種模式是先對坐標數據進行量化，然後對量化後的整數坐標數據進行無損整數DCT變換，得到整數變換係數；第二種模式是直接對坐標數據進行浮點DCT變換，得到浮點變換係數，b.對第二種模式處理得到的所有變換係數進行均勻量化，得到量化變換係數，c.對每個矢量數據塊的量化變換係數或者第一種模式中的整數變換係數按順序逐塊進行無損熵編碼，生成壓縮矢量數據塊，由步驟a、b和c組成的編碼過程稱為第一層編碼，或者，d.按照矢量數據的重建精度遞增的要求進一步組織壓縮矢量數據塊，使得壓縮位流具有漸進性質，這樣，由步驟a、b、c和d組成的編碼過程稱為第二層編碼；第二層編碼僅針對第二種模式下得到的量化變換係數。
4.根據權利要求1所述的二維矢量數據的壓縮方法，其特徵在於輸出對有損壓縮數據塊添加各種標記和控制信息，並將得到的二進位位流輸出到指定格式的壓縮文件，擴展名為jvg；該壓縮文件由文件頭和文件體兩個部分組成。
全文摘要
本發明是一種二維矢量數據的壓縮方法，具體是首先將原始矢量數據劃分為矢量數據塊，再按照兩種模式之一對矢量數據塊進行基於DCT變換的有損壓縮，然後對得到的DCT變換係數進行熵編碼得到壓縮矢量數據塊，最後將所有壓縮矢量數據塊組織為指定格式的二進位位流。本發明的主要效果是在對等高線、道路網、水系等範圍廣泛的自然形成的矢量數據達到了近20的壓縮比的情況下，其信噪比高達60dB，最大絕對失真僅為原矢量數據動態範圍的10
文檔編號H03M7/30GK1777038SQ20051001993
公開日2006年5月24日 申請日期2005年12月1日 優先權日2005年12月1日
發明者吳華意, 朱海軍, 劉異 申請人:武漢大學