Measuring the similarity between shapes of buildings using graph edit distance

ABSTRACT

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

KEYWORDS:

• Geometric Similarity Measurement
• Shape Cognition
• Graph Edit Distance
• Building Data

1. Introduction

Similarity measurement is a central construct in human cognition (Medin, Goldstone, and Gentner 1993). Humans use similarity to store and retrieve information and compare different entities. With rapid advancements in spatial information data acquisition technologies, similarity measurement techniques are being widely used in geographic information systems (GIS), especially for data retrieval (Ai et al. 2013), cartographic generalization (Yan 2015; Yan, Ai, and Zhang 2017), and map updating (Yang et al. 2018).

Building data play a crucial role in spatial analyses (Biljecki et al. 2021). Measuring and analyzing buildings provide theoretical foundations and guidance on urban development planning (Rehan 2014), statistical prediction of anthropogenic activities (Ma et al. 2019), map navigation (Zhang et al. 2013), and other spatial data mining applications (Du, Shu, and Feng 2016; He et al. 2020). Compared with natural objects, building possess distinct visual characteristics (such as orthogonality, symmetry, regionality, and pattern). Thus, shape similarity is more commonly used for matching, retrieving, and updating building data instead of semantic (Schwering 2008; Ballatore, Wilson, and Bertolotto 2013) or topological similarity, (Chen, Xu, and Wu 2015).

Conventional shape representation methods primarily use region- or contour-based approaches to describe shapes. However, these methods, which use geometric and statistical measures, may not effectively capture subtle differences among different building shapes. In recent years, emerging geospatial artificial intelligence (GeoAI) methods, particularly graphs neural networks (GNN), have substantially improved both accuracy and efficiency of algorithm in shape coding. However, these methods may not consider detailed contour information in complex building contours, leading to limitations in tasks that require fine-grained similarity measurements, such as map quality evaluation (Fan et al. 2014; Xu et al. 2017a). In additionally, measuring shape similarity using GNN has low interpretability.

This study proposes a novel method for measuring shape similarity based on the graph edit distance (GED) method, which provides accurate and highly interpretable measurements of shape similarity. The proposed method transforms a building contour into a graph model and defines the edit costs among primitives based on geometric and positional differences. It simplifies optimal edit path determination and uses a heuristic approach to achieve an exact optimal solution instead of an approximate one within a moderately suitable timeframe, ensuring that the edit costs of the optimal edit path accurately describe the differences between two shapes of different objects, which can further reflect shape similarity. During the determination of the optimal edit path, the algorithm associates primitives with visual similarities in the two building contours, which aligns with the Gestalt principle of visual similarity (Yu et al. 2014; Cetinkaya, Basaraner, and Burghardt 2015; Xu et al. 2017b). The edit costs between two matched primitives intuitively reflect their visual differences, thus demonstrating the high interpretability of the proposed method.

The remaining study can be categorized as follows. Section 2 briefly reviews studies on shape representation and similarity measurements. Section 3 elaborates on the proposed methods. Section 4 presents the experiments and compares the proposed method with other popular methods. Section 5 analyzes the interpretability of the proposed method, addresses its current limitations, and provides a potential improvement in its approach. Finally, Section 6 concludes the paper with a with suggestions for future research.

2. Related work

2.1. Conventional building shape representation and similarity measurement methods

Conventional techniques for shape representation can be categorized into two groups: contour- and region-based methods (Zhang and Lu 2004). This classification is based on whether the shape attributes are extracted from contours or the entire shape region.

Region-based methods use all pixels or grid within a shape region to obtain shape representation, such as describe shapes (Teague 1980), shape matrices (Goshtasby 1985), convex hulls (Hu 1962), media axes (Pavlidis 1980), reversed sketches (Huang et al. 2018), and the multiscale features & grid context descriptors (Fan, Zhao, and Li 2021). However, these representation methods encounter frequent challenges during building shape measurements because humans assess the similarity among building shapes primarily by their contour features rather than interior features (Zhang and Lu 2004). Furthermore, building shapes are commonly stored as vector data in maps and align easily using contour-based representation methods.

Contour-based techniques can be further categorized into global and structural approaches. Global contour techniques typically compute multidimensional numeric feature vectors using shape boundary information, such as shape signatures (Zhang and Lu 2002), boundary moments (Sonka, Hlavac, and Boyle 1993; Fu et al. 2018), Fourier descriptor (Ai et al. 2013; Chen, Feng, and Wu 2015) and triangle area representation (Yang, Wei, and Yu 2018). Matching among different shapes is a straightforward process. It is usually performed to measure distance using a metric distance, such as Euclidean (Danielsson 1980) or Hausdorff (Huttenlocher, Klanderman, and Rucklidge 1993) distance. Structural contour techniques break shapes into boundary segments, which have different procedures for selecting and organizing primitives to describe shapes among different priorities. This design performs partial matching without an exact difference measurement. Examples of these techniques include the chain-code histogram (Iivarinen and Visa 1996), chain of vectors (Mehrotra and Gary 1995), turning function (Arkin et al. 1991), curvature decomposition and curve fitting (Pavlidis 2012).

Generally, both global and structural methods are useful in partial inquiry or matching and can be combined to improve performance (Chen et al. 2021; Xu et al. 2021). However, both methods have some limitations. Global approaches typically omit detailed information. For example, a compact description is a prior option when using Fourier method, but this description provides inaccurate detailed information, especially when describing the corner points of building contours, which are vital in visual cognition. Therefore, they must be combined with other descriptors to create practical shape descriptors for obtaining detailed information (Chen et al. 2019; Xu et al. 2017b). In contrast, structural approaches analyze detailed information and enable partial matching between primitives of shapes, but their computational process is more complex because of the intricate matching in the calculation process. Most structural approaches use sub-graph matching to find an optimal solution, which is often impractical because of its high computational cost. Therefore, most methods seek an approximate solution instead of an exact solution to obtain high efficiency, which may not always guarantee the best match.

2.2. Building shape similarity measurement using GeoAI-based methods

Deep learning technology has opened new possibilities for studying GeoAI-based methods. In geoscience, GeoAI-based methods are being used to extract geographical features and recognize real geographical entities (Steiniger et al. 2008; García Balboa and Ariza López 2008; Ma et al. 2016; Touya and Dumont 2017; Sester, Feng, and Thiemann 2018; Courtial et al. 2020; Du et al. 2022a). Studies have demonstrated the potential of GNNs in shape representation and similarity measurement (Yan and Yang 2022; Yu et al. 2023), shape simplification (Liu et al. 2021; Du et al. 2022b; Zhou, Fu, and Weibel 2023), geographic entities selection (Zheng et al. 2021) and patterns classification (Yan et al. 2019; Hu et al. 2022; Li, Yan, and Lu 2023a). The maturity of the GNN technology has bridged the gap between deep learning and vector data and forged a new path for shape representation and similarity measurement.

However, two potential issues need to be addressed in current GeoAI-based methods. First, representing shape from the vector data to graphs should be careful and delicate because these predefined features primarily determine the quality of the results. In most studies on building shape coding using GNN (Yan et al. 2021; Liu et al. 2021; Hu et al. 2022), fixed number of vertices are selected along the boundary, which is slightly hasty and may cause the loss of delicate information regarding the building contour nodes. These limitations maybe owing to the nascent stage of early GNN technologies and the lack of guidance from classical methods that rely on graph model representations. Second, the GNN has a low interpretability during the extraction of shape features, particularly during the graph spectral convolution approach (Shuman, Ricaud, and Vandergheynst 2016), which is not conducive to identifying potential problems in the network and makes improving the robustness of the model difficult.

3. Method

This study proposes a graph-based shape representation method that describes building shapes by extracting the regional characteristics of building contours. It breaks the shape boundary into segments as vertices of a graph to construct primitives using regional geometry characteristics. This method defines the edit costs between primitives of two building shapes based on geometric and positional differences and uses a heuristic approach to obtain the optimal edit path that minimizes the total edit cost. This cost represents the difference between two building shapes and can reflect shape similarity. The smaller the shape difference, the more similar the shapes are.

