1、第4章 空間數(shù)據(jù)結(jié)構(gòu),1,主要內(nèi)容,4.1 矢量數(shù)據(jù)結(jié)構(gòu) 4.2 柵格數(shù)據(jù)結(jié)構(gòu) 4.3 矢柵一體化數(shù)據(jù)結(jié)構(gòu) 4.4 鑲嵌數(shù)據(jù)結(jié)構(gòu) 4.5 柵格與矢量數(shù)據(jù)的相互轉(zhuǎn)換,2,4.2 柵格數(shù)據(jù)結(jié)構(gòu),3,4.2 柵格數(shù)據(jù)結(jié)構(gòu),4.2.1 柵格單元的確定 4.2.2 完全柵格數(shù)據(jù)結(jié)構(gòu) 4.2.3 壓縮柵格數(shù)據(jù)結(jié)構(gòu),4,4.2 柵格數(shù)據(jù)結(jié)構(gòu),以規(guī)則柵格陣列表示空間對(duì)象的數(shù)據(jù)結(jié)構(gòu)，是最簡(jiǎn)單最直觀的空間數(shù)據(jù)結(jié)構(gòu)，又稱(chēng)為網(wǎng)格結(jié)構(gòu)(raster或grid cell)或像元結(jié)構(gòu)(pixel)。 陣列中每個(gè)柵格單元上的數(shù)值表示空間對(duì)象的非幾何屬性特征； 其位置由柵格陣列中每個(gè)單元的行列號(hào)來(lái)確定。 柵格數(shù)據(jù)結(jié)構(gòu)表示的地表

2、是不連續(xù)的，是量化和近似離散的數(shù)據(jù)，一個(gè)柵格單元對(duì)應(yīng)于小塊地理范圍。,5,對(duì)于柵格數(shù)據(jù)結(jié)構(gòu) 點(diǎn)：為一個(gè)像元 線：在一定方向上連接成串的相鄰像元集合。 面：聚集在一起的相鄰像元集合。,6,7,點(diǎn)、線、面數(shù)據(jù)的矢量與柵格表示,8,Representation of point, line, and area features: raster format on the left and vector format on the right.,柵格數(shù)據(jù)類(lèi)型,1衛(wèi)星影像：像元值代表從地球表面反射或發(fā)射的光能，可從中提取各種專(zhuān)題，如土地利用、水文、水質(zhì)等。 2數(shù)字高程模型（DEM）：由等間隔海拔數(shù)據(jù)的排

3、列組成。DEM以點(diǎn)為基礎(chǔ)，將海拔高度點(diǎn)置于格網(wǎng)單元中心的方法轉(zhuǎn)成柵格數(shù)據(jù)。 3數(shù)字正射影像圖（DOQ）：是一種由航片或其他遙感數(shù)據(jù)制備而得到的數(shù)字化影像，其中由照相機(jī)鏡頭傾斜和地形起伏引起的位移已被消除。 4二進(jìn)制掃描文件：是含數(shù)值1或數(shù)值0的掃描圖像。 5數(shù)字柵格圖形：是USGS（美國(guó)地質(zhì)調(diào)查局）地形圖的掃描圖像。 6圖形文件：如JPG、TIFF、GIF等； 7特定地理信息系統(tǒng)軟件的柵格數(shù)據(jù)。,4.2.1柵格單元的確定,1. 柵格數(shù)據(jù)的參數(shù) 一個(gè)完整的柵格數(shù)據(jù)通常由以下幾個(gè)參數(shù)決定： （1）柵格形狀。柵格單元通常為矩形或正方形。特殊的情況下也可以按經(jīng)緯網(wǎng)劃分柵格單元。 （2）柵格單元大小。也

