邱國清

(漳州師范學院計算機科學與工程系, 福建 漳州 363000)

0 前 言

矢量數(shù)據(jù)結構精度高，易于空間信息的可視化表達[1].多邊形矢量編碼使邊界坐標數(shù)據(jù)和多邊形單元一一對應，各個多邊形邊界都單獨編碼和數(shù)字化，具有編碼容易、數(shù)字化操作簡單等特點，但它無法解決多邊形中嵌套多邊形這種復雜的結構.四叉樹編碼方法的優(yōu)點在于能彌補多邊形矢量編碼的缺陷，它允許在多邊形中嵌套多邊形即所謂“洞”這種結構的存在，但它最大的缺點在于編碼轉(zhuǎn)換時具有圖形編碼的不確定性，用同一形狀和大小的多邊形可能會得出多種不同的四叉樹結構，不利于形狀分析和模式識別.為了克服該缺點，本文采用霍夫曼編碼的原理，在四叉樹編碼圖的基礎上重新進行編碼，形成霍夫曼編碼樹.由于霍夫曼編碼是以二叉樹來表示的，這樣就能保證一組編碼只能對應一個霍夫曼編碼樹，從而防止了同一形狀和大小的多邊形可能出現(xiàn)多種不同的編碼樹結構，然后采用Morton碼的原理對每個節(jié)點進行表示.

圖1 復雜多邊形圖形 圖2 四叉樹編碼圖

1 四叉樹編碼圖

四叉樹編碼的基本思路是將一幅地圖等分成4等分，逐塊檢查網(wǎng)格屬性值，如果某個子區(qū)的所有格網(wǎng)值都具有相同的值，則無論該區(qū)域值是否相等都同樣繼續(xù)分割，直到每個子塊都只含有相同的屬性值[2]，如圖2所示.以圖2為例，做以下假設：屬性值為1的節(jié)點有1、2、3；屬性值為2的節(jié)點有4；屬性值為3的節(jié)點有5、6、7、8、9；屬性值為4的節(jié)點有10、11；屬性值為5的節(jié)點有12；屬性值為6的節(jié)點有13、14、15、16、17、18、19；屬性值為7的節(jié)點有20、21；屬性值為8的節(jié)點有22.

表1 概率表

2 四叉樹編碼圖轉(zhuǎn)換成二叉樹

霍夫曼編碼的基本思想[3]是按照字符出現(xiàn)概率的大小編碼，概率大的字符分配短碼，概率小的字符分配長碼來構造最短的平均碼長，以圖2為例，該圖形編碼中每個像素元的屬性值出現(xiàn)的概率大小計算如表1所示.

表2編碼過程

用霍夫曼編碼方法對屬性值進行編碼，其編碼過程如表2所示.

表2的編碼過程可用圖3的編碼樹來表示.

因為表2中的編碼只能得出一棵對應的編碼樹，從而不會產(chǎn)生形狀分析和模式識別的問題.

3 Morton碼的原理

Morton碼的原理如圖4所示， 其計算過程如圖5所示.這樣就可以行列表示2維柵格陣列圖形，用Morton碼寫成二維數(shù)組，通過Morton碼來確定節(jié)點的坐標.利用Morton碼對每個節(jié)點數(shù)字化時，如果某個節(jié)點之前已經(jīng)完成過一次數(shù)字化就不需要再重復數(shù)字化和存儲，這樣就可以保證每個節(jié)點只被數(shù)字化一次.

節(jié)點1對應的Morton碼為第1行第5列即18,節(jié)點2對應的Morton碼為第4行第6列即27,用同樣的計算方法可以計算出所有節(jié)點對應的Morton碼.將Morton碼讀入二維數(shù)組中:

Morton碼： 18 27 31 ……

霍夫曼編碼: 11 1011 11 ……

圖3 霍夫曼編碼樹

圖4 Morton碼

4 多邊形矢量編碼

圖5 Morton碼的計算過程

多邊形矢量編碼的文件編碼坐標為x1,y1；x2,y2；x3,y3;…，所以使用多邊形矢量編碼來表示時只要將與編碼坐標對應的霍夫曼編碼值依次寫入即可.

霍夫曼編碼 11 1011 11 …

多邊形矢量編碼x1,y1x2,y2x3,y3…

5 結束語

本文利用霍夫曼編碼的算法很好地克服了四叉樹編碼轉(zhuǎn)換時不利于形狀分析和模式識別的缺點,研究表明利用Morton碼的原理對圖形進行壓縮編碼效果良好.

參考文獻

[1] 王 昌，騰艷輝. 矢量柵格一體化數(shù)據(jù)結構設計與應用[J]. 計算機工程，2010，20：88-89.

[2] 閆浩文. 計算機地圖制圖原理與算法基礎[M].北京：科學出版社,2007:94-95.

[3] 付先平. 多媒體技術及應用[M]. 北京：清華大學出版社，2007：53-55.

[4] 艾自興，龍 毅. 計算機地圖制圖[M].武漢：武漢大學出版社,2005:37-45.