Road geometry generation from sparse data

Abstract

Road geometries may be determined from sparse data by identifying a set of mobile device data points generated by a mobile device located in a geographic area. Further, the data points may be connected with a curve comprising a series of splines defined by curve functions. The shape of the splines may be optimized by applying a scaling factor to the curve functions. A resulting optimized curve may be representative of a road in a geographic area.

I claim: 
     
       1. A method comprising:
 identifying, by a processor, a set of mobile device data points generated by at least one sensor of a vehicle traveling along a path from a plurality of mobile device data points, the set of mobile device data points indicating a position of the vehicle, a heading of the vehicle, and a speed of the vehicle at particular times while traveling a road; 
 filtering the plurality of mobile device points to remove invalid data points, wherein a data point is determined invalid when a time difference between temporally sequential data points is larger than a specified value; 
 connecting, by the processor, the set of mobile device data points with a curve comprising a series of splines defined by curve functions using parameters derived from the position, the heading, and the speed for the plurality of mobile device data points; 
 optimizing, by the processor, the curve by applying at least one scaling factor to the parameters, wherein optimizing comprises more closely approximating the path of the vehicle; 
 associating, by the processor, the optimized curve with the road; 
 storing an association between the optimized curve and the road in a geographic database stored in a memory; 
 generating a road geometry map wherein the road in the geometry map is represented by the optimized curve; and 
 providing for autonomous control of a subsequent vehicle along the optimized curve. 
 
     
     
       2. The method of  claim 1 , wherein the curve functions can be represented as:
     p ( t )=(2 t   3 −3 t   2 +1) p   0 +( t   3 −2 t   2   +t ) m   0 +(−2 t   3 +3 t   2 ) p   1 +( t   3   −t   2 ) m   1  
 
 where t is a given spline variable; 
 p(t) is a position at the given spline variable t; 
 p 0  is an initial position of a spline indicated by the first mobile device data point; 
 p 1  is an ending position of the spline indicated by the second mobile device data point; 
 m 0  is a heading parameter determined for the first mobile device data point; and 
 m 1  is a heading parameter determined for the second mobile device data point. 
 
     
     
       3. The method of  claim 2 , wherein the heading parameters are determined according to:
     m=Δt   1-0   ×v    
 where Δt 1-0  is a difference in time between the second particular time and the first particular time; and 
 v is the speed associated with the first or the second mobile data point respectively. 
 
     
     
       4. The method of  claim 1 , wherein a data point is determined invalid when a speed associated with the data point is below a minimum speed threshold. 
     
     
       5. The method of  claim 1 , wherein a data point is determined invalid when a speed required for the vehicle to travel between associated locations of the data point and a temporally sequential data point is larger than a maximum speed threshold. 
     
     
       6. The method of  claim 1 , wherein the optimizing comprises:
 iteratively applying scaling factors from an established range of scaling factors; and 
 selecting the at least one scaling factor that includes a maximum number of data points within a specified distance of an optimized curve resulting from application of the scaling factors. 
 
     
     
       7. The method of  claim 1 , further comprising:
 generating a plurality of optimized curves for other sets of mobile data points from the plurality of mobile device data points; and 
 producing a merged curve representative of the road geometry based on the plurality of curves. 
 
     
     
       8. The method of  claim 1 , further comprising: using the generated road geometry map and the optimized curve for autonomous vehicle guidance. 
     
     
       9. The method of  claim 1 , wherein the at least one sensor comprises a location sensor and at least one of a magnetic sensor or accelerometer, wherein the position of the vehicle is obtained from a location sensor and wherein the heading of the vehicle is obtained from the at least one of a magnetic sensor or accelerometer. 
     
     
       10. The method of  claim 1 , wherein the data representing the road network comprises at least a road segment and at least two node points; and
 wherein the road segment represents a section of the road between the two node points and the two node points indicate a start and an end point of the road segment or an intersection of two or more road segments. 
 
     
     
       11. An apparatus comprising:
 at least one processor; and 
 at least one memory including computer program code and operable to store a plurality of data points associated with a vehicle, the plurality of data points generated by a mobile device at particular times while traveling a road; 
 the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus at least to: 
 identify the plurality of mobile device data points generated by at least one sensor of a vehicle traveling along a path from a plurality of mobile device data points, the set of mobile device data points indicating a position of the vehicle, a heading of the vehicle, and a speed of the vehicle at particular times while traveling a road; 
 filter the plurality of mobile device data points to remove invalid data points, wherein a data point is determined invalid when a time difference between temporally sequential data points is larger than a specified value; 
 connect the plurality of mobile device data points with a curve comprising a series of splines defined by curve functions using mobile device data generated by the mobile device, wherein the curve functions are represented as:
     p ( t )=(2 t   3 −3 t   2 +1) p   0 +( t   3 −2 t   2   +t ) m   0 +(−2 t   3 +3 t   2 ) p   1 +( t   3   −t   2 ) m   1  
 
 
 where t is a given incremental spline variable where t is zero (0) at a first mobile device data point and t is one (1) at a second mobile device data point; 
 p(t) is a position at the given spline parameter t; 
 p 0  is an initial position of a spline indicated by the first data point; 
 p 1  is an ending position of the spline indicated by the second data point; 
 m 0  is a heading determined for the first data point; and 
 m 1  is a heading determined for the second data point; 
 optimize the shape of the splines by applying a scaling factor to the curve functions, wherein optimizing the shape of the splines comprises more closely approximating a path of the vehicle; 
 associate the optimized curve with the road; 
 store an association between the optimized curve and the road in a geographic database stored in the at least one memory; 
 generate a road geometry map wherein the road in the geometry map is represented by the optimized curve; and 
 provide for guidance of a vehicle along the optimized curve. 
 
     
     
       12. The apparatus of  claim 11 , wherein the headings are determined according to:
     m=Δt   1-0   ×v    
 where Δt 1-0  is a difference in time between the second particular time and the first particular time; and 
 v is the speed associated with the first point or the second data point respectively. 
 
     
     
       13. The apparatus of  claim 11 , wherein the at least one memory and the computer program code further configured to, with the at least one processor, cause the apparatus at least to:
 filter a collection of data points to remove invalid data points; and 
 connect the filtered data points with the curve. 
 
     
     
       14. The apparatus of  claim 13 , wherein a data point is determined invalid when a time difference between temporally sequential data points is larger than a specified value. 
     
     
       15. The apparatus of  claim 13 , wherein a data point is determined invalid when a speed associated with the data point is below a minimum speed threshold. 
     
     
       16. A non-transitory computer readable medium including instructions that when executed on a computer are operable to:
 identify a plurality of mobile device data points generated by at least one sensor of a vehicle traveling along a path from a plurality of mobile device data points, the set of mobile device data points indicating a position of the vehicle, a heading of the vehicle, and a speed of the vehicle at particular times while traveling a road; 
 filter the plurality of mobile device data points to remove invalid data points, wherein a data point is determined invalid when a speed associated with the data point is below a minimum speed threshold; 
 connect the plurality of mobile device data points with a curve comprising a series of cubic Hermite splines defined by curve functions; 
 optimize the shape of the splines by applying at least one scaling factor to the curve functions, wherein optimizing comprises more closely approximating a path of the mobile device; 
 associate the optimized curve with a path in the geographic area; 
 store an association between the optimized curve and the road in a geographic database stored in a memory; 
 generate a road geometry map wherein the road in the geometry map is represented by the optimized curve; and 
 provide for guidance of a vehicle along the optimized curve. 
 
     
     
       17. The medium of  claim 16 , wherein the instructions are further configured to:
 generate a plurality of curves from a plurality of sets of mobile device data points; and 
 merge the plurality of curves into a single curve representative of the path. 
 
     
     
       18. The medium of  claim 16 , wherein the instructions are further configured to:
 iteratively apply scaling factors from an established range of scaling factors; and 
 select the at least one scaling factor that includes a maximum number of data points within a specified distance of an optimized curve resulting from application of the scaling factors.