Next Article in Journal
A Review of Urban Air Pollution Monitoring and Exposure Assessment Methods
Previous Article in Journal
Machine Learning Techniques for Modelling Short Term Land-Use Change
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

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

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://0-doi-org.brum.beds.ac.uk/10.3390/ijgi6120388
Submission received: 13 October 2017 / Revised: 15 November 2017 / Accepted: 27 November 2017 / Published: 29 November 2017

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.

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 Ri, i.e., S = {R1R2∪…∪Rn}. Therefore, the similarity of a complex scene can be regarded as an overall generalization of the similarity of Ri and the distribution similarity of Ri.
The multi-holed-region R, which can be thought of as a micro-scene, is m (m ≥ 0) holes Hj merged, i.e., R = {H1H2∪…∪Hn}. Likewise, the similarity of the micro-spatial-scene is considered to be a generalization of the geometric similarity of the hole Hj and the similarity of the distribution of Hj 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 Ri (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 Hj (j = 1, 2, …, m), and the simple entity Hj has a fixed position distribution in Ri. 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, N1, N2, N3 are, respectively, the nearest points from the centroid O to the outlines of R1, R2, R3, and F1, F2, F3, are, respectively, the farthest points from the centroid O to the exterior boundaries of R1, R2, R3, so the nearest points position graph(NPPG) and farthest points position graph (FPPG) is formed by connecting O to Ni and Fi 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:
i = 1 N f i x = 0 , i = 1 N f i y = 0
The parameter fix is the decomposition part of force fi on the x-axis, fiy is the decomposition part of force fi 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 ( α ) = i 1 N | f i x ( α ) |
Similarly, Fy(α) is available:
F y ( α ) = i 1 N | f i y ( α ) |
The projection interval function of the force diagram is defined as
F ( α ) = F x ( α ) / F y ( α )
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 P1 and P2 is calculated as:
M P 1 P 2 ( l ) = 1 N i = 0 N 1 | F 1 ( i ) F 2 ( i l ) |
where F1(i) and F2(i − l) (0 ≤ l ≤ N − 1) are the projection ratio functions of the position graphs P1 and P2, 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 min { M P 1 P 2 ( l ) } max { F 1 ( i ) , F 2 ( i ) } , 0 l ,   i N 1

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 O1 is the center of the CPPG. The vector from the point O to the nearest vertex of the MBR of the complex scene is u2, and u1 is the vector from the point O to the point O1. The angle between u1 and u2 is β, which is defined as the central angle. β is negative when u1 is on the left side of u2. The change value θ of β is the revolution angle.
The revolution similarity of two CPPGs can be defined as:
S r 1 = 1 | β 1 β 2 | 360 °

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 v1 is the direction vector of the scene and v2 is the direction vector of CPPG. The angle α between v1 and v2 is defined as the relative direction angle, and is negative when v1 is on the left side of v2. (Figure 5).
The rotation similarity of the two CPPGs with rotation can be defined as:
S r 2 = 1 | 1 2 | 360 °

Moving Similarity

The average radius of a complex scene is R, and the relative center distance (RCD) l is defined as:
l = [ x ( o ) x ( o 1 ) ] 2 + [ y ( o ) y ( o 1 ) ] 2 R
The center coordinate of the complex scene is (X(O),Y(O)), and at the same time (X(O1),Y(O1)) is the center coordinate of the CPPG. The moving translation similarity [33] can be defined as:
S m = 1 | l 1 l 2 | max ( l 1 , l 2 )

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:
h f 1 ( A , B ) = min { ε i : f 1 = ϑ ( ( B S ( ε i ) ) A ) ϑ ( A ) } h f 2 ( B , A ) = min { ε j : f 2 = ϑ ( ( A S ( ε j ) ) B ) ϑ ( B ) }
The extended Hausdorff distance formula is:
H f 1 f 2 ( A , B ) = max { min { ε i : f 1 = ϑ ( ( B S ( ε i ) ) A ) ϑ ( A ) } , min { ε j : f 2 = ϑ ( ( A S ( ε j ) ) B ) ϑ ( B ) } }
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). 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 = 1 N R i = 0 N H i
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 | D i s p D i s q | max ( D i s p , D i s q )

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 S1 and S2, which may produce different matching results: (R1, R1), (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 S1 and S2 are, respectively, the reference scene and the matching scene. Any holed-region Ri in S1 will match with a corresponding set of holed-regions {Ri} in S2. To obtain the matching set of the holed-region Ri in S1, 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 P d i by connecting di and P’, whose length is d1_i, as shown in Figure 8a. The angle between the vector P d i and the direction vector of the MBR is δ. Next, a point Q is determined in S2. A circular buffer with the center of Q is drawn and the average radius of the holed-region Ri is ri; furthermore, the regions in the buffer or that intersect with the buffer are regarded as the matching region candidates of Ri. The angle between the vector P Q and the vector of the MBR direction vector is δ, as shown in Figure 8b. The length of P Q is defined as d2_i:
d 2 _ i = d 1 _ i × R 2 R 1
where R2 is the average radius of scene S2 and R1 is the average radius of scene S1.
After obtaining the matching candidate set {Ri} of the reference entity Ri, 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 Ri and the regions belonging to S2 but not included in {Ri} 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 S1, n is the number of regions in S2, and the element dij in D is defined as dij = dis(Ri, R’j), which expresses the Euclidean distance between centroid Ri and R’j.
d i s ( R i , R j ) = ( x ( R i ) x ( R j ) 2 ) + ( y ( R i ) y ( R j ) 2 )
where (x(Ri),y(Ri)) and (x(R’i),y(R’j)) are the centroids of Ri and R’j, respectively.
The decision variable xi,j ranges from
x x , j = { 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
The decision variable matrix X is
D = [ d 11 d 12 d 1 d 1 n d 21 d 22 d 2 d 2 n d 1 d 2 d d n d m 1 d m 2 d m d m n ] X = [ x 11 x 12 x 1 x 1 n x 21 x 22 x 2 x 2 n x 1 x 2 x x n x m 1 x m 2 x m x m n ]
So the matching results can be calculated by
min Z = i = 1 m j = 1 n d i j x i j    s . t . { i = 1 m x i j = 1 , j = 1 , 2 , , n j = 1 n x i j = 1 , i = 1 , 2 , , n x i j = 1   o r   0 , i = 1 , 2 , , m , j = 1 , 2 , n
In this process, the value of xij 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 Ri in S1 and R’j in S2. Furthermore, the matching similarity between S1 and S2 can be obtained by:
S R _ S = 1 n i = 0 n ( 1 d i )
where n is the number of matching regions, and di 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 ebn and ebm represent the edges of the region Rhn and Rhm; (2) the variable set H1, …, Hn represents the holes in Rhn; (3) for each Hi, sets of possible matching variables H’I = {H’1, …, H’l} corresponding to holes in Rhm exist; (4) each variable Hi has a unit variable Si that describes its shape; and (5) for each variable set (Hi, H’j), a binary variable dij exists that describes the relationship between the variables.
In this study, the matching association graph is utilized to describe the constraints in Rhn, 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 Rhn and Rhm 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 Gm of Rhm matched with the graph Gn of Rhn, in which all holes and directions of Rhn have a correspondence in Rhm.
  • Incomplete solution. A subgraph G’m of Gm matches the subgraph G’n of Gn, in which a subset of holes and directions of Rhn have a correspondence in Rhm.
  • No solution.
The formation of the association graph for the holed-region entities Rhn and Rhm, for which Rhn has the graph G with the node set (g1, g2, ..., gn) and Rhm has the graph G’(g’1, g’2, ..., g’n), contains two important steps. First, a node aij(gi, g’j) is created if g’j is in G’ that satisfies the univariates (shape matching) of gi in G. Second, the nodes are connected with their edges by inserting an edge to connect the node aij(gi, g’j) with alk(gl, 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 Rhn and Rhm have t pairs of matching holes, SHi is the shape similarity of the ith pair of holes and WHi is the weight of the ith pair of holes. Next, the shape similarity between Rhn and Rhm is defined by S’shape for
S i n s h a p e = i = 1 t W H i S H i i = 1 t W H i
(2)
Supposing that the holed-region entities Rhn and Rhm have t pairs of matching holes with t(t − 1)/2 pairs of matching directions, SDi is the similarity of the ith pair of direction relationships, which have a weight WDi. Thus, the direction relationship similarity S’direction between Rhn and Rhm can be defined as
S d i r e c t i o n = i = 1 t ( t 1 ) / 2 W D i S D i i = 1 t ( t 1 ) / 2 W D i
(3)
The weight of the shape similarity and the direction relationship similarity is set to Wshp and Wdir, respectively; then, the similarity S’Rhn,Rhm between micro-spatial-scene Rhn and Rhm can be calculated:
S R h n , R h m = ( W s h p × S i n s h a p e ) + ( W d i r × S d i r e c i t i o n ) W s h p + W d i r
(4)
Since Rhn and Rhm may not be able to match all holes successfully, the unmatched holes should be considered as penalties in the similarity calculation of Rhn and Rhm. This situation is termed matching completeness. Assuming that Rhn and Rhm, respectively, have n and m holes, t pairs of matching holes, and the unmatched hole weights of Rhn and Rhm are α and β, the matching completeness can be defined as:
S C o m p ( R h n , R h m ) = t t + α × ( n t ) + β × ( m t )
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)
Wcomp is set as the weight value of the matching completeness, and the similarity of the micro-spatial-scene Rhn and Rhm can be calculated by:
S M S C i = S R h n , R h m = S R h n , R h m × ( W C o m p × ( S C o m p 1 ) + 1 )

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 S1 and S2 have t pairs of matching micro-spatial-scenes, such that SMSCi is the similarity of the tth pair of matching micro-spatial-scenes, and WRi is the weight of the corresponding holed-region entity. Thus, the similarity of S and S’ can be defined as
S M S C = i = 1 t W R i S M S C i i = 1 t W R i
(2)
Suppose that the complex scenes S1 and S2 have t pairs of matching micro-spatial-scenes, such that SRi is the shape similarity of the outer contour of the ith matching holed-region entities, and WRi is the weight of the corresponding holed entities. Thus, the outline similarity S'exshape between S1 and S2 can be defined as
S e x s h a p e = i = 1 t W R i S R i i = 1 t W R i
(3)
Assume that the weight of the position graph similarity is Wp_g, the similarity weights of the rotation, rotation, translation, and scaling of the position graph are respectively Wr1, Wr2, Wm, Ws, the matching similarity of the holed-region entity is WR_S, the weight of the matching micro-spatial-scene set is WMSC, and the similarity degree of the outer contour of the holed-region entity is Wexshape. Thus, to calculate the similarity of the complex scene,
S i m = W p _ g × S p _ g + W r 1 × S r 1 + W r 2 × S r 2 + W m × S m + W s × S s + W R _ S × S R _ S + W R _ S × S R _ S + W e x s h a p e × S e x s h a p e + W M S C × S M S C

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:
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 %

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 lA = 0.24599, lB = 0.22117. Using the results in Formula (10), the translation similarity of the Scenes A and B is obtained (Simm = 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 Sims = 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 (RA = 1382.3, RB = 1408.8). The scene center di_B in Scene B is connected to the start point P’ of the MBR of the CPPG to obtain a set of distances dBi, and the connection is vector P d i , dAi = dBi*(RA/RB). Next, the angle between the direction vector of the MBR of the CPPG and P d i is computed as follows: {62.1471°, 70.3416°, 90°, 86.3311°, 70.3416°}. Eventually, the corresponding point Qi of the center point of each holed-region entity in Scene B can be found in Scene A.
As shown in Figure 17, with Qi 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 ⊙Qi.
The matching results of the holed-region entities in Scene B are: the matching set of R’1 is {R1, R3}, the matching set of R’ is {R1, R2}, the matching set of R’3 is {R2, R3}, and the matching set of R’4 is {R2, R4, R5}, R’5 is {R4, R5}.
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 = [ 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 ] X = [ 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 ]
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’1, R1), (R2, R2), (R3, R3), (R4, R4), (R5, R5)}.
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 Gn and Gm 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, R2 (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’2 can be arbitrarily constructed by a hole H’j, and a corresponding hole of H’j should be found in R2. The association graph development of R’2 begins with H’5, and the subsequent order of priority is set as H’6, H’7, H’8, H’9. The construction process is:
(1)
According to the results in Figure 18, the shape similarity between H’5 and H4 is the highest. So, H’5 is paired with H4 and (H’5, H4) is designated as a node in the association graph.
(2)
Because H4 has been matched with H’5, H4 should be excluded from the matching analysis of H’6. H5 has the highest similarity score with H’6 in the remaining holes, and consequently (H’6, H5) id designated as an associated node.
(3)
H’7, H’8, H’9, H’10 are matched with H6, H7, H9 and H8 according to the same rules in step 1 and step 2, forming the nodes (H’7, H6), (H’8, H7), (H’9, H9), and (H’10, H8).
The’ matching result for the inner holes of the micro-spatial-scenes R’2 and R2 generated by the above steps is {(H’5, H4) (H’6, H5) (H’7, H6) (H’8, H7) (H’9, H9) (H’10, H8)}. 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 R2 and R’2, 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, i = 1 n W H i = 1 and 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, Wshp + Wdir + Wcomp = 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 Ri and the distribution similarity of Ri. The micro-spatial-scene similarity is considered to be an overall generalization of the geometric similarity of the hole Hj and the similarity of the distribution of Hj 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, i = 1 n W R i = 1 . The overall similarity of all matching micro-spatial scenes can be obtained by Formula (26) (SimMSC = 0.9087). At the end of experiment, according to the Analytic Hierarchy Process (AHP), the first-order weights of the similarity measurement is WMSC = 0.3822, Wexshape = 0.1387, Wp_g = 0.1991, Wr1 = 0.0471, Wr2 = 0.0471, Wm = 0.0471, Ws = 0.0471, and WR_S = 0.0916. As a result, the total similarity between Scenes A and B is
S i m = W p _ g × S p _ g + W r 1 × S r 1 + W r 2 × S r 2 + W m × S m + W s × S s + W R _ S × S R _ S + W e x s h a p e × S e x s h a p e + W M S C × S M S C = 0.9713 × 19.91 % + 0.9960 × 4.71 % + 0.9960 × 4.71 % + 0.8991 × 4.71 % + 0.9944 × 4.71 % + 0.9759 × 9.16 % + 0.9447 × 13.87 % + 0.9087 × 38.22 % = 93.48 %

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 = a i j i = 1 m a i j . The normalized matrix B of the similarity index is:
B = [ 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 ]
Bj is obtained by summing each row of matrix B and is the eigenvector λ of matrix A.
λ 1 = [ 3.0575 1.1099 1.5926 0.3769 0.3769 0.3769 0.3769 0.7325 ]
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 = λ i i = 1 n λ i
The weights of the eight similarity index are computed as WMSC = 0.3822, Wexshape = 0.1387, Wp_g = 0.1991, Wr1 = 0.0471, Wr2 = 0.0471, Wm = 0.0471, Ws = 0.0471, and WR_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

  1. 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]
  2. Walter, V.; Fritsch, D. Matching spatial data sets: A statistical approach. Int. J. Geogr. Inf. Sci. 1999, 13, 445–473. [Google Scholar] [CrossRef]
  3. 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]
  4. Saalfeld, A. Conflation automated map compilation. Int. J. Geogr. Inf. Syst. 1988, 2, 217–228. [Google Scholar] [CrossRef]
  5. Tang, W.; Hao, Y.; Zhao, Y.; Li, N. Feature matching algorithm based on spatial similarity. Int. Soc. Opt. Photonics 2008, 7147, 714704. [Google Scholar]
  6. Zhang, X.H.; Zhu, H.H.; Zheng, Q.Z. Hungary algorithm concerning best allotting and c++. Logist. Technol. 2004, 5, 25. [Google Scholar]
  7. 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]
  8. 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]
  9. 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]
  10. Mount, D.M.; Netanyahu, N.S.; Moigne, J.L. Efficient algorithms for robust feature matching. Pattern Recognit. 1999, 32, 17–38. [Google Scholar] [CrossRef]
  11. 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]
  12. 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]
  13. 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]
  14. 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]
  15. Al, T.; Shuai, Y.; Li, J. A spatial query based on shape similarity cognition. Acta Geod. Cartogr. Sin. 2009, 38, 356–362. [Google Scholar]
  16. Schneider, M.; Behr, T. Topological relationships between complex spatial objects. ACM Trans. Database Syst. 2006, 31, 39–81. [Google Scholar] [CrossRef]
  17. 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]
  18. 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]
  19. OpenGIS Consortium Inc. Opengis simple features specification for SQL. In Technical Report; Revision 1.0; OpenGIS Consortium Inc.: Wayland, MA, USA, 1999. [Google Scholar]
  20. Egenhofer, M. Topological relations between regions with holes. Int. J. Geogr. Inf. Sci. 1994, 8, 129–142. [Google Scholar] [CrossRef]
  21. Clementini, E.; Felice, P.D.; Califano, G. Composite regions in topological queries. Inf. Syst. 1995, 20, 579–594. [Google Scholar] [CrossRef]
  22. 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]
  23. 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]
  24. Yokoo, M. Constraint Satisfaction Problem; Springer: Berlin/Heidelberg, Germany, 2001; pp. 21–70. [Google Scholar]
  25. 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]
  26. 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]
  27. 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]
  28. 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]
  29. 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]
  30. 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]
  31. 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]
  32. Kaplansky, I. Rings of Operators; W. A. Benjamin, Inc.: Amsterdam, NY, USA, 1968. [Google Scholar]
  33. Liu, T. Similarity of Spatial Group Objects; Wuhan University: Wuhan, China, 2011. [Google Scholar]
  34. Serra, J. Image Analysis and Mathematical Morphology; Academic Press: Cambridge, MA, USA, 1982; p. 536. [Google Scholar]
  35. Kuhn, H.W. The hungarian method for the assignment problem. Nav. Res. Logist. 2005, 52, 7–21. [Google Scholar] [CrossRef]
  36. Markman, A.B.; Gentner, D. Structural alignment during similarity comparisons. Cogn. Psychol. 1993, 25, 431–467. [Google Scholar] [CrossRef]
  37. Blaser, A.D. Sketching Spatial Queries. Ph.D. Thesis, University of Maine, Orono, ME, USA, 2000. [Google Scholar]
  38. Egenhofer, M.J. Query processing in spatial-query-by-sketch. J. Vis. Lang. Comput. 1998, 8, 403–424. [Google Scholar] [CrossRef]
  39. 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 1. Hierarchical decomposition of a complex scene.
