Indoor location-based service

Patent metadata

Field	Value
Publication number	US-12467755-B2
Application number	US-201917056380-A
Country	US
Kind code	B2
Filing date	Jun 18, 2019
Priority date	Jun 29, 2018
Publication date	Nov 11, 2025
Grant date	Nov 11, 2025

Abstract

In implementations of the subject matter described herein, a solution for providing an indoor location-based service is provided. In this solution, a floor plan about a first floor of a first building comprising at least one floor is obtained. A first map for the first floor is generated based on the floor plan. The first map includes a plurality of vertices and edges, where one vertex corresponds to a position on the first floor, an edge connecting two vertices represents a physical object or a passable path on the first floor, and two positions corresponding to the two vertices are located at the physical object or on the passable path. Moreover, a location-based service is provided to a user at least based on the first map.

First claim

The invention claimed is:

1 . A computer-implemented method, comprising:
obtaining a floor plan about a first floor of a first building comprising at least one floor; identifying, using a floor parsing module, vertices and edges on the floor plan for the first floor and generating a first map for the first floor based on the floor plan, the first map including the identified vertices and edges, wherein one vertex corresponds to a position on the first floor, an edge connecting two vertices represents a physical object or a passable path on the first floor, and two positions corresponding to the two vertices are located at the physical object or on the passable path; preprocessing the first map using a triangulation module to add new edges to the first map by applying triangulation to the vertices by inserting edges between endpoints of the vertices until the first floor is divided into triangles, each triangle having an empty interior, and using a topology construction module to add a topology vertex to each new edge, the topology vertex representing a passable position on the floor plan; determining, using a path construction module, a path between a starting position and a destination position on the first map using the topology vertices of the new edges; collecting, via sensors of a user device, real-time environment data comprising at least one of WiFi signal data, geomagnetic signal data, and barometer signal data; binding the determined path with the collected environment data by storing the environment data in an environment database, associating the stored environment data with corresponding positions along the determined path, and determining a current position of the user device by comparing current sensor data to the stored environment data; providing a location-based service comprising navigation instructions to the user device at least based on the determined path; and updating the navigation instructions in real-time as the user device moves along the determined path based on the collected environment data.

2 . The method according to claim 1 , wherein providing the location-based service to the user device at least based on the determined path comprises:
obtaining the starting position and the destination position of the user device on the first map; wherein determining the path between the starting position and the destination position comprises determining the path from the starting position to the destination position at least based on the first map, the determined path being represented by a sequence of vertices and edges from the plurality of vertices and edges, and providing the determined path to the user device.

3 . The method according to claim 1 , wherein generating the first map comprises:
generating an initial map for the first floor based on the floor plan, the initial map including a first group of vertices and edges representing outlines of physical objects on the first floor; optimizing the initial map to generate a second map for the first floor, the second map including a second group of vertices and edges derived from optimizing the first group of vertices and edges; and generating the first map based on the second map.

4 . The method according to claim 3 , wherein optimizing the initial map comprises:
identifying a specific physical object from the first group of vertices and edges, the specific physical object being represented by a set of vertices and edges having a specific feature; and removing, from the set of vertices and edges, at least one of a redundant vertex and a redundant edge.

5 . The method according to claim 4 , wherein the specific physical object comprises a door.

6 . The method according to claim 3 , wherein optimizing the initial map comprises:
removing at least one of the following from the initial map: an overlapped edge, an intersection of edges and a gap between edges.

7 . The method according to claim 3 , wherein generating the first map based on the second map comprises:
generating a third map by applying triangulation to the second map, the third map including the second group of vertices and edges and at least one edge added through the triangulation; and generating the first map by adding at least one of following to the third map based on heuristics: a vertex representing a position on a passable path on the first floor, wherein the vertex is on the at least one edge, and an edge representing a passable path on the first floor.

8 . The method according to claim 7 , further comprising:
optimizing the generated first map based on a predetermined rule to avoid an existence of unreasonable topology information in the first map.

9 . The method according to claim 1 , wherein the first building further comprises a second floor connected with the first floor, and the method further comprises:
obtaining first information about a connection between the first floor and the second floor; combining the first map and a fourth map for the second floor based on the first information to generate a fifth map for the first building, and providing the location-based service to the user device based on the fifth map.

10 . The method according to claim 9 , wherein the first building is connected with the second building, and the method further comprises:
obtaining second information about a connection between the first building and the second building; combining the fifth map and a sixth map for the second building based on the second information; and providing the location-based service to the user device based on the combined map.

11 . An electronic device, comprising:
a processing unit; and a memory coupled to the processing unit and storing instructions executable by the processing unit, the instructions, when executed by the processing unit, causing the device to perform acts comprising: obtaining a floor plan about a first floor of a first building comprising at least one floor; identifying vertices and edges on the floor plan for the first floor; generating a map for the first floor based on the floor plan, the map including the identified vertices and edges, wherein one vertex corresponds to a position on the first floor, an edge connecting two vertices represents a physical object or a passable path on the first floor, and two positions corresponding to the two vertices are located at the physical object or on the passable path; preprocessing the first map to add new edges to the first map by applying triangulation to the vertices by inserting edges between endpoints of the vertices until the first floor is divided into triangles, each triangle having an empty interior, and to add a topology vertex to each new edge, the topology vertex representing a passable position on the floor plan; determining a path between a starting position and a destination position on the first map using the topology vertices of the new edges; collecting, via sensors of a user device, real-time environment data comprising at least one of WiFi signal data, geomagnetic signal data, and barometer signal data; binding the determined path with the collected environment data by storing the environment data in an environment database, associating the stored environment data with corresponding positions along the determined path, and determining a current position of the user device by comparing current sensor data to the stored environment data; providing a location-based service comprising navigation instructions to the user device at least based on the determined path; and updating the navigation instructions in real-time as the user device moves along the determined path based on the collected env

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Karlsson Börje Felipe Fernandes
• Shu Yuanchao
• Du Ruogu
• Jiang Yi

Classifications

• H04W4/025

  using location based information parameters · CPC title

• G01C21/3867

  Geometry of map features, e.g. shape points, polygons or for simplified maps · CPC title

• G01C21/383

  Indoor data · CPC title

• H04W4/33

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

• H04W4/024

  Guidance services · CPC title