Method of processing positioning data

• US 10,024,676 B2
• Filed: 10/22/2008
• Issued: 07/17/2018
• Est. Priority Date: 10/26/2007
• Status: Active Grant

• Current Assignee: TomTom Traffic B.V. (TomTom NV)
• Original Assignee: TomTom Traffic B.V. (TomTom NV)
• Inventors: Hilbrandie, Geert, Schafer, Ralf-Peter, Mieth, Peter, Atkinson, Ian Malcom, Wolf, Martin, Rutten, Ben
• Primary Examiner(s): Cass, Jean Paul
• Application Number:
  US12/734,253
• Publication Number:
  US 20100312472A1
• Time in Patent Office: 3,555 Days
• Field of Search: None
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G01C 21/3844 Data obtained from position sensors only, e.g. from inertial navigation
• CPC Class Codes: G08G 1/0104 Measuring and analyzing of parameters relative to traffic conditions
• CPC Class Codes: G08G 1/0129 for creating historical data or processing based on historical data
• CPC Class Codes: G08G 1/052 with provision for determining speed or overspeed speed measuring in general G01P
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data
• CPC Class Codes: G08G 1/096888 where input information is obtained using learning systems, e.g. history databases

Abstract

A method of creating map data is disclosed, the map data including a plurality of navigable segments representing segments of a navigable route in the area covered by the map with each segment being arranged to have speed data associated therewith. In at least one embodiment, the method includes processing speed data relating to a plurality of the segments of the navigable route covered by the map to generate a set of generated speed profiles, with each generated speed profile within the set being an approximation to traffic speed along one or more of the segments of the navigable route and each speed profile varying with respect to time; and associating at least one speed profile from the set with a navigable segment within the map data.

Claims

1. A computer implemented method of creating map data for a map, the map comprising a plurality of navigable segments, with each navigable segment having speed data associated therewith, wherein said speed data comprises a plurality of average speeds at which devices travelled along the segment represented by the navigable segment of the map, and wherein said speed data is grouped into a plurality of predetermined time periods over a period of time, the method comprising:

processing the speed data to determine a measured speed profile for each of the plurality of navigable segments, said processing comprising averaging the average speeds within each of the plurality of time periods, such that the measured speed profile comprises a representation of the variation in traffic speed along the segment represented by the navigable segment of the map over the period of time;

generating, based on the measured speed profiles, a set of generated speed profiles, the generating comprising processing the measured speed profiles using a clustering technique to identify similarities between the measured speed profiles, wherein each generated speed profile of the set of generated speed profiles is a representation of a variation in traffic speed over the period of time that is configured to be used to indicate a speed profile of any navigable segment having a sufficiently close measured speed profile;

separately comparing the measured speed profile for each of the plurality of navigable segments to the set of generated speed profiles to determine which of the generated speed profiles is closest to that measured speed profile;

associating, based on the comparing, one of the generated speed profiles from the set of generated speed profiles with each of the plurality of navigable segments;

generating a map using the map data, such that the map comprises the set of generated speed profiles and, for each navigable segment, an identifier providing a reference to the associated one of the generated speed profiles; and

providing, to a remote device, the map comprising the set of generated speed profiles and the identifiers for each navigable segment that indicate the associated one of the generated speed profiles.

2. The method of claim 1, which comprises modifying the measured speed profile to replace a portion thereof with modified values for the average speeds for one or more of the predetermined time periods.

3. The method of claim 1, in which the measured speed profiles are normalised using a normalisation criteria before the generated speed profiles are generated.

4. The method of claim 3, in which the measured speed profiles are normalised using one of:

a free flow speed;

an average speed; and

a speed limit, for the respective navigable segment.

5. The method of claim 3, in which the speed data associated with each segment in the generated map further comprises the normalisation criteria.

6. The method of claim 1, further comprising adding at least one flat line speed profile to the set of generated speed profiles, the flat line speed profile not varying with respect to time.

9. The method of claim 2, further comprising using an average of the average speeds as the modified value for each of the predetermined time periods within the replaced portion.

7. A machine arranged to create map data for a map, the map comprising a plurality of navigable segments, with each navigable segment having speed data associated therewith, wherein said speed data comprises a plurality of average speeds at which devices travelled along the segment represented by the navigable segment of the map, and wherein said speed data is grouped into a plurality of predetermined time periods over a period of time, the machine being arranged to:

