Geometric indexing for recognition of places based on expanded delaunay triangulation

Issue title: Intelligent Computing for Pattern Recognition, Image Processing and Computer Vision Papers from CIARP 2014, November 2-5, 2014, Puerto Vallarta, Jalisco, Mexico

Guest editors: Eduardo Bayro-Corrochano

Article type: Research Article

Authors: Lara-Álvarez, Carlos^a | Rojas-Domínguez, Alfonso^{b; *}

Affiliations: [a] Centro de Investigación en Matemáticas, Av Universidad 222, La Loma, Zacatecas, México | [b] Tecnológico Nacional de México/Instituto Tecnológico de León, Av Tecnológico S/N, Industrial Julián Obregón, León, Gto, México

Correspondence: [*] Corresponding author: Alfonso Rojas-Domínguez, Tecnológico Nacional de México/Instituto Tecnológico de León, Av Tecnológico S/N, Industrial Julián Obregón, León, Gto 37290, México. E-mail:alfonso.rojas@itleon.edu.mx

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 of geometric 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 an expanded 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.

Keywords: Place recognition, bag of visual words, geometric indexing, delaunay triangulation, q-grams

DOI: 10.3233/IDA-160848

Journal: Intelligent Data Analysis, vol. 20, no. s1, pp. S95-S107, 2016