线目标特征点相似性匹配

刘光孟，刘万增

(1．广州市城市规划勘测设计研究院，广东 广州 510060；2．国家基础地理信息中心，北京 100830)

线目标特征点相似性匹配

刘光孟1，刘万增2

(1．广州市城市规划勘测设计研究院，广东 广州 510060；2．国家基础地理信息中心，北京 100830)

针对地图制图数据库更新中多源数据匹配问题，通过提取线目标中的特征点，建立一种基于空间位置和拓扑关系的匹配模型，对特征点进行相似性匹配。实验证明该模型匹配效果良好，基本满足数据更新中图形纠正的需要。

地图制图；空间位置；拓扑关系；特征点；相似性匹配

在多种类型的地图制图数据中，由于矢量数据具有拓扑属性、占用空间小、缩放不失真等特点，被广泛应用于各种地形图制作和导航应用中。但不同来源的数据的尺度、版本和精度的差异，造成空间目标的位置、度量和拓扑关系等发生改变[1]，产生数据质量误差，给空间目标的匹配和更新带来困难，且多源多尺度数据在转换过程中存在的误差，需要对转换后的数据进行匹配。

各专家学者在地图数据匹配算法[2]领域对此进行了深入广泛的研究，采用通过节点匹配算法搜索道路数来解决道路线交叉口节点匹配问题[3]，有较好的效果，但该算法只考虑了空间距离和道路条数两方面，这无法满足大量复杂的道路网特征点匹配[4]情况，而且提取的特征点还存在一定平移、旋转和尺度变化[5]。本文在此基础上对该算法进行改进，提出线目标特征点相似性匹配算法，为解决多源多尺度数据匹配与集成问题，建立基于空间线线拓扑关系的道路网特征点匹配模型，通过计算道路节点拓扑连接数、节点最大最小距离、连接方向等空间关系特征，为解决道路网目标特征点匹配问题提供技术方案。

1 线目标特征点的选取与特性描述

1.1 特征点选取

基础地理信息数据库为空间数据库，空间数据库包含了栅格和矢量图形等多种数据形式，研究选取矢量图形中的线目标。对于多源多尺度的矢量数据而言，要实现线目标的精确匹配，必须在众多的矢量线目标中找到唯一性界定指标，从几何拓扑学角度分析可知线是由点构成的，因此，将线简化为点，并选取其特征点信息进行匹配的方法是可行的[3]。作为矢量形式的线段而言，忽略其宽度不计，其特征点主要包含端点、中点、节点等类型，如图1所示。本文结合线目标的空间拓扑特性，选取线目标特征点中的端点和节点作为研究对象实现线目标的最终匹配。

线的端点是相对于有向线段而言的，在给线段指定方向后，即可给定线段开始和结束的两个端点，简称为始端点和末端点。由于两者的连接具有方向性，因而可以选取线线拓扑关系中的角度因子对线段进行匹配。除了端点之外，线目标中另一个主要的特征点就是节点也即交叉点，是3个或3个以上的线路会合的点集，其中包含3个或3个以上的点集。以道路线为例，典型的道路线交叉点的特征形式具有T、Y、X等形式[6]，为了判别的方便，对于T、Y型线可以认为是由3条线段交叉形成，而X型线则认为是由4条线段相交而成。这样，相交成节点的线段数可视为相似点匹配的一个重要条件。

图1 线目标相关特征点示意图

1.2 特征点特性描述

在由点与点相互连接构成线段的过程中，点的位置特性是其最为重要的特性，它决定了线目标的位置属性，在平面几何中表现为平面直角坐标(x,y)；点与点的连接所形成的方向角决定了线目标的走向，丰富了线目标的拓扑特性；而线与线之间的连接或交叉，则形成了节点处不同线段始末端点的相互重叠，在ArcGIS空间分析中，通过拓扑检查和分析可以很好地获取节点处不同线段的端点重复数，也即该节点所连接的线段数，这对线目标进行拓扑分析具有重要的意义。

