Probe based identification and validation of roundabout junctions

Patent metadata

Field	Value
Publication number	US-9672759-B2
Application number	US-201514708827-A
Country	US
Kind code	B2
Filing date	May 11, 2015
Priority date	May 11, 2015
Publication date	Jun 6, 2017
Grant date	Jun 6, 2017

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.

First claim

We claim:

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.

Assignees

• Here Global Bv

Inventors

• Hofmann Hilko
• Jehlicka Prokop

Classifications

• G01C21/32

  Structuring or formatting of map data · CPC title

• G09B29/003 Primary

  Maps · CPC title

• G01C21/20

  Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) · CPC title

• G09B29/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) · CPC title

• G01C21/3841 Primary

  Data obtained from two or more sources, e.g. probe vehicles · CPC title