Hierarchical Model for the Similarity Measurement of a Complex Holed-Region Entity Scene

Chen, Zhanlong; Zhu, Rongrong; Xie, Zhong; Wu, Liang

doi:10.3390/ijgi6120388

Open AccessArticle

Hierarchical Model for the Similarity Measurement of a Complex Holed-Region Entity Scene

by

Zhanlong Chen

,

Rongrong Zhu

,

Zhong Xie

and

Liang Wu

^*

Department of Information Engineering, China University of Geosciences, Wuhan 430074, China

^*

Author to whom correspondence should be addressed.

ISPRS Int. J. Geo-Inf. 2017, 6(12), 388; https://doi.org/10.3390/ijgi6120388

Submission received: 13 October 2017 / Revised: 15 November 2017 / Accepted: 27 November 2017 / Published: 29 November 2017

Download

Browse Figures

Versions Notes

Abstract

:

Complex multi-holed-region entity scenes (i.e., sets of random region with holes) are common in spatial database systems, spatial query languages, and the Geographic Information System (GIS). A multi-holed-region (region with an arbitrary number of holes) is an abstraction of the real world that primarily represents geographic objects that have more than one interior boundary, such as areas that contain several lakes or lakes that contain islands. When the similarity of the two complex holed-region entity scenes is measured, the number of regions in the scenes and the number of holes in the regions are usually different between the two scenes, which complicates the matching relationships of holed-regions and holes. The aim of this research is to develop several holed-region similarity metrics and propose a hierarchical model to measure comprehensively the similarity between two complex holed-region entity scenes. The procedure first divides a complex entity scene into three layers: a complex scene, a micro-spatial-scene, and a simple entity (hole). The relationships between the adjacent layers are considered to be sets of relationships, and each level of similarity measurements is nested with the adjacent one. Next, entity matching is performed from top to bottom, while the similarity results are calculated from local to global. In addition, we utilize position graphs to describe the distribution of the holed-regions and subsequently describe the directions between the holes using a feature matrix. A case study that uses the Great Lakes in North America in 1986 and 2015 as experimental data illustrates the entire similarity measurement process between two complex holed-region entity scenes. The experimental results show that the hierarchical model accounts for the relationships of the different layers in the entire complex holed-region entity scene. The model can effectively calculate the similarity of complex holed-region entity scenes, even if the two scenes comprise different regions and have different holes in each region.

Keywords:

holed-region entity; complex holed-region entity scene; hierarchical model; position graph; multi-level chord-length function

1. Introduction

Although the collection and maintenance of spatial data is the most time-consuming activity in GIS engineering in the real world, data for the same objects are often repeatedly collected by different departments [1]. Several differences are present in the same objects on maps produced from different sources that are due to mapping errors, different applications, and interpretations [2,3,4]. These identical entities are usually inconsistent in positioning accuracy, shape, and attribute information. To reduce the cost of GIS data collected by the GIS application departments and to evaluate the quality of the existing map data, it is necessary to use standard map data as a reference to measure the similarity of two map data. Similarity and matching are not only widely used to update data from different sources [5] but also in data retrieval [6] and classification [7]. These topics have attracted a great deal of research attention over the past decades [8,9].

In a real-life situation, matching and similarity are used in spatial applications [10,11], not only to match simple objects described as points [12], lines [13], and polygons [14,15] but also to match complex geometric structures [16,17]. Many geographic phenomena have discontinuities in the form of internal cavities [18]. A real-world geographic entity containing inner boundaries, such as a region containing several lakes or an island lake, is abstracted as a holed-region. In the simple feature specification for the Structured Query Language (SQL) of Open Geospatial Consortium (OGC), the existence of a holed-region is implied when defining a region as a simple feature in a geo-database, “a region is a planar surface, defined by one exterior boundary and zero or more interior boundaries; interior boundary defines a hole in the region, ..., the exterior of a region with one or more holes is not connected. Each hole defines a connected component of the exterior” [19]. Meanwhile, the scene containing several island lakes is abstracted as a complex holed-region entity scene. The complex holed-region entity scene can be regarded as a collection of a random number of regions that contain holes.

Numerous methods that measure the similarity of two holed-regions exist, and most of them focus on topological relationships, such as the topological relationships between two holed-regions [20], a hierarchical model based on the CBM to treat complex regions in topological queries [21], the 23 topological relationships between a simple region and a region with a hole [22], the 152 topological relationships between two single holed-regions [23], and the topological similarity between a hole-free region and a multi-holed-region [18]. Compared to a simple holed-region, a complex holed-region entity scene usually has a more complicated distribution pattern. Such characteristics make a similar evaluation between two complex holed-region entity scenes extremely difficult. To the best of our knowledge, similarity measurements between two complex holed-region entity scenes have not been studied to date. Current holed-region similarity measurement methods and models cannot be directly used for complex holed-region entity scenes because they lack inherited relationships between different layers.

In this paper, we present a hierarchical model to measure the similarity of two complex holed-region entity scenes. In our model, a complex holed-region entity scene is decomposed into three layers—a complex scene, a micro-spatial-scene (i.e., a spatial scene comprising a collection of holes and their spatial relationships), and a simple entity (i.e., a hole).

The relationships between the adjacent layers are considered as sets of relationships. Each level of similarity measurements is nested with the adjacent one. Entity matching is performed from top to bottom, while the similarity results are calculated from local to global. The hole distribution is considered as a constraint satisfaction problem (CSP) [24] that comprises the shape descriptors and the directional relationships of the holes. In addition, position graphs [25] describe the distribution of the micro-spatial-scene, and a force diagram [26,27] is used to measure the similarity between the graphs. The extended Hausdorff distance [28] represents the relationships between the holed-regions and the scene center. Because of topological and semantic limitations of the entity matching process [29], we introduced the Hungarian algorithm [6] to resolve matching problems between holed-regions belonging to different complex entity scenes. The multilevel chord length [30] is adopted to construct complex functions to describe the geometric shape from entity to part, and the shape descriptor is based on the fast Fourier transform of the complex function [31]. This paper is an extension of our precedent work [25]. The main idea of this model is not characterized merely by the iterative approach of our previous work; the whole spatial distribution information of the holed-regions in the complex holed-region entity scenes is represented in our model, which is ignored in many previous studies.

The rest of this paper is organized as follows. Section 2 introduces the hierarchical model for a holed-region entity scene and proposes the similarity measurement of the position graphs. We next introduce the matching of holed regions and holes and the similarity measurement of the micro-spatial-scene in Section 3. In Section 4, we propose the similarity measurement between complex holed-region entity scenes. Next, we apply the model to the Great Lakes by using data from different years and then discuss and analyze the results in Section 5. Finally, the study’s conclusions are presented in Section 6.

2. Similarity Measurements of Two Complex Scenes

2.1. Hierarchical Method for a Complex Holed-Region Entity Scene

The Open Geospatial Consortium (OGC) Abstract Specification describes complex geometry as “The complex space object is mainly composed of geometric combinations, such as merging and difference generation for basic spatial objects or their topological parts.” A complex holed-region scene S is a set of n (n ≥ 1) multi-holed-regions R_i, i.e., S = {R₁∪R₂∪…∪R_n}. Therefore, the similarity of a complex scene can be regarded as an overall generalization of the similarity of R_i and the distribution similarity of R_i.

The multi-holed-region R, which can be thought of as a micro-scene, is m (m ≥ 0) holes H_j merged, i.e., R = {H₁∪H₂∪…∪H_n}. Likewise, the similarity of the micro-spatial-scene is considered to be a generalization of the geometric similarity of the hole H_j and the similarity of the distribution of H_j in R.

To simplify the overall similarity measurement of the complex scene, we introduce the concept of a hierarchy. The hole in the holed-region is the first level, designated as the “simple entity” layer; the holed-region entity is the second level, designated as the “micro-spatial-scene” layer; and the complex holed-region entity scene is the third level, designated as the “complex scene” layer. A hierarchical calculation is done for the similarity of the complex holed-region entity scene. The layered method is shown in Figure 1.

In the first step, the complex scene S is decomposed into several regions R_i (I = 1, 2, …, n), which contain the exterior boundary and the corresponding micro-spatial-scene R’_i (I = 1, 2, …, n), and the similarity of a complex scene layer is the aggregation of the similarity of all of the micro-spatial-scenes, all exterior shapes, and the matching and distribution of all regions.

