Enhancing building pattern recognition through multi-scale data and knowledge graph: a case study of C-shaped patterns

ABSTRACT

Building pattern recognition is important for understanding urban forms, automating map generalization, and visualizing 3D city models. However, current approaches based on object-independent methods have limitations in capturing all visually aware patterns due to the part-based nature of human vision. Moreover, these approaches also suffer from inefficiencies when applying proximity graph models. To address these limitations, we propose a framework that leverages multi-scale data and a knowledge graph, focusing on recognizing C-shaped building patterns. We first employ a specialized knowledge graph to represent the relationships between buildings within and across various scales. Subsequently, we convert the rules for C-shaped pattern recognition and enhancement into query conditions, where the enhancement refers to using patterns recognized at one scale to enhance pattern recognition at other scales. Finally, rule-based reasoning is applied within the constructed knowledge graph to recognize and enrich C-shaped building patterns. We verify the effectiveness of our method using multi-scale data with three levels of detail (LODs) collected from AMap, and our method achieves a higher recall rate of 26.4% for LOD1, 20.0% for LOD2, and 9.1% for LOD3 compared to existing methods with similar precision rates. We also achieve recognition efficiency improvements of 0.91, 1.37, and 9.35 times, respectively.

KEYWORDS:

• Building
• pattern recognition
• urban form
• knowledge graph
• rule-based reasoning

1. Introduction

In the context of urban environments, buildings often exhibit high-level patterns such as alphabetical shapes or linear arrangements, influenced by various socio-political, economic, cultural, or natural factors. Recognizing these patterns is essential for comprehending urban forms (Du, Shu, and Wang 2019; Yan et al. 2019), visualizing 3D city models (Hu, Fan, and Noskov 2018; Mao, Harrie, and Ban 2012), and automating map generalization (Renard and Duchêne 2014; Shen et al. 2022).

Numerous methods have been proposed to recognize building patterns automatically, which can be broadly categorized into shape recognition and arrangement recognition. Shape recognition methods employ techniques such as turning functions (Arkin et al. 1991), shape contexts (Belongie, Malik, and Puzicha 2002), Fourier descriptors (Ai et al. 2013), graph convolutional autoencoder models (Yan et al. 2021), or rectangular encodes (Wei et al. 2021) to represent and classify buildings into cognitively enhanced shapes like C-shaped or E-shaped ones. In contrast, arrangement recognition methods focus on identifying regularly arranged building clusters, such as alphabetical or linear patterns, using approaches like template matching (Rainsford and Mackaness 2002; Xing et al. 2021), structural rules (Du, Shu, and Feng 2015; Pilehforooshha and Karimi 2019; Wang and Burghardt 2020; Zhang, Ai, and Stoter 2013), or machine learning techniques (He, Zhang, and Xin 2018; Yan et al. 2019; Zhao et al. 2020). It is worth noting that, in some instances, arrangement recognition is synonymous with pattern recognition. To avoid confusion, in this work, pattern recognition will only refer to both shape recognition and arrangement recognition, while arrangement recognition solely refers to recognizing regularly arranged building clusters.

However, the majority of existing pattern recognition methods are object-independent and rely on proximity graph models, leading to two significant challenges. Firstly, object-independent methods may fail to capture all visually apparent patterns. This limitation arises from the fact that human vision operates as a part-based system, where shapes sometimes need to be decomposed into parts or grouped into clusters to accomplish visual tasks (Singh, Seyranian, and Hoffman 1999). For instance, shape recognition methods can only detect the C-shaped building in Figure 1(d), while arrangement recognition methods can solely identify the C-shaped arrangement in Figure 1(b). However, the buildings in Figures 1(a) and (c) also exhibit visually C-shaped patterns, which cannot be recognized by the aforementioned object-independent methods. Secondly, pattern recognition based on proximity graph models can be time-consuming due to the extensive searching and matching operations involved. This leads to inefficiencies in the pattern recognition process, hampering efficient analysis of large-scale datasets.

Figure 1. An example to illustrate the limitations of existing pattern recognition methods and the potential benefits of integrating multi-scale data. (a), (c) The patterns cannot be recognized using existing methods. (b) The pattern can be recognized using arrangement recognition; (d) The pattern can be recognized using shape recognition.

Multi-scale data reflects users’ understanding of how buildings can be clustered or divided at different levels (Zhang et al. 2018). Considering the part-based nature of human vision, recognizing patterns at one scale can enhance pattern recognition at other scales when integrating multi-scale data with an awareness of the corresponding relationships between buildings. For instance, if the C-shaped pattern in Figure 1(b) has been recognized, it becomes possible to recognize the buildings in Figure 1(c) as a pattern by identifying the one-to-many relations between buildings B_a, B_b in Figure 1(b) and building B_c in Figure 1(c). Recently, knowledge graphs have emerged as powerful tools for modeling relations between entities and facilitating the integration of multi-scale data (Huang and Harrie 2020; Wei et al. 2023). By storing entities and relationships as key-value pairs, knowledge graphs enable efficient reasoning to acquire new knowledge. Therefore, if we utilize a knowledge graph to represent the properties and relationships of buildings within and across different scales, the resulting building patterns as a form of new knowledge could also be efficiently and effectively recognized.

Motivated by the ideas mentioned above, we aim to enhance the efficiency and effectiveness of building pattern recognition by integrating multi-scale data through a knowledge graph. Our approach involves two main steps: first, recognizing C-shaped patterns at various scales, and second, enriching the C-shaped building patterns across scales based on the identified patterns. To achieve this, we construct a specialized knowledge graph that represents the properties and relationships of buildings within and across different scales. By converting the rules for C-shaped pattern recognition and enrichment into query conditions on the knowledge graph, we can effectively and efficiently recognize the C-shaped patterns by executing graph queries. It is important to note that C-shaped buildings, as single entities, need to be recognized beforehand as they cannot be directly identified through knowledge graphs.

