A canonical time warping algorithm for building shape similarity measurement

doi:10.11947/j.AGCS.2023.20220539

Abstract

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

CLC Number:

P208

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.

References

[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.