研究过程中对线目标节点的界定和选取为多条线段在某处的相交点，该节点的特性表现为在同一数据集中，其空间位置坐标、连接线目标数、包含的点集是唯一的，在此基础上进行不同数据集匹配时结合另外一个节点所形成的方向角，通过对数据集的预处理，便能够在空间线目标匹配的过程中实现相应范围内线目标节点的一对一匹配。而对于线目标的节点，因其表达形式的多样性，因此,所包含的结构特性也比较复杂，按照其连接线目标的结构问题分析，除了节点空间位置坐标唯一外，其连接的线目标数、包含点集和形成方向角的个数均≥3，这对于线目标特征点的相似性匹配加大了难度，但同时也提高了相似性匹配的精确度。

2 相似性匹配模型和过程

2.1 相似性匹配模型

考虑到原始数据在尺度及空间变换上存在的平移、旋转、缩放和数据综合方面存在的任意性，根据线目标的几何特征和图论拓扑连通关系，确定要选取的参考基准目标[2]，以两点间距离、方位角的几何特征结合节点的拓扑构成关系作为匹配因子，其中节点处包含的点集为主要匹配因子。

两点间的距离和方位角可以由选取的参考基准点计算得到，节点处的点集则由在打散线段时未简化的相同端点个数决定。对于单一线段，其节点(即始/末端点)的点集为1；而点集为2的节点在拓扑连通上认为是点构成线的主要因素，排除在外；因此，节点的点集n集合范围为{n∈N+,n≠2}。

由于多源多尺度数据转换造成的空间数据误差在整个数据集中是均匀分布的，因此，通过数理统计的方法在整个数据集的不同空间位置均匀选取若干个相似性匹配参考点，进行误差统计，取其误差平均值作为匹配条件的阈值。相似性匹配参考点的选取数量不应小于10个，分别在以小范围数据集中心的东、西、南、北、东南、东北、西南、西北和中心各取一个，误差较大的位置附近多取一个，以保证误差统计的准确性。

为了更精确地匹配到相似点，根据相同长度下两线夹角所围外切圆面积最小的原则，采用“相似圆”对距离和角度进行匹配，即落在“相似圆”内的所有被匹配点被认为跟匹配点是相似的。图2为参考点A与B进行相似性匹配示意图。

图2 相似点匹配模型

任意i和j两点进行相似匹配，需满足的关系式为

f(pi≈pj)=(f(dis)ij,f(angle)ij,f(topo)ij),

(pi∈点集1,pj∈点集2).

其中：f(dis)为距离因子，f(angle)为角度因子，f(topo)为拓扑关系因子。

2.2 相似性匹配过程

根据已建立的线目标相似性匹配模型，对于存储在空间数据库中的矢量线目标进行分析操作，其具体实施技术方案如下：

1)从空间数据库加载两幅相关的矢量线目标，提取特征点及其坐标，进行线目标特征点拓扑结构分析处理。线目标特征点的提取包含线端点的提取和节点的提取，其中线的端点，即线拓扑结构中的起始点(From Point)和终止点(To Point)可以直接获取，而节点则需要经过专门处理。在基于ArcEngine组件库的开发环境中，通过相关的类库函数和接口，采用Simplify方法对节点进行简化处理，获取其包含的端点个数及相对应的坐标，将数值存入计算函数数组，用于后续相似性匹配计算。

2)选取一对相似点基准，计算距离、方位角因子，并进行图形分块和邻近搜索等优化处理。在整个线目标相似性匹配的过程中，选择线目标中的相似点参考基准是必不可少的。在此基础上，获取距离、方位角和端点个数等搜索因子，输入相似性匹配模型，并进行图形分块和邻近搜索等优化处理，提高模型匹配的速度。

3)执行相似性匹配，对已匹配完成的数据显示相互匹配的特征点和输出其坐标信息表，用于检验匹配结果是否准确，图3给出了线目标特征点提取和匹配的详细过程。

