A Road Map Refinement Method Using Delaunay Triangulation for Big Trace Data

Abstract

With the rapid development of urban transportation, people urgently need high-precision and up-to-date road maps. At the same time, people themselves are an important source of road information for detailed map construction, as they can detect real-world road surfaces with GPS devices in the course of their everyday life. Big trace data makes it possible and provides a great opportunity to extract and refine road maps at relatively low cost. In this paper, a new refinement method is proposed for incremental road map construction using big trace data, employing Delaunay triangulation for higher accuracy during the GPS trace stream fusion process. An experiment and evaluation were carried out on the GPS traces collected by taxis in Wuhan, China. The results show that the proposed method is practical and improves upon existing incremental methods in terms of accuracy.

1. Introduction

With the rapid development of urban transportation infrastructure, people urgently need high-precision real-time road maps. At the same time, huge amounts of spatio-temporal trace data are being generated when people travel through the urban road network every day, acting as human sensors collecting real-time road information. How to construct road maps from these ubiquitous vehicle traces has attracted more and more attention in recent years.

A vast body of literature addressing the problem of road map construction from vehicle tracking data currently exists [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20], which can be divided into two categories in terms of the form of data input, offline and online algorithms. These methods take a full collection or a continuous stream of data as input, respectively, which will be detailed in the following section.

As a comparison and evaluation in the recent survey article of map construction methods indicates [21], maps produced by the offline methods are generally superior, density-based methods are more accurate and less complex, and the intersection identification and linking method developed by Karagiorgou et al. [5] yielded the most satisfying results balancing accuracy and coverage, among the seven methods evaluated. Incremental methods, however, are superior only in terms of coverage for streets less frequently traversed. Moreover, incremental methods are preferable in the context of big trace data. Given the development of ubiquitous computing and intelligent transportation systems, large quantities of traces are more commonly collected continuously as a real-time stream. Hence, incremental methods must be further developed to enhance their accuracy.

Existing approaches except for density-based methods, were mainly designed for, or based on the assumption of, high frequency track points. Each edge between neighboring track points is supposed to be a valid sample of the street. However, this is often challenged or has not held true for data sources like practical vehicle tracking applications, since strategies for data collection, transmission, and storage yield a relatively low time resolution for sampled locations [18]. A map construction algorithm for big trace data should also consider this factor when producing a robust inference of the road geometry.

Motivated to make use of the massive but low-frequency vehicle tracking data in the form of a stream instead of a collection of data, attempts have been made to improve the accuracy of the incremental approach for road map construction. Streaming low-frequency traces are incrementally merged using constrained Delaunay triangulation. Topology and geometry at intersections of road segments are also carefully handled for low-frequency data input. The contribution of this paper however, is to provide an online map construction method for continuously streaming big trace data at a less than ideal sampling frequency.

The remainder of the paper is as follows, the proposed method is introduced in Section 3 after a review of existing map construction methods in Section 2. In Section 4, GPS traces at a relatively low sampling rate approximately every 40 s, collected by taxis in Wuhan, China, are taken as a streaming data source to validate the proposed method and its robustness. The accuracy of the proposed method is compared to other incremental methods by established graph-based quality evaluation measures. The correctness of the topology of intersections is evaluated using the F-score [22]. Finally, conclusions are drawn in Section 5.

2. Related Work

Existing road map construction methods can be categorized as offline algorithms and online algorithms, in terms of the form of the input data.

Offline algorithms take a collection of archived traces as input and process this collection at the same time. Edelkamp and Schrodl [1] clustered the track points using a k-means algorithm. Schoredl et al. [2] proposed an approach to cluster track points from random seeds, and then derived a center line representation of roads by spline fitting the track points from the same road segment. The traces used were collected by vehicles equipped with differential GPS receivers. Similarly, Worrall and Nebot [3] clustered raw track points using similar positions with similar headings, and linked neighboring cluster centers to form a coherent chain. The final road center lines were derived using non-linear least squares fitting. Apart from this early work on point clustering methods, segment clustering or bundling also have been proposed. Liu et al. [4] presented a similar clustering method, although they clustered the tiny segments formed by two consecutive track points within a time interval threshold. Further, Karagiorgou and Pfoser [5] clustered traces linking the same pair of intersections as a polygonal curve instead of straight segment, based on the identification of possible intersections. A sweep-line method has been used to merge the geometry of bundled traces, while a similar method with more focus on the intersection boundary detection has also been developed [6]. Lane level information can also be effectively extracted by clustering [7,8].

