文章快速检索  
  高级检索
顾及几何特征相似性的多源等高线匹配方法
郭文月, 刘海砚, 孙群, 余岸竹, 丁梓越     
信息工程大学, 河南 郑州 450052
摘要:已有的多源等高线匹配方法主要基于等高线拓扑关系构建以及基于空间欧氏距离的相似性度量,缺少对等高线几何形态相似性的考虑,在等高线密集区域、图幅边界区域以及地形变化剧烈区域易产生误匹配情况。为此,本文提出一种基于几何特征相似性的由粗匹配到精匹配的多源等高线匹配策略。提出顾及局部特性的基于节点曲率以及法向量与横坐标轴夹角的混合特征描述测度,将等高线点序列转化为几何形态特征描述序列,引入最长公共子序列算法,量化计算多源等高线数据之间的相似程度,并依据相似度实现同名等高线匹配。利用模拟数据和真实数据对本文方法的可靠性和运行效率进行验证,试验证明,本文提出的匹配策略顾及了等高线空间位置特征和几何形态特征,能够保证较高的匹配精度和运行效率,并具有较好的适用范围。
关键词多源等高线匹配    几何特征    相似性度量    最长公共子序列    特征描述测度    
A multisource contour matching method considering the similarity of geometric features
GUO Wenyue, LIU Haiyan, SUN Qun, YU Anzhu, DING Ziyue     
Information Engineering University, Zhengzhou 450052, China
Abstract: The existing multi-source contour matching studies have focused on the matching methods with consideration of topological relations and similarity measurement based on spatial Euclidean distance, while it is lack of taking the contour geometric features into account, which may lead to mismatching in map boundaries and areas with intensive contours or extreme terrain changes. In light of this, it is put forward that a matching strategy from coarse to precious based on the contour geometric features. The proposed matching strategy can be described as follows. Firstly, the point sequence is converted to feature sequence according to a feature descriptive function based on curvature and angle of normal vector.Then the level of similarity among multi-source contours is calculated by using the longest common subsequence solution. Accordingly, the identical contours could be matched based on above calculated results. In the experiment for the proposed method, the reliability and efficiency of the matching method are verified using simulative datasets and real datasets respectively. It has been proved that the proposed contour matching strategy has a high matching precision and good applicability.
Key words: multisource contour matching    geometric feature    similarity measurement    longest common subsequence    feature descriptor    

等高线匹配是地形图局部更新与融合的重要环节,其匹配效率与准确度很大程度上影响空间数据更新与融合质量[1]。等高线匹配同时也可以应用于导航定位[2]、空间聚类[3]、变化检测[4]以及地形要素与地物要素的制图综合[5]等领域。多源数据中同类要素对象间的匹配关系需要通过几何特征、属性特征及拓扑关系的相似性比较来建立[5],目前相关领域的研究大多基于等高线空间拓扑关系构建及相似性度量等方法。

基于等高线空间拓扑关系构建的等高线匹配与融合方法首先依一定规则建立某种树结构,通过对无序等高线集群有序化、组织化和结构化,表达等高线的空间位置信息及等高线之间隐含的空间邻近关系[6-10],进而根据等高线树所表达的位置信息和关系信息辅助实现不同来源等高线数据之间的同名等高线融合与匹配。同时,为了适应地形图局部更新过程中区域边界处出现大量非闭合等高线的情况,文献[8]提出了顾及地形特征的等高线空间关系表达方式,优化等高线树构建;文献[9]提出基于约束Delaunay三角网的等高线层次结构构建方法,一定程度上克服了等高线被图幅截断的问题,但对于一些特殊地形如陡坎、悬崖等,生成等高线树存在困难;文献[11]提出利用分区二叉树、增量等高线束和拓扑关系网来组织包含未闭合等高线间的拓扑关系;文献[12]基于线-线拓扑关系制定了多源等高线间的融合与更新规则。但当地形变化剧烈或在拓扑关系复杂区域,基于拓扑关系的同名等高线融合与匹配的正确率和自动化处理能力会受到一定影响[12]

基于相似性度量的匹配与融合方法认为曲线间的空间关系和邻近程度更能反映其相似性。文献[13]提出了线群目标间顾及空间关系和几何特征的相似性度量模型,但该模型在应用于等高线匹配时易受局部变形较大点的影响;文献[14]提出了计算两条曲线之间离散Fréchet距离的方法,利用线状要素节点之间的欧氏距离度量有序点集之间的距离,进而描述线状要素的相似程度,更加适用于等高线匹配;文献[15-17]基于该方法研究了不同比例尺地图数据线状要素匹配;文献[18]提出了基于最短路径的平均Fréchet距离和“部分-整体”Fréchet距离计算方法,减少匹配误差,解决了部分与整体匹配问题并将其应用于等高线内插。但当线状要素局部变形较大时,这种用节点之间的欧氏距离衡量线状要素之间相似程度的度量方法可能存在较大误差。另外,此类基于空间欧氏距离的方法更加侧重体现线状要素在空间位置上的相近性,而没有能够衡量其在几何形态上的相似性,在等高线分布密集区域,当匹配候选集内存在多条干扰等高线时可能会出现误匹配的情况。

