Home

Welcome to the IndoorMapConstruction wiki!

IndoorMapConstruction

IndoorMapConstruction is a tool for Indoor Map Construction From Crowd-Source.
The project is still in progress, and is done as a final project for a B.Sc degree in Electrical Engineering at Tel-Aviv University.
In our project the Map-Constructor will build navigable indoor map objects of the buildings floors
given a data-base of pedestrians trajectories.

IndoorMapConstruction inputs:

A data-base of pedestrian trajectories inside a certain area.
We assume the fixes are made using a novel WiFi based location solution, which is a new technology of one of the leading companies in the field of device location. Since it is WiFi based, a fix inside buildings in the area provided is available and accurate, with an error of less than 3 meters for 90% of the measurements.

IndoorMapConstruction algorithm steps:

1. Data-Base Filtering [incomplete]
   1.1. We use Open Street Map API to query for building shapes in the area of the trajectories in the trajectory data-base. Then, we divide the trajectory data-base to different sets, each belonging to the a different building, and clean trajectories of outdoor fixes.
   1.2. Remove trajectories with fixes at a low periodicity. In trajectories in which fix measurements are made with too low periodicity, the line segments will go through many walls resulting with low SNR.

2. Trajectory Segmentation and Clustering
   The basic assumption is that inside a building: corridors, ways, and rooms share many behavioral movement patterns from a pedestrian to another. We connect the coordinates of the trajectory fixes into line segments, each of which represents a segment of a travel some pedestrian has made inside the building. In this stage of IndoorMapConstruction, we segment the trajectories, each trajectory segment might contain multiple line segments. Then, we cluster the trajectory segments together to detect their underlying corridors, ways, and rooms. Our algorithm is based upon a modified and improved TRACLUS trajectory segmentation and clustering algorithm. In our modified TRACLUS we use our own distance function, and not the one that was suggested in the paper. Its advantage is in allowing the storage of trajectory segments in a smart data-base, which allows querying for "near-by" trajectory segments much faster than the naive O(n^2) method. Exact complexity analysis is yet to be proven, but it is somewhere between O(n^1.5) to O(n) in the usual case, and works much faster than before, according to testing.
   A wiki page for IndoorMapConstruction Trajectory Segmentation and Clustering needs to be written.

3. Cluster Processing [incomplete]
   A cluster is essentially a set of trajectory segments. In the Cluster Processing phase, we process each cluster to estimate two important things: its representative trajectory, and its shape.
   In order to do so, we find the main direction of the cluster, in terms of azimuth. After concluding this main direction, we can rotate the cluster so that the main direction matches with the new "x" axis. Then, as proposed in the TRACLUS article, for x value along the main axis, the y value of the representative trajectory would be the mean of all trajectory segments y values at this x value.
   In order to estimate the width of the corridor we make the assumption that while walking along a corridor of direction x, pedestrian locations along the y axis are distributed uniformly within the range of the two walls. This allows us to take the following method of estimation - since the standard deviation of a uniform distribution is sigma = (b-a)/sqrt(12), and b-a symbolizes the width W of the corridor then W/2 = sqrt(3)*sigma. This is the value we take from either side of the representative trajectory, in order to estimate walls locations.

4. Cluster Connectivity [future work]
   Upon cluster processing, we will detect overlapping clusters to build a skeleton of the floor. Representative trajectories of overlapping clusters may be accordingly connected in order to serve as a graph for routing on the floor map. The polygon of the union of clusters, along with an underlying routing graph, makes an indoor map of the building.

Latest Results:

Clustering Example of a "W" shaped building:
The bold lines are the convex hull surrounding all the line segments of a cluster. The segments themselves are the dashed lines inside. In this image the clustering was done on 21 randomly simulated trajectories of 60 fixes each inside the "W" shaped building.