In summary, our contributions, achieved through the integration of multi-scale data using a knowledge graph, can be categorized into two folds: (1) Enhanced efficiency in building pattern recognition at specific scales through rule reasoning within the constructed knowledge graph; (2) Implementation of pattern enrichments based on the recognized patterns at each scale within the constructed knowledge graph, leading to the identification of a wider range of patterns. It is important to note that previous approaches lack the incorporation of such an enrichment process.

2. Related works

2.1. Building shape recognition

Building shape recognition aims to classify buildings into cognitively enhanced shapes like C-shaped or E-shaped ones, relying on effective shape representation. There are two primary methods for shape representation: region-based and boundary-based. Region-based methods involve measuring the overall characteristics of a building's region, such as compactness (Li, Goodchild, and Church 2013) or, the equal area circle (Basaraner and Cetinkaya 2017). The European Agent program also conducted a detailed analysis of the measures for building characteristics. Among them, Duchêne, Bard, and Barillot (2003) focused on building orientation measures, while Burghardt and Steiniger (2005) investigated the principal components of a building's spatial features. Wei et al. (2018) analyzed 24 measures for describing building geometric features and proposed a measure set for building geometry analysis. Boundary-based methods approximate building shapes as strings or functions, such as turning functions (Arkin et al. 1999), shape contexts (Belongie, Malik, and Puzicha 2002), Fourier descriptors (Ai et al. 2013), and rectangular encodes (Wei et al. 2022). Additionally, artificial intelligence algorithms, including graph convolutional autoencoder models and CNN-based polygon encoders, have also been introduced for shape representation (Mai et al. 2023; Yan et al. 2021). Using these shape representation methods, buildings can then be classified into standard shapes, which are commonly used in building typification and 3D city model visualization (Yan, Ai, and Yang 2016).

In summary, existing approaches have been able to effectively recognize building shapes. However, these standard shapes represent only a part of building patterns. To achieve a more comprehensive method of pattern recognition, it is necessary to consider other information, such as patterns recognized using arrangement recognition methods at the same scale or patterns recognized at other scales.

2.2. Building arrangement recognition

Building arrangement patterns refer to the regular arrangement of buildings, and recognizing such patterns requires defining their regularity. This can be accomplished through template-based, structural rule-based, or machine learning-based methods.

Template-based methods formalize building patterns using predefined templates. For instance, Rainsford and Mackaness (2002) employed templates to detect linear patterns in rural buildings, while Xing et al. (2021) used templates to identify combined collinear patterns. Similarly, Yang (2011) and Gong and Wu (2018) introduced templates for stair-shaped, Z-shaped, and H-shaped patterns based on structural parameters. Nonetheless, these methods have limitations in recognizing all potential patterns due to their rigid formalization. Alternatively, machine learning-based methods employ intelligent algorithms such as graph convolutional networks and random forest algorithms to learn pattern recognition rules (He, Zhang, and Xin 2018; Yan et al. 2019; Zhao et al. 2020). However, these methods may require a large and diverse training dataset to enhance their accuracy. Additionally, an examination of the reasons why these algorithms are effective may also be necessary.

Structural rule-based methods define patterns as groups of buildings based on perceptual rules. Compared to the aforementioned methods, structural rule-based methods provide greater flexibility in defining patterns, making them widely used in current research. They typically utilize proximity graphs to represent building properties and relationships, and rules are subsequently defined to detect patterns. For example, Zhang, Ai, and Stoter (2013) recognized collinear and curvilinear patterns based on the minimum spanning tree (MST) and Gestalt principles. Similarly, Wei et al. (2018) detected linear patterns using four proximity graphs, where the relative nearest graph (RNG) proved to be the most accurate. Pilehforooshha and Karimi (2019) proposed a framework for detecting linear building patterns based on a defined similarity index, which was then refined by a pattern interaction index. Wang and Burghardt (2020) employed stroke principles to detect linear building patterns based on a proximity graph. As different linear building patterns may share the same buildings, Gong et al. (2014) detected multi-connected linear patterns by deleting edges from a DT-like proximity graph, grid patterns were then recognized based on these multi-connected linear patterns. Recognizing the part-based nature of human vision, Du, Shu, and Feng (2015) developed a three-level relational method based on spatial reasoning to detect collinear patterns and alphabetical-shaped patterns. Additionally, Wei et al. (2022) recognized linear building patterns combining convex polygon decomposition, where a building could be decomposed into sub-buildings for pattern recognition. However, these methods based on proximity graphs often require numerous searching and matching operations, resulting in inefficiencies, making them inefficient.

In summary, structural rule-based approaches are popular in current research due to their flexibility in meeting personalized user needs. However, their efficiency is limited by the graph traversal strategy, which hinders their application in large-scale regions. Moreover, recent studies have demonstrated that incorporating data at lower or higher levels can enhance building pattern recognition, suggesting that integrating multi-scale data could improve the effectiveness of pattern recognition.

2.3. Knowledge graph representation and rule-based reasoning

The property graph model is widely used for representing knowledge graphs (Wang et al. 2019), and in this approach, we use it to replace the proximity graph models for building pattern recognition. To store the resulting knowledge graph, we utilize Neo4j, a popular graph database. The Cypher query language in Neo4j is then applied to express the rules governing building pattern recognition. Consequently, in this section, we introduce the utilization of the property graph model in Neo4j for knowledge graph representation and rule-based reasoning. It should be noted that alternative graph models such as the resource description framework (RDF) and other graph databases can also be employed for this purpose.

A property graph in Neo4j can be represented as $G=(V,E)$, $V=\left\{v1,v2,\dots ,vn\right\}$ is an entity set, $E=\left\{e(vi,vj),vi\in V,vj\in V\right\}$ is a relationship set. Each entity, denoted by v_m, can possess zero or more labels indicating its type, while each relationship between entities v_i and v_j, denoted by e(v_i,v_j), must be assigned a type to define the nature of the relationship. Both entities and relationships have properties (key-value pairs), which further describe them. In Figure 2, the right part illustrates demonstrates how a property graph can represent proximity relations (Has_Proxi), area similarity relations (Has_Sim), and the area similarity degree (SimDeg) among three buildings. Compared to the representation using a proximity graph (the left part of Figure 2), e(v_i,v_j) in a property graph can represent various relations, while e(v_i,v_j) in a proximity graph can only represent a proximity relation. It is worth noting that proximity graphs and property graphs can have different expressions according to practical requirements, Figure 2 is presented solely to provide examples.

