Database Reference
In-Depth Information
P
i
+1
c
1
P
i
c
3
P
i
:
trajectory point
c
j
:
road segment/edge
P
i
-2
P
i
-1
c
2
Figure 2.2 Applying map matching.
between a trajectory and a sequence of arcs on a map. The route with the smallest
distance from the initial trajectory is taken as the map-matched trajectory. For
instance, Figure
2.2
illustrates such a methodology: for every point
P
i
,given
that point
P
i
−
1
has already been matched to an edge, the adjacent edges to this
edge are the candidate edges to be matched to
P
i
and they are evaluated as
illustrated in Figure
2.2
. In this example,
P
i
−
1
is matched to edge
c
3
, hence
c
1
,
c
2
,and
c
3
are the candidate edges for point
P
i
. Two measures are used for
choosing among the candidate edges that are based on similarity and orientation
criteria. The higher the sum
s
of these measures is, the better the match to this
edge is. If the projection of the current point on the candidate edges does not lie
between the end points of any of these edges, the algorithm does not proceed
to the next point. Instead, the nearest edge of the candidates is set as part of the
trajectory and then the next set of candidate edges is evaluated. On the contrary to
geometric approaches, the topological approaches account for the connectivity
and contiguity of the road network without assuming any knowledge of the
expected traveling route and the speed or heading information supplied by the
GPS.
More recent map-matching methods deal with the problematic case where
GPS data are arriving with low sampling rate (e.g., one point every two minutes)
and high noise. These new methods employ both distance and topology and
aim to align an entire trajectory with the road network. In some cases, not only
distance and topology are used but also hidden Markov model approaches to
find the most likely road route corresponding to a sequence of positions.
The various proposals usually include several postprocessing techniques
to calibrate and correct the initial matching results. Obviously this worsens
the cost/efficiency of the algorithm. This is an important issue that should be
addressed by future research.
2.3.3 Data Compression
Trajectory data in applications grow progressively and intensively as the tracking
time goes by. Such huge amounts of data raise storage, transmission, computa-
tion, and display challenges. Therefore, trajectory data compression is an essen-
tial task of trajectory reconstruction. The research in this area usually assumes
that the objectives of trajectory compression are: (1) to reduce the size of the
