Snapping GPS tracks to road segments

• US 8,718,932 B1
• Filed: 08/31/2011
• Issued: 05/06/2014
• Est. Priority Date: 06/01/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ogale, Abhijit S., Pack, Jeremy B., Carceroni, Rodrigo L.
• Primary Examiner(s): Cheung, Mary
• Assistant Examiner(s): BRUSHABER, FREDERICK M
• Application Number:
  US13/223,203
• Time in Patent Office: 979 Days
• Field of Search: 701/200, 701/447, 701/446
• US Class Current: 701/447
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01C 21/30 Map- or contour-matching

Abstract

Methods and systems for snapping positions from location aware devices to road segments are provided. Data from the location aware device is received, which includes data about the location and direction of the location aware device. Each of the positions of the location aware device is snapped to a position on a road segment based on various factors, including the log likelihoods of snapping all of the previous positions of the location aware device to other possible positions on road segments, the comparison of direction of the location aware device and the direction of the road segment, and the distance between the location of the location aware device and the location of the road segment. Multiple threads can be generated to determine the most likely path for the location aware device. A most likely path of positions on road segments is determined for the location aware device and stored.

Claims

1. A method for snapping a position on a location track to a position on a road segment, the method comprising:

accessing a location track comprising the plurality of geographic positions, each geographic position including a latitude and a longitude, and obtained from a location aware device;

for each of the plurality of geographic positions on the location track, determining a likelihood that a geographic position is snapped to a position on a road segment using the likelihoods of snapping all previous geographic positions on the location track to all possible positions on the road segments, wherein the road segment comprises a plurality of positions having a latitude and a longitude;

determining a most likely snapped position for the last geographic position on the location track received from the location aware device using the likelihoods of snapping all previous geographic positions on the location track to all possible positions on the road segments;

determining a most likely path of snapped positions on the road segments for all of the geographic positions using the most likely snapped position for the last geographic position on the location track;

snapping the plurality of geographic positions on the location track to the most likely path of snapped positions on the road segments; and

storing the most likely snapped positions on the road segments for each of the plurality of geographic positions on the location track.

2. The method of claim 1, wherein determining the likelihood that a geographic position is snapped to a position on a road segment comprises comparing a heading of the geographic position and a heading of the position on the road segment.

3. The method of claim 1, wherein determining the likelihood that a geographic position is snapped to a position on a road segment comprises determining a likelihood of a change in position from a possible previous snapped position to a possible subsequent snapped position.

4. The method of claim 1, further comprising generating multiple threads in parallel on the location track for determining the likelihoods that a plurality of geographic positions are snapped to positions on road segments.

5. The method of claim 4, further comprising determining a most likely path of positions on road segments for all of the geographic positions by combining the calculations of multiple threads on the location track.

6. The method of claim 1, further comprising snapping each of the plurality of geographic positions to the center of the width of the road segment.

7. The method of claim 1, further comprising adjusting the snapping of each of the plurality of geographic positions to the road segment based on the width of the road segment.

8. The method of claim 1, further comprising associating sensor data obtained at the geographic position to the most likely snapped position on the road segment.

9. A non-transitory computer-readable storage medium storing executable computer program instructions for snapping a position on a location track to a position on a road segment, the computer program instructions comprising instructions for:

accessing a location track comprising the plurality of geographic positions, each geographic position including a latitude and a longitude, and obtained from a location aware device;

for each of the plurality of geographic positions on the location track, determining a likelihood that a geographic position is snapped to a position on a road segment using the likelihoods of snapping all previous geographic positions on the location track to all possible positions on the road segments, wherein the road segment comprises a plurality of positions having a latitude, a longitude;

determining a most likely snapped position for the last geographic position on the location track received from the location aware device using the likelihoods of snapping all previous geographic positions on the location track to all possible positions on the road segments;

determining a most likely path of snapped positions on the road segments for all of the geographic positions using the most likely snapped position for the last geographic position on the location track;

snapping the plurality of geographic positions on the location track to the most likely path of snapped positions on the road segments; and

storing the most likely snapped positions on the road segments for each of the plurality of geographic positions on the location track.

10. The computer-readable storage medium of claim 9, wherein determining the likelihood that a geographic position is snapped to a position on a road segment comprises comparing the heading of the geographic position and the heading of the position on the road segment.

11. The computer-readable storage medium of claim 9, wherein determining the likelihood that a geographic position is snapped to a position on a road segment comprises determining a likelihood of a change in position from a possible previous snapped position to a possible subsequent snapped position.

12. The computer-readable storage medium of claim 9, further comprising generating multiple threads in parallel on the location track for determining the likelihoods that a plurality of geographic positions are snapped to positions on road segments.

13. The computer-readable storage medium of claim 9, further comprising determining a most likely path of positions on road segments for all of the geographic positions by combining the calculations of multiple threads on the location track.

14. The computer-readable storage medium of claim 9, further comprising snapping each of the plurality of geographic positions to the center of the width of the road segment.

15. The computer-readable storage medium of claim 9, further comprising adjusting the snapping of each of the plurality of geographic positions to the road segment based on the width of the road segment.

16. The computer-readable storage medium of claim 9, further comprising associating sensor data obtained at the geographic position to the most likely snapped position on the road segment.

17. A method for snapping a position on a location track to a position on a road segment, the method comprising:

accessing a location track comprising the plurality of geographic positions, each geographic position including a latitude and a longitude, and obtained from a location aware device;

for one or more geographic positions on the location track, generating one or more worker threads, wherein the one or more worker threads perform steps comprising;

determining a likelihood that the geographic position is snapped to a position on a road segment using the likelihoods of snapping a plurality of previous geographic positions on the location track to a plurality of possible positions on the road segment, wherein the road segment comprises a plurality of positions having a latitude and a longitude;

determining a plurality of possible snapped positions on the road segment for the geographic position;

generating a main thread on the location track, wherein the main thread performs steps comprising;

determining transitions between the plurality of possible snapped positions generated by the one or more worker threads;

determining a most likely snapped position for the last geographic position on the location track received from the location aware device using the likelihoods of snapping the plurality of previous geographic positions on the location track to the plurality of possible positions on the road segments;

determining a most likely path of snapped positions on the road segments for all of the geographic positions using the most likely snapped position for the last geographic position on the location track;

snapping the plurality of geographic positions on the location track to the most likely path of snapped positions on the road segments; and

storing the most likely snapped positions on the road segments for each of the plurality of geographic positions on the location track.