Threshold-Free Step Detection Method for PDR Irrespective of Smartphone's Various Carrying Modes

Abstract

Pedestrian Dead Reckoning (PDR) technology, which can continuously estimate the location of a pedestrian regardless of indoor or outdoor environments, is being researched for application and commercialization in real environments. PDR can be implemented through various devices, and recently it has been implemented based on smartphones and smartwatches. Among the element technologies for this, the step detection technique is the most basic of PDR. However, it is not easy to implement a single algorithm that can accurately detect steps using inertial sensor data obtained from smart devices regardless of the carrying mode of the smart device and the speed of the pedestrian. The reason is that inertial sensor data obtained during one step appears differently according to various gait characteristics. In this paper, we propose a step detection technique without the threshold value used in existing techniques by changing the sensor signal for one step into a sinusoidal form through a LowPass Filter (LPF) with appropriate parameter settings for the accelerometer signal. By making the signal for one step in the form of a sinusoidal wave of one period, the peak can be easily detected only with the time difference of the signal. To achieve this, a Butterworth filter is used as the LPF. In order to properly apply this filter to the PDR, it is important to properly set the order and cutoff frequency of the filter. In this paper, suitable parameters are set through experiments that change the portable mode and walking speed of smartphone. Then we analyze the PDR results based on the set parameters.

Keywords

• eol>Pedestrian dead reckoning
• threshold-free step detection
• low-pass filter
• 1

1. Introduction

In outdoor environments, navigation information can be obtained through the Global Positioning System (GPS)/Global Navigation Satellite System (GNSS). Real-Time Kinematic GPS (RTK-GPS) can provide accurate navigation information through real-time error correction. However, in indoor environments, the performance of GPS/GNSS is significantly degraded due to signal blockage and multipath effects [ 1 ]. To solve this problem, various indoor navigation methods have been proposed. One of these approaches is the radio frequency-based method, which utilizes wireless communication technologies such as Wi-Fi, Bluetooth, and Ultra-Wide Band (UWB) to extract location information [ 2-6 ]. This method exhibits excellent performance in indoor environments. Among them, Wi-Fi utilizes the existing infrastructure within buildings, thereby eliminating the need for additional installation costs and enabling cost savings. However, it may encounter difficulties in position estimation when facing signal interference or obstacles. Additionally, UWB offers relatively high accuracy, but significant infrastructure costs make it problematic for indoor navigation.

Pedestrian Dead Reckoning (PDR) is a technology that estimates the position of pedestrians by attaching inertial sensors to their bodies and is independent of infrastructure, thus not being affected by external environments [ 7 ]. The research direction of PDR can be divided into two approaches based on the mounted location of the Inertial Measurement Unit (IMU). These approaches are the Integration Approach (IA) and the Parametric Approach (PA) [ 8 ]. The IA involves mounting the IMU on the foot and utilizing Inertial Navigation System (INS) to update the navigation information [ 9 ]. IA-based PDR compensates for the increasing errors over time by performing Zero-velocity UPdaTe (ZUPT) [ 10-11 ]. Additionally, the PA is primarily used in smartphone-based PDR. It involves detecting pedestrian steps, determining stride length based on walking characteristics, calculating the direction of movement, and then combining this information to update the position. PA has the advantage of being applicable to various carrying modes. However, if it fails to accurately detect pedestrian steps and recognize walking type, it can significantly affect the navigation results. Therefore, accurate step detection is a basic requirement for position estimation. A common approach for step detection is to use threshold methods [ 12 ]. However, it is difficult to update the adaptive threshold value dynamically and accurately in various walking speeds and carrying modes. Therefore, in this paper, to achieve a threshold-free approach, a Butterworth filter, which is a kind of Low-Pass Filter (LPF), is used to convert the signal into a sinusoidal waveform. Once the signal is filtered as a sinusoid, the rising and falling curves are determined by taking the difference of the signal. Subsequently, the transition point from the rising curve to the falling curve is identified as a positive peak, enabling the detection of steps. Therefore, it is very important to transform the signal into a sinusoidal waveform. To achieve this, the parameters of the Butterworth filter must be properly set. However, the parameters of the Butterworth filter, namely the order and cut-off frequency, are set differently and used in various ways in different papers [ 13-17 ]. Increasing the order of the filter is effective in changing the walking signal into a sinusoidal waveform. However, a time delay occurs depending on the order. Time delay is not a big problem when performing only PDR, but when integrating PDR with other sensors, time asynchrony problem occurs, so it is important to determine the minimum filter order for PDR for smart devices. The higher the cutoff frequency, the more effectively the characteristics of the signal can be captured. However, if the cutoff frequency is too high, accurate step detection may be difficult due to the influence of noise. Therefore, through experimentation, the appropriate order and cutoff frequency of the Butterworth filter are determined to accommodate various walking speeds (slow, normal, fast) and different carrying modes. Subsequently, step detection is performed using the established parameters. Finally, the performance of smartphone-based PDR in handheld mode is analyzed.

