Tim Samuelsson presents his Master's Thesis: Semantic Analysis of Indoor Floor Plans for Creation of Navigation Graphs, Thursday 28/11 at 13:15 in MH:333.

Abstract:
When developing systems for indoor navigation it is important that the user can be led between rooms through doors and openings, and is not told to go through walls. In order to provide this navigation assistance there needs to exist a representation of the indoor environment. One alternative for this is a navigation graph, which — in this thesis — is an undirected graph that connects rooms together such that the graph can be followed by a user. This means that they cannot cut through walls, and they should provide a path between all rooms in a building. Presently, the creation of a navigation graph is done by hand by placing individual nodes and connecting them using edges and as such creating the desirable graph.

Automating the creation of navigation graphs — the central problem in this thesis — is not a trivial task, and it is made more difficult because of the format in which floor plans often come. Floor plan images are easy to come by, but they are often highly detailed raster/bitmap images that are difficult to parse with any classical method. Thus, a pre-trained neural network is utilized to turn them into a format that is easier to work with — one consisting of only walls and doors. Using this output a navigation graph is created using image analysis methods which result in a skeleton of the floor plan and, moreover, the number of nodes is then reduced using a couple of node reducing algorithms.

Results of the methods are shown in a number of figures along with several metrics developed to evaluate their performance. The findings suggest that the navigation graphs created using the method suggested in this thesis often can serve as final graphs for indoor navigation either immediately or after some minor manual correction. It is also clear that the better suited the starting floor plan is the better the graph becomes, meaning that the quality of the output from the neural network heavily influences the quality of the navigation graph.

Supervisors:
Gabrielle Flood, Centre for Mathematical Sciences
Kalle Åström, Centre for Mathematical Sciences
Martin Larsson, Combain Mobile AB

Examiner:
Magnus Oskarsson, Centre for Mathematical Sciences