Method and apparatus for matching probe points to road segments utilizing a trajectory identifier

• US 10,209,082 B2
• Filed: 05/05/2016
• Issued: 02/19/2019
• Est. Priority Date: 05/05/2016
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Dorum, Ole Henry
• Primary Examiner(s): Paige, Tyler D
• Application Number:
  US15/147,406
• Publication Number:
  US 20170322035A1
• Time in Patent Office: 1,020 Days
• Field of Search: 701446
• 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: G08G 1/0112 from the vehicle, e.g. floating car data [FCD]

Abstract

A method, apparatus and computer program product are provided to match probe points to road segments utilizing a trajectory identifier, thereby increasing the accuracy with which probe points, such as probe points in ambiguous locations, are matched to road segments. For a probe point having a respective trajectory identifier (ID) and associated with an ambiguous link tuple, the method identifies each probe point having the respective trajectory ID that is unambiguously matched to first or second branches. The method separately determines a number of probe points having the respective trajectory ID that are unambiguously matched to the first and second branches. The method matches the probe point having the respective trajectory ID and associated with the ambiguous link tuple to either the first branch or the second branch based upon the number of probe points having the respective trajectory ID that are unambiguously matched to the first and second branches.

Claims

1. A method comprising:

for a probe point having a respective trajectory identifier (ID) that identifies probe points collected by a device at least for a period of time and associated with an ambiguous link tuple comprised of two or more links of a road network to which the probe point is matched, identifying each probe point having the respective trajectory ID that is unambiguously matched to one of a first branch or a second branch that extend away from the ambiguous link tuple;

separately determining a number of probe points having the respective trajectory ID that are unambiguously matched to the first branch and that are unambiguously matched to the second branch; and

matching the probe point having the respective trajectory ID that was associated with the ambiguous link tuple to a respective one of the first branch or the second branch based upon the number of probe points having the respective trajectory ID that are unambiguously matched to the first branch and that are unambiguously matched to the second branch.

2. A method according to claim 1 wherein matching the probe point comprises matching the probe point having the respective trajectory ID that was associated with the ambiguous link tuple to the respective one of the first branch or the second branch for which the number of probe points having the respective trajectory ID unambiguously matched thereto exceeds the number of probe points having the respective trajectory ID that are unambiguously matched to the other one of the first branch or the second branch by at least a predefined amount.

3. A method according to claim 2 further comprising causing the probe point having the respective trajectory ID to remain associated with the ambiguous link tuple in an instance in which the number of probe points having the respective trajectory ID that are unambiguously matched to the first branch and that are unambiguously matched to the second branch differ by less than the predefined amount.

4. A method according to claim 1 wherein a plurality of probe points having respective trajectory IDs are associated with the ambiguous link tuple, and wherein identifying each probe point comprises identifying each probe point having any one of the respective trajectory IDs of the probe points associated with the ambiguous link tuple that are unambiguously matched to one of the first branch or the second branch during a single traversal of the first branch and the second branch.

5. A method according to claim 1 further comprising determining a confidence value associated with the match of the probe point having the respective trajectory ID to a respective one of the first branch or the second branch based upon a ratio of a number of probe points having the respective trajectory ID that are unambiguously matched to the first branch and to the second branch.

6. A method according to claim 1 further comprising map matching a plurality of probe points to respective links, wherein map matching comprises identifying the probe point associated with the ambiguous link tuple.

7. A method according to claim 1 wherein identifying each probe point comprises identifying each probe point having the respective trajectory ID that is unambiguously matched to one of the first and second branches along a same predefined length of the first and second branches.

8. A method according to claim 1 wherein the first branch splits into at least two sub-branches, and wherein identifying each probe point comprises identifying each probe point having the respective trajectory ID that is unambiguously matched to one of the at least two sub-branches.

9. An apparatus comprising at least one processor and at least one memory storing computer program code, wherein the at least one memory and stored computer program code are configured, with the at least one processor, to cause the apparatus to at least:

for a probe point having a respective trajectory identifier (ID) that identifies probe points collected by a device at least for a period of time and associated with an ambiguous link tuple comprised of two or more links of a road network to which the probe point is matched, identify each probe point having the respective trajectory ID that is unambiguously matched to one of a first branch or a second branch that extend away from the ambiguous link tuple;

separately determine a number of probe points having the respective trajectory ID that are unambiguously matched to the first branch and that are unambiguously matched to the second branch; and

match the probe point having the respective trajectory ID that was associated with the ambiguous link tuple to a respective one of the first branch or the second branch based upon the number of probe points having the respective trajectory ID that are unambiguously matched to the first branch and that are unambiguously matched to the second branch.

