Incremental map generation, refinement and extension with GPS traces

• US 10,001,378 B2
• Filed: 04/25/2016
• Issued: 06/19/2018
• Est. Priority Date: 10/22/2009
• Status: Active Grant

• Current Assignee: Tomtom Global Content B.V (TomTom NV)
• Original Assignee: Tomtom Global Content B.V (TomTom NV)
• Inventors: Mund, Heiko
• Primary Examiner(s): Tran, Khoi H
• Assistant Examiner(s): Wallace, Donald J
• Application Number:
  US15/137,534
• Publication Number:
  US 20160238396A1
• Time in Patent Office: 785 Days
• 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. A computer-implemented method for generating, refining and extending digital vector maps using GPS traces from probe data, comprising:

providing, by a processor, 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;

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

establishing, by the processor, a map matching criteria;

comparing, by the processor, 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, by the processor, 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, by the processor, the portion of the GPS trace containing matched probe data points to the respective line segment(s) of the digital vector map;

creating, by the processor, 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;

calculating a measure and an offset distance between each line segment and probe data points of the GPS trace;

searching along the GPS trace to determine a first probe data point having a highest measure and an offset distance to a last matched probe data point less than a predetermined maximum value;

comparing the measure of the first probe data point with a measure of a projected probe data point;

computing, by the processor, a split point based on the first probe data point when the measure of the first probe data point is larger than the measure of the projected probe data point;

splitting, by the processor, the digital vector map by providing a new node at the first probe data point; and

connecting, by the processor, the new node with a next node in the digital vector map.

2. The method of claim 1, wherein the measure is a length from a node to an orthogonal projection of a trace probe data point associated with the node.

3. The method of claim 1 further including simplifying the updated digital vector map.

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

5. The method of claim 1 wherein the digital vector map is a unidirectional network.

6. The method of claim 1 wherein the digital vector map is a bidirectional network.

7. The method of claim 1 further comprising computing attributes of the updated digital vector map.

8. The method of claim 7, wherein said computing attributes includes computing a road class of the line segments.

9. The method of claim 1 further comprising providing the digital vector map to one or more navigation systems to assist in at least one navigation service.

10. A non-transitory computer-readable medium which stores a set of instructions which when executed performs a method for generating, refining and extending digital vector maps using GPS traces from probe data, the method executed by the set of instructions comprising:

providing, by a processor, 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;

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

establishing, by the processor, a map matching criteria;

comparing, by the processor, 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, by the processor, 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, by the processor, the portion of the GPS trace containing matched probe data points to the respective line segment(s) of the digital vector map;

creating, by the processor, 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;

calculating a measure and an offset distance between each line segment and probe data points of the GPS trace;

searching along the GPS trace to determine a first probe data point having a highest measure and an offset distance to a last matched probe data point less than a predetermined maximum value;

comparing the measure of the first probe data point with a measure of a projected probe data point;

computing, by the processor, a split point based on the first probe data point when the measure of the first probe data point is larger than the measure of the projected probe data point;

splitting, by the processor, the digital vector map by providing a new node at the first probe data point; and

connecting, by the processor, the new node with the next node in the digital vector map.

11. The computer-readable medium of claim 10, wherein the measure is a length from a node to an orthogonal projection of a trace probe data point associated with the node.

12. The computer-readable medium of claim 10 further including simplifying the updated digital vector map.

13. The computer-readable medium of claim 10 wherein said step of simplifying the updated digital vector map includes applying the Douglas-Peucker algorithm.

14. The computer-readable medium of claim 10 wherein the digital vector map is a unidirectional network.

15. The computer-readable medium of claim 10 wherein the digital vector map is a bidirectional network.

16. The computer-readable medium of claim 10 further comprising computing attributes of the updated digital vector map.

17. The computer-readable medium of claim 16, wherein said computing attributes includes computing a road class of the line segments.

18. The computer-readable medium of claim 10 further comprising providing the digital vector map to one or more navigation systems to assist in at least one navigation service.