Figure 2. Comparison of representing buildings and their relationships using proximity graph and property graph. (a) Buildings; (b) Proximity graph representation; (c) Property graph representation.

Once a knowledge graph is constructed and stored, new knowledge can be inferred by formulating rules as query conditions using the Cypher language. For example, to identify buildings with exactly two neighbors, the rules can be defined as depicted in Table 1. By converting these rules into Cypher query conditions, we can retrieve buildings that satisfy the specified criteria. In this case, the building with bID 1 can be obtained.

Table 1. Rules via Cypher language to identify buildings with exactly two neighbors.

MATCH (B1:Building)<-[:Has_Proxi]->(B2:Building), (B1:Building)<-[:Has_Proxi]->(B3:Building) RETURN B1

3. The knowledge graph representation

As per the illustrations in the introduction, the primary focus of our method is using a knowledge graph to recognize the C-shaped building arrangements initially, and enrich the C-shaped building patterns across scales subsequently. Hence, knowledge graph representation encompasses two key aspects. Firstly, it involves representing the relations between buildings, specifically targeting the recognition of C-shaped building arrangements at a particular scale. Secondly, it entails representing the corresponding relations between buildings across various scales.

3.1. Defining the building relations at a particular scale

According to Du, Shu, and Feng (2015) and Gong and Wu (2018), a C-shaped building arrangement comprises three adjacent buildings, with one building in the middle and two buildings on either side that form the wings of the C shape. The wing buildings are fully parallel to each other and partially perpendicular to the middle building. Therefore, to recognize a C-shaped building arrangement, it is necessary to define the ‘proximity relation’, ‘fully parallel relation’, and ‘partially perpendicular relation’, and establishing ‘interval relations’ is the first step in defining the latter two (Du, Shu, and Feng 2015).

(1) Proximity relation

The proximity relation between two buildings in topological maps is typically determined by adjacency or shared borders or corners. Because buildings separated by roads are not considered adjacent, we propose using the constrained Delaunay triangulation (CDT) skeleton, which takes roads into account, for detecting proximity relations between buildings based on the work of Liu et al. (2014). As shown in Figure 3(a), buildings that share the same CDT skeleton are considered to be in proximity to each other, and a proximity graph $PG=(PE,PV)$ can then be built to represent the proximity relations between buildings, as shown in Figure 3(b). $PV=\{pv1,pv2,\dots ,pvm\}$ is the node set, where pv_m represents building B_m. $PE=\left\{pe\right(pvi,pvj),pvi\in PV,vj\in PV\}$ is the edge set, where pe(pv_i, pv_j) indicates that buildings B_i and B_j are in proximity to each other. The proximity relation between B_i and B_j, denoted as P(B_i, B_j), is symmetric, which means P(B_i, B_j)$\leftrightarrow$ P(B_j, B_i).

Figure 3. Proximity relations between buildings. (a) The constrained Delaunay triangulation (CDT) skeleton; (b) The proximity graph.

(2) Interval relation

We approximate the buildings by their smallest bounding rectangles (SBRs) to define the interval relation between two buildings, as proposed by Du, Shu, and Feng (2015). Suppose two buildings B_a (the referent one) and B_b (the target one), their SBRs are SBR(B_a) and SBR(B_b). The long and short axes of SBR(B_a) are represented as l_a and s_a, respectively. The interval relation between B_a and B_b (as shown in Figure 4(a)) can be defined by projecting SBR(B_b) onto l_a and s_a, denoted as r(l_a, $l_a^b$) and r(s_a, $s_a^b$), and form a relation $r(Ba,Bb)=r(la,l_a^b)\times r(sa,s_a^b)$, where $l_a^b$ and $s_a^b$ are the projections. Based on the interval algebra introduced by Allen (1983), $r(la,l_a^b)$ or $r(sa,s_a^b)$ can be modeled as 13 basic relations. Thus, $r(Ba,Bb)$ can be defined as 169 basic relations, as shown in Figure 4(b). It is worth noting that non-overlapped relations are more prevalent in reality, and we exclude overlapped interval relations (indicated by × in Figure 4) in this proposed approach. To prevent excessive over-approximation or overlapped interval relations, we incorporate the rectangularity (S_rec) to determine whether a building can be approximated by its SBR, where S_rec is defined as Equation (1). (1) $Srec=A/Asbr$(1) A is the area of the building, and A_sbr is the area of its SBR. If a building is with $Srec\ge 0.6$, we approximate it using its SBR; else it indicates a complex shape that is less likely to form a regular arrangement (Du, Shu, and Feng 2015; Zhang, Ai, and Stoter 2013), and we represent it as-is, without considering interval relations for such buildings in our approach. Consequently, buildings with complex shapes are excluded from the C-shaped arrangement recognition process.

Figure 4. The interval relations between two buildings.

To further measure the facing degree between two buildings (B_a and B_b) in an interval relation, the facing ratio (F_d) is defined as Equation (2). (2) $Fd(Ba,Bb)=Max\left\{Overlap\right(l_a^b,la)/Merge(l_a^b,la),Overlap(s_a^b,sa)/Merge(s_a^b,sa)\}$(2) where Overlap means an intersection, and Merge means a union.

(3) Fully parallel relation

