Sensor de Flujo Óptico - Tesis de Grado

Universidad de Buenos Aires Facultad De Ingeniería

Sensor de Flujo Óptico Javier E. Luiso

Director: Dr. Ing. Juan Ignacio Giribet

Abril 2016

Índice general 1. Objetivo

1

2. Flujo Óptico

3

3. Estado del arte 3.1. Técnica para el cálculo del flujo óptico . . . . . . . . . . 3.2. Trabajos y enfoques analizados . . . . . . . . . . . . . . 3.2.1. Control Grid Motion Estimation . . . . . . . . . . 3.2.2. Optical Flow from 1D Correlation . . . . . . . . . 3.2.3. Trabajo de Horn y Schunck: “Determining Optical 3.2.4. Conclusión . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . Flow” . . . .

. . . . . .

. . . . . .

4 4 6 6 8 10 11

4. Enfoque elegido 4.1. Condiciones de restricción . . . . . . . . . . 4.1.1. Estimación de las derivadas parciales 4.1.2. Estimación de los laplacianos . . . . 4.2. Función de minimización . . . . . . . . . . . 4.3. Solución iterativa . . . . . . . . . . . . . . . 4.3.1. Condiciones Iniciales y de contorno .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

12 12 12 14 15 16 16

5. Software 5.1. Uso del sensor . . . . . . . . . . . . . . . . . 5.1.1. Uso de la API . . . . . . . . . . . . . 5.2. Implementación del Algoritmo de cálculo del 5.2.1. Intel extensiones streaming SIMD . . 5.2.2. Separación del canal de luminancia . 5.2.3. Estimación de las derivadas parciales 5.2.4. Estimación del Laplaciano . . . . . . 5.2.5. Estimación del Flujo Óptico . . . . .

. . . . . . . . . . . . . . . . Flujo Óptico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

17 17 17 19 19 19 22 24 27

i

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

6. Sensor de Imagen 6.1. Características generales . . . . . . . . . . . . . 6.2. Determinación de las capacidades de la webcam 6.3. Configuración de la webcam . . . . . . . . . . . 6.4. Medición del FPS . . . . . . . . . . . . . . . . . 6.5. Distribución de la Luminancia . . . . . . . . . . 7. Software 7.1. API para el uso del sensor . . . . . 7.2. Modo de funcionamiento del sensor 7.2.1. Transmisión por UDP . . . 7.2.2. Protocolo de transmisión . . 7.2.3. Aplicación remota de prueba 8. Ensayos y Mediciones 8.1. Tiempos del algoritmo . . . 8.1.1. Método de medición 8.2. Descripción de la prueba . . 8.2.1. Desarrollo del ensayo 8.2.2. Resultados . . . . . . 8.3. Video . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . .

. . . . . .

. . . . .

. . . . .

. . . . . .

. . . . .

. . . . .

. . . . . .

. . . . .

. . . . .

. . . . . .

. . . . .

. . . . .

. . . . . .

. . . . .

. . . . .

. . . . . .

. . . . .

. . . . .

. . . . . .

. . . . .

. . . . .

. . . . . .

. . . . .

. . . . .

. . . . . .

. . . . .

. . . . .

. . . . . .

. . . . .

28 28 29 30 31 34

. . . . .

41 41 41 41 44 45

. . . . . .

46 46 47 47 47 49 58

9. Conclusiones y pasos futuros 59 9.1. Próximos Pasos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

ii

Índice de figuras 3.1. Control Grid y su correspondiente mapeo a una grilla regular. . . . 8 3.2. La combinación de dos correlaciones ortogonales de longitud L, permite estimar el valor del flujo óptico en todo el parche 2D . . . . . 10 4.1. 4.2. 4.3. 4.4.

Estimación de la derivada parcial en x . . . . Estimación de la derivada parcial en y . . . . Estimación de la derivada parcial en t . . . . . El laplaciano es estimado sustrayendo el valor minado (i, j) de un promedio ponderado de los

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . en un punto detervalores vecinos . .

. 13 . 13 . 14 . 15

5.1. Diagrama de secuencia general del algoritmo . . . . . . . . . . . . . 5.2. Organización de la información en el formato YUV422. En este formato un frame 160x120 px requiere un buffer de 38.4 Kbytes. . . . 5.3. Canales de luminancia y crominancia separados. El buffer de luminancia es de 19.2 Kbytes. Los canales de crominancia se descartan porque la estimación del Flujo Óptico se hace con la información de luminancia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4. Se cargan 8 pixels en un registro SSE . . . . . . . . . . . . . . . . . 5.5. Se eliminan los bytes con información de crominancia y se obtiene la luminancia de 8 pixels en formate 8bits . . . . . . . . . . . . . . 5.6. Se expanden los 8 valores de luminancia a 16 bits y se almacenan de a 4 valores en sendos registros SSE . . . . . . . . . . . . . . . . . 5.7. Luego se expanden a un formato de 32 bits. La información contenida en los dos registros SSE se guarda en un buffer, que contendrá la información de luminancia en formato de punto flotante de 4 bytes 5.8. Misma área de 4x2 pixels de dos frames consecutivos en el tiempo Para el pixel correspondiente a IC tenemos que Ix = 41 {(ID − IC )k + (IS − IR )k + (ID − IC )k−1 + (IS − IR )k−1 } . . . . . . . . . . . . . .

iii

18 20

21 21 21 22

22

23

5.9. En dos registros SSE se cargan 4 pixels consecutivos, desplazados en 1 columna, de modo que al restar los registros se realiza simultáneamente el cálculo de la primer resta de la expresión IX para estos 4 pixels. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.10. Los 4 registros SSE que contiene las 4 restas se suman en entre sí y luego se divide por el factor 14 obteniendo así de manera simultánea las estimación de IX para 4 pixels. . . . . . . . . . . . . . . . . . . 5.11. El laplaciano es estimado sustrayendo el valor en un punto determinado (i, j) de un promedio ponderado de los valores vecinos . . 5.12. Según eq ?? el valor del laplaciano para los pixels K,L,M,N es: 1 uK = 61 {B + L + S + J} + 12 {A + C + R + T } uL = 16 {C + M + T + 1 1 {C +E +T +V } K}+ 12 {B +D+S +U } uM = 61 {D+N +U +L}+ 12 1 1 uN = 6 {E + O + V + M } + 12 {D + F + U + W } . . . . . . . . . 5.13. En primer lugar se resuelve la suma que es escalada por el factor de 1 y el resultado se guarda en un registro SSE. . . . . . . . . . . . 6 5.14. En primer lugar se resuelve la suma que es escalada por el factor de 1 y el resultado se guarda en un registro SSE. . . . . . . . . . . . 12 5.15. Teniendo los factores escalados se realiza la suma para así calcular de manera paralela el valor del laplaciano para 4 pixels. . . . . . . 6.1. 6.2. 6.3. 6.4. 6.5. 6.6. 6.7.

Comparativa de la cantidad de fps obtenidos . . . . Distribución de la Luminancia para texp = 0,8msec Distribución de la Luminancia para texp = 1,6msec Distribución de la Luminancia para texp = 6,4msec Distribución de la Luminancia para texp = 12,8msec Comparativa de la distribución de la Luminancia . Comparativa de la distribucion de la Luminancia .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. 23

. 23 . 24

. 25 . 25 . 26 . 26 . . . . . . .

33 35 36 37 38 39 40

7.1. Espacio de colores RGB para un valor de Y = 0,5 . . . . . . . . . . 45 8.1. 8.2. 8.3. 8.4. 8.5. 8.6.

Montaje del sensor de imagen y la placa Intel Edison en el cuadcóptero. Escenario de prueba: Piso uniforme con marcas . . . . . . . . . . . Detección con nivel de iteración k = 1 . . . . . . . . . . . . . . . . . Detección con nivel de iteración k = 3 . . . . . . . . . . . . . . . . . Detección con nivel de iteración k = 5 . . . . . . . . . . . . . . . . . Cuadro 1 de la secuencia de movimiento A, el desplazamiento es hacia la izquierda, el flujo óptico resultante es 8.9. . . . . . . . . . . 8.7. Cuadro 2 de la secuencia de movimiento A, la marcha se detiene y hay cierta rotación antes de iniciar el desplazamiento en sentido contrario, el flujo óptico resultante es 8.10. . . . . . . . . . . . . . .

iv

48 48 49 50 50 51

52

8.8. Cuadro 3 de la secuencia de movimiento A, el desplazamiento es hacia la dereceha, el flujo óptico resultante es 8.11. . . . . . . . . 8.9. Primera Secuencia, cuadro 1: Avance hacia la izquierda. Ver esquema 8.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.10. Primera Secuencia, cuadro 2: Detención y cierta rotación. Ver esquema 8.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.11. Primera Secuencia, cuadro 3: Avance hacia la derecha. Ver esquema 8.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.12. Cuadro 1 de la secuencia de movimiento B, el desplazamiento es hacia abajo en diagonal, acercándose a una de las líneas, el flujo óptico resultante es 8.15. . . . . . . . . . . . . . . . . . . . . . . . 8.13. Cuadro 2 de la secuencia de movimiento B, el desplazamiento es paralelo a una de las líneas, el flujo óptico resultante es 8.16. . . . 8.14. Cuadro 3 de la secuencia de movimiento B, el desplazamiento es alejándose de la línea, el flujo óptico resultante es 8.17. . . . . . . 8.15. Cuadro 1 de la secuencia de movimiento B: el desplazamiento es hacia abajo en diagonal, acercándose a una de las líneas, ver esquema 8.12. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.16. Cuadro 2 de la secuencia de movimiento B: el desplazamiento es paralelo a una de las líneas, ver esquema 8.13. . . . . . . . . . . . 8.17. Cuadro 3 de la secuencia de movimiento B: el desplazamiento es hacia arriba en diagonal, alejándose de una de las líneas, ver esquema 8.14. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1. Porcentaje de carga del procesador para distintos niveles de iteración del algoritmo trabajando a 25 FPS. No se incluye la carga de la transmisión por UDP . . . . . . . . . . . . . . . . . . . . . . . 9.2. Porcentaje de carga del procesador para distintos niveles de iteración del algoritmo trabajando a 20 FPS. No se incluye la carga de la transmisión por UDP . . . . . . . . . . . . . . . . . . . . . . . 9.3. Porcentaje de carga del procesador para distintos niveles de iteración del algoritmo trabajando a 10 FPS. No se incluye la carga de la transmisión por UDP . . . . . . . . . . . . . . . . . . . . . . . 9.4. Captura de la dirección del flujo óptico durante un vuelo con el ambiente con baja iluminación. Al aumentar la sensibilidad, el nivel de ruido de fondo aumenta y esto se puede observar en la imagen.

