ROAD NETWORK GENERATION

• US 20160092621A1
• Filed: 09/29/2015
• Published: 03/31/2016
• 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
• Granted Patent: US 10,452,810 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 for generating a road network, 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; 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.

2. The method according to claim 1, further comprising:

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.

3. The method according to claim 1, further comprising:

representing the trajectories using the road network.

4. 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.

5. The method according to claim 4, 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.

6. The method according to claim 5, 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.

7. The method according to claim 5, 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.

8. The method according to claim 7, 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.

9. The method according to claim 8, 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.

10. The method according to claim 1, 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.

11. The method according to claim 10, 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.

12. A road network generation apparatus, comprising:

an aggregating part configured to aggregate 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

a link generation part configured to generate 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.

13. The road network generation apparatus according to claim 12, further comprising:

a node generation part configured to generate 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.

14. The road network generation apparatus according to claim 12, further comprising:

a representing part configured to represent the trajectories using the road network.

15. The road network generation apparatus according to claim 12, wherein the aggregating part aggregates 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.

16. The road network generation apparatus according to claim 15, 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.

17. The road network generation apparatus according to claim 16, 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.

18. The road network generation apparatus according to claim 16, 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.

19. The road network generation apparatus according to claim 18, 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.

20. The road network generation apparatus according to claim 19, 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.

21. The road network generation apparatus according to claim 12, 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.

22. The road network generation apparatus according to claim 21, 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.