Reconocimiento Visual de Escenas en Entornos Multi-Robot

(1)

Reconocimiento Visual de Escenas en Entornos Multi-Robot

Miguel ´Angel Moll Llabr´es

Memoria del Trabajo de Fin de M´aster M´aster Universitario en Ingenier´ıa Industrial

de la

UNIVERSITAT DE LES ILLES BALEARS Curso Acad´emico 2018/2019

Fecha: 31/07/2019

Tutor 1: Dr. Emilio Garc´ıa Fidalgo Tutor 2: Dr. Alberto Ortiz Rodr´ıguez

(2)

Resumen

Dentro del ámbito de la robótica móvil, la generación de mapas del entorno (mapping por sus traducción al inglés) se considera una tarea fundamental, ya que sirve como base a otras tareas de más alto nivel tales como la localización, la planificación de caminos o la evitación de obstáculos. El proceso de construcción de mapas se encarga de construir una representa- ción del entorno en el que opera el robot a partir de la información sensorial recibida. Sin embargo, todos los sensores presentan un inherente ruido que dificulta este proceso, produciendo incoherencias en los mapas resultantes.

Por esta razón, los algoritmos actuales de construcción de mapas se apoyan en técnicas alternativas que permiten determinar cuando el robot se encuentra en una zona ya visitada previamente. La importancia de ser consciente de estas situaciones radica en que esta información permite minimizar el error que presentan los mapas resultantes, dando lugar a representaciones del entorno coherentes y mucho más fieles a la realidad.

La capacidad de determinar si el robot se encuentra en una zona ya visitada previamente es lo que se conoce en robótica móvil como la detección de bucles (en inglés, loop closure detection). Durante los últimos años han proliferado soluciones para detectar bucles basadas en técnicas de visión por computador, debido especialmente a la existencia, cada vez más, de ordena- dores más potentes y a la reducción del coste de las cámaras convencionales.

Cuando el problema de detectar bucles se basa en imágenes se dice que el proceso está basado en la apariencia (appearance-based loop closure detection). En ocasiones, también se le conoce como reconocimiento visual de escenas (visual place recognition).

La mayor´ıa de las soluciones propuestas para el cierre visual de bucles están pensadas para funcionar sobre un único agente. Sin embargo, en entornos grandes, el uso de diversos robots trabajando de una forma cooperativa provee diversos beneficios, como, por ejemplo, la reducción del tiempo uti-

(3)

que operen en escenarios multi-robot. Este tipo de escenarios, debido a que cada agente tiene una visión parcial del entorno, presentan una serie de dificultades que no se encuentran al detectar bucles con un único robot y que deben ser tenidas en consideración.

Dentro de este contexto, el objetivo de este trabajo de final de máster es adaptar una solución existente de reconocimiento visual de escenas para trabajar en entornos multi-robot. De forma más precisa, los objetivos del trabajo son:

Estudiar y comprender el funcionamiento de un algoritmo reciente de detecci´on visual de bucles.

Adaptar dicho algoritmo para trabajar en un entorno distribuido, im- plementando diversas variantes de funcionamiento.

Comparar los algoritmos desarrollados con respecto a la versi´on para un ´unico robot y con algunas soluciones existentes.

Evaluar las ventajas y desventajas de cada variante de funcionamiento.

(4)

´ Indice general

1. Introducci´on 10

1.1. Rob´otica . . . 10

1.2. Navegaci´on . . . 12

1.3. Construcci´on de mapas, localizaci´on y SLAM . . . 12

1.4. Detecci´on de bucles . . . 14

1.5. Sistemas multi-robot . . . 15

1.6. Tipos de sistemas multi-robot . . . 16

1.7. Objetivos del proyecto . . . 16

1.8. Organizaci´on del documento . . . 16

2. Aspectos fundamentales de la descripción e indexación de imágenes 18 2.1. Descripción de imágenes . . . 18

2.1.1. Descriptores locales . . . 18

2.1.2. Descriptores globales . . . 20

2.2. Indexaci´on de im´agenes . . . 21

2.2.1. Bolsa de palabras visuales (BoW) . . . 22

3. Breve revisi´on de trabajos relacionados 24 3.1. M´etodos basados en descriptores globales . . . 24

3.1.1. Histogramas . . . 24

3.1.2. Gist . . . 25

3.1.3. Soluciones inspiradas en la biolog´ıa . . . 26

3.2. M´etodos basados en descriptores locales . . . 26

3.3. M´etodos basados en el modelo BoW . . . 27

3.3.1. Sistemas basados en BoW offline . . . 27

3.3.2. Sistemas basados en BoW online . . . 28

3.3.3. Sistemas multi-robot . . . 28

(5)

4. OBIndex2 e iBoW-LCD 29

4.1. OBIndex2 . . . 29

4.2. iBoW-LCD . . . 32

4.3. Resultados . . . 34

5. Primer enfoque multi-robot: detecci´on de bucles centralizada 37 5.1. Arquitectura . . . 37

5.1.1. Modificaciones realizadas sobre la librer´ıaOBIndex2 . 39 5.1.2. Modificaciones realizadas sobre iBoW-LCD . . . 40

5.2.1. Resultados para Lip6In . . . 41

5.2.2. Resultados para Lip6Out . . . 42

5.2.3. Resultados para City Centre . . . 44

5.2.4. Resultados para KITTI00 . . . 46

5.2.6. An´alisis de la independencia deldataset . . . 48

6. Segundo enfoque multi-robot: detecci´on de bucles distribuida 51 6.1. Arquitectura . . . 51

6.2.1. Resultados para Lip6In . . . 53

6.2.2. Resultados para Lip6Out . . . 54

6.2.3. Resultados para City Centre . . . 55

6.2.6. An´alisis de la independencia deldataset . . . 59

6.3. Discusi´on . . . 60

7. Conclusiones y trabajo futuro 62 7.1. Conclusiones . . . 62

7.2. Trabajo futuro . . . 63

(6)

´ Indice de figuras

1.1. Ejemplo de dron a´ereo . . . 10 1.2. Ejemplo de industria automatizada . . . 11 1.3. Interfaz de robot aspirador . . . 13 1.4. Diferencia entre dos representaciones de un mismo mapa usan-

do y sin usar t´ecnicas de cierre de bucles . . . 15 2.1. Funcionamiento de un algoritmo BoW usado para clasificar

imágenes . . . 23 3.1. Ejemplos de histogramas usados como descriptores globales . 25 4.1. Ejemplo de árbol creado con el algoritmo de Muja y Lowe . . 30 4.2. Representación de 3 islas con dimensiones distintas . . . 33 4.3. Representación de la precisión vs la sensibilidad obtenido al

procesar distintosdatasets usandoOBIndex2 e IBoWLCD . . 36 5.1. Esquema de la arquitectura usada para llevar a cabo el enfo-

que centralizado . . . 38 5.2. Resultados obtenidos al ejecutar la soluci´on centralizada so-

bre eldataset Lip6In . . . 42 5.3. Resultados obtenidos al ejecutar la soluci´on centralizada so-

bre eldataset Lip6Out . . . 44 5.4. Resultados obtenidos al ejecutar la soluci´on centralizada so-

bre eldataset City Centre . . . 45 5.5. Resultados obtenidos al ejecutar la soluci´on centralizada so-

bre eldataset KITTI00 . . . 47 5.6. Resultados obtenidos al ejecutar la soluci´on centralizada so-

bre eldataset KITTI05 . . . 48 5.7. Representaci´on del resultado obtenido al dividir cada data-

(7)

6.1. Esquema de la arquitectura usada para llevar a cabo el enfoque no centralizado . . . 52 6.2. Resultados obtenidos al ejecutar la soluci´on no centralizada

sobre eldataset Lip6In . . . 53 6.3. Resultados obtenidos al ejecutar la soluci´on no centralizada

sobre eldataset Lip6Out . . . 55 6.4. Resultados obtenidos al ejecutar la soluci´on no centralizada

sobre eldataset City Centre . . . 56 6.5. Resultados obtenidos al ejecutar la soluci´on no centralizada

sobre eldataset KITTI00 . . . 58 6.6. Resultados obtenidos al ejecutar la soluci´on no centralizada

sobre eldataset KITTI05 . . . 59

(8)

´ Indice de tablas

