空间数据结构及编码.ppt

《空间数据结构及编码.ppt》由会员分享，可在线阅读，更多相关《空间数据结构及编码.ppt（50页珍藏版）》请在优知文库上搜索。

1、空间数据结构及编码空间数据结构及编码 1.定义：定义： 是指以地球表面空间位置为参照的是指以地球表面空间位置为参照的自然、社会和人文经济景观数据，可以是图形、自然、社会和人文经济景观数据，可以是图形、图像、文字、表格和数字等。图像、文字、表格和数字等。它是由系统的建立者通过数字化仪、扫描仪、键盘、它是由系统的建立者通过数字化仪、扫描仪、键盘、磁带机或其他系统通讯输入磁带机或其他系统通讯输入GISGIS，是系统程序作用的对，是系统程序作用的对象，是象，是GISGIS所表达的现实世界经过模型抽象的实质性内所表达的现实世界经过模型抽象的实质性内容容一、空间数据基本概念一、空间数据基本概念2.空间数据

2、特点：空间数据特点： 数据的空间性数据的空间性 数据的属性数据的属性 数据的时间性数据的时间性3.在在GIS中，空间数据主要包括中，空间数据主要包括 ： 1）某个已知坐标系中的位置）某个已知坐标系中的位置 2）实体间的空间关系）实体间的空间关系 3）与几何位置无关的属性）与几何位置无关的属性4.空间数据的拓扑关系空间数据的拓扑关系地理要素之间的空间区位关系可抽象为点、线（或弧）、多地理要素之间的空间区位关系可抽象为点、线（或弧）、多边形（区域）之间的空间几何关系，其关系边形（区域）之间的空间几何关系，其关系如下如下 欧氏平面上实体对象所具有的拓扑和非拓扑属性 拓扑属性拓扑属性一个点在一个弧段的

3、端点一个点在一个弧段的端点一个弧段是一个简单弧段（弧段自身不相交）一个弧段是一个简单弧段（弧段自身不相交）一个点在一个区域的边界上一个点在一个区域的边界上一个点在一个区域的内部一个点在一个区域的内部一个点在一个区域的外部一个点在一个区域的外部一个点在一个环的内部一个点在一个环的内部一个面是一个简单面（面上没有一个面是一个简单面（面上没有“岛岛”）一个面的连续性（给定面上任意两点，从一点可以完全在面一个面的连续性（给定面上任意两点，从一点可以完全在面的内部沿任意路径走向另一点）的内部沿任意路径走向另一点）非拓扑属非拓扑属性性两点之间的距离两点之间的距离一个点指向另一个点的方向一个点指向另一个点的

4、方向弧段的长度弧段的长度一个区域的周长一个区域的周长一个区域的面积一个区域的面积 基本的拓扑关系包括：连接性、包含和邻接性 定义：又称为网格结构，它是将地表划分定义：又称为网格结构，它是将地表划分成为紧密相邻的网格阵列。每个网格的位成为紧密相邻的网格阵列。每个网格的位置由行列号定义。它包含一个代码，以表置由行列号定义。它包含一个代码，以表示该网格的属性或指向属性记录的指针。示该网格的属性或指向属性记录的指针。 注意：栅格数据模型是将连续空间离散化。注意：栅格数据模型是将连续空间离散化。1.概念概念二、栅格数据结构二、栅格数据结构二 维 空 间 坐二 维 空 间 坐标 网 或 其 局标 网 或

5、其 局部部特别方便计算机特别方便计算机运作的数据组织运作的数据组织形式形式矩阵数矩阵数组组规整栅格：规整栅格：研究区域划分为规整研究区域划分为规整格网，空间位置数据格网，空间位置数据隐含其中隐含其中每一网格上放置空每一网格上放置空间对象在该位置上间对象在该位置上的属性数据的属性数据栅格空间数据模型栅格空间数据模型 三角形、方格和六角形划分三角形、方格和六角形划分 2.图形栅格数据结构表示图形栅格数据结构表示0 0 0 0 2 0 000 0 0 2 0 0 000 1 0 2 0 3 300 0 0 2 3 3 330 0 2 0 3 3 330 0 2 0 0 3 300 2 0 0 0 0

6、 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 6 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 7 4 4 4 4 4 4 7 7 7 7 4 7 7 7 4 4 4 4

7、8 7 7 8 0 8 4 0 8 7 7 8 0 8 8 0 0 8 0 0 8 8 7 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 线线面面点点3.栅格结构编码方式栅格结构编码方式 直接栅格编码直接栅格编码 行程编码行程编码 块码块码 链式编码链式编码 四叉树结构四叉树结构 二维行程编码二维行程编码下一页基本思路基本思路：对于一幅栅格图像，常常有行（或列）方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。游程长度编码（游程长度编码（Run-Length Codes）1）只在各行（或列）数据的代码发生变化时）只在各行（或列

8、）数据的代码发生变化时依次记录该代码以及相同的代码重复的个依次记录该代码以及相同的代码重复的个数，从而实现数据的压缩。数，从而实现数据的压缩。两种方案两种方案（属性值，长度）（属性值，长度） 例如例如 （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）。）。074444447777477744448778084087780880080088788

