Method for step detection and gait direction estimation

1. A computer-implemented method for detecting the steps of a person and estimating the person's three-dimensional (3D) movement to track a location of the person, comprising:

collecting accelerometer data from a worn or person carried device that includes an accelerometer in an unknown tilted orientation relative to a ground frame as the person moves around a physical location, the accelerometer data being indicative of the person's 3D movement relative to the ground frame and sampled based on movement of the person, the accelerometer data comprising x-axis data, y-axis data and z-axis data that corresponds to the movement of the person over a period of time and storing the accelerometer data in a non-transitory memory of a computer having a processor, wherein the person's 3D movement relative to the ground frame forms a reference frame for the device;

determining tilt data indicative of the accelerometer's orientation relative to the ground frame using the accelerometer data;

generating improved accelerometer data indicative of the accelerometer's orientation relative to the reference frame for the device by filtering the accelerometer data using the tilt data;

storing the improved accelerometer data in the non-transitory memory;

generating stride data based on the improved accelerometer data, comprising:

finding by the processor a local minima and a local maxima to detect each step by the person;

finding by the processor an x-displacement along the x-axis and a y-displacement along the y-axis for each step by the person based on the improved accelerometer data for the x-axis and the y-axis and storing the x-displacement and the y-displacement in the memory;

calculating by the processor a two-dimensional (2D) movement displacement and a translation direction for each stride by the person based at least on the x-displacement and the y-displacement; and

calculating by the processor an elevation change of the person and storing the elevation change in the memory; and

estimating a 3D movement to track the location of the person, on a step by step basis based at least on the stride data.

2. The computer-implemented method as recited in claim 1 , wherein the device is a smartphone that includes an accelerometer.

3. The computer-implemented method as recited in claim 1 , wherein the accelerometer data is sampled at a frequency greater than twice a Nyquist frequency of the movement of the person.

4. The computer-implemented method as recited in claim 1 , wherein the device further includes a gyroscope adding to the x-axis data, the y-axis data and the z-axis data for the device.

5. The computer-implemented method as recited in claim 1 , wherein the local minima occurs after each heel strike and wherein the local maxima occurs after each passive position.

6. The computer-implemented method as recited in claim 1 , wherein utilizing the processor to find the local minima and the local maxima includes utilizing the processor to reduce extraneous detections by determining if there are any neighboring minima within a sample window of a first number of samples before a local minima and a second number samples after each local minima, and not counting any neighboring minima within the sample window as a local minima.

7. The computer-implemented method as recited in claim 1 , wherein the processor utilizes a neural network to classify the person's gait.

8. The computer-implemented method as recited in claim 7 , wherein the processor classifies the person's gait on a per step basis.

9. The computer-implemented method as recited in claim 1 , wherein utilizing the processor to find the x-displacement and the y-displacement is performed in a time interval between the local minima and the local maxima for each step.

10. The computer-implemented method as recited in claim 1 , further comprising utilizing the processor to determine a translation direction for each step, wherein a most frequent direction of translation is forward, and wherein the ground frame is corrected to the y-axis.

11. The computer-implemented method as recited in claim 1 , further comprising utilizing the processor to determine a translation direction for each step, wherein a most frequent direction of translation is determined by assigning each possible direction of motion based on each step to a bin for the direction of motion and the bin with the highest frequency is considered the most frequent direction of translation.

12. The computer-implemented method as recited in claim 1 , further comprising utilizing the processor to determine a translation direction for each step, and further comprising detecting a transition corresponding to an abrupt change in orientation of the device and discontinuing the step of utilizing the processor to determine a translation direction for each step until the transition has completed.

13. The computer-implemented method as recited in claim 1 , wherein calculating the 3D movement is further based on determining the person's 3D translation and rotation, and further comprising determining a location and a heading for the person based on the 3D translation and rotation.

14. The computer-implemented method as recited in claim 1 , further comprising utilizing the processor to determine a translation direction for each step, wherein even and odd steps are tracked separately to find a most frequent direction of translation for even steps and for odd steps, and a forward direction is determined as an average of the most frequent translation direction for the even steps and the odd steps.

15. The computer-implemented method as recited in claim 1 , further comprising utilizing the processor to determine a translation direction for each step, wherein a most frequent direction of translation for even steps and for odd steps is separately determined by:

assigning each direction of motion based on each step to a bin for the direction of motion; and

considering the bin with a highest frequency as the most frequent direction of translation, and wherein a forward direction is determined as an average of the most frequent translation direction for the even steps and the odd steps.

16. A computer-implemented method for classifying a person's gait, comprising:

collecting accelerometer data from a worn or person carried device that includes an accelerometer in an unknown tilted orientation relative to a ground frame as the person moves around a physical location, the accelerometer data being indicative of the person's 3D movement relative to the ground frame and sampled based on movement of the person, the accelerometer data comprising x-axis data, y-axis data and z-axis data that corresponds to the movement of the person over a period of time and storing the data in a non-transitory memory, wherein the person's 3D movement relative to the ground frame forms a reference frame for the device;