Two buildings, B_a and B_b, are considered fully parallel (Full_Para) if they have a similar size (SimA), parallel directions(ParaO), their long axes overlap over a certain degree and two buildings fully overlap on long axes only, and is defined as Equation (3) (Du, Shu, and Feng 2015). (3) $\begin{array}{rl}& Full\mathrm{\_}Para(Ba,Bb)=def\left\{SimA\right(Ba,Bb)\wedge ParaO(Ba,Bb)\wedge FR(Ba,Bb)\ge \delta 1\\ & \wedge r(Ba,Bb)\in \{r1,j,r2,j,r12,j,r13,j{\}}_{j=3}^{11}\}\\ & WhereSimA(Ba,Bb)=def\left(\right|Aa/Ab-1|\le \delta 2),\\ & ParaO(Ba,Bb)=def\left(\right|Oa-Ob|\le \delta 3\vee (180-\left|Oa-Ob\right|)\le \delta 3)\end{array}$(3) where A is the building area, O is the orientation of the SBR of a building, $\delta 1$, $\delta 2$, and$\delta 3$ are thresholds.

(4) Partially perpendicular relation

A buildings B_b is considered partially perpendicular (Part_Per) to building B_a if they have perpendicular directions (PerO) and the projections of B_b onto B_a either partly overlap with the axes of B_a, and is defined as Equation (4). (4) $\begin{array}{rl}& Part\mathrm{\_}Per(Ba,Bb)=def\left\{PerO\right(Ba,Bb)\wedge r(Ba,Bb)\in \\ & \{r1,3,r2,3,r1,11,r2,11,r12,3,r13,3,r12,11,r13,11\}\}\\ & WherePerO(Ba,Bb)=def\left\{\right(90-\left|Oa-Ob\right|)\le \delta 3\}\end{array}$(4) where O is the orientation of the SBR of a building.

3.2. Defining the corresponding building relations across various scales

When buildings are represented at smaller scales, they may undergo simplification, elimination, aggregation with others, or collapse into points. This leads to coarser or more abstract representations of buildings at larger scales. Depending on the level of detail, six relations can occur between buildings across different scales, as detailed in Table 2 (Fan et al. 2014; Memduhoglu and Basaraner 2022). These relations encompass one-to-one, one-to-many, many-to-one, and many-to-many matches between corresponding buildings at different scales. However, in some cases, a building at one scale may not have a corresponding match at the other scale, resulting in either a one-to-none or none-to-one relation.

Table 2. The definition for corresponding building relations across various scales.

One-to-one relation: A building at one scale corresponds to one and only one at another scale; One-to-many relation: A building at one scale corresponds to multiple buildings at another scale; Many-to-one relation: Multiple buildings at one scale correspond to one building at another scale; Many-to-many relation: Multiple buildings at one scale correspond to multiple buildings at another scale; One-to-none relation: A building at one scale corresponds to no buildings at another scale; None-to-one relation: No buildings at one scale correspond to any buildings at another scale.

3.3. Representing the buildings and their relations in a knowledge graph

We utilize the property graph model to construct the knowledge graph, representing the buildings and building relations within the knowledge graph as $G=(V,E)$, where $V=\left\{v1,v2,\dots ,vn\right\}$ refers to the entity set, $E=\left\{e(vi,vj),vi\in V,vj\in V\right\}$ is the relation set, V and E are defined as follows.

(1) Entities

The entities are individual buildings or building groups, each of which possesses a property as ‘Scale’ that designates the scale of the associated building data. To differentiate between individual buildings and building groups, entities are assigned labels as ‘SingleB’ and ‘GroupB’. As defined in Equations (3) and (4) for fully parallel relation (Full_Para) and partially perpendicular relation (Part_Per), building area and orientation are involved. Therefore, the area and orientation are represented as the property of a building entity. Because we aim to recognize C-shaped patterns, a property ‘ShapeC’ is given to indicate whether an entity is a C-shaped one. Based on the above analysis, the entities in a knowledge graph are represented in Table 3.

Table 3. The entity representation in the knowledge graph.

Class	Element	Description
Entity	vi	Indicates an entity
Entity label	SingleB	Indicates an entity as an individual building
	Group B	Indicates an entity as a building group
Entity property	vID	Unique identifier of an entity
	Scale	Indicates the scale of the building data
	Area	Indicates the area of a building
	Ori	Indicates the orientation of the SBR of a building
	ShapeC	Indicates whether an entity is a C-shaped one (true or false)

(2) Relations

Recognizing C-shaped building patterns involves several types of relations at a particular scale, including proximity, interval, Full_Para, and Part_Per, as well as matching relations across scales. In addition, a ‘Belong_To’ relation needs to be included to indicate that an individual building entity is part of a group building entity.

To represent relations at a particular scale, Full_Para, and Part_Per relations can be derived from size, orientation, proximity, and interval relations between buildings. Since the area and orientation of a building are already represented as properties of a building entity, we focus on representing proximity and interval relations in the knowledge graph. Full_Para and Part_Per relations will be obtained through rule-based reasoning within the constructed knowledge graph. To distinguish between proximity and interval relations, we assign the ‘Has_Proxi’ and ‘Has_Interval’ types to these relations. The basic type of an interval relation is denoted by a property as ‘Inter_T’. For instance, if buildings B_i and B_j, represented as entity v_i and v_j, are proximate to each other, a relation e(v_i,v_j) is established with the type ‘Has_Proxi’, indicating that e(v_i,v_j) is a proximity relation.

The corresponding relationships between two buildings across scales, including one-to-one, one-to-many, many-to-one, and many-to-many, can be represented as ‘Has_Match’ with a property ‘Match_T’, where ‘Match_T’ values correspond to the relationship types. For instance, if two entities, v_i and v_j, have a ‘Has_Match’ relation with property ‘Match_T’ of one-to-many, this implies a one-to-many relationship between v_i and v_j. Additionally, none-to-one and one-to-none relationships can be explicitly expressed if they are not represented in a knowledge graph.

Based on the above analysis, Table 4 illustrates the representation of relations within a knowledge graph. Using this representation of entities and relations, we can construct and store a knowledge graph in Neo4j, an example of a constructed knowledge graph is shown in Figure 5. It is important to note that different knowledge graphs can be built for this task, and we will discuss building a different knowledge graph in Section 6.1.

