1、第4章 空間數據結構1主要內容4.1 矢量數據結構矢量數據結構4.2 柵格數據結構柵格數據結構4.4 鑲嵌數據結構鑲嵌數據結構4.5 柵格結構與矢量數據結構的比較柵格結構與矢量數據結構的比較 24.2 柵格數據結構34.2 柵格數據結構4.2.1 柵格單元的確定柵格單元的確定 4.2.2 完全柵格數據結構完全柵格數據結構 4.2.3 壓縮柵格數據結構壓縮柵格數據結構 44.2 柵格數據結構p網格結構(raster或grid cell)或像元結構(pixel) 以表示空間對象n每個柵格空間對象的屬性特征n其由柵格陣列中每個單元的來確定。p柵格數據結構表示的地表是不連續的，是量化和近似離散的數據，

2、一個柵格單元對應于小塊地理范圍。5p對于柵格數據結構n點點：為一個像元n線線：在一定方向上連接成串的相鄰像元集合。n面面：聚集在一起的相鄰像元集合。6點線面70000090000900000009070070090700760097777900077079000770709000000yx點、線、面數據的點、線、面數據的矢量與柵格矢量與柵格表示表示8Representation of point, line, and area features: raster format on the left and vector format on the right.柵格數據類型柵格數據類型1衛星影像

3、衛星影像2數字高程模型（數字高程模型（DEM）3數字正射影像圖（數字正射影像圖（DOM）4二進制掃描文件二進制掃描文件5數字柵格數字柵格影像影像6圖形文件圖形文件：如：如JPG、TIFF、GIF等等7特定地理信息系統軟件特定地理信息系統軟件的柵格數據的柵格數據 .grd4.2.1柵格單元的確定柵格單元的確定1. 柵格數據的參數（1）。柵格單元通常為矩形或。特殊的情況下按經緯網劃分。（2）。柵格單元的尺寸，即。柵格柵格單元的合理尺寸單元的合理尺寸應能有效地逼近空間對象的分布特征，以保證空間數據的精度。 保證保證最小圖斑不丟失為原則最小圖斑不丟失為原則（3） 和國家基本比例尺地形圖公里網的交點相一

4、致，或者和已有的柵格系統數據相一致，并同時使用作為柵格系統的坐標軸。（4） 柵格的坐標系統與國家坐標系統平行101.柵格數據的參數11X：列：列Y：行：行西南角格網坐標西南角格網坐標（XWS，YWS） （500，500）格網分辨率格網分辨率 302. 柵格數據單元值確定12CAB面面積積占占優優重重要要性性中心點法中心點法A位于柵格中心處位于柵格中心處的地物類型決定的地物類型決定其取值。其取值。常用于常用于連續分布連續分布特性特性的地理現象。的地理現象。C選取最重要的地選取最重要的地物類型為單元值。物類型為單元值。常用于有常用于有特殊意特殊意義而面積較小義而面積較小的的地理要素地理要素A占區域

5、面積最大占區域面積最大的地物類型取值的地物類型取值適用于適用于分類較細、分類較細、地物斑塊較小地物斑塊較小地地理要素理要素為了逼近原始數據精度，除了采用這幾種取值方法外，還可以采用縮小單個柵格單元的面積，增加柵格單元總數的方法 13abc345abcac距離距離: 7/4 (5)面積面積: 7 (6)幾何偏差幾何偏差屬性偏差屬性偏差如ac距離以像元邊線計算則為7，以像元個數為單位則為4。 三角形的面積為6個平方單位，而右圖中則為7個平方單位，這種誤差隨像元的增大而增加。 中心點法中心點法面積占優法面積占優法4. 柵格數據的編碼方法p4.2.2完全柵格數據結構n直接柵格編碼p4.2.3壓縮柵格數

6、據結構n游程長度編碼n鏈式數據編碼n四叉樹編碼n分塊壓縮編碼144.2.2完全柵格數據結構1.直接柵格編碼p將柵格看做一個數據矩陣，逐行逐個記錄代碼數據p優點：簡單、直觀，無壓縮p缺點：存在大量冗余，精度提高有限制。15完全柵格數據的組織完全柵格數據的組織有三種基本方式：基于像元、基于層（波段）和基于行.bsq （band sequential）基于層（波段）的方式16柵格數據文件柵格數據文件波段波段1像元像元1，1像元像元1，2像元像元1，m像元像元m，n波段波段2波段波段k.bil （band interleaved by line）基于行的方式17柵格數據文件柵格數據文件行行1波段波段1

