留言板

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

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

顾及邻域结构的线状要素Morphing方法

李精忠 方文江

李精忠, 方文江. 顾及邻域结构的线状要素Morphing方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1138-1143. doi: 10.13203/j.whugis20160142
引用本文: 李精忠, 方文江. 顾及邻域结构的线状要素Morphing方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1138-1143. doi: 10.13203/j.whugis20160142
LI Jingzhong, FANG Wenjiang. Morphing Polylines by Preserving Local Neighborhood Structures[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1138-1143. doi: 10.13203/j.whugis20160142
Citation: LI Jingzhong, FANG Wenjiang. Morphing Polylines by Preserving Local Neighborhood Structures[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1138-1143. doi: 10.13203/j.whugis20160142

顾及邻域结构的线状要素Morphing方法

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

国家重点研发计划 2017YFB0503601

国家重点研发计划 2017YFB0503502

国家自然科学基金 41671448

详细信息
    作者简介:

    李精忠, 博士, 副教授, 研究方向为DEM分析、地图综合、空间数据多尺度表达。00009232@whu.edu.cn

    通讯作者: 方文江, 硕士生。244550975@qq.com
  • 中图分类号: P208;P283

Morphing Polylines by Preserving Local Neighborhood Structures

Funds: 

The National Key Research and Development Program of China 2017YFB0503601

The National Key Research and Development Program of China 2017YFB0503502

the National Natural Science Foundation of China 41671448

More Information
    Author Bio:

    LI Jingzhong, PhD, associate professor, specializes in the DEM analysis, map generalization and multiple representations of spatial data. E-mail: 00009232@whu.edu.cn

    Corresponding author: FANG Wenjiang, postgraduate. E-mail: 244550975@qq.com
图(3)
计量
  • 文章访问数:  1143
  • HTML全文浏览量:  58
  • PDF下载量:  287
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-08-03
  • 刊出日期:  2018-08-05

顾及邻域结构的线状要素Morphing方法

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

    国家重点研发计划 2017YFB0503601

    国家重点研发计划 2017YFB0503502

    国家自然科学基金 41671448

    作者简介:

    李精忠, 博士, 副教授, 研究方向为DEM分析、地图综合、空间数据多尺度表达。00009232@whu.edu.cn

    通讯作者: 方文江, 硕士生。244550975@qq.com
  • 中图分类号: P208;P283

摘要: 地图综合过程中,综合前后图形轮廓上两点间的绝对距离可能会发生很大改变,但是点的邻域结构和上下文信息相对保持稳定。基于此,首先提出一种结合形状上下文和松弛标记法的形状匹配方法,通过全局形状描述子形状上下文来描述点集的不变特征;然后将点集间形状上下文的统计检验匹配代价转化为松弛标记法的初始匹配概率,接着通过迭代支持度函数更新匹配概率,直到建立最优匹配;最后根据点集的匹配关系,得到相应的匹配线段,通过线性插值实现要素的连续尺度变换。实验结果表明,该方法不仅能够很好地顾及要素的上下文信息,而且也能顾及到邻域结构特征,提高Morphing变换的精度。

English Abstract

李精忠, 方文江. 顾及邻域结构的线状要素Morphing方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1138-1143. doi: 10.13203/j.whugis20160142
引用本文: 李精忠, 方文江. 顾及邻域结构的线状要素Morphing方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1138-1143. doi: 10.13203/j.whugis20160142
LI Jingzhong, FANG Wenjiang. Morphing Polylines by Preserving Local Neighborhood Structures[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1138-1143. doi: 10.13203/j.whugis20160142
Citation: LI Jingzhong, FANG Wenjiang. Morphing Polylines by Preserving Local Neighborhood Structures[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1138-1143. doi: 10.13203/j.whugis20160142
  • Web2.0、网络地图以及基于位置的服务(location based service,LBS)等技术的发展,对地图多尺度表达提出了新的要求,人们希望能够实现空间信息的多视角、多层次和光滑连续的可视化表达。为满足这一要求,Sester和Brenner[1]提出了地图连续综合的技术。Morphing又称图形渐变技术,其基本思想是采用某种内插方法使初始图形P(图像)光滑连续地渐变到目标图形Q(图像)[2]。在这种光滑过渡中,中间态既具有P的特征,又具有Q的特征,这和连续地图综合技术思想相契合。在GIS领域,利用Morphing实现地图连续尺度变换的基本过程分为匹配和插值两步[3], 其精度主要受匹配精度的影响,因此学者们在优化匹配方面做了一系列工作。文献[4]将小比例尺图形进行点加密至与大比例尺点数一致,然后依据点号一一对应以建立匹配关系;文献[5]将弧度较大处的顶点视作特征点,然后基于位移的关系建立匹配关系;文献[6]通过约束Delaunay三角网提取小比例尺地图上线状要素的特征点,采用模拟退火技术在特征点与大比例尺线状要素顶点之间建立全局最优化匹配;文献[7-8]以弯曲结构作为切入点,提出基于弯曲结构的匹配方法;文献[9]提出将传统矢量坐标转化为转向角函数,基于转向角函数实现边特征匹配。

    综上分析,可以将Morphing匹配方法分为两类,一是从要素的局部结构出发,二是从要素的整体结构出发。对于地图要素而言,通过对大比例尺地图中的弯曲进行化简、删除、夸大和典型化操作得到小比例尺地图的过程中, 图形轮廓上两点间的绝对距离可能会发生很大改变,但是点的邻域结构和上下文信息应保持相对稳定,这种整体与局部的稳定性不应被割裂。因此, 本文提出了一种顾及邻域结构的线状要素Morphing方法,在保持形状轮廓点集局部邻域关系的情况下进行匹配,其主要思想是将形状上下文和松弛标记法结合来改进点集之间的匹配精度。算法首先利用形状上下文来描述点集之间的不变特征; 然后将点集间形状上下文的统计检验匹配代价转化为松弛标记法的初始匹配概率; 接着通过迭代支持函数更新匹配概率,直到建立最优匹配; 最后通过形状内插即可得到Morphing渐变效果。

    • 对于包含M个点的形状轮廓点集P={p1, p2pM}, 形状轮廓中任意点pi的形状上下文[10]就是pi与点集中其余各点相对于该点的角度θ以及对数距离lgρ的直方图分布。在对数极坐标系下分别将lgρθ进行S等分和T等分(图 1),整个空间被分成了K=S×T个区域,通常选择S=5,T=12,即划分出60个子区域。pi的形状上下文可根据式(1)计算:

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

      图  1  形状上下文计算方法[10]

      Figure 1.  Computation of Shape Context[10]

      式中,k=0, 1, 2…K-1;#操作表示qj为落入第k个区域中不同于pi点的轮廓上的其余点的数目; bin(k)为第k个被分割的区域。例如图 1中,落在箭头所指区域,即第48个bin内有4个点,则有hi 48 =4。其他的bin用同样的方法进行统计。

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

      $$ {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( k \right)} \right]}^2}}}{{{h_i}\left( k \right) + {h_j}\left( k \right)}}} {\rm{ }} $$ (2)

      式中,hi (k)、hj(k)分别代表初始图形上点pi的形状直方图分布和目标图形上点qj中第k个bin中的值。显然,Cij越大, 说明piqj的匹配代价越大,两点之间的相似性越小,互为对应点的可能性(概率)就越小。

    • 当形状发生变化时,它们之间的绝对距离可能会发生较大的改变,但是在物理结构的限制下,这两个点在形变之后仍然相距不会太远,或称它们仍然相邻。本文用邻域来描述这种相邻关系。

      定义1  邻域。对于包含M个点的形状轮廓点集P={p1, p2pM},记Nipi的邻域,Ni由与pi距离最近的几个点组成。相邻关系具有对称性,如果piNj, 则pjNi,且邻域内的点互为邻居。

      为顾及邻域结构,点集匹配问题转化为保持邻域关系的最佳匹配问题。假设两个形状分别为P={p1, p2pM}和Q={q1, q2qN},寻找PQ之间的最佳匹配,即寻找目标函数:

      $$ f^\circ = {\rm{arg}}\;{\rm{ma}}{{\rm{x}}_f}S\left( {P, Q, f} \right) $$ (3)

      式中,

      $$ \begin{array}{l} S\left( {P, Q, f} \right) = \sum\limits_{m = 1}^M {\sum\limits_{i \in {N_m}} {\delta \left( {m, i} \right)} } + \\ \;\;\;\;\sum\limits_{n = 1}^N {\sum\limits_{j \in {N_n}} {\delta \left( {{f^{-1}}\left( n \right){\rm{ }}, {f^{-1}}\left( j \right)} \right)} } \end{array} $$ (4)
      $$ \delta \left( {m, i} \right) = 1-d\left( {m, i} \right) $$ (5)
      $$ d\left( {m, i} \right) = {\left( {\left\| {{p_m}-{p_i}} \right\|-{\rm{ }}\left\| {{q_{f(m)}}-{q_{f(i)}}} \right\|} \right)^2} $$ (6)

      fPQ的形状匹配函数;f°为最佳匹配;$\left\| {{p_m}-{p_i}} \right\|$表示pmpi的距离;qf(m)表示pmQ中的匹配点;qf(i)表示piQ中的匹配点。文献[11]把问题简化,规定互为邻居的点间的距离为0,非邻居点的距离为1,则:

      $$ \delta \left( {m, i} \right) = \left\{ \begin{array}{l} 1, i \in {N_m}, f\left( i \right) \in {N_{f(m)}}\\ 0, 其他 \end{array} \right. $$ (7)

      如果pmpi相邻,qf(m)qf(i)也相邻,则δ(m, i) =1,说明f保持了pmpi的相邻关系;否则δ(m, i) =0,f没有保持pmpi的相邻关系或者pmpi本来就不相邻。

      最终,点集匹配转化成了一个最优化问题,本文选择松弛标记法来解决。

    • 松弛标记法是一种利用符号描述模式的识别方法,它以迭代的形式进行,整个过程与人的猜测推理过程类似,利用各种关系逐步缩小搜索范围,最终求出正确的结果[11-12]。在GIS领域,松弛标记法主要应用于城市道路网的匹配[13-14]以及遥感影像匹配[15]。松弛标记法将处理对象称为目标,描述目标的符号称为标记。假设目标集合X= (x1, x2xn),标记集合Λ= (λ1, λ2λm)。松弛标记任务就是基于目标集合的上下文信息和标记集合的相容性约束,将符合一致性和确定性要求的某一个标记λkΛ分配给对应目标xiX

      Mk (λi)为目标xk具有标记λi的概率,在松弛过程中,通过迭代来更新估计的概率,更新概率算子如下:

      $$ {M_k}^{(t + 1)}\left( {{\lambda _i}} \right) = \frac{{{M_k}^{(t)}({\lambda _i}){S_k}^{(t)}({\lambda _i})}}{{\sum\limits_{{\lambda _j} \in \Lambda } {{M_k}^{(t)}({\lambda _j}){S_k}^{(t)}({\lambda _j})} }}{\rm{ }} $$ (8)

      式中,Mk(t)(λi)为第t次迭代时标记λi指派给标记xk的概率;S为表示全局上下文信息对当前标记概率估计值的支持度函数; Sk(t)(λi)可定义为:

      $$ {S_k}^{(t)}({\lambda _i}) = \sum\limits_{l \in {N_i}} {\sum\limits_{{\lambda _j} \in \Lambda } {{R_{kl}}({\lambda _i}, {\lambda _j}){M_l}^{(t)}({\lambda _j})} } $$ (9)

      式中,Rkl(λi, λj)为相容性系数,表示将标记λiλj分别指派给xkxl时两者的共存相容性。松弛标记法用相容性系数Rkl(λi, λj)记录局部信息,Rkl(λi, λj)的值越大,说明λiλj标记xkxl的效果越好。

      松弛标记是一个不断迭代的过程,每一次迭代都更新一次概率矩阵M的值,直到M收敛或者达到预定的迭代次数,迭代结束。

    • 本文中,假定大比例尺线状要素P经过综合得到小比例尺要素Q。可将PQ表示为一系列点的集合,即P={p1, p2pm},Q={q1, q2qn}。由于通常要求得到一对一的匹配,因此在点集中加入特殊点nil与多余的点相对应,则P={p1, p2pm, nil},Q={q1, q2qn, nil}, f:PQ。在f中,除了可能有多个点对应到nil外,其他点都是一一对应的,本文中小比例尺图形由大比例尺图形综合得到,因此小比例尺图形上的点数小于大比例尺上的点数,故小比例尺上的点能够在大比例尺上找到对应点,反之不然。根据§1.3中松弛标记法的定义,将P视为松弛标记过程中的目标集合,Q视为标记集合。因此,点集匹配问题就转化成一个通过松弛标记法求解目标和标记的分配组合问题。

      在松弛标记法中,相容性系数的确定是关键步骤。文献[11]方法中,邻域Ni内点间的关系是对等的,不管是距离点pi近或者远的邻居,都会使得相容性系数为1。则该点的远邻可能会对匹配过程产生干扰。因此本文结合Scott等[16]提出的保持圈序的形状匹配方法以及加权的思想[17],构造出鲁棒性更强的新相容性系数。首先定义权的概念,假设Ni=(ni1, ni2niA),nijpi的第j个邻居的标号,pi所有邻居的距离为Si=(si1, si2siA),pi与所有邻居的序号差绝对距离为Oi=(oi1, oi1oiA),则可以得到pi邻居的权为Wi=(wi1, wi2wiA),其具体计算公式为:

      $$ {w_{ij}} = \left\{ \begin{array}{l} \alpha \cdot \frac{{\frac{1}{{{s_{ij}}}}}}{{\sum\limits_{k \in {N_i}} {\frac{1}{{{s_{ik}}}}} }} + \beta \cdot \frac{{\frac{1}{{{o_{ij}}}}}}{{\sum\limits_{k \in {N_i}} {\frac{1}{{{o_{ik}}}}} }}, j \in {N_i}\\ 0, j \notin {N_i} \end{array} \right. $$ (10)

      式中,权的大小与距离和圈序有关,近邻的权比远邻的权大,αβ用来调节总权值的范围,本文中均取为1。引入权的定义后,点集匹配的目标函数仍为式(3),式(4)可以修改为:

      $$ \begin{array}{l} S\left( {P, Q, f} \right) = \sum\limits_{m = 1}^M {\sum\limits_{i \in {N_m}} {{w_{mi}} \cdot {w_{f\left( m \right)f(i)}}} } + \\ \;\;\;\;\;\;\;\;\;\sum\limits_{n = 1}^N {\sum\limits_{j \in {N_n}} {{w_{{f^{-1}}\left( n \right){f^{-1}}(j)}} \cdot {w_{nj}}} } \end{array} $$ (11)

      令相容性系数为:

      $$ {R_{kl}}\left( {{q_i}, {q_j}} \right) = {w_{ij}} \cdot {w_{kl}} $$ (12)

      式中,当pkqi是匹配点对(相当于用qi去标记pk)时,plqj也是匹配点对。Rkl (qi, qj)越大,表明点对(pkpl)与点对(qiqj)共存的相容性越大;Rkl (qi, qj)越小,表明其共存的相容性越小。这个特性满足松弛标记法对相容性系数的要求,同时也考虑了邻居距离远近以及圈序的影响,更具鲁棒性。

      由于松弛标记法只能收敛到局部最优值,因此初值的选取十分重要。形状上下文是一个描述能力很强的全局形状描述子,有着很好的匹配代价定义,因此可以利用它来初始化匹配概率。根据式(2)计算得到的Cij,通过Gibbs分布将该代价转化为初始匹配概率:

      $$ {M_k}^{(0)}({q_i}) = {{\rm{e}}^{-{C_{ki}}/{T_{{\rm{init}}}}}} $$ (13)

      式中,参数Tinit将匹配概率调整到一个合适的范围内,本次实验中取值为0.2;Mk(0) (λi)为初始概率矩阵M的第k行第i列元素,表示pkqi的匹配概率。根据初始概率矩阵,通过式(9)计算支持函数S,进而通过式(8)更新概率矩阵M并归一化,直到迭代结束,得到最终的匹配结果。

    • 对于一同名实体,设它在较大比例尺RP下的表达为P,在较小比例尺RQ下的表达为Q,任一中间比例尺RC下的表达为C。通过形状上下文完成点集匹配后,假设P中的一个点的子集Psub(i)对应Q中一个点的子集Qsub(j),则有$P = \sum\limits_i {{P_{{\rm{sub}}\left(i \right)}}} $,$Q = \sum\limits_j {{Q_{{\rm{sub}}\left(j \right)}}} $。令f1f2分别表示定义域[0, 1]到Psub(i)Qsub(j)的连续函数, f表示形状内插之后中间状态的连续函数,对应的子集为Csub(k),则有:

      $$ f = \left( {1-g} \right){\rm{ }}{f_1} + g\;{f_2}, 0 \le g \le 1 $$ (14)

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

      $$ g = \left( {\frac{1}{{{R_C}}}-\frac{1}{{{R_P}}}} \right)/\left( {\frac{1}{{{R_Q}}}-\frac{1}{{{R_P}}}} \right) $$ (15)

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

      $$ C = \sum\limits_k {{C_{{\rm{sub}}(k)}}} $$ (16)
    • 采用实验来验证本文方法的可行性和有效性。实验数据如图 2所示,图 2(a)为大比例尺1:10 000下的表达,表达较为详细,弯曲结构较多。图 2(b)为小比例尺1:50 000下的表达,表达较为概略,由大比例尺数据综合得到,包括了弯曲的删除、典型化和夸大操作(分别对应图 2(c)中的Ⅰ、Ⅱ、Ⅲ区域)。两者形态上有差异,但是整体结构和邻域结构类似,这也是本文方法的出发点。同时引入文献[15]中线性插值匹配方法以及单纯基于形状上下文的方法进行对比实验。为定量化评价匹配结果,采用文献[5]中的加权位移矢量为指标,其值越小,说明匹配结果越好,Morphing变换效果也越好。

      图  2  实验数据和匹配结果

      Figure 2.  Experimental Data and Matching Results

      采用3种方法的匹配结果如图 2(d)~2(f)所示。考虑到图上的点较多,匹配线过于密集,这里选择隔5个点连一条线。图 2(d)为线性插值后的匹配结果,其加权位矢为308.97,图 2(e)为单纯基于形状上下文方法的匹配结果,其加权位矢为179.65,从整体结构简单的线性插值有了很大的改进。图 2(f)为顾及邻域结构的匹配结果,加权位矢为164.33,进一步提高了匹配的精度。

    • 基于§2.1实验的匹配结果,进行形状内插。其中g=0和g=1分别表示线状要素在大比例尺RP下和小比例尺RQ下的表达。实验中,分别设置g=0.2、0.4、0.6、0.8共4个不同的尺度进行形状内插。依据式(15),g与中间比例尺RC的关系为RC= (1-g) ×RP+g×RQ。GIS空间数据的精度主要包括属性精度和位置精度,为了验证顾及邻域结构可以提高Morphing的位置精度,将所有Morphing的中间状态和原图叠加(图 3(a)~3(c)),可以清楚看到Morphing的变化过程。同时放大图中的局部区域Ⅳ,结果很显然,位置精度得到很大的提升。从图 3(e)图 3(f)绿线框部分可以看出,在局部上,本文的方法优于单纯形状上下文的方法。

      图  3  效果叠加图和局部放大图

      Figure 3.  Overlaps of the Results and Close-Up of Region IV

    • 本文提出一种顾及邻域结构的线状要素Morphing方法,该方法将形状上下文和松弛标记法结合起来改进点集之间的匹配。依据形状上下文建立的初始匹配概率能够很好地顾及到要素的上下文信息。同时在松弛标记过程中,通过迭代基于邻域结构的支持函数来逐步更新匹配概率,邻域结构得到很好的保留。点集间的匹配关系建立之后,通过常规线性插值方法可以快速实现图形的Morphing变换。实验结果表明,该方法能够很好地顾及全局上下文信息以及局部邻域信息,提高了Morphing的精度。当然,在松弛标记过程中,相容性系数的设定后期还需做更多的对比实验,以期取得更好的匹配结果。

参考文献 (17)

目录

    /

    返回文章
    返回