v

. 52 . 53 . 53 . 54

. 55 . 55 . 56

. 56 . 57

. 57

. 59

. 60

. 60

. 61

1. Objetivo La necesidad que dió origen al trabajo que de esta tesis surgió dentro de la linea de investigación que viene desarrollando el Grupo de Procesamiento de Señales, Identificación y Control (GPSIC), en el área del estudio de sistemas de navegación en aplicaciones aeroespaciales. En ese marco, se planteó el interés de disponer de un sensor de flujo óptico, al cual pudiese integrarse a los vehículos multi-rotores sobre los que el grupo ha venido trabajando. En el campo de los UAVs, los sensores de flujo óptico encuentran su aplicación principalmente en los sistemas de control y navegación, trabajando en coordinación con los clásicos sensores inerciales (IMUs). Además pueden aplicarse para resolver temas relacionados con tracking de objetos, detectar objetos o superficies en curso de colisión, etc. En lo particular a las tareas que se estaban llevando a cabo dentro del grupo de investigación, el sensor de flujo óptico debía cumplir con algunas condiciones. Las mismas fueron planteadas atendiendo principalmente al hecho que el mismo pudiese integrase fácilmente a los trabajos ya realzados. Entonces se determinó que el sensor a desarrollar necesariamente tenía utilizar la plataforma de desarrollo seleccionada como computadora de vuelo. En esta caso se trata de la plataforma Edison de Intel. Pero no solamente el sensor debía utilizar esta plataforma sino que el uso de dicho hardware iba a ser compartido con los algoritmos de navegación y control. Por lo tanto al algoritmo asociado debía poder correr como un thread independiente y además utilizar un porcentaje del tiempo al procesador. También quedó establecido como condición que el sensor de imagen a utilizar fuera un sensor de bajo costo de fácil adquisición en el mercado local. Más específicamente debía ser una web-cam. Por último el sensor debía ser pensado entonces como un dispositivo cerrado y autónomo, con una interfaz de control y acceso a datos definida, que pueda ser empleado en otros desarrollos. Pensando en que dichos desarrollos sean usuarios del sensor o consumidores de la información que el sensor entregue. Este último concepto estableció la condición que la salida del sensor debía ser específicamente el campo de velocidades en cada punto (pixel) de la imagen vista por el sensor. 1

Capítulo 1. Objetivo

Esto es importante aclararlo, porque como se verá más adelante, algunos métodos e incluso soluciones comerciales se enfocan en determinar aspectos cualitativos del flujo óptico los cuales tienen un campo de aplicación. En el caso de este trabajo, la intensión fue que el sensor pudiese caracterizar completamente al flujo óptico como campo vectorial. Dado que a partir de ahí cualquier otra cualidad del campo puede ser determinada. En el presente documento primero se presenta el concepto de flujo óptico y las técnicas empleadas actualmente para el desarrollo de soluciones que permitan calcular el mismo. Luego se detallará el enfoque elegido para la implementación del sensor y en los capítulos siguientes los distintos aspectos que sobre los que se trabajó. Hacia el final se detallan las mediciones y ensayos realizados y por último las conclusiones y pasos futuros que pueden explorarse.

2

2. Flujo Óptico Así como la imagen vista o capturada por un sensor de imagen, es el resultado de la proyección de una porción del espacio sobre un plano. (el plano es el propio sensor de imagen y el volumen proyectado se define como el volumen de vista); el movimiento en dos dimensiones que se puede observar en alguna región de una secuencia de imágenes será el resultado de la proyección del movimiento tridimensional de objetos, respecto de la posición de un sensor de imagen. También puede ser el resultado del movimiento relativo del sensor respecto de los objetos. Si es posible detectar el desplazamiento que una región presenta entre dos frames consecutivos de una secuencia de imágenes, entonces se puede definir una magnitud que represente la velocidad del movimiento que dicha región está teniendo. Esta velocidad caracteriza al movimiento 2D que se detecta en el plano del sensor, por lo tanto también la velocidad será bidimensional. Esta idea es posible expandirla y pensar en un campo que represente la velocidad que posee cada pixel de la imagen y asi poder determinar si cada punto de la imagen se está moviendo o no, y en caso que se desplace, en que dirección lo está haciendo. Este campo de velocidades es lo que se denomina “Flujo Óptico” de la imagen o también “ campo de velocidades” de la imagen. [1], [2] El flujo óptico constituye entonces un estimador del movimiento 2D presente en la imagen. Bajo ciertas condiciones puede utilizarse para reconstruir el movimiento del sensor de imagen. También puede ser empleado para realizar detección de movimiento, segmentación de objetos, determinar cursos de colisión hacia objetos. También es de utilidad en UAVs o robots, en especial en los algoritmos de navegación y para evitar colisiones, [3].

3

3. Estado del arte 3.1.

Técnica para el cálculo del flujo óptico

Después de más de 30 años, la mayoría de los métodos para la estimación del flujo óptico que han surgido siguen fuertemente basados en lo formulado por Horn y Shunck en 1981,[2]. Estos métodos se pueden agrupar de acuerdo a la técnica que utilizan para la estimación.[4] Técnica diferencial: se basa en la estimación de la velocidad de la imagen a partir de las derivada espacio-temporales de la intensidad de una imagen o de una versión previamente filtrada de la misma, generalmente utilizando un filtro pasa-bajo o pasa-banda. Encontramos soluciones que utilizan derivadas de primer orden, generalmente basadas en una traslación de la imagen que cumpla con: I(x, t) = I(x − vt, 0)

(3.1)

donde x = (x, y) y v = (u, v)T . Como se vió en la sección anterior, el asumir que la intensidad se mantiene constante nos lleva a la expresión a partir de la cual la velocidad puede determinarse conociendo las derivadas espacio-temporales de la intensidad: ∇I(x, t)v + It (x, t) = 0

(3.2)

donde It (x, t) es la derivada temporal de la intensidad. Se requiere una restricción adicional sobre la Intensidad para que sea posible determinar las dos componentes de la velocidad v = (u, v)T . Los distintos métodos basados en esta técnica en general se diferencian por la restricción adicional que adoptan. También encontramos trabajos que usan derivadas de segundo orden que trabajan imponiendo la condición que d∇I(x, t) =0 dt

(3.3) 4

Capítulo 3. Estado del arte

esto lleva a la expresión "

Ixx (x, t) Ixy (x, t) Iyx (x, t) Iyy (x, t)

#

u v

!

+

Itx (x, t) Ity (x, t)

!

=

0 0

!

(3.4)

