Session E2, Paper #1

Context-aware Adaptive Extended Kalman Filtering Using Wi-Fi Signals for GPS Navigation
M. Shafiee, K. O´Keefe, G. Lachapelle, University of Calgary, Canada

Due to ever-growing coverage of WLAN networks, integrating Wi-Fi and GPS can be a promising approach to solving the problems encountered during precise indoor GPS positioning such as severe multipath conditions. Wi-Fi localization methods have been investigated and realized and can be categorized into RSS (Received Signal Strength)-based or model-based methods. RSS-based methods are based on collecting a database of observed RSS from available Wi-Fi access points and then applying pattern recognition algorithms to define an unknown position with regard to AP positions. Therefore, these methods require fingerprinting the network coverage and collecting database, which implies additional time and financial cost. Also, since the accuracy of Wi-Fi access points database reduces over time these systems should frequently update the database, which is an expensive process. On the other hand, model-based methods suffer from lack of knowledge for modeling signal propagation especially in indoor environments and under multipath conditions.

In this paper, the question of indirect use of WLAN signals and exploiting the external information provided by the Wi-Fi signals is addressed. One possible way to exploit knowledge of changes in user context is with adaptive positioning methods where the Wi-Fi information can be used to adjust uncertain parameters in the GPS positioning algorithm. The use of external information in a context-aware programming framework to improve the GPS positioning performance within the navigation solution is investigated. A new two-layer adaptive extended Kalman filter positioning algorithm is proposed based on multiple model adaptive estimation in which each individual Kalman filter, matched to a different dynamic model, has an IAE (Innovation-based Adaptive Estimation) structure and the external information is used as a context to adjust the adaptive parameters based on the different situations, i.e. environmental contexts like Indoor/outdoor and motion context like static/kinematic. More specifically, the motion contexts are used to weigh multiple models while the indoor/outdoor contexts are used to adapt the statistical information through the measurement covariance matrix or the process noise. The weighted sum of all individual estimates is used as the adaptive optimal estimate of the states. The weighting scheme is based on the posteriori probabilities for each of the hypothesis. As the measurements evolve with time, the proposed adaptive algorithm will converge to the correct hypothesis by learning the correct filter and making its weight factors approach 1 (if the state remains unchanged for a considerable amount of time) or adapting the system model to the most recent state. The proposed algorithm has a closed loop structure and the weighted sum is exploited to provide feedback information for both Kalman filters in a recursive scheme. First, the existence of similar patterns in WiFi signal features under similar environmental and/or dynamic conditions is investigated. Repeatability and consistency of the results of using WiFi features as context identifiers and that the pattern can be used to make assumptions or predictions about the current mode are demonstrated. Some simple effective identification algorithms are proposed based on several features such as the number of available APs or the number of APs with RSS exceeding a certain threshold, the mean and the variance of the total RSS from available APs, and the degree of similarity between the eigenvectors of the sample covariance matrix within windows of observations.The performance of these algorithms has been tested through field test results under different conditions to be described in the paper. An important parameter, which affects the performance of the proposed algorithm, is the probability of correct context identification (PCCI). Combining multiple identifiers can be a promising approach to improve PCCI. An algorithm based on the Dempster-Shafer theory is proposed to fuse decision sequences of several identifiers, which may or may not use the same source of external information. The algorithm is then modified to deal with high conflict situations and correlative decisions. Simulation results show the effectiveness of the algorithm.

The results also will be verified through field tests. Furthermore to improve the robustness of the proposed context-aware algorithm a control block based on the type 2 finite state Markov Decision Process (MDP) is implemented with regard to the reward history in which a reward is realized based on the one-step transition between identified contexts in two consecutive epochs. Here the reward is a function of innovation sequences in different modes and an optimum decision strategy (policy) is estimated so that the expected reward (performance measure) is maximized. Exploiting the reward function to determine the optimal policy is a considerable contribution, which does not appear to have been addressed in the literature for this particular problem. The transitions are controlled by both transition probabilities and reward history and a policy iteration method is used to find the optimum policy via two procedures of value-determination and policy-improvement. It should be noted that the control block can be considered as an optional block and one can decide to activate or deactivate it based on the required robustness of the system and at the cost of increasing the complexity of the algorithm. But yet it can be shown that the computational complexity of the algorithm is acceptable in cases where higher accuracy and reliability are required. The algorithm has been implemented and primary field test results show improvements in terms of positioning accuracy and reliability. The proposed algorithm outperforms the conventional adaptive Kalman filter, which adapts the process noise, and the covariance matrix of the observations based on innovation sequence. In addition, it is shown that in comparison to IMM-based methods, the proposed method is more reliable and robust in weight distribution between models, because of the use of the external information. Furthermore, the adaptation is also applied to statistical characteristics of the system, which gives additional improvement over IMM-based methods.

[Return to Program]

Session E2, Paper #2

A Pedestrian Indoor Positioning System Based on the WIPS and Walk Patterning Algorithm Using Smart Phone
J.H. Lee, B.J. Shin, S. Lee, J.H. Kim, Korea Institute of Science and Technology, South Korea; S-C. Lee, Korea Telecom, South Korea; J.W. Park, Korea University, South Korea; T. Lee, Korea Institute of Science and Technology, South Korea

Recently, according to the growth in the use of smart phone, the attention to Location Based Service(LBS) using the smart phone is increasing rapidly. Especially, the techniques for the LBS inside the buildings is being magnified. To provide the LBS inside the building to users, there are several techniques like PDR(Pedestrian Dead Reckoning) and Wi-Fi based fingerprinting and being researched actively. However, these techniques have the drawbacks each. PDR could not reflect the walking characteristics of the pedestrian like running or walking. And fingerprinting algorithm using k-Nearest Neighbor (k-NN) or Weighted-KNN (WKNN) adopting the fixed k for a given environment, so it has the relatively low accuracy for estimating the position of pedestrian. In this paper, to make up the drawbacks of existing algorithms, indoor navigation system which could have the high accuracy according to the walking characteristics of the pedestrian and the given environment is presented. The proposed navigation system includes the Pedestrian Walking Patterning (PWP) to reflect the walking characteristics of the pedestrian as well as the Wi-Fi based Indoor Positioning System (WIPS) to estimate the position of the pedestrian with optimal k which are calculated using the enhanced-kWNN changing the k all the time according to a given environment.

