Repositorio Institucional de Documentos

Proyecto Fin de Carrera Ingeniería Informática NAVEGACIÓN VISUAL USANDO UNA DESCRIPCIÓN DE LA RUTA CON SECUENCIAS DE IMÁGENES Eduardo Montijano Muñoz Director: Carlos Sagüés Blázquiz Departamento de Informática e Ingeniería de Sistemas Centro Politécnico Superior Universidad de Zaragoza Septiembre 2007 Índice general Índice de guras 4 Índice de tablas 6 1. Objeto y alcance 7 1.1. Introducción................................... 7 1.2. Objetivos .................................... 8 1.3. Alcance ..................................... 9 1.4. Estructura de la memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2. Técnicas de visión por computador 12 2.1. Características de las imágenes . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.1. Contornos verticales . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.2. Características SURF . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2. Emparejamientos: emparejamiento robusto . . . . . . . . . . . . . . . . . . 15 2.2.1. MétodoRANSAC............................ 16 2.2.2. MétodoLMS .............................. 16 2.2.3. Optimizaciones en los algoritmos . . . . . . . . . . . . . . . . . . . 17 2.3. Cálculo de homografías . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3. Algoritmos de navegación 19 3.1. Estimación del ángulo de desviación . . . . . . . . . . . . . . . . . . . . . . 20 3.2. Correcciones del ángulo de desviación . . . . . . . . . . . . . . . . . . . . . 20 3.3. Algoritmos de navegación . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3.1. Fase de aprendizaje . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3.2. Fase de repetición . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.4. Aplicación desarrollada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4. Experimentos realizados 28 4.1. Experimentos estáticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.2. Movimientos sencillos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.3. Trayectorias complejas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1 ÍNDICE GENERAL 2 5. Resultados obtenidos 31 5.1. Calidad de los emparejadores . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.2. Calidad de los sistemas de extracción de características . . . . . . . . . . . 33 5.2.1. Problema del entrelazado . . . . . . . . . . . . . . . . . . . . . . . . 34 5.2.2. Tiempos de cómputo . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.2.3. Homografías obtenidas . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.3. Movimientos sencillos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.3.1. Reparación de la orientación respecto a una imagen de referencia . 36 5.3.2. Correcciones en desplazamientos longitudinales . . . . . . . . . . . 39 5.3.3. Correcciones en giros . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.4. Trayectorias complejas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.4.1. Umbral de corrección . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.4.2. Velocidades de movimiento . . . . . . . . . . . . . . . . . . . . . . . 43 5.4.3. Acondicionamiento del entorno . . . . . . . . . . . . . . . . . . . . 43 5.4.4. Imágenes tomadas durante el aprendizaje . . . . . . . . . . . . . . . 44 6. Conclusiones y trabajos futuros 45 6.1. Conclusiones................................... 45 6.2. Dicultades encontradas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 6.3. Trabajosfuturos ................................ 47 7. Principales hitos temporales y diagrama de Gant 48 7.1. Hitosdelproyecto................................ 48 7.2. DiagramadeGant ............................... 49 A. Hardware de desarrollo 50 A.1.Hardwareutilizado ............................... 50 A.2.LibreríasPlayer................................. 50 B. Extractores de características en imágenes 52 B.1. Extracción de contornos verticales . . . . . . . . . . . . . . . . . . . . . . . 52 B.1.1.Segmentación.............................. 52 B.1.2. Localizando la línea . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 B.1.3. Atributos escogidos . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 B.2. SURF (Speeded Up Robust Features) . . . . . . . . . . . . . . . . . . . . . 54 B.2.1.Puntosdeinterés............................ 55 B.2.2. Características de los descriptores . . . . . . . . . . . . . . . . . . . 56 B.3. Detector de esquinas de Harris . . . . . . . . . . . . . . . . . . . . . . . . . 57 B.4.SIFT....................................... 59 C. Técnicas de emparejamiento 61 C.1. Emparejamiento básico de características . . . . . . . . . . . . . . . . . . . 61 C.1.1. Emparejamiento de rectas . . . . . . . . . . . . . . . . . . . . . . . 61 C.1.2. Emparejador de puntos SURF . . . . . . . . . . . . . . . . . . . . . 62 C.2. Emparejamiento robusto de características previamente emparejadas . . . . 63 Navegación visual usando una descripción de la ruta con secuencias de imágenes ÍNDICE GENERAL 3 C.2.1.RANSAC ................................ 63 C.2.2. Least Median of Squares (LMS) . . . . . . . . . . . . . . . . . . . . 66 D. Cálculo de homografías 68 D.1. Coordenadas homogéneas . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 D.2. Matrices de transformación . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 D.3. Sistema de ecuaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 D.4. Sistema sobredimensionado . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 E. Manual de usuario 72 E.1. Interacción con el usuario . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 E.2.Ayudainteractiva................................ 73 E.3. Conguración del programa . . . . . . . . . . . . . . . . . . . . . . . . . . 74 E.3.1. Nombre de la misión . . . . . . . . . . . . . . . . . . . . . . . . . . 74 E.3.2.Sistemadevisión............................ 74 E.3.3.Emparejamiento............................. 74 E.3.4.Guardarimágenes............................ 75 E.4. Opciones que no provocan movimiento del robot . . . . . . . . . . . . . . . 75 E.4.1.Capturarimagen ............................ 75 E.4.2.Calibrarrobot.............................. 76 E.4.3.Mostrarpuntos ............................. 76 E.4.4.Guardarpuntos............................. 76 E.4.5.Testderobustez ............................ 77 E.4.6. Resetear odometría . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 E.4.7.Salir ................................... 77 E.5.Moviendoelrobot................................ 78 E.5.1.DEMO.................................. 78 E.5.2.Reparargiro............................... 78 E.5.3. Aprendizaje por guiado . . . . . . . . . . . . . . . . . . . . . . . . . 79 E.5.4.Realizarmisión............................. 79 F. Estructura del código 80 F.1. Gestión de Conguraciones . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 F.2. Estructura del programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 F.3. Eciencia de los algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 F.4. Listado de cheros C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 F.5.CódigoMATLAB................................ 85 G. Relación del proyecto con la Ingeniería Informática 86 Bibliografía 87 Navegación visual usando una descripción de la ruta con secuencias de imágenes Índice de guras 2.1. Rectas verticales extraídas de una imagen . . . . . . . . . . . . . . . . . . 13 2.2. Características SURF de una imagen . . . . . . . . . . . . . . . . . . . . . 14 2.3. Emparejamientos entre dos imágenes . . . . . . . . . . . . . . . . . . . . . 15 3.1. Ejemplo de corrección en desplazamiento longitudinal . . . . . . . . . . . . 21 3.2. Esquema del algoritmo de navegación utilizado . . . . . . . . . . . . . . . . 22 3.3. Evolución del valor de las correcciones . . . . . . . . . . . . . . . . . . . . 24 3.4. Reparación de la orientación . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.1. Error cometido en la posición por error de orientación . . . . . . . . . . . . 29 5.1. Resultados del emparejamiento básico . . . . . . . . . . . . . . . . . . . . . 32 5.2. Resultados utilizando emparejamiento robusto RANSAC . . . . . . . . . . 32 5.3. Resultados utilizando emparejamiento robusto LMS . . . . . . . . . . . . . 33 5.4. Muestreo de una imagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.5. Problema del entrelazado . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.6. Reparación de la orientación . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.7. Reparación con velocidad lenta y margen de error grande . . . . . . . . . . 38 5.8. Reparación con velocidad alta y margen de error pequeño . . . . . . . . . . 38 5.9. Ejemplo de giro sin reparaciones . . . . . . . . . . . . . . . . . . . . . . . . 40 5.10. Ejemplo de giro realizando una reparación en cada imagen de referencia . . 41 5.11. Ejemplo de giro realizado mediante reparaciones . . . . . . . . . . . . . . . 41 5.12. Ejemplo de giro realizando una reparación al nalizar la rotación . . . . . . 42 5.13. Imágenes capturadas durante un aprendizaje . . . . . . . . . . . . . . . . . 44 A.1. Robots Pioneer del Grupo de Robótica, Percepción y Tiempo Real . . . . . 51 B.1. Segmentación de la imagen en regiones de soporte de recta LSR. . . . . . . 53 B.2.FiltrosdecajaSURF.............................. 55 B.3. Ejemplo de imagen con los puntos SURF extraídos . . . . . . . . . . . . . 57 B.4. Dos imágenes normales del mismo paisaje . . . . . . . . . . . . . . . . . . 57 B.5. Imagen panorámica compuesta a partir de dos imágenes normales . . . . . 58 B.6. Píxeles comparados para encontrar máximos locales en SIFT . . . . . . . . 59 B.7. Histogramas de orientación SIFT para el cálculo del descriptor . . . . . . . 60 C.1. Ejemplo de conjunto de puntos para ajustar a una recta . . . . . . . . . . 63 4 ÍNDICE DE FIGURAS 5 E.1.Aplicación.................................... 73 Navegación visual usando una descripción de la ruta con secuencias de imágenes Índice de tablas 5.1. Relación entre la velocidad de giro y la tolerancia en la reparación . . . . . 39 5.2. Velocidad máxima en la fase de aprendizaje y en la de repetición . . . . . . 43 7.1. DiagramadeGant ............................... 49 C.1. Valores de m en función de ε y s ........................ 65 6 Capítulo 1 Objeto y alcance 1.1. Introducción Desde el principio de su existencia, el hombre siempre se ha propuesto inventar artefactos que simpliquen las tareas que realiza en su día a día. Los avances de la ciencia en los últimos años han permitido el desarrollo de máquinas que puedan realizar tareas complejas de manera autónoma, y entre todas ellas se debe destacar a los robots. Las tareas que realizan en la actualidad los robots suelen ser sencillas y de carácter repetitivo. En muchos casos, además, se trata de tareas que se realizan en espacios interiores, lo que implica que los entornos en los que se va a mover son poco cambiantes. Algunas de ellas requieren que un robot móvil repita constantemente un camino que ha aprendido para llevar y traer objetos. Un ejemplo de estas características podría ser un robot cartero, en el seno de una empresa. El robot repite todos los días la misma ruta para entregar las cartas a sus destinatarios. Los robots reales distan mucho de parecerse a los descritos en novelas o películas de ciencia cción, máquinas pensantes con alta capacidad de raciocinio. Actualmente, en el marco de investigación y realizaciones de prototipos experimentales existen robots con capacidad de realizar algunas tareas sencillas en las que tanto el movimiento como la percepción se llevan a cabo de forma autónoma. Los robots deben entenderse como herramientas que simpliquen la vida de los humanos. Tareas que podrían suponer un riesgo potencial para las personas pueden ser ejecutadas por robots de manera automática, minimizando así los riesgos. Entre estas tareas se podrían destacar el transporte de objetos pesados o sustancias tóxicas, o tareas relacionadas con la exploración de un terreno desconocido. Naturalmente, a los robots también se les pueden asignar tareas domésticas que, aunque no impliquen un riesgo para nuestra seguridad, consigan hacer nuestras vidas más agradables. Existen múltiples formas de realizar trayectorias que debe seguir un robot; las más sencillas son las que utilizan una planicación estática con la hipótesis de que el entorno no cambia y es conocido. Otras, más complejas, emplean planicación dinámica y calculan los objetivos dependiendo de la información que obtienen en tiempo real del medio en que 7 1. Objeto y alcance 8 se encuentran. Suele ocurrir que, independientemente del tipo de planicación que se use, el robot no consigue llegar a su destino. La principal causa es la falta de precisión de los sensores de la odometría (posición y orientación respecto a las coordenadas iniciales) del robot. Esto puede ser debido a que no tienen en cuenta la fuerza de rozamiento, la utilización de velocidades muy grandes o muy pequeñas o a otras causas ajenas al robot tales como pequeños obstáculos encontrados en el camino, etc... Para corregir estos errores debe recurrirse a técnicas adicionales de percepción del entorno que aporten información más precisa de la localización exacta del robot. La generación de mapas con sensores láser o el uso de técnicas de visión por computador son algunos ejemplos de métodos que se utilizan en la actualidad para reducir los errores cometidos por los sensores odométricos. Para que el diseño de estas técnicas de percepción sea el adecuado hay que considerar varios aspectos. Así, si se pretende que las correcciones puedan realizarse en tiempo real habrá que conseguir que el método utilizado sea eciente; por otro lado, para que el error sea lo más pequeño posible necesitaremos garantizar que nuestro método sea robusto. Muchas veces, que un sistema sea robusto implica que no sea eciente, ya que necesita una gran cantidad de cálculos adicionales para garantizar la calidad de los resultados que obtiene. Conseguir un equilibrio entre eciencia y robustez puede resultar complicado y es uno de los principales objetivos de los investigadores a la hora de diseñar nuevos métodos para la realización autónoma de tareas de movimiento o percepción. En este proyecto se estudian algunos métodos que utilizan la visión por computador como medio para corregir errores en la repetición de trayectorias, analizando las ventajas e inconvenientes de las distintas técnicas utilizadas y proponiendo mejoras en las mismas que las hagan más ecientes y robustas. 1.2. Objetivos El objetivo principal de este proyecto ha sido la mejora en los algoritmos de control de movimientos del robot, dando lugar a comportamientos más ables en la repetición de trayectorias aprendidas previamente utilizando técnicas de visión por computador. Cumplir este objetivo ha implicado la realización de un estudio comparativo de varias técnicas de extracción de características de imágenes en el ámbito de la navegación de un robot en un entorno cerrado que utiliza imágenes de referencia. Para realizar este estudio se ha diseñado un amplio conjunto de experimentos que permitan comparar los métodos seleccionados a diferentes niveles. Estos experimentos evaluarán la ecacia de los métodos, su coste computacional y la robustez que presentan en distintas situaciones. Navegación visual usando una descripción de la ruta con secuencias de imágenes 2. Técnicas de visión por computador 15 2.2. Emparejamientos: emparejamiento robusto Una vez que se han extraído las características de las imágenes se emplea un emparejador para encontrar correspondencias entre ambas. La distancia de Mahalanobis o la norma euclídea son dos funciones que se utilizan habitualmente para calcular los emparejamientos. Los métodos empleados en este proyecto para el emparejamiento básico o inicial son muy utilizados en el campo de la visión por computador y se detallan en el apéndice C Con los emparejamientos obtenidos se plantea un sistema de ecuaciones que permite obtener una restricción geométrica entre las imágenes que se usa para obtener mejores emparejamientos y, posteriormente, para calcular el movimiento relativo entre las imágenes. Suele ocurrir que, dentro del conjunto de emparejamientos, hay un porcentaje de ellos que son espurios (véase gura 2.3) . Si se resuelve el sistema sobredimensionado sin eliminarlos, la solución que se obtiene no es la correcta. Para que la matriz de homografía calculada sea correcta hay que conseguir eliminar los emparejamientos espurios del conjunto de emparejamientos obtenido, este proceso se conoce como emparejamiento robusto. Existen diversas técnicas de emparejamiento robusto que consiguen eliminar los emparejamientos no deseados. En este proyecto se han realizado experimentos con dos métodos de emparejamiento robusto probabilísticos. Figura 2.3: Ejemplo de emparejamientos entre puntos SURF extraídos de dos imágenes. En la imagen se pueden apreciar algunos emparejamientos espurios. Navegación visual usando una descripción de la ruta con secuencias de imágenes 2. Técnicas de visión por computador 16 2.2.1. Método RANSAC El método RANSAC (RANdom SAmple Consensus) [14] es un método de emparejamiento robusto que da como resultado la solución más votada de entre unas cuantas, calculadas a partir de conjuntos mínimos obtenidos aleatoriamente. Para calcular una homografía en dos dimensiones se necesitan un mínimo de tres emparejamientos. La idea del método RANSAC consiste en seleccionar un número de subconjuntos de tres emparejamientos elegidos aleatoriamente dentro del total, que garantice que, con una probabilidad superior al 99%, al menos uno de dichos subconjuntos contendrá sus tres emparejamientos correctos, es decir, que ninguno de ellos es un espurio. Para cada uno de los subconjuntos formados se calcula la homografía. Esta homografía se valora mediante un sistema de votaciones. Para ello, se ja un umbral que separe los emparejamientos buenos de los malos para esta homografía. Un emparejamiento se considerará bueno si y sólo si la homografía lleva una característica a la otra con un error menor que el umbral considerado. Se contabiliza el número de emparejamientos buenos (votos favorables), quedándonos al nal con la homografía que más votos haya tenido. Una vez que se ha elegido la homografía más votada como solución, se consideran emparejamientos buenos aquellos que hayan votado a dicha solución, mientras que los espurios serán los que no la hayan votado. Para reducir el coste computacional, en el momento en que una homografía recibe más del 95% de los votos, esta se considera solución denitiva. De esta forma en conjuntos con un porcentaje pequeño de espurios el cálculo de la solución es casi inmediato. 2.2.2. Método LMS LMS proviene de las palabras inglesas Least Median of Squares (mínimo error de la mediana) [15]. Este método, al igual que el método RANSAC es un método probabilístico. La idea del método es similar a la que emplea RANSAC; se selecciona aleatoriamente un número de subconjuntos y se calcula la homografía para cada uno de ellos. En este caso, en lugar de realizar votaciones, lo que se hace es calcular los residuos que genera el conjunto total de emparejamientos para cada homografía. De todas las soluciones obtenidas el método escoge aquella que minimice la mediana de los cuadrados de los residuos. La ventaja de este método frente a RANSAC es que no necesita jar umbrales. Sin embargo, es más costoso computacionalmente. Partiendo de la hipótesis de que los datos se ajustan a una distribución normal, para eliminar los emparejamientos espurios el método LMS calcula un umbral σ en función del valor de la mínima mediana obtenida, y elimina todos aquellos emparejamientos cuyo residuo sea superior a dos veces el cuadrado de dicho valor. Navegación visual usando una descripción de la ruta con secuencias de imágenes 2. Técnicas de visión por computador 17 r2 i≤(2 ∗ˆσ2) 2.2.3. Optimizaciones en los algoritmos Para optimizar el cálculo de las homografías se puede utilizar la solución que se obtiene de los emparejadores robustos como solución denitiva o bien realizar una criba de espurios y resolver el sistema sobredimensionado para obtener una matriz de homografía. En el programa se ha incorporado la opción de realizar o no una criba de espurios y resolver el nuevo sistema sobredimensionado. En el capítulo de experimentos realizados y en el de resultados se trata con más detalle esta idea. En el apéndice C se adjunta una información mucho más detallada acerca de las técnicas de emparejamiento robusto utilizadas. 2.3. Cálculo de homografías En coordenadas homogéneas, para transformar puntos del plano se emplean matrices 3x3 denominadas matrices de transformación . La transformación de un punto p a otro q mediante una matriz de transformación tiene la forma: p = Hq . (2.2) En esta parte del proceso se trata de encontrar una matriz H que satisfaga la condición 2.2 para los puntos p y q emparejados. Como no se puede satisfacer para todo el conjunto de emparejamientos a la vez, el objetivo es satisfacer 2.2 con el menor error posible, por ejemplo en el sentido de mínimos cuadrados. Calcular una matriz de transformación 3x3, por lo tanto con 8 parámetros a determinar ya que existe un factor de escala, requiere 8 ecuaciones, y en consecuencia, se necesita un mínimo de 4 emparejamientos entre las características extraídas de las dos imágenes que se estén considerando. En las condiciones en las que se desarrolla este proyecto el movimiento va a ser siempre plano y las imágenes van a tener muy poco baseline , desplazamiento muy pequeño entre los centros ópticos. Partiendo de este hecho se puede realizar una simplicación en el problema eliminando de los cálculos la segunda coordenada de los puntos. Con esta simplicación, el problema del cálculo de la matriz de transformación queda reducido al cálculo de una matriz H de dimensión 2x2, que cumpla, para los emparejamientos obtenidos λ x 1 λ=h11 h12 h21 h22  x 2 1 (2.3) Navegación visual usando una descripción de la ruta con secuencias de imágenes 2. Técnicas de visión por computador 18 donde x 1 representa la coordenada x del punto p , extraído de la primera imagen, y x 2 representa la coordenada x del punto q (emparejamiento de p ) en la segunda imagen. En este caso solo hay que determinar 3 parámetros, cosa que se puede hacer utilizando únicamente 3 emparejamientos. Si suponemos que todas las características extraídas se encuentran en un mismo plano, la matriz que se obtiene se conoce con el nombre de matriz de homografía. En [2] se demuestra que existe una relación entre dicha matriz y el ángulo de rotación que se ha producido en la cámara para pasar de una imagen a la otra siempre que el movimiento de traslación sea pequeño El desarrollo de las ecuaciones para calcular la matriz de homografía a partir de los emparejamientos, así como una explicación más detallada de sus características, se encuentra detallado en el apéndice D. Navegación visual usando una descripción de la ruta con secuencias de imágenes Capítulo 3 Algoritmos de navegación Se puede denir la navegación de un robot como el movimiento que sigue entre un punto inicial, que llamaremos punto de partida, y un punto nal, denominado objetivo. Cuando el robot conoce las coordenadas de ambos puntos es capaz de desplazarse de uno a otro utilizando sus sensores odométricos. Sin embargo, la medida del desplazamiento mediante sensores de odometría es muy poco precisa y además los errores se van acumulando. Al nal, el error total puede ser muy grande. Es por ello que, aunque de acuerdo con la odometría el robot haya llegado a su objetivo, este se encuentra en una posición completamente distinta. Se ha dedicado mucho trabajo de investigación a la búsqueda de técnicas de corrección que permitan a los robots introducir correcciones en sus trayectorias con el objetivo de mejorar la navegación y conseguir movimientos más ables. Las técnicas basadas en visión que se van a utilizar en este proyecto funcionan de la siguiente manera. En una primera fase, denominada de fase de aprendizaje, se guía al robot describiendo el movimiento que se desea que repita posteriormente de manera autónoma y se van tomando imágenes de referencia, que servirán posteriormente para efectuar las correcciones cuando el robot repita el desplazamiento sin intervención humana. Esta navegación autónoma es la segunda fase del sistema, y se denomina fase de repetición. Las cuestiones que surgen al utilizar este esquema son la determinación de los instantes más adecuados para tomar imágenes de referencia, cómo utilizar las imágenes de referencia para saber qué correcciones hay que hacer y cuándo y cómo hay que llevarlas a cabo. Todos estos aspectos se tratan a lo largo de este capítulo. En particular se describen los algoritmos que se han diseñado para realizar navegaciones robustas con el robot empleando, además de la odometría, los datos de corrección que proporciona la matriz de homografía. 19 3. Algoritmos de navegación 20 3.1. Estimación del ángulo de desviación Si se quiere corregir los errores en el movimiento del robot, es necesario conocer cuáles son estos errores. Como se ha visto en el capítulo anterior, se puede utilizar la matriz de homografía para realizar una estimación del error del robot en su orientación, comparando imágenes tomadas en tiempo real con imágenes de referencia almacenadas previamente. Dicha estimación proporciona el ángulo que se tiene que girar la cámara sobre su eje vertical para que la segunda imagen coincida con la primera, es decir, el ángulo que hay que girar el robot para corregir su desviación. Para obtener el valor exacto de la corrección se ha empleado el parámetro h21 de la matriz de homografía. Después de varios experimentos, se ha ajustado el valor de la corrección, es decir, el ángulo de giro θ entre las imágenes, con la siguiente fórmula: θ=−arctan (h21) (3.1) En [2] se justica la bondad en el uso de este parámetro, h21 como estimador del error de orientación. Los otros parámetros de la matriz también se pueden usar como estimadores pero presentan una mayor sensibilidad al ruido y a los errores en la matriz, por lo que se comportan de manera menos able. Si tenemos una imagen que representa una referencia tomada previamente por el robot, entonces habrá que conseguir, mediante correcciones en su movimiento, principalmente rotaciones, que las imágenes que éste tome en tiempo real se aproximen todo lo posible a la de referencia. 3.2. Correcciones del ángulo de desviación Notemos que no solo basta con conocer el ángulo de corrección necesario, sino que también hay que saber como utilizarlo en la navegación. Para realizar las correcciones en tiempo real hay que tener en cuenta el tipo de movimiento que está realizando el robot. Si el robot se está desplazando hacia adelante (o está retrocediendo), el programa de control deberá asignarle una velocidad angular dependiendo del valor obtenido en la comparación de imágenes. De esta forma el robot consigue volver a situarse en la recta del recorrido aprendido. La imagen 3.1 muestra un ejemplo de esta situación. Cuando el robot se encuentra realizando un giro, realizar la corrección resulta más complicado. Por una parte, puesto que el robot está girando, la comparación de las imágenes necesariamente va a indicar que se debe realizar un giro. No hay ninguna forma de saber qué parte de este valor corresponde a corrección y qué parte corresponde al giro que se está realizando. Modicar la velocidad angular en tiempo real no aporta precisión en el giro. En capítulos posteriores se exponen algunas soluciones que se han probado, y los resultados que se han obtenido para resolver este problema con cada una de ellas. Navegación visual usando una descripción de la ruta con secuencias de imágenes 3. Algoritmos de navegación 21 ϕ Figura 3.1: Ejemplo de corrección seguida por el robot en un desplazamiento longitudinal. La línea discontinua muestra el recorrido que debería seguir el robot y la linea de trazo continuo muestra el recorrido real seguido al comenzar con un error de orientación. Es importante observar que en la mayoría de las situaciones, las correcciones necesarias son muy pequeñas, apenas unos grados. Para evitar que el robot realice giros demasiado bruscos serán necesarias velocidades angulares no mayores que unos pocos grados por segundo. 3.3. Algoritmos de navegación Existen numerosos algoritmos de navegación basados en visión por computador. Algunos investigadores, como Chen [10] proponen mantener velocidad lineal constante y utilizar las imágenes para realizar las correcciones de rotación, mediante un sistema de votaciones sobre las características emparejadas. Otros algoritmos emplean exclusivamente la odometría para el movimiento, y utilizan las imágenes para realizar correcciones de rotación [1]. Para este proyecto se ha decidido utilizar una versión modicada del algoritmo de navegación que propone Yoshio Matsumoto [11] [12]. Este algoritmo propone añadir marcas de movimiento a las imágenes de referencia, de esta forma el robot sabe en cada momento el tipo de movimiento que debe realizar (avanzar, girar a la izquierda, a la derecha, etc...). Se ha elegido este algoritmo por varios motivos. En primer lugar, el uso de marcas de navegación en las imágenes de referencia permite realizar movimientos más complejos que los permitidos en [10]. La idea de este algoritmo se adapta muy bien a la corrección en tiempo real de la trayectoria utilizando matrices de homografía. La versión que se ha implementado como parte de este proyecto, incorpora además información de la odometría del robot en el instante en que se ha tomado cada imagen. La combinación del uso de la odometría con los valores de las correcciones que se obtienen en tiempo real ha permitido conseguir unos resultados mucho mejores que los que se obtienen utilizando cada uno de los datos por separado. Navegación visual usando una descripción de la ruta con secuencias de imágenes 3. Algoritmos de navegación 22 Figura 3.2: Esquema del algoritmo de navegación utilizado [11]. 3.3.1. Fase de aprendizaje En esta fase el robot capta imágenes y almacena sus características conforme efectúa el recorrido a repetir. Un punto importante es saber cuándo hay que almacenar la información de una imagen. Si se almacenan muchas imágenes, se pierde eciencia; si, por el contrario no se toman sucientes, el control de correcciones en la fase de repetición no será able. Si se emplea la odometría como único criterio para determinar los instantes en los que se almacenan imágenes (por ejemplo, almacenar una imagen cada metro recorrido), podemos obtener resultados pobres porque no se tiene en cuenta la calidad de las características extraídas. En el algoritmo diseñado se ha tenido en cuenta la odometría, y como segunda condición para el almacenamiento de nuevas imágenes de referencia la corrección respecto a la última imagen de referencia almacenada. Si el robot ha capturado una imagen en un instante del recorrido, conforme se vaya desplazando irá tomando imágenes y el valor de la Navegación visual usando una descripción de la ruta con secuencias de imágenes 3. Algoritmos de navegación 23 corrección que obtendrá para estas imágenes respecto a la de referencia irá aumentando. Cuando el valor de la corrección supere un determinado umbral, el robot almacenará la nueva imagen y la tomará como nueva referencia. De esta forma al acabar el recorrido, el robot ha almacenado un conjunto de imágenes que dieren entre ellas el umbral de corrección o se encuentran a una distancia determinada. Es importante observar que cuando se habla de almacenar una imagen, no se almacena la imagen como tal, sino solamente las características que se han extraído de ella y la odometría del robot en la que se ha tomado. De esta forma se ahorra una gran cantidad de espacio en disco y la necesidad de volver a extraer las características de la imagen en la fase de repetición. Ahora bien, si solo se almacenan las características extraídas de cada imagen, en la etapa de repetición el robot no sabrá qué clase de movimiento debe realizar para repetir la trayectoria. Para que esto no ocurra, a cada imagen se le asocia una etiqueta de movimiento que indique al robot lo que debe hacer. Las etiquetas que se han empleado son la siguientes: AVANZAR (indica que el robot debe moverse hacia adelante a partir de esta imagen) RETROCEDER (indica que el robot debe moverse hacia atrás a partir de esta imagen) GIRAR_IZQUIERDA (indica que el robot debe girar hacia la izquierda a partir de esta imagen) GIRAR_DERECHA (indica que el robot debe girar hacia la derecha a partir de esta imagen) PARAR (identica la última imagen del recorrido, correspondiente al punto de destino) Además de todo lo anterior, el robot también almacena la posición, indicada por la odometría, en que ha tomado la imagen. De esta forma, en la fase de repetición se podrá decidir mediante un criterio más robusto cuando se debe avanzar de imagen dentro de la lista obtenida durante el aprendizaje, como se explicará más adelante. 3.3.2. Fase de repetición En la fase de repetición el robot utiliza las imágenes de referencia tomadas en el aprendizaje para repetir la trayectoria. Si el robot sólo tiene en consideración una imagen de referencia en cada momento, será capaz de corregir su error de orientación respecto a dicha imagen pero no sabrá en qué momento debe pasar a la siguiente de la lista. Para solventar esta dicultad, el robot trabaja en cada instante con dos imágenes de referencia consecutivas. Navegación visual usando una descripción de la ruta con secuencias de imágenes 3. Algoritmos de navegación 24 El proceso puede considerarse de la siguiente forma: partiendo de una posición correspondiente a una imagen de referencia, el robot debe desplazarse en el sentido indicado por la etiqueta de movimiento de dicha imagen hasta llegar a la posición asociada a la siguiente imagen de referencia. Inicialmente la corrección con respecto de la primera imagen será prácticamente nula, mientras que la corrección con respecto a la siguiente imagen de referencia será probablemente próxima al umbral de corrección jado en la etapa de aprendizaje. Es de esperar que conforme el robot se desplaza la corrección respecto de la primera imagen vaya aumentando, mientras que la corrección con respecto de la segunda irá disminuyendo. En la práctica estas variaciones tienen un comportamiento casi lineal, tal y como muestra la gura 3.3. Cuando la corrección respecto de la primera imagen sea sucientemente alta, y la corrección respecto de la segunda esté sucientemente próxima a cero, signicará que se ha alcanzado la posición correspondiente a la segunda imagen y, por tanto, ha llegado el momento de avanzar en la lista de imágenes, repitiendo para las nuevas imágenes el proceso anterior. valor corrección odometría umbral corrección Pos_img_1 Pos_img_2 Figura 3.3: Evolución del valor de las correcciones. En rojo se observa el valor de la corrección respecto a la primera imagen y en azul el valor de la corrección respecto a la segunda. Si sólo se emplean los valores de las dos correcciones para cambiar de imagen de referencia, puede ocurrir que el cambio se realice demasiado pronto o muy tarde. Entre imágenes que tienen la misma etiqueta de movimiento, estos desfases no representan un gran problema, ya que la antelación en un cambio se compensa con el retraso en el siguiente y viceversa. Sin embargo, cuando el cambio de imagen requiere de un cambio de tipo de movimiento, los errores que se produzcan pueden condicionar el resultado de la trayectoria. Un pequeño error en la orientación puede generar grandes errores en la posición si el robot se desplaza longitudinalmente. También se ha visto que emplear la odometría como única medida para determinar el instante en el que hay que cambiar de imagen de referencia no es adecuado, ya que los errores en la odometría son acumulativos, y al nal el robot nunca se encuentra donde se supone. Navegación visual usando una descripción de la ruta con secuencias de imágenes Capítulo 5 Resultados obtenidos En relación con los experimentos detallados en el capítulo 4, se resumen en este capítulo los resultados más destacados. 5.1. Calidad de los emparejadores En primer lugar se ha realizado una simulación con datos aleatorios para estudiar la probabilidad con la que cada emparejador es capaz de generar la solución correcta (matriz de homografía) en función del porcentaje de espurios que haya en el conjunto de emparejamientos. Entendamos una prueba como la generación de una matriz de homografía H aleatoria y 35 puntos p i también aleatorios. Con estos datos se han generado los 35 puntos q i emparejados realizando la transformación: q i= Hp i (5.1) de esta forma se garantiza que la matriz de homografía que relaciona los emparejamientos es la generada aleatoriamente. Se ha jado un valor del tanto por ciento de espurios en la muestra y se distorsiona una parte del conjunto de puntos q de manera que el conjunto de emparejamientos resultante tenga el porcentaje de espurios deseado. Con estos datos se han calculado las matrices de homografía con los distintos emparejadores. Para decidir si una prueba ha nalizado con éxito se ha comparado el valor de la homografía calculada con el valor de la homografía original; si la diferencia entre ambas es inferior a un umbral determinado, se considera que el emparejador ha nalizado con éxito el cálculo. En caso de que el error supere el umbral o no haya sido posible el cálculo de la homografía, se considera que el método ha fracasado. Para cada valor entero del porcentaje de espurios entre 1 y 100 se han realizado 1000 pruebas (1000 matrices de homografía diferentes) con cada emparejador. Se ha contabilizado el número de éxitos obtenido en cada caso, lo que nos ha permitido calcular el porcentaje de éxito de cada emparejador en función de la fracción de espurios de la muestra. También se ha calculado el error medio cometido en función de la fracción de espurios. 31 5. Resultados obtenidos 32 Las grácas 5.1, 5.2 y 5.3 muestran los resultados obtenidos en el experimento. 0 20 40 60 80 100 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 % espurios probabilidad de resolver Emparejamiento NO robusto 0 20 40 60 80 100 0 1 2 3 4 5 6 7 8 9 % espurios error en la matriz de homografía Emparejamiento NO robusto Figura 5.1: Resultados obtenidos empleando únicamente el emparejamiento básico de características. Para cada porcentaje de espurios se han realizado 1000 pruebas con diferentes matrices de homografía generadas aleatoriamente. 0 20 40 60 80 100 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 % espurios probabilidad de resolver Emparejamiento RANSAC 0 20 40 60 80 100 0 2 4 6 8 10 12 14 16 18 20 % espurios error en la matriz de homografía Emparejamiento RANSAC Figura 5.2: Resultados obtenidos utilizando un emparejamiento robusto con el algoritmo RANSAC. El número de pruebas realizado ha sido el mismo que el empleado con el emparejador básico. Como se aprecia en las grácas, el método de RANSAC es el más tolerante a espurios de emparejamientos, en el sentido de que tiene probabilidades más altas de generar soluciones exactas que el emparejador básico o el emparejamiento robusto utilizando LMS. Además los errores que se cometen en la matriz de homografía son en general menores que los que se cometen el emparejador LMS o los obtenidos resolviendo el sistema sobredimensionado. Aunque el emparejamiento no robusto es peor que los emparejadores robustos, si el número de espurios es muy elevado, los errores que se cometen son menores. Esto es debido a que cuando hay más espurios que emparejamientos buenos, estadísticamente los errores positivos de unos emparejamientos malos se compensan con los errores negativos de otros, Navegación visual usando una descripción de la ruta con secuencias de imágenes 5. Resultados obtenidos 33 0 20 40 60 80 100 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1Emparejamiento LMS % espurios probabilidad de resolver 0 20 40 60 80 100 0 5 10 15 20 25 % espurios error en la matriz de homografía Emparejamiento LMS Figura 5.3: Resultados obtenidos un emparejamiento robusto con el algoritmo LMS. El número de pruebas realizado ha sido el mismo que el empleado con el emparejador básico. y en promedio, la matriz resultante no tiene errores elevados. En el caso de RANSAC o LMS, al haber una fracción de espurios superior al conjunto de buenos emparejamientos es bastante probable que una mala solución reciba más votos que la solución buena, con lo cual, la matriz obtenida tiene poca relación con la matriz real, y el error resultante es mucho mayor. 5.2. Calidad de los sistemas de extracción de características Comparar dos sistemas de extracción de características es una tarea compleja, ya que no existen criterios objetivos que se adapten a todas las situaciones. Cambiar el tamaño de las imágenes muestreadas o el contenido de las mismas puede hacer que los métodos parezcan mejores o peores. Para poder realizar una valoración más o menos consistente se han realizado diferentes pruebas teniendo en cuenta: Tamaño de las imágenes. Grado de acondicionamiento del entorno Ángulo de separación entre las imágenes. Consideración de imágenes en movimiento. Las diferentes pruebas realizadas han ido manifestando las distintas ventajas e inconvenientes de los dos métodos (SURF y contornos verticales). Estas pruebas han servido también para encontrar y resolver problemas ajenos a los extractores como el problema del entrelazado. Navegación visual usando una descripción de la ruta con secuencias de imágenes 5. Resultados obtenidos 34 5.2.1. Problema del entrelazado Cuando las imágenes son tomadas durante el movimiento del robot aparece el problema del entrelazado. Como la cámara realiza muestreos de las pares e impares de la imagen por separado, en los giros, las imágenes obtenidas aparecen distorsionadas (Figura 5.4). Esto afecta negativamente a ambos extractores, y en especial al de contornos verticales ya que en estas imágenes las líneas verticales aparecen con trazo en forma de zigzag y el extractor no es capaz de identicarlas. Un ejemplo del efecto producido por el entrelazado se puede ver en la gura 5.5. Primer barrido Filas pares Segundo barrido Filas impares Imagen compuesta por ambos barridos (con movimiento) Imagen compuesta por ambos barridos (sin movimiento) Figura 5.4: Muestreo de una imagen. La solución que se ha adoptado para resolver este problema ha sido eliminar en las imágenes las las pares. De esta forma no solo desaparece el problema del entrelazado, sino que además el tiempo de cómputo se reduce considerablemente al trabajar con imágenes la mitad de grandes. Es importante aclarar que la eliminación de la mitad de las las, además, no ha afectado negativamente a los extractores. Después de haber experimentado con varios tamaños de imagen, se ha visto que la resolución de 625x240 es la que mejores resultados ha proporcionado. 5.2.2. Tiempos de cómputo El extractor de puntos SURF tiene un coste computacional claramente superior al del extractor de contornos verticales. Para que su uso sea efectivo en la práctica se han realizado algunas modicaciones en el algoritmo, orientadas a la reducción de los tiempos de cálculo. Por una parte se ha conseguido agilizar mucho los cálculos del extractor SURF eliminando la invariancia a rotaciones. Como el robot se mueve sobre un mismo plano todo Navegación visual usando una descripción de la ruta con secuencias de imágenes 5. Resultados obtenidos 35 Figura 5.5: Problema del entrelazado. el tiempo los puntos extraídos no presentan rotaciones en la imagen. La segunda modi- cación ha consistido en reducir el tamaño del descriptor de cada elemento SURF de 64 a 36 elementos. Las pruebas realizadas han demostrado que en el entorno en que se está trabajando, la pérdida de precisión en el descriptor no afecta de manera negativa a la navegación. La utilización de técnicas robustas de emparejamiento compensa con creces esta reducción. Con estas dos modicaciones se ha conseguido reducir el tiempo medio de cálculo del extractor, en el computador del robot, de aproximadamente 2 segundos a 300-400 milisegundos, para el tamaño de imagen citado en la subsección anterior, dependiendo del número de puntos que encuentre el extractor. Aun habiendo reducido considerablemente el tiempo de cómputo del extractor SURF, este necesita que el robot se mueva a velocidades inferiores a las que permite el extractor de Burns para funcionar correctamente. 5.2.3. Homografías obtenidas El hecho de que el extractor de características SURF sea más lento no lo convierte en peor extractor. La siguiente etapa de experimentos ha consistido en observar la calidad Navegación visual usando una descripción de la ruta con secuencias de imágenes 5. Resultados obtenidos 36 de las homografías obtenidas para ambos métodos con diferentes pares de imágenes. El extractor SURF ha resultado ser mucho más robusto en el cálculo de homografías. En primer lugar, los emparejamientos son más ables, ya que se basan en descriptores de 36 elementos frente a las 6 parámetros que emplea el emparejador de rectas. Esto hace que el número de espurios sea mucho menor. Además, el número de puntos que se pueden extraer de una imagen es mucho mayor que el número de rectas que tienen una orientación casi vertical. En denitiva hay un mayor número de emparejamientos con un porcentaje menor de espurios, lo que se traduce en mayor abilidad en el cálculo de la homografía. Con los experimentos se ha visto que las características SURF, para correcciones de hasta 0.7 radianes, tienen una probabilidad de éxito en el cálculo de casi el 100% y la precisión de la solución es del orden de las milésimas. El extractor de contornos verticales, en cambio, tiene probabilidades de éxito inferiores y es muy dependiente de la imagen, por lo que para garantizar su correcto funcionamiento hay que acondicionar el entorno para que haya gran cantidad de rectas verticales. 5.3. Movimientos sencillos 5.3.1. Reparación de la orientación respecto a una imagen de referencia Se han realizado varios experimentos para probar la función que se ha implementado para reparar la orientación del robot respecto a imágenes de referencia. En los experimentos se ha tenido en cuenta: El tipo de extractor empleado El giro a realizar Acondicionamiento del entorno Velocidad de giro Tolerancia (error permitido en la corrección) Tomando una imagen de referencia se ha querido comprobar la calidad de la reparación de la orientación haciendo pruebas con distintos ángulos de error. Los resultados han demostrado que en un intervalo de ±0.4 radianes, con una precisión menor a la tolerancia jada, el robot es capaz de reparar el error la mayoría de las veces. Para valores que oscilen entre 0.4 y 0.7 la reparación depende casi totalmente del grado de acondicionamiento de las imágenes capturadas. Para valores superiores no se garantiza la posibilidad de llevar a cabo la reparación de manera correcta. Navegación visual usando una descripción de la ruta con secuencias de imágenes 5. Resultados obtenidos 37 Se ha visto que existe una relación entre la velocidad que se emplea en el giro y la tolerancia que se debe utilizar para determinar que la reparación ha terminado correctamente. Esta relación es diferente para el extractor de contornos verticales que para el extractor de características SURF, ya que depende del tiempo de extracción. Notemos que mientras se está calculando el factor de corrección de una imagen el robot sigue en movimiento. Por lo tanto, en el instante en que detectemos que la corrección respecto a una imagen es inferior a la tolerancia, el robot se habrá desplazado un poco respecto a la posición en que se tomó dicha imagen (véase imagen 5.6). Este desplazamiento depende de la velocidad de rotación del robot y del tiempo empleado para el cálculo de la corrección. Si la velocidad de giro es alta, hay que aumentar el valor de la tolerancia (tolerancia menos precisa) para que compense el exceso de desplazamiento cometido durante los cálculos. Por el contrario, si la velocidad es baja, habrá que usar valores más pequeños de la tolerancia (tolerancia más precisa). umbral de tolerancia imagen de referencia orientación del robot en la última imagen capturada orientación nal tras la reparación orientación inicial del robot desplazamiento durante el cálculo de la corrección Figura 5.6: Reparación de la orientación. Partiendo de una posición en la que el robot se encuentra mal orientado, el robot realiza un giro hasta que detecte que la corrección de la última imagen capturada respecto de la imagen de referencia es inferior al umbral de tolerancia admitido. La posición nal del robot no coincide con la posición en la que se ha capturado la última imagen ya que durante el tiempo empleado en el cálculo de la corrección el robot ha seguido moviéndose. Eligiendo adecuadamente la velocidad de giro y el umbral de tolerancia para que tengan en consideración el desplazamiento nal se obtiene el resultado deseado: que el robot nalice su movimiento con la orientación adecuada. Si el error tolerado es alto y la velocidad es pequeña ocurrirá que el robot no llegará al punto deseado de la reparación, aunque estará dentro de los márgenes admitidos (imagen 5.7). Por otro lado, si el error que se tolera es demasiado bajo en relación a la velocidad, el robot se pasará el destino a causa del desplazamiento ocurrido durante los cálculos (imagen 5.8). La tabla 5.1 muestra la relación entre la velocidad de rotación y la tolerancia recomendada para los dos extractores utilizados. Navegación visual usando una descripción de la ruta con secuencias de imágenes 5. Resultados obtenidos 38 imagen de referencia umbral de tolerancia orientación inicial del robot orientación del robot en la última imagen capturada desplazamiento durante el cálculo de la corrección orientación nal tras la reparación Figura 5.7: Reparación con velocidad lenta y margen de error grande. En este caso aunque el robot termina con la orientación dentro de los márgenes permitidos, se observa que la orientación nal no es la correcta. Un umbral de error permitido alto, combinado con una velocidad de movimiento baja hacen que el robot no complete la reparación correctamente. Para resolver este error se tendría que reducir el umbral de error permitido. imagen de referencia umbral de tolerancia orientación inicial del robot orientación del robot en la última imagen capturada desplazamiento durante el cálculo de la corrección orientación nal tras la reparación Figura 5.8: Reparación con velocidad alta y margen de error pequeño. En este caso el robot termina mal orientado porque realiza un desplazamiento muy grande desde que captura una imagen dentro del intervalo permitido hasta que obtiene el valor de corrección de dicha imagen. Para solucionar este problema habría que reducir la velocidad de movimiento del robot. También se deduce de estos experimentos que para velocidades muy altas disminuir el error tolerado no va a generar movimientos más precisos y no se puede garantizar una reparación de calidad. Navegación visual usando una descripción de la ruta con secuencias de imágenes 5. Resultados obtenidos 39 Contornos verticales Puntos SURF Velocidad (rad/s) Tolerancia (rad) Velocidad (rad/s) Tolerancia (rad) 0.01 0.04 0.01 0.04 0.02 0.04 0.02 0.05 0.03 0.08 0.03 0.1 0.04 0.1 0.04 0.12 Tabla 5.1: Relación entre la velocidad de giro y la tolerancia en la reparación. 5.3.2. Correcciones en desplazamientos longitudinales Para los experimentos en desplazamientos longitudinales se ha considerado una trayectoria únicamente rectilínea durante el aprendizaje. En la posterior fase de repetición se ha colocado al robot con diferentes errores de rotación iniciales para observar su comportamiento.Los resultados han presentado sensibilidad a dos factores distintos. Por un lado, como es de esperar, el ángulo de error inicial es un factor que afecta al resultado. Si el error inicial es superior a ±0.8 radianes se ha visto que el robot no es capaz de recuperarse, independientemente del tipo de extractor utilizado. Para errores inferiores, aparte de la dependencia de las extracciones al condicionamien- to del entorno, el segundo factor que se ha considerado es la longitud del desplazamiento. Si la longitud es grande el robot dispone de más tiempo para corregir su trayectoria, y por tanto es capaz de corregir errores mayores. Si, por el contrario, se dispone de poco espacio para la corrección, aunque el robot fuera capaz de corregir el ángulo de desviación, se detendrá antes de que le de tiempo. Estos resultados hacen que sea de la máxima importancia que el robot empiece todos sus desplazamientos con la mejor orientación posible. 5.3.3. Correcciones en giros La corrección de los giros es, posiblemente, el problema más complicado de resolver que ha aparecido durante la realización de este proyecto. Se han realizado experimentos con cuatro tipos de soluciones al problema para estudiar la viabilidad de cada una de ellas. No corregir durante el giro La primera solución probada ha sido no realizar reparaciones de orientación durante el giro y dejar que sea en los posteriores desplazamientos longitudinales donde se realice la corrección. Como se ha visto en la subsección anterior, la corrección de un error inicial de rotación Navegación visual usando una descripción de la ruta con secuencias de imágenes 5. Resultados obtenidos 40 posición inicial del robot posición nal del robot Figura 5.9: Ejemplo de giro sin realizar reparaciones. El robot realiza un giro utilizando la odometría cometiendo un error. La corrección se realiza en el posterior desplazamiento longitudinal. a lo largo de un desplazamiento longitudinal, depende principalmente del error a corregir y de la distancia que haya para corregirlo. En una rotación, excepto en casos excepcionales, los errores que se cometen oscilan entre -0.2 y 0.2 radianes. Se ha visto que para este caso realizar la corrección en el desplazamiento es posible. Sin embargo, está solución se ha descartado, principalmente por dos motivos. El primero de ellos es el desconocimiento de la distancia que hay para corregir posteriormente el error; se ha procurado que cada fase del movimiento fuera lo más precisa posible y esta solución funciona justamente al revés. El segundo motivo viene cuando el último movimiento de la trayectoria es una rotación; en este caso no habría posibilidad de corregir más adelante el error y el robot no podría terminar de forma correcta el recorrido. Realizar una reparación por cada imagen de referencia Esta solución, de todas las utilizadas, es la que ha presentado peores resultados en los experimentos. Puesto que la distancia entre imágenes de referencia oscila entre 0.05 y 0.3 radianes la realización del giro a velocidad normal es muy imprecisa en proporción al giro realizado (entre un 50% y un 200%). Generalmente este error en el giro, además, es por exceso; esto implica que el robot esté girando constantemente hacia la izquierda y hacia la derecha para reparar el exceso de giro. Esto provoca grandes errores en la odometría del robot. Por todo ello se ha desechado el uso de esta solución en la realización de trayectorias complejas. Navegación visual usando una descripción de la ruta con secuencias de imágenes 6. Conclusiones y trabajos futuros 47 en la navegación. Gracias a los compañeros en el laboratorio de robótica se resolvió el problema encontrando la opción de conguración adecuada. Compaginar el desarrollo del proyecto con el trabajo de cursar las asignaturas del último curso de la titulación ha supuesto una dicultad añadida, ya que durante el periodo lectivo se ha dispuesto de menos tiempo para trabajar en el proyecto. Esto ha implicado una dedicación inferior al proyecto en los primeros meses y la realización de un esfuerzo mucho mayor durante la segunda mitad del mes de junio y los meses de julio y agosto. 6.3. Trabajos futuros Partiendo del trabajo realizado en este proyecto se plantean varias ampliaciones de gran interés. En este proyecto el robot es únicamente capaz de reproducir un recorrido aprendido previamente. Una posible mejora sería emplear la fase de aprendizaje para generar un mapa jerárquico del entorno que permita posteriormente al robot moverse libremente dentro de dicho entorno desde cualquier parte a cualquier otra. Este problema es conocido como el problema de localización jerárquica. Otra posible ampliación sería la utilización de la información obtenida por la visión por computador para la navegación cooperativa entre robots. La idea sería utilizar un robot, que tiene incorporada una cámara, para indicar a otros robots rutas y correcciones o bien, equipando varios robots con cámaras digitales, conseguir que naveguen en formación a partir de la información de las imágenes. Por último se propone emplear la aplicación desarrollada en este proyecto con cámaras omnidireccionales, estudiar posibles adaptaciones de las técnicas y comparar los resultados obtenidos. Es de esperar una mejora en la navegación, ya que una cámara omnidireccional captura imágenes que abarcan 360 o . La información de las imágenes omnidireccionales resulta más completa por abarcar todo el entorno del robot. Navegación visual usando una descripción de la ruta con secuencias de imágenes Capítulo 7 Principales hitos temporales y diagrama de Gant En este capítulo se comentan los principales hitos temporales que han acontecido durante la realización del proyecto. En la segunda sección se muestra el diagrama de Gant, donde se puede apreciar el tiempo destinado a cada parte del proyecto y las secciones que se han ido realizando en paralelo. 7.1. Hitos del proyecto 13 Noviembre : Comienzo del proyecto con la lectura de artículos de investigación. 8 Diciembre : Primera toma de contacto con el robot. 25 Enero - 14 Febrero : Parada por la realización de los exámenes de Febrero. 4 Abril: Primera versión del código terminada. 17 Abril: Comienzo de los experimentos. 8 Junio - 22 Junio: Parada por la realización de los exámenes de Junio. 31 Julio: Finalización de los experimentos. 16 Agosto: Finalización de la memoria del proyecto. 24 Agosto: Depósito del PFC. 48 7. Principales hitos temporales y diagrama de Gant 49 7.2. Diagrama de Gant Nov Dic Ene Feb Mar Abr May Jun Jul Ago Lectura de documentación Familiarización con el robot Familiarización código partida Integración de código Experimentos extractores Experimentos emparejadores Movimientos sencillos Trayectorias completas Documentación Tabla 7.1: Diagrama de Gant. Navegación visual usando una descripción de la ruta con secuencias de imágenes Apéndice A Hardware de desarrollo A.1. Hardware utilizado Para el desarrollo del proyecto se ha empleado un robot Pioneer de los que posee el Grupo de Robótica, Percepción y Tiempo Real de la Universidad de Zaragoza. El laboratorio de robótica dispone de cuatro robots de dicha marca (gura A.1). El robot utilizado para este proyecto es, en concreto, el robot modelo Pioneer3-dx con las siguientes características: Computadora con sistema operativo Debian . 16 sensores de ultrasonido alrededor del robot Odómetros (encoders) asociados a las ruedas para medir la variación de movimiento. Sensor láser frontal para recoger información del entorno. Interfaz de comunicación wi-. Cámara de visión Canon VCC4 Para el proyecto no se han empleado ni los sensores de ultrasonido ni el sensor láser. Las características hardware y las especicaciones de los modelos de robots se encuentran detalladas en la página de Activmedia http://www.activrobots.com/ROBOTS/specs.html . A.2. Librerías Player Para poder controlar el robot se han empleado unas librerías de código abierto llamadas Player . Estas librerías incorporan un conjunto de clases y tipos de datos que realizan el manejo del robot relativamente sencillo. 50 A. Hardware de desarrollo 51 Figura A.1: Robots Pioneer del Grupo de Robótica, Percepción y Tiempo Real Mediante un chero de conguración indicado en la ejecución de Player , el programa detecta qué hardware del robot se va a emplear. En el caso de este proyecto se han utilizado el sensor de odometría y la cámara digital. Las funciones que proporciona Player permiten mover el robot con una determinada velocidad lineal y angular, leer datos de la odometría y capturar imágenes de forma cómoda. Para su funcionamiento, en el robot se deben ejecutar simultáneamente dos programas. Por una parte se ejecuta el programa que controla al robot (el programado por el usuario), a la vez se tiene que estar ejecutando el programa Player , que se encarga de todo el control del robot. El chero de conguración especica una serie de parámetros, que serán con los que trabajará el robot. Los parámetros de la cámara digital especican el tamaño de las imágenes capturadas, si se capturan en color o en blanco y negro y el formato de la captura. Las opciones de control del movimiento contienen información acerca de la máxima velocidad permitida y el tipo de control de movimientos. Toda la información acerca de Player se encuentra disponible en la página web http://playerstage.sourceforge.net Navegación visual usando una descripción de la ruta con secuencias de imágenes Apéndice B Extractores de características en imágenes B.1. Extracción de contornos verticales La extracción de contornos verticales a partir de la intensidad de las imágenes es una técnica básica y poderosa para seleccionar la información contenida en una imagen. Existen dos clases de métodos para detectar los contornos: métodos basados en la agrupación de píxeles y métodos basados en modelos de brillo. En la primera clase de métodos, los contornos generalmente se extraen detectando máximos locales del gradiente en la dirección del gradiente o detectando intersecciones con cero en la imagen de convolución empleando el Laplaciano. Una vez que los contornos se han extraído se agrupan para formar líneas. Los contornos verticales también se pueden extraer considerando un modelo de brillo después de haber realizado una segmentación de la imagen en regiones. De los propuestos usando este modelo, el trabajo de Burns [7] es posiblemente el más importante para extraer contornos verticales. La característica más importante de este método es la organización global de la información de brillo de la imagen en regiones de soporte de recta (LSR). Se pueden citar dos ventajas de esta técnica: Permite obtener contornos cuando el contraste es bajo Permite la extracción de información acerca del brillo de la recta además de la información geométrica. El método consta de tres etapas. B.1.1. Segmentación El primer paso del procedimiento es la extracción de gradientes espaciales para segmentar la imagen. Los píxeles se agrupan en regiones que presenten una dirección similar 52 B. Extractores de características en imágenes 53 Figura B.1: Segmentación de la imagen en regiones de soporte de recta LSR. en el gradiente del brillo, siempre que además tengan una magnitud del gradiente mayor a un umbral. Se consideran dos conjuntos solapados de particiones del espacio de direcciones; de esta forma, se evitan los problemas relacionados con la separación arbitraria de las particiones en la etapa de selección posterior (Véase gura B.1). Utilizando ambas segmentaciones se obtiene posteriormente una mejor interpretación de la agrupación de las rectas. B.1.2. Localizando la línea Para obtener los contornos en la imagen se ajusta una supercie de brillo plano a la LSR utilizando una aproximación por mínimos cuadrados, prediciendo el brillo (E) como una función de las coordenadas de la imagen. En este ajuste, una norma Nw(x, y) proporcional a la magnitud del gradiente se utiliza para que grandes cambios en el brillo tengan mayor inuencia en el ajuste. La medida minimizada a lo largo de la LSR en función de los parámetros de la supercie de brillo ( Ae, Be, Ce ) se expresa como: LSR X x,y [Aex+Bey+Ce−E(x, y)]2Nw(x, y) Las líneas rectas se obtienen como intersección de su plano de brillo y el plano horizontal de la media del brillo Em en la LSR (escalada con la magnitud del gradiente). Navegación visual usando una descripción de la ruta con secuencias de imágenes B. Extractores de características en imágenes 54 Em=PLSR x,y E(x, y)Nw(x, y) PLSR x,y Nw(x, y) La orientación de la línea se da en el rango de 0 a 2π quedando siempre el lado oscuro de la recta a la derecha. Esto es muy útil para obtener mejores emparejamientos posteriormente. B.1.3. Atributos escogidos A diferencia de otros emparejadores de segmentos o de puntos que solo consideran los aspectos geométricos, en este caso, el emparejamiento de los contornos rectos se realiza comparando todos los atributos proporcionados por el extractor. Este planteamiento permite emparejar características utilizando no solo la información geométrica, sino también la de la intensidad, que en muchos casos resulta muy relevante y selectiva. El empleo de los parámetros de brillo hace que el emparejador sea mas sensible a cambios en las condiciones de iluminación, pero mejora las prestaciones del emparejador si usa solo características geométricas. Teniendo en cuenta que en este proyecto se está trabajando en entornos interiores, se puede tomar como hipótesis aceptable el hecho de que la iluminación va a presentar bastante estabilidad, lo que permite considerar los parámetros de brillo constantes en el emparejador. La representación de un contorno recto en la imagen se compone de 6 parámetros, 4 geométricos y 2 de intensidad luminosa. Los parámetros empleados para el emparejamiento son los siguientes: Xm , coordenada x del punto medio del segmento Ym , coordenada y del punto medio del segmento θ , orientación del segmento l , longitud del segmento agl , nivel medio de intensidad de la LSR c , contraste del contorno B.2. SURF (Speeded Up Robust Features) SURF es una técnica de extracción de puntos en una imagen, propuesta recientemente por Herbert Bay [6]. Se ha hecho muy famosa por la robustez de los puntos que extrae de la imagen. La principal ventaja del extractor SURF es su capacidad para extraer puntos Navegación visual usando una descripción de la ruta con secuencias de imágenes B. Extractores de características en imágenes 55 en una imagen sin verse afectado por rotaciones o escalados. Esto hace que el posterior emparejamiento de características entre imágenes sea muy robusto. Además lo hace con un coste computacional inferior al de otros extractores de calidad similares como SIFT [9]. A continuación se presenta una breve descripción de como funciona el extractor. B.2.1. Puntos de interés Lo primero que hace el algoritmo es encontrar puntos de interés dentro de la imagen. La imagen debe estar tomada en escala de grises, sin embargo, para obtener una mayor precisión numérica normaliza el valor de cada píxel, transformándolo en un valor real que se encuentre en el intervalo [0,1]. Con la matriz de píxeles ya normalizados, el algoritmo busca máximos locales del determinante de la matriz Hessiana. Dado un píxel de la imagen denido por sus coordenadas p= (x, y) , la matriz Hessiana de p con una escala σ se dene como: H(p, σ) = Lxx Lxy Lxy Lyy  (B.1) donde Lxx , Lxy y Lyy representan las derivadas segundas parciales de la gaussiana G(σ) respecto a las coordenadas de cada píxel p= (x, y) . Para que el algoritmo sea más eciente, en lugar de calcular las segundas derivadas, se hace una aproximación mediante ltros en forma de caja, como los que aparecen en la gura B.2. Figura B.2: De izquierda a derecha: Las derivadas parciales de segundo orden de la Gaussiana en la dirección de y en la dirección xy y las aproximaciones realizadas usando ltros de caja. Las regiones grises son igual a 0. Si se emplean imágenes integrales, las convoluciones para estos ltros pueden ser calculadas en muy poco tiempo. Una imagen integral I Σ es una representación de la imagen en la que cada píxel p= (x, y) almacena el valor del sumatorio en x y en y desde el origen hasta el punto. El valor viene representado en la ecuación B.2 Navegación visual usando una descripción de la ruta con secuencias de imágenes B. Extractores de características en imágenes 56 I Σ=X xX y p(x, y). (B.2) Realizando una transformación de la imagen al comienzo de la extracción para convertirla en integral, el cálculo posterior de los ltros de caja tiene coste constante independientemente del tamaño de la caja. Esto permite realizar búsquedas de máximos locales para diferentes tamaños de ltros. B.2.2. Características de los descriptores Para cada punto extraído en la imagen integral, se calcula un descriptor de longitud variable que identique de forma unívoca dicho punto. Cuanto mayor sea la longitud que se emplee para los descriptores, el emparejamiento será más robusto, pero todo el proceso requerirá un mayor tiempo de CPU. Las tres características que denen al punto son las siguientes: Signo del determinante de la matriz Hessiana: Se utiliza para distinguir manchas de brillo en un fondo oscuro y viceversa. Esta característica es muy interesante, ya que clasica los puntos en brillantes y oscuros. De esta forma, en el emparejamiento, mirando el signo del determinante se podrá descartar una gran cantidad de puntos sin tener que mirar el resto de los valores del descriptor. Orientación del gradiente: Para cada punto detectado, el extractor dene una región circular alrededor del punto y calcula la orientación dominante del gradiente dentro de dicha región. Sumatorio del gradiente: Se dene una región cuadrada alrededor del punto seleccionado del tamaño relativo a la escala σ con la que se detectó el punto. Dependiendo del tamaño elegido para el descriptor se subdivide la región en partes iguales (4, 9, 16 ó 32) y se calculan 4 valores en cada subregión basados en los valores del gradiente obtenidos en la correspondiente subregión. El conjunto de valores obtenido constituye el descriptor del punto. Después de realizar pruebas con los diferentes tamaños de descriptores, 16, 36, 64 ó 128, se ha elegido utilizar el de longitud 36 (aparte del signo del determinante de la matriz hessiana y la orientación del gradiente), por alcanzar un equilibrio entre la calidad que se le pide al sistema y el tiempo que necesita para realizar todos los cálculos. Además, pues- to que en los experimentos que se han realizado el robot siempre se está moviendo sobre el mismo plano (el que dene el suelo), el cálculo de la orientación del punto no aporta ningún benecio, ya que la orientación de la cámara permanece constante. Eliminando el cálculo de la orientación se ha reducido el tiempo de cálculo. Navegación visual usando una descripción de la ruta con secuencias de imágenes C. Técnicas de emparejamiento 63 Para cada uno de los puntos p 2 restantes se calcula la norma euclídea de la diferencia de los descriptores. De todas las distancias obtenidas se almacenan las dos menores. Si la distancia más pequeña obtenida es inferior a la mitad de la segunda menor distancia, entonces se considera que hay un emparejamiento entre el punto p 1 y el punto p 2 para el que se ha obtenido la mínima norma de la diferencia. Este método de emparejamiento parece peor que el utilizado para los contornos rectos ya que, a priori, nada impide que un punto de la segunda imagen pueda ser emparejado con varios de la primera. Sin embargo, se ha demostrado empíricamente que la calidad de los emparejamientos iniciales obtenidos es mucho mejor para puntos SURF con este emparejador que para contornos verticales. C.2. Emparejamiento robusto de características previamente emparejadas C.2.1. RANSAC El método RANSAC (RANdom SAmple Consensus) [14] es un método de emparejamiento robusto que da como resultado la solución más votada de entre unas cuantas, calculadas a partir de conjuntos mínimos obtenidos aleatoriamente. Para calcular una homografía en dos dimensiones se necesitan un mínimo de tres emparejamientos. La idea del método RANSAC consiste en seleccionar un número de subconjuntos de tres emparejamientos elegidos aleatoriamente dentro del total, que garantice que, con una probabilidad superior al 99%, al menos uno de dichos subconjuntos contendrá sus tres emparejamientos correctos, es decir, que ninguno de ellos es un espurio. Figura C.1: Ejemplo de conjunto de puntos para ajustar a una recta. Dados dos puntos elegidos aleatoriamente de entre todos los del conjunto, se dene una recta r con ellos. Con un umbral δ elegido arbitrariamente, se consideran inliers todos Navegación visual usando una descripción de la ruta con secuencias de imágenes C. Técnicas de emparejamiento 64 aquellos puntos que se encuentren dentro del intervalo (r+δ, r −δ) . La recta denida por c y d tendría únicamente 2 inliers mientras que la denida por a y b en la imagen tendría un total de 10 inliers . Probar el total de combinaciones posibles de subconjuntos de s datos del total resultaría muy costoso computacionalmente. Si se parte de n puntos se necesitarían C(n, s) = n! (n−s)!s! (C.4) pruebas. El coste computacional de un algoritmo de estas características sería de O(nn) en el número de emparejamientos obtenidos inicialmente. Si seleccionamos un número sucientemente grande de subconjuntos de s elementos podremos armar que, con una probabilidad ja, al menos habrá un subconjunto que contendrá sus s muestras dentro de la solución buena. Si encontramos la solución buena entre el subconjunto habremos hallado un algoritmo mucho más eciente. Número de subconjuntos a elegir La probabilidad P con la que al menos uno de los subconjuntos seleccionados aleatoriamente esta libre de espurios viene denida por P= 1 −[1 −(1 −ε)s]m (C.5) donde s representa el número de elementos que debe tener el subconjunto (en el caso de las rectas 2, en el de las homografías 2D 3), ε representa una estimación del porcentaje de espurios que hay en la muestra y m el número de subconjuntos tomado. Despejando m de la ecuación C.5 y tomando logaritmos se obtiene m=log(1 −P) log(1 −(1 −ε)s). (C.6) Es interesante observar que m es independiente del número de puntos de la muestra. En la tabla C.1 se muestra el valor de m requerido para P= 0.99 en función de ε y s . Para la elección de estas combinaciones se ha desarrollado una función que calcula aleatoriamente grupos de 3 elementos del conjunto de emparejamientos iniciales. Condicionamiento de las matrices Una vez elegida la combinación de tres emparejamientos se calcula la matriz de homografía que los relaciona utilizando las ecuaciones que se plantean en el apéndice D. Navegación visual usando una descripción de la ruta con secuencias de imágenes C. Técnicas de emparejamiento 65 Tabla C.1: Valores de m en función de ε y s [14]. El único problema que puede darse al resolver el sistema es que la conguración de puntos (o rectas) haya sido mala, en el sentido de que se hayan escogido tres puntos de una misma recta o tres rectas que son paralelas entre sí. Esto lleva a la obtención de una matriz con un número de condición excesivamente alto, hecho que no garantiza una solución correcta al sistema de ecuaciones. Para evitar resultados erróneos, primero se han elegido las combinaciones aleatoriamente y luego se han empleado únicamente aquellas que han producido matrices bien condicionadas. Para garantizar que se evalúan m subconjuntos, lo que se ha hecho es calcular un mayor número de combinaciones y luego se han seleccionado aquellas que han producido números de condición adecuados. En el caso de que no hubiera sucientes matrices bien condicionadas se ha devuelto un código de error para hacer notar que no se ha podido calcular la matriz de homografía correctamente. Elección de la mejor solución El algoritmo calcula el número de votos o inliers que recibe cada solución obtenida con los subconjuntos generados aleatoriamente. Al nalizar se elige como solución aquella que tiene un mayor número de inliers . Una optimización para este algoritmo es considerar como solución buena aquella que reciba más de un 90% de votos. En caso de que una solución obtenga un gran número de inliers (95%) se considera como solución nal y no hace falta realizar todos los cálculos para el resto de subconjuntos. Si se quiere obtener una solución más ajustada se puede resolver el problema sobredimensionado que generan sólo aquellos puntos que se consideran inliers a la homografía calculada por RANSAC. Navegación visual usando una descripción de la ruta con secuencias de imágenes C. Técnicas de emparejamiento 66 C.2.2. Least Median of Squares (LMS) El método de la mínima mediana de los cuadrados es otro método probabilístico de emparejamiento robusto [15] [16]. Este método da la solución de menor valor de la mediana del cuadrado de los residuos calculados para todo el conjunto de datos. Es un método muy robusto respecto a datos fuera de norma. Igual que en el método RANSAC, inicialmente se utiliza una técnica Monte-Carlo para elegir aleatoriamente m subconjuntos de s emparejamientos diferentes. Para cada subconjunto se calcula la solución que resuelve el problema. Este método tiene la ventaja respecto a RANSAC de no necesitar umbrales para el cálculo de buenos emparejamientos. Sin embargo, el coste computacional es mayor, ya que necesita realizar más operaciones para cada solución. Además, si el número de espurios es mayor que el 50% la calidad de la solución desciende drásticamente. En estos casos se propone utilizar un percentil menor del residuo. Cálculo de los residuos En el método LMS en lugar de realizar un sistema de votaciones se calcula el valor de los residuos que genera todo el conjunto de datos respecto a cada solución obtenida. Para calcular el residuo. Con las matrices de homografía se tiene que, en caso de ajuste perfecto: p 1− H 21 p 2= 0 (C.7) Esto sólo se cumplirá para los emparejamientos empleados en el cálculo de la matriz de homografía. Para el resto de emparejamientos esto da p 1− H 21 p 2= (C.8) donde  representa el vector residuo de la transformación. Tomando la norma euclídea del vector  obtenemos el valor escalar del residuo que genera cada punto respecto a una matriz de homografía. Con todos los residuos calculados para una solución se obtiene la mediana de éstos, que se emplea para calcular la bondad de la solución considerada. Al nal se elige como solución aquella que tenga un menor valor de la mediana del residuo. Navegación visual usando una descripción de la ruta con secuencias de imágenes C. Técnicas de emparejamiento 67 Eliminación de emparejamientos espurios A partir de la solución de mínima mediana se pueden eliminar los emparejamientos espurios. En este caso se consideran emparejamientos espurios aquellos que generen mayor residuo respecto a la solución nal. En este proyecto se han considerado como buenos emparejamientos aquellos que cumplen: r2 i≤(2 ∗ˆσ2) (C.9) donde ri es el residuo que genera el i-ésimo punto respecto a la solución nal y ˆσ representa una estimación de la desviación estándar calculada con la siguiente fórmula: ˆσ= 1.4826 ∗(1 + 5 n−s)∗pMJ (C.10) siendo MJ la mínima mediana, n el número de emparejamientos inicial y s los emparejamientos necesarios para obtener una solución. Navegación visual usando una descripción de la ruta con secuencias de imágenes Apéndice D Cálculo de homografías D.1. Coordenadas homogéneas En la geometría euclídea, un punto p del plano se puede representar mediante sus dos coordenadas p= (x, y) . Sin embargo, cuando trabajamos con computadores aparece el problema de la discretización de los reales y el problema de la limitación en el tamaño de los números. Para resolver el segundo problema se propuso la ampliación del número de coordenadas para representar los puntos. Añadiendo una tercera coordenada λ que represente la escala, un punto p queda denido de la siguiente manera p= (λx, λy, λ) . Con esta tercera coordenada desaparece la limitación en el tamaño de las coordenadas, si λ está próximo a 0, esto querrá decir que el punto se encuentra próximo al innito. Por denición se considera que λ= 0 implica que el punto se encuentra en el innito. Podemos pasar de coordenadas homogéneas a coordenadas estándar a través de la forma normalizada p= (x, y, 1) , que se obtiene de las coordenadas homogéneas dividiendo por el parámetro λ , siempre que este no sea 0. D.2. Matrices de transformación Una vez que se ha explicado como se denen los puntos hay que plantear como se calculan las matrices que transforman las coordenadas. Puesto que los puntos del plano tienen 3 coordenadas, una transformación entre dos puntos se representa mediante una matriz 3x3 de manera que:   λ x 1 λ y 1 λ  =  h11 h12 h13 h21 h22 h23 h31 h32 h33    x 2 y 2 1   (D.1) 68 D. Cálculo de homografías 69 En las condiciones en las que se desarrolla este proyecto el movimiento va a ser siempre plano y las imágenes van a tener muy poco baseline , desplazamiento muy pequeño entre los centros ópticos. Partiendo de este hecho se puede realizar una simplicación en el problema eliminando de los cálculos la segunda coordenada de los puntos. En este caso la matriz de transformación pasa a tener dimensión 2x2 y el producto para transformar puntos queda como sigue: λ x 1 λ=h11 h12 h21 1 x 2 1 (D.2) Esta simplicación no afecta al cálculo de errores de rotación, que son los más importantes, empleando matrices de homografía como se demuestra en [2]. El objetivo ahora es encontrar una matriz de estas características, que transforme los puntos extraídos en una imagen con los emparejamientos obtenidos de las extracciones en otra. A partir de esta matriz podremos calcular el ángulo de rotación entre las dos imágenes. D.3. Sistema de ecuaciones Sea p 1 un punto extraído en la primera imagen y q 1 su correspondiente emparejamiento en la segunda. Si denominamos H 21 a la matriz 2x2 que transforma los puntos de la segunda imagen en sus emparejamientos de la primera (matriz que lleva de 2 a 1), obtenemos la siguiente ecuación: p 1= H 21 q 1 (D.3) teniendo en cuenta D.2 se extraen las siguientes ecuaciones: λ x 1=h11 x 2+h12 λ=h21 x 2+ 1 (D.4) Sustituyendo en la primera ecuación el valor de λ dado en la segunda se obtiene: h11 x 2+h12 −h21 x 1 x 2= x 1 (D.5) La ecuación D.5 representa la ecuación que se obtiene de un emparejamiento. Si combinamos las ecuaciones que se obtienen de tres emparejamientos diferentes se plantea el Navegación visual usando una descripción de la ruta con secuencias de imágenes D. Cálculo de homografías 70 siguiente sistema:   x 21 1− x 11 x 21 x 22 1− x 12 x 22 x 23 1− x 13 x 23    h11 h12 h21  =  x 11 x 12 x 13   (D.6) Resolviendo este sistema de tres ecuaciones con tres incógnitas obtenemos los parámetros que nos denen la matriz de homografía H 21 . El parámetro que se emplea para estimar el ángulo de diferencia, como se demuestra en [2], es el valor del elemento h21 de la matriz. Se podrían emplear los otros elementos de la matriz; sin embargo, está demostrado que presentan una mayor sensibilidad al ruido o a errores en los cálculos, convirtiéndose por ello en peores estimadores. D.4. Sistema sobredimensionado Como norma general, cuando se comparan las características extraídas de dos imágenes, si estas son más o menos similares, se obtienen más emparejamientos de los tres que son necesarios para el cálculo de una homografía. En este caso el sistema de ecuaciones sobredimensionado queda como sigue:        x 21 1− x 11 x 21 x 22 1− x 12 x 22 x 23 1− x 13 x 23 . . .. . .. . . x 2n1− x 1n x 2n          h11 h12 h21  =        x 11 x 12 x 13 . . . x 1n        . (D.7) Para resolver este problema hay que recurrir a técnicas de mínimos cuadrados. En este proyecto se han empleado para obtener la solución las ecuaciones normales para un sistema sobredimensionado. El sistema sobredimensionado tiene la forma A x= b (D.8) donde A es una matriz n x3, x es el vector con las tres incógnitas de la matriz de homografía y b es un vector de n componentes como el de la ecuación D.7. Para resolver este sistema mediante ecuaciones normales lo que se hace es multiplicar ambos miembros de la igualdad por A T . A T A x= A T b (D.9) Navegación visual usando una descripción de la ruta con secuencias de imágenes D. Cálculo de homografías 71 quedando de esta forma un sistema con 3 ecuaciones y 3 incógnitas como el planteado en D.6. Se puede demostrar que la solución que se obtiene para este sistema es la que cumple que la norma euclídea del residuo para el sistema sobredimensionado es mínima. Navegación visual usando una descripción de la ruta con secuencias de imágenes Apéndice E Manual de usuario Este apéndice pretende servir como manual de ayuda para nuevos usuarios de la aplicación. En él se explican todas las opciones de que dispone el programa y como utilizar cada una de ellas. E.1. Interacción con el usuario El software incorporado en los robots Pioneer no permite la programación de aplicaciones con entorno gráco. No obstante, dada la importancia que tiene la facilidad de uso en cualquier software informático se ha pretendido que la aplicación nal tuviera un entorno amigable. Toda la interfaz de usuario gira en torno a un menú en modo texto que muestre al usuario las posibilidades que ofrece el software. La imagen E.1 muestra una vista general de la aplicación. Todas las opciones se han numerado con códigos de uno o dos dígitos que sean claramente identicables en la pantalla de inicio. La pantalla de inicio se ha dividido en varias secciones informativas: Cabecera del programa: la parte superior muestra el título del programa. Cumple una función estética para que el usuario sea consciente de que está dentro de la aplicación. Conguración: debajo del título se muestran las opciones que se encuentran activas en el momento actual. Se muestra el nombre de la misión, el sistema de extracción de características y el tipo de emparejamiento que se esta usando. También se indica al usuario si el programa almacenará o no las imágenes que vaya capturando. Opciones: muestra la lista de opciones que se pueden realizar con el programa, numeradas con códigos. 72 E. Manual de usuario 79 E.5.3. Aprendizaje por guiado El sistema pedirá al usuario una velocidad que se utilizará para iniciar el movimiento, y un umbral de corrección que servirá para determinar cuando se han de almacenar las características de las imágenes capturadas. En ese momento el usuario podrá mover libremente al robot por el entorno con los siguientes controles: TECLA w : Desplazar el robot hacia adelante TECLA s : Desplazar el robot hacia atrás TECLA a : Girar el robot a la izquierda TECLA d : Girar el robot a la derecha TECLA 1 : Capturar una imagen TECLA 2 : Incrementar la velocidad TECLA 3 : Decrementar la velocidad TECLA 4 : Activar/Desactivar motores TECLA 5 : Terminar proceso de aprendizaje Aparte de las imágenes que quiera tomar el usuario con la tecla 1, el robot irá almacenando las características extraídas de aquellas imágenes cuyos parámetros de corrección dieran en una magnitud mayor o igual al umbral escogido. Si la opción guardar_imagenes está activada, el robot almacenará también las imágenes correspondientes, si no, sólo almacenará el chero con las características extraídas. El aprendizaje se realiza con el código 7. E.5.4. Realizar misión Esta opción es la que permite al robot repetir el recorrido aprendido en la fase de aprendizaje. Para que funcione correctamente hay que cerciorarse de que el nombre de la misión es un nombre válido, es decir, deben existir los cheros con las características de referencia correspondientes a ese nombre de misión, que el sistema de vision empleado coincide con el que se usó en la etapa de aprendizaje y que el robot está (aproximadamente) en la misma posición inicial que cuando realizó el aprendizaje. En esta opción el usuario no intervendrá activamente ya que es el robot el que, de forma autónoma, debe ser capaz de repetir el recorrido corrigiendo los posibles errores de odometría. Para realizar una misión, el usuario deberá teclear el código 8. Navegación visual usando una descripción de la ruta con secuencias de imágenes Apéndice F Estructura del código Para desarrollar la aplicación se ha elegido el lenguaje de programación C++. Los motivos de su elección han sido varios. El código del que se partía al comienzo del proyecto estaba desarrollado en lenguaje C y las librerías de control del robot están implementadas en C++. Además, los cheros objeto que contienen las funciones para la extracción de características SURF también habían sido programados en C++. Eligiendo este lenguaje para el desarrollo se ha evitado tener que reescribir todo el código existente. Para compilar el programa se ha empleado el compilador GCC versión 4.0.2. Como el sistema operativo sobre el que se ha ejecutado era un sistema Linux, distribución Debian , el programa se ha desarrollado en sistema operativo Linux, concretamente en la distribución SUSE , versión 10.0. Se pretende que este apéndice sirva de referencia para futuras modicaciones en el programa. La lectura de este documento facilitará el aprendizaje de la estructura del código, la gestión de conguraciones y el material de partida. F.1. Gestión de Conguraciones Todos los archivos de código generado siguen el estándar del Grupo de Robótica, Percepción y Tiempo Real de la Universidad de Zaragoza. De esta forma cualquier miembro del grupo podrá comprender rápidamente el propósito de cada chero de código fuente leyendo la información de la cabecera sin necesidad de tener que mirar todo el contenido. El formato de las cabeceras es /***************************************************************************** ROBOTICS GROUP DEPARTAMENTO DE INFORMATICA E INGENIERIA DE SISTEMAS UNIVERSIDAD DE ZARAGOZA, SPAIN ****************************************************************************** 80 F. Estructura del código 81 File : corrector.c Version : v1.0 Purpose : Package to obtain corrections from vertical reference lines from images captured in real time. Authors : Ruben Martinez Date : 03-04-03 ****************************************************************************** Version : v2.0 Purpose : Deleted obsolete functions to calculate corrections Added functions to get corrections from SURF points and vertical contours using utilidades_homografia Authors : Eduardo Montijano Date : April - 2007 ******************************************************************************/ Además de incluir el nombre del grupo de investigación, la cabecera contiene información sobre el nombre del chero, numeración de versiones, propósito del archivo o las modicaciones, autor/es del código y fecha en que se realizó. Como en el grupo de investigación hay miembros de varias nacionalidades diferentes, los datos de la cabecera se han escrito en inglés para que todo el mundo pueda comprenderlos. El sistema de copias de seguridad llevado a cabo ha consistido en realizar una copia a una memoria ash al nalizar el trabajo de cada día. El periodo de duración de las copias ha sido de una semana. En la carpeta copiada se almacenaban los cheros modicados durante el día. Cada carpeta se nombraba con el nombre de la aplicación y la fecha de creación. F.2. Estructura del programa El código se ha estructurado en varios módulos. De esta forma ha resultado más fácil tener organizadas y separadas las diferentes funcionalidades del programa. Además esto permite la posible ampliación de las opciones del programa de forma sencilla. El programa incluye un módulo de trabajo con matrices desarrollado por miembros del grupo. Este módulo contiene una gran cantidad de funciones para trabajar con matrices y vectores. El código de este módulo se encuentra en los cheros sp_matrix . También incluye otro módulo para trabajar con imágenes pgm de forma muy sencilla. Este módulo incluye funciones de lectura y escritura de imágenes, una función de copia y funciones que permiten dibujar las características extraídas dentro de una imagen para su posterior visualización. Se han añadido al módulo inicial funciones especícas para trabajar con las imágenes obtenidas por la cámara del robot Pioneer ; también se ha añadido un función que permite eliminar las las pares de la imagen; de esta forma se resuelve el Navegación visual usando una descripción de la ruta con secuencias de imágenes F. Estructura del código 82 problema del entrelazado. El módulo utilidades_homografía incluye todas las funciones que permiten realizar un emparejamiento robusto de un conjunto de datos y el posterior cálculo de la matriz de homografía. Como los extractores de características utilizan estructuras de datos diferentes, se han incorporado al módulo funciones de conversión de los datos; de esta forma se ha conseguido separar y normalizar el cálculo de homografías de la parte de extracción de características en imágenes. Los módulos extractor_BURNS y extractor_SURF contienen todas las funciones necesarias para realizar la extracción de contornos verticales y puntos SURF respectivamente. Cada módulo incluye además un emparejador básico de características. Al no disponer del código fuente del extractor de características SURF ha resultado imposible normalizar los tipos de datos de ambos extractores; sin embargo, empleando el módulo de utilidades_homografía , se ha añadido una función en cada módulo que permite el cálculo de la matriz de homografía empleando directamente los datos del extractor. Esto evita al programador tener que realizar constantemente conversiones de datos que pueden resultar liosas. Con el objetivo de simplicar más la tarea de futuros programadores, se ha adaptado el módulo corrector ; tanto para contornos verticales como para puntos SURF permite realizar simultáneamente emparejamiento básico, emparejamiento robusto, cálculo de homografía y obtención de la corrección en el robot. Indicando a las funciones los dos conjuntos de características a comparar y el tipo de emparejamiento robusto deseado, estas devuelven directamente el valor de corrección necesario para solapar ambas imágenes. Los módulos mision y aprender son de más alto nivel. Estos módulos ya trabajan con el robot e incorporan implementados los algoritmos de navegación que se han explicado en el capítulo 4 de la memoria. Aprender contiene todo el código de la fase de aprendizaje; mision , además de contener el algoritmo de repetición de una ruta con secuencia de imágenes, contiene todas las funciones que permiten calibrar el robot, reparar giros, capturar una imagen con el robot y almacenar los datos de una misión en un chero de código de matlab; también se ha incluido una función DEMO que puede servir de referencia a los programadores mostrando el funcionamiento de las llamadas a los diferentes módulos. El código que contiene la ayuda interactiva y todo el menú de opciones se encuentra en el chero seguimiento.cc , este chero contiene también la función main del programa, desde donde se realizan las llamadas a todas las demás opciones del programa. Para realizar la compilación de manera automática se ha adjuntado un Makele con todas las órdenes necesarias para la compilación y el linkado de todos los cheros y librerías que se citan más adelante. Navegación visual usando una descripción de la ruta con secuencias de imágenes F. Estructura del código 83 F.3. Eciencia de los algoritmos Está sección pretende evaluar el coste temporal de los distintos algoritmos en función de los datos que emplean. En cuanto a los extractores, ambos tienen un coste computacional O(p) , siendo p el número de píxeles de la imagen sobre la que trabajan. La diferencia en el tiempo real de ejecución la marca el número de operaciones que se realizan con cada píxel y el número de veces que hay que recorrer todos los píxeles de la imagen. SURF realiza un cálculo mucho más pesado sobre cada píxel que el que realiza el método de Burns. Por lo que respecta a los emparejadores, el emparejamiento básico, para ambas características es del orden O(n2) , con n representando el número de características extraídas en cada imagen (suponiendo que el número de características es similar en ambas imágenes). Los algoritmos de emparejamiento robusto tienen un coste O(m) , siendo m el número de muestras de 3 elementos que hay que tomar sobre el conjunto de emparejamientos. El coste de calcular la matriz de homografía es O(k2) en el número de emparejamientos. Los costes computacionales de los algoritmos de emparejamiento, emparejamiento robusto y cálculo de homografías pueden ser despreciados en comparación con el coste de la extracción de características. Si empleamos los contornos verticales, los datos empíricos han demostrado que el robot es capaz de realizar una iteración del conjunto de operaciones (capturar imagen, extraer, emparejar, calcular homografía y corregir) aproximadamente en un cuarto de segundo. En el caso de utilizar puntos SURF esta cifra aumenta a medio segundo, aproximadamente, es decir, que es el doble de costoso. F.4. Listado de cheros C++ Los archivos que contienen el código C++ (ordenados por orden alfabético) de la aplicación son los siguientes: aprender.cc aprender.h burns.cc burns.h corrector.cc Navegación visual usando una descripción de la ruta con secuencias de imágenes F. Estructura del código 84 corrector.h extractor_BURNS.cc extractor_BURNS.h extractor_SURF.cc extractor_SURF.h fasthessian.h image.h imagen.cc imagen.h ipoint.h libSurf.a Makele mision.cc mision.h parametros.h seguimiento.cc sp_matrix.cc sp_matrix.h surf.h surib.h tipos.h utilidades_homograa.cc utilidades_homograa.h Navegación visual usando una descripción de la ruta con secuencias de imágenes F. Estructura del código 85 F.5. Código MATLAB Para poder visualizar de forma cómoda los resultados de los experimentos realizados, se han implementado una serie de programas en MATLAB que permiten al usuario observar grácas de errores y resultados obtenidos, así como animaciones de las trayectorias realizadas. Todo esto se ha desarrollado a partir de los códigos de los que se disponía al principio del proyecto que permitían dibujar un robot esquemático visto desde arriba en cualquier posición y orientación dentro del plano. Para que el usuario no tenga que preocuparse de programar en MATLAB, el programa principal incluye opciones de generación automática de código MATLAB. De esta forma, para visualizar los resultados el usuario lo único que tiene que hacer es copiar los cheros *.m que genera el programa principal en la carpeta en que se encuentren los cheros de MATLAB y luego ejecutarlos desde la línea de comandos del programa. El listado de cheros de código de MATLAB es el siguiente: cloc.m dptrans.m drawRobotTipo.m iloc.m iptrans.m NORMALIZE_PI.m recorrido.m Navegación visual usando una descripción de la ruta con secuencias de imágenes Apéndice G Relación del proyecto con la Ingeniería Informática En este apéndice se pretende relacionar los contenidos del proyecto con las distintas asignaturas que se han cursado durante la carrera. El tema de este proyecto está relacionado principalmente con la visión por computador. También han sido muy importantes los conocimientos adquiridos en las asignaturas de Sistemas de Tiempo Real, Inteligencia Articial y Control y Programación de Robots. Todas las asignaturas de matemáticas y estadística cursadas han servido para el cálculo matricial, la comprensión de las ecuaciones relacionadas con el cálculo de las homografías y poder entender la base matemática en la que se sustentan los diferentes extractores de características. La asignatura de Proyectos ha sido de gran utilidad durante la realización de la memoria y para toda la planicación temporal. De manera indirecta también se han empleado los conocimientos adquiridos en Metodología de la Programación y Estructura de Datos y Algoritmos para realizar el análisis de complejidad computacional de los algoritmos utilizados y poder crear estructuras de datos adecuadas a las necesidades del problema. 86 Bibliografía [1] R. Martínez-Cantín J.J. Guerrero and C. Sagüés. Visual map-less navigation based on homographies. Robotic Systems , 22(10):569581, 2005. [2] C. Sagüés and J.J. Guerrero. Visual correction for mobile robot homing. Robotics and Autonomous Systems , 50(1):4149, 2005. [3] J.J. Guerrero and C. Sagüés. Robust line matching and estimate of homographies simultaneously. In IbPRIA, Pattern Recognition and Image Analysis, LNCS 2652 , pages 297307, 2003. [4] O. Pellejero, C. Sagüés, and J.J. Guerrero. Automatic computation of fundamental matrix from matched lines. In Current Topics in Artical Intelligence, LNCS-LNAI 3040 , pages 197206, 2004. [5] O. Pellejero G. López-Nicolás, J.J. Guerrero and C. Sagüés. Computing homographies from three lines or points in an image pair. Image Analysis and Processing , 50(1):446 453, 2005. [6] H. Bay, T. Tuytelaars, and L. Van Gool. Surf: Speeded up robust features. In The ninth European Conference on Computer Vision , 2006. [7] J.B. Burns, A.R. Hanson, and E.M. Riseman. Extracting straight lines. IEEE Trans. on Pattern Analysis and Machine Intelligence , 8(4):425455, 1986. [8] C. Harris and M.J. Stephens. A combined corner and edge detector. In Alvey Vision Conference , pages 147152, 1988. [9] D. Lowe. Distinctive image features from scale-invariant keypoints. Int. Journal of Computer Vision , 60(2):91110, 2004. [10] Z. Chen and S.T. Bircheld. Qualitative vision-based mobile robot navigation. In IEEE Int. Conf. on Robotics and Automation (ICRA) , pages 17021708, May 2006. [11] M. Inaba Y. Matsumoto, K. Sakai and H. Inoue. View-based approach to robot navigation. In IEEE Int. Conf. on Intelligence Robots and Systems , pages 1702 1708, 2000. [12] M. Inaba Y. Matsumoto and H. Inoue. Visual navigation using view-sequenced route representation. In IEEE Int. Conf. on Robotics and Automation , pages 8388, 1996. 87 BIBLIOGRAFÍA 88 [13] J.J. Guerrero and C. Sagüés. From lines to homographies between uncalibrated images. In Pattern Recognition and Images Analysis, IX SNRFAI , pages 233240, 2001. [14] R. Hartley and A. Zisserman. Multiple View Geometry in Computer Vision , chapter 3, Section 7, Robust Estimation. Ed. Cambridge, 2000. [15] Peter J. Rousseeuw. Least median of square regression. In Journal of the American Statistical Association, Vol 79, No 38 , pages 871880, 1984. [16] J. Rissanen. Encyclopedia of Statistic Sciences , chapter Minimum description Length Principle. Ed. Cambridge, 1987. Navegación visual usando una descripción de la ruta con secuencias de imágenes