3.1. Similarity measurement between graphs using GED

GED is a powerful method for graph matching and similarity measurement (Bunke and Allermann 1983; Sanfeliu and Fu 1983). Owing to its exceptional error-tolerance performance and applicability to a wide class of graphs, it is one of the most mainstream graph similarity comparison methods that is being widely used in pattern analysis and recognition (Gao et al. 2010), such as biometric identification (Lajevardi et al. 2013), cancerous tissue detection (Ozdemir and Gunduz-Demir 2013), handwriting recognition (Fischer et al. 2013), scenario retrieval (Wessel et al. 2011) and and a few applications in the geosciences field, primarily for road network (Liu et al. 2015) and trajectory matching (Koide, Xiao, and Ishikawa 2020).

GED is an extension of the well-known string edit distance (Wagner and Fischer 1974) to the domain of graphs. It uses a set of graph-editing operations to transform one graph into another. The cost of each operation is determined by a cost function, which depends on the current edit operation. The total cost of the set represents the distance between the two graphs. The larger the distance, the greater the difference and the lower the similarity.

Given a graph $G=(V,E,L_V,L_E)$, where $V$ is a set of vertices and $E$ is a set of edges such as $E\in V\times V$. $L_V$ and $L_E$ are label sets of graph vertices and edges, respectively, recording the categories or attributes of vertices and edges. There are three basic operations for graph editing: insertion, deletion, and substitution for vertices and edges. Let $u$ and $v$ be two different vertices. If $\epsilon$ indicates no vertex; then, insert vertex $u$ by $\epsilon \to u$, delete vertex $u$ by $u\to \epsilon$, and substitute vertex $v$ for $u$ by $u\to v$. The other three editing operations for the edges were similar to those for the vertices. Figure 1 illustrates editing operations between two graphs that have two different type vertices and edges.

Figure 1. An explanation of graph edit operations (from $G_1$ to $G_2$).

Given graph $G_1=(V_1,E_1,L_{V}1,L_{E1})$ and graph $G_2=(V_2,E_2,L_{V}2,L_{E2})$, the ordered set of editing operations from $G_1$ to $G_2$ comprises a complete editing path $\lambda =(e_1,e_2,\dots ,e_i,\dots e_n)$, where $e_i$ denotes the i^th editing operation, and $n$ is the total number of operations. Let the editing cost of the edit operation $e_i$ be $\mathrm{c}(e_i)$; then, the GED of the path $\lambda$ is: (1) $\mathrm{Distance}(G_1,G_2{)}_{\lambda }=\sum _{e_i\in \lambda }c(e_i)$(1) There are multiple edit paths$\lambda \in \gamma$ between $(G_1,G_2)$, and the optimal edit path is the one with the smallest total edit cost, representing the distance between the two graphs. The shorter the distance, the more similar the two graphs are. The edit distance $\mathrm{Distance}(G_1,G_2)$ is: (2) $\mathrm{Distance}(G_1,G_2)=\underset{\lambda \in \gamma }{min}\mathrm{Distance}(G_1,G_2{)}_{\lambda }$(2)

3.2. Conversion of shapes into graphs

Building contours comprise points and lines, which makes them ideal for natural conversion into graphs with the nodes and connections representing vertices and edges, respectively. A cyclic graph is constructed by converting corner points and boundary lines into vertices and edges, respectively. A cyclic graph can be considered as a chain starting with any vertex and ending with cohesively connected vertices. It does not contain tree-like subgraphs, which makes it easy to perform the edit operation and discover the optimal edit path.

The primary objective during graph construction is to extract the geometric characteristics for shape representation and similarity measurement. We use the angle of the corner points to convey local information. Based on the Gestalt principles, we use the angle of the corner point and the length of two parts of building contour which connect two adjacent corner points to represent regional information for structural cognition. Both local and regional information were used for labeling the vertices in the graph.

To accurately and unambiguously represent the shape and avoid ambiguity caused by the use of the intersection angle, the rotation angle was chosen to represent the local information of the corner points (Figure 2). Then label $L(v)$ of vertex $v$ of the graph of a building is. (3) $L(v)=[R(v),l_{\mathrm{prev}}(v),l_{\mathrm{next}}(v)]$(3) where $l_{\mathrm{prev}}(v)$ is the length of the boundary between current vertex $v$ and the previous vertex (clockwise direction) and $l_{\mathrm{next}}(v)$ is the length of the boundary between current vertex $v$ and the next vertex. $R(v)\in [0,2\pi )$ is the angle of rotation between the two vectors corresponding to the two boundaries of the building contour. $L(v)$ represents the structural cognitive information of the building corner point corresponding to vertex $v$ in graph $G$.

Figure 2. Local information expression of the corner points.

As the local and regional information of the building corner points is stored in vertex labels, the edges in the graph represent only the relationships between adjacent vertices. An unweighted cyclic graph was constructed using an arbitrary starting vertex (Figure 3).

Figure 3. Conversion of building corner points shapes into shape graphs ($v_0$is an arbitrary start vertex of the graph).

3.3. Calculation of building shapes similarity

There are two key issues during the calculation of shape similarity using GED: defining the costs of different editing operations and searching for the optimal editing path.

Considering that the regional characteristics of a building are stored in the vertex labels of a graph, this study only edited the graph vertices. As vertex insertion is a dual-to-vertex deletion, this study defined only two types of edit costs: vertex substitution and deletion. Assuming that the process of editing $G_1$ to $G_2$ comprises the following steps: ‘delete vertices from $G_1$,’ ‘substitute vertices from $G_1$ with vertices from $G_2$,’ and ‘insert vertices from $G_2$,’ the editing cost is equivalent to ‘delete vertices from $G_1$,’ ‘delete vertices from $G_2$,’ and ‘substitute vertices from $G_1$ with vertices from $G_2$ (or vice versa).’

Unlike other structure-based similarity measurement methods that seek approximate solutions, we aimed for an exact solution to determine the optimal editing path and the corresponding editing cost. Consequently, we transformed the problem into a maximum-weight clique problem by constructing a vertex association graph to obtain a set of vertex pairs for $G_1$ and $G_2$where the sum of the costs of vertex substitution was minimized. This study used an improved Local Strong Configuration Checking (LSCC) model to obtain an exact solution.

Figure 4 illustrates the basic framework of the proposed method. The definition of the vertex edit cost and the method for obtaining the optimal editing path are elaborated in the subsequent sections.

Figure 4. Framework of the GED method. (a) illustrates a set of examples of original and target graphs; (b) represents multiple graph edit paths and their corresponding edit costs based on edit cost definition; (c) shows the construction of a vertex association graph using the above information, and the determination of its maximum-weight clique (a subgraph where each vertex is adjacent) through LSCC; and (d) illustrates the vertex editing scenario represented by the maximum-weight clique (optimal edit path), and the corresponding graph edit distance.

3.3.1. Definition of vertex edit cost

The cost function of the edit operation differs according to the discipline, objective, and graph. The rationality and adequacy of the definition of the cost function determine the effectiveness of the editing distance. Assuming that one building contour can be generated by stretching another, the geometric distortion during stretching represents the difference between the two contours.

In this study, we defined two edit operations: vertex deletion and vertex substitution (S). All graph vertices were categorized into three sets in an edit path (from $G_1$ to $G_2$ or $G_2$ to $G_1$): two sets of vertices to be deleted ($D_1$ and $D_2$) and the set of vertex pairs to be substituted ($S\in V_1\times V_2$). Let $d_u$ and $d_v$ be the costs of deleting vertices $u$ and $v$ from $G_1$ and $G_2$, respectively. Let $s_{\mathrm{uv}}$ be the cost of substituting vertex $u$ with vertex $v$ (label substitution). Then, the optimal editing distance can be rewritten as follows: (4) $\mathrm{Distance}(G_1,G_2)=min(\sum _{u\in D_1}{d}_u+\sum _{v\in D_2}{d}_v+\sum _{(u,v)\in S}{s}_{\mathrm{uv}})$(4) The ‘stretching operation-based definition’ does not imply that stretching operation will occur in the GED calculation. Instead, this approach is used to assign label values to each vertex. The primary reason for defining the edit cost is to guarantee alternately appropriate costs that can help the GED algorithm make wise decisions. When searching for the optimal edit path, the algorithm tends to substitute similar vertices, instead of deleting them.

