The technique to detect road intersections from road network relies on the underlying road vector data representation. Typically, there are two common ways to represent the geometry of a road vector dataset: (1). The road network is composed of multiple road segments (polylines), and the line segments are split at intersections (as the example shown in Figure 3(a)). (2). The road network is composed of multiple road segments (polylines), but the line segments are not split (if not necessary) at intersections (see Figure 3(b)).

This generation of our system focus on handling vector data represented in the first way (i.e., the line segments are split at intersections), because most of the popular road vector datasets (such as US Census TIGER/Line files and NAVSTREETS from NAVTEQ) represent their datasets in such way. Based on this sort of road segment representation, the process of finding the intersection points from the road network is divided into two steps. First, the system examines all line segments in the vector data to label the endpoints of each segment as the candidate intersection points. Second, the system examines the connectivity of these candidate points to determine if they are intersection points. In this step, each candidate point is verified to see if there are more than two line segments connected at this point. If so, this point is marked as an intersection point and the directions of the segments that are connected at the intersection point are calculated. In practice, the search of road intersections from large road networks is supported efficiently by spatial access method R-tree [ 11 ].

Now that we have described how to detect feature points from a road network, we now describe how this (a) Road segments are split at intersections (b) Road segments are not split at intersections Figure 3: Different ways to represent a crossshaped road network with one intersection information can be used to automatically match two road networks. Let U= {ui | ui= (xi, yi ), where (xi, yi ) is the location of intersections of the first road network} and V= {vj | vj= (mj, nj), where (mj, nj) is the location of intersections of the second road network}. Our objective is to locate the set: {RelPat={(ui,vj) | where ui is the intersection on the first vector dataset and vj is the corresponding intersection (if any) on the second dataset.

That is, point ui and vj are formed by the same intersected road segments}. Consider identifying matched point pattern between two road networks. If the system can recognize the names of road segments that meet at intersections, it can use these road names to infer the set RelPat. However, road vector data may not include the non-spatial attribute, road name. Instead, we propose our approach that relies on some prominent geometric information, such as the distribution of points, the degree of each point and the direction of incident road segments, to locate the matched point pattern. In other words, the problem of point pattern matching is at its core a geometric point sets matching problem. The basic idea is to find the transformation T between the layout (with relative distances) of the point set U and V.

The key computation of matching the two sets of points is calculating a proper transformation T, which is a 2D rigid motion (rotation and translation) with scaling.

Because the majority of vector datasets are oriented such that north is up, we only compute the translation transformation with scaling. Without loss of generality, we consider how to compute the transformation where we map from a fraction α of the points of U to the points of V. The reason that only a fraction α of the points of U is considered is that one road vector dataset could be detailed while the other one is represented abstractly or there may be some missing/noisy points from each road network. The transformation T brings at least a fraction α of the points of U into a subset of V. This implies:

∃ T and U’ ⊆ U , such that T(U’) ⊆ V , where | U’ | ≥ α| U | and T(U’) denotes the set of points that results from applying T to the points of U’. Or equivalently, for a 2D point (x, y) in the point set U’ ⊆ U, ∃ T in the matrix form Sx 0 0  0 Sy 0 (Sx and Sy are scale factors along x and y Tx Ty 1 direction, respectively, while Tx and Ty are translation factors along x and y directions, respectively), such that Sx 0 0   [x, y, 1] *  0 Sy 0 = [m , n, 1] , where | U’ | ≥ the datasets. Therefore, when checking whether a 2D point p belongs to the point set V, we declare that p ∈ V, if there exists a point in V that is within Euclidean distance δ of p for a small fixed positive constant δ, which controls the degree of inaccuracy. The minimum δ such that there is a match for U’ in V is called Hausdorff distance. Different computations of the minimum Hausdorff distance have been studied in great depth in the computational geometry literature [ 12 ]. We do not seek to minimize δ but rather adopt an acceptable threshold for δ.

The threshold is relatively small compared to the average inter-point distances in V. In fact, this sort of problem was categorized as “Nearly Exact” point matching problem in [ 13 ].

Given the parameters α and δ, to obtain a proper transformation T, we need to compute the values of the four unknown parameters Sx, Sy, Tx and Ty. This implies that at least four different equations are required. A straightforward (brute-force) method is first choosing a point pair (x1, y1) and (x2, y2) from U, then, for every pair of distinct points (m1, n1) and (m2, n2) in V, the transformation T’ that map the point pair on U to the point pair on V is computed by solving the following four equations: Sx* x1 + Tx = m1 Sy* y1 + Ty = n1 Sx* x2 + Tx = m2 Sy* y2 + Ty = n2

Each generated transformation T’ is thus applied to the entire points in U to check whether there are more than α|U| points that can be aligned with some points on V within the threshold δ. This process is repeated for each possible point pair from U, which implies that it could require examining O(|U|2) pairs in the worst case. Since for each such pair, the algorithm needs to try all possible point pairs on V (i.e., O(|V|2 )) and spends O(|U| log|V|) time to examine the generated transformation T’, this method has a worst case running time of O(|U|3 |V|2 log|V|). The advantage of this approach is that we can find a mapping (if the mapping exists) with a proper threshold δ, even in the presence of very noisy data. However, it suffers from high computation time. One way to improve the efficiency of the algorithm is to utilize randomization in choosing the pair of points from U as proposed in [ 14 ], thus achieving the running time of O(|V|2 |U| log|V|).

However, their approach is not appropriate for our datasets because it is possible one vector dataset is in detailed level while other vector dataset is represented abstractly.

In fact, in our previous work [ 15 ], we utilized the similar technique to match two point sets detected from a raster map and an image. More precisely, in [ 15 ], we proposed an enhanced point pattern matching algorithm to find the overlapping area of a map and an imagery by utilizing map-scale to prune the search space of possible point pattern matches (by reducing the numbers of potential matching point pairs needed to be examined). In the following sections, we focus on finding the matching Tx

Ty

1 α| U | and the 2D point (m, n) belongs to the intersection point set V on the second vector dataset. With this setting, we do not expect point coordinates to match exactly because of finite-precision computation or small errors in

(a) The two networks to compare (b) Using Point connectivity and Angles of the point to prune the search space

(110) (c) Using Angles between the points to prune the search space

Figure 4: Comparing two road networks by using Geo-PPM between different road networks and developing more is detailed and the other one is represented abstractly), efficient techniques by utilizing some additional spatial this condition will not be valid for a large portion of the information that can be inferred from the road vector intersections and may only be valid for major roads’ datasets. In addition, we also discuss how to prioritize the intersections. potential matching point pairs needed to be examined. 2. Angles of the point: The angles of a point are defined as the angles of the road segments that intersect at that 2.4 Enhanced PPM Algorithm: Prioritized Geo-PPM point. Similar to the connectivity, a point P’1 in S2 can Due to the poor performance of the brute-force point only be considered as a candidate for point P1 in S1 only if pattern matching algorithm mentioned in the previous the two points have similar angles, or the difference section, PPM cannot be applied to large datasets where between their angles is less than a threshold value. To the number of points (or intersections) is in the order of illustrate, consider comparing two road networks as the thousands (such as the road networks covering large example shown in Figure 4(a). Whenever the system areas). Consequently, we utilize some auxiliary chooses a point (as the point shown in the left figure of information that can be extracted from the road vector Figure 4(b)) in one road network, it only has to consider data to improve the performance of PPM for larger road the candidate matched points with same connectivity and networks. With the goal to reduce the numbers of similar directions of intersected road segments from the potential matching point pairs needed to be examined, the other network (as some possible candidates marked in the intuition here is to exclude all unlikely matching point right figure of Figure 4(b)). Note that if the densities of pairs. For example, given a point pair (x1, y1) and (x2, y2) the datasets are different (i.e., one dataset is detailed and in S1, we only need to consider pairs (x’1, y’1) and (x’2, the other one is represented abstractly), this condition will y’2) in S2 as candidate pairs such that the real world not be valid for a large portion of the intersections and distance and angle between (x1, y1) and (x2, y2) is close to may only be valid for major roads’ intersections. the real world distance and angle between (x’1, y’1) and 3. Angle between the points: The angle between two (x’2, y’2). In addition, (x’1, y’1) would be considered as a points is defined as the angle of the straight line that possible matching point for (x1, y1) if and only if they connects the points. Clearly, a pair (P’1,P’2) can be have similar connectivity and road directions. We considered as a possible candidate for the pair (P1,P2) only categorize the auxiliary information we utilize to the if the angle between P’1 and P’2 is similar to the angle following groups. between P1 and P2, or the difference between their angles 1. Point connectivity: We define the connectivity of a is less than a threshold value. Note that this feature can point as the number of the road segments that intersect at only be utilized when the second dataset is not rotated and that point. Clearly, if datasets S1 and S2 have very close has the same direction as the first dataset. Consider the densities (i.e., number of intersections per one unit of example shown in Figure 4(c). Whenever the system area), a candidate matching point P’1 in S2 for a point P1 chooses a point pair (as the point pair shown in the left in S1 must have the same connectivity as P1. Note that if figure of Figure 4(c) and the angle between these two the densities of the datasets are different (i.e., one dataset points is about 110 degree) in one road network, it only has to consider the candidate matched point pairs with the similar angle (as some possible candidate point pairs marked as dash lines in the right figure of Figure 4(c)). 4. Distance between the points: The distance between two points is defined as the length of the straight line that connects the points in Euclidean space. Similar to the previous case, a pair (P’1,P’2) can be considered as a possible candidate for the pair (P1,P2) only if the length of the line connecting P’1 and P’2 is similar to the length of the line connecting P1 and P2, or the difference between the lengths is less than a threshold value. Note that this feature can only be utilized when the relationship between the geometry of the datasets is known and hence, the distances between objects in two datasets are comparable.

By applying the above conditions simultaneously, the Geo-PPM approach can be defined as a specialization of PPM where only the candidate pairs that have similar point connectivity, angles of the point, angles between the points, and distances between the points, will be considered. This will greatly reduce the size of the search space. However, this is still a very complex approach when the number of points in the datasets is in the order of thousands. Hence, we propose prioritized Geo-PPM that can dramatically reduce the complexity of Geo-PPM for large networks by examining the points that have the minimum number of candidates.

The intuition behind prioritized Geo-PPM is to increase the possibility of examining the correct matching pair from the candidates by first examining the pairs of points that have the minimum number of candidates. Suppose that there are n1, n2, n3 and n4 points in the pool of candidates for points P1, P2, P3, and P4, respectively. This means that the number of possible candidate pairs for (P1, P2) and (P3, P4) that must be examined by Geo-PPM is n1n2 and n3n4, respectively. Note that the values of n1 to n4 could be very large, especially for urban areas where the road networks follow a grid pattern and hence, a large portion of the intersections have the same connectivity and angles. Also note that from these possible candidate pairs, only (a maximum of) one pair is the correctly matching one. Hence, by first examining the combination that contains the minimum number of points, we can significantly increase the possibility of finding the correct matching pair sooner. Consider the example shown in Figure 5. Our system can start the matching process by first examining the combination that contains the minimum number of points. As the point pair chosen in the left figure of Figure 5(b), it has less potential matching point pairs as shown in the right figure of Figure 5(b), comparing to the point pair examined in the left figure of Figure 5(a).