Efficient data association for view based SLAM using connected dominating sets

Loop closing in vision based SLAM applications is a difficult task. Comparing new image data with all previously acquired image data is practically impossible because of the high computational costs. Most approaches therefore compare new data with only a subset of the old data, for example by sampling the data over time or over space by using a position estimate. In this paper, we propose a more natural approach, which dynamically determines a subset of images that best describes the complete image data in the space of all previously seen images. The actual problem of finding such a subset is called the “Connected Dominating Set” (CDS) problem, which is well studied in the field of graph theory. Application on large indoor datasets results in approximately the same map using only 13% of the computational resources with respect to comparing with all previous images. Also, it outperforms other sampling approaches. The proposed method is particularly beneficial for realistic mapping scenarios including moving objects and persons, motion blur and changing light conditions.1