Map-matching for low-sampling-rate GPS trajectories

Patent metadata

Field	Value
Publication number	US-10288433-B2
Application number	US-71285710-A
Country	US
Kind code	B2
Filing date	Feb 25, 2010
Priority date	Feb 25, 2010
Publication date	May 14, 2019
Grant date	May 14, 2019

Abstract

This disclosure describes a map-matching module that supports a Global Positioning System (GPS) and provides a user with a best match trajectory corresponding to GPS sampling points taken at a low sampling rate. The best match trajectory is based upon a spatial-temporal analysis.

First claim

What is claimed is:

1. A computer-implemented method comprising:
collecting, from a global positioning system (GPS) of a computing device, GPS location data comprising a plurality of sampling points each corresponding to a location of the computing device;
receiving a GPS trajectory comprising the plurality of sampling points;
determining a first set of candidate projection points for a first sampling point of the plurality of sampling points corresponding to a first location of the computing device based on a first geometric shape that encompasses the first sampling point;
determining a second set of candidate projection points for a second sampling point of the plurality of sampling points corresponding to a second location of the computing device based on a second geometric shape that encompasses the second sampling point, wherein at least one of the first set of candidate projection points or the second set of candidate projection points comprises two or more candidate projection points;
performing a spatial analysis and a temporal analysis on the first set of candidate projection points, wherein the temporal analysis for a first pair of candidate projection points with one candidate projection point from the first set and one candidate projection point from the second set is based upon an average speed determined between the first sampling point of the plurality of sampling points corresponding to the first location of the computing device and the second sampling point of the plurality of sampling points corresponding to the second location of the computing device, and a speed constraint value of a road segment associated with one of the candidate projection points of the first pair of candidate projection points;
constructing a candidate graph based upon results of the spatial analysis and the temporal analysis, the candidate graph including more than one path between the candidate projection points of the first set and the candidate projection points of the second set;
evaluating the paths of the candidate graph to determine a preferred path between the candidate projection points of the first set and the candidate projection points of the second set; and
causing the preferred path between the candidate projection points of the first set and the candidate projection points of the second set to be presented at a graphical user interface.

2. The method of claim 1 , wherein performing the spatial analysis comprises:
determining an observation probability for at least candidate projection points for two neighboring sampling points;
determining a transmission probability for the candidate points for the neighboring sampling points; and
multiplying the observation probability by the transmission probability to produce a likelihood that the computing device will move from a candidate projection point associated with the first of the neighboring sampling points to a candidate projection point associated with the second of the neighboring sampling points.

3. The method of claim 2 , wherein the observation probability is calculated according to a distance between the first sampling point and the candidate projection points in the first set.

4. The method of claim 2 , wherein the transmission probability is calculated according to a plurality of candidate projection points and the corresponding plurality of sampling points, such that a distance between the plurality of sampling points follows the shortest path from a first candidate projection point to a second candidate projection point.

5. The method of claim 1 further comprising presenting the preferred path on a display associated with the computing device.

6. The method of claim 1 , wherein the determining of the first set of candidate projection points and the determining of the second set of candidate projection points are performed by a built-in grid-based spatial index method.

7. The method of claim 1 , wherein the evaluating the paths of the candidate graph is based upon an overall score for a candidate sequence path, wherein the overall score indicates a probability that the candidate sequence path is the preferred path.

8. The method of claim 1 , wherein the plurality of sampling points comprises data gathered by a GPS based upon a pre-determined, low-frequency sampling interval.

9. The method of claim 8 , wherein the low-frequency sampling interval comprises every 2 minutes, every 3 minutes, every 4 minutes, every 5 minutes, or a time period greater than every 5 minutes.

10. One or more computing devices, comprising:
one or more processors;
a memory coupled to the one or more processors; and
a map-matching module stored in the memory and executed on the processor to:
receive a plurality of sampling points collected from a global positioning system of a computing device along a computing device-travelled trajectory, each of the plurality of sampling points corresponding to a location of the computing device;
determine a first set of candidate projection points for a first sampling point of the plurality of sampling points corresponding to a first location of the computing device based on a predefined a first geometric shape that encompasses the first sampling point;
determine a second set of candidate projection points for a second sampling point of the plurality of sampling points corresponding to a second location of the computing device based on a second geometric shape that encompasses the second one of the sampling points, wherein at least one of the first set of candidate projection points or the second sets of candidate projection points comprises two or more candidate projection points;
determine a trajectory corresponding to the first sampling point and second sampling point based upon a spatial-temporal analysis and at least the first set of candidate projection points and second set of candidate projection points, wherein the spatial-temporal analysis for a first pair of candidate projection points with one candidate projection point from the first set and one candidate projection point from the second set is based at least upon an average speed determined between the first sampling point of the plurality of sampling points corresponding to the first location of the computing device and the second sampling point of the plurality of sampling points corresponding to the second location of the computing device, and a speed constraint value of a road segment associated with the candidate projection points of the first pair of candidate projection points; and
cause the trajectory corresponding to the first sampling point and second sampling point to be displayed at a graphical user interface.

11. The one or more computing devices of claim 10 , wherein the sampling points are collected at a pre-determined, low-frequency sampling interval.

12. The one or more computing devices of claim 11 , wherein the low-frequency sampling interval comprises every 2 minutes, every 3 minutes, every 4 minutes, every 5 minutes, or a time period greater than every 5 minutes.

13. The one or more computing devices of claim 10 , wherein a candidate path sequence is a result of the spatial-temporal analysis and is the best match trajectory corresponding to the one or more sampling points.

14. The one or more computing devices of claim 12 , wherein the pre-determined sampling interval is defined by a user.

15. The one or more computing devices of claim 10 , wherein the best match trajectory is further based upon a candidate set comprising a plurality of the candidate projection points.

16. The one or more computing devices of claim 15 , wherein th

Assignees

• Zheng Yu
• Lou Yin
• Zhang Chengyang
• Xie Xing
• Microsoft Technology Licensing Llc

Inventors

• Zheng Yu
• Lou Yin
• Zhang Chengyang
• Xie Xing

Classifications

• G01C21/30 Primary

  Map- or contour-matching · CPC title