Pedestrian Walking Patterning(PWP) is an algorithm to estimate the step length using the walking pattern of the pedestrian. The information about steps could be obtained from the inertial sensors like accelerometer, gyro and magnetometer. The position of the pedestrian could be estimated using the step length and azimuth when we assumes that we know the initial poistion of pedestrian. To determine the step length, we need the step information from the accelerometer. First, to determine the steps, we differentiate the output of the tri-axial accelerometer. From this process, we could eliminate various error sources, such as the bias of the accelerometer and gravity. Using the output of this process and algorithms to detect the steps, we could determine the steps. There are three types of algorithm to detect the steps, zero-crossing detection, peak detection and flat zone detection. But flat zone detection algorithm could now be used when the accelerometer is equipped in the mobile device. So we are going to use the zero-crossing detection and peak detection algorithm together for high accuracy. To estimate the step length, we need more information about walking distance. To get the information about walking distance, we use the azimuth information from the magnetometer equipped in the mobile device and the digital map. Using the digital map data and magnetometer, we could determine characteristic points where pedestrian has turned. So the distance between these points would be the real walking distance of the pedestrian in the digital map. The step length of the pedestrian could be estimated by dividing the walking distance by the number of steps. By doing this, we could reflect the walking characteristics of the pedestrian almost in real-time.

Along with the PWP, we use the Wi-Fi based Indoor Positioning System(WIPS) algorithm to estimate the position of pedestrian. Because of the position of the pedestrian from PWP is relative position in digital map, so we need WIPS to estimate the absolute position of the pedestrian. WIPS uses the fingerprinting to estimate the position of the pedestrian. In this paper, fingerprinting method using enhanced-KWNN (e-KWNN) is used to estimate the position of the pedestrian. In e-KWNN algorithm, we find the optimal k according to a given environment to improve the accuracy of the positioning. In other words, e-KWNN changes the value of k adaptively whenever the mobile device scans the RSSI according to a given environment to improve the accuracy of positioning. So WIPS could be efficient for estimating position of the pedestrian.

The estimated position of the pedestrian using PWP and WIPS has to be matched in the digital map to provide a location based service for the pedestrian. We use the Map Matching algorithm to match the estimated position of the pedestrian to the digital map data. MM algorithms not only enable the physical location to be identified but also improve the positioning accuracy.

To verify the proposed indoor navigation system, we used the smart phone based on the Android OS from Google Inc. and experimented inside the building which has the hall and lobby. Through the experiments, we could verify that proposed system has the high accuracy on the step length. Because, step length is computed adaptively according to the different users who has the different walking pattern. And proposed system could be provided to users almost in real-time. In this paper, we proposed the indoor navigation system using the mobile device. To provide the service to the user, we configured the algorithm with the two parts. First part is to calculate the step length and second part is to find the location of the pedestrian. To calculate the step length reflecting the walking characteristic of the pedestrian, we used the characteristic points on the digital map. So we could get the more accurate step length than existing algorithms that use the linear combination of walking frequency and acceleration variance. Moreover, by using the digital map data, we could identify the two status like tilting and turning the corner. In the training phase, we reduced the time to build the fingerprinting map by reducing the reference points. But reduction of the reference points could lead the decrease of accuracy, so we tried to make up this problem by using the Weighted-KNN algorithm with adaptive k at a given environment. And we reduced the unnecessary reference points during estimation phase so, we reduced the time to compute the position of the pedestrian. The PWP could have the low accuracy when WIPS has the high accuracy in some cases, and the opposite case could be exist. So we are going to use the integration of the PWP and WIPS.

[Return to Program]

Session E2, Paper #3

Gait Classification Using Wavelet Descriptors in Pedestrian Navigation
Y. Ma, Honeywell Aerospace; J. Hesch, University of Minnesota

The design of pedestrian navigation systems has received significant attention from both the industry and academic research communities in recent years. Numerous target applications have been proposed, including localization for a coordinating group of firefighters, first responders, or soldiers. In these applications, the safety and efficiency of the entire team relies directly on the availability of accurate position and orientation (pose) estimates of each team member. When the team is working within the coverage area of the Global Positioning System (GPS) satellite network, each person equipped with a GPS receiver can be reliably tracked. However, a far more challenging scenario arises when the team operates inside a building, in the urban canyon (i.e., next to tall buildings), underground (e.g., in a mine), in foliage, or under the forest canopy. In these cases, global localization cannot be addressed with GPS, and must be accomplished through secondary means. One popular approach is to equip each person with a body-mounted strap-down Inertial Measurement Unit (IMU), which has three accelerometers and three gyroscopes, mounted in orthogonal triads. As the person moves, the inertial measurements (i.e., linear acceleration and rotational velocity) can be integrated in order to obtain a pose estimate. However, the integration of both sensor noise and unknown bias causes the pose estimates to drift quickly. To mitigate the inertial drift errors in the strapdown navigation an aiding sensor can be employed, such as a camera or laser scanner, which provides exteroceptive information about the environment (e.g., color, texture, or scene geometry). The person´s pose can be estimated by fusing the integrated IMU signals with environmental cues, such as the locations of nearby landmarks, in order to improve pose-estimation accuracy.

