Hidden Markov Map Matching Through Noise and Sparseness
- Paul Newson ,
- John Krumm
17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2009), November 4-6, Seattle, WA |
The problem of matching measured latitude/longitude points to roads is becoming increasingly important. This paper describes a novel, principled map matching algorithm that uses a Hidden Markov Model (HMM) to find the most likely road route represented by a time-stamped sequence of latitude/longitude pairs. The HMM elegantly accounts for measurement noise and the layout of the road network. We test our algorithm on ground truth data collected from a GPS receiver in a vehicle. Our test shows how the algorithm breaks down as the sampling rate of the GPS is reduced. We also test the effect of increasing amounts of additional measurement noise in order to assess how well our algorithm could deal with the inaccuracies of other location measurement systems, such as those based on WiFi and cell tower multilateration. We provide our GPS data and road network representation as a standard test set for other researchers to use in their map matching work.
This map shows our test GPS data taken on a drive in Seattle, WA, USA and its eastern suburbs. The trip starts in the upper right corner near Marymoor Park. The data was sampled at 1 Hz using a RoyalTek RBT-2300 GPS logger. The drive took place on Saturday, January 17, 2009 starting at 20:27:37 UTC (12:27:37 local time) and ending at 22:34:28 UTC (14:34:28 local time), for an elapsed time of 02:06:51. A much higher resolution map is available here.
Test trip GPS data
Example format:
| Date (UTC) | Time (UTC, hh:mm:ss) | Latitude (degrees) | Longitude (degrees) |
| 17-Jan-2009 | 20:27:37 | 47.66748333 | -122.1070833 |
| 17-Jan-2009 | 20:27:38 | 47.66750000 | -122.1070667 |
Road network data (40 km radius around greater Seattle, WA, USA area)
Example format:
| Edge ID | From Node ID | To Node ID | Two Way | Speed (m/s) | Vertex Count | LINESTRING(latitude1 longitude1, latitude2 longitude2, …) |
| 883991900000 | 883991900000 | 883991900001 | 1 | 22.22222222 | 10 | LINESTRING(-122.732318937778 47.8899192810059, -122.732139229774 47.8903403878212, -122.731820046902 47.8910404443741, -122.731310427189 47.8921294212341, -122.730749845505 47.8933900594711, -122.730208039284 47.894441485405, -122.729588449001 47.8957316279411, -122.729159295559 47.8968098759651, -122.727560698986 47.9000902175903, -122.72741317749 47.900390625) |
| 883991900001 | 883991900002 | 883991900003 | 1 | 11.1111111111111 | 4 | LINESTRING(-122.71107852459 47.8776508569717, -122.712398171425 47.8788793087006, -122.71447956562 47.8810706734657, -122.715329825878 47.8818699717522) |
Note that it is always permissible to travel from the “From Node” to the “To Node” on an edge. If “Two Way” is 1, then it is also permissible to travel the opposite direction.
Ground truth path (Edge ID in order encountered on test trip)
Example format:
| Edge ID | Traversed From to To |
| 884147800801 | 1 |
| 884147800802 | 1 |
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage, and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. ACM GIS '09 , November 4-6, 2009. Seattle, WA, USA © 2009 ACM ISBN 978-1-60558-649- 6/09/11...$10.00.