Pedestrian Localization in Closed Environments

Jonáš Ševčík

► To cite this version:

Jonáš Ševčík. Pedestrian Localization in Closed Environments. 10th International Symposium on Environmental Software Systems (ISESS), Oct 2013, Neusiedl am See, Austria. pp.679-687, 10.1007/978-3-642-41151-9_64. hal-01457499

HAL Id: hal-01457499

https://inria.hal.science/hal-01457499

Submitted on 6 Feb 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Pedestrian Localization in Closed Environments

## Android Prototype

Jonáš Ševčík

Masaryk University, Faculty of Informatics, Brno, Czech Republic
jonas.sevcik@mail.muni.cz

**Abstract.** This research presents techniques suitable for pedestrian localization in closed environments using mobile devices without the need of GPS technology. The objective of this research is to design and implement a pedestrian localization system, which can be used directly without investments into building a support infrastructure and acquiring expensive devices. The research problem is that GPS signal is weak or absent in closed spaces, thus cannot be used to identify location. Several technologies, which are using mobile sensors, are used as part of the experimental methodology to implement the system. These include tracking of wireless networks, dead reckoning, step detection, and barcode scanning. These technologies were combined and coded in the Java programming language to form the localization system. Beside the technologies mentioned above, crowdsourcing is used for gathering environment data needed for calculation of location estimates. Currently, the implementation has been done for the Android platform, but it is designed to be universal, and can be expanded to other mobile platforms. Preliminary results of the prototype application report a positioning error (standard deviation) of roughly 2 meters.

**Keywords:** Indoor localization, Android, prototype, Wi-Fi tracking, step detection, dead reckoning, SMC filtering.

## 1 Introduction

Navigation throughout vast complex buildings e.g. hospitals or school buildings can be difficult even if the building is densely equipped with navigation signs. For acquiring location coordinates, the GPS can be used. This technique is commonly used in transportation and nowadays also in mobile phones to calculate coordinates on a virtual map. Even though, GPS tracking can be useful outdoors, it cannot be used indoors, because there is no direct visibility to GPS satellites [5].

The indoor environment positioning in comparison to outdoor positioning is problematic also for the reason that for meaningful localization it requires more accurate measurements. Where standard deviation of 10 meters may be sufficient outdoors, it may be insufficient indoors, due to the complexity of inner structure of indoor spaces.

In contrast to outdoor spaces, indoor environments offer systems other than GPS. Public buildings tend to have dense installations of WLAN infrastructure, which can be used for positioning.
Additionally, current mobile phones are not limited to perform localization only via GPS. They are equipped with various sensors such as magnetometer, linear accelerometer, gyroscope, and wireless network adapters. Even a low-end smartphone contains at least a magnetometer and an accelerometer. Therefore, they can be used as a sensor and computational devices for a localization system.

In order to achieve truly independent solution, we believe it must be as universal as possible. Therefore it is necessary to use only already present infrastructure (i.e. WLAN) and devices used for measurements being standard Android powered mobile phones. Even though we used Android devices, all the presented techniques are generally applicable to any mobile platform.

In this paper we will present an approach that combines an existing WLAN infrastructure and mobile device, which will be used as a pedometer, compass and computational device. We address, that using a mobile device in this way causes increased battery drain, and therefore there must be performed code optimizations for sensor handling, which are not the case of this study. The goal is to obtain and process all the sensor data locally. Main localization technique used is inertial navigation system. Mobile sensor fusion is used to provide position estimate, which is combined with WLAN positioning [1] and particle filtering [3] used to maintain a long term accuracy of this system. We enhance techniques presented in [4], where authors suggest a solution based on accelerometers mounted on shoe, which is only partially applicable to our approach, where we assume the user is holding the device in hand, thus we have to apply algorithms for filtering noise and false data generated by hand movement.

This work presents WLAN positioning and principles of gathering required data, sensor fusion and its application in dead reckoning, and particle filtering. Finally these techniques are combined into an Android pedestrian localization prototype. Subsequently, the prototype was tested for the positioning accuracy against ground locations. Achieved results were as accurate as those in [4], except our solution does not require additional hardware and is generally usable. The resulting system was shown to provide sufficient accuracy to locate user within a building. The paper concludes with recommendations for extensions and directions of further work.

## 2 Wi-Fi localization

The first technique is indoor tracking based on wireless networks. We decided not to use standard triangulation based on access point (AP) locations and signal regression, as instead, we use Received Signal Strength (RSS) fingerprinting, as presented in [1] to create a database of unified AP identifiers and their received signal strength, which is mapped to location coordinates. RSS measurements at an unknown location are then compared to the signal strength maps to estimate the receiver's location. This method proves to be useful, when the information about location of APs is not known.

RSS fingerprinting consist of two phases. Offline phase consists of fingerprint gathering. During this phase the database of RSS fingerprints is created. Fingerprint is symbolized as a pair (x, y), where x are coordinates in the real environment; y is a unique access point identifier and the strength of received signal measured in dBm.
During the online phase, the measured signal strength along with AP identifier are
compared against the database of gathered fingerprints. The best matching candidate
is chosen as an estimated location provider.