Different from these clustering approaches, density-based methods [9,10,11,12] provide another way to derive road maps from vehicle traces, also taking all track points as input. In these methods, the collection of track points in a study area is first converted to a raster image. The cell value of this raster image is determined by simply counting track points within a cell, or by calculating the kernel density estimation of input track points. Finally, image processing techniques, such as skeleton extraction, are used to extract the geometry of roads from the image.

Online algorithms take a stream of track points from a certain vehicle as input, and process this input stream to progressively construct and refine a road map. This kind of approach emerged in early work on incremental updating of road maps according to GPS traces [13,14], which merged every trace successively into an existing road map. Ekpenyong et al. [15] developed an artificial neutral network to classify the input track points by the type of road, which can accept continuous input data streams. Considering the uncertainty stemming from the input tracking data, Cao and Krumm [16] presented a novel physical model for preprocessing traces, which clarified traces by defining and calculating the balance of attractive and repelling forces in a so-called gravity model. The clarified track points were incrementally added to the empty road map or merged based on their distance and heading. This incremental manner of constructing a road map from scratch has been continuously improved; using a curve-graph matching distance measure and minimum-link representative edge, Ahmed et al. [17] proposed a map construction method with theoretical error estimation.

Some of the methods reviewed [17] are capable of handling three-dimensional input traces, while there are also dedicated methods for extracting three-dimensional road maps [18]. It is beyond the scope of this paper to incrementally construct the two-dimensional road map from low-frequency data and so is not discussed.

Recently, both online and offline methods have begun to focus on the practical issues of less than ideal data sources, mostly vehicle tracking systems with track points recorded at a lower frequency. Li et al. [19] managed to handle incremental vehicle tracking data in the national highway network at a large geographic scale, a method more suitable for small scale map construction. Qiu and Wang [20] proposed an offline solution called the segmentation and grouping framework, which clusters track points and then extracts centerlines by the locally-weighted scatterplot smooth method. The method proposed in this paper continues along this path, providing an online map construction method at a city scale using a less than ideal vehicle tracking data source.

3. Methodology

This section details the proposed road map construction and refinement method, aiming to extract the geometry and topology of an urban road network at the carriageway level. As in the common incremental methods, our proposed method preprocesses the input trace data to handle the uncertainty in data collected under complex circumstances (Section 3.1). The streaming track points are segmented according to their heading direction and similarity to the partially constructed map (Section 3.2). A road map can then be constructed from an empty map and refined repeatedly by appending new segments to and merging similar segments in an existing map by constrained Delaunay triangulation (CDT) and a modified skeleton of the triangular network (Section 3.3). Topology information is extracted in this process when the input track departs from or enters a segment already in the map (Section 3.4). These steps are illustrated by Figure 1 and are elaborated in the following subsections, respectively. The evaluation methods applied to these results are also presented in the last subsection.

3.1. Data Preprocessing

The GPS track point records contain the following fields: taxi ID, sampling timestamp, speed, heading, and coordinates. The speeds and headings were acquired from GPS devices, not post hoc estimations from the locations and timestamps of neighboring points. The trace of each taxi was acquired by linking the track points from the same car by a straight line chronologically. However, there are two inevitable problems in the practice of GPS observation that must be tackled, inaccurate track point position and GPS signal interruption.

Inaccurate positioning results from high-rise blocks, trees, and other objects beside urban roads (i.e., urban canyons) are known as track point drift. The velocity (speed and heading) and position of the preceding and succeeding track points can be utilized to predict the possible position of drifting point [23]. A track point should be reachable from a previous point with the velocity and possible error considered, and it should also reach the next point. If the recorded position is outside the predicted area, it is considered an outlier and its position will be corrected by a simple linear interpolation between the preceding and succeeding track points so as to reduce the disadvantages of inaccurate track point positioning.