Figure 5. The constructed knowledge graph for multi-scale building data in Neo4j. (a) The multi-scale building data; (b) The query window; (c) The constructed knowledge graph; (d) Detailed information about a selected entity or relation.

Table 4. The relation representation in the knowledge graph.

Class	Element	Description
Relation	e(vi,vj)	Indicates a relation
Relation type	Has_Proxi	Indicates that a relation is a proximity relation between two building entities
	Has_Inter	Indicates that a relation is an interval relation between two building entities
	Has_Match	Indicates that a relation is a matching relation between two entities
	Belong_To	Indicates a relation that a building entity is part of a building group entity
Relation property	eID	Unique identifier of a relation
	Inter_T	A property of relation ‘Has_Inter’, indicates the type of ‘Has_Inter’. Suppose the type of a ‘Has_Inter’ is ri,j, the value of Inter_T is calculated as (i-1)*13 + j
	Face_R	A property of relation ‘Has_Inter’, indicates the facing degree of two buildings
	Match_T	A property of relation ‘Has_Match’, indicates the type of ‘Has_Match'

4. C-shaped building pattern recognition using rule-based reasoning

C-shaped building pattern recognition via rule-based reasoning within the built knowledge graph in our proposed approach involves two steps: recognizing C-shaped building arrangements at a particular scale and enriching the patterns across different scales. It is important to note that C-shaped buildings have been recognized beforehand.

4.1. Recognizing C-shaped building arrangements at a particular scale

A C-shaped building arrangement consists of three adjacent buildings, with one building in the middle (B_M) and two wing buildings (B_W1 and B_W2) on either side. The wing buildings are fully parallel to each other, while also being partially perpendicular to the middle building, and a C-shaped building arrangement is defined as Equation (5). (5) $\begin{array}{rl}& C\mathrm{\_}Pattern(BM,BW1,BW2)=def\left\{P\right(BM,BW1)\wedge P(BM,BW2)\wedge P(BW1,BW2)\\ & \wedge Full\mathrm{\_}Para(BW1,BW2)\wedge Part\mathrm{\_}Per(BM,BW1)\wedge Part\mathrm{\_}Per(BM,BW2)\}\end{array}$(5) To recognize a C-shaped building arrangement within the constructed knowledge graph, the definition needs to be converted into rules that are suitable for rule-based reasoning. Since we store the knowledge graph in a Neo4j database, we utilize the Cypher language to define rules for deriving the C-shaped building arrangement. As defined in Equation (5), Full_Para and Part_Per relations need to be obtained because they are not represented in the knowledge graph. Additionally, similar size (SimA), parallel directions(ParaO), and perpendicular directions (PerO) relations need to be determined for establishing Full_Para and Part_Per relations, as defined in Equations (3) and (4). Therefore, the rule-based reasoning process for C-shaped building arrangement recognition consists of three steps: (1) verify the SimA, ParaO, and PerO relations; (2) verify the Full-Para and Part_Per relations; (3) recognize the C-shape building arrangements. The overall process is illustrated in Figure 6.

Figure 6. The flowchart for recognizing C-shaped building arrangements. (a) Verify the SimA, ParaO, and PerO relations; (b) Verify the Full-Para and Part_Per relations; (c) Recognize the C-shape building arrangements.

4.2. Enriching C-shaped building patterns across various scales

Our method considers two types of enrichments, as identified by Wei et al. (2022) and Xing et al. (2021). Wei et al. (2022) proposed decomposing a building into sub-buildings for pattern recognition. Buildings at larger scales represent potential subdivisions of the buildings at a smaller scale, allowing structural patterns recognized at a larger scale to enrich those recognized at a smaller scale (i.e. bottom-up enrichment). In contrast, Xing et al. (2021) suggested grouping buildings into clusters for pattern recognition. Buildings at smaller scales represent potential building groups at a larger scale, enabling structural patterns recognized at a smaller scale to enrich those recognized at a larger scale (i.e. Top-down enrichment).

(1) Bottom-up enrichment

For bottom-up enrichment, suppose three buildings (B_a, B_b, B_c) as a group at a larger scale (S_b) are recognized as a C-shaped pattern. Their corresponding buildings at a smaller scale (S_u) are $BS=\left\{Bi{\}}_{i=1}^n\right(n\ge 1)$. As proposed by Wei et al. (2022), a building at a smaller scale can be decomposed into sub-buildings for building pattern recognition. If B_a, B_b, and B_c are part of B_i (i.e. have a many-to-one or one-to-one relation), then $BS=\left\{Bi{\}}_{i=1}^n\right(n\ge 1)$ can potentially form a C-shaped pattern. Take the C-shaped building pattern (B₀, B₁, B₂) in Figure 7(a) as an example, B₃ at a larger scale has a one-to-one relation with B₀, B₄ at a larger scale has a one-to-many relation to B₁, and B₂, then B₃ and B₄ can potentially form a C-shaped pattern. The process for bottom-up enrichment is shown in Figure 7(b).

Figure 7. The example process for building pattern enrichments across various scales. (a) The multi-scale building data; (b) The bottom-up enrichment; (c) The top-down enrichment.

(2) Top-down enrichment

For top-down enrichment, suppose a building or a building group is recognized as a C-shaped pattern at a smaller scale (S_u). Their corresponding building groups at a larger scale (S_b) are$BS=\left\{Bi{\}}_{i=1}^n\right(n\ge 1)$. As proposed by Xing et al. (2021), buildings can be grouped into clusters for pattern recognition. If $BS=\left\{Bi{\}}_{i=1}^n\right(n\ge 1)$ are parts of B_a, (i.e. have a one-to-many or one-to-one relation), then $BS=\left\{Bi{\}}_{i=1}^n\right(n\ge 1)$ can potentially form a C-shaped pattern. Take the C-shaped building B₅ in Figure 7(a) as an example, B₃ and B₄ at a larger scale have a one-to-many relation to B₅, then B₃ and B₄ can potentially form a C-shaped pattern. The process for top-down enrichment is shown in Figure 7(c).

