Flujo Óptico en Robots Móviles (7)

b) Métodos locales

Los modelos de velocidad asumen que movimientos simples en patrones son comunes. Y la forma más común de solucionarlos es por mínimos cuadrados; donde la velocidad estimada se calcula minimizando:

ΣxЄRW2(x)(Gradiente(I)(x,t)•V+It(X,t))^2

Donde W(x) denota la función de una ventana y R los vecinos espaciales. El problema de apertura es resuelto analíticamente incluyendo 2as derivadas parciales. Estas restricciones proveen ecuaciones en las dos componentes del vector velocidad y esta determinada por la ecuación:

(Gradiente)(Gradiente)(I)=-Gradiente(It)

Donde el resultado expresa las dos componentes de velocidad en cada punto de la imagen.

Otro de los métodos que se usan para calcular el flujo óptico y que evita el estimar la intensidad de las derivadas, usan el teorema de divergencia de Gauss; lo cual nos da la siguiente ecuación:

∫v(Ix+Iy+It)dV = ∫SuIdydt + ∫SvIdxdt - ∫VI(ux+vy)dxdydt + ∫SIdxdy = 0

Donde S y V denotan la integración local sobre las superficies y volúmenes en la intensidad de la información.

c) Modelos de Superficie

En dos planos con distintas orientaciones de superficie y que tienen diferentes movimientos en el espacio 3d tienen el mismo flujo óptico.
Las técnicas para calcular los movimientos en planos asumen que la velocidad en el punto de curvatura en una superficie es definido por una aproximación en las 2as series de expansión de Taylor (Waxman y Wohn, 1988).

v(x,y)=v(0,0) + δv/δx + δv/δy + 1δ^2vδ/2δx^2 +δ^2v/ δxδy + 1δ^2v/2δy^2


Cuando aplicamos la ecuación restrictiva de velocidad normal vn=v•n se obtiene una ecuación lineal con 12 incógnitas en las componentes de v y sus derivadas de 1er y 2º orden. Donde la superficie que es plana esta dada por:

δ^2v/δx^2=(2δ^2v/δxδy,0) y δ^2v/δy^2 = (0,2δ^2u/δxδy)

estas ecuaciones permiten escribir la ecuación de Waxman y Wohn en una ecuación con 8 incógnitas y que permiten recuperar la velocidad de una superficie plana.

d) Modelos de contornos

Estos métodos se enfocan en la extracción de contornos relevantes en la imagen con un prefiltrado, seguido de estimaciones diferenciales en el movimiento de la imagen; esto debido a que los contornos tienen señales fuertes de ruido que los hace un blanco fácil para poder extraer las características geométricas de un objeto. Hildreth \cite{} propone una restricción de suavidad que se aplica a velocidades normales estimadas a traves de contornos extraídos de imágenes variando en el tiempo. Donde para una superficie S la velocidad normal estimada es:

∫δv/δSdS

Si al menos dos velocidades normales estimadas a través de la superficie S son diferentes, entonces la minimización de esta integral cede a una única velocidad sobre el contorno S.


∫(δv/δS)^2 + β(v•ň-||v+||2)^2dS

Donde ň es el vector unitario en la dirección de la v+ minimizada a lo largo de los contorno. Donde β es el factor de peso y (v•ň-||v+||) es la diferencia de cuadrados entre la velocidad normal estimada y la velocidad predicha para la solución.

Gong y Brady(1990) formulan una restricción similar pero incluyen una diferencia de mínimos cuadrados para la velocidad tangencial.

∫(δv/δS)^2 + β( v • ň-||v+||2)^2dS + a(v • ŧ - ||v||||2)2dS

Donde ŧ es el vector unitario perpendicular ň y a es una expresión escalar asociada con la componente tangencial de v, proporcional al determinante de la matriz Hessiana de las intensidades de las estructuras en la imagen.

e) Métodos Multicontraste