While these aiding sensors are typically considered to be essential for accurate, GPS-denied navigation, they often require additional infrastructure (e.g., UWB radio beacons) which can increase the complexity, cost, and power requirements of the personal navigation system. For these reasons it is advantageous to consider other methods for constraining inertial drift that do not rely on incorporating additional sensors onto the platform. In the current work, we present an approach which constrains the person´s pose using a dictionary of motion models, and a gait classifier that only relies on the IMU data. Specifically, we propose to first detect the person´s gait (e.g., walking, running, crawling) using wavelet signatures computed from the IMU signals. Subsequently, a motion constraint is formulated based on a set of motion models which determine speed as a function of gait, frequency, and biometric information (e.g., leg length). Finally, we incorporate the motion constraint into the inertial navigation system to reduce pose estimate errors. The principal advantage of the proposed approach is that it works without requiring additional sensors, instead, it leverages domain information (i.e., how a person moves) and the already-available IMU measurements, in order to improve navigation accuracy.
The basis of our motion classification algorithm is a bank of one-class Support Vector Machines (SVM), each trained to classify a specific gait mode based on segments of the IMU data (i.e., up to six signals over a time horizon) recorded while the person is navigating around the environment. Instead of working directly with the raw sensor data, which is noisy and high-dimensional (e.g., a 0.5 second window of six channels of IMU data recorded at 100 Hz comprises 300 samples), we first transform the IMU data into the wavelet domain, and perform judicious down-sampling and feature selection. In order to obtain the most discriminative representation for each class, we compute a Radial Basis Function (RBF) describing each gait in the wavelet-feature space. We represent each gait at multiple phases and frequencies so that real-time classification can be accomplished without the need for complicated pre-processesing of the on-line IMU data.
The proposed gait-classification approach stands in stark contrast to existing approaches which first require the on-line data to be segmented into individual steps before classification. It is problematic to require on-line step segmentation, since even a single missed foot-fall can cause the algorithm to break. Furthermore, existing approaches often base gait-discrimination on key points in the time-domain IMU data (i.e., a specific peak or valley in the acceleration profile), however, detecting these time-domain interest points can be challenging in the presence of noise. In contrast to the existing approaches, we avoid the need to segment the on-line data into individual steps prior to classification, furthermore, since we use wavelet-domain features, our algorithm is significantly more robust as it inherently employs both time and frequency information.
At each time-step, we use the current window of IMU data to first classify the person´s motion into one of several categories (e.g., walking, running, crawling, duck walking). Based on the gait model and frequency, we formulate a motion constraint using a dictionary of motion models which have been compiled off-line using recorded IMU data collected along known trajectories. Using the information from the motion model, we incorporate each detected gait step as a measurement constraint in the extended Kalman filter (EKF). This additional information limits the inertial drift and significantly improves the accuracy of the pose estimates.
The key advantages of the proposed algorithm are: (i) the ability to reduce inertial drift without requiring additional sensors, (ii) high accuracy and reliability both in the classification stage and the gait modeling stage, (iii) flexibility and extensibility to any number of new gait modes, and (iv) a light-weight and computationally inexpensive algorithm design, which can run on standard computing hardware in real-time.
The proposed method has been evaluated both in simulations and experimental trials in order to exhaustively test the performance of the system. We present results for classifying and modeling ten gait modes, and describe how the method can be extended to any number of new gaits. We provide a thorough description of our results, and highlight interesting complications which may arise in practice.

[Return to Program]

Session E2, Paper #4

A Robust Sensor Fusion Algorithm for Pedestrian Heading Improvement
S. Siddharth, A.S. Ali, University of Calgary, Canada; C.L. Goodall, Z.F. Syed, Trusted Positioning, Inc., Canada; N. El-Sheimy, University of Calgary, Canada

Improvement in the heading of the user for walking cases, especially in GNSS denied environments and urban canyons, is a difficult problem in pedestrian navigation that needs investigation. The heading observability considerably degrades in low speed walking, making this problem even more challenging. The goal of this work is to improve the heading solution when hand-held personal/portable devices such as cell-phones are used for positioning. Most of the smart phones are now equipped with self-contained, low cost, small size, and power-efficient sensors, such as a magnetometer, a gyroscope, and an accelerometer. For an absolute heading computation, a suitable choice is using a magnetometer in combination with a gyroscope. Before the magnetometer can be used in the navigation it needs calibration. A method for fast calibration of the magnetometer and a magnetometer anomaly detection algorithm are discussed in this paper.

Detection and mitigation techniques for spurious time varying magnetic fields that corrupt magnetometers in the Earth´s Magnetic Field (EMF) are explored. Variations in EMF results in unreliable magnetometer heading measurements and therefore, checking for an EMF area becomes important. This can be done by comparing the variation of magnetic field norm, in a moving window of predefined number of samples, based on repeated tests. As part of improving the robustness of the heading solution, two 3D magnetometers, a Honeywell magnetometer (HMC5843) and an Asahi Kasei (AK8975), mounted as a mirror image configuration in the device are used. Tests for hand-held and reading/texting modes, where the user walks in a straight line trajectory with some turns, show promising results. Magnetometer calibration requires specific motion modes or maneuvers, which are important for calibration and will be discussed in detail.

The performance of a Kalman filter is suboptimal, and diverges when initialized with incorrect noise parameters. This can be avoided by obtaining the filter parameters offline using some evolutionary technique. To this end, a novel filter design referred in this paper as Swarm Optimized Constant gain fusion Kalman Filter (SOC-KF) is proposed, which combines the information from 3D calibrated magnetometer measurements, an accelerometer, and a gyroscope efficiently. The optimal gain of the SOC-KF, initialization, and noise parameters are obtained offline using a Particle Swarm Optimization (PSO). The PSO, like the Genetic Algorithm (GA), is a robust stochastic evolutionary computation technique based on the movement and intelligence of swarms looking for the most fertile feeding location [1]. It is a population-based heuristic searching methodology and found to be robust and fast in solving nonlinear, non-differentiable, and multi-modal optimization problems. A swarm consists of a set of particles (individuals) moving around the search space, each representing a potential solution (based on best fitness). Each particle is represented by a position vector, a velocity vector, the position at the best fitness, and the index of the best particle (Global best) in the swarm. The position of each particle is updated at every generation, and the final solution cannot be trapped in a local optimum. The GA is inspired by the principles of genetics and evolution, and imitates the reproduction behavior seen in biological species. Both the GA and the PSO are well suited and have been extensively employed to solve complicated design optimization problems as they can handle both discrete and continuous variables as well as nonlinear objective and constrain functions without the computation of a gradient [2]. Unlike the drawback of expensive computational cost of Genetic Algorithm (GA), the PSO has better convergence speed. The proposed filter is compared to the theoretical Cramer-Rao Lower Bound (CRLB) to check if the filter is a Minimum Variance Unbiased (MVU) estimator. Consequently, the real-time filter is shown to work optimally, efficiently, and with reduced time-complexity compared to a conventional Kalman filter. This filter can also be made adaptable to different application modes; two of them used in this research are stationary and walking. The adaptability can be guaranteed by exploiting the covariance matrix of the innovation sequence. Averaging inside a moving window of optimal size can be conclusive in the determination of mode switching.

