第五讲空间数据结构-矢栅数据转换

1、第五讲第五讲 矢矢/ /栅转换栅转换金毅金毅河南理工大学资源环境学院河南理工大学资源环境学院 454003454003:65585045:65585045电话电话13782806118E_mail: E_mail: 基本内容基本内容p栅格化：栅格化：矢量数据结构向栅格数据结构的转换矢量数据结构向栅格数据结构的转换l确定栅格矩阵（行列数确定栅格矩阵（行列数/ /分辨率）分辨率）l点的变换点的变换、线的变换线的变换以及以及多边形的变换多边形的变换（面的变（面的变换）换）p矢量化：矢量化：栅格数据结构向矢量数据结构的转换栅格数据结构向矢量数据结构的转换l拓扑转换拓扑转换保持

2、栅格表示出的联通性和邻接性保持栅格表示出的联通性和邻接性l转换物体正确的外形转换物体正确的外形一、栅格化一、栅格化 确定栅格矩阵确定栅格矩阵p矢量数据转换成栅格数据后，图形的矢量数据转换成栅格数据后，图形的几何精度几何精度必然要必然要降低，所以选择栅格尺寸的大小要降低，所以选择栅格尺寸的大小要尽量满足精度尽量满足精度要求，要求，使之使之不过多地损失地理信息不过多地损失地理信息。p为了提高精度，栅格需要细化，但栅格细化，数据量为了提高精度，栅格需要细化，但栅格细化，数据量将以平方指数递增，因此，将以平方指数递增，因此，精度和数据量精度和数据量是确定栅格是确定栅格大小的大小的最重要的影响因素最重要

3、的影响因素。p在转换之前需要确定在转换之前需要确定栅格单元的大小栅格单元的大小，栅格单元的大栅格单元的大小又称为小又称为栅格图像的分辨率栅格图像的分辨率，直接决定了栅格数据的，直接决定了栅格数据的精度精度一、栅格化一、栅格化 确定栅格矩阵确定栅格矩阵YXOJIyx(0,0)XmaxYminXminYmaxI=(Ymax-Ymin)/dyJ=(Xmax-Xmin)/dxI，J为整数，尾数入上去为整数，尾数入上去dx=(Xmax-Xmin)/Jdy=(Ymax-Ymin)/I一、栅格化一、栅格化 点的栅格化点的栅格化maxmin1 INT/1 INT/ppIyydyJxxdx 一、栅格化一、栅格化

4、 线的栅格化线的栅格化p线是由多个直线段组成的，因此线的栅格化的核心就线是由多个直线段组成的，因此线的栅格化的核心就是是直线段如何直线段如何由矢量数据由矢量数据转换转换为栅格数据为栅格数据p栅格化的两种常用方法为栅格化的两种常用方法为：lDDA法法(Digital Differential Analyzer数字微分分数字微分分析法析法)lBresenham法法1.1. DDA法法( (数字微分分析法数字微分分析法) )基本原理基本原理p设设(xA,yA),(xB,yB)与栅格网的交点为与栅格网的交点为(xi,yi)，则，则有有p这样从这样从i0计算到计算到in1，即可得直线与格网的，即可得直线

5、与格网的n个交点坐标，对其取整就是该点的栅格数据了个交点坐标，对其取整就是该点的栅格数据了一、栅格化一、栅格化 线的栅格化线的栅格化BnBnAAABABABAByyxxyyxxnyyynxxxdyyxxn,/,max001.1. DDA法法( (数字微分分析法数字微分分析法) )特点特点p该方法的基本依据是直线的微分方程，即该方法的基本依据是直线的微分方程，即dy/dx常数常数。其本质是其本质是用数值方法解微分方程用数值方法解微分方程，通过同时通过同时对对x x和和y y各增加一个小增量来计算下一步的各增加一个小增量来计算下一步的x,yx,y值，值，即这是即这是一种增量算法一种增量算法p在该算

