Extraction of walking direction from device orientation and reconstruction of device orientation during optimization of walking direction

• US 9,838,846 B1
• Filed: 07/31/2015
• Issued: 12/05/2017
• Est. Priority Date: 08/01/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Le Grand, Etienne
• Primary Examiner(s): Schwartz, Joshua
• Application Number:
  US14/815,500
• Time in Patent Office: 858 Days
• Field of Search: 4554561-4566
• CPC Class Codes: G01C 21/14 by recording the course traversed by the object G01C21/16 takes precedence
• CPC Class Codes: G01C 22/006 Pedometers
• CPC Class Codes: H04W 4/026 using orientation information, e.g. compass

Abstract

A method implemented by one or more processors may include determining a rotation between a client device frame and a world frame, determining a rotation between an average gravity aligned (AGA) frame of the client device and the client device frame, performing step detection of the client device, and determining a change in orientation from a first detected step to a second detected step. In one example, computing the change in orientation includes determining a rotation between a horizontally projected AGA (HPAGA) frame and the AGA frame, determining a rotation between the world frame and the HPAGA frame, and determining the change in orientation by using the rotation between the world frame and the HPAGA frame. The method may also include determining, using the computed change in orientation, pedestrian dead reckoning data of the client device over a time period, and determining an output location estimate of the client device using the pedestrian dead reckoning data.

Claims

1. A method comprising:

determining, by one or more processors of a computing device, a rotation between a client device coordinate frame defined with respect to a client device and a world coordinate frame defined with respect to a world;

determining, by the one or more processors, a rotation between an average gravity aligned (AGA) coordinate frame defined with respect to an average gravity measurement of the client device and the client device coordinate frame;

performing, by the one or more processors, step detection associated with the client device;

determining, by the one or more processors, a change in orientation associated with the client device from a first detected step to a second detected step, wherein computing the change in orientation includes;

determining a rotation between a horizontally projected AGA (HPAGA) coordinate frame that corresponds to the AGA coordinate frame when a vertically oriented Z-axis of the AGA coordinate frame is aligned with a vertically oriented Z-axis of the world coordinate frame and the AGA coordinate frame, wherein a horizontally oriented X-axis of the HPAGA coordinate frame represents an orientation associated with the device;

determining a rotation between the world coordinate frame and the HPAGA coordinate frame, wherein determining the rotation between the world coordinate frame and the HPAGA coordinate frame uses the rotation between the client device coordinate frame and the world coordinate frame, the rotation between the AGA coordinate frame and the client device coordinate frame, and the rotation between the HPAGA coordinate frame and the AGA coordinate frame; and

determining the change in orientation associated with the client device from the first detected step to the second detected step by using the rotation between the world coordinate frame and the HPAGA coordinate frame;

determining, by the one or more processors and using the computed change in orientation, pedestrian dead reckoning data of the client device over a time period; and

determining, by the one or more processors, an output location estimate of the client device using the pedestrian dead reckoning data.

2. The method of claim 1, further comprising:

determining, by the one or more processors, a rotation between a user coordinate frame defined with respect to a user of the client device and the HPAGA coordinate frame;

determining, by the one or more processors, a rotation between the user coordinate frame and the world coordinate frame, wherein determining the rotation between the user coordinate frame and world coordinate frame uses the rotation between the client device coordinate frame and the world coordinate frame, the rotation between the AGA coordinate frame and the client device coordinate frame, the rotation between the HPAGA coordinate frame and the AGA coordinate frame, and the rotation between the user coordinate frame and the HPAGA coordinate frame; and

wherein determining the pedestrian dead reckoning data includes using the rotation between the user coordinate frame and the world coordinate frame.

3. The method of claim 1, wherein determining the change in orientation further includes:

determining first user yaw data corresponding to the first step and second user yaw data corresponding to the second step, wherein determining the first user yaw data and the second user yaw data includes using the rotation between the world coordinate frame and the HPAGA coordinate frame; and

comparing the first user yaw data and the second user yaw data.