4、就是柵格單元的尺寸，即分辨率。柵格單元的合理尺寸應(yīng)能有效地逼近空間對(duì)象的分布特征，以保證空間數(shù)據(jù)的精度。通常以保證最小圖斑不丟失為原則來(lái)確定合理的柵格尺寸。 （3）柵格原點(diǎn)。柵格系統(tǒng)的起始坐標(biāo)應(yīng)將和國(guó)家基本比例尺地形圖公里網(wǎng)的交點(diǎn)相一致，或者和已有的柵格系統(tǒng)數(shù)據(jù)相一致。并同時(shí)使用公里網(wǎng)的縱橫坐標(biāo)軸作為柵格系統(tǒng)的坐標(biāo)軸。 （4）柵格的傾角。通常情況下，柵格的坐標(biāo)系統(tǒng)與國(guó)家坐標(biāo)系統(tǒng)平行。,10,1.柵格數(shù)據(jù)的參數(shù),11,X：列,Y：行,西南角格網(wǎng)坐標(biāo) （XWS，YWS）,格網(wǎng)分辨率,2. 柵格數(shù)據(jù)單元值確定,12,面 積 占 優(yōu),重 要 性,中心點(diǎn)法,A位于柵格中心處的地物類(lèi)型決定其取值。 常用于

5、連續(xù)分布特性的地理現(xiàn)象。,C選取最重要的地物類(lèi)型為單元值。常用于有特殊意義而面積較小的地理要素,A占區(qū)域面積最大的地物類(lèi)型取值適用于分類(lèi)較細(xì)、地物斑塊較小地理要素,為了逼近原始數(shù)據(jù)精度，除了采用這幾種取值方法外，還可以采用縮小單個(gè)柵格單元的面積，增加?xùn)鸥駟卧倲?shù)的方法,13,幾何偏差,屬性偏差,如ac距離以像元邊線計(jì)算則為7，以像元個(gè)數(shù)為單位則為4。 三角形的面積為6個(gè)平方單位，而右圖中則為7個(gè)平方單位，這種誤差隨像元的增大而增加。,中心點(diǎn)法,面積占優(yōu)法,4. 柵格數(shù)據(jù)的編碼方法,4.2.2完全柵格數(shù)據(jù)結(jié)構(gòu) 直接?xùn)鸥窬幋a 4.2.3壓縮柵格數(shù)據(jù)結(jié)構(gòu) 游程長(zhǎng)度編碼 鏈?zhǔn)綌?shù)據(jù)編碼 四叉樹(shù)編碼 分塊

6、壓縮編碼,14,4.2.2完全柵格數(shù)據(jù)結(jié)構(gòu),1.直接?xùn)鸥窬幋a 將柵格看做一個(gè)數(shù)據(jù)矩陣，逐行逐個(gè)記錄代碼數(shù)據(jù)。 優(yōu)點(diǎn)：簡(jiǎn)單、直觀，無(wú)壓縮 缺點(diǎn)：存在大量冗余，精度提高有限制。,15,完全柵格數(shù)據(jù)的組織,完全柵格數(shù)據(jù)的組織有三種基本方式： 基于像元、基于層（波段）和基于行 .bsq （band sequential）基于層（波段）的方式,16,柵格數(shù)據(jù)文件,波段1,像元1，1,像元1，2,像元1，m,像元m，n,波段2,波段k,.bil （band interleaved by line）基于行的方式,17,柵格數(shù)據(jù)文件,行1,波段1,行2,像元1n,波段2,像元1n,波段k,像元1n,行m,.b

