留言板

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

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

一种利用多维目标分割比的矢量图形匹配算法

邹静 陈永刚 龚金琪 董万虎 孙燕飞 王志林

邹静, 陈永刚, 龚金琪, 董万虎, 孙燕飞, 王志林. 一种利用多维目标分割比的矢量图形匹配算法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(10): 1626-1632. doi: 10.13203/j.whugis20190009
引用本文: 邹静, 陈永刚, 龚金琪, 董万虎, 孙燕飞, 王志林. 一种利用多维目标分割比的矢量图形匹配算法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(10): 1626-1632. doi: 10.13203/j.whugis20190009
ZOU Jing, CHEN Yonggang, GONG Jinqi, DONG Wanhu, SUN Yanfei, WANG Zhilin. An Efficient Matching Algorithm Based on Vector Graphics Using Multi-dimensional Object Segmentation Ratio[J]. Geomatics and Information Science of Wuhan University, 2020, 45(10): 1626-1632. doi: 10.13203/j.whugis20190009
Citation: ZOU Jing, CHEN Yonggang, GONG Jinqi, DONG Wanhu, SUN Yanfei, WANG Zhilin. An Efficient Matching Algorithm Based on Vector Graphics Using Multi-dimensional Object Segmentation Ratio[J]. Geomatics and Information Science of Wuhan University, 2020, 45(10): 1626-1632. doi: 10.13203/j.whugis20190009

一种利用多维目标分割比的矢量图形匹配算法

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

浙江省自然科学基金 LY16D010009

详细信息
    作者简介:

    邹静, 硕士生, 主要从事森林资源遥感监测与信息技术研究。zou_jane@163.com

    通讯作者: 陈永刚, 博士, 副教授。cyg_gis@163.com
  • 中图分类号: P208

An Efficient Matching Algorithm Based on Vector Graphics Using Multi-dimensional Object Segmentation Ratio

Funds: 

The Natural Science Foundation of Zhejiang Province LY16D010009

More Information
    Author Bio:

    ZOU Jing, postgraduate, specializes in the remote sensing monitoring and information technology of forest resources. E-mail: zou_jane@163.com

    Corresponding author: CHEN Yonggang, PhD, associate professor. E-mail: cyg_gis@163.com
图(7) / 表(1)
计量
  • 文章访问数:  814
  • HTML全文浏览量:  170
  • PDF下载量:  68
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-04-09
  • 刊出日期:  2020-10-05

一种利用多维目标分割比的矢量图形匹配算法

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

    浙江省自然科学基金 LY16D010009

    作者简介:

    邹静, 硕士生, 主要从事森林资源遥感监测与信息技术研究。zou_jane@163.com

    通讯作者: 陈永刚, 博士, 副教授。cyg_gis@163.com
  • 中图分类号: P208

摘要: 图形的旋转、缩放、平移(rotate, scaling, translation, RST)以及边界微形变是影响矢量图形匹配结果的主要因素, 也是评价形状描述算法优良的标准。针对以上因素, 提出了一种多维目标分割比的矢量图形匹配算法。该算法通过对矢量图形构建特征线的方式实现形状特征的提取, 准确描述面目标要素的形状特征, 度量要素间的形状相似性。以2 000个真实地理实体的矢量图形作为匹配标准库, 随机选取半数图形作为待匹配图形, 对其采取不同程度的RST变换和边界简化, 然后与标准库做匹配试验, 并与其他图形匹配算法进行对比。试验结果表明, 所提出的算法具有更高的匹配准确率, 具有RST不变性和形变鲁棒性, 可以精准识别矢量图形的形状。

English Abstract

