Navigating using an indoor map representation

• US 9,173,069 B2
• Filed: 01/12/2012
• Issued: 10/27/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): Mitchell, Nathan
• Assistant Examiner(s): HEIBER, SHANTELL LAKETA
• Application Number:
  US14/118,714
• Publication Number:
  US 20140113665A1
• Time in Patent Office: 1,384 Days
• Field of Search: 345/613, 345/440, 345/646
• US Class Current: 1/1
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings

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 providing indoor navigation, the method comprising:

determining a client location;

identifying the client location as being within a source polygon selected from a plurality of convex polygons, the plurality of convex polygons defined by a map model that comprises the plurality of convex polygons and a set of adjacency relationships among the plurality of convex polygons, the plurality of convex polygons being associated with navigable space within a given geographical area;

receiving a destination location;

determining whether the destination location is located within navigable space or a non-navigable area;

determining a destination polygon based on the determination of whether the destination location is located within navigable space or the non-navigable area;

determining, using a processor by a client device, a route from the source polygon to the destination polygon using the map model by identifying a path defined by the set of adjacency relationships; and

providing the route from the source polygon to the destination polygon as a navigation path from the client location to the destination location;

wherein the borders of each convex polygon is determined at least in part by a server identifying an initial navigable pixel and expanding the border in a direction away from the initial navigable pixel until reaching at least one pixel associated with non-navigable space in said direction, and the server provides the borders to the client device.

2. The method of claim 1, wherein the set of adjacency relationships are line segments representing the boundaries between polygons.

3. The method of claim 1, wherein the plurality of convex polygons define the entirety of navigable space in an area.

4. The method of claim 3, wherein the navigable space is contiguous.

5. The method of claim 1, wherein the map model is generated using a building floor plan.

6. The method of claim 1, wherein the map model further comprises metadata associated with one or more of the plurality of polygons and wherein the method further comprises determining the destination polygon by searching the metadata.

7. The method of claim 1, wherein the map model comprises a series of vertices that define the plurality of polygons, wherein the series of vertices are associated with location coordinates within the given geographical area.

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

determining a client location;

identifying the client location as being within a source polygon selected from a plurality of convex polygons, the plurality of convex polygons defined by a map model that comprises the plurality of convex polygons and a set of adjacency relationships among the plurality of convex polygons, the plurality of convex polygons being associated with navigable space within a given geographical area;

receiving a destination location;

determining whether the destination location is located within navigable space or a non-navigable area;

determining a destination polygon based on the determination of whether the destination location is located within navigable space or the non-navigable area;

determining, using a processor by a client device, a route from the source polygon to the destination polygon using the map model by identifying a path defined by the set of adjacency relationships; and

providing the route from the source polygon to the destination polygon as a navigation path from the client location to the destination location;

wherein the borders of each convex polygon is determined at least in part by a server identifying an initial navigable pixel and expanding the border in a direction away from the initial navigable pixel until reaching at least one pixel associated with non-navigable space in said direction, and the server provides the borders to the client device.

9. The non-transitory computer readable medium of claim 8, wherein the set of adjacency relationships are line segments representing the boundaries between polygons.

10. The non-transitory computer readable medium of claim 8, wherein the plurality of convex polygons define the entirety of navigable space in an area.

11. The non-transitory computer readable medium of claim 10, wherein the navigable space is contiguous.

12. The non-transitory computer readable medium of claim 8, wherein the map model is generated using a building floor plan.

13. The non-transitory computer readable medium of claim 8, wherein the map model further comprises metadata associated with one or more of the plurality of polygons and wherein the method further comprises determining the destination polygon by searching the metadata.

14. The non-transitory computer readable medium of claim 8, wherein the map model comprises a series of vertices that define the plurality of polygons, wherein the series of vertices are associated with location coordinates within the given geographical area.

15. A processing system for providing indoor navigation comprising:

a navigation element for providing a current location of the processing system;

at least one processor; and

a memory coupled to the at least one processor, the memory comprising a map model that includes a plurality of convex polygons and a set of adjacency relationships among the plurality of convex polygons, the plurality of convex polygons being associated with navigable space within a given geographical area, wherein the navigable space is determined by identifying a navigable pixel and analyzing adjacent pixels to identify one or more boundaries of the plurality of convex polygons by extrapolating one or more non-navigable areas;

wherein the at least one processor is configured to;

identify the current location provided by the navigation element as being within a source polygon selected from the plurality of convex polygons;

receiving a destination location;

determining whether the destination location is located within navigable space or a non-navigable area;

determine a destination polygon based on the determination of whether the destination location is located within navigable space or the non-navigable area;

determine, using a processor by a client device, a route from the source polygon to the destination polygon using the map model by identifying a path defined by the set of adjacency relationships;

provide the route from the source polygon to the destination polygon as a navigation path from the client location to the destination location;

wherein the borders of each convex polygon is determined at least in part by a server identifying an initial navigable pixel and expanding the border in a direction away from the initial navigable pixel until reaching at least one pixel associated with non-navigable space in said direction, and the server provides the borders to the client device.

16. The processing system of claim 15, wherein the set of adjacency relationships are line segments representing the boundaries between polygons.

17. The processing system of claim 15, wherein the plurality of convex polygons define the entirety of navigable space in an area.

18. The processing system of claim 17, wherein the navigable space is contiguous.

19. The processing system of claim 15, wherein the map model is generated using a building floor plan.

20. The processing system of claim 15, wherein the map model further comprises metadata associated with one or more of the plurality of polygons and wherein the processor is further configured to determine the destination polygon by searching the metadata.

21. The processing system of claim 15, wherein the map model comprises a series of vertices that define the plurality of polygons, wherein the series of vertices are associated with location coordinates within the given geographical area.