3.3.1.1. Vertex substitution operation cost

During vertex substitution, the geometric differences between the two vertices in the graph, which are represented by the vertex labels and the positional differences, should be considered. As we used an arbitrary vertex as the starting point during the graph construction process, we represented the graph as a set of chains to ensure that the replacement process did not fall into an infinite loop. For graph $G$ with $n$ vertices, we constructed chains in both the clockwise and counterclockwise directions considering each vertex as the starting point. The corresponding set of chains is $\{C\}=\{C^1,C^2,\dots ,C^{2n}\}$. Substitution operation cost $s_{(u,v)}$ for replacing vertex $u$ in $G_1$ with vertex $v$ in $G_2$ depends on geometric $\mathrm{GeomDis}(u|G_1,v|G_2)$ and positional $\mathrm{PosDis}(u|C_1^i,v|C_2^j)$ differences of the vertex, where $i$ and $j$ represent the chain indices. (5) $s_{(u,v)}=\mathrm{GeomDis}(u|G_1,v|G_2)\times \mathrm{PosDis}(u|C_1^i,v|C_2^j)$(5) Geometric difference $\mathrm{GeomDis}(u|G_1,v|G_2)$ represents the difference between two triangles, each formed by the information covered by the labels of vertices $u$ and $v$. $\mathrm{GeomDis}(u|G_1,v|G_2)$ was calculated as follow: (6) $\begin{array}{rl}& \mathrm{GeomDis}(u|G_1,v|G_2)=\mathrm{ScDis}(u|G_1,v|G_2)\times [\mathrm{StrDis}(u|G_1,v|G_2)\\ & +\mathrm{AngDis}(u|G_1,v|G_2)]\end{array}$(6) where $\mathrm{ScDis}(u|G_1,v|G_2)$, $\mathrm{StrDis}(u|G_1,v|G_2)$, and $\mathrm{AngDis}(u|G_1,v|G_2)$ represent the distortion among different phases. The calculation is performed in the following steps:

Let $u_p$ and $v_q$ be the vertices of $G_1$ and $G_2$, respectively. $u_{p-1}$ and $u_{p+1}$ are the two adjacent vertices of $u_p$. $v_{q-1}$, $v_{q+1}$ are the two adjacent vertices of $v_q$. Move $u_{p-1}$ and $v_{q-1}$ to the same position, and then rotate the structure to make $u_{p-1}$, $v_{q-1}$, $u_{p+1}$, and $v_{q+1}$ collinear on datum line l. Note the triangle constructed by $u_{p-1}$, $u_p$, $u_{p+1}$ as $T_1$, and constructed by $v_{q-1}$, $v_q$, $v_{q+1}$ as $T_2$ (Figure 5).

Figure 5. ‘Stretching’ of the regional characteristics from $G_1$ to $G_2$.

Only when $T_1$ and $T_2$ have the same base, is it reliable to make them similar by stretching point $u_p$. Therefore, it is necessary to scale the triangles for ensuring that they share the same base. Scale up $T_1$ to $T_1^{\mathrm{\prime }}$ till point $u_{p+1}^{\mathrm{\prime }}$ coincides with $v_{q+1}$. The distortion in this operation is noted as $\mathrm{ScDis}(u|G_1,v|G_2)$.

Considering that a triangle can be determined using one side, the height on that side, and the opposite angle of that side, this study designed two parameters, $\mathrm{StrDis}(u|G_1,v|G_2)$ and $\mathrm{AngDis}(u|G_1,v|G_2)$, to describe the distortion caused by stretching $u_p$ to $v_q$.

