Flujo Óptico en Robots Móviles (2)

Siendo que el flujo óptico tiene que ver con la secuencia de imágenes en movimiento y para los objetos que se encuentran en el entorno cambian de posición en cada imagen que es analizada por la cámara, se tienen algunos problemas en la obtención del flujo óptico para las secuencias de imágenes, como pueden ser la perdida de información de los objetos en la imagen, el ruido, los cambios de iluminación en la imagen, conservación den la información, coherencia espacial, continuidad temporal entre otras.

Restricciones del flujo óptico según Black (1992):

1. Conservación de la información: Esta restricción establece que a partir de las medidas de la imagen son las mismas a medida que pasa el tiempo, por lo tanto se conserva la información de la imagen.

Figura1. Conservación de la información.

2. Coherencia espacial: Los pixeles vecinos por lo general pertenecen a la misma superficie del objeto, por consiguiente tienden a tener velocidades similares en el flujo óptico; y por tanto su flujo óptico varía ligeramente.

Figura2. Coherencia Espacial.

3. Continuidad Temporal: Esta restricción nos dice que la ruta de movimiento de la imagen en el plano cambia gradualmente a através del tiempo.

Figura3. Continuidad Temporal

La restricción de la conservación de la información es violada generalmente donde la luz no reflectada en los objetos varia; esta restricción también se viola cuando existen múltiples movimientos dentro de la región. Por lo tanto para satisfacerla se asume que las regiones de la imagen se someten a traslación en el plano, e ignora los efectos de las deformaciones en las rutas locales de la imagen causadas por movimientos relativos entre el observador y la escena.

Por otro lado la restricción de coherencia espacial es violada en discontinuidades de movimiento, esto se observa cuando tenemos un objeto oculta a otro a medida que nos acercamos a el. También ocurre cuando a medida que nos acercamos a un objeto el objeto que estaba oculto se va descubriendo; o cuando dos objetos se mueven opuestamente en direcciones hacia arriba y hacia abajo.

La tercera restricción es violada en pequeños intervalos de tiempo; esto es cuando el objeto cambia radicalmente de trayectoria; también puede ocurrir cuando la cámara tiene movimientos inestables. Partiendo de esta información se puede asumir que teniendo una adquisición de imágenes muy frecuente a modo de que el movimiento entre las imágenes pueda ser analizado no se violara esta restricción.

Referencias:

• Robust Incremental Optical Flow, Advisors: P. Anandan and D. V. McDermott, Yale University, Department of Computer Science, Research Report YALEU/DCS/RR-923, 1992.
  

Flujo Óptico en Robots Móviles (1)

Flujo óptico

Cuando observamos el movimiento de los objetos en el espacio, tendemos a percibir espacialmente cuales son las direcciones que tienen o en que posición están ubicados dentro del espacio, debido a que las imágenes analizadas por un robot son imágenes bidimensionales, no le es posible al robot poder determinar la ubicación espacial de dichos objetos.

Para poder obtener una aproximación de cual es el movimiento de los objetos en el espacio, se utiliza el flujo óptico que es el movimiento visual aparente que experimentamos cuando nos movemos dentro del entorno, además de poder determinara la dirección y la velocidad de movimiento de las características de los objetos contenidos dentro de la imagen, donde los objetos que se encuentran mas cercanos se mueven mas rápido que los objetos que están alejados.

figura: Flujo óptico de un cubo en moviento

Dentro de la imagen de la cual se obtendrá el flujo óptico se determina el punto de expansión, el cual es la dirección de hacia donde nos dirigimos, a partir de los movimientos que realizamos en alguna dirección se percibe un efecto llamado paralaje de movimiento diferencial, el cual es la diferencia de velocidad percibida entre objetos cercanos con relación a objetos lejanos.

Dentro de los movimientos que se pueden analizar contamos con los movimientos que se hacen con una cámara estática; es decir que el movimiento lo percibe en base a las escenas que capta la cámara cuando se encuentra fija y no presenta movimiento. Otro de los movimientos que se analizan es cuando la cámara tiene movimientos dentro del espacio.

Otro efecto que la cámara tiene cuando percibe las imágenes es el movimiento relativo, cuando la cámara se acerca a algún objeto y cuando el objeto se mueve a hacia la cámara ambos a velocidad constante, este efecto produce la obtención de la misma secuencia de imágenes en ambos casos.

Debido a que el movimiento captado por la cámara produce cambios diferenciales en los pixeles de la imagen; este presenta un flujo de pixeles en la dirección opuesta al movimiento que la cámara realiza; este flujo se representa con un campo vectorial, donde cada vector representa la velocidad instantánea de cada píxel, y por tanto el flujo óptico de la imagen es el arreglo de vectores de cada uno de los pixeles que constituyen la imagen o serie de imágenes y pueden ser representados por una función dada por f(x,y,t) donde las coordenadas (x,y,t) representan un punto en el espacio a través del tiempo t.

Figura: Espacio de cordenadas de la secuencia de imagenes

Referencias:

• Robust Incremental Optical Flow, Advisors: P. Anandan and D. V. McDermott, Yale University, Department of Computer Science, Research Report YALEU/DCS/RR-923, 1992.
  
• http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/OWENS/LECT12/lect12.html
  

Robots Móviles con Visión Artificial (8)

Navegación en exteriores no estructurados

Este tipo de navegación se refiere a la navegación en entornos que no tienen una estructura regular; y los robots tienen que lidiar con una ruta a campo traviesa; muchas veces este tipo de navegación estará dando vueltas en las vecindades sin encontrar una ruta a seguir. Además se requiere que el robot tenga rutas específicas y para eso el robot tiene que crear un algoritmo de localización para poder llevar a cabo la navegación hasta su objetivo. Para crear un mapa del entorno el robot tiene que tomar un marco de coordenadas a partir de su ubicación o a partir de un punto de referencia en el espacio.

