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 work and occupancy of buildings. Footsteps are then detected and counted, and these are then used as the inter‐fingerprint distance measurements. Feeding the inter‐fingerprint distances to a multidimensional scaling (MDS) algorithm results in a high‐dimension space called the fingerprint space, where the mutual distances between points (fingerprints) are preserved. The fingerprint space is then mapped to the physical floor plan to associate fingerprints with their corresponding physical locations in the indoor environment. The mapping is achieved by exploring the spatial similarity between the fingerprint space and a transformed floor plan, called the stress‐free floor plan. The stress‐free floor plan is a space that transforms a normal floor plan into a high‐dimension space using MDS, in such a way that the geometrical distances between the points in the new space reflect walking distances instead of straight distances. The rationale behind such transformation is that, due to the presence of obstacles (e.g. walls), the walking distance between two locations is not necessarily equal to the geographical distance between them. LiFS was shown to achieve good performance, with the 95th percentile mapping error being lower than 4 m and an average error of 1.33 m. The radio map generated using LiFS can be used as a starting point for various fingerprint‐based localization techniques.
Several other efforts have addressed map matching. In [136], a framework was proposed to combine a backtracking particle filter (BPF) with different levels of building plan detail to improve the indoor localization performance via dead reckoning. Particle filters are able to take into account building plan information during indoor localization with a technique called map filtering [137]. With map filtering, new particles are not allowed to occupy impossible positions given the map constraints. For example, particles are not allowed to cross directly through walls. Particles that transition through such obstacles are deleted from the set of particles or downweighted, as shown in Figure 37.7. BPF further exploits particle trajectory histories to improve upon simple particle filters, by recalculating previous state estimates after invalid particles are detected. In order to enable backtracking, each particle has to remember its state history or trajectory. Mean location estimation errors when using dead reckoning, dead reckoning with particle filters, and dead reckoning with BPF were shown to be 7.7, 3.1, and 2.6 m, respectively [136].
Figure 37.7 Particle transition near obstacles: if a particle tries to move to an impossible location, for example, across walls defined in the map, it will be killed off [136].
Source: Reproduced with permission of IEEE.
Predicting the trajectory of a mobile subject can also help reduce ambiguity when using fingerprinting for localization [138]. As an example, displacement and direction information obtained with dead reckoning impose relative geometrical constraints between consecutive location queries along a trajectory. These constraints transform the fingerprint matching from essentially being a point matching process to one that now involves line fitting by embedding the entire trajectory into the radio map. ACMI [139] employs FM broadcast signal fingerprinting for localization, and uses trajectory predictions for localization accuracy improvement. Experimental results have demonstrated that localization errors decreased from 10–18 m to 6 m, along with an increase in the room identification accuracy from 59% to 89%, when trajectory matching was used.
Certain indoor landmarks and contexts also possess distinctive sensor signatures. For example, accelerometer readings on an elevator exhibit a sharp surge and drop at the start and the stop of the elevator. An investigation of such unique acceleration patterns of stairs, elevators, escalators, and so on, was performed in [111], and it was concluded that if the locations of these structures were known previously, they could serve as landmarks to improve indoor localization accuracy (e.g. to overcome dead reckoning drifts).