Road network generation

Patent metadata

Field	Value
Publication number	US-11270039-B2
Application number	US-201916576489-A
Country	US
Kind code	B2
Filing date	Sep 19, 2019
Priority date	Sep 30, 2014
Publication date	Mar 8, 2022
Grant date	Mar 8, 2022

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 on a trajectory map, wherein the aggregating is based on trajectories in each grid cell of the plurality of grid cells, wherein the trajectories comprise routes traveled by vehicles in a road network, wherein each trajectory of the trajectories is represented as a sequence of position points on the trajectory map, and wherein the aggregating forms a plurality of level-1 regions;
generating a link of the road network by merging a first subset of the plurality of level-1 regions, wherein the link corresponds to a road segment on the map;
generating a node of the road network by merging a second subset of the plurality of level-1 regions, wherein the node corresponds to a meeting point of at least two road segments on the map;
constructing a map of the road network using the link and the node; 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 first subset of the plurality of level-1 regions comprises:
a first level-1 region; and
a second level-1 region; and
a third-level-1 region,
wherein the second level-1 region and the third level-1 region are valid neighbors of the first level-1 region, and
wherein each of the second level-1 region and the third level-1 region has two valid neighbors among the plurality of level-1 regions.

3. The method according to claim 1 , wherein the second subset of the plurality of level-1 regions comprises:
a first level-1 region;
a second level-1 region;
a third level-1 region; and
a fourth level-1 region,
wherein the second level-1 region, the third level-1 region, and the fourth level-1 region are valid neighbors of the first level-1 region, and
wherein each of the second level-1 region, the third level-1 region, and the fourth level-1 region has three valid neighbors among the plurality of level-1 regions.

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

5. The method according to claim 4 , wherein a size of each grid cell 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.

6. The method according to claim 5 , wherein the size of each grid cell 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.

7. The method according to claim 5 , wherein the aggregating comprises, when the number limit of aggregated cells is not reached:
aggregating a first grid cell of the plurality of grid cells with a second grid cell of the plurality of grid cells that is adjacent to the first grid cell, when it is determined that the second grid cell contains at least a threshold number of the trajectories that are different from those of the trajectories that are present in the first grid cell.

8. The method according to claim 7 , wherein the aggregating further comprises, when the number limit of aggregated cells is not reached:
designating the first grid cell as a level-1 region, when it is determined that the second grid cell does not contain at least the threshold number of the trajectories that are different from those of the trajectories that are present in the first grid cell.

9. The method according to claim 8 , further comprising:
computing a first quantity comprising a number of trajectory segments that are present in the first grid cell and a second quantity comprising a number of trajectory segments that are present in the second grid cell;
adding the first quantity and the second quantity, to get a sum number of trajectory segments;
computing a third quantity comprising a number of trajectory segments that are present in the second grid cell and that are located on a same trajectory as the trajectory segments that are present in the first grid cell;
subtracting the third quantity from the sum number of trajectory segments, to get a sum number of valid trajectory segments; and
determining that the second grid cell contains at least a threshold number of the trajectories that are different from those of the trajectories that are present in the first grid cell, when the sum number of valid trajectory segments exceeds the first quantity by a predefined number.

10. 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 on a trajectory map, wherein the aggregating is based on trajectories in each grid cell of the plurality of grid cells, wherein the trajectories comprise routes traveled by vehicles in a road network, wherein each trajectory of the trajectories is represented as a sequence of position points on the trajectory map, and wherein the aggregating forms a plurality of level-1 regions;
generating a link of the road network by merging a first subset of the plurality of level-1 regions, wherein the link corresponds to a road segment on the map;
generating a node of the road network by merging a second subset of the plurality of level-1 regions, wherein the node corresponds to a meeting point of at least two road segments on the map;
constructing a map of the road network using the link and the node; 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.

11. The apparatus according to claim 10 , wherein the first subset of the plurality of level-1 regions comprises:
a first level-1 region; and
a second level-1 region; and
a third-level-1 region,
wherein the second level-1 region and the third level-1 region are valid neighbors of the first level-1 region, and
wherein each of the second level-1 region and the third level-1 region has two valid neighbors among the plurality of level-1 regions.

12. The apparatus according to claim 10 , wherein the second subset of the plurality of level-1 regions comprises:
a first level-1 region;
a second level-1 region;
a third level-1 region; and
a fourth level-1 region,
wherein the second level-1 region, the third level-1 region, and the fourth level-1 region are valid neighbors of the first level-1 region, and
wherein each of the second level-1 region, the third level-1 region, and the fourth level-1 region has three valid neighbors among the plurality of level-1 regions.

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

14. The apparatus according to claim 13 , wherein a size of each grid cell 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.

15. The apparatus according to claim 14 , wherein the size of each grid cell 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.

16. The apparatus according to claim 14 , wherein the aggregating comprises, when the number limit of aggregated cells is not reached:
aggregat

Assignees

• IBM

Inventors

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

Classifications

• G06F30/18 Primary

  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

• 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

• G01C21/3881 Primary

  Tile-based structures · CPC title