Methods and systems for creating digital transportation networks

• US 9,222,786 B2
• Filed: 04/23/2010
• Issued: 12/29/2015
• Est. Priority Date: 05/04/2009
• Status: Active Grant

• Current Assignee: Tomtom Global Content B.V (TomTom NV)
• Original Assignee: Tomtom North America Incorporated (TomTom NV)
• Inventors: Witmer, James Alan
• Primary Examiner(s): Desta, Elias
• Application Number:
  US13/318,794
• Publication Number:
  US 20120116678A1
• Time in Patent Office: 2,076 Days
• US Class Current: 1/1
• 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/3881 Tile-based structures
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G09B 29/00 Maps; Plans; Charts; Diagrams, e.g. route diagram star maps G09B27/04; devices for holding or supporting maps A47B97/02; for computing purposes G06G1/14, G09B1/16; display boards G09F

Abstract

In a method for creating a digital representation of a transportation network, acquired probe traces are refined based on characteristics of the transportation network. Geographic objects associated with the transportation network are identified based on the refined probe traces. A digital geographic network is built based on the refined probe traces and identified geographic objects, and the digital representation of the transportation network is created by linking the identified geographic objects in the digital geographic network.

Claims

1. A method for creating a digital representation of a transportation network, the method comprising:

refining acquired probe traces based on characteristics of the transportation network, the probe traces being a plurality of sequential location measurements from a plurality of devices;

identifying geographic objects associated with the transportation network based on the refined probe traces;

building a digital geographic network based on the refined probe traces and identified geographic objects; and

creating the digital representation of the transportation network by linking the identified geographic objects in the digital geographic network.

2. The method of claim 1, further comprising:

clustering the refined probe traces based on a relative spatial proximity of associated geographic objects; and

wherein the building of the digital geographic network includes,

bundling, for each unique probe path in the transportation network, probe traces in each cluster representing measurements along a same probe path;

identifying and merging probe paths that intersect one another;

creating child probe paths by splitting probe paths at intersection points; and

building the geographic network based on the merged probe paths and child probe paths.

3. The method of claim 2, wherein the clustering of the refined probe traces comprises:

creating one of a spatial index and range-tree structure based on the refined probe traces.

4. The method of claim 2, wherein the unique probe path is a path traversed by one or more probe traces having the same beginning and end within a spatial threshold value and which does not deviate, in location, more than a threshold value from a reference probe trace.

5. The method of claim 2, wherein the bundling comprises:

identifying a reference probe trace for each bundle of probe traces, and

bundling, for each reference probe trace, probe traces that do not deviate more than a given distance from the reference probe trace.

6. The method of claim 2, wherein the identifying and merging comprises:

identifying intersecting centerline probe traces;

averaging a distance separating the centerline probe traces; and

merging probe paths based on the averaged distance.

7. The method of claim 2, wherein the clustering of the refined probe traces comprises:

generating a spatial index for the refined probe traces, the spatial index including a grid having a plurality of grid cells, each grid cell including a representation of a portion of the geographic objects of the transportation network.

8. The method of claim 7, wherein the creating comprises:

linking geographic objects to adjacent and coincident geographic objects in adjacent spatially indexed areas.

9. The method of claim 1, further comprising:

applying attribution to the geographic objects.

10. The method of claim 9, wherein the attribution includes at least one of direction of traffic flow, number of lanes in a multilane highway, turn restrictions;

average speed limits, stop signs, stop signals, elevation for polylines, and allowable vehicle types.

11. The method of claim 1, wherein the refining of probe traces includes at least one of curve smoothing, adjusting the positioning of probe traces depending on direction of traffic flow for road centerline capture, filtering probe traces not associated with a type of the transportation network, and segmenting probe traces at inferred intersections.

12. A system for creating a digital representation of a transportation network, the system comprising:

a geographic network generation module configured to,

refine acquired probe traces based on characteristics of the transportation network, the probe traces being a plurality of sequential location measurements from a plurality of devices,

identify geographic objects associated with the transportation network based on the refined probe traces, and

build a digital geographic network based on the refined probe traces and identified geographic objects; and

a digital transportation network generation module configured to create the digital representation of the transportation network by linking geographic objects among groups of geographic objects in the digital geographic network.

13. The system of claim 12, wherein the geographic network generation module is configured to,

cluster the refined probe traces based on a relative spatial proximity of associated geographic objects, and the digital transportation network generation is configured to,

bundle, for each unique probe path in the transportation network, probe traces in each group representing measurements along a same probe path,

identify and merge probe paths that intersect with one another,

create child probe paths by splitting probe paths at intersection points, and

generate the geographic network based on the merged probe paths and child probe paths.

14. The system of claim 13, wherein the geographic network generation module is configured to create one of a spatial index and range-tree structure based on the refined probe traces.

15. The system of claim 13, wherein the probe path is a path traversed by one or more probe traces having the same beginning and end within a spatial threshold value and which does not deviate, in location, more than a threshold value from a reference probe trace.

16. The system of claim 13, wherein the geographic network generation module is further configured to,

identify a reference probe trace for each bundle of probe traces, and

bundle, for each reference probe trace, probe traces that do not deviate more than a given distance from the reference probe trace.

17. The system of claim 13, wherein the geographic network generation module is further configured to,

identify intersecting centerline probe traces,

average a distance separating the centerline probe traces, and

merge the probe paths based on the averaged distance.

18. The system of claim 13, wherein the geographic network generation module is further configured to,

generate a spatial index for the refined probe traces, the spatial index including a grid having a plurality of grid cells, each grid cell including a representation of a portion of the geographic objects of the transportation network.

19. The system of claim 18, wherein the digital transportation network generation module is further configured to link geographic objects to adjacent and coincident geographic objects in adjacent spatially indexed areas.

20. The system of claim 12, wherein the digital transportation network generation module is further configured to apply attribution to the geographic objects.

21. The system of claim 20, wherein the attribution includes at least one of direction of traffic flow, number of lanes in a multilane highway, turn restrictions;

average speed limits, stop signs, stop signals, elevation for polylines, and allowable vehicle types.

22. The system of claim 12, wherein the geographic network generation module is further configured to refine probe traces by at least one of curve smoothing, adjusting the positioning of probe traces depending on direction of traffic flow for road centerline capture, filtering probe traces not associated with a type of the transportation network, and segmenting probe traces at inferred intersections.