图3 线目标特征点匹配过程

3 线目标相似性匹配实验

3.1 统一坐标系和确定阈值

实验选取某市导航数据和1∶5万道路网数据为例(见图4)，首先获取地图数据所采用的坐标系和投影参数，对两种不同实验数据的空间参考进行统一的设置，然后量取部分线目标特征点与相邻特征点之间的距离进行统计，取所有计算距离之差的平均值作为“相似圆”半径的阈值，这有利于线目标特征点距离的计算和提高匹配的精度。

图4 两层不同的道路线

3.2 实验结果

经对落在“相似圆”内的点进行匹配实验计算验证，发现阈值Δd对匹配的结果有很大的影响，实验证明，匹配的准确率随着Δd的增大而减小，Δd越大所圈定的搜索范围就越大，Δd太小则找不到匹配点，而Δd0采用算术平均值进行匹配时，取得了较好的匹配效果。

利用该模型对图4的道路数据进行匹配，获得的结果如图5所示，图6为局部放大后的匹配效果。匹配计算结束后得到图7匹配点对应数据表，不仅可以清楚地查阅对应点的坐标和拓扑构成情况，通过双击属性表还可以定位到图形控件中的对应点上。

图5 实验匹配结果

图6 局部放大的匹配效果

4 结束语

空间数据特征点匹配是空间数据纠正和数据库更新的重要部分。本文针对多源复杂线目标数据的匹配问题，通过提取线目标特征点进行相似性匹配，利用线目标节点间的空间关系建立相似性匹配模型，直观描述局部匹配点间的拓扑、方向与度量的相似关系，选用实际中常用的道路线目标数据进行相似性匹配实验，显示并输出对应匹配点数据，取得较好的效果。

[1]刘万增，陈 军，邓喀中，等．线目标空间冲突自动检测方法研究[J]．中国矿业大学学报，2006，35(6):768-771.

[2]曾波，江资斌．GPS车载导航系统的地图匹配算法[J]．测绘工程，2004，13(3):65-67.

[3]孙棣华，毕俊杰，廖孝勇．一种矢量道路图层节点匹配新算法[J]．计算机系统应用，2010,19(10)：225-227.

[4]胡明昊，任明武，杨静宇．一种快速实用的特征点匹配算法[J]．计算机工程，2004，30(9):31-33.

[5]张江水，李传广，郭海涛．基于动态规划和Hough变换的遥感影像与GIS矢量数据匹配方法[J]．测绘工程，2011，20(5):9-12.

[6]陈晓飞，薛 峰，王润生．航空照片中道路交叉口的自动检测[J]．模式识别与人工智能，2000，13(1):83-86.

[7]胡云岗，陈 军，李志林，等．基于网眼密度的道路选取方法[J]．测绘学报，2007，36(3):351-357.

[8]郭克华．基于微分几何的局部相似目标匹配算法研究[D]．南京：南京理工大学，2008:3-16.

[9]吕金建，文贡坚，李德仁，等．一种新的基于空间关系的特征匹配方法[J]．测绘学报，2008，37(3):367-373.

[10]俞慈君，李江雄，余锋杰，等．带工程约束的点匹配算法[J]．机械工程学报，2010，46(5):183-190.

[责任编辑：刘文霞]

Similaritymatchingoffeaturesextractionandlineobjects

LIU Guang-meng1, LIU Wan-zeng2

(1．Guangzhou Urban Planning & Design Institute，Guangzhou 510060,China; 2．National Geomatic Center of China, Beijing 100830,China)

For the matching cases of multi-source data on mapping data updating, by extracting the feature points from the line objects, a model of similarity matching is established based on space-based position and topology. Experimental results show that the model matches basely well with the needs of the graphic correction in the data updating.

mapping; spatial location; topology; feature points; similarity matching

2013-04-16

刘光孟(1986-)，男，硕士研究生.

P28

：A

：1006-7949(2014)01-0035-04