2.1. Resumen de detectores locales . . . 19 2.2. Resumen de descriptores locales . . . 20 2.3. Resumen de detectores globales . . . 21 4.1. Resultados obtenidos al usarOBIndex2 eiBoW-LCD en dis-

tintosdatasets . . . 36 5.1. Resultados al ejecutar el algoritmo de detecci´on de bucles de

manera no distribuida sobre el dataset Lip6In . . . 43 5.2. Resultados al ejecutar el algoritmo de detecci´on de bucles de

manera no distribuida sobre el dataset Lip6Out . . . 44 5.3. Resultados al ejecutar el algoritmo de detecci´on de bucles de

manera no distribuida sobre el dataset City Centre . . . 46 5.4. Resultados al ejecutar el algoritmo de detecci´on de bucles de

manera no distribuida sobre el dataset KITTI00 . . . 47 5.5. Resultados al ejecutar el algoritmo de detecci´on de bucles de

manera no distribuida sobre el dataset KITTI05 . . . 49 5.6. Valores de sensibilidad obtenidos al ejecutar los distintosda-

tasets mediante el algoritmo centralizado usando 3 agentes a los que se les ha asignado un número desigual de imágenes . . 49 6.1. Resultados al ejecutar el algoritmo de detección de bucles de

manera distribuida sobre eldataset Lip6In . . . 54 6.2. Resultados al ejecutar el algoritmo de detecci´on de bucles de

manera distribuida sobre eldataset Lip6Out . . . 56 6.3. Resultados al ejecutar el algoritmo de detecci´on de bucles de

manera distribuida sobre eldataset City Centre . . . 57 6.4. Resultados al ejecutar el algoritmo de detecci´on de bucles de

manera distribuida sobre eldataset KITTI00 . . . 58

(9)

6.5. Resultados al ejecutar el algoritmo de detecci´on de bucles de manera distribuida sobre eldataset KITTI05 . . . 60 6.6. Valores de sensibilidad obtenidos al ejecutar los distintosda-

tasets mediante el algoritmo no centralizado usando 3 agentes a los que se les ha asignado un n´umero desigual de im´agenes . 60

(10)

´ Indice de algoritmos

1. A˜nadir un nuevo descriptor como palabra visual nueva . . . . 31 2. Eliminar palabra visual . . . 31 3. Construir islas din´amicas . . . 34

(11)

Cap´ıtulo 1

Introducci´ on

1.1. Rob´ otica

La robótica es un campo de estudio cuya importancia ha ido creciendo de forma constante a lo largo de las últimas décadas. Una prueba de ello es la vasta variedad de aplicaciones que han sido desarrolladas en este campo gracias a los avances tanto a nivel de hardware (mejores actuadores, procesadores, etc.) como de software. Un ejemplo de estos avances se encuentra en los drones comerciales (figura 1.1) cuyos sensores y funciones están mejorando con cada nuevo modelo manteniendo los precios en un rango relativamente asequible.

Figura 1.1: Dron fabricado por la marca DJI cuya relaci´on entre prestaciones y dimensiones era impensable hace varios a˜nos.

Uno de los campos que ha sido más revolucionado por la robótica es la industria. La inclusión de agentes autónomos en las fábricas ha permitido un aumento de la producción industrial disminuyendo costes y manteniendo la calidad.

En la agricultura tambi´en se han propuesto soluciones mediante el uso

(12)

Figura 1.2: Ejemplo de industria automatizada mediante el uso de robots.

de la robótica. Un ejemplo de estas soluciones es el propuesto por la empresa onubense Soluciones Robóticas Agr´ıcolas -Agrobot- que ha desarrollado una cosechadora con brazos capaz de determinar qué fresas están listas para ser recolectadas. Lo que puede suponer una enorme mejora de la producción en plantaciones masivas como las que se encuentran en California o China¹.

Otro campo en el que la robótica ha despertado un gran interés es el militar. El uso de UAV (Unmanned Aerial Vehicle), en zonas de guerra, ha sufrido un enorme incremento en los últimos años debido a las enormes inversiones, por parte de los gobiernos, para el desarrollo de plataformas autónomas que permitan espiar o realizar ataques en territorio enemigo sin la necesidad de poner en riesgo operativos de sus propios cuerpos militares.

Un campo en el que se está empezando a plantear la introducción de soluciones mediante la robótica es la medicina. La cirug´ıa robótica, inicial- mente ideada para operaciones cardiovasculares, está presentando resultados prometedores especialmente en el campo de la urolog´ıa. Hoy en d´ıa el 85 % de las prostatectom´ıas radicales llevadas a cabo en EEUU se hacen mediante la asistencia de robots [1].

Otro claro ejemplo de lo comentado previamente se encuentra en el ámbi- to de la educación en el que la aparición de actuadores y controladores económicos, capaces de realizar tareas relativamente complejas, as´ı como de sistemas sencillos para el desarrollo de aplicaciones permiten introducir estas disciplinas en los colegios e institutos. Esto se puede observar en la aparición de competiciones de robótica estudiantiles como laFirst Lego Leage².

1http://bit.ly/roboticaAgricola

(13)

1.2. Navegaci´ on

Uno de los ámbitos más relevantes en el campo de la robótica móvil consiste en dotar a los veh´ıculos con la habilidad de moverse por su entorno de una manera segura, evitando colisiones que puedan causar daños. A este proceso se le conoce como navegación. Las arquitecturas de navegación se pueden dividir en dos grandes categor´ıas: las reactivas, en las que el robot simplemente reacciona a la información que recibe de sus alrededores mediante sus sensores y las deliberativas que permiten al robot planificar sus movimientos gracias a la disposición de un mapa del entorno en el que se encuentra. Para realizar una navegación deliberativa eficiente es imprescin- dible la creación de mapas que definan de una manera entendible para el robot el entorno y la disposición de los obstáculos que se pueda encontrar durante el desarrollo de sus tareas.

La aparición de estos sistemas de navegación (basados en mapas) ha permitido la creación de robots cuya dependencia de un operario encargado de dirigirlos sea cada vez menor. Un claro ejemplo de ello son los aspiradores automáticos cuyos primeros modelos necesitaban balizas para delimitar el entorno en el que deb´ıan trabajar y cuya navegación se basaba en la mayor´ıa de los casos en un sistema reactivo. Sin embargo, en la actualidad, ya están apareciendo propuestas que realizan mapas suficientemente preci- sos del entorno en el que van a trabajar (véase figura 1.3), lo que permite que el propietario simplemente deba asignarle el momento y la zona en la que quiere que trabaje mediante una interfaz gráfica y el robot, usando el mapa creado la primera vez que se movió por el entorno, planificará sus movimientos de una manera eficiente.

1.3. Construcci´ on de mapas, localizaci´ on y SLAM

Como se ha comentado en el apartado anterior, la creaci´on de mapas que definan eficazmente el entorno de operaci´on es enormemente importante.

En robótica, el proceso de creación de estos mapas se conoce comúnmente comomapping por su traducción al inglés. Las composiciones de los mapas creados var´ıan dependiendo de los datos usados para hacer el reconocimiento del entorno [2]. Por ello, los mapas normalmente se pueden clasificar en tres tipos: mapas métricos, topológicos e h´ıbridos.

Mapas métricos: Estos mapas representan el entorno de la manera más precisa. Almacenan información de detalles del entorno como distancias, medidas del entorno. Relacionando dicha información con

(14)

Figura 1.3: Interfaz gr´afica de un robot aspirador moderno en la que se puede ver el plano realizado de la casa en la que desempe˜na sus funciones.

la posici´on respecto a un sistema de coordenadas global. La principal desventaja de estos sistemas es el tiempo de c´omputo necesario y el almacenamiento requerido [3].

Mapas topológicos: Este enfoque genera representaciones abstractas del mundo. Estos mapas son más simples y compactos que los anteriormente citados, por lo que requieren de menos tiempo de proceso pero incluyen menos información del entorno [3].

(15)

citados anteriormente para maximizar las ventajas de estos, minimizando las desventajas [3].

La generación de estos mapas carece de sentido si el robot no dispone de la capacidad de saber dónde se encuentra en cada momento. Es necesario, por tanto, dotar al robot con la capacidad de reconocer donde está y situarse en el entorno. Esto es lo que se conoce en la robótica como localización. A pesar de que la construcción de mapas y la localización pueden realizarse de forma independiente, existen una serie de técnicas que permiten llevar a cabo las dos de forma simultánea, creando un mapa del entorno a la vez que se localiza el robot en dicho mapa. Estas técnicas se conocen como SLAM (Simultaneous Localization and Mapping).