5. Experiments

5.1. Benchmark dataset and experimental environment

5.1.1. Benchmark dataset

The AMap offers spatial data across 20 different levels of detail. Since buildings are predominantly displayed at larger scales, we utilized a building dataset obtained from the AMap, focusing specifically on three levels of detail (levels 8–11) that served as our benchmark dataset. These levels of detail correspond to different scales: approximately 1:5000, 1:10000, and 1:20000 for levels 8, 9, and 10, respectively. This dataset was sourced from a specific area in Nanjing, China, as illustrated in Figure 8. The spatial characteristics of buildings within the benchmark dataset including building count (B_c), average area (Ave_A), average edge count (Ave_E_d), the rate of buildings with edge count fewer than eight ($REd\le 8$), average rectangularity (Ave_S_rec), and the rate of buildings with rectangularity greater than 0.6 ($RSrec\ge 0.6$) are presented in Table 5 (Wei et al. 2022). From the table, we can make the following observations. Firstly, the majority of the buildings exhibit simple shapes, as indicated by the high values of $REd\le 8$(>0.64) and $RSrec\ge 0.6$ (>0.78). This implies that the buildings in this benchmark dataset can be reasonably approximated with their SBRs for C-shaped arrangement recognition. Secondly, as the scale decreases, there is a corresponding increase in Ave_Area, while $REd\le 8$, Ave_S_rec, and $RSrec\ge 0.6$ decrease. This suggests that the buildings become more complex in shape, and shape recognition is also a crucial factor for enriching C-shaped building patterns as the scale decreases.

Figure 8. Benchmark dataset.

Table 5. Analysis of the spatial characteristics of buildings in the study area.

Data	Scale	Bc	Ave_Area/m^2	Ave_Ed	$REd\le 8$	Ave_Srec	$RSrec\ge 0.6$
Lod1	1: 5000	1977	797.22	8.78	0.69	0.80	0.89
Lod2	1: 10000	618	2528.14	9.48	0.67	0.80	0.83
Lod3	1: 20000	337	4602.54	8.18	0.64	0.78	0.78

5.1.2. Experimental environment

We utilized the C# code to compute the measures for spatial characteristics of buildings and their relationships based on ArcEngine 10.2. The resulting knowledge graph was stored in Neo4j 1.4.12, and rule-based reasoning was implemented using Cypher language. The experiments were conducted on a personal computer equipped with an Intel® Core™ 1.60 GHz i5-8265U CPU and 8G RAM.

5.2. Constructing the knowledge graph and its visualization

(1) Deriving the building relations at a particular scale

Section 3.1 outlines the derivation process of building relations at a particular scale. Initially, a proximity graph was proposed to represent proximity relations between buildings. Based on these proximity relations, we derived the interval relations, fully parallel relations (Full_Para), and partially perpendicular relations (Part_Per) between buildings. To define the Full_Para and Part_Per relations, we used the thresholds in Equations (3) and (4) according to Du, Shu, and Feng (2015) and Wei et al. (2022), as follows: $\delta 1=0.4$, $\delta 2=2$, and $\delta 3=15$.

(2) Deriving the corresponding relations between buildings at various scales

To identify the corresponding relations between buildings at various scales, a geometric matching process can be performed. However, since geometric matching is not the primary focus of our approach, we employed a simple but efficient method proposed by Fan et al. (2014) and Memduhoglu and Basaraner (2022) and identified corresponding buildings (B_ref and B_tar) based on their overlapping areas, as defined in Equation (6). Specifically, if $Roverlap\ge 0.3$, B_ref and B_tar were considered to be corresponding buildings. To ensure more accurate identification of corresponding relations, manual adjustments were made to refine the identified relations between buildings following the aforementioned process. (6) $Roverlap={\displaystyle \frac{Aref\cap tar}{\mathrm{M}\mathrm{i}\mathrm{n}(Aref,Atar)}}$(6) A_ref and A_tar are areas of B_ref and B_tar, and $Aref\cap tar$is the overlapping area of B_ref and B_tar.

(3) The knowledge graph and visualization

Building upon the illustrations presented in Section 3.3, we can represent the building relations within and across various scales as a knowledge graph, as depicted in Figure 9. Figure 9(a) visualizes the proximity relations at a particular scale (Has_Proxi) and the corresponding relations across various scales (Has_Match), which was implemented via EChart, and a force-direct method was applied to avoid crosses and overlaps between nodes and edges as much as possible (Li et al. 2018). Figure 9(a) demonstrates that the defined proximity relations result in the formation of different clusters of building entities. Moreover, Figure 9(b) provides a more detailed view of the constructed knowledge graph, effectively showcasing how the inter-building relationships in a local area can be accurately represented as a knowledge graph.

Figure 9. (a) The constructed knowledge graph; (b) An enlarged view.

5.3. Pattern recognition results

5.3.1. Effectiveness evaluation

(1) Implement details

Pattern enrichments, as introduced in Section 4.2, represent a novel addition to our proposed approach, allowing for the recognition of a wider range of C-shaped building patterns compared to previous methods. To evaluate the effectiveness of our approach, we conducted a comparative experiment comprising two distinct parts: (1) the recognition of C-shaped buildings and building arrangements without pattern enrichments (SP + PP), and (2) the recognition of C-shaped buildings and building arrangements with pattern enrichments (SP + PP + EP). C-shaped buildings were initially identified through manual shape recognition, while C-shaped building arrangements were recognized within the constructed knowledge graph using the rules defined in Section 4.1. Furthermore, C-shaped pattern enrichments were implemented within the constructed knowledge graph using the rules defined in Section 4.2.