For the proposed orientation filter, quaternions as system states are estimated by merging the information from a gyroscope, an accelerometer, and a magnetometer. Gyroscopes work accurately over short time intervals, and assist in compensation for loss in heading information during magnetic anomalies and are also used to smooth the coarse magnetic heading derivations. Lab tests were first conducted to evaluate the validity of using the calibration procedure seamlessly in indoor and outdoor environments, and later the proposed filter was applied to real walking scenarios to obtain the heading. The results show that good pedestrian navigation solutions can be obtained if the heading derived by using the technique described above along with an appropriate pedestrian dead reckoning algorithm is implemented.

References [1] Eberhart, R.C., Shi, Y. "Comparison Between Genetic Algorithms and Particle Swarm Optimization", In: 1998 Annual Conf. on Evolutionary Programming, 1998.

[2] Hassan, R., Cohanim, B., Weck, O. De, Venter, G., "A Comparison of Particle Swarm Optimization and the Genetic Algorithm"In 46th AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference, 2005.

[Return to Program]

Session E2, Paper #5

Integration of Heading-Aided MEMS IMU with GPS for Pedestrian Navigation
J. Pinchin, C. Hide, K. Abdulrahim, T. Moore, C. Hill, University of Nottingham, UK

Pedestrian navigation is a difficult problem since pedestrians are able to walk inside buildings for long periods where GNSS signals are typically degraded or unavailable. Even when pedestrians walk outside, GNSS performance can be significantly degraded when walking in areas such as urban canyons. Therefore it is necessary to augment GNSS with other positioning sensors and systems in order to provide seamless navigation in all environments. Inertial navigation is typically identified as a technology to be combined with GNSS, however, the accuracy can be very poor particularly for low cost devices. Recent developments in the research community have dramatically increased positioning accuracy by mounting inertial sensors on a pedestrian´s shoe and using zero velocity measurements every time a user takes a step. Using this technique, positioning accuracy is usually governed by the accuracy to which the yaw of the Inertial Navigation System (INS) can be maintained. Typically this is achieved using measurements from a 3-axis magnetometer, however, this is often unreliable particularly inside buildings where there are significant magnetic disturbances.
Previously, the authors have developed an indoor positioning system based entirely on inertial measurements starting from a known location and heading. To alleviate the yaw accuracy problem, the authors have developed an approach of using ´building´ heading to restrict the heading drift of a low cost MEMS IMU for pedestrian navigation. Using simple information of the orientation of the building derived from maps, the yaw drift is controlled by restricting the motion of the user to typically one of four directions. This is because most buildings have a simple construction of corridors and rooms that constrains the user´s motion to one of four directions. The additional measurements are used along with zero velocity measurements in a Kalman filter to estimate the inertial sensor errors and maintain an accurate position. Using this algorithm, the authors have demonstrated inertial-only positioning to within 5m over periods as long as 45 minutes. The algorithm is also robust to short periods where the user motion is not constrained to the building orientation such as in open plan areas or buildings with unusual construction.

This paper explores the issues of integrating GPS measurements with a foot mounted IMU and heading correction algorithm. The paper addresses two significant issues. Firstly, initialisation of the inertial algorithm is necessary, in particular the initial position and heading need to be computed. Magnetometer measurements can be used to compute the initial heading although they are typically unreliable. GPS measurements can be used to refine the heading solution given sufficient dynamics although this needs to be achieved rapidly since the pedestrian may only have measurements available for a short period. Secondly, it is important to correctly weight the GPS measurements in the filter. Depending on the type of GPS receiver used, the accuracy of the measurements may vary significantly. For example, the accuracy found on modern consumer GPS receivers will vary significantly depending on the multipath environment and number of signals. Traditional measures such as Dilution of Precision (DOP) become unreliable as geometry effects are less significant than multipath. Instead, measures such as signal-to-noise ratio and pseudorange residuals are examined.

This paper will describe results from field trials that contain a mixture of indoor and outdoor positioning. A Microstrain 3DM-GX3-25 inertial sensor is used along with a low cost u-blox high sensitivity GPS receiver that provides position and velocity measurements as well as access to raw pseudorange and carrier phase measurements. In addition to using the receiver derived position solution, the pseudorange and carrier phases are used to generate a differential positioning solution using RTK algorithms. It is demonstrated that despite significantly reduced availability, the RTK solution is much more suitable for integration due to the improved position accuracy. This makes the integrated solution much more reliable when transitioning from outside to inside since the IMU positioning accuracy is governed by the GPS accuracy when it was last available which can be quite unreliable when using measurements from a high sensitivity receiver.

Overall, the paper describes the development of a high accuracy ubiquitous positioning system using low cost sensors. The system is based around a low cost IMU continuously updated using automatically detected zero velocity measurements in a Kalman filter as the user walks. GPS measurements are used for initialisation and to control INS errors when the signals are available. A comparison of measurements types (RTK or standalone) from the GPS receiver is given as well as an analysis of algorithms used to correctly weight the measurements in the Kalman filter. The system also uses a novel building heading correction algorithm that offers a significant improvement over magnetometer based corrections to maintain high accuracy positioning while indoors. Application of the algorithm in outside areas is also investigated since it can be applied when the user is walking along straight roads and paths. The developed system is demonstrated to provide high accuracy continuous positioning in mixed indoor and outdoor locations.

[Return to Program]

Session E2, Paper #6

Multi-Sensors Observability Analysis on Pedestrian Navigation System
X. Zhao, University of Calgary, Canada

Observability is an important aspect of the system estimation problem in the integration of the multiple
sensors with GPS in deep indoor and dense urban areas for personal navigation. As such Kalman filter
applications, analytical and empirical approaches on the observability analysis provide additional insights on the estimator behavior in a systematic way. Consequently, the designed state errors can be guaranteed to be observable and converged quickly.

The paper explores the relationship between some maneuvers of pedestrian navigations with the error states in the INS/magnetometer/GPS integration, such as heading angle, gyro, magnetometer biases, scale factor, and stride length correction etc. It also provides quantitative information about the degree of observability for each estimated state to assist optimal selection of estimated states for the navigation solutions using different sensors configurations.

