METHOD AND APPARATUS FOR DEFINING ROAD GEOMETRY FROM PROBE DATA

• US 20160356606A1
• Filed: 06/03/2015
• Published: 12/08/2016
• Est. Priority Date: 06/03/2015
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Dorum, Ole Henry
• Granted Patent: US 10,444,020 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G01V 11/002 Details, e.g. power supply systems for logging instruments, transmitting or recording data, specially adapted for well logging, also if the prospecting method is irrelevant means for transmitting well survey signals E21B47/12; signal transmission systems in general G08C; transmission in general H04B
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

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.

Claims

1. A method comprising:

determining a seed point representative of one or more probe points, wherein determining the seed point comprises determining a weighted center of mass of the one or more probe points;

determining an orientation representative of one or more probe points proximate the seed point; and

creating a polyline representative of a road geometry, wherein creating the polyline comprises extending the polyline in the orientation from the seed point.

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:

extending the polyline from a first point to a second point, wherein the second point is spaced from the first point by a predefined amount and is disposed in the orientation from the first point;

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; 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 3 further comprising determining if another seed point is proximate the polyline prior to repeating the extension of the polyline and, in an instance in which another seed point is determined to be proximate the polyline, incorporating the seed point into the polyline so as to replace the second point.

5. 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 one or more probe points.

6. A method according to claim 1 further comprising defining a plurality of grid cells, each grid cell including at least one probe point, wherein determining the seed point comprises determining a seed point for each grid cell.

7. A method according to claim 6 further comprising determining a heading density for the one or more 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.

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:

determine a seed point representative of one or more probe points, wherein determining the seed point comprises determining a weighted center of mass of the one or more probe points;

determine an orientation representative of one or more probe points proximate the seed point; and

create a polyline representative of a road geometry, wherein creating the polyline comprises extending the polyline in the orientation from the seed point.

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:

extending the polyline from a first point to a second point, wherein the second point is spaced from the first point by a predefined amount and is disposed in the orientation from the first point;

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; 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 10 wherein the at least one memory and computer program code are further configured to, with the processor, cause the apparatus to determine if another seed point is proximate the polyline prior to repeating the extension of the polyline and, in an instance in which another seed point is determined to be proximate the polyline, to incorporate the seed point into the polyline so as to replace the second point.

12. 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 one or more probe points.

13. 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 define a plurality of grid cells, each grid cell including at least one probe point, 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.

14. An apparatus according to claim 13 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 one or more 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.

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:

determine a seed point representative of one or more probe points, 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 one or more probe points;

determine an orientation representative of one or more probe points proximate the seed point; and

create a polyline representative of a road geometry, wherein the program code instructions configured to create the polyline comprise program code instructions configured to extend the polyline in the orientation from the seed point.

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:

extend the polyline from a first point to a second point, wherein the second point is spaced from the first point by a predefined amount and is disposed in the orientation from the first point;

determine a weighted center of mass of 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 17 further comprising program code instructions configured to determine if another seed point is proximate the polyline prior to repeating the extension of the polyline and program code instructions configured to, in an instance in which another seed point is determined to be proximate the polyline, incorporate the seed point into the polyline so as to replace the second point.

19. 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 one or more probe points.

20. A computer program product according to claim 15 further comprising program code instructions configured to:

define a plurality of grid cells, each grid cell including at least one probe point, 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; and

determine a heading density for the one or more 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.