Dentro de las técnicas que desarrollada para poder determinar la localización del robot en este tipo entornos incluyen la observación por cámaras externas, triangular puntos de referencia lejanos, tener un posicionamiento global, entre otros; uno de estos últimos se basa en la posición del sol mediante un inclinometro, “que es una cámara con filtros de densidad neutral y una plataforma ajustable” (DeSouza, 2002).

Uno de los robots que navegan en exteriores es el RATLER, este presenta un sistema de mapeo el cual consta de una concordancia de correlaciones que selecciona partes de la imagen tanto del lado derecho como del izquierdo para poder determinar las intensidades del entorno; y su sistema posicional es determinado por inclinometros, un compas entre otros instrumentos.

Otro de los robots que utilizan esta navegación es el Pathfinder el cual consta de un vehículo para la exploración de Marte; el explorador consiste de un sistema de navegación formado por diferentes funciones las cuales son: designación de un objetivo, selección de la ruta, localización del explorador en el entorno y la detección de peligros.

Iluminación en la navegación de exteriores

Debido a que el ambiente exterior es muy variable en los grados de iluminación; esto debido a que los niveles de iluminación del entorno dependen de las condiciones climáticas, la hora del día entre otros factores. Para poder lidiar con estos problemas se han desarrollados sistemas que usan el color para poder compensar los grados de iluminación de la imagen que es analizada. A lo largo de los años se han desarrollado técnicas que permiten diferenciar sombras de obstáculos. Algunos de estos usan módulos de visión redundantes, cuyo principal objetivo es determinar la posición de los obstáculos mientras que el robot navega en el entorno. Los diferentes módulos estudiaran áreas de las cuales se obtendrá su histograma de la intensidad de sus valores; cuando hay diferencias en los umbrales, se utilizan el alto del marco para estimar el alto del objeto que esta obstaculizando; estas salidas se promedian para poder determinar los movimientos y aceleración del robot.

Otro sistema de navegación que utiliza las diferencias de color para solucionar los problemas del sombreado en los objetos es el desarrollado por Mori(Mori1988), el cual utiliza un factor de impresión de color el cual es utilizado para compensar las variaciones de la iluminación causada por el sol; este sistema esta utiliza tres ventas posicionales que corresponden a tres regiones de la imagen analizada, dichas regiones analizan distancias largas, medianas y cortas; que facilitan las transiciones de estados sombreados a iluminados. Además de estos sistemas mencionados ha propuesto otro que utiliza la profundidad del pixel en lugar del promedio de los componentes RGB; debido a que utiliza una representación de la imagen dividida en 6 regiones, se determina que hay un obstáculo en la imagen si se detecta un movimiento de altura en la región de camino analizada.
A medida que pasa el tiempo se presentan nuevas y mejores innovaciones dentro del campo de la visión artificial, y al mismo tiempo se presentan nuevos retos con los que lidiar y problemas que resolver para poder desarrollar mejores sistema de navegación en cualquiera de sus modalidades en las que se utilice.


Referencias.

• H. Mori, K. Kobayashi, N. Ohtuki, and S. Kotani, “Color Impression Factor: An Image Understanding Method for Outdoor Mobile Robots,” Proc. IEEE Int’l Conf. Intelligent Robots and Systems, pp. 380-386, Sept. 1997.

• Guilherme DeSouza and A. C. Kak, "Vision for Mobile Robot Navigation: A Survey," IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 237-267, February 2002.

Robots Móviles con Visión Artificial (7)

Navegación en exteriores

Similarmente a la navegación en interiores; para que un robot móvil pueda navegar en el mundo exterior se necesita evitar obstáculos, detectar puntos de referencia, construcción de mapas y estimar su posición en el entorno para poder moverse dentro de este; aunque difícilmente es posible estimar un mapa de el entorno, dado que este es muy cambiante; además de que es muy difícil poder determinar su ubicación en el plano. Para poder determinar un sistema de navegación fiable se han dividido su estudio en dos vertientes que son la navegación en ambientes estructurados y la navegación en ambientes no estructurados.

Navegación en exteriores en entornos estructurados

Este tipo de navegación requiere un camino para recorrer, este debe de ser tal que se puedan determinar las líneas que delimitan un camino del resto del entorno. Estos deben de contener puntos de desvanecimiento, anchos de camino y línea de seguimiento, aunque estos sistemas de navegación tienen que lidiar con problemas de sombras, cambios de iluminación, colores entre otros. Entre los sistemas de esta índole, uno de los mas prominentes es el Navlab (Thorpe, 1987), el cual se utiliza desde minivans hasta metro buses que se encargan de conducirlos hasta ciertos destinos. Este sistema usa la visión en color para poder seguir una ruta y una visión tridimensional para poder detectar los obstáculos en el entorno. Su algoritmo de seguimiento se basa en tres puntos que son, la clasificación de los pixeles, el voto de la mejor posición para el camino y la actualización de los colores.

Dentro del la clasificación de los pixeles hay dos procedimientos que son la clasificación del color y la clasificación de la textura; dentro del primer procedimiento

“Cada pixel es asignado a una clase dependiendo de las distribuciones del color. Los pixeles del camino están representados por cuatro clusters Gausianos separados para tomar en cuenta los cambios de iluminación, las propiedades del camino, etc. Similarmente, los pixeles que no pertenecen al camino también están representados por un vector de medias tridimensional (con medias de R, G y B), por una matriz de covarianza de tres por tres y por la fracción de pixeles esperados a priori con el vector de colores X perteneciente a la da distribución i, PCi, que es calculada usando la distancia Mahalanobis: (X-mi)T ∑-1(X-mi). La clasificación es llevada a cabo usando estándares de pruebas de probabilidad de radios máximos. ”(DeSouza, 2002)