Estos métodos usan múltiples instancias de la ecuación restrictiva del flujo óptico para proveer expresiones ambiguas de los movimientos en las imágenes a partir de simples puntos, expanden la imagen espacio temporal con polinomios Hermite y resuelven para v usando mínimos cuadrados estándar.
Sistemas con funciones diferentes a la intensidad pueden ser sustituidos en la ecuación restrictiva del flujo óptico, que pueden ser vistas como operaciones aplicadas a los niveles de gris. Aunque el problema de apertura no puede ser resuelto cuando se encuentran singularidades en sistemas sobre restringido. Esto ocurre en estructuras con intensidades particulares, como lo son regiones con intensidad uniforme, texturas periódicas o imágenes muy estructuradas.

f) Enfoques Jerárquicos.

Este tipo de enfoques se utilizan cuando existen problemas con largos movimientos en el espacio 2D, en la aplicación de métodos diferenciales en una forma de lo grueso a lo fino se soluciona este problema. Donde se trata de bajar la resolución de una imagen para poder determinar su flujo óptico, de forma más sencilla.

Bibliografia:

• A. M. Waxman and K. Wohn. Contour evolution, neighborhood deformation, and global image flow: planar surfaces in motion. Int. J. of Robotics Res.,4(3): 95-108, 1985.
  
• S. Gong and M. Brady, Parallel computation of optic flow. In Proc. of ECCV, pages 124-133, 1990.
  
• Beauchemin, S. S. & Barron, J. L.,The computation of optical flow, ACM Comput. Surv., ACM, 1995, 27, 433-466.
  

Flujo Óptico en Robots Móviles (6)

Técnicas para calcular el flujo óptico


Dentro de las técnicas que existen para calcular el flujo óptico encontramos:

1. Métodos basados en diferencias de intensidades.
2. Métodos basados en frecuencias.
3. Métodos basados en correlación.
4. Métodos de múltiples movimientos.
5. Métodos de refinamientos temporales.

A continuación se describirán cada uno de ellos.

1. Métodos basados en diferencia de intensidades.

Las técnicas diferenciales calculan las velocidades de una imagen a partir de derivadas espaciotemporales de las intensidades de la imagen; esto asumiendo que el dominio de la imagen es diferenciable en espacio y tiempo. Dentro de estos métodos podemos hacer una clasificación de cómo se ha obtenido el flujo óptico usando la diferencia de intensidades; para esto tenemos que se han utilizado:

a) Métodos Globales.
b) Modelos Locales.
c) Modelos de Superficie.
d) Modelos de Contorno.
e) Métodos Multicontraste.
f) Enfoques Jerárquicos.

A continuación se describirán como están se desarrolla cada uno de estos métodos para la obtención del flujo óptico.

a) Métodos Globales

Dentro de estos métodos podemos encontrar que a partir de la ecuación:

I(x,t)≈(x +δx,t + δt)

y con la restricción de suavidad obtenemos una minimización sobre el dominio de la imagen todo esto para clarificar las medidas normales y obtener las velocidades vecinas si corresponden a la misma superficie del objeto; debido a que estas velocidades serán muy idénticas. Donde se define el error funcional conforme a las restricciones sobre el dominio de interés de la imagen D.

∫D ((I•v + It )2 + λ2 tr((v)T(v)))dx

Donde v = (u,v) y la solución a v esta dada por las ecuaciones de Gauss-Seidel que se resuelven iterativamente y donde se deben de satisfacer las condiciones que permitan satisfacer la restricción del brillo constante en la imagen (dI/dt = 0) y estas son: que se tenga una iluminación uniforme en el dominio de interés de la imagen , proyecciones ortográficas y movimientos de traslación paralelos puros a la escena de la imagen. Donde a partir del cumplimiento de estas condiciones se obtiene la siguiente ecuación:

Gradiente(I)•v + I(ux+vy) = - It