Encontramos métodos que combinan las restricciones 3.1 y 3.4. Los trabajos de Horn y Shunck [2], Lucas y Kanade [5], Simoncelli et al [6] y Nagel [7] están basados en esta técnica. Técnica basada en la coincidencia de regiones: esta técnica define la velocidad de la imagen como el desplazamiento d = (dx , dy ) que realiza una determina región de la imagen en un ∆t. Definida una métrica para la similitud de regiones dentro de una imagen, se busca determinar el desplazamiento d asociado al máximo de similitud encontrado. En general se utiliza la función de correlación cruzada como una medida de la similitud entre regiones. Aunque también se puede buscar la distancia que minimiza una función de diferencia de cuadrados entre la región de interés y las posibles regiones dentro del frame: SSD1,2 (x, d) = Σnj=−n Σni=−n W (i, j) [I1 (x + (i, j)) − I2 (x + d + (i, j))]2 = W (i, j) ∗ [I1 (x) − I2 (x + d)] (3.5) donde W (i, j) representa una ventana discreta. El trabajo de Anandan [8], Ancona et al [9] utilizan esta técnica. Técnica basada en frecuencia: Esta técnica se basa en el uso de filtros sintonizados en el espacio de la frecuencia espacial. Dependiendo del método se puede priorizar el análisis en al energía del espectro o en su fase. La condición establecida en 3.1 tiene su correspondiente en el dominio de las frecuencias, mediante la transformada de Fourier: ˆ ω) = Iˆ0 (k)δ(ω + vT k) I(k,

(3.6)

ˆ es la transformada de Fourier de I(x, 0), δ(k) es la función delta donde I0 (K) de Dirac, ω representa la frecuencia en el tiempo y k = (kx , ky ) representa la frecuencia espacial. Determinadas características de las imágenes son más evidentes en el dominio de las frecuencias. Heeger [10], expone en su trabajo como se mapea en el espacio de las frecuencias el desplazamiento de un patrón dentro de una imagen: el espectro de una traslación 2D de un patrón ocupa un plano inclinado en el dominio de la frecuencia. Para obtener el flujo óptico la idea de esta 5

Capítulo 3. Estado del arte

técnica es encontrar el plano donde esta concentrada la energía del espectro y apartir de allí determinar los parámetros que caracterizan al desplazamiento asociado a dicho espectro.

3.2.

Trabajos y enfoques analizados

En esta sección se exponen los trabajos más relevantes que fueron analizados como trabajo de investigación previo a la elección del enfoque a implementar en el sensor. Quedan fuera de este análisis aquellas las soluciones desarrolladas a partir de la técnica basada en frecuencia, por el hecho que dichas soluciones requieren trabajar en el dominio de la frecuencia y por lo tanto han de requerir el cómputo de la Transformada de Fourier Discreta. La plataforma Edison no es un DSP y por lo tanto es posible anticipar que una solución que requiera del cómputo de una DFT ha de significar una carga importante al procesador. Habiendo otra soluciones basadas en las otras técnicas mencionadas anteriormente, que representan una carga de cómputo menor, se decide analizar la viabilidad de una solución en la técnica diferencial o en la coincidencia de regiones. Se analiza en primer lugar una solución basada en la técnica diferncial, que incorpora la técnica de Control Grid Interpolation.A continuación se analiza una solución basada en la técnica de coincidencia de regiones. Por último se detalla una solución basada en la técnica diferencial planteada en el trabajo original de Horn y Schunck, [2].

3.2.1.

Control Grid Motion Estimation

El principal aporte de este trabajo es el uso de la técnica de Control Grid Interpolation (CGI) al cálculo del flujo óptico, la cual aplica a una desarrollo basado en la técnica diferencial. [11]. Estimación del flujo óptico Este trabajo al igual que la solución de de Horn y Schunck, parte de asumir que la intensidad del punto se mantiene constante frente a un pequeño desplazamiento espacial y temporal: I(x, y, t) = I(x + α, y + β, t + δt)

(3.7)

trabajando con la ecuación anterior se tiene que: ∂I(x, y, t) ∂I(x, y, t) ∂I(x, y, t) +β + δt I(x, y, t) ≈ I(x, y, t) + α ∂x ∂y ∂t 6

Capítulo 3. Estado del arte

Utilizando el desarrollo de Taylor de primer orden para estimar las derivadas parciales, y siendo Ix , Iy , It las aproximación de las derivadas, el error cuadrático se puede expresar como: E(α, β) = (αIx (x, y, t) + βIy (x, y, t) + δtIt (x, y, t))2

(3.8)

Cuando estamos trabajando con frames de una secuencia de video, se toma como paso incremental del tiempo δt = 1. La solución es encontrar el desplazamiento D = (α, β) que minimiza la ecuación 3.8. Aquí también se requiere una segunda condición para poder determinar ambas componentes del flujo óptico. Se plantea el uso de la técnica CGI, para asegurar que la condición de suavidad en el flujo se cumple localmente y luego se sostiene globalmente como propiedad del método CGI. Control Grid Interpolation Se define como “Control Grid” o grilla de control a un conjunto de puntos que forman una grilla o malla de cuadriláteros contiguos, cuyos vértices son mapeados con los vértices de una grilla regular de rectángulos contiguos, ver figura 3.1. “Control Grid Interpolation” describe el proceso mediante el cual puntos que se encuentran dentro de los elementos de la grilla de control son mapeados a la superficie que contiene la grilla regular. Esta técnica se aplica para realizar transformaciones espaciales sobre una imagen. En primer lugar se especifican algunos puntos sobre la imagen que constituyen los puntos de la grilla de control. Se efectúa la transformación únicamente sobre esos puntos de control y luego mediante un proceso de interpolación se estima la transformación para todos los puntos interiores a cada elemento de la grilla. Esta técnica aplicada a la estimación del flujo óptico implica definir una grilla de control sobre una imagen y efectuar el cálculo del flujo óptico únicamente en esos puntos. Una vez que se obtiene el flujo óptico de los puntos de control, se interpola el valor para todos los puntos intermedios. Ventajas y desventajas La aplicación de esta técnica permite realizar una estimación grosera del flujo óptico sobre todo el frame, que en principio podría ser de resoluciones altas. Luego es posible pensar en un proceso de refinamiento en las zonas de interés y para ello repetir el proceso con una grilla de puntos más próximos. Lo que a prior parece ser más simple y económico (evitar un cálculo complejo en cada pixel de la imagen y simplemente estimar usando técnicas de interpolación), termina requiriendo un proceso que puede ser complejo para determinar la resolución inicial de la grilla de control que resulte más apropiado. Luego debe 7

Capítulo 3. Estado del arte

Figura 3.1: Control Grid y su correspondiente mapeo a una grilla regular. determinarse sobre cuáles áreas de interés se ha de realizar el refinamiento. Este proceso parece ser más apropiado para una aplicación que requiera la interacción de un usuario, que le permita definir áreas de interés y entonces refinar el cálculo del flujo óptico en esas zonas.

3.2.2.

Optical Flow from 1D Correlation

En el trabajo presentado por Ancona y Poggio [9], se presenta una solución basada en la técnica de la similitud de regiones. El criterio que se emplea para poder medir la similitud es utilizar la correlación 2D entre la región de interés y todas las posibles regiones desplazadas. Esta solución plantea descomponer el cálculo de la correlación 2D de la zona de interés en un procedimiento donde se calcula dos veces una correlación 1D y luego se interpolan los resultados, ver Fig. 3.2. Este trabajo tiene como aplicación directa el desarrollo de un detector de colisión, o mejor dicho detectar la condición de una colisión próxima a ocurrir, para ser evitada, [12]. En ese trabajo se busca determinar el flujo óptico desde un aspecto cualitativo y no tiene como objetivo conocer el valor del campo de velocidades en cada punto de la imagen. En lugar de ello se busca extraer las cualidades de expansión y rotación del campo, [13]. En particular, es la característica de expansión la que se aprovecha para la realización del detector de colisiones, [9]. Los autores en ambos trabajos enfocan el problema de la estimación del flujo óptico partiendo de la idea de disponer de detectores de las cualidades del flujo óptico (rotación, traslación y expansión) y no en la determinación del campo en cada punto de la imagen. Teniendo en cuenta los requerimientos que se fijaron para esta tesis, el enfoque de los trabajos de Ancona y Poggio, es limitante, en el sentido que la solución que ellos proponen permite determinar de manera cualitativa el flujo óptico. Permite 8

Capítulo 3. Estado del arte

determinar si el flujo presenta determinadas características o no. Es objetivo de esta Tesis poder determinar en cada pixel de la imagen que obtenemos del sensor de imagen, el valor del campo de velocidades. Porque a partir de esa información es posible realizar un procesamiento a fin de evaluar las características del flujo óptico. Los detectores de traslación, rotación, expansión del flujo óptico se pueden implementar por software. Determinando la similitud de las regiones - Uso de la correlación La idea básica detrás de esta técnica es determinar para cada punto de interés dentro de la imagen, el desplazamiento d = (δx, δy) que maximiza la correlación entre dos regiones 2D centradas en alrededor de los puntos de interés entre dos frames sucesivos. La función correlación entre la imagen en el tiempo t y el tiempo t + δt se define como: w

Φ(δx , δy ; t) = I ⊗ I =

Z

I w (ξ, η; t)I(δx + ξ, δy + η; t + δt)dξdη

donde I w (ξ, η; t) es la función intensidad en el frame asociado al tiempo t, ⊗ es el producto de Kronecker. Se adopta I(x, y) = 0 en cualquier punto fuera de la zona de interés. Sea D(δx , δy ) la distancia L2 , entre dos regiones de interés en dos frames sucesivos en la posición (x, y). D(δx , δy ) es función del vector desplazamiento (δx , δy ). El método propone encontrar s∗ = (δx∗ , δy∗ ) tal que minimize D, o lo que es lo mismo: maximice la función de correlación Φ(δx , δy ; t). s∗ Luego define la estimación del flujo óptico como u∗ = ∆t A partir de lo anterior se procede a minimizar la función Φ(δx , δy ; t) pero en dos direcciones ortogonales, es decir: Φ(δx , 0; t) Φ(0, δy ; t) Los resultados del cálculo de la correlación 1D en ambos ejes, puede luego combinarse para estimar la correlación de todo el parche 2D. Ver figura 3.2. Consideraciones finales Como se mencionó anteriormente, este trabajo se enfoca en poder determinar los aspectos cualitativos del flujo óptico. En este marco utilizar la correlación 2D para estimar el flujo en algunos puntos es una solución viable. Sin embargo utilizar el método de la correlación para estimar el flujo óptico en todos los pixels del campo de visión del sensor genera una cantidad de cálculo que excede al que emplearía una técnica diferencial. 9

Capítulo 3. Estado del arte

Figura 3.2: La combinación de dos correlaciones ortogonales de longitud L, permite estimar el valor del flujo óptico en todo el parche 2D

3.2.3.

Trabajo de Horn y Schunck: “Determining Optical Flow”

En su trabajo de 1981, [2], Horn y Schunck hacen un aporte importante al dar un paso hacia un planteo más sistemático del problema de calcular el flujo óptico, cuando se compara con las soluciones “ad-hoc”‘que hasta ese momento se habían planteado, [14]. Su trabajo aplica la técnica diferencial y por lo tanto parte de la restricción 3.2: ∇I(x, t)v + It (x, t) = 0 siendo x = (x, y), v = (u, v)T y It (x, t) la derivada temporal. La restricción adicional que Horn y Schunck plantean sobre el campo Intensidad es que el mismo varíe suavemente. Dicha restricción queda expresada como: ∇2 u + ∇2 v =

∂ 2u ∂ 2u ∂ 2v ∂ 2v + + + =0 ∂x2 ∂y 2 ∂x2 ∂y 2

(3.9)

Combinando ambas restricciones plantean la función de minimización: Z n D



(∇I(x, t)v + It )2 + λ2 ||∇u||22 + ||∇v||22

o

dx

(3.10)

La función de minimización está definida para una región D, donde λ representa la influencia o factor de peso del término asociado a la restricción de la suavidad de la Intensidad. La solución iterativa al problema de minimización de la función definida en 3.10 es: h

uk+1 = uk −

i

Ix Ix uk + Iv v k + It α2 + Ix2 + Iy2

(3.11) 10

Capítulo 3. Estado del arte

h

v k+1 = v k −

i

Iy Ix uk + Iv v k + It α2 + Ix2 + Iy2

(3.12)

Tanto la estimación de las derivadas parciales espacio-temporales y la solución iterativa se presta para una implementación paralela y esto permitiría aprovechar las capacidades de cómputo SIMD presente en la plataforma Intel Edison. Por otro lado, en este enfoque se estima el flujo óptico para cada punto (pixel) de cada frame del sensor de imagen.

3.2.4.

Conclusión

En el trabajo de D. Sun, S. Roth y M. J. Black, [15] se hace un detallado análisis de la evolución de los métodos basados en la técnica diferencial y cuales son la razones que han permitido una mejora notable en el análisis y determinación del flujo óptico. Ellos exponen que en sí la formulación ha cambiado muy poco desde el trabajo de Horn y Shunck. de hecho afirman que esa “clásica” formulación, 3.2 y 3.9, se comporta sorprendentemente bien y el mejora radica en combinarla con técnicas modernas de optimización e implementación. A partir de este trabajo y en base a las ventajas y desventajas de cada uno de las técnicas y soluciones que se analizaron, se decide adoptar como solución a implementar el trabajo de Horn y Schunck. Y sobre su formulación trabajar en una optimización de cómputo aprovechando las funcionalidades de procesamiento paralelo disponibles en la plataforma Intel Edison. Los detalles de la implementación sobre dicha plataforma se detallan en la sección siguiente.

11

4. Enfoque elegido De los trabajos analizados se seleccionó el enfoque abordado por Horn y Schunck, [2]. Su enfoque enuncia que el Flujo Óptico no puede ser calculado localmente, dado que en una punto (x, y) de la imagen solamente se dispone de un dato independiente, mientras que el flujo es una magnitud de dos componentes. Entonces se requiere una segunda restricción y ellos proponen asumir que la velocidad aparente del patrón del brillo varia suavemente prácticamente en toda la imagen.

4.1.

Condiciones de restricción

El enfoque seleccionado se basa en las restricciones que fueron planteadas por Horn y Shucnk: ∇I(x, t)v + It (x, t) = 0 (4.1) ∇2 u + ∇2 v =

4.1.1.

∂ 2u ∂ 2u ∂ 2v ∂ 2v + + + =0 ∂x2 ∂y 2 ∂x2 ∂y 2

(4.2)

Estimación de las derivadas parciales

Para aplicar las restricciones es necesario poder estimar, a partir de la infor∂I ∂I mación obtenida en las imágenes, las derivas parciales del brillo ∂x , ∂y y ∂I , como ∂t también el valor de los laplacianos. Para la estimación de las derivadas parciales se utiliza un kernel de 2x2x2 pixels. Es decir que estamos considerando las dimensiones (i, j, k) donde i, j representan la posición del pixel en el frame y el k representa la coordenada discreta del tiempo, donde se ordenan los sucesivos frames. La estimación de la derivada parcial en x se realiza conforme lo que indica la ecuación 5.2.3 y la figra 4.1. 12

Capítulo 4. Enfoque elegido

frame k-1

i j

frame k

i j

Figura 4.1: Estimación de la derivada parcial en x

frame k-1

i j

frame k

i j

Figura 4.2: Estimación de la derivada parcial en y

1 Ix = {(Ii,j+1,k − Ii,j,k ) + (Ii+1,j+1,k − Ii+1,j,k )+ 4 (Ii,j+1,k−1 − Ii,j,k−1 ) + (Ii+1,j+1,k−1 − Ii+1,j,k−1 )}

(4.3)

La estimación de la derivada parcial en y se realiza conforme lo que indica la ecuación 4.1.1 y la figra 4.2. 1 Iy = {(Ii+1,j,k − Ii,j,k ) + (Ii+1,j+1,k − Ii,j+1,k )+ 4 (Ii+1,j,k−1 − Ii,j,k−1 ) + (Ii+1,j+1,k−1 − Ii,j,k−1 )}

(4.4)

La estimación de la derivada parcial en y se realiza conforme lo que indica la ecuación 4.1.1 y la figra 4.2. 1 Iy = {(Ii+1,j,k − Ii,j,k ) + (Ii+1,j+1,k − Ii,j+1,k )+ 4 13

Capítulo 4. Enfoque elegido

frame k-1

i j

frame k

i j

Figura 4.3: Estimación de la derivada parcial en t

4.1.2.

(Ii+1,j,k−1 − Ii,j,k−1 ) + (Ii+1,j+1,k−1 − Ii,j,k−1 )}

(4.5)

1 It = {(Ii,j,k−1 − Ii,j,k ) + (Ii+1,j,k−1 − Ii+1,j,k )+ 4 (Ii,j+1,k−1 − Ii,j+1,k ) + (Ii+1,j+1,k−1 − Ii+1,j+1,k )}

(4.6)

Estimación de los laplacianos

Para la estimación del laplaciano se utiliza un kernel de 3x3 pixels, donde los pesos relativos del kernel se muestan en la figura 4.4. La expresión de la estimación es: ∇2 u ≈ K(ui,j,k − ui,j,k )

(4.7)

∇2 v ≈ K(v i,j,k − vi,j,k )

(4.8)

donde u y v se definen como (ver figura 4.4): 1 ui,j,k = {ui−1,j,k + ui,j+1,k + ui+1,j,k + ui,j−1,k }+ 6 1 {ui−1,j−1,k + ui−1,j+1,k + ui+1,j+1,k+ui+1,j−1,k } 12 1 v i,j,k = (vi−1,j,k + vi,j+1,k + vi+1,j,k + vi,j−1,k ) + 6   1 vi−1,j−1,k + vi−1,j+1,k + vi+1,j+1,k+vi+1,j−1,k 12

(4.9)

(4.10)

14

Capítulo 4. Enfoque elegido

1 12

1 6

1 12

1 6

-1

1 6

1 12

1 6

1 12

Figura 4.4: El laplaciano es estimado sustrayendo el valor en un punto determinado (i, j) de un promedio ponderado de los valores vecinos

4.2.

Función de minimización

La función de minimización adoptada es la que plantean en su trabajo Horn y Schunck y que combina ambas restricciones: Z n D



(∇I(x, t)v + It )2 + α2 ||∇u||22 + ||∇v||22

o

dx

(4.11)

donde λ representa la influencia o factor de peso del término asociado a la restricción de la suavidad de la Intensidad. El proceso de minimización implica calcular un valor de (u, v) que haga mínimo el error. A partir de la ecuación 4.11 obtenemos: Ix2 u + Ix Iy v = α2 ∇2 u − Ix It Ix Iy u + Iy2 v = α2 ∇2 v − Iy It Reemplazando los laplacianos por las aproximaciones detalladas anteriormente, 











α2 + Ix2 u + Ix Iy v = α2 u − Ix It 



Ix Iy u + α2 + Iy2 v = α2 v − Iy It

El sistema se puede resolver para las incógnitas u y v, 







α2 + Ix2 + Iy2 u = + α2 + Iy2 u − Ix Iy v − Ix It









α2 + Ix2 + Iy2 v = −Ix Iy u + α2 + Ix2 v − Iy It

(4.12) (4.13)

15

Capítulo 4. Enfoque elegido

4.3.

Solución iterativa

La solución iterativa que se plantea para calcular los valores de (u, v) es la siguiente: 



(4.14)





(4.15)

un+1 = un − Ix [Ix un + Iy v n + It ] / α2 + Ix2 + Iy2 v n+1 = v n − Iy [Ix un + Iy v n + It ] / α2 + Ix2 + Iy2

4.3.1.

Condiciones Iniciales y de contorno

Se requieren dos imágenes para poder calcular un primer par (u, v) dado que la estimación de las derivadas parciales necesita disponer del frame actual y del anterior. Como condiciones de borde se toma las estimaciones de las derivadas Ix = 0, Iy = 0 sobre el borde de la imagen. La solución para la condición de borde en la estimación del laplaciano se explica más adelante cuando se muestre como se resuelven los algoritmos.

16

5. Software En este capítulo se documenta el diseño del software que implementa el algoritmo de estimación del Flujo Óptico, como también el acceso al sensor de imagen y la implementación de la API destinada a ofrecer servicios a una aplicación usuaria.

5.1.

Uso del sensor

La uso del sensor de flujo óptico se realiza a través de los servicios disponibles en la API implementada como punto de contacto con una aplicación usuaria. La documentación completa de la API y todos los módulos que consituyen el software asociado al Sensor se detallan en el Anexo correspondiente. En este capítulo se muestra de modo general cuál es la secuencia de uso de la API y en las secciones subsiguientes los aspectos relevantes de la implementación de los algoritmos que calculan el Flujo Óptico.

5.1.1.

Uso de la API

La API se implementa como un conjunto de funciones que ofrecen servicios para cargar la configuración por defecto con la que trabaja en sensor. inicializar los buffers de memoria y el propio dispositivo (sensor de imagen) a nivel del sistema operativo. la función que implementa todo el proceso de captura y procesamiento de los frames desde el sensor de imagen y el algoritmo que estima el Flujo Óptico. También se implementa la transmisión vía UDP del campo de velocidades estimado. Esta función debe ser ejecutada como un thread independiente. En el diagrama de secuencia de la figura 5.1 se muestra a un nivel general el funcionamiento de la API del sensor de flujo óptico, desde una aplicación de software. El detalle de cada uno de las funciones se describen en el Anexo correspondiente. 17

Capítulo 5. Software

main: API: load_sensor_config()

CameraThread:

init_device() OpticalFlowLoop() init_buffers()

start_Tx()

loop

read_frame()

get_Ix()

get_Iy()

get_It()

calculate_OpFlow()

alt

queue_OpFlow_frame()

[R2Tx]

stop_process_loop() stop_device() stop_Tx()

free_buffers()

close_device()

Figura 5.1: Diagrama de secuencia general del algoritmo

18

Capítulo 5. Software

5.2.

Implementación del Algoritmo de cálculo del Flujo Óptico

A continuación se detallará los aspectos de diseño y el modo en que se implementó la estimación del Flujo Óptico. Uno de los objetivos iniciales de este trabajo fue analizar las capacidades de procesamiento SIMD disponibles en la plataforma Edison de Intel.

5.2.1.

Intel extensiones streaming SIMD

La tecnología SSE (Streaming SIMD Extension) fue introducida por Intel en 1999 para su línea de procesadores Pentium III. SIMD hace referencia a Single Instruction Multiple Data. Esta tecnología permite a las instrucciones la manipulación de múltiples elementos de datos simultáneamente, logrando así un rendimiento superior. Estas instrucciones operan con paquetes de operandos en punto flotante de precisión simple (FP). Hay varios tipos de instrucciones SSE Instrucciones SSE de Transferencia de datos. Instrucciones SSE de Conversión. Instrucciones SSE Aritméticas. Instrucciones SSE Lógicas. Con la tecnología SSE, los microprocesadores x86 fueron dotados de setenta nuevas instrucciones y de ocho registros nuevos: del xmm0 al xmm7. Estos registros tienen una extensión de 128 bits (es decir que pueden almacenar hasta 16 bytes de información cada uno). Las estructuras de datos y algoritmos imvolucrados en el procesamiento de imágenes a menudo son candidatos adecuados para optimizaciones utilizando estos conjuntos de instrucciones. Este es el caso de los algoritmos involucrados en la estimación del Flujo Óptico. En las secciones subsiguientes se detalla como se ha aprovechado la tecnología SSE.

5.2.2.

Separación del canal de luminancia

El formato en que el sensor de imagen entrega los frames capturados es el YUYV o YUV422, en donde la información de luminancia se alterna con las componentes U y V de crominancia. La figura 5.2 muestra la organización de la información. 19

Capítulo 5. Software

Figura 5.2: Organización de la información en el formato YUV422. En este formato un frame 160x120 px requiere un buffer de 38.4 Kbytes. La primera operación necesaria sobre un frame es separar la información de luminancia de los canales de crominancia. Ver figura 5.3. Utilizando los registros SSE se consigue procesar de a 8 pixels en paralelo. El algoritmo primero separa la información de luminancia y luego la convierte a formato de punto flotante en 32 bits. Las figuras 5.4, 5.5, 5.6 y 5.7 muestran el proceso realizado en los registros SSE.

20

Capítulo 5. Software

Figura 5.3: Canales de luminancia y crominancia separados. El buffer de luminancia es de 19.2 Kbytes. Los canales de crominancia se descartan porque la estimación del Flujo Óptico se hace con la información de luminancia.

U0 Y0 V0 Y1 U2 Y2 V2 Y3 U4 Y4 V4 Y5 U6 Y6 V6 Y7 Figura 5.4: Se cargan 8 pixels en un registro SSE

Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 Figura 5.5: Se eliminan los bytes con información de crominancia y se obtiene la luminancia de 8 pixels en formate 8bits

21

Capítulo 5. Software

Y4

Y5

Y6

Y7

Y0

Y1

Y2

Y3

Figura 5.6: Se expanden los 8 valores de luminancia a 16 bits y se almacenan de a 4 valores en sendos registros SSE Y4

Y5

Y6

Y7

Y0

Y1

Y2

Y3

Figura 5.7: Luego se expanden a un formato de 32 bits. La información contenida en los dos registros SSE se guarda en un buffer, que contendrá la información de luminancia en formato de punto flotante de 4 bytes

5.2.3.

Estimación de las derivadas parciales

De acuerdo a lo detallado en 4.1.1 la operación de estimar las derivadas parciales consiste en realizar 4 restas y luego un promedio entre los cuatro resultados. 1 Ix = {(Ii,j+1,k − Ii,j,k ) + (Ii+1,j+1,k − Ii+1,j,k )+ 4 (Ii,j+1,k−1 − Ii,j,k−1 ) + (Ii+1,j+1,k−1 − Ii+1,j,k−1 )}

(5.1)

Las operaciones de resta se realizan entre los pixels vecinos para el frame tk y tk−1 . Nuevamente el objetivo es poder lograr estimar las derivadas procesando varios pixels en paralelo. En las siguientes imágenes se muestra el modo en que se ordenan la información de luminancia para poder calcular en paralelo las derivadas parciales. La figura 5.8 muestra una porción de dos frames consecutivos con información de luminancia I. Dicha informacióñ se carga en registros SSE para realizar el cálculo de IX . Se han de procesar en paralelo de a 4 pixels. El procedimiento que se detalla en 5.9 se repite 4 veces, dos para cada frame tk , tk−1 . Se obtiene entonces en 4 registros SSE el resultado de las 4 restas que requiere el cálculo de Ix . Ver figura 5.10. El procedimiento es similar para la estimación de las derivadas parciales Iy y It . En todos los casos se logra una paralelización del cálculo en un factor x4.

22

Capítulo 5. Software

IC

ID

IE

IF

IG

IC

ID

IE

IF

IG

IR

IS

IT

IU

IV

IR

IS

IT

IU

IV

frame tk−1

frame tk

Figura 5.8: Misma área de 4x2 pixels de dos frames consecutivos en el tiempo Para el pixel correspondiente a IC tenemos que Ix = 41 {(ID − IC )k + (IS − IR )k + (ID − IC )k−1 + (IS − IR )k−1 } XM M 0

IC

ID

IE

IF

XM M 1

ID

IE

IF

IG

XM M 2

ID − IC

IE − ID

IF − IE

IG − IF

Figura 5.9: En dos registros SSE se cargan 4 pixels consecutivos, desplazados en 1 columna, de modo que al restar los registros se realiza simultáneamente el cálculo de la primer resta de la expresión IX para estos 4 pixels. XM M 5

(IS − IR )k−1

(IT − IS )k−1

(IU − IT )k−1

(IV − IU )k−1

XM M 4

(ID − IC )k−1

(IE − ID )k−1

(IF − IE )k−1

(IG − IF )k−1

XM M 3

(IS − IR )k

(IT − IS )k

(IU − IT )k

(IV − IU )k

XM M 2

(ID − IC )k

(IE − ID )k

(IF − IE )k

(IG − IF )k

XM M 8

(IX )D

(IX )E

(IX )F

(IX )F

Figura 5.10: Los 4 registros SSE que contiene las 4 restas se suman en entre sí y luego se divide por el factor 41 obteniendo así de manera simultánea las estimación de IX para 4 pixels. 23

Capítulo 5. Software

1 12

1 6

1 12

1 6

-1

1 6

1 12

1 6

1 12

Figura 5.11: El laplaciano es estimado sustrayendo el valor en un punto determinado (i, j) de un promedio ponderado de los valores vecinos

5.2.4.

Estimación del Laplaciano

De acuerdo a lo desarrollado en la sección 4.1.1, para estimar el laplaciano se utiliza el kernel que se muestra en la figura 5.11, que implica sumar el valor de los pixels vecinos con la ponderación correspondiente y al resultado restarle el valor del pirxel. La paralelización del algoritmo no se logra indexando los pixels vecinos en cada cálculo sino con un enfoque similar al utilizado para las derivadas parciales. La figura 5.12 muestra un conjunto de pixels de un buffer que contiene alguna de las dos componentes estimadas del Flujo Óptico (u, v). Se detallan las expresiones de la estimación para los 4 pixels consecutivos K,L,M,N. En las expresiones que se listan debajo de la figura, se puede observar siempre hay conjuntos de 4 pixels consecutivos que intervienen en el cálculo de cada uno. Los pixels quedan ordenados en columnas. Esta es la condición que se aprovecha a la hora de implementar el algorítmo. Estos conjuntos de 4 pixels consecutivos se cargan en registros SSE y 1 respectivase efectuan las operacones de suma, de escalado por los factores 16 y 12 mente. Esta operación se realiza para ambas componentes (u, v) del Flujo Óptico. Nuevamente en ambos casos se logra una paralelización del cálculo en un factor x4.

24

Capítulo 5. Software

A

B

C

D

E

F

J

K

L

M

N

O

R

S

T

U

V

W

Figura 5.12: Según eq ?? el valor del laplaciano para los pixels K,L,M,N es: 1 {A + C + R + T } uK = 61 {B + L + S + J} + 12 1 1 uL = 6 {C + M + T + K} + 12 {B + D + S + U } 1 {C + E + T + V } uM = 16 {D + N + U + L} + 12 1 {D + F + U + W } uN = 61 {E + O + V + M } + 12

XM M 3

E

O

V

M

XM M 2

D

N

U

L

XM M 1

C

M

T

K

XM M 0

B

L

S

J

XM M 4

1 6 {B

+ L + S + J}

1 6 {C

+ M + T + K}

1 6 {D

+ N + U + L}

1 6 {E

+ O + V + M}

Figura 5.13: En primer lugar se resuelve la suma que es escalada por el factor de 1 y el resultado se guarda en un registro SSE. 6

25

Capítulo 5. Software

XM M 3

D

F

U

W

XM M 2

C

E

T

V

XM M 1

B

D

S

U

XM M 0

A

C

R

T

XM M 5

1 12 {A

+ C + R + T}

1 12 {B

+ D + S + U}

1 12 {C

1 + E + T + V } 12 {D + F + U + W }

Figura 5.14: En primer lugar se resuelve la suma que es escalada por el factor de 1 y el resultado se guarda en un registro SSE. 12

XM M 6

K

L

XM M 4

1 6 {B

+ L + S + J}

1 6 {C

XM M 5

1 12 {A

+ C + R + T}

1 12 {B

XM M 7

uK

+ M + T + K} + D + S + U}

uL

M

N

1 6 {D

+ N + U + L}

1 12 {C

1 + E + T + V } 12 {D + F + U + W }

uM

1 6 {E

+ O + V + M}

uK

Figura 5.15: Teniendo los factores escalados se realiza la suma para así calcular de manera paralela el valor del laplaciano para 4 pixels.

26

Capítulo 5. Software

5.2.5.

Estimación del Flujo Óptico

Como se expresa en 4.3, la estimación del Flujo Óptico se realiza con una algoritmo iterativo que implementa el siguiente cómputo: 



(5.2)





(5.3)

un+1 = un − Ix [Ix un + Iy v n + It ] / α2 + Ix2 + Iy2 v n+1 = v n − Iy [Ix un + Iy v n + It ] / α2 + Ix2 + Iy2

La condición inicial para la primera iteración n = 1 es que un = v n = 0. Atendiendo esta condición particular para el cálculo en la primera iteración se determinó eficiente separar el algoritmo para n = 1 (eq. 5.4 y 5.5) y para n > 1 (eq. 5.2 y 5.3). Esta condisideración redunda en una simplificación del cálculo en la primera iteración ya que no es necesario estimar el Laplaciano del campo de velocidades porque se supone nulo. Como se verá más adelante esta decisión impacta directamente en el tiempo de cálculo del Flujo Óptico. Las ecuaciones 5.4, 5.5, 5.2 y 5.2 representan siempre operaciones escalares entre todos los valores para una coordenada (i, j) de un pixel. Es decir que dicha operación se debe efectuar para cada uno de los 19200 pixels de un frame. Claramente ambas ecuaciones permiten ser paralelizdas. Y trabajando de manera similar a como se detalló para la estamación de las derivadas parciales y del laplaciano, se consigue un grado de paralelización x4. 



(5.4)





(5.5)

u1 = (−Ix It ) / α2 + Ix2 + Iy2 v 1 = (−Iy It ) / α2 + Ix2 + Iy2

27

6. Sensor de Imagen En este capítulo se describe el ensayo realizado utilizando la placa Intel Edison y una webcam con el objetivo de obtener capturas y analizar la tasa de fps disponible en esta configuración. Se exponen los resultados y mediciones obtenidos. Para poder tener un control de los procesos involucrados no se utilizó una biblioteca de captura u otra similar sino que se decidió programar el software a utlizar directamente sobre el driver v4l2 (Video for Linux 2) http://linuxtv. org/downloads/v4l-dvb-apis/.

6.1.

Características generales

Una de las características importantes del sensor a utilizar es la cantidad de cuadros por segundo que es capaz de entregar. Para el caso de este trabajo, es un requerimiento lograr una tasa superior a 15 fps, por lo tanto el primer paso fue asegurar que esta tasa era alcanzable. El otro parámetro a determinar es la resolución a la que va a trabajar el sensor. Puede pasar que en algunos modelos de sensores, para algunas resoluciones exista indicado una tasa máxima de fps a la que el sensor puede trabajar. En el caso del sensor que disponemos para este trabajo, en todas las resoluciones que podía trabajar, la tasa máxima es de 30 fps. Al momento de decidir la resolución de trabajo, se decidió trabajar con una resolución de 160x120 px teniendo en cuanta que es una resolución aceptable en cuanto al detalle que puede observarse. La resolución mínima que se puede distinguir en función de la distancia que determinada por la fórmula: r = tan(

f ov D ). 2 80

donde f ov es el ángulo de apertura de la cámara, tomando un valor típico de f ov = 60o , nos queda r = 0,007D 28

Capítulo 6. Sensor de Imagen

siendo D la distancia al sensor de imagen, medida en metros. Esto significa que por ejemplo a 10 metros, la resolución es de r = 7cm. En base a esto y teniendo en cuenta que una resolución mayor implicará mayor tiempo de cálculo el algoritmo, se decidió trabajar en esta resolución. Recordar que otra de las restricciones es que el sensor comparte la computadora con los algoritmos de control y navegación. En cuanto a la tasa FPS hay que tener presente que la mayoría de las webcams de bajo costo no poseen un obturador físico sino que poseen un obturador electrónico. En este tipo de dispositivos, el obturador electrónico fija el tiempo al que es expuesto el sensor a la luz. El modo por default que la mayoría de las aplicaciones o bibliotecas de procesamiento de imágenes configuran el funcionamiento del obturador electrónico es tal que, este tiempo se ajusta de acuerdo al nivel de luz presente en el momento de tomar una captura. Cuando el sensor no recibe suficiente luz el tiempo de exposición se incrementa hasta que la carga acumulada en las celdas del sensor superan cierto valor fijado como umbral mínimo requerido para obtener una imagen de buena calidad. Si el tiempo de exposición aumenta, entonces el tiempo entre capturas aumenta y por consiguiente disminuye el factor FPS. Este modo de funcionamiento origina que muchas veces, a pesar que las especificaciones del dispositivo indiquen 15 - 30 fps, la tasa de frames real termina siendo muy baja, a veces de 5 fps. Controlar la tasa de fps requiere establecer de manera manual el tiempo de exposición del sensor de imagen. En general la mayoría de los modelos de webcam permite activar el modo manual del tiempo de exposición. Para poder acceder a controlar estos parámetros de la cámara se decidió trabajar directamente con el driver del dispositivo. En el caso de este trabajo, por estar utilizando una plataforma Linux, el driver a utilizar es “Video for Linux”. El rango de valores de tiempo de exposición absolutos dependen de la cámara y se determinan mediante una consulta realizada al dispositivo a través del driver.

6.2.

Determinación de las capacidades de la webcam

Utilizando servicios de la API v4l2 se determinó en primer lugar las capacidades disponibles en el dispositivo. Es de interés que el dispositivo pueda realizar streaming de video: c a r d : Vimicro USB Camera ( A l t a i r ) bus_info : usb−dwc3−h o s t .2 −1 v e r s i o n : 30A11 29

Capítulo 6. Sensor de Imagen

c a p a b i l i t i e s : 84000001 V4L2_CAP_VIDEO_CAPTURE V4L2_CAP_STREAMING También es de interés conocer los formatos y resoluciones en los que el dispositivo puede trabajar: IMAGE FORMATS SUPPORTED 1 . YUV 4 : 2 : 2 (YUYV) Frame s i z e : 640 x 480 Frame i n t e r v a l Frame i n t e r v a l Frame s i z e : 352 x 288 Frame i n t e r v a l Frame i n t e r v a l Frame s i z e : 320 x 240 Frame i n t e r v a l Frame i n t e r v a l Frame s i z e : 176 x 144 Frame i n t e r v a l Frame i n t e r v a l Frame s i z e : 160 x 120 Frame i n t e r v a l Frame i n t e r v a l

6.3.

: 1 / 30 : 1 / 15

seg . seg .

: 1 / 30 : 1 / 15

seg . seg .

: 1 / 30 : 1 / 15

seg . seg .

: 1 / 30 : 1 / 15

seg . seg .

: 1 / 30 : 1 / 15

seg . seg .

Configuración de la webcam

La tasa de fps que un dispositivo como una webcam puede entregar es fuertemente dependiente de un parámetro involucrado durante el proceso de captura en el sensor del dispositivo que es el tiempo de exposición. Por default este tiempo queda configurado en uno de sus cuatro modos que es el “automático”. Cuando se trabaja en este modo la tasa de fps que se obtiene es muy baja, del orden de 3-5 fps. Para aumentar la cantidad de frames por segundos, es necesario configurar manualmente el tiempo de exposición. De acuerdo a la documentación del driver de video los 4 modos de configuración disponibles son: #define V4L2_CID_EXPOSURE_AUTO enum v4l2_exposure_auto_type { V4L2_EXPOSURE_AUTO = 0,

(V4L2_CID_CAMERA_CLASS_BASE+1)

30

Capítulo 6. Sensor de Imagen

V4L2_EXPOSURE_MANUAL = 1, V4L2_EXPOSURE_SHUTTER_PRIORITY = 2, V4L2_EXPOSURE_APERTURE_PRIORITY = 3 }; Y para el caso particular del dispositivo utilizado, se determinó el conjunto de parámetros configurables desde el driver:

