第二章空间数据结构及编码课件

《第二章空间数据结构及编码课件》由会员分享，可在线阅读，更多相关《第二章空间数据结构及编码课件（110页珍藏版）》请在金锄头文库上搜索。

1、第二章 空间数据结构及编码,1、从现实世界到计算机世界,概念模型,数据模型,数据结构,文件格式,四个层次,按照著名数据库专家E.F.Codd的理论认为数据模型实质上是一组为用户服务的规则,这些规则规定其数据结构如何组织以及应当允许进行何种操作。,一 基本概念,2.Gis中地理空间数据组织的主要对象,从地理空间现象或事物到计算机世界,一般也要有概念模型,数据模型,数据结构和文件格式几个层次.这个过程有时统称为地理空间数据建模,Gis怎样组织数据以模拟地理事物和现象的呢?,举例,我们将gis所抽象,表达的地理事物和现象,称为空间对象;空间对象的位置相互关系,称为空间关系,a空间对象,点状空间对象(

2、0维对象) 线状空间对象 面状空间对象 体状空间对象,除空间维数特性外,空间对象还可以从其复杂性,规则性,人为性等角度认识和区分,b空间关系通常分为3类 度量空间关系 顺序空间关系 拓扑空间关系 -连接性 -包含 -邻接性,3.空间数据结构和空间数据模型两个概念之间的关系,空间数据结构和空间数据模型研究地理空间数据组织和管理.两者之间的关系,与一般的数据结构和数据模型的关系有两点相似之处.其一,空间数据结构所作的数据组织工作,比空间数据模型更基层些,它偏重数据表达的物理实现,而空间数据模型涉及到空间数据管理的层次.其二，同普通数据的数据模型一样,空间数据模型的命名通常与相应的空间数据结构相同.

3、,4.空间分析与非空间分析,5.空间数据 定义 特点： 数据的空间性 数据的属性 数据的时间性,6.空间数据的编码,7.空间数据的拓扑关系,地理要素之间的空间区位关系可抽象为点、线（或弧）、多边形（区域）之间的空间几何关系，其关系如下,欧氏平面上实体对象所具有的拓扑和非拓扑属性,弧属性表（AAT）,多边形属性表（PAT）,1. 本图有多少个多边形和弧？ 2. 哪个多边形是包含于另一个中？ 3. 哪个多边形和多边形102相邻？ 4. 手工建立一个简单示意图表明本图的空间格局,二、栅格数据结构,定义：又称为网格结构，它是将地表划分成为紧密相邻的网格阵列。每个网格的位置由行列号定义。它包含一个代码，

4、以表示该网格的属性或指向属性记录的指针。 注意：栅格数据模型是将连续空间离散化，即用二维铺盖或划分覆盖整个连续空间，这种铺盖可以分为规则的和不规则的,1.概念,三角形、方格和六角形划分,栅格数据模型,2.图形栅格数据结构表示,线,面,点,3.决定栅格单元代码的方式,面积占优法,中心点法,重要性法,4.栅格结构编码方式,直接栅格编码 行程编码 块码 链式编码 四叉树结构 二维行程编码,基本思路：对于一幅栅格图像，常常有行（或列）方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。,游程长度编码（Run-Length Codes）,1）只在各行（或列）数据的代码发生变化

5、时依次记录该代码以及相同的代码重复的个数，从而实现数据的压缩。,两种方案,（属性值，长度）,例如 （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）。,压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变化少的部分游程数就少，图件越简单，压缩效率就越高,44：64,2）逐个记录各行（或列）代码发生变化的位置和相应代码,编码如下（沿列方向） （1，0），（2，4

6、），（4，0）； （1，4），（4，0）； （1，4），（5，8），（6，0）； （1，7），（2，4），（4，8），（7，0）； （1，7），（2，4），（3，8），（8，0）； （1，7），（3，8）； （1，7），（6，8）； （1，7），（5，8）。,（属性值，属性发生变化的位置）,特点：属性的变化愈少，行程愈长，则压缩的比例越大，压缩比与图的复杂程度成反比。,块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置（行、列号）和半径，再加上记录单位的代码组成。,块 码,对图所示图像的块码编码如下： (1,1,1,0),(1,2,

7、2,4),(1,4,1,7),(1,5,1,7), (1,6,2,7),(1,8,1,7),(2,1,1,4),(2,4,1,4), (2,5,1,4),(2,8,1,7),(3,1,1,4),(3,2,1,4), (3,3,1,4),(3,4,1,4),(3,5,2,8),(3,7,2,7), (4,1,2,0),(4,3,1,4),(4,4,1,8),(5,3,1,8), (5,4,2,8),(5,6,1,8),(5,7,1,7),(5,8,1,8), (6,1,3,0),(6,6,3,8),(7,4,1,0),(7,5,1,8), (8,4,1,0),(8,5,1,0)。,该例中块码用了

8、120个整数，比直接编码还多，这是因为例中为描述方便，栅格划分很粗糙，在实际应用中，栅格划分细，数据冗余多的多，才能显出压缩编码的效果，而且还可以作一些技术处理，如行号可以通过行间标记而省去记录，行号和半径等也不必用双字节整数来记录，可进一步减少数据冗余。,块码具有可变的分辨率，即当代码变化小时图块大，就是说在区域图斑内部分辨率低；反之，分辨率高。 块码与游程长度编码相似，随着图形复杂程度的提高而降低效率，就是说图斑越大，压缩比越高；图斑越碎，压缩比越低。 块码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。 然而在某些操作时，则必须把游程长度编码和块码解码，转换为基本栅格结构进行。

