留言板

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

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

利用等距同构建立多尺度空间实体相似性度量模型

徐丰 牛继强 林昊 陈时雨 张兵兵 陈飞燕

徐丰, 牛继强, 林昊, 陈时雨, 张兵兵, 陈飞燕. 利用等距同构建立多尺度空间实体相似性度量模型[J]. 武汉大学学报 ● 信息科学版, 2019, 44(9): 1399-1406. doi: 10.13203/j.whugis20170344
引用本文: 徐丰, 牛继强, 林昊, 陈时雨, 张兵兵, 陈飞燕. 利用等距同构建立多尺度空间实体相似性度量模型[J]. 武汉大学学报 ● 信息科学版, 2019, 44(9): 1399-1406. doi: 10.13203/j.whugis20170344
XU Feng, NIU Jiqiang, LIN Hao, CHEN Shiyu, ZHANG Bingbing, CHEN Feiyan. Establishment of the Similarity Metric Model of Multi-scale Spatial Object Using Isometry[J]. Geomatics and Information Science of Wuhan University, 2019, 44(9): 1399-1406. doi: 10.13203/j.whugis20170344
Citation: XU Feng, NIU Jiqiang, LIN Hao, CHEN Shiyu, ZHANG Bingbing, CHEN Feiyan. Establishment of the Similarity Metric Model of Multi-scale Spatial Object Using Isometry[J]. Geomatics and Information Science of Wuhan University, 2019, 44(9): 1399-1406. doi: 10.13203/j.whugis20170344

利用等距同构建立多尺度空间实体相似性度量模型

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

国家自然科学基金 41671405

国家自然科学基金 41771438

河南省高等学校青年骨干教师资助计划 2016GGJS-099

河南省高等学校重点科研项目 15A170012

详细信息
    作者简介:

    徐丰, 硕士, 副教授, 主要从事空间数据多尺度表达不确定性处理的理论和方法研究。xu-f88@163.com

    通讯作者: 牛继强, 博士, 教授。njq8196@163.com
  • 中图分类号: P208

Establishment of the Similarity Metric Model of Multi-scale Spatial Object Using Isometry

Funds: 

The National Natural Science Foundation of China 41671405

The National Natural Science Foundation of China 41771438

the Youth Core Teachers Funding Scheme of Universities in Henan Province 2016GGJS-099

the Key Research Projects of Universities in Henan Province 15A170012

More Information
    Author Bio:

    XU Feng, master, associate professor, specializes in the theories and methods of the uncertainty of multi-scale space data. E-mail:xu-f88@163.com

    Corresponding author: NIU Jiqiang, PhD, professor. E-mail: njq8196@163.com
图(8) / 表(2)
计量
  • 文章访问数:  1299
  • HTML全文浏览量:  129
  • PDF下载量:  146
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-07-31
  • 刊出日期:  2019-09-05

利用等距同构建立多尺度空间实体相似性度量模型

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

    国家自然科学基金 41671405

    国家自然科学基金 41771438

    河南省高等学校青年骨干教师资助计划 2016GGJS-099

    河南省高等学校重点科研项目 15A170012

    作者简介:

    徐丰, 硕士, 副教授, 主要从事空间数据多尺度表达不确定性处理的理论和方法研究。xu-f88@163.com

    通讯作者: 牛继强, 博士, 教授。njq8196@163.com
  • 中图分类号: P208

摘要: 从度量几何学的观点,建立多尺度空间实体等距同构模型。将多尺度空间实体分别看作刚性图形和弹性图形,利用等距同构不变性的概念,构建多尺度空间实体几何相似性图形距离和拓扑相似性图形距离。通过统一几何和拓扑相似性图形距离,构成一个二元集值距离,作为多尺度空间实体相似性的评价指标。通过对不同复杂性的面状和线状空间实体多尺度表达图形的几何和拓扑相似性度量实验表明,该方法能同时顾及多尺度空间实体几何和拓扑结构的改变,且符合空间实体的多尺度抽象规律。

English Abstract