Field tests using a prototype portable navigation system demonstrated results consistent with observability analysis and showed that the prototype system can effectively deal with short GPS signal outages and correctly estimate navigation states online using EKF. Therefore, different simplified sensors configurations can be adapted for different application environment. The solutions exhibit good potential for a portable, reliable, accurate and low-cost system that enables continuous navigation anywhere.

[Return to Program]

Session E2, Paper #7

Collaborative Pedestrian Mapping of Buildings Using Inertial Sensors and FootSLAM
P. Robertson, German Aerospace Center, Germany; M. Garcia Puyol, German Aerospace Center and University of Malaga, Spain; M. Angermann, German Aerospace Center, Germany

Pedestrian navigation is drawing significant research and development interest over the last few years and encompasses a wired range of research communities. In addition to using satellite navigation receivers, or signals of opportunity such as mobile radio or WLAN, the use of other low-cost sensors has become one of the addressed topics. For a number of years it has been known that foot mounted MEMS based inertial sensors (IMUs) can, in combination with known building plans, allow for stable positioning in two and three dimensions even in the absence of other signals.

As an extension to this work we recently presented FootSLAM - Simultaneous Localization and Mapping for pedestrians - using foot IMUs as the main sensors. Developed by the robotics community, traditional SLAM for indoor and urban environments has drawn on sensors such as laser scanners and cameras whereas FootSLAM uses only the odometry - the noisy IMU-based measurements of a person´s step vectors. In a perfect world this odometry would be error free and the pedestrian´s location could be estimated within the relative coordinate system for an unlimited distance travelled. Since state-of-the art odometry suffers from the gradual increase in errors, FootSLAM must searches over many different odometry error hypotheses finding one which best fits. Hypotheses in which the pedestrian revisits areas in the environments are rewarded and over time a reliable map of essentially "walkable areas" is constructed. Real data from people walking within office environments at two locations has so far been used to validate the map building and relative localization abilities of FootSLAM. The approach can use GPS as a provider of reference position before and after entering a building, thus anchoring the map with reasonable position accuracy. FootSLAM is necessary because existing maps are often inaccurate, unavailable, outdated, proprietary, and do not reflect important features such as furniture, stalls, displays and other features of a place that significantly limit or channel pedestrian motion.

In this paper we will present an extension to the FootSLAM method. We shall address the problem whereby different data sets are to be processed to generate a common map. First of all we distinguish these different cases of FeetSLAM:

1.A number of walks all starting at the same starting point and/or finishing at the same finishing point (or pose) and overlapping the explored area to a certain degree. 2.Walks not necessarily starting/finishing in the same point (or pose) but overlapping in the explored area to a certain degree. 3.Walks not necessarily starting in the same point and not necessarily overlapping in the explored area.

All these cases may be formulated as real-time or offline mapping problems. A real-time usage scenario is mapping of a building by multiple collaborating pedestrians with the objective of providing immediate map and position information of all collaborating pedestrians or others. Such a scenario may occur in emergency situations were multiple teams of fire-fighters enter a building through the same of different entrances and carry out search and rescue tasks and want to avoid unnecessarily revisiting areas or involuntarily leaving out areas. In law enforcement applications, accurate determination of every team member´s position and providing this information on a map may significantly improve mutual situation awareness and potentially reduce the risk of accidentally harming a team member. In this application the real-time requirements may be severe and no a priori map data may be available. In the paper we will focus on non-real time processing first, in the expectation that the techniques can be sped up to real-time capabilities over time. In offline applications we wish to derive a map that will later serve as basis for localizing pedestrians by map-aided pedestrian dead reckoning. An example of this is collaborative mapping of airports, museums and other public buildings for use in tourism, travel, and any high-precision location based services. In FeetSLAM pedestrians roam through all accessible rooms and areas on all levels of a building - perhaps as a deliberate mapping effort or during activities of everyday life. The pedestrians carrying out the mapping task needs to be equipped with some form of odometry-generating sensor, such as a foot-mounted IMU and most likely a GPS receiver for anchoring. In this scenario the measurement data needs to be recorded and will then be processed offline. The resulting map is then stored at a server or distributed to localization devices that use it to perform map-aided pedestrian dead reckoning.

The FeetSLAM technique builds on iterative processing of odometry data; using maps originating from other data sets as a so-called prior map for a given data set. We show that this follows from the optimal FeetSLAM derivation but is more suited to practical computation limitations such as limited memory. Its also yields maps which are not overly dominated by one data set but rather balances the characteristics of each with the effect of averaging out errors. Over iterations, the GPS anchors and FootSLAM maps are gradually combined to yield a high-accuracy global map - the iteration speed is controlled by employing concepts from simulated annealing.

Finally, a novel quantitative metric of performance evaluation will be presented that counts the violations of FeetSLAM or FootSLAM maps against a known ground truth. Our current results show that processing FeetSLAM can improve the FootSLAM hexagon transition error rate from roughly 1% (FootSLAM only) to less than 0.3% (FeetSLAM iteration 5). With FeetSLAM we have even exposed an error in our building plan ground truth - the actual layout of the drywall construction has been recently changed and not reflected in the map.

In summary FeetSLAM significantly improves the mapping accuracy in addition to providing maps for the entire area based on data collected during multiple walks. The maps are useful not only for greatly improved positioning of pedestrians, but also as a basis for semantic maps where places have meanings which can be learnt from data.

[Return to Program]

Session E2, Paper #8

Low Cost IMU, GPS and Camera Integration for Handheld Indoor Positioning
C. Hide, T. Moore, IESSG, University of Nottingham, UK; T. Botterill, University of Canterbury, New Zealand

Indoor positioning is a significant challenge since GPS signals are typically unavailable or significantly degraded due to multipath. It is also preferable not to install dedicated transmitters inside buildings for positioning due to the cost of installation and maintenance. Furthermore, an ideal indoor positioning system would use only sensors already found on modern smartphones. Such sensors include GPS, inertial (gyros and accelerometers), Wi-Fi, Bluetooth and cameras, all of which may be useful for indoor positioning.
This paper explores the possible use of measurements from GPS; Inertial Measurement Unit (IMU) consisting of 3-axis gyros and accelerometers; and measurements from a camera using computer vision algorithms. This particular combination of sensors is now commonly available on modern smartphones and hence is of significant interest if the measurements can be combined to provide accurate indoor positioning capability. An algorithm has been developed by the authors that combines measurements from these sensors. The low cost IMU provides continuous navigation regardless of the ability to capture measurements from other sensors, however the accuracy degrades rapidly due to measurement errors from the inertial sensors. When position and velocity measurements are available from the GPS receiver, they are used to correct the drift of the IMU using a Kalman filter. The Kalman filter estimates position, velocity, attitude and sensor biases to improve position accuracy from the IMU-only solution.

