MAP PROCESSING FOR INDOOR NAVIGATION GUIDANCE

• US 20150153180A1
• Filed: 07/22/2011
• Published: 06/04/2015
• Est. Priority Date: 07/22/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ettinger, Scott, Rivlin, Ehud
• Granted Patent: US 9,291,460 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation

Abstract

Directions are provided to a location in an indoor space in response to receiving a request from a mobile device. First, a map of the indoor space is processed to identify navigable areas in the indoor space. A distance transform is then executed on the map as part of a process to generate a directed graph. The directed graph includes nodes that correspond to points in the indoor space and paths that correspond to routes between the nodes. Next, a navigation table is generated based on the directed graph to identify a shortest route from each node to at least one other node. In response to a request for directions to a location in the indoor space, the navigation table is accessed to identify a route to the requested location. The identified route is then provided to a mobile device such that an end user may navigate to the location.

Claims

1. A computer-implemented method comprising:

accessing, by one or more processors, a preliminary map associated with an indoor space;

converting, by the one or more processors, the preliminary map into a segmented map, wherein the segmented map distinguishes a navigable area of the indoor space from a non-navigable area of the indoor space;

generating, by the one or more processors, a directed graph corresponding to the indoor space based on the segmented map, the directed graph comprising a plurality of nodes connected by a plurality of paths, the plurality of nodes corresponding to points of a set of points in the navigable area of the indoor space and the plurality of paths corresponding to routes between the points, wherein the directed graph is generated by;

executing a distance transform on the segmented map to generate a distance map, wherein the distance map identifies, for each point of the set of points in the navigable area, a distance between that point to a nearest point in the non-navigable area;

for each point of the set of points in the navigable area, identifying a value that indicates the likelihood that a route would pass through that point, the value based on a position of that point in the indoor space; and

generating the plurality of nodes for the directed graph based on the values, wherein the plurality of nodes correspond to points of the set of points of the navigable area;

generating the plurality of paths for the directed graph based on the plurality of nodes, the plurality of paths corresponding to routes between the plurality of nodes;

storing, by the one or more processors, the directed graph for subsequent access to identify a route between two locations in the indoor space;

receiving, by the one or more processors, a request for directions to a location in the indoor space; and

displaying, by the one or more processors, a route to the location based on the directed graph.

3. The method of claim 1, further comprising:

generating a navigation table based on the directed graph, wherein the navigation table is generated by identifying a shortest route from each node to at least one of the plurality of nodes in the directed graph; and

accessing the navigation table to identify a route to the requested location.

4. The method of claim 3, wherein the request is received from a mobile device, and further comprising providing the directions corresponding to the route to the mobile device in response to the request.

5. The method of claim 4, wherein the route indicates a shortest path that the end user would realistically follow to reach the requested location.

6. The method of claim 5, further comprising:

identifying a location of the mobile device in the indoor space; and

indicating the identified location on the route displayed on the mobile device.

7. The method of claim 6, wherein identifying the location of the mobile device in the indoor space based on wireless beacon data.

8. The method of claim 1, wherein the preliminary map and the segmented map are processed as images.

9. The method of claim 1, wherein converting the preliminary map into the segmented map comprises removing extraneous information from the preliminary map, wherein the extraneous information is not required to generate the directed graph.

2. (canceled)

10. A computer-implemented method for processing a map to provide guidance for navigating an indoor space, the method comprising:

for each point of a set of points in a navigable area, identifying, by one or more processors, a distance between that point to a nearest point in a non-navigable area of the indoor space;

for each point of the set of points in the navigable area, identifying, by the one or more processors, a value that indicates a likelihood that a route would pass through that point based on a position of that point in the indoor space;

generating, by the one or more processors, a directed graph corresponding to the indoor space based on the values, the directed graph comprising a plurality of nodes connected by a plurality of paths, the plurality of nodes corresponding to points of the set of points in the navigable area, and wherein the plurality of paths are generated based on the plurality of nodes, corresponding to routes between the plurality of nodes;

generating, by the one or more processors, a navigation table based on the graph, the navigation table including navigation information that identifies a route between two locations in the indoor space;

receiving, by the one or more processors, a request for directions to a location in the indoor space; and

displaying, by the one or more processors, a route to the location based on the directed graph.

11. The method of claim 10, further comprising

accessing, by the one or more processors, the navigation table to identify a route to the requested location.

12. The method of claim 11, wherein the request is received from a mobile device, and further comprising providing the directions corresponding to the route to the mobile device in response to the request.

13. The method of claim 12, wherein the route indicates a shortest path that an end user would realistically follow to reach the requested location.

14. The method of claim 13, further comprising:

identifying, by one or more processors, a location of the mobile device in the indoor space; and

indicating, by the one or more processors, the identified location on the route displayed on the mobile device.

15. The method of claim 10, wherein the navigation table is generated by identifying the shortest route from each node to at least one of the plurality of nodes in the directed graph.

16. The method of claim 10, further comprising:

accessing a preliminary map associated with the indoor space; and

converting, using the processor, the preliminary map into a segmented map, wherein the segmented map distinguishes the navigable area of the indoor space from the non-navigable area of the indoor space.

17. The method of claim 16, further comprising executing a distance transform on the segmented map as part of a process to generate a distance map, wherein the distance map is used to identify the distance between each point of the set of points in the navigable area to the nearest point in the non-navigable area of the indoor space.

18. The method of claim 16, wherein the preliminary map and the segmented map are processed as images.

19. The method of claim 16, wherein converting the preliminary map into the segmented map comprises removing extraneous information from the preliminary map, wherein the extraneous information is not required to generate the directed graph.

20. (canceled)

21. (canceled)

22. (canceled)

23. A system comprising one or more computing devises configured to:

for each point of a set of points in a navigable area, identify a distance between that point to a nearest point in a non-navigable area of the indoor space;

for each point of the set of points in the navigable area, identify a value that indicates a likelihood that a route would pass through that point, the value based on a position of that point in the indoor space;

generate a directed graph corresponding to the indoor space based on the values, the directed graph comprising a plurality of nodes connected by a plurality of paths, the plurality of nodes corresponding to points of the set of points in the navigable area, and wherein the plurality of paths are based on the plurality of nodes, corresponding to routes between the plurality of nodes;

generate a navigation table based on the graph, the navigation table including navigation information that identifies a route between two locations in the indoor space;

receive a request for directions to a location in the indoor space; and

display a route to the location based on the directed graph.