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压缩栅格数据结构n游程长度编码n链式数据
6、编码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行行2像元像元1n波段波段2 像元
7、像元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),(0,4),(9,3),(0,5),(0,1)(9
8、,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不适合于类型连续变化或类型区域分散的数据。203.链式数据编码（Chain Encoding，弗里曼Freeman）p链式编码主要是。它把线状地物和面状地物的边界表示为：由某一起始点开始并按某些基本方向确定的。基本
9、方向可定义为：东0，东南l，南2，西南3，西4，西北5，北6，东北7等八个基本方向。p编码过程：n起始点的寻找一般遵循从上到下，从左到右从上到下，从左到右的原则；n当发现没有记录过的点，且数值不为0时，就是一条线或边界的；n记下该，然后按顺时针方向寻迹，找到相邻的等值点，并按八个方向编码。213.链式数据编码（Chain Encoding，弗里曼Freeman）链式编码表特征码 起点行 起点列 链码 线 1 5 3223323 面 3 6 0213246676226 67 70 01 12 23 34 45 5链式编码的方向代码链式编码的方向代码 链式编码示意图链式编码示意图 3 32 22
10、23 33 32 23 33 32 24 46 66 67 76 60 02 21 1起始点起始点起始点起始点4 4p优点：n链式编码对多边形的表示具有很强的数据压缩能力n且具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进部分等都比较容易，比较适于存储图形数据。p缺点：n对边界做合并和插入等修改编辑比较困难；n类似矢量结构，不具有区域的性质，对叠置运算如组合、相交等则很难实施；n而且由于链码以每个区域为单位存储边界，相邻区域的边界则被重复存储而产生冗余。234.四叉树编码（Quad tree Encoding）p四叉树概述：一种可变分辨率的非均匀网格系统。p基本思想：将一幅栅格数据层
11、或图像等分为四部分，逐块检查其格网属性值（或灰度）；如果某个子区的所有格网值都具有相同的值，则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区；这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。n最上面的一个结点叫做根结点，它对应于整个图形。n不能再分的结点称为叶子结点，可能落在不同的层上，该结点代表子象限单一的代码，所有叶子结点所代表的方形区域覆盖了整个图形。n从上到下，从左到右为叶子结点编号，最下面的一排数字表示各子区的代码。p为了保证四叉树分解能不断的进行下去，要求图形必须为2n2n的栅格阵列。n 为极限分割次数，n1是四叉树最大层数或最大高度.24方法：1.自上而下
12、2.自下而上 A B A A A B A A B B25AAAAA BBBAABBAABBB BA AAAAAA BBBAABBAABBB BA A1）常规四叉树p记录这棵树的叶结点外，中间结点，结点之间的联系用指针联系，p每个结点需要：n父结点指针、四个子结点的指针和本结点的属性值。p指针不仅增加了数据的存储量，还增加了操作的复杂性：n如层次数（分割次数）由从父结点移到根结点的次数来确定，结点所代表的图像块的位置需要从根节点开始逐步推算下来。p常规四叉树并不广泛用于存储数据，其价值在于建立索引文件，进行数据检索。262）线性四叉树p只记录叶结点的信息，包括叶结点的位置，深度（几次分割）和属性
13、。p叶结点的编号遵循一定的规则，这种编号称为地址码，常用的有四进制、十进制Morton码p优点：存贮量小，只对叶结点编码，节省了大量中间结点的存储，地址码隐含着结点的位置和分割次数。线性四叉树可直接寻址，通过其坐标值直接计算其Morton码，而不用建立四叉树。定位码容易存储和执行实现集合相加等组合操作。27 3）四进制的Morton码024.44.211321kkkQqqqqqqqMk28方法1（自上而下分割）其始行列号从0计 由叶结点找Morton码。A、分割一次，增加一位数字，大分割在前，小分割在后。所以，。B、每一个位均是不大于3的四进制数，表达位置。由Morton码找出四叉树叶结点的具
14、体位置。0123AAAAA BBBAABBA A AABB0303B BA A方法2（自下而上合并的方法）1）计算二维矩阵每个元素的下标对应的MQ 其始行列号从0计。2)按码的升序排成线性表，放在连续的内存块中。3）依次检查每四个相邻的MQ对应的属性值，相同合并（不同码位去掉），不同则存盘,直到没有能够合并的子块为止。bbQJIM*2290110110A000A001A010A0111A002B003B012B01310A020A021B030B03111A022A023B032B033304）十进制的Morton码-MDp四进制Morton码直观上符合四叉树分割，但许多语言不支持四进制变量，
15、需用十进制表示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 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
16、 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）阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量；3）栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方
17、法容易；4）多边形中嵌套异类小多边形的表示较方便。33四叉树编码缺点p此外，目前应用四叉树还存下列问题：1)矢/栅正反变换还不理想。2)建立四叉树耗费机时很多。3)四叉树虽可修改，但很费事4)四叉树未能直接表示物体间的拓扑关系。5)与非树表示法比较，四叉树表示法的缺点在于转换的不稳定性或叫滑动变异例如，两个图像的差异仅由于平移，就会构成极为不同的四叉树，因而很难根据四叉树来判断这两个图像是否全同，故不利于做形状分析和模式识别，6)一个物体的图像在构成四叉树时会被分割到若干个象限中，使它失去了内在的相关性。345.块状编码块状编码(block code)p采用方形区域作为记录单元，每个记录单元包
18、括相邻的若干栅格，数据结构由初始位置(行、列号)和半径，再加上记录单元代码组成。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一个多边形所包含的正方形越大，多边形
19、的边界越简单，块状编码的效率就越好。n块状编码对大而简单的多边形更为有效，而对那些碎部较多的复杂多边形效果并不好。n块状编码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而对某些运算不适应，必须在转换成简单数据形式才能顺利进行。35栅格数据压缩存储的编码方法36AAAAARAAARAAARAARAAAAAAAAAGGAAGGGGGGGAGGGAGGAAAAAARAAAARAAARRAAA143258761234567801234567起点行列号，单位矢量R:(1,5),3,2,2,3,3,2,3链式编码游程长度编码逐行编码数据结构:行号,属性,重复次数A,4,R,1,A,6,.块状编码正方形区域为记录单元数据结构:初始位置,半径,属性(1,1,3,A),(1,5,1,R),(1,6,2,A),NE SWNWSEGGGGAGGAAGAAA四叉树编码