Debido a que esta ecuación es equivalente a I(x,t)≈(x +δx,t + δt) pero conteniendo un nuevo termino el cual expresa la compresión o expansión de las vecindades de la imagen, así como las transformaciones afines.

Otro de los métodos que recaen en esta clasificación general es el propuesto por Nagel el cual considera que la restricción del flujo óptico debe estar basada explícitamente en las propiedades geométricas de las escenas 3D, el cual plantea la siguiente ecuación:

Gradiente(I)•v + It = 4I(zPT/ zPT-PPT/PPT)

Donde P es punto 3D del ambiente, P es la velocidad 3D y z es el vector unitario a lo largo de los ejes de línea de visión.


Bibliografía:

Beauchemin, S. S. & Barron, J. L.,The computation of optical flow, ACM Comput. Surv., ACM, 1995, 27, 433-466.

Flujo Óptico en Robots Móviles (5)

Problemas y cuestiones en el cálculo del flujo óptico.

Aunque existen diversas dificultades para poder obtener un flujo óptico de una secuencia de imágenes. Beauchemin y Barron (Barron1995) han hecho modelos para el análisis de imágenes en movimiento, los cuales analizan algunas propiedades del movimiento que presentan dificultades en el cálculo del flujo óptico, y estas son:

Imágenes en movimiento y flujo óptico. La estimación de flujo óptico a partir de variaciones de intensidad en imágenes solo da una aproximación del movimiento en las imágenes; además se tienen problemas donde el flujo óptico presenta diferencias en imágenes con ausencia de textura, donde el flujo óptico es nulo, también se tiene problemas cuando la consistencia del brillo es violada, donde superficies con reflejo Lamberciano, brillos, sombras, entre otros efectos de luz causan un flujo óptico incorrecto.

Superficies ocluidas y movimiento independiente de objetos. El problema que se presenta en la oclusión de imágenes es el poder determinar la dirección de traslación de los objetos, así como segmentar la escena en superficies con movimientos independientes.

Transparencia. Los movimientos creados por superficies traslucidas crean problemas de múltiples distribuciones de movimiento.

Así mismo Beauchemin y Barron (Barron1995) observaron el rendimiento de las técnicas desarrolladas para el cálculo del flujo óptico durante el periodo 1981 – 1990, y obtuvieron las siguientes conclusiones, en las que se determinan las características principales para el cálculo del flujo óptico.

Diferenciación y Prefiltrado. El suavizado temporal es requerido para evitar diferencias numéricas; donde los métodos diferenciales para el cálculo del flujo óptico requieren intensidades lineales en la imagen con movimientos menores a una unidad espacial por cuadro; en caso de que el suavizado temporal no pueda ser evitados, entonces métodos jerárquicos proveen mejores resultados.

Fiabilidad de las medidas. La mayoría de los métodos diferenciales no proveen exactitud en las medidas en las velocidades del flujo óptico; y es donde los métodos de la matriz de mínimos cuadrados es la que obtiene los mejores resultados que los determinantes de las matrices Hessianas, el número condicionante de la solución de una matriz, la magnitud de los gradientes locales de una imagen o los valores del principio de curvatura, entre otros.

Exactitud. Para obtener la exactitud en los cálculos del flujo óptico, los métodos de correlación jerárquicos son esquemas que determinan las medidas de una forma más robusta que otros métodos.

Dentro de los métodos que estiman la velocidad de imagen se encuentran clasificados según Beauchemin y Barron(Barron1995), de la siguiente forma:

• Métodos basados en la diferencias de intensidades.
• Métodos basados en el filtrado de frecuencias.
• Métodos basados en correlación.

Y en los métodos que calculan los múltiples valores discontinuos en el flujo óptico y los métodos que calculan los refinamientos a medida que se obtiene mayor información.

• Métodos de múltiples movimientos.
• Métodos de refinamientos temporales.

Donde el desarrollo de cualquiera de estos métodos esta basado en los pasos de: prefiltrado, extracción de medidas e integración de medidas; además de prestar especial atención en las propiedades de las imágenes.

