典型时间规整算法支持下的建筑物形状相似性度量

doi:10.11947/j.AGCS.2023.20220539

测绘学报 ›› 2023, Vol. 52 ›› Issue (12): 2197-2208.doi: 10.11947/j.AGCS.2023.20220539

典型时间规整算法支持下的建筑物形状相似性度量

李精忠^1,2,3, 毛凯楠^2,3

1. 兰州交通大学测绘与地理信息学院, 甘肃兰州 730070;
2. 武汉大学资源与环境科学学院, 湖北武汉 430079;
3. 自然资源部城市国土资源监测与仿真重点实验室, 广东深圳 518000

收稿日期:2022-09-19 修回日期:2023-06-08 发布日期:2024-01-03
通讯作者: 毛凯楠 E-mail:maokainan@whu.edu.cn
作者简介:李精忠(1983-),男,博士,教授,研究方向为地图综合、空间分析与大数据挖掘。E-mail:00009232@whu.edu.cn
基金资助:
国家自然科学基金(42271454;42001402);湖北省自然科学基金(2022CFB053);自然资源部城市国土资源监测与仿真重点实验室开放基金(KF-2022-07-017);兰州交通大学研究生教育教学质量提升工程(JG202301);中国科学院数字地球重点实验室开放基金(2022LDE004)

A canonical time warping algorithm for building shape similarity measurement

LI Jingzhong^1,2,3, MAO Kainan^2,3

1. Faculty Geomatics, Lanzhou Jiaotong University, Lanzhou 730070, China;
2. School of Resource and Environmental Sciences, Wuhan University, Wuhan 430079, China;
3. Key Laboratory of Urban Land Resources Monitoring and Simulation, Ministry of Natural Resources, Shenzhen 518000, China

Received:2022-09-19 Revised:2023-06-08 Published:2024-01-03
Supported by:
The National Natural Science Foundation of China (Nos. 42271454;42001402);The Natural Science Foundation of Hubei Province (No. 2022CFB053);The Open Fund of Key Laboratory of Urban Land Resources Monitoring and Simulation,Ministry of Natural Resources (No. KF-2022-07-017);The Graduate Education Teaching Quality Improvement Project of Lanzhou Jiaotong University (No. JG202301);The Open Research Fund of Key Laboratory of Digital Earth Science, Chinese Academy of Sciences (No. 2022LDE004)

摘要/Abstract

摘要： 本文提出了一种基于典型时间规整(canonical time warping,CTW)算法的形状相似性度量模型,该模型运用动态时间规整(dynamic time warping,DTW)算法和典型相关分析(canonical correlation analysis,CCA),对齐具有不同节点个数的建筑物坐标序列,并综合评价不同形状轮廓之间的相似性。该方法直接以矢量坐标作为模型输入而无须复杂的形状编码,顾及了建筑物图形原始的轮廓特征,可高效地应用于形状检索等场景。试验表明,CTW算法在度量形状相似性时具有平移、旋转、缩放和镜像不变性,能有效度量建筑物形状之间的形状相似性,其结果符合人类的空间视觉认知。

关键词: 建筑物, 形状相似性, 典型时间规整, 空间认知

Abstract: This paper proposes a shape similarity measurement model based on canonical time warping (CTW) algorithm. The model combines canonical correlation analysis (CCA) and dynamic time warping (DTW) to align building coordinate sequences with different number of vertices, which can comprehensively evaluate the shape similarity between different shape contours. This method directly uses vector coordinates as model input without constructing complex shape coding and considers the original contour features of building shapes, which can be applied efficiently to shape retrieval and other scenarios. Experiments show that CTW algorithm is invariant to translation, rotation, scaling and mirroring when used to measure the similarity of geometric objects, and can effectively measure the shape similarity between building shapes. The results are consistent with human spatial visual cognition.

Key words: buildings, shape similarity, canonical time warping, spatial cognition

中图分类号:

P208