The phase of gathering fingerprints can be simplified as shown in [2]. This method consists of gathering a smaller amount of fingerprints and interpolating the gathered data to obtain the full map image. Measured map is triangulated using Delaunay algorithm.

The triangulation algorithm splits the area into non-overlapping triangle mesh,
where each location in the plane is as-signed three unique vertices of the triangle. Full
linear interpolation of the map can be recreated from the Barycentric coordinates of
the location in the triangle.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Interpolated RSS map with Delaunay triangulation</figcaption></figure>

Fingerprint gathering in offline phase is time consuming activity, because it must be
done accurately and time of taking one fingerprint should be, from our testing, at least
20 seconds. This amount of time is optimal for collecting enough data. To shorten
total sampling time, we implemented Wi-Fi fingerprinting as a crowdsourcing activi-
ty. Users are encouraged to perform measurements and upload them to our online
service, from where they can be distributed into other client applications. Users are
for their work awarded with more precise positioning capabilities.

3 Dead Reckoning

The second used technique is dead reckoning – a process of calculating current posi-
tion by using a previously determined coordinates, which are advanced by known
speed and course. We use dead reckoning in inertial navigation system, where initial
location is determined via WLAN fingerprinting. Alternatively, coordinates can be
encoded into a barcode, which when placed in to the position of those coordinates,
can be scanned by a camera and then decoded. Position tracking is done by calculating number of steps. Stride length and its deviation are calculated by letting user walk fixed distance 5 times as presented in [2]. Course of steps is determined by a compass.

Sensor data from mobile device cannot be used as they are to provide reliable measurements. We use magnetometer to obtain physical position of a device; gyroscope to measure rotational forces along device's three axes; and accelerometer to measure acceleration of the device. Unfortunately, all those sensors have their flaws. Magnetometer can be easily affected by external electro-magnetic and magnetic fields. If the magnetometer is not parallel to the Earth's surface, the z component (pointing downward) of the Earth's magnetic vector is projected into the x and y axes of the mobile device's magnetic sensor causing the compass to rotate when the device is tilted. Gyroscope measurements tend to cumulate errors as the device moves, and accelerometer measurements are influenced by Earth's gravity. However, all those flaws can be suppressed by fusion of all above mentioned sensors as described in [5]. Accelerometer-gyroscope fusion provides gravity and linear acceleration. Compass-gravity fusion provides compass tilt compensation. The gravity is already a derived measurement coming from the accelerometer-gyroscope fusion. Compass-gyroscope fusion provides orientation and external magnetic field.

Even though linear acceleration data do not contain gravity, they still need to be filtered to be used for further calculations. For filtering we use moving averaging. We use 2 pass moving average filter with window size of 0.2. This low-pass filtering smooths the signal and subsequently we calculate moving average with window size of 0.5. When it intersects with rising edge of the signal, we state the user made a step forward (we assume user does not walk backwards, and strafe left and right).

Fig. 2 shows signal filtering and step detection. Red line (bottom) corresponds to raw linear acceleration data measurement. Green line corresponds to filtered signal. Blue line represents moving average. Green dots (first 10) are positive steps. Red dots are false positive steps. To filter white noise and slight movements of hand we use threshold approach to discard any steps which might have been detected. We calculate accumulative signal power (ASP) and only those values are marked as positive, which ASP is higher than threshold value. Also, while continuously walking, elapsed time between 2 following steps cannot exceed 2 seconds.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Signal filtering</figcaption></figure>
# 4 Particle Filtering

The third technique is Sequential Monte Carlo filtering (SMC) [3]. It is modeling the state of a dynamic system by approximating the posterior density function by a set of random samples of the state vector while sequences of noisy measurements are made on the system. The computation of the SMC requires two models [3]:

1. System model – model describing the evolution of the state and time;

2. Measurement model – model relating the noisy measurements to the state.

Filter processes events from the step detector (step event, length estimate) and a probability density function from the Wi-Fi AP scans, which uses particles evenly spread in the probable location determined by RSS fingerprint database. These particles are set to motion with events generated by step detection. Consequently, those particles, which hypothetical motion leads through impassable obstacles, e.g. walls, are eliminated (Fig. 3). This results in improvement of location estimation.

<figure><img src="image_4.png" /><figcaption>Fig. 3. Particle elimination</figcaption></figure>

# 5 Implementation and Evaluation

## 5.1 Test Environment and Device

We chose hallway of university building, which was covered with a total of 6 APs used for public internet access. There were also present several devices transmitting Wi-Fi signal, but these were discarded from the measured sample due to the possible loss of accuracy. Prior to the test, we marked 11 locations such that distance between 2 adjacent points was 2.5 meters. The exact coordinates of marked points were placed into the system. Initial location was set programmatically (top-right circle in Fig. 4). We performed a circular walk taking 4 laps around selected markers (movement was done counterclockwise). After reaching a marked physical point, we took a sample, which coordinates were compared to the real coordinates of the marked point and
distance between these points was calculated. As a testing device we used Asus Nex-
us 7 tablet running Android 4.2.2 JellyBean. During testing the device was held in
constant height.

