Automated Matching of Multi-Scale Building Data Based on Relaxation Labelling and Pattern Combinations

Abstract

With the increasingly urgent demand for map conflation and timely data updating, data matching has become a crucial issue in big data and the GIS community. However, non-rigid deviation, shape homogenization, and uncertain scale differences occur in crowdsourced and official building data, causing challenges in conflating heterogeneous building datasets from different sources and scales. This paper thus proposes an automated building data matching method based on relaxation labelling and pattern combinations. The proposed method first detects all possible matching objects and pattern combinations to create a matching table, and calculates four geo-similarities for each candidate-matching pair to initialize a probabilistic matching matrix. After that, the contextual information of neighboring candidate-matching pairs is explored to heuristically amend the geo-similarity-based matching matrix for achieving a contextual matching consistency. Three case studies are conducted to illustrate that the proposed method obtains high matching accuracies and correctly identifies various 1:1, 1:M, and M:N matching. This indicates the pattern-level relaxation labelling matching method can efficiently overcome the problems of shape homogeneity and non-rigid deviation, and meanwhile has weak sensitivity to uncertain scale differences, providing a functional solution for conflating crowdsourced and official building data.

1. Introduction

In the context of urbanization and big data, rapid development of geospatial data acquisition has caused an explosive growth of geospatial datasets. In particular, with the popularity of volunteered geographic information (VGI), geospatial data updating is undergoing a significant transformation from top-down active updating to bottom-up crowd updating [1]. On the one hand, crowdsourced geospatial data play an important role in generating 3D city models or highly precise road maps [2,3,4]. On the other hand, it is also essential to utilize the existing geospatial data to enrich the user-generated building information [5]. In practical applications, different departments or volunteers collect various geospatial datasets with different accuracies, different scales, or different thematic focuses. These heterogeneous geospatial datasets cannot effectively interoperate with each other, leading to the problems of information isolation. It is a crucial issue in the GIS community to conflate multi-source and heterogeneous geospatial datasets into an enriched or timely data product with higher geometric precision and detailed attribute information [6,7]. Data matching aims to identify the associated point, linear, or area objects between two or more geospatial datasets in the same or overlapping region, which is widely regarded as the essential step of data conflation and map updating. The subject of the article is building polygon matching.

Due to amateur participation and limited quality inspection, data inconsistencies (such as uneven scale differences, large geometric discrepancies, and diverse semantic descriptions) possibly occur between crowdsourced and authoritative geospatial data [8]. Researchers have found that crowdsourced datasets are characterized by inconsistent levels of detail (LODs) and inexplicit scales [9]. This inconsistency in LODs may result in the prevalence of 1:M and M:N correspondences between various datasets. Moreover, user-generated content may be less geometrically accurate and semantically unstructured, especially in rural or undeveloped areas [10]. This brings about large challenges for matching crowdsourced and authoritative datasets. In particular, the matching of multi-scale building polygons is associated with some complex difficulties. Firstly, the shape and orientation homogenization of building objects and the non-rigid deviations between different datasets make it difficult to distinguish 1:1 matching objects with similar shapes and layouts [11]. As shown in Figure 1a, most building polygon objects are represented as regularized rectangles with non-rigid deviations, which can hardly be matched based on shape similarity comparison. Secondly, the inconsistent LODs lead to low similarity of 1:M and M:N matching objects. As illustrated in Figure 1b, there are many 1:0, 1:M, N:1, and M:N correspondences with low similarity. Hence, this paper focus on the particular issue of matching multi-scale building polygons with an improved relaxation labelling approach.

The remainder of the paper is organized as follows. In Section 2, the state of art information about data matching is reviewed. Section 3 presents an improved building matching method based on relaxation labelling and pattern combinations. Section 4 elaborates the experimental results and undertakes some evaluation analysis to demonstrate the efficiency and robustness of the proposed method. Finally, the conclusions and future works are outlined at the end of the paper.

2. Literature Review