process the speed data to determine a measured speed profile for each of the plurality of navigable segments, said processing comprising averaging the average speeds within each of the plurality of time periods, such that the measured speed profile comprises a representation of the variation in traffic speed along the segment represented by the navigable segment of the map over the period of time;

generate, based on the measured speed profiles, a set of generated speed profiles, the generating comprising processing the measured speed profiles using a clustering technique to identify similarities between the measured speed profiles, wherein each generated speed profile of the set of generated speed profiles is a representation of a variation in traffic speed over the period of time that is configured to be used to indicate a speed profile of any navigable segment having a sufficiently close measured speed profile;

separately compare the measured speed profile for each of the plurality of navigable segments to the set of generated speed profiles to determine which of the generated speed profiles is closest to that measured speed profile;

associate, based on the comparing, one of the generated speed profiles from the set of generated speed profiles with each of the plurality of navigable segments;

generate a map using the map data, such that the map comprises the set of generated speed profiles and, for each navigable segment, an identifier providing a reference to the associated one of the generated speed profiles; and

providing, to a remote device, the map comprising the set of generated speed profiles and the identifiers for each navigable segment that indicate the associated one of the generated speed profiles.

10. The machine of claim 7, wherein the machine is further arranged to modify the measured speed profile to replace a portion thereof with modified values for the average speeds for one or more of the predetermined time periods.

11. The machine of claim 10, wherein the machine is further arranged to use an average of the average speeds as the modified value for each of the predetermined time periods within the replaced portion.

12. The machine of claim 7, wherein the machine is further arranged to normalise the measured speed profiles using a normalisation criteria before the generated speed profiles are generated.

13. The machine of claim 12, wherein the measured speed profiles are normalised using one of:

a free flow speed;

an average speed; and

a speed limit, for the respective navigable segment.

14. The machine of claim 12, wherein the speed data associated with each segment in the generated map further comprises the normalisation criteria.

15. The machine of claim 7, wherein the machine is further arranged to add at least one flat line speed profile to the set of generated speed profiles, the flat line speed profile not varying with respect to time.

8. A machine readable medium containing instructions which, when processed by a machine, cause the machine to perform a method of creating map data for a map, the map comprising a plurality of navigable segments, with each navigable segment having speed data associated therewith, wherein said speed data comprises a plurality of average speeds at which devices travelled along the segment represented by the navigable segment of the map, and wherein said speed data is grouped into a plurality of predetermined time periods over a period of time, the method comprising:

processing the speed data to determine a measured speed profile for each of the plurality of navigable segments, said processing comprising averaging the average speeds within each of the plurality of time periods, such that the measured speed profile comprises a representation of the variation in traffic speed along the segment represented by the navigable segment of the map over the period of time;

generating, based on the measured speed profiles, a set of generated speed profiles, the generating comprising processing the measured speed profiles using a clustering technique to identify similarities between the measured speed profiles, wherein each generated speed profile of the set of generated speed profiles is a representation of a variation in traffic speed over the period of time that is configured to be used to indicate a speed profile of any navigable segment having a sufficiently close measured speed profile;

separately comparing the measured speed profile for each of the plurality of navigable segments to the set of generated speed profiles to determine which of the generated speed profiles is closest to that measured speed profile;

associating, based on the comparing, one of the generated speed profiles from the set with each of the plurality of navigable segments within the map;

generating a map using the map data, such that the map comprises the set of generated speed profiles and, for each navigable segment, an identifier providing a reference to the associated one of the generated speed profiles; and

providing, to a remote device, the map comprising the set of generated speed profiles and the identifiers for each navigable segment that indicate the associated one of the generated speed profiles.

16. The machine readable medium of claim 8, wherein the method further comprises modifying the measured speed profile to replace a portion thereof with modified values for the average speeds for one or more of the predetermined time periods.

17. The machine readable medium of claim 16, wherein the method further comprises using an average of the average speeds as the modified value for each of the predetermined time periods within the replaced portion.

18. The machine readable medium of claim 8, wherein the method further comprises normalising the measured speed profiles using a normalisation criteria before the generated speed profiles are generated.

19. The machine readable medium of claim 18, wherein the measured speed profiles are normalised using one of:

a free flow speed;

an average speed; and

a speed limit, for the respective navigable segment.

20. The machine readable medium of claim 18, wherein the speed data associated with each segment in the generated map further comprises the normalisation criteria.

21. The machine readable medium of claim 8, wherein the method further comprises adding at least one flat line speed profile to the set of generated speed profiles, the flat line speed profile not varying with respect to time.