Linear building pattern recognition via spatial knowledge graph

Zhiwei Wei, Yi Xiao, Ying Tong, Wenjia Xu, Yang WangarXiv 2023 · DOI · arXiv

TL;DR

This paper introduces a novel approach to identifying linear building patterns in urban maps by leveraging Spatial Knowledge Graphs. By modeling buildings and their spatial relationships as a property graph and using the Cypher query language for reasoning, the researchers achieved a nearly 6x speedup over traditional graph isomorphism methods while maintaining high recognition accuracy.

What Problem Does This Paper Address?

In urban planning, cartography, and social-economic analysis, understanding the spatial arrangement of buildings—known as "building patterns"—is crucial. Linear patterns (buildings lined up along a street or axis) are the most fundamental of these structures.

Traditionally, researchers have used two main approaches:

  1. Template Matching: Rigid and often fails to account for local variations.
  2. Graph Isomorphism/Traversal: Modeling buildings as nodes in a proximity graph and using algorithms to find specific subgraphs.

The "bottleneck" is efficiency. As the number of buildings in a dataset grows, traditional graph traversal and rule-based matching become computationally expensive and slow. The authors sought a way to make this process scalable for large-scale urban datasets without losing the flexibility of rule-based logic.

Methods

The authors propose a three-step workflow centered on a Property Graph model (implemented in Neo4j):

  1. Spatial Relation Modeling: Instead of just looking at coordinates, they define three key "Gestalt" relationships between buildings:
  2. Proximity: Using a Relative Neighborhood Graph (RNG) constrained by roads to determine which buildings are "neighbors."
    • Similarity: Calculating differences in area, orientation (using Smallest Bounding Rectangles), and shape complexity (edge count).
  3. Linearity: Defining "triplets" of buildings that satisfy specific thresholds for angle deviation and distance.
  4. Knowledge Graph Construction: These relationships are stored as edges (HAS_PROXI, HAS_SIM) and properties within a Neo4j database. This transforms a geometric problem into a topological query problem.
  5. Rule-Based Reasoning via Cypher: The core innovation is translating recognition rules into Cypher queries. Instead of writing custom traversal code, they use Cypher’s efficient subgraph matching capabilities to:
  6. Identify all valid triplets of buildings.
  7. Apply an Align_Rule to merge overlapping triplets into longer linear chains.

Datasets

The study utilized data from OpenStreetMap (OSM):

  • Primary Test Area: A section of Dresden, Germany, containing 1,286 buildings.
  • Scalability Benchmarks: Five datasets of increasing size, ranging from 36 entities (Dataset_1) to 3,566 entities (Dataset_5), were used to compare the efficiency of the Knowledge Graph approach against traditional graph isomorphism.

Key Insights and Ideas

  • Pattern Recognition as Subgraph Matching: The "aha moment" is treating urban pattern recognition not as a custom geometry problem, but as a standard graph search problem. Knowledge Graphs are specifically optimized for this.
  • Decoupling Calculation from Search: By pre-calculating spatial relations (like proximity and similarity) and storing them as graph attributes, the actual "reasoning" (finding the lines) becomes a simple, high-speed query.
  • Linear Scalability: Traditional methods often see an exponential or high-polynomial increase in processing time as data size grows. The Knowledge Graph approach scales much more linearly, making it far better suited for "Big Data" urban analysis.

Key Results

  • Accuracy: The method achieved a Precision of 96.21% and a Recall of 91.36%, closely matching the results of human visual perception tests conducted with cartography experts.
  • Efficiency Gains: On the standard dataset of 1,289 buildings, the Knowledge Graph method was 5.98 times faster than traditional graph isomorphism.
  • Massive Scalability: The efficiency gap widened significantly as the data grew. For the largest dataset (3,566 buildings), the proposed method was 31.49 times faster than the baseline.

Limitations and Future Work

While highly efficient, the authors acknowledge a few areas for improvement:

  • Threshold Sensitivity: Like all rule-based systems, the results depend on pre-defined thresholds (e.g., "how similar is similar enough?"). This can lead to occasional false negatives or positives in complex urban environments.
  • Pattern Variety: This paper focuses specifically on linear patterns. Future work aims to extend this framework to recognize more complex arrangements, such as grid patterns, circular patterns, or staggered clusters.
  • Latent Pattern Discovery: The current model identifies patterns defined by the user. The researchers suggest that future iterations could use Knowledge Graph embeddings or graph neural networks to discover new, latent urban patterns that aren't immediately obvious to human observers.

Summary updated

Abstract

Building patterns are important urban structures that reflect the effect of the urban material and social-economic on a region. Previous researches are mostly based on the graph isomorphism method and use rules to recognize building patterns, which are not efficient. The knowledge graph uses the graph to model the relationship between entities, and specific subgraph patterns can be efficiently obtained by using relevant reasoning tools. Thus, we try to apply the knowledge graph to recognize linear building patterns. First, we use the property graph to express the spatial relations in proximity, similar and linear arrangement between buildings; secondly, the rules of linear pattern recognition are expressed as the rules of knowledge graph reasoning; finally, the linear building patterns are recognized by using the rule-based reasoning in the built knowledge graph. The experimental results on a dataset containing 1289 buildings show that the method in this paper can achieve the same precision and recall as the existing methods; meanwhile, the recognition efficiency is improved by 5.98 times.
BibTeX
@misc{wei2023linear,
  author = {Zhiwei Wei and Yi Xiao and Ying Tong and Wenjia Xu and Yang Wang},
  title = {{Linear building pattern recognition via spatial knowledge graph}},
  year = {2023},
  eprint = {2304.10733},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2304.10733},
}
Figure