METHOD OF RESOLVING A LOCATION FROM ENCODED DATA REPRESENTATIVE THEREOF

• US 20110098912A1
• Filed: 06/29/2009
• Published: 04/28/2011
• Est. Priority Date: 06/30/2008
• Status: Active Grant

• Current Assignee: TomTom Traffic B.V. (TomTom NV)
• Original Assignee: TomTom International BV (TomTom NV)
• Inventors: Petzold, Lars, Schaefer, Ralf-Peter, Baselau, Sven
• Granted Patent: US 8,818,707 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

A method, of resolving a location from an ordered list of location reference points being representative of nodes in an encoder digital map and each having attributes representative of a specific line or segment in the encoder digital map emanating from or incident at those nodes, is disclosed. In at least one embodiment, the method includes (i) for each location reference point, identifying at least one candidate node existing in a second digital map, and, using the available attributes of that location reference point, identifying at least one candidate line or segment existing in the second digital map emanating from or incident at the candidate node, (ii) performing a route search within the second digital map between: (a) at least one of said at least one candidate node and the corresponding candidate line or segment emanating therefrom or incident thereat, and (b) at least one of a candidate node for the next location reference point appearing in the list and the corresponding candidate line or segment emanating therefrom or incident thereat, and extracting from the second digital map each line or segment forming part of the route so determined between the candidate nodes, (iii) repeating step (ii) for each consecutive pair of location reference points up to and including the final location reference point appearing in the list. Preferably, the route search is a shortest path route search, most preferably operating on respective pairs of successive candidate nodes, and includes a way of ensuring that the corresponding line or segment of the first of the pair of nodes forms part of the route resulting therefrom.

Claims

1. A method of resolving a location from an ordered list of location reference points being representative of nodes in an encoder digital map and each having attributes representative of a specific line or segment in said encoder digital map emanating from or incident at those nodes, comprising the steps of:

(i) for each location reference point, identifying at least one candidate node existing in a second digital map, and, using the available attributes of that location reference point, identifying at least one candidate line or segment existing in said second digital map emanating from or incident at said candidate node,

(ii) performing a route search within said second digital map between;

at least one of said at least one candidate node and the corresponding candidate line or segment emanating therefrom or incident thereat, and

at least one of a candidate node for the next location reference point appearing in the list and the corresponding candidate line or segment emanating therefrom or incident thereat, and extracting from said second digital map each line or segment forming part of the route so determined between said candidate nodes,

(iii) repeating step (ii) for each consecutive pair of location reference points up to and including the final location reference point appearing in the list.

2. A method according to claim 1 wherein the route search is a shortest path route search.

3. A method according to claim 1 wherein the route search operates on respective pairs of successive candidate nodes.

4. A method according to claim 1 wherein the route search includes a way of ensuring that the corresponding line or segment of the first of the pair of nodes forms part of the route resulting therefrom.

5. A method according to claim 1 wherein the candidate nodes identified are real nodes in that they are representative of real world intersections.

6. A method according to claim 1 wherein the extracting of each line or segment from the second digital map is enhanced by storing each of said extracted lines or segments in a location path list.

7. A method according to claim 6 wherein each location path list created for each successive route search is concatenated.

8. A method according to claim 6 wherein the lines or segments extracted during a succeeding route search are appended to a pre-existing location path list.

9. A method according to claim 1 further comprising rating said identified candidate nodes according to one or more prescribed metrics in the case where more than one candidate node is identified for a location reference point.

10. A method according to claim 1 further comprising rating candidate lines or segments to identify a most likely candidate line or segment according to one or more prescribed metrics in the case where more than one candidate line or segment existing in the second digital map is identified.

11. A method according to claim 9 wherein the rating is achieved using a rating function.

12. A method according to claim 11 wherein the rating function includes a candidate node rating part and a candidate line or segment rating part.

13. A method according to claim 12 wherein the candidate node rating part of the rating function includes some dependence on a representative or calculated distance between the location reference point or its absolute coordinates, and said candidate nodes or their absolute coordinates as appearing in and extracted from the second digital map.

14. A method according to claim 12 wherein the candidate line or segment rating part of the rating function includes a way of assessing the similarity of the line or segment attributes as appearing in the encoder digital map and those appearing in the second digital map used in resolving the location.

15. A method according to claim 1 wherein the method further comprises:

determining, from the second digital map, a path length value for each path between successive candidate nodes within said second digital map, said path being established as a result of the route search between said successive candidate nodes,

comparing the path length value so determined with a DNP attribute of the first of the two location reference points used in the route search, and

in the event of too great a discrepancy between the path length value and the DNP attribute, either repeating the route search using at least one of alternative candidate nodes and lines for one or both of each successive pair of location reference points to attempt to reduce the discrepancy between path length value and DNP attribute, or reporting an error.

16. A method according to claim 1 further comprising applying any offset value which may be associated with the first and last location reference points to the first and last lines extracted from the second digital map as a result of the route search therein.

17. A computer program element, embodied on a non-transitory computer readable medium, comprising computer program code to execute, when run on a computer device, the method as set out in claim 1.

18. A non-transitory computer readable medium embodying the computer program element according to claim 17.

19. A computing device comprising:

a processor;

storage, in which computer program code according to claim 17 resides and which together provide an execution environment for the program code;

a program resource being a digital map, stored in the storage or in a different storage; and

an information output device.

20. A computing device according to claim 19 wherein the information output device provides at least one of an audible output, a printed output, or a visible output on a display screen capable of displaying a graphical representation of said digital map.

21. A computing device according to claim 20 wherein a resolved location or a portion of it, is displayed in superposed, overlaid, juxtaposed or in conjunction with the relevant portion of the digital map to which it relates.