Data matching was developed to find identical objects or positions between multiple geospatial datasets that reflect the same real-world entity [12,13,14]. Finding inconsistencies between up-to-date images and existing geospatial datasets was a significant means of achieving change detection and data updating [15,16]. This paper tackles the matching of vector building objects, and thus undertakes a brief review into vector data matching.

According to object types, vector data matching can be classified into point, linear, and area object matching. For point matching, multi-criteria-decision methods have been developed to match POIs (Points of Interest) from different social network platforms [17,18]. For linear matching, most studies have compared multiple similarities (e.g., geometry, semantic, topology) and applied node-based, arc-based, polygon-based, or hybrid matching strategies [19,20,21,22,23]. Recent advances have introduced relaxation labelling, logistic regression, and genetic algorithms to improve the performance of road network matching [24,25,26]. Du et al. [27] designed ontology descriptions and fusion operators to integrate authoritative and crowdsourced road data. Liu et al. [28] proposed a progressive buffering method to update road maps with OSM (OpenStreetMap) data. Yang et al. [29,30] utilized spatial clustering and shape fitting to mine pattern-related correspondences between heterogeneous POIs and the road network. Ai et al. [31] constructed bend hierarchical trees to match contour data and river networks for geometry inconsistency detection.

Although numerous studies have been devoted to matching various crowdsourced or authoritative road datasets, little attention has been paid to area object matching (e.g., building polygons) [32]. Building polygon matching mainly concentrates on identifying object-level correspondences [33] and conjugate-point pairs between matched objects [34]. Ai et al. [35] and Fan et al. [32] calculated Fourier descriptors and turning functions to measure the shape similarity of building polygon objects. Wang et al. [36] proposed a back-propagation neural network approach for adaptively determining the weights of multiple similarities. Du et al. [37] considered location and lexical information to determine candidate-matching buildings, and then utilized spatial reasoning to refine them. Samal et al. [38] and Kim et al. [39] incorporated the geographic context to amend shape homogenization and non-rigid deviations. Zhang et al. [40] combined shape similarities and contextual information to find neighboring-compatible matching pairs. The above studies only computed the matching confidence of 1:1 matching objects, and ignored the total matching probability of 1:M, N:1, and M:N matching objects. Huh et al. [41] applied the graph embedding technique and agglomerative hierarchical clustering to explore multi-scale corresponding building objects. However, due to shape homogenization, non-rigid deviations, and multi-scale complex correspondences, it is still a challenging task to match multi-scale building polygon data. This paper thus proposes a novel approach for matching multi-scale building polygons based on relaxation labelling and pattern combinations. The proposed method mainly extends the relaxation labelling matching model [40,42] in consideration of simultaneous matches with multiple objects (i.e., pattern combinations).

3. Methodology

Traditional relaxation labelling methods [24,40] ignore the total matching confidences of 1:M and M:N correspondences, and may reduce the average probability that multiple objects simultaneously match with an identical one. Hence, this paper explores potential pattern combinations to model 1:M and M:N matching relations. Generally, the proposed approach consists of two main steps, outlined as follows:

●

Detect candidate-matching building objects based on buffering analysis, aggregate neighboring objects into pattern combinations, and calculate the geo-similarities between candidate-matching objects and pattern combinations to initialize the matching matrix;

●

Compute the contextual compatibilities between neighboring matching pairs to iteratively update the initial matching matrix, select the matching pairs based on the convergent matching matrix, and refine them through a matching conflict detection.

Let two building datasets be R = {r_i|i = 1, …, m} and T = {t_j|j = 1, …, n}. We suppose that R is the reference dataset and T is the target one. On the one hand, due to inconsistent LODs between crowdsourced and authoritative building datasets, it is difficult to assert whether T has a higher LOD than S, leading to the problem of matching direction [24]. On the other hand, since traditional relaxation labelling methods ignore total matching confidences for multiple cardinalities, this paper aggregates candidate-matching objects into pattern combinations to represent simultaneous matches with multiple objects. As illustrated in Figure 2, rp₁…rp_m’ and tp₁…tp_m’ are the aggregated pattern combinations in R and T. This paper calculates not only the matching probabilities of individual objects (r_i, t_j), but also calculates those of pattern combinations (r_i, tp_j) or (rp_i, t_j) to constitute a matching matrix. After that, the compatible influences of neighboring objects and pattern combinations are taken into account to heuristically update the initial matching matrix for a global matching consistency.

