Seamless network generation

Patent metadata

Field	Value
Publication number	US-9599476-B2
Application number	US-201013977891-A
Country	US
Kind code	B2
Filing date	Dec 30, 2010
Priority date	Dec 30, 2010
Publication date	Mar 21, 2017
Grant date	Mar 21, 2017

Abstract

A system and method for generating a seamless road network of a large geographical area includes a plurality of GPS probe traces extending across a geographical area. The probe traces are divided into sub-sets base on criteria, such as accuracy. A plurality of threads simultaneously employ the sub-sets traces to generate an independent network of the entire geographical area. The networks generated using sub-sets having a high accuracy are preferred over networks generating using sub-sets having a lower accuracy. The independent networks are combined to form a seamless networks of road segments.

First claim

The invention claimed is:

1. A method of generating, revising, or extending a digital map, said digital map storing a plurality of line segments or features spatially associated within a coordinate system representing a network within a geographical area, comprising:
providing a plurality of probe traces extending across a geographical area, wherein the probe traces are a plurality of location measurements;
dividing the probe traces into a plurality of sub-sets, wherein each sub-set includes a plurality of probe traces having at least one criteria in common, the criteria being an accuracy of the probe traces or a quality of the probe traces;
employing probe traces of a first sub-set using a first processing thread to generate a first sub-network of line segments;
employing probe traces of a second sub-set using a second processing thread, while the first processing thread is employing the traces of the first sub-set, to generate a second sub-network of line segments; and
conflating at least said first and second sub-networks of line segments to generate a network of line segments associated with the geographical area, the conflating comprising:
using line segments from the first sub-network to generate the network of line segments for locations where the first sub-network is complete; and
using line segments from the second sub-network to generate the network of line segments for locations where the first sub-network is incomplete.

2. A method as set forth in claim 1 including conflating at least one of said first and second sub-networks of line segments with a pre-existing network of line segments of a digital map.

3. A method as set forth in claim 1 wherein an additional criteria is selected from the group consisting of: position of the probe traces, and timestamp of the probe traces.

4. A method as set forth in claim 1 including determining the accuracy of each of the probe traces, and said dividing includes dividing the probe traces into the sub-sets based on accuracy.

5. A method as set forth in claim 1 including associating the common criteria of each sub-set of probe traces with the sub-network of line segments generated using said sub-set of probe traces.

6. A method as set forth in claim 5 wherein said conflating includes conflating at least said first and second sub-networks of line segments based on the criteria associated with each sub-network.

7. A method as set forth in claim 1 including matching one or more line segments or features of a generated sub-network of a known accuracy with corresponding line segments or features of a pre-existing network of line segments of a digital map to verify the accuracy of the pre-existing network.

8. A method as set forth in claim 1 wherein the plurality of probe traces are provided simultaneously.

9. A method as set forth in claim 1 wherein said dividing includes distributing a predetermined number of probe traces to each of the sub-sets of probe traces.

10. A method as set forth in claim 1 wherein each processing thread employs each probe trace of one sub-set before employing a probe trace of another sub-set.

11. A method as set forth in claim 1 wherein each sub-set of probe traces is placed in a queue and each processing thread employs the probe traces of one sub-set of the queue before employing the probe traces of another sub-set of the queue.

12. A method as set forth in claim 1 , wherein the digital map is a transportation network, and wherein the line segments represent at least a portion of a road.

13. A system of generating, revising, or extending a digital map, said digital map storing a plurality of line segments or features spatially associated within a coordinate system representing a network within a geographical area, comprising:
means for receiving a plurality of probe traces extending across a geographical area, wherein the probe traces are a plurality of location measurements;
means for dividing the probe traces into a plurality of sub-sets, wherein each sub-set includes a plurality of probe traces having at least one criteria in common, the criteria being an accuracy of the probe traces or a quality of the probe traces;
one or more processing resources arranged to employ probe traces of a first sub-set using a first processing thread to generate a first sub-network of line segments and to employ probe traces of a second sub-set using a second processing thread, while the first processing thread is employing the traces of the first sub-set, to generate a second sub-network of line segments; and
means for conflating at least said first and second sub-networks of line segments to generate a network of line segments associated with the geographical area, the conflating comprising:
using line segments from the first sub-network to generate the network of line segments for locations where the first sub-network is complete; and
using line segments from the second sub-network to generate the network of line segments for locations where the first sub-network is incomplete.

14. A system as set forth in claim 13 wherein an additional criteria is selected from the group consisting of: position of the probe traces, and timestamp of the probe traces.

15. A system as set forth in claim 13 , wherein the criteria is the accuracy of each of the probe traces, and said means for dividing the probe traces into a plurality of sub-sets is arranged to divide the probe traces into the sub-sets based on accuracy.

Assignees

• Mund Heiko
• Scharmann Hannes
• Tomtom Global Content Bv

Inventors

• Mund Heiko
• Scharmann Hannes

Classifications

• G09B29/106 Primary

  using electronic means · CPC title

• G01C21/26 Primary

  specially adapted for navigation in a road network · CPC title

• G01C21/32

  Structuring or formatting of map data · CPC title

• G01C21/3844

  Data obtained from position sensors only, e.g. from inertial navigation · CPC title

• G01C21/3815

  Road data · CPC title