Robust Step Counting for Inertial Navigation with Mobile Phones

sensors Article Robust Step Counting for Inertial Navigation with Mobile Phones Germán Rodríguez 1, Fernando E. Casado 2, Roberto Iglesias 2,*, Carlos V. Regueiro 3and Adrián Nieto 1 1Situm Technologies S.L., Santiago de Compostela 15782, Spain; [email protected] (G.R.); [email protected] (A.N.) 2CiTIUS, University of Santiago de Compostela, Santiago de Compostela 15782, Spain; [email protected] 3Department of Computer Engineering, University of A Coruña, A Coruña 15071, Spain; [email protected] *Correspondence: r[email protected]; Tel.: +34-881-816-429 Received: 20 July 2018; Accepted: 14 September 2018; Published: 19 September 2018   Abstract: Mobile phones are increasingly used for purposes that have nothing to do with phone calls or simple data transfers, and one such use is indoor inertial navigation. Nevertheless, the development of a standalone application able to detect the displacement of the user starting only from the data provided by the most common inertial sensors in the mobile phones (accelerometer, gyroscope and magnetometer), is a complex task. This complexity lies in the hardware disparity, noise on data, and mostly the many movements that the mobile phone can experience and which have nothing to do with the physical displacement of the owner. In our case, we describe a proposal, which, after using quaternions and a Kalman filter to project the sensors readings into an Earth Centered inertial reference system, combines a classic Peak-valley detector with an ensemble of SVMs (Support Vector Machines) and a standard deviation based classifier. Our proposal is able to identify and filter out those segments of signal that do not correspond to the behavior of “walking”, and thus achieve a robust detection of the physical displacement and counting of steps. We have performed an extensive experimental validation of our proposal using a dataset with 140 records obtained from 75 different people who were not connected to this research. Keywords: indoor-positioning; pedestrian dead reckoning; sensor fusion; step counting 1. Introduction We are immersed in a society of devices (mobile phones, tablets, wearables, etc.) that are transforming us at an incredible speed, changing the way we live or interact with each other. Not only do current generation devices incorporate increasingly better processors, but also high-end sensors previously unavailable. These progressive incorporation of sensors opens important opportunities towards the development of applications that use them in an increasing number of domains—healthcare, leisure, education, sport, social interaction, etc. One example of such is the use of the inertial sensors of the mobile phone to monitor human activity, in particular the action of walking. This information is very valuable for many applications, like biometric identification (e.g., recognition of the owner of the device by the way of walking) [ 1 – 3 ], medicine (detection of certain pathologies) [ 4 ], indoor localization, etc. In fact, in the particular case of pedestrian indoor localization, identifying the activity of walking using inertial sensors is essential, since alternatives like the Global Navigation Satellite System (GNSS) do not work indoors, and other sensor modalities such as WiFi or BlueTooth [ 5 ], infrared, ultrasound [ 6 ], vision based [ 7 ], magnetic field, audible sound or Sensors 2018,18, 3157; doi:10.3390/s18093157 www.mdpi.com/journal/sensors Sensors 2018,18, 3157 2 of 21 Ultra Wide Band (UWB), often provide a gross probabilistic estimation of the position, which can be significantly improved when combined with Pedestrian Dead Reckoning (PDR). PDR works with the estimated speed of a person to update the current position starting from a previous location. Different sensors and processing strategies have been applied to estimate this value of the speed: cameras for visual odometry, pressure sensors attached to the shoes using ultrasonic ranging between feet, inertial sensors, etc. [ 8 ]. Some of these approaches are undesirable since they require extra hardware attached to the body or, in the case of visual odometry, free line of sight of the person moving. On the contrary, inertial sensors (accelerometer, gyroscope and magnetometer) are more appealing, since they present fewer restrictions. Applying PDR when the sensors are placed on the body (foot, trunk, arm, etc. [ 9 – 11 ]) is more reliable and the processing of the sensor information is simpler than with the inertial sensors in the mobile phone. However, attaching sensors to the body or clothes very much restrains their applicability. Instead, working with the inertial sensors with which most mobile phones are already endowed is much more attractive, since most people carry these phones, and they can even run applications that use PDR-based techniques to offer localization services. In this paper, we describe and analyze the performance of a novel strategy in the context of PDR, aimed at recognizing and counting steps given by any person carrying a mobile phone. The identification of human activities by using mobile phones and inertial sensors is much more complex than what it may seem. In the particular case of walking, it is relatively easy to recognize this activity and even count the steps when a person walks ideally with the mobile in the palm of his/her hand. Nevertheless, the situation gets much worse in real life, when the orientation of the mobile with respect to the body, as well as its location (hand, bag, pocket, ear, etc.), changes constantly while the person moves [ 12 ]. Mobile phones often experience a large variety of motions, which may have nothing to do with walking, but which can all produce similar patterns in the signal. This is what makes the recognition of this activity a complex task, especially when the performance is to be increased beyond a certain threshold. Since we want no limitations about where or how the user carries the mobile, our proposal will estimate whether the person is walking before actually counting the steps. This will allow filtering chunks of useless signal and thus discarding false positives common in these kind of approaches. Obviously, with the proposal described in this paper, we tried to achieve a reliable and robust classification, able to achieve high performances regardless of how the device is being carried or its orientation. Nevertheless, we are aware that an idealistic 100% reliability is not feasible, which is why we also aim for a error-symmetric prediction (similar number of false positives and negatives). If this is true, these errors can cancel each other, so that the number of steps predicted by our proposal in a time interval will be very accurate. This will make our proposal very appropriate for indoor local navigation. Even though there has been a significant amount of research in this subject, the current state-ofthe-art solutions are far from optimal because they are either susceptible to false positives or require undesirable constraints or complexity. Additionally, the datasets used in most of the literature are not representative enough, i.e., they do not comprise the huge variability of situations in which an smartphone is often used/carried. In addition, in these datasets, the real steps walked by the persons are not individually labeled (one by one) to be used as ground truth. We have have actually built such a database (as we will describe in Section 4) and used it to perform an exhaustive analysis of the performance of each element of our proposal. Through the experimental results, and thanks to the use of our database, in which the steps are individually labeled, we will empirically demonstrate how our proposal fulfills all the objectives just described. The rest of the paper is structured as follows: Section 2describes the state of the art. Section 3 describes our proposal. Section 4presents the database used for ground truth together with the experimental analysis of our proposal. The conclusions are presented in Section 5. Sensors 2018,18, 3157 3 of 21 2. State of the Art Thanks to the technological advances of the last years, it has been possible to integrate sensors of very small size in smartphones, like the inertial ones: accelerometer, gyroscope and magnetometer. Taking advantage of their presence, an emerging class of localization systems that use inertial sensors to perform dead reckoning on mobile phones is gaining attention. These systems have the advantage that very little physical infrastructure is required for them to run. Pedestrian Dead Reckoning works by estimating successive positions starting from a known location, based on a rough calculation of the direction and the distance walked. The direction can be obtained by the compass or the gyroscope. To determine the distance walked, a common solution is to count the number of steps and estimate their length. This is typically done analyzing the acceleration data [ 13 – 15 ], although other sensors have also been tried—Jimenez et al. [ 16 ] used the magnetometer in order to detect steps. In particular, they thresholded the magnitude of the signal that resulted after the removal of the DC component of the magnetic field—. In most studies, the position of the device is kept fixed (foot, trunk, arm, etc.) [ 9 – 11 ] because any changes in position may result in a loss of recognition performance. This is not desirable because people carry their smartphones in a variety of ways (hand, pocket, bag, etc.) and they do not keep it in a static position all the time. In recent years, especially with the popularization of smartphones, more research has been carried out on identification of steps and activity without restricting the position of the sensors. A simple approach for step counting is the heuristic solution, present in many of the current commercial pedometer applications, and which consists of applying techniques such as the peak-valley detection to the magnitude of the acceleration [ 17 , 18 ]. This technique works by identifying peaks in the signal caused by the feet touching the floor (heel strikes) [ 14 ]. Thus, a step corresponds to a segment of signal in which there is a peak (local maximum which exceeds a threshold) followed by a valley (local minimum below a threshold). On the other hand, working with the magnitude of the acceleration avoids certain dependence on the orientation of the mobile phone. Another technique is zero crossing, which looks for the points at which the signal changes from positive to negative or the other way round [ 19 ]. However, these algorithms are susceptible to detect any motion as walking, hence they are prone to commit false positives. Due to this, another module responsible for filtering out is necessary, and, in real time, those parts of the signal that reflect some kind of movement in the mobile, but which have nothing to do with walking. This is a challenging task due to the high perceptual aliasing (i.e., the existence of many signals very similar but caused by different movements of the mobile or human actions). A robust way of identifying the walking activity and counting the steps is by analyzing the shape of the inertial signals. In this case, it is assumed that it is possible to distinguish the activity of walking from that of not walking by simply observing the characteristic shape of the acceleration signal. This is mainly because, when walking, this signal shows a repetitive pattern, also known as step cycle. The event that is often used to mark the beginning of the cycle is the heel strike of the swing leg [ 2 , 3 ]. Then, it is necessary to find a match between the step cycle candidates and one or more patterns selected beforehand using a distance measure. Euclidean distance is a simple measure; however, it has been observed that it is very sensitive to distortion and noise and similar patterns can be separated by very large distances if the data items are not aligned [ 20 ]. A better alternative is to use warping distances, such as dynamic time warping (DTW) [ 21 ], longest common subsequence (LCSS) [ 22 ] or edit distance on real sequence (EDR) [ 20 ]. The main weakness of this approach is that, if the step candidates are misidentified during the signal division process, the subsequent matching with the reference patterns is compromised. In addition, there is a need to have a series of patterns that must be chosen beforehand and possibly manually. Another way of dealing with this problem of step recognition is by extracting significant features from the inertial signals and using them to train a classifier. Susi et al. [ 18 ] identify the motion mode of the device (static, handheld texting, swinging, etc.) by extracting time and frequency domain features and applying a decision tree. (e.g., they classify a sequence as non-walking based on the Sensors 2018,18, 3157 4 of 21 periodicity and variance of the signal.). They use a different step detection algorithm for each motion mode, but all involve peak detection over the accelerometer or gyroscope signal. Finally, they apply a step length estimation using the step frequency and the height of the user. They report a good performance, but they only evaluated the performance of their step counting algorithm in restricted scenarios such as walking while texting and swinging. Bradjic et al. [ 23 ] conducted a survey in which they tested different step counting algorithms, and walking detection classifiers against a dataset of 130 sensor traces of 27 different users walking and performing different activities while carrying a smartphone. They concluded that neither of them performed better than a windowed peak detection, which presented a median error around 1.3%. However, it had a high rate of false positives when the device was moved without the user walking. They also obtained good classification rates using the standard deviation of the acceleration. Even though the accuracy reported is high, these algorithms will exhibit a high number of false positives when the phone is being moved, but the user is not walking. There are also different commercial solutions for counting steps. As an example of this, we can mention Actigraph, which manufactures different activity monitoring devices frequently used in the medical field [ 24 ]. The main drawback is that additional hardware is required, and it is expensive. In addition, Eslinger et al. [ 25 ] obtained a solution that performs well when the user walks at a high speed, but the performance of which is significantly lower when the walking is slow. Another alternative used in medical literature is GAITRite1 [ 26 ]. This solution consists of a sensorized walkway that presents high precision in the detection of steps and activities. Nevertheless, this involves the deployment of hardware in the environment, and obviously a high cost and restricted areas of operation. Other alternatives, such as Fitbit, have proven to have a high number of false positives when performing activities different than walking [27]. We can conclude that even though there has been a lot of research in this subject, the current state of the art solutions are far from optimal because they are either susceptible to false positives or require undesirable constraints or complexity. Furthermore, most of the experimentation in the bibliography comprises only data of people walking, thus it is not clear how these algorithms would perform in terms of false positives when the person uses the phone without walking. Additionally, they tend to evaluate the performance of their proposals against the total traveled distance or the total detected steps, but there is no evaluation of whether a detected step is really a step or not (false positives and false negatives can cancel each other and mask the real performance of the system in short time intervals). 3. Walking Detection and Step Counting Figure 1provides a schematic representation of our complete proposal. Basically it detects “step candidates”, i.e., a segment of signal that might reflect a step given by the person carrying the mobile. In parallel, supervised learning and Bayesian filtering are being used to recognize the walking activity. Hence, a step is validated and counted in those circumstances in which the detection of a step candidate coincides with the positive identification of the walking activity in the same signal segment. Next, we provide details of each one of the parts that make up our proposal. Sensors 2018,18, 3157 5 of 21 Figure 1. Our proposal to Pedestrian Dead Reckoning in a positioning system. 3.1. Raw Signal Processing The walking recognition and step counting is performed using the signals provided by the tri-axis accelerometer and the tri-axis gyroscope in a mobile phone, and which respectively measure the acceleration and the angular velocity of the device with respect to the navigation frame. The output of these sensors is a six-dimensional time series composed by the accelerometer output S~ at∈R3 and the gyroscope output S~ ωt∈R3 , where t represents the temporal index of the signal. We choose a sampling frequency of 16 Hz for the accelerometer and 100 Hz for the gyroscope. The low sampling frequency in the case of the accelerometer responds to the need of achieving high performance with a low consumption: we want to run our algorithm on normal smartphones, and human walking frequency is usually between 1.5 Hz and 2.5 Hz, the reason why our sampling frequency of the accelerometer signal should be high enough. At this stage, we carry out all the necessary transformations of the raw sensor data. Since the device can be carried at any position, first, we need to estimate its orientation with respect to an inertial frame. Then, we can estimate the vertical component of the acceleration that is being experienced by the mobile phone in this inertial reference system and, finally, we filter and center the resultant signal for noise reduction. 3.1.1. Attitude Estimation As we pointed out before, we need to know the attitude, or 3D orientation of the mobile phone with respect to an inertial frame, so that we can extract the vertical component of the acceleration experienced by the mobile. This signal will allow the identification of the heel strikes when walking. Some of the previous publications in walking recognition use the acceleration’s magnitude instead of the vertical component. Nevertheless, as the module is independent of a phone’s orientation, it is more failure prone in the presence of movements that have nothing to do with walking, thus increasing the rate of false positive detections. To understand this stage, we must be aware of the existence of two reference systems: (1) a local reference system linked to the phone (also known as body frame or sensor frame). This local frame is defined relative to the device’s screen. (2) There is also an inertial reference system (Earth frame), the axes of which always point towards the same points (with respect to Earth). In the case of the inertial-Earth frame, we work with a frame analogous to the East North Up (ENU) coordinate system [ 28 ], in which the x -axis points toward the East, the y -axis points towards the North Magnetic Pole and the z -axis is pointing in the opposite direction of the gravitational force. The accelerometer and gyroscope readings are provided in the body frame, and therefore it is convenient to project them into the inertial-Earth frame in order to estimate the movement of the person who carries the Sensors 2018,18, 3157 6 of 21 mobile. Hence, it is necessary to know the orientation (attitude) of the mobile with respect to the inertial-Earth frame. In order to represent this orientation, we use quaternions [ 29 , 30 ] because of their many advantages over other representations. A quaternion is a four-dimensional vector that represents the relative orientation between two coordinate frames B and A , as a rotation of an angle θ around a three-dimensional axis r: A Bq=[q0q1q2q3]=cosθ 2,rxsin θ 2,rysin θ 2,rzsin θ 2, (1) where A Bq is the normalized quaternion that represents the orientation of a frame B relative to a frame A [ 30 ]. Following this notation, we will use S Eqt to refer to the current value of the quaternion that represents the orientation of frame E (Earth frame), relative to the frame S (local/Sensor frame). This quaternion represents the current state of the mobile phone. We will use an Extended Kalman Filter (EKF) [ 31 ] to estimate these quaternions. Our EKF will work with a process mode. that is represented as the evolution of the state due to the rotation of the mobile detected with gyroscope. Since the gyroscope measures the rate of angular velocity, it can be used to determine the orientation: S Eˆ q− t=S Eˆ q+ t−1+1 2S Eˆ q+ t−1⊗S~ ωt∆t, (2) where ⊗ is the quaternion product, S~ ωt= ( 0, Sωx,t , Sωy,t , Sωz,t) is the vector that arranges the readings (angular velocities) provided by the tri-axial gyroscope at the current instant, t . S Eˆ q− is the a priori estimate of the state before the current sensor observations are processed, whereas S Eˆ q+ is the a posteriori estimate. Therefore, given an initial orientation, the information provided by the gyroscope can be integrated to determine the device’s change in position. The gyroscope has a high error rate (its data drifts over time), is unstable, and low angular velocities might not be properly registered. Because of all this, and to compensate for all these errors, the EKF uses a measurement model to compute the posterior estimate S Eˆ q+ , Equation (2). Let us consider S~ at as the vector that arranges the current tri-axial accelerometer readings: S~ at={ 0, Sax,t , Say,t , Saz,t} , the observation model of the EKF works on the basis that when the magnitude of the current value of the accelerometer signal ( kS~ atk ) is close to Earth’s gravity ( g )—which would mean that the mobile phone is not being affected by other forces—the accelerometer should measure only Earth-gravity in the local device frame. In this case, the projection of the unit gravity vector in the Earth frame, ~ uG=−→ G/kGk={ 0,0,0,1 } , into the local reference system (body frame), should coincide with the information detected by the tri-axial accelerometer S~ at . This projection of ~ uG into the local reference system can be computed as: S Eˆ q−∗ t⊗~ uG⊗S Eˆ q− t, (3) where S Eˆ q−∗ t is the conjugate of S Eˆ q− t [ 30 ]. According to this, when ~ uG is rotated using the current estimation of the quaternion S Eˆ q− t (Equations (2) and (3)), we should obtain the same values as those currently provided by the accelerometer S~ at . In fact, this difference amongst the predicted values of the accelerometer and the ones observed is precisely what the EKF uses to correct the a priori estimate of the quaternion: S Eˆ q+ t=S Eˆ q− t+KthS Eˆ q−∗ t⊗~ uG⊗S Eˆ q− t−S~ ati, (4) where K is the Kalman gain, a dynamic parameter that weights the importance between the predicted state S Eˆ q− t and the information carried out by the observations S~ at , and which depends on the process noise and the observation noise [ 32 ]. The EFK together with the quaternions has been already used in other works for the estimation of orientation [19,33]. Sensors 2018,18, 3157 7 of 21 3.1.2. Estimation of the Vertical Linear Acceleration Since we know the attitude of the phone, we can now obtain the vertical component of the linear acceleration experienced by the mobile in the Earth reference system. To do so, we just remove the gravity force: lacct=S Eqt⊗S~ at⊗S Eq∗ t−~ G, (5) where S~ at is the vector that arranges the accelerometer readings. The first term of the previous equation (Equation (5)) represents the projection of the information gathered by the accelerometer into the Earth frame. ~ G= ( 0,0,0,9.81 ) is the vector representation of the gravity force in the Earth frame. The vertical linear acceleration, laccz,t (i.e., the vertical acceleration experienced by the mobile once the gravity has been removed), is the last component of the vector represented in Equation (5), lacct= (lacc0,t,lacc1,t,lacc2,t,lacc3,t=laccz,t)). 3.1.3. Signal Characteristics At this point, we have isolated the vertical component of acceleration and eliminated the effect of gravity from it. When a person walks carrying a phone in its hand, and in the absence of other stimuli, the signal received (i.e., the vertical component of the acceleration in the Earth reference system) is often similar to a sinusoidal pattern shown in Figure 2a. Consequently, the signal shown in this figure can be considered as the characteristic signal generated by a person walking at a relatively low frequency [ 34 ]. In this signal, each step taken by the person is identified by the segment formed by a local peak followed by a valley. Hence, in this scenario, it might seem that a Peak Valley algorithm should be enough to identify the steps walked by a person. However, things usually are far from this ideal case, since there is a problem of perceptual aliasing, i.e., very similar signals to the one shown in Figure 2a can be obtained when the mobile phone is being used in a natural way, but when the person is not walking at all (Figure 2b). This makes the identification and segmentation of the signal into walking versus non-walking segments a difficult problem. Section 3.3 describes the way we have addressed this issue. In order to achieve a satisfactory identification of steps, the vertical linear acceleration should be centered in zero as seen in Figure 2, but some devices may have a bias in the readings of the accelerometer that might prevent this centering. Non centered signals can lead to errors in the step detection algorithms. To ensure that this does not happen in our case, we apply a high pass filter to center the signal and thus remove any possible DC offset: yt=αhyt−1+αh(xt−xt−1), (6) where xt is the input (vertical linear acceleration signal), yt the filtered signal, αh=RC RC+∆t and RC =1 2πfcand fcthe cutoff frequency (0.5 Hz). Finally, we apply a low pass filter to remove the noise from the signal: yt=αlxt+ (1−αl)(yt−1), (7) where x is the input (i.e., the already centered acceleration after applying Equation (6)), y the filtered signal, αl=∆t RC+∆tand RC =1 2πfc. Sensors 2018,18, 3157 8 of 21 (a) (b) Figure 2. Vertical linear acceleration sampled at 16 Hz. ( a ) signal obtained when the user walking while holding its phone; ( b ) signal obtained when the mobile phone is being moved by the user but without walking. 3.2. Step Detection Step or gait detection can be achieved in different ways. One typical approach is to use a peak detector [ 35 ] to identify events, like heel strikes, where the impacts of the feet are reflected in the vertical acceleration signal. Other approaches involve exploiting the cyclic and repetitive nature of walking, and hence using properties such as the signal auto-correlation [ 36 ]. In our case, we have used an enhanced Peak Valley detector that locates local extremes in the signal. In this case, a step corresponds to a segment of signal in which there is a peak (local maximum which exceeds a threshold) followed by a valley (local minimum below a threshold). On the other hand, the time elapsed from the previous detected step to the new step-candidate must be above a valid walking period for it to be accepted. This is due to the fact that humans commonly walk within a low range of frequencies [34]. Sensors 2018,18, 3157 9 of 21 However, this peak valley algorithm is susceptible to detect any motion produced within the expected range of frequencies, and hence is prone to commit false positives and, on the other hand, usually has problems detecting changes in the walking speed [ 23 ]. Due to this, we consider the use of another module responsible for filtering out necessary, and, in real time, those parts of the signal which reflect some kind of movement in the mobile, but which have nothing to do with walking. This is a challenging task due to the high perceptual aliasing (i.e., the existence of many signals very similar but caused by different movements of the mobile or human actions). 3.3. Walking Recognition In this section, we describe a module aimed at detecting when the user is walking, and thus discard noisy signals and filter out the false positives detected by the peak-valley algorithm described in the previous section. This module is strictly necessary to reach a symmetric error: on one side, the number of false positives will decrease since a step will be counted if, and only if, it is detected by the peak-valley algorithm and the activity of walking is recognized in the same signal segment by this module. On the other side, the inclusion of this module will have the collateral effect of increasing the number of false negatives, as a consequence of the misclassification of signals (although, as we will see, the rate increase of false negatives will be low). As we will see in the experimental results, the number of false positives and false negatives will tend to be very similar, thus canceling each other and making this proposal very suitable for pedestrian dead reckoning and indoor positioning. We use supervised learning and Bayesian filtering [ 37 ] to differ walking from non-walking sequences in the signal. To do so we define the state xt as a vector which reflects whether the user is walking or not. Bayesian filtering involves the recursive application of a prediction and an update stages. The predictive distribution of the state xtcan be computed by the equation: p(xt|y1:t−1) = p(xt|xt−1)p(xt−1|y1:t−1), (8) where y1:t−1 is the history of measurements up to the time t− 1. Therefore, as we can see, we work with a very simple dynamic model in which the only important element is 2 × 2 transition matrix p(xt|xt−1) , the elements of which have been learned by an inductive process using a training data set. This transition matrix basically introduces a certain amount of hysteresis in the process: i.e., if the user was detected as walking in the previous time interval, there is a not null probability that the user is still walking at the current instant, despite the fact that the activity might not be identified in the current signal segment. Only after a certain time-lapse without recognizing the walking activity does this module set the probability of walking as null. Something similar happens in the contrary case. Regarding the update stage, the Bayes’ rule will be applied to estimate the posterior distribution of the state xt, starting from the current measurement yt: p(xt|y1:t) = αp(yt|xt)p(xt|y1:t−1), (9) where α is a normalizing constant. We write yt to refer to the current observation. In our case, we work with the overlapping sliding window, i.e., segments of signal and not instantaneous sensor readings. This means that yt represents the observed signal ( laccz ) in a window, while yt and yt−1 represent two different windows that overlap. To compute the probability p(yt|xt) , we will merge an ensemble of SVMs together with a logistic estimator that works over the standard deviation of the signal. Regarding the SVM, we opted for an ensemble instead of a single SVM. We work with an ensemble because we have an unbalanced training dataset, with more walking sequences than non-walking sequences; therefore, we decided to use Bagging, oversampling randomly and with replacement from the minority class [ 38 ]. The outputs of all the SVMs that are part of the ensemble were merged to get a probability value: psvm(yt|xt)∝1 n n ∑ i=1 zi svm, (10) Sensors 2018,18, 3157 16 of 21 Table 1. Confusion matrices of the Peak Valley detector, the walking recognition working as a classifier over the candidate steps detected by the Peak Valley, and the Complete System, for each subset of data. Columns show the output of the system while the rows show the output of the ground truth (GT). (a) Complete Dataset Peak Valley Classifier Complete System True False True False True False GT true 13,104 (85%) 706 (5%) true 12,544 (85%) 560 (4%) true 12,544 (83%) 1266 (8%) false 1640 (10%) - false 1259 (8%) 381 (3%) false 1259 (8%) - (b) Hand Peak Valley Classifier Complete System True False True False True False GT true 5775 (92%) 213 (4%) true 5630 (92%) 145 (2%) true 5630 (90%) 358 (6%) false 311 (5%) - false 259 (4%) 52 (1%) false 259 (4%) - (c) Pocket Peak Valley Classifier Complete System True False True False True False GT true 2848 (83%) 195 (6%) true 2693 (83%) 155 (5%) true 2693 (80%) 350 (10%) false 398 (12%) - false 320 (10%) 78 (2%) false 320 (10%) - (d) Hybrid Peak Valley Classifier Complete System True False True False True False GT true 2547 (84%) 163 (5%) true 2410 (84%) 137 (5%) true 2410 (81%) 300 (10%) false 321 (11%) - false 255 (9%) 66 (2%) false 255 (9%) - (e) Not Walking Peak Valley Classifier Complete System True False True False True False GT true 137 (26%) 22 (4%) true 114 (23%) 23 (4%) true 114 (30%) 45 (12%) false 368 (70%) - false 226 (45%) 142 (28%) false 226 (59%) - Table 2. Total steps in the ground truth, detected by the Peak Valley (PV) detector and detected by the whole system (PV with the walking recognition working as a classifier). Total Steps Dataset Hand Pocket Hybrid Not Walking GT 13,810 5988 3043 2710 159 PV 14,744 6086 3246 2868 505 PV + C 13,803 5889 3013 2665 340 Therefore, we think that this makes our proposal suitable for tasks such as Pedestrian Dead Reckoning and, in combination with other techniques, for indoor location. Our system filters out noise in the signal, which is particularly relevant in sequences in which the user uses the phone without barely walking. However, it still has a significant amount of false positives, a problem that we will address in future research. 4.3. Analysis of the Estimated Distance Besides the analysis of the performance of our proposal when recognizing steps, we also carried out experiments to evaluate the accuracy of the estimations made by our system regarding the distance walked by the users. We run 20 experiments with 10 users in which they had to walk along a predefined path of 44 m. This path is shown in Figure 8a. During the experiment, there were marks on the ground every two meters to indicate to the users the path that they had to follow Figure 8b. The users walked following the route and carrying a phone that recorded the data. We run our system using these data Sensors 2018,18, 3157 17 of 21 and compared the distance estimated with our proposal versus the ground truth. It should be noted that the ground truth may have an error of approximately ± 1 m, due to some possible experimental artifacts: the last step taken by the user does not have to necessarily coincide with the last mark on the floor, and there can be a little deviation between the path followed by a person and the one marked on the ground, etc. The device used in these experiments was a BQ Aquaris E5. Figure 9and Table 3show the results of the experiment. In Figure 9, we can see a boxplot with the distances estimated by our proposal. The blue line represents the ground truth. It can be seen that the median is slightly above the ground truth of 44 m and the percentiles Q1 and Q3 only deviate from it around 2 m. There are two outliers that identified a distance greater than 10 m above the real one. It is interesting to note that both belong to the same person. Table 3. Statistical values corresponding to the distances estimated with our proposal. Distance (m) Average 45.11 Standard Deviation 3.31 Maximum 53.8 Minimum 40.38 (a) (b) Figure 8. ( a ) path followed by the people taking part in the experiment aimed for the analysis of the performance of our proposal at estimating the distance travelled by a person walking; ( b ) marks on the ground every 2 m placed to indicate the path that must be followed during the experiment. As it was previously shown in Figure 3, there is a relationship between step length and the walking period, which is taken into a account by our model. Nevertheless, our proposal does not consider the influence of other variables like the user height, etc. The only way we foresee including those other variables is by means of personalized models that can integrate particular information of the user carrying the mobile. Nevertheless, considering the outcome of this experiment, our proposal performs well enough and it does not seem necessary to include this other information to improve the step size estimation. Sensors 2018,18, 3157 18 of 21 Figure 9. Boxplot with the distances estimated by our proposal for the 44 m long path. 4.4. Analysis of the Independence of Our Proposal to the Hardware Being Used In this experiment, we will study the impact of the hardware—model of the mobile phone being used—in the performance of our proposal. Hardware differences generally involve different acquisition frequencies, differences in the amount of noise in the signal, and some devices can even have a bias in one or more of the sensor axes. These signal differences should not affect our algorithm thanks to the subsampling and filtering of the signal, the use of robust features, an ensemble of classifiers or Bayesian filtering, etc., with which our proposal should generalize well. However, we performed experiments with different smartphones, in order to analyze their impact on the outcome of our proposal. We took different models of smartphones at the same time and walked while running our system. If our hypothesis is correct, the number of steps detected by each smartphone should be very similar for each experiment. We performed four experiments using five terminals at the same time. In the first two, we carried all of the telephones in the same hand, and, in the next two, in the pocket. In all of them, we took 60 steps. The results can be seen in Table 4. For the experiments in the hand, there are hardly any variations. In those experiments in which the mobiles are placed in the pockets, experiments (3 and 4), there is a slightly higher variation regarding the number of steps counted with our proposal. Nevertheless, even in this case, the difference is not important, since the maximum difference between the steps counted for the different mobiles is three steps. Looking at the results, we can say that there are certain differences, especially when the mobile phone is in the pocket, but they should not represent a serious threat. Table 4. Steps detected in four experiments running our proposal with different smartphones. Hand Pocket Experiment 1 Experiment 2 Experiment 3 Experiment 4 BQ Aquaris E5 58 57 58 60 Samsung Galaxy A2 58 58 59 59 Xiaomi Mi A2 58 58 59 62 Motorola Moto G6 plus 58 58 61 60 OnePlus 2 58 58 60 59 5. Conclusions In this paper, we describe a robust solution to detect the displacement of a person carrying a mobile phone. Our proposal processes the information provided by the inertial sensors of the phone to estimate the number of steps walked by the person as well as their length. Due to the necessity of Sensors 2018,18, 3157 19 of 21 allowing the user to move freely with no bounds about the position or way of carrying the phone, we had to include the recognition of the walking activity to reduce the number of mistakes that a classic peak valley algorithm would commit. The recognition of the walking activity filters out those parts of the signal that are due to movements of the phone that have nothing to do with the act of walking. This is a complex task due to the existence of a high aliasing, i.e., we get very similar signals for many different movements of the mobile, which makes the filtering out extremely difficult. In this work, we collected an extensive dataset with a large amount of different people walking naturally under different circumstances in order to validate our proposal. We have carried out an extensive analysis of the performance comparing step by step the ground truth with the output of our system. Although further improvements can be carried out in an attempt to increase the performance, we believe that the combined use of our proposal with other positioning systems (WiFi, for example) would allow the achievement of ever more robust estimations of the movement of the person, although this will be part of our future research. Author Contributions: G.R. designed and developed the activity classification and step counting algorithms and analyzed the data; F.E.C. and C.V.R. designed the dataset and developed the software for its acquisition; G.R. and F.E.C. co-wrote the article; R.I. supervised the project, designed the quaternion based pose estimation algorithms and reviewed and edited the manuscript; A.N. implemented the application to run the system on a phone; all authors contributed to the data acquisition. Funding: This research was funded by (AEI/FEDER, UE) grant number TIN2017-90135-R, as well as the Consellería de Cultura, Educación e Ordenación Universitaria (accreditation 2016–2019, ED431G/01 and ED431G/08 and reference competitive group 2014–2017, GRC2014/030), the European Regional Development Fund (ERDF) and was supported by the Ministerio de Economía, Industria y Competitividad in the program Industrial PhD 2014. Conflicts of Interest: The authors declare no conflict of interest. References 1. Lu, H.; Huang, J.; Saha, T.; Nachman, L. Unobtrusive gait verification for mobile phones. In Proceedings of the 2014 ACM International Symposium on Wearable Computers, Seattle, WA, USA, 13–17 September 2014; pp. 91–98. 2. Ren, Y.; Chen, Y.; Chuah, M.C.; Yang, J. User verification leveraging gait recognition for smartphone enabled mobile healthcare systems. IEEE Trans. Mob. Comput. 2015,14, 1961–1974. [CrossRef] 3. Teixeira, T.; Jung, D.; Dublon, G.; Savvides, A. PEM-ID: Identifying people by gait-matching using cameras and wearable accelerometers. In Proceedings of the Third ACM/IEEE International Conference on Distributed Smart Cameras, Como, Italy, 30 August–2 September 2009; pp. 1–8. 4. Dutta, S.; Chatterjee, A.; Munshi, S. An automated hierarchical gait pattern identification tool employing cross-correlation-based feature extraction and recurrent neural network based classification. Expert Syst. 2009,26, 202–217. [CrossRef] 5. Liu, H.; Darabi, H.; Banerjee, P.; Liu, J. Survey of wireless indoor positioning techniques and systems. IEEE Trans. Syst. Man Cybern. Part C (Appl. Rev.) 2007,37, 1067–1080. [CrossRef] 6. Randell, C.; Muller, H. Low cost indoor positioning system. In International Conference on Ubiquitous Computing; Springer: Berlin/Heidelberg, Germany, 2001; pp. 42–48. 7. Mautz, R.; Tilch, S. Survey of optical indoor positioning systems. In Proceedings of the 2011 International Conference on Indoor Positioning and Indoor Navigation (IPIN), Guimaraes, Portugal, 21–23 September 2011; pp. 1–7. 8. Harle, R. A survey of indoor inertial positioning systems for pedestrians. IEEE Commun. Surv. Tutor. 2013 , 15, 1281–1293. [CrossRef] 9. Kourogi, M.; Ishikawa, T.; Kurata, T. A method of pedestrian dead reckoning using action recognition. In Proceedings of the 2010 IEEE/ION Position Location and Navigation Symposium (PLANS), Indian Wells, CA, USA, 4–6 May 2010; pp. 85–89. 10. Vathsangam, H.; Emken, A.; Spruijt-Metz, D.; Sukhatme, G.S. Toward free-living walking speed estimation using Gaussian Process-based Regression with on-body accelerometers and gyroscopes. In Proceedings of the 2010 4th International Conference on Pervasive Computing Technologies for Healthcare, Munich, Germany, 22–25 March 2010; pp. 1–8. [CrossRef] Sensors 2018,18, 3157 20 of 21 11. Steinhoff, U.; Schiele, B. Dead reckoning from the pocket-an experimental study. In Proceedings of the 2010 IEEE International Conference on Pervasive Computing and Communications (PerCom), Mannheim, Germany, 29 March–2 April 2010; pp. 162–170. 12. Yang, J.; Lu, H.; Liu, Z.; Boda, P.P. Physical activity recognition with mobile phones: Challenges, methods, and applications. In Multimedia Interaction and Intelligent User Interfaces; Springer: London, UK, 2010; pp. 185–213. 13. Stirling, R.; Collin, J.; Fyfe, K.; Lachapelle, G. An innovative shoe-mounted pedestrian navigation system. In Proceedings of the European Navigation Conference GNSS, Graz, Austria, 22–25 April 2003; Volume 110. 14. Lee, H.H.; Choi, S.; Lee, M.J. Step detection robust against the dynamics of smartphones. Sensors 2015 ,15, 27230–27250. [CrossRef] [PubMed] 15. Bayat, A.; Pomplun, M.; Tran, D.A. A study on human activity recognition using accelerometer data from smartphones. Procedia Comput. Sci. 2014,34, 450–457. [CrossRef] 16. Jimenez, A.R.; Seco, F.; Prieto, C.; Guevara, J. A comparison of pedestrian dead-reckoning algorithms using a low-cost MEMS IMU. In Proceedings of the 2009 IEEE International Symposium on Intelligent Signal Processing, Budapest, Hungary, 26–28 August 2009; pp. 37–42. 17. Qian, J.; Ma, J.; Ying, R.; Liu, P.; Pei, L. An improved indoor localization method using smartphone inertial sensors. In Proceedings of the 2013 International Conference on Indoor Positioning and Indoor Navigation (IPIN), Montbeliard-Belfort, France, 28–31 October 2013; pp. 1–7. 18. Susi, M.; Renaudin, V.; Lachapelle, G. Motion mode recognition and step detection algorithms for mobile phone users. Sensors 2013,13, 1539–1562. [CrossRef] [PubMed] 19. Goyal, P.; Ribeiro, V.J.; Saran, H.; Kumar, A. Strap-down pedestrian dead-reckoning system. In Proceedings of the 2011 International Conference on Indoor Positioning and Indoor Navigation (IPIN), Guimaraes, Portugal, 21–23 September 2011; pp. 1–7. 20. Chen, L.; Özsu, M.T.; Oria, V. Robust and fast similarity search for moving object trajectories. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, Baltimore, MD, USA, 14–16 June 2005; pp. 491–502. 21. Berndt, D.J.; Clifford, J. Using dynamic time warping to find patterns in time series. In Proceedings of the KDD Workshop, Seattle, WA, USA, 31 July–1 August 1994; Volume 10, pp. 359–370. 22. Vlachos, M.; Kollios, G.; Gunopulos, D. Discovering similar multidimensional trajectories. In Proceedings of the 18th International Conference on Data Engineering, San Jose, CA, USA, 26 February–1 March 2002; pp. 673–684. 23. Brajdic, A.; Harle, R. Walk detection and step counting on unconstrained smartphones. In Proceedings of the 2013 ACM International Joint Conference on Pervasive and Ubiquitous Computing, Zurich, Switzerland, 8–12 September 2013; pp. 225–234. 24. Sasaki, J.E.; John, D.; Freedson, P.S. Validation and comparison of ActiGraph activity monitors. J. Sci. Med. Sport 2011,14, 411–416. [CrossRef] [PubMed] 25. Esliger, D.W.; Probert, A.; Connor, S.G.; Bryan, S.; Laviolette, M.; Tremblay, M.S. Validity of the Actical accelerometer step-count function. Med. Sci. Sports Exerc. 2007,39, 1200–1204. [CrossRef] [PubMed] 26. Webster, K.E.; Wittwer, J.E.; Feller, J.A. Validity of the GAITRite R  walkway system for the measurement of averaged and individual step parameters of gait. Gait Posture 2005,22, 317–321. [CrossRef] [PubMed] 27. O’Connell, S.; Olaighin, G.; Quinlan, L.R. When a step is not a step! Specificity analysis of five physical activity monitors. PLoS ONE 2017,12, e0169616. [CrossRef] [PubMed] 28. Grewal, M.S.; Weill, L.R.; Andrews, A.P. Global Positioning Systems, Inertial Navigation, and Integration; John Wiley & Sons: New York, NY, USA, 2007. 29. Shuster, M.D. A survey of attitude representations. Navigation 1993,8, 439–517. 30. Madgwick, S.O. An Efficient Orientation Filter for Inertial and Inertial/Magnetic Sensor Arrays; Report x-io; University of Bristol: Bristol, UK, 2010. 31. Simon, D. Optimal State Estimation: Kalman, H Infinity, and Nonlinear Approaches; John Wiley & Sons: Hoboken, NJ, USA, 2006. 32. Thrun, S. Probabilistic robotics. Commun. ACM 2002,45, 52–57. [CrossRef] 33. Sabatini, A.M. Kalman-Filter-Based Orientation Determination Using Inertial/Magnetic Sensors: Observability Analysis and Performance Evaluation. Sensors 2011,11, 9182–9206. [CrossRef] [PubMed] Sensors 2018,18, 3157 21 of 21 34. Zijlstra, W.; Hof, A.L. Displacement of the pelvis during human walking: Experimental data and model predictions. Gait Posture 1997,6, 249–262. [CrossRef] 35. Li, F.; Zhao, C.; Ding, G.; Gong, J.; Liu, C.; Zhao, F. A reliable and accurate indoor localization method using phone inertial sensors. In Proceedings of the 2012 ACM Conference on Ubiquitous Computing— UbiComp ’12, Pittsburgh, PA, USA, 5–8 September 2012; p. 421. [CrossRef] 36. Rai, A.; Chintalapudi, K.K.; Padmanabhan, V.N.; Sen, R. Zee: Zero-effort crowdsourcing for indoor localization. In Proceedings of the 18th Annual International Conference on Mobile Computing and Networking, Istanbul, Turkey, 22–26 August 2012; pp. 293–304. 37. Durrant-Whyte, H.F.; Henderson, T.C. Multisensor data fusion. In Springer Handbook of Robotics; Siciliano, B., Khatib, O., Eds.; Springer: Berlin/Heidelberg, Germany, 2008; pp. 585–610 38. Breiman, L. Bagging predictors. Mach. Learn. 1996,24, 123–140. [CrossRef] 39. Preece, S.J.; Goulermas, J.Y.; Kenney, L.P.J.; Howard, D.; Meijer, K.; Crompton, R. Activity identification using body-mounted sensors—A review of classification techniques. Physiol. Meas. 2009 ,30, R1–R33. [CrossRef] [PubMed] 40. Yang, J.Y.; Wang, J.S.; Chen, Y.P. Using acceleration measurements for activity recognition: An effective learning algorithm for constructing neural classifiers. Pattern Recognit. Lett. 2008 ,29, 2213–2220. [CrossRef] 41. Bernecker, T.; Graf, F.; Kriegel, H.; Moennig, C.; Dill, D.; Tuermer, C. Activity Recognition on 3D Accelerometer Data; Technical Report; Institute for Informatics, Ludwig Maximilians University: Munich, Germany, 2012; pp. 1–22. 42. Guyon, I.; Weston, J.; Barnhill, S.; Vapnik, V. Gene selection for cancer classification using support vector machines. Mach. Learn. 2002,46, 389–422. [CrossRef] 43. Zhang, A.; Yang, B.; Huang, L. Feature extraction of EEG signals using power spectral entropy. In Proceedings of the 2018 International Conference on BioMedical Engineering and Informatics, Sanya, China, 27–30 May 2008; Volume 2, pp. 435–439. 44. Thomas, M.; Jankovic, J.; Suteerawattananon, M.; Wankadia, S.; Caroline, K.S.; Vuong, K.D.; Protas, E. Clinical gait and balance scale (GABS): Validation and utilization. J. Neurol. Sci. 2004 ,217, 89–99. [CrossRef] [PubMed] 45. Gopal, K. TrueTime for Android. 2016. Available online: https://github.com/instacart/truetime-android (accessed on 17 September 2018). c 2018 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).