3.1. Matching Probability Initialization in Consideration of Multi-Scale Pattern Combinations

According to the framework of relaxation labelling matching, the matching matrix was first formed based on local geo-similarities (e.g., position, orientation, area, and shape). One contribution of this paper is that we aggregated neighboring candidate-matching objects into pattern combinations and calculated the probabilities of individual objects and pattern combinations to model 1:1, 1:M, and M:N correspondences. To reduce the computational complexity, a buffering analysis was executed to filter out the impossible matching features.

3.1.1. Detection of Candidate-Matching Objects and Pattern Combinations

A buffer operation can feasibly detect all possible matching objects between two geospatial datasets in the same spatial reference [28]. Previous studies have used an empirical buffering threshold for candidate-matching detection [21,24]. We constructed the Delaunay triangle network (DT_R) for the building centroids in R. The buffering threshold ε was then set as the average edge length of DT_R after deleting all global and local long edges according to the method of Deng et al. [43]. The candidate-matching set of each object r_i was determined as those objects in T that fall in the ε-buffer region of r_i, that is, CR_i = {t_j|t_j ∈ T and t_j in Buffer (r_i, ε)}. Similarly, the candidate-matching set of objects t_j in dataset T can be determined as CT_j = {r_i|r_i ∈ R and r_i in Buffer (t_j, ε)}.

Due to inconsistent LODs, one building object may match with multiple objects in another geo-spatial dataset. As illustrated in Figure 3a, object r_i has four candidate-matching objects; that is, CR₁ = {t₁, …, t₄}. Theoretically, there are C₄⁰ + C₄¹ + C₄² + C₄³ + C₄⁴ = 2⁴ matching situations, as shown in Figure 3b–f. However, the object-level probabilistic matching strategy may identify one 1:1 matching pair but ignore other matching objects with slightly lower probabilities. Hence, it is necessary to aggregate neighboring candidate-matching objects as a whole pattern combination to model multi-scale relaxation labelling correspondences.

To measure the total similarity with more than one candidate-matching object, we should aggregate them into one whole polygon, named a pattern combination. In detail, for one candidate-matching set, we iteratively aggregated the two closest building objects and finally obtained one polygon object to represent the pattern combination of that candidate-matching set. For example, as shown in Figure 4a, we first aggregated closer t₁ and t₂ as M(t₁, t₂) and then aggregated closer M(t₁, t₂) and t₃ as M(t₁, t₂, t₃). To aggregate two individual building objects, a convex hull approximation algorithm was developed, which encompasses the following three steps:

●

Step 1: Initialize the convex hull of two building objects as the merged polygon;

●

Step 2: Iteratively add the convex points closest to the intermediate lines to refine the merged polygon;

●

Step 3: Insert the inner concave points within objects t₁ and t₂ to further refine the merged polygon.

As shown in Figure 4b, for two objects t₁ = <u₁, …, u₈> and t₂ = <v₁, …, v₈>, the convex hull was first initialized as the pattern combination M⁽¹⁾(t₁, t₂) = <u₁, u₂, v₁, v₂, v₄, v₅, v₇, u₈>, of which two segments s₁ = <u₂, v₁> and s₂ = <v₇, u₈> were found as the intermediate lines that connect the vertexes of t₁ and t₂. Secondly, the convex points closest to the intermediate lines (e.g., u₇, u₄, v₈ and u₅) were iteratively added to refine the pattern combination as M⁽²⁾(t₁, t₂). Finally, the inner concave points within objects t₁ and t₂ (e.g., u₃, v₃ and v₆) were inserted to refine the pattern combination as M(t₁, t₂).