Ijgi 06 00388 g001
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 2. (a) Selection of the center point and nearest tangent points; (b) center point position graph (CPPG); (c) nearest tangent point position (NTPPG).
Ijgi 06 00388 g002
Figure 3. (a) Selection of the nearest points and farthest points; (b) nearest points position graph (NPPG); (c) farthest points position graph (FPPG).
Figure 3. (a) Selection of the nearest points and farthest points; (b) nearest points position graph (NPPG); (c) farthest points position graph (FPPG).
Ijgi 06 00388 g003
Figure 4. Revolution of CPPG.
Figure 4. Revolution of CPPG.
Ijgi 06 00388 g004
Figure 5. Rotation of CPPG.
Figure 5. Rotation of CPPG.
Ijgi 06 00388 g005
Figure 6. Complex holed-region entity scene S1.
Figure 6. Complex holed-region entity scene S1.
Ijgi 06 00388 g006
Figure 7. Complex holed-region entity scene S2.
Figure 7. Complex holed-region entity scene S2.
Ijgi 06 00388 g007
Figure 8. Buffer analysis determines the matching set.
Figure 8. Buffer analysis determines the matching set.
Ijgi 06 00388 g008
Figure 9. Expression graph of the constraints of Rhn.
Figure 9. Expression graph of the constraints of Rhn.
Ijgi 06 00388 g009
Figure 10. (a) Complete solution; (b) incomplete solution; (c) no solution.
Figure 10. (a) Complete solution; (b) incomplete solution; (c) no solution.
Ijgi 06 00388 g010
Figure 11. Great lakes study area.
Figure 11. Great lakes study area.
Ijgi 06 00388 g011
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 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.
Ijgi 06 00388 g012
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 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.
Ijgi 06 00388 g013
Figure 14. The center angle of Scene A.
Figure 14. The center angle of Scene A.
Ijgi 06 00388 g014
Figure 15. The center angle of Scene B.
Figure 15. The center angle of Scene B.
Ijgi 06 00388 g015
Figure 16. Relative direction angle of Scene A and Scene B.
Figure 16. Relative direction angle of Scene A and Scene B.
Ijgi 06 00388 g016
Figure 17. Buffer analysis of Scenes A and B.
Figure 17. Buffer analysis of Scenes A and B.
Ijgi 06 00388 g017
Figure 18. Shape similarities of the inner contours of Lake Huron.
Figure 18. Shape similarities of the inner contours of Lake Huron.
Ijgi 06 00388 g018
Figure 19. Association graphs of possible matching solutions between R2 and R2.
Figure 19. Association graphs of possible matching solutions between R2 and R2.
Ijgi 06 00388 g019aIjgi 06 00388 g019b
Table 1. Pseudocode for the measurement of complex holed-region entity scene’s similarity.
Table 1. Pseudocode for the measurement of complex holed-region entity scene’s similarity.
1Input: 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)
2BuildPositionGraph (A); //CPPG_A, NTPPG_A, NPPG_A, FPPG_A
3BuildPositionGraph (B); //CPPG_B, NTPPG_B, NPPG_B, FPPG_B
4//the similarity of the two position graphs can be computed by Formula (6)
5SimofDistribution (CPPG_A, CPPG_B); //S’_pg1 Similarity of CPPG
6SimofDistribution (NTPPG_A, NTPPG_B); //S’_pg2 Similarity of NTPPG
7SimofDistribution (NPPG_A, NPPG_B); //S’_pg3 Similarity of NPPG
8SimofDistribution (FPPG_A, FPPG_B); //S’_pg4 Similarity of FPPG
9SimofDis (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)
11SimofGeometricTrans (CPPG_A, CPPG_B)
12PairwiseofMicroScene (A, B)
13SimofShape (Ri, R’i); //by the method of multilevel length chord description
14ComputeSimofMicroScene (Ri, R’i)
15return SimofScene
16end procedure
17double ComputeSimofMicroScene (Ri, R’i)
18SimofShape (Hi, H’i);
19SimofDirction (Hi, Hj, H’i, H’j)
20PairwiseofHole (Hi,H’i)
21return SimofMicroScene
22end procedure
Table 2. The number of holes and entities in Scenario A and B.
Table 2. The number of holes and entities in Scenario A and B.
Lake SuperiorLake HuronLake MichiganLake ErieLake OntarioSum
19863622316
20154622216
Table 3. The similarity results for the position graphs.
Table 3. The similarity results for the position graphs.
CPPGNPPGFPPGNTPPG
MME0.1014150.0390200.0308320.041860
MaxV2.9625111.3657021.3647191.420649
Sim0.9657550.9714280.9774080.970535
Table 4. Hausdorff distance calculation results for Scenes A and B.
Table 4. Hausdorff distance calculation results for Scenes A and B.
Hausdorff DisR1/R’1R2/R’2R3/R’3R4/R’4R5/R’5
Hf1 (OA, Ri)/
Hf1 (OB, R’i)
1647.6142/
1679.754
1082.5446/
1063.1474
965.5698/
991.2311
1355.1922/
1346.6466
1852.9394/
1861.6845
Hf2 (Ri, OA)/
Hf2 (R’i, OB)
595.8135/
609.6859
235.1493/
201.5952
184.2397/
210.6782
737.9486/
741.5354
1099.1535/
1092.4108
Hf1f2 (OA, Ri)/
Hf1f2 (OB, 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.
Table 5. CPPG transformation similarities.
SimsSimmSimr1Simr2
Transformation Similarity (%)0.99440.89910.995990.99598
Table 6. The contour shape similarity of the matching holed-region entities after filtering.
Table 6. The contour shape similarity of the matching holed-region entities after filtering.
RegionR’1R’2R’3R’4R’5
R10.9007/0.90530.7223/0.7660---
R2-0.8991/0.92010.8014/0.83920.7879/0.8185-
R30.8009/0.8474-0.9528/0.9791--
R4---0.9042/0.93350.7505/0.7860
R5---0.7716/0.79640.9832/0.9855
CommentA/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.
Table 7. Shape similarity and direction relationship similarity of each matching solution.
Solution12
Shape0.90930.9303
Direction0.85830.9083
Table 8. Integral similarities of the two matching solutions.
Table 8. Integral similarities of the two matching solutions.
Solution12
Similarity0.88380.9193
Table 9. The similarities of all matching micro-spatial-scenes in Scenes A and B.
Table 9. The similarities of all matching micro-spatial-scenes in Scenes A and B.
Region(R1, R’1)(R2, R’2)(R3, R’3)(R4, R’4)(R5, R’5)
S’shape0.98840.96080.97830.99360.9595
S’direction0.98610.783310.8750.9375
S’Comp3/41112/3
Similarity0.90500.87210.98920.93430.8431
Table 10. Similarity index of the relative weight of the 8-order matrix.
Table 10. Similarity index of the relative weight of the 8-order matrix.
W(A)WMSCWexshapeWp_gWr1Wr2WmWsWR_S
WMSC13288884
Wexshape1/311/233332
Wp_g1/22144442
Wr11/81/31/411111/2
Wr21/81/31/411111/2
Wm1/81/31/411111/2
Ws1/81/31/411111/2
WR_S1/41/21/222221

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://0-doi-org.brum.beds.ac.uk/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://0-doi-org.brum.beds.ac.uk/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://0-doi-org.brum.beds.ac.uk/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 Metrics

Back to TopTop