Source-linked AI summary
CrowdInside: Automatic Construction of Indoor Floorplans
Moustafa Alzantot, Moustafa Youssef
TL;DR
CrowdInside tackles the limited availability and costly maintenance of indoor floorplans by automatically constructing them from crowdsourced smartphone traces. It uses anchor points to reset inertial-trace errors and processes the corrected traces into building layouts and semantic features. In two Android testbeds, it achieved low anchor-detection error, substantially improved median distance error, and estimated detailed floorplans from relatively few trace segments.
Problem
Indoor floorplans are limited because existing systems rely on manual construction and updating, constraining the availability of maps for indoor location-based applications.
Method
CrowdInside crowdsources transparent smartphone sensor traces, resets inertial errors using indoor anchor points, and processes traces to estimate layouts, rooms, corridors, and points of interest.
Results
0.2% false positive rate and 1.3% false negative rate were reported for anchor detection; error resetting improved median distance error by more than 12 times, while detailed floorplans used as few as 290 segments.
Takeaways & Limitations
CrowdInside autonomously constructs detailed indoor floorplans from natural user movement without special infrastructure or prerequisite building-layout details.
Takeaways & Limitations
The authors identify higher-level semantic inference, including room types and owners and energy-efficiency aspects, as ongoing extensions.
Abstract
from arXiv · showhide
The existence of a worldwide indoor floorplans database can lead to significant growth in location-based applications, especially for indoor environments. In this paper, we present CrowdInside: a crowdsourcing-based system for the automatic construction of buildings floorplans. CrowdInside leverages the smart phones sensors that are ubiquitously available with humans who use a building to automatically and transparently construct accurate motion traces. These accurate traces are generated based on a novel technique for reducing the errors in the inertial motion traces by using the points of interest in the indoor environment, such as elevators and stairs, for error resetting. The collected traces are then processed to detect the overall floorplan shape as well as higher level semantics such as detecting rooms and corridors shapes along with a variety of points of interest in the environment. Implementation of the system in two testbeds, using different Android phones, shows that CrowdInside can detect the points of interest accurately with 0.2% false positive rate and 1.3% false negative rate. In addition, the proposed error resetting technique leads to more than 12 times enhancement in the median distance error compared to the state-of-the-art. Moreover, the detailed floorplan can be accurately estimated with a a relatively small number of traces. This number is amortized over the number of users of the building. We also discuss possible extensions to CrowdInside for inferring even higher level semantics about the discovered floorplans.
1. INTRODUCTION
CrowdInside addresses the scarcity and maintenance burden of indoor floorplans by automatically constructing detailed building maps from crowdsourced smartphone traces. It combines anchor-based trace correction with semantic floorplan estimation and evaluates the system on Android phones in a campus building and a mall.
- Motivation: Indoor floorplans remain limited because existing systems depend on manually building and updating maps, requiring substantial cost and effort.The paper frames this limitation as affecting the ubiquity and spread of indoor location-based applications.
- Approach: CrowdInside transparently crowdsources smartphone sensor measurements from people moving naturally inside buildings to infer floorplan and semantic information.The system targets general layouts, room and corridor locations and shapes, and points of interest such as elevators, stairs, and escalators.
- Contributions: CrowdInside aims to automatically estimate indoor floorplans for virtually any building through a crowdsourcing-based system architecture.The paper presents this architecture as a contribution toward broad-scale indoor mapping.
- Evaluation: The system estimates points of interest from inertial sensors and was implemented across four Android phone models in a campus building and a mall.The evaluated devices were Samsung Nexus S, Nexus One, Galaxy Ace, and Galaxy Tab.
- Approach: Anchor-based error resetting constructs accurate indoor motion traces from noisy commodity-phone inertial sensors.The technique uses detected anchor points to reset accumulated error.
- Floorplan estimation: CrowdInside separates corridors from rooms, clusters rooms, and uses computational geometry to identify room shapes.These processing stages support detailed floorplan estimation beyond the overall building outline.
2. SYSTEM DESIGN
CrowdInside collects smartphone sensor measurements from users and processes them into accurate motion traces for automatic indoor floorplan construction. Its design combines dead reckoning, step-based displacement estimation, and anchor-point detection to reduce trace errors before floorplan estimation.
- Data collection: CrowdInside crowdsources smartphone sensor measurements from users moving naturally inside buildings to infer layouts and semantic information.The system collects measurements from devices and processes them in the cloud.
- System architecture: The system has data collection, trace generation, and floorplan estimation modules, with the latter separating corridors from rooms and detecting room boundaries.
- Trace generation: Dead reckoning estimates current position from the previous position, traveled distance, and motion direction, using magnetometers or gyroscopes for direction and accelerometers for displacement.
- Trace generation: Accelerometer noise and gravity components can make displacement errors grow cubically with time, reaching 100 meters after one minute even with accurate foot-mounted inertial sensors.
- Trace generation: Step-based displacement estimation changes error growth from cubical to linear and is independent of phone placement because walking acceleration patterns are orientation-independent.
- Anchor-based error resetting: Anchor points with unique sensor signatures reset trace errors; the system uses GPS-based entrances and windows alongside inertial-based stairs, elevators, escalators, and room doors.These anchors also address errors in the trace starting point and displacement accumulation.
- GPS-based anchors: GPS duty cycling saves energy but introduces entrance-location ambiguity, which crowdsourcing reduces by averaging samples between the last GPS position and first signal loss.
3. FLOORPLAN ESTIMATION MODULE
The floorplan estimation module processes accurate motion traces to recover both the building’s overall shape and room-corridor details, including higher-level semantic information.
- 3. FLOORPLAN ESTIMATION MODULE: The module estimates two levels of floorplan detail: the overall building shape and room-corridor details.The section also discusses obtaining other higher-level semantic information.
3.1 Overall Floorplan Shape
CrowdInside represents user steps as a point cloud and uses alpha shapes to estimate overall indoor floorplan geometry, including concavities and holes that convex hulls miss.
- User steps are represented as points, and the system estimates a shape representing the combined point cloud.
- Alpha shapes capture building shape with high accuracy and generalize the convex hull concept.An alpha shape is a family of piecewise linear curves associated with a finite point set.
- The convex hull cannot represent concavities and holes in the floorplan, whereas the alpha shape can.
3.2 Detailed Floorplan
CrowdInside derives detailed floorplans by segmenting and filtering traces, classifying segments as rooms or corridors, clustering rooms, shaping regions, and estimating doors.
- Detailed floorplan construction combines trace segmentation, filtering, classification, clustering, door estimation, and final shaping and labeling.
- Trace preprocessing: Segments are separated at turns or pauses and short segments are filtered because they are not descriptive.
- Room–corridor classification: A tree-based classifier separates segments into corridors and rooms using timing, length, and neighboring-trace density features.Corridor segments are typically faster, longer, and denser than room segments.
- Room clustering: DBSCAN clusters room-segment centers using spatial and WiFi similarity to identify rooms, boundaries, and locations.
- Shaping: Alpha shapes are computed separately for each room and for the corridor point set to form the final detailed floorplan.Different rooms are displayed in different colors.
- Shaping: Further smoothing can make regions rectangular, but this may not work for general shapes such as concave corridors.
- Door estimation: Door locations are estimated by clustering intersections between corridor-type and room-type segments, using each cluster centroid as a door position.
3.3 Discussion
CrowdInside proposes attaching higher-level semantic labels to estimated floorplans, including room types, brands, or owners, using sensor, social, or user-provided information.
- The system can extend estimated floorplans with room or shop types, shop brands, and room owners.
- The detailed-floorplan pipeline estimates room doors as part of the semantic information attached to indoor layouts.
- Candidate labeling approaches include phone sensor fingerprints, social-network and visiting-pattern information, user games, and automatic group discovery.
4. EVALUATION
CrowdInside was evaluated on Android phones across a shopping mall and university-campus testbed, measuring anchor detection, trace accuracy, and floorplan construction.
- The evaluation covers anchor-point estimation, trace-generation accuracy, and floorplan-estimation accuracy in two testbeds.
- GPS-based anchors: Less than 1m entrance-position error was reached with 100 samples in the reported two-minute-duty-cycle experiment.
- GPS-based anchors: At a 6-minute GPS duty cycle, as few as 1200 samples were required for less than one-meter error with 95% confidence.
- Inertial-based anchors: Less than 0.2% false positives and 1.3% false negatives were achieved when classifying inertial anchor-point types.
- Trace generation: Up to 12 times enhancement in accuracy over the state-of-the-art was achieved using anchor-based error resetting.
- Floorplan construction: As few as 290 segments were required to obtain the full floorplan shape.A break near 150 segments occurred when traces began covering all rooms.
5. RELATED WORK
Prior indoor localization and mapping systems typically require existing floorplans, specialized infrastructure, or labor-intensive setup. CrowdInside instead uses commodity-phone inertial traces and indoor anchor points to construct both overall and detailed floorplans automatically.
- Most indoor localization systems are deployed in limited areas and assume that building floorplans already exist.
- Dead-reckoning enables ubiquitous phone-based tracking without prior setup, but accumulated error motivates step-counting and related corrections.
- Crowdsourced localization databases have focused on RF fingerprints rather than floorplan construction, and some require inconvenient manual user input.
- Traditional SLAM relies on sensors unsuitable for commodity phones, does not fuse multiple robots, and SmartSLAM produces corridor layouts without room details.
- CrowdInside distinguishes itself by using indoor anchor points to improve trace accuracy while automatically detecting floorplan outlines and detailed shapes.
6. CONCLUSION
CrowdInside autonomously constructs indoor floorplans from traces collected by users moving naturally, without special infrastructure or prior building-layout details. Evaluations show accurate anchor detection, substantially improved distance error, and detailed floorplans from relatively few segments, while higher-level semantic inference remains future work.
- CrowdInside autonomously generates user traces and estimates floorplans, identifying rooms, corridors, and doors without special infrastructure or prerequisite layout details.
- 0.2% FP and 1.3% FN rates were achieved for anchor-point detection across two Android-phone testbeds.
- More than 12 times enhancement in median distance error resulted from the proposed error-resetting technique.
- Detailed floorplans were estimated with as few as 290 segments, amortized across the building’s users.
- Future work includes inferring higher-level semantics such as room types, owners, energy-efficiency aspects, and user incentives.