邱 國 清
(閩南師范大學(xué) 計算機學(xué)院, 福建 漳州 363000)
矢柵混合模型和矢柵一體化模型是數(shù)據(jù)模型研究的兩個部分。其中,矢柵混合模型是將矢量結(jié)構(gòu)和柵格結(jié)構(gòu)的數(shù)據(jù)不加任何處理分別存儲在同一個空間數(shù)據(jù)庫中,當(dāng)需要使用時只需將兩種數(shù)據(jù)分別調(diào)入,這樣就可以極大地提高地圖編輯對象的信息量和準(zhǔn)確性,矢柵混合模型已經(jīng)在GIS和制圖中得到了廣泛的應(yīng)用,但該模型數(shù)據(jù)重復(fù)存儲占用了大量的存儲空間[1],為了彌補該缺點,提出了將存儲空間中的矢量數(shù)據(jù)和柵格數(shù)據(jù)進(jìn)行編碼處理,同時對這兩種編碼進(jìn)行壓縮,以達(dá)到減少存儲空間和提高效率的目的。
圖1:復(fù)雜多邊形圖形
矢量數(shù)據(jù)結(jié)構(gòu)是通過記錄坐標(biāo)的方式,盡可能精確地表示點線多邊形等地理實體[2],該數(shù)據(jù)結(jié)構(gòu)精度高,易于空間信息的可視化表達(dá)[3]。矢量數(shù)據(jù)的編碼及壓縮比較簡單而且方法有多種。
柵格數(shù)據(jù)結(jié)構(gòu)又稱為網(wǎng)格數(shù)據(jù)結(jié)構(gòu),每個小方格用(x,y)坐標(biāo)表示,其最明顯的特點就是屬性明確,定位隱含[4]。
四叉樹編碼方式是柵格數(shù)據(jù)編碼最常用的方法之一,該編碼方式將圖形分為四個部分,逐塊檢查其格網(wǎng)屬性值,但該編碼方式最大缺點在于轉(zhuǎn)換的不定性,同一個圖形可能會有多種不同的四叉樹,這樣就不利于形狀分析和模式識別,為此還需要將四叉樹轉(zhuǎn)換成二叉樹,這樣就能保證只得出一棵對應(yīng)的編碼樹。
利用霍夫曼原理[5]將四叉樹轉(zhuǎn)換成二叉樹,該基本原理是按照字符出現(xiàn)概率的大小,概率大的字符分配短碼,概率小的字符分配長碼來構(gòu)造最短的平均碼長,以圖1為例,假設(shè)點1、2、3的屬性值為1,點4、5、6、7的屬性值2,點8、9、10、11的屬性值為3,點12的屬性值為4,該圖形編碼中每個像素元的屬性值出現(xiàn)的概率大小計算如表1所示。
表1:概率表
用霍夫曼編碼方法,對屬性值進(jìn)行編碼,其編碼過程如表2所示。
表2:編碼過程
表2的編碼過程可用圖2的編碼樹來表示。
圖2:霍夫曼編碼樹
Morton碼的計算如下[6]:
圖3:Morton碼
圖4:Morton碼的計算過程
這樣就可以行列表示二維柵格陣列圖形,用Morton碼寫成二維數(shù)組,通過Morton碼來確定節(jié)點的坐標(biāo)。
圖5:復(fù)雜多邊形轉(zhuǎn)化后的編碼
對于矢量數(shù)據(jù)結(jié)構(gòu)才采用元子空間填充來表達(dá)。圖1是復(fù)雜多邊形的原始矢量數(shù)據(jù)結(jié)構(gòu),采用元子空間填充后,轉(zhuǎn)化成圖5復(fù)雜多邊形的十進(jìn)制四叉樹。
柵格數(shù)據(jù)結(jié)構(gòu)本身就可以直接采用十進(jìn)制四叉數(shù)編碼方式存儲,假設(shè)圖1中點1、2、3、4、5、6、7的屬性值為,點8、9、10、11、12的屬性值為2,其它都為0,那么多邊形圖形的柵格結(jié)構(gòu)為圖6所示,
圖6:多邊形圖形柵格數(shù)據(jù)結(jié)構(gòu)
通過圖5和圖6可以看出,將矢量數(shù)據(jù)結(jié)構(gòu)采用元子填充后,矢量數(shù)據(jù)和柵格數(shù)據(jù)都可以采用十進(jìn)制四叉樹編碼,從而保證了編碼的一致性。
矢柵混合模型中的矢量數(shù)據(jù)和柵格數(shù)據(jù)轉(zhuǎn)換同樣的編碼,對于重復(fù)的數(shù)據(jù)不需要在同一個數(shù)據(jù)庫中反復(fù)存儲,節(jié)省了存儲空間,混合模型中數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換成同一個格式,這樣在數(shù)據(jù)處理更加方便,提高了編碼的效率。
〔參考文獻(xiàn)〕
[1]閆浩文,等. 計算機地圖制圖原理與算法基礎(chǔ)[M].北京:科學(xué)出版社,2007:108-109.
[2]何嘉珈. 矢柵數(shù)據(jù)一體化存儲技術(shù)研究[J].科技資訊,2009,(26):233.
[3]王昌、滕艷輝. 矢量柵格一體化數(shù)據(jù)結(jié)構(gòu)設(shè)計與應(yīng)用[J]. 計算機工程,2010,20(36):88-89.
[4]王建、杜道生. 矢量數(shù)據(jù)向柵格數(shù)據(jù)轉(zhuǎn)換的一種改進(jìn)算法[J].地理與地理信息科學(xué),2004,20(1):31-34.
[5]付先平. 多媒體技術(shù)及應(yīng)用[M]. 北京:清華大學(xué)出版社,2007:53-55.
[6]艾自興,龍毅. 計算機地圖制圖[M].武漢:武漢大學(xué)出版社,2005:37-45.