Geometric indexing for recognition of places based on expanded delaunay triangulation

Abstract

Models based on q-grams are widely used in communication theory, natural language processing, statistical pattern classification, and other areas of machine learning. In this paper, the idea ofgeometric q-grams is used to solve the place recognition problem, which is fundamental for autonomous navigation. Visual place recognition implies the capacity to recognize a previously visited place given current camera measurements (i.e. digital images). A conventional approach for solving the place recognition problem is to employ histograms of visual features, typically losing the spatial location of said features (relative to the image) in the process. Our approach first detects interest points and assigns labels to them based on visual features; then the images are represented by a set of geometric q$-grams obtained from triangles of anexpanded Delaunay triangulation, thus implicitly encoding relative spatial information. Through this representation and the use of an inverted index, images that match a query can be efficiently recovered in real time. The proposed approach is path independent and was tested on publicly available datasets, resulting in a high recall rate and reduced time complexity.