determining tilt data indicative of the accelerometer's orientation relative to the ground frame using the accelerometer data;

generating improved accelerometer data indicative of the accelerometer's orientation relative to the reference frame for the device by filtering the accelerometer data using the tilt data;

storing the improved accelerometer data in the non-transitory memory;

generating stride data based on the improved accelerometer data comprising:

detecting steps of the person within the improved accelerometer data;

inputting to a neural network a first number of values of each of the x-axis, y-axis and z-axis components of angle vectors for each step;

inputting to the neural network a second number of values of each of the x-axis, y-axis and z-axis components of velocity vectors for each step;

inputting to the neural network a minimum and a maximum acceleration amplitude difference over each step;

inputting to the neural network an orientation vector at the end of each step; and

inputting to the neural network an index where a magnitude of the x-axis and y-axis plane acceleration achieves a minimum value for each step; and

classifying by the neural network the person's gait as a level gait, an up gait, or a down gait, based on the stride data.

17. The method of claim 16 , further comprising:

calculating by the processor a two-dimensional (2D) movement displacement for each step by the person;

when the person's gait is classified as the up gait or the down gait, calculating the elevation change of the person; and

on a step by step basis, calculating the 3D movement of the person based at least on the 2D movement displacement and the elevation change in order to track a location of the person.

18. The computer-implemented method as recited in claim 16 , wherein the accelerometer data is sampled at a frequency greater than twice a Nyquist frequency of the movement of the person.

19. A computer-implemented method for detecting the steps of a person and estimating the person's two-dimensional (2D) movement to track a location of the person, comprising the steps of:

collecting accelerometer data from a worn or person carried device that includes an accelerometer in an unknown tilted orientation relative to a ground frame as the person moves around a physical location, the accelerometer data being indicative of the person's 3D movement relative to the ground frame sampled based on movement of the person, the accelerometer data comprising x-axis data, y-axis data and z-axis data that corresponds to the movement of the person over a period of time and storing the accelerometer data in a non-transitory memory of a computer having a processor, wherein the person's 3D movement relative to the ground frame forms a reference frame for the device;

determining tilt data indicative of the accelerometer's orientation relative to the ground frame using the accelerometer data;

generating improved accelerometer data indicative of the accelerometer's orientation relative to the reference frame for the device by filtering the accelerometer data using the tilt data;

storing the improved accelerometer data in the non-transitory memory;

generating stride data based on the improved accelerometer data, comprising:

calculating using the filtered accelerometer data a periodic signal where a period of the filtered accelerometer data is the same as a step period of the person;

finding by the processor a local minima and a local maxima of the periodic signal, wherein one of the local minima or the local maxima are used to detect each step by the person;

finding by the processor an x-displacement along the x-axis and a y-displacement along the y-axis for each step by the person based on the filtered accelerometer data for the x-axis and the y-axis between the local minima and the local maxima and storing the x-displacement and the y-displacement in the memory; and

calculating by the processor a 2D movement displacement and a translation direction for each stride by the person based at least on the x-displacement and the y-displacement; and

estimating a 2D movement to track the location of the person on a step by step basis, based at least on the stride data.

20. The computer-implemented method of claim 19 , wherein finding by the processor an x-displacement and a y-displacement is further based on a double integration of the filtered accelerometer data.

21. The computer-implemented method as recited in claim 19 , wherein the accelerometer data is sampled at a frequency greater than twice a Nyquist frequency of the movement of the person.

22. A computer-implemented method for detecting the steps of a person and estimating the person's two-dimensional (2D) movement to track a location of the person, comprising the steps of:

collecting gyroscope data from a worn or person carried device that includes a gyroscope in an unknown tilted orientation relative to a ground frame as the person moves around a physical location, the gyroscope data being indicative of the person's 3D movement relative to the ground frame and sampled based on movement of the person, the gyroscope data comprising x-axis data, y-axis data and z-axis data that corresponds to rotation of the device over a period of time and storing the gyroscope data in a non-transitory memory of a computer having a processor, wherein the person's 3D movement relative to the ground frame forms a reference frame for the device;

determining tilt data indicative of the gyroscope's orientation relative to the ground frame using the gyroscope data;

generating improved accelerometer data indicative of the gyroscope's orientation relative to the reference frame for the device filtering the gyroscope data using the tilt data;

storing the improved accelerometer data in the non-transitory memory;

generating stride data based on the improved accelerometer data, comprising:

calculating using the improved gyroscope data a periodic signal where a period of the filtered gyroscope data is based on a stride period of the person;

finding by the processor a local minima and a local maxima of the periodic signal;

finding by the processor an x-motion around the x-axis and a y-motion around the y-axis between the local minima and the local maxima based on the filtered gyroscope data for the x-axis and the y-axis and storing the x-motion and the y-motion in the memory; and

estimating a 2D movement to track the location of the person based at least on the stride data.

23. The computer-implemented method of claim 22 , wherein a stride is two alternating steps by the person.

24. The computer-implemented method as recited in claim 23 , wherein the gyroscope data is sampled at a frequency greater than twice a Nyquist frequency of the movement of the person.