Research on automatic search method of vector dataGCP based on Voronoi diagram

LU Yue-feng1, CHANGXi-zhi2

(1. School of Architecture and Engineering, Shandong Universityof Technology, Zibo, Shandong,255049, China; 

2. School of Materials Science and Engineering, Shandong Universityof Technology, Zibo, Shandong,255049, China;)

Abstract:In this paper, we first present a search method of vector graphics boundary feature points automatically, and on the basis of the use of point impact characteristics of Voronoidiagram, theautomatic search method of vector graphics boundary feature pointsis proposed based on Voronoidiagram. We could the feature points as the control points, and can guarantee the quantity and distribution uniformity of control points. Through the application in theregistration between vector data image data registration and the precision analysis, results show that the proposed in this paper automatic search method of the ground control points is effective and feasible.

Key words:GIS;Voronoi diagram; vector data; ground control point; automatic search; geometric correction

1引言

随着遥感、地理信息系统和摄影测量及计算机等相关技术的快速发展，利用多种技术相结合的方法对所获取的遥感数据进行处理需求也越来越多。当前遥感技术的快速发展使遥感影像数据的获取更加快捷和方便，为地理空间数据的持续更新提供了强大的动力。相应地，对地理空间数据间自动匹配的要求也越来越高，特别是在新获取的遥感影像与现有矢量空间数据之间的配准方面，如在土地调查、变化检测等应用中，常常需要将新获取的遥感影像和现有的矢量数据进行配准等预处理。在遥感影像预处理中，关键步骤是对遥感影像的几何纠正，而在几何纠正中，目前通常的是采用人工选择控制点的方法，一般选取原始遥感影像上的地面突变点，所选取的控制点常常受到人为因素很大的影响，如选取经验、工作态度、判读能力、综合反应能力等[1] [2] 。

控制点选取的数量和分布将直接影响到影像纠正的精度，所以选取尽可能多的、有效的且分布均匀的控制点就显得非常重要，通常做法是选取边界上明显的特征点作为控制点。本文提出一种基于Voronoi图的矢量图形边界特征点自动搜索算法，首先通过矢量图形边界特征点自动搜索方法选取足够的控制点数量，然后用Voronoi图的点影响范围特性使所选取的控制点达到均匀分布。

2基于Voronoi图的矢量图形控制点自动选取方法

2.1. 矢量图形边界特征点自动搜索

设为矢量数据中的任意一个要素实体，它的边界为，周长为，几何中心点为。

定义1将实体边界线上任一点到几何中心点的距离称为边界线在该点的中心距离(也称为半径)，记为，则有 。

边界上控制点选取方法为：对于实体边界，任选边界上一点作为起始点，记为，将边界周长归一化为1，若选取个控制点，则按顺时针方向(或逆时针方向)每隔个周长距离将整个边界划分为个子段，在每一个子段内选取一个特征点作为控制点。

在每一个子段中通过下面方法选取特征点：根据定义1，通过比较该子段上所有边界点的半径大小，取其中半径最大值(或最小值)所处位置的边界点为特征点，若最大值(或最小值)不唯一，则按子段划分方向选取第一个最值。

由于单个实体边界上控制点的选择因起始点的不同而不同，且匹配的实体对所选择的起始点相对于整个边界上所处的位置应是相似或相近点，只有这样在实体边界上所选取的一系列控制点才有意义，所以必须考虑起始点的选择。

应用子段中选取控制点方法，通过比较实体边界上所有点的半径大小，取其中半径最大值(或最小值)所处位置的点为起始点，则可以解决实体起始点选择问题，示意图如图1所示：

图1自动搜索边界特征点作为控制点示意图

对于规则面状地物，特别是圆形面状地物，如圆形工厂设施等，通常无法获取其边界上的特征点，而其几何中心点能够准确的表达面状地物边界所包含的整个地区区域，其具有旋转、平移和缩放的不变性，也称之为几何形状中心点，所以几何中心点完全可以作为影像在这些地物上的控制点。

2.2. 基于Voronoi图的矢量图形边界特征点自动搜索

控制点选取的基本原则之一就是要使控制点分布尽量均匀，为了满足这一原则，可以通过每个控制点的影响范围来进行评价，若各个控制点的影响范围相同或相近，则认为所选取的控制点分布均匀，否则，认为所选取的控制点分布不均匀[3] 。因此，利用Voronoi图的点影响范围特性[4] ，提出一种基于Voronoi图的矢量图形边界特征点自动搜索方法。

根据Voronoi图中点的影响范围特性，利用上节初始选取的控制点所形成的Voronoi图中各个子区域面积的离散程度来判断所选取的控制点是否均匀分布。选取控制点步骤如下：

(1) 利用边界特征点自动搜索方法，选择实体中一定数量的边界特征点，将这些特征点作为初始控制点。

(2) 以这些控制点为基点生成Voronoi图，判断图中各个子区域面积大小，选择面积最小的子区域，其它各子单元均与相比较，若比值大于一定阈值，则根据比值，在此子区域增加相应个数的控制点。其中，增加控制点的方法采用上小节所述的边界特征点法，根据个数需要依次选取增加的控制点数。

