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

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

田泽宇, 门朝光, 刘咏梅, 蒋庆丰, 汤亚楠. 一种应用三角形划分的空间对象形状匹配方法[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

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

基金项目: 

国家自然科学基金 61672181

详细信息
    作者简介:

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

    通讯作者:

    门朝光, 博士, 教授。E-mail:menchaoguang@hrbeu.edu.cn

  • 中图分类号: P407;P208

A Spatial Object Shape Matching Method Based on Triangular Division

Funds: 

The National Natural Science Foundation of China 61672181

More Information
  • 摘要: 为解决现有空间对象形状相似性匹配准确率较低的问题,提出一种应用三角形划分的形状相似性匹配方法。该方法按形状主方向对面状空间对象进行分割,按串联、并联和组合形式对空间对象进行三角形划分,准确描述面状空间对象的形状特征,度量空间对象间的形状相似性。通过形状数据集匹配、不同年份面状水系图层匹配和矢量地图草图检索,测试本方法的形状检索性能,并和其他空间对象形状匹配方法进行对比。实验结果表明,本方法具有更高的形状检索准确率。三角形划分形状匹配方法具有平移、旋转、尺度不变性和较强的形状描述识别能力。
    Abstract: Existing spatial object shape similarity matching methods are not accurates. To solve this problem, a spatial object shape matching method based on triangular division is proposed. This method segments the areal spatial object through the main direction of the object shape and divides the object shape into triangles into a series form, parallel connection form, and combined form. This method describes the shape features of the areal spatial object exactly and measures the shape similarity of spatial objects. The matching on the shape data set, the matching on areal water in different years and sketch retrieval on a vector map are used to test the retrieval performance of this method. This method is compared to other spatial object shape matching methods. Experimental results show that this method has higher retrieval accuracy. The spatial object shape matching method based on triangular division is invariant to translation, rotation, scaling, and has a strong capacirty to describe and recognize shapes.
  • 空间对象形状相似性匹配是空间数据几何相似性查询、空间聚类、空间数据融合更新、遥感影像目标识别等的理论基础。空间对象形状相似性匹配有基于空间域和基于变换域两类方法。基于空间域的形状匹配主要有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
    下载: 导出CSV 
    | 显示表格
    图  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
    下载: 导出CSV 
    | 显示表格

    以清华大学校园地图为实验数据,通过程序提供的绘图功能,绘制要查询的建筑的形状,对本文三角形划分形状匹配法进行测试,如图 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

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

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

  • 图  1   形状主方向分割

    Figure  1.   Main Direction Segmentation of the Shape

    图  2   空间对象的计算单元

    Figure  2.   Computing Unit of the Spatial Object

    图  3   基本三角形划分

    Figure  3.   Division Method of the Basic Triangle

    图  4   串联形式

    Figure  4.   Series Form

    图  5   并联形式

    Figure  5.   Parallel Connection Form

    图  6   组合形式

    Figure  6.   Combined Form

    图  7   面状形状数据集

    Figure  7.   Areal Shape Data Set

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

    Figure  8.   Retrieval Results on the Areal Shape Data Set

    图  9   绘制建筑物草图

    Figure  9.   Drawing the Sketch of Buildings

    图  10   草图查询结果

    Figure  10.   Query Results of the Sketch

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV
  • [1] 邓敏, 钮沭联, 李志林. GIS空间目标的广义Hausdorff距离模型[J].武汉大学学报·信息科学版, 2007, 32(7): 641-645 http://ch.whu.edu.cn/CN/abstract/abstract1938.shtml

    Deng Min, Niu Shulian, Li Zhilin. A Generalized Hausdorff Distance for Spatial Objects in GIS[J].Geomatics and Information Science of Wuhan University, 2007, 32(7): 641-645 http://ch.whu.edu.cn/CN/abstract/abstract1938.shtml

    [2] 刘鹏程, 艾廷华, 胡晋山, 等.基于原型模板形状匹配的建筑多边形化简[J].武汉大学学报·信息科学版, 2010, 35(11): 1369-1372 http://ch.whu.edu.cn/CN/abstract/abstract1117.shtml

    Liu Pengcheng, Ai Tinghua, Hu Jinshan, et al.Building-polygon Simplification Based on Shape Matching of Prototype Template[J]. Geomatics and Information Science of Wuhan University, 2010, 35(11): 1369-1372 http://ch.whu.edu.cn/CN/abstract/abstract1117.shtml

    [3] 郝燕玲, 唐文静, 赵玉新, 等.基于空间相似性的面实体匹配算法研究[J].测绘学报, 2008, 37(4): 501-506 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB200804019.htm

    Hao Yanling, Tang Wenjing, Zhao Yuxin, et al. Areal Feature Matching Algorithm Based on Spatial Similarity[J].Acta Geodaetica et Cartographica Sinica, 2008, 37(4): 501-506 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB200804019.htm

    [4] 杨春成, 何列松, 谢鹏, 等.顾及距离与形状相似性的面状地理实体聚类[J].武汉大学学报·信息科学版, 2009, 34(3): 335-338 http://ch.whu.edu.cn/CN/abstract/abstract1205.shtml

    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 http://ch.whu.edu.cn/CN/abstract/abstract1205.shtml

    [5] 王新生, 何津, 叶晓雷, 等.图的谱方法的空间目标形状表达研究[J].武汉大学学报·信息科学版, 2012, 37(11): 1281-1284 http://ch.whu.edu.cn/CN/abstract/abstract380.shtml

    Wang Xinsheng, He Jin, Ye Xiaolei, et al. Representation and Measurement of Shape for Spatial Objects Based on Spectral Method of Graph[J]. Geomatics and Information Science of Wuhan University, 2012, 37(11): 1281-1284 http://ch.whu.edu.cn/CN/abstract/abstract380.shtml

    [6] 汪汇兵, 唐新明, 邱博, 等.运用多算子加权的面要素几何匹配方法[J].武汉大学学报·信息科学版, 2013, 38(10): 1243-1247 http://ch.whu.edu.cn/CN/abstract/abstract2765.shtml

    Wang Huibing, Tang Xinming, Qiu Bo, et al. Geometric Matching Method of Area Feature Based on Multi-weighted Operators[J].Geomatics and Information Science of Wuhan University, 2013, 38(10): 1243-1247 http://ch.whu.edu.cn/CN/abstract/abstract2765.shtml

    [7]

    Fan H, Zipf A, Fu Q, et al. Quality Assessment for Building Footprints Data on OpenStreetMap[J].International Journal of Geographical Information Science, 2014, 28(4): 700-719 doi: 10.1080/13658816.2013.867495

    [8] 帅赟, 艾廷华, 帅海燕, 等.基于形状模板匹配的多边形查询[J].武汉大学学报·信息科学版, 2008, 33(12): 1267-1270 http://ch.whu.edu.cn/CN/abstract/abstract1775.shtml

    Shuai Yun, Ai Tinghua, Shuai Haiyan, et al. Polygonal Inquiry Based on Shape Template Matching[J].Geomatics and Information Science of Wuhan University, 2008, 33(12): 1267-1270 http://ch.whu.edu.cn/CN/abstract/abstract1775.shtml

    [9] 王斌.一种基于多级弦长函数的傅立叶形状描述子[J].计算机学报, 2010, 33(12) : 2387-2396 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201012019.htm

    Wang Bin. A Fourier Shape Descriptor Based on Multi-level Chord Length Function[J].Chinese Journal of Computers, 2010, 33(12) : 2387-2396 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201012019.htm

    [10] 安晓亚, 孙群, 肖强, 等.一种形状多级描述方法及在多尺度空间数据几何相似性度量中的应用[J].测绘学报, 2011, 40(4): 495-508 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201104018.htm

    An Xiaoya, Sun Qun, Xiao Qiang, et al. A Shape Multilevel Description Method and Applicationin Measuring Geometry Similarity of Multi-scale Spatial Data[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(4): 495-508 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201104018.htm

    [11] 安晓亚, 孙群, 杨云, 等.一种利用主动轮廓模型和矢量数据的遥感影像面状水体提取方法[J].武汉大学学报·信息科学版, 2013, 38(10): 1152-1157 http://ch.whu.edu.cn/CN/abstract/abstract2772.shtml

    An Xiaoya, Sun Qun, Yang Yun, et al. A Method for Extracting Area Water Body from Remote Sensing Images Using Active Contour Model and Vector Data[J].Geomatics and Information Science of Wuhan University, 2013, 38(10): 1152-1157 http://ch.whu.edu.cn/CN/abstract/abstract2772.shtml

    [12] 付仲良, 逯跃锋.利用弯曲度半径复函数构建综合面实体相似度模型[J].测绘学报, 2013, 42(1): 145-151 http://xueshu.baidu.com/s?wd=paperuri%3A%281d50680739d322a6f267fa024c0d6a4d%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fkns.cnki.net%2FKCMS%2Fdetail%2Fdetail.aspx%3Ffilename%3Dchxb201301024%26dbname%3DCJFD%26dbcode%3DCJFQ&ie=utf-8&sc_us=6351647540084149547

    Fu Zhongliang, Lu Yuefeng. Establishment of the Comprehensive Model for Similarity of Polygon Entity by Using the Bending Radius Complex Function[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(1): 145-151 http://xueshu.baidu.com/s?wd=paperuri%3A%281d50680739d322a6f267fa024c0d6a4d%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fkns.cnki.net%2FKCMS%2Fdetail%2Fdetail.aspx%3Ffilename%3Dchxb201301024%26dbname%3DCJFD%26dbcode%3DCJFQ&ie=utf-8&sc_us=6351647540084149547

    [13]

    Zunic J, Rosin P L, Kopanja L. On theOrientability of Shapes[J]. IEEE Transactions on Image Processing, 2006, 15(11): 3478-3487 doi: 10.1109/TIP.2006.877527

    [14] 江浩, 褚衍东, 闰浩文, 等.多尺度地理空间线状目标形状相似性的度量[J].测绘科学, 2010, 35(5): 35-38 http://www.cnki.com.cn/Article/CJFDTOTAL-CHKD201005009.htm

    Jiang Hao, Chu Yandong, Yan Haowen, et al. Measurement of Shape Similarity for Linear Objectsin Multi-scale Geographical Space[J]. Science of Surveying and Mapping, 2010, 35(5): 35-38 http://www.cnki.com.cn/Article/CJFDTOTAL-CHKD201005009.htm

    [15]

    Wang Bin, Gao Yongsheng. Hierarchical String Cuts: A Translation, Rotation, Scale, and Mirror Invariant Descriptor for Fast Shape Retrieval[J].IEEE Transactions on Image Processing, 2014, 23(9): 4101-4111 doi: 10.1109/TIP.2014.2343457

  • 期刊类型引用(3)

    1. 闫浩文. 空间相似关系的理论体系与潜在研究方向. 测绘学报. 2023(11): 1962-1973 . 百度学术
    2. 邹静,陈永刚,龚金琪,董万虎,孙燕飞,王志林. 一种利用多维目标分割比的矢量图形匹配算法. 武汉大学学报(信息科学版). 2020(10): 1626-1632 . 百度学术
    3. 李兆兴,翟京生,武芳. 线要素综合的形状相似性评价方法. 武汉大学学报(信息科学版). 2019(12): 1859-1864 . 百度学术

    其他类型引用(4)

图(10)  /  表(2)
计量
  • 文章访问数:  1580
  • HTML全文浏览量:  174
  • PDF下载量:  316
  • 被引次数: 7
出版历程
  • 收稿日期:  2016-06-29
  • 发布日期:  2017-06-04

目录

/

返回文章
返回