Generating a road network based on satellite imagery

• US 9,262,852 B1
• Filed: 12/31/2014
• Issued: 02/16/2016
• Est. Priority Date: 04/13/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kehl, Roland, Heiler, Matthias, Bakir, Gokhan Hasan
• Primary Examiner(s): Heidemann, Jason
• Application Number:
  US14/587,545
• Time in Patent Office: 412 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06V 10/426 Graphical representations
• CPC Class Codes: G06V 20/182 Network patterns, e.g. roads or rivers

Abstract

A system and method for generating a road network based on satellite imagery. Plural pixels corresponding to satellite imagery of a region are obtained. For each of the plural pixels, a probability value corresponding to the probability that the pixel belongs within the road network is calculated. A grayscale image is formed based on the calculated probability values. Plural curves are produced based on the grayscale image, wherein the producing of each curve includes positioning a shape on the grayscale image so that an average intensity of the grayscale image covered by the shape exceeds a preset threshold, moving the shape about the grayscale image while the average intensity is maintained, and tracking the movement of the shape to produce the curve. A planar-connected graph is generated by connecting at least portions of the plural curves. The planar-connected graph corresponds to the road network.

Claims

1. A computer-implemented method comprising:

obtaining, by one or more computing devices, plural pixels corresponding to satellite imagery of a region;

calculating, by the one or more computing devices, for each of the plural pixels, a probability value corresponding to the probability that the pixel belongs within a road network;

forming, by the one or more computing devices, an image based on the calculated probability values;

producing, by the one or more computing devices, plural curves based on the image; and

generating, by the one or more computing devices, a planar-connected graph by connecting at least portions of the plural curves, wherein the planar-connected graph corresponds to the road network.

2. The method of claim 1, wherein the producing of each curve comprises:

positioning a shape on the image so that an average intensity of the image covered by the shape exceeds a preset threshold;

moving the shape about the image while the average intensity is maintained; and

tracking the movement of the shape to produce the curve.

3. The method of claim 1, wherein the positioning comprises positioning the shape on the image so that the average intensity of the image covered by the shape is maximized.

4. The method of claim 1, wherein the producing of each curve further comprises blacking out the tracked movement of the shape corresponding to the curve within the image.

5. The method of claim 1, wherein the shape is a rectangle.

6. The method of claim 1, wherein the planar-connected graph is maintained within a spatial database which defines the geometries for the plural curves.

7. The method of claim 6, wherein the generating comprises, for a curve within the plural curves:

determining if an endpoint of the curve is within a predetermined distance of an edge another curve within the planar-connected graph, based on the geometries defined within the spatial database; and

if it is determined that the endpoint is within the predetermined distance to the edge,

connecting the curve to the edge, and

storing the connection in the spatial database.

8. The method of claim 6, wherein the generating comprises, for a curve within the plural curves:

determining if the curve intersects another curve within the planar-connected graph, based on the geometries defined within the spatial database; and

if it is determined that the curve intersects the other curve,

splitting the curve at a point corresponding to the intersection, and

storing the split in the spatial database.

9. The method of claim 8, further comprising:

if it is determined that the curve does not intersect the other curve, storing the curve in the spatial database.

10. The method of claim 8, wherein the determining comprises performing a Manhattan distance calculation using the curve and the other curve to determine if the curve intersects the other curve.

11. The method of claim 1, wherein the planar-connected graph corresponds to a first region, the method further comprising:

connecting the planar-connected graph with another planar-connected graph corresponding to a second region which is different from the first region.

12. A system comprising:

one or more computing devices; and

a machine-readable medium comprising instructions stored therein, which when executed by the one or more computing devices, cause the one or more computing devices to perform operations comprising;

obtaining plural pixels corresponding to satellite imagery of a region;

calculating, for each of the plural pixels, a probability value corresponding to the probability that the pixel belongs within a road network;

forming an image based on the calculated probability values;

producing plural curves based on the image; and

generating a planar-connected graph by connecting at least portions of the plural curves, wherein the planar-connected graph corresponds to the road network.

13. The system of claim 12, wherein the producing of each curve comprises:

positioning a shape on the image so that the average intensity of the image covered by the shape is maximized;

moving the shape about the image while the average intensity is maintained;

tracking the movement of the shape to produce the curve; and

blacking out the tracked movement of the shape corresponding to the curve within the image.

14. The system of claim 12, wherein the shape is a rectangle.

15. The system of claim 12, wherein the planar-connected graph is maintained within a spatial database which defines the geometries for the plural curves.

16. The system of claim 15, wherein the generating comprises, for a curve within the plural curves:

determining if an endpoint of the curve is within a predetermined distance of an edge another curve within the planar-connected graph, based on the geometries defined within the spatial database; and

if it is determined that the endpoint is within the predetermined distance to the edge,

connecting the curve to the edge, and

storing the connection in the spatial database.

17. The system of claim 15, wherein the generating comprises, for a curve within the plural curves:

determining if the curve intersects another curve within the planar-connected graph, based on the geometries defined within the spatial database; and

if it is determined that the curve intersects the other curve,

splitting the curve at a point corresponding to the intersection, and

storing the split in the spatial database.

18. A non-transitory machine-readable medium comprising instructions stored therein, which when executed by a system, cause the system to perform operations comprising:

obtaining plural pixels corresponding to satellite imagery of a region;

calculating, for each of the plural pixels, a probability value corresponding to the probability that the pixel belongs within a road network;

forming an image based on the calculated probability values;

producing plural curves based on the image; and

generating a planar-connected graph by connecting at least portions of the plural curves, wherein the planar-connected graph corresponds to the road network.

19. The non-transitory machine-readable medium of claim 18, wherein the satellite imagery corresponds to a single satellite image or a blend of multiple satellite images.

20. The non-transitory machine-readable medium of claim 18, wherein the positioning comprises positioning the shape on the image so that the average intensity of the image covered by the shape is maximized.