7、行行2像元像元1n波段波段2 像元像元1n波段波段k 像元像元1n行行m.bip （band interleaved by pixel）基于像元方式18柵格數據文件柵格數據文件像元像元1，1像元像元1，2波段波段1波段波段k像元像元m，n2.游程長度編碼（Run-Length Encoding），將每行中具有映射為一個游程，每個游程的數據結構為（A，P），A表示屬性值，P代表該游程。p屬性變化越少，壓縮比例越大，適合于的柵格。199999000099090000900977000000770000007777000077770000777700007777原始柵格數據( 9 , 4 ) , (

8、 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 , 4 ) , ( 7 , 4 ) ,( 0 , 4 ) , ( 7 , 4 ) ,(0,4),(7,4)2.游程長度編碼（Run-Length Encoding）p優點：n柵格加密時，數據量不會明顯增加，壓縮效率高，最大限度保留原始柵格結構，n編碼解碼運算簡單，且易于檢索、疊加、合并等操作，得到廣泛應用。p缺點：n不適合于類型連續變化或類型區域分散

9、的數據。203. 鏈式數據編碼（Chain Encoding，弗里曼Freeman）p鏈式編碼主要是。它把線狀地物和面狀地物的邊界表示為：由某一起始點開始并按某些基本方向確定的。基本方向可定義為：東0，東南l，南2，西南3，西4，西北5，北6，東北7等八個基本方向。p編碼過程：n起始點的尋找一般遵循從上到下，從左到右從上到下，從左到右的原則；n當發現沒有記錄過的點，且數值不為0時，就是一條線或邊界的；n記下該，然后按順時針方向尋跡，找到相鄰的等值點，并按八個方向編碼。213. 鏈式數據編碼（Chain Encoding，弗里曼Freeman） 鏈式編碼表特征碼 起點行 起點列 鏈碼 線 1 5

10、 3223323 面 3 6 0213246676226 67 70 01 12 23 34 45 5鏈式編碼的方向代碼鏈式編碼的方向代碼 鏈式編碼示意圖鏈式編碼示意圖 3 32 22 23 33 32 23 33 32 24 46 66 67 76 60 02 21 1起始點起始點起始點起始點4 4p優點：n鏈式編碼對多邊形的表示具有很強的數據壓縮能力n且具有一定的運算功能，如面積和周長計算等，探測邊界急彎和凹進部分等都比較容易，比較適于存儲圖形數據。p缺點：n對邊界做合并和插入等修改編輯比較困難；n類似矢量結構，不具有區域的性質，對疊置運算如組合、相交等則很難實施；n而且由于鏈碼以每個區域

11、為單位存儲邊界，相鄰區域的邊界則被重復存儲而產生冗余。 234. 四叉樹編碼（Quad tree Encoding）p四叉樹概述：一種可變分辨率的非均勻網格系統。p基本思想：將一幅柵格數據層或圖像等分為四部分，逐塊檢查其格網屬性值（或灰度）；如果某個子區的所有格網值都具有相同的值，則這個子區就不再繼續分割，否則還要把這個子區再分割成四個子區；這樣依次地分割，直到每個子塊都只含有相同的屬性值或灰度為止。n最上面的一個結點叫做根結點，它對應于整個圖形。n不能再分的結點稱為葉子結點，可能落在不同的層上，該結點代表子象限單一的代碼，所有葉子結點所代表的方形區域覆蓋了整個圖形。n從上到下，從左到右為葉子

12、結點編號，最下面的一排數字表示各子區的代碼。p為了保證四叉樹分解能不斷的進行下去，要求圖形必須為2n2n的柵格陣列。n 為極限分割次數，n1是四叉樹最大層數或最大高度.24方法：1. 自上而下2. 自下而上 A B A A A B A A B B25AAAAA BBBAABBAABBB BA AAAAAA BBBAABBAABBB BA A1）常規四叉樹p記錄這棵樹的葉結點外，中間結點，結點之間的聯系用指針聯系，p每個結點需要：n父結點指針、四個子結點的指針和本結點的屬性值。p指針不僅增加了數據的存儲量，還增加了操作的復雜性：n如層次數（分割次數）由從父結點移到根結點的次數來確定，結點所代表的

