建筑物图形形状相似性计算的序列分析法

doi:10.11947/j.AGCS.2021.20200227

测绘学报 ›› 2021, Vol. 50 ›› Issue (12): 1683-1693.doi: 10.11947/j.AGCS.2021.20200227

• 位置服务与地理空间信息处理 • 上一篇下一篇

建筑物图形形状相似性计算的序列分析法

魏智威^1,2, 郭庆胜^3,4, 程璐³, 刘洋³, 童莹³

1. 中国科学院网络信息体系技术重点实验室, 北京 100830;
2. 中国科学院空天信息创新研究院, 北京 100830;
3. 武汉大学资源与环境科学学院, 湖北武汉 430079;
4. 武汉大学测绘遥感信息工程国家重点实验室, 湖北武汉 430079

收稿日期:2020-06-08 修回日期:2021-01-14 发布日期:2022-01-08
通讯作者: 郭庆胜 E-mail:guoqingsheng@whu.edu.cn
作者简介:魏智威(1993—),男,博士,研究方向为地理信息智能化处理与可视化。
基金资助:
国家自然科学基金（41871378）

Shape similarity measurement based on DNA alignment for buildings with multiple orthogonal features

WEI Zhiwei^1,2, GUO Qingsheng^3,4, CHENG Lu³, LIU Yang³, TONG Ying³

1. Key Laboratory of Network Information System Technology, Institute of Electronic, Chinese Academy of Sciences, Beijing 100830, China;
2. The Aerospace Information Research Institute, Chinese Academic of Sciences, Beijing 100830, China;
3. School of Resources and Environment Science, Wuhan University, Wuhan 430079, China;
4. State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China

Received:2020-06-08 Revised:2021-01-14 Published:2022-01-08
Supported by:
The National Natural Science Foundation of China (No. 41871378)

摘要/Abstract

摘要： 建筑物图形形状相似性能有效用于建筑物匹配、分类和查询等。基于DNA序列比对的Needleman-Wunsch（NW）算法和Smith-Waterman（SW）算法，本文提出一种度量多直角建筑物图形形状相似性的方法。本文方法顾及建筑物图形多直角表达的形态特征，将邻近两个转折作为建筑物图形编码序列的基础元素，并基于这些基础元素的类型、角度和长度特征定义基础元素间相似性；其次，利用NW算法和SW算法计算建筑物图形编码序列间的相似程度，该相似程度表达了对应建筑物图形间的形状相似性。基于形状的空间查询试验结果表明，本文方法能有效度量多直角建筑物图形间的形状相似性，符合人的空间视觉认知。

关键词: 建筑物, 形状相似性, 空间认知, 序列分析

Abstract: Shape similarity between buildings is useful for building matching, classification, retrieval, etc. As buildings tend to be designed with square angles, we proposed a method to measure shape similarity for buildings with multiple orthogonal features based on Needleman-Wunsch (NW) and Smith-Waterman (SW) algorithms. While encoding building shape into a sequence, adjacent two angles are taken as codes. Type, angle and length characteristics of the codes are described, and their similarity are then defined. NW and SW algorithms are applied to compute similarities between two encoding sequences of buildings. Shape-based query experiments show that proposed method in this paper can effectively measure the shape similarity between buildings. And the experimental results are also in line with human visual perception.

Key words: buildings, shape similarity, spatial cognition, sequence analysis

中图分类号:

P208

魏智威, 郭庆胜, 程璐, 刘洋, 童莹. 建筑物图形形状相似性计算的序列分析法[J]. 测绘学报, 2021, 50(12): 1683-1693.