CONTROLS SUPPORTED *) Brightness: Minimum: -10 - Maximum: 10 - Default value: 0 *) Contrast: Minimum: 0 - Maximum: 20 - Default value: 10 *) Saturation: Minimum: 0 - Maximum: 10 - Default value: 7 *) White Balance Temperature, Auto: Minimum: 0 - Maximum: 1 - Default value: 1 *) Power Line Frequency: Minimum: 0 - Maximum: 2 - Default value: 1 *) White Balance Temperature: Minimum: 2800 - Maximum: 6500 - Default value: 650 *) Sharpness: Minimum: 0 - Maximum: 10 - Default value: 2 *) Backlight Compensation: Minimum: 0 - Maximum: 2 - Default value: 0 *) Exposure, Auto: Minimum: 0 - Maximum: 3 - Default value: 3 *) Exposure (Absolute): Minimum: 8 - Maximum: 16384 - Default value: 512 A partir de esto, se realizaron 4 ensayos trabajando siempre con una configuración manual del tiempo de exposición y partiendo desde el mínimo valor posible. De acuerdo a lo indicado por la documentación del driver, el valor indicado se interpreta en unidades de 100µseg. Por lo tanto el mínimo valor posible para el tiempo de exposición es de 800µseg.

6.4.

Medición del FPS