In the second step, we focus on the similarity of the micro-spatial-scene. The hole in the micro-spatial-scene is regarded as a simple surface entity H_j (j = 1, 2, …, m), and the simple entity H_j has a fixed position distribution in R_i. The micro-spatial-scene is a combination of simple entities; therefore, the similarity of the micro-scene is a generalization of the shape similarity, the direction similarity, and the completeness of the matching of simple entities.

In the third step, the matching situation is not considered. The similarity of the simple entity layer focuses on the shape similarities and direction similarities of holes.

2.2. Location Distribution and Similarity Measurement

2.2.1. Position Graphs

The hierarchical method of Section 2.1 implies that the similarity of a complex scene is closely related to the similarity of the distribution of the holed-regions. In this paper, we refer to the method of position graphs to describe the distribution of the holed entity in a complex scene. The boundary of a complex scene S is determined by the MBR method and the centroid C of scene S found by the diagonal of the rectangle. In the Position Graphs, the distance between the centroid of a holed entity and the scene center is defined as the relative distance between the holed entity and the scene. As shown in Figure 2, C1, C2, C3 are the centroids of the holed entities R1, R2, R3, respectively. The point O is the scene center, and the points NT1, NT2, NT3 are, respectively, the nearest tangent points from O to the outlines of R1, R2, R3. The center point position graph (CPPG) is formed by connecting the center point holed entities. The nearest tangent point position (NTPPG) is formed by connecting the nearest tangent points from scene centroid to the outlines of the holed-region.

As shown in Figure 3, N₁, N₂, N₃ are, respectively, the nearest points from the centroid O to the outlines of R₁, R₂, R₃, and F₁, F₂, F₃, are, respectively, the farthest points from the centroid O to the exterior boundaries of R₁, R₂, R₃, so the nearest points position graph(NPPG) and farthest points position graph (FPPG) is formed by connecting O to N_i and F_i respectively.

2.2.2. Descriptive Measurement of the Position Graphs

Each edge of a shape is formed by two forces that have equal value but opposite direction [25]. As a result, a region can be described by a set of forces. A group of forces that form a region in a coordinate system is drawn and these forces represent a force diagram. According to the parallelogram law [32], the force can be decomposed along the x-axis and y-axis, and the sum in x-axis and y-axis always meet:

\sum_{i = 1}^{N} f_{i x} = 0, \sum_{i = 1}^{N} f_{i y} = 0

(1)

The parameter f_ix is the decomposition part of force f_i on the x-axis, f_iy is the decomposition part of force f_i on the y-axis, and N is the force number. The positive or negative value of these forces will change periodically with the direction of the force, with a period of 180°.

Adding the absolute value of the forces in the positive and negative directions of the x-axis provides:

F_{x} (α) = \sum_{i - 1}^{N} | f_{i x} (α) |

(2)

Similarly, F_y(α) is available:

F_{y} (α) = \sum_{i - 1}^{N} | f_{i y} (α) |

(3)

The projection interval function of the force diagram is defined as

F (α) = F_{x} (α) / F_{y} (α)

(4)

where α is the rotation angle of the force diagram, and the F(α) is also a periodic function with a period of 180° and its function image is a waveform.

2.2.3. Similarity Measurement of the Position Graph

Different position graphs can be described with different force diagrams, and different position graphs have different projection interval functions; therefore, the similarity between the distributions of the holed-regions can be measured by the degree of matching of the projection intervals. Because of the characteristics of the waveform, the degree of matching between the two projections ratios is calculated by the minimum mean error (MME) of the waveform.

When the sample points are distributed in a 180° range and the rotation angle α is replaced by the discrete value i, the MME between the position graphs P₁ and P₂ is calculated as:

M_{P_{1} P_{2}} (l) = \frac{1}{N} \sum_{i = 0}^{N - 1} | F_{1} (i) - F_{2} (i - l) |

(5)

where F₁(i) and F₂(i − l) (0 ≤ l ≤ N − 1) are the projection ratio functions of the position graphs P₁ and P₂, l is the deviation of the two functions, and N is the number of discrete sampling points. The MME is more accurate when N is larger. Since F ∈ [0, 1], the similarity of the two position graphs can be defined as:

