Probe based identification and validation of roundabout junctions

• US 9,672,759 B2
• Filed: 05/11/2015
• Issued: 06/06/2017
• Est. Priority Date: 05/11/2015
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Hofmann, Hilko, Jehlicka, Prokop
• Primary Examiner(s): Badii, Behrang
• Assistant Examiner(s): GREENE, DANIEL LAWSON
• Application Number:
  US14/708,827
• Publication Number:
  US 20160335923A1
• Time in Patent Office: 757 Days
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3819 Road shape data, e.g. outline of a route
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G09B 29/003 Maps
• CPC Class Codes: G09B 29/004 Map manufacture or repair; Tear or ink or water resistant maps; Long-life maps printing processes for maps B41M3/02; by permanently attaching map sections to sheets B42B7/00

Abstract

Probe data including points with geographic locations and heading angles are identified for a geographic area. A translation is performed on the points in the probe data in a predetermined direction orthogonal to the corresponding heading. The translated points are aggregated according to a location grid. The aggregated points are analyzed from the location grid according to the heading. A potential location for a center of a roundabout road formation is determined based on the analysis.

Claims

1. A method comprising:

receiving probe data for a geographic area;

identifying a plurality of points in the probe data, wherein each of the plurality of points includes a geographic location and a heading;

performing, by a processor, a translation of locations of the plurality of points in the probe data in a predetermined direction orthogonal to the corresponding heading;

aggregating the plurality of points, after translating, according to a location grid;

performing, by the processor, an analysis on the plurality of points in the location grid according to the heading; and

identifying a center of a roundabout road formation based on the analysis.

2. The method of claim 1, wherein the analysis comprises:

segmenting the plurality of points into a plurality of directional segments within a cell of the location grid,

wherein the roundabout road formation is identified when a threshold number of the direction segments within the cell include one or more of the plurality of points.

3. The method of claim 1, wherein the translation is a first translation, and the analysis is a first analysis, the method further comprising:

performing a second translation on the plurality of points in the probe data in a second predetermined direction orthogonal to the corresponding heading;

aggregating the plurality of points, after translating, according to the location grid; and

performing a second analysis on the plurality of points in the location grid according to the heading,

wherein the center of the roundabout road formation is identified based on the first analysis and the second analysis.

4. The method of claim 1, further comprising:

selecting a subset of the geographic area for an estimate intersection location based on a user input or stored map data.

5. The method of claim 1, further comprising:

calculating a distance from the center of the roundabout road formation for each of the plurality of points;

sorting the plurality of points according to the distance from the center of the roundabout road formation;

identifying a peak distance range; and

comparing the peak distance range to a predetermined distance.

6. The method of claim 1, further comprising:

determining an interior quantity of a number of the plurality of points that are less than a predetermined distance from the roundabout center of the road formation; and

comparing the interior quantity to an interior threshold value.

7. The method of claim 1, further comprising:

identifying a speed for the plurality of points in the location grid;

comparing the speed to a speed threshold; and

excluding at least one of the plurality of points when the corresponding speed exceeds the speed threshold.

8. The method of claim 1, further comprising:

storing the center of the roundabout road formation and a distance for the roundabout road formation in a geographic database.

9. The method of claim 1, further comprising:

providing routing from an origin to a destination through the roundabout road formation.

10. The method of claim 1, wherein the plurality of points in the probe data, after translating and aggregating, form a four-dimensional space.

11. The method of claim 10, wherein the four-dimensional space includes the heading, a radius, and two dimensions for the geographic location of the plurality of points.

12. The method of claim 1, further comprising:

determining a heading outlier quantity for a number of the plurality of points at a heading range and a distance range from the roundabout center of the road formation; and

comparing the heading outlier quantity to a heading outlier threshold.

13. The method of claim 12, further comprising:

selecting a new potential radius for the roundabout road formation when the heading outlier quantity exceeds the heading outlier threshold.

14. The method of claim 1, wherein multiple potential radius values area identified for the roundabout road formation, and the analysis selects one of multiple potential radius values.

15. The method of claim 14, further comprising:

receiving a user input for the multiple potential radius values for the roundabout road formation.

16. The method of claim 14, further comprising:

determining the multiple potential radius values for the roundabout road formation based on a statistical analysis of the plurality of points.

17. 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 at least perform;

receiving probe data for a geographic area;

identifying a plurality of points in the probe data, wherein each of the plurality of points includes a geographic location and a heading;

performing a plurality of translations on the plurality of points in the probe data in a predetermined direction orthogonal to the corresponding heading, wherein the plurality of translations are based on iterations of potential radius distances for a roundabout;

performing an analysis on the plurality of points in a grid according to the heading; and

identifying a center of the roundabout based on the analysis.

18. The apparatus of claim 17, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least perform:

selecting one of the potential radius distances based on the analysis.

19. The apparatus of claim 18, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least perform:

storing the one of the potential radius distances and the center of the roundabout in a map database.

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

receiving probe data for a geographic area;

identifying a plurality of points in the probe data, wherein each of the plurality of points includes a geographic location and a heading;

performing a first translation on the plurality of points in the probe data in a predetermined direction orthogonal to the corresponding heading at a first radius distance;

performing a second translation on the plurality of points in the probe data in the predetermined direction orthogonal to the corresponding heading at a second radius distance;

performing an analysis on the plurality of points in a grid according to the heading; and

selecting the first radius distance or the second radius for a roundabout based on the analysis.