$\mathrm{ScDis}(u|G_1,v|G_2)$ is determined using the ratio of the base of triangle $T_1$ and $T_1^{\mathrm{\prime }}$: (7) $\mathrm{ScDis}(u|G_1,v|G_2)={\log }_e[\arg max({\displaystyle \frac{b_{T_1}}{b_{T_1^{\mathrm{\prime }}}},{\displaystyle \frac{b_{T_1^{\mathrm{\prime }}}}{b_{T_1}})]+1}}$(7) $\mathrm{StrDis}(u|G_1,v|G_2)$ is the structure difference determined using the bases and the heights of the two triangles (Jiang et al. 2010; Tian et al. 2017). Let $b$ to be the base of $T_1^{\mathrm{\prime }}$ and $T_2$, and $h_1^{\mathrm{\prime }}$, $h_2$ are the height of triangles. (8) $\mathrm{StrDis}(u|G_1,v|G_2)=\delta \left|(1-{\displaystyle \frac{b}{h_1^{\mathrm{\prime }}+b})-\tau (1-{\displaystyle \frac{b}{h_2+b})}}\right|$(8) Where $\delta$ is the ratio of the total length of a corner point to the shape’s perimeter. $\tau$ is a parameter with value 1 or −1, which based on whether $u_p$ and $v_q$ are on the same side of the baseline $b$. (9) $\delta ={\displaystyle \frac{(l_{\mathrm{prev}}(v)+l_{\mathrm{next}}(v))}{\sum _{u\in V}(l_{\mathrm{prev}}(v)+l_{\mathrm{next}}(v))}}$(9) (10) $\tau =\{\begin{array}{c}1,\mathrm{if}{u}_p\mathrm{and}{v}_q\mathrm{on}\mathrm{the}\mathrm{same}\mathrm{side}\mathrm{of}\mathrm{base}\mathrm{line}b\\ -1,\mathrm{otherwise}\end{array}$(10) Let $\mathrm{\Delta }\theta$ be the difference between two angles opposite to the base, then $\mathrm{AngDis}(u|G_1,v|G_2)$ is: (11) $\mathrm{AngDis}(u|G_1,v|G_2)={\displaystyle \frac{\mathrm{\Delta }\theta }{\pi }}$(11) To calculate the similarity between the cycle graphs using GED, the graph was represented by a set of directed chains (explained in Section 3.3.2). Thus, every vertex in a chain had a sequence position representing the positional difference. If the two vertices have a low $\mathrm{GeomDis}(u|G_1,v|G_2)$but an obvious positional difference, GED will set a comparatively high substation cost.

Let $\mathrm{pos}(u|C_1^i)$ and $\mathrm{pos}(v|C_2^j)$ be the relative position of vertices $u$ and $v$ in the chains $C_1^i$ and $C_2^j$, respectively, which are obtained by adding labels $l_{\mathrm{next}}(u)$ and $l_{\mathrm{next}}(v)$ of vertices that precede the current vertex. This is the total length of the contour from the chain's starting point to the current point in the corresponding building contour, which is shown in Figure 6. Then, the $\mathrm{PosDis}(u|C_1^i,v|C_2^j)$ is given by: (12) $\mathrm{PosDis}(u|C_1^i,v|C_2^j)=e^{|\mathrm{pos}(u|C_1^i)-\mathrm{pos}(v|C_2^j)|}$(12)

Figure 6. An example for calculating the relative position.

3.3.1.2. Vertex deletion operation cost

Defining the deletion cost of a vertex is a major challenge for GED. Because substitution is more meticulous than deletion, the cost of deletion is usually set to 1, whereas the cost of substitution is relatively higher. However, this approach may not be suitable for measuring shape similarity, as removing a corner point from the contours can have a considerable impact. Despite this, the substitution cost should be higher in this study, but not too much for most pairs of vertices. For vertices $u$ and $v$ on $G_1$ and $G_2$, if their geometric or positional differences on chains $C_1^i$ and $C_2^j$ are too large, the cost of substituting vertices $u$ and $v$ may be higher than that of deleting the two vertices. In such case, the proposed method deletes both vertices rather than performing an irrational substitution operation.

Consequently, the deletion cost was designed based on the geometric distortion to extrude the corner of the shape to the baseline. Then the deletion cost for deleting vertex $v$ is: (13) $d_v=\delta (1-{\displaystyle \frac{b}{h+b})}$(13) where $\delta$ is the ratio parameter, $b$ is the base of the triangle constructed using the corner and adjacent points, and $h$ is the height of the base.

3.3.2. Search for the optimal edit path

This study aimed to determine the optimal edit path that represents the distance between the two graphs. According to Equation (4(4) $\mathrm{Distance}(G_1,G_2)=min(\sum _{u\in D_1}{d}_u+\sum _{v\in D_2}{d}_v+\sum _{(u,v)\in S}{s}_{\mathrm{uv}})$(4) ), the set of vertices to be substituted represents an edit path. Then, the Equation (4(4) $\mathrm{Distance}(G_1,G_2)=min(\sum _{u\in D_1}{d}_u+\sum _{v\in D_2}{d}_v+\sum _{(u,v)\in S}{s}_{\mathrm{uv}})$(4) ) can be rewritten as. (14) $\begin{array}{rl}\mathrm{Distance}(G_1,G_2)& =min[\sum _{u\in D_1}{d}_u+\sum _{v\in D_2}{d}_v+\sum _{(u,v)\in S}(d_u+d_v-s_{\mathrm{uv}})]\\ & =\sum _{u\in V_1}{d}_u+\sum _{v\in V_2}{d}_v-max[\sum _{(u,v)\in S}(d_u+d_v-s_{\mathrm{uv}})]\\ & =\sum _{u\in V_1}{d}_u+\sum _{v\in V_2}{d}_v-\underset{(u,v)\in S}{max}[\mu (S)]\end{array}$(14) Because $\sum _{u\in V_1}{d}_u$ and $\sum _{v\in V_2}{d}_v$ are constant and independent of $\lambda$, the optimal edit distance between the two graphs depends on the maximum value of the utility $\mu (S)=\sum _{(u,v)\in S}(d_u+d_v-s_{\mathrm{uv}})$. Thus, the optimal edit path is determined when the optimal substitution set $(u,v)\in S$ is calculated.

Furthermore, determining the minimum edit distance between graphs can be transformed into searching for the maximal weighted clique of the association graph (Torsello and Hancock 2004; Torsello, Robles-Kelly, and Hancock 2007). In this method, an association graph is constructed by obtaining both $G_1$ and $G_2$ with vertices deletion and substitution operations. A clique of the association graph can represent a substitution set $(u,v)\in S$, so the edit-distance problem is equivalent to searching for a clique of an association graph that maximizes the total utility $\mu (S)$.

Hence, the optimal edit path is obtained in two steps: constructing an association graph and determining the maximal weighted clique, which are explained as follows.

3.3.2.1. Construction of an association graph

For an association graph, the maximal weighted clique of it represents the optimal substitution set $S$ that determines the minimum edit distance of a pair of chains. Let $\{C_1\}$ and $\{C_2\}$ are the chain sets of $G_1$ and $G_2$ respectively. $i$ and $j$ represent the chain indices. The optimal edit path can be determined by traversing combinations of chains in the two sets with the minimum value. (15) $\mathrm{Distance}(G_1,G_2)=\underset{C_1^i\in \{C_1\},C_2^j\in \{C_2\}}{min}\mathrm{Distance}(C_1^i,C_2^j)$(15) A transitive closure should be constructed before constructing an association graph. For directed chain $C=(V,E_C)$, transitive closure $\mathrm{\Omega }(C)=(V,{\hat{E}}_C)$ has the same vertex $V$ and directed edges. In a transitive closure, all vertices are connected to the remaining vertices; therefore, the deletion of any vertex will not break the connectivity. When deletion occurs, the vertex and adjacent edge are deleted in both the chain and the associated transitive closure (Figure 7).

Figure 7. (a) Conversion of a graph into a transitive closure where all the vertices are connected to the others. (b) When deletion is performed on the transitive closure, the connectivity of the original graph still exists.

Let $\mathrm{\Omega }(C_1^i)=(V_1,{\hat{E}}_{C_1^i})$ and $\mathrm{\Omega }(C_2^j)=(V_2,{\hat{E}}_{C_2^j})$ be two transitive closures of $C_1^i$ and $C_2^j$. $G_A=(V_A,E_A,W)$ is the association graph of $\mathrm{\Omega }(C_1^i)$ and $\mathrm{\Omega }(C_2^j)$, which has vertices set $V_A=V_1\times V_2$ equivalent to the Cartesian products of vertices of $\mathrm{\Omega }(C_1^i)$ and $\mathrm{\Omega }(C_2^j)$. In the association graph $G_A$, the vertex means a pair of vertices in $\mathrm{\Omega }(C_1^i)$ and $\mathrm{\Omega }(C_2^j)$ operating the substitution, and $w\in W$is the weight of the vertex: (16) $w(u,v)=d_u+d_v-s_{\mathrm{uv}}$(16) The edges represent the mutual constraints between pairs of vertices. Specifically, let $(u_i,v_j)$ and $(u_p,v_q)$ be the two vertices in $G_A$; then, there is a directed edge $((u_i,v_j),(u_p,v_q))$ in $E_A$ only when there are edges $(u_i,u_p)$ and $(v_j,v_q)$ in ${\hat{E}}_{C_1^i}$ and ${\hat{E}}_{C_2^j}$, respectively. For better demonstration, arrange the vertices in $G_A$ as a matrix (Figure 8), in which directed edges only exist between one vertex and the other vertices on the lower right side.

Figure 8. An example of the structure of an association graph. The dashed arrows and solid arrows indicate a possible edit path and directed edges in the graph, respectively. (a) is an association graph $G_A$ of $\mathrm{\Omega }(C_1^i)$ and $\mathrm{\Omega }(C_2^j)$ in a matrix-like expression. (b) illustrates the directed edges between vertices in $G_A$. Directed edges only exist between one vertex and other vertices on its lower right side. (c) is a clique of $G_A$ and represents an edit path. The selected vertices of $G_A$ (a clique) are substituted, whereas the left vertices in two transitive closures are deleted.

In Figure 8, a set of connected arrows means a clique of $G_A$, and it also can be regarded as an edit path with substitution vertices set and deletion vertices set. When the arrow goes through the vertex $(u_p,v_q)$ of $G_A$, the label of $u_p$ in $\mathrm{\Omega }(C_1^i)$ is updated to the label of $v_q$ after the substitution operation. If the arrow jumps over column q in the matrix, the vertex $v_q$ will be deleted from $\mathrm{\Omega }(C_2^j)$.

3.3.2.2. Optimal path based on the maximum weighted clique

A clique in a graph is a complete or fully connected subgraph, and a maximum weighted clique is a clique with maximum total weight among all the cliques. When setting a weight $w(u,v)$ to the vertices of $G_A$, the search for the optimal edit path is transformed into obtaining the maximum weighted clique of $G_A$.

The maximum weighted clique problem is a typical non-deterministic polynomial that requires considerable time to solve. LSCC is a heuristic algorithm (Wang, Cai, and Yin 2016) for determining the maximum clique by performing the following operations: initialize, add, swap, and drop. The algorithm defines the check region for the local maximum clique. When the region extends to the entire graph, it determines the maximum clique of the given graph.

Considering that association graph $G_A$ has evident structural patterns, this study modifies the LSCC algorithm to improve the efficiency of solving the maximum weighted clique problem as follows.

A matrix-like graph expression was used for an enhanced elaboration. Substitution set $S_0=[(u_0,v_0),(u_1,v_1),\dots ,(u_k,v_k)]$ and a corresponding clique $\mathrm{Cl}{q}_0$ were initialized. Then, the total weight of clique was equivalent to utility $\mu (S_0)$ as shown in Equation (17(17) $W(\mathrm{Cl}{q}_0)=\mu (S_0)=\sum _{(u,v)\in S_0}(d_u+d_v-s_{\mathrm{uv}})$(17) ). (17) $W(\mathrm{Cl}{q}_0)=\mu (S_0)=\sum _{(u,v)\in S_0}(d_u+d_v-s_{\mathrm{uv}})$(17) Subsequently, the vertices were swapped as follows:

• The vertices were swapped from bottom to top and row by row. For the $k^{\mathrm{th}}$ row, the candidate set contains the vertices on the right side of the current vertex and has a larger weight. After checking the candidate set's weight and swapping in the $k^{\mathrm{th}}$ row, clique $\mathrm{Cl}{q}_k$ and substitution set $S_k$ were recorded as the $k^{\mathrm{th}}$ local optimal solution (the local optimal solution was recorded only once for each row). Subsequently, we jumped to the $(k-1{)}^{\mathrm{th}}$ row and continued swapping until the swap operations were completed in every row. The final recorded local optimal solution represented the maximum weighted clique $\mathrm{Cl}{q}^{\ast }$.

• When checking the vertices in the set, if the weight is larger than the current vertex weight and the vertex position lies to the left of the vertex in the next row (the last row is not considered), the vertex was swapped with the candidate, and the candidate set was updated.

• If a vertex whose weight was larger than the current vertex was present, but it was located directly above or to the right of the vertex in the next row, current vertex $(u,v)$ and total weight $W$ were recorded. Subsequently, a new substitution set $S^{\mathrm{\prime }}$ was initialized based on the current vertex (extending to the lower right by one row and column), and the swap row was relocated to the last for swapping. When the swapping of the $(u+1{)}^{\mathrm{th}}$ row was finished, total weight $W^{\mathrm{\prime }}$was recorded. If $W^{\mathrm{\prime }}\ge W$, the current clique was recorded as a temporary optimal solution $S_{\mathrm{temp}}$, and swapping was continued from $(u,v)$. After swapping all the candidates in this row, the current clique was compared with all $S_{\mathrm{temp}}$, and the one with the largest total weight was recorded as local optimal solution $S_k$.

Table

Algorithm 1: Determining the maximum weighted clique of an association graph
Input: An association graph $G_A$;
Output: Maximum weight clique $\mathrm{Cl}{q}^{\ast }$ of $G_A$;
1	$\mathrm{Cl}{q}^{\ast }=\mathrm{\varnothing },k=n$(n is the number of the row of the matrix), $\mathrm{endrow}=0$;
2	Initialize $S_0$ consistent with $\mathrm{Cl}{q}_0$;
3	$\mathrm{Cl}{q}_{\mathrm{localbest}}=\mathrm{Cl}{q}_0$;
4	while $k\ge \mathrm{endrow}$ do
5	$\mathrm{CliqueSet}=\{\mathrm{\varnothing }\}$;
6	for vertex in $\mathrm{CandidateSet}$ in current row do
7	check the location of current candidate $(u,v)$ and vertex $(u^{\mathrm{\prime }},v^{\mathrm{\prime }})$ in the next row;
8	if the candidate located at left to the vertex in the next the row, then
9	swap the candidates in current row, and update vertex with larger
	value, update substitution set $S$, and $\mathrm{Clq}$;
10	else
11	initialize a substitution set $S_{\mathrm{temp}}$, execute the algorithm with $\mathrm{endrow}=k-1$ record optimal solution as $S_{\mathrm{temp}}$, and optimal clique $\mathrm{Cl}{q}_{\mathrm{temp}}$;
12	If $W(\mathrm{Cl}{q}_{\mathrm{temp}})>W(\mathrm{Cl}{q}_{\mathrm{localbest}})$, then $\mathrm{Cl}{q}_{\mathrm{temp}}\in \mathrm{CliqueSet}$;
13	$\mathrm{Cl}{q}^{\mathrm{\prime }}=max(\mathrm{CliqueSet})$, record corresponding substitution set as $S^{\mathrm{\prime }}$;
14	if $W(\mathrm{Cl}{q}^{\mathrm{\prime }})>W(\mathrm{Clq})$ then $S_k:=S^{\mathrm{\prime }}$, $\mathrm{Cl}{q}_k:=\mathrm{Cl}{q}^{\mathrm{\prime }}$;
15	record local optimal solution as $S_k$, and optimal clique $\mathrm{Cl}{q}_k$;
16	if $W(\mathrm{Cl}{q}_k)>W(\mathrm{Cl}{q}_{\mathrm{localbest}})$ then $\mathrm{Cl}{q}_{\mathrm{localbest}}:=\mathrm{Cl}{q}_k$;
17	$k--$;
18	$\mathrm{Cl}{q}^{\ast }:=\mathrm{Cl}{q}_{\mathrm{localbest}}$;
19	return $\mathrm{Cl}{q}^{\ast }$;

Figure 9 shows an example of determining the maximum weighted clique of an association graph. Each subfigure represented substitution sets (cliques) in k-steps and the optimal solution in former steps. Figure 9 (a) shows the initial substitution set and the followed swap process in the last row of the matrix. Figures 9 (b) and (c) illustrate how a new substitution set was initialized and updated using different k values. When the start vertex was changed (Figure 9 (d)), more columns representing transfer closures were added. $k$ = 0 implied a change in the starting point of matching substitution. Additional association graphs were constructed by adding more columns. Therefore, this example illustrates association graphs constructed using a transitive closure from $G_1$and all transitive closures from $G_2$, with had the same direction and the maximum weight clique in these graphs. The final editing path was obtained by performing the above algorithm with backward and same transitive closures from $G_1$and $G_2$, respectively. Finally, the maximum weight clique was obtained, i.e. $\mathrm{Clq}\ast =[(u_0,v_0),(u_1,v_2),(u_2,v_3),(u_3,v_4)]$. The optimal edit path was obtained as $\lambda =[(u_0\to v_0),(u_1\to v_2),(u_2\to v_3),(u_3\to v_4),(v_1\to \epsilon )]$.

Figure 9. Determination of maximum weighted clique in the matrix-like association graph.

4. Experiments and results

We designed three experiments to validate the proposed method. The experiments include qualitative and quantitative comparisons with traditional shape measurement methods and GeoAI-based shape measurement methods. Two different datasets were constructed to assess the cognitive ability of the proposed method, and all building contours were standardized.

4.1. Shape matching experiment

In this study, three metrics were used to quantitatively assess shape cognition ability in the shape match task: first tier (FT), second tier (ST), and discounted cumulative gain (DCG) (Shilane et al. 2004). The FT and the ST metrics refer to the percentage of shapes within the top K matches that belong to the same template type. For each shape class comprising $N$ members, $K=N-1$ and $K=2\times (N-1)$ for FT and ST, respectively. In all cases, an ideal matching result lead to a score of 100%, and higher values indicated better matches. DCG is a statistic that weighs more correct matches near the front of the ranked similarity list than the latter part of the same list. For each shape, similarities to the other shapes were determined and sorted in descending order. The more advanced the sorted shape, the stronger the relevance or irrelevance. The DCG ranged from 0 to 1, with higher values indicating better performance.

The experiment dataset is a labeled building shapes dataset (Table 1) obtained from Yan et al. (2021). It comprised 10 typical standard shapes, including E-, T-, and U-shape. Each type comprised 500 shapes, which were used as training samples for 5,000 samples.

Table 1. Examples of 10 building shapes type.

To quantitatively assess the proposed method, this study compared it with three conventional methods: two contour-based approaches, namely the Fourier descriptor (FD) (Ai et al. 2013) and turning function (TF) (Arkin et al. 1991), and one region-based method, namely multiscale features and grid context descriptors (MF&GCD) (Fan, Zhao, and Li 2021). In addition, the proposed method was also compared with two novel methods: graph convolutional autoencoder (GCAE) (Yan et al. 2021) and LineStringNet (Li, Yan, and Lu 2023b). Considering the remarkable impact of the rotating operation on the results when using certain methods, we compared the performance of shape similarity measurements for both rotated (marked by the letter R) and unrotated buildings.

The proposed GED method exhibited rotational invariance and outperformed conventional methods, particularly for unrotated buildings (Table 2). Both the GED and TF methods traversed all contour points to obtain the optimal value; however, the GED method calculated the cost using a more reasonable way, which explains its superior performance. The FD method used compact descriptions to reduce the computational complexity, which rendered it insensitive to continuous characteristics, thereby resulting in inaccurate details. Although the MF&GCD method also has rotation invariance, its precision was unsatisfactory and substantially affected by the grid size. Furthermore, the region-based method did not exhibit superior performance when using vector data. Table 2 indicates that the proposed GED method was comparable to the GCAE method. Although the GCAE method was sensitive to the orientation of the buildings, it outperforms the rotating building data. The LineStringNet method exhibited excellent performance in the shape matching experiment; however, its generalization ability should be further examined owing to the supervised training process used in this study.

Table 2. Performance of shape similarity measurements using different methods. Higher number indicates better performance.

	FT	ST	DCG
Turning function	0.294	0.402	0.802
Turning function (R)	0.567	0.653	0.911
Fourier descriptor	0.266	0.346	0.787
Fourier descriptor (R)	0.441	0.587	0.873
MF&GCD	0.591	0.722	0.920
GCAE model	0.408	0.566	0.866
GCAE model (R)	0.835	0.941	0.983
LineStringNet	0.986	0.997	0.998
GED method	0.865	0.977	0.989

The precision-recall curves of different methods for classifying the shape type by averaging the 10 standard shapes are depicted in Figure 10, which aligns with the previous analysis.

Figure 10. Precision–recall curves of different methods. (a) Compares to the conventional methods. (b) Compares to the GeoAI-based methods.

Further analysis was conducted on different shape type matching using the proposed GED method. Figure 11 illustrates a matching result showing the matching details for the10 standard shapes. Relatively complex shapes, such as E-, H-, and Z-shapes, exhibited better performance, whereas the most incorrect matches were observed in the L-, I-, and O-shapes.

Figure 11. Image of matching result obtained using the GED method. The blue and red blocks (bottom left to top right diagonally) represent correct and incorrect matches, respectively. The deeper the color, the more matches there are between the shape pairs.

It is noteworthy that there is a significant misclassification of I-shapes as O-shapes. This may be because prior knowledge can influence sample labeling, marking shapes with an aspect ratio close to 1 as O-shapes and the rest as I-shapes. However, the GED method measures the similarity between shapes objectively without prior knowledge. Therefore, when determining the similarity between a rectangle (assuming an aspect ratio of 2:1) and the O- and I-templates (with aspect ratios of 1:1 and 5:1, respectively, in Dataset 1), the algorithm may calculate it as more similar to the O-template from an edit cost perspective. In contrast, humans would consider it to have an I-shape. For regular I-shapes, a hidden aspect ratio threshold of approximately 2.873:1 exists. When the aspect ratio exceeds this threshold, the GED considers the shape as more similar to the I-template; otherwise, it considers the shape as more similar to the O-template. This clarifies why a substantial number of buildings labeled as I-shapes were misclassified as O-shapes, whereas a few buildings labeled as O-shapes were misclassified as I-shapes.

4.2. Shape retrieval experiment

We constructed a dataset using 9410 building shapes from OpenStreetMap (Figure 12). The shapes in this dataset were more intricate, and the 10 building-shape templates were retrieved from similar buildings in the dataset.

Figure 12. Experimental area for the retrieval experiment. The left picture illustrates the location of Shanghai City in mainland China and the red line depicts the study area in Shanghai City (it is located in the vicinity of the walled region defined by Zhongshan North, West Yan'an, and North Chengdu Roads). The two right pictures denote a sample block and building shapes in the area.

Table 3 lists the templates’ top nine similar shapes and the graph edit distance of the templates. The retrieved shapes exhibited high visual similarity to the templates, and the retrieval results aligned with the intuitive notion of humans. Furthermore, the retrieved shapes had different orientations, indicating that the GED method has a high rotation invariance.

Table 3. Top nine retrieved buildings for the 10 standard shapes.

In this dataset, a large proportion of the shapes were simple, such as I-, O-, and L-shapes, resulting in the best performance of the retrieval results, with a small edit distance. However, the retrieval results of some of the more complex shapes, such as E-, F-, H-, and Y-shapes, did not align with human visual cognition. There are two possible explanations for this discrepancy. First, Dataset 2 comprised only a limited number of regularly-shape buildings, particularly for the E- F-, and Y-shapes. Consequently, the retrieved shapes presented in Table 3 may not represent buildings that are similar to the templates. Second, the GED method tends to measure regional information; therefore, shapes with more similar regions obtain a relatively low score. For example, the 7th and 8^th similar buildings in the Y-shape class were partially similar to the templates (in the top half ‘valley’ part). The 5^th and 6^th similar buildings in the H-shape class partially resembled (at the bottom part) the template (the left or right part), resulting in low edit distances.

Furthermore, some shapes were more similar to the target from human perceive but had a high GED value and rank such that the 7th and 8^th H -shapes were more similar to the template than the 5^th and 6^th H -shapes. The primary cause may be the GED's tendency toward regional information. The bottoms of the 5th and 6th H-shapes were extremely similar to the left/right parts of the template; thus, that the corresponding vertices had low edit costs. Although the 7th and 8th H-shapes were similar to the template, more vertices had high detailed edit costs, and the total edit cost was greater.

In addition, the 7th and the 8th similar buildings in F- and E-shapes were the same building. Although this shape is more similar to the E-shape owing to a lower edit distance, which is consistent with visual judgment, it should not have been retrieved by the F-shape template. This can be explained as follows: First, the GED method overemphasizes the regional characteristics instead of global ones. The graph is a discrete structure, i.e. its shape is described by a set of regional characteristics. When the majority of regional characteristics are very similar, but a fraction is not, then the fractional part will not considerably affect the results; however, this fraction may cause a large difference in human cognition. This limitation should be further investigated in future studies. Second, dense corner points and small contour segments can affect the GED results. This point is further discussed in Section 5.

We also compared the GED method with the GCAE and LineStringNet methods, which have demonstrated good performance in shape matching experiments for building shape retrieval.

Table 4 presents the top five retrieved building elements and their corresponding quantitative measurement values obtained using the three methods. $\mathrm{GED}$ and $\mathrm{SD}$ represent the output values of the GED and GCAE methods, respectively, where smaller values indicated a higher similarity. $P_{\mathrm{sim}}$ is the output value of the LineStringNet model, where larger values indicated a higher similarity. The results demonstrated that the shapes retrieved using the GED method were more consistent with human cognition than those obtained using the GCAE and LineStringNet methods, particularly in the F-, T-, and Z- shape classes. This comparison indicates that the current GeoAI-based methods have some limitations in their generalization ability and require more diverse and representative samples to learn latent features for better performance in new datasets. However, obtaining sufficient samples remains a considerable challenge. Conversely, the GED method exhibited higher stability and provided more reliable candidates for shape retrieval.

Table 4. Retrieval results of templates using GCAE and LineStringNet methods.

Some shapes, such as the 1^st and 3^rd E-shape targets, were not retrieved using the GED method but were retrieved using alternative methods, such as LineStringNet method, as shown in Table 4. Although these shapes were similar to the human-perceived letter shapes, they differed substantially from the templates used in the experiment. For example, the 1^st E-shape retrieved using LineStringNet had a thinner trunk than that of the template, and its upper-left corner was sunken. These factors increased the edit costs required to match the E-shape template when using the GED method.

An additional experiment was conducted to retrieve four additional intricate shapes from the same dataset. Table 5 lists the top nine retrieved buildings and their corresponding quantitative measurements. Among the three candidate methods, shapes that were almost identical to the targets were retrieved. However, after retrieving extremely similar shapes, the subsequent retrieval sequences of the GED method comprised features that were more similar to the target than those of the LineStringNet and GCAE models. For the first target, all three candidate methods retrieved four shapes that were almost identical to the target. In addition, the GED method retrieved additional shapes with regional characteristics that were more similar to the target, exhibiting a distinct ‘step-like’ feature, which is consistent with human cognition of the retrieval targets. In the second target, the 5–9^th buildings that were retrieved using the GED method displayed obvious similarity to the target, whereas the shapes retrieved using GCAE exhibited considerable differences from the target, and the H-shapes retrieved using LineStringNet differed locally from the target. In the third target, the 4–9^th results retrieved using GCAE and LineStringNet were markedly different from the target, whereas the GED results showed certain regional similarities with the target. The 6th result was globally similar to the target. In the fourth target, the first seven results retrieved using the GED method visually resembled the target, whereas GCAE and LineStringNet could only retrieve three buildings that were similar to the target. Additionally, shapes that appear visually similar and dissimilar to the target exhibit a small numerical difference in the measurement values.

Table 5. Retrieval results of complicated shapes using GED, GCAE and LineStringNet methods.

4.3. Shape cognition experiment

We designed a cognition experiment to compare the human cognition results for buildings with those of the GED method in the test area (block in Figure 12).

In this experiment, the GED method was first used to query buildings based on qualitative shape similarity representation, which was defined as follows: strongly (0 ≤ GED < 0.05), moderately (0.05 ≤ GED < 0.1) similar. Subsequently, 10 graduated students majoring in GIS were asked to judge the degree of similarity. They were required to assign an order number describing the shape similarity of each building in the experimental data to the E-, H-, and Z-shape templates. The order numbers ranged from zero to two, with two, one, and zero indicating strong moderate, and no similarity, respectively.

Figure 13 lists the cognition experiment results for E-, H-, and Z-shape template buildings. In this study, we used a ratio model (Eisler and Ekman 1959; Tversky 1977) to measure the difference in shape recognition results between the GED method and human cognition. (18) $S(a,b)={\displaystyle \frac{2|A\cap B|}{|A+B|}}$(18) $S(a,b)$ represents the similarity between the GED method and human cognition result. A and B represent building sets queried using GED and human cognition, respectively.

Figure 13. Qualitative shape similarity representation by GED value (strongly (0 ≤ GED < 0.05) and moderately (0.05 ≤ GED < 0.1) similar). Red rectangular boxes indicate some mismatched cognition results.

This experiment obtained a semantic similarity using two qualitative representations, which was 60.0% and 38.5% for strong and moderate similarity, respectively. Qualitative representation using the GED method was different to human cognition. There are two possible explanations for this discrepancy. First, the shape cognition task is inherently ambiguous, and there exists no clear boundaries among different qualitative representation levels, such as strongly and moderately similar. Therefore, subtle differences in shape may cause substantial differences in the qualitative representation of the GED values. For example, the two H-shape buildings on the left side had a GED value of 0.473, which was close to a predefined threshold but caused the building to be recognized as ‘moderately similar’.

Second, the thresholds for qualitative representation using the GED method may differ for different shapes. For example, the two E-shape buildings in the middle had a GED value of 0.115, which exceeded the threshold and caused the building shapes to be recognized as dissimilar. Moreover, the GED value of the two Z-shape buildings at the bottom were 0.086, which exceeded the threshold and caused the building shapes to be recognized as moderately similar.

Consequently, the results may vary if we set a more ambiguous definition of ‘similarity.’ For example, considering both ‘strongly similar’ and ‘moderately similar’ as ‘similar’ and the rest as ‘dissimilar,’ the semantic similarity between the two recognitions would be 93.33%, indicating that shape recognition using the GED method was consistent with human cognition.

5. Analysis and discussion

The proposed method can precisely identify the detailed differences among different building contours, thereby providing accurate similarity measurements with high interpretability. As mentioned in the experiments in Section 4, the GED method is superior to conventional similarity measurements, and it is expected to be applied for more downstream applications, such as cartographic generalization. This section further analyzes the high interpretability of the proposed method, addresses its current limitations, and provides potential improvements in its approach.

5.1. Analysis of the GED method

5.1.1. High interpretability of the GED method

The GED method provides an optimal edit path, which presents a local feature-matching solution based on corner points of building contours. This ensures that when two buildings are matched based on their contour corner points, the sum of the geometric differences is minimized. Such a matching solution is visually intuitive and aligns with the Gestalt principle of visual similarity, thereby rendering the proposed method highly interpretable. This section illustrates the calculation of edit costs for graph vertices and the matching solution using an example, emphasizing the high interpretability of the proposed method.

Figure 14 illustrates a relatively complicated test shape, labeled as Z-shape, in the Dataset 1 and its GED value in the 10 standard shape templates. The GED method correctly recognized it as a Z-shape, whereas other conventional methods classified it as either O- or H-shapes. Although it has the visual characteristics of a Z-shape, some nodes may cause the measurement methods into categorizing it as other standard shape types. Furthermore, it is a mirrored Z-shape, which has been rotated. Additionally, small noise segments are present in the shape, which may interfere with the measurement methods.

Figure 14. Contour of the test building shape and its 10 standard shape template cognition results using the proposed GED method. A low GED value indicates that the two shapes are more similar.

Figure 15 depicts the ultimate matching scenario of contour corner points between the test shape and the Z-shape template, accompanied by the associated edit costs for each editing operation. Table 6 lists the geometric distortion cost between vertices, and Table 7 delineates the computational process for a non-optimal edit path.

Figure 15. GED calculation process in the test shape. Red indices and arrows indicate substitution in the optimal edit path, whereas black indices indicate deletion. The two sub-tables display the edit cost of each edit operation. The sum of these costs is the graph edit cost. (To better explain the vertex matching between the two shape pairs, the test shape has been rotated)

Table 6. Geometric difference between the regional characteristics of the test shape and the Z- shape template.

Geometric Distortion Cost		Template Shape Z (v)
		0	1	2	3	4	5	6	7
Building Shape (u)	0	0.5118	0.1666	0.0884	0.1824	0.5147	0.1690	0.0897	0.1852
	1	0.6171	0.1060	0.0485	0.1461	0.6203	0.1082	0.0498	0.1492
	2	0.0390	0.7963	0.6104	0.7458	0.0330	0.7984	0.6101	0.7484
	3	0.6973	0.0005	0.0691	0.0124	0.7078	0.0035	0.0677	0.0149
	4	0.5348	0.1322	0.0480	0.1262	0.5442	0.1349	0.0490	0.1288
	5	0.7769	0.0076	0.0668	0.0256	0.7800	0.0100	0.0656	0.0288
	6	0.2746	0.4704	0.4684	0.6124	0.2808	0.4733	0.4705	0.6157
	7	1.3788	0.0120	0.1219	0.0409	1.3874	0.0165	0.1197	0.0465
	8	0.3022	0.6301	0.6134	0.7822	0.3103	0.6337	0.6159	0.7863
	9	0.2827	0.6450	0.6307	0.8006	0.2909	0.6486	0.6333	0.8046
	10	0.6280	0.2831	0.2308	0.3662	0.6340	0.2862	0.2327	0.3700
	11	0.7506	0.0469	0.0227	0.0761	0.7541	0.0494	0.0214	0.0794
	12	0.3796	0.3492	0.2313	0.2900	0.3882	0.3519	0.2320	0.2924

Table 7. Matrix-like association graph with weight $w(u,v)$ in the current chain sequence. The units with bold numbers represent the optimal edit path (maximum weighted clique) of the current chain combination.

Association Graph Vertex Weight		Template Shape Z (v)
		0	7	6	5	4	3	2	1
Building Shape (u)	0	0.064	0.125	0.084	0.063	0.033	0.111	0.076	0.047
	1	0.064	0.134	0.092	0.076	0.037	0.124	0.088	0.068
	2	0.167	0.104	0.057	0.009	0.168	0.036	−0.008	−0.081
	3	0.027	0.220	0.161	0.164	0.044	0.218	0.152	0.163
	4	0.022	0.144	0.110	0.089	0.066	0.147	0.108	0.082
	5	0.026	0.155	0.103	0.099	0.066	0.155	0.102	0.099
	6	0.064	0.073	0.040	0.034	0.075	0.090	0.044	0.033
	7	0.064	0.117	0.066	0.059	0.073	0.116	0.066	0.058
	8	0.071	0.086	0.047	0.039	0.078	0.097	0.050	0.039
	9	0.072	0.084	0.046	0.038	0.079	0.096	0.050	0.040
	10	0.046	0.099	0.058	0.048	0.063	0.106	0.060	0.049
	11	0.013	0.138	0.095	0.084	0.054	0.140	0.095	0.084
	12	−0.009	0.058	0.030	0.003	0.030	0.083	0.046	0.022

Table 6 shows the geometric distortion cost between the regional characteristics of this shape and the Z-shape template. The cost of geometric distortion was generally lower for corner points with similar regional characteristics but higher for those that were visually different. For example, when calculating the geometric distortion cost of corner point $u_0$ in the test shape (Figure 15), the substitution cost of $u_0{v}_0$ and $u_0{v}_4$was higher than that of the other points of the Z-shape template. This is because the rotation angles of the corner points $v_0$ and $v_4$were different from $u_0$ ($1.5\pi$ and $0.5\pi$, respectively); thus, the algorithm identified them as two different structures. Structure is the primary factor that determines the geometric distortion cost, which also explains why some points with similar structures but different sizes had low costs, such as $u_3{v}_1$ and $u_7{v}_1$.

After breaking both shapes into chain sets and considering the positional difference, Table 7 represents the association graph with weight $w(u,v)$ in the current chain sequence. The algorithm obtained an edit path using a substitution set ($u_2{v}_0$, $u_3{v}_7$, $u_4{v}_6$, $u_5{v}_5$, $u_6{v}_4$, $u_7{v}_3$, $u_{10}{v}_2$, $u_{11}{v}_1$), with an edit cost of 0.1380. Obviously, this was not the optimal edit path between the two shapes. The matches of $u_6{v}_4$, $u_7{v}_3$, and $u_{10}{v}_2$ were not consistent with human cognition. These unsuitable matches were derived from the inappropriate match sequence. Therefore, it is necessary to switch other chains in the chain set of the test shape or template shape graph.

As shown in Figure 15, the algorithm obtained the optimal edit path using a substitution set ($u_0{v}_6$, $u_1{v}_5$, $u_2{v}_4$, $u_3{v}_3$, $u_4{v}_2$, $u_5{v}_1$, $u_9{v}_0$, and $u_{11}{v}_7$), with a minimum edit cost of 0.0823, by traversing the chain set of the template graph. In this edit path, the vertices of the two graphs associated with the corner points of the two shapes performed the substitution, and the vertices associated with the corner points of the test shapes($u_6$, $u_7$, $u_8$, $u_{10}$, and $u_{12}$) performed deletion. This edit operation was consistent with human cognition and reflected the high interpretability of the proposed GED method.

5.1.2. Major limitations of the GED method

One major limitation of the proposed GED method is its over-sensitivity to regional characteristics, which is common in structure-based methods. However, this sensitivity may not have a substantial impact on shape cognition unless numerous dense corner points and small contour segments of contours, are present, affecting the ability of the algorithm to accurately recognize regional characteristics. Second, the GED method can be time consuming when the number of vertices in the graphs is high. It exhibits a substantial disparity in efficiency when compared to GeoAI-based methods, which restrict utilizing it alone to intricate shape recognition tasks in practical scenarios.

5.2. Cluster technique for improving the method

To address this issue above mentioned limitations, we aimed to improve the accuracy of the algorithm by aggregating dense adjacent corner points into clusters when analyzing with complex shapes. In the algorithm, a cluster of points was treated as a vertex comprising the regional characteristics. Unlike simplification, this technique preserves the regional characteristics of individual points within a cluster. Every point is considered during the edit cost computation, and the cluster is considered as a single vertex during the optimal edit path determination.

Two cluster approaches were used in this study (Figure 16). One approach merged the clustering of small convex and concave structures into a single vertex. The alternative approach aggregated continuous small segments together or with large segment. a cluster operation was performed depended on the left and right contour boundary lengths of the candidates. We set a cluster threshold k (0.02–0.04; the proportion of the shape perimeter) to determine points that needed clustering.

Figure 16. Two cluster approaches: (a) aggregates continuous small segments together or with large segments, such as v₁ and v₅, and (b) clusters small convex and concave structures into one vertex, such as v₇.

Cluster operation cans affect cognition results. A larger cluster threshold can reduce the elapsed time, but it may neglect crucial details. However, an appropriate threshold can help construct a more rational graph structure. Table 8 presents the shape matching experiment results for the two cluster approaches with different thresholds. In general, the cluster technique with an appropriate threshold also can increase the accuracy of the algorithm when analyzing complex shapes. Due to the method's ability to reduce computational complexity, it holds the potential to enhance algorithm scalability, making it applicable for measuring the shape similarity of other natural features.

Table 8. Performance of shape similarity measurements using the GED method with different clusters and thresholds.

Cluster Approach & Cluster Threshold	FT	ST	DCG
GED (1st cluster approach, k =0.01)	0.869	0.973	0.990
GED (1st cluster approach, k =0.02)	0.881	0.973	0.990
GED (1st cluster approach, k =0.03)	0.855	0.947	0.985
GED (1st cluster approach, k =0.04)	0.773	0.873	0.968
GED (2nd cluster approach, k =0.01)	0.856	0.960	0.987
GED (2nd cluster approach, k =0.02)	0.874	0.976	0.990
GED (2nd cluster approach, k =0.03)	0.876	0.972	0.990
GED (2nd cluster approach, k =0.04)	0.855	0.951	0.986
Original GED method	0.865	0.977	0.989

6. Conclusion

This study proposes a graph-based similarity measurement for building shapes based on GED, which constructs cyclic graphs by extracting the local and regional characteristics of shapes, calculates edit costs using geometry distortion, and transforms the optimal edit path into a series of maximum-weight clique to accurately compute the graph edit distance. Experimental results demonstrated that the proposed method was rotation invariant, discriminative, and outperformed conventional similarity measurements (FD, TD, and MF & GCD methods).

The proposed method also has some limitations: it’s sensitivity to regional characteristics and may overlook global information; it’s unable to measure holed polygons and multi-polygons; its efficiency is not as good as GeoAI-based methods, especially for measuring intricate shapes. Future studies should develop more rational graph structures to better extract the global characteristics when analyzing complex shapes.

Moreover, the proposed GED method showed great potential for integration with current mainstream shape cognition studies based on the GNN. The GED method provides detailed similarity measurement information that can be used to construct samples for supporting supervised learning. Furthermore, combining high-precision GED methods with high-efficiency GeoAI-based methods will allow precise fine-grained measurements of shape features, thus catering to various practical application scenarios.

Acknowledgement

The authors would like to sincerely thank the anonymous reviewers and editors for their constructive comments and valuable suggestions to improve the quality of this article.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Correction Statement

This article has been corrected with minor changes. These changes do not impact the academic content of the article.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [Grant No. 41871305; 42371454; 42001340; 42122025] and the Opening Fund of Key Laboratory of Geological Survey and Evaluation of Ministry of Education [Grant No. CUG2022ZR06].