The second case of GPS signal interruption may cause a loss of track points, when vehicles travel in tunnels or under elevated roads. When the interval between successive track points is significantly larger than the expected value, interpolation may be inapplicable; interpolation based simply on direct linking of two distant points introduces gross error. With no reliable referential maps available during the map construction phase of this study, trace recovery techniques could not be used. These kinds of traces must usually be split into two trips, based on temporal or spatial intervals [24].

After preprocessing, the input trace now consists of clean GPS track points with timestamp and velocity. GPS track points from the same vehicle and the same trip are then connected by straight edges according to time sequence.

3.2. Segmentation

After preprocessing, we obtained traces for each trip for map construction and subsequent refinement. Before constructing or refining the road map, traces of trips must be segmented to avoid segments that are not aligned to the real position of a road. Similar segments of a single long trip must also be segmented for merger rather than added as duplicate. The subsections must be located to a matched portion in the partially constructed map for merger. Subsections with no similar parts are added to the map.

There are several established frameworks using monotone spatio-temporal criteria [23] or non-monotone criteria [25] that address the trace segmentation problem. We use a relatively simple heading criterion as in the first framework. If the incoming track point has similar heading to track points already in the current subsection, it will be added to the current subsection. Otherwise, the current subsection ends and the incoming track point will start a new subsection (Figure 2a). This is helpful when eliminating turning segments not aligned to real streets.

After this heading-based segmentation to avoid misaligned segments and similar segments in the same trip, a further segmentation prepares them for a subsequent fusion procedure. We find the longest possible segment that is similar to the road segments in the partially constructed map, and segment the subsection according to the matching results. Similarity is defined simply by the orientation difference and Euclidean distance to existing road segments in the partially constructed map.

If there are portions of the new trace that have a similar road segment, as in a partially constructed map, they are subject to merging in the next step, which is detailed in Section 3.3. Otherwise, if there are no portions of the new trace intersecting or similar to any segments in the partially constructed map, it will be directly included in the partially constructed map as a single segment. This is exemplified in Figure 2b. The first two points in the new trace have no similar segments in the partially constructed map (solid lines), while the last four points in the new trace find a similar counterpart in an existing trace. As such, the trace is split, with the first part to be added and the second part to be merged in the next step. If any subsection of the new trace intersects with road segments in the constructed map, it will be split at the intersections before being merged with similar road segments. Intersections are added to the point set for future triangulation processing.

3.3. Merging

For the matched portions of the new trace and existing street segment in the partially constructed map, we calculate a modified skeleton for a Delaunay triangulation constrained by the two road segments considering their weights, to gradually refine the geometry of the constructed road map.

3.3.1. Constrained Delaunay Triangulation of Two Similar Traces

The Delaunay triangulation is a support model suited for spatial proximity and geomorphology analysis. It also yields satisfying results in cartographic generalization applications, such as amalgamation of multiple polygons, collapse of areal features, and map conflict detection and displacement [26]. In the density-based method for map construction from traces [6], more accurate road maps are produced using Voronoi diagrams of the density contours. To merge incoming traces gradually into similar segments in a partially constructed map, a similarly weighted skeleton is used to construct the average geometric representation of a road network.

In view of the trace fusion, we adopt Delaunay triangulation based on the linear constraint of a pair of trace subsections and road segments in a partially constructed map (see Figure 3, where the thick line is the partially constructed map before fusion and the thin line is the new trace to be merged).

First of all, intersections of the traces are detected. If any, traces are split at the intersections (grey point in Figure 3) and the intersections are added to the triangulation point set. Then the constrained Delaunay triangulation of the track points is constructed based on Delaunay triangulation criterion (i.e., no point is inside the circumscribed circle of any triangles) [27].

3.3.2. Modified Weighted Skeleton

To merge the new trace into the map segment, we extract the skeleton of the triangular network. The segment in the partially constructed map has already taken into consideration some traces passing nearby, while the trace to be merged is only a single observation of the road geometry. Hence, they should be merged with different weights assigned to the vertices of triangles. The new track point is weighted as 1, and the weight of a point in a constructed map segment is the number of traces it has merged. Then, the weight of points in the merged road segment can be derived by adding the weights of the new trace and the road segment in the partially constructed map. Thus, the weight remains proportional to the number of observations from which it has been derived.