1.4. Detecci´ on de bucles

Para describir el entorno se usan sensores que permiten a los robots navegar y mapear los escenarios por los que se mueven. Las medidas de estos sensores, independientemente del tipo, siempre incluyen algo de ruido, lo que puede conducir a mapas poco coherentes con la realidad. Es por ello que son necesarios m´etodos para detectar estas situaciones y ayudar a su correcci´on.

Uno de esos métodos es la detección de bucles (Loop Closure detection en inglés), los cuales se refieren a determinar que no es la primera vez que se pasa por un determinado lugar. Estos algoritmos se usan para corregir la distorsión presente en los mapas generados mediante datos adicionales obtenidos de sensores complementarios (véase figura 1.4).

Cuando el sensor utilizado para navegar es una c´amara, se habla entonces deAppearance-based Loop Closure Detection. Este es uno de los principales temas de este proyecto.

La detección de bucles presenta una serie de dificultades que deben ser tenidas en cuenta. Uno de ellos es el perceptual aliasing que consiste en diferentes escenarios que presentan las mismas caracter´ısticas; estos casos pueden representar problemas a la hora de detectar correctamente cierres de bucles [2]. Otro problema es la escalabilidad: la carga computacional que requiere comparar imágenes para determinar si el escenario que representan es el mismo. Esta carga irá creciendo a medida que se expanda la zona conocida por el robot. El ruido presente en las imágenes obtenidas por los agentes también puede presentar problemas a la hora de reconocer los entornos en los que estos se mueven. La variabilidad de los entornos es una eventualidad que debe ser tomada en consideración, esta consiste en el caso en el que una zona conocida por el robot ha sufrido cambios desde la última vez que este

(16)

Figura 1.4: Diferencia entre un mapa representado ´unicamente con los datos de los sensores del robot (a) y otro representado mediante los sensores del robot e informaci´on de cierre de bucles (b) [4].

la visit´o por lo que el agente puede ser inducido a error a la hora de cerrar bucles.

1.5. Sistemas multi-robot

En la actualidad, la mayor´ıa de soluciones planteadas se centran el la de- tección de bucles mediante un solo robot [5–8]. A pesar de ser funcionales, pueden presentar problemas a la hora de mapear escenarios grandes, pudiendo llegar a tardar demasiado ya que ese único robot va a tener que recorrer todo el entorno para obtener un mapa completo de la zona. Es en estas situaciones donde el uso de un sistema multi-robot permite que varios agentes recorran el entorno de manera simultánea para as´ı abarcar más distancia en menos tiempo. Aunque con menos frecuencia en la literatura se pueden encontrar soluciones para la detección de bucles con varios robots [9, 10].

Este tipo de soluciones podr´ıan ser ´utiles en escenarios con muchas zonas aisladas entre ellas ya que cada robot puede ser programado para que va- ya en direcciones distintas pudiendo as´ı realizar mapas m´as velozmente y disminuyendo el riesgo de dejar zonas sin inspeccionar.

A pesar de aportar grandes ventajas, estos sistemas multi-robot presentan problemas para su ejecuci´on: al usar varios robots para procesar el mismo escenario, la informaci´on que estos obtienen debe ser compartida con

(17)

podr´ıa llegar a ser insostenible. También, se podr´ıa dar el caso de que uno de los robots pierda la señal y no sea capaz de enviar su información al resto de agentes.

1.6. Tipos de sistemas multi-robot

Al implementar un sistema de detección de bucles multi-robot, se pueden considerar, entre otras, las dos alternativas siguientes. La primera de ellas es centralizada, es decir, un servidor central procesa la información que los agentes le env´ıan a medida que avanzan por el escenario y este se encarga de procesarla, almacenarla y determinar si se ha cerrado bucle. Esta solución presenta la desventaja de que en caso de fallo en el servidor, el sistema deja de funcionar por completo.

Otra solución obedece a un paradigma descentralizado en el que cada robot almacena únicamente la información que él mismo ha ido recopilando y para cada nueva observación se lleva a cabo una consulta con el resto de agentes para determinar si se ha cerrado algún bucle. A pesar de ser la solución aparentemente más eficaz, este tipo de arquitecturas pueden hacer que el algoritmo pierda efectividad ya que cada robot únicamente cuenta con una visión parcial del entorno y esto, como se verá en apartados posteriores, puede llegar a suponer un problema.

1.7. Objetivos del proyecto

El objetivo principal de este proyecto es adaptar una solución de detec- ción de bucles ya existente, desarrollada para funcionar mediante un único robot, para que pueda llevar a cabo su función usando varios agentes a la vez. Dentro de este contexto, se presentan dos soluciones diferentes: una centralizada y otra no centralizada y se evalúa el rendimiento de cada una de ellas en diversosdatasets públicos.

1.8. Organizaci´ on del documento

El presente documento se organiza de la siguiente forma:

En el cap´ıtulo 2 se presentan los fundamentos te´oricos sobre los que funciona la soluci´on planteada.

En el cap´ıtulo 3 se comenta el estado del arte de este ´ambito de inves- tigaci´on.

(18)

El cap´ıtulo 4 detalla el funcionamiento de la soluci´on sobre la que parte este proyecto.

Los cap´ıtulos 5 y 6 presentan las dos soluciones desarrolladas en este proyecto (centralizada y no centralizada respectivamente) con sus resultados.

Finalmente, en el cap´ıtulo 7 se detallan las conclusiones a las que se han llegado una vez terminado el proyecto.

(19)

Cap´ıtulo 2

Aspectos fundamentales de la descripci´ on e indexaci´ on de im´ agenes

El rendimiento de un sistema de detección de cierre de bucles visual está fuertemente influenciado por la forma de describir imágenes y la forma de indexarlas. En este cap´ıtulo se van a comentar los fundamentos teóricos sobre los que se basan estos.

2.1. Descripci´ on de im´ agenes

Existen fundamentalmente dos paradigmas de descripci´on de im´agenes:

descriptores locales y descriptores globales. A continuaci´on se detallan los principios de funcionamiento de estos y se muestran algunas soluciones propuestas para cada uno de ellos.

2.1.1. Descriptores locales

Estos métodos requieren un proceso de detección de puntos de interés (keypoints) antes de proceder a describirlos. Tras haber identificado dichos puntos de interés se obtiene un vector por cada uno de ellos que describe el entorno alrededor del punto. A este vector se le conoce como descriptor [2].

Para ser capaces de identificar los mismos puntos de interés en distintas imágenes, éstos deben ser independientes de caracter´ısticas como rotaciones de cámara o transformaciones afines. Es por ello que es de suma importancia

(20)

Nombre Referencias Tipo de detector

Harris [16] Esquinas

Shi and Tomasi [17] Esquinas

SUSAN [18] Esquinas

FAST [13] Esquinas

FAST-ER [19] Esquinas

ORB [15] Esquinas

AGAST [20] Esquinas

BRISK [21] Esquinas

SIFT [22] Blobs

SURF [12] Blobs

CenSure [23] Blobs

Star [24] Blobs

SUSurE [25] Blobs

KAZE [26] Blobs

AKAZE [27] Blobs

ASIFT [28] Blobs

MSER [29] Regi´on

Tabla 2.1: Resumen de detectores locales [3].

que los descriptores de puntos de inter´es sean capaces de sobrellevar defor- maciones de los puntos de inter´es debidas a cambios de puntos de vista [3].

El ejemplo más conocido de estos métodos es SIFT [11], que detecta y describe puntos de interés. Estos puntos de interés son independientes de cambios de posición de la cámara o iluminación de la escena. Otro ejemplo podr´ıa ser SURF [12] que, inspirado por SIFT, mejora los tiempos de ejecución de este último. FAST (detector) [13], BRIEF (descriptor) [14] y ORB (detector y descriptor) [15] son otros casos de algoritmos de detección y descripción de puntos de interés usados en la actualidad. Tradicionalmen- te se han propuesto algoritmos de descripción basados en vectores de punto flotante (como SIFT y SURF) con su consiguiente consumo de recursos. En los últimos tiempos, descriptores binarios como BRIEF u ORB están siendo muy utilizados debido a su eficiencia computacional [3].

