COLLABORATIVE CREATION OF INDOOR MAPS

• US 20140278060A1
• Filed: 02/12/2014
• Published: 09/18/2014
• Est. Priority Date: 05/31/2007
• Status: Active Grant

• Current Assignee: TRX Systems, Inc.
• Original Assignee: TRX Systems, Inc.
• Inventors: Kordari, Kamiar, Funk, Benjamin, Teolis, Carole, Napora, Jared, Karvounis, John, Hakim, Dan, Giles, Christopher, Politi, Carol
• Granted Patent: US 9,733,091 B2
• Time in Patent Office: Days
• US Class Current: 701/422
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/383 Indoor data

Abstract

This disclosure provides techniques for the creation of maps of indoor spaces. In these techniques, an individual or a team with no mapping or cartography expertise can contribute to the creation of maps of buildings, campuses or cities. An indoor location system can track the location of contributors in the building. As they walk through indoor spaces, an application may automatically create a map based on data from motion sensors by both tracking the location of the contributors and also inferring building features such as hallways, stairways, and elevators based on the tracked contributors'"'"' motions as they move through a structure. With these techniques, the process of mapping buildings can be crowd sourced to a large number of contributors, making the indoor mapping process efficient and easy to scale up.

Claims

1. A computer-implemented method for generating a building map of an indoor space, the method comprising:

collecting sensor data via an electronic network from each computing device among a plurality of computing devices;

estimating a location of each computing device;

determining motions of each computing device;

generating a plurality of graphical maps of one or more building features associated with the indoor space, each graphical map among the plurality of graphical maps being based on the location and the motions for each computing device;

correcting the plurality of graphical maps based on one or more constraints related to the indoor space to create a plurality of corrected graphical maps; and

merging the plurality of corrected graphical maps to generate the building map, the merging being based on a correlation between the one or more building features in the plurality of graphical maps.

2. The method of claim 1, wherein each computing device among the plurality of computing devices is connected to a user among a plurality of users moving about the indoor space, and wherein the building map is updated based on the location and the motions of each user among the plurality of users.

3. The method of claim 1, wherein the one or more building features are based on a history of location information and motion information associated with each computing device.

4. The method of claim 1, wherein the one or more building features are based on a confidence level based on the location of each computing device and prior information about the indoor space.

5. The method of claim 1, wherein the one or more constraints are imposed on the generation of the one or more building features of the plurality of graphical maps.

6. The method of claim 1, wherein the one or more constraints correct for angular drift associated with the motions.

7. The method of claim 1, wherein one or more of the plurality of computing devices is a smartphone.

8. The method of claim 1, wherein at least two or more building features among the one or more building features are connected to create a single building feature if each of the two or more building features are associated with two events.

9. The method of claim 8, wherein the two events include the location and an error bound of each computing device at a time of discovery of the two or more building features.

10. The method of claim 1, wherein generating the plurality of graphical maps includes representing the one or more building features with a graph model, wherein two locations in the graph model are connected by an edge if the one or more building features connect two estimated locations of each computing device.

11. The method of claim 1, wherein generating the plurality of graphical maps includes segmenting a path of each computing device and segmenting the path by floors of the indoor space.

12. The method of claim 1, wherein the plurality of graphical maps includes a plurality of nodes representing the one or more building features, and wherein generating the plurality of graphical maps includes clustering and merging two or more nodes among the plurality of nodes based on a weighted average of locations of the two or more nodes.

13. The method of claim 12, wherein the weighted average is weighted based on an occupancy of each of the two or more nodes and inversely weighted based on an error bound for each of the two or more nodes.

14. The method of claim 12, wherein generating the plurality of graphical maps further includes removing nodes with a low occupancy number.

15. The method of claim 12, wherein generating the plurality of graphical maps further includes determining a role of each node among the plurality of nodes, the role including one of a decision point node, an articulation point node, a corner point node, a leaf node, and a redundant node.

16. A computing system for generating a map of an indoor space, the computing system comprising:

a processor; and

a memory communicatively coupled to the processor, the memory bearing instructions that, when executed on the processor, cause the computing system to at least;

receive sensor data at the processor via an electronic network from each computing device among a plurality of computing devices, the sensor data being indicative of a location of each computing device in the indoor space and motions of each computing device in the indoor space;

classify the motions into an activity associated with a user of each computing device;

determine one or more building features of the indoor space based on the classification of the motions and the location of each computing device;

generate a plurality of graphical maps based on the one or more building features; and

merge the plurality of graphical maps to generate the map, the merging being based on a correlation between the one or more building features in the plurality of graphical maps.

17. The system of claim 16, wherein each computing device is connected to a user among a plurality of users moving about the indoor space.

18. The system of claim 16, wherein the one or more building features are based on a history of location information and motion information associated with each computing device.

19. The system of claim 16, wherein the one or more building features are based on a confidence level based on the location of each computing device and prior information about the indoor space.

20. The system of claim 16, wherein one or more constraints are imposed on the generation of the one or more building features.

21. The system of claim 20, wherein the one or more constraints correct for angular drift associated with the motions.

22. The system of claim 16, wherein each of the plurality of graphical maps connect two or more building features among the one or more building features to create a single building feature if each of the two or more building features are associated with two events.

23. The system of claim 22, wherein the two events include the location and an error bound of each computing device at a time of discovery of the two or more building features.

24. The system of claim 16, wherein the plurality of graphical maps are represented with a graph model, wherein two locations in the graph model are connected by an edge if the one or more building features connect two estimated locations of each computing device.

25. A computer readable storage medium comprising instructions that, when executed on a system configured to generate a map of an indoor space, cause the system to at least:

receive sensor data at the processor via an electronic network from each computing device among a plurality of computing devices, the sensor data being indicative of a location of each computing device in the indoor space and motions of each computing device in the indoor space;

classify the motions into an activity associated with a user of each computing device;

determine one or more building features of the indoor space based on the classification of the motions and the location of each computing device;

generate a plurality of graphical maps based on the one or more building features; and

merge the plurality of graphical maps to generate the map, the merging being based on a correlation between the one or more building features in the plurality of graphical maps.

26. The system of claim 25, wherein each computing device is connected to a user among a plurality of users moving about the indoor space.

27. The system of claim 25, wherein the one or more building features are based on a history of location information and motion information associated with each computing device.

28. The system of claim 25, wherein the one or more building features are based on a confidence level based on the location of each computing device and prior information about the indoor space.

29. The system of claim 25, wherein one or more constraints are imposed on the generation of the one or more building features.

30. The system of claim 29, wherein the one or more constraints correct for angular drift associated with the motions.

31. The system of claim 25, wherein each of the plurality of graphical maps connect two or more building features among the one or more building features to create a single building feature if each of the two or more building features are associated with two events.

32. The system of claim 31, wherein the two events include the location and an error bound of each computing device at a time of discovery of the two or more building features.

33. The system of claim 25, wherein the plurality of graphical maps are represented with a graph model, wherein two locations in the graph model are connected by an edge if the one or more building features connect two estimated locations of each computing device.