Suppose that one object r_i has P candidate-matching objects (|CR_i| = P), the candidate-matching pattern combination set of r_i is defined as CRP_i = {CRP_i²…CRP_i^p…CRP_i^P}, where CRP_i^p means the pattern combination subset that contains p polygon objects. Similarly, suppose that one object t_j has Q candidate-matching objects (|CT_j| = Q), the candidate-matching pattern combination set of t_j is defined as CTP_j = {CTP_j², …, CTP_j^q…CTP_j^Q}, where CTP_j^q means the pattern combination subset that contains q polygon objects. Hence, based on candidate-matching detection and neighboring pattern combinations, the candidate-matching table was created as c_Table = {(r_i, t_j)|r_i ∈ R, t_j ∈ CR_i∪CRP_i or r_i ∈ CT_j∪CTP_j, t_j ∈ T}, which is simplistically described as a candidate-matching table c_Table = (r_i, t_j), i = 1…(m + m’), j = 1…(n + n’).

3.1.2. Calculation of Geo-Similarities and Initial Matching Probabilities

For each candidate matching pair (r_i, t_j) in the candidate-matching table c_Table, four geometry similarities, namely the position similarity sim_p, orientation similarity sim_o, area similarity sim_a, and shape similarity sim_s, were calculated to initialize the candidate-matching matrix. The formulas are listed as follows.

$$\begin{array}{c}si{m}_p(i,j)=1-\frac{ds(i,j)}{\epsilon }, si{m}_a=\frac{\min \{area(i),area(j)\}}{\max \{area(i),area(j)\}}\\ si{m}_o(i,j)=1-\frac{dr(i,j)}{\pi /2}, si{m}_s=\frac{\min \{elg(i),elg(j)\}}{\max \{elg(i),elg(j)\}}\end{array}$$

(1)

As shown in Figure 5a, ds(i, j) means the centroid distance between two objects r_i and t_j, dr(i, j) denotes their wall statistical weighting orientation (WSW) [44] difference, elg(*) indicates the major–minor axis ratio of the minimum enclosing rectangle (MER), and area(*) measures the polygon area. After that, the initial matching probability is calculated by:

$$\begin{array}{c}{p}_{ij}=\frac{sim(i,j)}{{\displaystyle {\sum }_{t_k\in C{R}_i\cup CR{P}_i}sim(i,k)}}\\ sim(i,j)=si{m}_p(i,j{)}^{\ast }si{m}_o(i,j{)}^{\ast }si{m}_a(i,j{)}^{\ast }si{m}_s(i,j)\end{array}$$

(2)

where t_k ∈ CR_i∪CRP_i, sim(i, j) is the total geo-similarity of (r_i, t_j), so does sim(i, k). sim_p, sim_o, sim_a, and sim_s are the position, orientation, area, and shape similarities calculated by Formula (1).

It is time-consuming to consider all possible candidate-matching pattern combinations. Hence, the candidate-matching pairs with sim_p < T_pos, sim_o < T_dir, sim_a < T_area, and sim_s < T_shp were eliminated from the c_Table and the initial candidate-matching matrix was constructed as m_Matrix = (p_ij)_M×N, M ≤ m + m’, N ≤ n + n’.

3.2. Matching Probability Relaxation Based on Multi-Scale Contextual Information

The initial matching probability only considers the local geometric similarities and ignores the impacts of neighboring matching relations. The relaxation labelling algorithm models the contextual information of neighboring candidate-matching pairs as a compatibility coefficient to heuristically update the local-similarity-based matching probability.

3.2.1. Definition of the Neighboring Relation and Compatibility Coefficient

As no explicit neighboring relations are stored in the building datasets, some researchers have utilized the fixed radius, triangulation network, and proximity graph to search the local neighboring objects [38,40]. For the reference building object r_i in R, we constructed the Delaunay triangulation and defined the first-order connected objects and pattern combinations as its neighboring set Ɲ(r_i); for target building object t_j in T, the objects and pattern combinations in buffer(t_j, ε) were determined as the neighboring set Ɲ(t_j). Specifically, for one pattern combination r_u’ = {r_a, …, r_b}, Ɲ(r_u’) was defined as an subtraction set, Ɲ(r_a)∪…∪Ɲ(r_b)-{r_a…r_b}.

