Online topological segmentation of visual sequences using the algebraic connectivity of graphs

In the context of topological mapping, the automatic segmentation of an environment into meaningful and distinct locations is still regarded as an open problem. This paper presents an algorithm to extract places online from image sequences based on the algebraic connectivity of graphs or Fiedler value, which provides an insight into how well connected several consecutive observations are. The main contribution of the proposed method is that it is a theoretically supported alternative to tuning thresholds on similarities, which is a difficult task and environment dependent. It can accommodate any type of feature detector and matching procedure, as it only requires non-negative similarities as input, and is therefore able to deal with descriptors of variable length, to which statistical techniques are difficult to apply. The method has been validated in an office environment using exclusively visual information. Two different types of features, a bag-of-words model built from SIFT keypoints, and a more complex fingerprint based on vertical lines, color histograms, and a few Star keypoints, are employed to demonstrate that the method can be applied to both fixed and variable length descriptors with similar results.