Road network generation

Patent metadata

Field	Value
Publication number	US-10452810-B2
Application number	US-201514868744-A
Country	US
Kind code	B2
Filing date	Sep 29, 2015
Priority date	Sep 30, 2014
Publication date	Oct 22, 2019
Grant date	Oct 22, 2019

Abstract

A method and an apparatus for generating a road network are disclosed. The method for generating a road network comprises: aggregating a plurality of grid cells partitioned in advance on a trajectory map based on trajectories in each grid cell of the plurality of grid cells to form level-1 regions; and generating a link of the road network by merging a level-1 region having two valid neighbors with its neighbor level-1 regions having two valid neighbors.

First claim

What is claimed is:

1. A method, comprising:
aggregating a plurality of grid cells partitioned in advance on a trajectory map based on trajectories in each grid cell of the plurality of grid cells to form level-1 regions, where the trajectories comprise routes traveled by vehicles, and wherein each trajectory of the trajectories is represented as a sequence of position points on the trajectory map;
generating a link of a road network by merging a level-1 region having two valid neighbors with its neighbor level-1 regions having two valid neighbors, wherein a level-1 region B is called a valid neighbor of a level-1 region A when it satisfies the following conditions:
the level-1 region B is a neighbor level-1 region of the level-1 region A; and
the level-1 region B has at least one neighbor level-1 region, in addition to the level-1 region A, which is not a neighbor level-1 region of the level-1 region A;

generating a node of the road network by merging a level-1 region having three or more valid neighbors with its neighbor level-1 regions having three or more valid neighbors;
constructing a map of the road network using the link and the node, wherein the link corresponds to a road segment on the map and the node corresponds to a meeting point of at least two road segments on the map; and
representing a trajectory of the trajectories by replacing the sequence of position points with a set containing at least one of: the link and the node.

2. The method according to claim 1 , wherein the aggregating a plurality of grid cells partitioned in advance on a trajectory map based on trajectories in each grid cell of the plurality of grid cells comprises:
aggregating the plurality of grid cells based on a density of trajectories in each grid cell of the plurality of grid cells partitioned in advance on the trajectory map.

3. The method according to claim 2 , wherein a size of the plurality of grid cells is set based on a preset spatial accuracy of the road network and a number limit of aggregated cells in each direction.

4. The method according to claim 3 , wherein the size of the plurality of grid cells is equal to or less than a quotient obtained by dividing the spatial accuracy of the road network by the number limit of aggregated cells.

5. The method according to claim 3 , wherein the aggregating the plurality of grid cells based on a density of trajectories in each grid cell of the plurality of grid cells partitioned in advance on the trajectory map comprises:
in the case that the number limit of aggregated cells is not reached:
if it is determined that in an adjacent grid cell of a present grid cell there are enough trajectories different from the trajectories in the present grid cell, aggregating the present grid cell and the adjacent grid cell, otherwise, taking the present grid cell as a level-1 region.

6. The method according to claim 5 , wherein the determining that in the adjacent grid cell adjacent of the present grid cell there are enough trajectories different from the trajectories in the present grid cell comprises:
computing a number of trajectory segments in the present grid cell and a number of trajectory segments in the adjacent grid cell;
adding a computed number of trajectory segments in the present grid cell and a computed number of trajectory segments in the adjacent grid cell, to get a sum number of trajectory segments;
subtracting a number of trajectory segments in the adjacent grid cell, which are located on a same trajectory as the trajectory segments in the present grid cell, from the sum number of trajectory segments, to get a sum number of valid trajectory segments; and
determining that in the adjacent grid cell adjacent of the present grid cell there are enough trajectories different from the trajectories in the present grid cell, if the sum number of valid trajectory segments exceeds the number of trajectory segments in the present grid cell by a certain amount.

7. The method according to claim 6 , wherein the computing the number of trajectory segments in the present grid cell and the number of trajectory segments in the adjacent grid cell comprises:
scanning a sequence of position points contained in each trajectory, the sequence of position points being obtained by positioning.

8. The method according to claim 1 , wherein a level-1 region B is called a neighbor level-1 region of a level-1 region A when it satisfies the following conditions:
the level-1 region B meets at least in part with the level-1 region A at an edge; or
the level-1 region B meets with the level-1 region A on a corner, and there is no other level-1 region, which meets at least in part with the level-1 region A at an edge, meets at least in part with the level-1 region B at an edge.

9. An apparatus, comprising:
a processor; and
a computer readable storage medium having computer readable program instructions stored thereon for causing the processor to carry out operations comprising:
aggregating a plurality of grid cells partitioned in advance on a trajectory map based on trajectories in each grid cell of the plurality of grid cells to form level-1 regions, where the trajectories comprise routes traveled by vehicles, and wherein each trajectory of the trajectories is represented as a sequence of position points on the trajectory map;
generating a link of the road network by merging a level-1 region having two valid neighbors with its neighbor level-1 regions having two valid neighbors, wherein a level-1 region B is called a valid neighbor of a level-1 region A when it satisfies the following conditions:
the level-1 region B is a neighbor level-1 region of the level-1 region A; and
the level-1 region B has at least one neighbor level-1 region, in addition to the level-1 region A, which is not a neighbor level-1 region of the level-1 region A;

generating a node of a road network by merging a level-1 region having three or more valid neighbors with its neighbor level-1 regions having three or more valid neighbors;
constructing a map of the road network using the link and the node, wherein the link corresponds to a road segment on the map and the node corresponds to a meeting point of at least two road segments on the map; and
representing a trajectory of the trajectories by replacing the sequence of position points with a set containing at least one of: the link and the node.

10. The apparatus according to claim 9 , wherein the aggregating comprises:
aggregating the plurality of grid cells based on a density of trajectories in each grid cell of the plurality of grid cells partitioned in advance on the trajectory map.

11. The apparatus according to claim 10 , wherein a size of the plurality of grid cells is set based on a preset spatial accuracy of the road network and a number limit of aggregated cells in each direction.

12. The apparatus according to claim 11 , wherein the size of the plurality of grid cells is equal to or less than a quotient obtained by dividing the spatial accuracy of the road network by the number limit of aggregated cells.

13. The apparatus according to claim 11 , wherein the aggregating the plurality of grid cells based on a density of trajectories in each grid cell of the plurality of grid cells partitioned in advance on the trajectory map comprises:
in the case that the number limit of aggregated cells is not reached:
if it is determined that in an adjacent grid cell of a present grid cell there are enough trajectories different from the trajectories in the present grid cell, aggregating the present grid cell and the adjacent grid cell, otherwise, taking the present grid cell as a level-1 region.

Assignees

• IBM

Inventors

• Hu Guoqiang
• Ding Jiandong
• Ji Peng
• Duan Ning
• Zhu Jun

Classifications

• G06F30/18

  Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling (circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18) · CPC title

• G06F17/509 Primary

  Physics · mapped topic

• G01C21/32

  Structuring or formatting of map data · CPC title

• G01C21/3844

  Data obtained from position sensors only, e.g. from inertial navigation · CPC title

• G01C21/3815

  Road data · CPC title