{S^{'}}_{p_g} = 1 - \frac{\min {M_{P_{1} P_{2}} (l)}}{\max {F_{1} (i), F_{2} (i)}}, 0 \leq l, i \leq N - 1

(6)

2.2.4. Geometric Transformation of the Position Graph

Climate change, ocean currents, crustal movements, natural disasters, artificial construction, and other factors may drive diverse phenomena for lakes that contain islands (i.e., holed-regions in a complex spatial scene), such as revolution, rotation, moving, and scaling. Obviously, it is necessary to measure the similarity of revolution in which the CPPG rotate around the centroid of the complex scene, the rotation in which the CPPG rotates around its center point, and moving and scaling based on position graphs.

Revolution Similarity

As shown in Figure 4, O is the centroid of a complex scene, and O₁ is the center of the CPPG. The vector from the point O to the nearest vertex of the MBR of the complex scene is u₂, and u₁ is the vector from the point O to the point O₁. The angle between u₁ and u₂ is β, which is defined as the central angle. β is negative when u₁ is on the left side of u₂. The change value θ of β is the revolution angle.

The revolution similarity of two CPPGs can be defined as:

{S^{'}}_{r 1} = 1 - \frac{| β_{1} - β_{2} |}{360 °}

(7)

Rotation Similarity

Draw the CPPG and the complex scene of the MBRs and move the MBR of the scene to vertex of the MBR of CPPG, where v₁ is the direction vector of the scene and v₂ is the direction vector of CPPG. The angle α between v₁ and v₂ is defined as the relative direction angle, and is negative when v₁ is on the left side of v₂. (Figure 5).

The rotation similarity of the two CPPGs with rotation can be defined as:

{S^{'}}_{r 2} = 1 - \frac{| \partial_{1} - \partial_{2} |}{360 °}

(8)

Moving Similarity

The average radius of a complex scene is R, and the relative center distance (RCD) l is defined as:

l = \frac{\sqrt{{[x (o) - x (o_{1})]}^{2} + {[y (o) - y (o_{1})]}^{2}}}{R}

(9)

The center coordinate of the complex scene is (X(O),Y(O)), and at the same time (X(O₁),Y(O₁)) is the center coordinate of the CPPG. The moving translation similarity [33] can be defined as:

{S^{'}}_{m} = 1 - \frac{| l_{1} - l_{2} |}{\max (l_{1}, l_{2})}

(10)

Scaling Similarity

The Hausdorff distance [28] is introduced to describe the zoom of a complex scene with a holed-region. The directional Hausdorff distance formula is:

\begin{array}{l} h^{f 1} (A, B) = \min {ε_{i} : f_{1} = \frac{ϑ ((B \oplus S (ε_{i})) \cap A)}{ϑ (A)}} \\ h^{f 2} (B, A) = \min {ε_{j} : f_{2} = \frac{ϑ ((A \oplus S (ε_{j})) \cap B)}{ϑ (B)}} \end{array}

(11)

The extended Hausdorff distance formula is:

H^{f 1 f 2} (A, B) = \max {\min {ε_{i} : f_{1} = \frac{ϑ ((B \oplus S (ε_{i})) \cap A)}{ϑ (A)}}, \min {ε_{j} : f_{2} = \frac{ϑ ((A \oplus S (ε_{j})) \cap B)}{ϑ (B)}}}

(12)

In Formula (12),

ϑ (•)

is the area or line length measure function of region. When A or B is a point, the value of

ϑ (•)

is 0 (“

•

” is the empty set).

\oplus

is the mathematical morphological expansion operator that represents the Minkowski value, and

S (ε)

is a disc with a radius of ε [34]. The position graph scaling can be derived from the ratio of the extended Hausdorff distance from the center of a scene to its contour to the average radius of the scene. This ratio is defined as the relative expansion of the Hausdorff distance:

D i s = \frac{1}{N R} \sum_{i = 0}^{N} H_{i}

(13)

where H is the extended Hausdorff distance of the center of a scene to a holed-region, N is number of a holed-region, and R is the average radius of a region. The similarity of the CPPG of the holed-region can be calculated by the following formula:

{S^{'}}_{s} = 1 - \frac{| D i s_{p} - D i s_{q} |}{\max (D i s_{p}, D i s_{q})}

(14)

3. Similarity Measurement of Micro-Spatial-Scene

3.1. Pairwise Matching of a Holed-Region Entity

It is necessary to match pairs of holed-region entities to measure the similarity of a holed-region in different complex scenes. Figure 6 and Figure 7, respectively, show three and four holed-regions in the complex scenes S₁ and S₂, which may produce different matching results: (R₁, R₁’), (R1, R2’), (R1, R3’), (R1, R4’), (R2, R1’), (R2, R2’), (R2,R3’), (R2, R4’), (R3,R1’), (R3, R2’), (R3, R3’), (R3, R4’). Different matching results will yield different similarity measurements.

The scenes S₁ and S₂ are, respectively, the reference scene and the matching scene. Any holed-region R_i in S₁ will match with a corresponding set of holed-regions {R_i} in S₂. To obtain the matching set of the holed-region R_i in S₁, we first determine the vertex P’, which is the closest point on the MBR of the CPPG to the center of the CPPG; then, we obtain the vector

\vec{P^{'} d_{i}}

by connecting d_i and P’, whose length is d₁_i, as shown in Figure 8a. The angle between the vector

\vec{P^{'} d_{i}}

and the direction vector of the MBR is δ. Next, a point Q is determined in S₂. A circular buffer with the center of Q is drawn and the average radius of the holed-region R_i is r_i; furthermore, the regions in the buffer or that intersect with the buffer are regarded as the matching region candidates of R_i. The angle between the vector

\vec{P Q}

and the vector of the MBR direction vector is δ, as shown in Figure 8b. The length of

\vec{P Q}

is defined as d_{2_i}:

d_{2_i} = d_{1_i} \times \frac{R_{2}}{R_{1}}

(15)

where R₂ is the average radius of scene S₂ and R₁ is the average radius of scene S₁.

After obtaining the matching candidate set {R_i} of the reference entity R_i, our next step is to determine the matching entity with the highest degree of matching in the matching candidate set. For this case, the Hungarian algorithm [35] is introduced. It is supposed that the similarity between R_i and the regions belonging to S₂ but not included in {R_i} is 0, and the distance is infinite. A matrix D of m rows and n columns is constructed, where m is the number of regions in scene S₁, n is the number of regions in S₂, and the element d_ij in D is defined as d_ij = dis(R_i, R’_j), which expresses the Euclidean distance between centroid R_i and R’_j.

d i s (R_{i}, {R_{j}}^{'}) = \sqrt{(x (R_{i}) - x {({R_{j}}^{'})}^{2}) + (y (R_{i}) - y {({R_{j}}^{'})}^{2})}

(16)

where (x(R_i),y(R_i)) and (x(R’_i),y(R’_j)) are the centroids of R_i and R’_j, respectively.

The decision variable x_i,j ranges from

x_{x, j} = {\begin{cases} 0, & R_{i} i n S_{1} n o t m a t c h i n g w i t h {R_{j}}^{'} i n S_{2} \\ 1, & R_{i} i n S_{1} m a t c h w i t h {R_{j}}^{'} i n S_{2} \end{cases}

(17)

The decision variable matrix X is

D = [\begin{array}{l} d_{11} & d_{12} & d_{1 \dots} & d_{1 n} \\ d_{21} & d_{22} & d_{2 \dots} & d_{2 n} \\ d_{\dots 1} & d_{\dots 2} & d_{\dots} & d_{\dots n} \\ d_{m 1} & d_{m 2} & d_{m \dots} & d_{m n} \end{array}] X = [\begin{array}{l} x_{11} & x_{12} & x_{1 \dots} & x_{1 n} \\ x_{21} & x_{22} & x_{2 \dots} & x_{2 n} \\ x_{\dots 1} & x_{\dots 2} & x_{\dots} & x_{\dots n} \\ x_{m 1} & x_{m 2} & x_{m \dots} & x_{m n} \end{array}]

(18)

So the matching results can be calculated by

\min Z = \sum_{i = 1}^{m} \sum_{j = 1}^{n} d_{i j} x_{i j} s . t . {\begin{cases} \sum_{i = 1}^{m} x_{i j} = 1, & j = 1, 2, \dots, n \\ \sum_{j = 1}^{n} x_{i j} = 1, & i = 1, 2, \dots, n \\ x_{i j} = 1 o r 0, & i = 1, 2, \dots, m, j = 1, 2, \dots n \end{cases}

(19)

In this process, the value of x_ij that minimizes the sum of each column of Z for each row is vital, and this calculation can be derived from the Hungarian algorithm. The decision variable matrix X obtained can determine the result between the regions R_i in S₁ and R’_j in S₂. Furthermore, the matching similarity between S₁ and S₂ can be obtained by:

{S^{'}}_{R_S} = \frac{1}{n} \sum_{i = 0}^{n} (1 - d_{i})

(20)

where n is the number of matching regions, and d_i is the Euclidean distance mentioned above.

3.2. Pairwise Matching of Holes

In this part, we consider a holed-region entity as a micro-spatial-scene, and the “hole” in the micro-spatial-scene is an independent simple surface entity. Therefore, in the measurement of the similarity of a micro-spatial-scene, we not only must consider the scene of the internal and external boundaries, but we also must consider the direction similarity of the holes. From a human perception viewpoint, a scene comparison is a process of associating similar objects across a scene, and the relationships between objects must correspond as well [36]. Therefore, the first task in the common models of spatial scene similarity measurement is the identification of corresponding objects [37,38]. As in the similarity measurement process of the micro-spatial-scene, it is most important to find the matching relationship of the hole. This matching problem is treated as a constraint satisfaction problem (CSP), in which the contour and direction relationships of holes in reference to the multi-holed-region act as constraints.

The CSP has the following conditions: (1) the variables eb_n and eb_m represent the edges of the region Rh_n and Rh_m; (2) the variable set H₁, …, H_n represents the holes in Rh_n; (3) for each H_i, sets of possible matching variables H’_I = {H’₁, …, H’_l} corresponding to holes in Rh_m exist; (4) each variable H_i has a unit variable S_i that describes its shape; and (5) for each variable set (H_i, H’_j), a binary variable d_ij exists that describes the relationship between the variables.

In this study, the matching association graph is utilized to describe the constraints in Rh_n, in which the value of each node represents the shape of the contour constraints, and the values attaching to edges indicate the directional constraint between the holes, as shown in Figure 9.

Since the number of holes in Rh_n and Rh_m can be different, the hole-matching in this study does not compare the entire graph, just the subgraphs. There are three matching solutions as follows (Figure 10):

Complete solution. A subgraph G’_m of the graph G_m of Rh_m matched with the graph G_n of Rh_n, in which all holes and directions of Rh_n have a correspondence in Rh_m.
Incomplete solution. A subgraph G’_m of G_m matches the subgraph G’_n of G_n, in which a subset of holes and directions of Rh_n have a correspondence in Rh_m.
No solution.

The formation of the association graph for the holed-region entities Rh_n and Rh_m, for which Rh_n has the graph G with the node set (g₁, g₂, ..., g_n) and Rh_m has the graph G’(g’₁, g’₂, ..., g’_n), contains two important steps. First, a node a_ij(g_i_, g’_j) is created if g’_j is in G’ that satisfies the univariates (shape matching) of g_i in G. Second, the nodes are connected with their edges by inserting an edge to connect the node a_ij(g_i, g’_j) with a_lk(g_l, g’_k). The value attached to the node is the geometric similarity between the two holes, and the value of the edge is the similarity of the direction relationship. As a result, the associated graph with weight is formed.

3.3. Similarity Measurement of Holes

The hierarchical method of Section 2.1 shows that the geometric similarity of the inner and outer contours of a holed-region entity belongs to different similarity measurement levels, and the geometric similarity of the inner contours belongs to the measuring dimension of the micro-spatial-scene level, while the geometric similarity of the outer contours is the measuring dimension of a complex scene level. Therefore, we do not account for the outer contour of the holed-region entities when we compute the similarity of Holes.

(1): Assuming that the holed-region entities Rh_n and Rh_m have t pairs of matching holes, S_Hi is the shape similarity of the i^th pair of holes and W_Hi is the weight of the i^th pair of holes. Next, the shape similarity between Rh_n and Rh_m is defined by S’_shape for

${S^{'}}_{i n s h a p e} = \frac{\sum_{i = 1}^{t} W_{H i} • S_{H i}}{\sum_{i = 1}^{t} W_{H i}}$

(21)
(2): Supposing that the holed-region entities Rh_n and Rh_m have t pairs of matching holes with t(t − 1)/2 pairs of matching directions, S_Di is the similarity of the i^th pair of direction relationships, which have a weight W_Di. Thus, the direction relationship similarity S’_direction between Rh_n and Rh_m can be defined as

${S^{'}}_{d i r e c t i o n} = \frac{\sum_{i = 1}^{t (t - 1) / 2} W_{D i} • S_{D i}}{\sum_{i = 1}^{t (t - 1) / 2} W_{D i}}$

(22)
(3): The weight of the shape similarity and the direction relationship similarity is set to W_shp and W_dir, respectively; then, the similarity S’_Rhn,Rhm between micro-spatial-scene Rh_n and Rh_m can be calculated:

${S^{'}}_{R h n, R h m} = \frac{(W_{s h p} \times S^{'}_{i n s h a p e}) + (W_{d i r} \times {S^{'}}_{d i r e c i t i o n})}{W_{s h p} + W_{d i r}}$

(23)
(4): Since Rh_n and Rh_m may not be able to match all holes successfully, the unmatched holes should be considered as penalties in the similarity calculation of Rh_n and Rh_m. This situation is termed matching completeness. Assuming that Rh_n and Rh_m, respectively, have n and m holes, t pairs of matching holes, and the unmatched hole weights of Rh_n and Rh_m are α and β, the matching completeness can be defined as:

${S^{'}}_{C o m p (R h n, R h m)} = \frac{t}{t + α \times (n - t) + β \times (m - t)}$

(24)

Three adjustment schemes for the weights α and β in the completeness computation for spatial scene similarity [39] can serve different retrieval purposes:

If α = β = 1, two scenes in the matching hole are equally important (the desired outcome of this experiment).
If α = β = 0, the similarity measurement process ignores unmatched holes.
If α = 1, β = 0, only the unmatched holes in the reference micro-spatial-scene have an impact on the matching completeness.

(5): W_comp is set as the weight value of the matching completeness, and the similarity of the micro-spatial-scene Rh_n and Rh_m can be calculated by:

$S_{M S C i} = S_{R h n, R h m} = {S^{'}}_{R h n, R h m} \times (W_{C o m p} \times ({S^{'}}_{C o m p} - 1) + 1)$

(25)

4. Similarity of a Complex Holed-Region Entity Scene

The above discussion indicates that the similarity between two complex scenes is the similarity measurement of the complex layer. The Pseudocode for the Measurement of Complex Holed-region Entity Scene’s Similarity is shown in Table 1.

(1): Suppose that the complex scenes S₁ and S₂ have t pairs of matching micro-spatial-scenes, such that S_MSCi is the similarity of the t^th pair of matching micro-spatial-scenes, and W_Ri is the weight of the corresponding holed-region entity. Thus, the similarity of S and S’ can be defined as

${S^{'}}_{M S C} = \frac{\sum_{i = 1}^{t} W_{R i} • S_{M S C i}}{\sum_{i = 1}^{t} W_{R i}}$

(26)
(2): Suppose that the complex scenes S₁ and S₂ have t pairs of matching micro-spatial-scenes, such that S_Ri is the shape similarity of the outer contour of the i^th matching holed-region entities, and W_Ri is the weight of the corresponding holed entities. Thus, the outline similarity S'_exshape between S₁ and S₂ can be defined as

${S^{'}}_{e x s h a p e} = \frac{\sum_{i = 1}^{t} W_{R i} • S_{R i}}{\sum_{i = 1}^{t} W_{R i}}$

(27)
(3): Assume that the weight of the position graph similarity is W_{p_g}, the similarity weights of the rotation, rotation, translation, and scaling of the position graph are respectively W_r1, W_r2, W_m, W_s, the matching similarity of the holed-region entity is W_{R_S}, the weight of the matching micro-spatial-scene set is W_MSC, and the similarity degree of the outer contour of the holed-region entity is W_exshape. Thus, to calculate the similarity of the complex scene,

$\begin{array}{l} S i m & = W_{p_g} \times {S^{'}}_{p_g} + W_{r 1} \times {S^{'}}_{r 1} + W_{r 2} \times {S^{'}}_{r 2} + W_{m} \times {S^{'}}_{m} + W_{s} \times {S^{'}}_{s} \\ + W_{R_S} \times {S^{'}}_{R_S} + W_{R_S} \times {S^{'}}_{R_S} + W_{e x s h a p e} \times {S^{'}}_{e x s h a p e} + W_{M S C} \times {S^{'}}_{M S C} \end{array}$

(28)

5. Experiments and Discussion

5.1. Experiment Data

We chose the Great Lakes in North America in 1986 and 2015 as the study area to calculate the similarity of the five lakes during different periods to validate the hierarchical model for the similarity measurement of the complex holed-region entity scene. The study area is composed of five large freshwater lakes at the junction of Canada and the United States of America, which are Lake Superior, Lake Huron, Lake Michigan, Lake Erie, and Lake Ontario, as shown in Figure 11. The outer contours of the five Great Lakes and the area of the lakes have changed during different periods due to global warming, human activity, and other factors.

The fundamental method for the comparison of the variation of the Great Lakes is to calculate the similarity of Great Lakes in different years. We chose the Great Lakes’ data in 1986 and 2015 to validate the hierarchical similarity model proposed in this paper. We treat the Great Lakes as regions that contain holes, and the islands in the lakes are regarded as holes in regional entities. The collection of the five lakes is a complex scene. The Great Lakes scene in 1986 and 2015 are, respectively, designated as Scenario A and Scenario B, and the number of holes and entities included in Scenario A and Scenario B are as shown in Table 2:

During the similarity measurement process of the two complex holed-region entity scenes, the similarities of the position graphs and geometric transformation similarities of CPPG should be first taken into account. Then, the geometry of the multi-holed-region and the holes is described by the multilevel chord length. The shape similarity is derived from the distance of the FFT description. Next, the directional consistency of the holes in the two matching regions should also be measured. To obtain the geometric similarity of the region and its holes, and the direction similarity between the holes, the top-down stratification method is used to find the correspondence between the regions and holes in this experiment. Finally, the weights of different dimensions are assigned to different levels, and the quantitative similarity between Scene A and Scene B is calculated.

5.2. Experimental Results and Analysis

5.2.1. Building and Measuring the Position Graphs

To build the complete distribution of the Great Lakes using position graphs, we ignore the holes in the multi-holed entities in Scene A and Scene B, considering them to be simple entities, and construct the CPPG, NTPPG, NPPG, and FPPG based the relationships noted in Section 2.2.1 of the two scenes, as shown in Figure 12 and Figure 13.

Section 2.2.2 indicates that each position graph can be described by a set of tension, and the projection interval function F(α) is a periodic change function with a variation period of 180°. In this experiment, we selected 180 sample points in the range of 180°. Each waveform corresponds to a single projection interval function, and each projection interval function corresponds to a unique position graph. The degree of matching of the two waveforms represents the similarity of the two position graphs. Using Formula (5), we obtain the MME of the two waveforms, and the similarity of the position graphs between Scenes A and B can be calculated by Formula (6). The CPPG, NTPPG, NPPG, and FPPG of the two scenarios are calculated and the results are shown in Table 3.

The data in Table 3 can be used to calculate the similarity between Scene A and Scene B as:

\begin{array}{l} {S^{'}}_{p_g} & = ({S^{'}}_{p_g 1} + {S^{'}}_{p_g 2} + {S^{'}}_{p_g 3} + {S^{'}}_{p_g 4}) / 4 \\ = (0.965755 + 0.971428 + 0.977408 + 0.970535) / 4 = 0.9712815 = 97.12815 % \end{array}

5.2.2. Great Lakes’ Distribution Transformation Measurement

In reality, the surface entities of two scenes may shift position, or change in size. Thus, the similarity measurement process must consider the geometric transformation similarity of the position graph. We defined the center angle of the CPPG above and used it to expound the rotation of the position graph. One side of the center angle is the connection between the centroid of the scene and the centroid of the position graph, and the other side is the edge that connects the start point on the MBR of the scene with the centroid of the scene.

Figure 14 and Figure 15 show that in this case, vector OOA runs from the center of Scene A to the center of the CPPG, vector OMA runs from the scene center to the start point of the MBR, and, in a similar manner, the vector OOB runs from the center of Scene B to the center of the CPPG, and vector OMB runs from the scene center to the start point of the MBR of Scene B.

The center angle β_A of Scene A is calculated to be 72.379°, the center angle β_B of Scene B is 70.935°, and the rotation transformation similarity (Simr1 = 0.99599) between Scenes A and B can be obtained by Formula (7).

The degree of change in the relative direction angle is expounded when measuring the rotation similarity. As shown in Figure 16, the direction angles of the MBRs of Scene A and its CPPG are, respectively, 43.677° & 45.098°, and the direction angles of the MBRs of Scene B and its CPPG are, respectively, 46.142° & 46.115°.

Therefore, the relative direction angles of Scenes A and B are, respectively, θ_A − λ_A = 1.421° and θ_B − λ_B = −0.027°. The rotation similarity (Simr2 = 0.99598) between Scenes A and B can be calculated by Formula (8).

To determine the movement of the holed entities inside the scene, we measure the degree of the relative change of the center distance. According to Formula (9), the relative center distance of Scenes A and B can be computed as l_A = 0.24599, l_B = 0.22117. Using the results in Formula (10), the translation similarity of the Scenes A and B is obtained (Sim_m = 0.8991).

Because the size of the entities in the scene may change, we must measure the scaling similarity of the two scenes. After determining the scene center, it is easy to derive the extended Hausdorff distance of Scenes A and B, respectively, from Formula (11)–(13). The scaling similarity of two scenes can be obtained by taking the expansion Hausdorff distance into Formula (14) as Sim_s = 0.9944. The calculation results are shown in Table 4.

According to the above, transformation similarity results for the position graphs are shown in Table 5.

5.2.3. Pairwise Matching and Shape Similarity of the Great Lakes

In this experiment, Scene B is the reference scenario, and Scene A is the matching scenario. The matching process of the holed-region entities comprises two steps: (1) filtering multi-holed-regions by a buffer analysis; (2) using the decision matrix to calculate the minimum Euclidean distance to determine the holed-region entity matching results.

The center and radius of the circular buffer must be determined in the first filtering step. The average radius of Scenes A and B is calculated first (R_A = 1382.3, R_B = 1408.8). The scene center d_{i_B} in Scene B is connected to the start point P’ of the MBR of the CPPG to obtain a set of distances d_Bi, and the connection is vector

\vec{P^{'} d_{i}}

, d_Ai = d_Bi*(R_A/R_B). Next, the angle between the direction vector of the MBR of the CPPG and

\vec{P^{'} d_{i}}

is computed as follows: {62.1471°, 70.3416°, 90°, 86.3311°, 70.3416°}. Eventually, the corresponding point Q_i of the center point of each holed-region entity in Scene B can be found in Scene A.

As shown in Figure 17, with Q_i as the center, half of the maximum chord length of Hi is the radius ri, and a circular buffer is built on scene A. The matching holed-region entities are those contained in or that intersect ⊙Q_i.

The matching results of the holed-region entities in Scene B are: the matching set of R’₁ is {R₁, R₃}, the matching set of R’ is {R₁, R₂}, the matching set of R’₃ is {R₂, R₃}, and the matching set of R’₄ is {R₂, R₄, R₅}, R’₅ is {R₄, R₅}.

Using the buffer filter, we obtain the matching set of each holed-region entity in Scene B. Next, we perform the Fast Fourier Transform (FFT) [31] to obtain the contour shape similarity of each pair of possible matching results. The results are shown in Table 6.

After filtering, we must obtain a definite set of matches so that each holed-region entity of the matching set in Scene B has the only corresponding surface entities within scene A. From Formula (16), we calculate the Euclidean distance between each holed-region entity of Scene B and the entities in its matching set, and bring the result into Formula (17) to obtain the decision matrix D.

D = [\begin{matrix} 0.0114 & 0.1708 & 0 & 0 & 0 \\ 0 & 0.0417 & 0.2049 & 0.0884 & 0 \\ 0.1690 & 0 & 0.0338 & 0 & 0 \\ 0 & 0 & 0 & 0.0219 & 0.0986 \\ 0 & 0 & 0 & 0.1479 & 0.0115 \end{matrix}] X = [\begin{array}{l} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{array}]

(29)

According to Formula (19), the minimum value of Z is 0.1203. Combined with the contour shape similarity measurement from Table 6, the final matching result can be determined by the Hungarian algorithm: {(R’₁, R₁), (R’₂, R₂), (R’₃, R₃), (R’₄, R₄), (R’₅, R₅)}.

On the basis of Formula (20), the similarity degree between scene A and Scene B is calculated as S’_{R_S} = 0.9759.

Formula (27) is used to calculate the outer contour shape similarity of all pairwise holed-region entities of scene A to scene B (S’_exshape = 0.9447).

5.2.4. Inner Contour Similarity Measurement of the Matching Lakes

According to Section 2.1, a multi-holed-region can be treated as a micro-spatial-scene, and the hole within the region can be regarded as an ordinary surface entity. To obtain a matching relationship between two holes in corresponding micro-spatial-scenes, the association graphs G_n and G_m should be created to describe the constraints of the two micro-spatial-scenes. The node value is the shape similarity of two holes and the edge value is the directional similarity of two pairs of holes.

The shape similarity of holes in each pair of matching micro-spatial-scenes can be computed by fast Fourier descriptor. In this experiment, R₂ (Lake Huron) is used as an example to show the matching analysis process, and the results are shown in Figure 18.

The association graph of the micro-spatial-scene R’₂ can be arbitrarily constructed by a hole H’_j_, and a corresponding hole of H’_j should be found in R₂. The association graph development of R’₂ begins with H’₅, and the subsequent order of priority is set as H’₆, H’₇, H’₈, H’₉. The construction process is:

(1): According to the results in Figure 18, the shape similarity between H’₅ and H₄ is the highest. So, H’₅ is paired with H₄ and (H’₅, H₄) is designated as a node in the association graph.
(2): Because H₄ has been matched with H’₅, H₄ should be excluded from the matching analysis of H’₆. H₅ has the highest similarity score with H’₆ in the remaining holes, and consequently (H’₆, H₅) id designated as an associated node.
(3): H’₇, H’₈, H’₉, H’₁₀ are matched with H₆, H₇, H₉ and H₈ according to the same rules in step 1 and step 2, forming the nodes (H’₇, H₆), (H’₈, H₇), (H’₉, H₉), and (H’₁₀, H₈).

The’ matching result for the inner holes of the micro-spatial-scenes R’₂ and R₂ generated by the above steps is {(H’₅, H₄) (H’₆, H₅) (H’₇, H₆) (H’₈, H₇) (H’₉, H₉) (H’₁₀, H₈)}. The weights of all holes are set to the same value in this experiment. Given that different priority matching orders will lead to different matching results, we must consider the entire matching order of holes in the test.

In addition to the shape similarity, the similarity measurement of the matching holes also must consider the consistency of the direction relationship. When evaluating the consistency of the direction relationship between two holes in the micro-spatial-scenes R₂ and R’₂, which are multi-hole regions, we should give the characteristic matrix of any pairs of holes in the scenes. A conceptual space of the F-Matrix is represented by the 4-D lattice [25]. The distance between two F-Matrixes on the 4-D lattice stands for the dissimilarity of the directions. After eliminating the redundancy, we obtain the association graphs in Figure 19.

Using Formulas (21) and (22), we can obtain the shape similarity and direction relationship similarity of each matching solution. The results are shown in Table 7.

It is easily to see that the shape similarity and direction relationship similarity of solution 1 are all higher than those in solution 2 from Table 7. We can compute the matching completeness of the two solutions with Formula (24) and then substitute the results of matching completeness, shape similarity, and direction similarity into Formulas (23) and (25) to obtain the similarities of the two solutions, as shown in Table 8.

In this experiment, the importance of the holes inside the Great Lakes are treated equally. It follows that all holes have the same weight, that is,

\sum_{i = 1}^{n} W_{H i} = 1

and

\sum_{i = 1}^{n (n - 1)} W_{D i} = 1

. We assume that the same weight is attached to the shape similarity, the direction relationship similarity, and the matching completeness; that is, W_shp + W_dir + W_comp = 1. Repeating the above processes yields all of the integral similarities of matching lakes, and the results are shown in Table 9.

5.2.5. Similarity of the Great Lakes Scene

Based on the hierarchical model in Section 2.1, the similarity of the two complex scenes is the generalization of the similarity of its component micro-spatial-scenes R_i and the distribution similarity of R_i_. The micro-spatial-scene similarity is considered to be an overall generalization of the geometric similarity of the hole H_j and the similarity of the distribution of H_j in R. Consequently, the similarity of two complex holed-region entity scenes is regarded as the unity of the micro-spatial-scene similarities, the outer contour shape similarities, and distribution similarities of the holed-region entities, along with the transformation similarities of the CPPG.

In Section 5.2.3, we calculated the similarities of the outer contour shape of the multi-holed-regions as simple entities. In this experiment, we consider each holed-region equally important, that is, each holed-region has the same weight. Additionally,

\sum_{i = 1}^{n} W_{R i} = 1

. The overall similarity of all matching micro-spatial scenes can be obtained by Formula (26) (Sim_MSC = 0.9087). At the end of experiment, according to the Analytic Hierarchy Process (AHP), the first-order weights of the similarity measurement is W_MSC = 0.3822, W_exshape = 0.1387, W_{p_g} = 0.1991, W_r1 = 0.0471, W_r2 = 0.0471, W_m = 0.0471, W_s = 0.0471, and W_{R_S} = 0.0916. As a result, the total similarity between Scenes A and B is

\begin{array}{l} S i m & = W_{p_g} \times {S^{'}}_{p_g} + W_{r 1} \times {S^{'}}_{r 1} + W_{r 2} \times {S^{'}}_{r 2} + W_{m} \times {S^{'}}_{m} + W_{s} \times {S^{'}}_{s} \\ + W_{R_S} \times {S^{'}}_{R_S} + W_{e x s h a p e} \times {S^{'}}_{e x s h a p e} + W_{M S C} \times {S^{'}}_{M S C} \\ = 0.9713 \times 19.91 % + 0.9960 \times 4.71 % + 0.9960 \times 4.71 % + 0.8991 \times 4.71 % + 0.9944 \times 4.71 % \\ + 0.9759 \times 9.16 % + 0.9447 \times 13.87 % + 0.9087 \times 38.22 % \\ = 93.48 % \end{array}

5.3. Experimental Results and Analysis

The experiment measuring the similarity of the two Great Lakes scenes in North America between 1986 and 2015 does not involve other scenarios that might match the map of the Great Lakes; therefore, we do not need to consider that little difference exists in the index that may exist in the similarity calculation process of the multiple matching scenarios. Only when the comparison of degree of importance between two similarity metrics can be determined, can the Analytic Hierarchy Process be used to obtain the index weights of a complex scene with a multi-holed entity similarity measurement system.

It is known that the similarity measurement of a complex holed-region entity scene has eight first-order indexes: the similarity of the matching micro-spatial-scene collection S’_MSC, the outer contour shape similarity of the matching holed-region entities S’_exshape, the similarity of the position graphs S’_{p_g}_, the transformation similarity of the CPPG (revolution similarity S’_r1, rotation similarity S’_r2, moving similarity S’_m, scaling similarity S’_s), and the matching similarity of the holed-regions S’_{R_S}. In accordance with the AHP, an 8th order matrix A with respect to the relative weight of the similarity index is obtained, as shown in Table 10.

The 8-order matrix of similarity index relative weight is normalized where the normalization formula is

b_{i j} = \frac{a_{i j}}{\sum_{i = 1}^{m} a_{i j}}

. The normalized matrix B of the similarity index is:

B = [\begin{matrix} 0.3871 & 0.3830 & 0.4000 & 0.3810 & 0.3810 & 0.3810 & 0.3810 & 0.3636 \\ 0.1290 & 0.1277 & 0.1000 & 0.1429 & 0.1429 & 0.1429 & 0.1429 & 0.1818 \\ 0.1935 & 0.2553 & 0.2000 & 0.1905 & 0.1905 & 0.1905 & 0.1905 & 0.1818 \\ 0.0484 & 0.0426 & 0.0500 & 0.0476 & 0.0476 & 0.0476 & 0.0476 & 0.0455 \\ 0.0484 & 0.0426 & 0.0500 & 0.0476 & 0.0476 & 0.0476 & 0.0476 & 0.0455 \\ 0.0484 & 0.0426 & 0.0500 & 0.0476 & 0.0476 & 0.0476 & 0.0476 & 0.0455 \\ 0.0484 & 0.0426 & 0.0500 & 0.0476 & 0.0476 & 0.0476 & 0.0476 & 0.0455 \\ 0.0968 & 0.0638 & 0.1000 & 0.0952 & 0.0952 & 0.0952 & 0.0952 & 0.0909 \end{matrix}]

B_j is obtained by summing each row of matrix B and is the eigenvector λ of matrix A.

λ^{- 1} = [\begin{matrix} 3.0575 & 1.1099 & 1.5926 & 0.3769 & 0.3769 & 0.3769 & 0.3769 & 0.7325 \end{matrix}]

(30)

According to the AHP, the weights of the eight first-level indicators of the similarity measurement of the complex holed-region entity scene must satisfy:

W_{i} = \frac{λ_{i}}{\sum_{i = 1}^{n} λ_{i}}

(31)

The weights of the eight similarity index are computed as W_MSC = 0.3822, W_exshape = 0.1387, W_{p_g} = 0.1991, W_r1 = 0.0471, W_r2 = 0.0471, W_m = 0.0471, W_s = 0.0471, and W_{R_S} = 0.0916.

To test the consistency of the contrast matrix A, the maximum eigenvalue λ_max = 8.028 of the matrix is calculated, and the consistency index is CI = 0.004. The average random randomness index RI is 1.41, CR = CI/RI = 0.004/1.41 = 0.0028 < 0.1, meaning that the contrast matrix A remains consistent.

6. Conclusions

To solve the matching problem of multiple lakes with multiple islands, several land areas with lakes, complex holed buildings, and other geographic entities with inner boundaries in GIS, we propose a new hierarchy similarity measurement method in this paper. We believe that the hierarchy similarity measurement method presented in this paper may be useful and is readily applicable to actual scenes for performing complicated spatial scene matching and querying by various users. During the process of similarity measurement, we dismantle the relationship between layers, and degrade a holed-region entity to a simple entity, initially. Afterwards, the similarity indexes of the complex scene’s similarity measurement are analyzed. The holed-region entity is subsequently regarded as a non-boundary micro-spatial-scene, and the similarity of the micro-spatial-scene is taken into a complex scene to present the similarity measurement results of the complex holed-region entity scene.

At the complex scene level, we take the holed-region as a micro-spatial-scene, and a position graph method is proposed to generate the distribution similarity of the holed-regions. The relationship between the shape and the direction of the micro-spatial-scene is described by the association graph. Additionally, the similarity of the two micro-scenes is also calculated by the matching association graphs.

Although the eight first-order index weights of a complex holed-region entity scene are discussed in Section 5.3, further improvement is still needed. In this paper, we did not study the weight ratio of each measurement index, and we treated all holes and all regions that contain holes equally. Whereas, in reality, the areas, the hole positions, multi-holed-regions, and their associated factors all will impact the weight. In addition, the matching of multiple complex holed-region entity scenes has not been studied yet. The matching efficiency of a complex scene similarity measurement and the improvement of the weight adjustment scheme should be studied in future research.

Acknowledgments

This work is supported by the National key R & D program of China (2017YFC0602204), the National Natural Science Foundation of China (No. 41401443), the Fundamental Research Funds for the Central Universities, China University of Geosciences (Wuhan) (No. CUG160226), and the Open Research Fund of Teaching Laboratory in China University of Geosciences (No. skj2014168).

Author Contributions

Zhanlong Chen conceived and designed the experiments and performed the modeling; Rongrong Zhu analyzed the data and reviewed and edited the draft. All authors discussed the basic structure of the manuscript and read and approved the manuscript.

Conflicts of Interest

The authors declare no conflict of interest.

References

Liu, Z. The Research on Areal Feature Matching among the Conflation of Urban Geographic Databases. Master’s Thesis, Wuhan University, Wuhan, China, June 2006. [Google Scholar]
Walter, V.; Fritsch, D. Matching spatial data sets: A statistical approach. Int. J. Geogr. Inf. Sci. 1999, 13, 445–473. [Google Scholar] [CrossRef]
Cobb, M.A.; Chung, M.J.; Foley, H., III; Petry, F.E.; Shaw, K.B.; Miller, H.V. A rule-based approach for the conflation of attributed vector data. GeoInformatica 1998, 2, 7–35. [Google Scholar] [CrossRef]
Saalfeld, A. Conflation automated map compilation. Int. J. Geogr. Inf. Syst. 1988, 2, 217–228. [Google Scholar] [CrossRef]
Tang, W.; Hao, Y.; Zhao, Y.; Li, N. Feature matching algorithm based on spatial similarity. Int. Soc. Opt. Photonics 2008, 7147, 714704. [Google Scholar]
Zhang, X.H.; Zhu, H.H.; Zheng, Q.Z. Hungary algorithm concerning best allotting and c++. Logist. Technol. 2004, 5, 25. [Google Scholar]
Van der Werff, H.M.A.; van der Meer, F.D. Shape-based classification of spectrally identical objects. ISPRS J. Photogr. Remote Sens. 2008, 63, 251–258. [Google Scholar] [CrossRef]
Ai, T.; Cheng, X.; Liu, P.; Yang, M. A shape analysis and template matching of building features by the fourier transform method. Comput. Environ. Urban Syst. 2013, 41, 219–233. [Google Scholar] [CrossRef]
Xie, P.; Xiaoyong, M.A.; Zhang, X.; Lin, M. A new fast algorithm for complex polygons matching. Comput. Eng. 2003, 29, 177–181. [Google Scholar]
Mount, D.M.; Netanyahu, N.S.; Moigne, J.L. Efficient algorithms for robust feature matching. Pattern Recognit. 1999, 32, 17–38. [Google Scholar] [CrossRef]
Masuyama, A. Methods for detecting apparent differences between spatial tessellations at different time points. Int. J. Geogr. Inf. Sci. 2006, 20, 633–648. [Google Scholar] [CrossRef]
Yan, H.W.; Wang, J.Y. A generic algorithm for point cluster generalization based on voronoi diagrams. J. Image Graph. 2005, 17, 633–636. [Google Scholar]
Du, Q.; Yang, P.; Tan, R. Classification of river networks structure based on spatial statistical character. Geomat. Inf. Sci. Wuhan Univ. 2006, 31, 419–422. [Google Scholar]
Lee, D.J.; Antani, S.; Long, L.R. Similarity measurement using polygon curve representation and fourier descriptors for shape-based vertebral image retrieval. Proc. SPIE 2003, 5032, 1283–1291. [Google Scholar]
Al, T.; Shuai, Y.; Li, J. A spatial query based on shape similarity cognition. Acta Geod. Cartogr. Sin. 2009, 38, 356–362. [Google Scholar]
Schneider, M.; Behr, T. Topological relationships between complex spatial objects. ACM Trans. Database Syst. 2006, 31, 39–81. [Google Scholar] [CrossRef]
Disser, Y.; Ghosh, S.K.; Mihalák, M.; Widmayer, P. Mapping a polygon with holes using a compass. Theor. Comput. Sci. 2014, 553, 106–113. [Google Scholar] [CrossRef]
Vasardani, M.; Egenhofer, M.J. In Comparing Relations with a Multi-Holed Region, Spatial Information Theory. In Proceedings of the International Conference, COSIT 2009, Aber Wrac’h, France, 21–25 September 2009; pp. 159–176. [Google Scholar]
OpenGIS Consortium Inc. Opengis simple features specification for SQL. In Technical Report; Revision 1.0; OpenGIS Consortium Inc.: Wayland, MA, USA, 1999. [Google Scholar]
Egenhofer, M. Topological relations between regions with holes. Int. J. Geogr. Inf. Sci. 1994, 8, 129–142. [Google Scholar] [CrossRef]
Clementini, E.; Felice, P.D.; Califano, G. Composite regions in topological queries. Inf. Syst. 1995, 20, 579–594. [Google Scholar] [CrossRef]
Egenhofer, M.J.; Vasardani, M. Spatial Reasoning with a Hole, Spatial Information Theory. In Proceedings of the International Conference, COSIT 2007, Melbourne, Australia, 19–23 September 2007; pp. 303–320. [Google Scholar]
Vasardani, M.; Egenhofer, M.J. Single-Holed Regions: Their Relations and Inferences. In Proceedings of the International Conference on Geographic Information Science, Park City, UT, USA, 23–26 September 2008; pp. 337–353. [Google Scholar]
Yokoo, M. Constraint Satisfaction Problem; Springer: Berlin/Heidelberg, Germany, 2001; pp. 21–70. [Google Scholar]
Xu, Y.; Xie, Z.; Chen, Z.; Wu, L. Shape similarity measurement model for holed polygons based on position graphs and fourier descriptors. Int. J. Geogr. Inf. Sci. 2016, 31, 253–279. [Google Scholar] [CrossRef]
Heijmans, H.J.A.M.; Tuzikov, A.V. Similarity and symmetry measures for convex shapes using minkowski addition. IEEE Trans. Pattern Anal. Mach. Intell. 1998, 20, 980–993. [Google Scholar] [CrossRef]
Fan, L.T.; Wu, S.Y.; Chen, J. An approach to similarity measures for polygonal shapes based on mechanics. J. Shanghai Jiaotong Univ. 2003, 37, 874–877. [Google Scholar]
Deng, M.; Li, Z. L.; Chen, X. Y. Extended hausdorff distance for spatial objects in GIS. Int. J. Geogr. Inf. Sci. 2007, 21, 459–475. [Google Scholar]
Feng, X.U.; Deng, M.; Zhao, B.; Chen, J. A detailed investigation on the methods of object matching: A detailed investigation on the methods of object matching. J. Geo-Inf. Sci. 2009, 11, 657–663. [Google Scholar]
Xiaoya, A.N.; Sun, Q.; Qiang, X.; Wei, Y. A shape multilevel description method and application in measuring geometry similarity of multi-scale spatial data. Acta Geod. Cartogr. Sin. 2011, 40, 495–508. [Google Scholar]
Chen, Z.; Qin, M.; Liang, W.U.; Xie, Z. Establishment of the comprehensive shape similarity model for complex polygon entity by using bending mutilevel chord complex function. Acta Geod. Cartogr. Sin. 2016, 45, 224–232. [Google Scholar]
Kaplansky, I. Rings of Operators; W. A. Benjamin, Inc.: Amsterdam, NY, USA, 1968. [Google Scholar]
Liu, T. Similarity of Spatial Group Objects; Wuhan University: Wuhan, China, 2011. [Google Scholar]
Serra, J. Image Analysis and Mathematical Morphology; Academic Press: Cambridge, MA, USA, 1982; p. 536. [Google Scholar]
Kuhn, H.W. The hungarian method for the assignment problem. Nav. Res. Logist. 2005, 52, 7–21. [Google Scholar] [CrossRef]
Markman, A.B.; Gentner, D. Structural alignment during similarity comparisons. Cogn. Psychol. 1993, 25, 431–467. [Google Scholar] [CrossRef]
Blaser, A.D. Sketching Spatial Queries. Ph.D. Thesis, University of Maine, Orono, ME, USA, 2000. [Google Scholar]
Egenhofer, M.J. Query processing in spatial-query-by-sketch. J. Vis. Lang. Comput. 1998, 8, 403–424. [Google Scholar] [CrossRef]
Nedas, K.A.; Egenhofer, M.J. Spatial-scene similarity queries. Trans. GIS 2008, 12, 661–681. [Google Scholar] [CrossRef]

Figure 1. Hierarchical decomposition of a complex scene.

Figure 2. (a) Selection of the center point and nearest tangent points; (b) center point position graph (CPPG); (c) nearest tangent point position (NTPPG).

Figure 3. (a) Selection of the nearest points and farthest points; (b) nearest points position graph (NPPG); (c) farthest points position graph (FPPG).

Figure 4. Revolution of CPPG.

Figure 5. Rotation of CPPG.

Figure 6. Complex holed-region entity scene S₁.

Figure 7. Complex holed-region entity scene S₂.

Figure 8. Buffer analysis determines the matching set.

Figure 9. Expression graph of the constraints of Rh_n.

Figure 10. (a) Complete solution; (b) incomplete solution; (c) no solution.

Figure 11. Great lakes study area.

Figure 12. Position graphs of the Great Lakes in 1986. (a) CPPG in 1986; (b) NTPPG in 1986; (c) NPPG in 1986; and (d) FPPG in 1986.

Figure 13. Position graphs of the Great Lakes in 2015. (a) CPPG in 2015; (b) NTPPG in 2015; (c) NPPG in 2015; and (d) FPPG in 2015.

Figure 14. The center angle of Scene A.

Figure 15. The center angle of Scene B.

Figure 16. Relative direction angle of Scene A and Scene B.

Figure 17. Buffer analysis of Scenes A and B.

Figure 18. Shape similarities of the inner contours of Lake Huron.

Figure 19. Association graphs of possible matching solutions between R₂ and R’₂.

Table 1. Pseudocode for the measurement of complex holed-region entity scene’s similarity.

1	Input: The two complex holed-regions entity scenes Scene A and Scene B Output: The similarity of the two scenes double ComputeSimofScene (Scene A, Scene B)
2	BuildPositionGraph (A); //CPPG_A, NTPPG_A, NPPG_A, FPPG_A
3	BuildPositionGraph (B); //CPPG_B, NTPPG_B, NPPG_B, FPPG_B
4	//the similarity of the two position graphs can be computed by Formula (6)
5	SimofDistribution (CPPG_A, CPPG_B); //S’_pg1 Similarity of CPPG
6	SimofDistribution (NTPPG_A, NTPPG_B); //S’_pg2 Similarity of NTPPG
7	SimofDistribution (NPPG_A, NPPG_B); //S’_pg3 Similarity of NPPG
8	SimofDistribution (FPPG_A, FPPG_B); //S’_pg4 Similarity of FPPG
9	SimofDis (S’_pg1, S’_pg2, S’_pg3, S’_pg4); //(S’_pg1+ S’_pg2,+S’_pg3,+S’_pg4)/4
10	//the revolution, rotation, moving and scaling similarities. Formulas (7), (8), (10) and (14)
11	SimofGeometricTrans (CPPG_A, CPPG_B)
12	PairwiseofMicroScene (A, B)
13	SimofShape (Ri, R’i); //by the method of multilevel length chord description
14	ComputeSimofMicroScene (Ri, R’_i)
15	return SimofScene
16	end procedure
17	double ComputeSimofMicroScene (Ri, R’_i)
18	SimofShape (Hi, H’_i);
19	SimofDirction (Hi, Hj, H’_i, H’_j)
20	PairwiseofHole (H_i,H’_i)
21	return SimofMicroScene
22	end procedure

Table 2. The number of holes and entities in Scenario A and B.

	Lake Superior	Lake Huron	Lake Michigan	Lake Erie	Lake Ontario	Sum
1986	3	6	2	2	3	16
2015	4	6	2	2	2	16

Table 3. The similarity results for the position graphs.

	CPPG	NPPG	FPPG	NTPPG
MME	0.101415	0.039020	0.030832	0.041860
MaxV	2.962511	1.365702	1.364719	1.420649
Sim	0.965755	0.971428	0.977408	0.970535

Table 4. Hausdorff distance calculation results for Scenes A and B.

Hausdorff Dis	R₁/R’₁	R₂/R’₂	R₃/R’₃	R₄/R’₄	R₅/R’₅
H^f1 (O_A, R_i)/ H^f1 (O_B, R’_i)	1647.6142/ 1679.754	1082.5446/ 1063.1474	965.5698/ 991.2311	1355.1922/ 1346.6466	1852.9394/ 1861.6845
H^f2 (R_i, O_A)/ H^f2 (R’_i, O_B)	595.8135/ 609.6859	235.1493/ 201.5952	184.2397/ 210.6782	737.9486/ 741.5354	1099.1535/ 1092.4108
H^f1f2 (O_A, R_i)/ H^f1f2 (O_B, R’_i)	1647.6142/ 1679.754	1082.5446/ 1063.1474	965.5698/ 991.2311	1355.1922/ 1346.6466	1852.9394/ 1861.6845

Table 5. CPPG transformation similarities.

	Sim_s	Sim_m	Sim_r1	Sim_r2
Transformation Similarity (%)	0.9944	0.8991	0.99599	0.99598

Table 6. The contour shape similarity of the matching holed-region entities after filtering.

Region	R’₁	R’₂	R’₃	R’₄	R’₅
R₁	0.9007/0.9053	0.7223/0.7660	-	-	-
R₂	-	0.8991/0.9201	0.8014/0.8392	0.7879/0.8185	-
R₃	0.8009/0.8474	-	0.9528/0.9791	-	-
R₄	-	-	-	0.9042/0.9335	0.7505/0.7860
R₅	-	-	-	0.7716/0.7964	0.9832/0.9855
Comment	A/B: A is the results computed by the method in literature [25]; B is the results computed by the method of multilevel chord description.

Table 7. Shape similarity and direction relationship similarity of each matching solution.

Solution	1	2
Shape	0.9093	0.9303
Direction	0.8583	0.9083

Table 8. Integral similarities of the two matching solutions.

Solution	1	2
Similarity	0.8838	0.9193

Table 9. The similarities of all matching micro-spatial-scenes in Scenes A and B.

Region	(R₁, R’₁)	(R₂, R’₂)	(R₃, R’₃)	(R₄, R’₄)	(R₅, R’₅)
S’_shape	0.9884	0.9608	0.9783	0.9936	0.9595
S’_direction	0.9861	0.7833	1	0.875	0.9375
S’_Comp	3/4	1	1	1	2/3
Similarity	0.9050	0.8721	0.9892	0.9343	0.8431

Table 10. Similarity index of the relative weight of the 8-order matrix.

W(A)	W_MSC	W_exshape	W_{p_g}	W_r1	W_r2	W_m	W_s	W_{R_S}
W_MSC	1	3	2	8	8	8	8	4
W_exshape	1/3	1	1/2	3	3	3	3	2
W_{p_g}	1/2	2	1	4	4	4	4	2
W_r1	1/8	1/3	1/4	1	1	1	1	1/2
W_r2	1/8	1/3	1/4	1	1	1	1	1/2
W_m	1/8	1/3	1/4	1	1	1	1	1/2
W_s	1/8	1/3	1/4	1	1	1	1	1/2
W_{R_S}	1/4	1/2	1/2	2	2	2	2	1

© 2017 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Chen, Z.; Zhu, R.; Xie, Z.; Wu, L. Hierarchical Model for the Similarity Measurement of a Complex Holed-Region Entity Scene. ISPRS Int. J. Geo-Inf. 2017, 6, 388. https://doi.org/10.3390/ijgi6120388

AMA Style

Chen Z, Zhu R, Xie Z, Wu L. Hierarchical Model for the Similarity Measurement of a Complex Holed-Region Entity Scene. ISPRS International Journal of Geo-Information. 2017; 6(12):388. https://doi.org/10.3390/ijgi6120388

Chicago/Turabian Style

Chen, Zhanlong, Rongrong Zhu, Zhong Xie, and Liang Wu. 2017. "Hierarchical Model for the Similarity Measurement of a Complex Holed-Region Entity Scene" ISPRS International Journal of Geo-Information 6, no. 12: 388. https://doi.org/10.3390/ijgi6120388

APA Style

Chen, Z., Zhu, R., Xie, Z., & Wu, L. (2017). Hierarchical Model for the Similarity Measurement of a Complex Holed-Region Entity Scene. ISPRS International Journal of Geo-Information, 6(12), 388. https://doi.org/10.3390/ijgi6120388

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Hierarchical Model for the Similarity Measurement of a Complex Holed-Region Entity Scene

Abstract

1. Introduction

2. Similarity Measurements of Two Complex Scenes

2.1. Hierarchical Method for a Complex Holed-Region Entity Scene

2.2. Location Distribution and Similarity Measurement

2.2.1. Position Graphs

2.2.2. Descriptive Measurement of the Position Graphs

2.2.3. Similarity Measurement of the Position Graph

2.2.4. Geometric Transformation of the Position Graph

Revolution Similarity

Rotation Similarity

Moving Similarity

Scaling Similarity

3. Similarity Measurement of Micro-Spatial-Scene

3.1. Pairwise Matching of a Holed-Region Entity

3.2. Pairwise Matching of Holes

3.3. Similarity Measurement of Holes

4. Similarity of a Complex Holed-Region Entity Scene

5. Experiments and Discussion

5.1. Experiment Data

5.2. Experimental Results and Analysis

5.2.1. Building and Measuring the Position Graphs

5.2.2. Great Lakes’ Distribution Transformation Measurement

5.2.3. Pairwise Matching and Shape Similarity of the Great Lakes

5.2.4. Inner Contour Similarity Measurement of the Matching Lakes

5.2.5. Similarity of the Great Lakes Scene

5.3. Experimental Results and Analysis

6. Conclusions

Acknowledgments

Author Contributions

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI