Generating a road network based on satellite imagery

• US 8,938,094 B1
• Filed: 04/13/2012
• Issued: 01/20/2015
• 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): Bella, Matthew
• Assistant Examiner(s): HEIDEMANN, JASON E
• Application Number:
  US13/446,948
• Time in Patent Office: 1,012 Days
• Field of Search: None
• US Class Current: 382/103
• 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 machine-implemented method for generating a road network based on satellite imagery, the method 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 the road network;

forming a grayscale image based on the calculated probability values;

producing plural curves based on the grayscale image, wherein the producing of each curve comprises;

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;

tracking the movement of the shape to produce the curve; 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.

2. The method of claim 1, wherein the satellite imagery corresponds to a single satellite image or a blend of multiple satellite images.

3. The method of claim 1, wherein the positioning comprises positioning the shape on the grayscale image so that the average intensity of the grayscale 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 grayscale 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 for generating a road network based on satellite imagery, the system comprising:

one or more processors; and

a machine-readable medium comprising instructions stored therein, which when executed by the processors, cause the processors 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 the road network;

forming a grayscale image based on the calculated probability values;

producing plural curves based on the grayscale image, wherein the producing of each curve comprises;

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

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

tracking the movement of the shape to produce the curve; 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 further comprises blacking out the tracked movement of the shape corresponding to the curve within the grayscale 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. The system of claim 17, the operations further comprising:

if it is determined that the curve does not intersect the other curve,

storing the curve in the spatial database.

19. The system of claim 17, 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.

20. The system of claim 12, wherein the planar-connected graph corresponds to a first region, the operations further comprising:

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

21. A non-transitory computer readable storage 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 the road network;

forming a grayscale image based on the calculated probability values;

producing plural curves based on the grayscale image, wherein the producing of each curve comprises;

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

moving the rectangle about the grayscale image while the average intensity is maintained;

tracking the movement of the rectangle to produce the curve;

blacking out the tracked movement of the rectangle corresponding to the curve within the grayscale 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.