Time and/or accuracy dependent weights for network generation in a digital map

• US 9,341,488 B2
• Filed: 12/23/2010
• Issued: 05/17/2016
• Est. Priority Date: 12/23/2009
• Status: Active Grant

• Current Assignee: Tomtom Global Content B.V (TomTom NV)
• Original Assignee: TomTom Germany Gmbh & Co. Kg. (TomTom NV), Tomtom North America Incorporated (TomTom NV)
• Inventors: Mund, Heiko, Morlock, Clayton Richard
• Primary Examiner(s): Drennan, Barry
• Assistant Examiner(s): HICKEY, DIANA S
• Application Number:
  US13/518,922
• Publication Number:
  US 20130021382A1
• Time in Patent Office: 1,972 Days
• Field of Search: None
• 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/3844 Data obtained from position sensors only, e.g. from inertial navigation

Abstract

A method for improving and extending an existing digital 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 map, then the data merged into the existing network using a time-dependent weight and/or accuracy-dependent weight. A recalculation date is established, and the weight value of a line segment and/or trace is adjusted as a function of the time span relative to the recalculation. The function may include setting a maximal time period divided into bins each having a respective weight reduction factor, or applying decay function. Through this technique, digital maps can be updated and extended without undue influence exerted by old trace data.

Claims

1. A method for generating, refining and/or extending a digital map using traces derived from probe data, said digital map storing a plurality of line segments spatially associated within a coordinate system, at least one, and preferably all, of the line segments having an associated segment weight value, the method comprising a computer performing the steps of:

providing at least one probe trace having a defined creation date;

assigning a trace weight value to the at least one probe trace;

adjusting the position of a line segment associated with the at least one probe trace based on the segment weight value of the line segment and the trace weight value;

adjusting at least one of the trace weight value and the segment weight value as a function of the time span between a recalculation date and the trace creation date, comprising;

dividing a maximal time period into a plurality of bins, each bin representing a respective portion of time between the recalculation date and the maximal time period;

assigning each bin a factor;

associating the trace with a specified one of the bins corresponding to the trace creation date; and

calculating the trace weight value as a function of the factor assigned to the bin associated with the trace;

removing a line segment from the digital map when a segment weight value of the line segment falls below a threshold.

2. The method of claim 1, wherein at least one, and preferably all, of the line segments have a computed centreline and the step of adjusting the position of a line segment comprises recalculating the centreline of the line segment, optionally using a weighted average of the segment and trace weight values.

3. The method of claim 1, wherein said step of adjusting the trace weight value and/or the segment weight value comprises reducing the trace weight value as a function of the time span between the recalculation date and the trace creation date.

4. The method of claim 1, wherein the segment weight value is calculated as a sum of the weights of the bins.

5. The method of claim 1, further comprising defining a half-life time (T) and a decay function, preferably an exponential decay function, and wherein said adjusting step includes computing at least one of the segment weight value and trace weight value as a function of the half-life time (T) and the decay function.

6. The method of claim 5, wherein said computing step includes altering the trace weight value and/or the segment weight value as a function of the half-life time (T) and the decay function.

7. The method of claim 1, wherein said step of assigning a trace weight value includes assigning an equal and common initial weight value to a plurality of traces having different respective creation dates.

8. The method of claim 1, wherein the digital map is a transportation network, and preferably the line segments represent at least a portion of a road.

9. The method of claim 1, wherein the predetermined threshold is zero or a value greater than zero.

10. The method of claim 1, wherein a predicted expiry date is determined for a line segment based on when the segment weight value will fall below a predetermined threshold value, and the line segment is removed from the digital map when the expiry date is reached.

11. The method of claim 10, wherein the predicted expiry date is adjusted, preferably extended, as additional probe traces associated with the line segment are provided.

12. The method of claim 1, wherein the trace weight value assigned to the at least one probe trace is based on at least one of accuracy and precision criteria of the acquisition system used to obtain the probe trace.

16. A non-transitory computer readable medium having computer software stored thereon, said computer software operable, when executed on a computer, to cause the computer to perform the method of claim 1.

13. A method for generating, refining and/or extending a digital map using traces derived from probe data, said digital map storing a plurality of line segments spatially associated within a coordinate system, at least one, and preferably all, of the line segments having an associated segment weight value, the method comprising a computer performing the steps of:

providing at least one probe trace having a defined creation date;

assigning a trace weight value to the at least one probe trace;

creating a line segment associated with the at least one probe trace;

assigning a segment weight value to the line segment based on the trace weight value;

adjusting at least one of the trace weight value and the segment weight value as a function of the time span between a recalculation date and the trace creation date, comprising;

dividing a maximal time period into a plurality of bins, each bin representing a respective portion of time between the recalculation date and the maximal time period;

assigning each bin a factor;

associating the trace with a specified one of the bins corresponding to the trace creation date;

calculating the trace weight value as a function of the factor assigned to the bin associated with the trace; and

removing a line segment from the digital map when a segment weight value of the line segment falls below a threshold.

14. The method of claim 13, wherein at least one, and preferably all, of the line segments have a computed centreline and the step of creating a line segment comprises calculating a centreline for the line segment.

15. The method of claim 13, wherein:

said step of providing at least one probe trace comprises providing a plurality of probe traces each having a different creation date; and

said step of assigning a trace weight value to the at least one probe trace comprises assigning the same trace weight value to each of the plurality of probe traces at the respective creation date of the probe trace.

17. A non-transitory computer readable medium having computer software stored thereon, said computer software operable, when executed on a computer, to cause the computer to perform the method of claim 13.