留言板

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

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

一种应用三角形划分的空间对象形状匹配方法

田泽宇 门朝光 刘咏梅 蒋庆丰 汤亚楠

田泽宇, 门朝光, 刘咏梅, 蒋庆丰, 汤亚楠. 一种应用三角形划分的空间对象形状匹配方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(6): 749-755. doi: 10.13203/j.whugis20150786
引用本文: 田泽宇, 门朝光, 刘咏梅, 蒋庆丰, 汤亚楠. 一种应用三角形划分的空间对象形状匹配方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(6): 749-755. doi: 10.13203/j.whugis20150786
TIAN Zeyu, MEN Chaoguang, LIU Yongmei, JIANG Qingfeng, TANG Yanan. A Spatial Object Shape Matching Method Based on Triangular Division[J]. Geomatics and Information Science of Wuhan University, 2017, 42(6): 749-755. doi: 10.13203/j.whugis20150786
Citation: TIAN Zeyu, MEN Chaoguang, LIU Yongmei, JIANG Qingfeng, TANG Yanan. A Spatial Object Shape Matching Method Based on Triangular Division[J]. Geomatics and Information Science of Wuhan University, 2017, 42(6): 749-755. doi: 10.13203/j.whugis20150786

一种应用三角形划分的空间对象形状匹配方法

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

国家自然科学基金 61672181

详细信息

A Spatial Object Shape Matching Method Based on Triangular Division

Funds: 

The National Natural Science Foundation of China 61672181

More Information
图(10) / 表(2)
计量
  • 文章访问数:  1007
  • HTML全文浏览量:  62
  • PDF下载量:  307
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-06-30
  • 刊出日期:  2017-06-05

一种应用三角形划分的空间对象形状匹配方法

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

    国家自然科学基金 61672181

    作者简介:

    田泽宇, 博士生, 主要从事空间数据检索、遥感图像处理研究。tianzeyu@hrbeu.edu.cn

    通讯作者: 门朝光, 博士, 教授。E-mail:menchaoguang@hrbeu.edu.cn
  • 中图分类号: P407;P208

摘要: 为解决现有空间对象形状相似性匹配准确率较低的问题,提出一种应用三角形划分的形状相似性匹配方法。该方法按形状主方向对面状空间对象进行分割,按串联、并联和组合形式对空间对象进行三角形划分,准确描述面状空间对象的形状特征,度量空间对象间的形状相似性。通过形状数据集匹配、不同年份面状水系图层匹配和矢量地图草图检索,测试本方法的形状检索性能,并和其他空间对象形状匹配方法进行对比。实验结果表明,本方法具有更高的形状检索准确率。三角形划分形状匹配方法具有平移、旋转、尺度不变性和较强的形状描述识别能力。

English Abstract

