柵格數(shù)據(jù)結(jié)構(gòu)及編碼

1、柵格數(shù)據(jù)結(jié)構(gòu)及編碼點(diǎn)線面點(diǎn)點(diǎn)：為一個(gè)像元線線：在一定方向上連接成串的屬性相同的相鄰像元集合。面面：屬性相同聚集在一起的相鄰像元集合。定義：定義：柵格數(shù)據(jù)結(jié)構(gòu)是以規(guī)則的陣列來(lái)表示空間地物或現(xiàn)象分布的數(shù)據(jù)組織，組織中的每個(gè)數(shù)據(jù)表示地物或現(xiàn)象的非幾何屬性特征。（ a） 三 角 形（ b） 菱 形（ c) 六 邊 形d正方形 形狀二、柵格像元參數(shù) 形狀與大小Y：列格網(wǎng)分辨率 大小3333柵格象元的大小與描述實(shí)體的近似程度及存儲(chǔ)的空間相矛盾 三、柵格單元代碼的確定方法中心點(diǎn)法重要性長(zhǎng)度占優(yōu)法為了逼近原始數(shù)據(jù)精度，除了采用這幾種取值方法外，還可以采用縮小單個(gè)柵格單元的面積，增加?xùn)鸥駟卧倲?shù)的方法。 面積占

2、優(yōu)B連續(xù)分布地理要素C具有特殊意義的較小地物A分類(lèi)較細(xì)、地物斑塊較小Bab中心點(diǎn)法 處理方法： 用處于柵格中心處的地物類(lèi)型或現(xiàn)象特性決定柵格代碼 常用于具有連續(xù)分布特性的地理要素，如降雨量分布、人口密度圖等。 面積占優(yōu)法n處理方法：以占柵格區(qū)域面積比例最大的地物類(lèi)型或現(xiàn)象特性決定柵格單元的代碼 n面積占優(yōu)法常用于分類(lèi)較細(xì)，地物類(lèi)別斑塊較小的情況 重要性法 處理方法：根據(jù)柵格內(nèi)不同地物的重要性，選取最重要的地物類(lèi)型決定相應(yīng)的柵格單元代碼 重要性法常用于具有特殊意義而面積較小的地理要素，特別是點(diǎn)、線狀地理要素，如城鎮(zhèn)、交通樞紐、交通線、河流水系等，在柵格中代碼應(yīng)盡量表示這些重要地物 長(zhǎng)度占優(yōu)法n處

3、理方法：以網(wǎng)格中線的大部分長(zhǎng)度所對(duì)應(yīng)的面域的屬性值來(lái)確定。四、柵格數(shù)據(jù)的值1122112311333332aabbaabcaacccccbn整數(shù)值：如土壤分類(lèi)五、柵格數(shù)據(jù)組織方法柵格數(shù)據(jù)以層的方式來(lái)組織文件，在柵格數(shù)據(jù)結(jié)構(gòu)中，物體的空間位置就用其在笛卡爾平面網(wǎng)格中的行號(hào)和列號(hào)坐標(biāo)表示，物體的屬性用象元的取值表示，每個(gè)象元在一個(gè)網(wǎng)格中只能取值一次，同一象元要表示多重屬性的事物就要用多個(gè)笛卡爾平面網(wǎng)格，稱為層。v以像元為序。不同層上同一像元位置上的各屬性值表示為一個(gè)列數(shù)組。v以層為基礎(chǔ)。每一層又以像元為序記錄它的坐標(biāo)和屬性值。v以層為基礎(chǔ)。但每一層內(nèi)以多邊形為序記錄多邊形的屬性值和充滿多邊形的各像