2. Smartphone-based PDR

where N is the number of sensor data obtained in the stop state.

Afterwards, step detection can be performed based on peak values. To achieve this, the synthesized signal needs to be transformed into a sinusoidal waveform by applying a Butterworth filter with appropriate cutoff frequency and order to attenuate frequencies outside the desired band. Once the sinusoidal waveform is obtained, the rising and falling curves can be (1) (2) easily identified by taking the signal's differentiation. This allows for the detection of positive peaks, enabling step detection without the need for a threshold. However, if the generated waveform deviates significantly from a perfect sinusoid, it may lead to incorrect step detection. Therefore, it is important to appropriately set the cutoff frequency and order of the Butterworth filter. Detailed explanations of this process can be found in Chapter 3.

Stride estimation refers to determining the distance between steps. In INS, distance is typically calculated by integrating the accelerometer outputs twice. However, in smartphone-based PDR, stride estimation relies on the relationship between stride and walking states. Stride can be estimated using walking frequency and acceleration variance, and it can be expressed as follows [ 8 ]. where WF is the walking frequency, AV denotes the variance of the accelerometer, and , and are pre-learned parameters based on prior calibration.

The estimation of the heading angle relies on the gyroscope output. The calculation of the heading angle based on quaternions can be expressed as follows.

where q represents the quaternion, ∗ denotes quaternion multiplication, and refers to the gyroscope output. The heading angle may be calculated based on the updated quarternion.

Smartphone-based PDR relies on combining these pieces of information to update the position. However, the process of step detection can lead to significant errors due to both false detections and missed detections. Therefore, accurate step detection is fundamental and the most important factor in smartphone-based PDR.

3. Threshold-free step detection method

The walking process of pedestrians exhibits periodicity, and thus the acceleration waveform is similar to a sinusoidal wave. However, the collected raw data can contain significant errors due to noise and hand tremors. Therefore, in this paper, suitable parameters of the Butterworth filter are experimentally determined to obtain smoother and clearer acceleration variations. In addition, the applicability is evaluated by analyzing the set parameters for various walking speeds, carrying modes, and different pedestrians.

3.1. Experiment-based parameter setting of LPF

LPF is commonly used to suppress interfering signals and reduce noise by attenuating certain frequencies. Sliding Window Averaging (SWA) and Butterworth filter can be employed for this purpose. SWA acts as a LPF by averaging the data within a window to reduce noise components. However, it lacks adaptability across different signal characteristics due to the use of a fixed ̇ = 21 ∗ ( ) (4) window. Therefore, a Butterworth filter is used as the LPF. For example, the second-order transfer function of the Butterworth filter for analog LPF can be expressed as follows [ 14 ]. ( ) = where 2 represents the selected cut-off frequency(rad/s). To obtain the digital formulation of the IIR filter, the bilinear transformation = 2 (1− −1 1+ −1) can be used. where denotes the sampling interval. where denotes the sampling interval. line represents the signal before filtering, and the red solid line represents the signal after filtering. Prior to filtering, the sensor data exhibited significant high-frequency noise components. However, following filtering, these components were removed resulting in a clear and distinct smooth sinusoidal waveform. Such data can provide valuable information for the step detection phase. However, if the order and cut-off frequency of the Butterworth filter are incorrectly set, the signal may not be perfectly transformed into a sinusoidal waveform. Therefore, it is crucial to determine appropriate values for the order and cut-off frequency. A higher cut-off frequency allows for better reflection of the signal's characteristics. However, if the signal's characteristics are overly emphasized, it can be difficult to perform step detection due to the influence of noise. Additionally, as the order increases, the magnitude of the signal decreases and a delay issue arises. To address these considerations, an analysis of the order and cut-off frequency based on the pedestrian's walking speed is conducted. Firstly, the accuracy of step detection is compared by varying the cut-off frequency to determine the optimal value.

