Map-matching for low-sampling-rate GPS trajectories
First Claim
Patent Images
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 Assignments
0 Petitions
Accused Products
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.
274 Citations
20 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12, 13, 14, 15, 16)
-
-
17. One or more computer-readable devices storing computer-executable instructions that, when executed on one or more processors, perform operations comprising:
-
collecting, from a global positioning system of a computing device, GPS location data comprising a plurality of sampling points each corresponding to a location of the computing device; performing a spatial-temporal analysis on a plurality of candidate projection points, the plurality of candidate projection points corresponding to the plurality of sampling points collected along a computing device-travelled trajectory, wherein a first pair of the candidate projection points are selected based on a geometric shape that encompasses an associated one of the plurality of sampling points, wherein the spatial-temporal analysis is based upon an average speed determined between at least two consecutive sampling points of the plurality of sampling points corresponding to at least two consecutive locations 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 the candidate projection points; constructing a candidate graph having a plurality of candidate sequence paths based upon the plurality of candidate projection points; evaluating the candidate graph to determine a trajectory based on the plurality of candidate sequence paths; and causing the trajectory to be displayed at a graphical user interface. - View Dependent Claims (18, 19, 20)
-
Specification