Repositorio Institucional de Documentos

Resumen En el campo de la teor´ıa de se˜nal, el muestreo y la compresi´on siempre han sido puntos claves. El teorema de muestreo de Nyquist-Shannon es fundamental, especialmente en el campo de las telecomunicaciones. Este teorema establece que la reconstrucci´on exacta de una se˜nal continua en banda base y limitada en banda a partir de sus muestras, es posible siempre y cuando su frecuencia de muestreo sea igual o superior al doble de su ancho de banda. Esto supone una barrera a la hora de muestrear ciertas se˜nales de frecuencia elevada, ya que empiezan a aparecer limitaciones en el hardware necesario. Recientemente se ha estado desarrollando un nuevo campo en teor´ıa y procesado de se˜nal llamado compressive sensing. La teor´ıa de compressive sensing establece que una se˜nal puede reconstruirse perfectamente incluso cuando es muestreada a frecuencias menores que las establecidas por el teorema de Nyquist siempre que sea lo suficientemente dispersa (sparse seg´un el t´ermino en ingl´es), esto es, que gran parte de los coeficientes en su representaci´on en el dominio de alguna base sean cero, y el muestreo cumpla una serie de condiciones. Para poder trabajar en este marco, es pues necesario transformar la se˜nal a una base (tambi´en llamadas diccionarios) en la que sea sparse. Una vez se cuenta con este diccionario, y conociendo el patr´on de muestreo, es posible reconstruir la se˜nal original a partir de una versi´on muestreada por debajo del l´ımite de Nyquist de la misma mediante la resoluci´on de un problema de minimizaci´on L1. Uno de los campos de aplicaci´on de esta teor´ıa es la captura de v´ıdeo de alta resoluci´on temporal. Las c´amaras de v´ıdeo est´an limitadas por diversos factores hardware y para capturar v´ıdeos de gran resoluci´on espacial a altas velocidades se requiere material altamente especializado. Una alta resoluci´on temporal es una necesidad para el estudio de ciertos fen´omenos como el comportamiento de fluidos o tejidos bajo ciertas condiciones externas o la observaci´on de fracturas de materiales. En este proyecto se aborda el problema de la captura de v´ıdeo de alta resoluci´on tanto temporal como espacial desde la perspectiva de la teor´ıa de compressive sensing. El objetivo es explotar su potencial para lograr reconstruir un v´ıdeo completo a partir de una ´unica imagen en la que se encuentra codificada la informaci´on temporal. Esto se consigue realizando la captura del v´ıdeo con una exposici´on codificada, es decir, muestreando diferentes p´ıxeles en cada fotograma en funci´on del tiempo, para despu´es recuperar toda la informaci´on necesaria para reconstruir el v´ıdeo completo mediante procesado basado en compressive sensing. 1 Agradecimientos Este proyecto ha sido desarrollado dentro del Graphics and Imaging Lab, perteneciente al Grupo de Inform´atica Gr´afica Avanzada (GIGA) de la Universidad de Zaragoza. Me gustar´ıa expresar mi gratitud hacia mi directora de proyecto, Bel´en Masi´a por su inestimable direcci´on y ayuda, lo que ha hecho el desarrollo de este proyecto un proceso interesante y altamente gratificante. Me gustar´ıa agradecer tambi´en a Diego Guti´errez por introducirme en el mundo de la inform´atica gr´afica y por la oportunidad de trabajar en su grupo. Tambi´en quiero extender mi agradecimiento a todo el GIGA por su acogida y ayuda. Por otra parte, me gustar´ıa agradecer al departamento de inform´atica de la universidad Rey Juan Carlos de Madrid por aportar algunos de los v´ıdeos utilizados en este proyecto, en particular a Miguel ´ Angel Otaduy y David Miraut. Tambi´en al departamento de Laser & Optical Technologies del instituto universitario de investigaci´on en ingenier´ıa de Arag´on (I3A), en concreto a Mar´ıa Pilar Arroyo por facilitarme el equipamiento, y a Laura Ar´evalo y Eva Roche por ayudarme a capturar el resto de los v´ıdeos utilizados. A nivel personal, quiero agradecer su continuo apoyo durante toda la carrera a mi familia y amigos, en especial a mis padres, que siempre me han apoyado a pesar de los malos momentos, y a mi compa˜nero Samuel Navarro ya que sin su ayuda no hubiese llegado hasta aqu´ı. Por ´ultimo, me gustar´ıa dar las gracias a todos los profesores que han aportado algo a mi formaci´on a lo largo de todo el trayecto, como persona y como ingeniera. 3 ´ Indice 1. Introducci´on 9 1.1. Objetivo, alcance y contexto del proyecto . . . . . . . . . . . . . . . . . . . . . . 9 1.2. Organizaci´on del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3. Planificaci´on ...................................... 12 2. Trabajo relacionado 13 3. Compressive sensing: marco te´orico 17 3.1. Ejemplo de aplicaci´on: Se˜nales unidimensionales . . . . . . . . . . . . . . . . . . 19 4. Captura de v´ıdeo mediante compressive sensing 21 4.1. Introducci´on....................................... 21 4.2. Diccionario ....................................... 24 4.3. Matrizdemedida.................................... 25 4.3.1. Limitaciones hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.3.2. Funciones del obturador . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4. Reconstrucci´on ..................................... 28 4.4.1. Detalles de la implementaci´on . . . . . . . . . . . . . . . . . . . . . . . . . 29 5. Adquisici´on de una base de datos 31 6. An´alisis de par´ametros 33 6.1. Introducci´on....................................... 33 6.2. Caracter´ısticas espacio-temporales de los v´ıdeos usados en el an´alisis . . . . . . . 35 6.3. Selecci´on del tama˜no de bloque de v´ıdeo . . . . . . . . . . . . . . . . . . . . . . . 39 6.3.1. Tama˜no espacial del bloque de v´ıdeo . . . . . . . . . . . . . . . . . . . . . 39 6.3.2. Tama˜no temporal del bloque de v´ıdeo . . . . . . . . . . . . . . . . . . . . 41 6.4. Diccionario ....................................... 42 6.4.1. Diccionario entrenado vs DCT . . . . . . . . . . . . . . . . . . . . . . . . 43 6.4.2. M´etodo de selecci´on de bloques de entrenamiento . . . . . . . . . . . . . . 44 6.5. Algoritmo de reconstrucci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.6. Matriz de medida: funci´on del obturador . . . . . . . . . . . . . . . . . . . . . . . 47 7. Resultados 51 8. Conclusiones y trabajo futuro 55 Bibliograf´ıa 57 5 A. Propiedades de la matriz de medida 61 A.1.Incoherencia....................................... 61 A.2. RIP: Restricted Isometry Property . . . . . . . . . . . . . . . . . . . . . . . . . . 61 B. Entrenamiento de diccionarios: Algoritmo K-SVD 63 B.1.Introducci´on....................................... 63 B.2.AlgoritmoK-SVD ................................... 64 C. Algoritmos OMP y LASSO 67 C.1. LASSO: Least Absolute Shrinkage and Selection Operator . . . . . . . . . . . . . 67 C.2. OMP: Orthogonal Matching Pursuit . . . . . . . . . . . . . . . . . . . . . . . . . 68 D. ´ Indice de v´ıdeos utilizados en el proyecto 71 D.1. V´ıdeos de entrenamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 D.2. V´ıdeos originales del an´alisis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 D.3.V´ıdeosreconstruidos.................................. 74 E. Caracterizaci´on de los v´ıdeos utilizados durante el an´alisis 77 6 ´ Indice de figuras 1.1. Esquema de la single pixel camera [1] ........................ 10 1.2. Esquema b´asico de captura de v´ıdeo mediante compressive sensing......... 11 1.3. Diagrama de Gantt de las actividades realizadas a lo largo del proyecto. . . . . . 12 2.1. Matriz de 52 c´amaras de Wilburn . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2. Diagrama temporal para diferentes tipos de shutter. Figura de [2]. . . . . . . . . 15 2.3. C´amara con apertura codificada de [3]. . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1. Ecuaci´on fundamental de compressive sensing. ................... 18 3.2. Transformada de Fourier de una se˜nal unidimensional [4]. . . . . . . . . . . . . . 19 3.3. Se˜nal unidimensional muestreada en el dominio temporal [4]. . . . . . . . . . . . 20 4.1. Proceso de captura de un v´ıdeo en una sola imagen . . . . . . . . . . . . . . . . . 22 4.2. Arquitectura del sistema de captura y reconstrucci´on de v´ıdeo mediante compressive sensing........................................ 23 4.3. Muestra de los v´ıdeos de entrenamiento . . . . . . . . . . . . . . . . . . . . . . . 24 4.4. Fotogramas de un ´atomo aleatorio de un diccionario entrenado. . . . . . . . . . . 25 4.5. Limitaciones hardware de la matiz de medida . . . . . . . . . . . . . . . . . . . . 26 4.6. Funciones del obturador (shutters) para el muestreo de v´ıdeo. . . . . . . . . . . . 27 4.7. Normas L1yL2. .................................... 29 4.8. Subdivisi´on en parches solapados para la reconstrucci´on. . . . . . . . . . . . . . . 30 5.1. Montaje para la captura de v´ıdeo con la c´amara Photron SA2 en el I3A . . . . . 32 6.1. Fotograma representativo extra´ıdo de cada uno de los v´ıdeos utilizados en el an´alisis. 35 6.2. Caracterizaci´on del v´ıdeo Coke. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.3. Histograma de los ratios de energ´ıa de alta frecuencia temporal Hratios para cada uno de los v´ıdeos utilizados en el an´alisis. . . . . . . . . . . . . . . . . . . . . . . 37 6.4. PSNR y MS-SSIM de las reconstrucciones para el diccionario por defecto . . . . 38 6.5. Ejemplo de reconstrucci´on con el diccionario por defecto . . . . . . . . . . . . . . 38 6.6. MS-SSIM de la reconstrucci´on en funci´on del tama˜no espacial del bloque . . . . . 39 6.7. PSNR de la reconstrucci´on en funci´on del tama˜no espacial del bloque . . . . . . 40 6.8. Tiempo medio de la reconstrucci´on del v´ıdeo en funci´on del tama˜no espacial del bloque........................................... 40 6.9. MS-SSIM de la reconstrucci´on en funci´on del tama˜no temporal del bloque. . . . . 41 6.10. PSNR de la reconstrucci´on en funci´on del tama˜no temporal del bloque. . . . . . 42 6.11. Tiempo medio de la reconstrucci´on del v´ıdeo en funci´on del tama˜no temporal del bloque........................................... 42 7 6.12. Comparaci´on del PSNR de los resultados utilizando un diccionario aprendido o eldiccionarioDCT.................................... 43 6.13. PSNR en funci´on del m´etodo de selecci´on utilizado para escoger los bloques de entrenamiento. ..................................... 46 6.14. Comparaci´on del PSNR de los resultados para diferentes v´ıdeos y diferentes combinaciones de algoritmos de Entrenamiento/Reconstrucci´on. . . . . . . . . . . . . 47 6.15. Comparaci´on del PSNR de los resultados para diferentes tipos de funciones del obturador ........................................ 49 7.1. Im´agenes codificadas para el v´ıdeo Llama. . . . . . . . . . . . . . . . . . . . . . . 52 7.2. Fotogramas reconstruidos de una llama prendi´endose. . . . . . . . . . . . . . . . 53 7.3. Fotogramas reconstruidos de una llama estabilizada. . . . . . . . . . . . . . . . . 54 B.1. Proceso iterativo del algoritmo K-SVD [5] . . . . . . . . . . . . . . . . . . . . . . 65 D.1. Muestra de un fotograma representativo para cada uno de los v´ıdeos utilizados en el entrenamiento de diccionarios. . . . . . . . . . . . . . . . . . . . . . . . . . 73 D.2. Muestra de un fotograma representativo para cada uno de los v´ıdeos utilizados enelan´alisis. ...................................... 74 E.1. Caracterizaci´on del v´ıdeo City. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 E.2. Caracterizaci´on del v´ıdeo Coke. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 E.3. Caracterizaci´on del v´ıdeo Foreman. . . . . . . . . . . . . . . . . . . . . . . . . . . 78 E.4. Caracterizaci´on del v´ıdeo LlamaHold. . . . . . . . . . . . . . . . . . . . . . . . . 79 E.5. Caracterizaci´on del v´ıdeo LlamaStart. . . . . . . . . . . . . . . . . . . . . . . . . 79 E.6. Caracterizaci´on del v´ıdeo Spring. . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 8 2. Trabajo relacionado Figura 2.2: Diagrama temporal para cuatro tipos de shutter. (a) Shutter global: Muestreo continuo en un intervalo de tiempo, (b) flutter shutter: muestreo no continuo en intervalos aleatorios, (c) rolling shutter: muestreo continuo de diferentes intervalos de tiempo a lo largo de las filas de la imagen, (d) coded rolling shutter: Modificaci´on de la secuencia de muestreo del rolling shutter convencional mediante una funci´on de optimizaci´on [2]. Figura 2.3: Izquierda: C´amara desmontada usada en los tests de Masia et al. para correcci´on de blur por desenfoque. Derecha: Lente con una de las aperturas codificadas insertada [3]. puntos clave para este proyecto. Por una parte, proponen la arquitectura de un sistema capaz de recuperar un fragmento de v´ıdeo de una sola imagen con exposici´on codificada mediante aprendizaje de diccionarios. Los resultados en simulaci´on se contrastan con resultados pr´acticos mediante el uso de un prototipo creado con un dispositivo LCoS (cristal l´ıquido sobre silicio). Por otra parte, presentan una nueva codificaci´on para el obturador basado en un muestreo aleatorio de p´ıxeles para cada fotograma y prueban sus resultados en la reconstrucci´on de v´ıdeo a partir de una sola imagen tal y como se muestra m´as adelante en este proyecto. 15 3. Compressive sensing: marco te´orico En este cap´ıtulo se presentan las bases te´oricas gen´ericas de compressive sensing necesarias para entender c´omo se puede reconstruir un v´ıdeo completo de una sola imagen. Primeramente se presentan las ecuaciones b´asicas para despu´es concluir con un ejemplo sencillo de aplicaci´on. Sea una se˜nal de inter´es Xde valores reales, unidimensional y discreta de duraci´on N. Dicha se˜nal puede representarse como un vector columna N×1 en RNcon elementos X[n], con n= 1,2, . . . , N. Sea una base ortonormal {ψi}K i=1 representada matricialmente de manera que ψ= [ψ1|ψ2|. . . |ψK] con cada vector de la base ψicomo una columna de la matriz. La se˜nal Xpuede expresarse como una combinaci´on lineal de los vectores de la base ψ X= K X i=1 αiψi (3.1) donde αson los coeficientes de dicha combinaci´on αi=hX, ψii=ψT iX Tambi´en puede representarse la Ecuaci´on 3.1 de manera matricial, que es como se utilizar´a de aqu´ı en adelante, tal y como se presenta en la siguiente ecuaci´on X=ψα (3.2) Se dice que una se˜nal es k-sparse cuando puede expresarse como combinaci´on lineal de k vectores de la base ψ, es decir (K−k) elementos del vector αson cero. Cuando k << K, es decir, la informaci´on se encuentra contenida tan solo en unos pocos coeficientes, se dice que la se˜nal es compresible. Convencionalmente, el proceso de compresi´on se realiza capturando la se˜nal completa para posteriormente transformarla en alguna base en la que sea compresible y descartar los coeficientes menos significativos (por ejemplo DCT para el est´andar JPEG). El objetivo de compressive sensing es incrementar la eficiencia de este proceso de manera que se logre capturar la se˜nal ya comprimida, es decir, realizar ese descarte de informaci´on en el proceso de muestreo en lugar de posteriormente en el procesado. A este efecto, se define la matriz de medida φ, que es el concepto matem´atico que precede a la realizaci´on f´ısica que ser´ıa el obturador. Es la colecci´on de vectores utilizados para aplicar un 17 3. Compressive sensing: marco te´orico proceso de muestreo lineal que computa M < N productos internos entre Xy la colecci´on de vectores {φj}M j=1 de manera que Yj=hX, φji(3.3) Si se expresa Y= [Y1. . . YM]Tcomo un vector columna de M×1 elementos y se organizan los elementos de la base φcomo filas en una matriz M×Ny usando la Ecuaci´on 3.2 se puede representar el proceso completo de compressive sensing de acuerdo a la Figura 3.1 y la siguiente ecuaci´on: Y=φX =φψα = Θα(3.4) donde Θ = φψ es una matriz de tama˜no M×Kque representa conjuntamente la base y la matriz de medida. Figura 3.1: Representaci´on del proceso de compressive sensing acuerdo a la ecuaci´on 3.4. La se˜nal Yde tama˜no M×1 procede de la se˜nal Xde tama˜no N×1 con N > M muestreada con la matriz de medida φ. Finalmente, la se˜nal Xpuede expresarse tambi´en mediante la base ψde Kelementos y el vector de coeficientes de representaci´on αde la se˜nal en la base. El proceso de muestreo no es adaptativo, esto es, la matriz de medida es siempre la misma independientemente de la se˜nal, por lo que se presenta el problema de dise˜nar una matriz de medida φestable capaz de muestrear correctamente toda se˜nal compresible en la base ψ. Para que la reconstrucci´on sea posible la matriz de medida debe cumplir dos condiciones, la primera es cumplir la propiedad de isometr´ıa restringida (RIP) y la segunda es que dicha matriz sea incoherente con la base ψ. Una descripci´on en detalle de estas propiedades se puede encontrar en el Anexo A. El dise˜no de una matriz de medida que cumpla estas dos propiedades y que sea realizable desde un punto de vista pr´actico es un proceso complejo. Sin embargo, una manera sencilla de cumplir satisfactoriamente las dos condiciones con alta probabilidad, es construir φcomo una matriz aleatoria como demuestran Baraniuk et al. [27]. Finalmente, utilizando la Ecuaci´on 3.4 y conociendo la matriz de medida φy la se˜nal muestreada Y, es posible reconstruir la se˜nal original Xmediante un problema de minimizaci´on que se plantear´a en la Secci´on 4.4 del Cap´ıtulo 4. Los factores principales que deben considerarse a la hora de dise˜nar un sistema en el marco te´orico de compressive sensing, y que se analizar´an en el siguiente cap´ıtulo son: Selecci´on de una base en la que el conjunto de se˜nales de inter´es sea sparse, dise˜no de una matriz de medida que 18 3. Compressive sensing: marco te´orico permita recuperar la se˜nal original evitando p´erdidas de informaci´on, y elecci´on de un algoritmo adecuado que sea capaz de calcular los coeficientes αpara recuperar dicha se˜nal. A continuaci´on se presenta un ejemplo sencillo propuesto por Romberg en [4] de aplicaci´on de compressive sensing a una se˜nal unidimensional para ilustrar lo expuesto anteriormente. 3.1. Ejemplo de aplicaci´on: Se˜nales unidimensionales Sea una se˜nal discreta de 256 muestras compuesta por 16 sinusoides complejas de frecuencia desconocida como puede verse en la Figura 3.2. Se puede decir que esta se˜nal es sparse en el dominio de Fourier ya que la mayor parte de los coeficientes son cero. Figura 3.2: Transformada de Fourier de una se˜nal discreta unidimensional de 256 muestras [4]. Dado que no est´a limitada en banda, para una reconstrucci´on completa de acuerdo al teorema de Nyquist, en el dominio del tiempo se deben muestrear las 256 componentes. Ahora, suponer que se quiere aplicar la teor´ıa de compressive sensing y se muestrean aleatoriamente solo 80 muestras en el tiempo de acuerdo a la Figura 3.3. Se tiene pues, la se˜nal original de 256 muestras, y la versi´on muestreada de la misma con tan solo 80 muestras. El conjunto de se˜nales de longitud 256 muestras que podr´ıan dar lugar a una misma se˜nal sub-muestreada de 80 muestras es un subespacio de dimensi´on 256 −80 = 176. Sin embargo, dado que se sabe que la se˜nal es sparse en el dominio de Fourier, la soluci´on, como se ver´a m´as adelante, ser´a aquella se˜nal cuya DFT tenga norma L1 m´ınima, es decir, que la suma de los coeficientes de la transformada de Fourier sea la menor posible o lo que es lo mismo, que la mayor parte de sus coeficientes sean cero, dando lugar con ello a una se˜nal sparse en la reconstrucci´on. De esta manera, es posible extender este mismo planteamiento a se˜nales de todo tipo: 2D (imagen), 3D (v´ıdeo), 4D (lightfields), etc. Por otra parte, en este ejemplo sencillo es posible recuperar la se˜nal perfectamente. Sin embargo, como se ver´a m´as adelante, esto no siempre es posible en la pr´actica debido a diferentes factores; por ejemplo, se˜nales que en la pr´actica no ser´an totalmente sparse, es decir, que la mayor parte de sus coeficientes ser´an muy 19 3. Compressive sensing: marco te´orico Figura 3.3: Se˜nal discreta unidimensional en el dominio temporal. Muestras originales de la se˜nal en azul y muestreadas en rojo [4]. bajos pero no estrictamente cero, o matrices de medida que no ser´an totalmente aleatorias. 20 4. Captura de v´ıdeo mediante compressive sensing 4.1. Introducci´on En este cap´ıtulo se introducen los conceptos y par´ametros presentes en un sistema de captura y reconstrucci´on de v´ıdeo mediante compressive sensing para m´as tarde en el Cap´ıtulo 7 analizar su repercusi´on en los resultados de una reconstrucci´on. La teor´ıa de compressive sensing puede aplicarse a todo proceso que requiera un muestreo siempre y cuando se cumplan las condiciones para permitir la reconstrucci´on de la se˜nal, es decir, siempre que la se˜nal sea sparse en un dominio y se cuente con una matriz de medida adecuada. En este caso, el proceso que se presenta es la captura de v´ıdeo. En un dispositivo convencional, el proceso de captura de un v´ıdeo se realiza mediante el muestreo todos los p´ıxeles para cada fotograma de tama˜no M×Np´ıxeles y para Tinstantes temporales, lo que hace un total de M×N×Tmuestras. El objetivo al abordar este proceso desde la perspectiva de compressive sensing es lograr reconstruir dicho v´ıdeo a partir de un n´umero de muestras menor que el que se requiere convencionalmente, en este caso a partir de una ´unica imagen, es decir, M×Nmuestras. A este efecto, tal y como se ha visto en el cap´ıtulo anterior, se puede dividir el problema en tres factores principales a considerar: Base: Conjunto de vectores linealmente independientes capaces de representar la se˜nal, en este caso v´ıdeo, de manera sparse, es decir, con un reducido n´umero de coeficientes distintos de cero. Llamadas diccionarios en este campo de aplicaci´on. Matriz de medida: Matriz que define c´omo se va a muestrear la se˜nal, en este caso mediante una exposici´on codificada, esto es, una funci´on de obturaci´on que var´ıa los p´ıxeles a muestrear en cada instante temporal, y que debe cumplir las condiciones presentadas en el Cap´ıtulo 3. En el caso de captura de v´ıdeo este concepto se materializa en forma de un obturador. Algoritmo de reconstrucci´on: Algoritmo que sea capaz de calcular los coeficientes de representaci´on αde la se˜nal en determinada base ψde manera sparse. Es necesario relacionar el caso concreto de captura de v´ıdeo con las bases te´oricas de compressive sensing expuestas en el Cap´ıtulo 3. Para ello se define la se˜nal original Xcomo un bloque 21 4. Captura de v´ıdeo mediante compressive sensing de v´ıdeo de duraci´on Tfotogramas y M×Np´ıxeles por fotograma. La se˜nal capturada Yes una proyecci´on de dos dimensiones (una imagen) del espacio tridimensional de la se˜nal original X (un v´ıdeo) y queda definida muestreando dicha se˜nal Xcon la matriz de medida φ, que en este caso es un obturador. El resultado es una sola imagen de tama˜no M×Np´ıxeles, obtenida como una combinaci´on de los fotogramas del v´ıdeo original. Un ejemplo de este proceso puede verse en la Figura 4.1, en la que se ilustra c´omo un fragmento de un v´ıdeo de una llama prendi´endose se captura en una sola imagen mediante una matriz de medida que muestrea p´ıxeles aleatorios. La forma de esta matriz de medida, es decir, la manera en la que debe muestrearse el v´ıdeo original, se discute en profundidad m´as adelante en la Secci´on 4.3. Figura 4.1: Proceso de captura de un v´ıdeo de tama˜no M×Np´ıxeles y duraci´on Tfotogramas mediante una matriz de medida φque muestrea p´ıxeles aleatorios para cada fotograma del v´ıdeo con el objetivo de construir la imagen Yde tama˜no M×Np´ıxeles. Una vez obtenida la captura de v´ıdeo en forma de una ´unica imagen, se plantea la problem´atica de la reconstrucci´on en la Secci´on 4.4, as´ı como los posibles algoritmos que pueden utilizarse. Es muy importante remarcar que despu´es de la captura, durante todo procesado, no se trabaja con la informaci´on (tanto v´ıdeos como im´agenes) del tama˜no original sino que se divide en bloques m´as peque˜nos, de orden de la decena de p´ıxeles. Cada uno de estos bloques m´as peque˜nos se trata por separado, como si de un problema independiente se tratase. Esto es as´ı porque a la hora de representar la informaci´on en un diccionario, nos interesa ser capaces de representar caracter´ısticas clave, como bordes o ciertos movimientos, que puedan utilizarse despu´es para conformar, poco a poco, un v´ıdeo completo. No tendr´ıa sentido buscar un diccionario capaz de representar v´ıdeos completos porque se necesitar´ıa un diccionario muy espec´ıfico, adaptado a dichos v´ıdeos, lo cual restringir´ıa mucho la generalizaci´on del diccionario para un conjunto m´as amplio. Para esto, la imagen Ydebe dividirse en sub-im´agenes m´as peque˜nas de tama˜no p×qcon p<Myq < N. Con ello, el problema de la reconstrucci´on del v´ıdeo completo queda reducido a varias reconstrucciones independientes de fragmentos de v´ıdeo de menor tama˜no p×q×T, que ser´a el tama˜no de bloque con el que se hayan entrenado los diccionarios. El esquema de todo el proceso de captura y reconstrucci´on de v´ıdeo seguido durante este proyecto se muestra en la Figura 4.2. 22 4. Captura de v´ıdeo mediante compressive sensing Figura 4.2: Arquitectura del sistema de captura y reconstrucci´on de v´ıdeo mediante compressive sensing. Arriba: Entrenamiento de un diccionario de Kelementos apropiado para el conjunto de se˜nales de inter´es. Abajo: Muestreo de la se˜nal original de v´ıdeo Xmediante una matriz de medida φresultando en la imagen Y. Divisi´on de la imagen Yen parches de menor tama˜no. Derecha: Reconstrucci´on de sub-bloques de v´ıdeo a partir de cada parche como un problema independiente y composici´on del v´ıdeo original completo. 23 4. Captura de v´ıdeo mediante compressive sensing 4.2. Diccionario Como se ha explicado anteriormente, es necesario un sistema de representaci´on adecuado para el caso de v´ıdeo, es decir, un diccionario. Para ello, se puede generalizar una clasificaci´on entre dos opciones, la alternativa no adaptativa y la adaptativa. La opci´on no adaptativa consiste en escoger un diccionario de entre la gran cantidad de sistemas de representaci´on ya existentes, como por ejemplo, en el caso de imagen DCTs (Discrete Cosine Transform) o Wavelets. La ventaja en este caso radica en que estos diccionarios ya est´an matem´aticamente definidos y sus propiedades son conocidas, as´ı como la existencia de transformadas r´apidas y computacionalmente eficientes en sus respectivos dominios. Por otra parte, el uso de estos diccionarios no proporciona unos coeficientes ´optimamente sparse para la se˜nal de inter´es. Esto puede mejorarse con la opci´on adaptativa: mediante el uso de diccionarios aprendidos con muestras de la se˜nal de inter´es, es decir, adaptados a dicha se˜nal. Para entrenar un diccionario es necesario un conjunto de se˜nales de inter´es (es decir, de la misma naturaleza de las se˜nales que se quieren representar), as´ı como un algoritmo de entrenamiento. En este proyecto, las se˜nales de inter´es son v´ıdeos de alta resoluci´on temporal (1000 fps - fotogramas por segundo) de todo tipo de escenarios. La descripci´on de la base de datos as´ı como detalles acerca de su obtenci´on, pueden encontrarse en el Cap´ıtulo 5, no obstante, un ejemplo de los v´ıdeos utilizados puede verse en la Figura 4.3. Figura 4.3: Fotogramas de algunos de los v´ıdeos utilizados para el entrenamiento de diccionarios. (a) Parpadeo de un ojo, (b) P´aginas de un libro siendo pasadas, (c) Una moneda girando, (d) Flujo de agua cayendo de un cuentagotas a una superficie plana. A la hora del entrenamiento, uno de los algoritmos m´as conocidos y m´as usados es el algoritmo K-SVD introducido por Aharon, Elad y Bruckstein [5], motivo por el cual se usa en este proyecto. Los detalles acerca del funcionamiento de este algoritmo pueden consultarse en el Anexo B. Para representar la se˜nal de v´ıdeo en el dominio del diccionario de acuerdo a la Ecuaci´on 3.2 es necesario conocer los coeficientes α. Para el c´alculo de dichos coeficientes se utiliza el mismo algoritmo que en la reconstrucci´on, que ser´a discutido m´as adelante en la Secci´on 4.4. Finalmente, como resultado del entrenamiento, se obtiene un diccionario de Kelementos, siendo el n´umero de elementos Kmayor o igual que el tama˜no de la se˜nal a representar, en este caso p×q×T. Cada uno de los elementos de este diccionario es llamado ´atomo. En el caso de v´ıdeo, cada ´atomo es un bloque de v´ıdeo de tama˜no p×q×T. Un ejemplo de un ´atomo de uno 24 5. Adquisici´on de una base de datos Para el desarrollo de este proyecto, se ha creado una base de datos de v´ıdeos de alta velocidad y alta resoluci´on temporal. Esta base de datos cuenta con v´ıdeos de muy diferentes caracter´ısticas, entre ellas: diferentes dispositivos de captura, para no obtener resultados adaptados a un ´unico dispositivo de captura concreto; objetos de diferente naturaleza representados en las escenas, para obtener la mayor diversidad posible; y, lo m´as importante, diferentes caracter´ısticas espaciales y temporales, esto es, movimientos bruscos, suaves, peri´odicos, v´ıdeos con muchos contornos, etc. Para una versi´on en baja resoluci´on y comprimida de esta base de datos consultar el Anexo D. Es importante recalcar que los experimentos no pueden reproducirse con las versiones en baja resoluci´on de los v´ıdeos. La base de datos de alta resoluci´on esta disponible bajo petici´on, pero, debido al tama˜no de los v´ıdeos sin comprimir y la limitaci´on en recursos de almacenamiento on-line, facilitarla completa ha sido inviable. Los v´ıdeos de esta base de datos provienen de tres fuentes distintas, que se describen a continuaci´on. Parte de estos v´ıdeos, han sido capturados con el equipamiento del instituto universitario de investigaci´on en ingenier´ıa de Arag´on (I3A). La captura se realiz´o con el montaje mostrado en la Figura 5.1 con una c´amara Photron SA2 [39]. Durante este proceso, comprobamos de primera mano algunas de las limitaciones de los equipos de captura de v´ıdeo de alta velocidad. Para el proceso de captura se necesita una fuente de luz potente, as´ı como estabilizar tanto la c´amara como el objeto a grabar. Adem´as, la profundidad de campo de la c´amara era muy limitada, por lo que el objeto a grabar tiene que estar situado en un punto muy concreto, de otra manera, aparece desenfocado. Esto pone de manifiesto, una vez m´as, la necesidad de una alternativa a la captura convencional, ya que a pesar de tratarse de equipamiento especializado, todav´ıa presenta ciertas limitaciones. Durante el proceso de captura, se grabaron 12 v´ıdeos con una resoluci´on temporal de 1000 fps (fotogramas por segundo) y con una resoluci´on espacial de 1024 ×1024 p´ıxeles. Otros 5v´ıdeos han sido proporcionados por el departamento de ingenier´ıa inform´atica de la universidad Rey Juan Carlos (URJC), y est´an capturados a 1000 fps y con una resoluci´on de 1280 ×1024 p´ıxeles. Por ´ultimo, los restantes 9v´ıdeos son parte de los v´ıdeos usados en el trabajo de Hitomi et al. [8]. Est´an capturados a 30 fps y con una resoluci´on de 352×288. Es importante destacar que estos v´ıdeos son de resoluciones frecuenciales y espaciales muy diferentes al resto de los v´ıdeos de la base de datos. El uso de estos v´ıdeos se debe a que quer´ıamos comprobar qu´e sucede al 31 5. Adquisici´on de una base de datos Figura 5.1: Montaje para la captura de v´ıdeo con la c´amara Photron SA2 en el I3A consistente en un soporte tanto para la c´amara como para el objeto a grabar, y una fuente de luz iluminando el objeto. intentar reconstruir v´ıdeos capturados con caracter´ısticas muy diferentes de los v´ıdeos con los que se entrena el diccionario, es decir, comprobar cuanto de extrapolable es dicho diccionario. De estos 26 v´ıdeos, diez se han usado para el entrenamiento de diccionarios. De estos diez, ocho pertenecen a los v´ıdeos capturados en el I3A y los otros dos a los v´ıdeos proporcionados por la URJC. Una muestra de los v´ıdeos de entrenamiento puede verse en el Anexo D. Se ha realizado un escalado de los v´ıdeos tanto para entrenamiento como para reconstrucci´on, debido a que el tiempo de c´alculo se incrementa con la dimensionalidad y el tama˜no de los datos, y el procesado de v´ıdeos de mayor tama˜no durante este proyecto se hizo inviable debido a la limitaci´on de recursos. Para la parte de entrenamiento, los v´ıdeos se han escalado a una resoluci´on espacial de 512 ×512 y se han extra´ıdo 200 fotogramas de cada v´ıdeo, esto es, cada v´ıdeo de entrenamiento es de tama˜no 512 ×512 ×200. Para la parte de reconstrucci´on, los v´ıdeos se han escalado a una resoluci´on espacial de 200 ×200 y el n´umero de fotogramas extra´ıdos depende del tipo de an´alisis realizado, as´ı pues se tienen v´ıdeos de reconstrucci´on de 200 ×200 y 10, 20 y 30 fotogramas, ya que ´estas son las longitudes de v´ıdeo para las que se analiza la reconstrucci´on. 32 6. An´alisis de par´ametros 6.1. Introducci´on En un sistema basado en compressive sensing, independientemente de la aplicaci´on final, la calidad de los resultados obtenidos depende en gran medida de un elevado n´umero de factores, entre los que se incluyen una serie de par´ametros relativos al algoritmo de entrenamiento del diccionario a partir de la base de datos, el tipo de algoritmo de reconstrucci´on, o la matriz de medida utilizada. Con el objetivo de dar con los valores ´optimos de estos par´ametros a emplear en nuestro sistema, se han realizado una serie de pruebas y an´alisis, que se exponen, junto con las conclusiones obtenidas en cada caso, en este cap´ıtulo. Asimismo, observamos que la calidad de la reconstrucci´on de un v´ıdeo exhibe una dependencia significativa con las caracter´ısticas del v´ıdeo a reconstruir, y en particular con sus frecuencias espaciales y temporales. Es por esto que los seis v´ıdeos utilizados en este an´alisis de par´ametros se han estudiado, analizando su variaci´on espacio-temporal, en la Subsecci´on 6.2. M´etricas de error. Para cada uno de los par´ametros de influencia que se estudiar´an, se han analizado los seis v´ıdeos mencionados, calculando el error obtenido en la reconstrucci´on de cada uno mediante las m´etricas de error PSNR (dB) [40] y MS-SSIM [41]. PSNR (Peak Signal-toNoise Ratio) es una m´etrica objetiva com´unmente utilizada en procesado de se˜nal, basada en la diferencia entre p´ıxeles correspondientes de ambas secuencias de v´ıdeo. La expresi´on matem´atica para el c´alculo de la misma, que da el resultado en decibelios, se muestra en las siguientes ecuaciones: MSE =1 MN M−1 X i=0 N−1 X j=0 kI(i, j)−K(i, j)k2(6.1) PSNR = 10 log10(MAX2 I MSE ) = 20 log10(MAXI √MSE ) (6.2) MS-SSIM (Multi-Scale Structural Similarity Index Metric) es una m´etrica muy utilizada en visi´on por computador para la medida de similitud entre dos im´agenes. Esta m´etrica tiene en cuenta el modo en que funciona el sistema visual humano a la hora de calcular el error, y se dise˜n´o para mejorar las m´etricas tradicionales de error como MSE o PSNR basadas s´olo en la diferencia entre p´ıxeles, y por tanto inconsistentes en muchas ocasiones con la percepci´on del sistema visual humano. La m´etrica MS-SSIM se calcula sobre varias ventanas de la imagen y 33 6. An´alisis de par´ametros para diferentes resoluciones. La medida de dos ventanas xeydel mismo tama˜no N×Nse obtiene a partir de la comparaci´on de la luminancia l, del contraste c, y de la estructura s. La luminancia se compara a una sola escala (la original, denotada M), pero el contraste y la estructura se comparan en m´ultiples (M) escalas. Para ello, se aplica iterativamente un filtro paso bajo y un diezmado de la imagen filtrada por un factor 2. La m´etrica se calcula por tanto con la siguiente f´ormula: MSSSIM(x,y) = [lM(x,y)]αM· M Y j=1 [cj(x,y)]βj[sj(x,y)]γj(6.3) donde las diferencias de luminancia (l), de contraste (c) y en la estructura (s) se calculan como sigue: l(x,y) = 2µxµy+C1 µ2 xµ2 y+C1 c(x,y) = 2σxσy+C2 σ2 xσ2 y+C2 s(x,y)) = σxy +C3 σxσy+C3 (6.4) siendo µx, µylas respectivas medias de las ventanas x,y;σx, σylas desviaciones t´ıpicas y σx,y su covarianza. Los valores C1,C22 y C3son constantes para estabilizar la divisi´on donde C1= (K1L)2,C2= (K2L)2yC3=C2/2, siendo Lel rango din´amico de los valores de p´ıxel (L= 2bitsperpixel −1). Los exponentes αM, βjyγjse usan para ajustar la importancia relativa de diferentes componentes. Las f´ormulas de la Ecuaci´on 6.4 hacen que la diferencia se compute en valores relativos en vez de absolutos, emulando una de las caracter´ısticas del funcionamiento del sistema visual humano. Par´ametros por defecto. En todas las pruebas que se exponen en las subsecciones siguientes de este cap´ıtulo se ha variado uno de los par´ametros del sistema, dejando todos los dem´as fijos, y analizando la influencia de dicho par´ametro. Para poder hacer esto, se han fijado un conjunto de par´ametros que denominamos ”por defecto”, que son los siguientes: Bloques de v´ıdeo de tama˜no 7 ×7×20 p´ıxeles. Diccionario de 10000 elementos entrenado con el algoritmo K-SVD. Algoritmo de reconstrucci´on Lasso. Muestreo con obturador pixel-wise V´ıdeos para el an´alisis. Se han utilizado para el an´alisis seis v´ıdeos de escenas de muy distinta naturaleza, con diferentes objetos, movimientos variados, y por tanto de diferentes caracter´ısticas espacio-temporales. ´ Estas se analizan en la Secci´on 6.2, dada su influencia en la calidad de la reconstrucci´on final. Un fotograma representativo de cada uno de los v´ıdeos se muestra en la Figura 6.1. Naturalmente, ninguno de los v´ıdeos que se han utilizado en este an´alisis forma parte de la base de datos empleada para el entrenamiento de diccionarios. 34 6. An´alisis de par´ametros Figura 6.1: Fotograma representativo extra´ıdo de cada uno de los v´ıdeos utilizados en el an´alisis. 6.2. Caracter´ısticas espacio-temporales de los v´ıdeos usados en el an´alisis Es interesante hacer una caracterizaci´on de estos v´ıdeos porque el resultado de la reconstrucci´on, como se ha mencionado anteriormente, depende fuertemente de las caracter´ısticas del v´ıdeo que se desea reconstruir, como por ejemplo su distribuci´on de frecuencias espaciales (si tiene muchos contornos o es m´as bien suave), o su distribuci´on de frecuencias temporales (si ocurre mucho movimiento o poco). Para la caracterizaci´on de imagen, existen muchos procesos estandarizados, sin embargo, la caracterizaci´on de un v´ıdeo de la manera que nos interesa en este proyecto, no es un proceso tan sencillo. Para intentar dar con un m´etodo de caracterizaci´on que nos permita saber con antelaci´on si un v´ıdeo se va a poder reconstruir correctamente, esto es, caracterizarlo, se han explorado diferentes m´etodos que se listan a continuaci´on: Histograma de ratios de densidad de energ´ıa de alta frecuencia temporal calculados para cada bloque, tras dividir el v´ıdeo en bloques del tama˜no del que se quiere reconstruir (Hratios). Estos ratios se calculan realizando una DFT unidimensional a lo largo del eje temporal para cada p´ıxel del bloque. Despu´es, se suman los coeficientes de la DFT de todos los p´ıxe35 6. An´alisis de par´ametros les del bloque y se calcula el ratio entre la energ´ıa total y la energ´ıa de alta frecuencia de esta DFT conjunta. Este valor calculado para todos los bloques que componen el v´ıdeo es lo que se representa en el histograma para despu´es calcular sus descriptores estad´ısticos. El objetivo de esta caracterizaci´on es obtener una medida de la variaci´on temporal del bloque de v´ıdeo. Obtenido el histograma, se calculan sus descriptores estad´ısticos: media, desviaci´on t´ıpica, skewness y kurtosis. Histograma de las varianzas calculadas para cada bloque, tras dividir el v´ıdeo en bloques del tama˜no del que se quiere reconstruir (Hvarianzas). Las varianzas se calculan sobre el bloque completo de v´ıdeo y se representan en el histograma para despu´es calcular sus descriptores estad´ısticos. El objetivo de esta caracterizaci´on es obtener una medida conjunta de la variaci´on espacial y temporal para tener en cuenta tanto los eventos temporales (e.g. movimiento) como los espaciales (e.g. contornos). Una vez obtenido el histograma, se calculan los mismos descriptores estad´ısticos que en el caso anterior: media, desviaci´on t´ıpica, skewness y kurtosis. Suma de la diferencia entre fotogramas (Sdiff ). Para esta medida se calcula una imagen diferencia que contiene la suma de todas las diferencias entre fotogramas consecutivos. Despu´es, se suman todos los p´ıxeles de esta imagen obteniendo un ´unico valor. El objetivo es obtener una medida de cu´anto movimiento (cu´anta variaci´on espacio-temporal) hay en el v´ıdeo completo. Figura 6.2: M´etodos de caracterizaci´on para el v´ıdeo Coke. En la fila de arriba se pueden ver el histograma de las varianzas de cada bloque (izquierda) y el histograma del ratio de energ´ıa de alta frecuencia temporal (derecha). En la fila de abajo se puede ver la imagen calculada como la suma de diferencias entre fotogramas consecutivos, donde se puede ver que este v´ıdeo presenta muy poco movimiento, y la transformada de Fourier bi-dimensional. Estos m´etodos de caracterizaci´on se han obtenido para los seis v´ıdeos de test. La Figura 6.2 muestra, para el v´ıdeo Coke, el resultado de los tres m´etodos de caracterizaci´on y la transformada discreta de Fourier bi-dimensional. Estos mismos resultados para los cinco v´ıdeos de test restantes se pueden encontrar en el Anexo E. Una vez obtenidos los histogramas y la diferencia entre fotogramas, se calculan los descriptores de los histogramas mencionados y la suma de la diferencia de fotogramas. El objetivo es ver cu´al de estos descriptores o valores es una buena forma de 36 6. An´alisis de par´ametros V´ıdeo µ σ sk k City 0,3323 0,1273 0,9124 4,7346 Coke 0,0764 0,0381 11,8942 196,4976 Foreman 0,2611 0,0976 1,5505 8,059 LlamaHold 0,6749 0,0855 −2,62 15,9144 LlamaStart 0,2694 0,1943 1,1941 3,5215 Spring 0,2016 0,2129 1,4616 3,9331 Tabla 6.1: Media µ, varianza σ, skewness sk y kurtosis kcorrespondientes a los histogramas mostrados en la Figura 6.3. caracterizar la variaci´on espacio-temporal de un v´ıdeo dado para, dado un v´ıdeo, poder inferir c´omo de buena ser´a la reconstrucci´on de una escena de ese tipo. Para ello, se reconstruyen los seis v´ıdeos de test (usando los par´ametros ”por defecto”mencionados en la Secci´on 6.1), se mide su calidad utilizando PSNR y MS-SSIM, y se compara esta calidad de los resultados con las medidas dadas por los m´etodos de caracterizaci´on descritos en este apartado. Para ello, se calcul´o la correlaci´on entre m´etricas calidad y medidas de caracterizaci´on utilizando los coeficientes de correlaci´on de Pearson [42] y Spearman [43]. La medida de caracterizaci´on que arroja una mayor correlaci´on con la calidad final es la desviaci´on t´ıpica del histograma de ratios de energ´ıa de alta frecuencia temporal, σratios. Para esta medida, el coeficiente de Pearson arroja un valor ρP=−0,9636 con un p-valor de 0,0020, mientras que el coeficiente de Spearman resulta en un valor ρS=−1 y un p-valor de 0,0028. Por tanto, σratios es el descriptor que se ha decidido utilizar para la caracterizaci´on de los v´ıdeos. En la Figura 6.3 puede verse el histograma de los ratios de energ´ıa de alta frecuencia temporal Hratios para cada uno de los seis v´ıdeos de test, mientras que en la Tabla 6.1 se presenta la media, desviaci´on t´ıpica, skewness y kurtosis para cada uno de estos seis histogramas. Figura 6.3: Histograma de los ratios de energ´ıa de alta frecuencia temporal Hratios para cada uno de los v´ıdeos utilizados en el an´alisis. Los valores de PSNR [40] y MS-SSIM [41] obtenidos para cada uno de los seis v´ıdeos pueden verse en la Figura 6.4, mientras que en la Figura 6.5 se muestra un fotograma del resultado reconstruido para cada v´ıdeo. Como se puede ver, el resultado no siempre es bueno, y depende 37 6. An´alisis de par´ametros en gran medida del v´ıdeo que se quiere reconstruir: v´ıdeos con histogramas muy esparcidos frecuencialmente—esto es, un elevado valor de σratios—tendr´an peores reconstrucciones, siendo por tanto σratios el mejor indicador de la calidad de los resultados que se obtendr´an seg´un las caracter´ısticas del v´ıdeo a reconstruir. Figura 6.4: PSNR (izquierda) y MS-SSIM (derecha) para cada uno de los v´ıdeos reconstruidos con el diccionario por defecto. Figura 6.5: Fotograma reconstruido para los seis v´ıdeos utilizados en el an´alisis con el diccionario por defecto. Se puede ver como la calidad de los resultados depende mucho del v´ıdeo que se quiera reconstruir y el resultado visual coincide con los resultados de PSNR y MS-SSIM obtenidos. 38 6. An´alisis de par´ametros 6.3. Selecci´on del tama˜no de bloque de v´ıdeo Como se ha explicado en el Cap´ıtulo 4, es necesario dividir un v´ıdeo en bloques para su reconstrucci´on. As´ı pues, se reconstruir´a el v´ıdeo bloque a bloque, en bloques de dimensiones p×q×T, en este caso, 7 ×7×20, que luego se unir´an para formar el v´ıdeo reconstruido final. Estos bloques pueden verse como peque˜nos v´ıdeos en s´ı mismos, de corta duraci´on y peque˜no tama˜no. La influencia de las dimensiones espaciales y temporales de estos bloques en la calidad de los resultados reconstruidos se analiza a continuaci´on. El tama˜no del bloque influye tambi´en en el tiempo de c´alculo de la reconstrucci´on, pudiendo generar un compromiso entre calidad y tiempo de ejecuci´on. 6.3.1. Tama˜no espacial del bloque de v´ıdeo Elegimos bloques cuadrados, para reducir el n´umero de posibles combinaciones, de tama˜nos p=q={5,7,9}. Tama˜nos m´as elevados son computacionalmente inviables y contienen demasiados detalles, por lo que el algoritmo de entrenamiento se sobre-adapta a ellos, mientras que tama˜nos menores (e.g. 3 ×3 p´ıxeles) apenas contienen informaci´on en s´ı mismos y no capturan la estructura subyacente. Las Figuras 6.6 y 6.7 muestran el error de la reconstrucci´on en los seis v´ıdeos de test para diferentes valores de p y q, medido con MS-SSIM y PSNR respectivamente. Figura 6.6: MS-SSIM de la reconstrucci´on en funci´on del tama˜no espacial del bloque En primer lugar, observamos una variabilidad del error de reconstrucci´on con el tipo de v´ıdeo, tal y como se ha explicado en la secci´on anterior. En cuanto al tama˜no de bloque, se puede ver un incremento tanto del PSNR como del MS-SSIM para todos los v´ıdeos en el paso de bloques de 5 ×5 p´ıxeles a 7 ×7 p´ıxeles mientras que el aumento a 9 ×9 p´ıxeles no tiene una 39 6. An´alisis de par´ametros Figura 6.7: PSNR de la reconstrucci´on en funci´on del tama˜no espacial del bloque mejor´ıa clara. Esto es as´ı porque al aumentar mucho el tama˜no del parche espacial se incluyen muchos detalles y caracter´ısticas muy concretas de la imagen que probablemente se perder´an en la reconstrucci´on. Adem´as, en la Figura 6.8 se observa el incremento de tiempo de c´alculo de la reconstrucci´on al incrementar el tama˜no de bloque, que es muy elevado. As´ı pues, considerando la calidad del resultado y tiempo de c´alculo se concluye que el mejor tama˜no de bloque espacial es 7×7 p´ıxeles. Figura 6.8: Tiempo medio de la reconstrucci´on del v´ıdeo en funci´on del tama˜no espacial del bloque. N´otese que este tiempo se corresponde con el tiempo de la reconstrucci´on del v´ıdeo completo y no de un solo bloque. 40 6. An´alisis de par´ametros Lasso/Lasso OMP/OMP OMP/Lasso Lasso/OMP Tiempo(segundos) 9185 8545 8156 10347 Tabla 6.3: Tiempos medios de las reconstrucciones para diferentes combinaciones de algoritmos de Entrenamiento/Reconstrucci´on. m´as r´apido, 432000 segundos con OMP y 212220 con Lasso. El v´ıdeo Spring vuelve a presentar un comportamiento claramente diferente al resto, que achacamos a sus particulares caracter´ısticas espacio-temporales (Secci´on 6.2). Por tanto, decidimos utilizar Lasso tanto para las reconstrucciones como para el entrenamiento. Figura 6.14: Comparaci´on del PSNR de los resultados para diferentes v´ıdeos y diferentes combinaciones de algoritmos de Entrenamiento/Reconstrucci´on. 6.6. Matriz de medida: funci´on del obturador La elecci´on de una matriz de medida adecuada es determinante para los resultados de un esquema de compressive sensing. Como se ha explicado en la Secci´on 4.3, debe cumplir una serie de propiedades matem´aticas (incoherencia, RIP), pero al mismo tiempo ser f´ısicamente realizable, e implementable mediante un obturador y/o una m´ascara o LCoS (panel de cristal l´ıquido cuyos p´ıxeles pueden regularse para dejar pasar o bloquear la luz, formando una m´ascara din´amica). En esta secci´on se comparan diferentes matrices de medida f´ısicamente implementables, que 47 6. An´alisis de par´ametros han sido descritas previamente en la Secci´on 4.3.2. Se muestran y analizan los resultados de esta comparaci´on para el v´ıdeo Coke; la diferencia de resultados en las reconstrucciones es tan grande que las conclusiones para un solo v´ıdeo pueden generalizarse para el resto. En la Figura 6.15 puede verse el PSNR de las reconstrucciones obtenidas as´ı como un fotograma representativo del v´ıdeo reconstruido para cada una de las matrices de medida (o funciones del obturador). Los mejores resultados se obtienen para la funci´on pixel-wise. Esto se debe, principalmente, a que garantiza que para cada fotograma al menos uno de los p´ıxeles de cada bloque en los que se divide el v´ıdeo para su reconstrucci´on ser´a muestreado, y adem´as es un muestreo m´as aleatorio que otros de los empleados. El obturador global, de muy sencilla implementaci´on, ofrece resultados demasiado borrosos, en los que no se pueden recuperar las altas frecuencias, que se han eliminado irreversiblemente. Los obturadores basados en rolling shutter (rolling ocoded rolling), interesantes porque muchas c´amaras utilizan este m´etodo para controlar el obturador, simplificando la necesidad de modificar el hardware, ofrecen los resultados de menor calidad, con visibles artefactos. Mientras, el flutter-shutter ofrece unos resultados de calidad media que no compensan el coste de su implementaci´on. Esto se debe a que, al muestrear tan solo algunos fotogramas de manera aleatoria, hay fotogramas completos que se pierden por lo que la calidad en la reconstrucci´on es muy inferior a la de la funci´on pixel-wise, que es la finalmente elegida. 48 6. An´alisis de par´ametros Figura 6.15: Comparaci´on del PSNR de los resultados para diferentes tipos de funciones del obturador 49 7. Resultados A lo largo del Cap´ıtulo 6 se han analizado diversos par´ametros tanto de captura como de reconstrucci´on. Tal y como se ha justificado, los mejores par´ametros en t´erminos de resultados y tiempos de computaci´on son los siguientes. Diccionario: Entrenado con algoritmo Lasso, tama˜no del ´atomo de 7 ×7×20, muestras de entrenamiento escogidas mediante selecci´on de varianza. Matriz de medida: Funci´on del obturador pixel-wise aleatorio. Reconstrucci´on: Algoritmo Lasso. Como ejemplo, para estos par´ametros se ha reconstruido el v´ıdeo de la llama prendi´endose en el mechero completo. Se ha escogido este v´ıdeo porque, tal y como se ha visto en el Cap´ıtulo 6 con los ejemplos LlamaHold yLlamaStart, contiene tanto partes con cambios m´as marcados y r´apidos que se reconstruyen peor (al prenderse la llama), como partes con cambios leves que se reconstruyen mejor (cuando la llama esta estabilizada). Por ello, y debido a la limitaci´on de recursos que han impedido una reconstrucci´on completa de todos los v´ıdeos, se ha considerado este v´ıdeo como ejemplo representativo. Este v´ıdeo consta de 200 fotogramas y una resoluci´on de 512 ×512 p´ıxeles y esta dividido en 10 fragmentos de 20 fotogramas cada uno. Las im´agenes codificadas correspondientes a estos 10 fragmentos pueden verse en la Figura 7.1. Se muestran tambi´en dos ejemplos del v´ıdeo reconstruido, en cada uno aparecen los 20 fotogramas correspondientes a la reconstrucci´on de dos fragmentos diferentes, uno de ellos al prenderse la llama, en la Figura 7.2 y el otro cuando la llama ya esta estabilizada, en la Figura 7.3. Asimismo, el tiempo medio de reconstrucci´on son 82851 segundos para cada fragmento de 20 fotogramas. 51 7. Resultados Figura 7.1: Im´agenes codificadas para el v´ıdeo Llama. Orden temporal de izquierda a derecha y de arriba a abajo. Cada imagen codificada contiene informaci´on para la reconstrucci´on de 20 fotogramas de v´ıdeo. Las im´agenes con marcos de color muestran sus reconstrucciones en la Figura 7.1 (Azul) y en la Figura 7.3 (amarillo). 52 7. Resultados Figura 7.2: Fotogramas reconstruidos para la llama prendi´endose. En la imagen se pueden observar los 20 fotogramas reconstruidos a partir de la imagen codificada. Orden temporal de izquierda a derecha y de arriba a abajo. 53 7. Resultados Figura 7.3: Fotogramas reconstruidos para la llama estabilizada. En la imagen se pueden observar los 20 fotogramas reconstruidos a partir de la imagen codificada. Orden temporal de izquierda a derecha y de arriba a abajo. 54 8. Conclusiones y trabajo futuro En este proyecto hemos presentado un sistema de de captura y reconstrucci´on de v´ıdeo de alta resoluci´on temporal, a partir de una sola imagen codificada. Para ello hemos utilizado t´ecnicas de compressive sensing. El desarrollo b´asico de la t´ecnica utilizada se ha basado en el trabajo de Hitomi et al. [8, 9], que posteriormente hemos analizado y sobre el que hemos a˜nadido ciertas mejoras. En concreto, hemos analizado una serie de escenas (grabadas en v´ıdeos originales de alta resoluci´on) y hemos encontrado una m´etrica para caracterizarlas, que nos permite explicar las diferencias de resultados en su reconstrucci´on con unos mismos par´ametros. Tambi´en hemos explorado el entrenamiento de diccionarios con el algoritmo K-SVD, analizando los resultados obtenidos en la reconstrucci´on en funci´on del tama˜no de los ´atomos, y comparando los resultados de este algoritmo frente a un diccionario ya existente, en este caso DCT. Hemos profundizado en el m´etodo de selecci´on de muestras de entrenamiento de entre un conjunto, hallando el m´etodo de selecci´on de varianza que arroja los mejores resultados en las reconstrucciones. Asimismo, hemos comparado el rendimiento de dos algoritmos de reconstrucci´on, Lasso y OMP, llegando a la conclusi´on de que con el primero, en general, se obtiene una mejor calidad de los resultados as´ı como una mayor velocidad en el c´alculo de los coeficientes. Por otra parte, se ha analizado la compatibilidad de diversos obturadores com´unmente utilizados con la captura de v´ıdeo mediante compressive sensing, corroborando formalmente que ninguno de ellos es superior al propuesto originalmente por Liu et al. en [9]. Todo esto proporciona unas serie de contribuciones al campo que pretendemos completar y consolidar en una sumisi´on de un art´ıculo cient´ıfico. Sin embargo, al ser ´este es un campo relativamente novedoso, nuestra exploraci´on del espacio de par´ametros y el an´alisis de su rendimiento est´an lejos de ser completos, abriendo muchas posibles v´ıas de trabajo futuro. Un camino a seguir ser´ıa continuar este trabajo con un an´alisis m´as exhaustivo, que quiz´a lleve a combinaciones de par´ametros ´optimas seg´un el tipo de escena a capturar. Por otra parte, en el campo del entrenamiento de diccionarios, el algoritmo K-SVD que es el usado en este proyecto, y en gran cantidad de trabajos, es un algoritmo gen´erico. Una mejora en la reconstrucci´on se puede buscar con el desarrollo de un algoritmo de entrenamiento perceptual, esto es, incorporar al entrenamiento modelos computacionales de visi´on o m´etricas perceptuales, resultando reconstrucciones mejores a vista del ojo humano. Este tipo de m´etricas ya se han usado anteriormente, por ejemplo, Masia et al. [3, 44] hacen uso de aperturas codificadas optimizadas con m´etricas perceptuales para correcci´on del desenfoque. Finalmente, los sensores de imagen y el hardware de las c´amaras est´an en continua evoluci´on, por lo que es de esperar que en alg´un momento algunas de las limitaciones actuales del sistema de captura se vayan eliminando. Esto podr´ıa estar asociado con la construcci´on de obturadores 55 8. Conclusiones y trabajo futuro m´as cercanos a las matrices de medida te´oricas, que sean capaces de capturar la se˜nal de una manera m´as ´optima para su reconstrucci´on. Aunque en este proyecto nos hemos limitado a trabajar en simulaci´on, se podr´ıa considerar el uso de pantallas de cristal l´ıquido sobre silicona (LCoS), que act´uan sobre la exposici´on a nivel de p´ıxel de manera independiente, ofreciendo gran versatilidad. A nivel personal, el desarrollo de este proyecto ha sido una experiencia decisiva para m´ı, ya que he podido profundizar en un campo que siempre me ha gustado, el procesado de imagen, desde una perspectiva nueva y diferente. Adem´as, gracias a este proyecto y la buena acogida del grupo de investigaci´on en el que lo he desarrollado, he descubierto en la investigaci´on un camino a seguir, algo que nunca hab´ıa considerado, y voy a comenzar el doctorado, bajo la tutela de mi directora y el ponente de este Proyecto Fin de Carrera. 56 Anexo B. Entrenamiento de diccionarios: Algoritmo K-SVD B.1. Introducci´on En este anexo se desarrolla el funcionamiento del algoritmo K-SVD propuesto por Aharon, Elad y Bruckstein en [5]. K-SVD es un algoritmo de aprendizaje de diccionarios overcomplete especialmente desarrollado para representaciones sparse haciendo uso de la descomposici´on en valores singulares o SVD [46]. Overcompleteness es un t´ermino que denomina a un sistema completo al que si le quitamos un vector, resulta en un sistema completo [47]. Este algoritmo es una generalizaci´on del algoritmo K-Means [48] que consiste en dividir Nobservaciones en K clusters o n´ucleos en los que cada observaci´on pertenece al cluster con la media m´as cercana. K-SVD alterna iterativamente entre codificar los datos de entrenamiento de manera sparse con el diccionario actual y actualizar los ´atomos de dicho diccionario para que se ajusten mejor a los datos de entrenamiento. El objetivo del algoritmo es aprender un diccionario D∈ <n×Kcon K´atomos tal que la se˜nal X∈ <npueda ser representada de manera sparse como combinaci´on lineal de estos ´atomos. Para ello el vector de coeficientes αdebe satisfacer al menos que X≈Dα de manera que kX−Dα kp≤para alg´un valor peque˜no de y alguna norma Lp. T´ıpicamente la norma se elige como L1,L2, o L∞. Si n<KyDes una matriz de rango completo (rango(D) = n), se tienen un infinito n´umero de soluciones para el problema de representaci´on, por lo que se deben poner restricciones en la soluci´on. Para asegurar un resultado sparse debe imponerse que m´ın αkαk0sujeto aX=Dα (B.1) o m´ın αkαk0sujeto a kX−Dα k2≤(B.2) donde la norma L0cuenta el n´umero de elementos distintos de cero del vector α. Debido a la complejidad del problema con la norma L0, se consideran soluciones aproximadas para el c´alculo de los coeficientes α, para saber m´as acerca de estos algoritmos de aproximaci´on consultar el Anexo C. 63 B. Entrenamiento de diccionarios: Algoritmo K-SVD B.2. Algoritmo K-SVD El objetivo es encontrar el conjunto de ´atomos que represente de la mejor manera posible las muestras XiN i=1, es decir, que minimice el error, bajo el supuesto de vecino mas cercano resolviendo m´ın D,α {k X−Dα k2 F}sujeto a∀i, kαik0≤T0(B.3) o, escrito de otra manera m´ın D,α X ikαik0sujeto a∀i, kX−Dα k2 F≤(B.4) con kAkFla norma Frobenius definida como kAkF=qPi,j A2 ij y siendo T0el n´umero de elementos distintos de cero del vector de coeficientes α. En el algoritmo K-SVD primero debe fijarse un diccionario inicial Dy un conjunto de datos de entrenamiento X. El primer paso consiste en codificar de manera sparse el conjunto de datos de entrenamiento en el diccionario Dmediante un algoritmo de aproximaci´on, es decir, obtener el vector de coeficientes α. Despu´es, el siguiente paso es buscar una mejora del diccionario D. Sin embargo, no se puede encontrar un mejor diccionario completo de una vez, por lo que el proceso consiste en actualizar solo una columna del diccionario cada vez que se fija un nuevo vector α. Se asume pues que αyDest´an fijados y debe actualizarse la columna dky los coeficientes que le corresponden, la k−esima fila en α. Entonces, el t´ermino de penalizaci´on puede escribirse como kX−Dα k2 F=|X− K X j=1 djαj T|2 F=|(X−X j6=k djαj T)−dkαk T)|2 F=kEk−dkαk Tk2 F(B.5) donde αk Tdenota la k−esima fila de αy la matriz Ekes el error para todas las muestras cuando el k−esimo ´atomo se elimina. Se ha descompuesto la multiplicaci´on Dα en suma de Kmatrices de rango 1. De ellas, se consideran K−1 t´erminos fijados y el k−esimo permanece desconocido. Despu´es de este paso, se podr´ıa aplicar SVD para encontrar la matriz de rango 1 que aproxima Eky esto minimizar´ıa el error tal y como se ha definido, sin embargo, la condici´on de soluci´on sparse no esta aplicada todav´ıa por lo que no ser´ıa el resultado deseado. Para tener en cuenta esta condici´on, se define ωkcomo el grupo de ´ındices apuntando a las muestras Xique usan el ´atomo dk, i.e, aquellas donde αk T(i) es distinto de cero. Entonces ωk={i|1≤i≤K, αk T(i)6= 0}(B.6) Despu´es, se define Ωkcomo una matriz de tama˜no N× | ωk|, con unos en las entradas correspondientes a (ωk(i), i) y ceros en el resto. Al multiplicar αk R=αk TΩk, esto reduce el vector fila αk Tdescartando las entradas iguales a cero, resultando el vector fila αk Rde longitud |ωk|. De igual manera, la multiplicaci´on XR k=XΩkes el sub-conjunto de muestras que est´a usando 64 B. Entrenamiento de diccionarios: Algoritmo K-SVD actualmente el ´atomo dk, y la multiplicaci´on ER k=EkΩkson las columnas error correspondientes a las muestras que usan el ´atomo dk. As´ı pues, el problema de minimizaci´on se convierte en kEkΩk−dkαk Tωkk2 F=kER k−dkαk Rk2 F(B.7) y puede resolverse directamente via SVD, que descompone la matriz ER kcomo ER k=UMVT. Se define la soluci´on para dkcomo la primera columna de Uy el vector de coeficientes αk Rcomo la primera columna de Vmultiplicada por M(1,1). Es importante remarcar que las columnas de Ddeben permanecer normalizadas. Despu´es de actualizar el diccionario completo, el proceso vuelve a calcular αy a resolver de nuevo Diterativamente. El proceso resumido del algoritmo puede verse en la Figura B.1 Figura B.1: Proceso iterativo del algoritmo K-SVD [5] 65 Anexo C. Algoritmos OMP y LASSO En este anexo se presentan dos algoritmos para resolver el problema de minimizaci´on que presenta compressive sensing a la hora de representar una se˜nal en una base de manera sparse tal y como se indica en la siguiente ecuaci´on m´ın αkαk0sujeto a Y= Θα(C.1) Para ello, a lo largo del tiempo se han estudiado diferentes tipos de enfoques, entre ellos, optimizaci´on convexa, algoritmos voraces y algoritmos combinatorios. Los algoritmos por optimizaci´on convexa requieren menos muestras pero son m´as complejos computacionalmente. En el otro extremo, los algoritmos combinatorios son muy r´apidos pero necesitan muchas medidas, lo cual esta en contraposici´on con el objetivo de compressive sensing. Por otra parte, los algoritmos voraces son un buen compromiso entre n´umero de medidas y complejidad computacional. En este anexo se presentan los dos algoritmos usados durante el proyecto, un algoritmo de optimizaci´on convexa: LASSO, y un algoritmo voraz: OMP. C.1. LASSO: Least Absolute Shrinkage and Selection Operator LASSO es un algoritmo de optimizaci´on convexa. En general, para estos algoritmos, si se cumplen las condiciones de se˜nal sparse y las matrices φyψ(la matriz de medida y la base que conforman la matriz Θ) cumplen las condiciones de incoherencia y la propiedad de isometr´ıa restrictiva tal y como se explican en el Anexo A, el problema puede aproximarse mediante la norma L1de manera m´ın αkαk1sujeto a Y= Θα(C.2) Por otra parte, si las medidas se ven afectadas por ruido, se necesita definir una constante de error, quedando la ecuaci´on m´ın αkαk1sujeto a kΘα−Yk2 2≤(C.3) para un  > 0. En el algoritmo LASSO, se utiliza un factor de regularizaci´on, entonces el problema es equivalente a la versi´on sin restricciones dada por m´ın α 1 2kΘα−Yk2 2+λkαk1(C.4) 67 C. Algoritmos OMP y LASSO Para resolver este problema, se plantea una modificaci´on del algoritmo LAR(Least Angle Regression) llamada LARS(Least angle regression and shrinkage) que es capaz de resolver la regularizaci´on planteada por LASSO. En este anexo se describe una visi´on general del algoritmo, para una descripci´on m´as detallada consultar el trabajo de Efron et al. en [49]. Siendo, yla se˜nal a representar, Ala matriz que define la base del dominio en el que se quiere representar y, y xlos coeficientes a calcular de esta representaci´on, el algoritmo LAR consiste en Establecer todos los xj= 0. Encontrar el predictor Ajm´as correado con y. Aumentar el coeficiente xjen la direcci´on del signo de su correlaci´on con y. calcular el residuo r=y−Ax Repetir hasta que otro predictor Aktenga tanta correlaci´on con el residuo actual como Aj y a˜nadirlo al conjunto de predictores ativos. Aumentar (xj, xk) en su direcci´on conjunta por m´ınimos cuadrados hasta que otro predictor Amtenga tanta correlaci´on con el residuo actual como el conjunto de predictores activos. Continuar hasta que todos los predictores est´en en el modelo La modificaci´on necesaria para adaptarlo a LASSO consiste en: si un coefficiente xjdiferente de cero llega a cero, eliminarlo del conjunto activo y recalcular la direcci´on conjunta. C.2. OMP: Orthogonal Matching Pursuit Los algoritmos voraces aproximan iterativamente los coeficientes y el soporte de la se˜nal original. Tienen la ventaja de ser muy r´apidos y f´aciles de implementar. Uno de los m´as conocidos es OMP [50] que se describe a continuaci´on. Siendo, yla se˜nal a representar, Ala matriz que define la base del dominio en el que se quiere representar y, y xlos coeficientes a calcular de esta representaci´on. Entrada Matriz A= (ai)n i=1 ∈ <m×ny el vector x∈ <n Umbral del error  Algoritmo Establecer k= 0 Establecer la soluci´on inicial x0= 0. 68 C. Algoritmos OMP y LASSO Establecer el residuo inicial r0=y−Ax0=y. Establecer el soporte inicial S0=suppx0= 0. Repetir •Establecer k=k+ 1. •Escoger un i0tal que minckcai0−rk−1k2≤minckcai−rk−1k2para todo i. •Establecer Sk=Sk−1∪{i0}. •Calcular xk=argminxkAx −yk2sujeto a suppx =Sk. •Calcular rk=y−Axk. Hasta krkk2< . Salida Soluci´on aproximada xk 69 Anexo D. ´ Indice de v´ıdeos utilizados en el proyecto En este anexo se listan los v´ıdeos de la base de datos usados en la realizaci´on de este proyecto, as´ı como una breve descripci´on y la fuente donde poder consultar una versi´on en baja resoluci´on de los mismos. Es importante recordar que los experimentos realizados en el proyecto no pueden reproducirse con esta versi´on de los v´ıdeos, no obstante, la base de datos original esta disponible bajo petici´on. Los v´ıdeos se encuentran disponibles en un DVD suplementario junto con esta memoria, as´ı como en un fichero on-line. Enlace: https://drive.google.com/folderview?id=0Bxsb8iSM9CHNZ1ZQeml5TDFIWWs&usp=sharing D.1. V´ıdeos de entrenamiento Para el entrenamiento de diccionarios se han utilizado diez v´ıdeos con im´agenes de diferente naturaleza capturadas. Una muestra de cada uno de estos v´ıdeos puede verse en la Figura D.1. Listado de los v´ıdeos: Aspas: aspas de un ventilador manual girando. En el centro, el dibujo de un bal´on de f´utbol va girando a la misma velocidad. Resoluci´on espacial: 512 ×512 p´ıxeles. Resoluci´on temporal: 1000 fps. Duraci´on: 200 fotogramas. Blink: parpadeo de un ojo humano. Resoluci´on espacial: 512 ×512 p´ıxeles. Resoluci´on temporal: 1000 fps. Duraci´on: 200 fotogramas. Book: p´aginas de un libro de texto siendo pasadas. Resoluci´on espacial: 512 ×512 p´ıxeles. Resoluci´on temporal: 1000 fps. Duraci´on: 200 fotogramas. 71 D. ´ Indice de v´ıdeos utilizados en el proyecto Brain: objeto de goma con la forma de un cerebro rebotando en una mesa contra una cadena de bici. Resoluci´on espacial: 512 ×512 p´ıxeles. Resoluci´on temporal: 1000 fps. Duraci´on: 200 fotogramas. Coin: moneda de 50 c´entimos de Euro girando sobre una superficie. Resoluci´on espacial: 512 ×512 p´ıxeles. Resoluci´on temporal: 1000 fps. Duraci´on: 200 fotogramas. Dado: dado de veinte caras girando sobre una superficie. Resoluci´on espacial: 512 ×512 p´ıxeles. Resoluci´on temporal: 1000 fps. Duraci´on: 200 fotogramas. Dados: conjunto de dados de diferentes texturas cayendo y rebotando sobre una superficie. Resoluci´on espacial: 512 ×512 p´ıxeles. Resoluci´on temporal: 1000 fps. Duraci´on: 200 fotogramas. Drop: flujo de agua, incluyendo gotas, cayendo de un cuentagotas hacia una superficie. Resoluci´on espacial: 512 ×512 p´ıxeles. Resoluci´on temporal: 1000 fps. Duraci´on: 200 fotogramas. Globo: globo explotando bajo la influencia de una llama. Resoluci´on espacial: 512 ×512 p´ıxeles. Resoluci´on temporal: 1000 fps. Duraci´on: 200 fotogramas. Rueda: Rueda de un coche de juguete girando. Resoluci´on espacial: 512 ×512 p´ıxeles. Resoluci´on temporal: 1000 fps. Duraci´on: 200 fotogramas. D.2. V´ıdeos originales del an´alisis Para el an´alisis se han reconstruido v´ıdeos diferentes a los v´ıdeos de entrenamiento, tambi´en de diferente naturaleza entre ellos. Una muestra de cada uno de estos v´ıdeos puede verse en la 72 E. Caracterizaci´on de los v´ıdeos utilizados durante el an´alisis Figura E.4: M´etodos de caracterizaci´on para el v´ıdeo LlamaHold. En la fila de arriba se pueden ver el histograma de las varianzas de cada bloque (izquierda) y el histograma del ratio de energ´ıa de alta frecuencia temporal (derecha). En la fila de abajo se puede ver la imagen calculada como la suma de diferencias entre fotogramas consecutivos (izquierda), y la transformada de Fourier bi-dimensional (derecha). Figura E.5: M´etodos de caracterizaci´on para el v´ıdeo LlamaStart. En la fila de arriba se pueden ver el histograma de las varianzas de cada bloque (izquierda) y el histograma del ratio de energ´ıa de alta frecuencia temporal (derecha). En la fila de abajo se puede ver la imagen calculada como la suma de diferencias entre fotogramas consecutivos (izquierda), y la transformada de Fourier bi-dimensional (derecha). 79 E. Caracterizaci´on de los v´ıdeos utilizados durante el an´alisis Figura E.6: M´etodos de caracterizaci´on para el v´ıdeo Spring. En la fila de arriba se pueden ver el histograma de las varianzas de cada bloque (izquierda) y el histograma del ratio de energ´ıa de alta frecuencia temporal (derecha). En la fila de abajo se puede ver la imagen calculada como la suma de diferencias entre fotogramas consecutivos (izquierda), y la transformada de Fourier bi-dimensional (derecha). 80