Method of resolving a location from data representative thereof

• US 8,954,265 B2
• Filed: 04/07/2011
• Issued: 02/10/2015
• Est. Priority Date: 04/09/2010
• Status: Expired due to Fees

• Current Assignee: Tomtom North America Incorporated (TomTom NV)
• Original Assignee: Tomtom North America Incorporated (TomTom NV)
• Inventors: Hagan, James Edward
• Primary Examiner(s): Mawari, Redhwan k
• Assistant Examiner(s): Torchinsky, Edward
• Application Number:
  US13/640,088
• Publication Number:
  US 20130030692A1
• Time in Patent Office: 1,405 Days
• Field of Search: None
• US Class Current: 701/410
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/3811 Point data, e.g. Point of Interest [POI]
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G01C 21/3856 Data obtained from user input
• CPC Class Codes: G01C 21/3874 Structures specially adapted for data searching and retrieval
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

The invention provides a method of resolving a location in a second digital map from an ordered list of location reference points determined from a first digital map. The method involves identifying candidate lines and nodes in the second digital map, and using curvature, height and gradient information associated with the location reference points to identify the most likely candidate nodes or lines in the second digital map corresponding to the nodes represented by the location reference points and to lines emanating from or incident at the node in the first digital map. The method involves carrying out a route search between the most likely identified candidate node or line identified for one location reference point, and the corresponding node or line associated with the next reference point in the list, and repeating this step for consecutive pairs of reference points until the final location reference point is reached.

Claims

1. A method of resolving a location from an ordered list of location reference points, each location reference point being representative of a node in a first digital map and each location reference point being associated with information relating to the properties of a specific line or segment in said first digital map emanating from or incident at the node, the method comprising the steps of:

(i) for each location reference point, identifying at least one candidate node existing in a second digital map, and 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 an identified candidate node and a corresponding identified candidate line or segment emanating therefrom or incident thereat, and at least one of an identified candidate node for the next location reference point appearing in the list and a corresponding identified 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; and

(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,

wherein, when more than one candidate node and/or more than one candidate line or segment in the second digital map is identified for a given location reference point, the method further comprises a step of identifying a most likely candidate node and/or a most likely candidate line or segment, and using the most likely candidate node and/or most likely candidate line or segment in the route search,

wherein elevation information is associated with each location reference point, the elevation information relating to the location reference point and/or the specific line or segment emanating from or incident at the node in the first digital map represented by the location reference point, the elevation information comprising gradient information and a distance of validity for the gradient information along the candidate line or segment, and

using the elevation information in said step of identifying the most likely candidate node and/or most likely candidate line or segment when more than one candidate node and/or candidate line or segment is found in the second digital map to resolve the location in the second digital map.

2. The method of claim 1 wherein the elevation information is one or more of absolute elevation information or relative elevation information.

3. The method of claim 1, wherein the elevation information further comprises ellipsoidal height information.

5. The method of claim 1 wherein the gradient information includes information regarding the degree of the gradient and the direction of the gradient.

6. The method of claim 1, wherein curvature information is associated with each location reference point, the curvature information relating to the location reference point and/or the specific line or segment emanating from or incident at the node in the first digital map represented by the location reference point.

7. The method of claim 6, wherein each location reference point is associated with curvature and/or gradient information relating to the specific line or segment emanating from or incident at the node in the first digital map represented by the location reference point, wherein the curvature and/or gradient information is used to identify the most likely candidate line or segment for the location reference point when more than one candidate line or segment is identified for a given location reference point.

8. The method of claim 1, wherein each location reference point is associated with elevation information for the location reference point, wherein the elevation information is used to identify the most likely candidate node for the location reference point when more than one candidate node is identified for a given location reference point.

9. The method of claim 1 further comprising rating the identified candidate nodes and/or candidate lines or segments according to a likelihood that the identified candidate nodes and/or candidate lines or segments correspond to the node in the first map represented by the location reference point or the specific line or segment corresponding to the node in the first map.

10. The method of claim 9 wherein the step of rating the candidate nodes is carried out by using factors associated with elevation and the distance between the location reference point and the candidate node in the second map.

11. The method of claim 9 wherein the step of rating the candidate lines or segments is carried out by using factors associated with curvature or gradient.

12. The method of any of claims 9 further comprising ranking the candidate nodes and/or lines or segments according to a likelihood that the candidate nodes and/or lines or segments correspond to the node in the first map or the line or segment corresponding to the node in the first map represented by the location reference point.

13. The method of claim 9 further comprising displaying the second digital map and displaying the resolved location on the second digital map.

14. A non-transitory computer program product comprising computer readable instructions executable to perform a method according to any of claims 1.

16. The method of claim 6 wherein the curvature information includes information regarding the degree of curvature of the line or segment and the direction of curvature, and optionally a distance of validity for the curvature information along the line or segment.

4. The method of 1, wherein each location reference point is associated with information defining the position of the location reference point, the position information including longitudinal, latitudinal and elevation position information.

15. A navigation apparatus comprising:

a memory, wherein the memory stores at least one digital map;

a set of one or more processors, wherein the one or more processors are coupled to the memory storage, wherein the one or more processors are operative to;

(i) for each location reference point, identify at least one candidate node existing in a second digital map, and identifying at least one candidate line or segment existing in said second digital map emanating from or incident at said candidate node;

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

at least one of an identified candidate node and a corresponding identified candidate line or segment emanating therefrom or incident thereat, and at least one of an identified candidate node for the next location reference point appearing in the list and a corresponding identified 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; and

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

wherein, when more than one candidate node and/or more than one candidate line or segment in the second digital map is identified for a given location reference point, the method further comprises a step of identifying a most likely candidate node and/or a most likely candidate line or segment, and using the most likely candidate node and/or most likely candidate line or segment in the route search,

wherein elevation information is associated with each location reference point, the elevation information relating to the location reference point and/or the specific line or segment emanating from or incident at the node in the first digital map represented by the location reference point, the elevation information comprising gradient information and a distance of validity for the gradient information along the candidate line or segment, and

using the elevation in said step of identifying the most likely candidate node and/or most likely candidate line or segment when more than one candidate node and/or candidate line or segment is found in the second digital map.

17. The navigation apparatus of claim 15, wherein the gradient information comprises a gradient value for incoming and outgoing paths associated with each location reference point.

18. The navigation apparatus of claim 17, wherein a spatial lookup or conflation is used to determine the grained value.

19. The navigation apparatus of claim 15, wherein the gradient value is an average gradient value over the validity distance.