En las tablas 2.1 y 2.2, se detallan algunos de los detectores y descriptores locales respectivamente usados en la actualidad.

(21)

Nombre Referencias Tipo de descripto N´umero de componentes

SIFT [22] Punto flotante 128

SURF [12] Punto flotante 32, 64, 128

U-SURF [12] Punto flotante 32, 64, 128

GLOH [30] Punto flotante 64, 128

PCA-SIFT [31] Punto flotante 36

M-SIFT [32] Punto flotante 128

DAISY [33] Punto flotante 200

LESH [34] Punto flotante 128

ASIFT [28] Punto flotante 128

KAZE [26] Punto flotante 64

BRIEF [35] Bit 128, 256, 512

ORB [15] Bit 256

BRISK [21] Bit 512

FREAK [36] Bit 512

AKAZE [27] Bit 488

D-BRIEF [37] Bit 32

LDAHash [38] Bit 128

BinBoost [39] Bit 64

LDB [40] Bit 256, 512

CBDF [41] Bit 256

Tabla 2.2: Resumen de descriptores locales [3].

2.1.2. Descriptores globales

Algunos ejemplos de este tipo de algoritmos son Gist [42], BRIEF-Gist [43]

´

o FACT [44]. Estos descriptores no requieren de una fase de detección de puntos de interés sino que siempre procesan y describen toda la imagen como un todo. Por lo general, son menos susceptibles a los cambios de condiciones del entorno, pero son poco robustos a los cambios de posición desde los que se ve la escena [2].

En la tabla 2.3 se resumen algunos de los descriptores globales que se usan en la actualidad.

(22)

Nombre Referencias Principal Components [45, 46]

Colour Histograms [47]

Gradient Orientation Histograms [48]

WGOH [49]

WGII [50]

OACH [51]

Receptive Field Histograms [52]

Gist [53]

Omni-Gist [54]

BRIEF-Gist [43]

Spherical Harmonics [55]

Fingerprints [56]

FACT [44]

DP-FACT [57]

Fourier Signatures [58, 59]

Colour Segmented Images [60]

Scanline Intensity Profile [61]

Normalized Patches [62]

2D Haar Wavelet Decomposition [63, 64]

WI-SURF [65]

WI-SIFT [65]

DIRD [66]

OFM [67]

OFSC [67]

Tabla 2.3: Resumen de descriptores globales [3].

2.2. Indexaci´ on de im´ agenes

Otro factor que afecta al rendimiento de un sistema de detección de bucles basado en apariencia es su habilidad para obtener e indexar imágenes previas. En general, una búsqueda por fuerza bruta es inabordable cuando el número de imágenes a indexar es elevado. Este problema ha sido solven- tado en la literatura mediante esquemas de indexación (como los kd-trees) y mediante cuantificación de descriptores (t´ıpicamente el esquema Bag-of Words). En este trabajo nos centraremos en el uso de éste último.

(23)

2.2.1. Bolsa de palabras visuales (BoW)

En lugar de almacenar ´unicamente los descriptores que se reciben e inde- xarlos por medio de alguna estructura eficiente de datos, se puede tratar de agregarlos en funci´on de las caracter´ısticas especiales que estos presentan. Un ejemplo de estos algoritmos es el esquemaBag of Words (BoW en adelante).

Consiste en agrupar, en una fase de entrenamiento, cada descriptor extra´ıdo de las im´agenes que se van procesando a los m´as parecidos, formando as´ı grupos de descriptores que comparten unas caracter´ısticas determinadas. A estos grupos se les suele llamarwords (palabras), por ello el algoritmo es lla- madoBag of Words. Al conjunto de palabras se le conoce como diccionario.

Posteriormente, durante la fase de consulta, cada uno de los descriptores de la imagen actual se asocia con la palabra más cercana del diccionario. Con ello, la imagen se representa por un histograma de ocurrencias de cada palabra del diccionario en la imagen, reduciendo la representación a un vector de enteros. Dado que algunas palabras pueden ser más representativas que otras, a veces se añaden mecanismos para dar más peso a estas palabras a la hora de construir el vector BoW, como por ejemplo elTerm frequency – In- verse document frequency(TF-IDF). En la actualidad, se están proponiendo esquemas que crean su diccionario a medida que desempeñan sus funciones, sin necesidad de un entrenamiento previo [6, 68, 69].

En sistemas de reconocimiento de escenas, t´ıpicamente los algoritmos BoW se combinan con ´ındices inversos. Estas estructuras almacenan el conjunto de im´agenes en los que cada palabra del diccionario ha aparecido.

Combinando este ´ındice con el vector BoW comentado en el párrafo anterior, se puede obtener de una forma rápida una lista de imágenes similares previas [3].

En la figura 2.1 se aprecia el funcionamiento de un algoritmo de estas caracter´ısticas. El diccionario está dividido en cuatro palabras que definen un sill´ın, un pómulo, la barbada de un viol´ın y un ojo. Al procesar las imáge- nes de entrada (primera fila de imágenes) se obtienen los puntos de interés que mejor podr´ıan definir esas imágenes (segunda fila de imágenes) y estos son comparados con los descriptores ya presentes en el diccionario. Cada coincidencia encontrada en el BoW implica que el grupo (o bolsa) al que pertenece el descriptor incrementa la puntuación y con ello se construyen los histogramas de ocurrencias (tercera fila de imágenes). Con estos histogramas se puede determinar qué caracter´ısticas presenta más frecuentemente una imagen y con ello, conjuntamente con un ´ındice inverso, se puede hacer una estimación bastante precisa de si ya se ha visto esa imagen previamente o no.

(24)

Figura 2.1: Funcionamiento de un algoritmo BoW usado para clasificar imágenes. En la primera serie de figuras se aprecian las imágenes de entrada, en la segunda serie de figuras se observa cómo se han dividido las imágenes en puntos de interés y en la tercera se pueden ver los histogramas creados [70].

(25)

Cap´ıtulo 3

Breve revisi´ on de trabajos relacionados

En este apartado se van a revisar las principales soluciones que existen en la actualidad para detectar bucles. En función de la tecnolog´ıa que se use para describir imágenes, se clasifican en tres tipos: métodos basados en descriptores globales, métodos basados en descriptores locales y métodos basados en el modelo BoW.

3.1. M´ etodos basados en descriptores globales

La tarea de crear mapas y localizar robots en ellos mediante descriptores globales ha sido un tema ampliamente tratado. Por ello, existen un n´umero considerable de soluciones que se basan en este tipo de m´etodos. Algunas de

´estas se basan en histogramas, en el descriptor Gist o est´an inspiradas en la biolog´ıa.

3.1.1. Histogramas

En procesamiento de imágenes, los histogramas proveen una manera eficaz de representar cómo se distribuyen los colores en el escenario. Por ejemplo, en una imagen en escala de grises de 8 bits (como los que se pueden ver en la figura 3.1) se representarán los 256 niveles de intensidad que el color gris toma en la imagen. En el caso de imágenes en color, estos histogramas se deben hacer individualmente para cada canal de color. Por ejemplo, en caso de usar un sistema RGB, se representarán los histogramas para las intensidades de las capas Red, Green y Blue por separado. Estos sistemas

(26)

presentan ventajas considerables a la hora de procesar imágenes como el decremento de tiempo necesario a la hora de comparar dos histogramas respecto al tiempo necesario para comparar dos imágenes directamente. Un ejemplo del uso de estos sistemas en tareas de construcción de mapas es la solución planteada por Iwan Ulrich y Illah Nourbaksh [47].

Figura 3.1: Ejemplos de histogramas de la misma imagen (en escala de grises de 8 bits) a la que se le han dado distintos procesados.

3.1.2. Gist

El uso del descriptor global Gist [71] también ha sido investigado por un número considerable de art´ıculos. Estas soluciones se basan en la idea de que los humanos somos capaces de captar la esencia de un escenario con un solo vistazo, siendo capaces de clasificar diferentes escenas en muy poco tiempo. Este descriptor ha dado lugar a varios trabajos con buenos resultados. Entre ellos, destaca el trabajo realizado por Singh y Kosecka [72] y la unión entre el concepto de descriptor global Gist y el descriptor binario BRIEF por parte de Sunderhauf y Protzel [43]. Su método se basa en reducir el tamaño de la imagen y calcular el descriptor BRIEF en la zona central de la imagen resultante de dicha reducción. En el mismo trabajo, se presenta otra solución consistente en dividir una imagen en una secuencia de fragmentos de la imagen original y aplicar el descriptor BRIEF para cada

