Ambiguity map match rating

• US 10,145,691 B2
• Filed: 05/18/2016
• Issued: 12/04/2018
• Est. Priority Date: 05/18/2016
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Lynch, James
• Primary Examiner(s): Cass, Jean Paul
• Application Number:
  US15/157,542
• Publication Number:
  US 20170336214A1
• Time in Patent Office: 930 Days
• Field of Search: 701446
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/34 Route searching; Route guidance

Abstract

Methods and apparatuses are provided for generating, using, and storing ambiguity ratings for map matching. In an embodiment, an ambiguity rating is generated using a road segment and a relationship of the road segment and other nearby road segments. The ambiguity rating may be stored in a cell based map. The ambiguity rating may be used to select an efficient map matching algorithm and provide expected map matching confidence.

Claims

1. A method for conserving computational resources and time by determining when to use a less or more complex algorithm to map match a positional point to a road segment, the method comprising:

identifying, by a processor, the road segment;

identifying, by the processor, one or more neighboring road segments;

determining, by the processor, a relationship between the road segment and the one or more neighboring road segments;

and

selecting, by the processor, a map matching algorithm from a plurality of potential map matching algorithms based on a complexity value of the relationship between the road segment and the one or more neighboring road segments, wherein a less complex map matching algorithm is selected over a more complex map matching algorithm for lower complexity values, wherein the plurality of potential map matching algorithms include map matching algorithms with a range of complexity, wherein the map matching algorithm is used to map match the positional point collected by a positioning sensor while a vehicle traverses a roadway network.

2. The method of claim 1, wherein the neighboring road segments are located within a threshold distance from the road segment.

3. The method of claim 1, further comprising:

storing the complexity value as an attribute for the road segment in a map database that describes a geographic area.

4. The method of claim 1, wherein determining the relationship comprises:

generating, by the processor, a score for each of the one or more neighboring road segments for a potential to be selected by one or more of the plurality of potential map matching algorithms.

5. The method of claim 1, further comprising:

counting, by the processor, a number of adjacent neighboring road segments to the road segment for the complexity value.

6. The method of claim 1, wherein the complexity value includes a varying complexity value along a distance of the road segment.

7. The method of claim 1, wherein the complexity value comprises numerical data used to select inputs and complexity of the map matching algorithm to be used.

8. A method for limiting waste of resources and time by determining when to use a less or more complex algorithm to map match a positional point to a road segment, the method comprising:

identifying, when traveling a roadway, the positional point of a vehicle;

determining, by a processor, a complexity value stored in a map database, wherein the complexity value is associated with a first road segment or node thereof, wherein the complexity value describes a level of map matching complexity in the vicinity of the first road segment;

identifying, by the processor, a level of computational complexity of map matching based on the complexity value;

selecting, by the processor, a map matching algorithm from a plurality of potential map matching algorithms based on the complexity value, wherein a less complex map matching algorithm is selected over a more complex map matching algorithm for lower complexity values, wherein the map matching algorithm is equal to or exceeds the level of computational complexity; and

map matching, by the processor, the positional point to a second road segment with the map matching algorithm.

9. The method of claim 8, wherein prior to determining the complexity value, the first road segment or node is identified using a preliminary map matching algorithm, wherein the map matching algorithm is a secondary map matching algorithm.

10. The method of claim 8, wherein the complexity value is derived from the first road segment and a relationship of the first road segment and one or more neighboring road segments.

11. The method of claim 8, wherein different values of the complexity value correspond to specific types of map matching algorithms.

12. The method of claim 9, wherein the preliminary map matching algorithm matches the first road segment to a closest spatial road segment.

13. The method of claim 12, wherein the map matching algorithm uses a heading as an input.

14. The method of claim 12, wherein the map matching algorithm uses one or more prior road segments as an input.

15. The method of claim 8, further comprising:

determining, by the processor, a second complexity value for the second road segment;

identifying, by the processor, a second level of computational complexity of map matching for the second complexity value;

selecting, by the processor, a third map matching algorithm, wherein the third map matching algorithm is equal to or exceeds the second level of computational complexity; and

map matching, by the processor, the positional point to a third road segment with the third map matching algorithm.

16. An apparatus for map matching a positional point to a road segment using a computationally appropriate map matching algorithm, the apparatus comprising:

at least one processor; and

at least one memory including computer program code for one or more programs;

the at least one memory configured to store the computer program code configured to, with the at least one processor, cause the apparatus to at least perform;

determine the positional point as a vehicle traverses a roadway network;

identify, using the at least one processor, in a plurality of geographic cells stored in the at least one memory, a complexity value for a geographic cell of the plurality of geographic cells, wherein the complexity value describes a level of map matching computational complexity to be used when map matching in the geographic cell, wherein the geographic cell includes the positional point;

select, using the at least one processor, a map matching algorithm from a plurality of potential map matching algorithms based on the complexity value, wherein the potential map matching algorithms include map matching algorithms with a range of computational complexity, wherein a less computationally complex map matching algorithm is selected as the map matching algorithm when the ambiguity rating is lower and a more computationally complex map matching algorithm is selected as the map matching algorithm when the complexity value is higher;

map match, using the at least one processor, the positional point to the road segment using the map matching algorithm; and

provide, the road segment as a location of the vehicle to an operator of the vehicle.

17. The apparatus of claim 16, wherein the complexity value is a function of a number of road segments in the geographic cell.

18. The apparatus of claim 16, wherein the complexity value is based on a number of parallel road segments in the geographic cell.

19. A computer-readable, non-transitory medium storing a program that causes a computer to execute a method for conserving computational resources of a navigation device by determining when to use a less or more complex algorithm to map match a positional point to a value for use in selecting a computationally efficient map matching algorithm when map matching a road segment, the method comprising:

identifying one or more neighboring road segments in a predefined vicinity of the road segment;

selecting a map matching algorithm from a plurality of potential map matching algorithms based on a complexity value of the relationship between the road segment and the one or more neighboring road segments, wherein a less complex map matching algorithm is selected over a more complex map matching algorithm for lower complexity values, wherein the plurality of potential map matching algorithms include map matching algorithms with a range of computational complexity;

map matching using the selected map matching algorithm, the road segment and the positional point collected by a positioning sensor while a vehicle traverses a roadway network; and

generating using the map matched positional point, a maneuver to be performed by the vehicle.