Map-Matching for Low-Sampling-Rate GPS Trajectories

• US 20110208426A1
• Filed: 02/25/2010
• Published: 08/25/2011
• Est. Priority Date: 02/25/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Chengyang, Lou, Yin, Xie, Xing, Zheng, Yu
• Granted Patent: US 10,288,433 B2
• Time in Patent Office: Days
• US Class Current: 701/208
• CPC Class Codes: G01C 21/30 Map- or contour-matching

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.

Claims

1. A computer-implemented method comprising:

implementing a processor to execute computer executable instructions stored on a computer-readable medium to perform operations comprising;

receiving a global positioning system (GPS) trajectory comprising a plurality of sampling points;

determining a set of one or more candidate projection points for each sampling point of the plurality of sampling points;

performing a spatial analysis and a temporal analysis on the retrieved sets of one or more candidate points;

constructing a candidate graph based upon the results of the spatial analysis and the temporal analysis; and

evaluating the candidate graph to determine a best-match trajectory that corresponds to the plurality of sampling points.

2. The method of claim 1, wherein performing the spatial analysis comprises:

determining an observation probability; and

determining a transmission probability.

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

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 the 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 best-match trajectory on a display.

6. The method of claim 1, wherein the determining is performed by a built-in grid-based spatial index method.

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

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 along a user-travelled trajectory;

determine a best-match trajectory corresponding to the plurality of sampling points based upon a spatial-temporal analysis; and

present the best-match trajectory.

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 method 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 the 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 candidate projection points

16. The one or more computing devices of claim 15, wherein the spatial-temporal analysis employs a road network database comprising geometric information and topological information to evaluate the plurality of candidate projection points.

17. One or more computer-readable media storing computer-executable instructions that, when executed on one or more processors, perform operations comprising:

performing a spatial-temporal analysis on a plurality of candidate projection points, the plurality of candidate projection points correspond to a plurality of sampling points collected along a user-travelled trajectory;

constructing a candidate graph based upon the plurality of candidate projection points;

evaluating the candidate graph to determine a best-match trajectory; and

presenting the best-match trajectory.

18. The one or more computer-readable media of claim 17, wherein the plurality of sampling points are gathered during a pre-defined low-frequency sampling interval.

19. The one or more computer-readable media of claim 17, wherein the candidate graph comprises one or more partial candidate graphs.

20. The one or more computer-readable media of claim 17, wherein the best-match trajectory is determined based on a score calculated for each candidate sequence path on the candidate graph.