1. INTRODUCTION
Navigating in GPS denied environments such as urban canyons and indoors using GPS technology is often very difficult (Lachapelle, Reference Lachapelle2004). This is due to the absence of direct line of sight to GPS satellites to acquire GPS signals. As a result, the quality of the received signal (if it can be received) deteriorates largely due to multipath or weakened signal power. Although High Sensitivity GPS (HSGPS) receivers can be used to detect weak signals, often the signal is not reliable enough to produce an accurate position solution. An example was demonstrated (Odijk and Kleijer, Reference Odijk and Kleijer2007, Reference Odijk and Kleijer2008) where the use of HSGPS produced corrupted solutions in an indoor environment due to weak and reflected signals.
Resorting to different types of navigation technology that do not use Radio Frequency (RF) signals is therefore a potential alternative. Inertial sensors satisfy this criterion because they do not receive or transmit any signals. Furthermore, the advent of low cost MEMS inertial sensors suits the requirement for low cost consumer applications such as pedestrian navigation. MEMS Inertial Measurement Units (IMU) normally consist of accelerometers and gyros that produce measurements (acceleration and attitude rate) in a body coordinate frame. Attitude parameters are then used to transform these measurements into a desired frame such as the navigation frame and from these, one can work out the position of the system. However, due to its low cost nature, it is prone to errors (Pang and Liu, Reference Pang and Liu2001; Godha, Reference Godha2006; Park and Gao, Reference Park and Gao2006) that eventually cause large position errors.
One idea to reduce the solution error is to strap the IMU on a user's foot or shoe to perform Zero Velocity Updates (ZUPT) (Jiemenez et al., Reference Jimenez, Prieto and Guevara2009; Skog et al., Reference Skog, Nilsson and Händel2010; Hide et al., Reference Hide, Botterill and Andreotti2009; Foxlin, Reference Foxlin2005). Due to the strap-down configuration, it has the advantage of measuring the foot's velocity directly. It is therefore valid to assume that during the stance phase (zero velocity) of a walking gait, the IMU should produce zero velocity measurements for the foot's velocity. In practise however, this is not entirely true because of the inherent errors of the inertial sensors. Therefore, the non-zero velocity measurement from the strapped-down IMU during this period is considered as an error, and can be subsequently corrected. For example, this can be performed by feeding back this error to a control system. Furthermore, if this measurement update is used in an estimation filter such as Kalman filter, it can not only be used to correct the user's walking velocity, but also help restrict the position and attitude errors, and estimate the sensor bias errors. This is because the Kalman filter uses an inertial error model that builds up information on the correlation between the states modelled such as position, velocity, attitude and sensor biases. A 15-state Kalman filter estimating position, velocity, attitude, gyro bias and accelerometer bias errors is used for the work in this paper as described in Abdulrahim et al. (Reference Abdulrahim, Hide, Moore and Hill2011).
Nonetheless, heading drift is still a major concern in low-cost-self-contained-IMU systems, even with the use of ZUPT measurements. Although frequent use of ZUPTs consistently bounds many IMU errors, optimal estimation of heading becomes a difficult process because there is no direct correlation between velocity and heading (Godha and Lachapelle, Reference Godha and Lachapelle2008). Therefore there is a need to have other measurement updates that have high correlation with heading angle to aid the estimation process.
In Abdulrahim et al. (Reference Abdulrahim, Hide, Moore and Hill2011), we presented an approach of using heading aiding using very basic information derived from maps or aerial images. This alleviates the need for detailed room-level maps of the inside of buildings which are typically unavailable, particularly for private buildings. The heading measurements are able to maintain accurate heading without the need for any additional sensors such as magnetometers. This paper describes the developed algorithm that constrains a walk in a typical building to only walking in cardinal headings. It is shown to consistently and effectively restrict heading drift for all test datasets, resulting in a significant improvement in an INS-only positioning.
This paper describes further developments to the indoor positioning algorithm. An additional measurement is applied to address the problem of heading drift when the user is stationary since the cardinal heading algorithm is only applicable when the user is moving. The measurement is termed Zero Integrated Heading Rate (ZIHR) (Shin, Reference Shin2005) where knowledge of previous and current heading rates are used to constrain the drift. To the authors’ knowledge, ZIHR has never been used before in pedestrian navigation to constrain heading drift during prolonged stop. Most of the results in the literature demonstrate walking without stopping in an extended period of time, which is slightly unusual for pedestrians. Another measurement is also introduced to restrict vertical position drift when the pedestrian is inside buildings.
Trials have taken place at the University of Nottingham using a low cost MEMS inertial sensor to show the effectiveness of combining the constraints. This paper demonstrates that using the constraints described, average position error is consistently kept below 5 meters while walking for an average distance of approximately 1·5 kilometres. To conclude, this paper presents an effective approach to restrict heading drift and vertical drift using constraints in a typical low cost indoor pedestrian navigation system. The improvement made in estimating heading error with the use of this approach will be analysed. It is envisaged that self-contained inertial navigation could be made possible in a longer duration, at least in typical indoor environments.
2. HEADING CONSTRAINT DURING WALKING
This section describes the algorithm developed (Abdulrahim et al., Reference Abdulrahim, Hide, Moore and Hill2010, Reference Abdulrahim, Hide, Moore and Hill2011) where a measurement is derived to constrain heading drift as a pedestrian walks around a building. The underlying idea is that when a pedestrian walks through a building, most of their motion is constrained to one of four principle (termed cardinal) directions. This is due to the simple construction of most buildings which are typically rectangular in shape and have the rooms and corridors aligned with the outer walls. The orientation of the building can be derived from maps or aerial images and a database can be constructed that can be used to aid navigation. For this work, it is helpful to highlight that building orientation will be consistent with the Course Over Ground (COG) direction that the user walks as opposed to heading or yaw which is the true orientation of the x-axis of the IMU with respect to North.
The algorithm makes two important assumptions. Firstly, it is assumed that the pedestrian will typically (but not always) walk in a direction that is consistent with the orientation of the outer walls of the building. Secondly, it is assumed that the difference between the COG (calculated from the difference in position of two steps) and the outer orientation of the building is the result of heading drift plus some uncertainty due to the pedestrian not walking in a straight line. This second assumption is only valid because there is a large acceleration caused by the foot moving through a step. Because there is a large acceleration, the heading error is observable through the position difference since heading is used to determine the orientation of the accelerometer axes. For other applications such as vehicle navigation, it is not possible to use this assumption since the vehicle may be travelling at constant velocity and therefore heading has no effect on position.
The algorithm can be described using Figure 1. The COG is computed using 
where dN and dE are the change in position in North and East axes respectively caused by a step being made between epochs k and k+1. To remove steps that are not consistent with the building orientation we introduce the condition,
where t COGmax is an empirically derived threshold that is used to exclude steps that are not consistent with the building such as when walking around corners or not walking straight along a corridor. The threshold has to be large enough to accommodate the heading drift of the IMU as well as small variations in COG that are caused by the pedestrian not walking exactly in straight lines.
A second condition is also used,
where d=[dN 2+dE 2]0·5 is the footstep length. This threshold is used to ensure that only steps of a typical stride length are used to compute COG. If both C 1 and C 2 return true (logical 1), then a measurement is added to the Kalman filter, otherwise, no update is sent to the Kalman filter.
Figure 1. Illustration of the heading measurement at each epoch.
The measurement used for the Kalman filter is the difference between the COG calculated from the change in position between steps and the orientation of the building. A measurement update is applied by forming the observation,
![$$\delta {\kern 1pt} \varphi = \left[ {\matrix{ {\displaystyle{{\delta {\kern 1pt} \varphi} \over {\delta {\kern 1pt} \phi _N}}} & {\displaystyle{{\delta {\kern 1pt} \varphi} \over {\delta {\kern 1pt} \phi _E}}} & {\displaystyle{{\delta {\kern 1pt} \varphi} \over {\delta {\kern 1pt} \phi _D}}} \cr}} \right]{\bi \phi} + n_k $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000518_eqn3.gif?pub-status=live){kind=small}
where n k is the measurement noise with covariance R k=E(n knkT) which is large enough to accommodate steps that are not consistent with the building (which is closely related to the value used for t COGmax); the partial derivatives are formed with respect to ϕ which is a vector of attitude errors in the navigation frame as modelled in the Kalman filter. See (Shin, Reference Shin2005) for details including derivation of the partial derivatives) and,
where, δ φ is the IMU heading error and φ building is the current ‘building’ orientation.
The heading measurement is tested by walking along a straight line (next to a straight road). Figure 2 shows the values for δ φ that are used in the Kalman filter. The values comprise the Inertial Navigation System (INS) heading error, other small INS drift, and also the variations of the user's step in relation to the true COG. A Microstrain 3DM-GX3 inertial sensor is used with the accelerometer bias stability quoted as ±0·01 g, and for the 300 degree/s model, the gyro biases are specified as ±0·2 degree/s. The particular IMU used has a limit of 1200 degree/s for angular rotation and 18 g for acceleration. The standard deviation of heading difference is only 1·54° while the maximum heading difference is 7·58° (which corresponds to the 10° threshold used).
Figure 2. Heading error for walking in a straight walk.
Figure 3 shows the position error after approximately 3 minutes of walking in a straight line. The blue line represents the position error using the heading algorithm while the black line represents position error without using the algorithm. Using the heading update, the final North position error is 1·25 m whereas the end position error is 49·77 m if the algorithm is not used. Further results in more realistic situations are described towards the end of this paper.
Figure 3. Position with and without heading update.
3. HEADING CONSTRAINT DURING STOP
In this paper, an approach proposed (Shin, Reference Shin2005) to constrain heading drift for a wheeled vehicle when it stops is adopted for our pedestrian navigation system. This is because during a stationary condition, roll and pitch errors can be constrained by applying ZUPTs, but not the heading error due to its poor observability. The algorithm is known as Zero Integrated Heading Rate (ZIHR) and it uses the knowledge of previous and current heading rate to stop the accumulation of heading drift error. The measurement equation is written as follows:
![$$\displaystyle{{\varphi _k - \varphi _{k - 1}} \over {\Delta t_k}} \approx \left[ {\matrix{ 0 & {{\rm sec}\;\theta \;{\rm sin}\,\phi} & {{\rm sec}\,\theta \;{\rm cos}\,\phi} \cr}} \right]{\bi b}_g + n_k $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000518_eqn5.gif?pub-status=live){kind=small}
where φ k is the INS heading; roll (ϕ) and pitch (θ) are considered as constants over the time interval Δt k; bg is the vector of body frame gyro biases; n k is the remaining noise term; and k is the epoch. Due to the term sec θ, ZIHR cannot be applied when pitch is close to ±90°. For this algorithm, the epochs k and k+1 correspond to times either side of a step.
Before the ZIHR measurement model can be used in the Kalman filter, we introduce two conditions that need to be satisfied. First, a zero velocity condition is checked to ensure that the system is stationary (i.e. the pedestrian has stopped walking). If this event returns true, a second check is performed by checking whether the foot is rotating or not. This is important to highlight a case when the pedestrian stops walking and rotates his foot at the same time. The conditions can be written as:
where Vk is the three dimensional velocity of the IMU and ωk is the three dimensional rotation determined by the gyros. The logical “1”s in equations (6) and (7) mark the detected stance phase (ZUPT event) and non-rotating foot respectively. If both C3 and C4 return true (logical 1), then the ZIHR measurement model is used to update attitude in the Kalman filter, otherwise, no update is sent to the Kalman filter. The threshold tωmax must be set to be larger than the expected total gyro bias and yet small enough to ensure the IMU is not physically rotating.
A static test is first conducted to illustrate the result of using the ZIHR measurement using the Microstrain 3DM-GX3 sensor used in the previous test. The IMU is put on a stationary table for 16 minutes and is initialised with a known position and attitude to represent a condition where pedestrian stops walking for a long period. A comparison is made between using ZUPT only (normal approach) and using ZUPT with ZIHR applied. Figure 4 shows the heading solution and it clearly shows that the heading drifts quite considerably if only ZUPT is used. After 60 seconds a heading error of 5° is observed, which then grows to about 100° after 900 seconds. When the ZIHR constraint is applied, an accuracy of better than 0·04° is achieved.
Figure 4. Heading errors during static test for ZUPT and ZUPT/ZIHR.
An alternative to using ZIHR is to fix the heading whenever conditions C 3 and C 4 are true. However, this would not make full use of the measurement as achieved using ZIHR where full correlation between states is exploited. Alternatively a yaw measurement can be applied using Equation 3 where δφ is computed as the difference between the current yaw and the yaw estimate before conditions C 3 and C 4 are true. However, if a heading measurement is used directly, it will result in an over optimistic estimate of the uncertainty of the attitude states. Consider an example where initial heading uncertainty and heading measurement noise are set to 10° and 1° respectively. Figure 5 shows the standard deviation of the down axis attitude error state, ϕD. Here we see that the standard deviation for the yaw measurement case drops to a small value which is unrealistic as the measurement is not a true measurement (such as from an external sensor). Instead we are only wishing to stop the heading error increasing and we wish to preserve the covariance in the Kalman filter. Thus, ZIHR is able to make full use of the measurement while preserving the covariance in the Kalman filter.
Figure 5. Down attitude error standard deviation for ZIHR and Heading Constraint.
4. HEIGHT CONSTRAINT
A height measurement is also introduced for our pedestrian navigation system to restrict the IMU height drift in indoor environments. Without the availability of height measurements from sensors such as GPS, the height of the INS solution will drift to some extent due to accumulation of errors in the inertial sensors that are not fully removed through ZUPT measurements.
Therefore, we make use of the knowledge that in most indoor environments, the floor will be level, and we assume that changes in height in indoor environment would only be caused by walking up or down the staircases. Since it is reasonable to assume that a pedestrian's foot lies on the floor during every stance phase of walking event, we create a predetermined height threshold that represents steps height, to limit the height error growth that gets updated in every stance phase. A change in height over one step is calculated and if it is below the threshold, the height from previous epoch calculation is maintained and projected to the next epoch. Thus, a fifth condition (C5) is used:
where |δh|=|h k−h k−1| (where epochs k and k−1 correspond to different steps) with empirical threshold, t hstep=0·05 m. If both C 3 and C 5 return true (logical 1), then height at the last epoch is preserved to update the position state vector in the Kalman filter, otherwise no update is applied. Using the measurement in this way unfortunately results in an over optimistic covariance of the height due to the issues discussed in regard to yaw measurements in the previous section. Although not strictly rigorous, the benefits of applying the height correction indoors are thought to outweigh any issues caused by an overoptimistic height covariance estimate. A measurement update is applied by forming the observation:
![$$\delta h = \left[ {\matrix{ 0 & 0 & { - 1} \cr}} \right]\delta p + n_k $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000518_eqn9.gif?pub-status=live){kind=small}
where δp is the IMU position error state vector with measurement noise n k.
A height constraint test is carried out by walking down and up a staircase. A pedestrian walked from the top to the bottom of the stairs, then walked up again and stopped at the same starting position. The stairs consist of 42 steps with ±16·5 cm each in height (measured using steel tape and assumed to be the truth), totalling 6·93 m in height. Figure 6 shows the INS height, with and without height constraint, and Figure 7 shows the period when the height constraint was performed.
Figure 6. IMU height output with and without height constraint.
Figure 7. Height constraint is being updated.
From Figure 6, when height constraint is used, the end position error for this trial is 6·6 cm, and it correctly identified 42 steps. In contrast, without height constraint, the end position error has drifted to 45 cm. The start of the data in Figure 6 is further magnified and shown in Figure 7. It clearly shows that when height constraint is performed (green marker), height error does not grow as opposed to when height constraint is not used (red plot). However it is important to highlight that for height constraint to hold true, changes in height in indoor buildings are assumed to be caused by staircases. Therefore, the height constraint will not work as expected if we consider other situations where the height change between epochs might not be as big, such as when walking on a ramp on the floor.
5. FULL TRIALS
Several field trials have been conducted in Nottingham, UK. The IMU used was a Microstrain 3DM-GX3 as described earlier in this paper. Table 1 summarises the output of the walks. ‘Return Height Error’ represents the difference in height while ‘Return Position Error’ represents the difference in position, after returning to the same location. The ‘Constraint’ column consists of results that use all the proposed constraints, while the ‘No Constraint’ column represents results that use only ZUPT as measurement update. From these eight field trials that use proposed constraints, it was found that for an average duration of 23·79 minutes and an average total distance travelled of 1557 m, the average return height error is 0·39 m, and the average return position error is 4·62 m. In contrast, trials that do not use the proposed constraints have an average error in height and position error of 40·38 m and 153·62 m respectively. Figures 8, 9 and 10 show the visualisation of three outputs from Table 1 trials, where heading drift errors have been reduced significantly. In the Figures, the yellow star marks the start and end of the walking trials, the red line marks the position output without using constraints and the green line shows the position output when constraints are applied.
Figure 8. Example of position output from Trial 8.
Figure 9. Example of position output from Trial 8.
Figure 10. Example of position output from Trial 8.
Table 1. Comparison of errors for proposed system with and without constraints applied.
6. CONCLUSIONS
This paper proposed an improved version of using ‘building’ heading information in the Kalman filter to restrict heading drift error. Previously the authors have demonstrated an effectiveness of using ‘building’ heading to correct heading drift for a low cost shoe mounted IMU system. It was however tested in a 2-dimensional environment excluding vertical position errors. Therefore this work extended the approach by considering a 3-dimensional situation. Furthermore this work highlights the importance of implementing the ZIHR algorithm where the user might stop walking for a long period of time, which is quite common for normal pedestrian walking. This is because a previous algorithm resulted in a significant problem with heading drift during prolonged stationary periods.
Full trials with an improved version of the algorithm were carried out in typical buildings and environments such as a car park. It was shown to give an average return position error of 4·62 m in 24 minutes of IMU-only navigation. For the vertical channel, a maximum height error of only 0·39 m was found. However, note that these figures represents the return position error (difference between start and end position), and not the accuracy of the system throughout the trial. Analysis was performed using a forward running Kalman filter only, which means that such results are achievable in real-time.
Future work will attempt to address several aspects of the system. Firstly, future work will examine the use of lower cost inertial sensors for navigation. The algorithm described is able to provide regular updates of velocity and heading which should enable the use of lower performance sensors since the errors can be continually estimated. While the sensor used in these trials is typically termed ‘low cost’, it is still substantially too expensive to be considered for consumer applications. Secondly, augmentation with other sensors such as GPS (when available) and magnetometers (which are typically available in low cost inertial sensor assemblies) will be explored. GPS will provide an essential source of position measurements in the environments where the signals are available and of sufficient quality to improve the position solution. The magnetometer may provide some additional measurements to correct the INS in environments where magnetic disturbances are low or buildings are not of a conventional shape. Finally, two situations have been identified where the algorithm is likely to fail: lifts and escalators. In these situations, it is likely that the zero velocity detection will provide a false positive and hence the algorithm will fail. Use of other sensors (such as a barometer), or additional measurements such as constant velocity may help to address these issues.
ACKNOWLEDGEMENTS
The authors would like to thank the Ministry of Higher Education of Malaysia and Universiti Sains Islam Malaysia (USIM) for partly sponsoring the study.