To evaluate the performance, we adopted two metrics, Precision and Recall, as proposed by Du, Shu, and Feng (2015). Precision and Recall values were determined by comparing the recognized patterns with those manually identified by three experienced graduate students specializing in cartography and geographic information science. These students independently annotated the C-shaped patterns, being aware that the buildings could be organized into groups or decomposed to facilitate pattern recognition. In cases where the annotated results were inconsistent, a voting system was implemented to reach a consensus. Recognized patterns that were consistent with those identified by the students were denoted as true positives (tp), while inconsistent patterns were denoted as false positives (fp). Patterns that went unnoticed by the proposed method were denoted as false negatives (fn). Precision and Recall values were calculated using Equations (7) and (8). (7) $Precision=tp/(tp+fp)$(7) (8) $Recall=tp/(tp+fn)$(8)

(2) Results

The C-shaped patterns obtained through our proposed method are illustrated in Figure 10, while the corresponding statistics are presented in Table 6. Examining Figure 10 and Table 6, it is evident that the implementation of pattern enrichments leads to improved Recall values. Specifically, for Lod1, the Recall value increases by 26.4%, for Lod2 it increases 20.0%, and for Lod3 it increases 9.1% when compared to the results obtained without pattern enrichments. These findings indicate that the pattern enrichments can help recognize more C-shaped building patterns. This difference can be attributed to the fact that human vision is a part-based system, and object-independent pattern recognition is insufficient to recognize all potential patterns. For example, the C-shaped arrangements P1 and P2 (Area A in Figure 10) can only be partially recognized, and P3, P4, P5, and P6 can’t be recognized with the existing method (Area A and Area B in Figure 10). However, all of these patterns can be recognized using the proposed approach, and these patterns are also visually aware patterns by users. Particularly, P1, P2, P3, P4, and P5 are recognized with top-down pattern enrichments, and P6 is recognized with bottom-up pattern enrichments.

Figure 10. C-shaped building pattern recognition results.

Table 6. Evaluation of the effectiveness.

Data	Method	tp	fp	fn	Precision ↑	Recall ↑
Lod 1	SP + PP	23	4	11	85.2%	67.7%
	SP + PP + EP	32	6	2	84.2%	94.1%
Lod 2	SP + PP	31	0	9	100%	77.5%
	SP + PP + EP	39	3	1	92.9%	97.5%
Lod 3	SP + PP	27	0	6	100%	81.8%
	SP + PP + EP	30	2	3	97.0%	90.9%

Regarding Precision, we can observe that high Precision values can be achieved if pattern enrichments are implemented. Specifically, the Precision value for Lod1 is 84.2%, for Lod2 it is 92.9%, and for Lod3 it is 97%. However, it is important to note that implementing pattern enrichments may also lead to a decrease in Precision. The Precision values decrease amounts to 1.0% for Lod1, 7.1% for Lod2, and 3% for Lod3. These indicate that while pattern enrichments assist in recognizing more patterns, they may also introduce misrecognitions, such as those shown in Figure 10. Such misrecognitions occur since patterns are only stable within certain scale ranges or periods, and patterns at different scales can be altered through map generalization or changes in geographical features (Tenerelli and Ehrlich 2011). For example, the C-shaped building in 10(d) can be recognized via shape recognition, but its corresponding building at higher levels is more likely to have a rectangular shape, which will lead to a misrecognition in a bottom-up pattern enrichment. In Section 6.3, we will delve into a detailed analysis of the underlying factors that contribute to misrecognition and discuss potential strategies to address this issue Figure 11.

Figure 11. C-shaped building pattern misrecognition results.

5.3.2. Efficiency evaluation

(1) Implement details

A key innovation of our proposed approach is the efficient recognition of C-shaped building patterns through the utilization of a knowledge graph, in contrast to the predominant reliance on proximity graphs in previous works. To evaluate the efficiency of our proposed approach, we performed a comparative experiment wherein we separately recognized C-shaped building arrangements using both a proximity graph and a knowledge graph. Both methods applied the same rules, as defined in Section 4.1, to recognize the C-shaped building arrangements. To ensure the robustness of the results, each method underwent testing in 10 experiments. In evaluating the efficiency, we considered the entity count (v_c), minimum time (Min_t), maximum time (Max_t), and average time (Ave_t).

(2) Results

The efficiency results are presented in Table 7. Notably, the Ave_t value for our proposed method is 1.368s for Lod1, 0.558s for Lod2, and 0.351s for Lod3. Comparing these values to the method utilizing a proximity graph, our proposed approach achieves speeds that are 9.35, 1.37, and 0.91 times faster, respectively. These results indicate that our method offers improved efficiency. Moreover, the Ave_t values exhibit an approximately linear increase with the growth in v_c. This observation suggests that the average time required does not sharply escalate with larger data sizes, indicating that our method is well-suited for handling large areas. This efficiency can be attributed to the utilization of a knowledge graph, which stores entity relations as key-value pairs, eliminating the need for extensive computing resources to establish entity matching. In summary, our method not only offers improved efficiency compared to the proximity graph-based methods but also provides significant enhancements in efficiency as the data size increases.

Table 7. Evaluation of the efficiency.

Data	Method	vc	Min_t/s	Max_t/s	Ave_t/s↓
Lod1	Proximity graph-based	1977	12.298	13.104	12.787
	Knowledge graph-based		0.841	1.677	1.368
Lod2	Proximity graph-based	618	0.712	0.887	0.765
	Knowledge graph-based		0.420	0.902	0.558
Lod3	Proximity graph-based	337	0.311	0.345	0.321
	Knowledge graph-based		0.324	0.468	0.351

6. Discussions

6.1. Constructing a different knowledge graph

The extensibility of the knowledge graph is a key advantage that we leverage to construct the knowledge graph in a flexible and scalable bottom-up manner, tailored to the specific application requirements. In practice, different knowledge graphs can be constructed based on diverse needs. For instance, we have represented building size, orientation, proximity, and interval relations in the knowledge graph, while Full_Para and Part_Per are obtained through rule-based reasoning. Alternatively, we can directly represent Full_Para and Part_Per relations to build a different knowledge graph, as shown in Table 8. This would simplify the rules for pattern recognition. However, obtaining Full_Para and Part_Per before constructing the knowledge graph would take a longer time. Despite this, it would also enable recognition of the C-shaped building patterns.

