矢量数据和栅格数据

矢量数据和栅格数据
2009年10月17日
　　
1. 矢量数据和栅格数据
　　矢量数据 Vector Data
　　在直角坐标系中，用X、Y坐标表示地图图形或地理试题的位置和形状的数据。矢量数据一般通过记录坐标的方式来尽可能将地理实体的空间位置表现的准确无误。
　　点实体：在二维空间中，点实体可以用一对坐标X，Y来确定位置；
　　线实体：线实体可以认为是由连续的直线段组成的曲线，用坐标串的集合（X1，Y1，X2，Y2……Xn，Yn）来记录；
　　面实体：在记录面实体时，通常通过记录面状地物的边界来表现，因而有时也称为多边形数据。
　　栅格数据 Raster Data
　　按格网单元的行和列排列的、具有不同灰度值或颜色的阵列数据。栅格数据的每个元素可用行和列唯一地标识，而行和列的数目则取决于栅格的分辨率（或大小）和实体的特性。
　　2. 栅格和矢量数据结构的比较与选择
　　空间数据的栅格结构和矢量结构是模拟地理信息的截然不同的两种方法。几年以前，人们习惯的观点是：这两种结构势不两立、互不相容。原因是栅格数据结构需要大量的计算机内存来存储和处理地理数据，才能达到与矢量数据结构相同的空间分辨率，而矢量结构在某些特定形式的处理中，如象多边形叠加、空间均值处理等都表现出大量的技术问题没有解决。同时栅格结构是“属性明显，位置隐含”，而矢量结构是“位置明显，属性隐含”。栅格数据结构十分有利于空间分析，但输出的专题地图既不美观也不够精确；相反矢量数据结构存储量小，并且能输出精美的地图，但空间分析相当困难。
　　近几年来，人们越来越清楚地认识到：原来把栅格数据和矢量数据结构的差别当成重要的概念差别是不正确的，事实上都是技术问题。计算机技术的发展使运算速度、存储能力、地理数据的空间分辨率大大提高。为了更有效地利用GIS，人们面临的问题之一是栅格数据和矢量数据结构的恰当选择问题。
　　从图形质量出发，最初研究和发展的是矢量数据处理技术。原因很简单：矢量数据结构是人们最熟悉的图形表达形式。但到70年代后期，许多实际工作者都认为在许多情况下，栅格方案更有效。例如多边形周长、面积、总和、平均值的计算、从一点出发的半径等，在栅格数据中都简化为简单的计数操作。又因为栅格坐标是规则的，删除和提取数据都可按位置确定窗口来实现，比矢量数据结构方便得多。另一方面，相互连接的线网络和多边形网络则仍需应用矢量数据结构模式。因为矢量结构更有利于网络分析（交通运输网、给排水网等）和制图应用。但是矢量表示的多边形网络、线网络数据结构中包括了大量拓扑信息即关系数据等多余数据，也使矢量结构的数据库容量大幅度增加。
　　由此可知栅格结构和矢量结构都有各自的优点和局限性。两种数据结构的比较如下：
　　1.矢量数据结构：
　　优点：
　　（1）表示地理数据的精度较高；
　　（2）严密的数据结构，数据量小；
　　（3）用网络连接法能完整地描述拓扑关系；
　　（4）图形输出精确美观；
　　（5）图形数据和属性数据的恢复、更新、综合都能实现。
　　缺点：
　　（1）数据结构复杂；
　　（2）矢量多边形地图或多边形网很难用叠置方法与栅格图进行组合；
　　（3）显示和绘图费用高，特别是高质量绘图、彩色绘图和晕线图等；
　　（4）数学模拟比较困难；
　　（5）技术复杂，多边形内的空间分析不容易实现。
　　2.栅格数据结构：
　　优点：
　　（1）数据结构简单；
　　（2）空间数据的叠置和组合十分容易方便；
　　（3）各类空间分析都很易于进行；
　　（4）数学模拟方便；
　　（5）技术开发费用低。
　　缺点：
　　（1）图形数据量大；
　　（2）用大像元减少数据量时，可识别的现象结构将损失大量信息；
　　（3）地图输出不精美；
　　（4）难以建立网络连接关系；
　　（5）投影变换花的时间多。
　　从上述比较中可以了解到栅格数据和矢量数据结构的适用范围。对于一个与遥感相结合的地理信息系统来说，栅格结构是必不可少的，因为遥感影像是以像元为单位的，可以直接将原始数据或经处理的影像数据纳入栅格结构的地理信息系统。而对地图数字化、拓扑检测、矢量绘图等，矢量数据结构又是必不可少的。较为理想的方案是采用两种数据结构，即栅格结构和矢量结构并存，用计算机程序实现二种结构的高效转换。数字地图根据需要按矢量结构或栅格结构存储最大限度地减少冗余，提高数据精度，对于数据的提取和分析、输出，由程序自动根据操作的需要选取合适的结构，以获取最强的分析能力和时间效率。栅格和矢量双结构，对于提高地理信息系统的空间分辨率、数据压缩率和增强系统分析、输入输出的灵活性十分重要。但是在转换程序效率不高、硬、软件功能不太全的情况下，又要及时开展GIS工作，选用恰当的数据结构是GIS有效运行的前提之一。
　　3.栅格和矢量数据结构相互转换算法
　　矢量结构与栅格结构的相互转换，一直是地理信息系统的技术难题之一。这主要是由于转换程序通常占用较多的内存，涉及复杂的数值运算，而难以在实用系统特别是微机地理信息系统中被采用。近年来已发展了许多高效的转换算法，适用于不同的环境。
　　对于点状实体，每个实体仅由一个坐标对表示，其矢量结构和栅格结构的相互转换基本上只是坐标精度转换问题。线实体的矢量结构由一系列坐标对表示，在变为栅格结构时，除把序列中坐标对变为栅格行列坐标外，还需根据栅格精度要求，在坐标点之间插满一系列栅格点，这也容易由两点式直线方程得到；线实体由栅格结构变为矢量结构与将多边形边界表示为矢量结构相似。因此以下重点讨论多边形（面实体）的矢量结构与栅格结构相互转换问题。
　　（一）矢量格式向栅格格式转换
　　矢量格式向栅格格式转换又称为多边形填充，就是在矢量表示的多边形边界内部的所有栅格上赋予相应的多边形编号，从而形成栅格数据阵列。
　　1.内部点扩散算法；该算法由每个多边形一个内部点（种子点）开始，向其八个方向的邻点扩散，判断各个新加入点是否在多边形边界上，如果是边界点，则新加入点不作为种子点，否则把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该种子点赋予多边形的编号。重复上述过程，直到所有种子点填满该多边形并遇到边界为止。
　　扩散算法程序设计比较复杂，需要在栅格阵列中进行搜索，占用内存很大。在一定栅格精度上，如果复杂图形的同一多边形的两条边界落在同一个或相邻的两个栅格内，会造成多边形不连通，则一个种子点不能完成整个多边形的填充。
　　2.复数积分算法：对全部栅格阵列逐个栅格单元判断栅格归属的多边形编码，判别方法是由待判点对每个多边形的封闭边界计算复数积分，对某个多边形，如果积分值为2πi，则该待判点属于此多边形，赋予多边形编号，否则在此多边形外部，不属于该多边形。
　　复数积分算法涉及许多乘除运算，尽管可靠性好，设计也并不复杂，但运算时间很长，难以在比较低档次的计算机上采用。采用一些优化方法，如根据多边形边界坐标的最大最小值范围组成的矩形来判断是否需要做复数积分运算，可以部分地改善运算时间长的困难。
　　3.射线算法：射线算法可逐点判别数据栅格点在某多边形之外或在多边形内，由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数，如相交偶数次，则待判点在该多边形的外部，如为奇数次，则待判点在该多边形内部。
　　射线算法要计算与多边形交点，因此运算量大。另一个比较麻烦的问题是射线与多边形相交时有些特殊情况如相切、重合等，会影响交点的个数，必须予以排除，由此造成算法的不完善，并增加了编程的复杂性。
　　4.扫描算法：扫描算法是射线算法的改进，通常情况下，沿栅格阵列的行方向扫描，在每两次遇到多边形边界点的两个位置之间的栅格，属于该多边形。扫描算法省去了计算射线与多边形交点的大量运算，大大提高了效率，但一般需要预留一个较大的数组以存放边界点，而且扫描线与多边形边界相交的几种特殊情况仍然存在，需要加以判别。
　　5.边界代数算法：边界代数多边形填充算法（Boundary Algebra Filling，简称BAF），是任伏虎等设计并在微机地理信息系统上实现的一种基于积分思想的矢量格式向栅格格式转换算法。
　　为说明边界代数转换法的原理，先考虑图3－23所示单个多边形的简单情况，模仿积分求多边形区域面积的过程，初始化的栅格阵列各栅格值为零，欲填充多边形编号为a的区域，即将区域内栅格点的值变为a，而区域外各点仍保持原值零。转换时，以栅格行列为参考坐标轴，由多边形边界上某点为起点顺时针搜索边界线，当边界线段为上行时（图3－23（a）），位于搜索边界曲线左侧的具有相同行坐标的所有栅格点被减去一个值a；当边界线段为下行时（图3－23（b）），则将边界曲线左边（从曲线前进方向看为右侧）所有具相同行坐标的栅格点加上一个值a，当沿边界搜索运算一周回到起始点后，所有多边形内部的栅格点都被赋值a，而多边形外的栅格点的值不变。
　　事实上，每幅地图都是由多个多边形区域组成的。如果把不属于任何多边形的区域（包括无穷远点）看成一个编号为零的特殊区域，则每一条边界弧段都与两个不同编号的多边形相邻，按边界弧段的前进方向分别称为左、右多边形。对图3－24所示的3个多边形的6条边，有如表3－5所示的多边形编号。
　　表3-5 线号与左右多边形号的对应关系
　　对多边形n1：线Ⅰ上行－n1，下行+n1；线Ⅳ上行+n1；线Ⅵ下行+n1；
　　对多边形n2：线Ⅱ上行+n2，下行－n2；线Ⅳ上行－n2；线Ⅲ上行－n2；
　　对多边形n3：线Ⅳ下行-n3，线Ⅲ上行+n3；线Ⅴ下行-n3，上行+n3。
　　对所有运算按线号进行排列，把图外区域作为编号为零的区域参加计算，下面括号内标出的为相应线的左或右多边形。
　　线Ⅰ上行：+0（左） -n1（右）
　　下行：-0（左） +n1（右）
　　线Ⅱ上行：+n2（左） -0（右）
　　下行：-n2（左） +0（右）
　　线Ⅲ上行：+n3（左） -n2（右）
　　线Ⅳ上行：+n1（左） -n2（右）
　　线Ⅴ上行：+n3（左） －0（右）
　　下行：-n3（左） +0（右）
　　线Ⅵ下行：-n3（左） +n1（右）
　　由此得到边界代数算法的基本思想：对每幅地图的全部具有左右多边形编号的边界弧段，沿其前进的方向逐个搜索，当边界上行时，将边界线位置与左图框之间的网格点加上一个值=（左多边形编号）-（右多边形编号）；当边界线下行时，将边界线位置与左图框的栅格点加上一个值=（右多边形编号）-（左多边形编号），而不管边界线的排列顺序。
　　边界代数法与其它算法的不同之处在于它不是逐点搜寻判别边界，而是根据边界的拓扑信息，通过简单的加减代数运算将拓扑信息动态地赋予各栅格点，实现了矢量格式到栅格格式的转换。由于不需考虑边界与搜索轨迹之间的关系，因此算法简单，可靠性好，而且由于仅采用加减代数运算，每条边界仅计算一次，免去了公共边界重复运算，又可不考虑边界存放的顺序，因此运算速度快，同时较少受内存容量的限制，特别适用于微机地理信息系统。
　　（二）栅格格式向矢量格式的转换
　　栅格格式向矢量格式转换的目的，是为了将栅格数据分析的结果，通过矢量绘图装置输出，或者为了数据压缩的需要，将大量的面状栅格数据转换为由少量数据表示的多边形的边界。但是更重要的是为了将自动扫描仪获取的栅格数据加入矢量形式的数据库。
　　多边形栅格格式向矢量格式转换，就是提取以相同编号的栅格集合表示的多边形区域的边界和边界的拓扑关系，并表示成多个小直线段的矢量格式边界线的过程。
　　栅格格式向矢量格式转换通常包括以下四个基本步骤：
　　（1）多边形边界提取：采用高通滤波将栅格图像二值化或以特殊值标识边界点；
　　（2）边界线追踪：对每个边界弧段由一个节点向另一个节点搜索，通常对每个已知边界点需沿除进入方向的其它7个方向搜索下一个边界点，直到连成边界弧段。
　　（3）拓扑关系生成：对于矢量表示的边界弧段，判断其与原图上各多边形的空间关系，形成完整的拓扑结构，并建立与属性数据的联系。
　　（4）去除多余点及曲线圆滑：由于搜索是逐个栅格进行的，必须去除由此造成的多余点记录，以减少数据冗余。搜索结果曲线由于栅格精度的限制可能不够圆滑，需要采用一定的插补算法进行光滑处理。常用的算法有线性叠代法、分段三次多项式插值法、正轴抛物线平均加权法、斜轴抛物线平均加权法、样条函数插值法等。
　　栅格向矢量转换中最为困难的是边界线搜索、拓扑结构生成和多余点去除。任伏虎等发展了一种栅格数据库数据双边界直接搜索算法（Double Boundary Direct Finding，缩写为DBDF），较好地解决了上述问题。
　　双边界直接搜索算法的基本思想是通过边界提取，将左右多边形信息保存在边界点上，每条边界弧段由两个并行的边界链组成，分别记录该边界弧段的左右多边形编号。边界线搜索采用2×2栅格窗口，在每个窗口内的四个栅格数据的模式可以唯一地确定下一个窗口的搜索方向和该弧段的拓扑关系，这一方法加快了搜索速度，拓扑关系也很容易建立。具体步骤如下：
　　（1）边界点和节点提取：采用2×2栅格阵列作为窗口顺序沿行、列方向对栅格图像全图扫描，如果窗口内四个栅格有且仅有两个不同的编号，则该四个栅格标识为边界点并保留各栅格所有多边形原编号；如果窗口内四个栅格有三个以上不同编号，则标识为节点（即不同边界弧段的交汇点），保证各栅格原多边形编号信息。对于对角线上栅格两两相同的情况，由于造成了多边形的不连通，也作为节点处理（图3―26、图3―27、图3―28）。
　　（2）边界线搜索与左右多边形信息记录：边界线搜索是逐个弧段进行的，对每个弧段从一组已标识的四个节点开始，选定与之相邻的任意一组四个边界点和节点都必定属于某一窗口的四个标识点之一。首先记录开始边界点组的两个多边形编号作为该弧段的左右多边形，下一点组的搜索方向则由前点组进入的搜索方向和该点的可能走向决定，每个边界点组只能有两个走向，一个是前点组进入的方向，另一个则可确定为将要搜索后续点组的方向。例如图3－28（c）所示边界点组只可能有两个走向，即下方和右方，如果该边界点组由其下方的一点组被搜索到，则其后续点组一定在其右方；反之，如果该点在其右方的点组之后被搜索到（即该弧段的左右多边形编号分别为b和a），对其后续点组的搜索应确定为下方，其它情况依次类推。可见双边界结构可以唯一地确定搜索方向，从而大大地减少搜索时间，同时形成的矢量结构带有左右多边形编号信息，容易建立拓扑结构和与属性数据的联系，提高转换的效率。
　　（3）多余点去除：多余点的去除基于如下思想：在一个边界弧段上连续的三个点，如果在一定程度上可以认为在一条直线上（满足直线方程），则三个点中间一点可以被认为是多余的，予以去除。即满足：
　　由于在算法上的实现，要尽可能避免出现除零情形，可以转化为以下形式：
　　（x1-x2）（y1-y3）=（x1-x3）（y1-y2）
　　或
　　（x1-x3）（y2-y3）=（x2-x3）（y1-y3）
　　其中（x1，y1），（x2，y2），（x3，y3）为某精度下边界弧段上连续三点的坐标，则（x2，y2）为多余点，可予以去除。
　　多余点是由于栅格向矢量转换时逐点搜索边界造成的（当边界为或近似为一直线时），这一算法可大量去除多余点，减少数据冗余。