9、8880000888800000888压缩比的大小是与图的复杂程度成反比压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变的，在变化多的部分，游程数就多，变化少的部分游程数就少，图件越简单，化少的部分游程数就少，图件越简单，压缩效率就越高压缩效率就越高44：64 2）逐个记录各行（或列）代码发）逐个记录各行（或列）代码发生变化的位置和相应代码生变化的位置和相应代码编码如下（沿列方向）编码如下（沿列方向） （1，0），（），（2，4），（），（4，0）；）； （1，4），（），（4，0）；）； （1，4），（），（5，8），（），（6，0）；）； （1，7），（），（2，4），

10、（），（4，8），（），（7，0）；）； （1，7），（），（2，4），（），（3，8），（），（8，0）；）； （1，7），（），（3，8）；）； （1，7），（），（6，8）；）； （1，7），（），（5，8）。）。（属性发生变化的位置（属性发生变化的位置 ，属性值），属性值）0744444477774777444487780840877808800800887888880000888800000888 特点：属性的变化愈少，行程愈长，则压特点：属性的变化愈少，行程愈长，则压缩的比例越大，压缩比与图的复杂程度成缩的比例越大，压缩比与图的复杂程度成反比。反比。 块码是游程长度编码扩展到二维的

11、情况，采用方块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置（行、列号）和半径，干栅格，数据结构由初始位置（行、列号）和半径，再加上记录单位的代码组成。再加上记录单位的代码组成。块块 码码0744444477774777444487780840877808800800887888880000888800000888对图所示图像的块码编码如下：对图所示图像的块码编码如下： (1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7), (1,6,2,7),(1,8,1,7

12、),(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)。该例中块码用了该例中块码用了120个整数，比直接编码还多，这是因为例中为描述方便，个整数，比直接编码还多

13、，这是因为例中为描述方便，栅格划分很粗糙，在实际应用中，栅格划分细，数据冗余多的多，才能显栅格划分很粗糙，在实际应用中，栅格划分细，数据冗余多的多，才能显出压缩编码的效果，而且还可以作一些技术处理，如行号可以通过行间标出压缩编码的效果，而且还可以作一些技术处理，如行号可以通过行间标记而省去记录，行号和半径等也不必用双字节整数来记录，可进一步减少记而省去记录，行号和半径等也不必用双字节整数来记录，可进一步减少数据冗余。数据冗余。 链码（链码（Chain Codes） 链码又称为弗里曼链码链码又称为弗里曼链码Freeman或边界或边界链码，链码可以有效地压缩栅格数据，而链码，链码可以有效地压缩栅格

14、数据，而且对于估算面积、长度、转折方向的凹凸且对于估算面积、长度、转折方向的凹凸度等运算十分方便，比较适合于存储图形度等运算十分方便，比较适合于存储图形数据数据。缺点缺点是对边界进行合并和插入等修改编辑是对边界进行合并和插入等修改编辑工作比较困难，对局部的修改将改变整体工作比较困难，对局部的修改将改变整体结构，效率较低，而且由于链码以每个区结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界将被域为单位存储边界，相邻区域的边界将被重复存储而产生冗余重复存储而产生冗余。 基本思想基本思想：将一幅栅格地图或图像等分为四部分，：将一幅栅格地图或图像等分为四部分，逐块检查其格网属性值（

15、或灰度），如果某个子逐块检查其格网属性值（或灰度），如果某个子区的所有格网值都相同，则这个子区就不再继续区的所有格网值都相同，则这个子区就不再继续分割，否则还要把这个子区再分割，直到每个子分割，否则还要把这个子区再分割，直到每个子块都只含有相同的属性值或灰度为止。块都只含有相同的属性值或灰度为止。 四叉树结构四叉树结构四叉树编码具有可变的分辨率，并且有区域性质，四叉树编码具有可变的分辨率，并且有区域性质，压缩数据灵活，许多运算可以在编码数据上直接实压缩数据灵活，许多运算可以在编码数据上直接实现，大大地提高了运算效率，是优秀的栅格压缩编现，大大地提高了运算效率，是优秀的栅格压缩编码之一码之一11

16、1100001111000011100000111000003344400033444000334400003344000011011010344004034000层1层2层3层（1）（2）（3）（4）（5）（6） （7）（8）（9） （10） （11） （12）（13）（14） （15） （16）（17） （18） （19） 常规四叉树除了记录叶结点之外，还要记常规四叉树除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每录中间结点。结点之间借助指针联系，每个结点需要用六个量表达，即四个叶结点个结点需要用六个量表达，即四个叶结点指针、一个父结点指针和一个结点的属性指针、一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据储存或灰度值。这些指针不仅增加了数据储存量，而且增加了操作的复杂性。量，而且增加了操作的复杂性。常规四叉树与线性四叉树常规四叉树与线性四叉树 线性四叉树只存储最后叶结点的信息。线性四叉树只存储最后叶结点的信息。 包括叶结点的位置、深度和本结点的属性包括叶结点的位置、深度和本结点的属性或灰度值或灰度值 线性四叉树叶结点的编号需要遵循一定的线性四叉树叶