参考地理信息系统课件---07栅格矢量的相互转化--来自华北科技学院-魏志刚

1第三章空间数据模型与数据库23.4矢量结构与栅格结构的相互转换1.矢量数据结构向栅格数据结构的转换（栅格化）2.栅格数据结构向矢量数据结构的转换（矢量化）33.4.1矢量到栅格栅格化过程包括以下操作：1）确定栅格矩阵(行列数\分辨率)；2）点的变换3）线的变换4）多边形的变换(面的变换)41)确定栅格矩阵•矢量数据转换成栅格数据后，图形的几何精度必然要降低，所以选择栅格尺寸的大小要尽量满足精度要求，使之不过多地损失地理信息。•为了提高精度，栅格需要细化，但栅格细化，数据量将以平方指数递增，因此，精度和数据量是确定栅格大小的最重要的影响因素。5I=(Ymax-Ymin)/dyJ=(Xmax-Xmin)/dxI，J为整数，尾数入上去dx=(Xmax-Xmin)/Jdy=(Ymax-Ymin)/I1)确定栅格矩阵•在转换之前需要确定栅格单元的大小，栅格单元的大小又称为栅格图像的分辨率，直接决定了栅格数据的精度。YXOJIyx(0,0)XmaxYminXminYmax62）点的栅格化dxxxINTJdyyyIpp/1/INT1minmaxX,Y73）线的栅格化方法•线是由多个直线段组成的，因此线的栅格化的核心就是直线段如何由矢量数据转换为栅格数据。•栅格化的两种常用方法为:–DDA法(DigitalDifferentialAnalyzer数字微分分析法)–Bresenham法8DDA法(数字微分分析法)设(xA,yA),(xB,yB)与栅格网的交点为(xi,yi)，则:其中：这样从i＝0计算到i＝n－1，即可得直线与格网的n个交点坐标，对其取整就是该点的栅格数据了。•该方法的基本依据是直线的微分方程，即dy/dx＝常数。其本质是用数值方法解微分方程，通过同时对x和y各增加一个小增量来计算下一步的x,y值，即这是一种增量算法。•在该算法中，必须以浮点数表示坐标，且每次都要舍入取整，因此，尽管算法正确，但速度不够快。BnBnAAABABABAByyxxyyxxnyyynxxxdyyxxn,,,,/,max009Bresenham算法•该算法原来是为绘图机设计的，但同样适合于栅格化。该算法构思巧妙，只需根据由直线斜率构成的误差项的符号，就可确定下一列坐标的递增值。•根据直线的斜率，把直线分为8个卦限。下面举斜率在第一卦限的情况为例，其余卦限的情况类似。•该算法的基本思路可描述为：若直线的斜率为1/2≤△y/△x≤1，则下一点取(1，1)点，若0≤△y/△x＜1/2，则下一点取(1，0)点。10在算法实现时，令起始的误差项为e＝-1/2，然后在推断出下一点后，令e＝e＋△y/△x,若e≥0时，e＝e-1。这样只要根据e的符号就可确定下一点的增量，即：若e≥0，取(1，1)点若e＜0，取(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当△x≥0时与e同号当e’0时，y方向获增量1，即令e’＝e’-2*△x；一般情况下e’＝e’+2△y起始点：e＝-1/2，即e’＝-3第2点：e＝-1/2+1/3＝-1/6，e’＝-3+2△y＝-1取点①第3点：e＝-1/6+1/3=1/6，即e’＝-1+2＝1,取点②且e=-5/6,e’=-5；5623401114）面域的栅格化•边界线的转化与线的栅格化方法相同，接下来就是属性的填充。•填充的方法很多，关键问题是正确判断哪些栅格单元位于多边形之内，哪些位于多边形之外。为此，多边性必须严格封闭，没有缝隙。•方法有：–内部点扩散法–射线算法–平行线扫描法与铅垂线跌落法–边界代数充填算法–边界点跟踪算法12（1）内部点扩散算法•该算法由每个多边形一个内部点（种子点）开始，向其八个方向的邻点扩散，判断各个新加入点是否在多边形边界上，如果是边界上，则该新加入点不作为种子点，否则把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该种子点赋以该多边形的编号。重复上述过程直到所有种子点填满该多边形并遇到边界停止为止。•扩散算法程序设计比较复杂，并且在一定的栅格精度上，如果复杂图形的同一多边形的两条边界落在同一个或相邻的两个栅格内，会造成多边形不连通，这样一个种子点不能完成整个多边形的填充。13（2）射线算法•射线算法可逐点判断数据栅格点在某多边形之外或在多边形内，由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数，如相交偶数次，则待判点在该多边形外部，如为奇数次，则待判点在该多边形内部。•采用射线算法，要注意的是：射线与多边形边界相交时，有一些特殊情况会影响交点的个数，必须予以排除。射线算法14射线算法的特殊情况15（3）平行线扫描法与铅垂线跌落法•射线算法的改进，将射线改为沿栅格阵列列方向或行方向扫描线，判断与射线算法相似。省去了计算射线与多边形边界交点的大量运算，大大提高了效率。XYRfebagdcMN16（4）边界代数算法（BAF-BoundaryAlgebraFilling）•边界代数多边形填充算法是一种基于积分思想的矢量格式向栅格格式转换算法，它适合于记录拓扑关系的多边形矢量数据转换为栅格结构。•转换单个多边形：设多边形编号为a，初始化的栅格阵列各栅格值为零，以栅格行列为参考坐标轴，由多边形边界上某点开始顺时针搜索边界线，当边界上行时，位于该边界左侧的具有相同行坐标的所有栅格被减去a；当边界下行时，该边界左侧（前进方向看为右侧）所有栅格点加一个值a，边界搜索完毕则完成了多边形的转换。单个多边形的转换17•事实上，每幅数字地图都是由多个多边形区域组成的，如果把不属于任何多边形的区域（包含无穷远点的区域）看成编号为零的特殊的多边形区域，则图上每一条边界弧段都与两个不同编号的多边形相邻，按弧段的前进方向分别称为左、右多边形，对于这种多个多边形的矢量向栅格转换问题，只需对所有多边形边界弧段作如下运算而不考虑排列次序：–当边界弧段上行时，该弧段与左图框之间栅格增加一个值（左多边形编号减去右多边形编号）；当边界弧段下行时，该弧段与左图框之间栅格增加一个值（右多边形编号减去左多边形编号）。18000000000000005550000002555500002255552000225552200222222220022220000002222000000000000000000000000000000000000000000000-3-3-3-3000000-3-3-3-3000000-3-3-3-30000000000000000000000000000000000000000000000000000000019000000000000005550000002555500002255552000225552200222222220022220000002222000000000000000000000000000000000000000000000-3-3-3-3000000000033330000003330000000000000000000000000000000000000000000000000000000000000000000000000-3-3-3-3000000-3-3-3-3000000-3-3-3-3000000000000000000000000000000000000000000000000000000002000000000000000000000-5-5-5-3000000-2-200333300-2-200333000-2000000000-2000000000-20000000000000000000000000000000000000000000000000-3-3-3-3000000000033330000003330000000000000000000000000000000000000000000000000000000225555200225552202222222202222022220000000000000055500000025555000022555520002255522002222222200222200000022220000000000000000000000000210000000000-5-5-5-5000000-5-5-5-30000000022555520002255522002222222200222200000022220000000000000000000000000000000000000005550000002555500002255552000225552200222222220022220000002222000000000000000000000000000000000000000000000-5-5-5-30000000022555520002255522002222222200222200000022220000000000000000000000000000055500002555522•边界代数法与前述其他算法的不同之处，在于它不是逐点判断与边界的关系完成转换，而是根据边界的拓扑信息，通过简单的加减代数运算将边界位置信息动态地赋给各栅格点，实现了矢量格式到栅格格式的高速转换，而不需要考虑边界与搜索轨迹之间的关系，因此算法简单、可靠性好，各边界弧段只被搜索一次，避免了重复计算。•但是这并不意味着边界代数法可以完全替代其它算法，在某些场合下，还是要采用种子填充算法和射线算法，前者应用于在栅格图像上提取特定的区域；后者则可以进行点和多边形关系的判断23（5）边界点跟踪算法•以多边形为单位•按顺时针方向跟踪单元格–上行L–横向N–下行R（岛则相反）•逐行扫描，充填LR间的单元格NNLRNNLRLRLRLRNNN243.4.2栅格到矢量•从栅格单元转换到几何图形的过程称为矢量化，矢量化过程要保证以下两点：–1）拓扑转换，即保持栅格表示出的连通性与邻接性；–2）转换物体正确的外形。253.4.2栅格数据结构向矢量数据结构的转换•主要步骤：1.边界提取1.边缘锐化（遥感影像或分类栅格，面状地物）2.线的细化（扫描矢量图，线状地物）3.二值化2.边界追踪3.拓扑关系生成4.线的简化及曲线圆滑261.边界提取1)边缘检测（图像处理）对于影像栅格数据，检测出不同特征区域的边界。27Lenna的Sobel边界Lenna的Prewitt边界282)线的细化:将占有多个栅格宽的图形要素缩减为只有1个像素。1.剥皮法：每次剥掉等于一个栅格宽的一层，最后只留下彼此连通的由单个栅格组成的图形。292.骨架法：确定图形的骨架，而将非骨架上的多余栅格删除。具体做法是扫描全图，凡是像元值为1的栅格都用V值取代。V值是该栅格与北、东和北东三个相邻栅格像元值之和，即在V值图上保留最大V值的栅格，删去其他栅格，但必须保证连通。因为最大V值的栅格只能分布在图形的中心线上（骨架上），因此选取最大值栅格的过程就是细化的过程。3.数学形态法30311.边界提取3)二值化一般情况下，栅格数据是按0～255的不同灰度值表达的。为了简化追踪算法，需把256个灰阶压缩为2个灰阶，即0和1两级。为此，假设任一格网的灰度值为G(i,j),阀值为T，那么，根据下式就可以得到二值图。G(i,j)=1f(i,j)=T0f(i,j)=T322.边界线追踪：边界线跟踪的目的就是将细化处理后的栅格数据，整理为从结点