针对上述问题,本文提出一种顾及几何特征相似性的等高线匹配策略,采用节点曲率以及法向量与横坐标轴夹角(curvature and the angle of normal vector, CANV)作为混合特征描述测度,提取等高线几何形态特征,将等高线节点序列转化为空间几何形态特征描述序列,并引入最长公共子序列算法(longest common subsequence solution, LCSS),量化计算多源等高线之间在几何形态上的相似和差异程度,实现同名等高线匹配,并利用模拟数据和真实数据进行试验验证。试验结果证明本文提出的基于几何特征相似性的等高线匹配策略具有较高匹配精度和运行效率,并具有较好的适用范围,实现了融合位置特性和几何形态特性的等高线匹配,为局部地形数据更新提供依据。

1 特征提取与相似性度量 1.1 等高线匹配策略

顾及几何特征的匹配过程一般包含形态特征提取和形态特征匹配[19]。基于这一认识,本文设计了顾及几何特征相似的等高线匹配策略,先根据空间位置相近和高程值相等的原则进行粗匹配,再通过特征序列转化和相似度计算的推进式过程,实现同名等高线精匹配,旨在提高多源等高线匹配的匹配精度。具体实施流程如图 1所示,主要分为粗匹配和精匹配两个部分。

图 1 顾及几何特征相似性的等高线匹配策略 Fig. 1 The contour matching strategy considering the similarity of geometric characteristic

在粗匹配过程中,首先读取不同来源的原始等高线集和待匹配等高线集,然后构建原始数据集中等高线的缓冲区,在与原始等高线缓冲区相交的待匹配等高线集内按照高程值相等的原则进行等高线粗匹配。为避免相邻等高线缓冲区之间过度重叠,导致候选等高线集过大,缓冲区半径应小于相邻等高线之间的实际水平距离,但由于等高线各处坡度可能存在差异,因此可用相邻等高线点集之间的平均距离替代等高线间的实际水平距离[20],或根据区域内等高距以及不同地形对应的坡度范围合理设置缓冲区半径。对于存在多条待匹配等高线的情况,需要根据粗匹配结果生成精匹配候选集,再进一步实施精匹配。以图 2中等高线为例,经粗匹配后,与原始等高线A缓冲区相交的等高线集{B1, B2}构成A的精匹配候选集。由于等高线B1B2高程值均与原始等高线A相等,且B1B2为并列等高线,仅依据拓扑关系难以判断B1B2是否均为A的同名等高线,因此需进一步对精匹配候选集内的等高线实施精匹配。

(此图中相关要素及数值为虚构) 图 2 基于空间邻近和高程值相等原则粗匹配 Fig. 2 Coarse matching based on spatial adjacency and elevation

在精匹配阶段,本文提出先利用特征描述测度函数提取等高线几何形态特征,将等高线的二维节点序列转化为几何形态特征描述序列,将等高线匹配问题转化为特征描述序列匹配问题,再引入最长公共子序列算法求解特征描述序列间的最长公共子序列,进而计算原始等高线与其精匹配集内候选等高线之间的相似度,根据相似度值的大小确定同名等高线,如仍存在无法确定的情况,则需结合曲线长度、曲折系数等其他空间特征信息进行辅助判断,最终实现同名等高线匹配。

基于上述匹配策略,特征描述序列转化、最长公共子序列求解及相似度计算是顾及几何特征相似性的等高线匹配策略中的关键环节。为了克服单一特征测度函数在描述等高线几何形态特征时的局限性,本文提出一种顾及曲线一阶变化率和二阶变化率的混合特征描述测度,通过增加控制参数的方式优化特征描述序列的最长公共子序列求解过程,并提出以最长公共子序列长度来量化衡量多源等高线之间相似程度的方法。

1.2 特征描述序列转化

设两条不同来源等高线AB包含的二维节点个数分别为nm,则可分别表示为A=((ax, 1, ay, 1), (ax, 2, ay, 2), …, (ax, n, ay, n)),B=((bx, 1, by, 1), (bx, 2, by, 2), …, (bx, m, by, m))。首先需要将等高线二维节点序列通过映射转化为表征其几何形态特征的一维特征描述序列A′、B′,本文利用特征描述测度函数实现几何形态特征提取。

定义1:特征描述测度函数f。定义特征描述测度函数f将等高线上二维节点序列映射为一维几何特征描述序列,即f:(ax, i, ay, i)→ai, f:(bx, j, by, j)→bj,如图 3所示。

