留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种基于形状上下文特征匹配的线状要素Morphing方法

方文江 李精忠

方文江, 李精忠. 一种基于形状上下文特征匹配的线状要素Morphing方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(7): 963-967. doi: 10.13203/j.whugis20150674
引用本文: 方文江, 李精忠. 一种基于形状上下文特征匹配的线状要素Morphing方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(7): 963-967. doi: 10.13203/j.whugis20150674
FANG Wenjiang, LI Jingzhong. A Morphing of Linear Feature Based on Shape Context Matching[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 963-967. doi: 10.13203/j.whugis20150674
Citation: FANG Wenjiang, LI Jingzhong. A Morphing of Linear Feature Based on Shape Context Matching[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 963-967. doi: 10.13203/j.whugis20150674

一种基于形状上下文特征匹配的线状要素Morphing方法

doi: 10.13203/j.whugis20150674
基金项目: 

国家自然科学青-基金 41001229

国家863计划 2012AA12A404

国家基础科学人才培养基金 J1103409

详细信息
    作者简介:

    方文江, 博士, 硕士生, 主要从事空间数据库多尺度表达的理论与方法研究。ironicstone@163.com

    通讯作者: 李精忠, 博士, 副教授。lilideyx@126.com
  • 中图分类号: P208

A Morphing of Linear Feature Based on Shape Context Matching

Funds: 

The National Natural Science Foundation of China 41001229

the National High Technology Research and Development Program(863 Program) of China 2012AA12A404

the National Science Talents Fund J1103409

More Information
    Author Bio:

    FANG Wenjiang, postgraduate, spcializes in the multiple representations of spatial data. E-mail: ironicstone@163.com

    Corresponding author: LI Jingzhong, PhD, associate professor. E-mail:lilideyx@126.com
图(8) / 表(1)
计量
  • 文章访问数:  1109
  • HTML全文浏览量:  59
  • PDF下载量:  310
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-03-10
  • 刊出日期:  2017-07-05

一种基于形状上下文特征匹配的线状要素Morphing方法

doi: 10.13203/j.whugis20150674
    基金项目:

    国家自然科学青-基金 41001229

    国家863计划 2012AA12A404

    国家基础科学人才培养基金 J1103409

    作者简介:

    方文江, 博士, 硕士生, 主要从事空间数据库多尺度表达的理论与方法研究。ironicstone@163.com

    通讯作者: 李精忠, 博士, 副教授。lilideyx@126.com
  • 中图分类号: P208

摘要: 提出了一种基于上下文特征的形状匹配方法,并将其用于线状要素的Morphing变换。首先通过计算每个点的形状上下文,建立形状直方图,然后通过直方图匹配找到同名实体在大小比例尺下轮廓点的最佳匹配关系。根据点的匹配关系,得到对应线段。最后通过分段线性内插实现线状要素的连续尺度变换。实验结果表明,基于形状上下文的轮廓点集匹配方法不需要标志点或者关键点,适应性较强,可以有效地实现形状匹配,极大地提高Morphing变换的精度。

English Abstract

方文江, 李精忠. 一种基于形状上下文特征匹配的线状要素Morphing方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(7): 963-967. doi: 10.13203/j.whugis20150674
引用本文: 方文江, 李精忠. 一种基于形状上下文特征匹配的线状要素Morphing方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(7): 963-967. doi: 10.13203/j.whugis20150674
FANG Wenjiang, LI Jingzhong. A Morphing of Linear Feature Based on Shape Context Matching[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 963-967. doi: 10.13203/j.whugis20150674
Citation: FANG Wenjiang, LI Jingzhong. A Morphing of Linear Feature Based on Shape Context Matching[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 963-967. doi: 10.13203/j.whugis20150674
  • 近年来, WEB2.0、LBS(location-based service)等的快速发展,对地图的连续尺度表达提出了新的需求,人们希望能够实现空间信息可视化表达的多视角和多层次。为满足人们的要求,地图连续综合技术被提出[1]。Morphing又称图形渐变技术,其基本思想是采用某种内插方法使得初始图形光滑连续地渐变到目标图形。这和地图连续综合技术的思想相契合。在GIS领域,利用Morphing实现地图连续尺度变换,其基本思想分为匹配和插值两步[2]。因Morphing变换的精度主要受匹配精度的影响[3],因此,很多学者在优化匹配方面做了一系列工作,主要有文献[4]通过将小比例尺图形进行点加密,加密到与大比例尺点数一致,然后依据点号进行一一对应,以此建立匹配关系;文献[5]将弧度较大处的顶点视作特征点,然后基于位移的关系建立匹配关系;文献[6]通过约束Delaunay三角网提取小比例尺地图上线状要素的特征点,然后采用模拟退火技术在特征点与大比例尺线状要素顶点之间建立全局最优化匹配;文献[7-9]把弯曲结构作为切入点,提出基于弯曲结构的匹配方法;文献[10]将传统矢量坐标转化为转向角函数,基于转向角函数实现边特征匹配。这些方法或需要寻找特征点建立对应匹配;或不需要特征点,只进行简单内插后匹配,没有顾及要素的上下文信息。对于地图要素而言,小比例尺要素通常是由大比例尺经过综合变换得来的,如弯曲的化简、删除、夸大和典型化的操作[1]。因此,可以从小比例尺上的点入手,寻找各点在大比例尺上的最佳匹配来完成对应点的匹配。大小比例尺具有类似的上下文信息。形状上下文是一种得到广泛运用的目标形状描述子[11],它通过点集之间的关系,即其上下文信息来描述形状,该方法不需要这些点具有曲率最大、弧度较大等常规方法中认为的特殊点所具备的特征,因此,适应性和鲁棒性较强。

    本文提出一种基于形状上下文的Morphing方法,其基本思想是将点的形状上下文作为图形的形状描述,对于大小比例尺下同名实体所对应的点集来说,对应点的匹配可以通过计算每个点的形状上下文及各点之间的匹配度来寻找最佳匹配。匹配完成之后通过常用的线性内插方法就可以得到中间比例尺的地图表达。

    • 一个形状表示为N个轮廓点的集合,任意点pi的形状上下文就是pi与点集中其余各点相对于该点的角度θ以及对数距离lgρ的直方图分布,利用直方图来描述图形特征。因此,轮廓上的采样点越多,N越大,对形状的描述就越详细。对任意点pi以其为原点建立对数极坐标系,在对数极坐标系下分别将lgρθ进行S等分和T等分(图 1),因此,整个空间被分成了S×T个区域。通常选择S=5,T=12,即划分出60个子区域[11]。空间区域分割完成之后,记录除pi点外的N-1个点在这60个区域的分布数目,由该数目来作为点的形状上下文。计算公式为:

      图  1  形状上下文的计算[11]

      Figure 1.  Computation of Shape Context

      $$ {h_i}\left( k \right) = \# \left\{ {p \ne {p_i}:p \in {\rm{bin}}\left( k \right)} \right\} $$ (1)

      其中,k=0, 1, 2, 3, …, 59,#操作表示取p为落入第K个区域(bin)且不同于pi点的轮廓上其余点的数目。以图 1为例,假设从X轴正方向开始由内而外以逆时针起算,则落在箭头所指区域,即第48个bin内有4个点,有hi(48)=4。其他的bin用同样的方法来统计,这样就得到了一个有60个分量的形状直方图。计算点集中每一个点的形状直方图,即可完成图形的形状描述。

      考虑到形状上下文描述子是基于直方图分布的特征,因此采用χ2分布统计检验作为形状上下文的相似性匹配代价,定义两个点的匹配代价Cij为:

      $$ {C_{ij}} = C\left( {{p_i},{q_j}} \right) = \frac{1}{2}\sum\limits_{k = 1}^K {\frac{{\left[ {{h_i}\left( k \right) - {h_j}\left( h \right)} \right]2}}{{{h_i}\left( k \right) + {h_j}\left( k \right)}}} $$ (2)

      式中,hi(k)、hj(k)分别代表第一个图形上点pi和第二个图形上点qj的形状直方图中第K个bin中的值。Cij越大,说明两个点的匹配代价越大,两点之间相似性越小,互为对应点的可能性就越小。得到两个形状所有点之间的匹配代价之后,点模式匹配的目标是寻找一个匹配关系π,使得式(3) 取得最小值。

      $$ \mathop {\min }\limits_{\rm{\pi }} H\left( \pi \right) = \sum\limits_i {C\left( {{p_i},{q_{\pi \left( i \right)}}} \right)} $$ (3)

      式中,π(i)为与i的对应点号。上面的点集匹配问题就变成了典型的二分图匹配问题,把匹配代价最小的点作为最相似的对应点,而二分图的最大匹配问题可以利用匈牙利算法来解决。

      本文从小比例尺出发,利用匈牙利算法建立完美匹配,找到对应大比例尺上的对应点,既可以充分利用小比例尺上的点,又能够很好地顾及到要素的上下文信息。

    • 对于一同名实体,它在较大比例尺RA下的表达为A,在较小比例尺RB下的表达为B,任一中间比例尺Rc下的表达为C。通过形状上下文完成点集匹配后,假设A中的一个点的子集Asub(i)对应B中一个点的子集Bsub(j)。则:

      $$ A = \sum\limits_i {{A_{{\rm{sub}}\left( i \right)}}} $$ (4)
      $$ B = \sum\limits_j {{B_{{\rm{sub}}\left( j \right)}}} $$ (5)

      f1f2分别表示定义域[0, 1]到Asub(i)Bsub(j)的连续函数, f表示形状内插之后中间状态的连续函数,对应的子集为Csub(k)

      $$ f = \left( {1 - g} \right) \times {f_1} + g \times {f_2},0 \le g \le 1 $$ (6)

      式中,g为介于大、小比例尺之间的归一化中间尺度。由此可知,当g=0时, f=f1, 即Csub(k)=Asub(i);当g=1时,f=f2, 即Csub(k)=Bsub(j);当0 < g < 1时,f为介于f1f2之间的中间表达,且g的大小控制内插结果的偏向度。归一化参数g为:

      $$ g = \frac{{\left( {\frac{1}{{{R_C}}} - \frac{1}{{{R_A}}}} \right)}}{{\left( {\frac{1}{{{R_B}}} - \frac{1}{{{R_A}}}} \right)}} $$ (7)

      通过对每一组对应点集进行相同的处理,最后可以得到Morphing后的中间状态:

      $$ C = \sum\limits_i {{C_{{\rm{sub}}\left( k \right)}}} $$ (8)
    • 为了定量化Morphing的精度,引入文献[5]的评价方法,采用加权的位矢距离来衡量。曲线相似性指标通常有距离、长度、方向、形状等。假设对应的两个点集分别为α(μ)、β(μ),对应的曲线分别为A′、B′。如果单纯用长度差异clen来衡量,则有:

      $$ {c_{{\rm{len}}}}\left( {A',B'} \right) = \left| {\left| {A'} \right| - \left| {B'} \right|} \right| $$ (9)

      但是在多尺度环境下,单一指标可能会发生很大的变化,因此,单一指标缺乏鲁棒性。可以通过引入位移矢量来描述曲线方向的变化。对于对应点集来说,其位移矢量就为β(μ)-α(μ),这些位移矢量又构成一条曲线,定义为γ(μ),则γ(μ)=β(μ)-α(μ),μ∈[0, 1],如图 2(b)所示。

      图  2  位矢距离γ(μ)的构造

      Figure 2.  Construction of the Measuring Distance Parameter γ(μ)

      可以用|γ|来表示A′渐变到B′的在方向上的变化大小,很显然,|γ|越大,方向上的偏移就越大。因此可以结合长度和方向这两个指标,用加权位矢δ(A′, B′)来衡量图形变化中的位移大小, 定义如下:

      $$ \delta \left( {A',B'} \right) = \frac{{\left| \gamma \right|\left( {\left| {A'} \right| + \left| {B'} \right|} \right)}}{{\left( {\left| {A'} \right| + \left| {B'} \right|} \right)}} $$ (10)

      那么对于整体就有:

      $$ \delta \left( {A,B} \right) = \sum {\delta \left( {A',B'} \right)} $$ (11)

      δ(A, B)反映了对应点之间位移矢量的加权变化情况,其值越小说明匹配效果越好,Morphing精度越高。

    • 本文采用模拟数据和真实等高线数据进行实验来说明本文方法的可行性和有效性。

      模拟实验数据如图 3所示,图 3(a)为一线状要素在大比例尺下的表达,共有205个顶点,即A(p0, p1, p2, …, p203, p204), 表达较为详细。图 3(b)中为同名实体在小比例尺下的表达,共有28个顶点,即B(q0, q1, …, p26, p27),表达较为概略。实验中,小比例尺图形B上的所有点都将参与匹配。对于该数据,分别采用线性插值算法和本文方法进行点模式的匹配实验。匹配的结果如图 4所示。图 4(a)中Ⅰ区和Ⅱ区出现了明显的误匹配情况,其加权位矢距离δ(A, B)为130.552 8,基于线性的插值算法从纯几何的角度进行点的一一匹配,忽视了点的上下文信息。采用本方法,δ(A, B)为70.747 1,有了很大的改善,在进行匹配的过程中,充分考虑了点的形状上下文信息,提高了匹配的精度,匹配结果见图 4(b)

      图  3  数据在大小比例尺下的表达

      Figure 3.  Representations of Polylinesin Two Different Scales

      图  4  线性方法和本文方法的点匹配结果

      Figure 4.  Matching Results of Two Different Method

    • 基于上面实验的匹配结果,进行形状内插。B被其端点分成了27段,分别为q0q1q1q2、…、q26q27A被其端点分成了204段,分别为p0p1p1p2p2p3、…、p203p204。点匹配关系可用表 1来表示。

      表 1  匹配点对

      Table 1.  Corresponding Points

      qj pi
      q0 p0
      q1 p10
      q2 p13
      q3 p16
      q4 p20
      q5 p25
      q6 p45
      q7 p47
      q8 p53
      q9 p66
      q10 p74
      q11 p92
      q12 p100
      q13 p109
      q14 p121
      q15 p123
      q16 p125
      q17 p128
      q18 p129
      q19 p131
      q20 p136
      q21 p143
      q22 p153
      qj23 p179
      qj24 p191
      qj25 p196
      qj26 p199
      qj27 p204

      线状要素上点将线划分成了线段,因此,由匹配点关系得到匹配线段之间的关系。例如,线段q0q1对应线段p0p10q1q2对应p10p13。因此, 在基于形状上下文匹配的基础上把对应点之间的连线作为插值路径进行线性插值。

      图 5图 6分别为本文方法和线性插值方法的Morphing结果。其中g=0和g=1分别为线状要素在大比例尺RA下的表达A,在小比例尺RB下的表达B。实验中,分别设置g=0.2、0.4、0.6、0.8等4个不同的尺度进行形状内插。依据式(7),g与中间比例尺RC的关系为RC=(1-gRA+g×RB。可以看出,图 5中的结果更加符合空间数据的渐变特征,弯曲过渡光滑自然。图 6中,由于大小比例尺初始数据采样点密度差异较大,单纯的线性内插并没有考虑要素的上下文信息,使得匹配过程中出现较大偏差,因此渐变过程中出现了不同程度的变形。这主要有以下两个问题:① 出现了不符合原始形态的变化,图 6(d)中方框标注的地方产生了形态变异;② 各部分渐变的尺度不一致,出现了局部的突变,见图 6(c)中的圆框部分。

      图  5  基于本文方法的模拟数据Morphing效果

      Figure 5.  Morphing Effects of Simulation Data Based on the Method in this Paper

      图  6  基于线性插值方法的模拟数据Morphing效果

      Figure 6.  Morphing Effects of Simulation Data Based on the Linear Interpolation Method

      图 7图 8为某区域真实等高线数据采用本方法和线性插值方法的Morphing效果,等高距为25 m,从左到右g值分别为0、0.4、0.6和1,其中,g=0对应1:1万的初始表达,g=1对应1:5万的初始表达,g=0.4、0.6分别对应1:2.6万、1:3.4万的表达。由结果很容易发现图 7的渐变效果更好,曲线弯曲形态由复杂到简单,过渡比较平滑,中间状态不存在自相交;图 8则存在一些明显的形态变异,图中圆框位置发生变形和严重拓扑错误,不符合制图综合的基本要求。

      图  7  基于本文方法的真实等高线数据Morphing效果

      Figure 7.  Morphing Effects of Real Contour Data Based on the Method in this Paper

      图  8  基于线性插值方法的真实等高线数据Morphing效果

      Figure 8.  Morphing Effects of Real Contour Data Based on the Linear Interpolation Method

    • 本文提出了一种基于形状上下文匹配的线状要素Morphing变换方法,该方法把点集的形状上下文作为形状描述子,在点模式匹配过程中顾及了要素的上下文信息,同时该方法不需要像常规方法那样寻找特征点,具有很强的鲁棒性,提高了Morphing变换的精度和适用范围。

参考文献 (11)

目录

    /

    返回文章
    返回