Registration of location data to street maps using hidden markov models, and application thereof

• US 8,209,121 B1
• Filed: 10/10/2007
• Issued: 06/26/2012
• Est. Priority Date: 10/10/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ogale, Abhijit
• Primary Examiner(s): Algahaim, Helal A
• Application Number:
  US11/870,265
• Time in Patent Office: 1,721 Days
• Field of Search: 701/200, 701/207, 701/208, 701/213, 701/214
• US Class Current: 701/495
• CPC Class Codes: G01C 21/30 Map- or contour-matching

Abstract

The present invention provides systems and methods for improving the accuracy of location data, such as GPS data. In an embodiment, the present invention adjusts coordinates by receiving a sequence of coordinates corresponding to a plurality of locations; identifying in a map database, for each location, polyline features within a distance from the coordinates for the location; calculating emission probabilities for the polyline features; calculating transition probabilities for the polyline feature; and adjusting the coordinates for the plurality of locations so that the adjusted coordinates correspond to polyline features belonging to a sequence of polyline features selected, based on the emission probabilities and the transition probabilities, to be the most likely sequence of polyline features that correspond to the sequence of coordinates. Besides improving accuracy, embodiments of this invention enable novel geospatial applications and user interfaces by adding a large amount of meta-information to a location.

Claims

1. A method for adjusting coordinates obtained using a satellite-based positioning system device, comprising:

(1) receiving a sequence of coordinates corresponding to a plurality of locations;

(2) identifying in a map database, for each location, polyline features within a first distance from the coordinates for the location;

(3) calculating emission probabilities for the polyline features identified in (2), wherein each emission probability E_ij represents the probability of obtaining coordinates C_i for a location represented by a polyline feature P_j;

(4) calculating transition probabilities for the polyline feature identified in (2), wherein each transition probability T_xy represents the probability of a transition from a polyline feature P_x to a polyline feature P_y; and

(5) adjusting the sequence of coordinates corresponding to the plurality of locations so that the adjusted coordinates correspond to polyline features belonging to a sequence of polyline features selected based on the emission probabilities calculated in (3) and the transition probabilities calculated in (4),

wherein steps (1)-(5) are performed by at least one computing device.

2. The method of claim 1, farther comprising:

(6) adjusting the sequence of coordinates corresponding to the plurality of locations using information from sensors other than the satellite-based positioning system device.

3. The method of claim 1, wherein (2) comprises selecting the first distance based on an accuracy associated with the sequence of coordinates corresponding to the plurality of locations.

4. The method of claim 1, wherein (3) comprises calculating emission probabilities for the polyline features identified in (2) based on an error associated with the satellite-based positioning system device.

5. The method of claim 1, wherein (5) further comprises:

(a) modeling the sequence of polyline features as a Hidden Markov Model; and

(b) decoding the adjusted coordinates using Viterbi decoding.

6. The method of claim 1, wherein (1) through (5) are performed by the satellite-based positioning system device while the device is carried in a vehicle.

7. A method for adjusting location data, comprising:

(1) identifying in a map database, for a plurality of locations, polyline features within a first distance from each location;

(2) calculating emission probabilities for the polyline features identified in (1), wherein each emission probability E_ij represents the probability of obtaining location C_i for a location on the map represented by a polyline feature P_j;

(3) calculating transition probabilities for the polyline feature identified in (1), wherein each transition probability T_xy represents the probability of a transition from a polyline feature P_x to a polyline feature P_y; and

(4) adjusting the plurality of locations so that the adjusted locations correspond to polyline features belonging to a sequence of polyline features selected based on the emission probabilities calculated in (2) and the transition probabilities calculated in (3),

wherein steps (1)-(4) are performed by at least one computing device.

8. The method of claim 7, wherein the plurality of locations have associated heading values, and (4) comprises adjusting the associated heading values.

9. The method of claim 7, wherein (2) comprises calculating emission probabilities based on a Gaussian probability function.

10. The method of claim 9, wherein (2) comprises using adaptive optimization to select parameters for the Gaussian probability function.

11. The method of claim 7, wherein (3) comprises calculating transition probabilities using at least one of turn restriction information, intersection information, and one-way street information stored in the map database.

12. The method of claim 7, wherein (5) comprises modeling the sequence of polyline features as a Hidden Markov Model.

13. The method of claim 7, further comprising:

(5) adjusting the plurality of locations with particle filtering.

14. The method of claim 7, further comprising:

(5) adjusting the plurality of locations with Kalman filtering.

15. The method of claim 7, wherein (5) comprises modeling the sequence of polyline features as a probabilistic context free grammar.

16. A system for adjusting location data, comprising:

a spatial indexer that receives a sequence of location data corresponding to a plurality of locations and identifies in a map database, for each location, polyline features within a first distance from the coordinates for the location;

an emission probability calculator that calculates emission probabilities for the polyline features identified by the spatial indexer, wherein each emission probability E_ij represents the probability of obtaining location C_i for a location on the map represented by a polyline feature P_j;

a transition probability calculator that calculates transition probabilities for the polyline feature identified by the spatial indexer, wherein each transition probability T_xy represents the probability of a transition from a polyline feature P_x to a polyline feature P_y; and

a pose optimizer that adjusts the location data for the plurality of locations so that the adjusted location data correspond to polyline features belonging to a sequence polyline features selected based on the calculate emission probabilities and the calculated transition probabilities.

17. The system of claim 16, wherein the location data includes heading values.

18. The system of claim 16, wherein the emission probability calculator calculates the emission probabilities using a Gaussian probability function.

19. The system of claim 16, wherein the transition probability calculator calculates transition probabilities using at least one of turn restriction information, intersection information, and one-way street information stored in the map database.

20. The system of claim wherein the pose optimizer includes a Viterbi decoder.