留言板

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

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

利用约束满足问题进行多洞面实体相似性度量

陈占龙 吴亮 谢忠 张丁文

陈占龙, 吴亮, 谢忠, 张丁文. 利用约束满足问题进行多洞面实体相似性度量[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 745-751, 785. doi: 10.13203/j.whugis20160191
引用本文: 陈占龙, 吴亮, 谢忠, 张丁文. 利用约束满足问题进行多洞面实体相似性度量[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 745-751, 785. doi: 10.13203/j.whugis20160191
CHEN Zhanlong, WU Liang, XIE Zhong, ZHANG Dingwen. Similarity Measurement of Multi-holed Regions Using Constraint Satisfaction Problem[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 745-751, 785. doi: 10.13203/j.whugis20160191
Citation: CHEN Zhanlong, WU Liang, XIE Zhong, ZHANG Dingwen. Similarity Measurement of Multi-holed Regions Using Constraint Satisfaction Problem[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 745-751, 785. doi: 10.13203/j.whugis20160191

利用约束满足问题进行多洞面实体相似性度量

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

国家重点研发计划 2017YFC0602204

中央高校基本科研业务费专项资金 CUG160226

地理信息工程国家重点实验室开放基金 SKLGIE2013-Z-4-1

测绘遥感信息工程国家重点实验室 13I02

国家自然科学基金 41401443

国家自然科学基金 41671400

湖北省自然科学基金 2015CFA012

详细信息

Similarity Measurement of Multi-holed Regions Using Constraint Satisfaction Problem

Funds: 

The National Key R & D Program of China 2017YFC0602204

the Fundamental Research Funds for the Central Universities, China University of Geosciences (Wuhan) CUG160226

Open Research Fund of State Key Laboratory of Geography Information Engineering SKLGIE2013-Z-4-1

Open Research Fund of State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Programs 13I02

the National Natural Science Foundation of China 41401443

the National Natural Science Foundation of China 41671400

the Natural Science Foundation of Hubei Province of China 2015CFA012

More Information
    Author Bio:

    CHEN Zhanlong, PhD, associate professor, specializes in geo-computation and spatial analysis, and high performance computation.E-mail:Chenzhanlong2005@126.com

    Corresponding author: ZHANG Dingwen, PhD.dingwenzhang@yahoo.com
  • 摘要: 多洞面实体作为现实世界的抽象,主要用来表示拥有多个内部边界的地理实体,如包含多个湖泊的区域,或带有岛屿的湖泊。为了度量这些空间实体,提出了一种顾及多约束的多洞面实体相似性度量模型,该模型将多洞区域看做微场景,将洞视为空间对象,洞之间的方向表示为空间分布关系。顾及复杂多洞面实体中洞与洞之间的方向、几何形状等约束条件,利用傅里叶描述子来描述洞的形状,使用方向特征矩阵来表示洞之间的分布,将相似性度量过程转换变成满足约束条件问题。利用由结点和边组成的关联图对约束条件的匹配过程进行描述。采用伊朗西北部的乌鲁米耶湖作为实验数据,对其不同年份的形态进行相似性度量,实验结果表明该方法简单可行且不失精度。
  • 图  1  多洞区Rn中洞间约束的关联图

    Figure  1.  Association Graph of Multiple Constraints in Rn

    图  2  两个多洞实体间的3种匹配情形

    Figure  2.  Three Matching Cases Between Two Multi-holed Regions

    图  3  特征矩阵邻域空间的四维网格

    Figure  3.  4 Demision Feature Matix Space

    图  4  乌鲁米耶湖

    Figure  4.  Lake Urmia

    图  5  匹配关联图

    Figure  5.  Assocaition Graph of Holes Matching

    图  6  投影区间

    Figure  6.  Projection Interval

    图  7  其余方案的关联图

    Figure  7.  Assocaition Graph of Other Solutions

    表  1  RnRm外边界及每对洞的几何相似度

    Table  1.   Similarity of Outer andHoles of Rn and Rm

    em H1 H2 H3 H4 H5
    en 0.901 75
    H1 0.827 52 0.683 2 0.712 96 0.704 29 0.682 88
    H2 0.685 5 0.849 12 0.732 75 0.786 79 0.762 22
    H3 0.704 13 0.729 53 0.684 83 0.759 61 0.684 23
    H4 0.721 28 0.751 07 0.706 49 0.747 27 0.712 13
    下载: 导出CSV

    表  2  对象A的方向矩阵

    Table  2.   Direction Matrix of Region A

    H1 H2 H3 H4
    H1 [(0, 0) (0, 2)]T [(2, 2) (2, 2)]T [(2, 2) (2, 2)]T
    H2 [(-2, 2) (-2, 0)]T [(0, 2) (2, 2)]T [(2, 2) (-1, 2)]T
    H3 [(-2, 2) (-2, -2)]T [(-2, 0) (-2, -2)]T [(-1, 2) (-2, -2)]T
    H4 [(-2, -2) (-2, -2)]T [(-2, -2) (-1, 0)]T [(-1, 0) (2, 2)]T
    下载: 导出CSV

    表  3  对象B的方向矩阵

    Table  3.   Direction Matrix of Region B

    H1 H2 H3 H4 H5
    H1 [(0, 0) (0 2)] [(2, 2) (2, 2)] [(2, 2) (2, 2)] [(-2, -2) (2, 2)]
    H2 [(-2, 2) (-2, 0)] [(0, 2) (2, 2)] [(2, 2) (-2, 2)] [(1, 2) (-2, -2)]
    H3 [(-2, 2) (-2, -2)] [(-2, 0) (-2, -2)] [(0, 2) (-2, -2)] [(0, 2) (-2, -2)]
    H4 [(-2, -2) (-2, -2)] [(-2, -2) (0, 0)] [(-2, 0) (2, 2)] [(0, 0) (-2, -2)]
    H5 [(-2, -2) (2, 2)] [(-2, -1) (2, 2)] [(-2, 0) (2, 2)] [(-2, 2) (2, 2)]
    下载: 导出CSV

    表  4  解决方案的形状相似度和方向相似度

    Table  4.   Shape and Direction Similarity of Solutions

    解决方案 1 2 3 4 5 6
    形状相似度 0.787/0.751 0.777/0.731 0.775/0.728 0.762/0.720 0.739/0.711 0.76/0.721
    方向相似度 0.717 0.98 0.737 0.758 0.322 0.457
    综合相似度 0.752 0.879 0.756 0.76 0.53 0.508
    注:A/B中,A是本文方法结果,B为文献[27]结果
    下载: 导出CSV
  • [1] OpenGIS Consortium Inc. OpenGIS Simple Features Specification for SPL[R]. OpenGIS Consortium, Wayland, M A, 1999
    [2] Egenhofer M J, Clementini E, di Felice P. Topological Relations Between Regions with Holes[J]. International Journal of Geographical Information Science, 1994, 8(2):129-142 doi:  10.1080/02693799408901990
    [3] 徐枫, 邓敏, 赵彬彬, 等.空间目标匹配方法的应用分析[J].地球信息科学学报, 2009, 11(5):657-663 http://www.dqxxkx.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=23242

    Xu Feng, Deng Min, Zhao Binbin, et al. A Detailed Investigation on the Methods of Object Matching[J]. Journal of Geo-Information Science, 2009, 11(5):657-663 http://www.dqxxkx.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=23242
    [4] Frank A U, Kuhn W. CellGraphs: A Provable Correct Method for the Storage of Geometry[C]. International Symposium on Spatial Data Handling, Seattle, USA, 1986
    [5] Egenhofer M J, Vasardani M. Spatial Reasoning with a hole[C]. International Conference on Spatial Information Theory, Melbourne, Australia, 2007
    [6] Vasardani M, Egenhofer M J. Single-Holed Regions: Their Relations and Inferences[C]. International Conference on Geographic Information Science, Park City, USA, 2008
    [7] 陈占龙, 周林, 龚希, 等.基于方向关系矩阵的空间方向相似性定量计算方法[J].测绘学报, 2015, 44(7):813-821 doi:  10.11947/j.AGCS.2015.20140198

    Chen Zhanlong, Zhou Lin, Gong Xi, et al. A Quantitative Calculation Method of Spatial Direction Similarity Based on Direction Relation Matrix[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(7):813-821 doi:  10.11947/j.AGCS.2015.20140198
    [8] Chetverikov D, Khenokh Y. Matching for Shape Defect Detection[C]. International Conference on Computer Analysis of Images and Patterns, Berlin, Heidelberg, 1999
    [9] Bimbo A D, Pala P. Visual Image Retrieval by Elastic Matching of user Sketches[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997, 19(2):121-132 doi:  10.1109/34.574790
    [10] Abbasi S, Mokhtarian F, Kittler J. Curvature Scale Space Image in Shape Similarity Retrieval[J]. Multimedia Systems, 1999, 7(6):467-476 doi:  10.1007/s005300050147
    [11] Mokhtarian F, Abbasi S, Kittler J. Efficient and Robust Retrieval by Shape Content Through Curvature Scale Space[J]. Series on Software Engineering and Knowledge Engineering, 1997, 8(2):51-58
    [12] Arbter K, Snyder W E, Burkhardt H, et al. Application of Affine-Invariant Fourier Descriptors to Recognition of 3-D Objects[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990, 12(7):640-647 doi:  10.1109/34.56206
    [13] Chellappa R, Bagdazian R. Fourier Coding of Image Boundaries[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1984(1):102-105
    [14] Krzyak A, Leung S Y, Suen C Y. Reconstruction of Two-Dimensional Patterns from Fourier Descriptors[J]. Machine Vision and Applications, 1989, 2(3):123-140 doi:  10.1007/BF01212454
    [15] Mehtre B M, Kankanhalli M S, Lee W F. Shape Measures for Content Based Image Retrieval:A Comparison[J]. Information Processing & Management, 1997, 33(3):319-337
    [16] van Otterloo P J. A Contour-Oriented Approach to Shape Analysis[M]. Hertfordshire, UK: Prentice Hall International (UK) Ltd., 1991
    [17] Ohm J R, Bunjamin F, Liebsch W, et al. A Set of Visual Feature Descriptors and Their Combination in a Low-level Description Scheme[J]. Signal Processing:Image Communication, 2000, 16(1):157-179
    [18] Tieng Q M, Boles W W. Recognition of 2D Object Contours Using the Wavelet Transform Zero-crossing Representation[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1997(8):910-916
    [19] Yang H S, Lee S U, Lee K M. Recognition of 2D Object Contours Using Starting-Point-Independent Wavelet Coefficient Matching[J]. Journal of Visual Communication and Image Representation, 1998, 9(2):171-181 doi:  10.1006/jvci.1998.0384
    [20] Iivarinen J, Visa A J E. Shape Recognition of Irregular Objects[C]. International Society for Optics and Photonics, Boston, Massachusetts, 1996
    [21] Grosky W I, Mehrotra R. Index-Based Object Recognition in Pictorial Data Management[J]. Computer Vision, Graphics, and Image Processing, 1990, 52(3):416-436 doi:  10.1016/0734-189X(90)90085-A
    [22] Grosky W I, Neo P, Mehrotra R. A pictorial Index Mechanism for Model-based Matching[J]. Data & Knowledge Engineering, 1992, 8(4):309-327 https://www.sciencedirect.com/science/article/pii/0169023X9290044C
    [23] Mehrotra R, Gary J E. Similar-Shape Retrieval in Shape data Management[J]. Computer, 1995, 28(9):57-62 doi:  10.1109/2.410154
    [24] Berretti S, del Bimbo A, Pala P. Retrieval by Shape Similarity with Perceptual Distance and Effective Indexing[J]. IEEE Transactions on Multimedia, 2000, 2(4):225-239 doi:  10.1109/6046.890058
    [25] Torokhti A, Howlett P. Syntactic Methods in Pattern Recognition[M]. Atlanta, GA: Elsevier, 1974
    [26] 陈占龙, 冯齐奇, 吴信才.复合面状对象拓扑关系的表达模型[J].测绘学报, 2015, 44(4):438-444 doi:  10.11947/j.AGCS.2015.20130708

    Chen Zhanlong, Feng Qiqi, Wu Xincai. Representation Model of Topological Relations Between Complex Planar Objects[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(4):438-444 doi:  10.11947/j.AGCS.2015.20130708
    [27] 陈占龙, 覃梦娇, 吴亮, 等.利用多级弦长弯曲度复函数构建复杂面实体综合形状相似度量模型[J].测绘学报, 2016, 45(2):224-232 doi:  10.11947/j.AGCS.2016.20140633

    Chen Zhanlong, Qin Mengjiao, Wu Liang. Establishment of the Comprehensive Shapes Similarity Model for Complex Polygon Entity by Using Bending Mutilevel Chord Complex Function[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(2):224-232 doi:  10.11947/j.AGCS.2016.20140633
  • [1] 金澄, 安晓亚, 陈占龙, 马啸川.  矢量居民地多边形多级图划分聚类方法 . 武汉大学学报 ● 信息科学版, 2021, 46(1): 19-29. doi: 10.13203/j.whugis20190358
    [2] 赵云鹏, 孙群, 刘新贵, 程绵绵, 俞童, 李元復.  面向地理实体的语义相似性度量方法及其在道路匹配中的应用 . 武汉大学学报 ● 信息科学版, 2020, 45(5): 728-735. doi: 10.13203/j.whugis20190039
    [3] 李兆兴, 翟京生, 武芳.  线要素综合的形状相似性评价方法 . 武汉大学学报 ● 信息科学版, 2019, 44(12): 1859-1864. doi: 10.13203/j.whugis20180164
    [4] 程绵绵, 孙群, 李少梅, 徐立.  多尺度点群广义Hausdorff距离及在相似性度量中的应用 . 武汉大学学报 ● 信息科学版, 2019, 44(6): 885-891. doi: 10.13203/j.whugis20170305
    [5] 徐丰, 牛继强, 林昊, 陈时雨, 张兵兵, 陈飞燕.  利用等距同构建立多尺度空间实体相似性度量模型 . 武汉大学学报 ● 信息科学版, 2019, 44(9): 1399-1406. doi: 10.13203/j.whugis20170344
    [6] 信睿, 艾廷华, 晏雄锋, 杨敏.  相似性度量支持下的隐喻地图轮廓设计 . 武汉大学学报 ● 信息科学版, 2019, 44(4): 625-632. doi: 10.13203/j.whugis20170153
    [7] 沈永林, 刘修国, 吴立新, 苏红军, 何浩.  Hyperion高光谱影像坏线修复的局部空间-光谱相似性测度方法 . 武汉大学学报 ● 信息科学版, 2017, 42(4): 456-462. doi: 10.13203/j.whugis20150007
    [8] 陈占龙, 吕梦楼, 吴亮, 徐永洋.  基于特征矩阵和关联图的空间场景相似性度量方法 . 武汉大学学报 ● 信息科学版, 2017, 42(7): 956-962. doi: 10.13203/j.whugis20140450
    [9] 许俊奎, 武芳, 钱海忠, 马芳博.  一种空间关系相似性约束的居民地匹配算法 . 武汉大学学报 ● 信息科学版, 2013, 38(4): 484-485.
    [10] 刘鹏程, 罗静, 艾廷华, 李畅.  基于线要素综合的形状相似性评价模型 . 武汉大学学报 ● 信息科学版, 2012, 37(1): 114-117.
    [11] 唐永鹤, 陶华敏, 卢焕章, 胡谋法.  一种基于Harris算子的快速图像匹配算法 . 武汉大学学报 ● 信息科学版, 2012, 37(4): 406-409.
    [12] 谢明霞, 王家耀, 郭建忠, 陈科.  不等距划分的高维相似性度量方法研究 . 武汉大学学报 ● 信息科学版, 2012, 37(7): 780-783.
    [13] 安晓亚, 孙群, 尉伯虎.  利用相似性度量的不同比例尺地图数据网状要素匹配算法 . 武汉大学学报 ● 信息科学版, 2012, 37(2): 224-228.
    [14] 王新生, 何津, 叶晓雷, 姜友华.  图的谱方法的空间目标形状表达研究 . 武汉大学学报 ● 信息科学版, 2012, 37(11): 1281-1284.
    [15] 杨春成, 何列松, 谢鹏, 周校东.  顾及距离与形状相似性的面状地理实体聚类 . 武汉大学学报 ● 信息科学版, 2009, 34(3): 335-338.
    [16] 李光强, 邓敏, 朱建军.  基于Voronoi图的空间关联规则挖掘方法研究 . 武汉大学学报 ● 信息科学版, 2008, 33(12): 1242-1245.
    [17] 杜培军, 唐宏, 方涛.  高光谱遥感光谱相似性度量算法与若干新方法研究 . 武汉大学学报 ● 信息科学版, 2006, 31(2): 112-115.
    [18] 杨春成, 张清浦, 田向春, 何列松.  应用于面状地理实体聚类分析的线段链形状相似性准则 . 武汉大学学报 ● 信息科学版, 2005, 30(1): 61-64.
    [19] 李浩松, 朱欣焰, 李京伟, 陈军.  WebGIS空间数据分布式缓存技术研究 . 武汉大学学报 ● 信息科学版, 2005, 30(12): 1092-1095.
    [20] 郭庆胜, 丁虹.  基于栅格数据的面状目标空间方向相似性研究 . 武汉大学学报 ● 信息科学版, 2004, 29(5): 447-450,465. doi: 10.13203/j.whugis2004.05.016
  • 加载中
图(7) / 表(4)
计量
  • 文章访问数:  1267
  • HTML全文浏览量:  77
  • PDF下载量:  281
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-12-25
  • 刊出日期:  2018-05-05

利用约束满足问题进行多洞面实体相似性度量

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

    国家重点研发计划 2017YFC0602204

    中央高校基本科研业务费专项资金 CUG160226

    地理信息工程国家重点实验室开放基金 SKLGIE2013-Z-4-1

    测绘遥感信息工程国家重点实验室 13I02

    国家自然科学基金 41401443

    国家自然科学基金 41671400

    湖北省自然科学基金 2015CFA012

    作者简介:

    陈占龙, 博士, 副教授, 主要研究地理计算及空间分析、高性能计算等。Chenzhanlong2005@126.com

    通讯作者: 张丁文, 博士。dingwenzhang@yahoo.com
  • 中图分类号: P208

摘要: 多洞面实体作为现实世界的抽象,主要用来表示拥有多个内部边界的地理实体,如包含多个湖泊的区域,或带有岛屿的湖泊。为了度量这些空间实体,提出了一种顾及多约束的多洞面实体相似性度量模型,该模型将多洞区域看做微场景,将洞视为空间对象,洞之间的方向表示为空间分布关系。顾及复杂多洞面实体中洞与洞之间的方向、几何形状等约束条件,利用傅里叶描述子来描述洞的形状,使用方向特征矩阵来表示洞之间的分布,将相似性度量过程转换变成满足约束条件问题。利用由结点和边组成的关联图对约束条件的匹配过程进行描述。采用伊朗西北部的乌鲁米耶湖作为实验数据,对其不同年份的形态进行相似性度量,实验结果表明该方法简单可行且不失精度。

English Abstract

陈占龙, 吴亮, 谢忠, 张丁文. 利用约束满足问题进行多洞面实体相似性度量[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 745-751, 785. doi: 10.13203/j.whugis20160191
引用本文: 陈占龙, 吴亮, 谢忠, 张丁文. 利用约束满足问题进行多洞面实体相似性度量[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 745-751, 785. doi: 10.13203/j.whugis20160191
CHEN Zhanlong, WU Liang, XIE Zhong, ZHANG Dingwen. Similarity Measurement of Multi-holed Regions Using Constraint Satisfaction Problem[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 745-751, 785. doi: 10.13203/j.whugis20160191
Citation: CHEN Zhanlong, WU Liang, XIE Zhong, ZHANG Dingwen. Similarity Measurement of Multi-holed Regions Using Constraint Satisfaction Problem[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 745-751, 785. doi: 10.13203/j.whugis20160191
  • 开放地理空间协会(Open Geospatial Consortium, OGC)在定义面对象作为地理数据库中的简单要素时提到了带洞面的存在[1],“带洞面实体对象是一个二维平面,由一条外边界和若干条内边界组成;内边界形成了面实体对象中的洞,带洞面实体对象的外部区域是不连续的,每个洞都包含了外部区域的一个分区”。文献[2]在描述GIS处理的现实问题时也提到了带洞面,如“圣马力诺共和国被意大利包围”,其他类似的情况如南非的休伦湖完全包围着岛屿Lesotho和Manitoulin,前东德包围着西柏林等,上述文献对带洞面实体进行了定义,并对带洞面实体的现实情形进行了描述。空间实体的相似性度量是一个重要课题,在空间实体匹配方面占有举足轻重的地位,面实体的匹配是空间数据库的更新和融合的核心问题,面实体的几何相似性度量是决定匹配的关键。文献[3]研究了空间实体的拓扑、几何等匹配算法。在面实体之间的拓扑相似度匹配方面,文献[4]在空间关系的4-交矩阵和9-交矩阵基础上进行了空间相似性度量的研究,文献[5-6]在该研究的基础上,使用模糊隶属函数定义了空间拓扑, 包括一个简单面和一个带洞面之间的23种拓扑关系、两个单洞面之间的152种拓扑关系及一个不带洞面和一个多洞面之间的拓扑相似度等,文献[7]对经典的9-交集模型进行了改进,利用分解的思想建立了复合面状对象拓扑关系的表达模型。

    在面实体之间的几何相似度方面,由于带洞面实体中的洞可表现为形成区内外边界的线圈[1],现阶段的模型大多利用成熟的形状描述子来精确描述面实体,如豪斯多夫距离[8]、基于形状图像检索的弹性匹配[9]、尺度空间表示[10-11]、傅里叶描述子[12-16]、小波描述子[17-19]、链条编码表示[20]、多边形近似[21-23]、光滑曲线分解[24]及语法分析[25]等,取得了较好的效果。

    复杂带洞面实体的相似性度量除了需要对几何图形的整体和局部特征都能较好地进行描述外,由于带洞面实体的组合复杂性,还需顾及多洞区域之间的空间分布关系,而不仅仅是对带洞面实体的单圈边界进行描述和度量。现有的模型将带洞面实体机械割裂开来进行度量,对多洞面实体中洞的方向关系[26]考虑不足。本文将多洞面实体视为空间微场景(空间场景包含一组空间对象及对象间的空间关系)来度量多洞面实体之间的相似度,该算法可应用于检索、分类更新不同来源的地理空间数据。

    • 本文将多洞面实体间的相似度计算转换为约束满足问题(constraint satisfaction problem, CSP),并以多洞面实体中边界的形状及洞之间的方向作为约束条件。对于带m个洞的多洞面实体Rm,度量其与多洞面实体Rn相似度的CSP中包含了:

      1) 与RnRm的外边界相对应的变量enem

      2) 与Rn中的洞相对应的n个变量H1Hn的集合。

      3) 对于每个变量Hi,实体Rm中与Hi可能存在对应关系的变量集合Hi={H1Hl}。

      4) 对于每个变量Hi, 存在描述形状的一元约束si

      5) 对于每对变量(Hi, Hj),描述了它们之间方向关系的二元约束dij

      解决该约束满足问题的关键在于基于所有约束条件将RmRn中的洞进行相互匹配。本文使用由节点和边组成的关联图来表现Rn中的约束(见图 1),每个节点上的值与边界的几何约束相对应,每条边上的值则描述了洞之间的方向约束。由于所有的洞都位于Rn外边界的内部,因此不考虑外边界与洞之间的方向,即节点e与其他节点间不存在边。

      图  1  多洞区Rn中洞间约束的关联图

      Figure 1.  Association Graph of Multiple Constraints in Rn

      两个不同多洞面实体的关联图通常包含了不同数量的节点,RnRm不一定具有相同数量的洞,因此两个多洞实体之间的匹配存在3种类型的情形。

      1) 完整的解决方案。Rm的关联图Gm中的子关联图GmRn的关联图Gn相匹配,即Rn中所有的洞和方向关系在Rm中都能找到对应(图 2(a))。

      图  2  两个多洞实体间的3种匹配情形

      Figure 2.  Three Matching Cases Between Two Multi-holed Regions

      2) 不完整的解决方案。Gm的子关联图GmGn的子关联图Gn相匹配,即Rn中洞及方向关系的子集在Rm的子集中找到对应(图 2(b))。

      3) 不存在解决方案(图 2(c))。

    • 对两个实体边界进行准确的几何形状相似度量时,需要对边界进行详细的描述。本文使用多等级弦长弧段弯曲度的傅里叶描述子来描述边界。

      将形状描述为一组空间点的有序集合{Pi=(xi, yi), i=1, 2…N},假设P0是起始点,则ci可表示为弧段$ \overset\frown{{{P}_{0}}{{P}_{i}}}$的长度,对点Pit级弦长的弧段弯曲度θt(ci)执行快速傅里叶变换,可得:

      $$ a\left( m \right) = \frac{1}{{N'}}\sum\limits_{j = 0}^{N' - 1} {{\theta _t}\left( {{c_j}} \right){{\rm{e}}^{ - j2{\rm{ \mathsf{ π} }}m{\rm{i}}/N'}}} ,m = 0,1 \cdots N' - 1 $$ (1)

      式中,a(m)是第t级弦长弧段弯曲度的快速傅里叶描述子,则集合at={|at(0)|, |at(1)|…|at(N′-1)|}描述了坐标点集{Pi=xi, yi, i=1, 2…N}第t级弦长的弧段弯曲度;N表示有序集合中所有点的个数;j对应有序点集中的某一点Pj; i为虚数单位。取t=1, 2…N即可得到形状AB的描述子αAαB,其中atAatB分别表示形状AB坐标点集的第t级弦长的弧段弯曲度集合:

      $$ {\alpha _A} = \left\{ {\alpha _1^A,\alpha _2^A \cdots \alpha _N^A} \right\},{\alpha _B} = \left\{ {\alpha _1^B,\alpha _2^B \cdots \alpha _N^B} \right\} $$ (2)

      对描述子α执行标准化运算,形状AB之间的差异度可被定义为:

      $$ d{\left( {A,B} \right)_s} = {\left( {\sum\limits_{t = 1}^N {{{\left| {a_t^A - a_t^B} \right|}^2}} } \right)^{1/2}} $$ (3)

      根据形状差异度,且基于差异度及相似度互余的事实,AB的形状相似度可定义为:

      $$ S{\left( {A,B} \right)_s} = 1 - d{\left( {A,B} \right)_s} $$ (4)
    • 为了有效度量洞之间的方向相似度,本文用特征矩阵来描述两个空间区域的最小外包矩形(minimum bounding rectangle, MBR)之间的方向。

      定义1特征矩阵:对于矩形对象AB,特征矩阵定量地描述了它们之间的空间约束。特征矩阵FA, B的构建主要基于ABxy轴投影区间端点间的顺序关系。使用特征值元组fxfy对特征矩阵进行化简,则可分别描述矩形对象ABxy轴投影区间之间的约束。

      $$ {\mathit{\boldsymbol{F}}_{A,B}} = \left( {\begin{array}{*{20}{c}} {C\left( {{A_{x - }},{B_{x - }}} \right) + C\left( {{A_{x - }},{B_{x + }}} \right)}&{C\left( {{A_{x + }},{B_{x - }}} \right) + C\left( {{A_{x + }},{B_{x + }}} \right)}\\ {C\left( {{A_{y - }},{B_{y - }}} \right) + C\left( {{A_{y - }},{B_{y + }}} \right)}&{C\left( {{A_{y + }},{B_{y - }}} \right) + C\left( {{A_{y + }},{B_{y + }}} \right)} \end{array}} \right) = {\left[ {\begin{array}{*{20}{c}} {{f_x}}&{{f_y}} \end{array}} \right]^{\rm{T}}} $$ (5)

      式中,C表示矩形对象AB的边投影至x轴及y轴上形成的端点间的排序关系。将矩形对象AB的边投影至x轴及y轴上,可分别得到AB的投影区间(Ax-, Ay-, Ax+, Ay+)与(Bx-, By-, Bx+, By+),Ax-Ay-表示A左下角的xy坐标,Ax+Ay+分别表示A右上角的xy坐标。Bx-By-Bx+By+同理。

      本文利用4维网格表示法来描述特征矩阵的邻域空间,如图 3所示,两个垂直平面的轴分别标记为x1x2y1y2,代表着特征值元组对中的4个特征值,并与矩形投影区间的约束相对应。x1-x2平面中13个顶点所对应的特征值元组被标记在投影网格上,每一个顶点(x1i, x2i)都有一个对应的y1-y2平面且(x1i, x2i)为该平面原点,此平面描述了矩形的y轴投影区间约束。相似地,在每个y1-y2平面上有13个顶点分别与13个特征值元组相对应。通过将每两个相邻顶点进行连接,可得到特征矩阵邻域空间的4维网格表示。

      图  3  特征矩阵邻域空间的四维网格

      Figure 3.  4 Demision Feature Matix Space

      在特征矩阵的4维网格表示中,任意两个相邻的矩阵之间的最短距离是1,两个矩阵之间最长的距离是16,在特征矩阵的概念空间中,矩阵之间越远,其方向差别越大。研究发现,两个矩阵方向差别与其4维网格中的最长距离成比例,因此两个矩阵方向之间的相似度可以表示为:

      $$ S\left( {{d_1},{d_2}} \right) = 1 - \frac{{D\left( {{F_1},{F_2}} \right)}}{{16}} $$ (6)

      其中,D(F1, F2)表示在4维网格表示中特征矩阵F1F2之间的距离。

    • 建立多洞面实体RnRm间的匹配关联图有两个步骤,其中与Rn对应的关联图G的节点集为{g1gn},与Rm对应的关联图H的节点集为{h1hm}。首先根据GH间的匹配关系生成关联图节点。若H的节点hj满足G的节点gi的约束,则创建节点aij(gi, hj)来描述这个对应关系。其次,根据洞之间的关系创建边来连接对应节点。使用边连接节点aij(gi, hj)和alk(gl, hk)。在两个洞的匹配方案中,某个带洞区的每个洞或方向关系在另一个带洞实体中只存在一个对应的洞或方向关系,满足一对一匹配的约束。

      假设多洞区RnRm间存在t对相匹配的洞,SHi为第i对洞的几何相似度,wHi为该洞对中参照洞的权重,通过累积所有洞对的几何相似度可得区RnRm的几何相似度Ss:

      $$ {S_s} = \frac{{\sum\limits_{i = 1}^t {{w_{{H_i}}} \cdot {S_{{H_i}}}} }}{{\sum\limits_{i = 1}^t {{w_{{H_i}}}} }} $$ (7)

      假设多洞区RnRm间存在t对相匹配的洞和t×(t-1)/2对匹配方向关系,SDi是第i对方向关系的方向相似度,wDi是与方向关系对应的参照洞的权重,通过累积所有方向关系相似度得到可得RnRm的方向相似度SD

      $$ {S_D} = \frac{{\sum\limits_{i = 1}^{t\left( {t - 1} \right)/2} {{w_{{D_i}}} \cdot {S_{{D_i}}}} }}{{\sum\limits_{i = 1}^{t\left( {t - 1} \right)/2} {{w_{{D_i}}}} }} $$ (8)

      假设形状和方向相似度的全局权重分别为wswD,基于洞的匹配情况可计算出多洞区RnRm的相似度S′:

      $$ {{S'}_{{R_n},{R_m}}} = \frac{{\left( {{w_s} \cdot {S_s}} \right) + \left( {{w_D} \cdot {S_D}} \right)}}{{{w_s} + {w_D}}} $$ (9)

      为了确保度量准确,还需考虑到RnRm间不匹配的洞对相似度所产生的影响,将此描述为洞的匹配完整度,并将其纳入到多洞面实体相似度的计算。

      匹配完整度SC是多洞区之间不匹配洞的比例函数,函数值属于区间[0, 1]。对于分别有nm个洞的多洞区RnRm,如果它们之间有t对匹配洞,并假设αβ分别为RnRm不匹配洞的权重,则匹配完整度的计算公式为:

      $$ {S_{C\left( {{R_n},{R_m}} \right)}} = \frac{t}{{t + \alpha \left( {n - t} \right) + \beta \left( {m - t} \right)}} $$ (10)

      在空间场景匹配对象的完整度计算中,为了实现不同的检索目的,权重αβ的设置存在3种方式:(1)α=β=1,两个场景间的不匹配对象具有相同的重要性;(2)α=β=0,忽略场景间的不匹配对象;(3)α=1,β=0,仅参照场景中的不匹配对象数量对匹配完整度计算存在影响。本文严格度量两个多洞面实体之间的相似度,即两个多洞实体中的不匹配洞具有同等重要性,α=β=1。通过匹配完整度可实现不匹配洞对多洞区相似性度量的影响。

      多洞区RnRm间的相似度函数由多洞实体之间的几何相似度、方向关系相似度及洞的匹配完整度组成。

      $$ {S_{{R_n},{R_m}}} = {{S'}_{{R_n},{R_m}}} \cdot \left( {{w_C} \cdot \left( {{S_C} - 1} \right) + 1} \right) $$ (11)

      式中, SRn, Rm为考虑到几何相似度和方向关系相似度的多洞面实体相似度;SC为多洞面实体之间的匹配完整度;wC为匹配完整度权重。两个多洞实体之间可能存在若干种匹配解决方案,通过计算及对不同解决方案的相似度进行排序,可得多洞区之间匹配方案的优先度。

    • 本文利用乌鲁米耶湖2010年与1985年的数据对所提出的相似性度量模型进行验证(见图 1)。本文将乌鲁米耶湖视为一个多洞实体,岛屿作为其中的洞,因此匹配问题转换为两个多洞实体之间的相似度计算。1985年的乌鲁米耶湖表现为多洞面实体Rm,而2010年的乌鲁米耶湖则表现为多洞面实体Rn。可以观察到,由于湖的缩减,Rm中的洞H5从区Rn中消失了。

    • 为了创建RnRm间匹配关联图的节点,本文利用多级弦长弯曲度计算每对洞之间的几何相似度。根据式(1)~(4)进行计算可得表 1,描述了RnRm的外边界及每对洞的几何相似度。

      图  4  乌鲁米耶湖

      Figure 4.  Lake Urmia

      表 1  RnRm外边界及每对洞的几何相似度

      Table 1.  Similarity of Outer andHoles of Rn and Rm

      em H1 H2 H3 H4 H5
      en 0.901 75
      H1 0.827 52 0.683 2 0.712 96 0.704 29 0.682 88
      H2 0.685 5 0.849 12 0.732 75 0.786 79 0.762 22
      H3 0.704 13 0.729 53 0.684 83 0.759 61 0.684 23
      H4 0.721 28 0.751 07 0.706 49 0.747 27 0.712 13

      关联图的构建始于在Rn中随机选择一个洞Hx,并从Rm中寻找其匹配洞。将H1作为检索的起始洞,并设检索洞的优先顺序为H2H3H4, 到目前为止可得RnRm间的匹配方案{(H1, H1), (H2, H2), (H3, H4), (H4, H5)}, 注意到本文并不考虑洞和外边界之间的方向。假设多洞实体中的每个洞都具有同等重要性,即Rn的洞在Rm中检索匹配对象的优先顺序是随机的,且不同的优先顺序会产生不同的匹配方案,清除重复后,6种可能的匹配方案及相应的关联图如图 5所示。

      图  5  匹配关联图

      Figure 5.  Assocaition Graph of Holes Matching

      在特征矩阵中,最小外包矩形之间的方向关系被分解为对应投影区间的区间约束。在图 6中,使用x-y平面来描述RnRm中的洞的最小外包矩形及投影区间端点。

      图  6  投影区间

      Figure 6.  Projection Interval

      每两个洞HAHB间存在方向关系,且HA相对于HB的方向不能简单地由HB相对于HA的方向推断而出。因此将每个洞都作为参照对象来分别计算方向特征矩阵,并得到表 2表 3

      表 2  对象A的方向矩阵

      Table 2.  Direction Matrix of Region A

      H1 H2 H3 H4
      H1 [(0, 0) (0, 2)]T [(2, 2) (2, 2)]T [(2, 2) (2, 2)]T
      H2 [(-2, 2) (-2, 0)]T [(0, 2) (2, 2)]T [(2, 2) (-1, 2)]T
      H3 [(-2, 2) (-2, -2)]T [(-2, 0) (-2, -2)]T [(-1, 2) (-2, -2)]T
      H4 [(-2, -2) (-2, -2)]T [(-2, -2) (-1, 0)]T [(-1, 0) (2, 2)]T

      表 3  对象B的方向矩阵

      Table 3.  Direction Matrix of Region B

      H1 H2 H3 H4 H5
      H1 [(0, 0) (0 2)] [(2, 2) (2, 2)] [(2, 2) (2, 2)] [(-2, -2) (2, 2)]
      H2 [(-2, 2) (-2, 0)] [(0, 2) (2, 2)] [(2, 2) (-2, 2)] [(1, 2) (-2, -2)]
      H3 [(-2, 2) (-2, -2)] [(-2, 0) (-2, -2)] [(0, 2) (-2, -2)] [(0, 2) (-2, -2)]
      H4 [(-2, -2) (-2, -2)] [(-2, -2) (0, 0)] [(-2, 0) (2, 2)] [(0, 0) (-2, -2)]
      H5 [(-2, -2) (2, 2)] [(-2, -1) (2, 2)] [(-2, 0) (2, 2)] [(-2, 2) (2, 2)]

      根据式(5)~(6)计算出洞对之间的几何及方向相似度,并在关联图的节点和边上附加相应的相似度值,解决方案1中的关联图如图 7(a)所示,其他方案的关联图如图 7(b)~7(f)所示。

      图  7  其余方案的关联图

      Figure 7.  Assocaition Graph of Other Solutions

      为了对匹配完整度进行精确度量,本文中的不匹配洞都拥有同等重要性,即式(1)~(2)中不匹配洞的权重αβ的值为1。由于匹配完整度只受到匹配和不匹配洞数量的影响,因此6种匹配方案中的RnRm的匹配完整度相等:

      $$ {S_{C\left( {{R_n},{R_m}} \right)}} = \frac{4}{{4 + \left( {4 - 4} \right) + \left( {5 - 4} \right)}} = 0.8 $$ (12)

      根据式(7)~(8),可以计算出每个匹配方案中形状和方向的总相似度。为了简化案例复杂度及增强可读性,本文将式(7)~(11)中的所有权重设为1。表 4描述了每个解决方案中的形状和方向相似度,基于每个解决方案中的形状和方向相似度及匹配完整度,通过计算可得6个方案的总体相似度。同时,对本文中提出的复杂多洞面实体相似性度量模型在计算几何相似度部分与同类算法中利用多级弦长弯曲度复函数的计算方法[27]进行了对比,计算结果列举在表 4中,从表 4中可以看出,在计算轮廓的相似度方面,本文模型与文献[27]基本一致。但由于本文重点解决的是复杂带洞面实体的相似度计算,解决问题的复杂度规模远远超过已有相关模型。

      表 4  解决方案的形状相似度和方向相似度

      Table 4.  Shape and Direction Similarity of Solutions

      解决方案 1 2 3 4 5 6
      形状相似度 0.787/0.751 0.777/0.731 0.775/0.728 0.762/0.720 0.739/0.711 0.76/0.721
      方向相似度 0.717 0.98 0.737 0.758 0.322 0.457
      综合相似度 0.752 0.879 0.756 0.76 0.53 0.508
      注:A/B中,A是本文方法结果,B为文献[27]结果

      通过表 4可以看出,RnRm间匹配方案的优先顺序为S2S4S3S1S6S5。方案S2具有最高的相似度,匹配的洞对分别为(H1H1)、(H2H2)、(H3H3)、(H4H4),洞H5Rn中没有匹配对象,因为其所在地在2010年已和陆地连为一体。在实际应用中,根据洞间的匹配顺序及每个方案的相似度,用户可以自行选择合适的解决方案。

    • 为解决多洞面实体之间的匹配问题,本文提出多洞面实体的相似性度量模型,将洞看作独立的空间对象实体,顾及洞之间的方向关系,洞的几何形状和洞之间的方向为约束条件,将复杂多洞面实体的相似性度量过程转变成一个满足约束条件问题,同时采用多级弦长弯曲度半径作为基本的形状描述子。在后续的研究中将着重于研究复杂面实体中单个实体的相对位置对匹配的影响,分析该模型的时间复杂度并得出相应的最佳方案,提高匹配的正确性和唯一性。

参考文献 (27)

目录

    /

    返回文章
    返回