GENERATING A ROAD NETWORK FROM LOCATION DATA

• US 20150377636A1
• Filed: 06/15/2015
• Published: 12/31/2015
• Est. Priority Date: 06/27/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ding, Jian Dong, Duan, Ning, Gao, Peng, Ji, Peng, Zhang, Xin, Zhao, Qian Kun
• Granted Patent: US 9,631,935 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/30 Map- or contour-matching

Abstract

The present disclosure relates to a method and system for generating a road network. An embodiment of the present invention provides a method comprising: identifying a target area to be refined in a road network skeleton; and refining the target area using at least one trajectory associated with the target area to generate the road network. Another embodiment of the present invention provides a corresponding system.

Claims

1. A method for generating a road network, the method comprising:

identifying, by a computer, a target area to be refined in a road network skeleton; and

refining, by a computer, the target area using at least one trajectory associated with the target area to generate the road network.

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

generating, by a computer the road network skeleton by rasterization processing based on location data representing a plurality of locations.

3. The method according to claim 1, wherein identifying the target area to be refined in the road network skeleton comprises:

dividing, by a computer, the road network skeleton into a plurality of areas; and

identifying, by a computer, the target area in the plurality of areas.

4. The method according to claim 3, wherein identifying the target area in the plurality of areas comprises:

determining, by a computer, a connectivity of the road network skeleton in the plurality of areas; and

identifying, by a computer, the target area at least in part based on the connectivity.

5. The method according to claim 4, wherein identifying the target area at least in part based on the connectivity comprises:

determining, by a computer, a distribution of a plurality of locations for generating the road network skeleton among the plurality of areas; and

identifying, by a computer, the target area based on the connectivity and the distribution.

6. The method according to claim 1, wherein the at least one trajectory is generated based on at least one of:

a first group of locations that are used for generating the road network skeleton and located in the target area; and

a second group of locations that are obtained after the road network skeleton is generated, and is located in the target area.

7. The method according to claim 1, wherein refining the target area using the at least one trajectory associated with the target area to generate the road network comprises:

creating, by a computer, a virtual link connecting points in the target area;

generating, by a computer, in the target area, a virtual path containing the virtual link; and

refining, by a computer, the target area by matching the at least one trajectory and the virtual path.

8. The method according to claim 7, wherein creating the virtual link connecting points in the target area comprises:

selecting, by a computer, an initial node in the target area;

selecting, by a computer, a candidate node in the target area based on the initial node and a predefined constraint; and

creating, by a computer, the virtual link by connecting the initial node and the candidate node.

9. The method according to claim 8, wherein the predefined constraint comprises at least one of a spatial constraint and a time constraint.

10. The method according to claim 7, wherein refining the target area by matching the at least one trajectory and the virtual path comprises:

adding, by a computer, the virtual link contained in the virtual path into the road network in response to the virtual path matching a predetermined number of trajectories in the at least one trajectory.

11. A computer system for generating a road network, the computer system comprising:

one or more computer processors, one or more computer-readable storage media, and program instructions stored on one or more of the computer-readable storage media for execution by at least one of the one or more processors, the program instructions comprising;

program instruction to identify a target area to be refined in a road network skeleton; and

program instruction to refine the target area using at least one trajectory associated with the target area to generate the road network.

12. The computer system according to claim 11, further comprising:

program instructions to generate the road network skeleton by rasterization processing based on location data representing a plurality of locations.

13. The computer system according to claim 11, further comprising:

program instructions to divide the road network skeleton into a plurality of areas, wherein the target area is in at least one of the plurality of areas.

14. The computer system according to claim 13, further comprising:

program instructions to determine a connectivity of the road network skeleton in the plurality of areas,

wherein the target area is identified from the plurality of areas at least in part based on the connectivity of the road network skeleton in the plurality of areas.

15. The computer system according to claim 14, further comprising:

program instructions to determine distribution of a plurality of locations for generating the road network skeleton among the plurality of areas,

wherein the target area is identified from the plurality of areas at least in part based on the distribution of the plurality of locations.

16. The computer system according to claim 11, wherein the at least one trajectory comprises at least one of:

a first group of locations, located in the target area, which are used for generating the road network skeleton; and

a second group of locations, located in the target area, which are obtained after the road network skeleton is generated.

17. The computer system according to claim 11, wherein the program instructions to refine the target area comprises:

program instructions to create a virtual link connecting points in the target area;

program instructions to generate, in the target area, a virtual path containing the virtual link; and

program instructions to match the at least one trajectory and the virtual path to refine the target area.

18. The computer system according to claim 17, wherein the program instructions to create the virtual link comprises:

program instructions to select an initial node in the target area;

program instructions to select a candidate node in the target area based on the initial node and a predefined constraint; and

program instructions to connect the initial node and the candidate node to create the virtual link.

19. The computer system according to claim 18, wherein the predefined constraint comprises at least one of a spatial constraint and a time constraint.

20. The computer system according to claim 17 the program instructions to refine the target area comprises:

program instructions to add the virtual link contained in the virtual path into the road network, in response to the virtual path matching a predetermined number of trajectories in the at least one trajectory.