Generating an indoor map model

• US 9,052,206 B2
• Filed: 01/12/2012
• Issued: 06/09/2015
• Est. Priority Date: 01/12/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Li, Guanfeng, Zhang, Faen, Wang, Feng
• Primary Examiner(s): Zarka, David
• Assistant Examiner(s): Vu, Khoa
• Application Number:
  US14/118,689
• Publication Number:
  US 20140078150A1
• Time in Patent Office: 1,244 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 7/90 Determination of colour characteristics
• CPC Class Codes: G06V 20/176 Urban or other man-made structures

Abstract

A method and system for providing an indoor map representation are provided herein. Aspects of this disclosure provide a representation of an indoor map environment whereby navigable areas are represented by a series of convex polygons in adjacency relationships with one another. Image analysis may be performed on a floor plan image to identify navigable areas and to determine the boundaries of the polygons, such as by assigning one or more colors to navigable space and one or more colors to non-navigable space. Route-finding operations may be performed using the adjacency relationships to find a path from a source area to a destination area.

Claims

1. A computer implemented method for generating a map model, the method comprising:

identifying one or more first colors in an image as associated with navigable space in a geographic area;

analyzing, using a processor, the image to identify areas of the navigable space by identifying pixels within the image that correspond to the one or more first colors;

generating at least one or more convex polygons that cover the areas of the navigable space by identifying an initial navigable pixel and analyzing adjacent pixels expanding outward from the initial navigable pixel;

identifying one or more boundaries of the at least one or more convex polygons by extrapolating one or more non-navigable areas identified by the analysis of adjacent pixels into navigable areas to ensure that the boundaries of the one or more polygons are convex; and

generating the map model, wherein the map model comprises the one or more convex polygons and a set of adjacency relationships among the one or more convex polygons.

2. The method of claim 1, further comprising identifying one or more second colors in the image as associated with non-navigable space in the geographic area.

3. The method of claim 1, further comprising identifying one or more elements of the image other than the one or more first colors that correspond to features of the geographic area, and associating the one or more elements with one or more of the polygons as polygon metadata.

4. The method of claim 3, wherein at least one of the one or more elements is a text string.

5. The method of claim 1, further comprising providing the map model to a client device for use in navigation operations.

6. The method of claim 1, wherein the map model comprises a series of vertices that define the one or more convex polygons, wherein the series of vertices are associated with location coordinates within the geographic area.

7. A non-transitory computer readable medium comprising instructions that, when executed by a processor, cause the processor to perform a method comprising:

identifying one or more first colors in an image as associated with navigable space in a floor plan;

analyzing the image to identify areas of the navigable space by identifying pixels within the image that correspond to the one or more first colors;

generating at least one or more convex polygons that cover the areas of the navigable space by identifying an initial navigable pixel and analyzing adjacent pixels expanding outward from the initial navigable pixel;

identifying one or more boundaries of the at least one or more convex polygons by extrapolating one or more non-navigable areas identified by the analysis of adjacent pixels into navigable areas to ensure that the boundaries of the one or more polygons are convex; and

generating the map model, wherein the map model comprises the one or more convex polygons and a set of adjacency relationships among the one or more convex polygons.

8. The non-transitory computer readable medium of claim 7, further comprising identifying one or more second colors in the image as associated with non-navigable space in the floor plan.

9. The non-transitory computer readable medium of claim 7, further comprising identifying one or more elements of the image other than the one or more first colors that correspond to features of the floor plan, and associating the one or more elements with one or more of the polygons as polygon metadata.

10. The non-transitory computer readable medium of claim 9, wherein at least one of the one or more elements is a text string.

11. The non-transitory computer readable medium of claim 7, further comprising providing the map model to a client device for use in navigation operations.

12. The non-transitory computer readable medium of claim 7, wherein the map model comprises a series of vertices that define the one or more convex polygons, wherein the series of vertices are associated with location coordinates within a given geographical area within the floor plan.

13. A processing system for providing indoor navigation comprising:

at least one processor; and

a memory coupled to the at least one processor, the memory comprising an image corresponding to a geographic area;

wherein the at least one processor is configured to;

identify one or more first colors in the image as associated with navigable space in the geographic area;

analyze the image to identify areas of the navigable space by identifying pixels within the image that correspond to the one or more first colors;

generate at least one or more convex polygons that cover the areas of the navigable space by identifying an initial navigable pixel and analyzing adjacent pixels expanding outward from the initial navigable pixel;

identifying one or more boundaries of the at least one or more convex polygons by extrapolating one or more non-navigable areas identified by the analysis of the adjacent pixels into navigable areas to ensure that the boundaries of the one or more polygons are convex; and

generate the map model, wherein the map model comprises the one or more convex polygons and a set of adjacency relationships among the one or more convex polygons.

14. The processing system of claim 13, wherein the processor is further configured to identify one or more second colors in the image as associated with non-navigable space in the geographic area.

15. The processing system of claim 13, wherein the processor is further configured to identify one or more elements of the image other than the one or more first colors that correspond to features of the geographic area, and to associate the one or more elements with one or more of the polygons as polygon metadata.

16. The processing system of claim 15, wherein at least one of the one or more elements is a text string.

17. The processing system of claim 13, wherein the processor is further configured to provide the map model to a client device for use in navigation operations.

18. The processing system of claim 13, wherein the map model comprises a series of vertices that define the one or more convex polygons, wherein the series of vertices are associated with location coordinates within a given geographical area within the floor plan.