Map processing for indoor navigation guidance
First Claim
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 a likelihood that a route would pass through that point, the value based on a position of that point in the indoor space;
generating the plurality of nodes for the directed graph based on the values by;
generating a first node at a point having a highest value of the values in the navigable area,generating a first set of at least two nodes connected to the first node, each node in the first set being at a point in the navigable area having a value of the values higher than the values of neighboring points, andgenerating a second set of nodes connected to at least one node in the first set, each node in the second set being at a point in the navigable area having a value of the values higher than the values of neighboring points;
generating the plurality of paths for the directed graph based on the plurality of nodes, the plurality of paths corresponding to routes between the first node and the first set of nodes and between the first set of nodes and the second set 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 on an electronic display.
2 Assignments
0 Petitions
Accused Products
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.
12 Citations
17 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 a likelihood that a route would pass through that point, the value based on a position of that point in the indoor space; generating the plurality of nodes for the directed graph based on the values by; generating a first node at a point having a highest value of the values in the navigable area, generating a first set of at least two nodes connected to the first node, each node in the first set being at a point in the navigable area having a value of the values higher than the values of neighboring points, and generating a second set of nodes connected to at least one node in the first set, each node in the second set being at a point in the navigable area having a value of the values higher than the values of neighboring points; generating the plurality of paths for the directed graph based on the plurality of nodes, the plurality of paths corresponding to routes between the first node and the first set of nodes and between the first set of nodes and the second set 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 on an electronic display. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A computer-implemented method for processing a map to provide guidance for navigating an indoor space, the method comprising:
-
Accessing, by one or more processors, a preliminary map associated with the indoor space; Converting, using the one or more processor, the preliminary map into a segmented map, wherein the segmented map distinguishes a navigable area of the indoor space from non-navigable area of the indoor space; For each point of a set of points in the navigable area, identifying, by one or more processors, a distance between that point to a nearest point in the 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 by executing a distance transform on the segmented map 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, 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 by; Computing a shortest route between every pair of nodes, each pair of nodes comprising a first node and an ending node, Determining a next node in a given shortest route for a given pair from the first node to the ending node, and Storing an identifier for the next node in the navigation table in association with the first node and the ending node; 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 on an electronic display. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
-
17. A system comprising:
-
An electronic display; and One or more computing devices, each computing device comprising one or more processors, the one or more computing devices being configured to; Access a preliminary map associated with the indoor space Convert 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; For each point of a set of points in the navigable area, identify a distance between that point to a nearest point in the 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 by executing a distance transform on the segmented map 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, 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 by; Computing a shortest route between every pair of nodes, each pair of nodes comprising a first node and an ending node, Determining a next node in a given shortest route for a given pair from the first node to the ending node, and Storing an identifier for the next node in the navigation table in association with the first node and the ending node; Receive a request for directions to a location in the indoor space; and Display a route to the location based on the directed graph on the electronic display.
-
Specification