4. The method of claim 1, further comprising identifying time slices during which the rotation between the client device coordinate frame and the world coordinate frame varies less than a predetermined amount, and wherein one or more of determining the rotation between the AGA coordinate frame and the client device coordinate frame, performing step detection of the client device, or determining the change in orientation from the first detected step to the second detected step includes using data corresponding to the identified time slices and excluding data that does not correspond to the identified time slices.

5. The method of claim 1, further comprising:

performing, by the one or more processors, window averaging of determined changes in orientation; and

determining the pedestrian dead reckoning data using the window averaged determined changes in orientation.

6. The method of claim 1, wherein determining the output location estimate includes performing a simultaneous localization and mapping (SLAM) optimization of the location of the client device based on the pedestrian dead reckoning data.

7. The method of claim 6, wherein determining the output location estimate includes performing the SLAM optimization of the location of the client device based on data generated by one or more sensors of the client device, wherein the one or more sensors include a global positioning system (GPS) receiver, a Wi-Fi sensor, a Bluetooth sensor, or a magnetometer.

8. The method of claim 7, wherein determining the output location estimate includes performing the SLAM optimization of the location of the client device based on magnetometer data generated by a magnetometer of the client device, further wherein determining the output location estimate includes processing the magnetometer data using a rotation from the client device coordinate frame to the world coordinate frame.

9. The method of claim 8, further comprising determining the rotation from the client device coordinate frame to the world coordinate frame by using a rotation from the HPAGA coordinate frame to the world coordinate frame and a rotation from the client device coordinate frame to the HPAGA coordinate frame.

10. A non-transitory computer-readable medium having stored therein instructions, that when executed by one or more processors of a computing device, cause the computing device to perform functions comprising:

determining, by one or more processors of a computing device, a rotation between a client device coordinate frame defined with respect to a client device and a world coordinate frame defined with respect to a world;

determining, by the one or more processors, a rotation between an average gravity aligned (AGA) coordinate frame defined with respect to an average gravity measurement of the client device and the client device coordinate frame;

performing, by the one or more processors, step detection associated with the client device;

determining, by the one or more processors, a change in orientation associated with the client device from a first detected step to a second detected step, wherein computing the change in orientation includes;

determining a rotation between a horizontally projected AGA (HPAGA) coordinate frame that corresponds to the AGA coordinate frame when a vertically oriented Z-axis of the AGA coordinate frame is aligned with a vertically oriented Z-axis of the world coordinate frame and the AGA coordinate frame, wherein a horizontally oriented X-axis of the HPAGA coordinate frame represents an orientation associated with the device;

determining a rotation between the world coordinate frame and the HPAGA coordinate frame, wherein determining the rotation between the world coordinate frame and the HPAGA coordinate frame uses the rotation between the client device coordinate frame and the world coordinate frame, the rotation between the AGA coordinate frame and the client device coordinate frame, and the rotation between the HPAGA coordinate frame and the AGA coordinate frame; and

determining the change in orientation associated with the client device from the first detected step to the second detected step by using the rotation between the world coordinate frame and the HPAGA coordinate frame;

determining, by the one or more processors and using the computed change in orientation, pedestrian dead reckoning data of the client device over a time period; and

determining, by the one or more processors, an output location estimate of the client device using the pedestrian dead reckoning data.

11. The non-transitory computer-readable medium of claim 10, wherein the functions further comprise:

determining, by the one or more processors, a rotation between a user coordinate frame defined with respect to a user of the client device and the HPAGA coordinate frame;

determining, by the one or more processors, a rotation between the user coordinate frame and the world coordinate frame, wherein determining the rotation between the user coordinate frame and world coordinate frame uses the rotation between the client device coordinate frame and the world coordinate frame, the rotation between the AGA coordinate frame and the client device coordinate frame, the rotation between the HPAGA coordinate frame and the AGA coordinate frame, and the rotation between the user coordinate frame and the HPAGA coordinate frame; and

further wherein determining the pedestrian dead reckoning data includes using the rotation between the user coordinate frame and the world coordinate frame.

12. The non-transitory computer-readable medium of claim 10, wherein determining the change in orientation further includes:

determining first user yaw data corresponding to the first step and second user yaw data corresponding to the second step, wherein determining the first user yaw data and the second user yaw data includes using the rotation between the world coordinate frame and the HPAGA coordinate frame; and