WEI Zhiwei, GUO Qingsheng, CHENG Lu, LIU Yang, TONG Ying. Shape similarity measurement based on DNA alignment for buildings with multiple orthogonal features[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(12): 1683-1693.

参考文献

[1] VELTKAMP R C. Shape matching:similarity measures and algorithms[C]//Proceedings of 2001 International Conference on Shape Modeling and Applications. Genova, Italy:IEEE, 2001:188-197.
[2] 付仲良,逯跃锋.利用弯曲度半径复函数构建综合面实体相似度模型[J].测绘学报, 2013, 42(1):145-151. FU Zhongliang, LU Yuefeng. Establishment of the comprehensive model for similarity of polygon entity by using bending radius complex function[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(1):145-151.
[3] 晏雄锋,艾廷华,杨敏.居民地要素化简的形状识别与模板匹配方法[J].测绘学报, 2016, 45(7):874-882. DOI:10.11947/j.AGCS.2016.20150162. YAN Xiongfeng, AI Tinghua, YANG Min. A simplification of residential feature by the shape cognition and template matching method[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(7):874-882. DOI:10.11947/j.AGCS.2016.20150162.
[4] 艾廷华,帅赟,李精忠.基于形状相似性识别的空间查询[J].测绘学报, 2009, 38(4):356-362. DOI:10.3321/j.issn:1001-1595.2009.04.012. AI Tinghua, SHUAI Yun, LI Jingzhong. A spatial query based on shape similarity cognition[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(4):356-362. DOI:10.3321/j.issn:1001-1595. 2009. 04. 012.
[5] 安晓亚,刘平芝,金澄,等.手绘地图开域空间方向关系检索法[J].测绘学报, 2017, 46(11):1899-1909. DOI:10.11947/j.AGCS.2017.20170001. AN Xiaoya, LIU Pingzhi, JIN Cheng, et al. A hand-drawn map retrieval method based on open area spatial direction relation[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(11):1899-1909. DOI:10.11947/j.AGCS.2017.20170001.
[6] AI Tinghua, CHENG Xiaoqiang, LIU Pengcheng, et al. A shape analysis and template matching of building features by the Fourier transform method[J]. Computers, Environment and Urban Systems, 2013, 41:219-233.
[7] 王斌.一种基于多级弦长函数的傅立叶形状描述子[J].计算机学报, 2010, 33(12):2387-2396. WANG Bin. A Fourier shape descriptor based on multi-level chord length function[J]. Chinese Journal of Computers, 2010, 33(12):2387-2396.
[8] ZHANG Dengsheng, LU Guojun. A comparative study of curvature scale space and Fourier descriptors for shape-based image retrieval[J]. Journal of Visual Communication and Image Representation, 2003, 14(1):39-57.
[9] ARKIN E M, CHEW L P, HUTTENLOCHER D P, et al. An efficiently computable metric for comparing polygonal shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1991, 13(3):209-216.
[10] FU Zhongliang, FAN Liang, YU Zhiqiang, et al. A moment-based shape similarity measurement for areal entities in geographical vector data[J]. ISPRS International Journal of Geo-Information, 2018, 7(6):208.
[11] WEI Zhiwei, GUO Qingsheng, WANG Lin, et al. On the spatial distribution of buildings for map generalization[J]. Cartography and Geographic Information Science, 2018, 45(6):539-555.
[12] BAI Xiang, JAN LATECKI L. Path similarity skeleton graph matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(7):1282-1292.
[13] BELONGIE S, MALIK J, PUZICHA J. Shape matching and object recognition using shape contexts[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(4):509-522.
[14] XU Chunjing, LIU Jianzhuang, TANG Xiaoou. 2D shape matching by contour flexibility[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(1):180-186.
[15] WANG Junwei, BAI Xiang, YOU Xinge, et al. Shape matching and classification using height functions[J]. Pattern Recognition Letters, 2012, 33(2):134-143.
[16] CHEN Longbin, FERIS R, TURK M. Efficient partial shape matching using Smith-Waterman algorithm[C]//Proceedings of 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops. Anchorage, AK:IEEE, 2008.
[17] 危辉,李俐瑢.拱序列的曲线描述与匹配[J].中国图象图形学报, 2017, 22(8):1045-1055. WEI Hui, LI Lirong. Curve description and matching using arch sequence[J]. Journal of Image and Graphics, 2017, 22(8):1045-1055.
[18] MOUNT D W. Bioinformatics:sequence and genome analysis[M].2nd ed. New York:Cold Spring Harbor Press, 2004.
[19] 郭庆胜.以直角方式转折的面状要素图形简化方法[J].武汉测绘科技大学学报, 1999, 24(3):255-258. GUO Qingsheng. The method of graphic simplification of area feature boundary as right angle[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1999, 24(3):255-258.
[20] 郭庆胜,黄远林,郑春燕,等.空间推理与渐进式地图综合[M].武汉:武汉大学出版社, 2007. GUO Qingsheng, HUANG Yuanlin, ZHENG Chunyan, et al. Spatial reasoning and progressive map generalization[M]. Wuhan:Wuhan University Press, 2007.
[21] 许文帅,龙毅,周侗,等.基于邻近四点法的建筑物多边形化简[J].测绘学报, 2013, 42(6):929-936. XU Wenshuai, LONG Yi, ZHOU Tong, et al. Simplification of building polygon based on adjacent four-point method[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(6):929-936.
[22] 陈文瀚,龙毅,沈婕,等.利用约束D-TIN进行建筑物多边形凹部结构识别与渐进式化简[J].武汉大学学报(信息科学版), 2011, 36(5):584-587, 592. CHEN Wenhan, LONG Yi, SHEN Jie, et al. Structure recognition and progressive simplification of the concaves of building polygon based on constrained D-Tin[J]. Geomatics and Information Science of Wuhan University, 2011, 36(5):584-587, 592.
[23] SESTER M. Optimization approaches for generalization and data abstraction[J]. International Journal of Geographical Information Science, 2005, 19(8-9):871-897.
[24] 苏为华.多指标综合评价理论与方法问题研究[D].厦门:厦门大学, 2000. SU Weihua. Research on multiple-objective-comprehensive-evaluation[D]. Xiamen:Xiamen University, 2000.
[25] HU Rongxiang, JIA Wei, ZHAO Yang, et al. Perceptually motivated morphological strategies for shape retrieval[J]. Pattern Recognition, 2012, 45(9):3222-3230.
[26] YAN Haowen, WEIBEL R, YANG Bisheng. A multi-parameter approach to automated building grouping and generalization[J]. Geoinformatica, 2008, 12(1):73-89.

建筑物图形形状相似性计算的序列分析法

Shape similarity measurement based on DNA alignment for buildings with multiple orthogonal features

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	何直蒙, 丁海勇, 安炳琪. 高分辨率遥感影像建筑物提取的空洞卷积E-Unet算法[J]. 测绘学报, 2022, 51(3): 457-467.
[2]	葛小三, 陈曦, 赵文智, 李瑞祥. 基于生成对抗网络的建筑物损毁检测[J]. 测绘学报, 2022, 51(2): 238-247.
[3]	晏雄锋, 袁拓, 杨敏, 孔博, 刘鹏程. 建筑物形状特征分析表达与自适应化简方法[J]. 测绘学报, 2022, 51(2): 269-278.
[4]	张玉鑫, 颜青松, 邓非. 高分辨率遥感影像建筑物提取多路径RSU网络法[J]. 测绘学报, 2022, 51(1): 135-144.
[5]	高俊, 曹雪峰. 空间认知推动地图学学科发展的新方向[J]. 测绘学报, 2021, 50(6): 711-725.
[6]	万刚, 武易天. 地图空间认知的数学基础[J]. 测绘学报, 2021, 50(6): 726-738.
[7]	应申, 张雯博, 苏俊如, 黄丽娜. 地球球观认知分析:以谷歌地球上的寻路任务为例[J]. 测绘学报, 2021, 50(6): 739-748.
[8]	晏雄锋, 艾廷华, 杨敏, 郑建滨. 地图空间形状认知的自编码器深度学习方法[J]. 测绘学报, 2021, 50(6): 757-765.
[9]	郑束蕾. 地理空间认知理论与地图工具的发展[J]. 测绘学报, 2021, 50(6): 766-776.
[10]	刘远刚, 李少华, 蔡永香, 何贞铭, 马潇雅, 李鹏程, 郭庆胜, 何宗宜. 移位安全区约束下的建筑物群移位免疫遗传算法[J]. 测绘学报, 2021, 50(6): 812-822.
[11]	巩丹超, 韩轶龙, 黄旭. 线特征约束的建筑物密集匹配边缘全局优化方法[J]. 测绘学报, 2021, 50(6): 833-846.
[12]	王永君, 陈青燕, 杨玉娇, 陈学业, 孙剑. 语义辅助的CityGML模型一致性检测方法[J]. 测绘学报, 2021, 50(5): 664-674.
[13]	黄丽娜, 张定娆, 应申, 艾廷华. 桌面式虚拟环境与真实环境中个体特征影响空间认知能力的差异分析[J]. 测绘学报, 2021, 50(4): 509-521.
[14]	王昶, 张永生, 纪松, 张磊. 建筑物变化的多特征融和及随机多图综合检测法[J]. 测绘学报, 2021, 50(2): 235-247.
[15]	王勇, 罗安, 王慧慧, 曹元晖, 刘纪平. 复杂建筑物最短邻近线多边形聚合法[J]. 测绘学报, 2021, 50(12): 1671-1682.