Method and apparatus for defining road geometry from probe data

Abstract

A method, apparatus and computer program product are provided in order to define the road geometry based upon a plurality of probe points. In the context of a method, a seed point is determined that is representative of one or more probe points. The method determines the seed point by determining a weighted center of mass of the one or more probe points. The method also includes determining an orientation representative of one or more probe points proximate the seed point and creating a polyline representative of the road geometry. In this regard, the method creates the polyline by extending the polyline in the orientation from the seed point.

That which is claimed: 
     
       1. A method comprising:
 defining a plurality of grid cells, each grid cell including at least one probe point; 
 determining a seed point for a respective grid cell, wherein the seed point is representative of a first plurality of probe points, and wherein determining the seed point comprises determining a weighted center of mass of the first plurality of probe points; 
 determining an orientation associated with the seed point that is based on at least one of a position or heading of a second plurality of probe points proximate the seed point; 
 creating a polyline representative of a road geometry for mapping or navigation, wherein creating the polyline comprises extending the polyline by a predefined amount and in the orientation from the seed point, thereby defining a second point on the polyline that is spaced from the seed point by the predefined amount and is disposed in the orientation from the seed point; 
 determining if another seed point for another respective grid cell is proximate the polyline prior to extending the polyline beyond the second point and, in an instance in which another seed point is determined to be proximate the polyline that extends from the seed point to the second point, incorporating the another seed point into the polyline as a vertex so as to replace the second point such that the polyline will then extend from the seed point to the another seed point; and 
 providing the mapping or navigation using the polyline representative of the road geometry. 
 
     
     
       2. A method according to  claim 1  wherein creating the polyline comprises creating the polyline so as to extend in opposite directions from the seed point by extending in both the orientation from the seed point and in an opposite orientation from the seed point. 
     
     
       3. A method according to  claim 1  wherein extending the polyline comprises:
 determining a weighted center of mass of one or more probe points proximate the second point; 
 determining an orientation representative of the one or more probe points proximate the weighted center of mass of the one or more probe points proximate the second point such that the weighted center of mass of the one or more probe points proximate the second point has a single orientation that is based on at least one of the position or the heading of each of the one or more probe points proximate the second point; and 
 repeating extension of the polyline from the weighted center of mass of the one or more probe points proximate the second point. 
 
     
     
       4. A method according to  claim 1  wherein determining the orientation comprises determining the orientation using a principal component analysis or a least median of squares technique or based upon headings of the second plurality of probe points. 
     
     
       5. A method according to  claim 1  wherein determining the seed point comprises determining a seed point for each grid cell. 
     
     
       6. A method according to  claim 5  further comprising determining a heading density for the first plurality of probe points proximate each respective seed point, wherein creating the polyline comprises identifying the seed point from which the polyline will be initially created based upon the heading densities of the seed points. 
     
     
       7. A method according to  claim 1  wherein each grid cell has a dimension dependent upon a width of a road for which the polyline represents the road geometry. 
     
     
       8. An apparatus comprising at least one processor and at least one memory including computer program code, the at least one memory and computer program code configured to, with the processor, cause the apparatus to at least:
 define a plurality of grid cells, each grid cell including at least one probe point; 
 determine a seed point for a respective grid cell, wherein the seed point is representative of a first plurality of probe points, and wherein determining the seed point comprises determining a weighted center of mass of the first plurality of probe points; 
 determine an orientation associated with the seed point that is based on at least one of a position or heading of a second plurality of probe points proximate the seed point; 
 create a polyline representative of a road geometry for mapping or navigation, wherein creating the polyline comprises extending the polyline by a predefined amount and in the orientation from the seed point, thereby defining a second point on the polyline that is spaced from the seed point by the predefined amount and is disposed in the orientation from the seed point; 
 determine if another seed point for another respective grid cell is proximate the polyline prior to extending the polyline beyond the second point and, in an instance in which another seed point is determined to be proximate the polyline that extends from the seed point to the second point, incorporate the another seed point into the polyline as a vertex so as to replace the second point such that the polyline will then extend from the seed point to the another seed point; and 
 provide the mapping or navigation using the polyline representative of the road geometry. 
 
     
     
       9. An apparatus according to  claim 8  wherein the at least one memory and computer program code are configured to, with the processor, cause the apparatus to create the polyline by creating the polyline so as to extend in opposite directions from the seed point by extending in both the orientation from the seed point and in an opposite orientation from the seed point. 
     
     
       10. An apparatus according to  claim 8  wherein the at least one memory and computer program code are configured to, with the processor, cause the apparatus to extend the polyline by:
 determining a weighted center of mass of one or more probe points proximate the second point; 
 determining an orientation representative of the one or more probe points proximate the weighted center of mass of the one or more probe points proximate the second point such that the weighted center of mass of the one or more probe points proximate the second point has a single orientation that is based on at least one of the position or the heading of each of the one or more probe points proximate the second point; and 
 repeating extension of the polyline from the weighted center of mass of the one or more probe points proximate the second point. 
 
     
     
       11. An apparatus according to  claim 8  wherein the at least one memory and computer program code are further configured to, with the processor, cause the apparatus to determine the orientation by determining the orientation using a principal component analysis or a least median of squares technique or based upon headings of the second plurality of probe points. 
     
     
       12. An apparatus according to  claim 8  wherein the at least one memory and computer program code are configured to, with the processor, cause the apparatus to determine the seed point by determining a seed point for each grid cell. 
     
     
       13. An apparatus according to  claim 12  wherein the at least one memory and computer program code are further configured to, with the processor, cause the apparatus to determine a heading density for the first plurality of probe points proximate each respective seed point, wherein the at least one memory and computer program code are configured to, with the processor, cause the apparatus to create the polyline by identifying the seed point from which the polyline will be initially created based upon the heading densities of the seed points. 
     
     
       14. An apparatus according to  claim 8  wherein each grid cell has a dimension dependent upon a width of a road for which the polyline represents the road geometry. 
     
     
       15. A computer program product comprising at least one non-transitory computer-readable storage medium having computer-executable program code portions stored therein, the computer-executable program code portions comprising program code instructions configured to:
 define a plurality of grid cells, each grid cell including at least one probe point; 
 determine a seed point for a respective grid cell, wherein the seed point is representative of a first plurality of probe points, and wherein the program code instructions configured to determine the seed point comprise program code instructions configured to determine a weighted center of mass of the first plurality of probe points; 
 determine an orientation associated with the seed point that is based on at least one of a position or heading of a second plurality of probe points proximate the seed point; 
 create a polyline representative of a road geometry for mapping or navigation, wherein the program code instructions configured to create the polyline comprise program code instructions configured to extend the polyline by a predefined amount and in the orientation from the seed point, thereby defining a second point on the polyline that is spaced from the seed point by the predefined amount and is disposed in the orientation from the seed point; 
 determine if another seed point for another respective grid cell is proximate the polyline prior to extending the polyline beyond the second point and, in an instance in which another seed point is determined to be proximate the polyline that extends from the seed point to the second point, incorporate the another seed point into the polyline as a vertex so as to replace the second point such that the polyline will then extend from the seed point to the another seed point; and 
 provide the mapping or navigation using the polyline representative of the road geometry. 
 
     
     
       16. A computer program product according to  claim 15  wherein the program code instructions configured to create the polyline comprise program code instructions configured to create the polyline so as to extend in opposite directions from the seed point by extending in both the orientation from the seed point and in an opposite orientation from the seed point. 
     
     
       17. A computer program product according to  claim 15  wherein the program code instructions configured to extend the polyline comprise program code instructions configured to:
 determine a weighted center of mass of one or more probe points proximate the second point such that the weighted center of mass of the one or more probe points proximate the second point has a single orientation that is based on at least one of the position or the heading of each of the one or more probe points proximate the second point; 
 determine an orientation representative of the one or more probe points proximate the weighted center of mass of the one or more probe points proximate the second point; and 
 repeat extension of the polyline from the weighted center of mass of the one or more probe points proximate the second point. 
 
     
     
       18. A computer program product according to  claim 15  wherein the program code instructions configured to determine the orientation comprise program code instructions configured to determine the orientation using a principal component analysis or a least median of squares technique or based upon headings of the second plurality of probe points. 
     
     
       19. A computer program product according to  claim 15  further comprising program code instructions configured to:
 determine a heading density for the first plurality of probe points proximate each respective seed point, 
 wherein the program code instructions configured to create the polyline comprise program code instructions configured to identify the seed point from which the polyline will be initially created based upon the heading densities of the seed points. 
 
     
     
       20. A computer program product according to  claim 15  wherein each grid cell has a dimension dependent upon a width of a road for which the polyline represents the road geometry, and wherein the program code instructions configured to determine the seed point comprise program code instructions configured to determine a seed point for each grid cell.