李精忠, 毛凯楠. 典型时间规整算法支持下的建筑物形状相似性度量[J]. 测绘学报, 2023, 52(12): 2197-2208.

LI Jingzhong, MAO Kainan. A canonical time warping algorithm for building shape similarity measurement[J]. Acta Geodaetica et Cartographica Sinica, 2023, 52(12): 2197-2208.

参考文献

[1] 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.
[2] 帅赟, 艾廷华, 帅海燕, 等. 基于形状模板匹配的多边形查询[J]. 武汉大学学报(信息科学版), 2008, 33(12): 1267-1270. SHUAI Yun, AI Tinghua, SHUAI Haiyan, et al. Poly-gonal inquiry based on shape template matching[J]. Geomatics and Information Science of Wuhan University, 2008,33(12): 1267-1270.
[3] 孟妮娜, 艾廷华, 周校东. 建筑群邻近关系相似性计算[J]. 武汉大学学报(信息科学版), 2012, 37(7): 775-779. MENG Nina, AI Tinghua, ZHOU Xiaodong. Similarity calculation of adjacency relation for building group[J]. Geomatics and Information Science of Wuhan University, 2012, 37(7): 775-779.
[4] 行瑞星, 武芳, 巩现勇, 等. 建筑群组合直线模式识别的模板匹配方法[J]. 测绘学报, 2021, 50(6): 800-811. DOI: 10.11947/j.AGCS.2021.20200298. XING Ruixing, WU Fang, GONG Xianyong, et al. The template matching approach to combined collinear pattern recognition in building groups[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(6): 800-811. DOI: 10.11947/j.AGCS.2021.20200298.
[5] 高晓蓉, 闫浩文, 禄小敏. 多尺度地图空间居民地语义相似度计算方法[J]. 测绘学报, 2022, 51(1): 95-103. DOI: 10.11947/j.AGCS.2022.20210074. GAO Xiaorong, YAN Haowen, LU Xiaomin. Semantic similarity measurement for building polygon aggregation in multi-scale map space[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(1): 95-103. DOI: 10.11947/j.AGCS.2022.20210074.
[6] 晏雄锋, 袁拓, 杨敏, 等. 建筑物形状特征分析表达与自适应化简方法[J]. 测绘学报, 2022, 51(2): 269-278. DOI: 10.11947/j.AGCS.2022.20210302. YAN Xiongfeng, YUAN Tuo, YANG Min, et al. An adaptive building simplification approach based on shape analysis and representation[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(2): 269-278. DOI: 10.11947/j.AGCS.2022.20210302.
[7] FAN Hongchao, ZHAO Zhiyao, LI Wenwen. Towards measuring shape similarity of polygons based on multiscale features and grid context descriptors[J]. ISPRS International Journal of Geo-Information, 2021, 10(5): 279.
[8] 魏智威, 郭庆胜, 程璐, 等. 建筑物图形形状相似性计算的序列分析法[J]. 测绘学报, 2021, 50(12): 1683-1693. DOI: 10.11947/j.AGCS.2021.20200227. WEI Zhiwei, GUO Qingsheng, CHENG Lu, et al. Shape similarity measurement based on DNA alignment for buildings with multiple orthogonal features[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(12): 1683-1693. DOI: 10.11947/j.AGCS.2021.20200227.
[9] LU Guojun, SAJJANHAR A. Region-based shape representation and similarity measure suitable for content-based image retrieval[J]. Multimedia Systems, 1999, 7(2): 165-174.
[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] 郑伟, 于洋, 刘砚菊. 骨架形状特征的目标识别算法[J]. 沈阳理工大学学报, 2022, 41(1): 14-19. ZHENG Wei, YU Yang, LIU Yanju. Target recognition algorithm based on skeleton shape features[J]. Journal of Shenyang Ligong University, 2022, 41(1): 14-19.
[12] BAI Xiang, LATECKI L J. Path similarity skeleton graph matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(7): 1282-1292.
[13] ASLAN C, ERDEM A, ERDEM E, et al. Disconnected skeleton: shape at its absolute scale[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(12): 2188-2203.
[14] 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.
[15] LU Guojun. Chain code-based shape representation and similarity measure[M]//Visual Information Systems. Berlin: Springer, 1997: 135-150.
[16] 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.
[17] PENG Shaohu, KIM D H, LEE S L, et al. A visual shape descriptor using sectors and shape context of contour lines[J]. Information Sciences, 2010, 180(16): 2925-2939.
[18] SHU Xin, WU Xiaojun. A novel contour descriptor for 2D shape matching and its application to image retrieval[J]. Image and Vision Computing, 2011, 29(4): 286-294.
[19] GUO Wenyue, YU Anzhu, SUN Qun, et al. A multisource contour matching method considering the similarity of geometric features[J]. Journal of Geodesy and Geoinformation Science, 2020, 3(3): 76-87.
[20] DENG Min, LI Zhilin, CHU Xiaoyong. Extended Hausdorff distance for spatial objects in GIS[J]. International Journal of Geographical Information Science, 2007, 21(4): 459-475.
[21] 陈占龙, 周林, 龚希, 等. 基于方向关系矩阵的空间方向相似性定量计算方法[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.
[22] 龚希, 谢忠, 周林, 等. 空间方向相似性二元组模型度量方法[J]. 测绘学报, 2021, 50(12): 1705-1716. DOI: 10.11947/j.AGCS.2021.20200361. GONG Xi, XIE Zhong, ZHOU Lin, et al. A two-tuple model based spatial direction similarity measurement method[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(12): 1705-1716. DOI: 10.11947/j.AGCS.2021.20200361.
[23] XU Yongyang, XIE Zhong, CHEN Zhanlong, et al. Measuring the similarity between multipolygons using convex hulls and position graphs[J]. International Journal of Geographical Information Science, 2021, 35(5): 847-868.
[24] 程绵绵, 孙群, 徐立, 等. 面轮廓线相似性和复杂性度量及在化简中的应用[J]. 测绘学报, 2019, 48(4): 489-501. DOI: 10.11947/j.AGCS.2019.20180124. CHENG Mianmian, SUN Qun, XU Li, et al. Polygon contour similarity and complexity measurement and application in simplification[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(4): 489-501. DOI: 10.11947/j.AGCS.2019.20180124.
[25] 刘鹏程, 黄欣, 马宏然, 等. 建筑物多边形高精度识别的傅里叶形状描述子神经网络方法[J]. 测绘学报, 2022, 51(9): 1969-1976. DOI: 10.11947/j.AGCS.2022.20210730. LIU Pengcheng, HUANG Xin, MA Hongran, et al. Fourier descriptor-based neural network method for high-precision shape recognition of building polygon[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(9): 1969-1976. DOI: 10.11947/j.AGCS.2022.20210730.
[26] 晏雄锋, 艾廷华, 杨敏. 居民地要素化简的形状识别与模板匹配方法[J]. 测绘学报, 2016, 45(7): 874-882. DOI: 10.11947/j.AGCS.2016.20150162. YAN Xiongfeng, Al 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.
[27] ZHOU Feng, DE LA TORRE F. Canonical time warping for alignment of human behavior[C]//Proceedings of 2009 International Conference on Neural Information Processing Systems. New York: ACM Press, 2009: 2286-2294.
[28] Wolfram Language & System Documentation Center. Canonical warping distance[EB/OL]. [2022-09-18]. https://reference.wolfram.com/language/ref/CanonicalWarpingDistance.html.
[29] YUAN Wei, XIAO Qinkun, LI Liqin. Gait recognition based on Fourier descriptors and canonical time warping[C]//Proceedings of 2015 International Symposium on Computational Intelligence and Design. Hangzhou: IEEE, 2015: 64-67.
[30] ZHOU Feng, DE LA TORRE F. Generalized canonical time warping[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016, 38(2): 279-294.
[31] CARDARILLI G C, DI NUNZIO L, FAZZOLARI R, et al. N-dimensional approximation of Euclidean distance[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2020, 67(3): 565-569.
[32] TRIGEORGIS G, NICOLAOU M A, SCHULLER B W, et al. Deep canonical time warping for simultaneous alignment and representation learning of sequences[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018, 40(5): 1128-1138.
[33] MENG Liting, SUN Yan, ZHAO Shuqing. Comparing the spatial and temporal dynamics of urban expansion in Guangzhou and Shenzhen from 1975 to 2015: a case study of pioneer cities in China’s rapid urbanization[J]. Land Use Policy, 2020, 97: 104753.
[34] 郭庆胜, 黄远林, 郑春燕, 等. 空间推理与渐进式地图综合[M]. 武汉: 武汉大学出版社, 2007. GUO Qingsheng, HUANG Yuanlin, ZHENG Chunyan, et al. Spatial reasoning and progressive map generalization [M]. Wuhan: Wuhan University Press, 2007.

典型时间规整算法支持下的建筑物形状相似性度量

A canonical time warping algorithm for building shape similarity measurement

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	江宝得, 黄威, 许少芬, 巫勇. 融合分散自适应注意力机制的多尺度遥感影像建筑物实例细化提取[J]. 测绘学报, 2023, 52(9): 1504-1514.
[2]	程昫, 葛亮, 张帆, 黄先锋. 倾斜摄影建筑物模型自动纹理重建[J]. 测绘学报, 2023, 52(9): 1528-1537.
[3]	安晓亚, 朱余德, 晏雄锋. 卷积神经网络支持下的建筑物选取方法[J]. 测绘学报, 2023, 52(9): 1574-1583.
[4]	刘昌振, 马威, 马红, 魏世轩. 建筑物轮廓方向计算和规则化的向量重组算法[J]. 测绘学报, 2023, 52(9): 1584-1594.
[5]	魏智威, 肖屹, 童莹, 许文嘉, 王洋. 基于知识图谱的直线型建筑物模式识别方法[J]. 测绘学报, 2023, 52(8): 1355-1363.
[6]	胡明洪, 李佳田, 姚彦吉, 阿晓荟, 陆美, 李文. 结合多路径的高分辨率遥感影像建筑物提取SER-UNet算法[J]. 测绘学报, 2023, 52(5): 808-817.
[7]	李华蓉, 郑嘉欣, 李天童. 室内POI显著度评价的Fisher判别法模型[J]. 测绘学报, 2023, 52(4): 679-688.
[8]	魏智威, 丁愫, 童莹, 程璐, 刘洋. 格式塔原则与图形凸分解结合的建筑物群直线模式识别方法[J]. 测绘学报, 2023, 52(1): 117-128.
[9]	何直蒙, 丁海勇, 安炳琪. 高分辨率遥感影像建筑物提取的空洞卷积E-Unet算法[J]. 测绘学报, 2022, 51(3): 457-467.
[10]	葛小三, 陈曦, 赵文智, 李瑞祥. 基于生成对抗网络的建筑物损毁检测[J]. 测绘学报, 2022, 51(2): 238-247.
[11]	晏雄锋, 袁拓, 杨敏, 孔博, 刘鹏程. 建筑物形状特征分析表达与自适应化简方法[J]. 测绘学报, 2022, 51(2): 269-278.
[12]	陈占龙, 李双江, 徐永洋, 徐道柱, 马超, 赵军利. 高分影像密集建筑物Correg-YOLOv3检测方法[J]. 测绘学报, 2022, 51(12): 2531-2540.
[13]	张玉鑫, 颜青松, 邓非. 高分辨率遥感影像建筑物提取多路径RSU网络法[J]. 测绘学报, 2022, 51(1): 135-144.
[14]	高俊, 曹雪峰. 空间认知推动地图学学科发展的新方向[J]. 测绘学报, 2021, 50(6): 711-725.
[15]	万刚, 武易天. 地图空间认知的数学基础[J]. 测绘学报, 2021, 50(6): 726-738.