资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第三章 空间数据模型与数据库,1,矢量结构与栅格结构的相互转换,矢量数据结构向栅格数据结构的转换（,栅格化,）,栅格数据结构向矢量数据结构的转换（,矢量化,）,2,矢量到栅格,栅格化过程包括以下操作：,1）确定栅格矩阵(行列数分辨率)；,2）点的变换,3）线的变换,4）多边形的变换(面的变换),3,1) 确定栅格矩阵,矢量数据转换成栅格数据后，图形的,几何精度,必然要,降低,，所以选择栅格尺寸的大小要尽量满足精度要求，使之不过多地损失地理信息。,为了提高精度，栅格需要细化，但栅格细化，数据量将以平方指数递增，因此，,精度和数据量,是确定栅格大小的,最重要的影响因素,。,4,I=(Ymax-Ymin)/dy,J=(Xmax-Xmin)/dx,I，J为整数，尾数入上去,dx=(Xmax-Xmin)/J,dy=(Ymax-Ymin)/I,1) 确定栅格矩阵,在转换之前需要确定,栅格单元的大小,，栅格单元的大小又称为,栅格图像的分辨率,，直接决定了栅格数据的精度。,Y,X,O,J,I,y,x,(0,0),X,max,Y,min,X,min,Y,max,5,2）点的栅格化,X,Y,6,3）线的栅格化方法,线是由多个直线段组成的，因此线的栅格化的核心就是,直线段如何,由矢量数据,转换,为栅格数据。,栅格化的两种常用方法为:,DDA法,(Digital Differential Analyzer数字微分分析法),Bresenham法,7,DDA法(数字微分分析法),设(x,A,y,A,),(x,B,y,B,)与栅格网的交点为(x,i,y,i,)，则:,其中：,这样从i0计算到in1，即可得直线与格网的n个交点坐标，对其取整就是该点的栅格数据了。,该方法的基本依据是直线的微分方程，即,dy/dx常数,。其本质是,用数值方法解微分方程,，通过同时对x和y各增加一个小增量来计算下一步的x,y值，即这是,一种增量算法,。,在该算法中，必须,以浮点数表示坐标,，且,每次都要舍入取整,，因此，,尽管算法正确，但速度不够快,。,8,Bresenham算法,该算法原来是为绘图机设计的，但同样适合于栅格化。该算法构思巧妙，只需根据,由直线斜率构成的误差项的符号，就可确定下一列坐标的递增值,。,根据直线的斜率，把直线分为8个卦限。下面举斜率在第一卦限的情况为例，其余卦限的情况类似。,该算法的基本思路可描述为：若直线的斜率为,1/2y/x1,，则下一点取(1，1)点，若,0y/x1/2,，则下一点取(1，0)点。,9,在算法实现时，,令起始的误差项,为e-1/2，,然后在推断出下一点后，令eey/x,若e0时，ee-1。,这样只要根据e的符号就可确定下一点的增量，即：,若e0，取(1，1)点,若e0，取(1，0)点,例如，一直线的斜率为1/3，起始点：e0-1/2,取点0,第1点：e1-1/2 +1/3-1/6取点,第2点：e2-1/6 +1/3 = 1/6且e2=-5/6；取点,第3点：e3-5/6+1/3=-1/2取点,第4点：e4-1/2+1/3=-1/6取点,第5点：e5-1/6 +1/3 = 1/6且e2=-5/6；取点,第6点：e6-5/6+1/3=-1/2取点,依次进行，直到到达直线的另一端点。,这种算法不仅速度快、效果好，而且可以理论上证明它是目前同类各种算法中最优的。,为避免浮点运算，可令初值e=e*2*x 当x0时与e同号,当e0时，y方向获增量1，即令ee-2*x； 一般情况下ee+2y,起始点：e-1/2， 即e-3,第2点：e-1/2 +1/3-1/6，e-3+2y-1取点,第3点：e-1/6 +1/3 = 1/6，即e-1+21,取点且e=-5/6,e=-5；,10,4）面域的栅格化,边界线,的转化与,线的栅格化方法相同,，接下来就是,属性的填充,。,填充的方法很多，,关键问题,是正确判断哪些栅格单元位于多边形之内，哪些位于多边形之外。为此，多边性必须严格封闭，没有缝隙。,方法有：,内部点扩散法,射线算法,平行线扫描法与铅垂线跌落法,边界代数充填算法,边界点跟踪算法,11,（1）内部点扩散算法,该算法,由每个多边形一个内部点（种子点）开始，向其八个方向的邻点扩散，判断各个新加入点是否在多边形边界上,，如果是边界上，则该新加入点不作为种子点，否则把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该种子点赋以该多边形的编号。重复上述过程直到所有种子点填满该多边形并遇到边界停止为止。,扩散算法程序设计比较复杂，并且在一定的栅格精度上，如果复杂图形的同一多边形的两条边界落在同一个或相邻的两个栅格内，会造成多边形不连通，这样一个种子点不能完成整个多边形的填充。,12,（2）射线算法,射线算法可逐点判断数据栅格点在某多边形之外或在多边形内，,由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数,，如相交偶数次，则待判点在该多边形外部，如为奇数次，则待判点在该多边形内部。,采用射线算法，,要注意的是,：射线与多边形边界相交时，有一些特殊情况会影响交点的个数，必须予以排除。,射线算法,13,射线算法的特殊情况,14,（3）平行线扫描法与铅垂线跌落法,射线算法的改进,，将射线改为沿栅格阵列列方向或行方向扫描线，判断与射线算法相似。省去了计算射线与多边形边界交点的大量运算，大大提高了效率。,X,Y,R,f,e,b,a,g,d,c,M,N,15,（4）边界代数算法（BAF-Boundary Algebra Filling）,边界代数多边形填充算法是一种,基于积分思想,的矢量格式向栅格格式转换算法，它适合于,记录拓扑关系,的多边形矢量数据转换为栅格结构。,转换单个多边形,：设多边形编号为a，,初始化,的栅格阵列各栅格值为零，以栅格行列为参考,坐标轴,，由多边形边界上某点开始,顺时针,搜索边界线，当边界,上行,时，位于该边界,左侧,的具有相同行坐标的所有栅格,被减去a,；当边界,下行,时，该边界,左侧,（前进方向看为右侧）所有栅格点,加一个值a,，边界搜索完毕则完成了多边形的转换。,单个多边形的转换,16,事实上，每幅数字地图都是由,多个多边形,区域组成的，如果把不属于任何多边形的区域（包含无穷远点的区域）看成编号为零的特殊的多边形区域，则图上每一条边界弧段都与两个不同编号的多边形相邻，按弧段的前进方向分别称为左、右多边形，对于这种多个多边形的矢量向栅格转换问题，只需对所有多边形边界弧段作如下运算而不考虑排列次序：,当边界弧段,上行,时，该弧段与左图框之间栅格,增加一个值,（,左多边形编号减去右多边形编号,）；当边界弧段,下行,时，该弧段与左图框之间栅格,增加一个值,（,右多边形编号减去左多边形编号,）。,17,18,19,20,21,边界代数法与前述其他算法的不同之处，在于它不是逐点判断与边界的关系完成转换，而是根据边界的拓扑信息，通过,简单的加减代数运算,将边界位置信息动态地赋给各栅格点，实现了矢量格式到栅格格式的高速转换，而,不需要考虑,边界与搜索轨迹之间的关系，因此算法简单、可靠性好，各边界弧段只被,搜索一次,，避免了重复计算。,但是这,并不意味着,边界代数法可以完全替代其它算法，在某些场合下，还是要采用种子填充算法和射线算法，,前者应用于,在栅格图像上提取特定的区域；,后者,则可以进行点和多边形关系的判断,22,（5）边界点跟踪算法,以多边形为单位,按顺时针方向跟踪单元格,上行L,横向N,下行R,（岛则相反）,逐行扫描，充填LR间的单元格,23,3.4.2 栅格到矢量,从栅格单元转换到几何图形的过程称为,矢量化,，矢量化过程要保证以下两点：,1）拓扑转换，即保持栅格表示出的连通性与邻接性；,2）转换物体正确的外形。,24,栅格数据结构向矢量数据结构的转换,主要步骤：,边界提取,边缘锐化（遥感影像或分类栅格，面状地物）,线的细化（扫描矢量图，线状地物）,二值化,边界追踪,拓扑关系生成,线的简化及曲线圆滑,25,1. 边界提取,边缘检测（图像处理）,对于影像栅格数据，检测出不同特征区域的边界。,26,Lenna的Sobel边界,Lenna的Prewitt边界,27,2) 线的细化: 将占有多个栅格宽的图形要素缩减为只有1个像素。,剥皮法：每次剥掉等于一个栅格宽的一层，最后只留下彼此连通的由单个栅格组成的图形。,28,2.骨架法：确定图形的骨架，而将非骨架上的多余栅格删除。,具体做法是扫描全图，凡是像元值为1的栅格都用V值取代。V值是该栅格与北、东和北东三个相邻栅格像元值之和，即,在V值图上保留最大V值的栅格，删去其他栅格，但必须保证连通。因为最大V值的栅格只能分布在图形的中心线上（骨架上），因此选取最大值栅格的过程就是细化的过程 。,3.数学形态法,29,30,1. 边界提取,3) 二值化,一般情况下，栅格数据是按0255的不同灰度值表达的。,为了简化追踪算法，需把256个灰阶压缩为2个灰阶，即0和1两级。为此，假设任一格网的灰度值为G(i,j),阀值为T，那么，根据下式就可以得到二值图。,G(i,j)=,1 f(i,j)= T,0 f(i,j)= T,31,2. 边界线追踪：边界线跟踪的目的就是将细化处理后的栅格数据，整理为,从结点出发的线段或闭合的线条,，并以矢量形式存储（坐标）。,3. 线的简化及曲线圆滑：由于搜索是逐个栅格进行的，所以弧段或多边形的数据列十分密集。为了减少存储量，在保证线段精度的情况下可以,删除部分数据点,。,4. 拓扑关系生成：,判断弧段与多边形间的空间关系,，以形成完整的拓扑结构并建立与属性数据的关系。,32,3.4.3 矢量格式和栅格格式的相互转换,矢量格式向栅格格式的转换,建立空白栅格,点、线的栅格化,多边形填充,内部点扩散法,复数积分算法,射线算法,扫描算法,边界代数算法,栅格格式向矢量格式的转换,边界提取,边界追踪,去除多余点及曲线圆滑,拓扑关系生成,33,
展开阅读全文