Measuring the similarity between shapes of buildings using graph edit distance

• Published in: International journal of digital earth 2024-12, Vol.17 (1)
• Main Authors: Lu, Xiechun, Li, Houpu, Xu, Yongyang, Liu, Jiangwen, Chen, Zhanlong
• Format: Article
• Language: English
• Subjects: Building Data; Geometric Similarity Measurement; Graph Edit Distance; Shape Cognition
• ISSN: 1753-8947; 1753-8955
• DOI: 10.1080/17538947.2024.2310749

ABSTRACTBuilding data play a crucial role in geographic information science, and building shape similarity can be used for spatial inquiry, cartographic generalization, map updating, data quality assessment, and other spatial data mining applications. However, conventional shape representation and measurement methods use geometric and statistical measures and may not effectively capture the subtle differences among building shapes. Geospatial artificial intelligence methods often overlook nuanced differences in building contours, posing a challenge when precise fine-grained measurements are required. Furthermore, they have low interpretability. This study proposes a graph edit distance-based method for measuring the similarity between building shapes. It uses geometrics characteristics to construct a graph, matches and associates similar regional features between two building contours, and defines edit costs based on geometric and positional differences that align with the Gestalt principle of visual similarity. It converts the optimal edit path problem to the maximum weighted cluster solution problem and utilizes a heuristic approach to achieve the exact optimal solution within a moderately suitable timeframe. The experimental results demonstrated that the proposed method identifies detailed differences between building contours, providing accurate similarity measurement with high interpretability.