Diverging and converging road geometry generation from sparse data

• US 9,658,074 B2
• Filed: 10/13/2014
• Issued: 05/23/2017
• Est. Priority Date: 10/13/2014
• 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): Black, Thomas G
• Assistant Examiner(s): Nolan, Peter D
• Application Number:
  US14/512,588
• Publication Number:
  US 20160102984A1
• Time in Patent Office: 953 Days
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/3819 Road shape data, e.g. outline of a route
• CPC Class Codes: G01C 21/3844 Data obtained from position sensors only, e.g. from inertial navigation
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G08G 1/012 from other sources than vehicle or roadside beacons, e.g. mobile networks
• CPC Class Codes: G08G 1/096811 where the route is computed offboard

Abstract

Road geometries may be determined from sparse data by receiving mobile device data points comprising data indicating positions of vehicles having traveled on a roadway of a geographic area, the roadway involving a convergence or divergence of road branches for the roadway. At least one trajectory angle for a particular mobile device data point of the mobile device data points may be determined using at least one trajectory line connecting the particular mobile device data point to an adjacent mobile device data point, and mobile device data points may be grouped based on the trajectory angles.

Claims

1. A method comprising:

receiving, by a processor, a plurality of mobile device data points comprising data indicating positions of vehicles having traveled on a roadway of a geographic area, the roadway involving a convergence or divergence of a plurality of road branches for the roadway;

connecting, by the processor, subsets of the plurality of mobile device data points with trajectory lines, each of the subsets associated with a particular vehicle, wherein the trajectory lines connect adjacent mobile device data points determined by a sequence in which the individual mobile device data points of subsets were acquired;

determining, by the processor, at least one trajectory angle for a particular mobile device data point of the plurality of mobile device data points using a first trajectory line connecting the particular mobile device data point to an adjacent mobile device data point, and either (i) a heading direction of the particular vehicle or (ii) a second trajectory line connecting the particular mobile device data point with an additional adjacent mobile device data point, wherein the particular mobile device data point is positioned between the adjacent mobile device data point and the additional adjacent mobile device data point; and

assigning, by the processor, the particular mobile device data point to a particular road branch of the plurality of road branches based on the determined at least one trajectory angle,

wherein the at least one trajectory angle is (i) an angle between the heading direction and the first trajectory line intersecting at the particular mobile device data point or (ii) an angle between the first trajectory line and the second trajectory line intersecting at the particular mobile device data point.

2. The method of claim 1, further comprising:

repeating the determining the at least one trajectory angle and assigning to the particular road branch for remaining data points of the plurality of mobile device data points.

3. The method of claim 1, further comprising:

determining a geometry of the particular road branch based on the mobile device data points assigned to the particular road branch.

4. The method of claim 1, wherein the at least one trajectory angle is determined as the angle between the heading direction and the first trajectory line.

5. The method of claim 4, wherein the adjacent mobile device data point is a subsequent mobile device data point of the subset of the mobile device data points.

6. The method of claim 4, wherein the adjacent mobile device data point is a previous mobile device data point of the subset of the mobile device data points.

7. The method of claim 1, wherein the at least one trajectory angle is determined as the angle between the first trajectory line and the second trajectory line.

8. The method of claim 1, wherein the assigning comprises clustering the plurality of mobile device data points based on the determined at least one trajectory angle.

9. An apparatus comprising:

at least one processor; and

at least one memory including computer program code and operable to store a plurality of mobile device data points comprising data indicating positions of vehicles having traveled on a roadway of a geographic area, the roadway involving a convergence or divergence of a plurality of road branches for the roadway;

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

connect subsets of the plurality of mobile device data points with trajectory lines, each of the subsets associated with a particular vehicle, and wherein the lines connect adjacent mobile device data points determined by a sequence in which the individual mobile device data points of subsets were acquired;

determine at least one trajectory angle for a particular mobile device data point of the plurality of mobile device data points using a first trajectory line connecting the particular mobile device data point to an adjacent mobile device data point, and either (i) a heading direction of the particular vehicle or (ii) a second trajectory line connecting the particular mobile device data point with an additional adjacent mobile device data point, wherein the particular mobile device data point is positioned between the adjacent mobile device data point and the additional adjacent mobile device data point; and

assign the particular mobile device data point to a particular road branch of the plurality of road branches based on the determined at least one trajectory angle,

wherein the at least one trajectory angle is (i) an angle between the heading direction and the first trajectory line intersecting at the particular mobile device data point or (ii) an angle between the first trajectory line and the second trajectory line intersecting at the particular mobile device data point.

10. The apparatus of claim 9, wherein the at least one memory and the computer program code further configured to, with the at least one processor, cause the apparatus at least to:

repeat the determination of trajectory angles and assigning to road branches for the rest of the plurality of mobile device data points.

11. The apparatus of claim 9, wherein the at least one memory and the computer program code further configured to, with the at least one processor, cause the apparatus at least to:

determine a geometry of the particular road branch based on the mobile device data points assigned to the particular road branch.

12. The apparatus of claim 9, wherein the at least one trajectory angle is determined as the angle between the heading direction and the first trajectory line.

13. The apparatus of claim 12, wherein the adjacent mobile device data point is a subsequent mobile device data point of the subset of the mobile device data points.

14. The apparatus of claim 12, wherein the adjacent mobile device data point is a previous mobile device data point of the subset of the mobile device data points.

15. The apparatus of claim 9, wherein the at least one trajectory angle is determined as the angle between the first trajectory line and the second trajectory line.

16. The apparatus of claim 9, wherein the assigning comprises determining clusters of the plurality of mobile device data points based on the determined at least one trajectory angle.

17. A non-transitory computer readable medium including instructions that when executed on a computer are operable to:

receive a plurality of mobile device data points comprising data indicating positions of vehicles having traveled on a roadway of a geographic area, the roadway involving a convergence or divergence of a plurality of road branches for the roadway;

connect subsets of the plurality of mobile device data points with trajectory lines, each of the subsets associated with a particular vehicle, and wherein the lines connect adjacent mobile device data points determined by a sequence in which the individual mobile device data points of subsets were acquired;

determine at least one trajectory angle for a particular mobile device data point of the plurality of mobile device data points using a first trajectory line connecting the particular mobile device data point to an adjacent mobile device data point, and either (i) a heading direction of the particular vehicle or (ii) a second trajectory line connecting the particular mobile device data point with an additional adjacent mobile device data point, wherein the particular mobile device data point is positioned between the adjacent mobile device data point and the additional adjacent mobile device data point; and

assign the particular mobile device data point to a particular road branch of the plurality of road branches based on at the at least one trajectory angle,

wherein the at least one trajectory angle is (i) an angle between the heading direction and the first trajectory line intersecting at the particular mobile device data point or (ii) an angle between the first trajectory line and the second trajectory line intersecting at the particular mobile device data point.

18. The medium of claim 17, wherein the at least one trajectory angle is determined as the angle between the heading direction and the first trajectory line, and

wherein the adjacent mobile device data point is a subsequent mobile device data point of the subset of the mobile device data points.

19. The medium of claim 17, wherein the at least one trajectory angle is determined as the angle between the heading direction and the first trajectory line, and

wherein the adjacent mobile device data point is a previous mobile device data point of the subset of the mobile device data points.

20. The medium of claim 17, wherein the at least one trajectory angle is determined as the angle between the first trajectory line and the second trajectory line.