Method and system for finding paths using GPS tracks

• US 9,086,288 B2
• Filed: 07/15/2011
• Issued: 07/21/2015
• Est. Priority Date: 07/15/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Raychev, Veselin, Hurand, Mathilde Claire
• Primary Examiner(s): Badii, Behrang
• Assistant Examiner(s): GREENE, DANIEL LAWSON
• Application Number:
  US13/184,457
• Publication Number:
  US 20150168161A1
• Time in Patent Office: 1,467 Days
• Field of Search: 701/200, 701/400, 701/450, 701/451, 701/452
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3837 Data obtained from a single source
• CPC Class Codes: G01C 21/3844 Data obtained from position sensors only, e.g. from inertial navigation
• CPC Class Codes: G01C 21/3859 Differential updating map data
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Systems, methods, and machine-readable media for refining mapping data are provided. One or more candidate routes may be identified based on input location coordinates of a mobile device. The one or more candidate routes may be compared to previously stored mapping data, and based on the comparison, a route score for each candidate route may be calculated. Based on the route score, a route most likely traveled by the mobile device based on the input location coordinates may be selected. The candidate route most likely traveled by the mobile device user may be analyzed to determine whether it contains a transition segment between one location coordinate and the next location coordinate in the input location coordinates that is not along a existing path known to the previously stored mapping data. The transition segment which is not part of the previously stored mapping data may be identified as a missing path of the previously stored mapping data.

Claims

1. A computer-implemented method for refining mapping data, the method comprising:

receiving, at a server, input location coordinates of a mobile device, wherein the server is configured to host a memory storing mapping data, the input location coordinates corresponding to a plurality of location coordinates associated with a sequence of locations along which the mobile device has previously traveled;

identifying one or more candidate routes based on the input location coordinates of the mobile device;

comparing the one or more candidate routes to known paths in mapping data previously stored in the memory hosted by the server;

using a processor at the server to;

calculate a route score for each candidate route based on the comparison,

select, based on the route score, a route that was most likely previously traveled by the mobile device based on the sequence of locations associated with the input location coordinates, and

identify a transition segment in the route that was most likely previously traveled by the mobile device as a missing path of the previously stored mapping data, wherein the transition segment links one location coordinate to a next location coordinate that is not along an existing path previously stored in the mapping data; and

adding the missing path to the mapping data stored in the memory hosted by the server.

2. The computer-implemented method of claim 1, further comprising removing the input location coordinates from consideration if the input location coordinates are associated with an accuracy measure below a threshold accuracy measure.

3. The computer-implemented method of claim 1, further comprising removing the input location coordinates from consideration if the input location coordinates contain a pair of sequential location coordinates that are more than a threshold distance apart.

4. The computer-implemented method of claim 1, further comprising removing the input location coordinates from consideration if the input location coordinates contain a pair of sequential location coordinates that are associated with timestamps that are more than a threshold amount of time apart.

5. The computer-implemented method of claim 1, further comprising:

calculating a speed for the input location coordinates of the mobile device;

identifying a desired track type associated with a predetermined range of speed; and

determining whether the speed for the input location coordinates is within the predetermined range for the desired track type;

wherein the comparing of the one or more candidate routes, the using of the processor to calculate the route score for each candidate route, to select the route that was most likely previously traveled, and to identify the transition segment, and the adding are performed if the speed for the input location coordinates is within the predetermined range for the desired track type.

6. The computer-implemented method of claim 1, further comprising:

identifying a desired track type; and

removing the input location coordinates from consideration if every location coordinate in the input location coordinates can be aligned with a path in the mapping data that is not associated with the desired track type.

7. The computer-implemented method of claim 1, wherein the route score is a confidence value and wherein the candidate route with the highest confidence value is selected to be the route that was most likely previously traveled by the mobile device.

8. The computer-implemented method of claim 1, wherein identifying one or more candidate routes comprises, for each candidate route:

aligning at least one location coordinate of the input location coordinates to a path in the mapping data; and

determining a transition segment between each pair of sequential location coordinates in the input location coordinates.

9. The computer-implemented of claim 8, wherein the calculating of the route score for each candidate route further comprises:

calculating an alignment value for each location coordinate; and

calculating a transition value for each pair of sequential location coordinates in the input location coordinates.

10. The computer-implemented of claim 9, wherein the alignment value for each location coordinate is based on the distance between the location coordinate and the point on the path in the mapping data the location coordinate is aligned to.

11. The computer-implemented method of claim 9, wherein the transition value for each pair of sequential location coordinates is based on whether the transition segment for the pair of sequential location coordinates is in the mapping data.

12. A system for refining mapping data, the system comprising:

an interface module at a server configured to receive, from a mobile device, a sequence of location signals of the mobile device associated with locations at which the mobile device has previously traveled;

a memory at the server configured to store mapping data;

a routing module configured to generate a plurality of candidate routes based on the sequence of location signals of the mobile device;

a scoring module configured to calculate a route score for each candidate route of the plurality of candidate routes; and

a map module configured to;

select, from the plurality of candidate routes, a route that was most likely previously traveled by the mobile device based on the route score for each candidate route,

identify a segment in the route that was most likely previously traveled by the mobile device as a possible missing path of the mapping data stored in the memory, wherein the segment links one location signal of the sequence of location signals to a next location signal that is not along an existing path previously stored in the mapping data, and

add the possible missing path to the mapping data stored in the memory at the server.

13. The system of claim 12, wherein generating a plurality of candidate routes comprises, for each candidate route, attempting to align each location signal of the sequence of location signals to a point on a path in the mapping data.

14. The system of claim 13, wherein the scoring module is further configured, for each candidate route, to:

calculate an alignment value for each location signal of the sequence of location signals based on the alignment of the location signal;

calculate a transition value for each pair of consecutive location signals in the sequence of location signals; and

wherein the route score for each candidate route is based on the alignment value for each location signal of the sequence of location signals and the transition value for each pair of consecutive location signals in the sequence of location signals.

15. The system of claim 12, further comprising:

a filtering module to remove the sequence of location signals from consideration if the sequence of location signals is not associated with a set of predetermined parameters.

16. The system of claim 12, wherein the map module is further configured to:

flag the possible missing path for further analysis; and

group the possible missing path with other possible missing paths that are located within a predetermined distance range.

17. A non-transitory machine-readable medium comprising instructions stored therein, which when executed by a machine, cause the machine to perform operations comprising:

receiving, from a mobile device, a sequence of location signals of the mobile device associated with locations at which the mobile device has previously traveled;

generating a plurality of candidate routes based on the sequence of location signals of the mobile device;

determining a route that was most likely previously traveled by the mobile device based on the sequence of location signals;

determining whether the route that was most likely previously traveled by the location device contains a transition segment that is not in mapping data hosted by a server, wherein the transition segment links one location signal of the sequence of location signals to a next location signal that is not along an existing path previously stored in the mapping data;

identifying the transition segment as a possible missing path if the transition segment is not in any known path in the mapping data hosted by the server; and

adding the possible missing path to the mapping data hosted by the server.

18. The machine-readable medium of claim 17, further comprising:

removing the sequence of location signals from consideration if the sequence of location signals is not associated with a set of predetermined parameters.

19. The machine-readable medium of claim 17, wherein determining the route that was most likely previously traveled by the mobile device further comprises:

calculating a route score for each candidate route; and

wherein identifying the route that was most likely previously traveled by the mobile device is based on the route scores of the plurality of candidate routes.

20. The machine-readable medium of claim 19, wherein the route score is a confidence value and wherein the route that most likely previously traveled by the mobile device is identified as the candidate route with a highest confidence value.