Los cuatro tiempos de exposión probados fueron: 0.8 mseg. 1.6 mseg. 6.4 mseg. 12.8 mseg. Se configuró al dispositivo con una cola de 16 buffers de captura, para permitirle continuar capturando y encolando los frames mientras son consumidos por la aplicación cliente. La medición se realizó sobre un único servicio del driver,justamente el servicio 31

Capítulo 6. Sensor de Imagen

que permite desencolar un frame ni bien está disponible, evitando así incluir en la medición tiempos de configuración y otros procesos. Se realizó la medición sobre un ciclo de 2048 capturas, trabajando sobre un frame 160 x 120 px. y midiendo individualmente el tiempo de cada captura para poder observar la distribución de la medición. La figura 6.1 muestra los tiempos medidos y la distribución de cada medición. Para evitar cualquier overhead introducido por servicios de acceso a consola o disco, todos los tiempos medidos durante el ciclo de ensayo se guardaron en memoria y terminado el ciclo de las 2048 capturas se volcaron en archivos para luego ser analizados. 0.8 mseg → fps = 25 1.6 mseg → fps = 20. 6.4 mseg → fps = 14. 12.8 mseg → fps = 12.

32

Capítulo 6. Sensor de Imagen

Figura 6.1: Comparativa de la cantidad de fps obtenidos

