復(fù)雜多邊形圖形矢量數(shù)據(jù)結(jié)構(gòu)編碼方式的改進(jìn)

邱國(guó)清

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

0 前 言

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

圖1 復(fù)雜多邊形圖形 圖2 四叉樹(shù)編碼圖

1 四叉樹(shù)編碼圖

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

表1 概率表

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

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

表2編碼過(guò)程

用霍夫曼編碼方法對(duì)屬性值進(jìn)行編碼，其編碼過(guò)程如表2所示.

表2的編碼過(guò)程可用圖3的編碼樹(shù)來(lái)表示.

因?yàn)楸?中的編碼只能得出一棵對(duì)應(yīng)的編碼樹(shù)，從而不會(huì)產(chǎn)生形狀分析和模式識(shí)別的問(wèn)題.

3 Morton碼的原理

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

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

Morton碼： 18 27 31 ……

霍夫曼編碼: 11 1011 11 ……

圖3 霍夫曼編碼樹(shù)

圖4 Morton碼

4 多邊形矢量編碼

圖5 Morton碼的計(jì)算過(guò)程

多邊形矢量編碼的文件編碼坐標(biāo)為x1,y1；x2,y2；x3,y3;…，所以使用多邊形矢量編碼來(lái)表示時(shí)只要將與編碼坐標(biāo)對(duì)應(yīng)的霍夫曼編碼值依次寫入即可.

霍夫曼編碼 11 1011 11 …

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

[2] 閆浩文. 計(jì)算機(jī)地圖制圖原理與算法基礎(chǔ)[M].北京：科學(xué)出版社,2007:94-95.

[3] 付先平. 多媒體技術(shù)及應(yīng)用[M]. 北京：清華大學(xué)出版社，2007：53-55.

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