Probalistic reverse geocoding

• US 8,838,379 B2
• Filed: 03/08/2013
• Issued: 09/16/2014
• Est. Priority Date: 10/06/2008
• Status: Expired due to Fees

• Current Assignee: TeleCommunication Systems Inc (Comtech Telecommunications Corporation)
• Original Assignee: TeleCommunication Systems Inc (Comtech Telecommunications Corporation)
• Inventors: Barcklay, Bob, Hahn, John, Tsurutome, Kevin
• Primary Examiner(s): Jayne, Darnell
• Assistant Examiner(s): Krycinski, Stanton L
• Application Number:
  US13/790,197
• Publication Number:
  US 20130184986A1
• Time in Patent Office: 557 Days
• Field of Search: 701/411, 701/412, 701/416, 701/417, 701/414, 701/491
• US Class Current: 701/416
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents

Abstract

The accuracy of a reverse geocode for a GPS fix in a mobile phone navigation device is improved significantly by considering together the user'"'"'s last known location on an original route, the elapsed time between the last known location on the original route and the latest GPS fix, and the likelihood that the user could have travelled from the last known location on the original route to one of numerous candidate locations (generated from the reverse geocode) in the elapsed time. The navigation server relies only on a GPS fix, timestamps, and a back-end routing database to provide improved or superior accuracy of reverse geocoding a GPS fix (selection of a point on a road) when a relevant user has deviated from the intended route. The reverse geocoding allows for accurate and functional re-routing capabilities.

Claims

1. A method of providing an accurate location to a user'"'"'s wireless navigation device, comprising:

receiving a route request from a user'"'"'s wireless navigation device;

obtaining a last known on-route location of said navigation device;

obtaining a latest location fix of said navigation device;

performing a reverse geocode on said latest location fix to determine a plurality of candidate locations within a given error radius of said latest location fix associated with said navigation device;

determining an estimated time of travel between each of said plurality of candidate locations and said last known on-route location; and

returning a most likely candidate location, from said plurality of candidate locations, based on a closest match between said respective estimated times, and an elapsed time between said last known on-route location and said latest location fix.

2. The method of providing an accurate location to a user'"'"'s wireless navigation device according to claim 1, wherein:

said latest location fix is a Global Positioning System (GPS) fix.

3. The method of providing an accurate location to a user'"'"'s wireless navigation device according to claim 1, wherein:

said navigation device calculates a new route from a current location of said navigation device and said returned most likely candidate location.

4. The method of providing an accurate location to a user'"'"'s wireless navigation device according to claim 1, wherein:

said navigation device is a portable navigation device.

5. The method of providing an accurate location to a user'"'"'s wireless navigation device according to claim 1, wherein:

said navigation device is a wireless phone.

6. The method of providing an accurate location to a user'"'"'s wireless navigation device according to claim 1, wherein:

generation of said plurality of candidate locations is based on a speed limit of each road segment traveled.

7. The method of providing an accurate location to a user'"'"'s wireless navigation device according to claim 1, wherein:

said plurality of candidate locations is based on traffic.

8. The method of providing an accurate location to a user'"'"'s wireless navigation device according to claim 1, wherein:

said plurality of candidate locations is based on a duty cycle of a traffic light.

9. The method of providing an accurate location to a user'"'"'s wireless navigation device according to claim 1, wherein:

a same speed limit is used for determining said estimated time of travel between each of said plurality of candidate locations and said last known on-route location.