Method and apparatus for providing node-based map matching

• US 10,209,083 B2
• Filed: 06/09/2017
• Issued: 02/19/2019
• Est. Priority Date: 06/09/2017
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Jang, Dongwook
• Primary Examiner(s): Elchanti, Hussein
• Application Number:
  US15/618,954
• Publication Number:
  US 20180356235A1
• Time in Patent Office: 620 Days
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G01C 21/3881 Tile-based structures

Abstract

An approach is provided for node-based map matching. The approach involves processing probe data to sort a plurality of probe points according to sessions keys. The approach also involves selecting a subset of the plurality of probe points within a threshold distance of a node of a map representation of a transportation network. The approach further involves initiating a map matching of the probe points of each session key to the map representation by, for said each session key: (1) determining a closest probe point to the node; (2) determining another closest probe point to a neighboring node, wherein the neighboring node is connected to the node by at least one link; and (3) projecting the plurality of probe points between the closest probe point to the node and the another closest probe point to the neighboring node onto the link.

Claims

1. A computer-implemented method for map matching probe data comprising:

processing the probe data to sort a plurality of probe points of the probe data according to one or more sessions keys;

selecting a subset of the plurality of probe points within a threshold distance of a node of a map representation of a transportation network; and

initiating a map matching of the plurality of probe points of each of the one or more session keys to the map representation by, for said each session key;

determining a closest probe point to the node;

determining another closest probe point to a neighboring node, wherein the neighboring node is connected to the node by at least one link; and

projecting the plurality of probe points between the closest probe point to the node and the another closest probe point to the neighboring node onto the link to map match the plurality of probe points to the link.

2. The method of claim 1, wherein the node and the neighboring node are nodes of a node-link map representation.

3. The method of claim 1, wherein the map matching of said each location further comprises:

determining that there are more than two neighboring nodes; and

selecting two neighboring nodes from among the more than two neighboring locations points to perform the map matching based on timestamp data.

4. The method of claim 3, wherein the selecting the two neighboring nodes is based on maximizing a time window calculated from the timestamp data.

5. The method of claim 4, further comprising:

determining respective links between the selected two neighboring nodes; and

projecting the plurality of probe points falling within the time window to the respective links to map match the plurality of probe points to the respective links.

6. The method of claim 1, further comprising:

selecting another node from which to perform the map matching when the neighboring node does not exist for the node.

7. The method of claim 1, further comprising:

determining all nodes to which at least one of the plurality of probe points associated with matched session key; and

ordering said all nodes according to timestamp data; and

for each node of said all nodes in timestamp order, determining whether there are exactly two links connected to said each node.

8. The method of claim 7, wherein there are exactly two links connected to said each node, the method further comprising:

traversing said ordered all nodes to determine whether an adjacent node shares at least one of the two links; and

when the at least one of the two links is shared, projecting the plurality of probe points between said each node and the adjacent node to the at least one of the two links.

9. The method of claim 8, further comprising:

when the at least one of the two links is not shared, completing the map matching using a point-based map matcher for the plurality of probe points falling between said each node and the adjacent node.

10. The method of claim 7, wherein there are more than two shared links between said each node and an adjacent node, the method further comprising:

completing the map matching using a point-based map matcher for the plurality of probe points falling between said each node and the adjacent node.

11. An apparatus for map matching probe data 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,

process the probe data to sort a plurality of probe points of the probe data according to one or more sessions keys;

select a subset of the plurality of probe points within a threshold distance of a node of a map representation of a transportation network; and

initiate a map matching of the plurality of probe points of each of the one or more session keys to the map representation by, for said each session key;

determine a closest probe point to the node;

determine another closest probe point to a neighboring node, wherein the neighboring node is connected to the node by at least one link; and

project the plurality of probe points between the closest probe point to the node and the another closest probe point to the neighboring node onto the link to map match the plurality of probe points to the link.

12. The apparatus of claim 11, wherein the map matching of said each location further causes the apparatus to:

determine that there are more than two neighboring nodes; and

select two neighboring nodes from among the more than two neighboring locations points to perform the map matching based on timestamp data.

13. The apparatus of claim 11, wherein the apparatus is further caused to:

determine all nodes to which at least one of the plurality of probe points is matched;

order said all nodes according to timestamp data; and

for each node of said all nodes in timestamp order, determine whether said node has exactly two links connected to said each node.

14. The apparatus of claim 13, wherein there are exactly two links connected to said each node, and wherein the apparatus is further caused to:

traverse said ordered all nodes to determine whether an adjacent node shares at least one of the two links;

when the at least one of the two links is shared, project the plurality of probe points between said each node and the adjacent node to the at least one of the two links; and

when the at least one of the two links is not shared, complete the map matching using a point-based map matcher for the plurality of probe points falling between said each node and the adjacent node.

15. The apparatus of claim 13, wherein there are more than two shared links between said each node and an adjacent node, and wherein the apparatus is further caused to:

complete the map matching using a point-based map matcher for the plurality of probe points falling between said each node and the adjacent node.

16. A non-transitory computer-readable storage medium for map matching probe data carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to at least perform the following steps:

processing the probe data to sort a plurality of probe points of the probe data into one or more location traces;

selecting a subset of the plurality of probe points within a threshold distance of a location point of a map representation of a transportation network; and

initiating a map matching of the plurality of probe points of each location trace of the one or more location traces to the map representation by, for said each location trace;

determining a closest probe point to the location point;

determining another closest probe point to a neighboring location point, wherein the neighboring location point is connected to the location point by at least one link; and

projecting the plurality of probe points between the closest probe point to the location point and the another closest probe point to the neighboring location point onto the link to map match the plurality of probe points to the link.

17. The non-transitory computer-readable storage medium of claim 16, wherein the map matching of said each location further causes the apparatus to further perform:

determining that there are more than two neighboring location points; and

selecting two neighboring location points from among the more than two neighboring locations points to perform the map matching based on timestamp data.

18. The non-transitory computer-readable storage medium of claim 16, wherein the apparatus is further caused to perform:

determining all location points to which at least one of the plurality of probe points is matched;

ordering said all location points according to timestamp data; and

for each location point of said all location points in timestamp order, determining whether said location point has exactly two links connected to said each location point.

19. The non-transitory computer-readable storage medium of claim 18, wherein there are exactly two links connected to said each location point, and wherein the apparatus is further caused to perform:

traversing said ordered all location points to determine whether an adjacent location point shares at least one of the two links;

when the at least one of the two links is shared, projecting the plurality of probe points between said each location point and the adjacent location point to the at least one of the two links; and

when the at least one of the two links is not shared, completing the map matching using a point-based map matcher for the plurality of probe points falling between said each location point and the adjacent location point.

20. The non-transitory computer-readable storage medium of claim 18, wherein there are more than two shared links between said each location point and an adjacent location point, and wherein the apparatus is further caused to perform:

completing the map matching using a point-based map matcher for the plurality of probe points falling between said each location point and the adjacent location point.