2014 International Conference on Indoor Positioning and Indoor Navigation, 27th -30th October 2014 Robust pedestrian dead reckoning (R-PDR) for arbitrary mobile device placement Zhuoling Xiao, Hongkai Wen, Andrew Markham, and Niki Trigoni Department of Computer Science, University of Oxford. Email: [email protected] Abstract—Pedestrian dead reckoning, especially on smartphones, is likely to play an increasingly important role in indoor tracking and navigation, due to its low cost and ability to work without any additional infrastructure. A challenge however, is that positioning, both in terms of step detection and heading estimation, must be accurate and reliable, even when the use of the device is so varied in terms of placement (e.g. handheld or in a pocket) or orientation (e.g holding the device in either portrait or landscape mode). Furthermore, the placement can vary over time as a user performs different tasks, such as making a call or carrying the device in a bag. A second challenge is to be able to distinguish between a true step and other periodic motion such as swinging an arm or tapping when the placement and orientation of the device is unknown. If this is not done correctly, then the PDR system typically overestimates the number of steps taken, leading to a significant long term error. We present a fresh approach, robust PDR (R-PDR), based on exploiting how bipedal motion impacts acquired sensor waveforms. Rather than attempting to recognize different placements through sensor data, we instead simply determine whether the motion of one or both legs impact the measurements. In addition, we formulate a set of techniques to accurately estimate the device orientation, which allows us to very accurately (typically over 99%) reject false positives. We demonstrate that regardless of device placement, we are able to detect the number of steps taken with >99.4% accuracy. R-PDR thus addresses the two main limitations facing existing PDR techniques. Keywords—Indoor positioning, inertial tracking, dead reckoning, heading tracking. I. I NTRODUCTION Pedestrian Dead Reckoning (PDR) is widely viewed as being a promising technique for enabling indoor positioning and navigation with low power and cost, and without requiring any infrastructure. Accurate and robust indoor localization is critical to bring location-based and location-aware services into widespread use. This is of ever growing importance as emerging device classes like smartwatches and glasses enter the wearable ecosystem and more and more applications require the use of accurate positioning. Pedestrian dead reckoning is conceptually a simple technique - a user’s displacement from a starting point is given by the number of steps they have taken and what direction each step was taken in. Typically, this is achieved with the aid of an IMU, consisting of an accelerometer (linear acceleration), gyroscope (rotational acceleration) and a magnetometer (to determine the heading relative to magnetic North). This is in contrast with inertial based techniques which double integrate the raw sensor values to estimate a platform’s displacement between sampling time instants, leading to rapid accumulation of errors, resulting in excessive drift after short time periods. PDR works particularly well when the sensor is rigidly attached to a person (i.e. a strapdown sensor) and mounted on the foot, and have helped to demonstrate its potential. However, for mobile devices (such as smartphones), the requirement for rigid attachment and specified placement are incompatible with the way in which people use devices. For example, over a period of a few hours, a smartphone could be carried in a backpack and then shifted to a pocket, before being taken out and being used to send a text message. Each of these activities are independent of whether or not the user is walking. The PDR system must operate correctly and consistently in all these scenarios. The challenge of accurately estimating steps and heading without knowledge of the device placement on the user is extremely challenging and a major hurdle that is preventing widespread adoption of PDR on consumer technology. For the first component of PDR, step detection, an error of even 2% over a long trajectory (e.g. 20 steps error in 1000 steps taken) can place the user in an incorrect room, leading to the potential failure of context aware services. This is because errors accumulate over a long trajectory, leading to increased uncertainty over time. Ever more sophisticated algorithms have been proposed to perform the task of motion or activity recognition, with the idea that if the placement can be inferred, then a case-specific step detection algorithm can be executed. One major issue that we have noticed with existing step detection techniques is that they are particularly poor at distinguishing between rhythmic signals caused by walking and signals caused by behaviours with strong periodic components like typing, tapping a finger, nodding one’s head and tapping a foot. For a PDR technique to be widely adopted, it must be able to reject these false positives or else the estimated position of the user rapidly deviates from the true position. The second component of a pedestrian dead reckoning system is being able to accurately determine the heading (forward direction of the user). Typically, this is achieved when the user is stationary i.e. at the zero velocity point. This is especially challenging if the device orientation is not known, as a translation from sensor to body frame coordinates needs to be made. Moreover, if the user changes the orientation of the device e.g. rotating it in their hand from portrait to landscape mode, tracking can fail for existing techniques. We propose a fresh approach to PDR that takes a step back from existing approaches and instead looks at the fundamentals of human bipedal motion and how this would be registered at various points of the human body. Based on this, we show that human motion as detected by an arbitrarily placed device falls into two categories, namely symmetric motion and asymmetric 2014 International Conference on Indoor Positioning and Indoor Navigation, 27th -30th October 2014 Fig. 1. System architecture. motion. Symmetric motion accounts for placements where both footfalls are detected, e.g. if a user is making a call and walking at the same time. Asymmetric motion, on the other hand, captures the case when the dominant motion component is registered on one side of the body only, e.g. if a user is walking with the phone in their hand. This simple binary decision allows us to build a very robust step detection system that does not need a complex, case-specific motion mode recognition algorithm. Similarly to address the issue of determining the heading of the user when the orientation of the device is unknown, we again turn to basic principles and attempt to determine the principal swing axis of the user, rather than the heading of the phone. We present a new technique for dead reckoning, Robust-PDR (R-PDR). In particular, the following are specific contributions of this paper: • Robust PDR with arbitrary device placement: By carefully examining every block of a PDR system, we develop techniques that attain extremely high step detection accuracy (>99.4%), regardless of where the device is sited. • Rejection of false steps: We demonstrate excellent rejection of non-walking human motion, again regardless of device placement. • Extensive real-world experiments: we show how we can greatly increase the accuracy of PDR systems by combining these suite of techniques in extensive real world tests with unconstrained placement. The remainder of this paper is organized as follows: Sec. II outlines the system architecture of R-PDR, motivating the need for each component. We first discuss how to accurately estimate device orientation in Sec. III, key to accurate step detection. Sec. IV presents the first component of the dead reckoning system that accurately counts the number of steps taken, regardless of device placement, whereas Sec. V illustrates how heading of the user can be accurately estimated by examining the principal swing axis of the device. Sec. VI extensively evaluates the proposed algorithm in a variety of techniques and compares it with competing techniques. Sec. VII contrasts our proposed work with existing techniques and lastly Sec. VIII summarises the contributions of the paper. II. S YSTEM A RCHITECTURE The block diagram of the system architecture is shown in Fig. 1. In this work, we focus on building robust and lightweight techniques for accurate pedestrian dead reckoning. Like many PDR systems, it comprises three main components: a fusion algorithm to convert raw sensor readings to estimates of device motion; a step detector; and a heading estimator. However, unlike existing PDR systems, it is intended for use in arbitrary device placement and orientation. Each component has thus been specifically tailored towards these challenges, exploiting fundamental characteristics of human motion. In addition, we have aimed to produce a lightweight system that is applicable to multiple settings (smartphone, smartwatch etc.) without requiring retuning or calibration. The core components are discussed in detail below. A. Inertial Fusion This comprises two main blocks, a standard Kalman Filter to combine data from the 3 classes of motion sensors, and an orientation correction algorithm (RIOT) that constrains long term orientation drift (especially in the pitch and roll axes) which arises as a result of bias in gyroscope measurements. This is made especially challenging as the device placement can be arbitrary and dynamically changed. By using short term estimates of relative rotation, estimates of gravity can be made invariant to the rotation of the device over time. B. Step detector Candidate Step Detection: Whereas existing work has typically built more and more elaborate models to recognize different classes of motion , , we instead take a simpler, more robust view, based on fundamentals of bipedal motion and how it couples to different device placements. The periodicity detector assesses whether the sensed motion of the user is symmetric or asymmetric. Informally, the symmetric motion modes correspond to the class of device placements that are impacted in a similar manner by both the right and left leg (e.g. making a call whilst walking), whereas asymmetric motion corresponds to placements where the movement of only one leg impacts device motion (e.g. holding the device in a hand and walking). In general, we find that symmetric motion corresponds to strong periodicity in the acceleration domain, whereas asymmetric motion corresponds to strong periodicity in the orientation domain. The step detector determines 2014 International Conference on Indoor Positioning and Indoor Navigation, 27th -30th October 2014 whether it is possible that a step has been taken, using an enhanced zero crossing detector. It must be noted at this point that the steps are treated as being candidates only, as it is possible that another motion (like shaking or tapping) would correspond to a similar looking acceleration pattern. Repetitive Pattern Update (REPUT): By exploiting constraints imposed on human steps, long term orientation drift, especially in the horizontal plane, can be greatly reduced. This novel algorithm attempts to correct the orientation bias introduced by the gyroscope. Step Validation: Given potential step events, this block verifies whether a step really was taken, key to the accuracy of our PDR system. It does this by estimating the displacement made in both the horizontal and vertical directions by double integrating the acceleration readings. C. Heading Estimation Using detected steps, the last task is to accurately determine the direction of travel of the user. In the majority of existing work, the heading is assumed to be parallel to one of the axes of the device. However, even with simple, arbitrary placements like texting, the heading of the device is not necessarily the same as the heading of the user. To tackle this problem, we project the displacement vectors of the step onto a two dimensional plane and determine the principal axis of travel. D. Positioning In this final block, a mapping application is used to turn dead reckoned steps and heading into user trajectories. We use an existing state-of-the-art map matching algorithm, MapCraft , which uses conditional random fields to constrain trajectories, to estimate positions. However, any technique such as particle filters or extended Kalman filtering can be used to determine position. III. ROTATIONALLY I NVARIANT O RIENTATION T RACKER (RIOT) Being able to accurately track the device’s orientation is the foundation for accurate long term inertial tracking. This is because most PDR subtasks, such as step detection and user heading estimation, are based on knowing the orientation of the device. However, determining device orientation remains a major issue for inertial tracking with unconstrained devices, especially with low-cost IMU sensors ubiquitous in mobile devices and wearable sensors. Generally, the gyro drift (and to a lesser degree, magnetic distortions from the environment) is the major obstacle for accurate orientation tracking. Most existing work uses Kalman filters to track device orientation, with measurements of the Earth’s magnetic field to correct the long term drift of the yaw angle. However, the gyro drifts in roll and pitch angles remain an issue. We argue that this problem can be addressed by accurately estimating the gravitational acceleration from the raw accelerometer signal, and using the gravity vector as an observation in the Kalman filter to correct drift in both roll and pitch. Currently there are two dominant approaches to estimating the gravity component of accelerometer measurements. The first approach, proposed by Mizell et al. , calculates the mean over a fixed length window to remove dynamic acceleration and estimate gravity as the static component. This approach is elegant and simple but is not suitable for mobile devices used by pedestrians. The major reason is that a change in orientation introduces a considerable lag in accurate gravity estimation. To reduce the lag, more recent work  reduces the length of the window, with a consequent decrease in accuracy. The second approach, recently proposed by Hemminki et. al , places additional constraints over allowable sampling instants for gravity estimation. Specifically, this approach estimates the direction of the gravitational vector only when the variation of the acceleration signals over a window is below a certain threshold. This reduces the lag introduced by the first approach, but also suffers from two fundamental limitations. First, this approach does not always lead to enough samples for estimating the gravitational vector, as it only works when the mobile device is static for a period of time. It typically does not work if the user is walking, when accurate estimates of the gravity vector are mostly needed. Secondly, the thresholds of variation in different motion modes are different, making it impractical in real-world settings, as significant tuning is required. To address these limitations, we propose a novel algorithm that can accurately estimate the gravity vector without lag and operates continually. The key property that it exploits is that gyro sensors have low drift and high reliability over a short time window, and thus can provide accurate measurements of relative changes in orientation. Assume we want to estimate the gravity vector at time t given a window of historical accelerometer data at−T :t of size T . We first rotate acceleration signals at−T :t−1 to the same orientation as at , and then estimate the gravity at time t as the mean of the acceleration readings after the rotation. In this way, we address the limitation of the first approach in needing a long window for accurate measurements of device orientation and avoids the constraint of the second in needing the device to be stationary for a length of time. Specifically, the gravity at time t is estimated as gt = Rt t X RTτ aτ , T (1) τ =t−T where aτ is the acceleration vector in the coordinate frame of the device, and Rτ is the rotation matrix describing the rotation from the earth coordinate system to the coordinate system of the device at time τ , as obtained from the Kalman Filter. This value is then used to compensate the Kalman Filter, by supplying an accurate observation of the gravity, thus removing the effects of long term gyro drift. Typically, we find that a window length of 4 seconds leads to good results. Experiments have been conducted to compare the proposed algorithm with the state-of-the-art gravity estimation techniques. In the experiment the pedestrian walks normally with the mobile device carried in their hand. The gravity vector is estimated using the proposed and competing approaches and then rotated to the earth’s coordinate system according to the current orientation of the device. The gravity value, as shown in Fig. 2, is then estimated as the acceleration in the Z axis (vertical axis). If the orientation algorithm is working correctly, the gravity vector should only have a component in the vertical axis, and this value should be equal to the true value of gravity. It is observed that Mizell’s approach has the largest errors due to its inability to manage changes in orientation of the device. Meanwhile, Samuli’s approach provides very Acceleration (m/s2) −6 −8 Acceleration (m/s2) −4 15 Acceleration (m/s2) 2014 International Conference on Indoor Positioning and Indoor Navigation, 27th -30th October 2014 15 −10 −12 −14 −16 10 15 20 Time (s) Acceleration Gravity Mizell et. al Samuli et. al R−PDR 25 30 Fig. 2. The acceleration due to gravity estimated along the Z axis using different techniques. sparse and sometimes inaccurate gravity estimates, because in most cases the motion of the pedestrian makes the variation in acceleration bigger than the threshold. In comparison, the proposed approach offers accurate gravity estimates and works continually. Both the proposed approach and Mizell’s approach use a window length of 4 s. Fig. 3 shows the long term estimate of gravity with and without the proposed orientation tracking algorithm in the Z axis. Again, we would expect a good technique to maintain the estimate of the gravity component at a constant -9.81m/s2 , regardless of the orientation of the device or dynamic acceleration changes due to motion. As expected, the drift of device orientation grows quickly without the proposed approach, leading to the gravity value drifting away from the actual. This drift can result in inaccuracy in counting number of steps, as will be explained in Sec. IV. However, the drift has been successfully corrected by the proposed orientation tracking approach, which has always kept the estimated gravity value very close to its true value. IV. S TEP D ETECTION In this section, we discuss our novel techniques for robust step detection. Key is to detect true steps accurately, whilst disregarding motion signatures such as shaking or tapping that could be mistaken for steps. Whereas existing work has typically built more and more elaborate models to recognize different classes of motion , , we instead take a simpler, more robust view, based on fundamentals of bipedal motion and how it couples to different device placements. The step detection component comprises three core blocks. The first block examines the pitch and vertical acceleration waveforms to determine whether a candidate step has been taken, based on periodicity. The second block further refines estimates of acceleration in the horizontal plane (forward direction), based on repetitive features common to multiple steps. The third and final block validates whether or not a step was really taken, by examining the overall displacement of the device over the duration of the step interval. A. Candidate Step Extractor The first block in the step detector extracts any potential candidate steps from the motion measurements. An approach 10 5 Acceleration Gravity Estimated gravity 100 300 400 Time (s) 10 5 0 200 500 600 Fig. 3. The resulting acceleration signal in the Z axis without (top) and with (bottom) the rotationally invariant orientation tracker. for detecting steps from unconstrained device placement is to build a classifier that recognizes where on the body the device is placed , . We take a fresh stance, based on fundamentals of bipedal motion and resultant sensor coupling for arbitrarily placed devices. Walking motion consists of two phases, the stance phase (when the foot is in contact with the ground) and the swing phase (when the foot is moving forward in an arc), which each leg undertakes in a rhythmic, offset pattern. When walking, the arms also typically swing back and forth. The motion of the legs and arms couples through the body, and depending on where the sensor is placed, it will either pick up equal and symmetric forces from both sides of the body, or asymmetric forces from only one half of the body, with the other side of the body weakly coupling to the sensor. An example of symmetric motion would be making a call whilst walking, as the smartphone would be held relatively rigidly against the head and thus would be impacted by the movements of both legs equally. Conversely, holding the device in one’s hand and swinging the arms would lead to strongly asymmetric waveforms. We argue that by exploiting these basic observations, the task of classification devolves to a simple binary decision, rather than the need for a classifier with multiple categories. This approach has the benefit of being inclusive in that no motion mode is left out. Examples of typical symmetrical motion modes include: • Texting: The mobile device is held in front of the user while walking; • Phoning: The mobile device is held close to the head while walking; • Heavy handbag: The mobile device is put in a heavy bag (so the hand of the pedestrian is not swinging) while walking; • Shirt pocket: The mobile device is put in a shirt pocket while walking; • Static: The mobile device is not moving, regardless of placement. Similarly, some typical asymmetrical motion modes include: • Hand Swinging: The mobile device is held in a swinging hand while walking; 2014 International Conference on Indoor Positioning and Indoor Navigation, 27th -30th October 2014 Phoning Swinging Trousers pocket Back pocket Orientation Vertical Pitch Acceleration Texting Symmetrical Fig. 4. Asymmetrical Acceleration and orientation signals of some typical symmetric and asymmetric motion modes. • Trouser pocket: The mobile device is put in a trouser pocket (front or back) while walking; • Belt mounted: The mobile device is fastened to the belt while walking; • Handshaking: The mobile device is (possibly periodically) shaken or tapped while not moving. To determine whether a device placement is leading to symmetric or asymmetric coupling, we examine both the vertical acceleration and the pitch (rotation around the y axis) component of the device orientation. This is the main reason that long term tracking of the orientation of the device is so important and why the RIOT technique introduced in Sec. III is crucial to accurate classification. Based on extensive experimental evidence, we make the novel observation that symmetric motion modes lead to strong periodicity in the vertical acceleration, closely approximating a sinusoidal wave, whereas the pitch waveform is aperiodic. On the other hand, asymmetric motion leads to aperiodicity in vertical acceleration, but strong periodicity in pitch angle. This is shown graphically in Fig. 4, illustrating a few examples of symmetrical and asymmetrical motion modes. Notice that all symmetrical motion modes have similar periodic vertical acceleration signals, with a period corresponding to a single step, while all asymmetrical motion modes have similar periodic pitch patterns, with a period corresponding to a stride. Thus, our classifier is based on assessing which one of the vertical acceleration or pitch waveforms has the strongest periodic component. More precisely, we compute the DFT of each signal (pitch and acceleration) over the frequency range that corresponds to human walking, typically between 1.2 Hz and 2.5 Hz. We then use an energy detector to decide whether the device placement is resulting in symmetric (vertical acceleration has stronger periodicity than pitch) or asymmetric (pitch has stronger periodicity than vertical acceleration). Based on this decision, the waveform with stronger periodicity is fed as input to an enhanced zero crossing detector that has hysteresis to reject low amplitude noise. Note that if the pitch waveform is used as input, each period of the waveform actually corresponds to a stride of the user. Each step thus is a half cycle of the periodic waveform. The candidate steps are then passed to the next block, REPUT, described in detail below. B. REpetitive Pattern Update (REPUT) Although the rotationally invariant orientation tracking algorithm described in Sec. III can achieve long term orientation tracking of the device, it is not sufficient to accurately estimate acceleration on the horizontal plane, which is important for step validation. The major reason is that a very small tilt of the device which cannot be corrected by the robust orientation tracking with the noisy measurements from low-cost IMU sensors, can significantly impact the acceleration signal on the horizontal plane. For instance, a tilt error of only two degrees changes the acceleration reading in the vertical axis from 9.806 m/s2 to 9.801 m/s2 , but it can offset the measured acceleration on the horizontal plane (either X or Y) by 0.342 m/s2 . To determine whether a step is valid or not (described in detail below in Sec. IV-C), the raw acceleration measurements are integrated twice to calculate the displacement of the step. Any orientation offset is significantly amplified through double integration which results in significant errors in displacement estimation. The example two degree tilt error described above can result in a cumulative displacement error of up to 20 metres within 10 seconds. To address this problem, we have further explored the physical constraints imposed by human walking. It is demonstrated in  that humans have surprisingly consistent walking patterns for consecutive steps. Inspired by this phenomenon, we present an algorithm to estimate and correct the orientation error using the repetitiveness in walking patterns, called repetitive pattern update (REPUT). Specifically, we assume that the extrinsic states of the mobile device (velocity, height, etc.) are largely the same after each step (or every stride in the case of asymmetric motion). If we assume that the bias in the orientation drifts slowly and remains constant over the duration of the step, our task is to find the inverse rotation matrix R that will compensate the offset, subject to the imposed constraints. Consider the case of maintaining the velocity of the device as a state that remains constant over a step. Suppose one step starts at time t0 with velocity v 0 and ends at time te with velocity v e . If there is no orientation bias, the difference between the initial and terminal velocities should be zero i.e. ∆v = v e − v 0 = 0. We can formulate the relation between the initial and 2014 International Conference on Indoor Positioning and Indoor Navigation, 27th -30th October 2014 Acc (<50%) Acc (>50%) Heading Before REPUT1 2 After REPUT 0.5 1 1 0 0 0 −0.5 −1 −1 −1 8.5 −1.5 9 9.5 X: Time (s) 9 9.5 Y: Time (s) −2 2 0 −2 0.5 0 −0.5 −2 8.5 0 Mean (Before) 2 Mean (After) Y (m/s2) Acceleration (m/s2) 2 8.5 9 9.5 Z: Time (s) −2 −1 0 X (m/s2) 1 (a) The acceleration signals before and after REPUT (b) Heading estimation Fig. 5. Examples demonstrating (a) how the mean acceleration has drifted significantly from zero without the aid of REPUT and corrected to have mean value close to zeros after REPUT has been applied, and (b) how the heading estimation calculates the best fit line for the instantaneous acceleration in the horizontal plane. terminal velocities as ve = v0 + te X R · at · ∆t, (2) t=t0 in which R is the inverse rotation matrix that corrects the orientation drift, at = [axt , ayt , azt ] is the acceleration vector at time t in earth’s coordinate frame, and ∆t is the time interval between two consecutive acceleration readings. Then based on our REPUT assumption, we have ∆v = v e − v 0 = R te X ·at · ∆t = 0, (3) t=t0 which allows us to solve for the unknown rotation matrix. Other repetitive patterns which impose constraints on orientation drift can also be derived. For instance, if it is known that the device is only used in 2D positioning, then the mobile device has the same height above the ground at the beginning and end of a step. Obviously in 3D tracking this cannot be used without knowledge of the map as a user could be climbing stairs for example, leading to a height difference. This can be formulated as ! te t X X z at ∆τ ∆t = 0. (4) ∆l = R t=t0 where azt τ =t0 is the vertical acceleration along the Z axis. These multiple repetitive constraints can be used to find the optimal rotation matrix through least squares optimization. To test the effectiveness of the REPUT algorithm, we have conducted a simple experiment during which the pedestrian walks normally with device held in a hand. Fig. 5(a) shows the acceleration signals before and after applying the REPUT algorithm. We can observe that the acceleration signals along the X and Y axis are significantly biased without the REPUT algorithm, whereas the offset has been corrected with the REPUT algorithm. C. Step Validation The last block of the step detector algorithm is to determine whether a candidate step really corresponds to a true step or whether it could have been caused by some other motion which resembles the waveform of a step. Essentially, this block acts to remove false positives i.e. when a step has been detected but it is not a real step of the user. To determine whether a step is real or not, we again turn to basics of human motion. Simply, a true step by the user must result in a forward displacement within the range that corresponds to human step length. To determine the displacement, it is necessary to double integrate the raw acceleration measurements. This motivates the need for extremely accurate measurements of orientation, provided by the RIOT algorithm, and removal of orientation bias, provided by the REPUT algorithm. The cross correlation between the acceleration signal and the orientation signal is also identified as an effective feature to reject false positives because the acceleration and orientation signal tend to have a higher correlation while shaking the device than normal walking behaviour. Then the features including horizontal/vertical displacements and cross correlation value are then feed into a simple three nodes decision tree to determine whether the candidate step really corresponds to a true step. V. ACCURATE HEADING ESTIMATION In most existing work, the heading of the user is assumed to be parallel to one axis of the device because the device placement is assumed to be known or can be inferred from sensor data. However, even with a simple placement like texting, the heading of the device is not necessarily the same as the heading of the user and differs greatly for different users. With unconstrained placement of the device, the heading of the device can be very difficult to determine, and can dynamically change over time. However, since we have very accurate orientation measurements of the device through RIOT (see Sec. III) and REPUT (see Sec. IV-B), we can infer the heading of the user by determining the principal swing axis, which is aligned with the forward motion of the user. If we consider the horizontal components of the acceleration over a single step and project them into a two dimensional plane, the best fit line (using simple least squares regression) corresponds to the overall direction of forward motion. This leads to a 180◦ ambiguity where the sign of the heading angle is not known. This is easily addressed by considering the trajectory of the first half of the acceleration signals, corresponding to the forward swing. Typical examples of the heading estimation are shown in Fig. 5(b). Note that if the residual error is small (Fig. 5(b) top and middle) we use the resulting estimate as the offset between device and user heading; otherwise (Fig. 5(b) bottom), we use the most recent offset that was reliably estimated. 2014 International Conference on Indoor Positioning and Indoor Navigation, 27th -30th October 2014 VI. 10 E VALUATION In this section, we compare and contrast the performance of our approach with leading PDR approaches for step detection and counting. 8 Error (%) The competing approaches we compare against are: Peak detection (PD:) The toe-off and heel-strike events are usually associated with sharp changes in vertical or the magnitude of acceleration which are the targets for typical peak detection algorithms , , . However, each heel-strike could come with multiple peaks, especially when the mobile device is in a swinging hand or attached low, e.g. a trousers pocket, which significantly increases the algorithm complexity. We use a low pass filter followed by a peak detector. Zero-crossing (ZC): Another way of identifying the cyclic patterns in acceleration is the detection of zero crossings , , . This algorithm is simple to implement, but can suffer from false positive zeros crossings from events other than walking. Spectral analysis (STFT and CWT): This promising technique has attracted a large amount of attention recently due to its robustness , , , . Algorithms of this category first convert the acceleration signal to frequency domain using different algorithms like Fourier transform , , short time Fourier transform (STFT) , or continuous wavelet transform (CWT) , and then the dominant peak of the signal in frequency domain is identified as the step frequency. Windowed acceleration signal (magnitude) is common choice for people working with spectral analysis . As a result, online step detection makes this algorithm very computationally intensive. Auto/cross correlation (AC): Since each individual human has a surprisingly consistent walking pace , the strong periodicity of the acceleration signal from such walking behavior makes it possible to extract the cyclic pattern with mean-adjusted autocorrelation of the sensor data sequence or cross correlation with prepared templates – such as a sample sequence of sensor data from the training phase . ZEE, a recent approach that we use as comparison, can also exploit characteristic waveforms from different device placements . Hand Glass Watch Shirt Trousers Backpack 6 4 2 0 ZC PD STFT CWT Algorithms AC R−PDR Fig. 6. Comparison between state-of-the-art step detection algorithms and the proposed approach, R-PDR, in terms of step detection accuracy for various device positions. from an experiment where a mix of daily behaviours such as walking, standing, sitting, sending a text, making a call and typing were performed. This is in comparison to other work where a limited subset of behaviours (e.g. walking and standing still) are used to demonstrate step detection accuracy. The experiment lasted two hours and a total of 4669 true steps were counted by the two foot mounted IMUs. Fig. 6 shows the results for different algorithms and different placements. It is interesting to note that for the competing algorithms, they typically attain good performance for some placements, but for one or two placements the accuracy is particularly poor, in some cases as high as 10%. In particular, the handheld placement typically registers the highest errors as repetitive motion such as typing has strong periodicity like a true step. Out of the competing algorithms, the autocorrelation (AC) algorithm performs reasonably well across the placements, with a maximum error of 3%. The strength of our approach, R-PDR, is apparent from the results, as regardless of placement, errors are consistently below 1%. This experiment using realistic human behaviour demonstrates how existing techniques suffer from sensitivity to device placement, whereas our approach is able to correctly detect the correct number of steps. A. Experimental setup For all tests, ground truth of steps was obtained using foot mounted IMU’s (X-IO Technologies Inc.) which are accurately calibrated. Two IMU’s were used, one on each foot, to accurately count the number of steps. Ground truth of position was obtained by placing numbered labels along the route at 1-m evenly spaced intervals and using a down facing hand-held camera to note the exact time when the foot crossed the midpoint of the label. For each test, the user was outfitted with 2 IMU’s (one on each foot) and 6 Nexus-S smartphones capturing IMU data at various positions of the body. This allows us to perform direct comparisons of accuracy, as an accurate PDR system should report the same number of steps, regardless of device placement. B. Overall detection accuracy In this test, we examine the accuracy of overall step detection for various placements for each of the competing algorithms, compared to the ground truth. Data was obtained C. False positive rejection In this test, using data from a number of behaviours that are repetitive but do not correspond to forward displacement, we demonstrate the performance of existing algorithms in determining whether a step has actually been taken or not. This is shown in Fig. 7. Each behaviour, such as tapping, was performed 200 times. Existing algorithms which are based solely on characteristics of the waveform itself, such as periodicity, are unable to distinguish between behaviours like tapping and true steps caused by walking. This is because they are only designed to detect periodical patterns and do not consider whether a motion, as registered by the sensors, actually corresponds to true forward motion. This is made even more challenging for unconstrained device placement. The suite of techniques presented in R-PDR allows us to evaluate, for each step, the displacement of the user and assess whether or not a step has really been taken. This ability to distinguish between true and 2014 International Conference on Indoor Positioning and Indoor Navigation, 27th -30th October 2014 250 Ground truth Nodding Foot tapping R−PDR PHA 30 4 200 20 2 150 100 10 Y (m) Heading (rad) Number of steps detected Tapping 0 0 −10 −2 −20 50 −4 0 0 ZC PD STFT CWT Algorithms AC 50 100 Time (s) −30 0 20 X (m) 40 R−PDR Fig. 7. Comparison between state-of-the-art step detection algorithms and the proposed approach, R-PDR, in terms of step detection accuracy for various device positions. false steps makes our algorithm greatly outperform existing algorithms. D. Heading estimation Existing heading algorithms assume that the heading of the user is parallel with a sensor axis e.g. that the phone is carried in a hand facing forward, called parallel heading assumption (PHA). In this test, we demonstrate how this assumption can lead to large heading errors if the device is rotated even a small amount. The user carried the device facing forward. Halfway through the test, the device was rotated in the hand by 30◦ . The results are shown in Fig. 8. This demonstrates that the trajectory estimated with the existing technique diverges significantly from the ground truth when we slightly change the orientation of the device whilst orientation changes do not impact the proposed approach. This ability to accurately estimate heading, regardless of device orientation, is extremely important for long term positioning, as small errors in heading accumulate rapidly and lead to the failure of PDR. Note that the initial heading is estimated from magnetometer and thus biased due to the magnetic distortions in indoor environments. E. Impact on positioning systems Lastly, we examine how errors in the PDR couple through to the positioning system. We use MapCraft, a state of the art technique for converting noisy dead reckoned trajectories into accurate locations. MapCraft does not require an initial starting point or heading and tolerates large errors in dead reckoned data. Using this technique as a common benchmark, we assess how different PDR step and heading estimation techniques impact overall positioning error. This experiments were conducted in an office building shown in Fig. 10. During the experiments, the subjects were mounted with several devices simultaneously in different parts of the body, typically hand, watch, glasses, and trousers pocket. Then they walk anywhere in the building without planned routes, to realistically capture real pedestrian motion, rather than artificial, constant speed trajectories. They were told to move freely and may have different motion modes including walking, standing still, tapping, foot tapping, typing, sitting down, bending to pick up something on the floor, etc. To provide accurate ground truth, numbered labels were placed Fig. 8. Comparison of different heading estimation techniques. along corridors and within rooms on a 2 m grid. Using the device’s camera, these were filmed at the same time experiments were conducted. The time-synchronized video streams were then mapped to locations on the floorplan. Fig. 9 compares the step detection accuracy of R-PDR against autocorrelation which is reported to have the best overall detection accuracy in existing techniques. It is observed that R-PDR always outperforms autocorrelation for various human motions and placements of devices. The major reason lies in the fact that R-PDR could reject false positives while AC cannot. Motions like nodding, tapping, typing, and foot tapping can generate step-like signals without really moving forward. As a result, AC significantly over counts the number steps, which, inevitably leads to significant errors in tracking (the significant drift of trajectory in Fig. 10(e)), even with the state-of-the-art map matching algorithm (Fig. 10(c)). Fig. 10(f) shows the error distribution function of the R-PDR and the competing approaches. It is observed that R-PDR has a RMS error of 0.98m regardless of device placement. An example of the testing trajectory can be found in Fig. 10. VII. R ELATED W ORK A wide variety of algorithms have been developed to identify steps from inertial signals so far . Typical step detection algorithms have been developed to accurately identify specific events for data segmentation, for instance, peaks, zero crossing, etc. These algorithms are mostly applied to acceleration or angular velocity signal, or their combinations , . To handle unconstrained device placement, a number of techniques have been proposed, such as motion recognition which attempts to classify different motion patterns (such as hand swinging, texting, running, etc.) based on waveform features , . Rather than building a rich classifier, which requires significant training, we take a simpler approach and consider a novel observation based on the periodicity of orientation and acceleration signals. To the best of our knowledge, this is the first technique that considers both acceleration and orientation waveforms simultaneously. The most crucial underlying assumption that existing algorithms make is that people do not generate periodical acceleration signals while not walking, such as a hand swing without the user really moving forward. This is because the two actions (a step and a hand swing) can actually generate 2014 International Conference on Indoor Positioning and Indoor Navigation, 27th -30th October 2014 0 5 10 0 m (a) Ground truth (b) R-PDR + map matching 1 0.8 −20 −20 0.6 −30 −40 0.4 −60 −40 Fig. 10. CDF 0 X (m) −10 −50 m (c) AC + PHA + map matching 0 X (m) 5 10 0.2 −80 −20 −10 0 10 Y (m) 20 30 R−PDR + map matching AC + PHA + map matching MapCraft (handheld) −80 −60 −40 −20 Y (m) 0 20 0 0 (d) R-PDR (e) AC + PHA Experiments in the office environment, showing the ground truth and reconstructed trajectories. an identical acceleration signal patterns, especially when the step detection algorithms are applied to the magnitude of the acceleration . The situation would be exacerbated with less constrained motions like crawling, stumbles, side-steps, shuffles, etc. , which pose great challenge to motion recognition algorithms. We demonstrate that by accurately estimating the horizontal and vertical displacement of each step (which requires enhanced filtering to prevent drift), we can accurately determine whether a forward step has been taken. Orientation tracking/heading estimation, tackles the problem of continuously estimating the orientation of the mobile device, relative to North. Typical orientation tracking algorithms with inertial data are based on indirect Kalman filters  or variants of Kalman filters like extended Kalman filters (EKF)  or Unscented Kalman filters (UKF) . The standard way of tracking the orientation with Kalman filters is to update the orientation using the angular velocity from gyroscope and compensate for the long term drift of orientation tracking from noisy gyro data with the magnetic field from magnetometer or gravity vector from accelerometer. However, the majority of research on orientation tracking in the context of indoor positioning is to determine the heading of the pedestrian rather than the heading the device. Most research therefor assumes the position where the mobile device is attached is known, thereby making the assumption that the heading of the pedestrian is always consistent with the heading of the mobile device . This is not always true. Recent research investigating the difference between the user’s heading and the phone’s heading  demonstrated that the second harmonic of the acceleration is either completely absent or is extremely weak in the direction perpendicular to the user’s walk. It is conversely dominant in the direction parallel to the user’s walk. Moreover, the long term drift of orientation tracking is still a pressing problem. Though in existing work 10 20 Error (m) 30 (f) Comparison of tracking errors the magnetic field of the earth can mostly compensate long term yaw errors, it has little correction power in roll and pitch estimation. This is because the gravity vector can be used only when the device is static . VIII. C ONCLUSIONS Pedestrian dead reckoning is a technique that can act as the foundation of an accurate indoor positioning system by exploiting low cost, infrastructure free device sensors. Work to date has made great strides in demonstrating the potential of PDR, but subject to constraints on device placement. These constraints are limiting the widespread adoption of PDR. Rather than seeking a placement specific approach, or attempting to derive the placement of the device, we have taken an alternative approach in this work and presented a suite of techniques that together provide robust PDR (RPDR). Through extensive experiments using R-PDR, we have demonstrated that step detection and heading estimation are accurately performed even when the position of the device is changed dynamically through the test. In addition, we also showed how R-PDR is able to reject common behaviours like typing that appear like steps to competing PDR techniques. We believe that the techniques presented here will have wide applicability not only in consumer devices like smartphones but also in wearable devices like smartwatches and glasses. In summary, R-PDR is a comprehensive technique that will enable the adoption of accurate, reliable and robust indoor positioning, without requiring any calibration or tuning. Acknowledgements The authors would like to thank the anonymous reviewers for their comments and suggestions to improve the paper. They also acknowledge the support of the EPSRC through grants EP/L00416X/1. 2014 International Conference on Indoor Positioning and Indoor Navigation, 27th -30th October 2014 Hand     Glasses    Watch    Trousers      Fig. 9. Typical human motions and the corresponding step detection accuracy for R-PDR and AC.  R EFERENCES  M. Alzantot and M. Youssef. UPTIME: Ubiquitous pedestrian tracking using mobile phones. In Proc. IEEE Wirel. Commun. Netw. Conf. (WCNC’12), pages 3204–3209. Ieee, Apr. 2012.  S. Beauregard and H. Haas. Pedestrian dead reckoning: A basis for personal positioning. In Proc. 3rd Workshop Pos. Nav. Commun. (WPNC’06), pages 27–36, 2006.  A. Brajdic and R. Harle. Walk detection and step counting on unconstrained smartphones. In Proc. ACM Conf. Ubi. Comput. (UbiComp’13), pages 225–234, Zurich, Switzerland, 2013. ACM Press.    I. Bylemans, M. Weyn, and M. Klepal. Mobile Phone-Based Displacement Estimation for Opportunistic Localisation Systems. In Proc. 3rd Int. Conf. Mob. Ubi. Comput. Syst. Services Technol. (UbiComm’09), pages 113–118, Sliema, Oct. 2009. L. Fang, P. Antsaklis, L. Montestruque, M. B. McMickell, M. Lemmon, Y. Sun, and H. Fang. Design of a wireless assisted pedestrian dead reckoning system-the NavMote experience. IEEE Trans. Instrument. Measurement, 54(6):2342–2358, 2005. P. Goyal, V. J. Ribeiro, H. Saran, and A. Kumar. Strap-down Pedestrian      Dead-Reckoning system. In Proc. Int. Conf. Indoor Pos. Indoor Nav. (IPIN’11), pages 1–7. Ieee, Sept. 2011. T. Harada, T. Mori, and T. Sato. Development of a Tiny Orientation Estimation Device to Operate under Motion and Magnetic Disturbance. The Int. J. Robotics Res., 26(6):547–559, June 2007. R. Harle. A Survey of Indoor Inertial Positioning Systems for Pedestrians. IEEE Commun. Surveys & Tutorials, 15(3):1281–1293, Jan. 2013. S. Hemminki, P. Nurmi, and S. Tarkoma. Accelerometer-based transportation mode detection on smartphones. In Proc. 11th ACM Conf. Embedded Netw. Sensor Syst. (Sensys’13), pages 1–14, New York, NY, USA, 2013. B. Huyghe, J. Doutreloigne, and J. Vanfleteren. 3D orientation tracking based on unscented Kalman filtering of accelerometer and magnetometer data. In Proc. IEEE Sens. App. Symp. (SAS’09), pages 1–5, New Orleans, LA, USA, 2009. J. W. Kim, H. J. Jang, D. H. Hwang, and C. Park. A step, stride and heading determination for the pedestrian navigation system. Journal of Global Position. Syst., 3(1):273–279, 2004. F. Li, C. Zhao, G. Ding, J. Gong, C. Liu, and F. Zhao. A reliable and accurate indoor localization method using phone inertial sensors. In Proc. ACM Conf. Ubiquitous Comput. (UbiComp’12), pages 421–430, 2012. H. Lu, J. Yang, Z. Liu, N. D. Lane, T. Choudhury, and A. T. Campbell. The Jigsaw continuous sensing engine for mobile phone applications. In Proc. 8th ACM Conf. Embedded Netw. Sensor Syst. (SenSys’10), pages 71–84, New York, New York, USA, 2010. ACM Press. D. Mizell. Using gravity to estimate accelerometer orientation. In Proc. 7th IEEE Int. Symp. Wearable Computers (ISWC’03), pages 252–253. Ieee, 2003. J.-g. Park, A. Patel, D. Curtis, S. Teller, and J. Ledlie. Online pose classification and walking speed estimation using handheld devices. In Proc. ACM Conf. Ubi. Comput. (UbiComp’12), pages 1–10, New York, New York, USA, 2012. ACM Press. A. Rai and K. Chintalapudi. Zee: Zero-effort crowdsourcing for indoor localization. In Proc. 18th Ann. Int. Conf. Mob. Comput. Netw. (MobiCom’12), pages 1–12, Istanbul, Turkey, 2012. N. Ravi, N. Dandekar, P. Mysore, and M. Littman. Activity recognition from accelerometer data. In Proc. 7th Conf. Innov. App. Artificial Intell. (AAAI’05), pages 1541–1546, 2005. V. Renaudin, M. Susi, and G. Lachapelle. Step length estimation using handheld inertial sensors. Sensors, 12(7):8507–8525, Jan. 2012. J. Rose and J. G. Gamble. Human Walking. Lippincott, Williams and Wilkins, Baltimore, PA, USA, 3rd edition, 2006. S. H. Shin, M. S. Lee, and P. C. G. Pedestrian dead reckoning system with phone location awareness algorithm. In Proc. IEEE/ION Position Location Nav. Symp. (PLANS’10), pages 97–101, 2010. Y. S. Suh. Orientation Estimation Using a Quaternion-Based Indirect Kalman Filter With Adaptive Estimation of External Acceleration. IEEE Trans. Instrument. Measurement, 59(12):3296–3305, Dec. 2010. M. Susi, V. Renaudin, and G. Lachapelle. Motion mode recognition and step detection algorithms for mobile phone users. Sensors, 13(2):1539– 62, Jan. 2013. J. S. Wang, C. W. Lin, Y. T. Yang, and Y. J. Ho. Walking pattern classification and walking distance estimation algorithms using gait phase information. IEEE Trans. Biomedical Engineer., 59(10):2884– 2892, 2012. Z. Xiao, H. Wen, A. Markham, and N. Trigoni. Lightweight map matching for indoor localization using conditional random fields. In Proc. Int. Conf. Info. Process. Sensor Netw. (IPSN’14), Berlin, Germany, 2014. J. Yang. Toward physical activity diary: motion recognition using simple acceleration features with mobile phones. In Proc.1st Int. workshop Interactive multimedia for consumer electronics, pages 1–9, Beijing, China, 2009. H. Ying, C. Silex, and A. Schnitzer. Automatic step detection in the accelerometer signal. In Proc. 4th Int. Workshop Wearable and Implantable Body Sensor Netw. (BSN’07), pages 80–85, 2007. X. Yun and E. R. Bachmann. Design, Implementation, and Experimental Results of a Quaternion-Based Kalman Filter for Human Body Motion Tracking. IEEE Trans. Robotics, 22(6):1216–1227, Dec. 2006.
© Copyright 2017 ExploreDoc