System and method for roundabouts from probe data using vector fields

• US 9,766,081 B2
• Filed: 05/12/2015
• Issued: 09/19/2017
• Est. Priority Date: 05/12/2015
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Dorum, Ole Henry
• Primary Examiner(s): Olszewski, John R
• Assistant Examiner(s): McPherson, James M
• Application Number:
  US14/710,193
• Publication Number:
  US 20160335887A1
• Time in Patent Office: 861 Days
• Field of Search: None
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/3822 Road feature data, e.g. slope data
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G08G 1/0112 from the vehicle, e.g. floating car data [FCD]
• CPC Class Codes: G08G 1/0129 for creating historical data or processing based on historical data
• CPC Class Codes: G08G 1/0141 for traffic information dissemination

Abstract

A computing device may detect roundabouts and other road features from probe data including probe heading information. The computing device may model the probe data as vector points in vector fields and perform vector field fitting on a subset of the probe data vectors to identify circulation in the vector fields. The computing device uses the circulation in the vector fields to detect the location of a roundabout or other road feature.

Claims

1. A method comprising:

identifying, using a processor, a potential roundabout location from a plurality of probe data points received from a plurality of mobile devices, wherein each of the plurality of probe data points is represented by a location, a heading vector and a velocity;

selecting, using the processor, a subset of the plurality of probe data points for the potential roundabout location;

normalizing, using the processor, a vector length of the selected subset of the plurality of probe data points;

performing, using the processor, a vector fit for the subset of the plurality of probe data points;

detecting a roundabout location from the vector fit, and

updating a geographic database based on the roundabout location.

2. The method of claim 1, wherein identifying a potential roundabout location comprises identifying locations where probe data points merge or intersect.

3. The method of claim 1, wherein identifying a potential roundabout location comprises identifying locations where probe data points bifurcate.

4. The method of claim 1, wherein a location of each of the plurality of probe data points represents a longitude and a latitude.

5. The method of claim 1, wherein the heading vector of each of the plurality of probe data points represents a heading direction of the probe.

6. The method of claim 5, wherein the subset of the plurality of probe data points excludes at least one probe data point with a velocity less than a threshold.

7. The method of claim 1, wherein the vector fit includes a least squares vector field fit to the subset of the plurality of probe data points.

8. The method of claim 7, wherein the vector field fit comprises a bivariate cubic polynomial.

9. The method of claim 1, further comprising:

determining, using the processor, a circular singularity for the vector fit; and

determining, using the processor, a direction of flow for the circular singularity, wherein the roundabout location is determined from the direction of flow and the circular singularity.

10. The method of claim 9 further comprising:

determining, using the processor, a roundabout center location and a radius for a vicinity of the circular singularity.

11. The method of claim 10, wherein the roundabout center location and the radius is determined from iteratively varying an estimated roundabout center location and an estimated radius in the vicinity of the circular singularity.

12. The method of claim 11, wherein determining the roundabout center location and the radius comprises performing a least median of squares technique, the least median of squares technique comprising:

computing median squared residual values for the plurality of probe data points with respect to an estimated circle formed using the estimated roundabout center location and the estimated radius; and

selecting the roundabout center location and the radius for which the median squared residual values is minimized.

13. The method of claim 10 further comprising:

determining, using the processor, a standard deviation of the subset of the plurality of probe data points to the roundabout center location and the radius.

14. 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;

identifying a potential roundabout location from a plurality of probe data points, wherein each of the plurality of probe data points is represented by a location, a heading vector and a velocity;

selecting a subset of the plurality of probe data points for the potential roundabout location;

normalizing a vector length of the selected subset of the plurality of probe data points;

performing a vector fit for the subset of the plurality of probe data points;

determining a circular singularity for the vector fit;

determining a direction of flow for the circular singularity;

determining a roundabout center location and a radius for the in a vicinity of the circular singularity,

updating a geographic database based on the roundabout center location and the radius, and

providing a navigation system update for a mobile device based on the updated geographic database.

15. The apparatus of claim 14, wherein identifying a potential roundabout location comprise identifying locations where probe data points merge, intersect or bifurcate.

16. The apparatus of claim 14, wherein selecting a subset of the plurality of probe data points excludes probe data points with substantially zero velocity.

17. The apparatus of claim 14, wherein performing the vector fit comprises preforming a least squares vector field fit to the subset of the plurality of probe data points.

18. The apparatus of claim 14, wherein determining the roundabout center location and the radius comprises performing a least median of squares technique, the least median of squares technique comprising:

iteratively varying a roundabout center location and a roundabout radius in the vicinity of the circular singularity;

computing the median squared residual value for the plurality of probe data points with respect to varied roundabout center location and the varied radius; and

selecting the roundabout center location and the radius for which the median squared residual is least.

19. The apparatus of claim 14, wherein 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:

determining a standard deviation of the subset of the plurality of probe data points to the roundabout center location and the radius.

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

select a potential roundabout location from a plurality of probe data points, wherein each of the plurality of probe data points is represented by a location, a heading vector and a velocity;

select a subset of the plurality of probe data points for the potential roundabout location;

perform a vector fit for the subset of the plurality of probe data points;

determine a circular singularity for the vector fit;

determine a direction of flow for the circular singularity;

determine a roundabout center location and a radius for the circular singularity;

update a geographic database based on the roundabout center location and the radius; and

providing a route to a user based on the updated geographic database.

21. The non-transitory computer readable medium of claim 20, wherein performing the vector fit comprises preforming a least squares vector field fit to the subset of the plurality of probe data points.

22. The non-transitory computer readable medium of claim 20 including instructions that when executed are operable to:

determine a standard deviation of the subset of the plurality of probe data points to the radius.