Ubiquitous Indoor Localization and Worldwide Automatic Construction of Floor Plans

Moustafa Youssef, Moustafa Elzantout, Reem Elkhouly, Amal LotfyarXiv 2012 · OpenReview

TL;DR

This paper proposes a vision for a ubiquitous indoor positioning system (IPS) that leverages crowd-sourced data from smartphone sensors to automatically build a worldwide floor plan database. The core contribution is demonstrating the feasibility of this approach, particularly in automatically constructing floor plans and identifying areas of interest with high accuracy, paving the way for seamless indoor-outdoor navigation and location-aware applications.

What Problem Does This Paper Address?

While GPS is ubiquitous for outdoor localization, a comparable, seamless indoor localization system is still missing. Existing indoor localization technologies are often isolated, require specialized infrastructure, or are limited to specific areas with pre-existing floor plans. The authors aim to bridge this gap by creating a system that works globally, with minimal overhead, across diverse devices, and allows users to transition smoothly between indoor and outdoor environments. A key challenge identified is the lack of comprehensive, automatically generated indoor floor plans, which hinders the widespread adoption of technologies like WiFi localization.

Methods

The proposed IPS architecture is built around a crowd-sourcing approach, utilizing the embedded sensors in smartphones (accelerometers, compasses, cameras, WiFi, GSM). The system comprises several modules:

  • Signal Collection Module: Gathers raw sensor data with timestamps.
  • Floor Plan Construction Module: This is the focus of the paper. It includes:
  • User Trace Construction Module: Processes raw sensor data to estimate user velocity and displacement, combining it with compass data to create user traces within a building. This module employs a dead reckoning approach, using accelerometer data for displacement and magnetometer for direction. To combat error accumulation, it leverages a zero velocity update (ZVU) technique, essentially using the accelerometer as a pedometer. A finite state machine (FSM) is introduced for robust step counting, outperforming a variance-based method.
  • Area of Interest Detection Module: Classifies blocks within the floor plan into categories like offices, corridors, elevators, and stairs. This module uses features derived from user traces, such as average time spent in a block, average and variance of acceleration, correlation between accelerometer axes, number of turns, and WiFi/GSM signal strength. A C4.5 decision tree classifier is used for this task.
  • Location Information Database Builder Module: Constructs a fingerprint database for localization.
  • Location Determination Engine: Estimates user location based on collected signals and the fingerprint database.
  • User Interface Module: Handles user queries for location and floor plans.

The system leverages cloud computing for data processing and storage.

Datasets

The paper describes an experimental testbed in a single building floor plan covering 448m². Three users with Android phones (two Nexus One, one Samsung Galaxy S) were used. The experiments involved collecting sensor data (accelerometer, magnetometer, WiFi, GSM, GPS for synchronization) as users moved through the building. No specific public datasets were used; rather, the authors generated their own data through these controlled experiments.

Key Insights and Ideas

  • Crowd-sourcing as the key to ubiquitous indoor mapping: The paper strongly advocates for leveraging the vast number of smartphone users to automatically build a global floor plan database, overcoming the manual effort and cost associated with traditional methods.
  • Smartphone sensors are powerful enough for floor plan construction: The research demonstrates that raw sensor data, particularly from accelerometers and compasses, can be effectively processed to reconstruct user movement and identify distinct areas within a building.
  • Robust step counting is crucial for accurate dead reckoning: The development of a finite state machine-based step detection method significantly improves accuracy compared to simpler integration methods, mitigating error accumulation in dead reckoning.
  • Feature engineering is vital for area classification: Identifying relevant features from user traces (e.g., time spent, acceleration patterns, turns) allows for accurate classification of different indoor spaces.
  • Elevators and corridors are good synchronization points: The results highlight that these areas can be identified with high accuracy and can serve as reliable reference points for correcting local traces.