Además este sistema de navegación basa su clasificación de las texturas en las regiones del camino siendo estas mas brillantes que las que no lo son; la igualdad es medida por un índice de gradiente normalizado que es calculado utilizando el operador de Robert; posteriormente la clasificación de la textura es determinada por la probabilidad PTi que depende de los microbordes. Para determinar la clasificación de un pixel se combina la clasificación de textura y de color; estas características se asocian mediante la formula:

Pi = (1-α)PTi + αPCi

Debido a que la clasificación del color es más segura que la clasificación de textura; este se ve reflejado en el valor de α.

por lo tanto la clasificación de los pixeles en el camino y el entorno diferente al camino; quedan determinados por:

C = max{Pi, donde i es una clase de camino} - max{Pi, donde i es una clase diferente al camino}

Posteriormente de que se haya clasificado un pixel se aplica la transformada de Hough para obtener los parámetros de los puntos de desvanecimiento (P) y la orientación (θ); y donde cada pixel queda determinado por (P, θ) siendo el pixel que pertenece al camino el que tiene mayores votos. Después de ser clasificados los pixeles que pertenecen al camino y los que no, los pixeles que pertenecen al camino se vuelven a reclasificar para determinar los pixeles que pertenecen a los bordes del camino; esto permite al sistema de navegación adaptarse a las condiciones del camino que se sigue.

Aunado a la detección de los bordes y del camino, el sistema Navlab cuenta con un sistema de redes neuronales llamado ALVINN, el cual se encarga de determinar los ángulos en que se moverán las llantas del robot, este sistema es entrenado usando un algoritmo de propagación hacia atrás; también para poder determinar el centro de navegación del robot se utiliza una distribución Gausiana que dirige la orientación del robot en el camino. Aunque este sistema tiene problemas en el rendimiento del manejo y que la red neuronal olvide lo que aprendió en caminos curvos.

Otro sistema de navegación basado en el seguimiento de caminos es el sistema VITS; el cual consta de cámaras y sensores que permiten obtener la representación del entorno; el sistema de visión para la navegación produce un bosquejo del camino en un marco de coordenadas centradas para el vehículo; el cual se encarga de calcular la trayectoria que el robot seguirá. Donde el modulo de visión recibe del modulo de resonancia el cual consta de la información recibida por los sensores y una base de datos para poder determinar características del entorno como lo son forma, obstáculos, intersecciones, etc. La principal descripción del funcionamiento de este sistema se basa en la construcción de pixeles que pertenecen al camino y los que no, posteriormente se utilizan una técnica de sombreado dinámico para calcular en base al umbral y así poder determinar los límites del camino; y poder predecir el camino en base a estas observaciones.

Otros de los sistemas que se basan en el seguimiento de caminos son el sistema Prometheus el cual pertenece al proyecto EUREKA; el cual esta destinado a ser un sistema de navegación copiloto que avise cuando hay peligro de una colisión o accidente al conductor e incluso manejar autónomamente por periodos de tiempo.

Debido a que la velocidad en los robots móviles que navegan en exteriores es de suma importancia se han desarrollado sistemas que maximizan esta variable; uno de estos es el que utiliza una percepción adaptativa que se basa en tres parámetros que son el mirar hacia delante, barrer y escanear.

Referencias:

• C. Thorpe, T. Kanade, and S.A. Shafer, “Vision and Navigation for the Carnegie-Mellon Navlab,” Proc. Image Understand Workshop, pp. 143-152, 1987.

• Guilherme DeSouza and A. C. Kak, "Vision for Mobile Robot Navigation: A Survey," IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 237-267, February 2002.

Robots Móviles con Visión Artificial (6)

Navegación Usando Concordancias Basadas en Apariencias

Además de la navegación usando flujo óptico también podemos ubicar dentro de la navegación Mapless la navegación basada en apariencias; la cual se enfoca en la memorización de su ambiente; esto a través de plantillas predefinidas que están almacenadas, que asocian estas con el entorno observado y conforme a las comparaciones que se observan, permiten dar movimiento al robot.

Uno de los sistemas que utilizan este tipo de navegación es el sistema desarrollado por Gaussier et al. y Joulian et al., el cual se basa en redes neuronales para mapear las percepciones que la cámara observa en los movimientos ejecutados por el robot. Su funcionamiento consta de una imagen que es procesada en por sus niveles de intensidad, almacenando sus promedios en un vector; en el cual se forma una visión local del entorno, después de tener un conjunto de estos vectores con sus respectivas visiones locales; se forma un lugar en el plano con dirección acimutal que define un objetivo, estos son representados por los datos obtenidos de cada vector; posteriormente a partir de los planos obtenidos las redes neuronales se encargan de hacer la asociación de cada plano con los movimientos de navegación del robot.

Otro de los sistemas que utilizan este sistema de navegación es el desarrollado por Matsumoto et al.; el cual usa una secuencia de imágenes y un procedimiento de concordancia con plantillas para dar movilidad al robot; para esto se extraían subventanas de secuencia para poder emular un tipo de memoria de todas las imágenes observadas. Así mismo se desarrollo otro sistema de navegación del mismo autor pero a diferencia de este, este ejercía sus movimientos en base a una secuencia de imágenes y este buscaba la s concordancias con las imágenes que tenia en una base de datos.

Navegación Utilizando el Reconocimiento de Objetos