4、元的坐標(biāo)。柵格數(shù)據(jù)文件像元1X坐標(biāo)Y坐標(biāo)層2屬性值層1屬性值層n屬性值像元2像元n柵格數(shù)據(jù)文件層1像元1層2X,Y,屬性值像元2X,Y,屬性值像元nX,Y,屬性值層n柵格數(shù)據(jù)文件層1多邊形1層2屬性值像元1坐標(biāo)多邊形N像元n坐標(biāo)層n1、直接?xùn)鸥窬幋a 當(dāng)每個(gè)像元都有唯一一個(gè)屬性值時(shí)，一層內(nèi)的編碼就需要m行n列3(x,y和屬性編碼值)個(gè)存儲(chǔ)單元。六、柵格數(shù)據(jù)存儲(chǔ)編碼 柵格數(shù)據(jù)是二維表面上地理數(shù)據(jù)的離散量化值，每一層的象元值組成像元陣列（即二維數(shù)組），其中行、列號(hào)表示它的位置。例如影像： A A A A A B B B A B B B A A A B在計(jì)算機(jī)內(nèi)是一個(gè)4*4階的矩陣。但在外部設(shè)備上，以

5、左上角開(kāi)始逐行逐列存貯。如上例存貯順序?yàn)椋篈 A A A A B B B A A B B A A A B2、壓縮編碼方法目的：用盡可能小的數(shù)據(jù)量來(lái)記錄盡可能多的信息。方法：游程長(zhǎng)度編碼、鏈碼、塊碼、四叉樹(shù)編碼。基本思想：對(duì)于一幅柵格圖像，常有行（列）方向上相鄰的若干點(diǎn)具有相同的屬性代碼，因而可采取某種壓縮方法壓縮那些重復(fù)的記錄內(nèi)容。方法：游程長(zhǎng)度編碼是按行（或列）序存儲(chǔ)多邊形內(nèi)的各個(gè)像元的列號(hào)，即在某行（列）上從左（上）至右（下）存儲(chǔ)屬該多邊形的像元個(gè)數(shù)。壓縮編碼-游程長(zhǎng)度編碼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

6、；8，1；0，3；8，5；0，4；8，4；0，5；8，3；（1）（2）0，1；4，2；0，5；4，3；0，5；4，4；8，1；0，3；7，1；4，2；8，3；0，2；7，1；4，1；8，5；0，1；7，2；8，6；7，5；8，3；7 ，4；8，4；0 4 4 7 7 7 7 74 4 4 4 4 7 7 74 4 4 4 8 8 7 70 0 4 8 8 8 7 70 0 8 8 8 8 7 80 0 0 8 8 8 8 80 0 0 0 8 8 8 8 0 0 0 0 0 8 8 82、塊碼 基本思想： 塊式編碼是將游程長(zhǎng)度編碼擴(kuò)大到二維的情況，把多邊形范圍劃分成由像元組成的正方形，然后對(duì)各

7、個(gè)正方形進(jìn)行編碼。塊式編碼的數(shù)據(jù)結(jié)構(gòu)由初始位置(行號(hào)，列號(hào)) 、半徑和屬性，再加上記錄單元的代碼組成。如圖：0 4 4 7 7 7 7 74 4 4 4 4 7 7 74 4 4 4 8 8 7 70 0 4 8 8 8 7 70 0 8 8 8 8 7 80 0 0 8 8 8 8 80 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8（1，1，1，0）；（4，1，2，0）；（6，1，3，0）；（7，4，1，0）；（8，4，1，0）；（8，5，1，0）；（1，2，1，4）；（1，3，1，4）；（2，1，2，4）；（2，3，3，4）；（2，5，1，4）；（1，4，1，7）；（1，5，

8、1，7）；（1，6，1，7）；（1，7，2，7）；（2，6，1，7）；（3，7，2，7）；（5，7，1，7）；（3，5，2，8）；（4，4，1，8）；（5，3，1，8）；（5，4，2，8）；（5，6，1，8）；（5，8，1，8）；（7，5，1，8）；（6，6，3，8）；壓縮編碼方法-塊碼特點(diǎn)： 具有可變的分辨率，即當(dāng)代碼變化小時(shí)圖塊大，表明在區(qū)域圖斑內(nèi)部分辨率低；反之以小塊記錄區(qū)域邊界地段分辨率高，以此達(dá)到壓縮的目的。 塊碼與游程長(zhǎng)度編碼相似，隨著圖形復(fù)雜程度的提高而降低效率，即圖斑越大，壓縮比越高；圖斑越破碎，壓縮比越低。01234567基本原理： 以多邊形的邊界為基本單元編碼，它是由某一原

