Send the link below via email or IMCopy
Present to your audienceStart remote presentation
- Invited audience members will follow you as you navigate and present
- People invited to a presentation do not need a Prezi account
- This link expires 10 minutes after you close the presentation
- A maximum of 30 users can follow your presentation
- Learn more about this feature in our knowledge base article
Do you really want to delete this prezi?
Neither you, nor the coeditors you shared it with will be able to recover it again.
Make your likes visible on Facebook?
Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.
Jigsaw: Indoor Floor Plan Reconstruction
Transcript of Jigsaw: Indoor Floor Plan Reconstruction
A ﬂoor plan reconstruction system that
leverages crowdsensed data from mobile users.
Accurate coordinates and orientations of indoor landmarks.
Insufficient “anchor points”.
EECS School, Peking University, China
Ruipeng Gao, Mingmin Zhao, Tao Ye,
Yizhou Wang, Kaigui Bian, Tao Wang,
ECE Dept., Stony Brook University
MobiCom’14, September 7-11, 2014
Lack of indoor floor plans Indoor localization sporadic.
Jigsaw: Indoor Floor Plan Reconstruction
via Mobile Crowdsensing
Effort - intensive and time - consuming
Need to hire dedicated personnel.
Complementary strengths of vision and mobile techniques
Use optimization and probabilistic formulations.
1. Landmark modeling
Extract sizes and coordinates of major geometry features of POI
1. Extract landmark’s major contour lines
Connecting points of
3. Detect connecting points of wall segments.
Set of Images
2. Project 2D lines into 3D
Structure from Motion (SfM)
Generates (in the LOCAL coordinate system) :
• a “cloud” of 3d points representing the exterior shape of the object;
• the location where each image is taken
Vanishing line detection
Given an image, detect orthogonal line segments of the object
2. Landmark placement
INPUT: Landmark models in local coordinate systems
OUTPUT: Landmark models on a global coordinate systems
Landmark placement process
1. Obtain pairwise spatial relationship between adjacent landmarks
2. Place adjacent landmarks on the common ground
Spatial Relation Acquisition
Click- Walk -Click (CWC)
Spatial relation acquisition
Spatial relation acquisition-WalkCompass
Gyro-compass rotation recognition
Multiple distance and orientation constraints
3. Map augmentation
INPUT: Landmark models on a global coordinate systems
OUTPUT: Final floor plan
(a) two nearly collinear segments
CWC inside one room
determine initial/final locations
Two camera locations as anchor points
. use trajectories to build an occupancy grid map.
. Thresholding and smoothing.
a. Get Landmark configuration
b. Form external boundary of hallway
c. Determine camera position
d. Determine trajectories
e. Build occupancy grid map
f. Binarization with a threshold
g. Smoothing Alpha-shape
(b) two nearly perpendicular segments
(c) two nearly
(a) Example scenario
(b) convex hull of all wall segments
(c) one possible output of the greedy method
(d) minimal weight matching using distance as weight
(e) our minimal weight matching method.
3 stories of malls: 150x75m and 140x40m
8,13,14 store entrances as landmarks
150 photos for each landmark
182,184,151 CRC measurements
24 CWC measurements in story 3
96,106,73 user traces along hallway
~7 traces inside each store
several assumptions not always found in real world.
Miss a few small-sized stores
RMSE and maximum error: 4x of Jigsaw
Hallway shape: ~30% less than Jigsaw
Precision~64%, Recall~48%, F-score~55%
Results of CrowdInside++
Wall segment detection accuracy: 91.7% 88.2% 100%
Wall segment detection precision: 100 % 100 % 100%
Not detected segments due to extreme angles.
100-150 images for each landmark are appropriate.
Store position error 1-2m
Store orientation error 5-9 degrees
Precision~80%, Recall~90%, F-score~84%
25.6% 28.3% 28.9%
Small considering some parts of room not accessible.
Floor plan construction
Reconstructs users’ mobile trajectories, but used many “anchor points” .
Jiang et. al
Detect similarities in WiFi signatures between diﬀerent segments to ﬁnd their adjacency.
Uses WiFi signals, but it uses locations where the trend of WiFi signal strength reverses
direction as anchor points.
Uses mobile trajectories as well using foot-mounted IMU.
Simultaneous Localization And Mapping :
Too many sensors, odometry, gyroscope, depth/stereo cameras and laser rangers.
3D construction in vision
Need continuous intervention
Plans are essentially 2D
Localization with vision techniques
Localization of user
Produces plans of complex indoor environments
Solves lack of ﬂoor plans at service providers.
Reconsruct floor plans from mobile users’ data,
Avoiding the intensive eﬀorts and time needed in business negotiations or environment surveys.
Reasonably complete and accurate locations/orientations of landmarks, hallways and rooms.
Antonio Reyes Lúa
Luis A. González G.