(27)

imagen total.

3.1.3. Soluciones inspiradas en la biolog´ıa

Estos sistemas tratan de imitar ciertos aspectos de procesos biológicos concretos. Un ejemplo de estos sistemas esRatSlam [73] que es un sistema SLAM basado en una sola cámara que trata de imitar los sistemas cogni- tivos de los roedores. Según los autores de este art´ıculo, RatSlam es una implementación de un modelo del hipocampo de los roedores que puede realizar SLAM en tiempo real en un robot real. Esta solución se sirve de una attractor network (red dinámica recurrente que tiende a evolucionar a un patrón constante) que combina información de sensores con detección de puntos de interés para representar el entorno. Los resultados del art´ıculo referenciado muestran que el sistema es robusto otorgando resultados positivos en ambientes complejos. Para demostrar la escalabilidad deRatSlam, Milford y Wyeth [61] generaron un mapa que cubr´ıa 66km siguiendo un su- burbio usandoRatSlam. Glover et al. [74] combinaRatSlam con otros tipos de soluciones para atajar el problema de generar mapas que se mantengan coherentes durante todo el d´ıa.

3.2. M´ etodos basados en descriptores locales

Los sistemas basados en descriptores locales son un campo altamente investigado en la actualidad. Desde la creaci´on de SIFT han aparecido muchos trabajos que han aportado soluciones. Un ejemplo dentro de esta categor´ıa es el trabajo realizado por Kosecka y Yang [75] quienes usaron los descriptores SIFT para desarrollar sistemas de localizaci´on en entornos de interior.

En trabajos posteriores [76], presentaron sistemas para filtrar caracter´ısti- cas permitiendo as´ı limitar el número de puntos de interés. Otro trabajo que también ha supuesto un avance es el realizado por Zhang [77], quien propone un sistema llamadoBag-Of-Raw-Features(BoRF para abreviar) en el que se seleccionan los puntos de interés encontrados en los escenarios en función de la consistencia en la que se ven, es decir, los puntos de interés

´

unicamente son almacenados en los diccionarios si se han visto en distintas imágenes. Esta solución supone que a medida que se añaden nuevas imáge- nes el número de puntos de interés a gestionar también aumenta, por lo que compararlas todas una a una puede llegar a ser inviable. Es por ello que en la actualidad, para limitar el número de comparaciones se usan estructuras de indexación, como por ejemplo, loskd-trees.

(28)

3.3. M´ etodos basados en el modelo BoW

La aplicación del modelo BoW para detectar bucles se ha popularizado en los últimos años debido a la capacidad que éstos presentan a la hora de encontrar coincidencias entre descriptores en grandes secuencias de imágenes en tiempos relativamente reducidos. Normalmente este tipo de soluciones requieren una fase de entrenamiento antes de poder funcionar por lo que generalmente se refiere a ellos como sistemas offline. No obstante, en la actualidad también se están proponiendo soluciones que crean su diccionario online, a medida que avanzan.

3.3.1. Sistemas basados en BoW offline

El algoritmo BoW originalmente fue diseñado para la categorización de documentos, ya que permite describir un texto sin importar el orden en el que se encuentran las palabras. No fue hasta el trabajo realizado por Sivic y Zisserman [78] que se usó este modelo para tareas de visión por computador.

Más adelante, Wang [79, 80] propuso otro modelo de localización basado en un sistema BoW que para construir un vocabulario y un ´ındice inverso re- quer´ıa de una fase de entrenamiento previa. En estos trabajos ya se incluyó el uso de la geometr´ıa epipolar para comprobar que la imagen con la que era más probable cerrar bucle según el sistema de puntuaciones aplicado en el algoritmo BoW era realmente el mismo sitio. Posteriormente, Cummins y Newman introdujeron una de las soluciones más conocidas en esta categor´ıa: Fast Appearance-Based Mapping o FAB-MAP para abreviar [81, 82]

quienes asumen que el cálculo de las probabilidades de que las palabras visuales aparezcan simultáneamente en una imagen puede ayudar a la correcta detección de bucles. Este enfoque presenta la desventaja del enorme coste computacional que supone tener que calcular las probabilidades para cada imagen observada.

Los sistemas basados en este tipo de algoritmos tienen grandes problemas en lo referente a la escalabilidad. Para solucionar este problema se han propuesto diccionarios jerárquicos en los que en la fase de entrenamiento los descriptores son agrupados en una jerarqu´ıa para as´ı facilitar la búsqueda de descriptores en diccionarios de gran tamaño [83].

En los primeros trabajos basados en BoW los descriptores usados (como SIFT) consist´ıan en vectores de punto flotante, pero recientemente se est´an introduciendo trabajos que basan su funcionamiento en descriptores binarios. Un ejemplo de ello son las investigaciones llevadas a cabo por Galvez-

(29)

y el descriptor binario BRIEF.

3.3.2. Sistemas basados en BoW online

Los sistemas descritos en el apartado anterior tienen como problema la incapacidad del diccionario de adaptarse a las variaciones que pueda sufrir el entorno. Es por ello que se han introducido soluciones que permitan que el diccionario pueda ser actualizado a medida que el robot avanza por la zona de trabajo. Uno de los primeros trabajos fue el presentado por Filliat [85].

Este autor propone que a medida que se extraen descriptores de las nuevas imágenes estos son emparejados con las palabras visuales ya existentes en el diccionario más parecidas a ellos. Si la distancia entre el vector ya existente y el nuevo en el diccionario supera un determinado umbral, este es añadido como nueva palabra en el diccionario. Usando este diccionario, Angeli [86]

present´o un sistema de reconocimiento de escenas. M´as recientemente, se han presentado soluciones basadas en jerarqu´ıas de memoria [5, 87], clustering aglomerativo [88, 89] y descriptores binarios [6, 69].

3.3.3. Sistemas multi-robot

Aunque no de una manera muy generalizada, en los últimos años están apareciendo soluciones para detectar bucles usando varios robots. Un ejemplo de ellas es el trabajo llevado a cabo por Cieslewski y Scaramuzza [10]

quienes proponen un sistema en el que se divide el diccionario de palabras visuales entre todos los agentes que deben funcionar consecutivamente (de esta forma cada agente dispone de una parte del diccionario), se calcula el vector BoW de la imagen que se desea procesar, este vector es dividido en pequeños “subvectores” cada uno de los cuales es enviado a los distintos robots, cada robot realiza un proceso de comparación, con su segmento del diccionario y el fragmento de vector que ha recibido, tras el cual se devuelve la imagen que tiene más posibilidades de ser la que cierre bucle con la imagen que se está procesando, se unen todos los resultados parciales de cada uno de los robots y se determina qué imagen es la que ha sido votada más consistentemente, por último, se le solicita al robot que ha visto la nueva imagen que realice una verificación geométrica para asegurar que se ha cerrado bucle. En otro trabajo de estos autores en este panorama [90], se usan descriptores globales para llevar a cabo la detección de bucles distribuida.

(30)

Cap´ıtulo 4

OBIndex2 e iBoW-LCD

Para este proyecto se va a adaptar una solución ya existente de cierre de bucles para trabajar en un entorno multi-robot. Esta solución está compues- ta de dos librer´ıas que trabajan conjuntamente: OBIndex2 e iBoW-LCD, desarrolladas por Garc´ıa-Fidalgo y Ortiz [6].

4.1. OBIndex2

OBIndex2 es una librer´ıa para indexar im´agenes basada en un esquema BoW incremental y descriptores binarios. Para poder indexar un diccionario de una manera escalable, es necesario el uso de estructuras de datos jer´arquicas, como por ejemplo kd-trees. Sin embargo, estas estructuras asumen que las componentes de los descriptores son promediables (valores en punto flotante). Debido a que OBIndex2 utiliza descriptores binarios y, por tanto, son vectores no promediables, se basa en el esquema propuesto por por Muja y Lowe [91], que combinado con un ´ındice inverso, permite crear una estructura de datos capaz de determinar si el escenario en el que se encuentra un robot ya se ha visto con anterioridad.