33

Capítulo 6. Sensor de Imagen

6.5.

Distribución de la Luminancia

Para determinar si el utilizar tiempos tan bajos de exposición implicaba un deterioro en la calidad de la imagen obtenida se tomó una captura para tiempo ensayado y se analizó la distribución de los valores de luminancia obtenidos. El ensayo se realizó en las mismas condiciones de iluminación. Las capturas se realizaron en una habitación con iluminación artificial. Y se analiza solamente la información de luminancia, descartando las componentes de color. Las figuras 6.2, 6.3, 6.4 y 6.5 muestra el frame obtenido y la distribución de luminancia. Las figuras 6.6 y 6.7 muestran las distribuciones comparadas. Puede observarse que la distribución son similares, ubicadas en distintas zonas del rango dinámico, lo cual es coherente con tener distintos tiempos de exposición. Pero no se observa compresión hacia el negro, situación en la que se estaría perdiendo información. Por último se decidió repetir el ensayo anterior en una notebook SAMSUNG Intel(R) Core(TM) i3-2310M CPU @ 2.10GHz y sobre una PC de escritorio equipada con un Intel(R) Core i7 y en ambos casos los tiempos obtenidos fueron similares. La tasa de fps, en estas condiciones, no depende de la plataforma, solamente del dispositivo de captura.

34

Capítulo 6. Sensor de Imagen

Figura 6.2: Distribución de la Luminancia para texp = 0,8msec

35

Capítulo 6. Sensor de Imagen

Figura 6.3: Distribución de la Luminancia para texp = 1,6msec

36

Capítulo 6. Sensor de Imagen

Figura 6.4: Distribución de la Luminancia para texp = 6,4msec

37

Capítulo 6. Sensor de Imagen

Figura 6.5: Distribución de la Luminancia para texp = 12,8msec

38

Capítulo 6. Sensor de Imagen

Figura 6.6: Comparativa de la distribución de la Luminancia

39

Capítulo 6. Sensor de Imagen

Figura 6.7: Comparativa de la distribucion de la Luminancia

40

7. Software 7.1.

API para el uso del sensor

Se adjunta un documento como anexo con toda la documentación respecto del software que implementa la API del sensor. La documentación incluye la descripción de las funciones de cada módulo y se incluye un ejemplo de uso.

7.2.

Modo de funcionamiento del sensor

Desde el inicio del trabajo siempre se tuvo como objetivo que el sensor de flujo óptico debía ser visto desde el punto de vista del software como un módulo o una biblioteca que pudiese ser utilizada por otra aplicación usuaria. La finalidad del sensor es generar y tener a disposición de dicha aplicación usuaria, el flujo óptico de cada frame capturado por el sensor de imagen. El formato del flujo óptico que el sensor entrega son dos buffers con las componentes x e y del campo de velocidades respectivamente. Se implementa una cola de buffers donde el sensor va guardando los frames de flujo óptico que calcula para que la aplicación usuaria los consuma. Esta cola se implementa sobre un buffer circular y tiene un tamaño fijo, de modo que siempre estarán disponibles los últimos N frames del campo de velocidades. A los fines de poder mostrar el resultado y evaluar el comportamiento del sensor se incorporó la posibilidad que el sensor transmita el flujo óptico como un streaming de datos por un canal UDP.

7.2.1.

Transmisión por UDP

Al iniciar el sensor se abre un socket UDP hacia una dirección IP fijada en un archivo de configuración y sobre un puerto, también asignado por configuración, se transmite de manera continua los frames de flujo óptico. 41

Capítulo 7. Software