9、,链码（Chain Codes）,基本思想：将一幅栅格地图或图像等分为四部分，逐块检查其格网属性值（或灰度），如果某个子区的所有格网值都相同，则这个子区就不再继续分割，否则还要把这个子区再分割，直到每个子块都只含有相同的属性值或灰度为止。,四叉树结构,四叉树编码具有可变的分辨率，并且有区域性质，压缩数据灵活，许多运算可以在编码数据上直接实现，大大地提高了运算效率，是优秀的栅格压缩编码之一,1）从四叉树的特点可知，一幅2n *2n 栅格阵列图，具有的最大深度数为n，可能具有的层次为0，1，2，.n,注 意,2）每一层的栅格宽度，即每层边上包含的最大栅格数，反映了所在叶结点表示的正方形集合的大小，

10、其值为：2（最大深度-当前层次）,例如：一幅23 23 的栅格阵列，它具有的最大深度为3，可能层次分别为0，1，2，3。 其中：第0层边长上的最大栅格数为2（3-0）8 第1层边长上的最大栅格数为2（3-1）4 第2层边长上的最大栅格数为2（3-2）2 第3层边长上的最大栅格数为2（3-3）1,0层,1层,2层,3层,（1）,（2）,（3）,（4）,（5）,（6）,（7）,（8）,（9）,（10）,（11）,（12）,（13）,（14）,（15）,（16）,（17）,（18）,（19）,常规四叉树除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达，即四个叶结点

11、指针、一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据储存量，而且增加了操作的复杂性。,常规四叉树与线性四叉树,线性四叉树只存储最后叶结点的信息。 包括叶结点的位置、深度和本结点的属性或灰度值 线性四叉树叶结点的编号需要遵循一定的规则，这种编号成为地址码，它隐含了叶结点的位置和深度信息。,a. 基于深度和层次码的线性四叉树的编码 它是通过记录叶结点的深度码和层次码来描述叶结点的位置码,几种线性四叉树的编码,0层,1层,2层,3层,（1）,（2）,（3）,（4）,（5）,（6）,（7）,（8）,（9）,（10）,（11）,（12）,（13）,（14）,（15）,（16）,（17）,

12、（18）,（19）,该地址码的十进制为：？,0层,1层,2层,3层,（1）,（2）,（3）,（4）,（5）,（6）,（7）,（8）,（9）,（10）,（11）,（12）,（13）,（14）,（15）,（16）,（17）,（18）,（19）,b. 基于四进制的线性四叉树编码,0层,1层,2层,3层,（1）,（2）,（3）,（4）,（5）,（6）,（7）,（8）,（9）,（10）,（11）,（12）,（13）,（14）,（15）,（16）,（17）,（18）,（19）,思 考,请为23 23 栅格阵列中的每个栅格建立基于四进制的四叉树编码方式的地址码？ 你能找出何种规律？,先将栅格的行列号转换为二

13、进 制，得二进制行号Iyb，列号Ixb， 则M=2IybIxb 如结点7： M=2*011+011033,如果知道基于四进制四叉树编码方式的地址码，你能知道它的行列号码吗？,思 考,若该位的编码值为0，1，则行号Iyb值为0； 若该位的编码值为2，3，则行号Iyb值为1； 若该位的编码值为0，2，则列号Ixb值为0； 若该位的编码值为1，3，则列号Ixb值为1； 如：M码为 ： 1 0 3 二进制行值Iyb为 ：0 0 1 二进制列值Ixb为： 1 0 1,规则：首先将二维栅格数据的行列号转换为二进制，然后交叉放入Morton码中，即为线性四叉树的地址码： 行号5（1 0 1）；列号7（1 1

14、 1） Morton 1 1 0 1 1 155,c. 基于十进制的线性四叉树编码,请快速建立 8*8 栅格阵列中的每个栅格的 Morton,思 考,二维行程编码,二维行程编码,再议游程编码,a.定义 游程编码结构 游程指相邻同值网格的数量，游程编码结构是逐行将相邻同值的网格合并，并记录合并后网格的值及合并网格的长度，其目的是压缩栅格数据量，消除数据间的冗余。 游程编码结构的建立方法是：将栅格矩阵的数据序列X1,X2,X3.XN，映射为相应的二元序列（Ai，Pi），i1，k，且k=n.其中，A为属性值，P为游程，k为游程序号,二元映射,这种结构特别适合于二值图数据的表示，如图,二元映射,b.游

15、程编码能否压缩数据量，主要决定于栅格数据的性质，通常可通过事先测试，估算图层的数据冗余度Re：,Re 1Q/(MN),Q：图层内相邻属性值变化次数的累加和 M：为图层网格的行数 N：为图层网格的列数 当的值大于1/5的情况下，表明栅格数据的压缩可取得明显的效果,c.当栅格数据位数字高程时,当栅格数据为规则的数字地形高程即DEM时，由于这种类型数据的相邻的数据具有高度的相关性，可通过差分映射进行预处理，然后在采用游程长度压缩编码法。例如,差分,d.基于游程编码结构的栅格数据文件的数据组织方式,为了提高系统对这些数据的访问效率，通常采用索引顺序文件的方法来组织数据。当由位置参数访问其属性特征时，利用逻辑顺序和逻辑地址的关系，很快在索引文件中找到指向数据文件欲访栅格的指针，并求出其逻辑地址，就能找到该栅格的属性。,索引文件,数据文件,5.多重属性下的栅格数据模型,数据文件,像元1,X 坐标,Y 坐标,层1属性,层2属性,层3属性,层n属性,像元2,像元n,以像元为记录的序列