Bibliografía

• Beauchemin, S. S. & Barron, J. L.,The computation of optical flow, ACM Comput. Surv., ACM, 1995, 27, 433-466.

Flujo Óptico en Robots Móviles (4)

Proceso jerárquico para el cálculo del flujo óptico.

En el calculo del flujo óptico se han tenido problemas en la medición de movimientos largos en las secuencias de imágenes analizadas, para esto se ha optado por analizar el flujo óptico de una forma jerárquica, esto es analizando las imágenes en diferentes escalas de resolución, utilizando pirámides Laplacianas o Gaussianas \cite{Barron1995}; donde estas técnicas permiten cumplir la restricción de movimientos largos en las imágenes, además de incrementar la eficiencia computacional del flujo óptico. Como ejemplo tenemos la siguiente secuencias de imágenes donde se obtiene el flujo óptico en diferentes resoluciones usando una pirámide Gaussiana.




Donde la imagen obtenida a partir de la imagen original se obtiene un flujo óptico muy disperso como lo vemos a continuación.



Mientras que usando la pirámide Gaussiana en el nivel de resolución más bajo se obtiene el siguiente flujo óptico el cual esta mas definido.

Bibliografía

• Beauchemin, S. S. & Barron, J. L.,The computation of optical flow, ACM Comput. Surv., ACM, 1995, 27, 433-466.

Flujo Óptico en Robots Móviles (3)

Cálculo del flujo óptico.

Para el cálculo del flujo óptico existen diversos métodos los donde cada uno de ellos asume ciertas restricciones para obtener el flujo óptico. Debido a que el estudio del movimiento para el cálculo del flujo óptico puede ser visto desde diferentes puntos de vista, como lo son la velocidad, disparidad e intensidad; aunque el análisis de cada uno de estos sus meritos y fallos(Barron1995). Debido a la hipótesis fundamental en el movimiento de las imágenes, es la en las los objetos en las imágenes con intensidades de brillo en variaciones de tiempo permanecen constante por un periodo corto de tiempo t (Horn1981); donde la función de intensidad de la imagen en el punto x con coordenadas (x,y) en el tiempo t esta dada por:

I(x,t)≈(x +δx,t + δt)

Donde δx es el desplazamiento de una región local de la imagen dada por (x,t) después del tiempo δt. Donde al aplicar series de Taylor obtenemos:

I(x,t)= I(x,t) + I•δx + δtIt + O^2

Donde I=(Ix,Iy) es el gradiente de los niveles de intensidad de la imagen y donde It es la derivada parcial de primer orden de la función de intensidad I(x,t), y O^2 son los términos de segundo orden o mayores que son insignificantes para el calculo del flujo óptico; simplificando la ecuación obtenemos:

I•v + It=0

Donde v = (u,v) es la velocidad de la imagen; y en donde la ecuación anterior es conocida como la ecuación restringida del flujo óptico (Barron1995); esta ecuación es la que satisface la hipótesis fundamental mencionada anteriormente. Aunque esta ecuación no es suficiente para poder determinar el flujo óptico debido a que las componentes en las componentes de la velocidad son desconocidas y solo se puede obtener la velocidad ortogonal que es la dirección del gradiente de los niveles de intensidad de gris, esto debido al problema de apertura (Black1991). Siendo que solo se puede estimar el flujo óptico de forma eficiente con este método cuando en la imagen hay suficiente intensidad en las en la imagen se presentan curvaturas Gaussianas. Por lo tanto es necesario agregar ciertas condiciones para poder determinar el movimiento en una secuencia de imágenes, según Beauchemin y Barron (Barron1995) estas condiciones son:

1. Iluminación uniforme.
2. Superficie de reflexión Lamberciana (de Lambert).
3. Traslación paralela pura en el plano de la imagen.

