Open area maps

• US 8,099,237 B2
• Filed: 07/25/2008
• Issued: 01/17/2012
• Est. Priority Date: 07/25/2008
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: Mays, Joseph P., Gale, William N., Seegers, Peter A., Stroila, Matei N.
• Primary Examiner(s): NGUYEN, TAN QUANG
• Application Number:
  US12/179,635
• Publication Number:
  US 20100023250A1
• Time in Patent Office: 1,271 Days
• Field of Search: 701/213, 701/208, 701/209, 701/201, 701/25, 701/28, 345/629, 345/587, 345/522, 345/620, 382/276, 382/153
• US Class Current: 701/213
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/383 Indoor data
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

Systems and methods associated with an open area map are disclosed. For example, one method comprises obtaining an image of a layout. The layout represents a real-world area in which a person moves about. A grid is applied on the image. The grid includes tiles that fill in a ground area of the image. A routable map is generated as a function of the grid. The routable map is configured to provide point-to-point routing within the layout.

Claims

1. A method of generating an open area map, the method comprising:

obtaining an image of a layout, the layout representing a real-world area in which a person moves about;

applying a grid on the image, the grid including tiles that fill in a ground area of the image; and

generating a routable map as a function of the grid,

wherein the routable map is configured to provide point-to-point routing within the layout as a function of the grid, the point-to-point routing including route calculation not dependent upon one or more predetermined path segments.

2. The method of claim 1, wherein the image of the layout comprises an image of a building floor plan.

3. The method of claim 1, wherein generating a routable map comprises:

designating a non-navigable area corresponding to the grid;

generating a plurality of reference regions; and

compiling the plurality of reference regions with the grid.

4. The method of claim 3, wherein generating the plurality of reference regions comprises:

identifying a plurality of reference image objects in the image; and

generating the plurality of reference regions by forming borders corresponding to the respective reference image objects.

5. The method of claim 4, wherein forming the borders comprises vectorizing a portion of a binarized image.

6. The method of claim 4, wherein the borders are associated with non-navigable tiles.

7. The method of claim 4, wherein the borders are associated with removed tiles.

8. The method of claim 3, wherein tiles within the plurality of reference regions are linked to the respective reference regions.

9. The method of claim 3, wherein the grid and the plurality of reference regions are in separate spatial layers prior to compilation.

10. The method of claim 1, wherein the tiles are substantially uniform.

11. The method of claim 1, wherein the point-to-point routing comprises generating a path via connected tiles.

12. A method of generating an open area floor plan, the method comprising:

obtaining a first graphical representation of a first floor plan, the first graphical representation corresponding to a real-world floor layout for a floor of a building;

applying a first grid on the first graphical representation; and

generating a first routable floor plan as a function of the first grid,

wherein the first routable floor plan is configured to provide point-to-point routing as a function of the first grid, the point-to-point routing including route calculation not dependent upon one or more predetermined path segments.

13. The method of claim 12, further comprising:

obtaining a second graphical representation of a second floor plan, the second graphical representation corresponding to a real-world floor layout for another floor of the building;

applying a second grid on the second graphical representation;

generating a second routable floor plan as a function of the second grid; and

linking the first routable floor plan and the second routable floor plan via a connection point.

14. The method of claim 13, wherein the connection point represents an elevator, a stairwell, or an escalator.

15. A method of routing in an open area map, the method comprising:

identifying a destination selected in the open area map, the open area map including an image of a layout representing a real-world area in which a person moves about, wherein the open area map further including an underlying grid;

calculating a route from an origin point to the selected destination in the open area map as a function of the underlying grid, wherein the route calculation is not dependent upon one or more predetermined path segments; and

generating a path from the origin point to the selected destination based on the calculation,

wherein the path is generated via connected tiles of the underlying grid.

16. The method of claim 15, wherein each of the connected tiles has a size that corresponds to an area of approximately 1 meter square.

17. The method of claim 15, wherein the connected tiles comprise tiles that are linked via a connection point.

18. The method of claim 15, wherein calculating the route comprises using a Douglas-Peucker method.

19. The method of claim 15, wherein the selected destination comprises any reference region in the image of the layout.

20. A method of generating an open area map, the method comprising:

receiving a map image;

overlaying a mesh on the map image, the mesh providing a grid pattern on the map image;

identifying a plurality of reference objects in the map image;

generating a plurality of reference regions by forming borders that outline the respective reference objects; and

generating a routable map by compiling the plurality of reference regions with the mesh,

wherein the routable map is configured to provide routing to and from any of the plurality of reference regions based on the compiled mesh, the routing including route calculation not dependent upon one or more predetermined path segments.

21. The method of claim 20, wherein the plurality of reference regions represent rooms of a building floor.

22. The method of claim 20, wherein the borders correspond to walls.

23. The method of claim 20, wherein the mesh comprises a three-dimensional grid.

24. The method of claim 20, wherein the map image corresponds to a temporary layout of a building floor, the temporary layout existing in the real-world for less than about three months.

25. A computer-readable medium including computer-executable instructions for performing a method of generating an open area map, the method comprising:

obtaining a pre-existing image of a layout, the layout representing a real-world area in which a person moves about and wherein the pre-existing image includes walls; and

using the pre-existing image to form a grid of contiguous tiles, wherein the grid has a shape that corresponds to a pedestrian-accessible contiguous sub-area within the real-world area and wherein the shape has a boundary that corresponds to the walls in the pre-existing image,

wherein the grid of contiguous tiles is configured to provide point-to-point routing, the point-to-point routing including route calculation not dependent upon one or more predetermined path segments.

26. A method of making a digital map of an area, wherein the digital map can be used by a routing software application to determine a route between a first location in the area to a second location in the area, the method comprising:

overlaying an image of the area with a grid of regular-sized tiles;

associating each tile that overlays a navigable portion of the image with a property that permits travel to another tile immediately adjacent thereto that overlays another navigable portion of the image; and

storing a data file as a digital map of the area, wherein the data file includes a representation of the tiles and their corresponding locations, and wherein the digital map is configured to provide point-to-point routing as a function of the tiles, the point-to-point routing including route calculation not dependent upon one or more predetermined path segments.

27. A method of making a digital map of an area, wherein the digital map can be used by a routing software application to determine a route between a first location in the area to a second location in the area, the method comprising:

overlaying an image of the area with a grid of regular-sized tiles;

associating each tile with a navigable property selected from a plurality of navigable properties, wherein the navigable property of a tile is inherited from that portion of the image overlaid thereby, and wherein the navigable properties include (i) non-navigable and (ii) navigable to another navigable tile immediately adjacent thereto;

and

storing a data file as a digital map of the area, wherein the data file includes a representation of the tiles, their corresponding locations and the navigable properties associated therewith, and wherein the digital map is configured to provide point-to-point routing as a function of the tiles corresponding to the (ii) navigable property, the point-to-point routing including route calculation not dependent upon one or more predetermined path segments.

28. A data representation of an area, wherein the data representation is stored on a computer-readable medium, the data representation comprising:

a data structure that represents a grid of regular-sized tiles, wherein the data structure includes data that indicates positions of each of the tiles; and

an associated image of the area,

wherein the positions of the tiles correspond to navigable portions of the area in the image, and wherein the grid of regular-sized tiles is configured to provide point-to-point routing, the point-to-point routing including route calculation not dependent upon one or more predetermined path segments.