Road network generation

• US 10,452,810 B2
• Filed: 09/29/2015
• Issued: 10/22/2019
• Est. Priority Date: 09/30/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hu, Guoqiang, Ding, Jiandong, Ji, Peng, Duan, Ning, Zhu, Jun
• Primary Examiner(s): Louis, Andre Pierre
• Application Number:
  US14/868,744
• Publication Number:
  US 20160092621A1
• Time in Patent Office: 1,484 Days
• Field of Search: 703 6
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/3844 Data obtained from position sensors only, e.g. from inertial navigation
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G06F 30/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

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.

Claims

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.

14. The apparatus according to claim 13, 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.

15. The apparatus according to claim 14, 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.

16. The apparatus according to claim 9, 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.