图 3 二维点序列与一维特征描述序列 Fig. 3 The two-dimensional point sequence and the one-dimensional feature descriptive sequence

一维特征描述序列应该反映原始节点序列的主要几何形态特性,测度函数应选择能够反映等高线几何形态特征的函数[21],对几何形态描述越准确详尽,其匹配结果越准确。在构建特征描述测度函数的过程中,基于曲率[22]、凹凸形态[23]以及弦长[24]的测度函数在形状识别与检索过程中均具有较好的效果,但单一描述测度难以满足复杂形状描述需求[25]。为了保证对原始等高线几何形态描述的准确性和稳定性,同时保证运算效率,本文提出一种基于节点曲率以及法向量与横坐标轴夹角(curvature and the angle of normal vector, CANV)的混合特征描述测度。

曲率是几何学中对几何体不平坦程度的一种衡量指标,等高线节点处的曲率反映了该点曲线弯曲程度。由于节点处的一阶和二阶导数可由数值微分近似计算,因此节点(ax, i, ay, i)处曲率测度函数可表达为

(1)

式中,ax, iay, i为节点处的一阶偏导数;ax, iay, i为节点处二阶偏导数。

曲线某点处的法向量为垂直于过该点处切线的向量,法向量与横坐标轴夹角表示等高线节点的法向量方向与横坐标轴的偏离程度。如图 4所示,曲线F(ax, ay)=0在点(ax, i, ay, i)处的法向量为n=[Fx(ax, i, ay, i)Fy(ax.i, ay, i)],则等高线节点法向量与横坐标轴夹角测度函数表达为

图 4 节点法向量与横坐标轴夹角 Fig. 4 The angle between normal vector and x-axis

(2)

曲率和法向量夹角分别从二阶变化率和一阶变化率刻画曲线的局部几何形态特征。基于此,在对等高线节点序列进行特征描述转化时,选取曲率以及法向量与横坐标轴夹角作为混合特征描述测度。为避免经两种测度转化后的特征描述值在数值上差异过大,需进行归一化处理

(3)
(4)

式中,minρ、minv分别为曲率测度和法向量夹角测度序列中的最小值;maxρ、maxv分别为曲率测度和法向量夹角测度序列中的最大值。在特征描述转化过程中,设曲率测度的权值为λ,则法向量夹角测度的权值为1-λ,据此得到等高线匹配的混合测度(CANV)函数表达公式

(5)

基于CANV测度函数,等高线节点序列A的特征描述序列为A′=(a1, a2, …, an),节点序列B的特征描述序列同样可通过上述转化函数获得,可表示为B′=(b1, b2, …, bm)。至此,等高线的二维节点序列均已转化为一维特征描述序列。

1.3 最长公共子序列求解及相似性度量

两个序列X(x1, x2, …, xn)、Y(y1, y2, …, ym)的所有公共子序列中,长度最长的即为XY的最长公共子序列(longest common subsequence, LCS)。由于其能够量化表现不同序列之间的相似程度,被广泛应用于版本控制、文件匹配和重复率检测等领域[26-28]。基于上文对等高线数据进行的特征描述序列转化,同名等高线匹配问题转化为等高线特征描述序列间的最长公共子序列求解问题。

常用的最长公共序列问题求解方法为动态规划法,对于长度分别为nm的序列XY,其最长公共序列求解方法可表达为

(6)

在多源等高线匹配过程中,原始等高线与待匹配等高线之间的对应点集组成其公共子序列。然而由于不同来源的等高线数据所包含的节点个数以及节点在曲线序列中的位置存在差异,序列间的对应点并不是严格的数值相等关系,在解算过程中需要给定控制参数来优化和控制解算过程。

定义2:控制参数δε。设定一个整数δ,用于控制节点的搜索宽度,在节点序号相差δ范围内搜索对应点;设定阈值实数ε,0 < ε < 1,对应点间的特征描述值差值应在阈值范围内。控制参数值应结合等高线包含的节点个数且保证运算效率的同时在一定范围内合理取值。本文试验中δ按两条待匹配等高线包含节点个数较少值的一定比例取整,ε取两条等高线特征描述序列标准差的较小值。

图 5(a)所示,参数δε控制了在等高线特征序列A′、B′中求解对应点时的范围,图 5(b)表示两个特征描述序列间的对应关系,即最长公共子序列的解算结果,则基于控制参数的最长公共子序列解LCSSδ, ε(A′, B′)表达为

图 5 基于控制参数的最长公共子序列求解 Fig. 5 The longest common subsequence solution based on control parameters

(7)

式中,head(A′)=(a1, a2, …, an-1);head(B′)=(b1, b2, …, bm-1)。

基于上述特征描述测度函数f和求解控制参数δε,多源等高线AB的特征描述序列之间基于控制参数的最长公共子序列求解算法实现为:

af(A)

bf(B)

n←length(a)

m←length(b)

