Repositorio Institucional de Documentos

palabra ii palabra palabra palabra palabra palabra palabra palabra palabra palabra palabra A mis padres, J´aCC y Glo, a mi segunda madre, Pilar, a mi hermano, Alberto, a una peque˜na qu´ımica que apareci´o sin avisar, a B, a D y a todos mis amigos. iii palabra iv Agradecimientos palabra palabra palabra palabra palabra palabra palabra palabra palabra palabra Me gustar´ıa dar las gracias a Bel´en Y Diego por ofrecerme la posibilidad de trabajar en un campo tan novedoso, siendo los primeros (a nivel nacional); pero adem´as me gustar´ıa agradecer su tiempo, ayuda y, muchas veces, paciencia a lo largo del desarrollo mi proyecto fin de carrera. Tambi´en quiero agradecer a mis compa˜neros del grupo de trabajo (en el seno del GIGA) por sus aportaciones, y su buen humor, durante los d´ıas que hemos compartido lugar de trabajo. Finalmente, pero siempre importante, le doy las gracias a mi entorno por apoyarme en cada momento y, simplemente, por “estar ah´ı” (muchas veces desconociendo la relevancia de su existencia). v palabra vi RESUMEN palabra palabra palabra La fotograf´ıa computacional es un campo emergente nacido de la uni´on de la ´optica, el procesamiento de la se˜nal, la visi´on por computador, la inform´atica gr´afica o incluso de la electr´onica y el arte. En los ´ultimos a˜nos este campo ha producido avances espectaculares en cuanto al procesamiento de im´agenes se refiere. La fotograf´ıa tradicional se basa en representar espacialmente, en una matriz de dos dimensiones, la escena real que se est´a observando en el momento de la captura. Uno de los problemas de este proceso es la aparici´on de zonas borrosas (blur) en las im´agenes por falta de enfoque, movimiento (de la c´amara o de la escena) u otros motivos. Esto es as´ı puesto que se pierde la informaci´on necesaria para representar de manera correcta parte de la escena. Las primeras aproximaciones para resolver este problema se basaban en el estudio de las estad´ısticas de las im´agenes, con el objetivo de a˜nadir informaci´on consiguiendo recomponer parte de esa informaci´on perdida. En los ´ultimos a˜nos, de manera emergente, se han desarrollado nuevas t´ecnicas que permiten codificar la informaci´on en el proceso de captura de im´agenes. Este trabajo, aprovechando el surgimiento de estas t´ecnicas, presenta el uso de las aperturas codificadas como herramienta para codificar la informaci´on en el proceso de captura, consiguiendo eliminar blur y recuperar esas zonas borrosas. El trabajo se centra en la recuperaci´on de blur por desenfoque (proceso com´unmente denominado defocus deblurring), por lo que se asumir´a que las escenas capturadas no presentar´an blur por movimiento; esto quiere decir que tanto la c´amara como las escenas permanecer´an inm´oviles durante la captura de las mismas. La primera parte de este trabajo consiste en obtener aperturas codificadas cuyo dise˜no sea ´optimo (o casi ´optimo) para el problema de defocus deblurring. Esto se realizar´a planteando el problema como uno de optimizaci´on, que se resolver´a mediante un algoritmo gen´etico. Se obtendr´an, de esta manera, aperturas dise˜nadas para distintos niveles de ruido y con distinta resoluci´on espacial, para su posterior an´alisis y validaci´on. Estas aperturas se validar´an inicialmente mediante simulaciones, simulando el proceso de captura para obtener im´agenes con defocus blur, consiguiendo eliminar a posteriori la mayor parte del mismo. Despu´es, una vez validado el proceso mediante simulaci´on, se trasladar´a el problema a entornos reales con una c´amara fotogr´afica y la impresi´on de las aperturas en material fotolitogr´afico. Finalmente se mostrar´a, en forma de resultados, el correcto funcionamiento del proceso y las limitaciones del mismo. Se ha realizado tambi´en, como parte de este proyecto, un estudio del estado del arte del campo de la fotograf´ıa computacional; estudio que se ha considerado de inter´es por tratarse de un campo de investigaci´on de muy reciente aparici´on y por lo tanto con muy poca documentaci´on existente. Adem´as, parte de la investigaci´on realizada en este proyecto ha permitido la creaci´on de un art´ıculo aceptado en el Congreso Ibero-Americano de Inform´atica Gr´afica (SIACG 2011) que fue considerado como uno de los tres mejores art´ıculos del congreso, siendo propuesto para su extensi´on y sumisi´on al Computer Graphics Forum, revista JCR. vii palabra viii ´ Indice general 1. Introducci´on 1 2. Estado del arte 5 2.1. Definici´on de fotograf´ıa computacional . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2. Clasificaci´on en base al elemento modificado . . . . . . . . . . . . . . . . . . . . . 5 2.3. Clasificaci´on en base a la evoluci´on temporal . . . . . . . . . . . . . . . . . . . . 6 2.4. Clasificaci´on en base a la aplicaci´on final . . . . . . . . . . . . . . . . . . . . . . . 6 2.4.1. Captura de im´agenes de alto rango din´amico (HDR) . . . . . . . . . . . . 7 2.4.2. Extensi´on o modificaci´on de la profundidad de campo (DOF) . . . . . . . 7 2.4.3. Re-enfoque (Deblurring) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4.4. Detecci´on de profundidad . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4.5. Detecci´ondebordes .............................. 8 2.4.6. Flash/No-Flash................................. 9 3. Defocus deblurring 11 3.1. Formulaci´on matem´atica del problema . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2. Trabajoprevio ..................................... 14 3.3. Soluci´onadoptada ................................... 15 4. Obtenci´on de aperturas codificadas ´optimas 17 4.1. Elecci´on del m´etodo de optimizaci´on . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.2. Implementaci´on de un algoritmo gen´etico . . . . . . . . . . . . . . . . . . . . . . 18 4.2.1. Representaci´on................................. 19 4.2.2. Operadores gen´eticos: cruce y mutaci´on . . . . . . . . . . . . . . . . . . . 20 4.2.3. Condici´on de parada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3. Convergencia del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.4. Aperturasobtenidas .................................. 22 5. Validaci´on I: Simulaciones 25 5.1. Simulaci´on del proceso de captura y recuperaci´on de la informaci´on de la imagen 25 5.1.1. Proceso de captura o desenfoque de la imagen . . . . . . . . . . . . . . . . 25 5.1.2. Recuperaci´on de la informaci´on de la imagen . . . . . . . . . . . . . . . . 26 5.2. An´alisis del error obtenido: Norma L2e ´ındice SSIM . . . . . . . . . . . . . . . . 28 5.2.1. Norma L2.................................... 28 5.2.2. ´ Indice SSIM .................................. 29 5.3. Espectrodepotencia.................................. 30 ix 1. Introducci´on 4 2. Estado del arte En este apartado se va a exponer el estado del arte de la fotograf´ıa computacional, como tarea de exploraci´on y an´alisis previo al inicio del proyecto, mostrando el trabajo realizado por distintos investigadores en este campo. M´as que un an´alisis detallado y exhaustivo, que escapa al alcance de esta memoria, este estado del arte pretende ofrecer un vistazo general del campo. 2.1. Definici´on de fotograf´ıa computacional Como se ha visto en la introducci´on, la fotograf´ıa computacional es un campo de trabajo de reciente aparici´on que surge con el objetivo de obtener y explotar la informaci´on capturada de una escena, m´as all´a que la simple representaci´on en dos dimensiones de la misma. Haciendo uso de nuevas t´ecnicas se pretende obtener una representaci´on m´as completa del mundo real, traspasando las limitaciones de la fotograf´ıa tradicional. Mediante la creaci´on de nuevos algoritmos y m´etodos se pretende llevar m´as all´a los l´ımites de la fotograf´ıa tal y como la conocemos logrando, entre otras cosas, mejorar la calidad visual de una escena, cambiar la iluminaci´on de una imagen o recuperar informaci´on perdida por desenfoque. Obteniendo, incluso, im´agenes imposibles mediante el uso convencional de una c´amara fotogr´afica como son las fotograf´ıas panor´amicas o efectos de video como es el “tiempo bala” aparecido en distintas pel´ıculas (The Matrix) y videoclips (The Rolling Stones). 2.2. Clasificaci´on en base al elemento modificado Los cuatro elementos, principales, que componen la fotograf´ıa tradicional son: sistema de lentes encargado de hacer llegar la informaci´on de una escena al sensor; sensor fotosensible que recibe informaci´on de la escena; obturador que permite controlar la luz que llega al sensor; fuente externa de luz o flash usado para iluminar una escena. Estos elementos han sido explorados para crear nuevas metodolog´ıas de captura de im´agenes y en funci´on de cual de estos elementos es modificado se puede esbozar una primera clasificaci´on: Sistema de lentes: modificando la forma de la apertura en campos como la astronom´ıa [34], a˜nadiendo complejidad al sistema de lentes [21] o, incluso, prescindiendo del mismo [38] a la hora de capturar una imagen. 5 2. Estado del arte Sensor: modificando la forma del sensor dando lugar a la Plenoptic Camera [9], que permite capturar la informaci´on de la luz de manera n-dimensional [28], o modificando el funcionamiento del sensor para aumentar el rango din´amico [13] o el rango espectral de la imagen capturada. Obturador: se puede controlar la luz que llega al sensor de tal manera que se puedan obtener im´agenes n´ıtidas de un objeto en movimiento controlando la apertura y cierre del obturador [24] u obtener una imagen en alto rango din´amico combinando varias fotograf´ıas tomadas de manera casi simult´anea. Iluminaci´on: mejorar y controlar la iluminaci´on de la escena a capturar permite obtener representaci´on m´as completa de la misma, como la forma tridimensional de un objeto mediante la utilizaci´on de varios flashes estrat´egicamente posicionados [26], o haciendo uso de la t´ecnica llamada “flash/no-flash” [6]. 2.3. Clasificaci´on en base a la evoluci´on temporal Haciendo uso de la definici´on establecida por Ramesh Raskar [25] se puede hacer una clasificaci´on de la fotograf´ıa computacional, en base a su evoluci´on en el tiempo, apareciendo tres fases principales: fotograf´ıa ´epsilon, fotograf´ıa codificada y fotograf´ıa en esencia. Fotograf´ıa ´epsilon: construir una c´amara mejorada en cuanto a los par´ametros tradicionales se refiere (rango din´amico, campo de visi´on o profundidad de campo). Debido a la reducida capacidad de una c´amara, la escena se re-construye mediante la utilizaci´on de varias fotograf´ıas (cada una capturada con ´epsilon variaciones de los par´ametros de la c´amara). Fotograf´ıa codificada: construir herramientas que traspasen las capacidades de esta c´amara mejorada. El objetivo es codificar la informaci´on capturada de la escena (en una o muy pocas im´agenes) de tal manera que su decodificaci´on permita una descomposici´on vers´atil de la escena en base a sus par´ametros f´ısicos. Fotograf´ıa en esencia: el siguiente paso, en este momento sin explorar, ser´ıa olvidar que una c´amara fotogr´afica debe imitar al ojo humano. Intentando recuperar mayor informaci´on sobre la escena (la esencia de la escena), a parte de los par´ametros f´ısicos de la misma, la idea es poder generar nuevas formas de expresi´on art´ıstica visual y comunicaci´on. 2.4. Clasificaci´on en base a la aplicaci´on final La aplicaci´on final para la que se desarrollan m´etodos o t´ecnicas de captura de la infomaci´on de las escenas conforma otra clasificaci´on posible. A continuaci´on se exponen, en base a la aplicaci´on final, las t´ecnicas m´as destacadas. 6 2. Estado del arte 2.4.1. Captura de im´agenes de alto rango din´amico (HDR) Dise˜no del sensor Una primera aproximaci´on es el uso de varios elementos sensores con diferentes niveles de sensibilidad, combinando las distintas medidas obtenidas por cada elemento sensor en el chip antes de dar lugar a la imagen HDR, dando lugar a varias patentes [10, 29, 32]. Uno de los problemas de este enfoque es la reducci´on de la frecuencia de muestreo espacial (pudiendo aparecer efectos de aliasing) y la p´erdida de resoluci´on en la imagen final. Un enfoque diferente se propuso en [3], donde se mide el tiempo que le cuesta al sistema llegar a la saturaci´on de cada zona de la imagen capturada. De esta manera, ese tiempo codifica la informaci´on de alto rango din´amico, al ser inversamente proporcional a la luminosidad de cada zona de la imagen. Existen enfoques m´as novedosos y flexibles donde la exposiciones var´ıan a trav´es del espacio de la c´amara [1, 22]. Usando patrones con diferentes niveles de sensibilidad la flexibilidad del sistema aumenta aunque, de nuevo, la resoluci´on espacial disminuye y pueden aparecer efectos de aliasing. Las distintas mediciones capturadas se combinan creando una imagen HDR. Exposici´on m´ultiple Otra aproximaci´on para obtener im´agenes en HDR es capturar varias im´agenes usando, para cada una, diferentes niveles de exposici´on. La idea principal es resaltar las zonas oscuras con niveles de exposici´on altos (saturando las zonas claras de la escena) y al contrario con niveles de exposici´on bajos. De esta manera, cuando una misma escena es capturada con distintos niveles de exposici´on, se pueden combinar las im´agenes seleccionando cada p´ıxel de aquella imagen en la que no aparece muy oscuro ni saturado. Esta t´ecnica se llama sucesi´on de exposiciones y ha sido utilizada por numerosos autores [4, 17]. Estos autores asumen que el brillo medido por el sistema de captura (c´amara) se relaciona linealmente con los valores de la escena real pero, casi siempre, existe una relaci´on no lineal entre ambos. Debido a este motivo algunos autores han propuesto m´etodos para estimar la funci´on de respuesta radiom´etrica de una c´amara, obteniendo mapas de radiancia (donde los valores de los p´ıxeles en la imagen final son proporcionales a los valores de la escena real) utilizados, por ejemplo, en aplicaciones m´edicas [5, 18, 19]. 2.4.2. Extensi´on o modificaci´on de la profundidad de campo (DOF) Los dispositivos de captura de im´agenes tienen limitaciones relacionadas con la configuraci´on f´ısica existente en el dispositivo en el momento de realizar una captura. Entre ellas se encuentra la profundidad de campo definida por el tama˜no del diafragma utilizado en el momento de la captura. Aunque el concepto se explicar´a en la Secci´on 3, la profundidad de campo determina, a grandes rasgos, qu´e objetos de la escena aparecer´an enfocados y cu´ales desenfocados en la imagen final. En el a˜no 2006 se desarroll´o una c´amara que permite obtener im´agenes enfocadas a distintas profundidades [28]. Para desarrollar el dispositivo, se insert´o una matriz de “micro-lentes” entre 7 2. Estado del arte el sensor y el sistema de lentes de tal manera que cada micro-lente obtiene informaci´on de manera independiente a las dem´as, reordenando los rayos incidentes se consigue enfocar la imagen a distintas profundidades. Esta implementaci´on permite enfocar digitalmente una imagen y variar la profundidad de campo, lo que ofrece posibilidades muy altas de personalizaci´on de las im´agenes finales con el uso de una c´amara que funciona exactamente igual que una c´amara convencional (desde el punto de vista del usuario). En el a˜no 2008, se present´o un dispositivo que extiende la profundidad de campo a un nivel superior pudiendo, adem´as de enfocar objetos a distintas profundidades en una escena, eliminar ´opticamente un objeto a una profundidad (DOF discont´ınuo) o incluso variar la inclinaci´on de la profundidad de campo (DOF inclinado) [20]. La idea principal para crear este dispositivo es dar libertad de movimiento al sensor, posibilitando variar la profundidad de campo sin cambiar el tama˜no del diafragma del objetivo. 2.4.3. Re-enfoque (Deblurring) La aparici´on de zonas desenfocadas o blur degrada significativamente la calidad de la imagen final. Por ello, en los ´ultimos a˜nos, algunos investigadores han propuesto distintos m´etodos intentando disminuir el efecto ocurrido en este tipo de im´agenes. Las primeras aproximaciones se basaban en estimar la funci´on de dispersi´on del punto (PSF, explicada en la Subsecci´on 3.1), del sistema de captura para usarla en el proceso de re-enfoque [2, 33]. Si bien es cierto que la mayor´ıa de t´ecnicas desarrolladas se han basado en paliar el desenfoque por presencia de movimiento, recientemente se ha presentado una soluci´on para las im´agenes con desenfoque por falta de enfoque [36]. Mediante el uso de una apertura codificada se consigue recuperar parte de la informaci´on que, a simple vista, se hab´ıa perdido en el proceso de captura de la escena. 2.4.4. Detecci´on de profundidad Varios autores han realizado estudios acerca de la obtenci´on de la profundidad de una escena fotografiada, mediante el uso de una apertura codificada ´optima dise˜nada en base a las estad´ısticas de las im´agenes [15], utilizando parejas de aperturas codificadas de alta resoluci´on [35] o analizando la variaci´on del desenfoque aparecido en los bordes de la imagen [37]. 2.4.5. Detecci´on de bordes En el a˜no 2003 se present´o un prototipo basado en una c´amara con un flash m´ultiple con el objetivo de detectar los bordes de los objetos de una escena [26]. El m´etodo desarrollado obtiene cuatro fotograf´ıas de la misma escena iluminadas desde distintas posiciones (arriba, abajo, derecha e izquierda) con el fin de detectar las sombras proyectadas por los objetos de la escena. Adem´as demostraron que esta t´ecnica se pod´ıa utilizar para detectar bordes en v´ıdeos mediante el uso de una secuencia muy r´apida de los cuatro flashes. 8 2. Estado del arte 2.4.6. Flash/No-Flash En 2001 se explor´o por primera vez la idea de capturar la misma escena con y sin el uso del flash de la c´amara (t´ecnica “flash/no-flash”) [6]. Con este m´etodo consiguen obtener una imagen de la escena como si s´olo estuviese iluminada con el flash (sin luz ambiental), estiman las funciones de reflectancia de los objetos de la escena y estiman la distribuci´on espectral de la iluminaci´on ambiente. Bajo este mismo enfoque, otros autores [7, 23] han desarrollado m´etodos de combinaci´on de pares de im´agenes de escenas con poca iluminaci´on ambiental, ya que las im´agenes sin flash poseen altos niveles de ruido y las im´agenes tomadas con flash alteran el color de los objetos de la escena. Recientemente se ha presentado un prototipo de c´amara con un flash que utiliza luz infrarroja y ultravioleta fuera del rango visible, llamado flash oscuro [14]. 9 2. Estado del arte 10 3. Defocus deblurring En general, cuando se utiliza una c´amara fotogr´afica se pretende obtener una copia de la escena que se est´a visualizando, pero en m´ultiples ocasiones las im´agenes capturadas poseen zonas borrosas. Estas zonas, generalmente indeseadas, se denominan blur y con deblurring se define el proceso de eliminaci´on de la mayor parte (idealmente del total) de esas zonas borrosas. ´ Este es uno de los motivos por los que se comenzaron a estudiar distintas t´ecnicas de re-enfoque de im´agenes o deblurring techniques. Aunque, en la actualidad, una gran cantidad de equipos fotogr´aficos son muy sofisticados, el blur en las im´agenes sigue siendo un problema de gran inter´es de estudio. Los motivos de este problema son por un lado humanos, como el movimiento de la c´amara o la ausencia de un enfoque correcto a la hora de hacer una captura. Por otro lado, existen motivos inherentes a la c´amara como son la resoluci´on del sensor o la presencia de filtros en el mismo. Por ello, en ciertas ocasiones es inevitable obtener im´agenes como las mostradas en la Figura 3.1, que muestra dos ejemplos de im´agenes con blur. Los problemas inherentes al equipo son m´as complicados de subsanar (siendo la mejora en la imagen casi inapreciable) por lo que, generalmente, la fotograf´ıa computacional trabaja en la eliminaci´on del blur por movimiento y del blur por desenfoque. Figura 3.1: Izquierda: imagen con blur por desenfoque. Derecha: imagen con blur por movimiento. El motivo de la existencia de blur por desenfoque (defocus blur) deriva del tama˜no de la apertura utilizada para la captura. Su di´ametro establece la profundidad de campo en el momento de la captura, que es el intervalo, en el eje Z (perpendicular al plano imagen y al plano del sensor), en el que los objetos de la escena aparecer´an enfocados en la imagen capturada (apareciendo desenfocados los objetos que est´en localizados fuera de dicho intervalo). Conforme el di´ametro del diafragma disminuye en tama˜no la profundidad de campo aumenta, siendo el caso extremo la pinhole camera en la que el di´ametro de diafragma es un punto. En una pinhole camera la profundidad de campo es infinita. 11 3. Defocus deblurring El enfoque de las c´amaras fotogr´aficas establece, para una profundidad d(distancia, en el eje Z, desde el sensor a un punto de la escena), un plano Pperpendicular al eje Z cuyos puntos est´an perfectamente enfocados; los sucesivos planos imagen (perpendiculares al eje Z) ir´an perdiendo enfoque a medida que vayan alej´andose del plano P. Esto se debe a que todos los rayos provenientes de un punto del plano Pinciden en un mismo punto del sensor de la c´amara, no ocurriendo as´ı con los puntos que se encuentran a otras profundidades. La aparici´on de blur en la imagen grabada se debe a que la informaci´on proveniente de esos puntos se distribuye por un ´area circular del sensor, como se puede ver en la Figura 3.2, creando los llamados c´ırculos de confusi´on. Figura 3.2: Concepto de profundidad de campo y c´ırculos de confusi´on. Los puntos del plano P est´an perfectamente enfocados. Los puntos de otros planos (fuera del intervalo definido por la profundidad de campo) est´an desenfocados, creando los llamados c´ırculos de confusi´on. 3.1. Formulaci´on matem´atica del problema El problema de aparici´on de blur en una imagen est´a estrechamente relacionado con la forma de la apertura utilizada para la obtenci´on de la misma. La siguiente ecuaci´on describe matem´aticamente el proceso de captura de una imagen: f=f0∗kd+η , (3.1) donde: fes la imagen desenfocada capturada, f0es dicha imagen perfectamente enfocada (i.e. la escena real), kdes la respuesta de la apertura utilizada a una profundidad d, ηes el ruido de la imagen. La respuesta kd, de la apertura utilizada var´ıa espacialmente en la escena seg´un las coordenadas 2D de dicha escena y la profundidad a la que se encuentra dicha escena respecto a la c´amara. Asimismo, no var´ıa s´olo con la profundidad absoluta sino tambi´en con la distancia entre el plano focal y la escena. Esta respuesta se denomina PSF (point spread function/funci´on de dispersi´on del punto) ya que codifica la respuesta del sistema cuando la entrada es un impulso (i.e. un punto). 12 3. Defocus deblurring Figura 3.3: Proceso, conceptual, de aparici´on de blur por desenfoque en im´agenes. Se asume que el ruido ηsigue una distribuci´on gaussiana de media 0 y una desviaci´on est´andar dada por σ,N(0, σ2). De manera conceptual, la ecuaci´on 3.1 se puede expresar como muestra la Figura 3.3. Figura 3.4: Apertura circular con distintos tama˜nos de diafragma. En las c´amaras fotogr´aficas (ya sean anal´ogicas o digitales) la apertura tiene forma aproximadamente circular, como se puede ver en la Figura 3.4. En el dominio de la frecuencia, la respuesta de una apertura circular disminuye la amplitud de las altas frecuencias en la imagen obtenida, lo que implica la p´erdida de los detalles en la escena, causando o incrementando el blur en la imagen (como se ver´a a lo largo de este trabajo); por lo que el paso de la ecuaci´on 3.1 al dominio de la frecuencia facilitar´a el an´alisis de dicha respuesta. Figura 3.5: Respuesta en el dominio de la frecuencia de una apertura circular. El eje X muestra frecuencia normalizada, n´otese que la escala del eje Y es logar´ıtmica. En la Figura 3.5 se puede ver la respuesta, en el dominio de la frecuencia de una apertura circular, se trata del espectro de potencia (power spectrum). ´ Este muestra el modo en que la 13 4. Obtenci´on de aperturas codificadas ´optimas Figura 4.2: Ejemplo de apertura codificada binaria. Dos tipos de p´ıxeles, negros (opacos) y grises (transparentes). Para las aperturas codificadas se ha elegido una representaci´on binaria. Teniendo en cuenta que el tama˜no de los cromosomas condicionar´a el tiempo de convergencia del algoritmo a una soluci´on v´alida, cada cromosoma se representa como un vector de n2elementos (genes), de manera que al mostrarlo en forma de matriz conforme una matriz n∗n, ya que se busca obtener una apertura codificada. De esta manera, el gen xen un cromosoma cualquiera ser´a el p´ıxel (x1, y1)de la apertura donde x1= (x/n) + 1 y y1=mod(x/n). Como se puede ver en la Figura 4.2, el valor posible para un gen tiene el siguiente significado: Gen cero o gen negro: no deja pasar la luz a su trav´es (como si de un objeto opaco se tratase). Gen uno o gen transparente: deja pasar perfectamente la luz a su trav´es (como si de un objeto perfectamente transparente se tratase). De esta manera, se puede hacer un peque˜no an´alisis del n´umero de posibles soluciones para la representaci´on elegida. Teniendo en cuenta el tama˜no de los cromosomas (n2genes) y los posibles valores para cada uno de ellos (cero o uno), se puede determinar que el n´umero de soluciones posible es 2n2. 4.2.2. Operadores gen´eticos: cruce y mutaci´on Los operadores gen´eticos son funciones empleadas en los algoritmos gen´eticos para mantener la diversidad gen´etica en cada generaci´on, siendo necesarios para obtener una evoluci´on correcta de los individuos de la poblaci´on. El operador de cruce equivale a la reproducci´on sexual y el operador de mutaci´on equivale a la mutaci´on biol´ogica. El operador de cruce es un operador binario; es el encargado de generar dos nuevos cromosomas a partir de una pareja de cromosomas base. Tal y como se ve en la Figura 4.3, el procedimiento es recorrer (gen a gen) los cromosomas base intercambiando, con una cierta probabilidad c1, los genes entre la pareja de cromosomas. Figura 4.3: Operador binario de cruce. 20 4. Obtenci´on de aperturas codificadas ´optimas El operador de mutaci´on, sin embargo, es un operador unario; es el encargado de a˜nadir variabilidad al genotipo. En este caso, como se ve en la Figura 4.4, el procedimiento es recorrer (de nuevo, gen a gen) el cromosoma a mutar cambiando, con una cierta probabilidad c2, el valor de sus genes (de cero a uno, o viceversa). Figura 4.4: Operador unario de mutaci´on. 4.2.3. Condici´on de parada La alternativa que mejor determina la detenci´on del algoritmo es establecer un n´umero m´aximo de generaciones. Hay que entender que hay otro tipo de condiciones de parada, como la convergencia del algoritmo a un valor o la no evoluci´on del cromosoma “mejor” a lo largo de varias generaciones. As´ı, se podr´ıan a˜nadir otras condiciones de parada, pero dada la naturaleza del problema que ocupa este trabajo es muy complicado determinar una condici´on de parada robusta (en t´erminos de error relativo de la soluci´on). 4.3. Convergencia del algoritmo Una vez implementado el algoritmo gen´etico, encargado de generar aperturas codificadas que despu´es se iban a utilizar a la hora de recuperar informaci´on perdida en im´agenes con blur por desenfoque, se crey´o conveniente realizar un estudio acerca de la convergencia del algoritmo en base a sus par´ametros (poblaci´on, n´umero de supervivientes, n´umero de generaciones, probabilidad de cruzamiento y probabilidad de mutaci´on). Para ello se estableci´o un conjunto de ejecuciones entre las cuales la ´unica variaci´on era el valor de uno, y s´olo uno, de los par´ametros de llamada con el fin de interpretar la influencia de los mismos en los resultados finales (siempre con el mismo valor para el par´ametro “ruido”, i.e. σen la ecuaci´on 4.1). Se propuso realizar cinco ejecuciones para diez valores distintos para cada par´ametro, obteniendo 250 aperturas (250 = (5 ejecuciones * 10 valores) * 5 par´ametros). De esta manera, se obtuvieron los valores alcanzados por la funci´on de evaluaci´on R(K) durante la sucesi´on de generaciones, as´ı como los tiempos empleados para cada ejecuci´on. A la vista de los resultados, que se muestran en las Figuras 4.5 y 4.6, y en el Ap´endice C, se decidieron utilizar los siguientes valores para los par´ametros del algoritmo: 4000 individuos conformando el genotipo, 400 supervivientes en cada generaci´on, 80 generaciones, probabilidad de cruzamiento de 0.2 y probabilidad de mutaci´on de 0.05. 21 4. Obtenci´on de aperturas codificadas ´optimas Figura 4.5: Izquierda, eje horizontal: distintos valores para el par´ametro generaciones, eje vertical: tendencia de la funci´on de evaluaci´on R(K)con la variaci´on del par´ametro generaciones. Derecha, eje horizontal: distintos valores para el par´ametro generaciones, eje vertical: tendencia del tiempo de ejecuci´on del algoritmo con la variaci´on del par´ametro generaciones. Figura 4.6: Supervivientes (porcentaje con respecto al n´umero de individuos de la poblaci´on). Izquierda, eje horizontal: distintos valores para el par´ametro supervivientes, eje vertical: tendencia de la funci´on de evaluaci´on R(K)con la variaci´on del par´ametro supervivientes. Derecha, eje horizontal: distintos valores para el par´ametro supervivientes, eje vertical: tendencia del tiempo de ejecuci´on del algoritmo con la variaci´on del par´ametro supervivientes. 4.4. Aperturas obtenidas A la hora de obtener una apertura codificada mediante la utilizaci´on del algoritmo gen´etico, uno de los factores m´as importantes a tener en cuenta es el valor de sigma (es decir, la desviaci´on est´andar del ruido de la imagen) para el cual se quiere obtener la misma. Dada la ecuaci´on 4.1, que define la funci´on de evaluaci´on utilizada, se puede ver que el valor de sigma determinar´a el tipo de apertura codificada obtenida. En este trabajo se eligieron distintos valores de sigma, cubriendo un amplio rango de soluciones, y para cada uno se realizaron varias ejecuciones del algoritmo gen´etico (siete exactamente) con el objetivo de seleccionar la apertura con mejor puntuaci´on en cada caso. En la Figura 4.7 se muestran las mejores aperturas obtenidas para distintos valores de sigma. Adem´as, como se anunciaba en la introducci´on de este documento, con el objetivo de explo- 22 4. Obtenci´on de aperturas codificadas ´optimas rar el rendimiento obtenido para aperturas con distintas caracter´ısticas, se obtuvieron aperturas con distinta resoluci´on. Como se puede ver en la Figura 4.8, se obtuvieron aperturas de tama˜no 7*7 y de tama˜no 20*20 para dos valores representativos de σ. Figura 4.7: Aperturas 11*11 obtenidas para distintos valores de σ. Figura 4.8: Arriba: aperturas 7*7 obtenidas con el correspondiente valor de σ.Abajo: aperturas 20*20 obtenidas con el correspondiente valor de σ. 23 4. Obtenci´on de aperturas codificadas ´optimas 24 5. Validaci´on I: Simulaciones Una vez obtenido un conjunto de aperturas para distintos niveles de ruido el siguiente paso es evaluarlas. El m´etodo explicado en este cap´ıtulo permite simular la captura de una imagen desenfocada a partir de una imagen enfocada para, a posteriori, re-enfocarla y poder comparar el resultado obtenido con la imagen inicial. Esta simulaci´on supone el primer paso en la validaci´on de las aperturas obtenidas, al confirmar que consiguen mejores resultados que una apertura circular. 5.1. Simulaci´on del proceso de captura y recuperaci´on de la informaci´on de la imagen El procedimiento desarrollado se puede ver en la Figura 5.1. Partiendo de una imagen totalmente enfocada f0, se obtiene la imagen fsimulando el proceso de captura de una fotograf´ıa desenfocada (con una apertura k). Como segunda parte del proceso se parte de la imagen desenfocada f, a partir de la cual se obtiene la imagen re-enfocada ˆ f0(con la misma apertura k). Finalmente, como an´alisis del resultado obtenido para la apertura k, se mide el error mediante la utilizaci´on de una m´etrica objetiva de comparaci´on entre f0yˆ f0. Los resultados finales de esta m´etrica se calcularon realizando la media entre los resultados obtenidos para un conjunto de diez im´agenes distintas. Figura 5.1: De izquierda a derecha: proceso de desenfoque y re-enfoque de una imagen utilizando una apertura k, que permite validar dicha apertura. 5.1.1. Proceso de captura o desenfoque de la imagen Conviene recordar la ecuaci´on 3.1 que define una imagen desenfocada: f=f0∗kd+η , (5.1) 25 5. Validaci´on I: Simulaciones donde fes la imagen desenfocada, f0es dicha imagen perfectamente enfocada (i.e. la escena real), kdes la respuesta de la apertura utilizada a una profundidad dyηes el ruido de la imagen. La ecuaci´on 5.1 define el proceso real ocurrido en la toma de una fotograf´ıa con una c´amara (anal´ogica o digital) en el dominio espacial. Como se puede ver, interviene el operador convoluci´on entre la imagen perfectamente enfocada y la apertura existente en la c´amara fotogr´afica en el momento de la toma. Si todos los par´ametros de la ecuaci´on 5.1 son llevados al dominio de la frecuencia, haciendo uso de la transformada de Fourier, la convoluci´on pasa a ser una multiplicaci´on: F=F0·Kd+ζ(5.2) En la imagen 5.2 se puede ver la simulaci´on del desenfoque (derecha) de una imagen totalmente enfocada (izquierda), mediante la utilizaci´on de la ecuaci´on 5.2 (es decir, la obtenci´on de f). La apertura utilizada se normaliza con respecto a una apertura circular, simulando la p´erdida de luz en la captura real, lo que produce el oscurecimiento en la imagen desenfocada. Figura 5.2: Izquierda: imagen enfocada f0.Derecha: imagen fobtenida mediante la ecuaci´on 5.2, simulando una captura mediante el uso de la apertura mostrada en la esquina inferior derecha, apertura ´optima obtenida para σ= 0,005. 5.1.2. Recuperaci´on de la informaci´on de la imagen En este caso, partiendo de una imagen desenfocada f, se pretende conseguir una imagen ˆ f0 id´entica a la escena original capturada f0(en este caso conocida). Haciendo uso de la formulaci´on establecida para la deconvoluci´on de Wiener [27]: 26 5. Validaci´on I: Simulaciones ˆ F0=F·¯ K |K|2+|C|2(5.3) donde ˆ F0es la imagen recuperada; Fes la imagen desenfocada y Kes la apertura utilizada (todas ellas en el dominio frecuencial). Ces la relaci´on de potencia se˜nal-ruido y se puede obtener como σ2/A siendo Ala media del espectro de potencia de un conjunto de im´agenes naturales (ver Ap´endice A). Notar que el tama˜no (en p´ıxeles) de las variables en la ecuaci´on 5.3 son, por norma general, distintos ya que las aperturas tienen tama˜no 11*11 y, en la mayor´ıa de los casos, las im´agenes a tratar poseen un tama˜no mayor. Por ello, es necesario realizar un padding orelleno a la variable de menor tama˜no, en este caso a la apertura Kutilizada. Esta operaci´on de relleno consiste en insertar la apertura en el centro de una matriz de ceros, del tama˜no de la imagen a tratar. En la imagen 5.3 se puede ver la recuperaci´on de la informaci´on (derecha) de una imagen desenfocada (izquierda), mediante la utilizaci´on de la ecuaci´on 5.3 (es decir, la obtenci´on de ˆ f0). Figura 5.3: Izquierda: imagen desenfocada f.Derecha: imagen ˆ f0obtenida tras la recuperaci´on de la informaci´on, mediante la ecuaci´on 5.3, usando la apertura mostrada en la esquina inferior derecha, apertura ´optima obtenida para σ= 0,005. Como se ve en la Figura 5.3 la imagen recuperada ˆ f0no est´a perfectamente enfocada pero los detalles (i.e. d´ıgitos), que en la imagen desenfocada fno son apreciables, son perfectamente legibles. Adem´as se aprecia la existencia de artefactos en la imagen recuperada ˆ f0en forma de bandas negras, esto es debido a la operaci´on de deconvoluci´on. 27 5. Validaci´on I: Simulaciones 5.2. An´alisis del error obtenido: Norma L2e ´ındice SSIM Con el objetivo de establecer una cuantificaci´on para el error cometido al recuperar la informaci´on perdida en la captura de las im´agenes es necesario utilizar una m´etrica objetiva. Se han evaluado dos m´etricas distintas, que se detallan a continuaci´on. 5.2.1. Norma L2 Se decidi´o utilizar, en primera instancia, la norma (o distancia eucl´ıdea) L2entre la imagen recuperada ˆ f0tras la deconvoluci´on y la escena real (imagen totalmente enfocada) f0, que para im´agenes de tama˜no n·mse define como: d(ˆ f0, f0) = n·m X i=1,j=1 kˆ f0(i, j)−f0(i, j)k2(5.4) Cada p´ıxel en una imagen posee un valor entre 0 (totalmente negro) y 1 (totalmente blanco), de tal manera que la distancia m´axima entre dos p´ıxeles es 1. Como se puede ver en la Figura 5.4, la distancia L2entre dos im´agenes opuestas (una imagen cuyos p´ıxeles tienen, todos, valor 0 y otra imagen cuyos p´ıxeles tienen, todos, valor 1), obtiene como resultado la distancia m´axima posible o error m´aximo posible (tama˜no en p´ıxeles de las im´agenes). En cambio, calcular la distancia L2entre dos im´agenes iguales obtiene como resultado la distancia m´ınima posible o error m´ınimo posible (cero). Figura 5.4: Izquierda: norma (o distancia) L2entre dos im´agenes totalmente opuestas. Derecha: norma L2entre dos im´agenes totalmente iguales. Se calcul´o, de este modo, el resultado para la norma (o distancia) L2obtenido para cada apertura (en funci´on del valor de σ). En la Figura 5.5 se puede ver el porcentaje del error obtenido, con respecto al error m´aximo posible, para cada una de las aperturas. Figura 5.5: Resultados de la norma L2para aperturas calculadas para diferentes valores de σ. Se muestran los porcentajes con respecto al error m´aximo posible. Las mayor´ıa de las aperturas obtenidas dan lugar a un menor error con respecto al m´aximo error posible en comparaci´on con el error obtenido por una apertura circular. 28 5. Validaci´on I: Simulaciones En la Figura 5.5 se puede ver que la mayor´ıa de las aperturas obtenidas obtienen un porcentaje menor de error (norma L2), en el proceso de recuperaci´on de informaci´on, que una apertura circular. Las que tienen un porcentaje de error mayor son las calculadas para valores de σelevados, muy superiores al nivel de ruido de las im´agenes utilizadas en la validaci´on. 5.2.2. ´ Indice SSIM Con el objetivo de verificar la validez de los resultados obtenidos con la norma L2se decidi´o utilizar otra m´etrica, eligiendo para ello la medida SSIM por su aceptaci´on entre los investigadores en el campo de la inform´atica gr´afica. La medida SSIM [31] se desarroll´o como mejora de m´etodos tradicionales de comparaci´on de im´agenes ya que, en teor´ıa, tiene en cuenta la percepci´on humana. Normalmente se calcula entre conjuntos de p´ıxeles de las im´agenes a comparar (ventanas de tama˜no n·n). Para dos ventanas (xey), se define como: SSIM(x, y) = (2µxµy+c1)(2σxy +c2) (µ2 x+µ2 y+c1)(σ2 x+σ2 y+c2),(5.5) donde, µx,µxson la media, σ2 x,σ2 yes la varianza, σxy es la convarianza de xyyrespectivamente yc1,c2son constantes obtenidas por el rango din´amico Lde las im´agenes que se van a comparar (donde L= 2#bits por p´ıxel −1). En este caso, como se puede ver en la Figura 5.6, el ´ındice SSIM entre dos im´agenes opuestas, obtiene como resultado el menor valor posible (-1). En cambio, el ´ındice SSIM entre dos im´agenes iguales obtiene como resultado el mayor valor posible (uno). Figura 5.6: Izquierda: ´ındice SSIM entre dos im´agenes totalmente opuestas. Derecha: ´ındice SSIM entre dos im´agenes totalmente iguales. Se calcul´o, de este modo, el resultado para la medida SSIM obtenido para cada apertura (en funci´on del valor de σ). En la Figura 5.7 se pueden ver los ´ındices obtenidos para cada una de las aperturas. Figura 5.7: Resultados de la medida SSIM para aperturas calculadas para diferentes valores de σ. Se muestran los valores obtenidos para dicha medida (´ındice SSIM). La mayor´ıa de las aperturas obtenidas dan lugar a un ´ındice SSIM mayor en comparaci´on con el ´ındice obtenido por una apertura circular. 29 6. Validaci´on II: Experimentos reales distancia cualquiera y para cualesquiera coordenadas de la imagen. Si se est´a fotografiando un objeto que ocupa, en el eje X, una gran parte de la imagen capturada, el obtener la PSF de la apertura codificada en las coordenadas correspondientes a uno de los extremos del objeto dar´ıa una recuperaci´on distinta de la imagen en esa posici´on que en el extremo contrario. Por ello, idealmente, se necesitar´ıa un “tablero” en el que se pudiesen colocar emisores puntuales de luz id´enticos en cuanto a luminosidad y a distintas alturas (cubriendo todo el plano imagen a cada profundidad para poder elegir con cual de las PSFs se quiere desenfocar qu´e parte de la imagen desenfocada, como se muestra en la Figura 6.4. As´ı, dada una imagen desenfocada, se podr´a elegir con cual de las PSFs se quiere recuperar qu´e parte de la imagen desenfocada. Figura 6.4: Tablero ideal para obtener un conjunto de PSFs de una apertura codificada a una distancia cualquiera. Esta idea se va a denominar array de diodos LED. Se construy´o un array de diodos LED, de una sola fila con 8 diodos LED separados entre s´ı 10 cent´ımetros usando materiales “caseros” (cart´on, cable de cobre y un soldador de esta˜no). Este array 1D fue utilizado para obtener las PSF que intervinieron en la recuperaci´on de informaci´on de las fotograf´ıas con blur, obtenidas con la c´amara. En la Figura 6.5 se muestra el array de diodos LED una vez construido. En la imagen superior se muestra la respuesta (como se puede ver es el propio punto de luz) de la apertura cuando el array de diodos LED est´a totalmente enfocado. En las im´agenes central e inferior se muestra la respuesta de la apertura a medida que se va desenfocando la escena capturada. La metodolog´ıa utilizada para las capturas se explica en la siguiente secci´on. Figura 6.5: Array de diodos LED construido. Arriba: PSFs con el array de diodos LED totalmente enfocado (puntos). Abajo: PSFs para dos desenfoques distintos del array de diodos LED, a profundidades de desenfoque de 50 cent´ımetros y un metro. 36 6. Validaci´on II: Experimentos reales 6.2.3. Captura de las im´agenes de calibraci´on Una vez introducida una apertura en el objetivo de la c´amara fotogr´afica, mediante el uso del array de diodos LED explicado, se procedi´o a obtener sus PSFs a distintas profundidades de desenfoque. En este trabajo, con el objetivo de obtener datos para un intervalo amplio de trabajo, se obtuvieron las PSFs para 10 distancias distintas. Esto se consigui´o alejando el array de diodos LED, desde la distancia D(plano focal, escena enfocada), en intervalos de diez cent´ımetros hasta llegar a una distancia (con respecto a la c´amara) de dos metros, como se muestra en la Figura 6.6. Notar que, para hacer el proceso m´as preciso, se utiliz´o un disparador a distancia para no tener que tocar f´ısicamente la c´amara entre las distintas capturas. Figura 6.6: Procedimiento utilizado para obtener las PSFs de una apertura insertada en el objetivo de la c´amara. Los pasos para la obtenci´on de las PSFs son: Se fija la c´amara en una posici´on en la que pueda permanecer inm´ovil durante todo el proceso. Se enfoca el array de diodos LED a una distancia Den el eje Z desde la posici´on de la c´amara (en este caso D= 1m). Los objetos en otras posiciones en el eje Z, como se explic´o en el Cap´ıtulo 3, aparecer´an desenfocados a medida que se incremente su distancia con respecto a D. Manteniendo el enfoque a la distancia Dse mueve el array de diodos LED en el eje Z para obtener la PSF de la apertura a distintas profundidades de desenfoque. De esta manera, para cada apertura, se obtiene un conjunto de PSFs como el mostrado en la Figura 6.3. 6.3. Captura y recuperaci´on de las im´agenes con blur Una vez calibrado el sistema, la metodolog´ıa aplicada a la hora de capturar im´agenes con blur fue la misma que la explicada para la obtenci´on de las PSFs de una apertura, es decir, fijar el enfoque a una distancia D= 1m y, a continuaci´on, mover la escena (variando la profundidad) sin modificar ning´un otro par´ametro obteniendo, finalmente, im´agenes desenfocadas. La diferencia en el caso de la obtenci´on de im´agenes con blur es que, una vez finalizado el proceso de captura para las distintas distancias, se procedi´o a capturar las mismas escenas totalmente enfocadas. Esto se decidi´o para que, una vez se procediese con la recuperaci´on de la informaci´on perdida, se pudiera comparar la imagen resultante con la escena real (totalmente enfocada). Se tomaron im´agenes con las aperturas obtenidas y con la apertura circular (inherente al objetivo) 37 6. Validaci´on II: Experimentos reales para comparar los resultados, mostrando los mismos en la siguiente secci´on. Finalmente, se procedi´o a recuperar la informaci´on de las im´agenes capuradas de forma an´aloga a la explicaci´on de la Subsecci´on 5.1.2 para los resultados simulados. Se utiliza la deconvoluci´on de Wiener, con una estimaci´on de SNR de 0.005. 6.4. Resultados Despu´es de explicar la metodolog´ıa para los experimentos reales se muestran, en las Figuras 6.7 y 6.8, dos ejemplos de los resultados obtenidos en la recuperaci´on de im´agenes con blur. En el Ap´endice D se muestran un conjunto de resultados obtenidos para el resto de aperturas evaluadas. Las aperturas evaluadas son las generadas para valores de σpeque˜nos (menores de 0.005), por ser las que daban mejores resultados en las simulaciones (v´eanse las Figuras 5.5 y 5.7 de la Secci´on 5.2). Los valores de ruido mayores son inusuales en fotograf´ıas convencionales, aunque no se ha comprobado para capturas de escenas con poca iluminaci´on (i.e. escenas nocturnas) en las que el ruido podr´ıa alcanzar valores mayores. En las Figuras 6.7 y 6.8 se puede ver la recuperaci´on de informaci´on totalmente perdida como las letras de los libros en las escenas fotografiadas. En las figuras se pretende enfocar los objetos que est´an posicionados en el centro de la imagen con blur (a una profundidad de desenfoque de 40 cm y 60 cm, respectivamente). Para ello se utiliz´o la respuesta m´as cercana, del array de diodos LED, al centro de la imagen. Al utilizar la respuesta, cuyas coordenadas se aproximan al centro de la imagen con blur, se consigue recuperar la informaci´on de los objetos que, espacialmente, est´an alrededor de esas coordenadas (siempre que su profundidad sea la misma que la de la respuesta utilizada). Sin embargo, en la Figura 6.9 se puede apreciar la existencia de objetos a distintas profundidades, cuya informaci´on no se recupera. En dichas zonas de la imagen aparecen artefactos puesto que la PSF con la que se deconvoluciona no es la adecuada para esas profundidades. No obstante, en el centro de la figura, se puede comprobar la calidad de nuestras aperturas codificadas a la hora de usar su respuesta para recuperar la informaci´on perdida en una captura. En la Figura 6.10 se puede ver una comparativa de los resultados obtenidos con aperturas ´optimas para tres valores distintos de σcon los resultados obtenidos al utilizar la PSF de una apertura circular en igualdad de condiciones (misma profundidad de desenfoque). Como se puede apreciar, la recuperaci´on de informaci´on con una apertura circular es m´ınima, en comparaci´on con la recuperaci´on obtenida con aperturas codificadas, apareciendo gran cantidad de artefactos (esta vez debido a la mala respuesta de una apertura circular). 38 6. Validaci´on II: Experimentos reales Figura 6.7: Resultado de la apertura ´optima para σ=0.005 para profundidad de desenfoque de 40 cent´ımetros. Arriba a la izquierda: foto capturada con aparici´on de blur y PSF de la apertura utilizada, a la derecha: zoom de detalle de la escena totalmente enfocada. Abajo a la izquierda: zoom de detalle de la foto capturada, a la derecha: zoom de detalle de la foto obtenida tras recuperar la informaci´on perdida en la captura. Figura 6.8: Resultado de la apertura ´optima para σ=0.0001 para profundidad de desenfoque de 60 cent´ımetros. Arriba a la izquierda: foto capturada con aparici´on de blur y PSF de la apertura utilizada, a la derecha: zoom de detalle de la escena totalmente enfocada. Abajo a la izquierda: zoom de detalle de la foto capturada, a la derecha: zoom de detalle de la foto obtenida tras recuperar la informaci´on perdida en la captura. 39 6. Validaci´on II: Experimentos reales Figura 6.9: Importancia de la profundidad de desenfoque para la que se obtiene la PSF utilizada en el proceso. La informaci´on de los objetos que est´an a distinta profundidad de desenfoque (como el marcado en la figura) no podr´a ser recuperada. Arriba a la izquierda: foto capturada con aparici´on de blur y PSF de la apertura utilizada, a la derecha: zoom de detalle de la escena totalmente enfocada. Abajo a la izquierda: zoom de detalle de la foto capturada, a la derecha: zoom de detalle de la foto obtenida tras recuperar la informaci´on perdida en la captura. 40 6. Validaci´on II: Experimentos reales Figura 6.10: Comparativa entre resultados obtenidos con aperturas codificadas y una apertura circular en igualdad de condiciones. Arriba: resultados de la apertura ´optima para σ=0.005 y una apertura circular para profundidad de desenfoque de 40 cent´ımetros. Centro: resultados de la apertura ´optima para σ=0.0001 y una apertura circular para profundidad de desenfoque de 60 cent´ımetros. Abajo: resultados de la apertura ´optima para σ=0.002 y una apertura circular para profundidad de desenfoque de 90 cent´ımetros. 41 6. Validaci´on II: Experimentos reales 42 7. Conclusiones y trabajo futuro Una vez finalizado el proyecto, se van a poner de manifiesto las aportaciones y limitaciones encontradas en el trabajo realizado, a modo de resumen final sobre el mismo. Adem´as se comentar´an los posibles puntos que se podr´ıan extender en un trabajo futuro y las conclusiones personales obtenidas. 7.1. Conclusiones La primera parte del proyecto gener´o un amplio trabajo de investigaci´on en un campo emergente, como lo es la fotograf´ıa computacional, recopilando un estudio del arte. Dicho estudio ofrece una visi´on sucinta, pero representativa y estructurada, de un campo de muy reciente aparici´on y con muy poca literatura establecida. El proyecto ofrece una soluci´on de blur por desenfoque en im´agenes. Para ello, el trabajo se bas´o en una reciente aproximaci´on para dicho problema, utilizando aperturas codificadas. De esta manera, se implement´o un algoritmo gen´etico que obtendr´ıa un conjunto de aperturas codificadas. Hay que tener en cuenta que los m´ultiples par´ametros de este tipo de algoritmos deben ser estudiados, con el objetivo de encontrar una soluci´on v´alida (en este caso una apertura codificada con mejores resultados que una apertura circular), para lo cual se realiz´o un estudio de la convergencia del algoritmo. Se analizaron las aperturas codificadas obtenidas por el algoritmo gen´etico, comparando sus resultados con los resultados obtenidos por una apertura circular, en un entorno controlado de simulaciones. Una vez validadas estas aperturas, se procedi´o a realizar pruebas con experimentos reales concluyendo los resultados obtenidos en la Secci´on 6.4 y en el Ap´endice D. El trabajo desarrollado permite recuperar informaci´on perdida en una imagen, siendo las ´unicas entradas una fotograf´ıa con blur y la PSF con la que se desea trabajar. Con el m´etodo desarrollado se ha conseguido recuperar gran parte de la informaci´on perdida en la captura de una escena, demostr´andose un rendimiento de las aperturas obtenidas claramente superior al de una apertura circular. Sin embargo, existen algunas limitaciones que no permiten recuperar la “totalidad” de la informaci´on perdida. La limitaci´on principal es la utilizaci´on de la misma PSF en toda la imagen capturada, en la que puede haber objetos a distintas profundidades. El m´etodo desarrollado permite recuperar la informaci´on perdida en la zona de la imagen en la que los objetos est´an a una profundidad conocida, apareciendo artefactos en el resto de la imagen. 43 7. Conclusiones y trabajo futuro 7.2. Desarrollo del proyecto El tiempo dedicado al desarrollo de este trabajo ha sido de 10 meses en dos intervalos temporales. La primera parte del proyecto, dedicada completamente al estudio del estado del arte de la fotograf´ıa computacional e investigaci´on de trabajos realizados por otros autores, se realiz´o durante abril y junio de 2010 durante tres horas diarias (a la vez, realizando asignaturas pendientes de la titulaci´on). El proyecto se retom´o en septiembre de 2010 con una jornada laboral de seis horas diarias hasta el mes de noviembre; a partir de entonces y hasta febrero de 2010 la jornada laboral ha sido de ocho horas diarias. Siendo un proyecto de investigaci´on, han ido surgiendo nuevos problemas a resolver dados los resultados obtenidos en cada momento, teniendo que incluir objetivos intermedios hasta llegar a resolver el objetivo principal del mismo. Adem´as, en el 2011 se decidi´o enviar una publicaci´on del trabajo realizado (extendida por un peque˜no estudio de aperturas no binarias) al Congreso Ibero-Americano de Inform´atica Gr´afica (SIACG 2011), cuya fecha l´ımite de aceptaci´on de publicaciones fue el 7 de febrero de 2011. Esto supuso dedicar una parte del desarrollo del proyecto a la creaci´on de la publicaci´on, as´ı como de una bater´ıa de resultados finales; por lo que el trabajo deb´ıa estar funcionando con tiempo suficiente para satisfacer la entrega a tiempo de la publicaci´on. 7.3. Trabajo futuro Una primera mejora del trabajo realizado es conseguir una ejecuci´on menos costosa del algoritmo gen´etico, paralelizando la ejecuci´on del mismo para conseguir acelerar la sucesi´on de generaciones. Por otro lado, ya que la transmitancia de luz de una apertura codificada es menor que la de una apertura circular, optimizar la funci´on de evaluaci´on consiguiendo tener en cuenta esa caracter´ıstica ser´ıa otra posible extensi´on del trabajo realizado. Otra principal mejora, ser´ıa trabajar con varias PSFs en la imagen, aplicando una PSF distinta a cada zona de la imagen, permitiendo recuperar casi la totalidad de la informaci´on perdida para cualquier fotograf´ıa con blur por desenfoque. Adem´as, encontrar otro m´etodo de obtenci´on de las PSFs de una apertura a distintas profundidades de desenfoque podr´ıa mejorar los resultados obtenidos. Finalmente, realizar un estudio m´as extenso acerca de la convergencia del algoritmo a aperturas ´optimas en relaci´on a los valores de los par´ametros podr´ıa determinar unos mejores valores de los mismos a la hora de buscar aperturas codificadas que funcionen de mejor manera que las obtenidas. 7.4. Conclusiones personales De manera subjetiva, el desarrollo de mi proyecto fin de carrera en el seno del GIGA, junto a Bel´en y Diego, ha generado una satisfacci´on enorme en varios aspectos. Para empezar, este proyecto ha sido un proyecto de investigaci´on sobre un campo muy emergente y su desarrollo no se limita a “construir una muro con los ladrillos que mis directores de proyecto me faciliten”; de esta manera he aprendido a trabajar bajo otro enfoque que el apren- 44 7. Conclusiones y trabajo futuro dido en la carrera muchas veces limitado a pensar en “como hacer que mi programa funcione”. Para continuar, el haber realizado experimentos reales sobre todo lo que, en otras ocasiones queda en el estudio te´orico de un problema (o, a lo sumo, en simulaciones), es algo que tampoco me esperaba llegar a conseguir, siendo una parte muy gratificante. Por ´ultimo, ser parte de una publicaci´on en un congreso me parece algo que no se consigue, en la mayor´ıa de las ocasiones, antes de acabar la carrera universitaria; de esta manera, que los acontecimientos me hayan permitido formar parte de una publicaci´on es muy satisfactorio. 45 A. Derivaci´on matem´atica de la funci´on de evaluaci´on Asumiendo que el ruido sigue una distribuci´on gaussiana de media 0 y una desviaci´on t´ıpica dada por σ,ζ∼N(0, σ2), la ecuaci´on A.3 queda: R(K, F0, C) =     σ·¯ K |K|2+|C|2    2 +     F0· |C|2 |K|2+|C|2     2 (A.4) Para poder eliminar de la ecuaci´on A.4 la inc´ognita F0, que es desconocida, se utiliza un modelo natural de im´agenes. La esperanza de |F0|2es calculada como: A(ξ) = ZF0 |F0(ξ)|2dµ(F0),(A.5) donde ξrepresenta frecuencia y Ase calcula promediando el espectro de potencia de un conjunto de im´agenes naturales. Sustituyendo dicha esperanza A.5 en la ecuaci´on A.4, se obtiene: R(K, C) =     σ·¯ K |K|2+|C|2    2 +     A1/2· |C|2 |K|2+|C|2     2 (A.6) El valor de |C|2que, para un Kdado, minimiza el valor de Res |C|2=σ2/A. Sustituyendo dicho valor en la ecuaci´on A.6 se elimina otra inc´ognita. Si se reorganiza la ecuaci´on A.6, se obtiene la funci´on de evaluaci´on empleada: R(K) = σ2 |K|2+σ2/A (A.7) 52 Ap´endice B. Desmontaje del objetivo En este ap´endice se va a mostrar el proceso de desmontaje del objetivo a la hora de introducir una apertura codificada en el interior del sistema de lentes. Figura B.1: Objetivo utilizado (EF 50mm f 1.8 II) sin abrir. Figura B.2: Paso 01: voltear el objetivo y extraer la tapa posterior del mismo. La tapa se extrae cuando se coloca el objetivo en la c´amara fotogr´afica. 53 B. Desmontaje del objetivo Figura B.3: Paso 02: extracci´on de dos micro-tornillos para, a posteriori, extraer una tapa interior (dejando visible la microelectr´onica del objetivo). Figura B.4: Paso 03: extracci´on de la tapa que permite cambiar el modo de enfoque del objetivo entre modo manual y modo autom´atico. Esto permitir´a extraer la carcasa exterior del objetivo. Figura B.5: Paso 04: extracci´on de la carcasa exterior del objetivo. 54 B. Desmontaje del objetivo Figura B.6: Paso 05: una vez se tiene abierto el objetivo se separa el sistema de lentes del aro de enfoque (pieza circular que permite enfocar la escena en modo de enfoque manual). Figura B.7: Paso 06: sistema de lentes, en cuyo interior se aloja el diafragma del objetivo. Figura B.8: Paso 07: colocaci´on de una apertura en el sistema de lentes. 55 B. Desmontaje del objetivo 56 Ap´endice C. Estudio de la convergencia del algoritmo gen´etico En este ap´endice aparecen los resultados del estudio explicado en la Secci´on 4.3. Se incluye la evoluci´on de R(K) y el tiempo de ejecuci´on para diferentes par´ametros. C.1. Supervivientes El par´ametro supervivientes indica el n´umero de cromosomas que son seleccionados al final de cada generaci´on para crear la siguiente generaci´on, es decir los cromosomas que act´uan como padres de la siguiente generaci´on. En los resultados obtenidos se observa que cuanto menor es el valor para dicho par´ametro (lo que implica un mayor n´umero de cromosomas nuevos en cada generaci´on) el valor de R(K) es menor, siendo el tiempo de ejecuci´on muy similar para cualquier valor del par´ametro. Figura C.1: Supervivientes (porcentaje con respecto al n´umero de individuos de la poblaci´on). Izquierda, eje horizontal: distintos valores para el par´ametro supervivientes, eje vertical: tendencia de la funci´on de evaluaci´on R(K)con la variaci´on del par´ametro supervivientes. Derecha, eje horizontal: distintos valores para el par´ametro supervivientes, eje vertical: tendencia del tiempo de ejecuci´on del algoritmo con la variaci´on del par´ametro supervivientes. 57 C. Estudio de la convergencia del algoritmo gen´etico C.2. Generaciones El par´ametro generaciones indica el n´umero de generaciones del algoritmo, es decir determina el per´ıodo de evoluci´on del fenotipo. En los resultados obtenidos se observa que cuanto mayor es el valor para dicho par´ametro (lo que implica un mayor n´umero generaciones) el valor de R(K) es menor, siendo el tiempo de ejecuci´on proporcional al incremento del valor del par´ametro. Figura C.2: Izquierda, eje horizontal: distintos valores para el par´ametro generaciones, eje vertical: tendencia de la funci´on de evaluaci´on R(K)con la variaci´on del par´ametro generaciones. Derecha, eje horizontal: distintos valores para el par´ametro generaciones, eje vertical: tendencia del tiempo de ejecuci´on del algoritmo con la variaci´on del par´ametro generaciones. C.3. Poblaci´on El par´ametro poblaci´on indica el n´umero de cromosomas que conforman cada generaci´on. En los resultados obtenidos se observa que el valor de R(K) es muy similar para cualquier valor del par´ametro, siendo el tiempo de ejecuci´on proporcional al incremento del valor del par´ametro. Figura C.3: Izquierda, eje horizontal: distintos valores para el par´ametro poblaci´on, eje vertical: tendencia de la funci´on de evaluaci´on R(K)con la variaci´on del par´ametro poblaci´on. Derecha, eje horizontal: distintos valores para el par´ametro poblaci´on, eje vertical: tendencia del tiempo de ejecuci´on del algoritmo con la variaci´on del par´ametro poblaci´on. 58 C. Estudio de la convergencia del algoritmo gen´etico C.4. Cruzamiento El par´ametro cruzamiento indica la probabilidad de que un gen sea intercambiado entre dos cromosomas en la operaci´on de cruzamiento. En los resultados obtenidos se observa que el valor de R(K) as´ı como el tiempo de ejecuci´on es muy similar para cualquier valor del par´ametro. Figura C.4: Izquierda, eje horizontal: distintos valores para el par´ametro cruzamiento, eje vertical: tendencia de la funci´on de evaluaci´on R(K)con la variaci´on del par´ametro cruzamiento. Derecha, eje horizontal: distintos valores para el par´ametro cruzamiento, eje vertical: tendencia del tiempo de ejecuci´on del algoritmo con la variaci´on del par´ametro cruzamiento. C.5. Mutaci´on El par´ametro mutaci´on indica la probabilidad de que un gen sea mutado (es decir, cambiado de valor) en un cromosoma en la operaci´on de mutaci´on. En los resultados obtenidos se observa que el valor de R(K) as´ı como el tiempo de ejecuci´on es muy similar para cualquier valor del par´ametro. Figura C.5: Izquierda, eje horizontal: distintos valores para el par´ametro mutaci´on, eje vertical: tendencia de la funci´on de evaluaci´on R(K)con la variaci´on del par´ametro mutaci´on. Derecha, eje horizontal: distintos valores para el par´ametro mutaci´on, eje vertical: tendencia del tiempo de ejecuci´on del algoritmo con la variaci´on del par´ametro mutaci´on. 59 C. Estudio de la convergencia del algoritmo gen´etico 60 Ap´endice D. Resultados de las pruebas reales Figura D.1: Resultados de la apertura ´optima para σ=0.0001. Se muestran, de arriba a abajo, resultados para tres profundidades de desenfoque distintas (40, 60 y 90 cent´ımetros respectivamente). Para cada profundidad, izquierda: imagen capturada con blur por desenfoque, derecha: imagen obtenida tras recuperar la informaci´on perdida en la captura, abajo: PSF de la apertura utilizada. 61 D. Resultados de las pruebas reales 68 Ap´endice E. Art´ıculo: Coded Apertures for Defocus Deblurring En febrero del 2011 se envi´o un art´ıculo basado en el trabajo realizado en este proyecto (extendido por un peque˜no estudio de aperturas no binarias) al Congreso Ibero-Americano de Inform´atica Gr´afica (SIACG 2011). El resultado no s´olo fue la aceptaci´on del art´ıculo enviado si no que, adem´as, fue reconocido como uno de los cinco mejores art´ıculos del congreso. En junio del mismo a˜no, en la celebraci´on del mismo, el art´ıculo se eligi´o como uno de los tres mejores del congreso, siendo propuesto para aparecer (de manera extendida) en la revista “Computer Graphics Forum, The International Journal of the Eurographics”, revista l´ıder en art´ıculos t´ecnicos sobre gr´aficos por ordenador con un factor de impacto de 1.681 y posici´on 22/93 en el ranking JRC. La versi´on final del art´ıculo, enviada al congreso, se muestra en este anexo. 69 Coded Apertures for Defocus Deblurring Belen Masia, Adrian Corrales, Lara Presa and Diego Gutierrez Universidad de Zaragoza Abstract The field of computational photography, and in particular the design and implementation of coded apertures, has yielded impressive results in the last years. Among their applications lies defocus deblurring, in which we focus in this paper. Following the approach of previous works, we obtain near-optimal coded apertures using a genetic algorithm and an existing quality metric. We perform both synthetic and real experiments, testing the performance of the apertures along the dimensions of depth, size and shape. We additionally explore non-binary apertures, usually overlooked in the literature, and perform a comparative analysis with their binary counterparts. Categories and Subject Descriptors (according to ACM CCS): I.4.3 [Image Processing and Computer Vision]: Enhancement—Sharpening and deblurring 1. Introduction In the past few years, the field of computational photography has yielded spectacular advances in the imaging process. The main idea is to code the light information in novel ways before it reaches the sensor, in order to decode it later and obtain an improved, enhanced or extended representation of the scene being captured. Several different strategies exist, from structured lighting, to new optical devices, to modulated apertures or shutters. In this work we focus on coded apertures. These are masks obtained by means of computational algorithms which, placed at the camera lens, encode the defocus blur in order to better preserve high frequencies in the original image. They can be seen as an array of multiple ideal pinhole apertures (with infinite depth and no chromatic aberration), whose location on the 2D mask is determined computationally. Decoding the overlap of all pinhole images yields the final image. Some existing works interpret the resulting coded blur attempting to recover depth from defocus. Given the nature of the blur as explained by simple geometrical optics, this approach imposes a multi-layered representation of the scene being depicted. While there is plenty of interesting on-going research in that direction, in this paper we limit ourselves to the problem of defocus deblurring: we aim to obtain good coded apertures that allow us to recover a sharp image from its blurred original version. We follow standard approaches and pose the imaging process as a convolution between the original scene being captured and the blur kernel (plus a noise function). In principle, this would lead to a blind deconvolution problem, given that the such blur kernel is usually not known. Assuming no motion blur nor camera shake, this kernel is reduced to the point spread function of the optical system. Traditional circular apertures, however, have a very poor response in the frequency domain: not only do they lose energy at high frequencies, but they exhibit multiple zero-crossings as well; it is thus impossible to recover information at such frequencies during deconvolution. In this paper, we present several coded apertures with better frequency response, which allow us to recover information apparently lost to blur during the capture process. We follow the approach of previous works, and rely on the average power spectra of natural images to guide our optimization process, which is in turn performed by means of genetic algorithms. Once the coded apertures have been obtained, we show the feasibility of our results by printing them out on a photomask sheet and inserting them in an off-the-shelf camera. The captured blurred images are then deconvolved using Wiener deconvolution. We analyze the performance of our apertures as a function of shape, depth and size. We additionally modify our genetic algorithm to allow for nonbinary masks, and perform a comparative analysis with their binary counterparts. 2. Previous Work Coded apertures have been traditionally used in astronomy, coding the direction of incoming rays as an alternative to fo- cusing imaging techniques [ItZ92]. Possibly the most popular patterns were the MURA patterns (Modified Uniformly Redundant Array) [GF89]. Veeraraghavan et al. [VRA∗07] showed how a 4D light field can be reconstructed from 2D sensor information by means of a coded mask. Placed at the lens, the authors achieve refocusing of images at full resolution, provided the scene being captured contains only Lambertian objects. Nayar and Mitsunaga [NM00], extended the dynamic range capabilities of the imaging system by placing a mask of spatially varying transmittance next to the sensor, and then mapping the captured information to high dynamic range. Other works have proposed different coded apertures for defocus deblurring or depth approximation. To restore a blurred image, the apertures are designed to have a broadband frequency response, along with none (or distinguishable) zero-crossings in the Fourier domain. Hiura and Matsuyama [HM98] proposed a four-pinhole coded aperture to approximate the depth of the scene, along with a deblurred version of it, although their system required multiple images. Liang et al. [LLW∗08] use a similar approach, combining tens of images captured with Hadamard-based coded patterns. Levin et al. [LFDF07] attempted to achieve all-focus and depth recovery simultaneously, relying on image statistics to design an optimal aperture. Depth recovery is limited to a multi-layered representation of the scene. Last, the idea of spatial coding of the mask was transferred to the temporal domain by applying a coded exposure aimed at motion deblurring [RAT06]. In [ZLN09], the authors obtained paired apertures to recover both depth and focus from two images, using both genetic algorithms and gradient descent search. Last, a framework for evaluating coded apertures was recently presented [ZN09], based on the quality of the resulting deblurring and taking into account natural image statistics. Near-optimal apertures are obtained by means of a genetic algorithm. In this paper we follow the same approach, and analyze the obtained apertures along the size, depth and shape dimensions. Additionally, we extend our study by analyzing non-binary masks. 3. Optimal Aperture Design Image blur due to defocus is caused by the loss of high frequency content when capturing the image. The capture process can be modeled as a convolution between the scene being captured and the point spread function (PSF) of the camera, which is defined as the response of the optical system of the camera to an impulse input in the spatial domain. Thus: f=kd∗f0+η(1) where f0is the real scene being photographed, fis the captured image, kdis the PSF and ηaccounts for the noise introduced in the imaging process. Subscript daccounts for depth, since the PSF varies with depth or, more specifically, with the degree of defocus (strictly speaking, it also varies spatially with the position within the image). We will assume that the noise follows a Gaussian distribution of zero mean and standard deviation denoted by σ,N(0,σ2). By means of deconvolution, an approximation ˆ f0to the original sharp image can be obtained. Note that in the frequency domain the convolution becomes a multiplication, and Equation 1can be written as: F=Kd·F0+ζ(2) As Figure 1shows, the PSF, and thus the response of the camera, is characterized by the pattern of the aperture. The response to a coded aperture can also be seen in Figure 2, which depicts the calibration array used in our physical experiments. Since, as mentioned, blur is caused by the loss of information at certain frequencies, the response of an aperture is better analyzed in the frequency domain. Figure 3 depicts a 1D slice of the power spectrum of different aperture patterns, computed by Fourier transforming the aperture (note that the y-axis is log-scale). This shows the magnitude of the response for different frequencies. Circular apertures exhibit zero crossings at several frequencies, and thus information at those frequencies is lost during the imaging process. Optimal apertures for deblurring therefore seek a smooth power spectrum, while keeping the transmitted energy as high as possible. Figure 1: Left: Images of the response to a point light of different apertures (from top to bottom: focused aperture, defocused circular aperture -defocus depth = 90 cm- and one of our coded apertures -defocus depth = 90 cm-, shown in the right). A LED and black cardboard were used to create the point light. Right: Canon EF 50mm f/1.8 lens with one of our coded apertures. 3.1. Aperture Quality Metric Devising an aperture pattern whose frequency response is optimal can be done in different manners. In this paper we follow the approach of Zhou and Nayar [ZN09], which states the quality of an aperture pattern based on the quality of the deconvolution and on a prior model of natural images. In the following we briefly describe the metric and its foundation, and we refer the reader to the original paper for additional details. Figure 2: Our poor man’s LED array used to calibrate the PSFs of the apertures. Top: Focused image. Bottom: Image taken with one of our coded apertures at a defocus depth of 70 cm. Figure 3: Power spectra comparison of different apertures with respect to a circular aperture (blue). Left: Our apertures for resolution 11×11 and noise levels σ=0.001 (red) and σ=0.005 (green). Right: Our apertures for resolution 7×7, binary (red) and non-binary (green). The quality metric chosen is the expectation of the L2 distance between the deconvolved image ˆ F0and the ground truth image F0with respect to ζ, which we want to be minimal (note that we have removed the subscript dfor the sake of simplicity): R(K,F0,C) = E ζ[ ˆ F0−F0  2](3) The recovered image ˆ F0can be obtained using Wiener deconvolution as follows: ˆ F0=F·¯ K |K|2+|C|2(4) where ¯ Kis the complex conjugate of K, and |K|2=K·¯ K. |C|2=C·¯ Cis the matrix of noise-to-signal power ratios (NSR) of the additive noise. Substituting this formulation in Equation 3we have: R(K,F0,C) = E ζ[      ζ·¯ K−F0·|C|2 |K|2+|C|2      2 ](5) and assuming that ζfollows a Gaussian distribution with zero mean, ζ∼N(0,σ2): R(K,F0,C) =      σ·¯ K |K|2+|C|2      2 +      F0·|C|2 |K|2+|C|2      2 (6) Using a model of natural images as a prior, the expectation of |F0|2is A(ξ) = ZF0 |F0(ξ)|2dµ(F0),(7) where ξrepresents frequency and Acan be approximated by averaging the power spectra of a number of natural images. This way the dependance on F0, which is unknown, is circumpassed, obtaining: R(K,C) =      σ·¯ K |K|2+|C|2      2 +      A1/2·|C|2 |K|2+|C|2      2 (8) The value of |C|2which, for a given K, minimizes the value of Ris |C|2=σ2/A. Substituting this value in Equation 8 yields the sought quality metric, which depends only on the Fourier transform of the aperture pattern K, the estimated image noise σand the average power spectra of natural images A: R(K) = σ2 |K|2+σ2/A(9) 3.2. Aperture Pattern Optimization Once we have a way of evaluating a certain aperture with Equation 9, an optimization method can be used to obtain the minimum value of R(K)over the range of possible apertures. The space of possible apertures is infinite, since the aperture can be of different resolutions, and each pixel can in principle take infinite values. A priori the solution is limited only by physical restrictions, i.e. apertures with negative values are not realizable in practice and resolution is limited by the printing process. Resolution is additionally limited by diffraction effects, which appear as the size of the pixels in the aperture gets smaller, and hinder the performance of the aperture. Transmissivity is an additional issue to be taken into account when designing an aperture. Coded apertures typically have lower transmission rates than their circular counterparts, and the use of a longer exposure time to obtain an equivalent brightness to that of the circular aperture can cause other problems such as motion blur. This metric does not consider transmissivity when evaluating an aperture, but still it yields satisfactory results for the majority of cases. 4. Experimental Setup and Results In order to search for the best aperture pattern we have implemented a genetic algorithm which uses the quality metric described in Section 3as evaluation function, resembling Zhou and Nayar’s work. The algorithm has the following scheme: •Initialization. The initial population of Npossible apertures is randomly generated. An aperture is defined by a vector of Lelements, each element corresponding to a pixel. •Selection. The quality metric of Equation 9is used to evaluate the Npossible apertures. They are then sorted according to this value and the best Mapertures are selected. •Reproduction. The selected Mapertures, by means of crossover and mutation, populate the next generation. Crossover implies randomly selecting two apertures, duplicating them, and exchanging corresponding bits between them with probability c1, obtaining two new apertures. Mutation ensures diversity by modifying each bit of the aperture with probability c2. •Termination. The two previous steps of reproduction and selection are repeated sequentially until the termination condition is met. We use a maximum number of generations Gas stopping condition. We have tested apertures of two different resolutions, 11 ×11 and 7 ×7 pixels (that is, L=121 and L=49, respectively), while the rest of the parameters we used for the algorithm are N=4000, M=400, G=80, c1=0.2 and c2=0.05. Since the optimal aperture depends on the noise of the image we have run the algorithm for different noise levels and tested the resulting apertures. Apertures designed for σvalues of 0.001 and 0.005 proved to work best for a wide variety of images. Regarding the possible values the pixels in the aperture can take, we have experimented both with binary and non-binary apertures, but at this first stage we show results just for binary apertures. Results for nonbinary apertures are discussed in Section 5. From all the obtained apertures we have chosen three, and a conventional circular aperture, to perform our experiments. We chose the ones which we saw performed best over a wide variety of images. Two of them are 11 ×11 apertures designed for noise levels of σ=0.001 and σ=0.005, and the third one is a 7 ×7 aperture designed for σ=0.005. The three of them are depicted in Figure 4. For these apertures, we have performed both a synthetic validation and a validation with physical printed-out apertures. The synthetic validation is done by simulating the capture process convolving a sharp image f0with the aperture (plus noise) as in Equation 1, and subsequently using Wiener deconvolution to recover a deblurred image ˆ f0. The quality of the recovered image is measured using the L2norm. We did this for 10 images and computed the average L2value. Results are shown in Table 1for the tested apertures. The minimum error is obtained by the 7 ×7 aperture and the two 11 ×11 apertures perform very similarly, there is no significant difference, while, as expected, the circular aperture yields worse results. Another measure of the quality of σ=0.001 σ=0.005 σ=0.005(7x7) Circular Figure 4: Apertures used in our experiments. 0.001 0.005 0.005 (7x7) circular L2 norm 1.28 1.27 0.88 1.62 Table 1: Results of the L2norm for different apertures. The table shows percentages with respect to the maximum error. the apertures is given by their power spectrum, depicted in Figure 3. The 11 ×11 apertures eliminate less frequencies than the circular aperture, and the 7×7 aperture has an even smoother spectrum, which correlates with the L2values previously obtained. Experiments in real scenarios have been performed using a Canon EOS 550D with a Canon EF 50mm f/1.8 II lens shown (unmounted) in Figure 5. Our apertures were printed in a high resolution photomask sheet (see Figure 6left) and inserted into the lens. The first step is the calibration of the Figure 5: Camera and lens used in our experiments. response of the camera (PSF) at different depths. We also calibrated the PSF for different image positions, since the response is spatially varying across the image plane. To do this we used an array of LEDs which we made as close as possible to point light sources with the aid of black cardboard. Figure 2shows a close-up of the LED array. We locked the focus at 1 m and took an initial focused image, followed by images of the LEDs every 10 cm and until a distance of 2 m, thus having PSFs for defocus depths from 10 to 100 cm. For each position within the image and each depth, the actual cropped image of the LED served us as PSF, after appropriate thresholding of surrounding values which contain residual light. The resulting PSFs for three depths and the four tested apertures are shown in Figure 6(right). Figure 6: Left: Photomask sheet showing some of the apertures used. Right: PSFs at three different defocus depths (40, 70 and 90 cm) for the four apertures depicted in Figure 4. Figure 7: Focused ground truth scenes. Once calibration had been performed, images of three scenes at different depths were taken with each of the selected apertures. These images are then deblurred using the corresponding calibrated PSF by means of Wiener deconvolution. We used a NSR of 0.001 when deconvolving, since it gave the best results. The same exposure time and aperture was used for all the apertures, which results in some images being darker than others. Figure 7shows the ground truth focused images of the three scenes, whereas Figure 8depicts the defocused image captured with each aperture and the recovered image for the three different depths. Insets show the corresponding PSF. For all cases our apertures clearly outperform the circular one. The results of the other three apertures are fairly similar, with the 7 ×7 aperture revealing more detail than the others in some regions. However, we believe this may be due to the fact that because of its smaller size, it offers a wider depth of field, thus causing less defocus blur for the same settings as the others. The ringing artifacts which can be observed are probably partially caused by inaccuracies of the calibrated PSFs. Additionally, and although very minor, some of the apertures exhibit slight diffraction effects which can also be the cause of artifacts due to misalignments of the color channels [VRA∗07]. 5. Study of Non-Binary Apertures Binary codes have the initial advantage of reducing the search space, and are usually preferred in the existing literature. However, there is no principled motivation to restrict the aperture pixel values to either black or white, other than apparent simplicity. A notable exception in this regard is the work by Veeraraghavan and colleagues [VRA∗07], where the authors report the advantages of continuous-valued apertures, found by gradient descent optimization, over their binary counterparts. In this section we perform an analysis of non-binary apertures focused on our specific context and optimization method; in order to limit the search space of the genetic algorithm, we restrict the set of possible values to {0,0.5,1}. We have studied the quality of the resulting aperture and the computation time for different executions of the genetic algorithm for the cases of binary and non-binary apertures. We have varied both the initial population Nand the number of generations G, yielding seven different combinations of these two parameters. For each combination of parameters we have performed three executions of the algorithm, plotting the average values. For all the figures in this section, the x-axis shows the initial population Nand the number of generations Gof each set of executions. The number of selected apertures, M, is always a 10% of the initial population, the crossover probability c1is set to 0.2 and the probability of mutation c2is 0.05. All the calculated apertures have a resolution of 7 ×7. The reason of this is two-fold; first, computational cost of the algorithm is significantly reduced, and second, our previous experiments have shown that 7×7 apertures yield results on par with (or better than) 11 ×11 apertures. The value of σ(noise level) is set to 0.005 for all executions. Figure 9shows the average value of the quality metric to which the algorithm converged. Non-binary apertures tend to converge to slightly lower values of R(K), potentially indicating a better performance. However, as expected, it also takes longer for non-binary apertures to converge to a stable value of R(K). The execution times consumed until conver- σ=0.001 σ=0.005 Circular σ=0.005 (7×7) σ=0.001 σ=0.005 Circular σ=0.005 (7×7) σ=0.001 σ=0.005 Circular σ=0.005 (7×7) Figure 8: From top to bottom, each of the three scenes have been captured at a defocus depth of 40, 70 and 90 cm, respectively. For each pair of images, the left image shows the captured defocused image and the right image the recovered one. Insets depict the PSF of the aperture used in each case. gence when running the algorithm on an Intel Core i7 930 @ 2.80GHz are shown in Figure 10. For all the optimal apertures obtained in the different executions we have performed a synthetic evaluation similar to the one described in Section 4. We applied Equation 1to an image f0of the ISO 12233 resolution chart, to simulate Figure 9: Average value of the quality metric R(K)for binary and non-binary apertures and for different initial parameters of the genetic algorithm. Figure 10: Average value of the time until convergence (in seconds) for binary and non-binary apertures and for different initial parameters of the genetic algorithm. the capture process with the different apertures; we then performed Wiener deconvolution to recover the estimated sharp image ˆ f0. We have computed the L2norm between ˆ f0and f0and plotted the results in Figure 11. The non-binary apertures tend to behave better, the global tendency thus correlating with that of the quality metric R(K). Nevertheless, this graphs shows how lower values of R(K)not necessarily yield lower values of the L2norm. This can be explained by the fact that R(K)is devised to give optimal performance over the entire space of natural images and thus may not be optimal for an image in particular [ZN09]. Figure 12 shows the image of the chart after convolution, and the recovered image for the best binary and non-binary apertures we obtained. For these two apertures we also plotted the power spectrum, shown in Figure 3(right). Although both spectra are similar, overall the non-binary aperture has a more favorable response. To further test the performance of binary vs. non-binary apertures, we printed out these two best apertures (shown in the insets of Figure 12) and captured real images with them. We have calibrated their PSF at different depths as explained in Section 4, and captured a set of images which we then have recovered using Wiener deconvolution. Figure Figure 11: Average value of the L2norm for binary and non-binary apertures and for different initial parameters of the genetic algorithm. Values show percentage with respect to the maximum error. 13 shows the results for a defocus depth of 70 cm and 90 cm. The corresponding ground truth focused scenes are shown in Figure 7. We can see how even though both recover detail to a great extent, the non-binary aperture performs better. Figure 12: Top left: Defocused image of the ISO 12233 chart obtained using Equation 1with the aperture shown in the inset in the right as convolution kernel. The aperture is the optimal binary aperture we obtained. Top right: Image recovered using Wiener deconvolution. Bottom row: Same for the optimal non-binary aperture, shown in the inset. 6. Conclusions and Future Work In this paper we have introduced a comprehensive study of coded apertures for defocus deblurring, and implemented the full pipeline: from the genetic algorithms to obtain the codes, to their physical realization, and finally to the actual deblurring of out-of-focus images. We have analyzed the perfor- Binary Non-binary Figure 13: For each pair of images, the left image shows the captured defocused image and the right image the deblurred image. Insets depict the PSF used in each case. Defocus depths are 70 cm (top scene) and 90 cm (bottom scene). The color of the images differs from those in Figure 8; please note that this is due to the fact that illumination conditions during the capture process were different, and not to the coded apertures itselves. mance of the different patterns along several dimensions, namely shape, depth and size. For instance, we found that 7×7 apertures are on par with, or outperform, higher resolution ones, which tend to be more computationally expensive to obtain. Additionally, we have extended previous works in the literature by lifting the binary restriction in our patterns, and allowing the genetic algorithms to add mid-gray to the binary (black or white) set of possible values. Although our results are not conclusive and more research needs to be carried out, initial findings suggest that there may be value in exploring continuous apertures, where several gray levels are allowed. The inherent reduced light transmission when placing a modulating mask at the lens is also a factor that we would like to investigate further. By adding a term that maximizes transmission, we may come up with more efficient apertures. Similarly, finding coded apertures that optimize both defocus deblurring and depth is still an open problem where the community has barely scratched the surface. Last, we believe that the results shown in this paper show the viability and potential of this line of research, and we hope to raise awareness of this exciting field, fostering the creation of more research groups and potential collaborations. 7. Acknowledgements We would like to thank the reviewers for their valuable comments. We also thank C. Zhou for his insights. This research has been partially funded by a Marie Curie grant from the 7th Framework Prog. (251415), the Spanish Ministry of Science and Technology (TIN2010-21543) and the Gobierno de Aragón (OTRI 2009/0411 and CTPP05/09). Belen Masia is supported by a FPU grant from the Spanish Ministry of Education. References [GF89] GOTTESMAN S., FENIMORE E.: New family of binary arrays new family of binary arrays for coded aperture imaging. Applied Optics, 20 (1989), 4344–4352. 2 [HM98] HIURA S., MATSUYAMA T.: Depth measurement by the multi-focus camera. In IEEE Conference on Computer Vision and Pattern Recognition (1998). 2 [ItZ92] IN’TZAND J.: Coded Aperture Imaging in High-Energy Astronomy. PhD thesis, University of Utrecht, 1992. 2 [LFDF07] LEVIN A., FERGUS R., DURAND F., FREEMAN W.: Image and depth from a conventional camera with a coded aperture. ACM Transactions on Graphics 26, 3 (2007). 2 [LLW∗08] LIANG C., LIN T., WONG B., LIU C., , CHEN H.: Programmable aperture photography: multiplexed light field acquisition. ACM Transactions on Graphics 27, 3 (2008). 2 [NM00] NAYAR S., MITSUNAGA T.: High dynamic range high dynamic range imaging: spatially varying pixel exposures. In Computer Vision and Pattern Recognition (2000), vol. 1, pp. 472–479. 2 [RAT06] RASKAR R., AGRAWAL A., TUBMLIN J.: Coded exposure photography: Motion deblurring using uttered shutter. ACM Transactions on Graphics 25, 3 (2006), 795–804. 2 [VRA∗07] VEERARAGHAVAN A., RASKAR R., AGRAWAL A., MOHAN A., TUMBLIN J.: Dappled photography: mask enhanced cameras for heterodyned light fields and coded aperture refocusing. ACM Trans. Graph. 26 (July 2007). 2,5 [ZLN09] ZHOU C., LIN S., NAYAR S.: Coded aperture pairs for depth from defocus. In ICCV (oral) (2009). 2 [ZN09] ZHOU C., NAYAR S. K.: What are Good Apertures for Defocus Deblurring? In IEEE International Conference on Computational Photography (2009). 2,7