田泽宇, 门朝光, 刘咏梅, 蒋庆丰, 汤亚楠. 一种应用三角形划分的空间对象形状匹配方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(6): 749-755. doi: 10.13203/j.whugis20150786
引用本文: 田泽宇, 门朝光, 刘咏梅, 蒋庆丰, 汤亚楠. 一种应用三角形划分的空间对象形状匹配方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(6): 749-755. doi: 10.13203/j.whugis20150786
TIAN Zeyu, MEN Chaoguang, LIU Yongmei, JIANG Qingfeng, TANG Yanan. A Spatial Object Shape Matching Method Based on Triangular Division[J]. Geomatics and Information Science of Wuhan University, 2017, 42(6): 749-755. doi: 10.13203/j.whugis20150786
Citation: TIAN Zeyu, MEN Chaoguang, LIU Yongmei, JIANG Qingfeng, TANG Yanan. A Spatial Object Shape Matching Method Based on Triangular Division[J]. Geomatics and Information Science of Wuhan University, 2017, 42(6): 749-755. doi: 10.13203/j.whugis20150786
  • 空间对象形状相似性匹配是空间数据几何相似性查询、空间聚类、空间数据融合更新、遥感影像目标识别等的理论基础。空间对象形状相似性匹配有基于空间域和基于变换域两类方法。基于空间域的形状匹配主要有Hausdorff距离[1],形状数匹配[2], 中心距离描述[3], 线段链形状相似性[4], 图的谱方法形状表达[5], 正切空间描述[6, 7]等。基于空间域的匹配方法会随形状旋转而发生改变。基于变换域的形状匹配主要有基于位置的傅里叶变换[8]、多级弦长描述[9, 10]、中心距离傅里叶变换[11]、弯曲度半径描述[12]等。基于变换域的匹配方法具有平移、旋转和尺度不变性,但对形状的形变比较敏感。

    针对现有空间对象形状相似性匹配方法的缺陷,通过空间对象的形状主方向分割与三角形划分,本文提出新的面状空间对象形状相似性匹配方法。

    • 面状空间对象的形状主方向由对象的形状决定,它是对象形状的最小惯性轴,具有平移、旋转和尺度不变性,位于通过重心且倾角为θ的直线上,倾角θ公式为[13]

      $$\theta =\text{arctan}\frac{{{\mu }_{02}}-{{\mu }_{20}}+\sqrt{{{\left( {{\mu }_{02}}-{{\mu }_{20}} \right)}^{2}}+4{{u}_{11}}^{2}}}{2{{\mu }_{11}}}$$ (1)

      式中,μ11μ02μ20为空间对象形状的p+q阶中心矩。空间对象形状主方向如图 1所示。

      图  1  形状主方向分割

      Figure 1.  Main Direction Segmentation of the Shape

      主方向与空间对象可能相交于多个点,只取空间对象与主方向的第一个交点和最后一个交点,这两个点间的线段为主方向线段。以空间对象与主方向的第一个交点为起点,分别沿顺时针、逆时针方向顺序遍历空间对象顶点,直到对象与主方向的最后一个交点为止。顺时针方向顶点集合构成的折线与主方向线段构成左侧部分,逆时针方向顶点集合与主方向线段构成右侧部分。主方向线段将空间对象分割为左、右两部分。如图 1所示,主方向与空间对象的第一个交点为v(v′),最后一个交点为v1(v1),线段vv1为主方向线段。点vv1代表主方向与空间对象左侧部分的交点,点v′、v1代表主方向与空间对象右侧部分的交点,此时两部分交点是相同的。将主方向的右侧部分沿主方向平移,直到右侧最小点v'与左侧最大点v1重合,如图 2所示。分布在主方向一侧的连续折线与主方向构成一个计算单元,如图 2中有4个计算单元。对空间对象的计算单元进行三角形划分,度量形状相似性。

      图  2  空间对象的计算单元

      Figure 2.  Computing Unit of the Spatial Object

    • 最简单的空间对象边界折线如图 3中的折线ABC所示,折线ABC与线段AC构成的三角形是空间对象三角形划分的最基本情况。据文献[14],任何三角形的形状、大小均能通过其一条边、该边上的高和该边的对角惟一确定。假设图 3AC=a,高BD=h,∠ABC=α。设SM1SM2为形状描述参量:

      图  3  基本三角形划分

      Figure 3.  Division Method of the Basic Triangle

      $$S{{M}_{1}}\left( ABC,AC \right)=1-\frac{h}{h+a}$$ (2a)
      $$S{{M}_{2}}\left( ABC,\text{ }AC \right)=\frac{\alpha }{{{180}^{\circ }}}$$ (2b)

      SM1描述折线ABC与线段AC之间的偏离率,SM2描述∠ABC相对于线段AC的角度变化率。参量SM1SM2可以准确度量折线ABC与线段AC之间形状的相似性。

      以主方向线段为参考,将空间对象的每个计算单元按串联形式、并联形式和组合形式划分为基本三角形的组合,计算形状描述参量SM1SM2,度量形状相似性。

    • 空间对象边界折线A1A2An被线段A1An分割成了(n-1)/2条折线,分别为折线A1A2A3A3A4A5、…An-2An-1An,如图 4所示。这些折线由线段A1An串联起来,将这类边界折线分布称为串联形式。在串联形式空间对象中计算每个折线与线段的相似关系描述参量SM1SM2,然后将每个线段An-2An占线段A1An的比例作为权重,将每个折线与线段的描述参量按权重相加,得到串联形式空间对象的形状描述参量。

      图  4  串联形式

      Figure 4.  Series Form

      设折线A1A2An的折点A2A4、…An-1到线段A1An的距离,即折线与线段构成三角形的高分别为h2h4hn-1,线段A1A3A3A5、…An-2An的长度分别为a2a4、…an-1。串联形式空间对象中折线A1A2An与线段A1An之间相似关系描述参量即串联形式空间对象的形状描述参量SM1SM2公式为:

      $$\begin{align} & ~S{{M}_{1}}\left( {{A}_{1}}{{A}_{2}}\cdots {{A}_{n}},{{A}_{1}}{{A}_{n}} \right)=\frac{{{a}_{2}}}{{{A}_{1}}{{A}_{n}}}S{{M}_{1}}({{A}_{1}}{{A}_{2}}{{A}_{3}},\text{ }{{A}_{1}}{{A}_{3}})+\frac{{{a}_{4}}}{{{A}_{1}}{{A}_{n}}}S{{M}_{1}}\left( {{A}_{3}}{{A}_{4}}{{A}_{5}},\text{ }{{A}_{3}}{{A}_{5}} \right) \\ & +\cdots +\frac{{{a}_{n-1}}}{{{A}_{1}}{{A}_{n}}} \\ & S{{M}_{1}}\left( {{A}_{n-2}}{{A}_{n-1}}{{A}_{n}},{{A}_{n-2}}{{A}_{n}} \right)~=\frac{{{a}_{2}}}{{{A}_{1}}{{A}_{n}}}\left( 1-\frac{{{h}_{2}}}{{{h}_{2}}+{{a}_{2}}} \right)+\frac{{{a}_{4}}}{{{A}_{1}}{{A}_{n}}}\left( 1-\frac{{{h}_{4}}}{{{h}_{4}}+{{a}_{4}}} \right)+ \\ & \cdots +\frac{{{a}_{n-1}}}{{{A}_{1}}{{A}_{n}}}\left( 1-\frac{{{h}_{n-1}}}{{{h}_{n-1}}+{{a}_{n-1}}} \right) \\ \end{align}$$ (3a)
      $$\begin{align} & S{{M}_{2}}\left( {{A}_{1}}{{A}_{2}}\cdots {{A}_{n}},{{A}_{1}}{{A}_{n}} \right)=\frac{{{a}_{2}}}{{{A}_{1}}{{A}_{n}}}S{{M}_{2}}({{A}_{1}}{{A}_{2}}{{A}_{3}},{{A}_{1}}{{A}_{3}})+\frac{{{a}_{4}}}{{{A}_{1}}{{A}_{n}}}S{{M}_{2}}\left( {{A}_{3}}{{A}_{4}}{{A}_{5}},\text{ }{{A}_{3}}{{A}_{5}} \right) \\ & +\cdots +\frac{{{a}_{n-1}}}{{{A}_{1}}{{A}_{n}}} \\ & S{{M}_{2}}\left( {{A}_{n-2}}{{A}_{n-1}}{{A}_{n}},\text{ }{{A}_{n-2}}{{A}_{n}} \right)=\frac{{{a}_{2}}}{{{A}_{1}}{{A}_{n}}}\frac{\angle {{A}_{2}}}{{{180}^{\circ }}}+\frac{{{a}_{4}}}{{{A}_{1}}{{A}_{n}}}\frac{\angle {{A}_{4}}}{{{180}^{\circ }}}+\cdots +\frac{{{a}_{n-1}}}{{{A}_{1}}{{A}_{n}}}\frac{\angle {{A}_{n-1}}}{{{180}^{\circ }}} \\ \end{align}$$ (3b)
    • 空间对象边界折线A1A2An分布在线段A1An的同一侧,形成多边形A1A2An,如图 5所示。将折点A3A4An-1分别与点A1相连,将多边形A1A2An分割成n-2条折线,分别为A1A2A3A1A3A4A1An-1An,这些折线并列地连接在线段A1An的同一侧,将此类边界折线分布称为并联形式。在并联形式空间对象中计算每个折线与线段的相似关系描述参量SM1SM2,将每个折线与线段的相似关系描述参量分别相乘,得到并联形式空间对象的形状描述参量。

      图  5  并联形式

      Figure 5.  Parallel Connection Form

      设折线A1A2An的折点A2A3、…An-1到线段A1A3A1A4、…A1An的距离即折线与线段构成三角形的高分别为h2h3hn-1,线段A1A3A1A4、…A1An的长度分别为a2a3an-1。并联形式对象中折线A1A2An与线段A1An之间相似关系描述参量即并联形式空间对象的形状描述参量SM1SM2为:

      $$\begin{align} & S{{M}_{1}}\left( {{A}_{1}}{{A}_{2}}\cdots {{A}_{n}},\text{ }{{A}_{1}}{{A}_{n}} \right)=S{{M}_{1}}\left( {{A}_{1}}{{A}_{2}}{{A}_{3}},\text{ }{{A}_{1}}{{A}_{3}} \right)\times S{{M}_{1}}\left( {{A}_{1}}{{A}_{3}}{{A}_{4}},\text{ }{{A}_{1}}{{A}_{4}} \right)\times \cdots \times \\ & \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad S{{M}_{1}}({{A}_{1}}{{A}_{n-1}}{{A}_{n}},{{A}_{1}}{{A}_{n}})= \\ & \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \left( 1-\frac{{{h}_{2}}}{{{h}_{2}}+{{a}_{2}}} \right)\times \left( 1-\frac{{{h}_{4}}}{{{h}_{4}}+{{a}_{4}}} \right)\times \cdots \times \text{ }\left( 1-\frac{{{h}_{n-1}}}{{{h}_{n-1}}+{{a}_{n-1}}} \right) \\ \end{align}$$ (4a)
      $$\begin{align} & S{{M}_{2}}\left( {{A}_{1}}{{A}_{2}}\cdots {{A}_{n}},\text{ }{{A}_{1}}{{A}_{n}} \right)=S{{M}_{2}}\left( {{A}_{1}}{{A}_{2}}{{A}_{3}},\text{ }{{A}_{1}}{{A}_{3}} \right)\times S{{M}_{2}}\left( {{A}_{1}}{{A}_{3}}{{A}_{4}},\text{ }{{A}_{1}}{{A}_{4}} \right)\times \cdots \times \\ & \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad S{{M}_{2}}({{A}_{1}}{{A}_{n-1}}{{A}_{n}},\text{ }{{A}_{1}}{{A}_{n}})= \\ & \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \frac{\angle {{A}_{2}}}{{{180}^{\circ }}}\times \frac{\angle {{A}_{4}}}{{{180}^{\circ }}}\times \cdots \times \frac{\angle {{A}_{n-1}}}{{{180}^{\circ }}} \\ \end{align}$$ (4b)
    • 空间对象边界折线A1A2A7分布在线段A1A7的一侧,且连线A1A4与边A2A3相交,如图 6所示。这种分布形式不能利用上述的串联形式、并联形式计算。

      图  6  组合形式

      Figure 6.  Combined Form

      将端点A1与折点A4A6相连,连线A1A4A2A3相交于n点,连线A1A6A4A5相交于m点,如图 6所示。折线A1A2A3A4与线段A1A4构成串联形式,按式(3a)计算SM1为:

      $$\begin{align} &S{{M}_{1(1)}}=\frac{{{A}_{1}}n}{{{A}_{1}}{{A}_{4}}}S{{M}_{1}}\left( {{A}_{1}}{{A}_{2}}n,{{A}_{1}}n \right)+ \\ &\quad \quad \quad \quad \frac{n{{A}_{4}}}{{{A}_{1}}{{A}_{4}}}S{{M}_{1}}\left( n{{A}_{3}}{{A}_{4}},n{{A}_{4}} \right) \\ \end{align}$$

      折线A1A2A3A4A1A4m构成并联形式,折线A1A4m与线段A1m的参量SM1为:

      $$S{{M}_{1(2)}}=S{{M}_{1(1)}}\times S{{M}_{1}}\left( {{A}_{1}}{{A}_{4}}m,{{A}_{1}}m \right)$$

      折线A1A4A5A6与线段A1A6构成串联形式,按式(3a)计算参量SM1为:

      $$S{{M}_{1(3)}}=\frac{{{A}_{1}}m}{{{A}_{1}}{{A}_{6}}}S{{M}_{1(2)}}+\frac{m{{A}_{6}}}{{{A}_{1}}{{A}_{6}}}S{{M}_{1}}\left( m{{A}_{5}}{{A}_{6}},m{{A}_{6}} \right)$$

      折线A1A4A5A6A1A6A7构成并联形式,折线A1A6A7与线段A1A7的参量SM1为:

      $$S{{M}_{1(4)}}=S{{M}_{1(3)}}\times S{{M}_{1}}\left( {{A}_{1}}{{A}_{6}}{{A}_{7}},{{A}_{1}}{{A}_{7}} \right)$$

      至此,图 6中边界折线A1A2A7与线段A1A7的相似关系描述参量SM1计算完成,参量SM2SM1的计算一致。

      图 6可知,组合形式空间对象的构成是串联、并联、串联……的结构,先利用式(3a)、式(3b)计算串联形式对象的相似关系描述参量,再利用式(4a)、式(4b)计算并联形式对象的相似关系描述参量。以此类推,得出组合形式对象的形状描述参量。

    • 空间对象的计算单元之间为串联形式,计算单元内部为并联形式或组合形式。

      设空间对象共由m个计算单元组成,主方向线段长度为L,每个计算单元与主方向相交线段的长度分别为L1L2Lm,每个计算单元与对应线段的相似关系描述参量分别为SM1(1)SM1(2)SM1(m)SM2(1)SM2(2)SM2(m),则空间对象边界折线与主方向线段的相似关系描述参量即空间对象的形状描述参量SM1SM2为:

      $$\begin{align} &S{{M}_{1}}=\frac{{{L}_{1}}}{2L}S{{M}_{1(1)}}+\frac{{{L}_{2}}}{2L}S{{M}_{1(2)}}+ \\ &\quad \quad \quad \cdots +\frac{{{L}_{m}}}{2L}S{{M}_{1(m)}} \\ \end{align}$$ (5a)
      $$\begin{align} &S{{M}_{2}}=\frac{{{L}_{1}}}{2L}S{{M}_{2(1)}}+\frac{{{L}_{2}}}{2L}S{{M}_{2(2)}}+ \\ &\quad \quad \quad \cdots +\frac{{{L}_{m}}}{2L}S{{M}_{2(m)}} \\ \end{align}$$ (5b)

      图 2中空间对象的4个计算单元之间为串联形式。计算单元1、计算单元2、计算单元3均为基本三角形,按式(2a)、式(2b)计算这3个计算单元的形状描述参量。计算单元4为并联形式,按式(4a)、式(4b)计算该计算单元的形状描述参量。根据4个计算单元的形状描述参量,按式(5a)、式(5b)计算图 2空间对象整体的形状描述参量。

      两个待匹配空间对象vu,对象v的形状描述参量为SM1(v)SM2(v),对象u的形状描述参量为SM1(u)SM2(u),两个对象vu的形状差异度为:

      $$\left\{ \begin{align} &{{d}_{1}}=\left| SM_{1}^{(v)}-SM_{1}^{(u)} \right| \\ &{{d}_{2}}=\left| SM_{2}^{(v)}-SM_{2}^{(u)} \right| \\ \end{align} \right.$$ (6)

      空间对象vu的形状相似性分值S为:

      $$S=\left( 1-{{d}_{1}} \right)\left( 1-{{d}_{2}} \right)$$ (7)

      三角形划分形状匹配算法流程如下。

      输入:待匹配空间对象vu

      输出:对象vu的形状相似性分值S

      第一步 通过式(1),计算空间对象的主方向,确定空间对象的主方向线段;

      第二步 以主方向线段起点为初始点,分别沿顺时针、逆时针方向顺序遍历空间对象顶点,直到主方向线段终点为止,主方向线段将空间对象分割为左、右两部分;

      第三步 确定空间对象左、右两部分的计算单元。计算单元之间为串联形式;

      第四步 以计算单元为单位,依据并联形式或组合形式,进行三角形划分,计算每个计算单元的形状性描述参量;

      第五步 根据式(5a)、式(5b),计算空间对象vu的整体形状描述参量;

      第六步 根据式(6)、式(7),计算空间对象vu的形状相似性分值S

      其中,第一步的时间复杂度为O(N)[13];第二步、第三步的时间复杂度均为O(N);其余各步的时间复杂度均小于O(N),则三角形划分形状匹配法的时间复杂度为O(N)。

      三角形划分形状匹配方法利用折线与线段之间的偏离率SM1和角度变化率SM2描述形状特征,与形状特征点的绝对位置无关,具有平移不变性。本方法的偏离率SM1为三角形高和对应边长度的比,与尺度变化无关;角度变化率SM2也不随尺度而改变,具有尺度不变性。利用形状主方向分割空间对象,形状主方向不随形状旋转而改变,具有旋转不变性。所以,三角形划分形状匹配具有平移、尺度和旋转不变性。

    • 为评估本文提出的三角形划分形状匹配法的检索性能,进行了形状数据集匹配、面状水系图层匹配和草图检索三种测试。

    • 从北京市地图中选取40个不同建筑的面状形状,从我国水系图中选取30个不同水系的面状形状,共70个面状形状,如图 7中上图所示,前三行为30个不同水系的面状形状,后四行为40个不同建筑的面状形状。对每一个面状形状分别缩放0.49、0.7、1.37倍,得到3个缩放后的面状形状,如图 7中的下图第一行从左至右依次是原始面状形状、缩放0.49倍面状形状、缩放0.7倍面状形状、缩放1.37倍面状形状。对原始形状和3个缩放形状分别旋转45°、135°、225°得到12个面状形状,如图 7中的下图第二行、第三行、第四行所示。对原始面状形状进行四种仿射变换,得到4个面状形状,如图 7中的下图第五行所示。对每个面状形状进行19次变换,得到19个面状形状,加上原始面状形状,构成相似面状形状20种形变。70个原始面状形状构成为1 400个面状形状的数据集。

      图  7  面状形状数据集

      Figure 7.  Areal Shape Data Set

      在面状形状数据集上,使用Bulls-eye测试方法[15]对中心距离描述法[3]、正切空间描述法[6]、多级弦长描述法[10]、弯曲度半径描述法[12]与本文三角形划分面状形状匹配法进行测试,检索率如表 1所示。本文三角形划分面状形状匹配法的部分检索结果如图 8所示。

      表 1  面状形状数据集检索率

      Table 1.  Retrieval Accuracy on the Areal Shape Data Set

      空间对象形状描述法平均检索率/%
      中心距离描述法[3]86.41
      正切空间描述法[6]87.96
      多级弦长描述法[10]90.36
      弯曲度半径描述法[12]89.25
      本文形状匹配法96.52

      图  8  面状形状数据集的部分检索结果

      Figure 8.  Retrieval Results on the Areal Shape Data Set

      表 1可以看出,在形状数据集中,本文三角形划分形状匹配法的检索率高于其它4种方法,具有平移、旋转和尺度不变性,对因仿射造成的形状形变具有一定的鲁棒性。图 8中第1列为待检索形状,第2列为检索结果中相似性分值最高的10个形状,其中误匹配被用圆圈标出。从图 8可以看出误匹配形状与待检索形状存在一定程度的相似。

    • 本测试对2010年和2015年的同比例尺世界面状水系图中的实体进行匹配。2010年水系图包含6 646个实体,2015年水系图包含6 636个实体。以2015年数据为待匹配数据,2010年数据为候选匹配数据,对中心距离描述法[3]、正切空间描述法[6]、多级弦长描述法[10]、弯曲度半径描述法[12]与本文三角形划分形状匹配法进行测试。测试结果如表 2所示,n表示匹配结果集中的实体数,r表示匹配结果集中正确的实体数,P为查准率,R为查全率。从表 2可以看出本文形状匹配法具有较高的查全率和查准率。

      表 2  面状水系匹配结果

      Table 2.  Matching Results on the Areal Water

      对象形状描述法nrP/%R/%
      中心距离法[3]6 3355 64089.0384.99
      正切空间法[6]6 3265 82192.0287.72
      多级弦长法[10]6 3646 10995.9992.06
      弯曲度半径法[12]6 3516 02894.9190.84
      本文形状匹配法6 3916 30898.7095.06
    • 以清华大学校园地图为实验数据,通过程序提供的绘图功能,绘制要查询的建筑的形状,对本文三角形划分形状匹配法进行测试,如图 9所示。草图检索实验只取形状相似性分值在0.970 0~1.000 0范围之间的检索结果。将形状相似性分值0.970 0作为最小值,此时形状相似度为0%。将形状相似性分值1.000 0作为最大值,此时形状相似度为100%。三组草图检索实验结果如图 10所示。三组实验均检索出了与草图建筑形状最相似的建筑,本三角形划分形状匹配法可以精准地识别面状空间对象的形状,对形状的轻微形变具有鲁棒性。

      图  9  绘制建筑物草图

      Figure 9.  Drawing the Sketch of Buildings

      图  10  草图查询结果

      Figure 10.  Query Results of the Sketch

    • 本文提出了面状空间对象的三角形划分形状匹配方法。该方法通过空间对象的形状主方向,对空间对象进行分割。按串联、并联和组合形式,对空间对象进行三角形划分,计算空间对象边界闭合折线与主方向线段的相似度,得出面状空间对象的形状描述参量。通过各空间对象的形状描述参量,计算各空间对象间的形状相似性。

      经过形状数据集匹配测试、面状水系图层匹配测试和矢量地图草图检索测试,表明本方法具有较高的形状检索准确率,具有平移、尺度和旋转不变性,对发生形变的形状具有较强的识别能力。三角形划分形状匹配方法可用于目标识别、空间数据几何相似性查询、空间数据融合更新及需要进行形状相似性评估的场景。

参考文献 (15)

目录

    /

    返回文章
    返回