Donde el a medida que se satisfagan las condiciones con un mayor grado de exactitud se obtendrá el movimiento de flujo óptico en la imagen.




Bibliografia:

• Black, M. J.Robust Incremental Optical Flow, Yale University, 1992 .
  
• Beauchemin, S. S. & Barron, J. L.,The computation of optical flow, ACM Comput. Surv., ACM, 1995, 27, 433-466.
• Horn, B. K. & Schunck, B. G.Determining Optical Flow, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Massachusetts Institute of Technology, 1980.
  
  
  
• 
  

Navegación en Robots Móviles (1)

Navegación de macro a micro escala.

Debido a que la navegación en robots móviles ocupa un amplio espectro en lo referente a sistemas, requerimientos y soluciones Dixon y Henlich (1997) lo han estructurado en base a su escala de navegación; partiendo de escalas físicas los podemos clasificar en:

• Navegación global: esta es usada para determinar la posición de mapas absolutos o referenciados y moverlos a un punto determinado, como ejemplo tenemos a los aviones jumbo a reacción y transatlánticos que operan con una navegación de piloto automático, entre otros.

• Navegación local: esta navegación se basan en la habilidad de determinar la posición relativa de los objetos tanto estáticos como dinámicos e interactuar con ellos.

• Navegación Personal: estos involucran robots de pequeños centímetros que requieren una alta precisión de navegación, sobre un rango pequeño.

Referencias de navegación.

Caminando junto a las escalas de navegación la fijación de la posición puede ser absoluta o relativa.

La determinación de la posición en forma absoluta implica encontrar la posición relativa a un origen absoluto, esto implica la determinación de un punto estacionario en común a todas las posiciones fijas entre el rango de navegación. Por otro lado la determinación de de la posición en forma relativa, implica encontrar un punto relativo a la posición del robot. Actualmente los sistemas de navegación se han dividido en dos vertientes los que utilizan Sistemas de Posicionamiento Global (Global Positioning Systems GPS) y los que utilizan Sistemas de Posicionamiento basados en la Visión de imágenes.

Sistemas d Posicionamiento Global (GPS).

El Sistema de Posicionamiento Global consta de tres segmentos:

• Segmento de espacio: este consta de 24 satélites en orbita alrededor del planeta, que permiten determinar la posición instantánea de un usuario en cualquier momento. Para determinar la posición de un usuario se necesitan cuatro satélites que determinan su posición en las dimensiones x, y, z y el tiempo en el que están recibiendo esa información.

• Segmento de tierra: que es el que monitorea y controla las posiciones de los satélites para asegurarse del correcto funcionamiento del sistema.

• Segmento de usuario: este es el usuario móvil que utiliza un equipo de recepción GPS.
El uso del GPS provee una exactitud de 100m a los usuarios del Servicio de Posición Estándar (Standar Positioning Service SPS) debido a los errores de disponibilidad selectiva que fueron introducidos intencionalmente por la milicia de E.U. Debido a que no es posible obtener una exactitud para la navegación de robots móviles, el uso de técnicas diferenciales para el uso del GPS se vuelve un método viable para obtener una referencia global de navegación.

Figura1. Segementos GPS.

En cuanto a los sistemas de posicionamiento para robots móviles se deben de tomar en cuenta varias consideraciones como el tamaño del transceptor móvil, los requerimientos de poder del transceptor, exactitud del posicionamiento, costo de las unidades móviles, costo de la implementación total, la habilidad de procesar información GPS diferencial, inclusión de la integración de comunicación de datos, tiempo de fijación de la primera posición, actualizar el rango con movimiento, estandarización/disponibilidad del equipo, portabilidad/tiempo de configuración, entre otras restricciones que permitan al sistema de navegación del robot móvil poder determinar su posición en forma eficiente.


Referencias:

• Jonathan Dixon, Oliver Henlich Mobile Robot Navigation, Issues in Practical Implementation Imperial College, London, information systems engineering year 2: Surprise 1997

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.