(3) 增加控制点后，将新增控制点作为基点，重新生成Voronoi图，重新执行步骤(2)，直至各个子区域面积与比值小于设定阈值为止。

选取实体中一定数量的边界特征点为初始控制点，并以它们为基点生成的Voronoi图，如图2所示，图中填充面状为所选取的实体，圆点为选择的初始控制点：

图2选择的初始控制点及生成的Voronoi图

Voronoi图中各个子区域面积及相对于最小面积子区域的比值如表1所示：

表1Voronoi图各子区域面积及比值

本文选取阈值为7，从图2及表1中可以看出，初始控制点作为基点生成的Voronoi图中，ID为10009这个基点所在多边形面积较大，需要进一步增加控制点。在该基点所在的实体边界上，通过增加边界特征点作为新的控制点(图3中右下角的点)，并重新生成Voronoi图，如图3所示：

图3增加控制点及重新生成的Voronoi图

从图3可以看出，原来的多边形10009被分割为两个子多边形，即新10009和10015，从而使控制点的分布达到了进一步均匀化分布。表2为增加控制点后重新生成Voronoi图后的子区域面积及面积比值。

表2Voronoi图各子区域面积及比值

从表2中可以看出，增加控制点10015后，各个基点所在子区域面积的比值均小于阈值，所以可以不需要再增加控制点。

3 实验与分析

3.1. 影像几何纠正

在将新获取的遥感影像和现有的矢量数据进行配准的过程中，通过对影像数据特征提取及矢量化，将矢量化后数据和现有矢量空间数据进行匹配，获取匹配实体对；然后在获取的匹配实体对分别选取控制点，在所属矢量化后数据的实体中选取控制点，并将这些控制点反馈到原始遥感影像上进而获得控制点相应的像元坐标；最后应用获取的像元坐标数据和现有矢量数据中对应的同名点坐标组成控制点对，对原始影像进行几何纠正，从而实现矢量空间数据和影像数据的配准。

利用ENVI软件实现对影像的矢量化，通过文献[5] 方法获取的匹配实体对，选取相对于整幅影像分布较均匀的一定数量匹配实体对，分别选择它们的边界特征点作为控制点，通过提取这些控制点对坐标，利用现有的影像几何纠正方法解算出转换矩阵。由于矢量化后的数据与原始影像是完全对应关系，所以通过这些控制点，依据遥感影像几何纠正步骤和方法[5] [5] ，选择二次多项式纠正模型，即可实现对原始影像的几何纠正，从而使新获取的影像和现有矢量数据配准。获取控制点文件及几何纠正的流程如图4所示：

图4控制点文件获取及几何纠正流程图

图5为矢量化数据、控制点数据和原始影像三者的叠加，其中红色线为矢量化数据，十字线为控制点。

图5矢量化数据、控制点与原始影像的叠加

根据控制点的位置，获取这些控制点在原始影像上的像元坐标，如表3所示：

表3控制点坐标

根据表3生成用于几何纠正的控制点文件，对原始影像进行几何纠正，纠正后效果，如

图6和图7(局部放大图)所示，其中线状为现有矢量数据：

图6原始影像几何纠正结果

图7原始影像几何纠正结果(局部放大图)

3.2. 精度评价分析

地面控制点选取后，通过计算控制点的均方根误差(Root Mean Square Error)来检查所选控制点的误差，并据此进行精度评价。表3所选控制点误差如表4所示：

表4控制点误差(单位：像素)

由表4可以看出，ID为2和3的控制点由于y误差导致这两个控制点大于一个像元；但是通过各个控制点的可得到总的为0.8202，小于一个像元，说明所选控制点精度总体上比较高。

根据2.2方法，在其中三个匹配实体边界上各增加一个边界特征点为控制点，可得增加控制点后误差如表5所示：

表5增加控制点后误差(单位：像素)

由表5可以看出，ID为10的控制点由于x误差导致该控制点大于一个像元；但是通过各个控制点的可得到总的为0.5539，小于一个像元，说明所选控制点精度总体上得到了较大提高。

4 总结

本文提出了基于Voronoi图的矢量图形控制点自动搜索，并利用该方法获取了实验数据上的控制点对，实现了对原始影像进行了几何纠正，从而最终实现了现有矢量数据与影像数据的配准。通过精度评价分析，也说明该方法在精度上满足了影像纠正的要求。

参考文献

[1]  宋伟东,王伟玺.遥感影像几何纠正与三维重建[M].北京:测绘出版社,2011.

[2]  黄健.遥感影像纠正的地面控制点选取[J].现代测绘,2005，S1：208-209，212.

[3]  周家香, 朱晓东, 周晓光. 基于Voronoi图的遥感影像校正地面控制点选取[J].地理信息世界,2007,02：67-70.

[4]  伯格(Berg,M.D.)等著;邓俊辉译.计算几何:算法与应用(第3版)[M].北京:清华大学出版社,2009.

[5]党安荣等.ERDAS IMAGINE遥感图像处理教程[M].北京:清华大学出版社,2010.

[6]  付仲良, 逯跃锋. 利用弯曲度半径复函数构建综合面实体相似度模型[J].测绘学报, 2013，42(1)：145-151.