10. An apparatus according to claim 9 wherein the at least one memory and stored computer program code are configured, with the at least one processor, to cause the apparatus to match the probe point by matching the probe point having the respective trajectory ID that was associated with the ambiguous link tuple to the respective one of the first branch or the second branch for which the number of probe points having the respective trajectory ID unambiguously matched thereto exceeds the number of probe points having the respective trajectory ID that are unambiguously matched to the other one of the first branch or the second branch by at least a predefined amount.

11. An apparatus according to claim 10 wherein the at least one memory and stored computer program code are further configured, with the at least one processor, to cause the apparatus to cause the probe point having the respective trajectory ID to remain associated with the ambiguous link tuple in an instance in which the number of probe points having the respective trajectory ID that are unambiguously matched to the first branch and that are unambiguously matched to the second branch differ by less than the predefined amount.

12. An apparatus according to claim 9 wherein a plurality of probe points having respective trajectory IDs are associated with the ambiguous link tuple, and wherein the at least one memory and stored computer program code are configured, with the at least one processor, to cause the apparatus to identify each probe point by identifying each probe point having any one of the respective trajectory IDs of the probe points associated with the ambiguous link tuple that are unambiguously matched to one of the first branch or the second branch during a single traversal of the first branch and the second branch.

13. An apparatus according to claim 9 wherein the at least one memory and stored computer program code are further configured, with the at least one processor, to cause the apparatus to determine a confidence value associated with the match of the probe point having the respective trajectory ID to a respective one of the first branch or the second branch based upon a ratio of a number of probe points having the respective trajectory ID that are unambiguously matched to the first branch and to the second branch.

14. An apparatus according to claim 9 wherein the at least one memory and stored computer program code are further configured, with the at least one processor, to cause the apparatus to map match a plurality of probe points to respective links, and wherein the at least one memory and stored computer program code are configured, with the at least one processor, to cause the apparatus to map match by identifying the probe point associated with the ambiguous link tuple.

15. A computer program product comprising at least one non-transitory computer-readable storage medium having computer-readable program instructions stored therein, the computer-readable program instructions comprising:

for a probe point having a respective trajectory identifier (ID) that identifies probe points collected by a device at least for a period of time and associated with an ambiguous link tuple comprised of two or more links of a road network to which the probe point is matched, program instructions configured to identify each probe point having the respective trajectory ID that is unambiguously matched to one of a first branch or a second branch that extend away from the ambiguous link tuple;

program instructions configured to separately determine a number of probe points having the respective trajectory ID that are unambiguously matched to the first branch and that are unambiguously matched to the second branch; and

program instructions configured to match the probe point having the respective trajectory ID that was associated with the ambiguous link tuple to a respective one of the first branch or the second branch based upon the number of probe points having the respective trajectory ID that are unambiguously matched to the first branch and that are unambiguously matched to the second branch.

16. A computer program product according to claim 15 wherein the program instructions configured to match the probe point comprise program instructions configured to match the probe point having the respective trajectory ID that was associated with the ambiguous link tuple to the respective one of the first branch or the second branch for which the number of probe points having the respective trajectory ID unambiguously matched thereto exceeds the number of probe points having the respective trajectory ID that are unambiguously matched to the other one of the first branch or the second branch by at least a predefined amount.

17. A computer program product according to claim 16 wherein the computer-readable program instructions further comprise program instructions configured to cause the probe point having the respective trajectory ID to remain associated with the ambiguous link tuple in an instance in which the number of probe points having the respective trajectory ID that are unambiguously matched to the first branch and that are unambiguously matched to the second branch differ by less than the predefined amount.

18. A computer program product according to claim 15 wherein a plurality of probe points having respective trajectory IDs are associated with the ambiguous link tuple, and wherein the program instructions configured to identify each probe point comprise program instructions configured to identify each probe point having any one of the respective trajectory IDs of the probe points associated with the ambiguous link tuple that are unambiguously matched to one of the first branch or the second branch during a single traversal of the first branch and the second branch.

19. A computer program product according to claim 15 wherein the computer-readable program instructions further comprise program instructions configured to determine a confidence value associated with the match of the probe point having the respective trajectory ID to a respective one of the first branch or the second branch based upon a ratio of a number of probe points having the respective trajectory ID that are unambiguously matched to the first branch and to the second branch.

20. A computer program product according to claim 15 wherein the computer-readable program instructions further comprise program instructions configured to map match a plurality of probe points to respective links, wherein the program instructions configured to map match comprise program instructions configured to identify the probe point associated with the ambiguous link tuple.