Repositorio Institucional de Documentos

E s Reposito r s timac r io de la Un Proy ión on P e E s iversidad d ecto line d e secue n Luis Ll a Direct o e dro Ant o s cuela de I n e Zaragoz a Fin d e l flujo ó n cia d e Autor/es a mas Bi o r/es y/o p o o nio Pinié s n geniería y 2013 – Zaguan d e C a ó ptico e vídeo naburo o nente s Rodrígu Arquitect u http://zag u a rrer a a parti ez u ra u an.unizar. e a r de u n e s n a Resumen Luis Llamas Binaburo Estimación online del Optical Flow E s s timación online d e secue n e l flujo ó n cia d e ó ptico e vídeo a parti r de u n n a I El objeto del proyecto es la implementación en C++/CUDA de un algoritmo para la estimación del movimiento de los pixels que componen una imagen (Optical Flow). Asimismo se desea acelerar el proceso hasta conseguir su aplicación en tiempo real a partir de imágenes capturadas mediante una webcam. A través de este cálculo se obtiene una gran información de los objetos dinámicos en la escena y supone un paso previo para el desarrollo de una amplia variedad de aplicaciones tanto en la robótica móvil como en visión por computador. Los fundamentos matemáticos en los que se basa el algoritmo son técnicas de variación total aplicadas al ámbito de la visión. Las funciones empleadas son no diferenciables, por lo que se emplea el método de optimización convexa basado en la transformada de Fenchel-Legendre. Para su resolución se emplea un algoritmo de Proximal Map. Debido a la complejidad matemática de estas técnicas se ha implementado, de forma adicional, una aplicación de filtrado de ruido en tiempo real (Denoise) que ha permitido familizarse con las técnicas empleadas con carácter previo a la implementación del Optical Flow. Para la aceleración del cálculo hasta conseguir la ejecución en tiempo real de ambas aplicaciones se ha hecho uso de la tecnología CUDA que permite la ejecución de programas en la tarjeta de vídeo (GPU), lo que supone un paradigma de computación paralela SIMT (Single Instruction Multiple Thread), es decir, una misma instrucción ejecutada en múltiples threads. Los resultados obtenidos recogen, para ambas aplicaciones, la comparación de tiempos de ejecución entre CPU y GPU, la influencia en el mismo de los distintos parámetros que intervienen, la caracterización de la eficacia en la consecución del resultado deseado y, finalmente, la obtención de una zona de real time como combinación de los parámetros de entrada dentro de la cual se consigue la ejecución en tiempo real. Luis Llamas Binaburo Estimación online del Optical Flow Luis Llamas Binaburo Estimación online del Optical Flow II Amitíoyamiabuela. Alládondeestéis,esperoqueos sintáisorgullososdemi. Luis Llamas Binaburo Estimación online del Optical Flow Índice 1 Introducción .......................................................................................................................... 2 1.1 Objetivos ....................................................................................................................... 2 1.2 Definición de Optical Flow ............................................................................................ 2 1.3 Definición de CUDA ....................................................................................................... 3 1.4 Trabajos realizados ........................................................................................................ 5 1.5 Consideraciones adicionales ......................................................................................... 6 1.5.1 Equipo empleado .................................................................................................. 6 1.5.2 Igualdad de condiciones ........................................................................................ 6 1.5.3 Parámetros de simulación ..................................................................................... 6 2 Fundamentos matemáticos .................................................................................................. 7 3 Denoise ................................................................................................................................ 13 3.1 Planteamiento ............................................................................................................. 13 3.2 Clase Denoise .............................................................................................................. 14 3.3 Resultados ................................................................................................................... 15 3.3.1 Comparación entre CPU y GPU ........................................................................... 15 3.3.2 Influencia de los parámetros ............................................................................... 16 3.3.3 Relación señal radio SNR ..................................................................................... 17 3.3.4 Zona tiempo real ................................................................................................. 18 4 Optical Flow ......................................................................................................................... 19 4.1 Planteamiento ............................................................................................................. 19 4.2 Clase pirámide ............................................................................................................. 21 4.3 Clase Optical Flow ....................................................................................................... 22 4.4 Esquema de funcionamiento ...................................................................................... 23 4.5 Resultados ................................................................................................................... 24 4.5.1 Comparación entre CPU y GPU ........................................................................... 24 4.5.2 Influencia de los parámetros ............................................................................... 25 4.6 Comparación con Ground Truth ................................................................................ 26 4.6.1 Zona tiempo real ................................................................................................. 27 5 Conclusiones........................................................................................................................ 28 5.1 Trabajos futuros .......................................................................................................... 28 Luis Llamas Binaburo Estimación online del Optical Flow Índice Memoria III Índice Luis Llamas Binaburo Estimación online del Optical Flow 1 Planteamiento del método ................................................................................................. 30 1.1 Caso general ................................................................................................................ 30 1.2 Modelo Tikhonov ........................................................................................................ 30 1.3 Modelo TV-ROF ........................................................................................................... 1.4 Modelo TV-L1 .............................................................................................................. 31 2 Método Dual Primal ............................................................................................................ 32 3 Discretización ...................................................................................................................... 34 3.1 Discretización caso general ......................................................................................... 34 3.2 Discretización operadores ........................................................................................... 35 4 Denoise ................................................................................................................................ 36 4.1 Planteamiento ............................................................................................................. 36 4.2 Discretización .............................................................................................................. 36 4.3 Esquema algoritmo ..................................................................................................... 38 4.4 Ecuaciones algoritmo .................................................................................................. 39 4.5 Ecuaciones algoritmo discretizadas ............................................................................ 40 5 Optical Flow ......................................................................................................................... 41 5.1 Planteamiento ............................................................................................................. 41 5.2 Discretización .............................................................................................................. 42 5.3 Esquema algoritmo ..................................................................................................... 44 5.4 Ecuaciones algoritmo .................................................................................................. 47 5.5 Ecuaciones algoritmo discretizadas ............................................................................ 48 Índice Apéndice A. Desarrollo matemático Bibliografía ................................................................................................................................ IV 50 30 MEMORIA Luis Llamas Binaburo Estimación online del Optical Flow 1 Memoria 2 Fundamentos matemáticos Los fundamentos matemáticos en los que se basa el presente proyecto están basados en la Tesis doctoral de Thomas Pock de la Universidad de Graz de enero de 2008 [TP08], que posteriormente serían ampliados en un artículo publicado en mayo de 2010, realizado por el mismo autor en colaboración con Antonin Cambolle [TA10]. Existe un marcado interés dentro del ámbito de la visión por computador en el estudio de los métodos variacionales debido a que su planteamiento y capacidad de modelado se ajusta con elevado éxito a un amplio tipo de problemas encontrado de forma habitual en visión por computador, tales como denoising, inpainting, deblurring, optical flow, segmentación y reconstrucción 3D, entre otros. Las técnicas y algoritmos presentados en estos artículos presuponen un conocimiento de las herramientas y fundamentos matemáticos en los que se basan. Desafortunadamente no se ha encontrado un compendio o libro en que explique de forma unificada estos conceptos. Por tanto se considera interesante proporcionar en este proyecto una explicación intuitiva sobre la base la base matemática y el funcionamiento de estos métodos. Una explicación extendida de los algoritmos se presenta en el Apéndice Matemático adjunto al presente documento. Los métodos variacionales aplicados a imágenes consisten, de forma general, en el estudio de la resolución de familias de ecuaciones del tipo: Término regularizador Término fidelidad El interés que subyace a la resolución de este tipo de problemas de minimización reside en una suposición lógica de que las imágenes poseen una relativa suavidad. Por tanto, resulta interesante minimizar la variación en las mismas. La ecuación presentada dispone de dos términos diferenciados, − El término regularizador penaliza la presencia de variaciones dentro de la imagen. Por tanto, favorece la obtención de soluciones suaves. − El término de fidelidad, o data term, aporta las condiciones de entrada, penaliza las soluciones que se desvían de las mismas. La relación entre ambos comportamientos, el carácter suave impuesto por el término regularizador, y el ajuste a los datos de entrada impuesto por el término de fidelidad, se regula a través del peso del parámetro lambda El método propuesto presenta, como se ha comentado, importantes aplicaciones dentro de un amplio rango de problemas típicos en visión por computadora. La diferencia entre su aplicación a una u otro caso viene dada por la forma adoptada por las funciones F y G, que deben ser particularizadas para cada aplicación en concreto. m´ın uZΩ F(∇u)λZΩ G( )  + Luis Llamas Binaburo Estimación online del Optical Flow 7Fundamentos matemáticos u Tomando como ejemplo por ser el caso más sencillo, variacional general pasa a estar expresado de Fina lmente, los métodos TV Imagen 8. Efecto de la norma L1 en métodos v Por tanto, el principal interés término regularizador en problemas variacionales en imágenes de zonas suaves sin penalizar en exceso, y por tanto conservando, los cont Las siguientes imágenes obtenidos en la aplicación de los distintos algoritmos como ejemplo para la explicación su aplicación al filtrado de ruido, por ser el caso más sencillo, aplicando una regularización Tikhonov el probl pasa a estar expresado de expresado de la siguiente forma lmente, los métodos TV -L1, sustituyen ambos términos por la norma L1. Efecto de la norma L1 en métodos v ariacionales el principal interés tras la susti tución de la norma cuadrática en el término regularizador en problemas variacionales en imágenes es permitir suaves sin penalizar en exceso, y por tanto conservando, los cont Las siguientes imágenes , obtenidas del artículo [A01], comparan los resultados obtenidos en la aplicación de los distintos algoritmos en la eliminación de ruido. su aplicación al filtrado de ruido, aplicando una regularización Tikhonov el probl ema expresado de la siguiente forma : ambos términos por la norma L1. tución de la norma cuadrática en el permitir la existencia suaves sin penalizar en exceso, y por tanto conservando, los cont ornos. comparan los resultados eliminación de ruido. m´ın uZΩ (∇u)2dΩ + λZΩ ( )2dΩ u−f m´ın uZΩ|∇u|+λZΩ (u−f)2dΩ m´ın uZΩ|∇u|+λZΩ|u−f|dΩ 01 Luis Llamas Binaburo Estimación online del Optical Flow 8  nor m esta d  enl o (azul func i elc o esca exist Elinter é m aL1pue d d ística. Encuan t o smétodo s ),esidénti c i onesmon ó o ntrario,la lón,quela enciadesa é strasla s d eentende t oalavari s variacion a c aalavari a ó tonascon normacua d gráficaden ltosbrusco s ustitución rsecomo a acióntotal , a les.Seob s a cióntotal d idénticose x d ráticadel tadayasu s delanor m a nalogíac o , lasiguien t s ervaquel a d elafunci ó x tremospr e gradiente d vezquela m acuadrát i o nlosmét o t efigurail u a variación ó ndentada e sentaránl a d elafunci ó funciónlin e i caenel d o dosdeaj u straelsig n totaldela (rojo).En g a mismava ó npenaliza r e alporloq d ataterm p usterobu s n ificadode funcióne s g eneral,to d riacióntot a r íamásla g uenoper m p orla toen |u| s calón d aslas a l.Por g ráfica m itela Fundamentos matemáticos En 1992 los autores Rudin, Osher y Fatemi norma cuadrática del término regularizador por la n término se convierte en la al método TVROF (Total Variation Rudi En 1992 los autores Rudin, Osher y Fatemi [LO92] , estudian la sustitución de la norma cuadrática del término regularizador por la n orma L1, con lo que el primer término se convierte en la variación total |∇u| de la función a minimizar, dando lugar ROF (Total Variation Rudi -Osher-Fatemi). , estudian la sustitución de la orma L1, con lo que el primer de la función a minimizar, dando lugar En primer lugar comparamos Tikhonov con TV-ROF para imágenes a las que se les ha añadido ruido independiente gaussiano en cada pixel. Original Imagen con ruido Resultado con Tikhonov Resultado con TV-ROF Se observa como el modelo TV-ROF es capaz de reconstruir con mayor precisión la imagen original de la imagen, manteniendo los contornos, mientras que el modelo Tikhonov presenta un difuminado general de la imagen. A continuación se compara el comportamiento del TV-ROF frente al TV-L1 para el caso en que la imagen, además de ruido gaussiano, tiene ruido de sal y pimienta es decir datos espurios. Original Imagen con ruido Resultado con TV-ROF Resultado con TV-L1 Luis Llamas Binaburo Estimación online del Optical Flow 9Fundamentos matemáticos El método TV-L1, al tener una norma absoluta en el término de fidelidad, presenta mayor inmunidad a la presencia de espurios, a la vez que el regularizador sigue preservando los bordes de la imagen. El método TV-ROF se ve más afectado por espurios dado que no es robusto, obteniendo una imagen con menor precisión. Pese a sus prestaciones superiores, la sustitución de las normas cuadráticas por el valor absoluto tiene como consecuencia el incremento de la dificultad en la resolución debido a la introducción de funciones no diferenciables. Para solventar este problema se emplea un algoritmo denominado Primal Dual, que permite hallar el mínimo absoluto de problemas del tipo que nos ocupan. Retomando el caso general, su formulación discretizada resulta, donde ambas funciones F y G son convexas, aunque no necesariamente diferenciables (por ejemplo, en el caso de usar valor absolutos en una o ambas de ellas) y K es la versión discreta del operador gradiente. A continuación, para facilitar la explicación, supongamos el modelo ROF, donde F es no diferenciable. La base del método es usar la transformación de LegendreFenchel para sustituir las funciones no diferenciables por una expresión equivalente. De forma general, la transformación de Legendre-Fenchel tiene la siguiente expresión Una versión intuitiva del concepto es considerar que <p,x> es la formulación de un hiperplano que pasa por el origen, cuya orientación está determinada por el que debe tener un hiperplano de orientación p para quedar siempre por debajo de Imagen 9. Interpretación de la conjugada convexa. m´ın uF(Ku) + G(u F∗(p) = sup x < x,p > −F(x) 0 2 4 6 8 10 0 5 10 15 20 25 30 0 2 4 6 8 10 0 5 10 15 20 25 30 Luis Llamas Binaburo Estimación online del Optical Flow 10 Fundamentos matemáticos ) vector p. De esta forma, F*(b) puede ser interpretado como la ordenada en el origen F(x). Esto permite interpretar F(x) como la envolvente definida por hiperplanos afines denominada conjugada convexa [SB04] como se ilustra en el siguiente esquema. cuya gráfica es la siguiente, Imagen 10. Formulación dual de la función valor absoluto Para ilustrar el resultado obtenido, así como la dependencia con la visión intuitiva anterior de la conjugada convexa, consideremos la siguiente imagen, Imagen 11. Interpretación de la conjugada convexa del valor absoluto. F∗(p) = 0|p| ≤ 1 ∞ |p|>1 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 0 0.5 1 1.5 2 2.5 3 3.5 4 p x −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 0 0.5 1 1.5 2 p<=1 p>1 Luis Llamas Binaburo Estimación online del Optical Flow 11 Fundamentos matemáticos La aplicación del método a la norma L1 resulta en la siguiente expresión, Se hace notar que la definición de la misma depende fuertemente de las derivadas de F(x). La conjugada convexa tiene importantes propiedades y aplicaciones dentro del campo de los problemas de optimización. Por ejemplo, la biconjugada de cualquier función es una función convexa, que representa el menor conjunto convexo que envuelve a la función original, denominada “Convex Hull”. De esta forma, la biconjugada de una función F coincide con si misma si y solo si F es convexa y semicontinua inferiormente. La aplicación del método a la norma L1 resulta en la siguiente identidad: De esta forma se sustituye la función norma L1 por una función derivable. Sin de maximización con restricciones |p|<=1. donde las expresiones del tipo precisamente suponen el Proximal Map, cuya definición formal se recoge en la siguiente expresión, En particular, para el problema de Denoising el Proximal Map admite una interpretación sencilla como un algoritmo de gradiente ascendente (dual) / descendente (primal), en los que el gradiente se evalúa en el punto posterior, mientras que se garantiza que las restricciones cumplen (|p|<=1). Por otro lado, si bien en un problema genérico de optimización no se puede garantizar encontrar el mínimo absoluto, para la clase de problemas con estructura que estamos considerando, en particular para F y G convexas, la metodología presentada permite encontrar el mínimo absoluto. |∇u|=max {p·∇ :||p|| ≤ 1}    yn+1 = (I+σ∂F ∗)−1(yn+σKˆxn) xn+1 = (I+τ∂G)−1(yn+τK∗yn+1) ˆxn+1 =xn+1 +θ(xn+1 −xn) x= (I+τ∂F)−1(y) = arg m´ın x||x−y||2 2τ+F(x) (I+τ∂F)−1 Luis Llamas Binaburo Estimación online del Optical Flow 12 Fundamentos matemáticos embargo se añade la dificultad de introduce una variable dual, y de una etapa adicional La función valor absoluto está compuesta por únicamente dos pendientes, de valores -1 y 1. Para direcciones p inferiores a -1 o superiores a 1, cualquier hiperplano resultante quedará por encima de |x| al tender x a infinito, y la diferencia entre la función y el hiperplano tenderá a infinito, por lo que F*(x) resulta infinito. Únicamente para direcciones tales que |p|≤1 el hiperplano resultante es un subestimador de F(x), siendo el máximo valor de la ordenada del mismo, y por tanto F*(x), el origen 0. u La razón de emplear el método Primal-Dual frente a otros de orden superior, como Newton Rapson, es que su implementación resulta más eficiente y, especialmente, que resulta susceptible de ser ejecutada en paralelo. Por tanto aunque el orden de convergencia del método es inferior, la eficiencia de la implementación y la posibilidad de posterior aceleración mediante su ejecución en GPU compensan con creces el mayor número de pasos necesarios para alcanzar la solución. Para la resolución del problema general ampliado, tras la sustitución de la norma L1 por su formulación dual equivalente, Thomas Pock propone la resolución mediante el método del Proximal Map [RF70] el cual se sintetiza en el siguiente esquema, 3 Denoise 3.1 Planteamiento Particularizando el ha adelantado con anteriorid lugar se presenta el método Donde, Intuitivamente, el prob encuentra determinado por la relación entre ambos términos. El término regularizador intenta imponer una suavidad en la imagen, mientras que el término de fidelidad intenta ajustar la imagen a la imagen ori La transición entre ambos comportamientos se controla mediante el peso del parámetro lambda. Si lambda toma un valor bajo, la imagen estará formada gradientes suaves, pero se habrá perdido todo el detalle de la imagen. S altos, la solución se ajustará a la imagen original, pero inexistente. Por su parte, el método TV en el término por regulador por la robusta norma L1. Ambos modelos son susceptibles del empleo de una sustitución como la presentada anteriormente mediante el empleo de resuelto con mediante una aproximación Particularizando el caso general para el filtrado de ruido en imágenes, ha adelantado con anteriorid ad al explicar los fundamentos matemáticos, lugar se presenta el método TV-ROF cuya expresión es la siguiente: Intuitivamente, el prob lema de minimización tras el filtrado de ruido se encuentra determinado por la relación entre ambos términos. El término regularizador intenta imponer una suavidad en la imagen, mientras que el término de fidelidad intenta ajustar la imagen a la imagen ori ginal introducida en el algoritmo. La transición entre ambos comportamientos se controla mediante el peso del parámetro lambda. Si lambda toma un valor bajo, la imagen estará formada gradientes suaves, pero se habrá perdido todo el detalle de la imagen. S i lambda toma valores ajustará a la imagen original, pero la eliminación de ruido será Por su parte, el método TV -L1 resulta similar, sustituyendo la norma cuadrática en el término por regulador por la robusta norma L1. Ambos modelos son susceptibles del empleo de una sustitución como la presentada anteriormente mediante el empleo de variables duales, resuelto con mediante una aproximación con anterioridad ruido en imágenes, como se explicar los fundamentos matemáticos, en primer lema de minimización tras el filtrado de ruido se encuentra determinado por la relación entre ambos términos. El término regularizador intenta imponer una suavidad en la imagen, mientras que el término de fidelidad ginal introducida en el algoritmo. La transición entre ambos comportamientos se controla mediante el peso del parámetro lambda. Si lambda toma un valor bajo, la imagen estará formada gradientes i lambda toma valores la eliminación de ruido será resulta similar, sustituyendo la norma cuadrática Ambos modelos son susceptibles del empleo de una sustitución como la variables duales, que puede ser con anterioridad . m´ın uZΩ|∇u|+λZΩ (u−f)2dΩ m´ın uZΩ|∇u|+λZΩ|u−f|dΩ Luis Llamas Binaburo Estimación online del Optical Flow 13 Denoise Los detalles del algoritmo s en el apartado 4. Los detalles del algoritmo s e presentan en Apéndice A Desarrollo Desarrollo Matemático, − u es la solución al método, es decir, la imagen tras el filtrado de ruido. − g es la imagen introducida en el algoritmo, es dec filtrar. − El término reg ulador tiene la forma habitual en los métodos de variación total. − E l término de fidelidad resulta imagen filtrada u, y la imagen origina es la solución al método, es decir, la imagen tras el filtrado de ruido. es la imagen introducida en el algoritmo, es dec ir, la imagen que se desea ulador tiene la forma habitual en los métodos de variación total. l término de fidelidad resulta la norma cuadrática de la diferencia entre la y la imagen origina l con ruido f. es la solución al método, es decir, la imagen tras el filtrado de ruido. ir, la imagen que se desea ulador tiene la forma habitual en los métodos de variación total. de la diferencia entre la Primal Dual comentado 3.2 Clase Denoise La Clase Denoise implementa los métodos ROF y TV-L1 para el filtrado de ruido. Pone a disposición del desarrollador métodos públicos para las siguientes tareas. − Inicializar el objeto a un tamaño de imagen determinado. − Introducir imagen a filtrar − Ejecutar el algoritmo de filtrado. − Obtener la imagen filtrada. La siguiente pantalla muestra el entorno de pruebas realizado para la Clase Denoise. El mismo permite cargar una imagen y realizar el proceso de eliminación de ruido. Los visores muestran la imagen antes y después del filtrado. Por su parte, los Sliders permiten variar la influencia del parámetro lambda y el número de iteraciones. Imagen 12. Entorno de pruebas Clase Denoise Las siguientes imágenes muestran el resultado de variar el parámetro lambda, que controla la transición entre término regularizador y término fidelidad. Lambda 2 Lambda 8 Lambda 20 Luis Llamas Binaburo Estimación online del Optical Flow 14 Denoise 3.3 Resultados 3.3.1 Comparación entre CPU y GPU La siguiente tabla recoge los tiempos de ejecución en milisegundos de las distintas etapas de la aplicación, para un tamaño de imagen fijo de 640x480 pixels y con 40 iteraciones de cálculo de Denoise. Individual Secuencial Concepto CPU GPU CPU GPU Iniciar Denoise 0,114 1,000 - - Introducir imagen 1,370 0,919 1,370 0,919 Mostrar imagen 17,368 15,068 - - Calcular Denoise 1184,58 6,338 1184,58 6,338 Resultado recibido 1,155 2,571 1,155 2,571 Mostrar resultado 13,341 6,624 - - Total 1217,928 42,827 1187,105 9,828 Relación CPU/GPU 28,44 120,79 Tabla 1. Comparación tiempos (ms) entre CPU y GPU Se observa que la implementación en GPU es 28,44 veces más rápida para el cálculo de una única imagen, incluyendo las etapas de inicialización de los objetos Denoise. Se hace notar que este resultado se muy penalizado por la etapa de mostrar ambas imágenes, que es una etapa relativamente lenta y que no puede ser acelerada mediante CPU, estando limitada por la librería OpenGL. En caso de ejecución continua, para una secuencia de imágenes, el cálculo resulta 120,79 veces más rápido. En particular, la etapa específica de cálculo del Denoise resulta 186,90 veces más rápida en la implementación realizada en GPU. Estos valores se muestran en la siguiente tabla. Se hace notar que la columna de la fase de cálculo en CPU, muy superior a las demás, no se representa a escala. Gráfica 1. Comparación tiempos (ms) entre CPU y GPU Iniciar CPU GPU 5 10 15 20 1185 Introducir Imagen Recibir resultado Mostrar resultado Calcular Mosrtar imagen Luis Llamas Binaburo Estimación online del Optical Flow 15 Tiempo ejecución (ms) Denoise 3.3.2 Influencia de los parámetros A continuación se diseña una serie de experimentos para caracterizar la influencia de los distintos parámetros que intervienen en el algoritmo en el tiempo de ejecución global del mismo. Los tiempos representados muestran el proceso completo, incluyendo captura de imágenes, cálculo de Denoise, y visualización de resultados. En primer lugar se determina la relación con el tamaño de la imagen, medida en número de pixels. Gráfica 2.Relación entre tiempo (ms) y tamaño de imagen. A continuación se determina la relación con el número de iteraciones realizada en el proceso de eliminación de ruido. Gráfica 3.Relación entre tiempo (ms) e iteraciones. 160x120 320x240 480x360 640x480 800x600 1024x768 0 10 20 30 40 50 60 70 80 90 Luis Llamas Binaburo Estimación online del Optical Flow 16 10 25 40 50 75 100 150 0 10 20 30 40 50 60 70 80 90 Tiempo ejecución (ms)Tiempo ejecución (ms) Tamaño imagen Iteraciones Denoise Las siguientes imágenes muestran el resultado de variar el parámetro lambda, que controla la transición entre término regularizador y término fidelidad. Lambda 4 Lambda 10 Lambda 20 4.4 Esquema de funcionamiento La siguiente figura muestra el esquema de funcionamiento del algoritmo, en especial la aproximación “coarse to fine”, y el papel de la Clase Pirámide en el mismo. Imagen 17. Esquema de funcionamiento Optical Flow Durante la fase de inicialización se generan las pirámides necesarias para almacenar las dos imágenes de entrada y todas las soluciones. Estas estructuras se crean al principio, de forma que durante la ejecución continua no sea necesario la reserva de memoria dinámica adicional, lo cual es un proceso costoso. Al introducir las imágenes de entrada en la base de ambas pirámides, estas se rellenan en sentido ascendente y se inicializa el nivel superior de las pirámides de soluciones a cero. Posteriormente, empezando por el nivel superior y de forma iterativa, se cargan las variables del nivel actual desde las distintas pirámides y se realiza el cálculo del Optical Flow con el número de iteraciones establecido para el cálculo de cada nivel. Finalmente se guardan los resultados en las pirámides, propagando sus valores, dejando la estructura lista para el cálculo del siguiente nivel. Al finalizar del algoritmo los resultados están disponibles en la parte inferior de las pirámides, si bien resta codificados y normalizados para poder ser visualizados. UP DOWN qxx qxy qyx qyy pxpy vxvy u Luis Llamas Binaburo Estimación online del Optical Flow 23 Frame 1 Frame 2 Iluminación Velocidad Optical Flow Step Optical Flow Variables internas Pirámides de soluciones Pirámides de imágenes Cargar Cargar Salvar Optical Flow 4.5 Resultados 4.5.1 Comparación entre CPU y GPU La siguiente tabla recoge los tiempos de ejecución en milisegundos de las distintas etapas de la aplicación para un tamaño de imagen fijo 640x480 pixels y con 50 iteraciones de cálculo de Optical Flow en cada nivel de pirámide. Individual Secuencial Concepto CPU GPU CPU GPU Iniciar Optical Flow 0,202 62,371 - - Introducir Frame 1 6,972 1,528 6,972 1,528 Introducir Frame 2 6,447 1,766 6,447 1,766 Calculo recibido 6250,590 29,267 6250,590 29,267 Resultado recibido 49,459 7,957 62,745 8,557 Iluminación recibida 6,826 6,624 20,287 6,624 Mostrar imagen 1 28,763 16,229 - - Mostrar imagen 2 22,820 12,878 - - Mostrar resultado 8,768 8,737 - - Mostrar iluminación 8,968 8,884 - - Total 6389,613 93,87 6347,041 47,742 Relación CPU/GPU 68,07 132,94 Tabla 2. Comparación tiempos (ms) entre CPU y GPU Se observa que la implementación en GPU es 68,07 veces más rápida para el cálculo entre dos imágenes individuales, incluyendo etapas de inicialización. En caso de ejecución continua para una secuencia de imágenes, el cálculo resulta 132,94 veces más rápido. En particular, la etapa específica de cálculo del Optical Flow resulta 213,57 veces más rápida en la implementación realizada en GPU. Estos valores se muestran en la siguiente tabla. Se hace notar que la columna de la fase de cálculo en CPU, muy superior a las demás, no se representa a escala. Gráfica 7. Comparación tiempos (ms) entre CPU y GPU Iniciar CPU GPU 20 40 60 80 6250 Introducir Frame 1 Introducir Frame 2 Mostrar imagen 1 Mostrar imagen 2 Calcular Calcular Resultado Calcular Iluminacion Mostrar resultado Mostrar Iluminacion Luis Llamas Binaburo Estimación online del Optical Flow 24 Tiempo ejecución (ms) Optical Flow 4.5.2 Influencia de los parámetros A continuación se diseña una serie de experimentos para caracterizar la influencia de los distintos parámetros que intervienen en el algoritmo en el tiempo de ejecución global del mismo. Los tiempos representados muestran el proceso completo, incluyendo captura de imágenes, cálculo Optical Flow, y visualización de resultados. En primer lugar se determina la relación con el tamaño de la imagen, medida en número de pixels. Se observa una relación fuertemente lineal entre ambas variables. Gráfica 8.Relación entre tiempo (ms) y tamaño de imagen. A continuación se determina la relación entre el número de iteraciones realizada por nivel de pirámide. Nuevamente se observa una relación fuertemente lineal entre ambas variables. Gráfica 9.Relación entre tiempo (ms) e iteraciones. 10 25 40 50 75 100 150 0 50 100 200 300 400 160x120 320x240 480x360 640x480 800x600 1024x768 0 50 100 150 200 300 400 Luis Llamas Binaburo Estimación online del Optical Flow 25 Tiempo ejecución (ms)Tiempo ejecución (ms) Tamaño imagen Iteraciones Optical Flow Para determinar la eficacia en la estimación de movimiento mediante el algoritmo realizado, se dispone de una serie de de entra da y la solución exacta de la estimación de movimiento, que denominaremos Ground Truth . A continuación se muestra las imágenes y resultados obtenidos para una de las muestras empleadas Frame 1 Resul tado con Lambda 20 Imagen 18 Se observa que con lambda a la solución Ground Truth de limitaciones propias del algoritmo, y no no pueden ser eliminadas con los métodos empleados en el presente proyecto. Para determinar la eficacia en la estimación de movimiento mediante el algoritmo realizado, se dispone de una serie de muestras que incluyen ambas imágenes da y la solución exacta de la estimación de movimiento, que denominaremos . A continuación se muestra las imágenes y resultados obtenidos para una empleadas , Frame 1 Frame 2 Resultado con Lambda 5 tado con Lambda 20 Resultado con Lambda 40 18 . Comparación resultados con Grounded Image Se observa que con lambda 15 a 25 se obtienen resultados altamente ajustados Ground Truth proporcionada. Las pequeñas difer encias restantes resultan propias del algoritmo, y no de la implementación realizada. Por tanto no pueden ser eliminadas con los métodos empleados en el presente proyecto. Para determinar la eficacia en la estimación de movimiento mediante el muestras que incluyen ambas imágenes da y la solución exacta de la estimación de movimiento, que denominaremos . A continuación se muestra las imágenes y resultados obtenidos para una Resultado con Lambda 5 Resultado con Lambda 40 15 a 25 se obtienen resultados altamente ajustados encias restantes resultan de la implementación realizada. Por tanto no pueden ser eliminadas con los métodos empleados en el presente proyecto. Luis Llamas Binaburo Estimación online del Optical Flow 26 Ground Truth Optical Flow 4.6 Comparación con Ground Truth Ground Truth 4.6.1 Zona tiempo real Finalmente, se desea caracterizar la relación entre tiempo, tamaño de imagen e iteraciones, para determinar una zona dentro de la cual la se consigue la ejecución en tiempo real. A estos efectos, se considera tiempo real a velocidades de refresco de 1020 frames por segundo, lo que implica tiempos de ejecución de 50 a 100 ms por frame. Para ello se diseña y ejecuta una serie muti variable de experimentos. Se ha optado por este método, en lugar de la interpolación a partir de los resultados previos, para eliminar la posible interferencia entre los efectos de ambos parámetros. Los resultados obtenidos se muestran en la siguiente tabla, donde se ha sombreado en amarillo la zona de tiempo real. Gráfica 10. Zona tiempo real Optical Flow Se comprueba que con menos de 10 iteraciones el método presenta problemas importantes de convergencia. Por otro lado, la ejecución de más 50 iteraciones resulta innecesaria dado que no se observa una mejora sustancial de la solución obtenida. Adicionalmente se observa la obtención de mejores resultados fijando un número de iteraciones relativamente bajo, pero que permita conseguir elevadas tasa de refresco. Esto permite la aparición de menores desplazamientos entre cuadros lo que favorece la convergencia, más que aumentar el número de iteraciones. Con estos datos, la implementación realizada y el equipo empleado, se considera que el punto óptimo es 640 x 480 a 15 fps, con 25 iteraciones por nivel. La ejecución en un equipo con una tarjeta superior o una implementación con un número menor de visualizadores aumentaría aún más la velocidad de ejecución. 0 10 25 40 50 75 100 160x120 320x240 50ms 100ms 640x480 800x600 1020x768 150ms 200ms 300ms 400ms 500ms 480x320 Zona RT Zona Online Luis Llamas Binaburo Estimación online del Optical Flow 27 Tamaño imagen Iteraciones Optical Flow 5 Conclusiones Luis Llamas Binaburo Estimación online del Optical Flow 28 Conclusiones Durante el desarrollo del presente proyecto se han conseguido los siguientes objetivos y resultados: − Se ha realizado la implementación de Denoise, en Matlab, en CPU y en GPU. − Se ha realizado la implementación del modelo TV-ROF y TV-L1 de Denoise, tanto en CPU como en GPU. − Se ha realizado la implementación del Optical Flow tanto en CPU como en GPU. − Se ha optimizado ambas aplicaciones en GPU hasta conseguir la ejecución en tiempo real mediante imágenes con una webcam. − Para ambas aplicaciones se ha caracterizado la relación entre tiempo y tamaño de la imagen, y tiempo entre número de iteraciones. − Para ambas aplicaciones se ha determinado la eficacia de los métodos empleados. En el caso de Denoise mediante el cálculo del SNR, y en el caso del Optical Flow mediante comparación con la solución Ground Truth. − Para ambas aplicaciones se ha obtenido una región de RT, como representación de la relación entre ambos parámetros para que la ejecución se realice en tiempo real. − Se han generado las herramientas y clases suficientes que permitan la reutilización del trabajo realizado en futuros proyectos y aplicaciones. Por tanto, se consideran correctamente conseguidos la totalidad de objetivos que motivan el presente proyecto. 5.1 Trabajos futuros Movidos por el éxito en la consecución de los objetivos se considera interesante presentar los siguientes trabajos como ejemplos de futuras aplicaciones o ampliaciones que resultarían interesantes de realizar en próximos proyectos: − Extender los algoritmos presentados para el tratamiento de imágenes en color. − Modificar las aplicaciones para su ejecución remota, permitiendo adquirir las imágenes con un dispositivo móvil, mientras que el cálculo se realiza en un equipo independiente de elevada potencia, tal como el cluster HERMES del I3A. − Combinar los algoritmos presentados con un sistema detección de blobs que permita reducir o eliminar el problema de falta de textura. − Extender el algoritmo para Scene Flow [AW11], que consiste en obtener la velocidad de cada punto 3D de la escena mediante visión estereoscópica. − Emplear las clases implementadas en una aplicación práctica, tal como un videojuego, el sistema de posicionamiento de un robot, o un sistema de detección de obstáculos para vehículos en movimiento. Luis Llamas Binaburo Estimación online del Optical Flow APÉNDICE A. DESARROLLO MATEMÁTICO Luis Llamas Binaburo Estimación online del Optical Flow 29 Apéndice A Luis Llamas Binaburo Estimación online del Optical Flow En un caso general, la aplicaci´on de los m´etodos variacionales consisten en la resoluci´on de funciones de la familia Donde el t´ermino regularizador F(∇u), impone condiciones de suavidad en la imagen, mientras que el t´ermino de fidelidad G(u), o data term, ajusta la soluci´on obtenida a las condiciones de entrada. La transici´on entre ambos comportamientos se controla mediante el par´ametro lambda. El m´etodo presenta dentro un ampli rango de problemas t´ıpicos en vision por computador. La diferencia entre su aplicaci´on a uno u otro caso depende de la forma adoptada por las funciones FyGque deben ser particularizadas para cada aplicaci´on en concreto. Con objeto de simplificar la presentaci´on del m´etodo general, y por sencillez, se ilustrar´a el modelo particularizado para el caso de filtrado de ruido. En su formulaci´on m´as sencilla, aplicando la regularizaci´on de Tikhonov, se obtiene la siguiente expresi´on. m´ın uZΩ (∇u)2dΩ + λZΩ (f−u)2dΩ) (2) TV (u) = ZΩ|∇u|dΩ (3) 30 Luis Llamas Binaburo Estimación online del Optical Flow 1 Planteamiento del método 1.1 Caso general 1.2 Modelo Tikhonov 1.3 Modelo TV-ROF Planteamiento del método m´ın uZΩ F(∇u) + λZΩ G(u)(1) Denotaremos a esta ecuaci´on como el modelo Tikhonov, donde el t´ermino regularizador tiene la forma (∇u)2y el t´ermino fidelidad resulta (u−f)2. Los metodos de variaci´on total en visi´on presentan una mejora del m´etodo anterior. Su formulaci´on general resulta de la aplicaci´on como regularizador de la variaci´on total de la se˜nal o imagen TV(u) definida por Los primeros en introducir los m´etodos de variaci´on total a los problemas de visi´on fueron Rudi, Osher y Fatemi (ROF) en su art´ıculo sobre la eliminaci´on de ruido preservando los contornos [LO92]. El modelo es capaz de eliminar ruido y otros detalles de peque˜na escala indeseados, mientras que preserva las discontinuidedes pronuciadas, tales comos los contornos. La funci´on δP indica la funci´on indicadora del conjunto Pque est´a definido como δP(p) = 0 si p∈P +∞si p /∈P Adicionalmente, el problema ROF primal ROF y el problema ROF primaldual son equivalentes al problema ROF dual m´ax p∈Y−1 2λ+||div p||2 2+hg, div piX+δP(p)(34) Resta por resolver los operadores (I+σδF?)−1y (I+τδG)−1. Identificando t´erminos con la formulaci´on general se observa que F?(p) = δP(p) y G(u) = λ 2||u−g||2 2. Dado que F?es la funci´on idnicadora del conjunto convexo, el operador se reduce a la proyecci´on Euclidea en bolas L2 p= (I+σδF ?)−1(ˆp)⇐⇒ pi,j =ˆpi,j max(1,|ˆpi,j|)(35) La resoluci´on del operador respecto a Gest´a dada por u= (I+τδG)−1(ˆu)⇐⇒ ui,j =ˆpi,j +τλgi,j 1 + τλ (36) En el caso del modelo TV-L1, obtenido mediante una variaci´on del modelo ROF reemplazando la norma cuadr´atica L2en el t´ermino de fidelidad por la robusta norma L1. m´ın xZΩ|Du|+λ 2||u−g||1(37) La versi´on discreta est´a dada por m´ın u∈X||∇u||1+λ||u−g||1(38) u= (I+τδG)−1(ˆu)⇐⇒ ui,j =   ˆui,j −τλ si ˆui,j −τλ > τλ ˆui,j +τλ si ˆui,j −τλ < −τλ gi,j si |ˆui,j −τλ| ≤ τλ 37 Luis Llamas Binaburo Estimación online del Optical Flow Denoise Donde la resoluci´on de respecto a pes id´entica al caso ROF, y la resoluci´on del operador respecto a Gviene dada por El siguiente esquema muestra el diagrama de flujo para la Clase Denoise, donde cada una de las etapas se detallan posteriormente. 38 Luis Llamas Binaburo Estimación online del Optical Flow 4.3 Esquema algoritmo Dual Primal Actualizar parametros U_hat p ˆu ˆu Num Iteraciones p u ˆu u Imagen a filtrar g for... Imagen filtrada u Denoise A continuaci´on se recogen las ecuaciones que integran cada una de las etapas de la Clase Denoise Update Dual Calculo de la variable Dual p p=p+σ·∇ˆu(39) Normalizaci´on aplicando la restricci´on |p| ≤ 1 pnorm =qp2 x+p2 y p=p/max(1, pnorm) (40) Update Primal Calculo de la variable Primal ˆu uant =u(41) ˆu=u+τ∇·p(42) En el caso de aplicar el modelo TV-ROF aplicar la ecuaci´on u=ˆu+τ·λ·g 1 + τ·λ(43) u=   ˆu−τλ si ˆu−τλ > τλ ˆu+τλ si ˆu−τλ < −τλ gsi |ˆu−τλ| ≤ τλ Update parameters Actualizaci´on de los par´ametros para siguiente iteraci´on θ=1 √1+2γτ (44) τ=τ·θ(45) σ=σ/θ (46) Calculate Uhat Calculo de ˆu ˆu=u+θ·(u−uant) (47) 39 Luis Llamas Binaburo Estimación online del Optical Flow 4.4 Ecuaciones algoritmo Denoise Para el modelo TV-L1 la resoluci´on de respecto a psustituir la expresi´on anterior por La discretizaci´on detallada de las ecuaciones que integran la formulaci´on de las distintas etapas de la Clase Denoise son las siguientes: Update Dual Calculo de la variable Dual pi,j px(i,j)=px(i,j)+σ(ui+1,j −ui,j) py(i,j)=py(i,j)+σ(ui,j+1 −ui,j ) (48) Normalizaci´on aplicando la restricci´on pi,j ≤1 pnorm(i,j)=qp2 x(i,j)+p2 y(i,j) p(i, j) = p(i, j)/max(1, pnorm(i,j)) (49) Update Primal Calculo de la variable Primal u(i,j) uant(i,j)=u(i,j) ˆu(i,j)=u(i,j)+τ[p(i,j)−p(i−1,j)+p(i,j)−p(i,j−1)] (50) En el caso de aplicar el modelo TV-ROF aplicar la ecuaci´on u(i,j)=ˆu(i,j)+τ·λ·g(i,j) 1 + τ·λ(51) Donde la resoluci´on de respecto la Pes id´entica al caso ROF, y la resoluci´on del operador respecto a Gviene dada por ui,j =   ˆui,j −τλ si ˆui,j −τλ > τλ ˆui,j +τλ si ˆui,j −τλ < −τλ gi,j si |ˆui,j −τλ| ≤ τλ Update parameters Actualizaci´on de los par´ametros para siguiente iteraci´on θ=1 √1+2γτ τ=τ·θ σ=σ/θ (52) Calculate Uhat Calculo de ˆu(i,j) ˆu(i,j)=u(i,j)+θ·u(i,j)−uant(i,j)(53) 40 Luis Llamas Binaburo Estimación online del Optical Flow 4.5 Ecuaciones algoritmo discretizadas Denoise El planteamiento general para los m´etodos variacionales aplicados a la estimaci´on de movimiento est´a dando por m´ın vZΩ|Dv|+λ||ρ(v)|| (54) donde v= (v1, v2)T: Ω →R2es el campo vectorial que recoge las componentes estimadas de velocidad, y ρ(v) es la restricci´on tradicional del Optical Flow (OFC). El par´ametro λes nuevamente empelada para definir la transici´on entre regularizaci´on y fidelidad. Para obtener la expresi´on de la restrici´on OFC consideremos en primer lugar la imagen como una funci´on que codifica la intensidad de cada pixel de la imagen como una funci´on del espacio y el tiempo. Imagen =I(x(t), t) (55) La restricci´on tradicional del Optical Flow queda dado por la siguiente expresi´on, d dtI(x(t), t) = 0 (56) Esta restricci´on es obtenida asumiento que las intensidades de los pixeles permanenecen invariantes en el tiempo. Realizando la expansi´on del t´ermino diferencial de la restrici´on OFC resulta d dtI(x(t), t) = dI dXu dXu dt +dI dXv dXv dt (57) Definiendo los siguientes operadores ∇I=dI dXu ,dI dXuT (58) dXu t,dXu t= (v−v0) (59) La restricci´on OFC puede ser reescrita mediante la siguiente expresi´on It+∇I(v−v0) = 0 (60) Por lo que el t´ermino de fidelidad buscado resulta ρ(v) = It+ (∇I)T(v−v0) (61) donde v= (v1, v2)T: Ω →R2es el campo vectorial que recoge las componentes estimadas de velocidad, Ites la variaci´on temporal de la secuencia de la secuencia de im´agenes, ∇Ies el gradiente espacial de la imagen y v0es una condici´on inicial dada. 41 Luis Llamas Binaburo Estimación online del Optical Flow 5 Optical Flow 5.1 Planteamiento Optical Flow En situaciones pr´acticas, no obstante, es altamente improbable debido a los cambios en la iluminaci´on que los intensidades de los pixels permanezcan constantes en el tiempo. Esto motiva la siguiente mejora en la restricci´on OFC, que de forma expl´ıcita modeliza la variaci´on de la iluminaci´on en t´erminos de una funci´on aditiva u ρ(u, v) = It+ (∇I)T(v−v0) + βu (62) La funci´on u: Ω →Res presumiblemente suave, y por tanto puede ser tambi´en regularizada mediante m´etodos de variaci´on total. El par´ametro βcontrola la influencia del t´ermino de iluminaci´on. El modelo de estimaci´on de movimiento mejorado est´a dado por m´ın vZΩ|Du|+ZΩ|Dv|+λ||ρ(u, v)|| (63) No obstante, la restricci´on OFC es ´unicamente v´alida para peque˜nos desplazamientos v−v0. En orden de extender el m´etodo para grandes desplazamientos, todo el m´etodo debe ser integrado dentro de una aproximaci´on tipo ¸coarse-fine”, que re-estime iterativamente las condiciones iniciales v0entre los distintos niveles que integren el algoritmo. Tras la discretizaci´on se obteniene la siguiente formulaci´on dual para el modelo de estimaci´on de movimiento m´ın u∈X,v∈Y||∇u||1+||∇v||1+λ||ρ(u, v)||1(64) donde la versi´on discreta de la restricci´on OFC mejorada est´a dada por ρ(ui,j, vi,j )=(It)i,j + (∇I)T i,j(vi,j −v0(i,j)) + βui,j (65) El gradiente vectorial (∇v) = (∇v1,∇v2) existe en el espacio Z=Y×Y equipado con el producto escalar hq, riZ=X i,j q1 i,jr1 i,j +q2 i,jr2 i,j +q3 i,jr3 i,j +q4 i,jr4 i,j (66) q= (q1, q2, q3, q4)∈Z(67) r= (r1, r2, r3, r4)∈Z(68) y la norma ||∇v||1=X i,j |∇vi,j|(69) |∇vi,j|=q((∇v1)1 i,j)2+ ((∇v1)2 i,j)2+ ((∇v2)1 i,j)2+ ((∇v2)2 i,j)2(70) 42 Luis Llamas Binaburo Estimación online del Optical Flow 5.2 Discretización Optical Flow La formulaci´on del problema primal se obtiene como m´ın u∈X,v∈Ym´ax p∈Y,q∈Zh∇u, piY+h∇v, qiZ+λ||ρ(u, v)||−δP(p)−δQ(q) (71) donde los conjuntos convexos PyQest´an definido como P={p∈Y:||p||∞≤1} Q={q∈Z:||q||∞≤1} y||q||∞es la norma m´axima discreta definida en Zcomo ||q||∞= m´ax i,j |qi,j,|qi,j |=q(q1 i,j)2+ (q2 i,j)2+ (q3 i,j)2+ (q4 i,j)2 Identificando t´erminos con el caso general resulta G(u, v) = λ||ρ(u, v)||1y F?(p, q) = δP(p) + δQ(q). La resoluci´on del operador con respecto a F?(p, q) est´a nuevamente dado por la proyecci´on simple dentro de bolas L2. (p, q)=(I+σδF?)−1(ˆp, ˆq) pi,j =ˆpi,j m´ax(1,|ˆpi,j|)qi,j =ˆqi,j m´ax(1,|ˆqi,j |) La resoluci´on para G(u, v) est´a dada por (I+τ∂G)−1(ˆu, ˆv) = λ|ρ(u, θ)|(72) arg m´ın u,v =ku−ˆuk2 2τ+kv−ˆvk2 2τ+G(u, v) (73) Resulta conveniente definir a= [∇I, β]Tyb= [v−v0, u]T, con lo que la restricci´on OFC puede ser reescrita en la forma m´as compacta ρ(u, v) = It+∇IT(v−v0) + βu =⇒ρ(b) = It+aTb(74) Por lo que la resoluci´on del operador G(u, v) puede ser expresado mediante arg m´ın b=kb−ˆ bk2 2τ+λ|ρ(b)|(75) Considerando la versi´on discreta dada por ai,j = (β, (∇I)i,j) y |a|2 i,j =β2+ |∇I|2 i,j, la soluci´on al operador est´a entonces definida por (ui,j, vi,j ) = (ˆui,j,ˆvi,j)+    τλai,j si ρ(ˆui,j ,ˆvi,j)<−τλ|a|2 i,j −τλai,j si ρ(ˆui,j ,ˆvi,j)>−τλ|a|2 i,j −ρ(ˆui,j,ˆvi,j)ai,j /|a|2 i,j si |ρ(ˆui,j,ˆvi,j)| ≤ −τλ|a|2 i,j 43 Luis Llamas Binaburo Estimación online del Optical Flow Optical Flow Los siguientes esquemas muestran el diagrama de flujo de la Clase Optical Flow. En primer lugar se rellenan las pir´amides que contienen las im´agenes de entrada y las soluciones del algoritmo y se inicializan las variables necesarias para realizar el c´alculo. A continuaci´on se implementa la aproximaci´on ¸coarse to fine”del algoritmo. Para todos los niveles de las pir´amides, empezando por la parte superior, se realiza el Optical Flow y se propagan las soluciones para el nivel siguiente. Al final se realiza el ´ultimo paso, dejando las soluciones en la parte inferior de los objetos Pir´amide. 44 Luis Llamas Binaburo Estimación online del Optical Flow 5.3 Esquema algoritmo Step Propagate Rellenar piramides Step Iniciar variables for... Niveles pirámide Frame 2 Frame 1 Iluminación Velocidad Optical Flow La etapa Step se detalla en el siguiente esquema. En cada paso de c´alculo se cargan las variables desde los distintos objetos Pir´amide que contiene el objeto Optical Flow. A continuaci´on se realiza el proceso de c´alculo de Igrad que realiza el c´alculo de It,Ix,Iy, variables necesarias para el c´alculo de rho. Estas variables se obtienen mediante la diferencia del frame 2, y el frame 1 deformado seg´un el campo de velocidad en cada paso del Optical Flow (proceso de wrapping), obtenido mediante interpolaci´on lineal. Posteriormente se realiza el c´alculo del paso, aplicando el n´umero de iteraciones definidas para cada nivel del Optical Flow. Por ´ultimo se salvan las variables en las pir´amides. 45 Luis Llamas Binaburo Estimación online del Optical Flow I_grad Calcular Salvar variables Cargar variables Step Num Iteraciones for... Optical Flow Finalmente, la etapa de c´alculo se detalla en el siguiente esquema. 46 Luis Llamas Binaburo Estimación online del Optical Flow Dual Primal Rho U_hat Calcular pqxqy ˆuˆvxˆvy pqxqy uvxvy uvxvy ˆuˆvxˆvy Optical Flow