MapGENIE: 基于众包数据的增强语法室内地图构建方法

MapGENIE：Grammar-enhanced Indoor Map Construction from Crowd-sourced Data

 

        位置服务在室外环境中已得到了广泛应用，但在室内环境中还不可用。主要有两个方面的原因：第一，没有支持移动设备的现成的室内定位系统；第二，在大部分建筑中缺乏面向公众的室内地图数据。同时，存在大量的劳力成本，使得有效的创建室内地图仍然面临许多挑战。

        作者提出的MapGENIE方法解决了室内制图的问题，即通过搜集室内建筑环境中行人的运动轨迹自动的构建室内地图。由于通过行人移动设备从后台搜集轨迹数据，避免了传统室内制图过程中花费大量的劳力成本，同时能够提高室内地图的有效性。为了改进地图构建过程，MapGENIE利用建筑物内部信息并通过语法编码建筑结构信息。该方法在室内制图过程中仅需要小量的轨迹数据而不需要用户的参与。

        为了测试MapGENIE的性能，作者实现了一套基于Android的系统，通过志愿者用绑在脚上的IMU搜集轨迹数据。与单纯的基于轨迹的方法相比，利用语法的方法能够识别出建筑物中四倍的房间数，同时在检测到房间的大小时错误率也更低。

 

      Abstract-While location-based services are already well established in outdoor scenarios, they are still not available in indoor environments. The reason for this can be found in two open problems: First, there is still no off-the-shelf indoor positioning system for mobile devices and, second, indoor maps are not publicly available for most buildings. While there is an extensive body of work on the first problem, the efficient creation of indoor maps remains an open challenge.

      We tackle the indoor mapping challenge in our MapGENIE approach that automatically erives indoor maps from traces collected by pedestrians moving around in a building. Since the trace data is collected in the background from the pedestrians' mobile devices, MapGENIE avoids the labor-intensive task of traditional indoor map creation and increases the efficiency of indoor mapping. To enhance the map building process, MapGENIE leverages exterior information about the building and uses grammars to encode structural information about the building. Hence, in contrast to existing work, our approach works without any user interaction and only needs a small amount of traces to derive the indoor map of a building.

      To demonstrate the performance of MapGENIE, we implemented our system using Android and a foot-mounted IMU to collect traces from volunteers. We show that using our grammar approach, compared to a purely trace-based approach we can identify up to four times as many rooms in a building while at the same time achieving a consistently lower error in the size of detected rooms.

System architecture showing the backend system and its inputs to the individual components.

 

Overview of the Trace-based Modeling component

相关工作

       大多数室内制图方法基于不同的SLAM原理，SLAM技术源自机器人领域。近年来，由人员进行操作微型激光扫描仪【13】或微软Kinect【14】的SLAM方法逐渐兴起。为了替代需要人工参与的扫描技术，出现了利用定位轨迹进行制图的方法，其中需要用到低成本泛在可用的硬件。系统仅利用轨迹数据来构建室内地图，

       类似的工作比如 CrowdInside [2] , FootSLAM [3] 和 SmartSLAM [15]。其中FootSLAM 利用绑在脚上的IMU传感器来构建可行走区域的室内地图，不区分走廊或者房间。为了不受复杂的外部IMU的约束，CrowdInside and SmartSLAM利用智能手机内置的传感器获取用户轨迹数据。然而，SmartSLAM只从结果数据集中构建走廊结构。而CrowdInside一方面需要沿着房间墙壁行走的大量轨迹数据以便得到较好的结果，另一方面，将房间构建成一种alpha形状（alpha shapes），而没有考虑室内建筑常识，如平行、矩形、重复等特征。

       文献【16】中提出的方法结合手机传感器和Wi-Fi指纹来学习走廊布局，以及区分不同的矩形房间。但对于精确重建室内结构（比如重复结构）的问题该方法也没有很好的解决。在人造建筑中，由于平行和矩形是最主要的规则，需要重建方法都是基于Manhattan World 约束【17】。另外还包括重复性或者建模更多一般约束。其中形式化语法（formal grammars）在多年前已经成功应用在了建模几何结构方面。但文献【18】仅集中在线性结构，比如通过 Lindenmayer-systems (Lsystems)仿真植物的生长。文献【5】和【6】验证了语法在重建街道路网和建筑外壳方面的有用性。在建模室内建筑方面，文献【19】提出了一种合适的分割语法，但没法应用在从不准确的观测数据进行重建方面。

 

RELATED WORK

