Method and apparatus for providing trajectory bundles for map data analysis

Patent metadata

Field	Value
Publication number	US-10359295-B2
Application number	US-201615259954-A
Country	US
Kind code	B2
Filing date	Sep 8, 2016
Priority date	Sep 8, 2016
Publication date	Jul 23, 2019
Grant date	Jul 23, 2019

Abstract

An approach is provided for generating trajectory bundles for map data analysis. The approach involves receiving probe data associated with the bounded geographic area. The probe data are collected from sensors of a plurality of devices traveling in the bounded geographic area, and includes probe points indicating a position, a heading, a speed, a time, or a combination thereof. The approach also involves constructing a plurality of trajectories from the probe points to represent respective movement paths of said each of the plurality of devices. The approach further involves computing similarities among a plurality of curves represented by the plurality of trajectories. The approach further involves clustering the plurality of trajectories into trajectory bundles based on the similarities with each bundle representing a possible maneuver within the bounded geographic area. The approach further involves generating a map of the bounded geographic area based on the trajectory bundles.

First claim

What is claimed is:

1. A method for generating map data to represent a bounded geographic area comprising:
receiving probe data associated with the bounded geographic area, wherein the probe data are collected from one or more sensors of a plurality of devices traveling in the bounded geographic area, and wherein the probe data include probe points indicating a position, a heading, a speed, a time, or a combination thereof of each of the plurality of devices;
constructing a plurality of trajectories from the probe points for said each of the plurality of devices, wherein the plurality of trajectories represents respective movement paths of said each of the plurality of devices within the bounded geographic area;
computing similarities among a plurality of curves represented by the plurality of trajectories;
clustering the plurality of trajectories into one or more trajectory bundles based on the similarities, wherein the one or more trajectory bundles respectively represent a possible maneuver within the bounded geographic area;
generating a map of the bounded geographic area based on the one or more trajectory bundles;
determining a subset of the one or more bundles that involve a problem maneuver;
determining a prevalence of the subset of the one or more bundles associated with the problem maneuver with respect to an entirety of the one or more bundles; and
designating the one or more geographic bounded areas, one or more map features within the one or more geographic bounded areas, or a combination thereof as a problematic area based on the prevalence.

2. The method of claim 1 , wherein the similarities among the plurality of curves are computed using a discrete Frechet distance, a dynamic time warping analysis, or a combination thereof.

3. The method of claim 1 , wherein the similarities among the plurality of curves are based on a curve shape without considering an underlying map topology.

4. The method of claim 1 , further comprising:
receiving an input specifying a geo-coordinate of an intersection or a highway interchange,
wherein the bounded geographic area is designated based on the geo-coordinate, and
wherein the possible maneuver is a maneuver through the intersection or the highway interchange.

5. The method of claim 1 , further comprising:
classifying the possible maneuver associated with the one or more trajectory bundles that have a trajectory count above a threshold value as a typical/allowed maneuver.

6. The method of claim 1 , further comprising:
classifying the possible maneuver associated with the one or more trajectory bundles that have a trajectory count below a threshold value as an atypical/non-allowed maneuver.

7. The method of claim 1 , further comprising:
constructing and clustering the plurality of trajectories into the one or more trajectory bundles over a time series; and
detecting changes in one or more traffic rules based on the one or more trajectory bundles classified over the time series.

8. The method of claim 1 , further comprising:
performing an analysis of a bundle topology of the one or more trajectory bundles with respect to a map topology determined from mapping data; and
detecting a point of interest in the geographic bounded area based on the analysis.

9. The method of claim 8 , further comprising:
determining a location along the bundle topology that does not follow the map topology; and
associating the location with the detected point of interest.

10. The method of claim 1 ,
wherein the problem maneuver includes a U-turn maneuver.

11. An apparatus for generating map data to represent a bounded geographic area 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 perform at least the following,
receive probe data associated with the bounded geographic area, wherein the probe data are collected from one or more sensors of a plurality of devices traveling in the bounded geographic area, and wherein the probe data include probe points indicating a position, a heading, a speed, a time, or a combination thereof of each of the plurality of devices;
construct a plurality of trajectories from the probe points for said each of the plurality of devices, wherein the plurality of trajectories represents respective movement paths of said each of the plurality of devices within the bounded geographic area;
compute similarities among a plurality of curves represented by the plurality of trajectories;
cluster the plurality of trajectories into one or more trajectory bundles based on the similarities, wherein the one or more trajectory bundles respectively represent a possible maneuver within the bounded geographic area;
generate a map of the bounded geographic area based on the one or more trajectory bundles;
determine a subset of the one or more bundles that involve a problem maneuver;
determine a prevalence of the subset of the one or more bundles associated with the problem maneuver with respect to an entirety of the one or more bundles; and
designate the one or more geographic bounded areas, one or more map features within the one or more geographic bounded areas, or a combination thereof as a problematic area based on the prevalence.

12. The apparatus of claim 11 , wherein the similarities among the plurality of curves are computed using a discrete Frechet distance, a dynamic time warping analysis, or a combination thereof.

13. The apparatus of claim 11 , wherein the similarities among the plurality of curves are based on a curve shape without considering an underlying map topology.

14. The apparatus of claim 11 , wherein the apparatus is further caused to:
receive an input specifying a geo-coordinate of an intersection or a highway interchange,
wherein the bounded geographic area is designated based on the geo-coordinate, and
wherein the possible maneuver is a maneuver through the intersection or the highway interchange.

15. The apparatus of claim 11 , wherein the apparatus is further caused to:
classify the possible maneuver associated with the one or more trajectory bundles that have a trajectory count above a threshold value as a typical/allowed maneuver; and
classify the possible maneuver associated with the one or more trajectory bundles that have a trajectory count below a threshold value as an atypical/non-allowed maneuver.

16. The apparatus of claim 11 , wherein the apparatus is further caused to:
perform an analysis of a bundle topology of the one or more trajectory bundles with respect to a map topology determined from mapping data; and
detect a point of interest in the geographic bounded area based on the analysis.

17. The apparatus of claim 11 , wherein the problem maneuver includes a U-turn maneuver.

18. A non-transitory computer-readable storage medium carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to at least perform the following steps:
receiving probe data associated with the bounded geographic area, wherein the probe data are collected from one or more sensors of a plurality of devices traveling in the bounded geographic area, and wherein the probe data include probe points indicating a position, a heading, a speed, a time, or a combination thereof of each of the plurality of devices;
constructing a plurality of trajectories from the probe points for said each of the plurality of

Assignees

• Here Global Bv

Inventors

• Stroila Matei
• Xu Bo
• Macfarlane Jane

Classifications

• G01C21/3446

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G01C21/3694 Primary

  Output thereof on a road map · CPC title

• G01C21/32

  Structuring or formatting of map data · CPC title

• G08G1/0141

  for traffic information dissemination · CPC title

• G08G1/0112

  from the vehicle, e.g. floating car data [FCD] · CPC title