<figure><img src="image_5.png" /><figcaption>Fig. 4. Test route</figcaption></figure>

**5.2 Implementation**

The implementation of the positioning system was realized in three separate compo-
nents: RSS position estimation provider, pedometer, and particle filter. These are
encapsulated in an application service.

<figure><img src="image_6.png" /><figcaption>Fig. 5. Building overlay over Google Maps</figcaption></figure>

This service merges all components together to supply location data for UI compo-
nent. All the code was implemented in Java using Android API v8 and compiled us-
ing API v17 to assure the best possible performance. Google Maps API with custom
overlay was used for the visual presentation as seen in Fig. 5.

5.3 Evaluation

Evaluation aim was to determine accuracy of the standalone WLAN location estima-
tion, determine the accuracy of inertial navigation, and finally to compare both men-
tioned approaches.

To evaluate the gathered data, we compared user's position obtained from the fusion
of WLAN fingerprinting and dead reckoning to location estimate obtained only via
WLAN fingerprinting. All the data samples for both approaches were taken simulta-
neously at each marked location. Fig. 6 shows each of 44 recorded measurements.
WLAN estimate data are presented by the red line (top), fused location data are pre-
sented by blue line (bottom). Black vertical lines show start of the new lap.

<figure><img src="image_7.png" /><figcaption>Fig. 6. Position error over walked distance</figcaption></figure>

Arithmetic mean for WLAN fingerprinting is 8.6557 m, for fused location is 3.2023 m. Standard deviations are 3.1770 m, and 2.0911 m respectively. As seen from the graph, fused solution results into more stable and less erroneous location estimation than WLAN fingerprinting. Measured data show regular tendency in respect to lap location. Nevertheless, it is visible, that the error cumulates with travelled distance.

6 Conclusion

In this paper we have presented indoor localization system for Android devices com-
bining WLAN fingerprinting with pedometer made as a fusion of gyroscope, accel-
erometer, and magnetometer. Presented solution is platform independent and requires
no additional changes to existing Wi-Fi infrastructure. The only a priori requirements
are map materials and WLAN fingerprint gathering. The accuracy of the combined
system was quantitatively evaluated in a real building and shows that it is much higher than that of the fingerprinting alone.

Designed solution proved to be efficient enough to be used in crisis management. In case of a fire emergency it is crucial to provide escape strategies for effective emergency management. Map data can provide user with accessible information about water hydrants, fire extinguishers, and possible escape routes/emergency exits. The system can be easily extended to provide visual location of particular users, therefore it may be possible to show also positions of people connected to the system. This functionality can be used in 2 scenarios.

The first possible scenario presents a situation when a group of people is trapped inside a building due to the fire, which has closed all possible escape routes. Trapped people are unable to escape. Therefore a rescue team must strike in for the rescue. With indoor localization system it would be possible to make crisis managers aware of trapped people's positions inside the building, thus keeping count of endangered victims and rescuing them easily.

Second possible scenario represents a fire brigade fighting a fire in a vast building. It may be difficult for the rescue team to track positions of its members. Every individual can monitor other team members' position and proceed efficiently. Of course this functionality can be combined with all above mentioned features.

## 6.1 Future work

Further work should focus on estimating stride length using a neural network. Constant stride length results into cumulative error increase. Also, current solution filters false positive steps, caused by hand movement, by threshold approach. This should be substituted by focusing on the frequency of steps and acceleration growth. Sustained walking can be recognized by periodical frequency and even pitches in acceleration growth. Recognizing left leg from the right may also provide interesting results, when treated separately. Last but not least, future work should focus on extending recognizing changes altitude.

**Acknowledgments.** The coding of the base of the Android prototype was made by Michal Holčík. Further enhancements and map convertor were implemented by Adam Berthóty. All map data and their partial format conversion was kindly provided by Masaryk University Department of Passportisation.

## References

1. A. Chen, C. Harko, D. Lambert, and P. Whiting, "An Algorithm for Fast, Model-Free Tracking Indoors," ACM SIGMOBILE Mobile Computing and Communications Review, vol. 11 (3), pp. 48-58, July 2007.

2. S.Y. Cho, and C.G. Park, "MEMS Based Pedestrian Navigation System," Journal of Navigation, vol. 59, pp. 135-153, 2006.
3. M.S. Arulampalam, S. Maskell, and N. Gordon, "A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking," IEEE Transactions on Signal Processing, vol 50 (2), pp. 174-188, 2002.

4. K. Frank, B. Krach, N. Catterall, and P. Robertson, "Development and Evaluation of a Combined WLAN & Inertial Indoor Pedestrian Positioning System," 4th International Symposium on Location and Context Awareness, pp. 538-546, 2001.

5. R. Feliz, E. Zalama, and J.G.G. Bermejo, "Pedestrian tracking using inertial sensors," Journal of Physical Agents, vol. 3 (1), pp. 35-43, January 2009.

6. O. Woodman, R. Harle, "Pedestrian localisation for indoor environments." Proceedings of the 10th international conference on Ubiquitous computing. ACM, pp. 114-123, 2008.