In addition to GPS measurements, computer vision algorithms are also used to correct the IMU drift through the Kalman filter. It is assumed that when using a smartphone for navigation purposes, a user would typically hold the device out in front of them with the camera approximately pointing towards the ground. The camera therefore has a view of the ground beneath, and immediately in front of the user. Successive images recorded by the camera can be used to track natural features on the ground as the user moves. Assuming that the ground underneath the camera is approximately planar, a homography can be used to form a model that allows features not consistent with the homography to be identified and removed. The homography can then be used to calculate the translation and rotation of the camera which can provide additional measurements to the Kalman filter, particularly when GPS measurements are available.

The translation measurements from the computer vision algorithm can be used to compute an estimate of the velocity of the camera (and hence IMU) if the height of the camera above the ground is known. An additional state is modeled in the Kalman filter to estimate the error in camera height which is refined when GPS measurements are available. The rotational measurements are not currently used as their accuracy is significantly less than that provided by the gyros. When GPS measurements are unavailable (such as indoors or close to buildings), measurements from the camera can be used to control the drift of the IMU.

This paper demonstrates real world results from a low cost GPS, IMU and camera. A u-blox ANTARIS 4 GPS receiver is used along with a Microstrain 3DM-GX3-25 IMU and Canon IXUS 750 camera. Data is collected in an outside area so that GPS measurements are constantly available and can be used to analyse the accuracy of the system when GPS measurements are removed from the filter. The position accuracy when GPS measurements are unavailable is demonstrated to be better than one metre per minute over a period of 6 minutes. This is significant since it enables a performance suitable to be used for indoor navigation applications. The characteristics of the IMU position error growth are investigated and demonstrated to be largely due to heading drift and scale errors caused by incorrect camera height. Knowledge of these characteristics is important since it enables future research to address these issues directly.

Details of the algorithm are described along with a consideration of the current limitations of the algorithm including computational requirements and use in low light areas. These issues are investigated and potential solutions are identified to improve efficiency and enable better performance in low light where the acquired images are more noisy and may contain motion blur. The developed system is shown to be a promising innovation for indoor navigation as it makes use of sensors on the handheld device rather than requiring sensors to be mounted elsewhere such as the user´s foot (where zero velocity measurements can be used but at the expense of needing an inconvenient additional sensors and communications). Furthermore the algorithm makes use of sensors that are already available on modern smartphones.

[Return to Program]

Session E2, Alternate #1

Experimental Validation of Foot to Foot Range Measurements in Pedestrian Tracking
M. Laverne, M. George, D. Lord, A. Kelly, T. Mukherjee, Carnegie Mellon University

We present an experimental validation of the usefulness of shoe-to-shoe range sensors in pedestrian tracking. Most foot mounted pedestrian tracking systems make use of zero-velocity updates to free inertial navigation. The principal source of error in these systems is heading and gyro bias drift, which are only partially corrected using zero velocity measurements. Previous work has shown, in simulation, the potential for shoe-to-shoe range measurements along with independent inertial sensors on each foot to reduce these remaining heading and drift errors. We present a system that implements this idea using MEMS IMUs and off-the-shelf sonar range finders. Significant accuracy improvements, when compared to the conventional approach, are observed in a variety of pedestrian tracking scenarios.
Pedestrian tracking refers to the problem of calculating the position and orientation of walking individuals with wearable devices. It is generally approached in one of two ways. Pedometry approaches count steps and measure heading and step distance to resolve position. Inertial navigation approaches implement a full six degree-of-freedom inertial solution at the foot and use each footfall to reset accumulated error. The system and results described herein are of the second type. Pedestrian tracking can be used to provide situational awareness for first responders, to target advertising, to map resources or buildings, to guide the visually impaired in addition to many other applications. It is a technology of interest across a number of domains.

A wearable pedestrian tracking system is described that incorporates sensor fusion algorithms with off-the-shelf and custom sensing along with embedded computing and power sources. Results verify the, now well known, importance of regular zero velocity updates at each step during the stance phase of walking. Such updates alone, reduce the time dependence of position error variance from cubic to linear, when assessed independently of orientation effects. In addition to zero velocity updates, we demonstrate the usefulness of range measurements between left and right shoes when they both contain an IMU. The range measurement is shown to remove most of the remaining heading and heading gyro drift. This improves the heading and positioning error by up to an order of magnitude.

An extended Kalman filter is developed in the traditional complementary inertial navigation configuration, except that both left and right feet are tracked with independent IMUs. Periods of zero velocity are inferred from acceleration signals and corrections are applied independently on each foot. A sonar sensing system is mounted alongside each IMU to measure range between the feet. This is used by the tracking filter to simultaneously correct errors on both sides. In experiments without this range measurement, heading error grows linearly in time, as a consequence of gyro drift and dynamic response. This leads to position error growth linear in time along straight lines. The addition of the range measurement reduces the heading error drift rate by up to an order of magnitude. The remaining trend is still generally linear in time, dependent on the remaining systematic errors. The system operates in a local coordinate frame that can easily be geo-located with the addition of initial position and north relative heading.

A variety of COTS inertial sensors have been tested in field trials, the results described here use a pair of tactical grade MEMS IMUs. The tracking filter provides three axis position, velocity and orientation as well as IMU calibration data for each IMU. Tests in an industrial building show that the user can be tracked through open spaces, into and out of rooms and up and down stairs accurately. One current limitation for indoor use is vertical motion in lifts. Results in outdoor scenarios demonstrate that the system works on a variety of surfaces and is on track to reach program accuracy goals. The system can be used to seamlessly transition from indoor to outdoor navigation.

[Return to Program]

Session E2, Alternate #2

Context Aware Mobile Personal Navigation Services Using Multi-Level Sensor Fusion
S. Saeedi, N. El-Sheimy, X. Zhao, Z. Syed, University of Calgary, Canada

