CROWD-SOURCING INDOOR LOCATIONS

• US 20150204676A1
• Filed: 08/15/2012
• Published: 07/23/2015
• Est. Priority Date: 08/15/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zhang, Faen, Chang, Edward Y., Zhou, Shuchang, Huang, Yongqiang
• Granted Patent: US 9,335,175 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01S 5/02526 using non-dedicated equipment, e.g. user equipment or crowd-sourcing
• CPC Class Codes: G01S 5/0264 at least one of the systems being a non-radio wave positioning system
• CPC Class Codes: G01S 5/0294 Trajectory determination or predictive filtering, e.g. target tracking or Kalman filtering
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings

Abstract

Aspects of the present disclosure provide techniques for constructing a scalable model of an indoor space using crowd-sourced inertial navigation system (INS) signals from mobile devices. By tracking INS signals from a number of participating users, the user'"'"'s trajectories can be estimated as they move their mobile devices indoors. The estimated trajectories can be scored against similar routes taken by other users. Routes with the highest scores are then laid out over a map of the indoor space to identify areas most often traveled to and from landmarks and distances between the landmarks.

Claims

1. A method, comprising:

identifying a map of an indoor space, the map being based on a plurality of constraints;

receiving inertial navigation signals from a first set of mobile devices moving through the indoor space, where the inertial navigation signals represent a direction and speed of movement of the mobile devices;

calculating, using a processor, a number of user trajectories based on the received set of inertial navigation signals;

identifying paths associated with the number of user trajectories, wherein each path comprises a number of turns traveled between a first position and a second position on the map;

determining a score for each of the identified paths based on a similarity of a given path to the number of user trajectories;

selecting at least one path from the identified paths that scores above a pre-determined threshold; and

generating, using the processor, map information based on at least one selected path that identifies walkable areas of the indoor space.

2. The method of claim 1, wherein the generated map information comprises wireless network access point identifiers and associated signal strengths collected along the identified paths.

3. The method of claim 2, further comprising refining the identified paths based on a comparison of the wireless network access point identifiers associated with each path, wherein the refining removes duplicate paths.

4. The method of claim 1, wherein the number of turns traveled along the identified paths comprises a directional indicator and a distance between each turn.

5. The method of claim 1, wherein the inertial navigation signals comprises one of:

accelerometer data, gyroscope data, and compass data.

6. The method of claim 1, wherein calculating the number of user trajectories comprises receiving information to identify a starting and ending position of an associated mobile device.

7. The method of claim 6, further comprising simplifying, using a smoothing algorithm, each user trajectory to a number of turns traveled between the starting and ending position of the given mobile device and a distance between each turn.

8. A system, comprising:

a memory storing maps of indoor spaces;

a receiver module to receive inertial navigation signals from a first set of mobile devices moving through the indoor space, where the inertial navigation signals represent a direction and speed of movement of the mobile devices; and

a processor coupled to the memory, the processor being configured to;

identify a map of an indoor space stored in the memory, the map being based on a plurality of constraints;

calculate a number of user trajectories based on the inertial navigation signals received at the receiver module;

identify paths associated with the number of user trajectories, wherein each path comprises a number of turns traveled between a first position and a second position on the map;

determine a score for each of the identified paths based on a similarity of a given path to the number of user trajectories;

select at least one path from the identified paths that score above a pre-determined threshold; and

generate map information based on at least one selected path that identifies walkable areas of the indoor space.

9. The system of claim 8, wherein the generated map information comprises wireless network access point identifiers and associated signal strengths collected along the identified paths.

10. The system of claim 8, wherein the number of turns traveled along the identified paths comprises a directional indicator and a distance between each turn.

11. The system of claim 8, wherein the set of inertial navigation signals comprises one of:

accelerometer data, gyroscope data, and compass data.

12. The system of claim 8, wherein to calculate the number of user trajectories the processor is further configured to receive information identifying a starting and ending position of an associated mobile device.

13. The system of claim 12, wherein the processor is further configured to simplify, using a smoothing algorithm, each user trajectory to a number of turns traveled between the starting and ending position and a distance between each turn.

14. A tangible computer-readable storage medium comprising instructions of a program, when executed by a processor, cause the processor to perform a method, the method comprising:

identifying a map of an indoor space, the map being based on a plurality of constraints;

receiving inertial navigation signals from a first set of mobile devices moving through the indoor space, where the inertial navigation signals represent a direction and speed of movement of the mobile devices;

calculating, using a processor, a number of user trajectories based on the received inertial navigation signals;

identifying paths associated the number of user trajectories, wherein each path comprises a number of turns traveled between a first position and a second position on the map;

determining a score for each of the identified paths based on a similarity of a given path to the user trajectories;

selecting at least one path from the identified paths that score above a pre-determined threshold; and

generating, using the processor, map information based on at least one of the selected set of paths that identifies walkable areas of the indoor space.

15. The tangible computer-readable storage medium 14, wherein the generated map information comprises wireless network access point identifiers and associated signal strengths collected along the identified paths.

16. The tangible computer-readable storage medium 15, wherein the method further comprising refining the identified paths based on a comparison of the wireless network access point identifiers associated with each path, wherein the refining removes duplicate paths.

17. The tangible computer-readable storage medium 14, wherein the number of turns traveled along the identified paths comprises a directional indicator and a distance between each turn.

18. The tangible computer-readable storage medium 14, wherein the inertial navigation signals comprises one of:

accelerometer data, gyroscope data, and compass data.

19. The tangible computer-readable storage medium 14, wherein calculating the number of user trajectories comprises receiving information to identify a starting and ending position of an associated mobile device.

20. The tangible computer-readable storage medium 19, wherein each user trajectory is simplified, using a smoothing algorithm, to a number of turns traveled between the starting and ending position of the associated mobile device and a distance between each turn.