徐丰, 牛继强, 林昊, 陈时雨, 张兵兵, 陈飞燕. 利用等距同构建立多尺度空间实体相似性度量模型[J]. 武汉大学学报 ● 信息科学版, 2019, 44(9): 1399-1406. doi: 10.13203/j.whugis20170344
引用本文: 徐丰, 牛继强, 林昊, 陈时雨, 张兵兵, 陈飞燕. 利用等距同构建立多尺度空间实体相似性度量模型[J]. 武汉大学学报 ● 信息科学版, 2019, 44(9): 1399-1406. doi: 10.13203/j.whugis20170344
XU Feng, NIU Jiqiang, LIN Hao, CHEN Shiyu, ZHANG Bingbing, CHEN Feiyan. Establishment of the Similarity Metric Model of Multi-scale Spatial Object Using Isometry[J]. Geomatics and Information Science of Wuhan University, 2019, 44(9): 1399-1406. doi: 10.13203/j.whugis20170344
Citation: XU Feng, NIU Jiqiang, LIN Hao, CHEN Shiyu, ZHANG Bingbing, CHEN Feiyan. Establishment of the Similarity Metric Model of Multi-scale Spatial Object Using Isometry[J]. Geomatics and Information Science of Wuhan University, 2019, 44(9): 1399-1406. doi: 10.13203/j.whugis20170344
  • 空间相似性是指两个空间目标场景之间在某一方面或多个方面的相同程度[1],在地图比较、图像识别、土地利用等方面具有广泛的应用。因此,空间相似性建模已成为地理信息科学研究的前沿与热点问题。空间实体的几何图形相似性度量是空间相似性的核心内容[1-2]。在计算机视觉等领域中,学者们分别从刚性图形和弹性图形两个角度构建了图形相似性评价模型[3-7]

    GIS中关于几何图形相似性的度量模型有许多,如分维数、小波等[8-9]。近年来,关于空间实体相似性也取得了一些新的研究进展,如基于傅里叶形状描述子的复杂面几何相似性度量模型[10-11]。但现有的空间相似性研究均是把空间实体当作刚性图形来对待,鲜有学者用弹性图形来研究空间实体的相似性。

    空间数据的多尺度表达是当前GIS中的重要研究内容[12]。本文基于空间实体的几何细节,研究其多尺度变换下几何图形的相似性。几何学中针对图形变换不变性质的研究一般从两方面展开,一是欧氏度量几何学,研究图形刚性变换的不变性[13];二是拓扑学,研究图形弹性运动的不变性[13]。因此,空间实体的多尺度表达既可以看作是独立的刚性图形,也可以看作是同一空间实体的弹性形变。在研究图形刚性变换时用几何形状、大小作为特征变量,研究弹性变换时用拓扑结构作为特征变量。这两种变换都可以用等距同构不变性来形式化描述。

    • 在数学中,用等距同构及ε-等距同构来定义独立度量空间之间的全等性或相似性[3, 14]。在GIS中,空间实体一般是用它的轮廓平面曲线表达的二维几何图形,如线状空间实体是用其中心线或边缘曲线表达的二维曲线(图 1(a))。因此,定义空间实体在不同尺度上的度量空间模型,可以确定它们是否等距同构或者ε-等距同构。

      图  1  空间实体距离度量标准

      Figure 1.  Distance Metric Criterions of Spatial Objects

      在二维欧氏空间E=R2里,设空间实体O在初始尺度$s$及扩展尺度序列$s_i$上的度量空间模型分别为$\left({\mathit{\boldsymbol{X}}, d} \right)$、$\left({{\mathit{\boldsymbol{X}}^i}, {d^i}} \right)$,i=1, 2…n。其中,$\mathit{\boldsymbol{X}}$、${{\mathit{\boldsymbol{X}}^i}}$是E里的二维光滑连通曲线或连通平面的矢量图,$d:\mathit{\boldsymbol{X}} \times \mathit{\boldsymbol{X}} \to {{\bf{R}}^ + }$、${d^i}:{\mathit{\boldsymbol{X}}^i} \times {\mathit{\boldsymbol{X}}^i} \to {{\bf{R}}^ + }$分别是$\mathit{\boldsymbol{X}}$、${{\mathit{\boldsymbol{X}}^i}}$上两点间的距离。如果$d\left({{x_1}, {x_2}} \right) = {d^i}\left({{\psi ^i}\left({{x_1}} \right), {\psi ^i}\left({{x_2}} \right)} \right)$,${x_1}, {x_2} \in \mathit{\boldsymbol{X}}$,那么一一对应的映射${\psi ^i}:\left({\mathit{\boldsymbol{X}}, d} \right) \to \left({{\mathit{\boldsymbol{X}}^i}, {d^i}} \right)$是等距同构的,称$\left({\mathit{\boldsymbol{X}}, d} \right)$和$\left({{\mathit{\boldsymbol{X}}^i}, {d^i}} \right)$等距同构。${\psi ^i}$为空间实体O从初始尺度s到扩展尺度$s_i$的制图综合。

      除等价尺度变换以外,空间实体的多尺度表达是相似的而不是全等的[14]。因此,可用空间实体的ε-等距同构模型来定义其相似性。即如果对于所有${x^i} \in {\mathit{\boldsymbol{X}}^i}$,有:

      $${\rm{dis}}{\psi ^i} = \mathop {{\rm{sup}}}\limits_{{x_1}, {x_2} \in \mathit{\boldsymbol{X}}} \left| {d\left( {{x_1}, {x_2}} \right) - {d^i}\left( {{\psi ^i}\left( {{x_1}} \right), {\psi ^i}\left( {{x_2}} \right)} \right)} \right| \le \varepsilon $$ (1)

      式中,dis是$\mathit{\boldsymbol{X}}$经过${\psi ^i}$作用下距离改变的最大值;sup表示上确界(下同)。那么两个度量空间$\left({\mathit{\boldsymbol{X}}, d} \right)$和$\left({{\mathit{\boldsymbol{X}}^i}, {d^i}} \right)$是ε-等距同构的,也就是说,$\mathit{\boldsymbol{X}}$和${\mathit{\boldsymbol{X}}^i}$是相似的。

      在欧氏度量几何学中,$d$的度量标准为欧氏度量标准(图 1(b)),记为${d_E}\left({{x_1}, {x_2}} \right)$,度量任何点对${x_1}, {x_2} \in \mathit{\boldsymbol{X}}$在E上沿直线的距离,因此用${d_E}$描述$\mathit{\boldsymbol{X}}$、${\mathit{\boldsymbol{X}}^i}$的几何特征,空间实体O在尺度$s$、${s_i}$上基于欧氏度量标准的度量空间模型分别表达为$\left({\mathit{\boldsymbol{X}}, {d_E}} \right)$、$\left({{\mathit{\boldsymbol{X}}^i}, {d_E}} \right)$;在拓扑学中,$d$的度量标准为测地线度量标准(图 1(c)),记为${d_X}\left({{x_1}, {x_2}} \right)$,度量任何点对${x_1}, {x_2} \in \mathit{\boldsymbol{X}}$在$\mathit{\boldsymbol{X}}$上的最短路径,所有连接点${x_1}$和${x_2}$的路径都是依靠连通性的拓扑函数,因此用${d_\mathit{\boldsymbol{X}}}$、$d_{{\mathit{\boldsymbol{X}}^i}}^i$分别描述$\mathit{\boldsymbol{X}}$、${\mathit{\boldsymbol{X}}^i}$的拓扑特征,空间实体O在尺度$s$、${s_i}$上基于测地线度量标准的度量空间模型分别表达为$\left({\mathit{\boldsymbol{X}}, {d_\mathit{\boldsymbol{X}}}} \right)$、$\left({{\mathit{\boldsymbol{X}}^i}, d_{{\mathit{\boldsymbol{X}}^i}}^i} \right)$。

    • 在图形空间M中,任一图形F相当于欧氏空间中的一个点。定义图形空间M上基于等距同构不变性的图形距离${d_F}$为F×FR+作为量化图形相似程度的方法,即在空间实体O的多尺度表达中,$d_F$是两个度量空间模型$\left({\mathit{\boldsymbol{X}}, d} \right)$和$\left({{\mathit{\boldsymbol{X}}^i}, {d^i}} \right)$的函数。${d_F}$应满足度量概念的基本特征:自反性、非负性、对称性及传递性(三角不等式)[8]

    • 空间实体的几何特征用欧氏度量标准描述,因此,度量空间实体多尺度表达几何相似性的等距同构不变图形距离${d_F}$是两度量空间模型$\left({\mathit{\boldsymbol{X}}, {d_E}} \right)$和$\left({{\mathit{\boldsymbol{X}}^i}, {d_E}} \right)$的函数。Hausdorff距离是由直线距离定义的,因此,Hausdorff距离也是多尺度空间实体O的度量空间模型$\left({\mathit{\boldsymbol{X}}, {d_E}} \right)$和$\left({{\mathit{\boldsymbol{X}}^i}, {d_E}} \right)$的函数。

      在空间实体的多尺度表达中,Hausdorff距离的计算公式可表达为:

      $$d_H^E\left( {\mathit{\boldsymbol{X, }}{\mathit{\boldsymbol{X}}^i}} \right) = {\rm{max}}\left\{ {\mathop {{\rm{sup}}}\limits_{x \in \mathit{\boldsymbol{X}}} {d_E}\left( {x, {\mathit{\boldsymbol{X}}^i}} \right), \mathop {{\rm{sup}}}\limits_{{x^i} \in {\mathit{\boldsymbol{X}}^i}} {d_E}\left( {{x^i}, \mathit{\boldsymbol{X}}} \right)} \right\}$$ (2)

      式中,${d_E}\left({x, {\mathit{\boldsymbol{X}}^i}} \right)$表示${\mathit{\boldsymbol{X}}^i}$与X上点x之间的距离;${d_E}\left({{x^i}, X} \right)$表示$\mathit{\boldsymbol{X}}$与${\mathit{\boldsymbol{X}}^i}$上点${x^i}$之间的距离。如果$X$与${\mathit{\boldsymbol{X}}^i}$全等,则存在$f \in {\rm{Iso}}\left(E \right)$(${\rm{Iso}}\left(E \right)$包括旋转、平移和反射变换),使得$d_H^E\left({f\left(\mathit{\boldsymbol{X}} \right), {\mathit{\boldsymbol{X}}^i}} \right) = 0$。同理可以找到$\mathit{\boldsymbol{X}}$与${\mathit{\boldsymbol{X}}^i}$的Hausdorff距离的最小可能值,即:

      $$d_{H - {\rm{min}}}^E\left( {\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right) = \mathop {{\rm{inf}}}\limits_{f \in {\rm{Iso}}\left( E \right)} d_H^E\left( {f\left( \mathit{\boldsymbol{X}} \right), {\mathit{\boldsymbol{X}}^i}} \right)$$ (3)

      因为${\rm{Iso}}\left(E \right)$容易参数化,则Hausdorff距离的最小可能值可用下式进行计算:

      $$d_{H - {\rm{min}}}^E\left( {\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right) = \mathop {{\rm{inf}}}\limits_{\mathit{\boldsymbol{R, t}}} d_H^E\left( {\mathit{\boldsymbol{RX}} + \mathit{\boldsymbol{t}}, {\mathit{\boldsymbol{X}}^i}} \right)$$ (4)

      式中,R表示旋转矩阵;t表示平移矢量;inf表示下确界(下同)。$d_{H - {\rm{min}}}^E$满足等距同构不变图形距离的4个特性,$d_{(H - {\rm{min}})}^E$越小,图形$\mathit{\boldsymbol{X}}$与${\mathit{\boldsymbol{X}}^i}$的几何特征越相似。

    • 空间实体的拓扑特征用测地线度量标准描述,因此,度量空间实体多尺度表达拓扑相似性的等距同构不变图形距离${d_F}$是两度量空间模型$\left({\mathit{\boldsymbol{X}}, {d_X}} \right)$和$\left({{\mathit{\boldsymbol{X}}^i}, d_{{X^i}}^i} \right)$的函数。Gromov-Hausdorff(GH)距离是由最短路径定义的[15],因此,Gromov-Hausdorff距离也是多尺度空间实体O的度量空间模型$\left({\mathit{\boldsymbol{X}}, {d_X}} \right)$和$\left({{\mathit{\boldsymbol{X}}^i}, d_{{X^i}}^i} \right)$的函数。

      在空间实体的多尺度表达中,Gromov-Hausdorff距离的计算过程分为两步,即拓扑等距(同构)嵌入和拓扑相似性图形距离计算。

    • 将$\mathit{\boldsymbol{X}}$的拓扑特征等距(同构)嵌入为欧氏度量空间$\left({E, {d_E}} \right)$中的几何特征,其基本思想是在二维欧氏空间中求出与$\mathit{\boldsymbol{X}}$的离散点对应的点,使这些点间的欧氏距离等于$\mathit{\boldsymbol{X}}$离散点对间的最短路径。这与多维标度算法(classical multidimensional scaling, MDS)的思路是一致的[16-17]。因此,$\mathit{\boldsymbol{X}}$的拓扑特征等距(同构)嵌入到欧氏度量空间采用MDS来实现,具体包括两个关键步骤,一是$\mathit{\boldsymbol{X}}$的离散化,二是MDS的执行。

      $\mathit{\boldsymbol{X}}$(图 2(a))的离散化是在$\mathit{\boldsymbol{X}}$上取样m个点$\hat X$(图 2(b)),组成一个r-覆盖,$\hat X$的坐标可表达为一个$m \times 2$的矩阵${\mathit{\boldsymbol{D}}_\mathit{\boldsymbol{X}}}$。r越小,$\hat X$与图形$\mathit{\boldsymbol{X}}$越接近。对于确定的图形$\mathit{\boldsymbol{X}}$,r理论上存在一个最大值,既能区分图形几何细节,又能保证时间和空间效率。本文在这里不研究r的最优取值问题。

      图  2  拓扑等距同构嵌入实例

      Figure 2.  Example of Isometric Embedding of Topology

      执行MDS算法时(在R软件中完成),先用Dijkstra算法生成$\hat X$上m个点间的最短路径矩阵${\mathit{\boldsymbol{D}}_{\mathit{\boldsymbol{X}} - \hat X}}$,然后将其代入cmdscale函数生成嵌入空间E中一个新的点结构$\varphi \left({\hat X} \right)$(图 2(c)),这m个点之间的直线距离矩阵${\mathit{\boldsymbol{D}}_{E - \varphi \left({\hat X} \right)}}$在某种程度上应尽可能与${\mathit{\boldsymbol{D}}_{\mathit{\boldsymbol{X}} - \hat X}}$的元素接近,如图 2(b)中点95到点318、点301到点307的最短路径分别与图 2(c)中点95到点318、点301到点307的直线距离相等。

      同理,可以生成图形${\mathit{\boldsymbol{X}}^i}$在嵌入空间E中一个新的点结构${\varphi ^i}\left({{\mathit{\boldsymbol{X}}^i}} \right)$。

    • 计算$\varphi \left(\mathit{\boldsymbol{X}} \right)$和${\varphi ^i}\left({{\mathit{\boldsymbol{X}}^i}} \right)$之间的几何相似性图形距离$d_{H - {\rm{min}}}^E\left({\varphi \left(\mathit{\boldsymbol{X}} \right), {\varphi ^i}\left({{\mathit{\boldsymbol{X}}^i}} \right)} \right)$,即为$\mathit{\boldsymbol{X}}$和${\mathit{\boldsymbol{X}}^i}$之间的Gromov-Hausdorff距离:

      $$\begin{array}{*{20}{l}} {{d_{{\rm{GH}}}}\left( {\left( {\mathit{\boldsymbol{X}}, {d_\mathit{\boldsymbol{X}}}} \right), \left( {{\mathit{\boldsymbol{X}}^i}, d_{{\mathit{\boldsymbol{X}}^i}}^i} \right)} \right) = }\\ {\mathop {{\rm{inf}}}\limits_{\begin{array}{*{20}{c}} E\\ {\varphi :\mathit{\boldsymbol{X}} \to E}\\ {{\varphi ^i}:{\mathit{\boldsymbol{X}}^i} \to E} \end{array}} d_{H - {\rm{min}}}^E\left( {\varphi \left( \mathit{\boldsymbol{X}} \right), {\varphi ^i}\left( {{\mathit{\boldsymbol{X}}^i}} \right)} \right)} \end{array}$$ (5)

      ${d_{{\rm{GH}}}}\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)$满足等距同构不变图形距离的4个特性,${d_{{\rm{GH}}}}\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)$越小,图形$\mathit{\boldsymbol{X}}$与${\mathit{\boldsymbol{X}}^i}$的拓扑特征越相似。

    • 因为空间实体多尺度表达的几何和拓扑特征化简是同时发生变化的,将$d_{H - {\rm{min}}}^E\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)$和${d_{{\rm{GH}}}}\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)$组成一个二元组$S\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right) = \left({d_{H - {\rm{min}}}^E\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right), {d_{{\rm{GH}}}}\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)} \right)$来判断空间实体多尺度表达之间的相似程度更完备。$S\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)$表示多尺度图形之间的几何-拓扑相似性图形距离。

      $S\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)$的大小和单一标量目标比较问题不同,不能明确定义$S\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)$的最小值,因为两个标准之间不存在一个完整的规则关系。例如,不能确定$S\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^j}} \right) = \left({100, 50} \right)$或者$S\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right) = \left({50, 50} \right)$谁更相似,i, j=1, 2…n。但$S\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right) = \left({50, 50} \right)$比$S\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)$=(100, 100)更相似是毫无疑问的,因为$S\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)$的两个标准都有更小的值。在空间实体的多尺度表达中,空间实体的几何和拓扑特征同时被抽象化简,其变化趋势从理论上讲是一样的,因此$S\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)$与$S\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^j}} \right)$之间是可以进行比较的。

    • 由于几何-拓扑相似性图形距离都是有单位的标量,不能体现空间实体O在尺度${s_i}$上的图形相对于初始尺度s上的图形的相对相似程度,因此分别用空间实体初始尺度图形上所有重采样点间的最大直线距离max(${\mathit{\boldsymbol{D}}_{E - \hat X}}$)和最大最短路径max(${\mathit{\boldsymbol{D}}_{\mathit{\boldsymbol{X}} - \hat X}}$)对几何相似性图形距离和拓扑相似性图形距离进行归一化处理,得到$\mathit{\boldsymbol{X}}$与${\mathit{\boldsymbol{X}}^i}$的几何相似度$K\_{d_H}\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)$和拓扑相似度$K\_{d_{{\rm{GH}}}}\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)$,即:

      $${K_ - }{d_H}\left( {\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right) = 1 - d_{H - \min }^E\left( {\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)/\max \left( {{\mathit{\boldsymbol{D}}_{E \cdot \mathit{\boldsymbol{\widehat X}}}}} \right)$$ (6)
      $${K_ - }{d_{{\rm{GH}}}}\left( {\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right) = 1 - {d_{{\rm{GH}}}}\left( {\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)/\max \left( {{\mathit{\boldsymbol{D}}_{X - \mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\frown$}} \over X} }}} \right)$$ (7)

      $K\_{d_H}\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)$越大,$\mathit{\boldsymbol{X}}$与${\mathit{\boldsymbol{X}}^i}$的几何相似度越大;$K\_{d_{{\rm{GH}}}}\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)$越大,$\mathit{\boldsymbol{X}}$与${\mathit{\boldsymbol{X}}^i}$的拓扑相似度越大。多尺度表达图形之间的几何-拓扑相似度$K\left({\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right)$的二元组为:

      $$K\left( {\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{X}}^i}} \right) = \left( {{K_ - }{d_H}, {K_ - }{d_{{\rm{CH}}}}} \right)$$ (8)
    • 1)将$\mathit{\boldsymbol{X}}$和${\mathit{\boldsymbol{X}}^i}$进行等间隔离散化,得到离散点${\hat X}$和${{\hat X}^i}$,离散化取样密度在不影响图形几何细节特征的情况下应尽量小些,以提高时间和空间效率。

      2)计算离散点${\hat X}$的欧氏距离矩阵和最短路径矩阵,并计算各矩阵中的最大值;计算${{\hat X}^i}$的最短路径矩阵。

      3)计算$\mathit{\boldsymbol{X}}$和${\mathit{\boldsymbol{X}}^i}$的等距(同构)嵌入点结构。

      4)计算${\hat X}$和${{\hat X}^i}$间的几何-拓扑相似性图形距离。

      5)计算${\hat X}$和${{\hat X}^i}$间的几何-拓扑相似度。

    • 本实验选用的数据为图 3所示的单一线状要素的多尺度表达,用线要素的节点代替离散点。依次执行§3.1的步骤,图 3中各子图与图 3(a)的几何-拓扑相似性用图 4的折线图表示。

      图  3  多比例尺单线要素

      Figure 3.  Multi-scale Single Line Features

      图  4  图 3中各图形与初始图形的几何-拓扑相似性

      Figure 4.  Similarity of Different Scale Shapes Against the Initial Shape in Fig. 3

      图 4可以看出,图 3中各子图与图 3(a)的几何-拓扑相似度的变化趋势为:(1)几何相似度随化简程度的增加而减少,但减少缓慢;(2)拓扑相似度随化简程度的增加而减少,且减幅较大;(3)随着化简程度的增加,拓扑相似度逐渐低于几何相似度,且差值越来越大。

      图 4的分析可以得出,随着线图形化简程度的增加,简化线与初始线的空间相似性逐渐减少,且拓扑相似性明显低于几何相似性。

      分析图 3在多尺度表达过程中形状、数量特征的变化。图 3在多尺度表达过程中执行的是线小弯曲处节点的删除,结果是曲线的基本形状特征保持不变、长度变短。形状特性变化小,以致于简化线相对于初始线对应点的直线距离变化小,而几何相似性图形距离是由直线距离定义的,因此几何相似性图形距离随线化简程度的增加而缓慢增加;曲线长度变短,致使点与点间的连通距离缩短,而拓扑相似性图形距离是由最短路径定义的,因此拓扑相似性图形距离随化简程度的增加而较快增加。这说明拓扑相似性图形距离、拓扑相似度能够敏锐地探测出多尺度单一线状要素连通性(最短路径)的改变。

      实验结果表明,几何-拓扑相似性图形距离、几何-拓扑相似度能有效地度量单线要素多尺度表达的相似性,且拓扑相似性图形距离、拓扑相似度比几何相似性图形距离、几何相似度对单一线要素的化简更敏感。

    • 本实验用于分析面状空间实体及复杂面状空间实体多尺度表达的几何-拓扑相似性。实验数据为图 5所示的多边形。在现实中,多边形往往比较复杂,其内部多带有“岛屿”,在图 5内部添加“岛屿”来改变多边形的拓扑结构。具体实验在以下4种情况下完成:(1)图 5采用简单多边形的多尺度表达;(2)在图 5(a)内部添加5个大小不等的“岛屿”得到图 6(a),且图 6(a)边界化简、“岛屿”不化简;(3)图 7(a)图 6(a)图形相同,且图 7(a)边界、“岛屿”同时化简;(4)图 8(a)图 6(a)图形相同,且图 8(a)边界不化简、“岛屿”化简。

      图  5  简单多边形多尺度表达——边界化简[12]

      Figure 5.  Multi-scale Representation of Simple Polygon—Boundary Simplification[12]

      图  6  在图 5(a)内部添加“岛屿”——边界化简、“岛屿”不化简

      Figure 6.  Complex Polygon with Holes—Boundary Simplification and Holes Unchanged

      图  7  在图 5(a)内部添加“岛屿”——边界化简、“岛屿”化简

      Figure 7.  Complex Polygon with Holes—Boundary Simplification and Holes Generalization

      图  8  在图 5(a)内部添加“岛屿”——边界不化简、“岛屿”化简

      Figure 8.  Complex Polygon with Holes—Boundary Unchanged and Holes Generalization

      分别对图 5图 8执行§3.1的步骤,得到各图各尺度图形与初始尺度图形的几何-拓扑相似性图形距离和几何-拓扑相似度,分别见表 1表 2

      表 1  实验数据各尺度图形与初始尺度图形的几何-拓扑相似性图形距离/m

      Table 1.  Comparison of Geometrical-Topological Similarity Shape Distances Between Different Scale Shapes Against Initial Scale Shapes in Four Groups of Experimental Data/m

      图形 尺度s 尺度s1 尺度s2 尺度s3
      图 5:边化简(无岛) (0, 0) (6, 3.8) (8.25, 7.97) (16, 20.40)
      图 6:边化简、岛不化简 (0, 0) (6, 4.79) (8.25, 9.00) (16, 24.80)
      图 7:边化简、岛化简 (0, 0) (6, 5.28) (8.25, 8.10) (16, 24.47)
      图 8:边不化简、岛化简 (0, 0) (2, 0.61) (2, 0.91) (3, 5.07)

      表 2  实验数据各尺度图形与初始尺度图形的几何-拓扑相似度/%

      Table 2.  Comparison of Geometrical-Topological Similarities Between Different Scale Shapes Against Initial Scale Shapes in Four Groups of Experimental Data/%

      图形 尺度s 尺度s1 尺度s2 尺度s3
      图 5:边化简(无岛) (100, 100) (94.77, 97.65) (92.81, 95.06) (86.04, 87.36)
      图 6:边化简、岛不化简 (100, 100) (94.70, 96.98) (92.72, 94.32) (85.88, 84.36)
      图 7:边化简、岛化简 (100, 100) (94.70, 96.67) (92.72, 94.89) (85.88, 84.57)
      图 8:边不化简、岛化简 (100, 100) (98.23, 99.62) (98.23, 99.42) (97.35, 96.80)

      表 2的数据显示:(1)图 5图 8的几何-拓扑相似度均随化简程度的增加而降低;(2)图 6图 7对应的尺度间几何相似度分别相等,而拓扑相似度各不相同;(3)图 8几何-拓扑相似度明显高于图 5图 6图 7

      这4组实验数据和实验结果表明:(1)多边形边界化简和多边形内部“岛屿”的化简都会引起几何-拓扑相似性的改变,且化简程度越高,与初始尺度多边形的几何-拓扑相似性图形距离越大,相似度越低;(2)在多边形内部增加“岛屿”,并未影响化简尺度多边形与初始尺度多边形的几何相似性图形距离,但却影响了拓扑相似性图形距离;(3)在边界不化简的情况下,内部“岛屿”的删除、合并同样会引起几何-拓扑相似性图形距离的改变,但这种改变小于边界化简引起的改变。

      值得深思的是,本实验中多边形几何相似性受多边形边界化简的影响大于内部“岛屿”化简的影响(图 5图 8),边界、“岛屿”同时化简时,“岛屿”对几何相似性的影响被边界的影响所覆盖(图 5图 7),但多边形边界、“岛屿”对多边形拓扑相似性的影响是形成合力的。

      本实验中,删除的“岛屿”的尺寸、合并的“岛屿”的间隔尺寸小于多边形边界化简的尺寸,以致于“岛屿”的综合对多边形几何相似性的影响被边界综合的影响所覆盖。为验证分析的正确性,另外增加一组数据进行与上面相同的实验,实验中“岛屿”综合的尺寸大于边界综合的尺寸。结果显示,当边界、“岛屿”同时综合时,“岛屿”对多边形几何相似性的影响覆盖了边界的影响,多边形边界、“岛屿”对多边形拓扑相似性的影响是形成合力的。也就是说,对于多边形局部形状的改变,几何相似性图形距离、几何相似度不能有效地度量这种改变,但拓扑相似性图形距离、拓扑相似度能敏感地探测到这种变化。

    • 空间实体图形间的相似性度量是评价空间实体多尺度表达质量的重要方法。本文从度量几何学的观点,利用等距同构不变性,分别将空间实体看作刚性和弹性图像,构建了空间实体多尺度表达的几何和拓扑相似性图形距离,继而定义了多尺度空间实体的几何相似度和拓扑相似度。

      实验表明,几何相似性图形距离、几何相似度用于量化多尺度空间实体的几何形状相似性是有效的;而拓扑相似性图形距离、拓扑相似度用于量化多尺度空间实体的拓扑结构相似性是有效的;二元集值相似度能同时顾及多尺度空间实体几何和拓扑特性的改变。这说明本文构建的相似性度量模型能客观地反映空间实体多尺度变换下几何和拓扑特征的变化,相较于其他研究中仅针对图形几何形状特征构建的相似性度量模型,更客观全面,更具有实用价值。但该模型是基于多尺度空间实体全局的几何形状和拓扑特征构建的,不能全面地反映多尺度空间实体的局部几何形状和拓扑特征的相似性。

      该成果一方面可用于同一目标在数据处理前后几何和拓扑变形程度的度量,另一方面可进一步应用于基于空间实体相似性的查询与空间数据匹配中。在后续研究中,将考虑多尺度表达中自动综合阈值与空间相似性图形距离、空间相似度的关系,以指导空间实体多尺度表达中自动综合阈值的设定,达到自动控制质量的目的。

参考文献 (17)

目录

    /

    返回文章
    返回