Automatic construction of garage maps for future vehicle navigation service

Digital garage maps are the basis for future vehicle navigation services such as smart parking management that displays the availability of parking spaces. It can direct drivers to empty ones, avoiding any searching, circulating in large, complex parking structures. However, such maps are not currently available, making it impossible to deploy smart parking management. Conducting manual survey incurs tremendous amount of human efforts, and cannot scale to large numbers of garages. In this paper, we propose three algorithms, Sequential Merging, Points Clustering and Segments Matching that can automatically construct complete and accurate garage maps using data crowdsensed from drivers. Upon entering and leaving the garage, the driver's smartphone collects inertial data, which are used to generate the vehicle's trajectory. Our algorithms fuse together these trajectories to recreate the size, layout of the garage. We compare the performance of the three algorithms using different garages. We find that Points Clustering is robust to trajectory errors, with F-score above 0.95 for trajectory length error up to 2 meters, Segments Matching can handle partial trajectories with arbitrary start/end locations, and it constructs the same map using trajectories much shorter than those needed by the other two algorithms.