for i 1 to n

  LCSS[i, 0]←0

for i 1 to m

  LCSS[0, i]←0

for i 1 to n

  do for ji-δ to i+δ

    if j>0 and j < n

      if b[j]+εa[i] and b[j]-εa[i]

        LCSS[i, j]←LCSS[i-1, j-1]+1

      else if LCSS[i-1, j]>LCSS[i, j-1]

        LCSS[i, j]←LCSS[i-1, j]

      else

        LCSS[i, j]←LCSS[i, j-1]

return LCSS

定义3:相似度S。参照文献[26]和文献[28]中的策略,基于控制参数δε,将包含节点个数分别为nm的多源等高线AB之间的相似度S定义为

(8)

式中,A′、B′分别为AB的特征描述序列。由式(8)易知,S∈[0, 1],相似度值随等高线之间的几何形态相似程度增加而趋近于1,当两条等高线的空间位置、几何形态以及包含节点数完全一致时,S=1。在原始等高线的匹配候选集内,认为相似度值较大的待匹配等高线为其同名等高线,在相同匹配范围和数据集条件下,同名等高线间相似度越小,说明该区域地形变化越明显。

2 试验与分析

分别利用模拟试验和真实数据试验对本文提出的混合特征描述测度(CANV)和顾及几何特征相似性的等高线匹配策略的适用性、匹配精度及运行效率进行验证。

在模拟试验部分,针对已有方法在等高线匹配过程中可能出现的不适用情况,对本文提出的混合测度(CANV)及匹配方法的有效性进行验证:

(1) 模拟试验1用于验证本文提出的混合特征描述测度(CANV)在等高线相似性量化度量中的可靠性。

(2) 模拟试验2用于验证在解决非闭合等高线及地形变化引起的一对多匹配问题时本文方法的适用性。

(3) 模拟试验3用于验证在已有的基于欧氏距离相似性度量方法可能导致误匹配的情况下,本文方法的有效性。

在真实数据试验部分,利用法国某地的DEM数据所生成的等高线对本文方法的匹配精度和运行效率进行验证,并对不同权重取值在实际应用中的适用性和可靠性进行分析。

2.1 模拟试验

在模拟试验中,根据参与运算的模拟等高线节点序列中所包含的节点个数nm,取δ=[min(n, m)/5],ε取参与运算的两个特征描述序列标准差最小值,即ε=min(σ1, σ2),特征描述测度函数中曲率测度的权值λ=0.5。

模拟试验1:经过粗匹配后,当一条原始等高线有两条或多条候选匹配等高线时,如图 6所示,原始等高线A与等高线B1B2空间位置邻近,且高程值均相等,需首先基于特征描述测度函数将等高线AB1B2转化为特征描述序列,再分别计算AB1B2的相似度,根据相似性的量化度量结果进一步实施精匹配。分别采用本文提出的CANV测度与单一弦长测度、单一夹角测度对等高线相似性进行量化度量。由表 1所示试验结果可知,AB1的相似度大于AB2的相似度,因而A应与B1匹配,这一结果与人的空间认知结果相符。对基于3种不同测度的相似性度量结果进行对比分析,发现基于本文提出的CANV测度的量化度量结果具有更大的相似度较差,说明CANV测度能够对等高线的相似程度提供更显著的数值上的区分。模拟试验1表明,本文策略适用于具有多条候选等高线的多源等高线匹配情况,且本文提出的CANV测度较单一测度能够对相似程度提供更显著的区分效果。

图 6 原始等高线与待匹配等高线 Fig. 6 A primitive contour with several contours to be matched

表 1 模拟试验1结果 Tab. 1 The results of the first simulated test
原始等高线 待匹配等高线 基于不同测度的相似度值
弦长测度 夹角测度 混合测度(CANV)
A B1 0.439 0 0.463 4 0.629 6
B2 0.365 9 0.292 7 0.370 4
相似度较差 0.073 1 0.170 7 0.259 2

模拟试验2:在图幅边界和地形变化较大区域,可能存在一条原始等高线与多条待匹配等高线匹配情况。当待匹配等高线集中的多条等高线与原始等高线相似度较差很小时,须考虑这些等高线可能是非闭合情况下原始等高线的不同部分(如图 7(a))或是由于地形变化造成的等高线拆分(如图 7(b)),需利用其他空间特征信息进一步辅助判断。

图 7 一对多匹配情况 Fig. 7 The one-to-many contours matching

