Method and apparatus for defining road geometry from probe data

Patent metadata

Field	Value
Publication number	US-2016356606-A1
Application number	US-201514729681-A
Country	US
Kind code	A1
Filing date	Jun 3, 2015
Priority date	Jun 3, 2015
Publication date	Dec 8, 2016
Grant date	—

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.

First claim

That which is claimed:

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:
ext

Assignees

• Here Global Bv

Inventors

• Dorum Ole Henry

Classifications

• G01C21/26 Primary

  specially adapted for navigation in a road network · CPC title

• G06F16/29 Primary

  Geographical information databases · CPC title

• H04W64/00

  Locating users or terminals {or network equipment} for network management purposes, e.g. mobility management · CPC title

• G01V11/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 title

• G01C21/3881

  Tile-based structures · CPC title