comparing the first user yaw data and the second user yaw data.

13. The non-transitory computer-readable medium of claim 10, wherein

determining the output location estimate includes performing a simultaneous localization and mapping (SLAM) optimization of the location of the client device based on the pedestrian dead reckoning data.

14. The non-transitory computer-readable medium of claim 13, wherein determining the output location estimate includes performing the SLAM optimization of the location of the client device based on data generated by one or more sensors of the client device, wherein the one or more sensors include a global positioning system (GPS) receiver, a Wi-Fi sensor, a Bluetooth sensor, or a magnetometer.

15. The non-transitory computer-readable medium of claim 14, wherein determining the output location estimate includes performing the SLAM optimization of the location of the client device based on magnetometer data generated by a magnetometer of the client device, further wherein determining the output location estimate includes processing the magnetometer data using a rotation from the client device coordinate frame to the world coordinate frame.

16. The non-transitory computer-readable medium of claim 15, wherein the functions further comprise determining the rotation from the client device coordinate frame to the world coordinate frame by using a rotation from the HPAGA coordinate frame to the world coordinate frame and a rotation from the client device coordinate frame to the HPAGA coordinate frame.

17. A system comprising:

at least one processor; and

a computer-readable medium, configured to store instructions, that when executed by the at least one processor, cause the system to perform functions comprising;

determining, by one or more processors of a computing device, a rotation between a client device coordinate frame defined with respect to a client device and a world coordinate frame defined with respect to a world;

determining, by the one or more processors, a rotation between an average gravity aligned (AGA) coordinate frame defined with respect to an average gravity measurement of the client device and the client device coordinate frame;

performing, by the one or more processors, step detection associated with the client device;

determining, by the one or more processors, a change in orientation associated with the client device from a first detected step to a second detected step, wherein computing the change in orientation includes;

determining a rotation between a horizontally projected AGA (HPAGA) coordinate frame that corresponds to the AGA coordinate frame when a vertically oriented Z-axis of the AGA coordinate frame is aligned with a vertically oriented Z-axis of the world coordinate frame and the AGA coordinate frame, wherein a horizontally oriented X-axis of the HPAGA coordinate frame represents an orientation associated with the device;

determining a rotation between the world coordinate frame and the HPAGA coordinate frame, wherein determining the rotation between the world coordinate frame and the HPAGA coordinate frame uses the rotation between the client device coordinate frame and the world coordinate frame, the rotation between the AGA coordinate frame and the client device coordinate frame, and the rotation between the HPAGA coordinate frame and the AGA coordinate frame; and

determining the change in orientation associated with the client device from the first detected step to the second detected step by using the rotation between the world coordinate frame and the HPAGA coordinate frame;

determining, by the one or more processors and using the computed change in orientation, pedestrian dead reckoning data of the client device over a time period; and

determining, by the one or more processors, an output location estimate of the client device using the pedestrian dead reckoning data.

18. The system of claim 17, wherein the functions further comprise:

determining, by the one or more processors, a rotation between a user coordinate frame defined with respect to a user of the client device and the HPAGA coordinate frame;

determining, by the one or more processors, a rotation between the user coordinate frame and the world coordinate frame, wherein determining the rotation between the user coordinate frame and world coordinate frame uses the rotation between the client device coordinate frame and the world coordinate frame, the rotation between the AGA coordinate frame and the client device coordinate frame, the rotation between the HPAGA coordinate frame and the AGA coordinate frame, and the rotation between the user coordinate frame and the HPAGA coordinate frame; and

further wherein determining the pedestrian dead reckoning data includes using the rotation between the user coordinate frame and the world coordinate frame.

19. The system of claim 17, wherein determining the change in orientation further includes:

determining first user yaw data corresponding to the first step and second user yaw data corresponding to the second step, wherein determining the first user yaw data and the second user yaw data includes using the rotation between the world coordinate frame and the HPAGA coordinate frame; and

comparing the first user yaw data and the second user yaw data.

20. The system of claim 17, wherein determining the output location estimate includes performing a simultaneous localization and mapping (SLAM) optimization of the location of the client device based on the pedestrian dead reckoning data.