La solución de Muja y Lowe [91] para indexar descriptores binarios, consiste en una estructura jerárquica de árbol cuyos nodos que no son hojas contienenclusters y los nodos hoja contienen los descriptores a buscar. Para construir estas estructuras se parte de una serie de descriptores iniciales de entre los cuales un número K de ellos son elegidos como clusters. Una vez hecho esto, en base a la distancia de Hamming, se emparejan el resto de descriptores con sucluster más cercano. Este proceso es repetido hasta que el número de nodos hoja asociado con un cluster es más pequeño que un

(31)

Figura 4.1: Ejemplo de ´arbol creado con el algoritmo de Muja y Lowe [91]

en el que se observa la clasificaci´on de 10 descriptores (d0−d9). Los nodos no hoja son representados en c´ırculos grises, el nodo ra´ız es R y los nodos hoja son el resto. En este casoK = 2 y S = 3 [6]

La solución planteada por Muja y Lowe se diseñó para indexar descriptores de forma estática. OBIndex2 adapta el esquema para ser usado como un diccionario incremental. Para ello los descriptores encontrados durante la navegación son emparejados recorriendo el árbol desde la ra´ız a un nodo hoja, minimizando en cada paso la distancia de Hamming. Si se encuentra el descriptor, la palabra visual del diccionario se combina con el descriptor actual mediante una operación binaria AND. En caso de no localizar el descriptor encontrado durante la navegación en el diccionario, éste es añadido al árbol como una nueva palabra visual. Si al añadir este nuevo descriptor no se supera el número máximo de descriptores por nodo S, este será añadido al diccionario directamente. Si se supera S, el nodo se reconstruye recursivamente para que no haya ningún nodo no hoja con más deS hojas asociadas a él. El algoritmo 1 muestra como se añaden nuevos descriptores al árbol [6].

Otra novedad que incluyeOBIndex2 es un sistema de depuración selectiva de descriptores para as´ı también mantener el diccionario libre de palabras que estén desfasadas. La idea es mantener como palabras visuales aquellos descriptores que al menos han sido vistos en un número concreto de imáge-

(32)

Algoritmo 1 Añadir un nuevo descriptor como palabra visual nueva Require: T: Árbol jerárquico,B: Descriptor binario

1: nodo← buscarDescriptor(T, B)

2: if numDescriptores(nodo) + 1 < S then

3: a˜nadirDescriptorANodo(nodo,B)

4: else

5: D←obtenerDescriptores(nodo)

6: D=D∪B

7: construirNodoRecursivamente(nodo, D)

nes consecutivas, para asegurar un m´ınimo de estabilidad de las palabras.

El algoritmo 2 muestra como funciona el proceso de eliminar descriptores del diccionario [6], que tambi´en puede implicar un reajuste del ´arbol.

Algoritmo 2 Eliminar palabra visual

Require: T: ´Arbol jer´arquico,B: Descriptor binario

1: nodo← buscarDescriptor(T, B)

2: eliminarDescriptor(nodo, B)

3: if numDescriptores(nodo) >0 then

4: if B == obtenerCluster(nodo) then

5: selecionarNuevoCluster(nodo)

6: else

7: nodo_r ←obtenerNodoRa´ız(nodo)

8: eliminarNodoHijo(nodo_r, nodo)

9: eliminarNodosRecursivamente(nodor)

Para facilitar la selección de la imagen ya vista que cierra bucle con la actual se usa un ´ındice inverso en el que, para cada descriptor, se apunta a qué imágenes lo han visto. Para determinar qué imagen es la que presenta más posibilidades de cerrar bucle, se parte del conjunto de descriptores zt

de la imagen actual en el instante t y se compara con las palabras que se encuentran en el diccionario. Una vez hecho esto, mediante el ´ındice inverso, se obtiene para cada uno de los descriptores, la lista de im´agenes que han visto esa palabra y se les asigna una puntuaci´on sque empieza en 0. Cada vez que una imagen vista anteriormente comparte un descriptor con la imagen actual, su s es incrementada. Este incremento se lleva a cabo usando

(33)

4.2. iBoW-LCD

En este trabajo se va a utilizar tambi´en iBow-LCD. Esta librer´ıa se utiliza para detectar bucles a partir de las im´agenes candidatas obtenidas medianteOBIndex2.

Este sistema empieza su funcionamiento buscando qué imágenes son candidatas para cerrar bucle mediante OBIndex2. Para evitar cerrarlo con imágenes muy próximas a la actual, se guardan en un buffer las pimágenes más recientes lo que permite retrasar la publicación de las imágenes recientes como candidatas a cerrar bucle. Al finalizar la búsqueda, se obtiene una lista que almacena lasj imágenes más parecidasCt={I_s1, ..., Isj}, las cuales son ordenadas en función de su puntuación s. El rango de estas puntuaciones se normaliza mediante la ecuación 4.1

˜

s(I_t, I_k) = s(I_t, I_k)−s(I_t, I_s₁)

s(I_t, I_s_j)−s(I_t, I_s₁), (4.1) en la ques(It, Is1) ys(It, Isj) son la puntuación m´ınima y máxima respectivamente. Este sistema de normalización permite que todos las puntuaciones se sitúen en el rango [0,1]. Esto se hace porque los rangos de las puntuaciones después de usar un sistema TF-IDF pueden variar drásticamente, lo que complica aplicar un umbral para descartar imágenes que no superen una determinada puntuación. Al hacer la normalización siempre se puede usar el mismo umbral τim para descartar las imágenes cuya puntuación no supere dicho valor. Si se establece un valor deτ_im no muy elevado, se obtiene una lista de imágenes candidatas ˜Ct para cerrar bucle [6].

Para evitar que imágenes consecutivas compitan entre s´ı como candidatas a cerrar bucle,iBoW-LCD presenta el concepto de islas dinámicas, que son agrupaciones de imágenes similares tomadas en tiempos consecutivos. La innovación de las islas dinámicas es que estas no parten de todo el conjunto de imágenes si no que parten del conjunto fijado ˜C_t de imágenes similares y que las dimensiones de las islas no son fijas si no que pueden ser variadas en función de parámetros como la velocidad de la cámara, lo que permite adaptar el tamaño de la isla a la secuencia de imágenes.

Sea Υ^m_n una isla que contiene imágenes cuyos instantes de tiempo se encuentran en el rango [m, n], para determinar qué imagen de esta isla será candidata para cerrar bucle se elegirá aquella que tiene una puntuación ˜s más alta. A esta imagen se la conoce como el representante de la isla.

Para construir las islas se parte de la lista de im´agenes filtradas ˜Ct y se procesa cada una de ellas secuencialmente. Para cada imagen I_c ∈ C˜_t (siendoc el instante de tiempo en el que se ha capturadoI), se comprueba

(34)

si su instante de tiempo se encuentra en el rango de alguna isla existente.

Si ese es el caso se asociaI_c a esa isla. En caso contrario, se crea una nueva isla cuyos l´ımites se encuentran alrededor del instantec. Al haber procesado toda la secuencia ˜Ct, se ajustan los l´ımites de las islas para que no haya solapamiento (overlap en ingl´es) entre ellos. En la figura 4.2 se puede ver un ejemplo de c´omo quedan las islas una vez completados todos los pasos previamente mencionados.

Figura 4.2: Representaci´on de 3 islas con dimensiones distintas. N´otese que la imagen 7 (I₇) no forma parte de ninguna isla y que los c´ırculos grises corresponden a los representantes de cada isla [6]

.

A continuación se calcula una puntuación global de isla mediante la ecuación 4.2:

G(Υ^m_n) =

n

X

i=m

˜ s(I_t, I_i)

m−n+ 1 , (4.2)

que se corresponde con la media de las puntuaciones normalizadas de todas las im´agenes asociadas a la isla

En el algoritmo 3 se observa el proceso descrito en los p´arrafos superiores en pseudoc´odigo.

Para determinar cu´al es la isla que m´as probablemente cierre bucle (Υ^∗(t) ∈ Γt) se observa si de entre la secuencia de islas encontradas Γt