It is necessary to analyze the adjacency relationship of the triangles in order to define the skeleton [28]. In the case of two polylines, there are two types of triangles in terms of the number of adjacent edges (right panel in Figure 3). A type I triangle has two adjacent edges with other triangles, and its weighted skeleton is defined as the segment connecting the two weighted dividing points of the adjacent edges. A type II triangle has only one adjacent edge with other triangles, and its weighted skeleton is defined as the line segment from the opposite vertex of the adjacent edges to the weighted dividing point of the adjacent edge. The weighted dividing point P (X_P, Y_P) of line segment AB is calculated by Equation (1) and its weight T_P defined as Equation (2), where T_A and T_B denote the weights of the segment endpoints A (X_A, Y_A) and B (X_B, Y_B).

$$\{\begin{array}{c}{X}_p=\left(X_A\times T_A+X_B\times T_B\right)/\left(T_A+T_B\right)\\ Y_p=\left(Y_A\times T_A+Y_B\times T_B\right)/\left(T_A+T_B\right)\end{array}$$

(1)

$$T_p=T_A+T_B$$

(2)

In this original definition of a skeleton, the start and end points of the matched proportion is not averaged, which does not agree with our intent to average the representation of streets gradually. As such, the first and last triangles of type I are handled as if they were of type II, with their skeleton endpoint defined as the weighted dividing point of the start or end points of the matched proportions.

Thus, the skeletons in each Delaunay triangle constitute a fused segment in the updated map. It can be regarded as line before the fusion, during further iterative trace fusion, and fused with the newly added traces, thus refining a partially constructed map by adding all similar traces during the iterative fusion process.

This trace fusion method averages a new trace with similar parts of a map constructed based on the Delaunay triangulation. Since the input traces have been preprocessed to mitigate uncertainty during observation, this merging process can refine a partially constructed map gradually to become detailed and accurate. Although the fusion process will add to the geometric complexity of the representation of a road network and subsequently, add to the time consumption in the fusion process, this influence is necessary for geometric representation refinement and is ultimately limited in terms of computational cost. In the case of low-frequency traces, the geometric representation of a sinuous street is refined by a fusion of multiple traces. With a time complexity of O(nlogn) for the constrained Delaunay triangulation algorithm [27], the increasing complexity of road geometry will only cause a modest increase in time consumption.

3.4. Topology Extraction

In the segmentation step, some portions of the new trace are matched to certain road segments in a partially constructed map, while other portions may enter or depart from these matched parts. Point matching is determined by similarity, taking both geometric distance and the heading direction into consideration, as previously used in the method by Cao and Krumm [16]. In this case, the involved segments can be divided into three parts for the extraction of topology information, i.e., one overlapping part and two branching parts, as illustrated in Figure 4. A₁ and A₂ are the first unmatched points in each part, and are defined as branching points. The topological branching point A is defined as the dividing point of segment A₁A₂ by the ratio of their weights. Spontaneously, point A is then added to the constructed map as a topology point. With the connectivity at point A validated, it is then connected to points B and C, the adjacent geometric points in each of the involved roads; this finalizes the topological information extraction at this point.

3.5. Evaluation

The map construction results were evaluated from three aspects in this paper, visual inspection, positional accuracy, and topology correctness. Visual inspection is a common qualitative evaluation step, it is an inspection of the constructed maps and a comparison with referential ground-truth vector maps or an orthoimage.

3.5.1. Positional Accuracy

For quantitative evaluation of the positional accuracy, a generic measure for line features as proposed by Goodchild and Hunter [29] was used to evaluate road map construction results. Taking the standard vector map as a reference, this method overlays constructed maps on a buffer area of the referential road network, and then derives the proportion of constructed maps that fall within the buffer. This method is quite simple for the positional accuracy evaluation from the geographic information perspective, but may encounter problems in the case of map construction evaluation where the evaluated data sets may contain segments that are not correct representations of the ground truth.

As such, evaluation methods from the computing perspective that formalize the problem as a comparison of graphs are also considered as complementary measures, including directed Hausdorff distance [30], path-based distance [31], and shortest path based distance [5]. Based on a review by Ahmed et al. [21], we selected the directed Hausdorff distance to focus on the geometric accuracy rather than the topology of the network, which will be evaluated separately.

The directed Hausdorff distance between two sets of points A and B is defined as follows:

$$\overrightarrow{d}\left(A,B\right)={\max }_{a\in A}{\min }_{b\in B}d\left(a,b\right)$$

(3)

where d(a, b) is the Euclidean distance between two points a and b. Intuitively, the directed Hausdorff distance assigns to every point in A its nearest neighbor $b\in B$ and takes the maximum of all distances between assigned points. By this measure, we quantify the distance between each edge in the constructed map and the benchmark map. The descriptive statistics of the edge-graph distance indicate the quality of maps.

3.5.2. Topological Correctness

Our proposed method also detects topological points during the process of trace fusion. Hence, it is necessary to evaluate the topological correctness separately. Assessment is quite straightforward, comparing topological points of extracted maps and the ground-truth benchmark. Although the methods compared do not express topology explicitly, it can be inferred from the graph structure that nodes with a degree of three or more are actually a topological point in the constructed map. With this method, the precision and recall of these methods can be evaluated.

4. Experiment and Evaluation

4.1. Experiment

GPS traces used in the experiment were collected by taxis in the city of Wuhan in March 2014. Traces in the areas of Qingshan and Zhuankou were extracted for map construction. There were 139,860 and 26,334 GPS points collected in 9089 and 3765 trips for each area, and the average sampling intervals were 40.8 and 38.2 s, respectively. The trips were comprised of records from two to 386 points each. Due to different capacities and traffic statuses, the distances between consecutive points range widely, with the majority from 2.87 m (10th percentile) to 552.38 m (90th percentile) for the experimental area of Qingshan, and 1.68 m to 509.21 m for Zhuankou.

The experiment was conducted on a personal computer, equipped with an Intel Core i3 processor at 3.07 GHz and 8 gigabytes of memory, with our own method implemented in C#. The tolerance parameters used in the search for similar road segments were set to 30 degrees in heading difference and 20 m in Euclidean distance. As a comparison, road networks of the same areas were also constructed by other incremental methods, including those of Cao and Krumm [16] and Ahmed and Wenk [17]. The open source implementations of the compared methods in Java and Python were used and the parameters for other compared methods were set to the defaults. For all tested methods, the minimum time interval of signal interruption in the preprocessing step was set to 180 s. Considering the common urban scenario where a probe car waits in a queue at a place with a poor GPS signal, it is reasonable for the probe car to spend several minutes waiting before leaving the area. Consecutive track points with intervals greater than this threshold were split as described in the preprocessing step.

4.2. Evaluation

A standard vector map of the city was taken as a benchmark road network for evaluation, after manual selection of the road segments traversed by the input traces. The positional accuracy of the vector map is claimed to be 10 m as a commercial digital map for navigation purposes. Since the benchmark represents the roads as their center lines, dual carriageways in the results produced using our method and Cao’s method were collapsed to make them compatible to the evaluation methods, outside of visual inspection.

4.2.1. Visual Inspection

As a qualitative evaluation of the results, the generated road map was overlaid on an orthoimage of the corresponding area, as shown in Figure 5. It is clear by visual inspection that the road map constructed by the proposed method completely covers the roads in the experimental area, and is aligned to the orthoimage. The compared methods, however, produced messy outputs, with non-existent roads captured in Ahmed’s results and duplicated samples of the same road segments in Cao’s results.

The coverage of the map was limited due to the trace coverage. Chinese residential areas are usually less open to the general public for security reasons, with access controls. As such, streets inside residential areas are less motorized and subsequently missing from the vehicle tracking data.

4.2.2. Positional Accuracy

The positional accuracy measures of the compared methods, including an accurate proportion for different buffer radiuses and statistics for Hausdorff distances, are listed in

Table 1. Proportion of constructed maps within different buffers.

Area	Method	Proportion of Constructed Maps within Buffer Radius (m)
		2	5	7	10
Qingshan	Proposed	59.2	72.8	79.3	90.6
	Ahmed	17.7	40.3	52.9	65.5
	Cao	17.9	39.3	52.8	66.6
Zhuankou	Proposed	64.3	76.2	81.6	92.3
	Ahmed	10.5	25.1	32.1	39.4
	Cao	20.4	47.2	56.2	64.9

and

Table 2. Hausdorff distance measure evaluation.

Area	Method	Hausdorff Distance (m)
		Min	Max	Median	Avg	2%	5%	10%
Qingshan	Proposed	1	45	7	8	35	24	18
	Ahmed	2	272	16	50	256	167	147
	Cao	3	251	130	125	251	234	198
Zhuankou	Proposed	1	43	6	7	36	23	18
	Ahmed	1	345	64	80	229	174	154
	Cao	2	367	146	139	277	263	212

. These tables indicate that the proposed method yielded better results than other incremental methods evaluated, in terms of positional accuracy from low-frequency vehicle traces. The Ahmed method performed worse than the Cao method according to the proportion inside the buffers, but better according to the Hausdorff distance and visual inspection. This may be due to duplicate representations of the streets that were not merged in the Cao method results.

4.2.3. Topological Correctness

Table 3. Topology point correctness.

Area	Method	Topology Points Count			F Score
		Correct	Identified	Ground-Truth
Qingshan	Proposed	32	32	32	1.00
	Ahmed	27	58	32	0.60
	Cao	9	50	32	0.22
Zhuankou	Proposed	30	30	48	0.77
	Ahmed	21	81	48	0.33
	Cao	10	67	48	0.17

lists the evaluation result for topological points. The proposed method performed better on the regular road network, but was not sensitive to minor branches with only limited trace coverage. The proposed method had a high precision with identified topology points, but did not detect all of the ground-truth topology points due to its insensitivity to less traversed streets. The Ahmed method also recognized most topology points, but excessive topology points at crossings were not merged. The Cao method performed poorly when extracting the topology at the intersections.

4.3. Discussion

As our evaluation results indicate, the proposed method was validated as an incremental approach taking low-frequency track points as input and constructing street maps with topological relation. However, the road network for selected areas in the experiment does not contain any complex junctions like roundabouts or overpasses with ramps, which cannot be captured by a low-frequency track point stream. This is a major challenge for incremental map construction methods when the sample rate is not high enough.

The experiment also evaluated the quality of the constructed map from a geographic information perspective, with a point set based measure derived from a computing perspective as a reference. As a fundamental measure to evaluate the map digitizing quality, the proportion of the constructed map in the buffer of the benchmark seems to have problems when directly applied to the evaluation of maps constructed from traces. Completely false segments may influence the measure unexpectedly. On the other hand, the evaluation of the topology by matching extracted intersections to ground truth worked well in conveying an important aspect of the quality of constructed maps. It is simple and direct, as compared to those methods used in the computing perspective, such as path sampling and point sampling methods in a graph setting.

5. Conclusions

In this paper, an approach for high accuracy trace fusion and road map construction using low-frequency vehicle tracking data is proposed based on Delaunay triangulation and weighted skeleton. The method was validated and evaluated using taxi GPS data with a sampling interval of approximately 40 s in two areas of Wuhan. The results indicate that the proposed method improves the positional accuracy of existing incremental methods [16,17], and provides satisfying topological information. It was demonstrated to be useful for quality enhancement in the low-frequency situations when merging multiple observations of the same road segment, and handles the trace near the intersections in a feasible way.

There are still some problems which must be tackled to improve the usability of the proposed method. First, the geometry of complex junctions cannot be derived by the segmentation based on heading criterion and topology extraction, due to the limit of low sampling frequency. Future online algorithms might consider ways to identify and keep the track points in the junction area rather than dropping them, to infer the geometry of the junction. Second, the proposed method does not provide an accuracy warranty as several existing methods do [17]. The skeletonization procedures in the fusion process can be further analyzed to provide quality guarantees with assumptions on the accuracy of raw data. Third, the extraction of triangular network skeletons continuously increases the geometric complexity of the constructed map. Simplification algorithms for linear features, like the Douglas-Peuker algorithm, might be integrated to the proposed method before its real-world application, where the constructed map must be refined sufficiently rapidly to avoiding becoming overly complicated.