Pedestrian dead reckoning (PDR) is one of the representative methods of indoor positioning, and many researchers have developed PDR methodologies that can accurately estimate step lengths of users. We propose a novel method to improve the accuracy of the step-length estimation by dividing up a gait into finer movements than a single step and extracting features. To our knowledge, no other studies have attempted to improve precision by breaking down the motion of a single step. This is not only in the step-length estimation, but also in machine learning studies for PDR. We propose two methods of breaking down a step: one is to segment the step data at the extreme values of the norm of the acceleration vectors, and the other is to segment the data so that the extreme values are at the middle points of the segmentation. The step length is estimated by extracting features from each segment. The results of an evaluation shows that these methods improved accuracy by 10% over the compared method.
Location information is used for various purposes such as navigation, analyses of people flow
[
Machine learning has been used to improve PDR[16, 17, 18, 19], for example, step-length estimation, walking heading estimation, body heading estimation, walking motion recognition. These machine learning models were trained using the time windows or one-step windows. However, this does not take advantage of the characteristics of walking. Since gait is the repetition of patterns, we thought that the accuracy of these models could be improved by dividing each steps into smaller segments corresponding to the walking motion.
In this paper, as a first step, we propose a method of precisely estimating the step length. Using the repetition of gait patterns as a reference, the step-length estimation model that uses machine learning was created by the divided gait data. We also analyzed the relationship between acceleration and motion.
In dividing the gait into smaller units, we referred to the findings of studies on the gait cycle. The Rancho Los Amigos study [20] is representative; it showed that gait can be divided into cyclic movements: feet landing, taking of, swinging, and other movements during gait. (The details are given in section 2.) We aimed to improve the step-length estimation by utilizing machine learning with this cycle in mind. The proposed method requires an analysis of the correspondence between the movements and sensor values obtained from devices such as smartphones. In addition, it is necessary to obtain correct data on walking in order to estimate the step length by using machine learning.
To deal with the above two problems, we utilized human behavior recognition technology that has become popular in recent years. This technology is capable of acquiring time series data on the 3D positions of body parts such as wrists, ankles, shoulders, and chest. For the former problem, we analyzed the correspondence between body movements obtained using this recognition technology and sensor values obtained from smartphones carried by pedestrians. For the latter, we generated correct data on the step length by applying the foot movements obtained from the recognition technology.
Our contributions are as follows: • We improved the step-length estimation by analyzing gait in units finer than a single step. • We gained insight into useful features when segmenting gait into units finer than a single step.
• We clarified the correspondence between movements and important features The rest of this paper is as follows. Section 2 reviews related work. Section 3 describes an analysis of information useful for splitting the gait and our step-length estimation using it. Section 4 describes the results of an experiment and section 5 discusses the results. Conclusions are presented in Section 6.
PDR has two main elements, estimating the walking distance and estimating the heading. The walking distance can be estimated using the step length because it is the sum of step lengths. Numerous methods of estimating step lengths have been proposed for PDR [21, 22, 23, 24]. In this section, we explain the walking distance estimation of previous mechanical PDR and machine learning PDR (ML-PDR). Next, we describe the methods of collecting training data for ML-PDR. In addition, we introduce the periodicity of gait referred to for dividing the steps in our method.
In mechanical PDR, the step length is used as a walking distance of a step. In order to perform a step-length estimation, steps have to be first detected. This is generally done using the extreme values of the norm of the acceleration vectors. It is known that the interval from one minimum value to the next minimum value corresponds to a single step. The step length can be estimated in a number of ways. Early PDR methods used the average step length of a person, assuming it to be a fixed value. However, the step length is not constant but varies. Kim et al. [ 25] and Weinberg et al. [26] are representative of the approaches that go beyond this assumption. The method of Kim et al. utilizes the average acceleration during a step, whereas the one of Weinberg et al. uses the amplitude of the vertical acceleration during a step. Both approaches calculate the step length mechanically. In addition, since they detect individual steps and output a value for each step, they take more advantage of the characteristics of walking compared with a method that uses machine learning.
In ML-PDR, the walking distance is usually calculated using the walking speed and time [16, 17, 18, 19]. One of the main reasons this is popular is the ease of creating training data. Walking speed and time are easy to collect training data than step detection and step length estimates. Asraf et al. [17] input acceleration and angular velocity data into a neural network by dividing the data into fixed time windows. However, since the time windows are mechanically segmented, their method does not consider the characteristics of human gait.
Fixed time window is adopted in other research of ML-PDR[18, 19]. In addition, it is dificult to understand what motions are important for the walking-distance estimation. Klein et al. [21] input acceleration and angular velocity data into a neural network by dividing them into variable time windows at each step. Thus, their method extracts features at each step. However, this method underutilizes the features of walking. By comparison, we focus on the cycle of walking and use a window size smaller than one step.
When using machine learning for the walking-distance estimation, acceleration data are input and the walking speed is output. Here, it is necessary to collect training data. Kang [27] et al. collected it by utilizing GPS. In particular, location and time information obtained from GPS were used to calculate the walking speed. Feigl [28] et al. used optical markers attached to pedestrians’ bodies and installed 28 cameras to obtain their positions with millimeter-level error. Their system could acquire positions at a high sampling rate of 100 Hz. Herath [18] et al. used the Google Tango device to collect walking speed data. Google Tango can accurately estimate the relative position of the terminal by using a camera and a depth sensor in addition to acceleration and angular velocity. They calculated the walking speed from the trajectory of the device and used it for training.
A few studies have used machine learning to estimate the step length. Klein [21] et al. collected training data by dividing the total distance by the number of steps. However, the data generated with this method is very rough. Vandermeeren [29] et al. manually created correct step-length labels by installing a camera on the ceiling and a tape measure on the ground. However, it is extremely dificult to obtain the necessary amount of data for training the model because the labels need to be manually created for each step.
In contrast to the above methods, we obtain correct step-length data by using human behavior recognition technology. The system was developed by our research team. Specifically the technology tracks the ankle’s 3D position.
The Rancho Los Amigos method [20] is representative of the methods used in studies of the gait cycle. It splits the gait into two phases. The first phase is the stance phase. The stance phase is when the feet are on the ground. That is, it is the period from when the feet land and the center of gravity of a person shifts to when the feet take of. The second phase is the swing phase. The swing phase is when the foot is in the air. That is, it is the period from the moment the foot takes of to the moment the foot swings and lands on the ground.
We divide up the gait into periods based only on IMU sensor data. As such, a division as above is not always possible. Moreover, the Rancho Los Amigos method does not necessarily give an accurate step-length estimation. Therefore, we searched for a way to divide up a single step on the basis of acceleration data.
First, step sections are recognized using the extreme values of the norm of the acceleration vectors. Second, steps are divided into segments smaller than a single step. Third, features are extracted from these segments. Finally, the machine learning model outputs the step length. Fig. 2 shows the key idea of our method: feature extraction in every phase. By linking data in every phase to walking movement, we can get features which we have not extracted.
We put smartphone in the chest pocket to refrain from shaking it. Fig. 3 shows the holding position of a smartphone and acceleration coordinate system.
To divide up a single step, we need to recognize the step sections. Here, we used the x-, y-, and z-axis acceleration values (, , ) collected by a smartphone and recognized the sections by using the minimum values of the norm of the acceleration vectors. The norm of the acceleration vectors () is given as: = √︀2 + 2 + 2. (1) Here, a step section is from one minimum value to the next.
First, we describe the information that can be used for segmentation. Then, we describe how the gait is segmented using them.
We analyzed acceleration in units finer than a single step to find an optimal segmentation method. We did not apply the segmentation method based on gait cycle [20]. This is because we have not been able to find characteristics of acceleration that correspond to the segmentation boundaries. In addition, splitting up the gait as per this gait cycle does not necessarily lead to an accurate estimation of the step length.
We examined the x, y, and z-axis acceleration values (, , ) collected by a smartphone, the norm of the acceleration vectors, and the horizontal component of acceleration.
The horizontal acceleration (ℎ) is given as: ℎ = √︀2 + 2. (2)
We found that the extreme values of the norm of the acceleration vectors were useful for splitting up the gait, as they satisfy the following criteria.
The first criterion is whether the information used for segmentation corresponds to the body motion. If it occurs at various times, we cannot map the information to a motion even if it is detected. Therefore, we can’t use such information for segmentation.
The second criterion is the reproducibility of detection. Without a correct detection, it is not possible to accurately segment a gait. This causes a significant decrease in the accuracy of the step-length estimation. Therefore, it is necessary to find features with high reproducibility.
We used human behavior recognition technology to determine features that satisfy these criteria. Fig. 4 shows the analysis of body movements obtained using this technology and acceleration data to find a segmentation method with high detection reproducibility.
The analysis can acquire the 3D positions of ankles, knees, chest, wrists, etc., at about 20 Hz. We analyzed the correspondence between the body movements and the acceleration. We used Network Time Protocol (NTP) to synchronize the smartphone that acquires the acceleration data with the human behavior recognition device. Since walking motion corresponds to foot motion, we analyzed the correspondence between foot motion and acceleration. We used the x-axis and z-axis components of the acceleration, the norm of the acceleration vectors, and the horizontal component acceleration, as shown in Fig. 5. The positions of the ankles are also shown. We didn’t use the y-axis (vertical) component of the acceleration because it is similar to the norm of the acceleration vectors.
(a) Sample of X-axis acceleration. It was dificult to detect features closely related to the motion. (b) Sample of Z-axis acceleration. It was dificult to detect features closely related to the motion. (c) Sample of the norm of the acceleration vectors. There was a relationship between the movement of the feet and the extreme values. There was also the reproducibility of the extreme value detection. (d) Sample of horizontal component of acceleration. It was dificult to detect features closely related to the motion.
From Fig. 5c, the extreme values of the norm of the acceleration vectors satisfy the two criteria, so we concluded that it was valid. There is a relationship between the movement of the feet and the extreme values. We can see that maximal values are reached when one foot is stationary and the other foot is changing velocity rapidly. Also, we can see that minimum values are reached just after one foot stops moving and just before the other one starts moving. Thus, the relationship between the norm of the acceleration vectors and the walking motion is clear. Fig. 6 shows their correspondence. After examining these results, we considered it appropriate to use the extreme values of the norm of the acceleration vectors for gait segmentation. On the other hand, it was dificult to detect features closely related to the motion except for the norm of the acceleration vectors.
In the previous section, we described that the extreme values of the norm of the acceleration vectors are useful for gait segmentation. In this section, we describe the methods of dividing up the gait by using these values. Specifically we use them as the segmentation points or middle points of the segmentations. Fig. 7 shows three methods (A, B, and B’) of doing so.
In method A, the data are segmented with the maximal values and minimum values. A step is divided into two phases. The minimum values occur between the landing and take-of of the foot. The maximal values occur at the moment when the foot swings and overtakes the other foot. Therefore, the two phases mean the following. The first phase is the interval where the foot swings and overtakes the other foot from the timing near where the foot takes of. The second phase is the interval from when the foot overtakes the other foot until the foot lands.
In method B, the data are divided up so that the maximal values and minimum values are at the middle points of the segmentations. A step is divided into three phases. The first phase is from a little before the previous step lands until a little after the foot takes of. The second phase is the interval when the foot swings past the other foot. It spans a short time after the foot takes of to a short time before the foot lands. The third phase is the interval from a little before the foot lands until a little after the foot takes of to take the next step. In method A, the step is split when the foot is swinging and when the foot is landing. By comparison, method B treats when the foot is swinging and when the foot is landing as one phase. It also includes the end of the previous step and the beginning of the next step.
In method B’, the data are split up at the minimum values. Additionally, the data are divided up so that the maximal values are at the middle points of the segmentations. Compared with method B, this method does not include the features of the previous and next steps since it uses the minimum values to divide up the data.
We extracted features that the machine learning would use to make the estimation model of the step length. We extracted the features from the raw acceleration (x, y, z-axis), the norm of the acceleration vectors, and the horizontal component acceleration values. We also used general features in PDR, specifically, maximum, minimum, and mean value, variance, kurtosis, and skewness. In addition, we devised our own features, i.e., the time taken for each phase and a slope value. We supposed that the time taken for each phase, such as the time from when the foot takes of to when the foot passes by the other foot, might be useful because we thought that it might afect the step length. The "slope" is the diference between the maximum value and the minimum value divided by the time ().
In method B and B’, the central phase has two slopes. The front part is from the beginning of the central phase to the maximum value. The back part is from the maximum value to the end of the central phase. Fig. 8 shows that the slope of the norm of the acceleration vectors obtained by the segmentation would be an efective feature.
In the case of the first phase or the front part of the central phase, the slopes are given as: = −
(3) In the case of the last phase or the back part of the central phase, the slopes are given as: = − .
(4)
We used multiple regression, Xgboost, and support vector machine (SVM) as the machine learning models. These models were trained with the extracted features described in the previous section.
Here, we explain the experimental conditions, the accuracy of the step-length estimation model we proposed, the importance of the features for machine learning, and the features of high importance. These high importance features were used for the analysis of the correspondence between features and walking motion.
The subject walked toward the installed LiDAR. To collect the acceleration values, he had smartphone in his chest pocket and walked.
A Google pixel 3 was used to collect the acceleration values, while LiDAR (Intel RealSense) was used to collect the training labels for the step length. The skeletal recognition software, Cubemos, was used to recognize the human skeleton. The sampling rates were about 400 Hz for the pixel3 and about 30 Hz for the LiDAR. We collected 1065 step-length data ranging from 30 cm to 70 cm from one person.
Here, we describe how the training labels for the step lengths were collected. Point cloud data were obtained from the LiDAR. Then, the data were transformed into a skeleton by Cubemos. We utilized the skeleton coordinates of both ankles. Fig. 9 shows the estimated step lengths. Since the feet stop alternately in walking, we took the distance between the coordinates of the ankles to be the correct step length.
We evaluated the accuracy of the step-length estimation by creating a model using the features obtained by our step-division method. We evaluated four methods, A, B, B’ and all three (Mixed), in comparison with a one-step segmentation method (One Step). One Step extracted features every single step and did not divide a step into smaller segments.
We calculated the errors between the correct step length collected by LiDAR and the estimated step length using the accelerometer. We conducted a 10-fold cross-validation. The evaluation function was the mean squared error (MSE).
We compared multiple regression, Xgboost, and SVM. Table I shows the errors of the steplength estimation using Xgboost, which had the highest accuracy.
Mixed improved accuracy by about 10% over that of the compared method. A p value less than 0.01 was considered statistically significant. In addition, all of our segmentation methods were more accurate than the compared method. We consider that the accuracy improved because the segmentation of the gait allowed us to extract features finely. In summary, the proposed method improved the accuracy of step-length estimation; thus, we expect that it can improve the performance of PDR.
more important when stepping sideways. with more complex behavior such as turning while walking and
Let us describe the correspondence between the important features determined in the previous section and movements. Among the segmented features, the interval from the minimum value to the maximum value is found to be particularly important for method A. This indicates that the period from the start of kicking to the time when the foot overtakes the other foot is important. Similarly, the other segmentation patterns show that the features after the foot takes of are important.
The result of our method of the step length estimation can adapt to PDR. Fig 11 shows the estimated trajectory of the conventional PDR, PDR adapted to our method (Our PDR), both ankles estimated by human behavior recognition technology. The algorithm of the conventional PDR is adapted to the method proposed by Yoshimi et al. [30]. Our PDR is estimated by result of their heading estimation and proposed our step length estimation.
m m
m m m m (a) Conventional PDR (fixed step (b) PDR adapted to our method (c) Correct trajectory of both length) ankles
PDR estimates the walking distance and heading when it updates the present position. In this study, we improved the accuracy of the step-length estimation for updating the walking distance. However, recognizing the step section correctly needs a highly accurate step detection. Moreover, we have to deal with various carrying positions of the measuring device and nonstraightforward motions, for example, walking while turning and complex behaviors such as stepping sideways.
Step-section recognition will not work unless the steps are detected correctly. In our method, it worked well because the data were collected while the person was walking. However, if steps are misdetected, e.g., when the user stops at a location, the step-section recognition will fail.
In this study, we focused on walking in a straight line. However, in the real world, a pedestrian’s direction of motion will vary. Therefore, it will be necessary to analyze the angular velocity. In addition, there is a possibility that the acceleration data may have diferent characteristics from that of straight-line motion. Therefore, we will have to examine if we can apply our method to changes in heading.
Besides changing heading often, people in the real world walk irregularly, such as by stepping sideways. Such irregularities in walking have not been well studied, and our method does not address with this problem. To do so, it will be necessary to distinguish irregular walking behavior from normal walking behavior.
We evaluated the accuracy of the step-length estimation in a circumstance where the subject had a smartphone in his chest pocket. However, people carry smart phones in various locations, such as in hand bags, so it is necessary to deal with such situations. It is possible to obtain similar the norm of the acceleration vectors even if the carrying positions are diferent as long as the smartphone is approximately fixed relative to the motion of the user, thereby making it possible to segment the gait. However, this is dificult to do when the hand carrying the phone is swinging because the norm of the acceleration vectors will not reflect the gait characteristics. It will be necessary to recognize such situations and deal with them.
We improved the accuracy of the step-length estimation by extracting features from segments of steps. We referred to the characteristics of the motion and periodicity of gaits for clues on how to divide up a step. We used human behavior recognition technology to map acceleration data to walking motion and create labels for the step length. The method we developed could extract features in units finer than a step. In particular, it improved accuracy by 10% over the conventional step-length estimation when Xgboost was used as the machine learning method. The features that were useful were understandable. In particular, the x-axis acceleration from when the foot takes of to when the foot swings and overtakes the other foot had a significant influence. In the future, we will have to deal with heading estimation and non-straightforward motion. [4] M. Radhakrishnan, S. Eswaran, A. Misra, D. Chander, K. Dasgupta, Iris: Tapping wearable sensing to capture in-store retail insights on shoppers, in: 2016 IEEE International Conference on Pervasive Computing and Communications (PerCom), 2016, pp. 1–8. doi:10.1109/PERCOM.2016.7456526. [5] S. Krishnan, R. Xenia Mendoza Santos, E. Ranier Yap, M. Thu Zin, Improving uwb based indoor positioning in industrial environments through machine learning, in: 2018 15th International Conference on Control, Automation, Robotics and Vision (ICARCV), 2018, pp. 1484–1488. doi:10.1109/ICARCV.2018.8581305. [6] P. K. Enge, The global positioning system: Signals, measurements, and performance, International Journal of Wireless Information Networks 1 (1994) 83–105. URL: https: //doi.org/10.1007/BF02106512. doi:10.1007/BF02106512. [7] Y. Zhuang, N. El-Sheimy, Tightly-coupled integration of wifi and mems sensors on handheld devices for indoor pedestrian navigation, IEEE Sensors Journal 16 (2016) 224– 234. doi:10.1109/JSEN.2015.2477444. [8] L.-H. Chen, E. H.-K. Wu, M.-H. Jin, G.-H. Chen, Intelligent fusion of wi-fi and inertial sensor-based positioning systems for indoor pedestrian navigation, IEEE Sensors Journal 14 (2014) 4034–4042. doi:10.1109/JSEN.2014.2330573. [9] S. N. A. Ahmed, Y. Zeng, Uwb positioning accuracy and enhancements, in: TENCON 2017 - 2017 IEEE Region 10 Conference, 2017, pp. 634–638. doi:10.1109/TENCON.2017. 8227939. [10] A. Alarifi, A. Al-Salman, M. Alsaleh, A. Alnafessah, S. Al-Hadhrami, M. Al-Ammar, H. Al-Khalifa, Ultra wideband indoor positioning technologies: Analysis and recent advances, Sensors 16 (2016) 707. URL: http://dx.doi.org/10.3390/s16050707. doi:10.3390/ s16050707. [11] Y.-C. Pu, P.-C. You, Indoor positioning system based on ble location fingerprinting with classification approach, Applied Mathematical Modelling 62 (2018) 654–663. URL: https:// www.sciencedirect.com/science/article/pii/S0307904X18302841. doi:https://doi.org/ 10.1016/j.apm.2018.06.031. [12] K. Huang, K. He, X. Du, A hybrid method to improve the ble-based indoor positioning in a dense bluetooth environment, Sensors 19 (2019) 424. URL: http://dx.doi.org/10.3390/ s19020424. doi:10.3390/s19020424. [13] R. Chen, L. Pei, Y. Chen, A smart phone based pdr solution for indoor navigation, in: Proceedings of the 24th international technical meeting of the satellite division of the institute of navigation (ION GNSS 2011), 2011, pp. 1404–1408. [14] S. Beauregard, Widyawan, M. Klepal, Indoor pdr performance enhancement using minimal map information and particle filters, in: 2008 IEEE/ION Position, Location and Navigation Symposium, 2008, pp. 141–147. doi:10.1109/PLANS.2008.4570050. [15] X. Wang, M. Jiang, Z. Guo, N. Hu, Z. Sun, J. Liu, An indoor positioning method for smartphones using landmarks and pdr, Sensors 16 (2016) 2135. URL: http://dx.doi.org/10. 3390/s16122135. doi:10.3390/s16122135. [16] I. Klein, Y. Solaz, G. Ohayon, Pedestrian dead reckoning with smartphone mode recognition,
IEEE Sensors Journal 18 (2018) 7577–7584. doi:10.1109/JSEN.2018.2861395. [17] O. Asraf, F. Shama, I. Klein, Pdrnet: A deep-learning pedestrian dead reckoning framework,
IEEE Sensors Journal 22 (2022) 4932–4939. doi:10.1109/JSEN.2021.3066840. [18] S. Herath, H. Yan, Y. Furukawa, Ronin: Robust neural inertial navigation in the wild: Benchmark, evaluations, amp; new methods, in: 2020 IEEE International Conference on Robotics and Automation (ICRA), 2020, pp. 3146–3152. doi:10.1109/ICRA40945.2020. 9196860. [19] C. Chen, X. Lu, A. Markham, N. Trigoni, Ionet: Learning to cure the curse of drift in inertial odometry, Proceedings of the AAAI Conference on Artificial Intelligence 32 (2018).
URL: https://ojs.aaai.org/index.php/AAAI/article/view/12102. [20] M. Jacquelin Perry, Gait analysis: normal and pathological function, New Jersey: SLACK (2010). [21] I. Klein, O. Asraf, Stepnet—deep learning approaches for step length estimation, IEEE
Access 8 (2020) 85706–85713. doi:10.1109/ACCESS.2020.2993534. [22] R. Soni, S. Trapasiya, A survey of step length estimation models based on inertial sensors for indoor navigation systems, International Journal of Communication Systems 35 (2022) e5053. [23] H. Xing, J. Li, B. Hou, Y. Zhang, M. Guo, Pedestrian stride length estimation from imu measurements and ann based algorithm, Journal of Sensors 2017 (2017). [24] F. Gu, K. Khoshelham, C. Yu, J. Shang, Accurate step length estimation for pedestrian dead reckoning localization using stacked autoencoders, IEEE Transactions on Instrumentation and Measurement 68 (2019) 2705–2713. doi:10.1109/TIM.2018.2871808. [25] J. W. Kim, H. J. Jang, D.-H. Hwang, C. Park, A step, stride and heading determination for the pedestrian navigation system, Journal of Global Positioning Systems 3 (2004) 273–279. [26] H. Weinberg, Using the adxl202 in pedometer and personal navigation applications (2002). [27] J. Kang, J. Lee, D.-S. Eom, Smartphone-based traveled distance estimation using individual walking patterns for indoor localization, Sensors 18 (2018) 3149. URL: http://dx.doi.org/10. 3390/s18093149. doi:10.3390/s18093149. [28] T. Feigl, S. Kram, P. Woller, R. H. Siddiqui, M. Philippsen, C. Mutschler, Rnn-aided human velocity estimation from a single imu, Sensors 20 (2020) 3656. URL: http://dx.doi.org/10. 3390/s20133656. doi:10.3390/s20133656. [29] S. Vandermeeren, H. Bruneel, H. Steendam, Feature selection for machine learning based step length estimation algorithms, Sensors 20 (2020) 778. URL: http://dx.doi.org/10.3390/ s20030778. doi:10.3390/s20030778. [30] S. Yoshimi, K. Kanagu, M. Mochizuki, K. Murao, N. Nishio, Pdr trajectory estimation using pedestrian-space constraints: Real world evaluations, in: Adjunct Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2015 ACM International Symposium on Wearable Computers, 2015, pp. 1499–1508.