Map-matching for low-sampling-rate GPS trajectories

Patent metadata

Field	Value
Publication number	US-12320650-B2
Application number	US-202217659550-A
Country	US
Kind code	B2
Filing date	Apr 18, 2022
Priority date	Feb 25, 2010
Publication date	Jun 3, 2025
Grant date	Jun 3, 2025

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 method comprising:
receiving a geographical location trajectory dataset from a geographical location system of a computing device;
determining a first set of candidate projection points for a first sampling point of the geographical location system trajectory dataset, the first sampling point corresponding to a first location of the computing device at a first point in time;
determining a second set of candidate projection points for a second sampling point of the geographical location system trajectory dataset, the second sampling point corresponding to a second location of the computing device at a second point in time;
performing a spatial analysis on the first set of candidate projection points;
performing a temporal analysis on the first set of candidate projection points, wherein the temporal analysis is based on a speed between the first sampling point and the second sampling point;
based on results of the spatial analysis and the temporal analysis, determining a plurality of distinct path options between the first set of candidate projection points and the second set of candidate projection points;
determining a path between the first location and the second location based on the plurality of paths; and
causing the path between the first location and the second location to be provided to a user via an electronic device.

2. The method of claim 1 , further comprising:
selecting the first sampling point provided by the geographical location system.

3. The method of claim 1 , wherein the geographical location system is a global positioning system (GPS) and the first sampling point is provided as GPS coordinates.

4. The method of claim 1 , wherein determining the first set of candidate projection points for the first sampling point comprises accessing a road network database to determine a road segment for each candidate projection point in the first set of candidate projection points.

5. The method of claim 4 , wherein the spatial analysis uses geometric and topological information from the road network database to evaluate each candidate projection point in the first set of candidate projection points.

6. The method of claim 1 , wherein performing the spatial analysis comprises determining an observation probability that represents a likelihood that a route is an optimal path between the first location and the second location.

7. The method of claim 6 , wherein the observation probability is based on a distance between two candidate projection points.

8. The method of claim 6 , wherein performing the spatial analysis further comprises determining a transmission probability that represents a likelihood that a route is the shortest path between the first location and the second location.

9. The method of claim 8 , wherein the transmission probability is based on a distance between two neighboring candidate projection points.

10. The method of claim 8 , wherein a product of the observation probability and the transmission probability represents a likelihood that the computing device will move from a first candidate projection point in the two neighboring candidate projection points to a second candidate projection point in the two neighboring candidate projection points.

11. The method of claim 1 , wherein the temporal analysis is further based on speed constraints of road segments associated with each candidate projection point in the first set of candidate projection points.

12. The method of claim 1 , wherein determining the path between the first location and the second location comprises calculating a score for each candidate path in the plurality of distinct path options based on the spatial analysis and the temporal analysis.

13. The method of claim 12 , wherein a candidate path having the highest score of the plurality of distinct path options is selected as the path between the first location and the second location.

14. A system comprising:
a processor; and
memory coupled to the processor, the memory comprising computer executable instructions that, when executed by the processor, perform operations comprising:
receiving a geographical location trajectory dataset from a geographical location system of a computing device;
determining a first set of candidate projection points for a first sampling point of the geographical location system trajectory dataset, the first sampling point corresponding to a first location of the computing device at a first point in time;
determining a second set of candidate projection points for a second sampling point of the geographical location system trajectory dataset, the second sampling point corresponding to a second location of the computing device at a second point in time;
performing a spatial analysis on the first set of candidate projection points;
performing a temporal analysis on the first set of candidate projection points, wherein the temporal analysis is based on a speed between the first sampling point and the second sampling point;
based on results of the spatial analysis and the temporal analysis, determining a plurality of distinct path options between the first set of candidate projection points and the second set of candidate projection points;
determining a path between the first location and the second location based on the plurality of paths; and
causing the path between the first location and the second location to be provided to a user via an electronic device.

15. The system of claim 14 , further comprising constructing a candidate graph based on the results of the spatial analysis and the temporal analysis, the candidate graph including the plurality of distinct path options between the first set of candidate projection points and the second set of candidate projection points.

16. The system of claim 14 , wherein determining the path between the first location and the second location comprises evaluating the plurality of distinct path options of the candidate graph.

17. The system of claim 14 , wherein causing the path between the first location and the second location to be provided to the user comprises presenting the path between the first location and the second location on a graphical user interface.

18. The system of claim 14 , wherein causing the path between the first location and the second location to be provided to the user comprises presenting the path between the first location and the second location as speech via a digital assistant.

19. The system of claim 14 , wherein the path between the first location and the second location represents a shortest path.

20. A device comprising:
memory comprising computer executable instructions that, when executed, perform operations comprising:
receive a geographical location trajectory dataset from a geographical location system of a computing device;
determining a first set of candidate projection points for a first sampling point of the geographical location system trajectory dataset, the first sampling point corresponding to a first location of the computing device at a first point in time;
determining a second set of candidate projection points for a second sampling point of the geographical location system trajectory dataset, the second sampling point corresponding to a second location of the computing device at a second point in time;
performing a spatial analysis on the first set of candidate projection points;
performing a temporal analysis on the first set of candidate projection points, wherein the temporal analysis is based on a speed bet

Assignees

• Microsoft Technology Licensing Llc

Inventors

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

Classifications

• G01C21/30 Primary

  Map- or contour-matching · CPC title