Due to the rapid developments in wireless communications, mobile computing power, and positioning technologies (such as GPS), personal navigation services are coming standard on most of the mobile devices such as smarthphones. Human movements make the personal navigation system (PNS) a challenging topic which is different from other navigation platforms in a number of ways: The personal navigation includes frequent changes of speed, orientation and position that cannot be constrained to predefined paths (i.e. roads) as in car navigation. Unlike other navigation systems, a mobile device is not held in a fixed position and can spontaneously move by the user. Moreover, user´s mobility necessitates an adaptive behaviour according to changing circumstances such as in-vehicle or on walk modes. Therefore, using customized and context-aware navigation services which are capable of detecting the device status and user activity in specific time and location is necessary for various aspects of personal mobile navigation services. Context-aware systems take into account contextual information in order to adapt their operations to the current situation without explicit user intervention. For example, if the user is walking in an indoor environment such as a mall, the navigation system can load the plan of that building for better way finding. The main motivations encouraging the addition of context information to mobile navigation includes: limitations in mobile devices (e.g. computing power, displaying capabilities, user interfaces, etc.), and popularity of smartphones with several built-in sensors, such as accelerometer, GPS, and camera which produce a vast amount of information. Therefore, providing context-aware and adaptive navigation techniques significantly improves service productivity and usability.

Designing a context-aware personal navigation system is quite challenging topic which has been explored in several researches. The main issue in such systems is detecting available context information using embedded mobile sensors in an implicit way. Consequently, it needs computational intelligence such as artificial neural network (ANN) or support vector machine (SVM) to recognize and inference context information from integration of embedded motion and location sensors. The proposed system will detect and track user location and activity modes (e.g. walking, stationary, driving, etc.) and mobile device´s placement (e.g. in hand, on the belt, etc.) to find the most appropriate navigation solution. The context detection algorithm proposed in this study is based on a multi-level sensor fusion algorithm which will improve the current intelligent navigation context detection solutions in the following ways:  Low-level integration of multi-sensor data coming from different device sensors such as accelerometer and gyroscope using data mining and pattern recognition techniques (i.e. ANN);  High level information fusion to detect context information from multiple information sources, such as historical data, intelligent traffic system and user constraints using knowledge discovery techniques (i.e. fuzzy inference engine).

To investigate capabilities of adaptive computing, a context-aware pedestrian navigation system is developed which uses various context data (such as time, location and user activity). Extensive pedestrian field tests have been performed using a portable prototype device which has been developed in Multi Mobile Sensor System research group in University of Calgary as well as iPhone4 smarthphone. First, training datasets for accelerometer and gyro signals were collected and pre-processed for calibration and noises reduction. Ten users were asked to perform various motions such as walking, running, climbing the stairs, or driving. In this study no assumption is made about how users carry the PNS; so, users carry the device with different orientations in various and convenient places such as in hand, in pocket, in bag or on belt. Then, feature extraction and selection is applied to find the relevant and independent set of feature for classification algorithm. Since, there are no theoretical guidelines that suggest the appropriate features for segmentation, various features have been examined such as time-domain, frequency domain and orientation independent features. Next, the selected set of features extracted from pre-processed data, are used as inputs for training the classifier. Based on our previous research, a recognition algorithm based on support vector machine (SVM) has been initiated for context detection. This algorithm has superior performance for modelling non-linear classification model and dealing with accelerometer and gyroscope data for activity recognition. The accuracy of the recognition module is exceeded 90% when the training and testing data were from the same user and 78% when a new user is exposed to the system.

To make the context information ready for applications, handle the uncertainty of the recognized activities using data driven methods, remove the conflicts and preserve consistency of detected context, fill the gaps, and fuse various sources of information, a context reasoning module has been used. Context reasoning consists of context Knowledge Base (KB) and context reasoning engines. Sensed and inferred context data can be converted to useful information according to the inference rules in a KB. The context reasoning which uses a decision level fusion such as fuzzy reasoning improves efficiency of context detection algorithm by applying new rules which is acquired from various source of information such as historical context information, expert knowledge, user preferences or constraints. The proposed system has been applied in several navigation applications such as context-aware pedestrian dead reckoning, context-aware tourist navigation, adaptive visualization for navigation services, selecting the best set of sensors and solutions based on the user´s context information.

[Return to Program]

Session E2, Alternate #3

A Smart Phone Based PDR Solution for Indoor Navigation
R. Chen, L. Pei, Y. Chen, Finnish Geodetic Institute, Finland

Background Navigation is now becoming a well-known application in smart phones. One of the enable technologies of this unique mobile application is the positioning technology. Most smart phones are embedded with low-cost navigation sensors such as GPS receiver, accelerometer, digital compass, and gyros. In addition to these low cost sensors, RF signals from WLAN (Wireless Local Area Network), Bluetooth, RFID (Radio Frequency Identification) and cellular networks are also available in smart phones. With the embedded navigation sensors, especially the GPS(Global Positioning System)receiver, it is not a challenge task to locate the smart phone whenever an open sky is visible. However, it is still a challenge task to locate the smart phone in challenge environments such as indoors.
Objectives This paper introduces a PDR (Pedestrian Dead Reckoning) positioning solution for indoors. The solution requires no additional hardware than a low cost accelerometer and a digital compass embedded in a smart phone (Nokia 6710). It is an instant solution that requires no additional training phases for e.g. establishing the step-length model and the heading error model. The user can start navigation by entering his/her height information and selecting his/her initial location from a building layout or a 3D building model installed in the smart phone (e.g the main entrance of a building).

Methodology As we know, step detection, step-length estimation and heading estimation are the three fundamental elements in a PDR solution. In our solution, step detection is derived from the real-time measurements of the accelerometer, while the step length is estimated with an empirical model developed in this paper. In this empirical model, the step length is a function of the height of the pedestrian and the step frequency as follows:

SL = 0.7 + a(H-1.75) + b(SF-1.79)H/1.75