Most approaches for indoor mapping build on different flavours of the Simultaneous Localization and Mapping (SLAM) principle, originating from robotics. Recently, also human-operated SLAM approaches have emerged which employ miniature laser scanners [13] , or the Microsoft Kinect [14]. Instead of using scanning techniques that require manual effort, the idea of using position traces, which may be acquired using low-cost ubiquitously available hardware, was proposed. Systems employing this data as the sole base for the reconstruction of building interiors are described in works like CrowdInside [2] , FootSLAM [3] and SmartSLAM [15]. FootSLAM-as in our approach, using a foot-mounted IMU reconstructs the building’s interior as a map of walkable areas, not distinguishing between hallways or rooms. Instead of being constrained to a dedicated external IMU, CrowdInside and SmartSLAM employ the set of sensors found in modern smartphones. However, SmartSLAM merely reconstructs hallway structures from the resulting data. CrowdInside, on the one hand, requires a large amount of traces following the room walls in order to function well and, on the other hand, reconstructs the rooms as alpha shapes, not taking knowledge about common features of interior architecture like parallelism, rectangularity, or repetition into account. Following the evaluation, CrowdInside needs 290 trace segments to fully reconstruct all corridor areas and the 12 rooms in the floor plan used in the testbed. The system presented in [16] uses a combination of smartphone sensors and WiFi fingerprints to learn hallway layouts as well as to distinguish different rectangular rooms. The authors state that the system needs only 20 data points per floor plan to converge, while delivering an average room position accuracy of 91 %, but a room area estimation error of 33% and a room aspect ratio error of 24%. The exact reconstruction of, e.g., repetitive structures is also not tackled by this approach. Due to parallelism and rectangularity being the most prominent rules used in man-made construction, many reconstruction approaches build on the Manhattan World constraints [17]. To further include, e.g., repetition or to model more general constraints, formal grammars have been applied successfully to the modeling of geometric structures for several years. While [18] focuses on line structures by, e.g., simulating growth processes of plants through Lindenmayer-systems (Lsystems), [5] and [6] proved the usability of grammars for the reconstruction of street networks and building shells. In terms of procedural modeling of building interiors, the authors of [19] present an appropriate split grammar, however, without the possibility of its use in the reconstruction from erroneous observation data.

 

Philipp D, Baier P, Dibak C, et al. Mapgenie: Grammar-Enhanced Indoor Map Construction From Crowd-Sourced Data[C]// Pervasive Computing and Communications (PerCom), 2014 IEEE International Conference on2014:139 – 147.

 

References

[2] A. Moustafa and Y. Moustafa, "Crowdinside: Automatic construction of indoor floorplans," in Proc. Con! Advances in Geographic Information Systems (SIGSPATIAL), 2012.

[3] M. Angermann and P. Robertson, "Footslam: Pedestrian simultaneous localization and mapping without exteroceptive sensors – hitchhiking on human perception and cognition," Proc. of the IEEE, vol. 1 00, pp.1 840-1 848, 2012.

[5] P. Miiller, P. Wouka, S. Haegler, A. Ulmer, and L. Van Gool, "Procedural modeling of buildings;' ACM Trans. Graph. , vol. 25, pp. 6 1 4–623, 2006.

[6] Y. I. H. Parish and P. Miiller, "Procedural modeling of cities," in Proc. 28th Annu. Con! Compo Graph. and Interactive Techniques, ser. SIGGRAPH ' 0 1 . New York, NY, USA: ACM, 2001 , pp. 301-308.

[13] M. Bosse, R. Zlot, and P. Flick, "Zebedee: Design o f a spring-mounted 3-d range sensor with application to mobile mapping," IEEE Trans. Robotics, vol. 28, pp. 1 1 04–1 1 19, 2012.

[14] R. A. Newcombe, A. J. Davison, S. Izadi, P. Kohli, O. Hilliges, J. Shotton, D. Molyneaux, S. Hodges, D. Kim, and A. Fitzgibbon, "KinectFusion: real-time dense surface mapping and tracking," in Proc. Symp. Mixed and Augmented Reality (ISMAR), 2011 .

[15] H. Shin, Y. Chon, and H. Cha, "Unsupervised construction of an indoor floor plan using a smartphone," IEEE Trans. Syst., Man, and Cybernetics, C: Applicat. and Reviews, vol. 42, pp. 889-89 8, 2012.

[16] Y. Jiang, Y. Xiang, X. Pan, K. Li, Q. Lv, R. P. Dick, L. Shang, and M. Hannigan, "Hallway based automatic indoor floorplan construction using room fingerprints;' in Proc. Joint Con! Pervasive and Ubiquitous Computing ( UbiComp), 2013.

[17] J. M. Coughlan and A. L. Yuille, "Manhattan world: Compass direction from a single image by bayesian inference;' in Proc. 7th IEEE Int. Con! Compo Vision, vol. 2, 1999, pp. 941-947.

[18] P. Prusinkiewicz and A. Lindenmayer, The algorithmic beauty of plants. Springer New York, 1 990.

[19] G. Groger and L. Pliimer, "Derivation of 3D indoor models by grammars for route planning," Photogrammetrie-Fernerkundung-Geoinformation, vol. 2010, pp. 1 93-210, 2010.