Key Results

  • User Trace Construction: Achieved a displacement error of less than 0.9m and an average error of less than 2.3% in estimating the number of steps.
  • Area of Interest Identification: Demonstrated up to 90% accuracy in correctly identifying areas of interest (offices, corridors, elevators, stairs).
  • Classifier Performance: Elevators and corridors were detected with zero false negative rates, and elevators and offices had zero false positive rates.
  • Block Size Impact: A block size of 0.7m was found to yield the best classification accuracy (90%).

Limitations and Future Work

Limitations:

  • Single Building Testbed: The experiments were conducted in a single building, and scalability to a worldwide, heterogeneous environment requires further validation.
  • Limited Sensor Usage: While phones have cameras and microphones, these were not utilized in the current testbed for area of interest detection.
  • Privacy Concerns: The paper acknowledges that user privacy is a significant concern for a 24/7 tracking system.
  • Hardware Variations: Dealing with the heterogeneity of smartphone sensors and their varying quality is a major challenge.
  • Robustness to Attacks: The system's vulnerability to data poisoning attacks needs to be addressed.
  • Energy Efficiency: Balancing accuracy with the energy consumption of continuous sensor data collection is critical.
  • Incentive Models: Encouraging users to contribute data for new buildings requires well-designed incentive mechanisms.
  • Phone Orientation: The impact of phone orientation on sensor readings needs to be fully compensated for.
  • Scalability: Handling the massive amount of data generated by a global system is a significant challenge.
  • Integration of Multiple Technologies: Seamlessly integrating various indoor and outdoor localization technologies is complex.

Future Work:

The authors identify several research directions:

  • Automating floor plan construction and fingerprint generation.
  • Seamless roaming between indoor and outdoor environments.
  • Addressing user privacy concerns through anonymization and user control.
  • Developing techniques to handle hardware variations and sensor fusion.
  • Improving system performance and energy efficiency.
  • Designing effective incentive models for crowd-sourcing.
  • Developing orientation-independent algorithms.
  • Investigating techniques for data reduction and search space pruning for scalability.
  • Integrating a wider range of localization technologies.
  • Exploring specific applications like enhancing first responder safety and location-aware social networking.

Summary updated

Abstract

Although GPS has been considered a ubiquitous outdoor localization technology, we are still far from a similar technology for indoor environments. While a number of technologies have been proposed for indoor localization, they are isolated efforts that are way from a true ubiquitous localization system. A ubiquitous indoor positioning system is envisioned to be deployed on a large scale worldwide, with minimum overhead, to work with heterogeneous devices, and to allow users to roam seamlessly from indoor to outdoor environments. Such a system will enable a wide set of applications including worldwide seamless direction finding between indoor locations, enhancing first responders' safety by providing anywhere localization and floor plans, and providing a richer environment for location-aware social networking applications. We describe an architecture for the ubiquitous indoor positioning system (IPS) and the challenges that have to be addressed to materialize it. We then focus on the feasibility of automating the construction of a worldwide indoor floor plan and fingerprint database which, as we believe, is one of the main challenges that limit the existence of a ubiquitous IPS system. Our proof of concept uses a crowd-sourcing approach that leverages the embedded sensors in today's cell phones as a worldwide distributed floor plan generation tool. This includes constructing the floor plans and determining the areas of interest (corridors, offices, meeting rooms, elevators, etc). The cloud computing concepts are also adopted for the processing and storage of the huge amount of data generated and requested by the system's users. Our results show the ability of the system to construct an accurate floor plan and identify the areas of interest with more than 90% accuracy. We also identify different research directions for addressing the challenges of realizing a true ubiquitous IPS system.
BibTeX
@misc{youssef2012ubiquitous,
  author = {Moustafa Youssef and Moustafa Elzantout and Reem Elkhouly and Amal Lotfy},
  title = {{Ubiquitous Indoor Localization and Worldwide Automatic Construction of Floor Plans}},
  year = {2012},
  eprint = {1204.3328},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1204.3328},
}

Loading related content...

Figure