Este tipo de navegación es una navegación simbólica la cual utiliza un enfoque en el cual se le ordena prácticamente mediante comandos hacia donde se tiene que mover; todo esto utilizando información simbólica que se establece para poder determinar los puntos de referencia y así poder llegar a el objetivo que tiene determinado el robot.

Referencias.

• Guilherme DeSouza and A. C. Kak, "Vision for Mobile Robot Navigation: A Survey," IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 237-267, February 2002.

• C. Joulian, P. Gaussier, A. Revel, and B. Gas, “Learning to Build Visual Categories from Perception-Action Associations,” Proc. IEEE Int’l Conf. Intelligent Robots and Systems, pp. 857-864, Sept.1997.

• P. Gaussier, C. Joulain, S. Zrehen, and A. Revel, “Visual Navigation in an Open Environment without Map,” Proc. IEEE Int’l Conf. Intelligent Robots and Systems, pp. 545-550, Sept. 1997.

• Y. Matsumoto, M. Inaba, and H. Inoue, “Visual Navigation Using View-Sequenced Route Representation,” Proc. IEEE Int’l Conf. Robotics and Automation, vol. 1, pp. 83-88, Apr. 1996.

Robots Móviles con Visión Artificial (5)

Localización derivada del seguimiento de puntos de referencia

“Uno puede hacer la localización por el seguimiento de puntos de referencia cuando ambas, la localización aproximada del robot y la identidad de los puntos de referencia vistos en la imagen son conocidos y pueden ser seguidos.” (Desouza, Guilherme, 2002)

Debido a que los puntos de referencia pueden ser artificiales o naturales son analizados desde puntos de vista diferentes, dado que los puntos de referencia artificiales constan de prototipos predefinidos por el usuario, para que el robot los pueda visualizarlos de forma meramente simple con cámaras ubicadas en los costados de este que permiten reconocer las plantillas y así pueda obtener su posición dentro del espacio. Cuando no hay cámaras auxiliares se opta por buscar las propiedades de las plantillas ubicadas por el usuario para poder utilizar distintos algoritmos para obtener dicha localización.

Otro sistema de navegación que utiliza este tipo de navegación es el desarrollado por Hashima(1997); el cual usa técnicas de correlación para seguir puntos de referencia consecutivos ya sean naturales o artificiales, así como detectar obstáculos, este sistema utiliza el hardware dedicado TVR el cual se encarga de calcular las correlaciones, así mismo su sistema para obtener la localización del robot es determinada por múltiples algoritmos lo cuales se encargan de identificar puntos de referencia que ya están establecidos en la base de datos del robot y que este sigue; a partir de los puntos de referencia que se van registrando y el robot se va moviendo en el entorno, la posición del robot es estimada a partir de la comparación de los puntos referencia calculados y las posiciones de los puntos de referencia.

Construcción de mapas

Este tipo de sistema de navegación consiste en el crear un mapa del entorno a partir de modelos previamente establecidos o a partir de cero, siendo que los modelos son difíciles de generar, muchos autores han optado por crear robots capaces de construir una representación interna del entorno en el que navegan a medida que este va siendo explorado. Para esto se han construido diferentes robots los cuales constan de propiedades específicas que les permiten crear dicha representación.

Una de las técnicas utilizadas para poder implementar la creación interna del mapa es la de Moravec (1981,1983), el cual toma 9 imágenes consecutivas espaciadas en 50cm y que utiliza un operador de interés que extrae las características distintivas de la imagen. Otra técnica fue la desarrollada por Thorpe (1984) el cual utilizaba el operador de interés de Moravec para generar las características de las imágenes en coordenadas tridimensionales. Con esta innovación en 1985 Moravec y Elfes propusieron las rejillas de ocupación que es información que determina si una celda en el espacio es ocupada o no esto a partir de la información obtenida por sensores ultrasónicos.

“Mientras que los acercamientos basados en rejillas de ocupación son posibles de generar mapas que son ricos en detalles geométricos, la extensión a la cual la geometría resultante puede ser confiable sobre navegaciones subsecuentes dependen de la exactitud de la edometría y las incertidumbres sensoriales durante la construcción del mapa.” (Desouza, Guilherme, 2002).

Otra de las técnicas es la utilizada por Thrun (1998) el cual propone integrar el sistema de navegación basado en rejillas de ocupación y el sistema de acercamiento basado en topología; aun cuando estas dos técnicas contrastan entre ellas; debido a que una pretende obtener el mapa en observaciones y en la otra ya esta representado el mapa de navegación por medio de nodos.

Navegación en Sin Mapas

Este tipo de sistemas de navegación es logrado sin tener ninguna descripción o información del entorno; es decir que en este tipo de navegación no se basa en mapas; sino a partir de información relevante de los objetos que se observan en el entorno, lo cual conlleva a el robot a ejercer movimientos dependiendo de dicha información. Siendo la única forma de que el robot pueda moverse en el entorno, este necesita observar los elementos que existen en el ; las técnicas utilizadas para analizar estos objetos son el sistema basado en el flujo óptico y el sistema basado en apariencia.

Navegación usando flujo óptico

Uno de los sistemas basados en el flujo óptico es el desarrollado por Santos-Victor (1993) el cual basa su sistema en la imitación del sistema visual de las abejas; ya que favorece los mecanismos de navegación ya que ocupa mayor campo de visión y es usado para generar movimientos a partir de las características del entorno. Este sistema utiliza estereofonía divergente para tratar de imitar el centro de reflejo de la abeja; el cual se basa en la diferencia de velocidades entre las imágenes izquierda y derecha siendo estas aproximadas a cero, si las velocidades son diferentes entonces tomara acciones necesarias para guiarse en el entorno.

Para calcular el flujo óptico de cada lado de la visión se parte de las ecuaciones:

δIu/δx + δIv/δy + δI/δt = 0