邹静, 陈永刚, 龚金琪, 董万虎, 孙燕飞, 王志林. 一种利用多维目标分割比的矢量图形匹配算法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(10): 1626-1632. doi: 10.13203/j.whugis20190009
引用本文: 邹静, 陈永刚, 龚金琪, 董万虎, 孙燕飞, 王志林. 一种利用多维目标分割比的矢量图形匹配算法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(10): 1626-1632. doi: 10.13203/j.whugis20190009
ZOU Jing, CHEN Yonggang, GONG Jinqi, DONG Wanhu, SUN Yanfei, WANG Zhilin. An Efficient Matching Algorithm Based on Vector Graphics Using Multi-dimensional Object Segmentation Ratio[J]. Geomatics and Information Science of Wuhan University, 2020, 45(10): 1626-1632. doi: 10.13203/j.whugis20190009
Citation: ZOU Jing, CHEN Yonggang, GONG Jinqi, DONG Wanhu, SUN Yanfei, WANG Zhilin. An Efficient Matching Algorithm Based on Vector Graphics Using Multi-dimensional Object Segmentation Ratio[J]. Geomatics and Information Science of Wuhan University, 2020, 45(10): 1626-1632. doi: 10.13203/j.whugis20190009
  • 形状匹配是指按照一定的准则来衡量两个图形是否相同或相似[1], 被广泛应用于图像检索、字符识别、地图斑块边界识别等领域。而地理空间矢量图形要素的形状匹配不仅能够对多源数据集进行空间集成、融合和定期更新, 还有利于维持空间数据库的完整性和现势性。

    地理空间矢量图形要素的形状匹配主要基于其包含的空间特征信息, 分别是空间关系特征、语义特征和几何特征[2]。空间关系特征匹配方法主要是拓扑关系匹配, 然而当目标形状发生旋转、缩放、平移(rotate, scaling, translation, RST)以及边界微形变时, 要素间有效的拓扑关系特征减少会导致匹配失败[3]。语义特征匹配通常根据目标的属性、数据模型等信息进行匹配, 当属性信息不唯一或数据模型不一致时, 会加大匹配难度, 降低匹配精度[4]。几何特征匹配是通过直接计算目标间几何相似度来进行匹配[5], 更适合用于要素的形状匹配[6]。根据几何对象的类型不同, 几何特征匹配可分为点目标匹配、线目标匹配以及面目标匹配。而面目标的识别、匹配是多元矢量图形匹配的重要内容, 同时也是多源矢量数据融合的难点。

    常用的面目标几何特征匹配算法主要分为基于变换域特征、基于空间域特征和基于统计特征3种。基于变换域特征的有联合不变矩[7]、傅里叶描述子[8]和小波描述子[9]等, 此类方法具有RST不变性, 但对形状的形变比较敏感[10]。基于空间域特征的有面积重叠度[11]、Hausdorff距离[12]和中心距离描述[13]等, 此类方法受RST变换影响较大。基于统计特征的有成对几何直方图[14]、形状上下文[15]、CALI(cloud-aerosol LiDAR)[16]、孔洞方向约束[17]等, 此类方法具有RST不变性, 同时对微形变不敏感, 但是其对于相似形状不能精确识别。

    本文针对现有面目标几何特征匹配算法的缺陷, 提出一种多维目标分割比算法来度量图形间的形状相似程度, 该算法通过对矢量图形构建特征线的方式实现形状特征的提取, 不仅克服了RST变换的影响, 同时在微形变图形的识别方面具有鲁棒性。

    • 形状描述子的提取在形状匹配过程中具有极其关键的作用[18], 本文在综合考虑多边形RST不变特性的基础上, 通过多边形和以其最大质边距为半径的外圆将特征线进行分割, 以分割线长度比组成的多维向量作为形状描述子。算法流程如图 1所示。

      图  1  算法流程图

      Figure 1.  Flow Chart of Algorithm

    • 张显全等[19]证明了质心和长轴端点具有RST不变性, 因此由多边形几何属性可知, 质心到边界点的最长线相对于图形位置具有RST不变性, 其长度(最大质边距)始终按RST比例变化。将质心到边界点最长线的综合方向作为形状描述的起始方向, 确保图形产生的形状描述子唯一, 避免因源目标与待匹配目标的起始位置不同而影响匹配结果。

      设多边形的质心为O, 多边形边界线上的点为${M_i}\left( {i = 1, 2 \ldots m} \right)$, 以O为原点, 分别连接OMi得到质边向量$\mathit{\boldsymbol{O}}{\mathit{\boldsymbol{M}}_i}\left( {i = 1, 2 \ldots m} \right)$, 将向量模长$\left| {O{M_i}} \right|$最大值设为最大质边距Dmax, 以O为圆心、Dmax为半径作最大质边圆R。当仅存在一条最大模长的质边向量时, 将该质边向量作为起始特征向量OP, 如图 2 (a)所示。当存在多条最大模长的质边向量时, 对这些向量进行求和得到起始方向, 并延伸至Dmax长度作为特征向量OP, 如图 2 (b)所示。根据多边形质心几何分布关系, 存在质心位于多边形外部的情况, 恒定起始方向按同样的方式选取, 如图 2 (c)2(d)所示。

      图  2  恒定起始方向的选取

      Figure 2.  Selection of Constant Starting Direction

    • 通过划分特征线来提取图形的特征信息, 能够提高匹配结果的鲁棒性。特征线划分需要确定单元划分的份数n, 以OP作为起始向量, 以O为原点按逆时针方向旋转, 每隔360°/n做一条特征线。其与R的交点设为${Q_i}\left( {i = 1, 2 \ldots n} \right)$, 与多边形的交点设为特征点${N_i}\left( {i = 1, 2 \ldots n} \right)$。特征线划分如图 3所示。

      图  3  特征线划分

      Figure 3.  Division of Characteristic Lines

      在特征线划分过程中, 当质心位于多边形外部时存在两种特殊情况:一是部分特征线与多边形不相交; 二是特征线与多边形交点有多个。当特征线与多边形不相交时, 取特征线反向交于多边形最近点为特征点。当特征线与多边形相交于多个点时, 取特征线与多边形相交时最远点为特征点。图 4给出了质心在多边形外部时的特征点选取示意图。

      图  4  质心在多边形外部时的特征点选取

      Figure 4.  Characteristic Points Selection when the Centroid is Outside the Polygon

    • 从起始特征线开始按逆时针方向, 分别将ONi的距离记为${d_i}\left( {i = 1, 2 \ldots n} \right)$, 反向取特征点情况下取其距离的负值, 另外OQi的距离等于Dmax。因此, 目标分割比可表示为:

      $$ {S_i} = \frac{{{d_i}}}{{{D_{{\rm{max}}}}}}{\rm{}}\left( {i = 1, 2 \ldots n} \right) $$ (1)

      设多边形按照伸缩系数k进行缩放, 则变换后${d_i}{\rm{'}} = k{d_i}\left( {i = 1, 2 \ldots n} \right)$, ${D_{{\rm{max}}}}{\rm{'}} = k{D_{{\rm{max}}}}$, 由定义可得构建的目标分割比相同, 具有缩放不变性。即:

      $$ {S_i}{\rm{'}} = \frac{{{d_i}{\rm{'}}}}{{{D_{{\rm{max}}}}{\rm{'}}}} = \frac{{k{d_i}}}{{k{D_{{\rm{max}}}}}} = \frac{{{d_i}}}{{{D_{{\rm{max}}}}}}\\(k > 0, i = 1, 2 \ldots n) $$ (2)

      将多边形每个特征线对应的长度分割比组合成一个多维向量, 向量的维数等于特征线的数目。这个多维特征向量即为构建的形状特征描述子。几何目标分割比向量的具体构建过程可定义为:

      $$ \mathit{\boldsymbol{U}} = \left[ {{S_1}, {S_2} \ldots {S_n}} \right] $$ (3)
    • 图形形状的相似程度通常用一个数值来表示, 这个数值称为形状相似度。形状相似度的值越大, 说明两个形状越相似。本文采用余弦距离来比较多边形形状的相似度。余弦距离也称为余弦相似度, 其定义为向量空间中两个向量夹角的余弦值。通常用向量的余弦相似度作为衡量两个向量间差异大小的度量[20], 这里的向量可以为特征空间向量, 也可为多维矢量空间。

      由于每个多边形均可产生对应的多维分割比向量, 而计算向量间夹角的余弦值即可度量两者的相似性。当两向量的余弦值越接近于1时, 两个图形越相似。设两个待匹配多边形的多维分割比向量分别为${\mathit{\boldsymbol{U}}_1}\left( {{x_1}, {x_2} \ldots {x_n}} \right)$和${\mathit{\boldsymbol{U}}_2}\left( {{y_1}, {y_2} \ldots {y_n}} \right)$。其形状相似度${\alpha _i}$可表示为:

      $$ {\alpha _i} = \frac{{{\mathit{\boldsymbol{U}}_1} \cdot {\mathit{\boldsymbol{U}}_2}}}{{\left| {{\mathit{\boldsymbol{U}}_1}} \right| \cdot \left| {{\mathit{\boldsymbol{U}}_2}} \right|}} $$ (4)

      其具体形式如下:

      $$ {\alpha _i} = \\{\rm{}}\frac{{{x_1}{y_1} + {x_2}{y_2} + \cdots + {x_n}{y_n}}}{{\sqrt {{x_1}^2 + {x_2}^2 + \cdots + {x_n}^2} \cdot \sqrt {{y_1}^2 + {y_2}^2 + \cdots + {y_n}^2} }} $$ (5)
    • 本文采用浙江省某地区林地、宜林地与非林地矢量数据为图形库进行实验。图库多边形为2 000个, 为避免图形选取数量过少造成的匹配结果可信度不高的情况, 从图形库中随机选取1 000个试验所需的待匹配矢量图形, 剩下的1 000个图形作为匹配干扰图形。图形库如图 5(a)所示, 其中带条纹图案标记的多边形代表随机选取的1 000个待匹配图形, 无图案标记的多边形为干扰多边形。图 5(b)中列举了图形库中部分具有相似性的图形和不规则图形。

      图  5  实验图形

      Figure 5.  Experimental Polygons

      图 5中可以看出, 图库多边形数量较多, 并且涵盖相似多边形和极度不规则多边形, 能够满足形状匹配对形状的相似性、多样性和复杂性要求。采用现实世界真实地理实体多边形为图形库, 能更好地验证本文算法的有效性。因此, 该图库适合用于形状特征匹配试验。

    • 为了检验本文算法对形状形变的鲁棒性, 需要将待匹配图形均进行形状简化, 在保留图形关键结点的情况下, 模拟图形产生边界形变的情况。由于矢量数据具有较高的复杂性, 目前研究出了较多具有代表性的压缩方法, 本文采用效果较好的道格拉斯-普克算法。道格拉斯-普克算法是矢量曲线压缩的经典算法, 它从整体角度对曲线进行压缩, 该算法能够得到最优的压缩结果[21]

      利用道格拉斯-普克算法对待匹配的多边形进行简化, 需要较大程度减少面积、周长和边界点数目。待匹配的矢量图形中, 面积范围在720.61~204 278.16 m2, 平均面积为32 406.61 m2, 周长范围在124.76~2 594.63 m, 平均周长为858.26 m。为了确保图形的简化效果, 对待匹配的矢量图形进行0~120 m阈值的简化试验, 间隔2 m产生一组简化图形。经比较, 与平均面积相近的图形在26 m阈值之前简化效果明显, 与平均周长相近的图形在32 m阈值之前简化效果明显。故选取8 m、16 m、24 m、32 m、40 m作为简化阈值, 生成5组不同简化程度的待匹配矢量图形, 简化效果如图 6所示。在简化阈值为40 m时, 1 000个原始待匹配多边形共计减少的面积、周长和边界点数分别为523 013.04 m2、51 573.71 m和30 889个。

      图  6  图形边界简化效果

      Figure 6.  Simplification Effect of Shape Boundary

      为了验证本文算法对RST变换的适应性, 本试验首先将选取的每个待匹配矢量图形分别缩放1.3倍和0.5倍, 得到两个缩放后的图形。然后对原始图形和两个缩放图形分别旋转72°、144°、216°、288°、360°, 并进行平移操作, 共得到15个变换后的图形。图形的平移程度是按旋转角度大小进行定义, 即图形旋转时以小组多边形为中心进行旋转, 旋转后小组内每个多边形会有一个平移度。经过上述变换后按照缩放倍数和旋转角度可分为15组, 对不同简化阈值的6组图形进行RST变换共计得到90组, 每组1 000个待匹配矢量图形。

      经测试, 当特征线划分单元份数n在8以上时, 分割比算法的匹配准确率逐渐趋于平稳, 如图 7所示。因此, 特征线划分单元的角度应取小于45°才能达到准确的效果。

      图  7  特征线划分份数与匹配率关系

      Figure 7.  The Relation Between the Number of Characteristic Line and Matching Results

      试验具体过程如下:分别计算每个待匹配图形与标准图库中多边形的相似度值, 将相似度值按降序排序, 并取相似度值最大的图库多边形作为待匹配图形的匹配结果。汇总匹配正确的数量占待匹配图形总数量的比重作为匹配结果的匹配准确率。

    • 表 1列出了联合不变矩算法[7]、中心距离法[13]、CALI算法[16]与分割比算法在不同简化阈值下的匹配率对比结果。分割比算法采用6个常用角度进行单元划分得到不同匹配结果, 分别是45°、30°、15°、10°、5°和3°。由于以上算法都具有RST不变性, 相同简化阈值下不同RST变换的15组待匹配矢量图形得到的匹配率相近, 因此取其均值作为该简化阈值下的最终匹配率。

      表 1  算法的形状匹配结果/%

      Table 1.  Shape Matching Results of the Algorithm/%

      算法 简化阈值
      0 m 8 m 16 m 24 m 32 m 40 m
      联合不变矩 76.5 0.6 0.1 0.2 0.0 0.1
      中心距离 100.0 74.3 44.7 27.3 17.6 11.4
      CALI 100.0 78.3 46.6 29.2 20.4 16.0
      45°分割比 100.0 80.9 54.8 33.1 24.4 16.0
      30°分割比 100.0 85.7 63.2 42.6 30.0 21.1
      15°分割比 100.0 87.8 66.7 49.3 35.0 25.3
      10°分割比 100.0 88.4 67.9 49.5 35.6 25.3
      5°分割比 100.0 89.0 69.7 50.9 36.6 25.9
      3°分割比 100.0 89.2 69.9 50.6 36.7 26.2

      表 1的形状匹配结果中可以看出, 分割比形状匹配算法可以精准地识别矢量图形的形状, 同时针对图形的简化形变情况具有较好的鲁棒性。在待匹配图形未简化的情况下分割比算法匹配结果与中心距离法和CALI算法相当, 匹配准确率达到100%。对比不同简化阈值下的匹配率, 由于多边形边界点数量减少引起形变, 其匹配准确率与简化阈值呈负相关趋势, 然而分割比算法的匹配结果在相同简化阈值下都高于其他算法。以45°划分单元的分割比算法匹配率略高于其他3种算法中效果最好的CALI算法, 但是随着划分度数的减少, 分割比算法能够得到更准确的匹配结果。这是由于单元度数划分的越小, 算法对原图形信息的描述越详细, 准确率越高。但更高维度的划分会增加分割比计算与匹配的时间, 需要针对不同的应用需求权衡确定。

    • 本文在深入分析矢量面图形几何变换特性的基础上, 提出了一种构建多维目标分割比的矢量图形匹配算法。该算法利用了分割线长度比具有RST不变性的特点, 克服了图形RST变换等因素对匹配结果的影响, 以描述几何形状的复杂性。并将其应用到真实地物的几何面目标的识别与匹配试验中, 试验结果表明, 本文方法在矢量图形经过道格拉斯-普克算法简化和RST变换后仍具有较高的形状匹配准确率, 说明本文方法对于矢量图形匹配是行之有效的。该方法不受RST变换影响, 同时能够克服图形形变的影响, 对于移除边界点导致的图形形变具有较好的鲁棒性, 可以应用于现实中真实地物的图形匹配中。

参考文献 (21)

目录

    /

    返回文章
    返回