(e.g. urban places) and much lower in rural environments [104].
37.5.4 Dead Reckoning
Dead reckoning refers to the use of sensors that provide location updates, calculated based on the last determined position and incrementing that position based on known or estimated speeds over elapsed time. Position and speed estimation is typically based on IMUs, which include multi‐axis accelerometers, gyroscopes, and possibly magnetometers. A disadvantage of dead reckoning is that the inaccuracy of the estimation process is cumulative, so any deviations in the position estimates become larger with time. This is because new positions are calculated entirely from previous positions. Thus, these inertial navigation systems (INSs) are often used to estimate relative rather than absolute location, that is, the change in position since the last update, with some other localization technology (e.g. Wi‐Fi fingerprinting) for obtaining periodic position fixes (absolute location estimates).
The first task in an INS that is used for human localization is the identification of steps or strides from the sensor data. A step is the period between two footfalls on opposite feet, whereas a stride is the same quantity but between the same foot. At a minimum, there is a need for accurate step detection and step counting for most INS‐based indoor localization approaches. Step cycle detection algorithms detect cycles in the INS data caused by the repetitive motion of walking, which may involve searching for repeating data patterns or for repeating events (e.g. the heel strike). This information can be used for step detection and counting. Figure 37.6 shows an example of extracting the cycle (and thus step counts) by seeking maxima in the mean‐adjusted autocorrelation of a sequence of accelerometer magnitude data [105]. Usually a low‐pass filter is used on the raw accelerometer data to remove noise as a pre‐processing step before the algorithm is used. Filter cutoff frequencies of around 20 Hz retain the step periodicity, although filtering down to 2 or 3 Hz has also been used successfully [106]. In general, the cyclic property of walking is directly reflected in the acceleration trace in the time domain. As heel strikes tend to introduce sharp changes, numerous schemes propose to detect magnitude peaks [107, 108], local variance peaks [109, 110], local minima [111, 112], zero crossings [113], or level crossings [114] (where levels are defined by historical mean and variance) from the low‐pass filtered acceleration trace.
Knowing the step count, it is possible to estimate displacement of a mobile subject if information related to the stride length is available. Pedestrians typically have a natural walking pace with a surprisingly constant stride length. However, this natural walking pace is altered when rushing, ambling, or walking with others. The stride length can vary by as much as 40% between pedestrians walking at the same speed, and up to 50% across the range of walking speeds of a pedestrian [106]. Direct measures involving additional sensors can help estimate the length with high accuracy (e.g. using ultrasonic sensors mounted on the front and back of each shoe [115], or electromyography sensors attached to the calf [116]), but such methods also come at high costs and inconvenience to the mobile user. Several studies in human kinematics correlate stride length with step frequency [117–119]. The major observation is that stride length tends to be shorter when walking slowly rather than fast [120]. A simple linear relationship often suffices [121], but the model parameters that are trained offline are specific to walking conditions, such as wearing sport shoes or high heels [122]. Techniques to detect locomotion modalities (e.g. walking or running) can help construct more elaborated motion models (e.g. adjust stride length estimation or step counting according to varying speeds), to improve localization accuracy. Utilizing accelerometers in smartphones to distinguish different locomotion modalities has been proposed in a few works [123–125].
Figure 37.6 Autocorrelation‐based step cycle detection. The top graph shows the raw acceleration magnitude during five sample strides. The autocorrelation of the mean‐subtracted signal is shown in the bottom graph, with strong peaks associated with each stride [105].
Source: Reproduced with permission of IEEE.
While accurate stride length improves displacement estimation, the accuracy increase is often marginal as drifts in heading (the direction of motion) typically dominate errors [126]. The heading direction of steps during motion can be obtained with a gyroscope or a compass (magnetometer). Gyroscopes output angular velocities in 3D, which are integrated over time to obtain direction change information. A turn can be detected when the relative orientation measured by a gyroscope changes abruptly. To distinguish between changes due to turns and changes caused by noise, only heading changes exceeding a predefined threshold are determined as turns [127]. A compass can measure the absolute orientation (heading) of the mobile device (e.g. smartphone) with respect to the magnetic north. However, Earth’s magnetic field is relatively weak at the surface, and buildings that are filled with metal and conducting wires can overpower the natural signal, leading to local “disturbances” (e.g. location‐specific magnetic offsets that can cause heading errors of up to 100o [128]). Some efforts attempt to filter the magnetic offset on consecutive compass readings, to improve accuracy [129]. An increasingly popular solution to overcome the offset is to combine gyroscope and magnetometer readings as the two sensors have complementary error characteristics: gyroscopes provide poor long‐term orientation, while magnetometers are subject to short‐term orientation errors [130]. In general, multiple types of inertial sensors perceive similar movements during walking, which can be used to overcome errors; for example, a compass value can be considered valid if the readings of the compass and gyroscope in the INS unit experience a correlated trend [111], which can help discard compass values containing a severe magnetic offset.
Today’s smartphones include IMUs, and the fact that they are carried by people almost everywhere makes INS‐based indoor localization particularly attractive. However, one important challenge is to account for the manner in which the smartphone is carried: in front pockets, back pockets, side pockets, shirt pockets, backpacks, handbags, on belt clips, or in the hand. A few efforts on activity recognition have explored estimating phone placements [125], which may help improve the performance of dead‐reckoning‐based localization systems. However, studies have shown that even if a smartphone is located in a single location (e.g. trouser pocket), notable errors are accrued (about 14.4% [131]) when estimating distance traveled, compared to foot‐mounted ground truth sensors.
37.5.5 Map Matching
Accurate trajectory estimation is a major goal of most indoor localization and navigation systems. A pedestrian trajectory consists of a sequence of step vectors. Techniques that utilize an electronic map to determine the position of a mobile person or object along a trajectory in the context of locations provided on the map are referred to as map matching techniques. The idea of applying electronic maps to adjust a mobile subject’s positions has been used in outdoor localization schemes [132]. Similarly, integrating the geometric constraints of floor plans in indoor environments can help improve indoor localization accuracy (e.g. when used in tandem with dead reckoning or Wi‐Fi fingerprinting). In general, the overall geometric shape of a mobile subject’s trajectory should be similar to that of the floor plan, and any deviations can point toward an error in a localization scheme. Various geometric abstraction models have been proposed for map matching, for example, link‐node models [133] and stress‐free floor plans [108]. Particle filtering techniques can additionally be used to exclude unlikely positions for mobile subjects, such as obstacles and walls [134, 135].
LiFS [110] is an example of a framework for matching sensor/signal readings to a physical floor plan. First, continuous measurement of acceleration readings and RSS readings is performed with the aid of smartphone users during their routine