7、ip （band interleaved by pixel）基于像元方式,18,柵格數(shù)據(jù)文件,像元1，1,像元1，2,波段1,波段k,像元m，n,2.游程長(zhǎng)度編碼（Run-Length Encoding）,也稱(chēng)為行程編碼，將每行中具有相同屬性值的連續(xù)像元映射為一個(gè)游程，每個(gè)游程的數(shù)據(jù)結(jié)構(gòu)為（A，P），A表示屬性值，P代表該游程最右端的列號(hào)或個(gè)數(shù)。 屬性變化越少，壓縮比例越大，適合于類(lèi)型區(qū)域面積較大的柵格。,19,原始柵格數(shù)據(jù),(9,4),(0,4),(9,3),(0,5),(0,1)(9,2),(0,1),(7,2),(0,2),(0,4),(7,2),(0,2),(0,4),(7,4),(0

8、,4),(7,4),(0,4),(7,4),(0,4),(7,4),2.游程長(zhǎng)度編碼（Run-Length Encoding）,優(yōu)點(diǎn)： 柵格加密時(shí)，數(shù)據(jù)量不會(huì)明顯增加，壓縮效率高，最大限度保留原始柵格結(jié)構(gòu)， 編碼解碼運(yùn)算簡(jiǎn)單，且易于檢索、疊加、合并等操作，得到廣泛應(yīng)用。 缺點(diǎn)： 不適合于類(lèi)型連續(xù)變化或類(lèi)型區(qū)域分散的數(shù)據(jù)。,20,3. 鏈?zhǔn)綌?shù)據(jù)編碼（Chain Encoding，弗里曼Freeman）,鏈?zhǔn)骄幋a主要是記錄線狀地物和面狀地物的邊界。它把線狀地物和面狀地物的邊界表示為：由某一起始點(diǎn)開(kāi)始并按某些基本方向確定的單位矢量鏈?；痉较蚩啥x為：東0，東南l，南2，西南3，西4，西北5，北6，

9、東北7等八個(gè)基本方向。 編碼過(guò)程： 起始點(diǎn)的尋找一般遵循從上到下，從左到右的原則； 當(dāng)發(fā)現(xiàn)沒(méi)有記錄過(guò)的點(diǎn)，且數(shù)值不為0時(shí)，就是一條線或邊界的起點(diǎn)； 記下該地物的特征碼、起點(diǎn)的行列號(hào)，然后按順時(shí)針?lè)较驅(qū)ほE，找到相鄰的等值點(diǎn)，并按八個(gè)方向編碼。,21,3. 鏈?zhǔn)綌?shù)據(jù)編碼（Chain Encoding，弗里曼Freeman）,鏈?zhǔn)骄幋a表 特征碼 起點(diǎn)行 起點(diǎn)列 鏈碼 線 1 5 3223323 面 3 6 0213246676,22,鏈?zhǔn)骄幋a的方向代碼,鏈?zhǔn)骄幋a示意圖,優(yōu)點(diǎn)： 鏈?zhǔn)骄幋a對(duì)多邊形的表示具有很強(qiáng)的數(shù)據(jù)壓縮能力， 且具有一定的運(yùn)算功能，如面積和周長(zhǎng)計(jì)算等，探測(cè)邊界急彎和凹進(jìn)部分等都比較容易

10、，比較適于存儲(chǔ)圖形數(shù)據(jù)。 缺點(diǎn)： 對(duì)邊界做合并和插入等修改編輯比較困難； 類(lèi)似矢量結(jié)構(gòu)，不具有區(qū)域的性質(zhì)，對(duì)疊置運(yùn)算如組合、相交等則很難實(shí)施； 而且由于鏈碼以每個(gè)區(qū)域?yàn)閱挝淮鎯?chǔ)邊界，相鄰區(qū)域的邊界則被重復(fù)存儲(chǔ)而產(chǎn)生冗余。,23,4. 四叉樹(shù)編碼（Quad tree Encoding）,四叉樹(shù)概述：一種可變分辨率的非均勻網(wǎng)格系統(tǒng)。 基本思想：將一幅柵格數(shù)據(jù)層或圖像等分為四部分，逐塊檢查其格網(wǎng)屬性值（或灰度）；如果某個(gè)子區(qū)的所有格網(wǎng)值都具有相同的值，則這個(gè)子區(qū)就不再繼續(xù)分割，否則還要把這個(gè)子區(qū)再分割成四個(gè)子區(qū)；這樣依次地分割，直到每個(gè)子塊都只含有相同的屬性值或灰度為止。 最上面的一個(gè)結(jié)點(diǎn)叫做根結(jié)點(diǎn)