9、點(diǎn)開(kāi)始并按某些基本方向確定的單位矢量。0 4 4 7 7 7 7 74 4 4 4 4 7 7 74 4 4 4 8 8 7 70 0 4 8 8 8 7 70 0 8 8 8 8 7 80 0 0 8 8 8 8 80 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8屬性值為“4”的多邊形：（ 4，1，2）0，1，0，3，3，5，4，6，7編碼方法-鏈?zhǔn)骄幋a特點(diǎn)： 可以有效地壓縮柵格數(shù)據(jù)，而且對(duì)于估算面積、長(zhǎng)度、轉(zhuǎn)折方向的凹凸度等運(yùn)算十分方便，比較適合于存儲(chǔ)圖形數(shù)據(jù)。 缺點(diǎn)是對(duì)邊界進(jìn)行合并和插入等修改編輯工作比較困難，對(duì)局部的修改將改變整體結(jié)構(gòu)、效率較低，而且由于鏈碼是以每個(gè)區(qū)域?yàn)?/p>

10、單位存儲(chǔ)邊界，相鄰區(qū)域的邊界將被重復(fù)存儲(chǔ)從而產(chǎn)生冗余。基本思想： 將一幅柵格地圖或圖像等分為四部分，逐塊檢查其格網(wǎng)屬性值。如果某個(gè)子區(qū)的所有格網(wǎng)值都具有相同的值，則這個(gè)子區(qū)就不再繼續(xù)分割，否則還需按該子區(qū)再分割成四個(gè)子區(qū)，這樣依次地分割，直至每個(gè)子區(qū)都具有相同的屬性值或灰度為止。編碼方法-四叉樹(shù)編碼采用四叉樹(shù)編碼時(shí)，為了保證四叉樹(shù)分解能不斷地進(jìn)行下去，要求圖像必須為2n2 n的柵格陣列，對(duì)于非標(biāo)準(zhǔn)尺寸的圖像需首先通過(guò)增加背景的方法將圖像擴(kuò)充為2 n 2 n的圖像。 n四叉樹(shù)結(jié)構(gòu)按其編碼的方法不同分為常規(guī)四叉樹(shù)和線性四叉樹(shù)： 常規(guī)四叉樹(shù)：除了記錄葉結(jié)/節(jié)點(diǎn)之外，還要記錄中間結(jié)點(diǎn)（非葉結(jié)/節(jié)點(diǎn)）。