donde:
u, v -> son las componentes de flujo horizontal y vertical

Mientras el robot se encuentre en un plano el flujo vertical tiende a cero; debido a que no hay movimiento en esa dirección por que se mantiene constante sobre el centro; entonces la ecuación quedara como:

u = -It/Ix

donde:
It e Ix son las derivadas espaciales de el tiempo y de x en la imagen.

Dado que los flujos ópticos en los lados tienen direcciones opuestas; se relacionan con la ecuacione:

e = uL + uR = TM(1/ZR – 1/ZL)

donde:
TM -> es la velocidad de movimiento hacia delante
ZR y ZL -> son las proyecciones horizontales de los movimientos de izquierda y derecha.

Debido a que estas ecuaciones no permiten cambiar la dirección del movimiento, no permiten hacer movimientos rotacionales, y estas ecuaciones solo pueden ser utilizadas si se cumplen las condiciones siguientes:

“1. La velocidad rotacional no es mas larga que ciertos factores de tiempo en la velocidad de traslación. Este factor esta en función de la posición relativa de las cámaras en representación polar, con respecto del marco de coordenadas del robot.
2. Las cámaras están montadas tan cerca como sea posible del centro de rotación del robot.
3. El procedimiento de calibración es realizado en orden de compensar por un termino independiente que aparece en la ecuación para movimiento rotacional.” (Desouza, Guilherme, 2002).

Además de tener que satisfacer estas condiciones, los cálculos del flujo óptico dependen de la existencia de texturas en el corredor que se navega; en caso de tener deficiencia en la textura se presentara lo que se llama comportamiento sostenido; el cual causa que el robot se detenga.

Referencias:

Guilherme DeSouza and A. C. Kak, "Vision for Mobile Robot Navigation: A Survey," IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 237-267, February 2002.

Santos-Victor, G. Sandini, F. Curotto, and S. Garibaldi,“Divergent Stereo for Robot Navigation: Learning from Bees,” Proc. IEEE CS Conf. Computer Vision and Pattern Recognition, 1993.

Robots Móviles con Visión Artificial (4)

Uso de una representación topológica del espacio

Dentro de la localización incremental también existe la localización por medio de representaciones topológicas del entorno; como lo es el caso del sistema NEURO-NAV; el cual representa un plano físico por medio de representaciones topológicas como lo pueden ser nodos y líneas que unen estos nodos; los cuales toman significado a partir del esquema fisco; donde cada nodo es un atributo de dicho esquema. Estudiando mas a fondo el sistema NEURO-NAV consiste de dos módulos uno dedicado a determinar el camino a recorrer y el otro dedicado a obtener los puntos de referencia; ambos utilizando redes neuronales.

“Ambos módulos permiten al robot ejecutar movimientos y al mismo tiempo realizar su localización” (Desouza, Guilherme, 2002).

Es decir que al mismo tiempo que se mueve en el entorno es capaz de reconocer puntos de referencia en el entorno. Dado que cada uno es una red neuronal, tanto el seguidor de caminos como el detector de puntos de referencia pueden tener subtareas específicas para realizar su labor en el sistema; debido a que esta haciendo tareas en paralelo sin recurrir al computo paralelo, para acelerar el computo se reduce el tamaño de la imagen y se aplica un filtro de Sobel para detectar los bordes.

Dado que ambas módulos utilizan redes neuronales; el proceso de entrenamiento utiliza un algoritmo de propagación hacia atrás; que es controlado por un modulo de supervisión humana que toma el control de la navegación del sistema.

“Este modulo permite al operador humano especificar comandos simples de movimiento mientras se empiezan las rutinas de digitalización, que graban imágenes usadas subsecuentemente para el entrenamiento” (Desouza, Guilherme, 2002).

Debido a que se utilizan diversas redes neuronales estas son supervisadas por un controlador basado en reglas.

Posteriormente, y debido a que las salidas de datos de las redes neuronales podían ser fácilmente construidos, se desarrollo un sistema de navegación que en lugar de utilizar a un controlador basado en reglas fue reemplazado por un supervisor controlador de rizo; el cual toma todas las salidas que producen las redes neuronales y decide que comando articular al modulo de control del robot; este se encargaría de usar variables lingüísticas como: la distancia a la unión, ángulo de giro y la distancia viajada.

Referencias:

• Guilherme DeSouza and A. C. Kak, "Vision for Mobile Robot Navigation: A Survey," IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 237-267, February 2002.
• M. Meng and A.C. Kak, “NEURO-NAV: A Neural Network Based,Architecture for Vision-Guided Mobile Robot Navigation Using Non-Metrical Models of the Environment,” Proc. IEEE Int’l Conf. Robotics and Automation, vol. 2, pp. 750-757, 1993.

Robots Móviles con Visión Artificial (3)

Propagación de incertidumbre posicional por movimientos comandados

El sistema de navegación FINALE para poder determinar su posición basada en localización incremental busca relaciones entre la posición actual p=(x,y,Θ) y su posición después de cierto movimiento p’=(x’,y’,Θ’) y esta dada por la relación lineal

p’=h(p)

Y por los parámetros de incertidumbre (p,Σp) con los parámetros (p’,Σ’p) que están relacionados por las ecuaciones con las que se puede determinar la posición del robot antes y después de algún movimiento.

p’ = h(p)
Σ’p = (δh/δp)Σp (δh/δp)T

Donde:
δh/δp -> es el Jacobiano de la función de transformación h.
P -> es la media.
Σp -> es la covariancia.

Para el movimiento de traslación el punto se parametriza en función de d, α y β que son variables aleatorias; dado que el robot se puede mover sobre el eje yr una distancia d0 su nueva posición estará determinada por las ecuaciones del punto p’ y que son:

p'x = px - dsin(φ+α) -> para la posición en x
  p’y = py + dcos(φ+α) -> para la posición en y
φ’ = φ + β -> para la orientación

donde los valores d, α y β tienen medias d, α y β y una matriz de covarianza:

ΣT(d, α ,β)= [[σ2d ρdασdσα ρβσdσα ]
                        [ρdασdσα σ2α ραβσασβ ]
                         [ρdβσdσβ ραβσασβ σ2β ]]

Donde los valores ρ son los coeficientes de correlación y σ son las desviaciones estándar. Así mismo d0 depende de estos valores y sus medias.

Similarmente para determinar la posición del robot cuando hay un movimiento de rotación en un ángulo Θ0 en su propio eje de coordenadas; su nueva posición p’ se encuentra determinada por los parámetros Θ, u y v; y la relación entre el punto anterior y el nuevo punto esta dado por las ecuaciones:

p'x = px – ucosΘ- vsinΘ -> para la posición en x
  p’y = py + usinΘ + vcosΘ -> para la posición en y
φ’ = φ + Θ -> para la orientación

Dado que al igual que la distancia recorrida en la traslación; la orientación Θ0 es parametrizada en términos de u, v y Θ con medias u, v y Θ y matriz de covarianza:

ΣR(u, v ,Θ)= [[σ2u ρuvασuσv ρuΘσuσΘ ]
                    [ρuvσuσv σ2v ρvΘσvσΘ ]
                        [ρuΘσuσΘ ρvΘσvσΘ σ2Θ ]]

Donde los valores ρ son los coeficientes de correlación y σ son las desviaciones estándar; siendo Θ0 dependiente de estos valores y las respectivas medias de los valores u, v y Θ.

“Estas ecuaciones muestran que la posición del robot al final de un comando de movimiento depende de la no linealidad de su posición anterior. La dificultad puesta por la naturaleza no lineal de las ecuaciones de transformación es superada por aproximaciones lineales a las ecuaciones y asegurando que los movimientos sean pequeños tales que no invaliden las aproximaciones”. (DeSouza, Guilherme, 2002)

Aunado a esto para poder obtener la linealidad solo se necesita saber el Jacobiano de la transformación de la media de p a la media de p’; que en términos de movimientos de traslación del robot tendríamos:

Σ’p = (p’x,p’y,φ’)=JT1Σp(px,py,φ)JTT1 + JT2ΣT(d,α,β)JTT2

Y para movimientos de rotación tendríamos:

Σ’p = (p’x,p’y,φ’)=JR1Σp(px,py,φ)JTR1 + JR2ΣR(u,v,Θ)JTR2

Siendo estas ecuaciones las que nos indicaran como actualizar las medias y covarianzas de la posición del robot en cada uno de sus movimientos de rotación y traslación.

Proyección de la incertidumbre posicional del robot en una imagen fotográfica

Proyectando la incertidumbre de la posición del robot en la imagen, esta puede ser utilizada para determinar mejores puntos de referencia en el entorno en el sistema de navegación FINALE; para lograr este fin se utiliza la matriz de calibración; la cual parte de las coordenadas espaciales del entorno en el que se encuentra el robot y que están determinadas por (x,y,z). En la imagen un punto del entorno estará dada por el pixel con (x,y) y con coordenadas homogéneas dadas para el punto del entorno; su relación esta dada por:

[[XW] [YW] [W]] = TH[[x][y][z][1]]

Donde:
W -> es el factor de perspectiva
T -> es la matriz de calibración
H -> la matriz de transformación de puntos del marco del entorno a marcos centrados del robot.

Aunado a esto también se puede expresar una relación entre las coordenadas del pixel y el vector posicional p=(px,py,φ) para puntos dados. Siendo que esta ecuación es no lineal se utiliza el Jacobiano para poder obtener la liberalización de la relación entre estos puntos.

Filtrado Kalman

Este filtrado es utilizado principalmente para actualizar los parámetros estadísticos de la posición del robot después de determinar puntos de referencia; para esto se parte de un modelo basado en el filtrado Kalman; el cual consiste de los siguientes pasos:

1. Derivación de una ecuación que tome a la matriz de calibración y relacione los parámetros de los puntos de referencia o en los parámetros de la imagen o en los parámetros del espacio Hough.
2. Forzar la linealidad de la ecuación para la derivar las ecuaciones del filtrado.
3. Proyectar la incertidumbre posicional en la imagen para encontrar las características candidatas a ser puntos de referencia.
4. Usar el filtrado Kalman.

Una vez que se ha llegado a el cuarto punto el sistema de navegación se ha localizado a si mismo en el espacio; siendo este el sistema de navegación de FINALE que muestra el como funciona la localización incremental.


Referencias:

• Guilherme DeSouza and A. C. Kak, "Vision for Mobile Robot Navigation: A Survey," IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 237-267, February 2002.
• Kosaka and A.C. Kak, “Fast Vision-Guided Mobile Robot Navigation Using Model-Based Reasoning and Prediction of Uncertainties,”Computer Vision, Graphics, and Image Processing—Image Understanding, vol. 56, no. 3, pp. 271-329, 1992.

Robots Móviles con Visión Artificial (2)

Localización absoluta

Uno de los principales objetivos de este tema es la localización del robot dentro del espacio; esto debido a que su posición inicial es desconocida; siendo que a partir de el punto de referencia donde se encuentra el robot se partirá para poder determinar los datos necesarios para la navegación; debido a que hay diferentes puntos de vista de cómo determinar la posición inicial, se han desarrollado métodos para poder establecer la localización inicial como son la localización de Markov, localización de Montecarlo, filtrado de hipótesis múltiples de Kalman; entre otros.