Figure 3 shows the step detection results with a fixed order of one and changes in the cut-off frequency to 2 Hz and 5 Hz. The blue dotted line represents the synthesized accelerometer signal, and the red solid line represents the signal after Butterworth filtering. The green dots indicate the peak detection results. The actual number of steps was 59, and as shown in Figure 3(a), precisely 59 steps were detected. However, 66 steps were detected in Figure 3(b). The reason for this discrepancy is that in Figure 3(b), as shown in the enlarged image in the 38.5 second, the signal was not entirely transformed into a pure sinusoidal waveform due to the less smoothness of the signal, leading to an incorrect detection. After conducting experiments by varying the cutoff frequency from 1Hz to 5Hz, it is determined that 2Hz is the most suitable choice.

After determining the cut-off frequency as 2 Hz through experimentation, the next step is to determine the order of the Butterworth filter. The order was analyzed based on the walking speed of the pedestrians. The walking speeds were classified into three categories: slow walking, normal walking, and fast walking. The actual number of steps for each walking speed category is as follows: 68 steps for slow walking, 59 steps for normal walking, and 50 steps for fast walking. Figure 4 shows the step detection results for each walking speed category using a first-order Butterworth filter. In all three walking speeds, false peaks are detected, leading to incorrect step detection. This method failed to detect steps correctly as the signal was not entirely transformed into a pure sinusoid waveform. To address this issue, we increased the order by one and conducted experiments using the same method to determine the appropriate order for all walking speeds, as shown in Table 1. (c) Figure 4: Step detection results according to walking speed, showing (a) slow, (b) normal, and (c) fast.

Based on the results of five experiments conducted for each walking speed category, the table shows the difference between the actual number of steps and the step detection results for Butterworth filter orders from one to three, with a cut-off frequency of 2 Hz. In Table 1, we can see that the first-order Butterworth filter results in many false detections for all walking speeds, as illustrated in Figure 4. On the other hand, the second-order filter showed minimal false detections, but even a single false detection can affect the accuracy of PDR. Therefore, designing the Butterworth filter with a third order provides a more stable and reliable performance, ensuring a higher level of accuracy. Based on the experimental results, it was observed that with appropriate parameter settings, the Butterworth filter can be applied to all walking speeds. Therefore, based on the results from the Handheld mode experiment, it was determined that setting the Butterworth filter with a third order and a cut-off frequency of 2Hz is suitable. The choice of using a third order instead of higher orders is to minimize the time delay associated with higher-order filters. The time delay for the first-order filter is about 0.05 seconds, for the second-order filter it is about 0.09 seconds, and for the third-order filter it is about 0.15 seconds. While a larger time delay is acceptable when using pedestrian navigation solely, for complex navigation systems that involve Wi-Fi or other measurements, it is preferable to have minimal time delay to ensure effective integration with other navigation techniques.

3.2. Apply set parameters for each pedestrian

In section 3.1, the parameters of the Butterworth filter were set based on experiments with a single pedestrian. However, it is important to ensure that these parameter settings are effective for various pedestrians. Therefore, additional experiments were conducted to analyze the validity of the Butterworth filter parameters for different pedestrians. Figure 5 compares the step detection results using SWA and the Butterworth filter for two pedestrians. The cyan dots represent the step detection results using SWA, and the green arrows indicate the step detection results using the Butterworth filter. In this experiment, a window size of 10 was used for SWA. (b) Figure 5: Step detection results according to walking speed, showing (a) slow, (b) normal, and (c) fast.

Pedestrian A has a height of 176cm and weighs 70kg, while pedestrian B has a height of 184cm and weighs 81kg.

During the experiments, a method of temporarily stopping for a certain period of time before changing the walking speed was employed. When using SWA, both pedestrians were able to detect steps accurately in the normal walking speed. However, false detections were observed in the slow and fast walking speeds. This is because the signal magnitudes vary for different walking speeds, but a fixed window size was used, which is not adaptive to all walking speed signals. However, it can be confirmed that the Butterworth filter detects the steps well regardless of the walking speed of both pedestrians. As a result, it was observed that the Butterworth filter performed well in step detection for both pedestrians, regardless of their walking speeds. Therefore, through experiments, it has been confirmed that the parameters set in this paper allow accurate step detection regardless of the pedestrian and walking speed.

3.3. Apply set parameters to various carrying mode

Unlike mounting the IMU on the foot various carrying modes need to be considered for smartphone-based PDR. Therefore, we conducted experiments to verify if the set Butterworth filter parameters were applicable across various carrying modes. Since the handheld mode had already been validated in a previous experiment, six representative carrying modes were performed to represent different environments. The carrying modes were as follows: calling, strap necklace, pocket (front), pocket (back), handbag, and backpack.

Figure 6 shows the results of step detection for each carrying mode. The blue dashed line represents the synthesized acceleration signal, and the red solid line represents the Butterworth filter signal. The green dots indicate the peak detection results. It can be observed that the synthesized acceleration signals vary across different carrying modes. Nevertheless, by using appropriate parameters for the Butterworth filter, the signals with different characteristics are simplified into sinusoidal waves, enabling accurate step detection.