11、結(jié)點(diǎn)之間借助指針聯(lián)系，每個(gè)結(jié)點(diǎn)需要用六個(gè)量表達(dá)：四個(gè)葉結(jié)點(diǎn)指針，一個(gè)父結(jié)點(diǎn)指針和一個(gè)結(jié)點(diǎn)的屬性或灰度值。這些指針不僅增加了數(shù)據(jù)貯存量，而且增加了操作的復(fù)雜性。 常規(guī)四叉樹(shù)主要應(yīng)用于數(shù)據(jù)的索引和圖幅的索引，為了減少編碼時(shí)間，在數(shù)據(jù)壓縮和GIS數(shù)據(jù)結(jié)構(gòu)中通常采用自下而上生成的線性四叉樹(shù)對(duì)一幅2n2n的柵格陣列，最大深度為n，層次可為0,1,n 記錄每個(gè)葉結(jié)點(diǎn)的地址和值，值就是子區(qū)的屬性代碼，其中地址包括兩部分，共32位（二進(jìn)制）最右邊4位記錄該葉結(jié)點(diǎn)的深度，左邊的28位記錄路徑，從右邊第5位往左記錄從葉節(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。0，1，2，3分別表示SW，SE，NW，NE。第10號(hào)結(jié)點(diǎn)的地址編碼為： 0

12、00000001101|0011n四叉樹(shù)結(jié)構(gòu)按其編碼的方法不同分為常規(guī)四叉樹(shù)和線性四叉樹(shù)： 線性四叉樹(shù)：只存貯最后葉結(jié)點(diǎn)的信息。包括葉結(jié)點(diǎn)的位置、深度和本結(jié)點(diǎn)的屬性或灰度值。所謂深度是指處于四叉樹(shù)的第幾層上。由深度可推知子區(qū)的大小。線性四叉樹(shù)葉結(jié)點(diǎn)的編號(hào)需要遵循一定的規(guī)則，這種編號(hào)稱為地址碼，它隱含了葉結(jié)點(diǎn)的位置和深度信息。常用的四叉樹(shù)編碼是四進(jìn)制莫頓碼和十進(jìn)制莫頓碼。由于四進(jìn)制莫頓碼建立四叉樹(shù)的方法內(nèi)存開(kāi)銷(xiāo)大，大多語(yǔ)言系統(tǒng)不支持四進(jìn)制變量，因此通用性不強(qiáng)，十進(jìn)制莫頓碼具有直觀性的特點(diǎn)，因此更常用。十進(jìn)制Morton碼的編碼，奇位組合是行號(hào)，偶位組合是列號(hào)行號(hào)行號(hào) 5 = 0 1 0 15 =

13、 0 1 0 1列號(hào)列號(hào) 7= 0 1 1 17= 0 1 1 1Morton Morton 碼碼 = 0 0 1 1 0 1 1 1 = 55= 0 0 1 1 0 1 1 1 = 55 這樣就可將用行列表示的二維圖像，用Morton碼寫(xiě)成一維數(shù)據(jù)，通過(guò)Morton碼就可知象元位置。 把一幅2 n2 n的圖像壓縮壓縮成線性四叉樹(shù)的過(guò)程為： 按Morton碼把圖象讀入一維數(shù)組。 相鄰的四個(gè)象元比較，一致的合并，只記錄第一個(gè)象元的Morton碼。 比較所形成的大塊，相同的再合并，直到不能合并為止。 對(duì)用上述線性四叉樹(shù)的編碼方法所形成的數(shù)據(jù)還可進(jìn)一步用游程長(zhǎng)度編碼壓縮。壓縮時(shí)只記錄第一個(gè)象元的Mo

14、rton碼。ABBBBBBBAAAAAAAA0213891011121314154567四叉樹(shù)Morton碼編碼結(jié)果 解碼時(shí)，據(jù)解碼時(shí)，據(jù)Morton碼，可知象元在圖像中位置。從左上角，本碼，可知象元在圖像中位置。從左上角，本Morton碼和下一個(gè)碼和下一個(gè)Morton碼之差即為象元個(gè)數(shù)。知道了象元的碼之差即為象元個(gè)數(shù)。知道了象元的個(gè)數(shù)和象元的位置就可恢復(fù)出圖像了。個(gè)數(shù)和象元的位置就可恢復(fù)出圖像了。優(yōu)點(diǎn)： 容易而有效地計(jì)算多邊形的數(shù)量特征； 陣列各部分的分辨率是可變的，邊界復(fù)雜部分四叉樹(shù)越高即分級(jí)多，分辨率也高，而不需表示許多細(xì)節(jié)的部分則分級(jí)少，分辨率低，因而既可精確表示圖形結(jié)構(gòu)又可減少存儲(chǔ)量。 柵格到四叉樹(shù)及四叉樹(shù)到簡(jiǎn)單柵格結(jié)構(gòu)的轉(zhuǎn)換比其他壓縮方法容易。缺點(diǎn)：轉(zhuǎn)換不定性，即用同一形狀和大小的多邊形可能得出多種不同的四叉樹(shù)結(jié)構(gòu)，不利于形狀分析和模式區(qū)別。七、柵格數(shù)據(jù)結(jié)構(gòu)特點(diǎn)l離散的量化柵格值表示空間對(duì)象l位置隱含,屬性明顯l數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單,易與遙感數(shù)據(jù)結(jié)合,但數(shù)據(jù)量大l幾何和屬性偏差l面向位置的數(shù)據(jù)結(jié)構(gòu),難以建立空間對(duì)象之間的關(guān)系矢量數(shù)據(jù)優(yōu)點(diǎn)：表示地理數(shù)據(jù)的精度較高嚴(yán)密的數(shù)據(jù)