Hatiya y Hanger propusieron un método para poder ubicar la posición inicial del robot el cuyo principal funcionamiento esta basado en el reconocer entidades dentro de las imágenes que la cámara esta procesando y que son invariantes; es decir busca puntos de referencia constantes durante la navegación en el entorno; una vez que se tengan los puntos de referencia el robot necesitara hacer las triangulaciones entre los puntos de referencia para obtener su localización; aunque existen varios errores por los que se podría incurrir; como lo puede ser el error de pixeles en la imagen, multiplicidad en los puntos de referencia entre otros. Sin embargo para poder lidiar con estos problemas de incertidumbre y ambigüedades en los puntos de referencia y poder obtener la localización del robot, se han utilizado conjuntos basados en acercamientos; y se ha denominado problema de etiquetado.

A continuación explicare el problema de etiquetado:

Sea j un punto de referencia observado en la imagen, y este punto de referencia es observado por dos cámaras, una en la derecha y otra en la izquierda; entonces podemos decir que:

Oj=(ol,or) con intervalo el cuadro de la cámara ± ε.

Donde:
Oj -> es el intervalo de observación entre las cámaras izquierda y derecha.
ol -> es la observación de la cámara izquierda.
or -> es la observación de la cámara derecha.
ε -> es el error de la medición sensorial.

Sea pj el intervalo de localización del punto de referencia j con respecto al marco de la imagen ± una tolerancia δ. Y sea p la posición del robot, entonces podemos dar un intervalo de observación esperado dado por la proyección en el plano:

h = Proy(p,pj)

Para que la obtención de los puntos de referencia estén libres de errores; el intervalo de observaciones y el intervalo de puntos de referencia deben conincidir. Y por lo tanto podemos definir a:

λ ={oi,pj}

como la coincidencia de los intervalos de observación y puntos de referencia; y a el conjunto de dichas coincidencias como:

Λ= {{oi,pj}}

Dado que ya hemos definido los intervalos en los que se basara para obtener la localización del objeto; esta localización estará en función de todas las intersecciones de estos dos intervalos.

“Esta se tornara mas pequeña mientras mas observaciones estén combinadas, dando un mejor estimado de la incertidumbre” (DeSouza, Guilherme, 2002).

Para poder estimar la posición del robot dada por p=(x,y,Θ) donde x, y es la posición del robot y Θ es la orientación de este; se dieron puntos de referencia conocidos y observaciones de estos; lo cual los conllevo a dos problemas.

“Problema 1. Dados n puntos localizados en los intervalos p1, p2, . . . ,pn en el marco de coordenadas del mundo que representan los puntos de referencia y los m pares de intervalos de observación o1,o2, . . . ,om en el marco de coordenadas de la cámara del robot, determinar un etiquetado constante Λ = {{oi,pj}}, tal que: Proy(p,pj) ∩ oi ≠ 0, para todo Є Λ .

Problema 2. Dado el etiquetado de arriba, encontrar el conjunto de posiciones de P del robot, consistentes con el etiquetado. Es decir, encontrar el conjunto P={p | Proy(p,pj) ∩ oi ≠ 0}, para todo Є Λ. “ (DeSouza, Guilherme, 2002)

Para solucionar el problema se sugiere usar el etiquetado con mayor número de concordancias, o mayor a cuatro; esto comparando todas las posibles triangulaciones sujetas a la heurística, esto con todos los posibles puntos de referencia que pueden ser encontrados en la imagen analizada.

Debido a que primero se tiene que resolver el problema 1, que consiste en encontrar un etiquetado consistente Λ, para poder seguir con determinar la posición del robot dado por el problema 2; para resolver este segundo se analizaron las fuerzas geométricas que involucran los puntos de referencia en las triangulaciones. Resumiendo podemos decir que la posición del robot esta dada por p=(x,y,Θ) donde:

Θ = Θo - Θd

Además

Θo = atan((ty + λsy)/(tx+λsx)) y Θd = atan(ry/rx)

Donde:
t -> representa segmentos conectando dos regiones de incertidumbre (t=o1-o2)
s -> representa segmentos dentro de la regiones (s=o2,k – o2,j ; j^k son esquinas de o2)
r -> representa segmentos conectando los puntos de referencia localizados por p1 y p2.

“Debido a la representación triangula, las regiones de incertidumbre producen diferentes valores de Θ. Estos valores son combinados para formar un intervalo o conjunto de intervalos.” (DeSouza, Guilherme, 2002)

Dada la intersección de los intervalos sobre las concordancias de λ se obtiene Θ*; y a partir de esto podemos determinar la posición del robot que esta dada por las ecuaciones:

xi = pi,x + sin(Θ*)ti – cos(Θ*)si
yi = pi,y + sin(Θ*)si – cos(Θ*)ti

La intersección de los conjuntos xi y yi para todas las regiones producen x*, y* que con Θ* tienden a cero mientras mas iteraciones haya.

Localización Incremental

Usando representaciones geométricas del espacio; es posible conocer la posición inicial del robot de una forma aproximada; esto es utilizando algoritmos que sigan la pista de la incertidumbres en las posiciones en las que se encuentra el robot y dar movimientos a partir de estos. Uno de los sistemas de navegación que utilizan este tipo es el sistema FINALE; el cual utiliza técnicas probabilísticas que se acercan a la representación y actualización de incertidumbres posicionales, a medida que el robot se mueve; este sistema consta de los siguientes elementos.

1. Representa la incertidumbre de una posición p=(x,y,Θ) por distribuciones Gaussianas; y esta incertidumbre es caracterizada por p y la covarianza Σp.
2. Se caracterizan y parametrizan los movimientos del robot conforme a movimientos de traslación y rotación.
3. Determinando la incertidumbre de la posición del robot cuando tiene movimientos de rotación y traslación; estos cambios son dependientes de p y Σp en dichos movimientos.
4. Diseño de un modelo basado en filtros Kalfman.

