Method and apparatus for two dimensional edge-based map matching

• US 10,359,290 B2
• Filed: 03/22/2013
• Issued: 07/23/2019
• Est. Priority Date: 03/22/2013
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Felix, Macgregor, Natesan, Senthil, Williams, Trent
• Primary Examiner(s): Featherstone, Mark D
• Assistant Examiner(s): McQuitery, Diedra
• Application Number:
  US13/849,238
• Publication Number:
  US 20140289267A1
• Time in Patent Office: 2,314 Days
• Field of Search: 701400, 701408, 701410, 701411, 701412, 701417, 701426, 701430, 701461, 701468, 701472, 701517, 701532, 701533, 707758
• 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/28 with correlation of data from several navigational instruments
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/32 Structuring or formatting of map data
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles

Abstract

Two-dimensional (2D) edge-based map matching includes using a 2D edge-based map matching platform. The 2D edge-based map matching platform receives at least one request to match a probe data point to one of a plurality of thoroughfare segments. Next, the 2D edge-based map matching platform determines respective edges of the plurality of thoroughfare segments and causes a matching of the probe data point to the one thoroughfare segment based on a comparison of the probe data point to the respective edges of the plurality of thoroughfare segments.

Claims

1. A method, comprising:

matching at least one probe data point to one of a plurality of thoroughfare segments, wherein the at least one probe data point is captured by way of map matching or geo-coding techniques that factor in velocity and bearing information for positional accuracy;

determining respective edges of the plurality of thoroughfare segments based on a respective width of the thoroughfare segments, wherein the respective edges extend along sides of centerlines of the thoroughfare segments;

matching the at least one probe data point to the one thoroughfare segment based, at least in part, on a comparison of the at least one probe data point to the respective edges of the plurality of thoroughfare segments;

determining first distances from the at least one probe data point to the centerlines of the plurality of thoroughfare segments; and

determining second distances from the centerlines to the respective edges of the plurality of thoroughfare segments,

wherein the comparison is based, at least in part, on subtracting the second distances from the first distances,

wherein the plurality of thoroughfare segments is substantially parallel, and

wherein the at least one probe data point lies between the centerlines of the plurality of thoroughfare segments, and wherein one or more of the plurality of thoroughfare segments that exceeds a threshold distance from the at least one probe data point or is separated from the at least one probe data point by one or more other thoroughfare segments is discarded.

2. The method of claim 1, further comprising:

determining the plurality of thoroughfare segments based, at least in part, on the plurality of thoroughfare segments being proximate to the at least one probe data point among a network of thoroughfare segments.

3. The method of claim 1, wherein the at least one probe data point is matched to the one thoroughfare segment based, at least in part, on a smallest distance.

4. The method of claim 1, further comprising:

determining respective edges of the plurality of thoroughfare segments based on respective numbers of lanes of the plurality of thoroughfare segments multiplied by a lane width.

5. The method of claim 1, further comprising:

determining elevation information associated with the plurality of thoroughfare segments, the at least one probe data point, or a combination thereof,

wherein the matching of the at least one probe data point to the one thoroughfare segment is based on the elevation information.

6. The method of claim 5, further comprising:

determining the elevation information of one or more of the plurality of thoroughfare segments based, at least in part, on an average elevation of one or more other probe data points associated with the plurality of thoroughfare segments.

7. The method of claim 1, wherein the respective edges of the plurality of thoroughfare segments are respective edges of each of the plurality of thoroughfare segments proximate to the at least one probe data point.

8. An 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 and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following,

receive at least one request to match at least one probe data point to one of a plurality of thoroughfare segments, wherein the at least one probe data point is captured by way of map matching or geo-coding techniques that factor in velocity and bearing information for positional accuracy;

determine respective edges of the plurality of thoroughfare segments based on a respective width of the thoroughfare segments, wherein the respective edges extend along sides of centerlines of the thoroughfare segments;

cause, at least in part, a matching of the at least one probe data point to the one thoroughfare segment based, at least in part, on a comparison of the at least one probe data point to the respective edges of the plurality of thoroughfare segments;

determining first distances from the at least one probe data point to the centerlines of the plurality of thoroughfare segments; and

determining second distances from the centerlines to the respective edges of the plurality of thoroughfare segments,

wherein the comparison is based, at least in part, on subtracting the second distances from the first distances,

wherein the plurality of thoroughfare segments is substantially parallel, and

wherein the at least one probe data point lies between the centerlines of the plurality of thoroughfare segments, and wherein one or more of the plurality of thoroughfare segments exceeds a threshold distance from the at least one probe data point or is separated from the at least one probe data point by one or more other thoroughfare segments is discarded.

9. An apparatus of claim 8, wherein the apparatus is further caused to:

determine the plurality of thoroughfare segments based, at least in part, on the plurality of thoroughfare segments being proximate to the at least one probe data point among a network of thoroughfare segments.

10. An apparatus of claim 8, wherein the at least one probe data point is matched to the one thoroughfare segment based, at least in part, on a smallest distance.

11. An apparatus of claim 8, wherein the apparatus is further caused to:

determine respective edges of the plurality of thoroughfare segments based, at least in part, on respective numbers of lanes of the plurality of thoroughfare segments multiplied by a lane width.

12. An apparatus of claim 8, wherein the apparatus is further caused to:

determine elevation information associated with the plurality of thoroughfare segments, the at least one probe data point, or a combination thereof,

wherein the matching of the at least one probe data point to the one thoroughfare segment is based, at least in part, on the elevation information.

13. An apparatus of claim 12, wherein the apparatus is further caused to:

determine the elevation information of one or more of the plurality of thoroughfare segments based, at least in part, on an average elevation of one or more other probe data points associated with the plurality of thoroughfare segments.

14. An apparatus of claim 8, wherein the respective edges of the plurality of thoroughfare segments are respective edges of each of the plurality of thoroughfare segments proximate to the at least one probe data point.