Una aplicación de software que corra en el nodo que tenga la IP indicada y escuche sobre el puerto correcto podrá recibir dicho streaming de datos. Problema con el ancho de banda La primera versión del sensor transmitía ambas componentes del flujo óptico en formato float32. Esto significa que para una tasa de 25 fps el flujo de datos resulta en: 2 ∗ 4bytes ∗ 160 ∗ 120 ∗ 25f ps = 3,84M bytes/seg Semejante tasa de datos resultó inviable sobre un enlace WIFI y como resultado la tasa a la que el sensor podía transmitir por UDP los frames de flujo óptico caí a valores de 5 fps. La lógica de transmisión que se implementó es cuando se termina de calcular el flujo óptico, si la etapa de transmisión no tiene más anda que transmitir entonces, ese frame se encola para ser enviado por el enlace UDP. Si la etapa aún está transmitiendo un frame, entonces no se encola y no se ha de transmitir. Esta lógica asegura que la aplicación escucha no se desfase en tiempo debido a la imposibilidad de lograr la tasa de transmisión necesaria. Como consecuencia, a pesar que el sensor pudiese trabajar a 25 fps, la aplicación remota recibe el flujo óptico a una tasa del orden de 5fps. Solución posible Lo correcto es implementar un protocolo que permita comprimir los frames y transmitirlo, para de este modo disminuir el ancho de banda requerido. Esta solución está por fuera del alcance de esta Tesis, pero de todos modos se implementó una solución alternativa a sólo fin de poder mostrar el resultado del sensor y lograr una tasa superior de fps. Solución alternativa implementada Se decidió que en lugar de transmitir el flujo óptico, el sensor realice un mapeo de la dirección del flujo en un espacio de color. Con lo cual lo que se está transmitiendo por el canal UDP es la dirección que tiene el flujo óptico en cada punto. Para representar este mapa de colores se requieren 3 bytes por elemento, entonces el ancho de banda, para una tasa de cálculo de 25 fps resulta ser: 3bytes ∗ 160 ∗ 120 ∗ 25f ps = 1,44M bytes/seg

42

Capítulo 7. Software

Es decir que se consigue reducir el ancho de banda a un 37,5 %. Con este requerimiento se consigue transmitir a razón de un promedio de 15 fps, lo cual es una buena tasa. Bajo ciertas condiciones que se explican a continuación, las componentes originales x, y del flujo óptico se pueden reconstruir a partir del mapeo en el espacio de color. Mapeo de la dirección del flujo óptico La forma en que se resolvió mapear la dirección del flujo óptico a un espacio de color, fue utilizar la conversión estandarizada del espacio de color YUV a RGB. Fijando la componente Y a un valor, y asociando las componentes x, y del flujo óptico a las componentes U y V del espacio de color se consigue llevar el campo de velocidades a un espacio RGB. Se fija el valor de Y = 0,5 y de acuerdo al standard adoptado en la norma NTSC el mapeo se realiza de acuerdo a las siguientes ecuaciones: R = 255 (0,5 + 1,402x)

(7.1)

G = 255 (0,5 − 0,344y − 0,714x)

(7.2)

B = 255 (0,5 + 1,722y)

(7.3)

El resultado obtenido se puede ver en la figura 7.1. Es importante notar que para el standard NTSC se espera que las componentes U, V , en este caso x, y del flujo óptico, se encuentren en el rango [−1,0; 1,0]. Aún así no todos los valores dentro de este rango son luego representables en el espacio RGB. Esto es debido a que en dicho espacio los valores posibles de las componentes de color son en el rango [0; 255]. Cualquier resultado por fuera de este rango termina siendo ajustado a los valores del extremo. El sensor implementa el cálculo del mapeo al espacio RGB en aritmética de punto flotante, aprovechando también la tecnología SSE de Intel. Los resultados numéricos de cada una de las componentes R, G, B podrán caer eventualmente fuera del rango posible. El proceso de saturación por corte a los valores máximos o mínimos de cada componente, se efectúa a la hora de empaquetar el mapa RGB resultante a un formato de 8bits por color. Al momento de realizar el mapeo del frame de flujo óptico no se tiene información del rango de los valores de las componentes x, y. Dicho rango guarda relación con el módulo de la velocidad. Por lo tanto la situación que algunos puntos del frame terminen siendo mapeados fuera del rango posible de valores R, G, B puede

43

Capítulo 7. Software

presentarse. Anticipar esta situación para ser ajustada requiere analizar previamente el frame a fin de determinar el valor máximo y luego escalar todo el frame. Pero esta operación sumaría overhead al procesamiento así que no se consideró como viable de implementar. Como solución alternativa, se resolvió incorporar un factor de ganancia que se aplica a las componentes x, y antes de realizar la conversión. Las ecuaciones de mapeo finalmente quedan: R = 255 (0,5 + Gain(1,402x))

(7.4)

G = 255 (0,5 + Gain(−0,344y − 0,714x))

(7.5)

B = 255 (0,5 + Gain(1,722y))

(7.6)

Este valor puede ser ajustado dinámicamente a través de la API del sensor y ofrece una forma de calibrarlo para evitar el problema de la saturación. Obtención de las componentes x, y del flujo óptico Cuando no se produce saturación o corte del valor resultante del mapeo RGB y siendo conocido el valor de la ganancia asociada, es posible recuperar los valores x, y de las componentes del flujo óptico. Teniendo en cuenta que existirá pérdida de la información que se produce al realizar la conversión de float32 a 8bits al momento de transmitir el frame RGB.

7.2.2.

Protocolo de transmisión

El sensor transmite por UDP la dirección del flujo óptico mapeada sobre el espacio RGB. Cada frame tiene un tamaño de 57,6 Kbytes. El frame se transmite en 112 paquetes de 512 bytes y un paquete final de 256 bytes. Previo a cada frame se transmite un Header con información sobre el estado del sensor y los tiempos asociados al cálculo del flujo óptico. Este Header es utilizado como Key Frame para que una aplicación que se esté escuchando sobre el canal UDP pueda sincronizarse. El header contiene: Nro de frame de flujo óptico Tiempo entre frame expresado en mseg. Este tiempo puede ser empleado para mostrar la tasa fps a la que que se encuentra trabajando el sensor. Tiempo que está empleando el sensor en realizar el procesamiento de un frame, expresado en mseg. A partir de este tiempo y la tasa fps se puede tener una idea del tiempo libre de CPU disponible. 44

Capítulo 7. Software

Figura 7.1: Espacio de colores RGB para un valor de Y = 0,5 Tiempo que se demoró en transmitir el frame por UDP. Se expresa en mseg y en realidad se corresponde con el tiempo empleado en transmitir el frame anterior. Este tiempo permite expresar la tasa fps del flujo que se está transmitiendo por UDP y también es una medida indirecta de la disponibilidad del canal UDP.

7.2.3.

Aplicación remota de prueba

Se desarrolló una aplicación que se ejecuta remotamente y que escucha sobre el puerto designado a fin de recibir el streaming de datos UDP del sensor de flujo óptico. Utilizando la biblioteca GNUPlot, se recibe el header y el frame correspondiente y se grafica el mapa RGB que muestra la dirección del flujo óptico. También se muestran los parámetros presentes en el header, a fin de poder apreciar el estado del algoritmo dentro de la placa Edison. Por último se recuperan las componentes x, y del campo de velocidades y se grafica el módulo del mismo en una imagen, mapeando el valor del módulo de la velocidad sobre un eje de colores.

45

8. Ensayos y Mediciones 8.1.

Tiempos del algoritmo

El algoritmo en cada frame realiza la medición de dos intervalos de tiempo para poder obtener información en tiempo real del funcionamiento del sensor. Durante el desarrollo del software, esta información ha sido de utilidad durante el proceso de depuración. Pero sigue estando disponible porque puede ser de utilidad para la aplicación que haga uso del sensor. En cada ciclo se realizan dos mediciones. La primer medición se inicia en el momento en que se solicita al driver del sensor de imagen un frame y finaliza cuando se ha terminado de calcular el flujo óptico. Incluye el tiempo que demore el driver en disponer de la captura del sensor. No incluye el tiempo de transmisión por UDP ni el tiempo que demore la llamada a la función callback instalada por la aplicación usuaria. La segunda medición solamente incluye el procesamiento del frame obtenido del sensor de imagen hasta que el flujo óptico está disponible. Ambas mediciones se incluyen dentro del estado general que es reportado en el header de cada frame transmitido por UDP. Ver 7.2.2. A partir de los valores obtenidos en la segunda medición se pudo determinar que tiempo necesario para procesar el frame y calcular el flujo óptico es en promedio: k = 1 (una iteración): ≈ 3mseg k = 2 : ≈ 13mseg k = 3 : ≈ 23mseg Se observa que como se mencionó en 5.2.5 el hecho de haber simplificado el cálculo para la primera iteración, evitando estimar el laplaciano del campo implicó un ahorro significativo del tiempo empleado. 46

Capítulo 8. Ensayos y Mediciones

Porque como se observa de las mediciones siguientes, el proceso de estimar el laplaciano para k > 1 tiene un costo de ≈ 10mseg. Es importante notar que para valores k > 4 el tiempo que se necesita para estimar el flujo óptico empieza a tener incidencia en la tasa de frames por segundos. Tiene incidencia haciendo que la tasa disminuya debido a que pasa a ser el tiempo de procesamiento el factor limitante y no la velocidad de adquisición del sensor de imagen.

8.1.1.

Método de medición

Para medir el tiempo de procesamiento se emplea la función disponible en C clock_gettime, que permite obtener el tiempo en precisión de nano segundos. #include struct timespec { time_t tv_sec; long tv_nsec; };

/* seconds */ /* nanoseconds */

int clock_gettime(clockid_t clk_id, struct timespec *tp);

8.2.

Descripción de la prueba

El sensor fue probado en una ambiente real de aplicación. Se montó la placa Edison y el sensor de imagen en uno de los cuadcópteros del laboratorio. El sensor de image se ubicó de modo que quede apuntando hacia el suelo. El sensor se monta sobre los brazos del robot como puede observarse en la imagen 8.1 El objetivo del ensayo es comprobar el funcionamiento sobre un piso uniforme con marcas. El cuadcóptero se desplaza paralelo al piso y las marcas entran y salen del campo de visión de la cámara. Ver imagen 8.2.

8.2.1.

Desarrollo del ensayo

El sensor se configuró para transmitir sobre un enlace UDP el flujo óptico mapeado al espacio RGB de acuerdo a lo explicado en la sección 7.2.1. Una aplicación remota es la encargada de recibir por el canal UDP los sucesivos frames y además de mostrarlos en tiempo real, guardarlos en disco para un posterior análisis.

47

Capítulo 8. Ensayos y Mediciones

Figura 8.1: Montaje del sensor de imagen y la placa Intel Edison en el cuadcóptero.

Figura 8.2: Escenario de prueba: Piso uniforme con marcas

48

Capítulo 8. Ensayos y Mediciones

Figura 8.3: Detección con nivel de iteración k = 1

8.2.2.

Resultados

Número de iteraciones del algoritmo Se probó el sensor trabajando en distinos configuraciones de iteraciones del algoritmo. Con la iteración mínima, la detección del flujo óptico se da en los bordes, a medida que el nro de iteraciones aumenta el campo de velocidades se expande hasta cubrir todo la sección de la imagen que tiene igual velocidad. Se muestran los resultados para tres configuraciones de iteración: k = 1, k = 3 y k = 5. Ver imágenes 8.3, 8.4 y 8.5.

49

Capítulo 8. Ensayos y Mediciones

