Automatic Extraction of
Road Networks from GPS Traces
Jia Qiu and Ruisheng Wang
Abstract
We propose a point segmentation and grouping method to
generate road maps from GPS traces. First, we present a pro-
gressive point cloud segmentation algorithm based on Total
Least Squares (
TLS
) line fitting. Second, we group topologically
connected point clusters by the point’s orientation and cluster’s
spatial proximity, where the topological relationship is generat-
ed using Hidden Markov Model (
HMM
) map matching. Finally,
we refine the intersections of roads so that their geometrical
and topological relationships are consistent with each other.
Experimental results show that our algorithm is robust to noises
and the generated road network has a high accuracy in terms of
geometry and topology. Compare to the representative algo-
rithms; the results of our new algorithm have a higher F-mea-
sure score for different matching thresholds.
Introduction
A road network is one of the most fundamental data of geo-
spatial information. It is, however, challenging to promptly
and consistently update the existing road maps (Wang
et al
.,
2013). Conventional map updating techniques mainly consist
of ground-based and aerial surveys (Guo
et al
., 2007). Ground-
based surveys are expensive and labor intensive. They are
limited to a long cycle of information acquisition. The aerial
surveys have the capability to obtain large-scale data about
the Earth’s surface in a short time. Though several algorithms
have been proposed to extract road network from high-resolu-
tion satellite imagery (Doucette
et al
., 2004, Youn
et al
., 2008,
Kasemsuppakorn
et al
., 2013), it is still difficult to generate
large-scale road networks with these algorithms, due to the
complexity of road networks and the occlusions in satellite
images caused by trees and buildings.
To overcome the shortcomings of traditional road map
mapping, nowadays, user generated content (
UGC
) (Krumm
et
al
., 2008) is being increasingly used in road map generation.
The
UGC
is achieved in two ways: (1) collaborative mapping
programs, such as OpenStreetMap, which are highly depen-
dent on manual work; and (2) automatic road generation from
Global Positioning System (
GPS
) trajectories (Li
et al
., 2014),
which is referred to as map inference. Being an efficient
method for road network updates, map inference focus on the
extraction of road’s geometric positions, topological con-
nections as well as some attribute information such as lane
counts (Schrödl
et al
., 2004) and road names (Li
et al
., 2014).
The
GPS
traces are collected by
GPS
-equipped vehicles, bicy-
cles or pedestrians and therefore, better captures the geometry
and topology of the latest road networks. Most of the existing
map inference methods are designed to deal with low-noise,
densely sampled, and uniformly distributed
GPS
traces (Guo
et al
., 2007, Wang
et al
., 2013). In this research, we propose a
novel algorithm to infer high-quality road maps from low-cost
and high-noise
GPS
traces. The primary contributions of our
method are summarized in the following:
A robust progressive 2D point cloud segmentation algorithm
using multi-density thresholds to separate
GPS
points that visit
different roads.
A topological relationship construction algorithm based on Hid-
den Markov Model (
HMM
) based map matching.
• An
α
–quantile distance to measure spatial proximity
between two point clusters for grouping.
The remainder of the paper is organized as follows: the
next Section presents a review of the related work, fol-
lowed by an outline of the procedure of our map inference
algorithm. Next, experiments of two
GPS
trace datasets are
presented, followed by conculsions and possible future work
on this topic.
Related Work
Several approaches have been proposed to automatically infer
road maps from
GPS
traces. These approaches mainly include:
clustering based methods, trace merging based methods, Ker-
nel Density Estimation (
KDE
) based methods, and intersection
linking based methods (Biagioni and Eriksson, 2012a, Ahmed
et al
. 2014).
The clustering-based approaches begin with the determi-
nation of a series of cluster seeds by location, bearing, and
heading of the traces. Seeds are then linked to form the road
segments according to the raw traces. Edelkamp and Schrödl
(2003) introduced an approach to infer road maps with high
geometric accuracy, containing detailed lane information from
fine-grained
GPS
traces. Based on this work, Schrödl
et al
.
(2004) described a process to refine the intersections accord-
ing to transition relationships between traces and segments.
Agamennoni
et al
. (2010, 2011) regarded road map inference
as finding the principal curve of the road segment by deter-
mining and linking the cluster seeds. Their method, however,
is not robust to noises (Biagioni and Eriksson, 2012b) and
requires densely sampled
GPS
traces.
Trace merging-based approaches involve the consolida-
tion of trace segments based on their geometric relations and
shape similarity. The centerlines of roads are then generated
by the merged traces. Cao and Krumm (2009) proposed an ag-
gregation technique to pull together traces that visit the same
road. Even though their method performs well on densely
sampled
GPS
traces, it is found to be non-robust towards
noisy data. Based on the research of Cao and Krumm (2009),
Wang
et al
. (2014) presented a novel approach for generating
routable road maps from
GPS
traces. They introduced circular
boundaries to isolate points near intersections and used a
k-means clustering method to refine the intersections.
Department of Geomatics Engineering, University of Calgary,
2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4
(
)
Photogrammetric Engineering & Remote Sensing
Vol. 82, No. 8, August 2016, pp. 593–604.
0099-1112/16/593–604
© 2016 American Society for Photogrammetry
and Remote Sensing
doi: 10.14358/PERS.82.8.593
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
August 2016
593