6、法中，必须在该算法中，必须以浮点数表示坐标以浮点数表示坐标，且，且每次都要每次都要舍入取整舍入取整，因此，因此，尽管算法正确，但速度不够快尽管算法正确，但速度不够快一、栅格化一、栅格化 线的栅格化线的栅格化2.2. Bresenham算法算法基本原理基本原理p算法核心思想是算法核心思想是根据根据由直线斜率构成的由直线斜率构成的误差项的符误差项的符号号来来确定下一列坐标的递增值确定下一列坐标的递增值p根据直线的斜率，把直线分为根据直线的斜率，把直线分为8 8个卦限。下面个卦限。下面以以斜斜率在第一卦限的情况为例，其余卦限的情况类似率在第一卦限的情况为例，其余卦限的情况类似一、栅格化一、栅格化 线

7、的栅格化线的栅格化该算法的基本思路可描述为：该算法的基本思路可描述为：p若直线的斜率为若直线的斜率为1/2y/x1，则下一点取则下一点取(1(1，1)1)点点；p若若0y/x1/2，则下一点取则下一点取(1(1，0)0)点点2.2. Bresenham算法算法实现过程实现过程p在算法实现时，令起始的误差项为在算法实现时，令起始的误差项为e-1/2，然后在然后在推断出下一点后推断出下一点后，令，令eey/x( (为直线斜率为直线斜率）, ,l若若e0e0，取，取(1(1，1)1)点点(45(45o o斜向斜向) )l若若e e0 0，取，取(1(1，0)0)点点( (平行方向）平行方向）l若若e

8、0e0时，时，e ee-1e-1一、栅格化一、栅格化 线的栅格化线的栅格化p直线直线斜率为斜率为1/31/3，起始点：，起始点：e0e0-1/2,-1/2,取点取点0 0p第第1 1点：点：e1e1-1/2 +1/3-1/2 +1/3-1/6-1/6取点取点1 1p第第2 2点：点：e2e2-1/6 +1/3 = 1/6-1/6 +1/3 = 1/6且且e2=-5/6e2=-5/6；取点；取点2 2p第第3 3点：点：e3e3-5/6+1/3=-1/2-5/6+1/3=-1/2取点取点3 3；p第第4 4点：点：e4e4-1/2+1/3=-1/6-1/2+1/3=-1/6取点取点4 4；p第第

9、5 5点：点：e5e5-1/6 +1/3 = 1/6-1/6 +1/3 = 1/6且且e2=-5/6e2=-5/6；取点；取点5 5；p第第6 6点：点：e6e6-5/6+1/3=-1/2-5/6+1/3=-1/2取点取点6 6；一、栅格化一、栅格化 面的栅格化面的栅格化p边界线边界线的转化与的转化与线的栅格化方法相同线的栅格化方法相同，接下来就是，接下来就是属属性的填充性的填充p填充的方法很多，填充的方法很多，关键问题关键问题是是正确判断哪些栅格单元正确判断哪些栅格单元位于多边形之内，哪些位于多边形之外位于多边形之内，哪些位于多边形之外。为此，。为此，多边多边形形必须严格封闭，没有缝隙必须严

10、格封闭，没有缝隙多边形内部属性填充方法多边形内部属性填充方法p内部点扩散法内部点扩散法p射线算射线算法法p平行线扫描法与铅垂线跌落平行线扫描法与铅垂线跌落法法p边界代数充填算边界代数充填算法法p边界点跟踪算边界点跟踪算法法一、栅格化一、栅格化 面的栅格化面的栅格化1 1、多边形内部属性填充方法、多边形内部属性填充方法基本原理基本原理p由每个多边形一个内部点由每个多边形一个内部点( (种子点种子点) )开始，向其八个开始，向其八个方向的邻点扩散方向的邻点扩散p判断各个新加入点是否在多边形边界上法判断各个新加入点是否在多边形边界上法p如果是边界点，则新加入点如果是边界点，则新加入点不作为种子点不作

11、为种子点p否则把非边界点的否则把非边界点的邻点作为新的种子点邻点作为新的种子点与原有种子点一起与原有种子点一起进行新的扩散运算进行新的扩散运算p将该种子点赋予多边形的编号将该种子点赋予多边形的编号p重复上述过程，直到所有种子点填满该多边形并遇重复上述过程，直到所有种子点填满该多边形并遇到边界为止到边界为止一、栅格化一、栅格化 面的栅格化面的栅格化1 1、多边形内部属性填充方法、多边形内部属性填充方法缺点缺点p程序设计复杂，需要在栅格阵列中搜索，占用内存程序设计复杂，需要在栅格阵列中搜索，占用内存很大，在内存受限时很难采用很大，在内存受限时很难采用p在一定的栅格精度上，在一定的栅格精度上，如果复

12、杂图形的同一多边形如果复杂图形的同一多边形的两条边界落在同一个或相邻的两个栅格内的两条边界落在同一个或相邻的两个栅格内，会造，会造成多边形不连通，不能完成多边形的填充成多边形不连通，不能完成多边形的填充( (需板书需板书) )一、栅格化一、栅格化 面的栅格化面的栅格化2 2、射线法、射线法基本原理基本原理p概念：概念：射线算法，又称为射线算法，又称为检验交点数法检验交点数法，是，是逐点判逐点判别别数据栅格点在某多边形之外或在多边形内来决定数据栅格点在某多边形之外或在多边形内来决定是否记录该点是否记录该点p基本原理：基本原理：具体实现是具体实现是由待判点向图外某点引射线由待判点向图外某点引射线，

13、判断该射线与某多边形所有边界相交的总次数，判判断该射线与某多边形所有边界相交的总次数，判断的基本原理：断的基本原理：如相交如相交偶数偶数次，则待判点在该多边形的次，则待判点在该多边形的外部外部如相交如相交奇数奇数次，则待判点在该多边形的次，则待判点在该多边形的内部内部一、栅格化一、栅格化 面的栅格化面的栅格化2 2、射线法、射线法基本原理基本原理一、栅格化一、栅格化 面的栅格化面的栅格化N=0N=2N=1N=3N=42 2、射线法、射线法特殊情况：奇异点特殊情况：奇异点一、栅格化一、栅格化 面的栅格化面的栅格化3 3、平行线扫描法与铅垂线跌落法平行线扫描法与铅垂线跌落法基本原理基本原理p射线算

14、法的改进射线算法的改进，将射线改为沿栅格阵列，将射线改为沿栅格阵列列方向或列方向或行方向扫描线行方向扫描线，判断与射线算法相似。省去了计算，判断与射线算法相似。省去了计算射线与多边形边界交点的大量运算，大大提高了效射线与多边形边界交点的大量运算，大大提高了效率率。又称为。又称为扫描算法扫描算法一、栅格化一、栅格化 面的栅格化面的栅格化XYRfebagdcMN4 4、边界代数填充算法、边界代数填充算法（BAF-Boundary Algebra FillingBAF-Boundary Algebra Filling）p基本思想：基本思想：基于积分思想基于积分思想的矢量格式向栅格格式转的矢量格式向栅

15、格格式转换算法，它适合于换算法，它适合于记录拓扑关系记录拓扑关系的多边形矢量数据的多边形矢量数据转换为栅格结构转换为栅格结构p实现过程实现过程：p初始化的栅格阵列初始化的栅格阵列各栅格值为零各栅格值为零p以栅格行列为参考坐标轴，由多边形某点开始顺时针以栅格行列为参考坐标轴，由多边形某点开始顺时针搜索搜索边界线边界线p边界边界上行上行时，边界时，边界左左侧行坐标相同的栅格被侧行坐标相同的栅格被加上加上0-a0-a，边界边界下行下行时，边界时，边界右右侧行坐标相同的栅格被侧行坐标相同的栅格被加上加上a-0a-0一、栅格化一、栅格化 面的栅格化面的栅格化4 4、边界代数填充算法、边界代数填充算法（B

16、AF-Boundary Algebra FillingBAF-Boundary Algebra Filling）一、栅格化一、栅格化 面的栅格化面的栅格化4 4、边界代数填充算法、边界代数填充算法（BAF-Boundary Algebra FillingBAF-Boundary Algebra Filling）p多多边形处理策略多多边形处理策略p实现过程实现过程：当边界弧段当边界弧段上行上行时，该弧段与左图框之间栅格时，该弧段与左图框之间栅格增加一个值增加一个值（左多边形编号减去右多边形编号）（左多边形编号减去右多边形编号）；当边界弧段当边界弧段下行下行时，该弧段与时，该弧段与右右图框之间栅格

17、图框之间栅格增加一个值增加一个值（右多边形编号减去左多边形编号）（右多边形编号减去左多边形编号）一、栅格化一、栅格化 面的栅格化面的栅格化5 5、边界点跟踪算法、边界点跟踪算法p以多边形为单以多边形为单位位p按顺时针方向跟踪单元按顺时针方向跟踪单元格：格：上行上行L L；横向横向N N；下行下行R R（如果为岛屿，则相反）（如果为岛屿，则相反）p逐行扫描，充填逐行扫描，充填LRLR间的单元格间的单元格一、栅格化一、栅格化 面的栅格化面的栅格化N NLRN NLRLRLRLRN N N二、矢量化二、矢量化 定义及要求定义及要求p定义及定义及要求要求：从栅格单元转换到几何图形的过程称为从栅格单元转

18、换到几何图形的过程称为矢量化矢量化，矢量化过程要保证以下两点，矢量化过程要保证以下两点要求要求：p拓扑转换拓扑转换，即保持栅格表示出的即保持栅格表示出的连通性与邻接性连通性与邻接性p转换物体正确的外形转换物体正确的外形二、矢量化二、矢量化 一般转化步骤一般转化步骤p边界提取边界提取p边缘锐化（遥感影像或分类栅格，面状地物）边缘锐化（遥感影像或分类栅格，面状地物）p线的细化（扫描矢量图，线状地物）线的细化（扫描矢量图，线状地物）p二值化二值化p边界追踪边界追踪p拓扑关系生成拓扑关系生成p线的简化及光滑线的简化及光滑1 1、边界提取、边界提取边缘提取（数字图像处理）边缘提取（数字图像处理）二、矢量

19、化二、矢量化 一般转化步骤一般转化步骤Lenna的的Sobel边界边界 Lenna的的Prewitt边界边界原始图片原始图片1 1、边界提取、边界提取线的细化线的细化p将占有多个栅格宽的图形要素缩减为只有将占有多个栅格宽的图形要素缩减为只有1 1个像素个像素剥皮法：剥皮法：每次剥掉等于一个栅格宽的一层，最后只留下彼每次剥掉等于一个栅格宽的一层，最后只留下彼此连通的由单个栅格组成的图形此连通的由单个栅格组成的图形剥皮法剥皮法保持图像的连接性不变保持图像的连接性不变和和关键部分关键部分二、矢量化二、矢量化 一般转化步骤一般转化步骤1 1、边界提取、边界提取线的细化线的细化p剥皮法剥皮法算法原理算法

20、原理二、矢量化二、矢量化 一般转化步骤一般转化步骤p剥皮法剥皮法过程过程1 1、边界提取、边界提取线的细化线的细化p骨架法骨架法：确定图形的骨架，而将非骨架上的多余栅确定图形的骨架，而将非骨架上的多余栅格删除格删除p基本原理基本原理：扫描全图，凡是：扫描全图，凡是像元值为像元值为1 1的栅格都用的栅格都用V V值取代值取代。V V值是该栅格与北、东和北东三个相邻栅格像元值之和，值是该栅格与北、东和北东三个相邻栅格像元值之和，即：即：p保留最大保留最大V V值的栅格，删去其他栅格，但必须保证连通值的栅格，删去其他栅格，但必须保证连通。因最大因最大V V值的栅格只能分布在图形的中心线、骨架上值的栅

21、格只能分布在图形的中心线、骨架上，因，因此选取最大值栅格的过程就是细化的过程此选取最大值栅格的过程就是细化的过程二、矢量化二、矢量化 一般转化步骤一般转化步骤1 1、边界提取、边界提取二值化二值化p一般情况下，栅格数据是按一般情况下，栅格数据是按0 0255255的不同灰度值表的不同灰度值表达的达的p为了简化追踪算法，为了简化追踪算法，需把需把256256个灰阶压缩为个灰阶压缩为2 2个灰阶个灰阶，即即0 0和和1 1两级。为此，假设任一格网的灰度值为两级。为此，假设任一格网的灰度值为G(i,j),G(i,j),阀值为阀值为T T，那么，根据下式就可以得到二值，那么，根据下式就可以得到二值图图二、矢量化二、矢量化 一般转化步骤一般转化步骤G(i,j)=1 f(i,j)= T0