Figura 8.4: Detección con nivel de iteración k = 3

Figura 8.5: Detección con nivel de iteración k = 5

50

Capítulo 8. Ensayos y Mediciones

Mapeo de la dirección en el espacio RGB Se puedo constatar que a diferentes direcciones de desplazamientos el color de las marcas varia. También en los casos en que la cámara rota sobre su eje. Secuencia de movimiento A Los esquemas 8.6, 8.7 y 8.8 muestran el movimiento del cuadcóptero en tres frames consecutivos en donde avanza en una dirección, detiene su avance y cambia de dirección. En el instante en que se produce el cambio se observa cierta componente de rotación junto con la detención para invertir la dirección del movimiento. La secuencia de las imágenes 8.9, 8.10 y 8.11 muestran el flujo óptico para esta secuencia.

Figura 8.6: Cuadro 1 de la secuencia de movimiento A, el desplazamiento es hacia la izquierda, el flujo óptico resultante es 8.9.

51

Capítulo 8. Ensayos y Mediciones

Figura 8.7: Cuadro 2 de la secuencia de movimiento A, la marcha se detiene y hay cierta rotación antes de iniciar el desplazamiento en sentido contrario, el flujo óptico resultante es 8.10.

Figura 8.8: Cuadro 3 de la secuencia de movimiento A, el desplazamiento es hacia la dereceha, el flujo óptico resultante es 8.11. Secuencia de movimiento B Los esquemas 8.12, 8.13 y 8.14 muestran el movimiento del cuadcóptero en tres frames consecutivos en donde se avanza siguiendo una trayectoria curva donde al inicio se acerca hacia una de las líneas, y luego el movimiento se orienta paralelo a dicha línea para comenzar a alejarse. La secuencia de imágenes 8.15,8.16 y 8.17 nos muestra el flujo óptico de dicha 52

Capítulo 8. Ensayos y Mediciones

Figura 8.9: Primera Secuencia, cuadro 1: Avance hacia la izquierda. Ver esquema 8.6

Figura 8.10: Primera Secuencia, cuadro 2: Detención y cierta rotación. Ver esquema 8.7

53

Capítulo 8. Ensayos y Mediciones

Figura 8.11: Primera Secuencia, cuadro 3: Avance hacia la derecha. Ver esquema 8.8 secuencia. Puede apreciarse como cuando el movimiento es paralelo a la línea el flujo óptico detectado disminuye sensiblemente. Idealmente, al ser la línea uniforme, debería ser cero. Es notorio el cambio de color entre los instantes en que el movimiento es “hacia la línea” y “alejándose de la línea”.

54

Capítulo 8. Ensayos y Mediciones

Figura 8.12: Cuadro 1 de la secuencia de movimiento B, el desplazamiento es hacia abajo en diagonal, acercándose a una de las líneas, el flujo óptico resultante es 8.15.

Figura 8.13: Cuadro 2 de la secuencia de movimiento B, el desplazamiento es paralelo a una de las líneas, el flujo óptico resultante es 8.16.

55

Capítulo 8. Ensayos y Mediciones

Figura 8.14: Cuadro 3 de la secuencia de movimiento B, el desplazamiento es alejándose de la línea, el flujo óptico resultante es 8.17.

Figura 8.15: Cuadro 1 de la secuencia de movimiento B: el desplazamiento es hacia abajo en diagonal, acercándose a una de las líneas, ver esquema 8.12.

56

Capítulo 8. Ensayos y Mediciones

Figura 8.16: Cuadro 2 de la secuencia de movimiento B: el desplazamiento es paralelo a una de las líneas, ver esquema 8.13.

Figura 8.17: Cuadro 3 de la secuencia de movimiento B: el desplazamiento es hacia arriba en diagonal, alejándose de una de las líneas, ver esquema 8.14. 57

Capítulo 8. Ensayos y Mediciones

8.3.

Video

Se incluye el video con las secuencia de frames de la dirección dle flujo óptico capturadas por la aplicación remota durante el vuelo del cuadcóptero.

58

9. Conclusiones y pasos futuros A partir de este trabajo pudo probarse y determinar que la plataforma Edison de Intel es apta para implementar un sensor de flujo óptico utilizando un sensor de imagen de bajo costo. Además el consumo de tiempo de procesador que requiere el sensor deja recursos disponibles para ser utilizados para la implementación de otros algoritmos de control que hagan uso del sensor. De acuerdo a los ensayos y mediciones realizas se puede caracterizar la carga que representa el sensor a la placa Edison. Las gráficas 9.1, 9.2 y 9.3 muestran la relación entre el porcentaje de uso del procesador en función de la cantidad de iteraciones que realice el algoritmo y la tasa FPS a la que esté trabajando el sensor. Con esta información y en función de la carga de la aplicación usuaria del sensor se puede determinar un punto de trabajo en términos de la tasa de FPS y la cantidad de iteraciones a realizar. 100 % 82,5 % 57,5 % 32,5 % 7,5 % 1

2

3

4

Nro de iteraciones Figura 9.1: Porcentaje de carga del procesador para distintos niveles de iteración del algoritmo trabajando a 25 FPS. No se incluye la carga de la transmisión por UDP 59

Capítulo 9. Conclusiones y pasos futuros

100 % 92 % 66 % 46 % 26 % 6% 1

2

3

4

5

Nro de iteraciones Figura 9.2: Porcentaje de carga del procesador para distintos niveles de iteración del algoritmo trabajando a 20 FPS. No se incluye la carga de la transmisión por UDP

100 % 83 %

93 %

73 % 63 % 53 % 43 % 33 % 23 % 13 % 3% 1

2

3

4

5

6

7

8

9

10

Nro de iteraciones Figura 9.3: Porcentaje de carga del procesador para distintos niveles de iteración del algoritmo trabajando a 10 FPS. No se incluye la carga de la transmisión por UDP

60

Capítulo 9. Conclusiones y pasos futuros

Figura 9.4: Captura de la dirección del flujo óptico durante un vuelo con el ambiente con baja iluminación. Al aumentar la sensibilidad, el nivel de ruido de fondo aumenta y esto se puede observar en la imagen. Ya se demostró en las pruebas realizadas y descriptas en 6.5 que el sensor puede trabajar con bajos tiempos de exposición en condiciones normales de iluminación. También se efectuó un ensayo en un ambiente de baja iluminación y los resultados obtenidos fueron satisfactorios. Para estos casos se puede modificar el valor del parámetro α presente en la solución iterativa: 



(9.1)





(9.2)

un+1 = un − Ix [Ix un + Iy v n + It ] / α2 + Ix2 + Iy2 v n+1 = v n − Iy [Ix un + Iy v n + It ] / α2 + Ix2 + Iy2

En la práctica este parámetro termina actuando como un ajuste de la sensibilidad del sensor. El valor por default es α = 100,0. Cuánto más chico es el valor, más sensibilidad tendrá el sensor. En el caso de la prueba realizada con baja luz ambiente el valor se ajustó a α = 10,0 y los resultados obtenidos pueden verse en la figura 9.4.

61

Capítulo 9. Conclusiones y pasos futuros

9.1.

Próximos Pasos

A medida que el sensor se vaya utilizando en otros trabajos futuros se dará asistencia a los bugs que pudieran surgir en cuanto al componente de software del mismo. También es de esperar que antes necesidades de nuevas aplicaciones usuarias se requiera expandir las funcionalidades presentes en esta versión en la interfaz de uso. Es factible pensar en servicios que permitan calibrar y definir el punto de funcionamiento más apropiado en función del modelo de sensor de imagen que se utilice.

62

Bibliografía J. J. Gibson. The Perception of the Visual World. Houghton Mifflin, Boston, MA, 1950. 3 Berthold K. P. Horn and Brian G. Schunck. Determining optical flow. 1981. 3, 4, 5, 6, 10, 12 c Lucian Busoniu. Control grid motion estimation for efKoppány Máthà ; ficient application of optical flow. Part of: Sensors 2015, 15, 14887-14916; doi:10.3390/s150714887. 3 J. L. Barron, D. J. Fleet, and S. S. Beauchemin. Performance of optical flow techniques. INTERNATIONAL JOURNAL OF COMPUTER VISION, 12: 43–77, 1994. 4 Bruce D. Lucas and Takeo Kanade. An iterative image registration technique with an application to stereo vision. pages 674–679, 1981. URL http://dl.acm. org/citation.cfm?id=1623264.1623280. 5 E. P. Simoncelli, E. H. Adelson, and D. J. Heeger. Probability distributions of optical flow. pages 310–315, Jun 1991. ISSN 1063-6919. doi: 10.1109/CVPR. 1991.139707. 5 H. Nagel. Displacement vectors derived from second-order intensity variations in image sequences. Computer Vision, Graphics, and Image Processing, 21(1): 85–117, January 1983. ISSN 0734189X. URL http://dx.doi.org/10.1016/ s0734-189x(83)80030-9. 5 P. Anandan. A computational framework and an algorithm for the measurement of visual motion. International Journal of Computer Vision, 2(3):283–310. ISSN 1573-1405. doi: 10.1007/BF00158167. URL http://dx.doi.org/10. 1007/BF00158167. 5

63

BIBLIOGRAFíA

N. Ancona and T. Poggio. Optical flow from 1d correlation: Application to a simple time-to-crash detector. IUW, 93:673–682. 5, 8 David J. Heeger. Optical flow using spatiotemporal filters. International Journal of Computer Vision, 1(4):279–302. ISSN 1573-1405. doi: 10.1007/BF00133568. URL http://dx.doi.org/10.1007/BF00133568. 5 David H Zwart, Christine M; Frakes. Vision and Control for UAVs: A Survey of General Methods and of Inexpensive Platforms for Infrastructure Inspection. Part of: Synthesis digital library of engineering and computer science. 6 Tomaso Verri, Alessandro ; Poggio. Motion feld and optical flow: Qualitative properties. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11:490 - 498, 1989. 8 Alessandro; Torre Vicent Poggio, Tomaso; Verri. Green theorems and qualitative properties of the optical fow. Technical Report A.I. Memo No. 1289, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, 1991. 8 H. H. Nagel. Image Sequence Analysis, chapter Image Sequence Analysis: What Can We Learn from Applications?, pages 19–228. Springer Berlin Heidelberg, Berlin, Heidelberg, 1981. ISBN 978-3-642-87037-8. doi: 10.1007/978-3-642-87037-8_2. URL http://dx.doi.org/10.1007/ 978-3-642-87037-8_2. 10 Deqing Sun, S. Roth, and M.J. Black. Secrets of optical flow estimation and their principles. volume 15, page 14887, 2015. URL http://www.mdpi.com/ 1424-8220/15/7/14887. 11

64