where SL is the step length to be estimated, H is the height of the pedestrian, SF is the step frequency estimated in real-time with the measurements of the accelerometer. The coefficients a=0.371 and b=0.227 are the two parameters of the model, while 0.7, 1,75 and 1,79 are constants representing the initial step length, height and step frequency. (The selection of these constants is discussed in detail in the paper). The model parameters a and b were estimated from 33 walking scenarios of 11 peoples on a surveyed baseline. The heights of the testers who contributed the step lengths for training the model range from 1,58 to 1.93 meters (5 women and 6 men). The minimum step length used for training the model is 0.56 meters, while the maximum step length is 0.86 meters.

For heading estimation, the building layout information and user motion patterns (e.g. stop, steady walking pace, U-turn) are used to constrain the final heading estimation. The user motion patterns provide additional information to discriminate whether the reading changes of the digital compass is caused by ambient disturbance or by turning of walking direction. For example, a U-turn will typically not happen when a user walking at a steady pace. He/she has to slow down before making a U-turn. Any large reading changes from the digital compass can be ignored in the process of steady walking because it is most probably caused by the ambient disturbances. These two constraints are extremely important for matching the headings to the correct walking directions. It reduces the impact of the large errors in the heading measurements to the PDR solutions. The user motion patterns were estimated with the real-time measurements of the accelerometer.

Field Tests and Results The performance of the proposed solution has been evaluated based on the field tests carried out in the office buildings of the Finnish Geodetic Institute. The test environment is a typical office environment with the walking distance of 173.4 meters along corridors and offices. The NovaTel SPAN GPS/INS system was used in the test to provide the reference tracks. Three pedestrians with the heights of 1.71m, 1.77m and 1.80m were involved in the test.

For evaluating the performance of the proposed empirical step-length model, two different solutions were estimated, one with a constant step length of 0.7 meters, while the other with the step lengths estimated with the proposed empirical model. The error of the travelled distance is about 9.2% for the constant step length solution, while it reduces to 3.4% for the solution based on the step lengths estimated with the empirical model.

For evaluating the performance of the PDR solution, two solutions were estimated, one with the headings constrained by building layout and user motion patterns, while the other with the original heading readings from digital compass (corrected with magnetic declination). The RMS of the horizontal error distance is about 1.8 meters for the solution with headings constrained by building layout and user motion patterns, while that for the un-constrained solution is 9.2 meters.

Conclusions This paper introduced a PDR solution based on the embedded sensors in smart phones. It is an instant positioning solution without any additional training phase by adopting an empirical model for step length estimation and applying building layouts and user motion patterns to constrain the heading estimations. The solution has been evaluated by a field test with a walking distance of 173.4 meters along corridors and offices in a typical office environment. The performance of the empirical step length model is about 3.4% in terms of error of travelled distance, while the accuracy of the PDR solution is about 1.8 meters in terms of RMS of the horizontal error distance.

[Return to Program]

Session E2, Alternate #4

Pedestrian Navigation with INS Measurements and Gait Models
Y. Cui, K.B. Ariyur, Purdue University

Today the Global Positioning System (GPS) is widely used in the estimation of position. But the GPS signal is not always available and not precise in some certain case. For pedestrian navigation applications, daily non-GPS systems mainly use inertial measurement units (IMUs), which are more portable and potentially inexpensive. However, the bias or drift in the process of inertial measurement largely limits the precision of position and attitude estimation when integrated directly from accelerations and angular rates. In our study, we have designed an integrated system to analyze the data collected from a MicroStrain Inertial Measurement Unit. For convenience and comfort, the inertial measurement instrument in our experiment is strapped at the middle of the beltline at the back to collect data.This is commonly considered closest to the center of gravity of a person. From frequency domain analysis, the fundamental frequency of walking is clear enough which shows the different stepping periods, and the noise is also easily seen from the spectra. Thus, in the integrated system, a Kalman Filter (KF) is applied first to reduce the noise, especially in the measurement system. The filtered angular rate is then integrated to the three by three rotation matrix, to make an output of walking directions, as well as the attitudes. The mainly auxiliary part to correct the estimation of position is the application of human gait model. From the investigated former results, the dynamic gait for individuals can be expressed clearly as a relationship between stride length and stride frequency. It is a basic characteristic of human walking and running. Here, we perform several series of experiments again to obtain the correct functional form of this relationship. After adding a non-zero constant in the formula instead of a sole power function, the updated curve of simulated result between stride length and stride interval fits the experimental data much better than before. Also we can know the variance of this method by analyzing the confidence interval of this relationship. Having the relationship in human gait model, both walking and running modes are covered by the function. Thus, the estimation of position can be corrected in each step by integrating both the results from integration of acceleration and the gait model. When detecting each step of human walking or running, we use the methodology of detecting the zero-crossing points from the compensated acceleration in vertical direction. After filtering the candidate zero points, which means potentially a moment that the force from the ground balanced by gravity, some false detections need to be filtered again to obtain the satisfied result. The idea here is to use the human gait again. Since human cannot run in a very large frequency, commonly not far beyond 3Hz, we can neglect some zero points if the time interval between them is very small which means oscillations may happen. Having found all the correct points when lift off (LO) and touch down (TD) events, we have produced an impulsive function illustrating two phases (on stance and on flight) in each stride interval very well. We have build up several experiments for human walking and running process and analyze by the integrated system. The typical experiment is implemented by walking back and forth in a straight line, as well as walking around a square closed-loop. In the square loop experiment, a close loop having a total length of 120 meters is set up. The pedestrian walked or ran in clockwise (CW) and counter-clockwise (CCW) then return to origin. Having estimated from the method, our most current result shows that overall drift can be minimized to below 4% and even 1.5% in one direction. Moreover, we are improving the system by investigating on the elimination of initial drift from IMUs by the use of rotation transformation matrix, as well as the application of magnetometer. By detecting each consecutive two uncompensated gravity vectors, we can calculate the changing of rotation matrix in which three angles can be used as an assistance to estimate the initial drift caused by the gravity in three directions and make a better initial compensation. The magnetometer is another way of illustrating the angle rotated from the origin in three directions, but is limited in some area especially has large interference. The results from the outside experiment are more precise than the indoor experiments because of cleaner magnetometer readings. We have also performed experiments with other mounting positions of the inertial unit on the pedestrian for comparison. The result from this integrated method indicates that the drift can be limited below some certain percentage. Based on the precise results from our experiments, we can improve this methodology a lot and apply this method to the area of pedestrian walking estimation, soldier and firefighter tracking, and urgent rescue.

[Return to Program]