Based on the definition of neighboring relations, the contextual information of neighboring candidate-matching pairs was quantified as a compatibility coefficient according to Formula (3) [40], which combines both the relative and absolute position, orientation, shape, and area relations.

$$C(ij;hk)=sim(i,j)·{\displaystyle \prod _{u=1}^{4}re{l}_u(ij;hk)}$$

(3)

where C(ij; hk) denotes the compatibility coefficient between two neighboring candidate-matching pairs (r_i, t_j) and (r_h, t_k), sim(i, j) is the absolute geo-similarity calculated by Formula (2), and rel_u(ij; hk) (u = 1…4) represents four relative geometric relations between them, which are calculated as Formulae (4)–(7), respectively.

$$\begin{array}{l}re{l}_1(ij;hk)={r_{dis}}^{\ast }{r_{dir}}^{\ast }{r}_{ratio}\\ \{\begin{array}{l}{r}_{dis}=1-\frac{\left|ds(i,h)-ds(j,k)\right|}{\underset{r_m\in \mathcal{N}\left(r_i\right),t_n\in \mathcal{N}\left(t_j\right)}{\max }\left\{ds(i,m),ds(j,m)\right\}}\\ r_{dir}=1-\frac{\theta (ih,jk)}{\pi /2}\\ r_{ratio}=1-\frac{ds(i,h)}{\underset{r_m\in \mathcal{N}\left(r_i\right)}{\max }\left\{ds(i,m)\right\}}\end{array}\end{array}$$

(4)

$$re{l}_2(ij;hk)=1-\frac{\left|dr(i,h)-dr(j,k)\right|}{\pi /2}$$

(5)

$$re{l}_3(ij;hk)=\frac{1}{1+{(elg(i/h)-elg(j/k))}^2}$$

(6)

$$re{l}_4(ij;hk)=\frac{1}{1+{(area(i/h)-area(j/k))}^2}$$

(7)

rel₁(ij; hk), rel₂(ij; hk), rel₃(ij; hk), and rel₄(ij; hk) represent the relative position, orientation, shape, and area relations between two neighboring candidate-matching pairs (r_i, t_j) and (r_h, t_k), respectively. As depicted in Figure 5b, ds(i, h) and dr(i, h) mean the centroid distance and orientation difference between two neighboring building objects r_i and r_h, Ɲ(r_i) indicates the neighboring set of object r_i, and θ(ih; jk) is the angle between two centroid vectors $\overrightarrow{r_i{r}_h}$ and $\overrightarrow{t_j{t}_k}$. elg(i/h) and area(i/h) are the elongation index ratio and area ratio between two neighboring building objects r_i and r_h, so do elg(j/k) and area(j/k).

3.2.2. Relaxation of the Matching Matrix and Selection of Final Matching Pairs

The compatibility coefficient calculated above measures the relative geometric consistency between two neighboring candidate-matching pairs. However, there are possibly more than one neighboring candidate-matching pairs. The relaxation labelling process incorporates the impacts of all neighboring candidate-matching pairs (also called the sub-support indexes) into a total support index and updates the geometric-based matching matrix. In light of multi-scale 1:M and M:N correspondences, the impacts of neighboring pattern combinations should be also integrated into the total support index. In detail, the total support index of one candidate-matching pair (r_i, t_j) was computed as follows:

●

Calculate the sub-support indexes of all neighboring individual objects and pattern combinations according to Formula (8), which are partitioned into two separate queues of Q_ij and Q’_ij. Q_ij stores the sub-support indexes of neighboring individual objects and Q’_ij stores the sub-support indexes of neighboring pattern combinations. For the candidate-matching pair (r_i, t_j) in Figure 6a, two sub-support index queues Q_ij and Q_ij’ are listed in Figure 6b.

$$q_{ij,h}=\underset{s_k\in C{R}_h\cup CR{P}_h}{\max }\{C(ij;hk)P(h,k)\},r_h\in N_i \mathrm{or} N{P}_i$$

(8)

●

Traverse Q_ij’ in ascending order of the included object number of the neighboring pattern combination, and judge whether its sub-support index is larger than the average support index of its included objects. If yes, the sub-support index of that pattern combination will replace the corresponding sub-support indexes of the included objects in Q_ij. As elaborated in Figure 6b, the sub-support index q_ij,x’ of r_x’ = {r_a, r_b} is larger than the average of q_ij,a and q_ij,b, so q_ij,x’ will substitute the values of q_ij,a and q_ij,b in Q_ij.

●

When all elements of Q_ij’ are traversed and judged by the above steps, the mean of the sub-support indexes in Q_ij is computed as the total support index q_ij of (r_i, t_j).

Once the total support indexes of all candidate-matching pairs were determined, the iteration of the geo-similarity matching matrix was executed according to Formula (9) [24]. The relaxation labelling process will continue until the probability differences between two iterations are less than a predefined threshold δ.

$$p_{ij}^{r+1}=\frac{p_{ij}^r+q_{ij}^r}{1+{\displaystyle {\sum }_{h\in C{S}_i}{q}_{ih}^r}}$$

(9)

Based on the convergent matching matrix, the matching pairs with the maximum matching probability per row were first selected and inserted into a queue MQueue. Then, check each matching pair A in MQueue. When there is another matching pair B in MQueue that contains one or more common building objects, it may be two conflict matching pairs or an M:N matching pair divided by several 1:M or M:1 matching pairs. To distinguish the above conditions, we calculated the overall geometry similarity Sim (A∪B) of merging A and B. If Sim (A∪B) is larger than both Sim (A) and Sim (B), A and B are merged into one M:N matching pair A∪B; otherwise, the one with the higher matching probability is reserved and the other with the lower probability is replaced by the pair with the next highest probability. After that, MQueue was determined as the final matching pair set between two building datasets R and T.

4. Experiment and Analysis

One mock building dataset and two real building datasets in Xi’an City, China and Dallas in the United States of America were used to verify the efficiency and reliability of the proposed method. As listed in

Table 1. Experimental data statistics and parameter settings.

Test Data	R (Scale/Object Number)	T (Scale/Object Number)	Tpos	Tdir	Tarea	Tshp	δ
Mock data	Small scale/25	Large scale/42	0.75	0.95	0.8	0.75	5‰
Xi’an data	1: 250,000 (83)	1: 200,000(118)	0.70	0.95	0.65	0.72	5‰
Dallas data	OpenStreetMap/83	Web data/80	0.87	0.93	0.9	0.87	5‰

, the spatial scales of two Xi’an building datasets were known as 1:250,000 and 1:200,000, but uncertain scale differences were found in the simulated dataset and Dallas dataset from web sources. In Table 1, T_pos, T_dir, T_area, T_shp are four similarity thresholds for the candidate-matching pairs filtering from Section 3.1.2, and δ is the convergent threshold for the relaxation labelling process outlined in Section 3.2.2.

Figure 7 illustrates the initial matching result of the mock building data based on local geometric similarity and the matching results generated by the object-level relaxation labelling method and the proposed pattern-level method. It can be seen from Figure 7a that several obvious errors occur in the similarity-based matching results because of non-rigid deviations and shape homogenization. Although the object-level relaxation labelling method is a great improvement in terms of finding a contextual matching consistency, as shown in Figure 7b, there still are some 1:M and M:N matching pairs ignored by the object-level matching strategy. Figure 7c indicates that various 1:M and M:N matching pairs are correctly recognized by the proposed method based on relaxation labelling and pattern combinations. The matching results of the Xi’an data and Dallas data are shown in Figure 8, which demonstrates the proposed method can robustly identify the complex correspondence of building objects with large and uncertain scale differences.

By comparing the matching results with manual matching, three accuracy indicators—precision P, recall R, and F value—were calculated according to Formula (10). tp denotes true matching pairs recognized by our method, fp denotes false matching pairs identified by our method, and fn means true matching pairs omitted by our method. It can be seen from

Table 2. Matching accuracy statistics of precision, recall, and F value.

Data		Precision P	Recall R	F Value
Mock data	Object-level method	100%	68.57%	81.35%
	The proposed method	100%	100%	100%
Xi’an data		93.56%	91.47%	92.5%
Dallas data		98.12%	95.45%	96.93%

that both the precision and recall rates are higher than 90%, and obvious higher accuracies were obtained by our method than the object-level relaxation labelling method.

$$P=\frac{tp}{tp+fp},R=\frac{tp}{tp+fn},F=\frac{2\times P\times R}{P+R}$$

(10)

Figure 9 displays the probability change of candidate-matching pairs of objects #125 and #26 during the relaxation labelling process. As shown in Figure 9a, the relaxation labelling process correctly distinguishes fake matching pairs (#125 → #141) and true matching pairs (#125 → #140) by integrating contextual information of neighboring matching pairs to heuristically amend the local-similarity-based matching matrix. This indicates the proposed method can efficiently overcome incorrect matching caused by shape homogenization and non-rigid deviation. Meanwhile, as depicted in Figure 9b, the pattern-level matching method correctly identifies a complex 1:M matching pair of (#26 → #64, 65, 70, 69) by considering pattern combinations in the relaxation labelling model. This demonstrates our method can efficiently find various 1:M and M:N correspondences possibly missed by the object-level matching method.

The matching probability distributions of object #81 and #17 in Figure 10a are elaborated in Figure 10b,c, respectively. It can be seen that both 1:1 object correspondence (#81 → #30) and 1:M pattern combination matching (#17 → #32, 33, 34, 35, 36, 37) are reliably identified in terms of a large probability gap. That indicates our method is relatively less sensitive to spatial scale differences than the object-level relaxation labelling method.

Table 3. Examples of candidate-matching pattern combinations.

Matching Combinations	Data R	Candidate Correspondences in Data T	Matching Probability
	rA	{ta}	0.011
		{ta, tb}	0.0469
		{ta, tb, tc}	0.138
		{ta, tb, tc, td}	0.218
	rB	{te}	0.0585
		{tf}	0.1424
		{te, tf}	0.308
		{te, tf, tg}	0.051
	rC	{te}	0.070
		{tg}	0.130
		{te, tg}	0.290
		{te, tf, tg}	0.055

shows two matching examples of pattern combinations. For object r_A, Table 3 lists the top four candidate correspondences. It can be seen that the matching probability of (r_A → {t_a, t_b, t_c, t_d}) was computed as 0.218, apparently higher than that of other candidate-matching objects or pattern combinations. For object r_B and r_C, the best matching pairs with the highest matching probabilities were computed as M₁ = (r_B → {t_e, t_f}) and M₂ = (r_C → {t_e, t_g}), respectively. Because M₁ and M₂ contain a common object t_e, these two matching pairs were finally merged into an M:N matching pair M = ({r_A, r_B} → {t_e, t_f, t_g}) by comparing their geo-similarities. This further indicates the good performance of our method in identifying complex 1:M and M:N matching relations between heterogeneous multi-scale building data.

5. Conclusions

Object matching is an essential step of map conflation and data updating. Multi-scale building data matching is confronted with such problems as shape homogenization, non-rigid deviations, and uncertain scale differences. This paper proposed an automated building matching method based on relaxation labelling and pattern combinations. The proposed method extended the object-level relaxation labelling matching method and constructed a probabilistic matching model considering both 1:1 object matching and 1:M pattern combination matching. The experimental results show that the relaxation labelling process takes contextual information into account, reliably increasing the matching accuracy and insensitivity to non-rigid deviations and shape homogenization. Moreover, pattern combinations are novelly integrated into the probabilistic matching model, efficiently improving the performance to match crowdsourced building datasets with large and uncertain spatial scale differences. Future work will focus on null matching modelling and optimized selection of candidate-matching pairs to improve the robustness of our method.