第二章3-柵格編碼1

1、1 1） 柵格數(shù)據(jù)結(jié)構(gòu)概念柵格數(shù)據(jù)結(jié)構(gòu)概念 柵格結(jié)構(gòu)是以規(guī)則的陣列來(lái)表示空間地物或現(xiàn)象分布的數(shù)據(jù)組織，組織中的每個(gè)數(shù)據(jù)表示地理要素的非幾何屬性特征。特點(diǎn)： 屬性明顯，定位隱含屬性明顯，定位隱含。 注意：柵格數(shù)據(jù)結(jié)構(gòu)是將連續(xù)空間離散化，即用二維鋪蓋或劃分覆蓋整個(gè)連續(xù)空間，這種鋪蓋可以分為規(guī)則的和不規(guī)則的 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0

2、0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 6 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 7 4 4 4 4 4 4 7 7 7 7 4 7 7 7 4 4 4 4 8 7 7 8 0 8 4 0 8 7 7 8 0 8 8 0 0 8 0 0 8 8 7 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 BCAO具有連續(xù)分布特性的地理要素，如降雨量分布、人口密度圖等常用于分類較細(xì)、地物類別斑塊較小的情況常用于具有特殊意義而面積又較

3、小的地理要素，尤其是點(diǎn)、線狀地理要素，如城鎮(zhèn)、交通樞紐、交通線、河流水系等。在屬性代碼中應(yīng)盡量表示這類重要地物。(2)鏈碼鏈碼(Chain Encoding)(1)直接?xùn)鸥窬幋a直接?xùn)鸥窬幋a(3)游程長(zhǎng)度編碼游程長(zhǎng)度編碼(Run_Length Encoding)(4)塊塊 碼碼(Block Encoding)(5)四叉樹(shù)編碼四叉樹(shù)編碼(Quadtree Encoding)2柵格結(jié)構(gòu)編碼方法1 1、直接?xùn)鸥窬幋a、直接?xùn)鸥窬幋a 直接編碼就是將柵格數(shù)據(jù)看作一個(gè)數(shù)據(jù)矩陣，逐行（或逐列）逐個(gè)記錄代碼，可以每行從左到右逐像元記錄，也可奇數(shù)行從左到右而偶數(shù)行由右向左記錄，為了特定的目的還可采用其他特殊的順序。

4、 0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 30，2，2，5，5，5，5，5；2，2，2，2，2，5，5，5；2，2，2，2，3，3，5，5；0，0，2，3，3，3，5，5；0，0，3，3，3，3，5，3；0，0，0，3，3，3，3，3；0，0，0，0，3，3，3，3；0，0，0，0，0，3，3，3。(1)直接?xùn)鸥窬幋a直接?xùn)鸥窬幋a 是壓縮編碼方法的邏輯原型。(1)直接?xùn)鸥窬幋a直接?xùn)鸥窬幋a(2)鏈碼鏈碼

5、(chain Encoding)鏈碼又稱為弗里曼鏈碼鏈碼又稱為弗里曼鏈碼Freeman或邊界或邊界鏈碼，鏈碼可以有效地壓縮柵格數(shù)據(jù)，而鏈碼，鏈碼可以有效地壓縮柵格數(shù)據(jù)，而且對(duì)于估算面積、長(zhǎng)度、轉(zhuǎn)折方向的凹凸且對(duì)于估算面積、長(zhǎng)度、轉(zhuǎn)折方向的凹凸度等運(yùn)算十分方便，比較適合于存儲(chǔ)圖形度等運(yùn)算十分方便，比較適合于存儲(chǔ)圖形數(shù)據(jù)數(shù)據(jù)。由起點(diǎn)位置和一系列在基本方向的單位矢量給出每個(gè)后續(xù)點(diǎn)相對(duì)其前繼點(diǎn)的可能的8個(gè)基本方向之一表示。8個(gè)基本方向自0開(kāi)始按逆時(shí)針?lè)较虼a分別為0，1，2，3，4，5，6，7。單位矢量的長(zhǎng)度默認(rèn)為一個(gè)柵格單元。2 2、鏈碼、鏈碼12345076001 0 767 01 1 0 0(2

6、)鏈碼鏈碼(Chain Encoding)鏈碼編碼鏈碼編碼： 2，2 ，6 ，7，6，0，6，5123450760 5 0 0 0 0 0 00 0 5 0 0 0 0 00 0 0 0 0 0 0 00 5 0 0 0 0 0 00 0 5 5 0 0 0 00 0 0 5 0 0 0 00 0 5 0 0 0 0 00 0 0 0 0 0 0 0鏈碼編碼示例鏈碼編碼示例 壓縮效率較高，接近矢量結(jié)構(gòu)，對(duì)邊界的運(yùn)算比較方便，但不具有區(qū)域性質(zhì)，區(qū)域運(yùn)算較難；(2)鏈碼鏈碼(chain Encoding)3 3、游程長(zhǎng)度編碼、游程長(zhǎng)度編碼只在各行（或列）數(shù)據(jù)的代碼發(fā)生變化時(shí)依次記錄 該代碼以及相同

