Implementing a Step Detection Algorithm
About 3 years ago, my lab mate and I had an assignment to implement a step detection algorithm. The implementation will be used for our research which is related to somewhat IoT’ish work.
The algorithm itself was not as complex as it was supposed to be, and it had been discussed in many paper works or tutorials. However, my teacher was very kind enough to let us learn and figure out the basic idea of how it is working.
A. Record The Steps
To understand how step detection works, we were asked to record our step. Our first question was, what to record? Since walking is related to movement activity, we decided record our movement acceleration data. And our guess was correct that time.
Since the accelerometer measures the external force at the center of mass, the forward acceleration should ideally be zero while standing still. Nevertheless unlike the inanimate object, a signal with a very low magnitude and variance is obtained.
A step motion can be defined when the foot start lifting and touch the ground with a measurable movement range to make a change from the outset to the posterior position. Another parameter is a time gap between each step. This become a challenge to distinguish a normal walk and running state, however we will not discuss this matter in this article.
By walking on a determined path, the Z value of accelerometer will change by the time of it moving or tilting. While walking the beginning of each step one push back with their foot on the floor. Without friction, the foot would slide back. But, static friction opposes this motion, and is thus directed forward (in the negative Z direction).
Contrary with previous state, at the end of each step, one pushes forward with their foot on the floor and thus, static friction is directed backward (in the positive z direction). The evidence in figure 1 there are protruding peaks in the negative z direction at the beginning of each step, but also positive z direction at the end of each step.
After recording our step, we found a quite obvious pattern of our acceleration reading.
B. Make the reading smoother
When we recorded the accelerometer data, the reading was somehow very crude. So, to make the reading smoother, the low pass filter function is needed to return the relatively small changes of z value using 2 parameter:
a. New accelerometer Z value and previous Z value.
b. The recent low pass filtered Z value which is obtained from this formula
Z[t’] = (α x Z[t-1]) + (1 — α) * Z[t]
Z[t’] : Low pass filtered Z value
Z[t-1] : Previous Z value from accelerometer reading
Z[t] :Current Z value from accelerometer reading
α : Constant (In this implementation the value is 0.9f)
Now, lets focus on figure 1, and now I am going to illustrate the image clearer.
C. Analize the Step Reading
If you observe the plot in figure 1. We can see the steep condition between up and down figure. As you may assume, thats the key of the step detection itself.
For detecting each step phase, the step detection algorithm maintains four thresholds: top threshold, upper threshold, lower threshold, and bottom threshold. In Fig. 2, we show these four thresholds and the acceleration value over time.
Two steps are detected during the time span of this figure. The lifting phase incurs the acceleration towards the gravity direction which causes a negative acceleration value. Therefore, the step detection algorithm detects the lifting phase when the acceleration value passes downward through the lower threshold.
The swing phase is the transient phase between the lifting phase and the stepping phase. The step detection algorithm detects the swing phase when the current phase is the lifting phase and the acceleration value passes upward through the lower threshold. The stepping phase leads to a positive acceleration value since it causes the acceleration towards the opposite of the gravity detection. The step detection algorithm detects the stepping phase when the current phase is the swing phase and the acceleration value goes upward through the upper threshold. Finally, a step is detected when the acceleration value goes downward through the upper threshold in the stepping phase.
D. Code Implementation
For the implementation, we created a prototype application using Android, since it accommodate the sensor reading using accelerometer and magnetometer.
First of all, lets declare some constants for step boundary checking.
double lastAccelZValue = -9999;
long lastCheckTime = 0; boolean highLineState = true;
boolean lowLineState = true;
boolean passageState = false; double highLine = 1;
double highBoundaryLine = 0;
double highBoundaryLineAlpha = 1.0; double highLineMin = 0.50;
double highLineMax = 1.5;
double highLineAlpha = 0.0005; double lowLine = -1;
double lowBoundaryLine = 0;
double lowBoundaryLineAlpha = -1.0; double lowLineMax = -0.50;
double lowLineMin = -1.5;
double lowLineAlpha = 0.0005; double lowPassFilterAlpha = 0.9; float[] rotationData = new float[9];
float[] resultData = new float[3];
Next, we need to create the function or method to detect the step by applying the theorem above. Lets call this function as readStepDetection function. The function below should be called when the sensor reading happen. This function detect the step event by reading a fluid data from accelerometer. We use accelerometer linear data for step detection.
private void readStepDetection(float[] accelLinearData) { long currentTime = System.currentTimeMillis();
long gapTime1 = (currentTime - lastCheckTime); if (lastAccelZValue == -9999){
lastAccelZValue = accelLinearData[2];
} if (highLineState && highLine > highLineMin) {
highLine = highLine - highLineAlpha;
highBoundaryLine = highLine * highBoundaryLineAlpha;
} if (lowLineState && lowLine < lowLineMax) {
lowLine = lowLine + lowLineAlpha;
lowBoundaryLine = lowLine * lowBoundaryLineAlpha;
}//perform a low pass filter for sensor reading
double zValue = (lowPassFilterAlpha * lastAccelZValue) + (1 -lowPassFilterAlpha) * accelLinearData[2]; if (highLineState && gapTime1 > 100 && zValue > highBoundaryLine){
highLineState = false;
} if (lowLineState && zValue < lowBoundaryLine && passageState) {
lowLineState = false;
} if (!highLineState) {
if (zValue > highLine) {
highLine = zValue;
highBoundaryLine = highLine * highBoundaryLineAlpha;
if (highLine > highLineMax) {
highLine = highLineMax;
highBoundaryLine = highLine * highBoundaryLineAlpha;
}
} else {
if (highBoundaryLine > zValue) {
highLineState = true;
passageState = true;
}
}
} if (!lowLineState && passageState) {
if (zValue < lowLine) {
lowLine = zValue;
lowBoundaryLine = lowLine * lowBoundaryLineAlpha;
if (lowLine < lowLineMin) {
lowLine = lowLineMin;
lowBoundaryLine = lowLine * lowBoundaryLineAlpha;
}
} else {
if (lowBoundaryLine < zValue) {
lowLineState = true;
passageState = false;
//step is detected here
//do something
lastCheckTime = currentTime;
}
}
}
lastAccelZValue = zValue;
}
The function above can be directly called on a sensor reading event when the accelerometer linear data is obtained.
public void onSensorChanged(SensorEvent sensorEvent) {
if (sensorEvent.sensor.getType() == Sensor.TYPE_LINEAR_ACCELERATION) {
this.accelLinearData = sensorEvent.values.clone();
} if (this.accelLinearData != null) {
actionReadStepDetection(accelLinearData);
}
}
E. Finally..
Now, by using the snippet above, we can somehow figure out how to obtain the step state while walking using a smartphone or other device which accommodates an accelerometer sensor reading.
However, does the code has no flaw ? Off course not. There are some challenges that are needed to be solved if we use this code.
- Each people step stride is different, we need to figure out how to maintain those constants above as adaptive as possible.
- Distinct walking activity and running. Those activity creates a different sensor reading trend.
- Hand grip position. So lets assume we use smartphone, then its position matter. Moreover, if we put the smartphone inside the bag, or pocket, I am afraid that this implementation is invalid.
Step detection algorithm is widely used for many cases and application. But to make it perfect, it requires more research and adjustment for cases by cases scenario.
Sources
Fang, L., Antsaklis, P.J., Montestruque, L.A., McMickell, M.B., Lemmon, M., Sun, Y., Fang, H., Koutroulis, I., Haenggi, M., Xie, M. and Xie, X., 2005. Design of a wireless assisted pedestrian dead reckoning system-the NavMote experience. IEEE transactions on Instrumentation and Measurement, 54(6), pp.2342–2358.
Naqvib, N.Z., Kumar, A., Chauhan, A. and Sahni, K., 2012. Step counting using smartphone-based accelerometer. International Journal on Computer Science and Engineering, 4(5), p.675.
Diaz, E.M. and Gonzalez, A.L.M., 2014, October. Step detector and step length estimator for an inertial pocket navigation system. In Indoor Positioning and Indoor Navigation (IPIN), 2014 International Conference on (pp. 105–110). IEEE.
