Indoor localization based on ultrasound sensors

• US 8,504,292 B1
• Filed: 05/05/2011
• Issued: 08/06/2013
• Est. Priority Date: 05/05/2011
• Status: Active Grant

• Current Assignee: Bentley Systems Incorporated
• Original Assignee: Bentley Systems Incorporated
• Inventors: Ct, Stphane, Girard, Gabriel, Zlatanova, Sisi, Barrette, Yannick, van Oosterom, Peter, St-Pierre, Johanne
• Primary Examiner(s): Camby, Richard M.
• Application Number:
  US13/101,918
• Time in Patent Office: 824 Days
• Field of Search: 701500-510, 701/514, 701/519, 701/530, 701/492
• US Class Current: 701/500
• CPC Class Codes: G01C 21/1652 with ranging devices, e.g. LIDAR or RADAR
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01S 15/66 Sonar tracking systems
• CPC Class Codes: G01S 15/86 Combinations of sonar systems with lidar systems; Combinations of sonar systems with systems not using wave reflection
• CPC Class Codes: G01S 15/87 Combinations of sonar systems
• CPC Class Codes: G01S 17/66 Tracking systems using electromagnetic waves other than radio waves
• CPC Class Codes: G01S 17/86 Combinations of lidar systems with systems other than lidar, radar or sonar, e.g. with direction finders
• CPC Class Codes: G01S 17/87 Combinations of systems using electromagnetic waves other than radio waves

Abstract

In one embodiment, a technique for determining a position of a user inside of a structure is disclosed. Acceleration and orientation data is captured by an inertial motion unit (IMU) affixed to the user. Range data is captured by one or more range finders affixed to the user. An estimate of the user'"'"'s relative displacement is produced based on the acceleration and orientation data captured by the IMU. A cloud of particles is generated within a model of the structure based on the estimated relative displacement. One or more particle filters are applied to the cloud of particles to eliminate any particles of the cloud of particles that violate physical constraints and to eliminate any particles of the cloud of particles that are inconsistent with the range data. Then a statistical function is applied to the cloud of particles to determine a calculated position of the user.

Claims

1. A method for determining a position of a user inside of a structure, comprising:

capturing acceleration and orientation data by an inertial motion unit (IMU) affixed to the user descriptive of acceleration and orientation of the user;

capturing range data by one or more range finders affixed to the user descriptive of distances from the user to physical constraints within the structure;

producing an estimate of the user'"'"'s relative displacement based on the acceleration and orientation data captured by the IMU;

generating a cloud of particles within a model of the structure based on the estimate of the user'"'"'s relative displacement, wherein each particle of the cloud of particles represents a possible position of the user;

applying one or more particle filters to the cloud of particles to

eliminate any particles of the cloud of particles that violate physical constraints, and

eliminate any particles of the cloud of particles that are inconsistent with the range data captured by the one or more range finders; and

applying a statistical function to the cloud of particles to determine a calculated position of the user.

2. The method of claim 1 further comprising:

initializing a starting position of the user by creating an existing cloud of particles.

3. The method of claim 2, wherein the initializing is in response to receipt of a manual selection of the starting position from the user on a map of the structure.

4. The method of claim 1 wherein the generating further comprises

applying an estimated error size to the estimate of the user'"'"'s relative displacement;

generating a set of motion vectors that fall within the estimated error size;

applying each motion vector of the set to each particle in an existing cloud of particles to generate a new cloud of particles.

5. The method of claim 1, comprising:

comparing particles of the cloud of particles; and

merging any particles that are within a minimum distance of each other into a single particle.

6. The method of claim 1, wherein particles of the cloud of particles are determined to be inconsistent with the range data based on a weight assigned to each of the particles that is proportional to similarity between a distance in the model from the particle to a representation of the physical constraint, and a distance from the user to physical constraints within the structure.

7. The method of claim 1, wherein the statistical function is a weighted average of the particles in the cloud or particles.

8. The method of claim 1, further comprising:

providing the calculated position of the user to an application that consumes position data.

9. The method of claim 8, wherein the application is one of an augmented reality (AR) application and a user guidance application.

10. The method of claim 1, wherein the one or more range finders are ultrasonic range finders.

11. The method of claim 1, wherein the one or more range finders comprise two range finders affixed to a support structure that directs the range finders to lateral sides of the user.

12. The method of claim 1, wherein the IMU is affixed to a foot of the user.

13. The method of claim 1, wherein the producing, generating, applying one or more particle filters, and applying a statistical function are implemented by a portable electronic device.

14. The method of claim 13, wherein the one or more range finders are secured to the portable electronic device.

15. An apparatus to determine a position of a user inside of a structure, comprising:

an inertial motion unit (IMU) configured to capture acceleration and orientation data descriptive of the acceleration and orientation of a user;

one or more range finders configured to capture range data descriptive of distances from the user to physical constraints within the structure;

a processor;

a memory configured to store instructions for a position determination process that are executable on the processor, the instructions for the position determination process, when executed, operable to;

produce an estimate of the user'"'"'s relative displacement based on the acceleration and orientation data captured by the IM,

generate a cloud of particles within a model of the structure based on the estimate of the user'"'"'s relative displacement, wherein each particle of the cloud of particles represents a possible position of the user,

apply one or more particle filters to the cloud of particles to eliminate any particles of the cloud of particles that violate physical constraints and to eliminate any particles of the cloud of particles that are inconsistent with the range data captured by the one or more range finders,

apply a statistical function to the cloud of particles to determine a calculated position of the user.

16. The apparatus of claim 15, wherein particles of the cloud of particles are determined to be inconsistent with the range data based on a weight assigned to each of the particles that is proportional to similarity between a distance in the model from the particle to a representation of the physical constraint, and a distance from the user to physical constraints within the structure.

17. The apparatus of claim 15, wherein the memory is further configured to store instructions for an application that consumes position data, and the instructions for the position determination process, when executed, are further operable to:

provide the calculated position of the user to the application that consumes position data.

18. The apparatus of claim 15, wherein the one or more range finders are ultrasonic range finders.

19. The apparatus of claim 15, wherein at least the processor and the memory are portions of a portable electronic device to which the one or more range finders are secured.

20. A non-transitory computer-readable medium that includes instructions executable on a processor, the instructions, when executed, operable to:

produce an estimate of the user'"'"'s relative displacement based on captured acceleration and orientation data from an inertial motion unit (IMU) affixed to the user;

generate a cloud of particles within a model of the structure based on the estimate of the user'"'"'s relative displacement, wherein each particle of the cloud of particles represents a possible position of the user;

apply one or more particle filters to the cloud of particles to

eliminate any particles of the cloud of particles that violate physical constraints, and

eliminate any particles of the cloud of particles that are inconsistent with the range data captured by the one or more range finders affixed to the user and descriptive of distances from the user to physical constraints within the structure; and

apply a statistical function to the cloud of particles to determine a calculated position of the user.