【正文】 4 4 7 7 7 4 4 4 4 8 8 7 7 0 0 4 8 8 8 7 7 0 0 8 8 8 8 7 8 0 0 0 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 (0,1) (4,3) (7,8) (4,5) (7,8) (4,4) (8,6) (7,8) (0,2) (4,3) (8,6) (7,8) (0,2) (8,6) (7,7)(8,8) (0,3) (8,8) (0,4) (8,8) (0,5) (8,8) 游程終止編碼 （ 3）游程（行程）編碼 0 4 4 7 7 7 7 7 4 4 4 4 4 7 7 7 4 4 4 4 8 8 7 7 0 0 4 8 8 8 7 7 0 0 8 8 8 8 7 8 0 0 0 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 （ 0,1) (4,2) (7,5) (4,5) (7,3) (4,4) (8,2) (7,2) (0,2) (4,1) (8,3) (7,2) (0,2) (8,4) (7,1) (8,1) (0,3) (8,5) (0,4) (8,4) (0,5) (8,3) 游程長(zhǎng)度編碼： （ 3）游程（行程）編碼 ? 特點(diǎn)： 屬性的變化愈少，游程愈長(zhǎng)，即壓縮比的大小與圖的復(fù)雜程度成反比。 ? 優(yōu)點(diǎn)： 數(shù)據(jù)壓縮率高，易于實(shí)現(xiàn)疊加，檢索和合并運(yùn)算。 ? 缺點(diǎn)： 適合類型區(qū)面積較大的專題圖、遙感影像分類集中的分類圖，不適合類型連續(xù)變化或類型區(qū)分散的分類圖。 （ 3）游程（行程）編碼 （ 4）塊狀編碼 是將游程長(zhǎng)度編碼擴(kuò)展到二維的情況，采用 正方形區(qū)域?yàn)閱卧?對(duì)塊狀地物的柵格數(shù)據(jù)進(jìn)行編碼，實(shí)質(zhì)是把柵格陣列中同一屬性方形區(qū)域各元素映射成一個(gè)元素系列。每個(gè)記錄單元包含相鄰若干柵格，數(shù)據(jù)結(jié)構(gòu)由初始位置和半徑，在加上記錄單元的代碼組成。 編碼方式： （行號(hào)，列號(hào)，半徑，代碼） 0 2 2 5 5 5 5 5 2 2 2 2 2 5 5 5 0 0 0 0 0 3 3 3 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 （ 1， 1， 1， 0），（ 1， 2， 2， 2）， （ 1， 4， 1， 5），（ 1， 5， 1， 5）， （ 1， 6， 2， 5），（ 1， 8， 1， 5）； （ 2， 1， 1， 2），（ 2， 4， 1， 2）， （ 2， 5， 1， 2），（ 2， 8， 1， 5）； （ 3， 3， 1， 2），（ 3， 4， 1， 2）， （ 3， 5， 2， 3），（ 3， 7， 2， 5）； （ 4， 1， 2， 0），（ 4， 3， 1， 2）， （ 4， 4， 1， 3）；（ 5， 3， 1， 3）， （ 5， 4， 2， 3），（ 5， 6， 1， 3）， （ 5， 7， 1， 5），（ 5， 8， 1， 3）； （ 6， 1， 3， 0），（ 6， 6， 3， 3）； （ 7， 4， 1， 0），（ 7， 5， 1， 3）； （ 8， 4， 1， 0），（ 8， 5， 1， 0）。 （ 4）塊狀編碼 特點(diǎn)： 面狀地物所能包含的正方形越大，多邊形邊界越簡(jiǎn)單，塊碼編碼效率超高； 圖形比較碎，多邊形邊界復(fù)雜的圖形，數(shù)據(jù)壓縮率低； 利于計(jì)算面積、合并插入等操作。 （ 4）塊狀編碼 （ 5）四叉樹編碼（ Quadtree Code） 四叉樹概述： 四叉樹又稱為四元樹或四分樹，是最有效的柵格數(shù)據(jù)壓縮編碼方法之一，絕大部分圖形操作和運(yùn)算都可以直接在四叉樹結(jié)構(gòu)上實(shí)現(xiàn)，四叉樹編碼即壓縮了數(shù)據(jù)量，又可大大提高圖形操作的效率。 基本思想： 將 2n 2n象元組成的圖像 (不足的用背景補(bǔ)上 ) 按四個(gè)象限進(jìn)行遞歸分割，并判斷屬性是否單一， 單一：不分。 不單一：遞歸分割。 最后得到一顆四分叉的倒向樹。 （ 5）四叉樹編碼（ Quadtree Code） 四叉樹的樹形表示： 用一倒立樹表示分割和分割結(jié)果。 根 ：整個(gè)區(qū)域 高 ：深度、分幾級(jí)，幾次分割 葉 ：不能再分割的塊 樹叉 ：還需分割的塊。 0 1 2 3 A A A A A B B B A A B B A A B B 0 0 0 0 0 4 4 4 0 0 0 4 4 4 4 4 0 0 4 4 4 4 8 8 0 0 4 4 4 8 8 8 2 2 4 4 8 8 8 8 2 2 2 4 8 8 8 8 2 2 2 2 8 8 8 8 2 2 2 2 8 8 8 8 0 0 0 0 4 4 0 4 4 4 0 4 4 4 8 4 8 2 4 4 8 2 4 2 2 1）常規(guī)四叉樹及編碼 原始柵格 四叉樹圖 1）常規(guī)四叉樹及編碼 四叉樹編碼的樹狀表示 NW NE SW SE 0 0 4 4 8 2 2 2 0 0 0 0 4 4 4 4 4 4 4 8 4 4 4 2 (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) (15) (16) (17) (18) (19) (20) (21) (22) (23) (24) 0層 1層 2層 3層 記錄這棵樹的葉結(jié)點(diǎn)外 ， 中間結(jié)點(diǎn) ， 結(jié)點(diǎn)之間的聯(lián)系用指針聯(lián)系 ， 每個(gè)結(jié)點(diǎn)需要 6個(gè)變量： 父結(jié)點(diǎn)指針 、 四個(gè)子結(jié)點(diǎn)的指針和本結(jié)點(diǎn)的屬性值 。 對(duì)一幅 2N 2N的柵格陣列，最大深度為 N，可能有的層次為 0， 1， 2， … ， N，最大層數(shù)為 N+，每層的柵格寬度為： 2（最大深度 當(dāng)前層次） 反映了所在葉結(jié)點(diǎn)表示的正方形集合的大小。 1）常規(guī)四叉樹 及編碼 缺點(diǎn)： 所占空間比較大，不僅要記錄每個(gè)結(jié)點(diǎn)，還要記錄一個(gè)前趨結(jié)點(diǎn)和四個(gè)后繼點(diǎn)，以及反映結(jié)點(diǎn)之間聯(lián)系，對(duì)柵格數(shù)據(jù)進(jìn)行運(yùn)算時(shí)，還要作遍歷樹結(jié)點(diǎn)的運(yùn)算，增加操作復(fù)雜性。 1）常規(guī)四叉樹及編碼 指針不僅 增加了數(shù)據(jù)的存儲(chǔ)量 ，還增加了操作的 復(fù)雜性 ：如層次數(shù)（分割次數(shù)）由從父結(jié)點(diǎn)移到根結(jié)點(diǎn)的次數(shù)來確定，結(jié)點(diǎn)所代表的圖像塊的位置需要從根節(jié)點(diǎn)開始逐步推算下來。所以， 常規(guī)四叉樹并不廣泛用于存儲(chǔ)數(shù)據(jù) ，其價(jià)值在于建立索引文件，進(jìn)行數(shù)據(jù)檢索。 2)線性四叉樹及編碼 以四叉樹的方式組織數(shù)據(jù)，但不以四叉樹方式存儲(chǔ)數(shù)據(jù)。 通過編碼四叉樹的葉結(jié)點(diǎn)表示數(shù)據(jù)的層次和空間關(guān)系。 葉結(jié)點(diǎn)具有一個(gè)反映位置的關(guān)鍵字，亦稱 位置碼 。 實(shí)質(zhì)是把原來大小相等的柵格集合轉(zhuǎn)換成大小不等的正方形集合，對(duì)不同尺寸和位置的正方形集合賦予一個(gè) 位置碼。 2)線性四叉樹及編碼 只存貯最后葉結(jié)點(diǎn)信息。 包括： 結(jié)點(diǎn)號(hào)、 結(jié)點(diǎn)位置、深度 、本節(jié)點(diǎn)的 屬性或灰度值 象限劃分： 0 1 2 3 (19) 0 (18) 0 (12) 0 (11) 0 (16) (15) (17) 0 (14) (13) (10) 1 （ 9） 1 (7) (6) (5) (4) （ 3） 1 （ 8） 0 （ 2） 0 （ 1） 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2)線性四叉樹及編碼 2）線性四叉樹及編碼 （ 1）基于深度和層次碼的線性四叉樹編碼 它通過記錄葉結(jié)點(diǎn)的 深度碼 和 層次碼 來描述葉 結(jié)點(diǎn)的位置， 2N為層次碼。 如圖中葉結(jié)點(diǎn)（ 7）的編碼為： 層次碼 深度碼（ 4位） 第一層 第二層 第三層 0 0 1 1 1 1 0 0 1 1 置碼十進(jìn)制值 =243+相應(yīng)的屬性代碼值 8 9 8 0 0 1 0 1 1 1 0 0 0 18 9 6 2 0 0 1 0 1 1 1 1 0 0 19 8 3 4 0 0 1 0 1 1 0 1 0 0 17 8 1 9 0 0 1 1 1 1 0 0 1 1 16 8 0 3 0 0 1 1 1 1 0 0 1 0 15 7 8 7 0 0 1 1 1 1 0 0 0 1 14 7 7 1 0 0 1 1 1 1 0 0 0 0 13 7 0 6 0 0 1 0 1 0 1 1 0 0 12 6 4 2 0 0 1 0 1 0 1 0 0 0 11 5 7 8 0 0 1 0 1 0 0 1 0 0 10 5 1 4 0 0 1 0 1 0 0 0 0 0 9 2 5 7 0 0 0 1 1 0 0 0 0 0 8 2 4 3 0 0 1 1 0 0 1 1 1 1 7 2 2 7 0 0 1 1 0 0 1 1 1 0 6 2 1 1 0 0 1 1 0 0 1 1 0