hay alguna que solape a nivel temporal con la isla que cerró bucle en el instante de tiempo anterior{t−1}Υ^∗(t−1). En caso de existir alguna isla que cumple esas caracter´ısticas, éstas se conocen comopriority islands. Esto nace de la observación de que si se sigue en la zona en la que se ha cerrado bucle previamente (t−1), es más probable que las imágenes consecutivas capturadas en t sean las que vuelvan a hacerlo. Si se han encontradoprio- rity islandsse elige como candidata para cerrar bucle la que más puntuación tenga. En caso contrario, se escoge la que tenga lap más alta del conjunto de islas generado Γt.

(35)

Algoritmo 3 Construir islas din´amicas

Require: C: Lista ordenada de im´˜ agenes similares Ensure: Γ_t: Lista de islas ordenadas en el instantet.

1: Γt←[]

2: forcada imagenIc∈C˜ do

3: encontrada← false

4: forcada isla Υ^m_n ∈Γt do

5: if m < c < ny no encontradothen

6: asociarAIsla(I_c,Υ^m_n)

7: cambiarTama˜noIsla(Υ^m_n, c, b)

8: encontrado← true

9: if no encontrado then

10: Υ^c−b_c+b← crearNuevaIsla(Ic, b)

11: Γt= Γt∪Υ^c−b_c+b

12: Γt←obtenerIslasSeparadas(Γt)

13: forcada isla Υ^m_n in Γt do

14: G(Υ^m_n)← calcularPuntuacionDeIsla(Υ^m_n)

15: ordenar(Γt)

fundamental mediante el algoritmo RANSAC [92]. Si el número de inliers supera un umbral, se considera que se ha cerrado bucle. Al ser un proceso que requiere de mucho tiempo de cómputo, para evitar calcularinlierspara todos los candidatos se mantiene un registro de las veces consecutivas que se está cerrando bucle y al superar un número determinado de cierres consecutivos y haberpriority islands, se considera que se ha cerrado bucle sin tener que calcularinliers.

4.3. Resultados

En esta sección se muestran los resultados obtenidos por los autores en su art´ıculo original [6]. Éstos servirán como base para analizar las futuras modificaciones. Para obtenerlos, se usó una máquina con un Intel Core i7- 6500U (2.5Ghz) con 12 GB de RAM. AOBIndex2 se le cedieron 4 cores y aiBoW-LCD 1.

La evaluación de un sistema de detección de bucles generalmente se lleva a cabo mediante métricas de precisión - sensibilidad (precision-recall). Para ello, se contrasta el resultado del algoritmo con los correspondientes valores

(36)

de referencia (ground truth), y se calculan los siguientes valores: verdadero positivo (TP por sus siglas en inglés), que es la cantidad de bucles correctos que se han detectado; verdadero negativo (TN por sus siglas en inglés), que corresponde con la cantidad de veces que se ha detectado que no se ha visto la escena en la que está el robot correctamente; falso negativo (FN por sus siglas en inglés), que es la cantidad de veces que no se ha detectado un bucle al pasar por una zona que ya se hab´ıa visitado y falso positivo (FP por sus siglas en inglés), que se corresponde con detectar un bucle cuando no se ha visto la escena en la que se encuentra el robot con anterioridad.

El objetivo fundamental es evitar obtener FPs, ya que al usar la informa- ción de cierre de bucle para corregir el mapa, si esa información es errónea, la distorsión del mapa puede aumentar.

Una vez calculados los datos anteriores, la precisi´on se calcula como:

precisi´on= T P

T P +F P; (4.3)

mientras que la sensibilidad se calcula como:

sensibilidad= T P

T P +F N. (4.4)

Al observar las dos ecuaciones superiores se puede afirmar que es fundamental mantener un valor de precisión del 100 % ya que se desea evitar falsos positivos. El objetivo es, por tanto, obtener la máxima sensibilidad posible manteniendo siempre la precisión al 100 %

Para analizar el comportamiento general de una estrategia de detección de bucles visuales, los valores bh puntuales de precisión - sensibilidad (P- R) se complementan con las denominadas curvas ROC (Receiver Operating Characteristic) de tipo P-R, las cuales se obtienen variando algún paráme- tro cr´ıtico de la estrategia y calculando el par (P,R) para cada caso. De esta forma se dispone de información sobre su rendimiento global, independientemente del valor asignado a su parámetro principal.

En la figura 4.3 se muestra la representación gráfica del comportamiento de OBIndex2 e iBoWLCD al ser ejecutado en distintos datasets públicos como son City Centre (CC) [7], New College (NC) [7], Lip6In (L6I) [93], Lip6Out(L6O) [93],KITTI00 (KOO) [94] yKITTI06 (K06) [94]. Se observa que en todos los casos se consigue una precisión del 100 % manteniendo una sensibilidad muy alta (76.50 % en el peor de los casos). En la tabla 4.1 se detallan los resultados obtenidos tras ejecutar el algoritmo sobre los

(37)

Figura 4.3: Representaci´on de la precisi´on vs la sensibilidad obtenida al procesar distintosdatasets usandoOBIndex2 e IBoWLCD. [6]

del algoritmo sobre los distintos datasets, la m´axima sensibilidad obtenida manteniendo una precisi´on del 100 % y el tiempo en ms que ha tardado en ser ejecutado el algoritmo.

VS R % T(ms) CC 95K 88.25 368.41 NC 98K 79.40 352.05 L6I 4K 83.18 19.17 L6O 121K 85.24 249.45 K00 958K 76.50 432.38 K06 212K 95.53 395.16

Tabla 4.1: Resultados obtenidos al usar OBIndex2 e iBoW-LCD en distintos datasets. VS se corresponde con la medida del diccionario, R % con la sensibilidad (recall) y T(ms) el tiempo de ejecuci´on [6].

(38)

Cap´ıtulo 5

Primer enfoque multi-robot:

detecci´ on de bucles centralizada

En esta sección se va a detallar la primera versión propuesta en este proyecto. Se trata de un sistema distribuido de detección de bucles basado en OBIndex2 eiBoW-LCD, que se ejecutan en un servidor central. Al trabajar en un entorno multi-robot, se incrementa la dificultad para detectar bucles correctamente, ya que las imágenes que forman el diccionario provienen de agentes distintos, lo que debe ser tenido en cuenta a la hora de almacenar y procesar las palabras visuales para buscar bucles, lo que no tiene porque ser tenido en cuenta al usar un único robot.

5.1. Arquitectura

La arquitectura del primer enfoque se ilustra en la figura 5.1, en la que se puede ver que un servidor central se encarga de almacenar el diccionario, compartido por todos los agentes, formado a partir de los descriptores extra´ıdos de las imágenes vistas por cada agente. En el servidor central tam- bién se determina si alguna de esas imágenes cierra bucle con las que se han visto con anterioridad. El servidor central se encarga de ejecutar las versio- nes modificadas deOBIndex2 e iBoW-LCD. Estas modificaciones han sido necesarias para acomodar las librer´ıas originales al nuevo paradigma multi- robot, ya que se debe tener en cuenta que las imágenes recibidas no son

(39)

haber sido enviadas por robots operando en zonas muy distintas del entorno.

Teniendo esto último en cuenta, se ha modificado el sistema de clasificación y almacenamiento de las imágenes para que estas no sigan una numeración secuencial a medida que van llegando al servidor central (como se hac´ıa en la solución de la que parte este proyecto) si no que se clasifican teniendo en cuenta el número de imágenes previas que ha visto el agente y el propio identificador del agente que la ha visto. Todos los métodos que necesitan la identificación de la imagen han sido adaptados para que no solamente miren el número de la misma sino que también tengan en cuenta qué agente las ha enviado. Un ejemplo de estos procesos es el de creación de islas, ya que no solamente se debe tener en cuenta el instante de tiempo en el que han sido capturadas las imágenes que las forman sino que agentes las han tomado.

OBIndex2 e iBoW-LCD (modificados)

Servidor central

Obtención, descripción, filtrado y envío de descriptores captados

por el agente

Agente 1

Agente 2

Agente N Descriptores

por el agente

Figura 5.1: Esquema de la arquitectura usada para llevar a cabo el enfoque centralizado.

También ha sido desarrollada una clase que va a gestionar el comportamiento de los agentes cuando han observado una nueva imagen. Esta clase extrae los puntos de interés de las imágenes recibidas, los describe usando ORB [15] y realiza un filtrado para “seleccionar” los descriptores más estables. Para realizar este filtrado, se almacenan los descriptores vistos en la

´