13、圖像塊的位置需要從根節點開始逐步推算下來。p常規四叉樹并不廣泛用于存儲數據，其價值在于建立索引文件，進行數據檢索。262）線性四叉樹p只記錄葉結點的信息，包括葉結點的位置，深度（幾次分割）和屬性。p葉結點的編號遵循一定的規則，這種編號稱為地址碼，常用的有四進制、十進制Morton碼p優點：存貯量小，只對葉結點編碼，節省了大量中間結點的存儲，地址碼隱含著結點的位置和分割次數。線性四叉樹可直接尋址，通過其坐標值直接計算其Morton碼，而不用建立四叉樹。定位碼容易存儲和執行實現集合相加等組合操作。27 3）四進制的Morton碼024.44.211321kkkQqqqqqqqMk28方法1（自上而

14、下分割）其始行列號從0計 由葉結點找Morton碼。A、分割一次，增加一位數字，大分割在前，小分割在后。所以，。B、每一個位均是不大于3的四進制數，表達位置。 由Morton碼找出四叉樹葉結點的具體位置。 0123AAAAA BBBAABBA A AABB0303B BA A方法2（自下而上合并的方法）1）計算二維矩陣每個元素的下標對應的MQ 其始行列號從0計。2) 按碼的升序排成線性表，放在連續的內存塊中。3）依次檢查每四個相鄰的MQ對應的屬性值，相同合并（不同碼位去掉），不同則存盤,直到沒有能夠合并的子塊為止。bbQJIM*2290110110A000A001A010A0111A002B0

15、03B012B01310A020A021B030B03111A022A023B032B033304）十進制的Morton碼-MDp四進制Morton碼直觀上符合四叉樹分割，但許多語言不支持四進制變量，需用十進制表示Morton碼.1、一種按位操作的方法：(1)行、列號轉換為二進制 Ib= 1 0 Jb= 1 1(2)I行J列交叉 1 1 0 1 = 13(3)再化為十進制. 實質上是按左上、右上、左下、右下的順序，從零開始對每個柵格進行自然編碼。315）線性四叉樹的二維行程編碼右圖的壓縮處理過程為：1.按Morton碼讀入一維數組。 Morton碼：0 1 2 3 4 5 6 7 8 9 10

16、 1112 13 14 15 象元值：A A A B A A B B A A A A B B B B2.四相鄰象元合并，只記錄第一個象元的Morton碼。 0 1 2 3 4 5 6 7 8 12 A A A B A A B B A B3.進一步用游程長度編碼壓縮。 0 3 4 6 8 12 A B A B A B 32A 0A 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B 13A 10A 11B 14B 15A 0A 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B 13A 10A 11B 14B 15四叉樹編碼法的優點1）容易而有效地計算多邊形的數量特征；2

17、）陣列各部分的分辨率是可變的，邊界復雜部分四叉樹較高即分級多，分辨率也高，而不需表示許多細節的部分則分級少，分辨率低，因而既可精確表示圖形結構又可減少存貯量；3）柵格到四叉樹及四叉樹到簡單柵格結構的轉換比其它壓縮方法容易；4）多邊形中嵌套異類小多邊形的表示較方便。33四叉樹編碼缺點p此外，目前應用四叉樹還存下列問題：1) 矢/柵正反變換還不理想。2) 建立四叉樹耗費機時很多。3) 四叉樹雖可修改，但很費事4) 四叉樹未能直接表示物體間的拓撲關系。5) 與非樹表示法比較，四叉樹表示法的缺點在于轉換的不穩定性或叫滑動變異例如，兩個圖像的差異僅由于平移，就會構成極為不同的四叉樹，因而很難根據四叉樹來

18、判斷這兩個圖像是否全同，故不利于做形狀分析和模式識別， 6) 一個物體的圖像在構成四叉樹時會被分割到若干個象限中，使它失去了內在的相關性。345.塊狀編碼塊狀編碼(block code)p采用方形區域作為記錄單元，每個記錄單元包括相鄰的若干柵格，數據結構由初始位置(行、列號)和半徑，再加上記錄單元代碼組成。p右圖用12個單位正方形，5個4單位的正方形和2個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)p特點：n一個多邊形所包含的正方形越大，多邊形的邊界越簡單，塊狀編碼的效率就越好。n塊狀編碼對大而簡單的多邊形更為有效，而對那些碎部較多的復雜多邊形效果并不好。n塊狀編碼在合并、插入、檢查延伸性、計算面積等操作時有明顯的優越性。然而對某些運算不適應，