Localization using tessellated grids

Patent metadata

Field	Value
Publication number	US-12498250-B2
Application number	US-202017134224-A
Country	US
Kind code	B2
Filing date	Dec 25, 2020
Priority date	Dec 25, 2020
Publication date	Dec 16, 2025
Grant date	Dec 16, 2025

Abstract

Examples for localization using tessellated grids are described. In an example, a plurality of physical entities can be identified in an indoor space and each physical entity can be georeferenced to a coordinate system. The indoor space can be divided into a grid of polygonal tiles abutting adjacent polygonal tiles, and arranged in a hierarchical structure with the tiles in one level of the hierarchical structure being substantially representable by polygonal tiles in other levels of the hierarchical structure. The grid is then spatially indexed by associating each physical entity with a polygonal tile from amongst the polygonal tiles in each hierarchical level, thereby correlating a georeference of the physical entity with the polygonal tile. Based on the spatial indexing, a grid map for the indoor space can be generated for localizing mobile devices in the indoor space.

First claim

What is claimed is:

1 . A method comprising:
identifying a plurality of physical entities in an indoor space, wherein a physical entity represents a structural feature of the indoor space and is not a network source and a signal source; georeferencing each of the physical entities to a coordinate system; dividing the indoor space into a grid of a plurality of polygonal tiles abutting adjacent polygonal tiles, the grid comprising a hierarchical structure of the plurality of polygonal tiles, wherein a polygonal tile at a level in the hierarchical structure is representable by polygonal tiles at other levels in the hierarchical structure; indexing, spatially, the grid with the physical entities in the indoor space, the indexing comprising associating each physical entity with a polygonal tile from amongst the plurality of polygonal tiles in each hierarchical level in the hierarchical structure to correlate a georeference of the physical entity with the polygonal tile in each hierarchical level; implementing an identifier allocation scheme to associate an identifier with each of the plurality of polygonal tiles, the identifier having the georeference embedded therein, the identifier allocation scheme is based on parameters associated with the polygonal tile, the parameters including at least one of an orientation of the polygonal tile, a size of the polygonal tile, and polygonal tiles neighboring the polygonal tile; and generating a grid map for the indoor space based on the indexing for localization of mobile devices in the indoor space, wherein spatial data of a mobile device is compared with a set of georeferences for the indoor space to identify a polygonal tile in which the mobile device is instantaneously located, the spatial data including sensor data obtained by the mobile device.

2 . The method of claim 1 , wherein the plurality of polygonal tiles have a symmetrical hexagon shape.

3 . The method of claim 1 , wherein the plurality of polygonal tiles have one of a same asymmetrical polygon shape and different symmetrical polygon shapes.

4 . The method of claim 1 , wherein a first set of polygonal tiles in one hierarchical level in the hierarchical structure are symmetrical and of a first shape and a second set of polygonal tiles in another hierarchical level in the hierarchical structure are symmetrical and of a second shape, wherein a plurality of second set of polygonal tiles cover a single polygonal tile from the first set.

5 . The method of claim 1 , wherein the indexing comprises spatially indexing child polygonal tiles from amongst the plurality of polygonal tiles hierarchically linked to a parent polygonal tile from amongst the plurality of polygonal tiles at a higher level in the hierarchical structure.

6 . The method as claimed in claim 1 , wherein the physical entity representing the structural feature of the indoor space includes at least of walls, passages, hallways, elevator shafts, escalators, open spaces, doorways, kiosks, stores, alleys, holes, a café, and a salon.

7 . The method as claimed in claim 1 , wherein based on association between the plurality of polygonal tiles on the grid map, analytics data is associated with the plurality of the polygonal tile to provide information pertaining to a selected polygonal tile.

8 . A server computing device comprising:
a processor; and a memory storing a set of instructions, the set of instructions executable in the processor to:
identify a plurality of physical entities in an indoor space, wherein a physical entity represents a structural feature of the indoor space and is not a network source and a signal source;
georeferencing each of the physical entities to a coordinate system;
divide the indoor space into a grid of a plurality of polygonal tiles abutting adjacent polygonal tiles, the grid comprising a hierarchical structure of the plurality of polygonal tiles, wherein a polygonal tile at a level in the hierarchical structure is representable by polygonal tiles at other levels in the hierarchical structure;
index, spatially, the grid with respect to the physical entities in the indoor space, the indexing comprising associating each physical entity with a polygonal tile from amongst the plurality of polygonal tiles in each hierarchical level in the hierarchical structure to correlate a georeference of the physical entity with the polygonal tile in each hierarchical level;
implement an identifier allocation scheme to associate an identifier with each of the plurality of polygonal tiles, the identifier having the georeference embedded therein, the identifier allocation scheme is based on parameters associated with the polygonal tile, the parameters including at least one of an orientation of the polygonal tile, a size of the polygonal tile, and polygonal tiles neighboring the polygonal tile; and
localize mobile devices in the indoor space based on the indexing, wherein a grid map is generated to represent the indoor space based on the indexing, wherein spatial data of a mobile device is compared with a set of georeferences for the indoor space to identify a polygonal tile in which the mobile device is instantaneously located, the spatial data including sensor data obtained by the mobile device.

9 . The server computing device of claim 8 , wherein the plurality of polygonal tiles have symmetrical hexagon shape.

10 . The server computing device of claim 8 , wherein the plurality of polygonal tiles have one of same asymmetrical polygon shape and different symmetrical polygon shapes.

11 . The server computing device of claim 8 , wherein a first set of polygonal tiles in one hierarchical level in the hierarchical structure are symmetrical and of a first shape and a second set of polygonal tiles in another hierarchical level in the hierarchical structure are symmetrical and of a second shape, wherein a plurality of second set of polygonal tiles cover a single polygonal tile from the first set.

12 . The server computing device of claim 8 further comprising instructions executable in the processor to index, spatially, with respect to the indoor space, child polygonal tiles from amongst the plurality of polygonal tiles hierarchically linked to a parent polygonal tile from amongst the plurality of polygonal tiles at a higher level in the hierarchical structure.

13 . The server computing device of claim 8 , wherein the physical entity representing the structural feature of the indoor space includes at least of walls, passages, hallways, elevator shafts, escalators, open spaces, doorways, kiosks, stores, alleys, holes, a café, and a salon.

14 . The server computing device of claim 8 , wherein based on association between the plurality of polygonal tiles on the grid map, analytics data is associated with the plurality of the polygonal tile to provide information pertaining to a selected polygonal tile.

Assignees

• Mapsted Corp

Inventors

• Huberman Sean
• Karon Joshua
• Mahmood Ahmed

Classifications

• H04W4/33 Primary

  for indoor environments, e.g. buildings · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G01C21/206

  specially adapted for indoor navigation · CPC title

• H04W4/029

  Location-based management or tracking services · CPC title

• G01C21/383 Primary

  Indoor data · CPC title