线群密度、曲折系数及曲线长度等是描述空间线状要素几何特征的主要指标[13]。本文以曲线长度作为辅助判断指标,对图 7(a)图 7(b)中的两组模拟数据依曲线长度公式分别计算AB1B2的长度及与A的相似度,获得表 2表 3所示结果。由表 2可知,原始等高线A与待匹配等高线B1B2的相似度较差为0.095 3,较差较小,且LB1+LB2LA,据此可判断图 7(a)中的B1B2均为A的同名等高线。由表 3可知,原始等高线A与待匹配等高线B1B2的相似度较差为0.065 2,较差较小,且LB1+LB2LA,因此图 7(b)中的B1B2均为A的同名等高线。由模拟试验2可知,本文方法在等高线非闭合以及等高线拆分情况下仍适用,并且能够结合其他辅助判断指标识别存在多条同名等高线的情况,实现一对多匹配。

表 2 模拟试验2(a)结果 Tab. 2 The results of the second simulative test (a)
A B1 B2
包含节点个数 42 30 26
LCSS长度 42 18 14
曲线长度/m 2 700.88 1 155.48 1 319.34
A相似度 1.000 0 0.428 6 0.333 3

表 3 模拟试验2(b)结果 Tab. 3 The results of the second simulative test (b)
A B1 B2
包含节点个数 46 44 26
LCSS长度 46 20 17
曲线长度/m 2 978.13 2 494.12 488.44
A相似度 1.000 0 0.434 8 0.369 6

模拟试验3:当等高线分布密集或原始等高线与待匹配等高线局部差异较大时,会出现如图 8所示的原始等高线与异名等高线间的欧氏距离小于其与同名等高线间的欧氏距离的情况,此时利用已有的基于欧氏距离的相似度计算方法可能造成误匹配。

图 8 等高线距离相近但形状不相似 Fig. 8 Contours are close in Euclidean distance but in different shapes

本文分别用传统Fréchet距离方法、文献[18]提出的平均Fréchet距离法和本文方法对图 8中的AB1B2进行匹配,获得如表 4所示结果。传统Fréchet距离法和平均Fréchet距离法计算结果均显示AB2之间距离小于AB1之间距离,按照文献[14]和文献[18]提出的匹配策略,A应与B2匹配。然而,由图 8可知,AB1在形状上更为相似。利用本文方法计算得到AB1相似度为0.527 3,大于AB2相似度0.200 0,A应与B1匹配,这一匹配结果与人的空间认知相符。同时,对3种方法运行效率的模拟结果显示,本文方法较传统Fréchet距离和平均Fréchet距离方法具有更好的运算效率。模拟试验3表明,当地形变化导致原始等高线邻近范围内出现干扰要素时,基于欧氏距离的相似性度量方法可能出现度量误差,导致误匹配情况。而本文方法由于顾及了等高线之间几何形态上的相似特征,能够对异同名等高线进行更有效区分,并保证较高的运算效率。

表 4 模拟试验3结果 Tab. 4 The results of the third simulative test
原始等高线 待匹配等高线 Fréchet距离/m 平均Fréchet距离[18]/m 本文相似度
A B1 1 108.85 522.31 0.527 3
B2 787.99 285.26 0.200 0
运行时间/s 0.427 0 0.802 0 0.082 0
匹配结果 B2 B2 B1

2.2 真实数据试验

本文获取了如图 9所示法国某地2000年SRTM合成孔径雷达90 m分辨率DEM数据和该地区2009年ASTER GDEM光学30 m分辨率DEM数据,分别生成如图 10所示的起始高程值相等的50 m等高距等高线,高程范围约为50~1600 m。由于成像时间、传感器和高程精度的不同,两种DEM生成的同一地区等高线在几何形态和空间位置上会存在一定差异。由于在高程精度和现势性方面ASTER GDEM数据优于SRTM数据,因此以SRTM生成等高线作为原始等高线,以ASTER GDEM生成等高线作为待匹配等高线,利用本文方法对两种等高线数据进行匹配,对匹配精度和运行效率分析,并对不同权重取值对匹配结果的影响进行比较。

图 9 原始DEM数据 Fig. 9 Original DEM datasets

图 10 DEM生成等高线数据 Fig. 10 Contours generated from DEM datasets

基于本文提出的等高线匹配策略,首先根据数据特点,构建原始等高线缓冲区,按照空间位置相近及高程值相等的原则进行粗匹配,生成精匹配数据集,针对存在多条候选匹配等高线的原始等高线,进一步实施精匹配:

(1) 基于CANV测度函数,利用式(5)将等高线二维节点序列转化为一维特征描述序列。

(2) 确定控制参数,利用式(7)求解特征描述序列之间的最长公共子序列。为了保证运算效率,δ取值不宜过大。本文根据原始等高线以及待匹配等高线节点序列中所包含的节点个数nm,取δ=[min(n, m)/10];基于特征描述序列的固有特征,ε则取两描述序列标准差最小值,即ε=min(σ1, σ2)。

(3) 利用式(8)计算原始等高线与其精匹配集内待匹配等高线的相似度。

(4) 依据相似度计算结果进行同名等高线匹配,若存在无法判断情况,需依据其他空间特征指标辅助判断。