Table 8. The elements of knowledge graph for C-shaped building pattern recognition.

Class	Element	Description
Entity	vi	Indicates an entity
Entity label	SingleB	Indicates an entity as an individual building
	Group B	Indicates an entity as a building group
Entity property	vID	Unique identifier of an entity
	Scale	Indicates the scale of the building data
	ShapeC	Indicates whether an entity is a C-shaped one (true or false)
Relation	e(vi,vj)	Indicates a relation
Relation type	Full_Para	Indicates that a relation is a fully parallel relation between two building entities
	Part_Per	Indicates that a relation is a partially perpendicular relation between two building entities
	Has_Match	Indicates that a relation is a matching relation between two entities
	Belong_To	Indicates a relation that a building entity is part of a building group entity
Relation property	eID	Unique identifier of a relation
	Match_T	A property of relation ‘Has_Match’, indicates the type of ‘Has_Match'

6.2. Recognizing other kinds of structural patterns

To facilitate the recognition of C-shaped building patterns, we represent the underlying relations as a knowledge graph and formulate the rules for pattern recognition and enrichment as query conditions on the graph. This methodology can also be extended to identify other types of building patterns, such as the E-shaped building patterns. For our experimental analysis, we utilized two levels of data, namely nominal scales of approximately 1:5000 and 1:20000, containing a total of 5014 and 778 buildings, respectively, collected from the AMap dataset. The rules used for recognizing E-shaped building arrangements were consistent with those outlined by Du, Shu, and Feng (2015). The corresponding outcomes are presented in Figure 12 and Table 9. The results indicate that our proposed method achieves comparable recognition outcomes for E-shaped building patterns, albeit with a slightly lower Precision (9.5% decrease and 6.2% decrease) but higher Recall (47.6% increase and 5.2% increase). Notably, the patterns depicted in Figures 12(c)−(f) require cross-scale enrichments for accurate recognition, which existing approaches fail to accomplish.

Figure 12. Recognition of other kinds of structural patterns.

Table 9. Evaluation of the effectiveness.

Data	Method	tp	fp	Fn	Precision ↑	Recall ↑
Lod 1	SP + PP	9	0	13	100%	42.9%
	SP + PP + EP	19	2	2	90.5%	90.5%
Lod 2	SP + PP	14	0	5	100%	73.7%
	SP + PP + EP	15	1	4	93.8%	78.9%

6.3. Analyzing misrecognition results and potential strategies

Our proposed approach integrates multi-scale data using a knowledge graph to enhance the recognition of building patterns in a more effective and efficient manner. However, it is important to note that this approach may occasionally misrecognize certain patterns. This occurs due to the dynamic nature of buildings, which can change at different scales. Chen, Zhang, and Lin (2018) identified two primary factors contributing to changes in map objects within multi-scale data: map generalization and real changes in geographical features.

Firstly, buildings at a smaller scale are typically derived through map generalization based on data from a larger scale. As a result of map generalization, buildings may undergo significant changes such as deletion. Then the patterns containing these buildings at a smaller scale may also be altered. For example, in Figure 13(a), left part, three buildings are recognized as a H-shaped structure at a larger scale. However, at a smaller scale, the corresponding buildings are more likely to form a parallel pattern due to the removal of a small building. Similarly, in the right part of Figure 13(a), a C-shaped building at a larger scale may be simplified into a rectangular shape at a smaller scale. Both of these scenarios can lead to the misrecognition of building patterns. To address this problem, studying the variation law of building patterns with respect to scale may be necessary. These findings can then be incorporated into rules within our pattern enrichment process to enhance its effectiveness.

Figure 13. Causes contributing to misrecognition of building patterns: (a) Map generalization and (b) Real changes.

Second, multi-scale data may be acquired at different points in time, and buildings can change during this period. For example, buildings may be demolished or reconstructed, as depicted in Figure 13(b). Consequently, the associated patterns can also be altered. In the left part of Figure 13(b), four buildings can be recognized as an E-shaped pattern, but at a later time, they are more likely to form a C-shaped pattern due to the demolition of a building during the period. Likewise, in the right part of Figure 13(b), an H-shaped building at an earlier time may change into a C-shaped building at a later time due to reconstruction. These scenarios can also result in the misrecognition of building patterns. To address this problem, it is essential to analyze the differences between changes caused by map generalization and those resulting from real changes. By identifying these real changes, and pattern enrichments may not be suitable for areas exhibiting such changes.

7. Conclusion

To improve the efficiency and effectiveness of recognizing building patterns in topographical maps, we proposed a method that integrates multi-scale data using a knowledge graph. As a case study, we focused on the C-shaped building pattern and represented the relationships between buildings within and across different scales in a knowledge graph. We then used rule-based reasoning to recognize and enrich patterns across scales within the built knowledge graph. Our results demonstrated that our method achieved higher recall and efficiency compared to existing approaches, with a recall of 26.4% for LOD1, 20.0% for LOD2, and 9.1% for LOD3, and an efficiency improvement of 0.91, 1.37, and 9.35 times. Additionally, our proposed approach was capable of recognizing other building patterns, such as E-shaped patterns.

However, we also found that patterns were only stable within a certain scale range or period. The patterns at different scales could change due to map generalization or realistic changes in geographical features, leading to misrecognition. Therefore, future work will focus on understanding the variation law of building patterns with scales or periods to enable more effective pattern recognition across scales.

Data and code availability statement and data deposition

The data and code that support the findings of this study are all openly available, website is: https://github.com/TrentonWei/Linear-Building-Pattern-Recognition-.git

Acknowledgments

The authors would like to thank the anonymous reviewers for their helpful and constructive comments that greatly contributed to improving the manuscript.

Disclosure statement

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

Additional information

Funding

This work was supported by The National Natural Science Foundation of China (No. 41871378), The Youth Innovation Promotion Association Foundation of Chinese Academic of Sciences(No.Y9C0060), Fundamental Research Funds for the Central Universities (No. 070323006), and State Key Laboratory of Networking and Switching Technology (No. 600123442).