ultima imagen vista; una vez obtenidos los de la nueva imagen, se busca para cada uno de ellos los 2 m´as parecidos presentes en la imagen anterior;

a continuación, si la distancia de Hamming con el descriptor presente en la imagen previa más parecido es menor a la del segundo más parecido mul- tiplicada por 0,8, se considera que ese descriptor no se trata de ruido y se

(40)

procede a su env´ıo al servidor central para su procesado.

Este tipo de arquitecturas presentan una serie de ventajas:

Es la aplicación distribuida más sencilla y parecida a la versión con un solo robot.

Una única identidad tiene el conocimiento general de todo el entorno, por lo que no es necesario el intercambio de información entre agentes, evitando as´ı el riesgo de colapsos en el canal de comunicación.

Además, al tener concentrada la información en la misma identidad que determina si se ha encontrado un nuevo bucle, se evita el riesgo de perder sensibilidad debido a disponer información parcial del entorno inspeccionado.

A pesar de presentar importantes ventajas, estas arquitecturas dependen de un servidor central para funcionar, por lo que el fallo de ´este, deriva en el cese de funcionamiento total del sistema.

A continuaci´on se resumen las modificaciones llevadas a cabo sobreOBIn- dex2 e iBoW-LCD

5.1.1. Modificaciones realizadas sobre la librer´ıa OBIndex2 Como se ha comentado con anterioridad, la librer´ıa OBindex2 ha sido modificada para que pueda ser usada en entornos multi-robot. Para ello, se han llevado a cabo las siguientes modificaciones:

El ´ındice inverso ha sido modificado para permitir almacenar qu´e agente ha visto cada imagen.

La estructura de datos encargada de almacenar información de cierre de bucles también ha sido modificada para saber qué robot ha visto la imagen con la que se ha cerrado bucle.

Se han añadido funciones que permiten la adición de entradas en el diccionario que incluyan información del robot que las ha enviado.

Se ha modificado la búsqueda de imágenes candidatas para cerrar bucles para tener en cuenta que no es necesario considerar la cercan´ıa entre imágenes si éstas han sido tomadas por agentes distintos. En caso de ser vistas por el mismo agente, se comprueba el parámetro p el cuál indica cuantas imágenes de distancia debe haber para que sean

(41)

de la actual, se acepta la imagen como candidata de cierre de bucle. En caso contrario, la imagen no es considerada v´alida para cerrar bucle ya que se podr´ıa dar el caso de que el robot no haya abandonado la zona en la que se tom´o la imagenny por tanto no resulta posible que se haya encontrado un bucle aunque el algoritmo, al estar en la misma zona, muy probablemente lo considerar´ıa como uno.

Por último, se ha modificado el método para llevar a cabo la depuración selectiva de descriptores para que se tenga en cuenta que ahora se está en un entorno multi-robot.

5.1.2. Modificaciones realizadas sobre iBoW-LCD

Para esta nueva solución distribuida, las islas también tienen que tener en cuenta que las imágenes provienen de robots distintos, es por ello que las estructuras que almacenan la información de las distintas islas y las funciones encargadas de gestionar los contenidos y uso de dichas estructuras han sido modificadas para incluir y saber utilizar la información del número de agente. A continuación se detalla la lista de modificaciones llevadas a cabo.

Se ha incluido en la estructura en el que consisten las islas la informaci´on del agente que ha visto todas las im´agenes que forman parte de ellas.

La funci´on para determinar si una imagen puede ser incluida en una isla ha sido modificada para que al comprobar que una imagen puede formar parte de una isla tambi´en tenga en cuenta que el agente de dicha imagen y el de dicha isla coincidan.

Al método encargado de determinar si 2 islas se solapan también se le han realizado cambios para no solo comprobar que los l´ımites de dos islas distintas están unidos, también deben compartir el agente que las ha visto.

Para el correcto funcionamiento del sistema ha sido creada una clase que permita almacenar palabras visuales y determinar si se ha encontrado un bucle correctamente funcionando en un entorno multi-robot. Para ello se ha partido de las funciones que se usan en el trabajo original introduciendo las siguientes variaciones:

El proceso de construcción de islas ha sido rediseñado para construir islas cuyas imágenes siempre hayan sido vistas por un mismo agente.

(42)

La funci´on usada para obtener islas prioritarias mantiene su estructura original debido a que las modificaciones hechas en la clase encargada de la gesti´on de islas son suficientes para adaptar el funcionamiento del sistema a una plataforma multi-robot.

En determinados puntos del programa, la solución original almacena información del último bucle encontrado. Debido a que se ha adap- tado dicha solución para trabajar en un entorno multi-robot, ha sido necesario adaptar también las estructuras necesarias para almacenar la información de cierre de bucle de cada uno de los agentes.

5.2. Resultados

Para comprobar el funcionamiento del algoritmo, éste ha sido evaluado sobre 5 datasets públicos: Lip6In [93],Lip6Out [93], City Centre [7],KIT- TI00 [94] y KITTI05 [94]. Todos los experimentos han sido ejecutados en una máquina equipada con una CPU Intel i7-5820K y 16 GB de RAM. La ejecución del algoritmo para un número concreto de agentes, guarda los resultados en ficheros de texto, que posteriormente se procesan con MATLAB.

Además de las medidas de precisión - sensibilidad, también se han obtenido los tiempos de ejecución y la cantidad de palabras que forman el diccionario al final de la ejecución del algoritmo.

5.2.1. Resultados para Lip6In

En la figura 5.2, se observan las curvas de P-R (precision - recall en inglés) para este dataset y diversos números de agentes. Estas curvas han sido obtenidas variando el número deinliers m´ınimo para aceptar la detec- ción de bucle. Se puede apreciar como la sensibilidad, en el caso de tener solamente un solo robot funcionando, disminuye levemente con respecto a los resultados del algoritmo original (figura 4.3). Esto es debido a que, al contrario que la solución propuesta en el trabajo de los autores originales [6], en este proyecto se realiza un filtrado previo de las imágenes que reciben los agentes lo que hace que en algunos casos imágenes que se interpretan como ruido no sean enviadas al diccionario. En el caso de este dataset, este fenómeno es muy pronunciado ya que ha sido tomado en el interior de un edificio en el que se han girado muchas esquinas, cosa que produce imágenes con ruido. Esto permite mantener diccionarios más ligeros pero en algunos

(43)

se observa que el comportamiento no tiene grandes variaciones ya que los valores de la sensibilidad se mantienen relativamente estables llegando a un máximo en el caso de usar 3 agentes tanto usando el sistema de depuración selectiva de descriptores como no usándolo.

0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0.7 0.75 0.8 0.85 0.9 0.95 1

Sensibilidad

Precision

N = 1 N = 2 N = 3 N = 4 N = 5

0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0.7 0.75 0.8 0.85 0.9 0.95 1

Sensibilidad

Precision

N = 1 N = 2 N = 3 N = 4 N = 5

Figura 5.2: Resultados obtenidos al ejecutar la solución centralizada sobre eldataset Lip6In sin usar la depuración selectiva en el diccionario (figura de la izquierda) y usándola (figura de la derecha)

Al observar la tabla 5.1 se puede ver un resumen de los resultados obtenidos al ejecutarLip6In. La sensibilidad representada es la máxima obtenida manteniendo una precisión del 100 %, viéndose que el peor de los casos es cuando se están usando 4 agentes, obteniendo un valor de 34.82 % en el caso de usar el sistema de depuración selectiva de descriptores y 2 agentes (sensibilidad de 44.52 %) al no usar el sistema de depuración selectiva de descriptores. Nótese también el decremento de palabras visuales en el diccionario al estar purgándolo constantemente. También se observa como los tiempos se mantienen aproximadamente constantes en ambos casos. A pesar de que en unos de los casos se está bajando hasta una sensibilidad de 34.82 %, estos resultados podr´ıan llegar a ser válidos para un sistema SLAM ya que en trabajos como ORB-SLAM 2 [8] se consiguen muy buenos resultados llegando a sensibilidades máximas muy parecidas a las m´ınimas obtenidas en este proyecto.

5.2.2. Resultados para Lip6Out

Si se observan los resultados representados en la figura 5.3, se aprecia que en el caso de estar trabajando ´unicamente con un solo robot, los datos llegan hasta el 90 % de sensibilidad lo que supera el valor obtenido por