The accuracy of step detection for each carrying mode is shown in Table 2. Except for one false step detection in the handbag mode, all other carrying modes achieve 100% accuracy in step detection.

(a) (d)

(b) (e)

(c) (f) Porket (Front), (d) Porket (Back), (e) Handbag, and (f) Backpack. Results of step detection in six carrying modes

Carrying mode

Calling

Strap necklace Porket (Front) Porket (Back)

Handbag Backpack

In Chapter 3, the appropriate order and cut-off frequency for the Butterworth filter were determined based on experiments. The experiments applied different walking speeds, different pedestrians, and various carrying modes. The results showed that accurate step detection is achievable without using threshold values.

4. Analysis of smartphone-based PDR experiment

This study conducted smartphone-based PDR experiments using Samsung S12-Ultra device in Handheld mode. An Android application was utilized to collect accelerometer 3-axis and gyroscope 3-axis data at a sampling rate of 100Hz for the experiments. Based on this data collection, the Butterworth filter's parameter settings were evaluated for step detection and smartphone-based PDR algorithm testing, and the results were analyzed.

Figure 7 shows the digital map and experiment trajectories of Electronics and Telecommunications Research Institute (ETRI) Building 12. (a) shows a 4th floor trajectory with the same starting and ending points, and (b) shows a 6th floor trajectory with different starting and ending points.

Figure 8 shows the PDR results using the Butterworth filter parameters set in Chapter 3 are compared with the SWA-based PDR results. The blue dotted line represents the SWA-based PDR results, while the red solid line represents the Butterworth filter-based PDR results. It can be observed that Butterworth filter-based PDR provides more accurate results than SWA in both the 4th floor trajectory and the 6th floor trajectory. This is because the Butterworth filter simplifies the synthesized accelerometer signal into a sinusoidal waveform, resulting in minimal false detections and missed detections during step detection.

(a) (b) Figure 7: Korea Electronics and Telecommunications Research Institute (ETRI) Building 12 Digital Map and Trajectory, showing (a) 4th floor, and (b) 6th floor.

5. Conclusions

Smartphone-based PDR detects the pedestrian's step, determines the strid length based on the gait characteristic information, calculates the moving direction, and then updates the location by combining this information. However, inaccurate detection of the pedestrian's steps and gait characteristics can significantly impact the navigation results. In this paper, a threshold-free approach is used for accurate step detection. To achieve step detection without threshold, a Butterworth filter among LPFs is employed to transform the accelerometer synthesized signal into a sinusoidal waveform. By filtering the composite signal with the Butterworth filter, rising and falling curves can be obtained through signal differentiation. steps are detected by identifying the moment when the rising curve transitions to the falling curve, which is detected as a peak value. Therefore, it is critical to accurately transform the signal into a sinusoidal waveform using the Butterworth filter. To achieve this, the parameters of the Butterworth filter, such as the order and the cut-off frequency, must be selected and set carefully based on experimentation. Moreover, various experiments were conducted to analyze the applicability of this approach to different walking speeds, different pedestrians, and carrying modes. Results showed that the step detection method without using threshold, using the selected parameters for the Butterworth filter, accurately detected steps in diverse environments, showcasing adaptability to different conditions. Furthermore, a comparative analysis with the commonly used SWA revealed that the proposed approach consistently achieved more stable and accurate step detection. Based on this, we analyzed the performance of the handheld mode PDR. The proposed Butterworth filter, which was implemented using the parameters suggested in this paper, demonstrated robust step detection in various environments compared to SWA. Therefore, it is evident that the performance of PDR using the proposed method outperformed SWA. However, during experiments, we noted the detection of stationary steps. Detecting stationary steps as steps could lead to a change in the distance traveled, which could ultimately affect the performance of PDR. Therefore, we plan to conduct further research in the future to develop an algorithm that detects and removes stationary steps, to improve the performance of PDR.

Acknowledgements

This work was supported by Crime Victim Protection R&D program funded by Korean National Police Agency (KNPA, Korea). [Project Name: Development of an Integrated Control Platform for Location Tracking of Crime Victims based on Low-Power Hybrid Positioning and Proximity Search Technology / Project Number: RS-2023-00236101]

References

[1] M. S. Grewal , L. R. Weill , A. P. Andrews , Global Positioning Systems , Inertial Navigation, and Integration., Wiley, New York, NY, 2001 .