7、代碼重復(fù)的個(gè)數(shù)；0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3沿行方向進(jìn)行編碼沿行方向進(jìn)行編碼：( 0，1），），（2，2），（），（5，5）；（）；（2，5），），（5，3）；（）；（2，4），（），（3，2），），（5，2）；（）；（0，2），（），（2，1），），（3，3），（），（5，2）；（）；（0，2），），（3，4），（），（5，1），（），（3，1）；）；（0，3），（），（3，5）；（

8、）；（0，4），），（3，4）；（）；（0，5），（），（3，3）。）。(3)游程長(zhǎng)度編碼游程長(zhǎng)度編碼(Run_Length Encoding)3 3、游程長(zhǎng)度編碼、游程長(zhǎng)度編碼逐個(gè)記錄各行（或列）代碼發(fā)生變化的位置和相應(yīng)代碼。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3沿列方向進(jìn)行編碼沿列方向進(jìn)行編碼：( 1，0），），（2，2），（），（4，0）；（）；（1，2），），（4，0）；（）；（1，2）

9、，（），（5，3），），（6，0）；（）；（1，5），（），（2，2），），（4，3），（），（7，0）；（）；（1，5），），（2，2），（），（3，3），（），（8，0）；）；（1，5），（），（3，3）；（）；（1，5），），（6，3）；（）；（1，5），（），（5，3）。）。(3)游程長(zhǎng)度編碼游程長(zhǎng)度編碼(Run_Length Encoding) 在很大程度上壓縮數(shù)據(jù)，又最大限度的保留了原始柵格結(jié)構(gòu)，編碼解碼十分容易，十分適合于微機(jī)地理信息系統(tǒng)采用；但計(jì)算期間的處理和制圖輸出處理工作量都有所增加。(3)游程長(zhǎng)度編碼游程長(zhǎng)度編碼(Run_Length Encoding) 4 4、塊碼、塊

10、碼 游程編碼是在一維情況下（按行或列）記錄像元的屬性及其位置?，F(xiàn)若采用方形區(qū)域作為記錄單元，則可以將游程編碼擴(kuò)展為二維情況下的編碼方式，即塊碼。 采用方形區(qū)域作為記錄單元，數(shù)據(jù)編碼由初始位置行列號(hào)加上半徑，再加上記錄單元的代碼組成。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3（1 1，1 1，1 1，0 0），（），（1 1，2 2，2 2，2 2），），（1 1，4 4，1 1，5 5），（），（1

11、 1，5 5，1 1，5 5），），（1 1，6 6，2 2，5 5），（），（1 1，8 8，1 1，5 5）；）；（2 2，1 1，1 1，2 2），（），（2 2，4 4，1 1，2 2），），（2 2，5 5，1 1，2 2），（），（2 2，8 8，1 1，5 5）；）；（3 3，3 3，1 1，2 2），（），（3 3，4 4，1 1，2 2），），（3 3，5 5，2 2，3 3），（），（3 3，7 7，2 2，5 5）；）；（4 4，1 1，2 2，0 0），（），（4 4，3 3，1 1，2 2），），（4 4，4 4，1 1，3 3）；（）；（5 5，3 3，1 1，3

12、3），），（5 5，4 4，2 2，3 3），（），（5 5，6 6，1 1，3 3），），（5 5，7 7，1 1，5 5），（），（5 5，8 8，1 1，3 3）；）；（6 6，1 1，3 3，0 0），（），（6 6，6 6，3 3，3 3）；）；（7 7，4 4，1 1，0 0），（），（7 7，5 5，1 1，3 3）；）；（8 8，4 4，1 1，0 0），（），（8 8，5 5，1 1，0 0）。）。(4)塊塊 碼碼(Block Encoding)(4)塊塊 碼碼(Block Encoding) 5 5、四叉樹(shù)編碼、四叉樹(shù)編碼 是根據(jù)柵格數(shù)據(jù)二維空間分布的特點(diǎn)，將空間區(qū)域按照4

13、個(gè)象限進(jìn)行遞歸分割（2n2 n，且n1），直到子象限的數(shù)值單調(diào)為止，最后得到一棵四分叉的倒向樹(shù)。四叉樹(shù)分解，各子象限大小不完全一樣，但都是同代碼柵格單元組成的子塊，其中最上面的一個(gè)結(jié)點(diǎn)叫做根結(jié)點(diǎn)，它對(duì)應(yīng)于整個(gè)圖形。不能再分的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，可能落在不同的層上，該結(jié)點(diǎn)代表子象限單一的代碼，所有葉子結(jié)點(diǎn)所代表的方形區(qū)域覆蓋了整個(gè)圖形。從上到下，從左到右為葉子結(jié)點(diǎn)編號(hào)，最下面的一排數(shù)字表示各子區(qū)的代碼。 為了保證四叉樹(shù)分解能不斷的進(jìn)行下去，要求圖形必須為2n2 n的柵格陣列。n 為極限分割次數(shù)，n1是四叉樹(shù)最大層數(shù)或最大高度(5)四叉樹(shù)編碼四叉樹(shù)編碼(Quadtree Encoding)0 2 2

14、 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3 1112131415161718192021222324252627282930313233363738393435400 0 00 3 3 3 0 3 3 33 3 5 3 0 0 2 2 2 3 2 2 2 2 0 22 2 2 5 2 5 5 53 33 5 5西南東南西北東北 221213013202322編號(hào)為213的子象限（葉結(jié)點(diǎn)）的地址可用二進(jìn)制表示為

15、：編號(hào)213100111四叉樹(shù)地址編碼這樣，記錄了各個(gè)葉結(jié)點(diǎn)的地址，再記上各自相應(yīng)的屬性代碼值就記錄了整個(gè)圖像。并在此基礎(chǔ)上進(jìn)行多種圖像操作。列號(hào)M碼行號(hào)Morton碼與行列號(hào)的關(guān)系(5)四叉樹(shù)編碼四叉樹(shù)編碼直接?xùn)鸥窬仃嚪ㄖ苯訓(xùn)鸥窬仃嚪ㄦ湸a鏈碼游程編游程編碼碼在很大程度上壓縮數(shù)據(jù)，又最大限度的保留了原始柵格結(jié)構(gòu)，編碼解碼十分容易；塊碼和四叉樹(shù)編碼塊碼和四叉樹(shù)編碼具有區(qū)域性質(zhì)，又具有可變的分辨率，有較高的壓縮效率，四叉樹(shù)編碼可以直接進(jìn)行大量圖形圖象運(yùn)算，效率較高，使用也日益廣泛。2255275577755555序號(hào)序號(hào)二元組序列二元組序列1（2，2）2（5，2）3（2，1）4（7，1）5（5，2

16、）6（7，3）7（5，5）二元映射二元映射1111111000001111100001111序號(hào)序號(hào)二元組序號(hào)二元組序號(hào)1（1，7）2（0，5）3（1，5）4（0，4）5（1，4）二元映射二元映射Re 1Q/(MN)Q：圖層內(nèi)相鄰屬性值變化次數(shù)的累加和：圖層內(nèi)相鄰屬性值變化次數(shù)的累加和M：為圖層網(wǎng)格的行數(shù)：為圖層網(wǎng)格的行數(shù)N：為圖層網(wǎng)格的列數(shù)：為圖層網(wǎng)格的列數(shù)當(dāng)?shù)闹荡笥诋?dāng)?shù)闹荡笥?/5的情況下，表明柵格數(shù)據(jù)的壓縮可取得明顯的效果的情況下，表明柵格數(shù)據(jù)的壓縮可取得明顯的效果2468357824682581122223221222223332321223差分游程序號(hào)編碼值0001000200030004.000