A graph-matching approach to indoor localization

Abstract

Indoor localization provides for a much researched subject, as the complexity and size of many public buildings require extensive and properly designed methods to facilitate location specific processes. Indoor localization entails finding a qualitative description of the occupied area, that is human interpretable, rather than a quantitative position in Euclidean space. In other words, the context of an indoor environment has to be understood, such that a position can be transcended to a meaningful location. A space is defined as a mathematical structure with relational properties, to which all its members adhere. As a subset of space, topological space describes the relationships between (parts of) objects that do not change under continuous transformation. It further defines metric space, as a set where distances and angles between all of its elements are defined. Indoor space is then interpreted as a structure bounded by physical or functional elements, enabling human activities. It should entail the geometric place an actor is in, the topological structure that place is a part of, and the semantics giving the place meaning. Many indoor positioning methods have been developed, which can provide an actor with a relative geometric place. Most preferred are positioning systems not relying on a contingent system, which can be performed using a hybrid fusion of sensors embedded into a mobile device. Such a system found to perform sufficiently is VI-SLAM, simultaneously building a geometric place and tracking each pose and heading relatively. Its output is a mesh model, in which a viewshed of the indoor environment is built. From a mesh model, a topological structure can be derived in the form of its dual graph. Now to finalize this representation of indoor space which can be captured using a mobile device, it has to be enriched with a meaningful context. These semantics are generally stored in BIM models. Thus to transcend the position retrieved using SLAM to a location, is has to be matched with a BIM model, so that the appertaining semantics can be connected.
The method proposed provides for a possibility to perform graph-based indoor localization, by extracting a graph from both input sources and comparing them, in order to find a match. However different in nature and structure, both input sources can be converted to a graph of similar calibre, such that they can be tested for a match. All operations performed on the graphs are derived from spectral graph theory. The graph simplification and analysis is performed using the eigen spectrum of the graph Laplacian, and the match is performed by remapping the spectral graphs into a vector sub space using the eigen spectrum of the data covariance matrix. After a match between both graphs is found, the current position of the actor within the mesh model can be translated to the room found in the graph. This room is now connected to a room within the reference graph, for which the semantics are stored in the BIM. Returning these to the actor, a location description is formed.