基于上述步骤实现多源等高线匹配(图 11),对匹配精度、运行效率及不同权重取值对试验结果的影响进行评估和对比,获得表 5表 6图 12所示结果。

图 11 真实数据匹配结果 Fig. 11 The matching result of real datasets

表 5 λ=0.6时结果精度评价 Tab. 5 Accuracy evaluation when λ=0.6
等高线数据 匹配数/条 正确匹配数/条 错误匹配数/条 未匹配数/条 匹配召回率/(%) 匹配准确率/(%) 平均耗时/s
原始等高线数/条 待匹配等高线数/条
1757 3792 1553 1415 138 204 87.40 91.11 0.11

表 6 λ取不同值时匹配精度对比 Tab. 6 The comparison of matching accuracy with different λ values
λ 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
准确率/(%) 90.60 90.66 90.60 90.60 90.60 90.60 91.11 90.99 90.99 90.99 90.99
召回率/(%) 87.34 87.34 87.34 87.34 87.34 87.34 87.40 87.38 87.38 87.38 87.38

图 12 运行时间随等高线节点数量变化 Fig. 12 The running time changing with the number of contour nodes diagram

(1) 为了对匹配结果进行评价,对λ=0.6时的匹配精度进行了检查,并利用文献[29]的评价公式(9)对结果进行评估,如表 5所示。

(9)

根据表 5所示的试验结果统计信息,在试验区域内,本文方法具有较高的匹配召回率和匹配准确率,并能够保证较好的运算效率。本文将运行时间随等高线包含节点数量的变化情况绘制于图 12。由结果可知,等高线匹配耗时随着等高线包含节点个数的增加而增加,但当等高线包含节点个数过多时,会由于地形细节形态过多而出现匹配耗时过长、效率降低的问题,因而本文对包含节点数量过多的等高线进行特征点提取以保证运算效率。但由于特征点提取本身具有运算代价,同时还存在提取质量和精度的问题,会导致误匹配和匹配失败情况,这也是本次试验中匹配召回率和准确率降低的原因之一。因此在面向具体应用时需要利用大量数据进行充分试验,将等高线所包含的节点个数限制在合理范围内进而保证匹配效率和精度。

(2) 为验证不同权重取值对匹配结果的影响,对λ取0~1范围内不同值时匹配准确率及召回率进行了比较,获得如表 6所示结果。通过对比分析可知,当λ取0~1范围内不同值时匹配准确率均为90%~92%,召回率为87%~88%,并没有显著差异,说明本文所提出的CANV测度能够保证较高的匹配准确率,且λ取值对匹配结果的精度影响并不显著,在本试验区内λ=0.6时匹配精度相对较高。

综上所述,在合理的参数取值和计算能力范围内利用本文方法进行等高线匹配具有较高匹配精度,且能够保证良好的运行效率。

3 结论

等高线匹配是地图更新、制图综合以及数据融合的重要环节之一,已有的基于拓扑关系构建的匹配方法和基于欧氏距离的相似度计算方法,由于未顾及等高线的几何形态特征,导致在匹配过程中可能产生误匹配情况。本文提出一种顾及几何特征相似性的基于最长公共子序列的多源等高线匹配策略,以空间几何形态特征描述为目标,提出了基于节点曲率以及法向量与横坐标轴夹角的混合特征描述测度(CANV),将等高线节点序列转化为几何形态特征描述序列,利用模拟数据和真实数据对本文方法的适用性、准确率及运行效率进行了验证,并对参数取值以及不同测度对等高线的相似度区分效果进行了对比。试验结果表明,与已有方法相比,本文匹配策略顾及了等高线空间位置特征和几何形态特征,在等高线密集、非闭合区域以及变化剧烈区域具有较好的适用性和可靠性,能够有效降低多源等高线数据匹配误差,并保证较好的运行效率。

然而,本文所提出的匹配策略主要基于等高线空间位置和几何形态特征,在基于相似度的匹配过程中并未考虑等高线群构成的地形特征以及地貌变化规律,因而在匹配过程中仍然存在误匹配情况。顾及地形特征的特征点提取、参数设置以及匹配规则的进一步完善,将有助于提高多源等高线匹配精度和自动化程度,也是后续研究的重点内容。


