In our swarming world, it is quite hard to imagine someone having no mobile phone in the pockets of his jeans, her dress or their suits. Even the inveterate skeptic has to accept the fact that smartphones entered our life and have become its inalienable part, the part of us. The mobile phones became our assistants in all aspects of our life, like filming the greatest events of our life, scheduling our time, being our doctors and fitness coaches, our guides in the world we live in.
Fig. 1. The life we all live
One of the most common usages of the smartphones nowadays is navigation. Let us bet that at least once you have driven your car following the route proposed by your favorite navigation system. These systems we call outdoor navigation systems. Global Positioning System (GPS) [1] has really revolutionized the way people travel nowadays, enabling the outdoor navigation satellite systems. This works just perfectly, for an outdoor system, but what about the indoor navigation. It has many potential applications that are still underexploited, like navigation in big structures such as shopping malls, airports, big railway stations etc [2]. Just imagine the profit people with special needs may gain from this undoubtedly perspective technology (for example, distinguishing the free and blocked space on your way).
Unavailability of GPS signal in the indoor space makes us realize the potential of indoor navigation systems. Nowadays there is no standardized approach to the indoor navigation and the sources of information it must use. Some researchers suggest using WiFi signal for getting the User position [3]. Other scientists think that the Beacon technology is more promising [4]. Nevertheless, they all agree with one incontestable fact. The indoor navigation is not really possible without the inertial sensor measurements despite all their problems and implementation challenges take a lion`s portion of indoor systems.
Inertial Indoor Navigation
The inertial systems scoop up the input information from the onboard sensors, which are compulsory components of modern mobile devices. The standard mobile phone has an accelerometer, gyroscope, magnetometer (optional), proximity sensor, light sensor, barometer (optional) and many others in devices that are more expensive [5]. The navigation systems we address use accelerometer, gyroscope and, sometimes, a magnetometer for magnetic correction when necessary. The flow of the inertial navigation system is presented in Fig. 2.
Fig. 2. Flow of the inertial navigation system
From the very beginning, the indoor navigator harvests raw data from the sensors using the native Android or iOS APIs and converts them to a format that suits the navigation algorithms. The readings of Android devices are very noisy to be used in the algorithm as the crow flies. Hence, they are subjected to the high pass and low pass filtration. The filtering technique depends on a particular SDK, but the most popular methods are the Butterworth filter [6], the SavitzkyGolay filter [7] and definitely the Kalman filter [8]. The readings obtained from the iOS devices in the majority of cases do not need the filtration because the native algorithms already filter them. Then the execution flow is vectorized: the first flow works to get the User steps (stepdetection algorithms), while the other one determines the attitude and heading (socalled AHRS algorithms [9, 10]). The attitude expresses the position of the mobile device in the global Cartesian coordinate system. The accurate evaluation of attitude and heading are very important because the raw data from the device is measured in the local Cartesian coordinate system of a mobile device. Next, the information from AHRS algorithm and step detection algorithm enter the next processing stage, which is step length and heading estimation. Here the algorithms evaluate the distance User covers per a single step and the direction of the step. The algorithms used for the step length estimation are considerably various. Some algorithms suggest referencing the measured acceleration and evaluated speed, the other offer the usage of different step models to estimate the step length like [11]
where H is a User height, L is a leg length.
At the very end of the flow, the collection of steps forms the track of User on the map.
We ingeniously kept the stepdetection algorithm undisclosed, because it is a key component of the flow. Moreover, in the next chapter we are going to prove this.
The Value of a Step
Once, famous French novelist Marc Levy claimed:
“If you want to know the value of one year, just ask a student who failed a course. If you want to know the value of one month, ask a mother who gave birth to a premature baby. If you want to know the value of one hour, ask the lovers waiting to meet. If you want to know the value of one minute, ask the person who just missed the bus. If you want to know the value of one second, ask the person who just escaped death in a car accident. And if you want to know the value of onehundredth of a second, ask the athlete who won a silver medal in the Olympics.”
However, he said nothing about the step. Definitely, the step is not as important as a month for a premature baby, but the step does matter because sometimes One step of a man turns to a giant leap for mankind.
The most probably reading these lines you ask yourself the question “Why are these guys so mad about the step detection? Okay, let us say, I miss a step or detect one extra step. What does it change? Why is it so important? ”
To answer this reasonable question we must analyze the accuracy of the innovative commercial indoor navigation systems. After googling a little, you will find few the most popular systems, which are Navigine [12], Estimote [13], Inciteo [14], Steerpath [15], Accuware [16] etc. The expected accuracy of these solutions is claimed to be less than 3 meters.
The wasted or misdetected step brings the error in the position equal to a step length. No matter how the step length is estimated, we can roughly say that the step length is rarely less than half a meter. Hence, if the indoor track lasts for 10 minutes you will make about 200…300 steps. For instance, if the step detection algorithms miss every 5th step the accumulated positioning error will be 20 meters, every 10th 10 m error, every 20th – 5 m error and so on. This accuracy looks horrible and cannot be commercialized.
Concluding all written about it becomes evident that the step detection algorithms of modern inertial navigation systems are of a very high tolerance, miss detecting only a few steps or having some kind of correction injections. The next chapter is aiming to make you familiar with the most used published algorithms of the step detection.
Step Detection Algorithms
In this chapter, we will try to briefly describe each step detection algorithm highlighting its pros and cons and awarding you with its experimental validation.
The described method is based on the detection of a moment when the norm of acceleration (square root of the sum of squared accelerations along each axis) or Zcomponent of acceleration breaks the preliminary set constant boundary magnitude twice (increasing and decreasing acceleration breakages). The period between the first and the second breakages limits the step time, which is interpreted as “step detected”. When the acceleration is below the threshold, one expects User to stand still. In some modifications of this algorithm, to distinguish the true steps from the fake ones (e.g. turning around), the readings of the gyroscope are engaged. If the gyroscope shows some activity, then the detected step is considered a fake step and is not accounted. On the figure below, you may see this algorithm in action.
Fig. 3. Constant threshold step detection (20 steps made)
Algorithm lags from the realtime processing for a half a window;
Constant time threshold performs poor for different types of moving like running, walking, slow pace etc.;
The correctness of algorithm to the utmost depends on the window size.
Pros & Cons
+

–




Step Detection Based on Median and Standard Deviation [18]
The algorithm described here analyzes the norm of acceleration (magnitude of acceleration) as well. The algorithm is based on the fact that a sharp peak of the magnitude is observed as the User takes a step. All events of the algorithm happen in the sliding window that must be selected from the very beginning.
The correct window size is essential for the considered algorithm. The recommended size is about 13 readings. If the window is too wide, the number of steps determined will be less than the actual number of steps. On the other hand, if the window is too narrow, noisy data can be wrongly detected as a step. This results in the number of steps detected to be more than the actual number of steps taken by the User.
Next, each window is analyzed for the occurrence of a step. However, before the step detection itself, the algorithm calculates some characteristics of the data in the sliding window, namely standard deviation of the readings in the window and the magnitude of the median of the readings in the window.
The step is detected if the standard deviation of the window is greater than the threshold value and the median of the window has the greatest magnitude.
That is not enough to be sure that the step is determined correctly because usually, some fake splashes surround the true peak. To distinguish the latest, the algorithm applies the time check, which is formulated as “If two steps are not separated by the certain threshold in time, then the detected step is a fake step.”
Pros & Cons
+

–




Step Pattern Recognition Based on Three Typical Events of the Step [19]
The method detects the step when it meets the definite pattern in the accelerometer readings. The pattern describes the way the norm of acceleration changes during the step and consists of three key consecutive events, which are:
 heeltouchingground (see pos. 5 on the figure);
 stance (see pos. 1 on the figure);
 heeloffground (see pos. 2 on the figure);
Fig. 4. The gait of a standard individual
The first event takes place when the heel just hits the ground and the waist is in its lowest position during the entire step. The second event corresponds to the moment when the foot is flat on the ground. The last of three events corresponds to the time moment right after the stance.
The heeltouchingground event is detected as a local minimum of the acceleration magnitude. The heeltouchingground event is followed by the increasing of acceleration magnitude up to some local maximum corresponding to the stance. Have passed the stance, the magnitude goes down up to a new local minimum, that is recognized as a heeloffground event only in case the magnitude of acceleration at that moment is greater than the heeltouchingground magnitude was.
Fig. 5. Main events of human gait and their understanding out from the accelerometer readings
The step is detected only when these three events form the correct sequence (heeltouchingground => stance => heeloffground => heeltouchingground = one step) and the duration between two consecutive heeltouchingground events is over the time threshold. Considering the walking frequency always been less than 3 Hz, the threshold is 0.33 s per one step.
Pros & Cons
+

–




The Derivative Step Detector
The method expects the accelerometer readings to oscillate similarly to the sine function, where the foot upstroke is represented with a positive portion of a period, and foot downstroke – with the negative one. Considering the introduced assumption, we expect the step beginning and its end at the moment when the time derivative of Zcomponent is maximum.
Prior to step detection itself, the algorithm evaluates the first time derivative of acceleration magnitude and a threshold. The threshold is determined statistically and is recommended to be set
where coefficient k value can be chosen to be 1.21.5, however, it depends on a particular environment and mobile device.
After the described calculations, the algorithm has all required data for the step detection. Therefore, the algorithm compares the time derivative at the current iteration to that at the previous one as well as with the threshold.
It the following condition is met
then the step start is considered to be detected.
The step end is detected with the same condition.
Fig.6. Derivative step detector (20 steps made)
To be sure that the step has been detected correctly, the algorithm checks a bilateral time constraint
For the most part, this condition is fulfilled, however, if it is not, then the detected step is ignored.
No matter was the step approved by the bilateral time constraint or not, the step end is set the start of the upcoming step.
Pros & Cons
+

–




In this review, we presented several step detection techniques that can be a good option for integration into INS systems. Apparently, there is a plenty of alternatives, however, they often share similar theoretical ideas and concepts. Interested readers can overview the below links to get more details.
References
 Wikipedia (2017) Global Positioning System https://en.wikipedia.org/wiki/Global_Positioning_Systema.
 Sander Soo “Indoor positioning using mobile sensors” (2017).
 Fred´eric Evennou and Franc´ois Marx “Advanced Integration of WiFi and Inertial Navigation Systems for Indoor Mobile Positioning” (2006).
 R. Doraiswami “A novel Kalman filterbased navigation using beacons” (1996).
 Developer.android.com (2017) Sensors Overview https://developer.android.com/guide/topics/sensors/sensors_overview.html.
 M.E. Vanvalkenburg “Analog filter design” (1982).
 Ronald W. Schafer “What Is a SavitzkyGolay Filter?” (2011).
 R. Kalman “A New Approach to Linear Filtering and Prediction Problems” (1960).
 Mark Pedley “Tilt Sensing Using a ThreeAxis Accelerometer” (2013).
 Sebastian O.H. Madgwick “An efficient orientation filter for inertial and inertial/magnetic sensor arrays” (2010).
 NgocHuynh Ho, Phuc Huu Truong, and GuMin Jeong “StepDetection and Adaptive StepLength Estimation for Pedestrian DeadReckoning at Various Walking Speeds Using a Smartphone” (2016).
 Navigine official website https://navigine.com/.
 Estimote official website https://estimote.com/.
 Inciteo official website https://www.insiteo.com/.
 Steerpath official website https://steerpath.com/.
 Accuware official website https://www.accuware.com/.
 Ruoyu Zhi “A Drif Eliminated Atttude & Position Estimation Algorithm In 3D” (2016).
 G.Trein, N.Singh, P.Maddila “Simple approach for indoor mapping using lowcost accelerometer and gyroscope sensors” (2012).
 KunChan Lan and WenYuah Shih “Using SmartPhones and Floor Plans for Indoor Location Tracking” (2014).