[2] K. Han , S. M. Yu , S. -L. Kim , Smartphone-based Indoor Localization Using Wi-Fi Fine Timing Measurement , in: International Conference on Indoor Positioning and Indoor Navigation (IPIN), Pisa , 2019 , pp. 1 - 5 . doi: 10 .1109/IPIN. 2019 . 8911751 .

[3] S. Guo , Y. Zhang , X. Gui , L. Han, An Improved PDR/UWB Integrated System for Indoor Navigation Applications , IEEE Sensors Journal 20 ( 2020 ) 8046 - 8061 , doi: 10.1109/JSEN. 2020 . 2981635 .

[4] X. Wang , Y. Zhuang , Z. Zhang , X. Cao , F. Qin , X. Yang , X. Sun , M. Shi , Z. Wang , Tightly Coupled Integration of Pedestrian Dead Reckoning and Bluetooth Based on Filter and Optimizer, IEEE Internet of Things Journal 10 ( 2023 ) 7327 - 7342 , doi: 10.1109/JIOT. 2022 . 3228790 .

[5] K. Nguyen-Huu , K. H. Lee , S. -W. Lee , An indoor positioning system using pedestrian dead reckoning with WiFi and map-matching aided , in: International Conference on Indoor Positioning and Indoor Navigation (IPIN) , Sapporo , 2017 , pp. 1 - 8 , doi: 10.1109/IPIN. 2017 . 8115898 .

[6] Y. Yu , R. Chen , L. Chen , G. Guo , F. Ye , Z. Liu , A Robust Dead Reckoning Algorithm Based on WiFi FTM and Multiple Sensors , Remote Sens 11 ( 2019 ), doi: 10.3390/rs11050504.

[7] S. Y. Cho , C. G. Park, MEMS based pedestrian navigation system , The Journal of Navigation 59 ( 2006 ) 135 - 153 doi: 10.1017/S0373463305003486.

[8] S. Park , J. H. Lee , C. G. Park , Robust Pedestrian Dead Reckoning for Multiple Poses in Smartphones, IEEE Access 9 ( 2021 ) 54498 - 54508 , doi: 10.1109/ACCESS. 2021 . 3070647 .

[9] H. Fourati , Heterogeneous data fusion algorithm for pedestrian navigation via foot-mounted inertial measurement unit and complementary filter , IEEE Transactions on Instrumentation and Measurement 64 ( 2015 ) 221 - 229 , doi: 10.1109/TIM. 2014 . 2335912 .

[10] M. Ma , Q. Song , Y. Gu , Y. Li , Z. Zhou , An Adaptive Zero Velocity Detection Algorithm Based on Multi-Sensor Fusion for a Pedestrian Navigation System , Sensors 18 ( 2018 ), doi: 10.3390/s18103261.

[11] S. K. Park , Y. S. Suh , A zero velocity detection algorithm using inertial sensors for pedestrian navigation systems , Sensors 10 ( 2010 ) 9163 - 9178 , doi: 10.3390/s101009163.

[12] H. Zhang , W. Yuan, Q. Shen , T. Li , H. Chang , A Handheld Inertial Pedestrian Navigation System With Accurate Step Modes and Device Poses Recognition , IEEE Sensors Journal 15 ( 2015 ) 1421 - 1429 , doi: 10.1109/JSEN. 2014 . 2363157 .

[13] A. R. Jimenez , F. Zampella , F. Seco , Improving Inertial Pedestrian Dead-Reckoning by Detecting Unmodified Switched-on Lamps in Buildings, Sensors 14 ( 2014 ) 731 - 769 , doi: 10.3390/s140100731.

[14] A. Manos , I. Klein, T. Hazan, Gravity-Based Methods for Heading Computation in Pedestrian Dead Reckoning , Sensors 19 ( 2019 ), doi: 10.3390/s19051170.

[15] L. Gao , S. Konomi , Indoor Spatiotemporal Contact Analytics Using Landmark-Aided Pedestrian Dead Reckoning on Smartphones, Sensors 23 ( 2023 ), doi: 10.3390/s23010113.

[16] Z. Tian , Y. Zhang , M. Zhou , Y. Liu, Pedestrian dead reckoning for MARG navigation using a smartphone , EURASIP Journal on Advances in Signal Processing 2014 ( 2014 ), doi: 10.1186/ 1687 -6180-2014-65.

[17] S. Y. Cho , C. G. Park , Threshold-less Zero-Velocity Detection Algorithm for Pedestrian Dead Reckoning , in: 2019 European Navigation Conference (ENC) , Warsaw, 2019 , pp. 1 - 5 , doi: 10.1109/EURONAV. 2019 . 8714170 .