INCREMENTAL MAP GENERATION, REFINEMENT AND EXTENSION WITH GPS TRACES

• US 20120277993A1
• Filed: 10/22/2009
• Published: 11/01/2012
• Est. Priority Date: 10/22/2009
• Status: Active Grant

• Current Assignee: Tomtom Global Content B.V (TomTom NV)
• Original Assignee: TomTom Germany Gmbh & Co. Kg. (TomTom NV)
• Inventors: Mund, Heiko
• Granted Patent: US 9,322,660 B2
• Time in Patent Office: Days
• US Class Current: 701/450
• CPC Class Codes: G01C 21/32 Structuring or formatting of map data
• CPC Class Codes: G01C 21/3811 Point data, e.g. Point of Interest [POI]
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G01C 21/3844 Data obtained from position sensors only, e.g. from inertial navigation
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

A method for improving and extending an existing road network and generating new networks from statistically relevant amounts of probe data recorded by GPS-enabled navigation devices. New probe data is matched to the existing digital vector map, then the data merged into the existing network using a weighted mean technique. When new roads are detected, appropriate junction points are made with the existing network elements. The updated network data is simplified to improve computing speed and reduce data storage requirements.

Claims

1. (canceled)

2. A method for generating, refining and extending digital vector maps using GPS traces from probe data, comprising the steps of:

providing a digital vector map having a plurality of nodes spatially associated within a coordinate system, each node having at least one line segment extending therefrom;

associating each line segment in the digital vector map with a weight value;

collecting at least one GPS trace from a plurality of sequentially transmitted probe data points;

establishing a map matching criteria;

comparing each probe data point along the GPS trace to at least one line segment in the digital vector map using the map matching criteria;

designating as “

matched”

each probe data point along the GPS trace that meets the map matching criteria while designating as “

unmatched”

each probe data point along the GPS trace that fails the map matching criteria;

associating the portion of the GPS trace containing matched probe data points to the respective line segment(s) of the digital vector map;

computing a centre-line between the respective line segment and the portion of the GPS trace containing matched probe data points using the weight value of the line segment;

replacing the line segment through the centre-line; and

creating a new line segment in the digital vector map with the portion of the GPS trace containing unmatched probe data points;

the method further comprising the steps of;

determining a split point based on the last matched probe data point and one of the nodes of the line segment of the digital vector map with which said last matched probe data point is associated;

splitting the digital vector map by providing a new node at this point; and

connecting the new node with the next node in the digital vector map.

9. The method of claim 2 further including simplifying the updated digital vector map.

10. The method of claim 2 wherein said step of simplifying the updated digital vector map includes applying the Douglas-Peucker algorithm.

11. The method of claim 2 wherein the digital vector map is a unidirectional network.

12. The method of claim 2 wherein the digital vector map is a bidirectional network.

13. The method of claim 2 further including the step of computing attributes of the updated digital vector map.

14. The method of claim 12, wherein said step of computing attributes includes computing a road class of the line segments.

15. The method of claim 2 further including removing line segments from the digital vector map which have a weight value below a predetermined threshold value in a post-processing operation.

3-8. -8. (canceled)