Referencias:

• Guilherme DeSouza and A. C. Kak, "Vision for Mobile Robot Navigation: A Survey," IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 237-267, February 2002.

Robots Móviles con Visión Artificial (1)

El campo de la visión artificial es bastante amplio debido a que hay un sinfín de derivaciones de los temas de inteligencia artificial. Al igual que nosotros como humanos podemos movernos dentro de espacios cerrados o abiertos; los robots también recaen dentro de la navegación en interiores y exteriores. Debido a que existe una gran variedad de entornos tanto en lugares abiertos como cerrados; se han desarrollado varias formas de cómo atacar los problemas que tienen los robots para poder moverse dentro de dichos entornos sin ser obstruidos por algún objeto.

Dentro de la navegación en interiores, en las décadas pasadas se tenían problemas para poder detectar de forma adecuada las características del entorno; una de las soluciones que se dieron para poder solventar estas limitantes fue el desarrollo de sistemas los cuales basaban sus modelos de navegación en marcos; como lo es el caso del sistema FINALE donde

“el robot solo examina las porciones de la imagen que contienen un nivel bajo de rasgos en la vecindad de las características del modelo; la extensión de la vecindad es determinada por la incertidumbre en la posición del robot”. (DeSouza, Guilherme, 2002)

Este tipo de sistemas son de los cuales la geometría del espacio es primordial para su implementación.

Otro de los sistemas que se han realizado para la navegación en interiores, son los sistemas de navegación basados en la visión; los cuales utilizan representaciones del espacio en forma topológica y con ayuda de las redes neuronales se puede guiar al robot a través del entorno físico; como lo son los sistemas NEURO-NAV y FUZZY-NAV.

Por otro lado dentro de los sistemas de navegación en exteriores se encuentra el sistema NAVLAB; el cual analiza los limites de un camino basándose en la intensidad de las imágenes; algunos de sus similares son los sistemas RALPH, ALVINN, AURORA, entre otros. Donde estos sistemas son utilizados para la navegación autónoma de automóviles.

Navegación en interiores

Dentro de los sistemas de navegación en interiores; estos han pasado por varios procesos para que el robot pueda moverse a través de ellos; anteriormente se utilizaban los sistemas que se basaban fuertemente en la geometría del espacio; posteriormente se opto por los sistemas basados en el Diseño Asistido por Computadora (CAD, por sus siglas en ingles); posteriormente estos fueron remplazados por los mapas ocupacionales, mapas topológicos o imágenes en secuencia.

Los sistemas de navegación en interiores se pueden clasificar de la siguiente forma:

“1. Navegación Basada en Mapas- son sistemas que dependen de modelos geométricos o mapas del entorno creados por el usuario.
2. Navegación Basada en Construcción de Mapas- sistemas que usan sensores para construir su propio modelo geométrico o topológico del entorno y usan este modelo para la navegación.
3. Navegación Sin Mapa- sistemas que no usan una representación explicita de todo el espacio en el que navegan para tomar espacio; pero recurren al reconocimiento de objetos encontrados en el entorno o siguiendo esos objetos por generación de movimientos basados en observaciones visuales. “ (DeSouza, Guilherme, 2002)

Navegación Basada en Mapas

Como ya se había mencionado antes estos sistemas de navegación se basan en darle al robot el mapa del entorno que tiene que recorrer; dentro de los primeros sistemas de este tipo estaban los que consistían en mapas de dos dimensiones en donde los objetos era representado por un objeto dentro de este espacio; después surgieron los que utilizaban los Campos Virtuales Forzados (VFF, por sus siglas en ingles); donde los objetos que obstaculizaban el paso del robot ejercían fuerzas repulsivas mientras que el objeto ejercía fuerzas atractivas. Posteriormente se desarrollo el S-Map; el cual consistía en compactar espacio tridimensional en un mapa de dos dimensiones; este sistema requiere de proyecciones de puntos en el espacio en un plano. Otro de los sistemas de navegación de este tipo ocupan la incertidumbre para contar los errores en medida de las coordenadas asociadas con el espacio del objeto; contabilizando las coordenadas del objeto en celdas ocupadas o vacías.

“Los cálculos involucrados en la localización basada en visión pueden ser divididos en cuatro pasos:
1. Adquirir Información Sensorial. – para la navegación basada en visión, significa adquirir y digitalizar imágenes.
2. Detección de puntos destacados. - usualmente significa extraer bordes, suavizar, filtrar, y segmentar regiones en base a diferentes niveles de gris, color, profundidad o movimiento.
3. Establecer marcas entre la observación y la expectativa. – En este paso el sistema trata de identificar los puntos que resaltan; buscando en la base de datos por posibles concordancias de acuerdo a algún criterio de medición.
4. Calcular la posición. – Una vez que hay concordancia o conjunto de concordancias es obtenida, el sistema necesita calcular su posición como función de los puntos observados y su posición en la base de datos.” (Borenstein, J., 1996 )

Dentro de la localización de los robots basados en la visión hay distintas vertientes de las cuales podemos mencionar: la localización absoluta o global, localización incremental y localización derivada del seguimiento de puntos destacados.

Referencias

• Guilherme DeSouza and A. C. Kak, "Vision for Mobile Robot Navigation: A Survey," IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 237-267, February 2002.
• J. Borenstein, Member, and Y. Koren, “The vector field histogram – fast obstacle avoidance for mobile robots” IEEE Journal of Robotics and Automation Vol 7, No 3, pp. 278-288, June 1991,.