参考文献
[1] COOPER A K, PELED A. Incremental updating and versioning[C]//Proceedings of the 20th International Cartographic Conference. Beijing: [s.n.], 2001: 2804-2809.
[2] 赵龙. 鲁棒惯性地形辅助导航算法研究[J]. 物理学报, 2012, 61(10): 231–237.
ZHAO Long. Robust inertial terrain aided navigation algorithm[J]. Acta Physica Sinica, 2012, 61(10): 231–237.
[3] 杨春成, 何列松, 谢鹏, 等. 顾及距离与形状相似性的面状地理实体聚类[J]. 武汉大学学报(信息科学版), 2009, 34(3): 335–338.
YANG Chuncheng, HE Liesong, XIE Peng, et al. Clustering analysis of geographical area entities considering distance and shape similarity[J]. Geomatics and Information Science of Wuhan University, 2009, 34(3): 335–338.
[4] 殷硕文, 邵茜. 基于地形匹配的InSAR地形变化检测方法研究[J]. 武汉大学学报(信息科学版), 2010, 35(1): 118–121.
YIN Shuowen, SHAO Qian. A method of topographic change detection base InSAR terrain matching technology[J]. Geomatics and Information Science of Wuhan University, 2010, 35(1): 118–121.
[5] 杨敏, 艾廷华, 刘鹏程, 等. 等高线与水网数据集成中的匹配及一致性改正[J]. 测绘学报, 2012, 41(1): 152–158.
YANG Min, AI Tinghua, LIU Pengcheng, et al. The matching and consistency correcting in the integration of contour and river network[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(1): 152–158.
[6] 王涛, 毋河海. 等高线拓扑关系的构建以及应用[J]. 武汉大学学报(信息科学版), 2004, 29(5): 438–442.
WANG Tao, WU Hehai. Construction and applications of topological relation among contour lines[J]. Geomatics and Information Science of Wuhan University, 2004, 29(5): 438–442.
[7] 艾廷华, 祝国瑞, 张根寿. 基于Delaunay三角网模型的等高线地形特征提取及谷地树结构化组织[J]. 遥感学报, 2003, 7(4): 292–298.
AI Tinghua, ZHU Guorui, ZHANG Genshou. Extraction of landform features and organization of valley tree structure based on Delaunay triangulation model[J]. Journal of Remote Sensing, 2003, 7(4): 292–298.
[8] 吴凡, 粟卫民. 顾及地形特征的等高线拓扑空间关系表达[J]. 武汉大学学报(工学版), 2006, 39(3): 140–144.
WU Fan, SU Weimin. Representation of topological spatial relations between contour lines based on terrain features[J]. Engineering Journal of Wuhan University, 2006, 39(3): 140–144.
[9] 张尧, 樊红, 黄旺. 基于Delaunay三角网的等高线树生成方法[J]. 测绘学报, 2012, 41(3): 461–467, 474.
ZHANG Yao, FAN Hong, HUANG Wang. The method of generating contour tree based on contour Delaunay triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(3): 461–467, 474.
[10] 朱强, 武芳, 钱海忠, 等. 基于空间认知的等高线树的构建[J]. 信息工程大学学报, 2011, 12(4): 458–462.
ZHU Qiang, WU Fang, QIAN Haizhong, et al. Spatial cognition oriented contour-tree building[J]. Journal of Information Engineering University, 2011, 12(4): 458–462. DOI:10.3969/j.issn.1671-0673.2011.04.016
[11] 吴凡, 粟卫民. 基于网络模型的等高线群拓扑关系表示[J]. 遥感学报, 2007, 11(2): 145–151.
WU Fan, SU Weimin. The representation of topological relations of contour groups based on a network model[J]. Journal of Remote Sensing, 2007, 11(2): 145–151.
[12] 邢汉发, 周晓光, 许礼林. 基于线/线拓扑关系的局部变化等高线融合[J]. 武汉大学学报(信息科学版), 2010, 35(11): 1322–1326.
XING Hanfa, ZHOU Xiaoguang, XU Lilin. Local contour line fusion based on line/line topological relations[J]. Geomatics and Information Science of Wuhan University, 2010, 35(11): 1322–1326.
[13] 刘涛, 杜清运, 毛海辰. 空间线群目标相似度计算模型研究[J]. 武汉大学学报(信息科学版), 2012, 37(8): 992–995.
LIU Tao, DU Qingyun, MAO Haichen. Spatial similarity assessment model and its application in line groups[J]. Geomatics and Information Science of Wuhan University, 2012, 37(8): 992–995.
[14] ALT H, GODAU M. Computing the Fréchet distance between two polygonal curves[J]. International Journal of Computational Geometry & Applications, 1995, 5(1-2): 75–91.
[15] MUSTIÈRE S, DEVOGELE T. Matching networks with different levels of detail[J]. Geoinformatica, 2008, 12(4): 435–453. DOI:10.1007/s10707-007-0040-1
[16] 安晓亚, 孙群, 尉伯虎. 利用相似性度量的不同比例尺地图数据网状要素匹配算法[J]. 武汉大学学报(信息科学版), 2012, 37(2): 224–228, 241.
AN Xiaoya, SUN Qun, YU Bohu. Feature matching from network data at different scales based on similarity measure[J]. Geomatics and Information Science of Wuhan University, 2012, 37(2): 224–228, 241.
[17] 安晓亚.空间数据几何相似性度量理论方法与应用研究[D].郑州: 信息工程大学, 2011.
AN Xiaoya. Research on theory, methods and applications of geometry similarity measurement for spatial data[D]. Zhengzhou: Information Engineering University, 2011. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=chxb201301027
[18] 安晓亚, 刘平芝, 杨云, 等. 一种线状要素几何相似性度量方法及其应用[J]. 武汉大学学报(信息科学版), 2015, 40(9): 1225–1229.
AN Xiaoya, LIU Pingzhi, YANG Yun, et al. A geometric similarity measurement method and applications to linear feature[J]. Geomatics and Information Science of Wuhan University, 2015, 40(9): 1225–1229.
[19] 韩敏, 郑丹晨. 基于模糊形状上下文特征的形状识别算法[J]. 自动化学报, 2012, 38(1): 68–75.
HAN Min, ZHENG Danchen. Shape recognition based on fuzzy shape context[J]. Acta Automatica Sinica, 2012, 38(1): 68–75.
[20] 秦奋, 焦学军. 全面定量评估DEM精度的缓冲区叠加法研究[J]. 西北农业学报, 2008, 17(3): 336–342.
QIN Fen, JIAO Xuejun. Study on buffer superposition to quantitatively evaluation DEM precision completely[J]. Acta Agriculturae Boreali-Occidentalis Sinica, 2008, 17(3): 336–342. DOI:10.3969/j.issn.1004-1389.2008.03.074
[21] 杨亚飞, 郑丹晨, 韩敏. 一种基于多尺度轮廓点空间关系特征的形状匹配方法[J]. 自动化学报, 2015, 41(8): 1405–1411.
YANG Yafei, ZHENG Danchen, HAN Min. A shape matching method using spatial features of multi-scaled contours[J]. Acta Automatica Sinica, 2015, 41(8): 1405–1411.
[22] MOKHTARIAN F, ABBASI S, KITTLER J. Efficient and robust retrieval by shape content through curvature scale space[M]//SMEULDERS A, JAIN R. Image Databases and Multi-media Search. River Edge, NJ: World Scientific Publishing Co Inc, 1998: 51-58.
[23] ADAMEK T, O'CONNOR N E. A multiscale representation method for nonrigid shapes with a single closed contour[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2004, 14(5): 742–753. DOI:10.1109/TCSVT.2004.826776
[24] DONOSER M, RIEMENSCHNEIDER H, BISCHOF H. Efficient partial shape matching of outer contours[C]//Proceedings of 9th Asian Conference on Computer Vision. Xi'an: Springer, 2009: 281-292. https://link.springer.com/chapter/10.1007%2F978-3-642-12307-8_26
[25] 安晓亚, 孙群, 肖强, 等. 一种形状多级描述方法及在多尺度空间数据几何相似性度量中的应用[J]. 测绘学报, 2011, 40(4): 495–501, 508.
AN Xiaoya, SUN Qun, XIAO Qiang, et al. A shape multilevel description method and application in measuring geometry similarity of multi-scale spatial data[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(4): 495–501, 508.
[26] VLACHOS M, KOLLIOS G, GUNOPULOS D. Discovering similar multidimensional trajectories[C]//Proceedings of the 18th International Conference on Data Engineering. San Jose, CA: IEEE, 2002: 673-684.
[27] 王华夏, 程咏梅, 刘楠, 等. 面向地形等高线匹配的三重约束LCSS算法[J]. 西北工业大学学报, 2017, 35(1): 38–42.
WANG Huaxia, CHENG Yongmei, LIU Nan, et al. A algorithm based on triple constraint LCSS for terrain contour lines[J]. Journal of Northwestern Polytechnical University, 2017, 35(1): 38–42. DOI:10.3969/j.issn.1000-2758.2017.01.007
[28] VLACHOS M, HADJIELEFTHERIOU M, GUNOPULOS D, et al. Indexing multi-dimensional time-series with support for multiple distance measures[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, D.C.: ACM, 2003: 216-225.
[29] TONG Xiaohua, LIANG Dan, JIN Yanmin. A linear road object matching method for conflation based on optimization and logistic regression[J]. International Journal of Geographical Information Science, 2014, 28(4): 824–846. DOI:10.1080/13658816.2013.876501
http://dx.doi.org/10.11947/j.AGCS.2019.20170688
中国科学技术协会主管、中国测绘地理信息学会主办。
0

文章信息

郭文月,刘海砚,孙群,余岸竹,丁梓越
GUO Wenyue, LIU Haiyan, SUN Qun, YU Anzhu, DING Ziyue
顾及几何特征相似性的多源等高线匹配方法
A multisource contour matching method considering the similarity of geometric features
测绘学报,2019,48(5):643-653
Acta Geodaetica et Cartographica Sinica, 2019, 48(5): 643-653
http://dx.doi.org/10.11947/j.AGCS.2019.20170688

文章历史

收稿日期:2017-12-04
修回日期:2018-09-06

相关文章

工作空间