- Forward


Map Matching
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

The Map-Matching Problem
Back SMYC Forward
  • The Situation:
    • A person/vehicle is moving along a finite set of streets \(\overline{\mathcal{N}}\)
    • We are provided with an estimate of this person's location at a finite number of points in time denoted \(\{0, 1, ..., T \}\)
    • The person's actual location at time \(t\) is denoted by \(\overline{P}^{t}\) and the estimate is denoted by \(P^{t}\)
  • The Problem:
    • Find the street in \(\overline{\mathcal{N}}\) that contains \(\overline{P}^{t}\)
The Map-Matching Problem (cont.)
Back SMYC Forward
  • A Complication:
    • We do not know the street system, \(\overline{\mathcal{N}}\) exactly
    • We have a network (or graph) representation \(\mathcal{N}\) and a set of piecewise linear curves (one curve associated with each arc/link)
  • The Actual Problem(s):
    • Match the estimated location \(P^{t}\) with a curve, \(A\) in the "map"
    • Then determine the street \(\overline{\mathcal{A}} \in \overline{\mathcal{N}}\) that corresponds to the actual location \(\overline{P}^{t}\)
    • A secondary concern is to determine the position on the curve \(A\) that best corresponds to \(\overline{P}^{t}\)
The Map-Matching Problem (cont.)
Back SMYC Forward
images/probstmt1.gif images/probstmt2.gif
Point-to-Point Matching
Back SMYC Forward
  • The Idea:
    • Match Pt to the "closest" breakpoint in the piecewise linear curve
  • A Difficulty:
    • images/noshape.gif
Point-to-Curve Matching
Back SMYC Forward
  • The Idea:
    • Identify the arc that is closest to \(P^{t}\)
  • One Approach:
    • images/pt2seg.gif
Point-to-Curve Matching (cont.)
Back SMYC Forward
  • One Difficulty:
    • images/corner.gif
Point-to-Curve Matching (cont.)
Back SMYC Forward
  • Another Difficulty:
    • images/parallel.gif
Curve-to-Curve Matching
Back SMYC Forward
  • The Idea:
    • Find the arc that is closest to the piecewise linear curve, \(P\) defined by the points \(P^{0}, P^{1}, ..., P^{m}\)
  • A Difficulty:
    • images/outlier.gif
Curve-to-Curve Matching (cont.)
Back SMYC Forward
  • Another Approach:
    • Use the "total" distance
  • A Difficulty:
    • images/param.gif
Curve-to-Curve Matching (cont.)
Back SMYC Forward
  • Another Approach:
    • "Correct" for differences in length
  • A Difficulty:
    • images/grid.gif
Using Topological Information
Back SMYC Forward
Getting Started
images/examp01.gif
Using Topology (cont.)
Back SMYC Forward
Using Connectivity/Topology
images/examp03.gif
There's Always More to Learn
Back -