11、，它對(duì)應(yīng)于整個(gè)圖形。 不能再分的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)，可能落在不同的層上，該結(jié)點(diǎn)代表子象限單一的代碼，所有葉子結(jié)點(diǎn)所代表的方形區(qū)域覆蓋了整個(gè)圖形。 從上到下，從左到右為葉子結(jié)點(diǎn)編號(hào)，最下面的一排數(shù)字表示各子區(qū)的代碼。 為了保證四叉樹(shù)分解能不斷的進(jìn)行下去，要求圖形必須為2n2n的柵格陣列。n 為極限分割次數(shù)，n1是四叉樹(shù)最大層數(shù)或最大高度.,24,方法： 自上而下 自下而上 A B A A A B A A B B,25,1）常規(guī)四叉樹(shù),記錄這棵樹(shù)的葉結(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)的屬性值。 指針不僅增加了數(shù)據(jù)的存儲(chǔ)量，還增加

12、了操作的復(fù)雜性： 如層次數(shù)（分割次數(shù)）由從父結(jié)點(diǎn)移到根結(jié)點(diǎn)的次數(shù)來(lái)確定，結(jié)點(diǎn)所代表的圖像塊的位置需要從根節(jié)點(diǎn)開(kāi)始逐步推算下來(lái)。 常規(guī)四叉樹(shù)并不廣泛用于存儲(chǔ)數(shù)據(jù)，其價(jià)值在于建立索引文件，進(jìn)行數(shù)據(jù)檢索。,26,2）線性四叉樹(shù),只記錄葉結(jié)點(diǎn)的信息，包括葉結(jié)點(diǎn)的位置，深度（幾次分割）和屬性。 葉結(jié)點(diǎn)的編號(hào)遵循一定的規(guī)則，這種編號(hào)稱(chēng)為地址碼，常用的有四進(jìn)制、十進(jìn)制Morton碼 優(yōu)點(diǎn)： 存貯量小，只對(duì)葉結(jié)點(diǎn)編碼，節(jié)省了大量中間結(jié)點(diǎn)的存儲(chǔ)，地址碼隱含著結(jié)點(diǎn)的位置和分割次數(shù)。 線性四叉樹(shù)可直接尋址，通過(guò)其坐標(biāo)值直接計(jì)算其Morton碼，而不用建立四叉樹(shù)。 定位碼容易存儲(chǔ)和執(zhí)行實(shí)現(xiàn)集合相加等組合操作。,27,

13、3）四進(jìn)制的Morton碼,28,方法1（自上而下分割）其始行列號(hào)從0計(jì) 由葉結(jié)點(diǎn)找Morton碼。 A、分割一次，增加一位數(shù)字，大分割在前，小分割在后。所以，碼的位數(shù)表示分割的次數(shù)。 B、每一個(gè)位均是不大于3的四進(jìn)制數(shù)，表達(dá)位置。 由Morton碼找出四叉樹(shù)葉結(jié)點(diǎn)的具體位置。,03,B,A,方法2（自下而上合并的方法）,1）計(jì)算二維矩陣每個(gè)元素的下標(biāo)對(duì)應(yīng)的MQ 其始行列號(hào)從0計(jì)。 2) 按碼的升序排成線性表，放在連續(xù)的內(nèi)存塊中。 3）依次檢查每四個(gè)相鄰的MQ對(duì)應(yīng)的屬性值，相同合并（不同碼位去掉），不同則存盤(pán),直到?jīng)]有能夠合并的子塊為止。,29,30,4）十進(jìn)制的Morton碼-MD,四進(jìn)制M

