Method and apparatus for providing trajectory bundles for map data analysis

• US 10,359,295 B2
• Filed: 09/08/2016
• Issued: 07/23/2019
• Est. Priority Date: 09/08/2016
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Stroila, Matei, Xu, Bo, Macfarlane, Jane
• Primary Examiner(s): Ingram, Thomas
• Application Number:
  US15/259,954
• Publication Number:
  US 20180066957A1
• Time in Patent Office: 1,048 Days
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3694 Output thereof on a road map
• CPC Class Codes: G01C 21/3811 Point data, e.g. Point of Interest [POI]
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G01C 21/3852 Data derived from aerial or satellite images
• CPC Class Codes: G01C 21/387 Organisation of map data, e.g. version management or database structures
• 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

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.

Claims

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

19. The non-transitory computer-readable storage medium of claim 18, wherein the apparatus is further caused to perform:

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.

20. The non-transitory computer-readable storage medium of claim 19, wherein the problem maneuver includes a U-turn maneuver.