Trail interpolation

• US 10,337,869 B2
• Filed: 05/26/2015
• Issued: 07/02/2019
• Est. Priority Date: 06/03/2014
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Jehlicka, Prokop, Rolf, Daniel, Hofmann, Hilko, Karge, Bjorn
• Primary Examiner(s): Black, Thomas G
• Assistant Examiner(s): Kong, Sze-Hon
• Application Number:
  US15/315,899
• Publication Number:
  US 20170089707A1
• Time in Patent Office: 1,498 Days
• CPC Class Codes: G01C 21/14 by recording the course traversed by the object G01C21/16 takes precedence
• CPC Class Codes: G01C 21/16 by integrating acceleration or speed, i.e. inertial navigation
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/3819 Road shape data, e.g. outline of a route
• CPC Class Codes: G08G 1/0112 from the vehicle, e.g. floating car data [FCD]

Abstract

A method comprising: collecting a plurality of probe data from a plurality of probe points by a probing device, said probe data comprising at least positional information, a speed vector and a direction of travel of the probing device and a timestamp of recording the probe data at a probe point; and estimating a trajectory of the probing device between two consecutive probe points as a cubic Hermite spline having the positions of said two consecutive probe points as control points and the speed vectors of said two consecutive probe points as control vectors.

Claims

1. A method comprising:

collecting a plurality of probe data from a plurality of probe points by a probing device of a navigation device moving along at least one road segment, said probe data comprising at least positional information, a speed vector and a direction of travel of the probing device and a timestamp of recording the probe data at a probe point, wherein for said probe points at a recording time of the probe data, the speed vector of the probing device corresponds to a continuous first derivative of a trajectory of the probing device and acceleration of the probing device corresponds to a second derivative of the trajectory of the probing device with the second derivative having a continuous value;

estimating a trajectory of the probing device between two consecutive probe points by determining a data set representing an estimate of an actual trajectory of the probing device on the basis of two or more consecutive probe points fulfilling a requirement of continuous values for the first and second derivatives of the trajectory of the probing device and applying a polynomial interpolation of at least degree of five on said data set;

providing a digital map comprising the at least one road segment; and

displaying the estimated trajectory of the probing device of the navigation device along with the digital map on a display of the navigation device.

2. The method according to claim 1, wherein:

jerk of the probing device is corresponded to a third derivative of the trajectory of the probing device, the third derivative having a continuous value.

3. The method according to claim 1, the method further comprising:

applying a further optimization method for the data set.

4. The method according to claim 3, wherein the optimization method comprises at least one of steepest gradient descent or simulated annealing.

5. The method according to claim 3, wherein the optimization method comprises reparametrizing the trajectory with a stopover profile.

6. The method according to claim 1, further comprising

calculating time, speed and/or distance information regarding the positional information and/or motion of the navigation device.

7. The method according to claim 1 further comprising applying an optimization method for the data set in which a duration of a probe data interval serves as a degree of freedom for the optimization method and a variance of the speed of the estimated trajectory is defined as a cost function of the optimization method.

8. The method according to claim 1 further comprising re-parameterizing the estimated trajectory in accordance with a stopover profile function that first reduces a traversal speed to zero and then maintains the traversal speed at zero for a period of time prior to increasing the traversal speed again to an original speed.

9. The method according to claim 1 wherein the estimated trajectory of the probing device is illustrated on the digital map on the display of the navigation device.

10. An apparatus comprising at least one processor, memory including computer program code, and a probing device of a navigation device, the memory and the computer program code being configured to, with the at least one processor, cause the apparatus to at least:

collect a plurality of probe data from a plurality of probe points by said probing device of the navigation device moving along at least one road segment, said probe data comprising at least positional information, a speed vector and a direction of travel of the probing device and a timestamp of recording the probe data at a probe point, wherein for said probe points at a recording time of the probe data, the speed vector of the probing device corresponds to a continuous first derivative of a trajectory of the probing device and acceleration of the probing device corresponds to a second derivative of the trajectory of the probing device with the second derivative having a continuous value;

estimate a trajectory of the probing device between two consecutive probe points by determining a data set representing an estimate of an actual trajectory of the probing device on the basis of two or more consecutive probe points fulfilling a requirement of continuous values for the first and second derivatives of the trajectory of the probing device and applying a polynomial interpolation of at least degree of five on said data set;

provide a digital map comprising the at least one road segment; and

display the estimated trajectory of the probing device of the navigation device along with the digital map on a display of the navigation device.

11. The apparatus according to claim 10, wherein:

jerk of the probing device is configured to correspond to a third derivative of the trajectory of the probing device, the third derivative having a continuous value.

12. The apparatus according to claim 10, the memory and the computer program code being configured to, with the at least one processor, cause the apparatus to at least:

apply a further optimization method for the data set.

13. The apparatus according to claim 12, wherein the optimization method comprises at least one of steepest gradient descent or simulated annealing.

14. The apparatus according to claim 12, wherein the optimization method comprises reparametrizing the trajectory with a stopover profile.

15. The apparatus according to claim 10, wherein the memory and the computer program code being configured to, with the at least one processor, cause the apparatus to at least:

calculate time, speed and/or distance information regarding the positional information and/or motion of the navigation device.

16. The apparatus according to claim 10 wherein the memory and the computer program code are further configured to, with the at least one processor, cause the apparatus to apply an optimization method for the data set in which a duration of a probe data interval serves as a degree of freedom for the optimization method and a variance of the speed of the estimated trajectory is defined as a cost function of the optimization method.

17. The apparatus according to claim 10 wherein the memory and the computer program code are further configured to, with the at least one processor, cause the apparatus to re-parameterize the estimated trajectory in accordance with a stopover profile function that first reduces a traversal speed to zero and then maintains the traversal speed at zero for a period of time prior to increasing the traversal speed again to an original speed.

18. A non-transitory computer readable storage medium stored with code thereon for use by an apparatus, which when executed by a processor, causes the apparatus to perform:

collecting a plurality of probe data from a plurality of probe points by a probing device of a navigation device moving along at least one road segment, said probe data comprising at least positional information, a speed vector and a direction of travel of the probing device and a timestamp of recording the probe data at a probe point, wherein for said probe points at a recording time of the probe data, the speed vector of the probing device corresponds to a continuous first derivative of a trajectory of the probing device and acceleration of the probing device corresponds to a second derivative of the trajectory of the probing device with the second derivative having a continuous value;

estimating a trajectory of the probing device between two consecutive probe points by determining a data set representing an estimate of an actual trajectory of the probing device on the basis of two or more consecutive probe points fulfilling a requirement of continuous values for the first and second derivatives of the trajectory of the probing device and applying a polynomial interpolation of at least degree of five on said data set;

providing a digital map comprising the at least one road segment; and

displaying the estimated trajectory of the probing device of the navigation device along with the digital map on a display of the navigation device.

19. The computer readable storage medium according to claim 18 wherein the code, when executed by a processor, causes the apparatus to additionally perform applying an optimization method for the data set in which a duration of a probe data interval serves as a degree of freedom for the optimization method and a variance of the speed of the estimated trajectory is defined as a cost function of the optimization method.

20. The computer readable storage medium according to claim 18 wherein the code, when executed by a processor, causes the apparatus to additionally perform re-parameterizing the estimated trajectory in accordance with a stopover profile function that first reduces a traversal speed to zero and then maintains the traversal speed at zero for a period of time prior to increasing the traversal speed again to an original speed.