14、orton碼直觀上符合四叉樹(shù)分割，但許多語(yǔ)言不支持四進(jìn)制變量，需用十進(jìn)制表示Morton碼. 1、一種按位操作的方法： (1)行、列號(hào)轉(zhuǎn)換為二進(jìn)制 Ib= 1 0 Jb= 1 1 (2)I行J列交叉 1 1 0 1 = 13 (3)再化為十進(jìn)制. 實(shí)質(zhì)上是按左上、右上、左下、右下的順序，從零開(kāi)始對(duì)每個(gè)柵格進(jìn)行自然編碼。,31,5）線性四叉樹(shù)的二維行程編碼,右圖的壓縮處理過(guò)程為： 1.按Morton碼讀入一維數(shù)組。 Morton碼：0 1 2 3 4 5 6 7 8 9 10 1112 13 14 15 象元值：A A A B A A B B A A A A B B B B 2.四相鄰象元合并，

15、只記錄第一個(gè)象元的Morton碼。 0 1 2 3 4 5 6 7 8 12 A A A B A A B B A B 3.進(jìn)一步用游程長(zhǎng)度編碼壓縮。 0 3 4 6 8 12 A B A B A B,32,四叉樹(shù)編碼法的優(yōu)點(diǎn),1）容易而有效地計(jì)算多邊形的數(shù)量特征； 2）陣列各部分的分辨率是可變的，邊界復(fù)雜部分四叉樹(shù)較高即分級(jí)多，分辨率也高，而不需表示許多細(xì)節(jié)的部分則分級(jí)少，分辨率低，因而既可精確表示圖形結(jié)構(gòu)又可減少存貯量； 3）柵格到四叉樹(shù)及四叉樹(shù)到簡(jiǎn)單柵格結(jié)構(gòu)的轉(zhuǎn)換比其它壓縮方法容易； 4）多邊形中嵌套異類(lèi)小多邊形的表示較方便。,33,四叉樹(shù)編碼缺點(diǎn),此外，目前應(yīng)用四叉樹(shù)還存下列問(wèn)題： 1)

16、 矢/柵正反變換還不理想。 2) 建立四叉樹(shù)耗費(fèi)機(jī)時(shí)很多。 3) 四叉樹(shù)雖可修改，但很費(fèi)事 4) 四叉樹(shù)未能直接表示物體間的拓?fù)潢P(guān)系。 5) 與非樹(shù)表示法比較，四叉樹(shù)表示法的缺點(diǎn)在于轉(zhuǎn)換的不穩(wěn)定性或叫滑動(dòng)變異 例如，兩個(gè)圖像的差異僅由于平移，就會(huì)構(gòu)成極為不同的四叉樹(shù)，因而很難根據(jù)四叉樹(shù)來(lái)判斷這兩個(gè)圖像是否全同，故不利于做形狀分析和模式識(shí)別， 6) 一個(gè)物體的圖像在構(gòu)成四叉樹(shù)時(shí)會(huì)被分割到若干個(gè)象限中，使它失去了內(nèi)在的相關(guān)性。,34,5.塊狀編碼(block code),采用方形區(qū)域作為記錄單元，每個(gè)記錄單元包括相鄰的若干柵格，數(shù)據(jù)結(jié)構(gòu)由初始位置(行、列號(hào))和半徑，再加上記錄單元代碼組成。 右圖用12個(gè)單位正方形，5個(gè)4單位的正方形和2個(gè)16 單位的正方形就能完整表示，具體編碼如下： (1,1,2,9)，(1,3,1,9)，(1,4,1,9)，(1,5,2,0)，(1,7,2,0)， (2,3,1,9)，(2,4,1,0)，(3,1,1,0)，(3,2,1,9)，(3,3,1,9)， (3,4,1,0)，(3,5,2,7)，(3,7,2,0)，(4,4,1,0)，(4,2,1,0)， (4,3,1,0)，(4,4,1,0)，(5,1,4,0)，(5,5,4,7) 特點(diǎn)： 一個(gè)多邊形所包含的正方形越大，多邊形的邊界越簡(jiǎn)單，塊狀編碼的效率就越好。 塊狀編碼對(duì)大而簡(jiǎn)單的多邊形更為