Repositorio Institucional de Documentos

D ESCOMPOSICIÓN DE IMÁ GENES EN SUS COMPONENTES INTRÍNSECAS Ponente: Dr. D. Diego Gutiérrez Director: D. Jorge López-Moreno Ingeniería Informática. Diciembre 2010 Autora: Elena Garcés García Proyecto Fin de Carrera Universidad de Zaragoza Centro Politécnico Superior Departamento de Informática e Ingeniería de Sistemas Grupo de Informática Gráfica Avanzada Si quieres conocer el pasado, mira el presente que es su resultado. Si quieres conocer el futuro, mira el presente que es su causa. BUDA ii Agradecimientos Quiero dar las gracias desde aqu´ı a mis padres, Aurora y C´andido, por su apoyo a lo largo de estos a˜nos de carrera y por aguantarme en los momentos m´as dif´ıciles. A mi hermana, M´onica, por no haber dejado de creer en m´ı. A Carlos, por estar siempre e incondicionalmente, por ayudarme, apoyarme y hacerme ver la luz cuando todo parec´ıa oscuridad. Tambi´en quiero agradecer a Jorge y a Diego la oportunidad que me dieron de trabajar en un proyecto tan interesante como ha sido este, por su ayuda, dedicaci´on y paciencia durante todos estos meses. Gracias a toda la gente del grupo por su apoyo y disposici´on y en especial a Adolfo por sus valiosas aportaciones en la linealizaci´on del problema. iii iv Resumen En m´ultiples tareas de fotograf´ıa computacional, tales como extracci´on de 3D o edici´on de materiales e iluminaci´on para una sola imagen, es necesario el conocimiento previo de las luces y los materiales de la escena. En ocasiones podemos disponer de esta informaci´on, bien porque nos encontramos en entornos controlados, o bien porque disponemos de la tecnolog´ıa que captura dichos datos al tomar la imagen. Sin embargo, en la mayor´ıa de los casos no disponemos de tal informaci´on y el ´unico modo que tenemos de obtener luces o materiales es a trav´es de una sencilla fotograf´ıa. Este proyecto tiene como objetivo resolver este problema que com´unmente se conoce como descomposici´on de una imagen en sus componentes intr´ınsecas, y que consiste en obtener, para una ´unica imagen, la parte correspondiente a iluminaci´on (sombreado) y la que corresponde con reflectancia (textura, color). A lo largo de los a˜nos se han desarrollado numerosos m´etodos para su resoluci´on, sin embargo, el elevado n´umero de inc´ognitas y la ausencia de informaci´on previa de la escena hacen imposible obtener una soluci´on un´ıvoca y ´optima. Por ello, para acotar el problema y que sea posible su resoluci´on hemos partido de ciertas asunciones iniciales: suponemos conocido el contorno de los objetos de la imagen y ´estos son considerados globalmente convexos. Nuestro algoritmo, realizado bajo un proyecto en colaboraci´on con Adobe Systems Inc., se basa en encontrar las relaciones de luminosidad entre las distintas regiones de la imagen, para posteriormente normalizarlas, y que de este modo se eliminen las variaciones de luminosidad que sean causadas por la textura de los materiales manteniendo la informaci´on de la geometr´ıa de la escena. Comparado con otros m´etodos, nuestro trabajo proporciona una soluci´on precisa y no requiere conocimientos avanzados sobre par´ametros del algoritmo ni interacci´on por parte del usuario, ya que se ejecuta de manera autom´atica. Por este motivo, sirve f´acilmente de base para cualquier t´ecnica que requiera de esta descomposici´on. v vi ´ Indice general Agradecimientos III Resumen V 1. Introducci´on 1 1.1. Motivaci´on .................................... 1 1.2. Objetivos ..................................... 3 1.3. Contexto ..................................... 3 1.4. Estructura de la memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Estudio de t´ecnicas de descomposici´on 5 2.1. Formaci´on de la imagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2. EstadodelArte.................................. 6 3. Descomposici´on en reflectancia e iluminaci´on 9 3.1. Fase1:Segmentaci´on............................... 10 3.1.1. Segmentaci´on basada en grafo . . . . . . . . . . . . . . . . . . . . . . 10 3.1.2. La influencia del modelo de color: RGB vs Lab . . . . . . . . . . . . 11 3.1.3. Filtrado y mejora de la segmentaci´on . . . . . . . . . . . . . . . . . . 12 3.1.4. Resultados segmentaci´on . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2. Fase 2: Normalizaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2.1. Linealizaci´on del problema . . . . . . . . . . . . . . . . . . . . . . . 15 3.2.2. Resoluci´on del sistema . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4. Resultados 21 5. Conclusiones 27 5.1. TrabajoRealizado ................................ 27 5.2. Resumen temporal del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.3. TrabajoFuturo.................................. 29 5.4. Conclusiones personales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Bibliograf´ıa 31 vii 2.2. Estado del Arte (a) Imagen original (b) Iluminaci´on (c) Reflectancia Figura 2.1: Descomposici´on. La imagen (a) est´a formada por sus componentes intr´ınsecas (b) y (c) 2.2. Estado del Arte Weiss [Wei01] propone un m´etodo para encontrar las im´agenes intr´ınsecas tomando como entrada una larga secuencia de im´agenes de la misma escena en las que la reflectancia permanece constante mientras que la iluminaci´on se modifica. Esta aproximaci´on fue extendida por Liu et al. [LWQ+08] a cualquier secuencia no controlada de im´agenes de la escena para dar color a fotograf´ıas en blanco y negro. Sin embargo, estas t´ecnicas requieren demasiadas im´agenes de entrada para resultar pr´acticas. Debido a la falta de variables que acoten el problema, obtener las descomposici´on a partir de una ´unica imagen no puede ser resuelto sin alg´un conocimiento a priori de la escena. Por ello, bas´andose en la teor´ıa Retinex [EHLM71], Horn [Hor86] en su trabajo, asume que mientras que la reflectancia se mantiene constante por segmentos, la iluminaci´on var´ıa suavemente. Esta heur´ıstica permite obtener la reflectancia de una imagen umbralizando los gradientes peque˜nos de la imagen ya que se consideran parte de la iluminaci´on. Tappen et al. [TFA05] cuentan con unos clasificadores entrenados en las derivadas de la imagen para distinguir la reflectancia de los gradientes de iluminaci´on. A pesar de estas heur´ısticas y clasificadores muchas configuraciones de reflectancia e iluminaci´on contin´uan siendo dif´ıciles de desambiguar (ver Figura 2.2). Shen et al. [STL08] proponen enriquecer estas aproximaciones con restricciones globales en la textura y partiendo de un algoritmo de Retinex, imponen que pixels que comparten textura tengan la misma reflectancia. Los ´ultimos avances publicados por Adobe Systems Inc. en el tema de obtenci´on de im´agenes intr´ınsecas est´an recogidos en el art´ıculo de Bousseau et al. [BPD09]. Los cuales, obtienen muy buenos resultados asumiendo que la reflectancia presenta variaciones de bajo rango a nivel local. Sin embargo, requieren excesiva ayuda de un usuario que est´e familiarizado con la t´ecnica, ya que el uso de sus pinceles no es intuitivo (ver Figura 2.3). Existe un extenso trabajo sobre la eliminaci´on de sombras, tanto de manera autom´atica [GDFL04, FHLD06] como basado en interacci´on con el usuario [MTC07, WTBS07]. La idea com´un de estos m´etodos consiste en identificar los pixels de sombra a trav´es de la detecci´on de bordes o de la segmentaci´on de la imagen. Una vez que las sombras son 6 2. Estudio de t´ecnicas de descomposici´on (a) Imagen original (b) Iluminaci´on (c) Reflectancia Figura 2.2: Error en la descomposici´on [TFA05]. La variaci´on blanco sobre negro del ojo de la figura se puede interpretar err´oneamente como sombreado, siendo en realidad parte de la textura. (b) (c) (d) (a) (e) Figura 2.3: Interacci´on del usuario de Bousseau et al. [BPD09]. En (a) vemos los trazos necesarios para obtener la descomposici´on de la imagen (b), en reflectancia (c) e iluminaci´on (d). En la tabla (e) se muestra el n´umero total de trazos que han necesitado algunas im´agenes para descomponerse seg´un su algoritmo. detectadas pueden ser eliminadas aplicando correcci´on de color o filtros de gradiente. Sin embargo, estos m´etodos se centran en capturar sombras proyectadas las cuales se caracterizan por tener fronteras bien diferenciadas, mientras que nosotros tenemos como objetivo eliminar sombreados suaves donde los l´ımites entre luz y oscuridad no pueden ser delimitados. Hay que destacar que aunque la aproximaci´on de Finalyson et al. [GDFL04] tiene como objetivo estimar una imagen sin iluminaci´on, esta imagen es en escala de grises y no representa la verdadera reflectancia. La obtenci´on de im´agenes intr´ınsecas est´a estrechamente relacionado con otros tipos de descomposici´on. Las descomposiciones autom´aticas en m´ultiples escalas que capturan 7 2.2. Estado del Arte diferentes niveles de detalle [SSD09, FAR07, FFLS08] pueden producir im´agenes muy similares a las que se pretende obtener en las im´agenes intr´ınsecas. Algunos de estos algoritmos como el Filtro Bilateral [CPD07] suelen ser utilizados como base para obtener la iluminaci´on en algoritmos de Shape from Shading (obtenci´on de 3D). El algoritmo de descomposici´on muli escala de Subr et al. [SSD09], captura en los niveles de menor detalle, caracter´ısticas globales de la iluminaci´on que podr´ıan servir de ayuda en la descomposici´on. 8 Cap´ıtulo 3 Descomposici´on en reflectancia e iluminaci´on Nuestro algoritmo de descomposici´on es un proceso autom´atico (no requiere intervenci´on del usuario) que toma como entrada la imagen original y una m´ascara en blanco y negro que define el objeto que queremos descomponer. Consta de dos fases principales f´acilmente modularizables. Una visi´on general de nuestro sistema se puede ver en la Figura 3.1: FASE 1. Segmentación FASE 2. Normalización Salida: IMÁGENES INTRÍNSECAS: ILUMINACIÓN + REFLECTANCIA Entrada: IMAGEN + MÁSCARA 1. Segmentación 2. Filtrado 1. Construcción Sistema Ec. lineales 2. QMR Segmentos 3. Normalización final Luminosidad Perceptual Figura 3.1: Visi´on general del sistema implementado. 9 3.1. Fase 1: Segmentaci´on En la primera fase dividimos la imagen en peque˜nos fragmentos de color o albedo constante. Para ello, utilizamos un m´etodo de segmentaci´on basado en grafo [FH04b] modificado para trabajar sobre espacio de color Lab (m´as detalles sobre la segmentaci´on en la secci´on 3.1). Estos segmentos (o clusters de pixels) servir´an como entrada a la segunda fase del algoritmo junto con la imagen que representa la luminosidad perceptual de la imagen de entrada. En la segunda fase (secci´on 3.2) construimos un sistema de ecuaciones estableciendo relaciones locales de luminosidad entre pares de clusters vecinos de la imagen. Como resultado, obtenemos unos ratios de luminancia para cada cluster que nos permiten llegar a la imagen final de la iluminaci´on. A partir de la imagen normalizada de la iluminaci´on, calculamos la imagen correspondiente de la reflectancia. Este par de im´agenes constituyen las im´agenes intr´ınsecas buscadas. 3.1. Fase 1: Segmentaci´on Segmentar una imagen consiste en dividirla en las diferentes partes que la integran. Esto puede parecer sencillo, sin embargo, en la pr´actica, decidir qu´e es una buena segmentaci´on es algo muy subjetivo y depende mucho de la finalidad de la aplicaci´on. Por este motivo, elegir un buen algoritmo de segmentaci´on que se ajustara a nuestras necesidades no fue f´acil. Evaluamos varias de las t´ecnicas de segmentaci´on existentes partiendo de unos requisitos iniciales: la segmentaci´on no deb´ıa ser supervisada (no conocemos a priori el n´umero de clusters ni sus caracter´ısticas), se deb´ıa usar informaci´on de color y/o de textura y el algoritmo deb´ıa ser eficiente. Teniendo esto en mente, estudiamos algoritmos basados en Campos Aleatorios de Markov (MRFs), m´etodos de agrupamiento y m´etodos basados en grafos. El estudio completo de los distintos m´etodos de segmentaci´on se encuentra en el Anexo A. Despu´es de analizar los distintos m´etodos decidimos escoger el algoritmo de segmentaci´on basado en grafo de Pedro F. Felzenszwalb [FH04b] con algunas modificaciones que se detallan a continuaci´on. 3.1.1. Segmentaci´on basada en grafo El algoritmo parte de un grafo no dirigido G= (V, E) formado por un conjunto de v´ertices vi∈V, que se corresponden con los pixels a segmentar de la imagen, y un conjunto de aristas (vi, vj)∈Eque constituyen pares de v´ertices vecinos. Cada arista tiene tiene un peso w((vi, vj)), que representa la similitud entre los dos pixels conectados por esa arista. En el art´ıculo original se proponen dos estructuras de grafo distintas, una basada en una malla (grafo GRID), donde cada pixel est´a conectado con sus 8-vecinos m´as pr´oximos por posici´on y otra basada en el m´etodo de vecino m´as pr´oximo (grafo KNN ) donde se 10 3. Descomposici´on en reflectancia e iluminaci´on realiza un mapeo de cada pixel en un espacio nuevo de caracter´ısticas y se puede definir libremente el n´umero de vecinos a usar. En el caso de usar un grafo GRID, la funci´on que define la similitud entre los dos pixels conectados por una arista, viene dada por su diferencia de color. Como propone el autor, usamos la distancia Eucl´ıdea L2, w((vi, vj)) = kC(vi)−C(vj)k=v u u t N X t=1 |C(vi)t−C(vj)t|(3.1) donde C(v) es el vector de color del v´ertice v, siendo C(v) = {r, g, b}en espacio de color RGB yC(v) = {a, b}en espacio de color Lab (m´as detalles sobre el modelo de color usado en la secci´on 3.1.2). En el otro caso, usando grafo KNN se realiza un mapeo de cada v´ertice en el espacio {x, y, C(x, y)}, donde (x, y) es la localizaci´on del v´ertice en la imagen y C(x, y) representa el color del punto que depender´a del modelo usado. Del mismo modo que con el grafo GRID usamos la distancia Eucl´ıdea L2para definir los pesos de las aristas, pero ahora, tambi´en tiene influencia la posici´on del pixel en la imagen. La ventaja de usar KNN frente a Grid, es que en el primero, el poder seleccionar un n´umero variable de vecinos y capturar en la funci´on de similitud la posici´on junto con el color, permite que las conexiones de los p´ıxeles sean m´as flexibles al poderse conectar regiones f´ısicamente separadas. En cambio, usando grafo Grid tenemos una estructura r´ıgida en la que solo podemos realizar conexiones locales. Para realizar la segmentaci´on de la imagen, el algoritmo trata de localizar los l´ımites entre regiones comparando dos cantidades: una basada en las diferencias de intensidades entre regiones lim´ıtrofes y la otra basada en las diferencias de intensidades dentro de cada regi´on. Intuitivamente, la diferencia de intensidad entre dos regiones es perceptualmente importante si es m´as grande que la diferencia dentro de al menos una de las dos regiones. En el proceso de segmentaci´on, los pixels se distribuyen formando distintas regiones, que se van modificando hasta que el sistema queda equilibrado y la cohesi´on interna entre los pixels de cada regi´on es suficientemente fuerte. La explicaci´on detallada de c´omo funciona el algoritmo de segmentaci´on se encuentra en el Anexo A. 3.1.2. La influencia del modelo de color: RGB vs Lab El art´ıculo original realiza la segmentaci´on de la imagen usando el espacio de col- or RGB. A pesar de que los resultados son buenos, no sirven totalmente para nuestros prop´ositos. Al trabajar sobre el espacio de color RGB, tratan del mismo modo todos los pixels de la imagen y no tienen en cuenta que en una regi´on pueda haber variaciones de luminosidad producidas por sombreado. Por ello, puesto que nosotros buscamos regiones 11 3.1. Fase 1: Segmentaci´on Grid Knn 5 Knn 10 Knn 20 RGB Lab Figura 3.2: Comparaci´on de segmentaci´on RGB vs Lab. Para cualquier tipo de grafo, la mejor segmentaci´on se obtiene con espacio de color Lab de albedo (reflectancia) constante y basandonos en el estudio de Funt et al. [FDB91] que dice que variaciones de reflectancia alteran la cromaticidad mientras que variaciones de sombreado la mantienen constante, utilizamos el modelo de color Lab 1. Este modelo, por la forma en que est´a definido, nos permite abstraernos de estas variaciones lum´ınicas y trabajar directamente con la crominancia. En concreto, usamos ´unicamente los canales crom´aticos a y b con lo que conseguimos que una regi´on con un albedo constante, pero sometida a un foco de luz y por ello, con un gradiente de intensidad, sea segmentada como un ´unico cluster y no como varios, como ocurre en el ejemplo de la Figura 3.2 para el caso de RGB. 3.1.3. Filtrado y mejora de la segmentaci´on Para mejorar los resultados de la segmentaci´on se somete la imagen segmentada inicial a un proceso iterativo de filtrado y re-segmentaci´on de manera que los clusters resultantes tengan la m´axima coherencia interna posible. Con este filtrado conseguimos que casos de segmentaci´on que pueden ser un problema para la posterior fase del algoritmo, sean mejorados. En la figura 3.3 vemos un ejemplo de clusters que pueden producir grandes errores en el algoritmo. 1El modelo Lab consta de tres dimensiones, la primera dimensi´on L, representa la luminosidad del color. Las dimensions a y b representan la cromaticidad del color. 12 3. Descomposici´on en reflectancia e iluminaci´on (a) Imagen Original (b) Mala segmentaci´on (c) Buena segmentaci´on Figura 3.3: Ejemplos de segmentaci´on. Los pixels blancos representan un cluster. En (b) los clusters seleccionados abarcan zonas de la imagen muy distantes entre s´ı y con valores de luminancia muy dispares. 3.1.4. Resultados segmentaci´on Para evaluar el algoritmo, realizamos varias pruebas utilizando grafos GRID yKNN (variando el n´umero de vecinos de 5 a 30). Asimismo, tambi´en probamos utilizando el modelo de color Lab y RGB tanto con im´agenes artificiales como con im´agenes reales. Las pruebas que realizamos nos permiten concluir que los mejores resultados se obtienen usando un modelo de color Lab, que permite una mejor clasificaci´on de clusters por albedo, y grafo KNN, puesto que captura mejor las relaciones de similitud entre p´ıxeles pr´oximos en la imagen. En el Anexo A hay una exhaustiva evaluaci´on del algoritmo original de segmentaci´on donde, adem´as de evaluar los tipos de grafos, se analizan los par´ametros de entrada que requiere la segmentaci´on. En nuestro caso, hemos podido fijar los valores de dichos par´ametros y mantener el m´etodo exento de la intervenci´on del usuario. Vemos algunos ejemplos de segmentaci´on en la Figura 3.4. 3.2. Fase 2: Normalizaci´on Nuestro objetivo es normalizar la imagen de luminancia inicial eliminando aquellas variaciones de luminosidad producidas por textura pero manteniendo las variaciones producidas por la geometr´ıa del objeto (sombras). Para ello, comenzamos calculando la imagen de la luminosidad inicial utilizando los valores RGB de cada pixel con la siguiente ecuaci´on L(x, y) = 0,212R(x, y)+0,715G(x, y)+0,072B(x, y) [I.T90]. La imagen obtenida representa la luminosidad de la imagen de manera similar a c´omo la percibe el ojo humano, sin embargo, no representa la luminosidad real (iluminaci´on) del objeto, ya que contiene toda la informaci´on relacionada con la textura de los materiales. Por este motivo, bas´andonos en la premisa de que el objeto es globalmente convexo y que la iluminaci´on var´ıa suavemente en la superficie del objeto [Hor86], en nuestro algoritmo asumimos que la luminosidad se mantiene constante en las fronteras entre clusters y planteamos un sistema de ecuaciones 13 3.2. Fase 2: Normalizaci´on (a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l) (m) (n) (˜n) (o) Figura 3.4: Ejemplos de segmentaci´on. De izquierda a derecha las columnas representan: la imagen original (a)(e)(i)(m), el canal de luminancia perceptual L (b)(f)(j)(n), los canales crom´aticos ab (c)(g)(k)(˜n) y la segmentaci´on obtenida (d)(h)(l)(o). 14 3. Descomposici´on en reflectancia e iluminaci´on para encontrar los factores o ratios que relacionan las luminosidades entre los pares de clusters vecinos. 3.2.1. Linealizaci´on del problema Dado un conjunto Cde clusters, queremos encontrar unos factores Fcpor los que multiplicar cada cluster de la imagen de luminosidad inicial Lpara obtener la imagen de luminosidad (o luminancia) normalizada Ln, Ln(x, y) = FcL(x, y) (3.2) para c∈Cy (x, y)∈c. Puesto que queremos igualar el valor de la luminosidad en las fronteras de los clusters, tenemos una ecuaci´on para cada par de clusters vecinos donde expresamos esta igualdad, FciLm(ci)cj−FcjLm(cj)ci= 0 (3.3) donde Lm(ci)cjrepresenta la luminosidad media de los pixels del cluster cique se encuentran en la frontera con el cluster cjy, FciyFcjrepresentan los factores por los que hay que multiplicar cada cluster para que se igualen sus luminancias. El conjunto de ecuaciones formado por cada pareja de clusters vecinos nos da un sistema lineal de Mecuaciones y Ninc´ognitas, siendo Mel n´umero de pares de clusters adyacentes y Nel n´umero total de clusters de la imagen. Como se puede observar, siendo un sistema con m´as ecuaciones que inc´ognitas la soluci´on que obtendr´ıamos resolvi´endolo es la trivial: Fc1=Fc2=FcN= 0. Por este motivo, se a˜nade una nueva ecuaci´on que conserva la luminosidad total de la imagen y evita la soluci´on trivial, N X i=1 FciLMe(ci) = N X i=1 LMe(ci) (3.4) donde LMe es la luminosidad media total de cada cluster. Esta ecuaci´on la denominamos ecuaci´on de conservaci´on de la energ´ıa, ya que obliga al sistema a mantener equilibrados los valores de luminancia total de la imagen. Las ecuaciones 3.3 y 3.4 forman el sistema AX =Bpara Nclusters y Mpares de clusters vecinos. Cada fila aide Aviene definida por, ∀i∈1..M, ai=           ∃k, l ∈1..N 3aik =Lm(ck)cl, ail =−Lm(cl)ck con k < l ∧ckes adyacente a cl aih = 0,∀h∈1..N 3h6=k∧h6=l i=M+ 1,∀j∈1..N, aij =LMe(cj) (3.5) 15 eliminar las pintadas del Jaguar de manera correcta. Nosotros, en cambio gracias a nuestro efectivo algoritmo de segmentaci´on somos capaces de detectarlas y eliminarlas. En 4.6, nuestros resultados se parecen mucho a los de Shen et al. [STL08] y Bousseau [BPD09], aunque estos ´ultimos requieren mucha interacci´on como vemos en 4.6f. (a) (b) (c) (d) Figura 4.1: Im´agenes intr´ınsecas obtenidas por nuestro algoritmo. (a) Imagen Original. (b) Luminancia perceptual. (c) Reflectancia. (d) Iluminaci´on. (a) (b) (c) Figura 4.2: Im´agenes intr´ınsecas obtenidas por nuestro algoritmo. (a) Imagen Original. (b) Reflectancia. (c) Iluminaci´on. Imagen original por Captain Chaos, flickr.com 22 4. Resultados (a) (b) (c) Figura 4.3: Im´agenes intr´ınsecas obtenidas por nuestro algoritmo. (a) Imagen Original. (b) Reflectancia. (d) Iluminaci´on. (a) (b) (c) (d) (e) (f) Figura 4.4: Comparaci´on de la componente de iluminaci´on con otros m´etodos. (a) Representa la imagen real (b) Representa la soluci´on correcta. Nuestra soluci´on (e) se acerca m´as correcta (b), que Shen [STL08] (c) o Tappen [TFA05] (d) . Los resultados de Adobe (f) se mostrar´an en la presentaci´on. 23 (a) (b) (c) (d) (e) (f) (g) (h) (i) Figura 4.5: Comparaci´on con otros m´etodos de descomposici´on. (a) Imagen Original. (b) Iluminaci´on real (c) Reflectancia real. (d) y (g) Iluminaci´on y reflectancia con nuestro m´etodo (e) y (h) Iluminaci´on y reflectancia de Shen et al. [STL08]. (f) e (i) Iluminaci´on y reflectancia de Tappen et al. [TFA05]. 24 4. Resultados (b) Nuestra descomposición: reflectancia e iluminación (c) Reflectancia e iluminación de Shen [STL08] (d) Reflectancia e iluminación de Tappen [TFA05] (e) Reflectancia e iluminación de Weiss a partir de 40 imágenes [Wei01] (f) Trazos del usuario, reflectancia e iluminación de Bousseau [BDP09] (a) Imagen original y luminancia perceptual Figura 4.6: Comparaci´on con otros m´etodos de descomposici´on 25 26 Cap´ıtulo 5 Conclusiones En este cap´ıtulo se realiza un resumen de las aportaciones de este trabajo al campo de la inform´atica gr´afica y se comenta el camino futuro de esta investigaci´on. Tambi´en recoge el resumen temporal del proyecto y las conclusiones personales de la autora. 5.1. Trabajo Realizado Una vez finalizado el proyecto, podemos concluir que se han alcanzado los objetivos establecidos al comienzo del proyecto (ver secci´on 1.2): Se ha desarrollado un algoritmo nuevo de descomposici´on en im´agenes intr´ınsecas que supera en muchos aspectos a los m´as relevantes en este ´area de investigaci´on, tanto en algoritmos autom´aticos: el m´etodo de Tappen et al. [TFA05] y el m´etodo de Shen [STL08], como en algoritmos que requieren de m´as informaci´on: el m´etodo de Weiss [Wei01] y el m´etodo de Bousseau [BPD09]. No requiere interacci´on del usuario y se ejecuta en tiempo interactivo. Se ha implementado y adaptado un algoritmo de segmentaci´on existente [FH04b], obteniendo una segmentaci´on basada en regiones de albedo constante. Se ha comprobado que la descomposici´on obtenida sirve de base para otras aplicaciones de edici´on de im´agenes: obtenci´on de 3D o cambios en la iluminaci´on, mejorando los resultados obtenidos hasta el momento con otras t´ecnicas. El trabajo realizado ha dado lugar a un posible acuerdo de estancia en Adobe Systems Inc. en San Jose (California). 5.2. Resumen temporal del proyecto En la Figura 5.1 se muestra el resumen de la evoluci´on temporal del proyecto, desde su comienzo a principios de abril hasta su finalizaci´on en noviembre. A continuaci´on se describen las fases principales: 27 5.2. Resumen temporal del proyecto Id. nov 2010oct 2010jul 2010may 2010abr 2010 jun 2010 sep 2010ago 2010 12/927/616/5 29/84/7 10/101/8 24/106/618/4 25/7 19/925/4 13/6 11/7 15/89/5 7/1122/830/523/511/4 20/6 3/1018/72/5 31/1017/108/8 5/9 26/94/4 1Documentación e investigación 2Diseño del algoritmo 3 5 Estudio de Técnicas de Segmentación 4FASE 1: Segmentación 11 Escritura Memoria 6 Implementación algoritmo «Efficient Graph-Based» 8FASE 2: Normalización, construcción del sistema lineal 10 Documentación y estudio Descomposición Multinivel Implementación 7 Análisis y evaluación de parámetros 9Análisis y evaluación de los resultados Figura 5.1: Diagrama de Gantt con la evoluci´on temporal del proyecto Documentaci´on e investigaci´on. Una vez definido el proyecto, tuvo lugar una per´ıodo de intensa documentaci´on e investigaci´on sobre las diversas t´ecnicas y m´etodos. Aunque la tarea de investigaci´on y lectura de documentaci´on ha continuado durante todo el proyecto, los primeros meses fueron clave para del dise˜no del algoritmo. Dise˜no del algoritmo. Este per´ıodo coincide con los ´ultimos d´ıas de la fase inicial de investigaci´on debido a que en ese momento ya se dispon´ıan de los conocimientos y las ideas necesarias para dise˜nar un buen algoritmo de descomposici´on. Implementaci´on. La fase de implementaci´on est´a dividida en dos fases principales: 1. FASE 1: Segmentaci´on. Se implement´o y redise˜n´o el algoritmo de segmentaci´on Efficient Graph-Based Image Segmentation [FH04b]. Previamente, se hab´ıan estudiado y evaluado los distintos algoritmos de segmentaci´on existentes. Asimismo, una vez implementado el algoritmo, se estudi´o su comportamiento para comprobar que cumpl´ıa nuestros requisitos y se explor´o el espacio de par´ametros. 2. FASE 2: Normalizaci´on y construcci´on del sistema lineal. Se implement´o al principio de la fase un m´etodo de resoluci´on simple del problema que, posteriormente, fue refinado gracias a la linealizaci´on del problema. A partir de ese momento, se fue perfeccionando la soluci´on y mejorando el sistema de ecuaciones hasta dar con la soluci´on ´optima. An´alisis y evaluaci´on de los resultados. Esta fase coincide con el final la fase 2 de la implementaci´on, ya que el an´alisis de los resultados fue paralelo a la construcci´on y perfeccionamiento del sistema lineal. Finalmente, se compararon los resultados 28 5. Conclusiones con las t´ecnicas m´as relevantes en descomposici´on de im´agenes intr´ınsecas y se confirm´o el ´exito de esta investigaci´on. Documentaci´on y estudio de la descomposici´on multinivel. A partir de los resultados obtenidos se observ´o que se podr´ıan a˜nadir mejoras sustanciales al algoritmo si se incorporaba an´alisis multinivel de la imagen. Por ello comenz´o un fase, que contin´ua actualmente, estudiando diversas de esas t´ecnicas. Escritura de la memoria. Escritura del presente documento que recoge la memoria del PFC. 5.3. Trabajo Futuro Actualmente se est´a trabajando en un art´ıculo que ser´a sometido al congreso internacional de inform´atica gr´afica SIGGRAPH 2011 y que contendr´a los resultados de esta investigaci´on. Se est´a estudiando la posibilidad de incorporar t´ecnicas de detecci´on de luces bas´andonos en los estudios de Lopez-Moreno et. al [LMHRG10]. El conocimiento previo de la luces de la escena puede ser un punto clave en la segmentaci´on de la imagen en parches de albedo constante. Esta informaci´on nos permitir´ıa desambiguar zonas de oscuridad debidas a sombras que por ser demasiado oscuras, sean consideradas como clusters individuales y por ello generar un error en la normalizaci´on. Por otro lado, conocer la direcci´on de la luz nos permite estudiar la orientaci´on de los gradientes y mejorar nuestra aproximaci´on en base a ese conocimiento. Otra de las principales ideas que se est´an explorando es la posibilidad de utilizar descomposici´on multi-escala [SSD09, FAR07, FFLS08], o trabajar sobre distintas resoluciones de la imagen. En concreto, se est´a evaluando el comportamiento de la t´ecnica de Subr et al. [SSD09] que obtiene la descomposici´on de una imagen en varios niveles de detalle (ver Figura 5.2). El uso de estas t´ecnicas nos permitir´ıa resolver los problemas que pueden causar texturas de alto rango, es decir mucho detalle, y que por ser tratadas del mismo modo que el resto de la imagen, y ser proporcionalmente mucho m´as peque˜nas, no desaparezcan. 5.4. Conclusiones personales Tanto el trabajo realizado como los resultados obtenidos han sido altamente gratificantes. No s´olo hemos realizado una importante aportaci´on al campo de la investigaci´on en inform´atica gr´afica, sino que he aprendido los ´ultimos avances en el ´area y podido aplicar y consolidar los conocimientos adquiridos en la carrera. Por otra parte, la gran carga de 29 5.4. Conclusiones personales (a) (b) (c) (d) (e) Figura 5.2: Descomposici´on multinivel de [SSD09]. En la imagen (a) vemos la imagen original. En (b)-(e) aparecen los niveles de detalle desde el m´as fino al m´as grueso. En (e) se aprecian indicios de la iluminaci´on de la escena. investigaci´on que llevaba este proyecto me ha permitido experimentar tanto la satisfacci´on de obtener buenos resultados, como la desesperaci´on, en algunos casos, de estar semanas con algo que finalmente no da los resultados esperados. Despu´es de todo, he podido comprobar que todo trabajo tiene su recompensa y en este caso, voy a tener la posibilidad de realizar una estancia en Adobe Systems Inc. en San Jos´e (California) y de publicar los resultados en uno de los congresos m´as importantes de este ´area. Personalmente, trabajar con Jorge y Diego estos meses ha sido un incre´ıble placer tanto por el entusiasmo e inter´es que transmiten en su trabajo, como por lo mucho que he podido aprender de ellos. 30 Bibliograf´ıa [BPD09] Adrien Bousseau, Sylvain Paris, and Fr´edo Durand. User assisted intrinsic images. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia 2009), 28(5), 2009. [BR94] Berry M. Chan T. F. Demmel J. Donato J. Dongarra J. Pozo R. Eijkhout V. Van der Vorst H. Barret, R. and C. Romine. Templates for the Solution of Linear Systems: Building Blocks for iterative Methods, 2nd Edition. SIAM, 1994. [BT78] H.G. Barrow and J.M. Tenenbaum. Recovering intrinsic scene characteristics from images. Computer Vision Systems, pages 3–26, 1978. [BVZ01] Yuri Boykov, Olga Veksler, and Ramin Zabih. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23:2001, 2001. [CM02] D. Comaniciu and P. Meer. Mean shift: a robust approach toward feature space analysis. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 24(5):603 –619, May 2002. [CPD07] Jiawen Chen, Sylvain Paris, and Fr´edo Durand. Real-time edge-aware image processing with the bilateral grid. In SIGGRAPH ’07: ACM SIGGRAPH 2007 papers, page 103, New York, NY, USA, 2007. ACM. [Cro80] George Robert Cross. Markov random field texture models. PhD thesis, East Lansing, MI, USA, 1980. AAI8112063. [EHLM71] John Edwin H. Land and J. Mccann. Lightness and retinex theory. Journal of the Optical Society of America, pages 1–11, 1971. [FAR07] Raanan Fattal, Maneesh Agrawala, and Szymon Rusinkiewicz. Multiscale shape and detail enhancement from multi-light image collections. In SIGGRAPH ’07: ACM SIGGRAPH 2007 papers, page 51, New York, NY, USA, 2007. ACM. 31 A.1. T´ecnicas de segmentaci´on naci´on de ruido, reconstrucci´on de texturas, etc. Seg´un formul´o Geman et al. [GG84], los campos aleatorios de Markov proporcionan un buen modelo te´orico para algunos de estos problemas de inferencia en im´agenes, en los que queremos obtener lo que hay realmente, a partir de los datos que disponemos que, en estos casos, son matrices que representan los p´ıxeles de la imagen. Asumimos que disponemos de un conjunto de observaciones sobre la imagen yi, y que queremos inferir su valor latente en la escena xi(el ´ındice ipuede representar un pixel o una regi´on de p´ıxeles). Adem´as, asumimos que hay una dependencia estad´ıstica entre xieyique viene definida por una funci´on de compatibilidad φ(xi, yi). Por otra parte, las variables de la imagen tambi´en est´an relacionadas de tal manera que podemos establecer otra funci´on de compatibilidad ψ(xi, xj) que relaciona pares de pixels vecinos (ver Figura A.1). Dicho esto, podemos formular probabilidad condicional entre la imagen observada yiy la imagen que queremos inferir con lo siguiente: p(x, y) = 1 ZYψ(xi, xj)Yφ(xi, yi) (A.1) donde Zes una constante de normalizaci´on. Figura A.1: Ejemplo gr´afico de un campo aleatorio de Markov. Los puntos negros yirepresentan las observaciones y los puntos blancos xilos valores que buscamos. En otras palabras, los campos aleatorio de Markov establecen que la probabilidad condicional de que un pixel tenga un determinado valor viene dada por el valor de sus vecinos, no por la imagen entera, y por tanto, pueden ser usados para modelar determinadas propiedades de continuidad y suavidad entre regiones de la imagen. Existen numerosas t´ecnicas que resuelven directamente problemas planteados en base a campos aleatorios de Markov. Algunas de las m´as usadas y eficientes [SZS+08] son la propagaci´on del conocimiento (Belief Propagation [YFW03, FH04c] o el corte de grafos (Graph Cuts) [BVZ01]. Sin embargo, estos m´etodos, aunque eficientes, necesitan conocer el n´umero de regiones de la imagen o al menos disponer de alguna funci´on de energ´ıa que relacione las variables y las observaciones para poder definir las funciones de compatibilidad. En nuestro caso, no hemos experimentado con estas t´ecnicas puesto que hemos tenido conocimiento de que Adobe ya ha desarrollado una l´ınea de investigaci´on explorando ese camino y no obtienen buenos resultados sin intervenci´on del usuario. 38 A. Estudio de la segmentaci´on A.1.2. M´etodos de clusterizado Una de las t´ecnicas m´as usadas en algoritmos de visi´on por computador es la llamada desplazamiento de media (mean shift) [CM02]. Se encuentra dentro de las t´ecnicas que tratan de buscar clusters dentro de un espacio de caracter´ısticas (no tienen en cuenta relaciones espaciales entre los pixels) y las cuales asumen que la imagen es constante por segmentos. El algoritmo de Mean-shift realiza un suavizado de la imagen agrupando p´ıxeles semejantes y formando clusters que se identifican por su color m´as significativo. Posteriormente, un refinamiento de este primer clusterizado obtiene la segmentaci´on deseada de la imagen. Esta t´ecnica obtiene buenos resultados, pero como se dice en [UPH07], es muy sensible a los par´ametros, es decir, la elecci´on de los par´ametros de ejecuci´on del algoritmo depende mucho de la imagen y de los resultados que queramos obtener, motivo por el cual no sirve a nuestros prop´ositos. Hay que hacer menci´on especial a una t´ecnica de clusterizado denominada k-means adaptativo [PJ89]. ´ Esta combina la idea sencilla de trabajar en un espacio de caracter´ısticas donde los pixels est´an relacionados por color, al igual que mean shift, junto con diversas propiedades de continuidad espacial. La idea se asemeja, en cierto modo, a la que usamos en nuestro m´etodo por lo que no descartamos en trabajo futuro evaluar su comportamiento en nuestro algoritmo. A.1.3. M´etodos basados en grafos Las t´ecnicas basadas en grafo, normalmente representan los p´ıxeles de la imagen como un grafo ponderado no dirigido, donde cada punto representa un nodo y el peso viene determinado por alguna relaci´on entre los v´ertices que conecta, como puede ser la diferencia de intensidades. Un conjunto de t´ecnicas muy extendidas son las basadas en realizar cortes m´ınimos en grafos, donde el criterio de corte esta dise˜nado para minimizar la similitud entre los p´ıxeles que est´an siendo divididos. La t´ecnica m´as famosa es la conocida como cortes normalizados (normalized cuts) [SM00] y destaca porque en lugar de solo capturar propiedades locales de la imagen, encuentra caracter´ısticas a nivel global. No obstante, estas aproximaciones de cortes normalizados son demasiado lentas para nuestro algoritmo. Dentro de estas t´ecnicas basadas en grafo se encuentra la que hemos escogido en nuestro algoritmo y que est´a siendo usada recientemente en aplicaciones de visi´on est´ereo para la b´usqueda de superpixels [MK10]. En la siguiente secci´on se da una descripci´on detallada de la misma. A.2. Segmentaci´on eficiente basada en grafo El m´etodo elegido, ideado por Felzenszwalb y Huttenlocher [FH04b], se trata de un algoritmo basado en grafo que se ajusta muy bien a nuestras necesidades de rapidez y 39 A.2. Segmentaci´on eficiente basada en grafo eficacia. La clave de su utilidad es que dispone de un umbral adaptativo como veremos a continuaci´on. El algoritmo parte un grafo no dirigido G= (V, E) formado por un conjunto nde v´ertices v∈V, que se corresponden con los pixels a segmentar de la imagen representados en el espacio de caracter´ısticas, y un conjunto mde aristas {ei}que constituyen pares de v´ertices vecinos. Cada arista tiene tiene un peso w((vi, vj)), que representa la similitud entre los dos pixels conectados por esa arista. La segmentaci´on final ser´a S= (C1, ..., Cr) donde Cies un cluster de puntos. El algoritmo es el siguiente: 1. Ordenar el conjunto de aristas E= (e1, ..., em) tales que |et| ≤ |et0|∀t < t0. 2. Sea S0= ({v1}, ..., {vn}), (inicialmente cada cluster contiene exactamente un v´ertice). 3. For t= 1, ..., m a Sean viyvjlos v´ertices conectados por et. b Sea Ct−1 viel componente que contiene el punto vien la iteraci´on t−1 y li= maxmstCt−1 viel mayor peso de las aristas que hay dentro de Ct−1 vi. Del mismo modo obtenemos lj. c Uniremos los componentes Ct−1 viyCt−1 vjsi, |et|<m´ın (li+k |Ct−1 vi|, lj+k |Ct−1 vj|)(A.2) donde kes una constante. 4. S=Sm En lugar de usar un valor fijo para determinar el umbral a partir del cual dos regiones se consideran distintas, del mismo modo que lo hace Zahn en su m´etodo [Zah71], utiliza un valor variable en la F´ormula A.2. Este umbral permite que dos componentes se unan si la arista de menor peso que los une, es menor que la m´axima arista en cada uno de los componentes m´as el t´ermino τ=k/|Ct−1 vi|. Como vemos, τdepende del tama˜no del componente y de una constante inicial k. En la primera iteraci´on del algoritmo li=lj= 0, y|C0 vi|=|C0 vj|= 1, por tanto, kinicialmente representa el m´aximo peso de arista que podr´a ser a˜nadido a cada componente, k=lmax. Al aumentar el n´umero de puntos por componente, la tolerancia de a˜nadir nuevas aristas disminuye y se realizan menos uniones. Intuitivamente, kcontrola el tama˜no final de los clusters ya que controla las primeras iteraciones de la segmentaci´on. Tipos de grafo: KNN vs Grid En el art´ıculo original se proponen dos estructuras de grafo distintas, una basada en una malla (grafo GRID), donde cada pixel est´a conectado con sus 8-vecinos m´as pr´oximos por posici´on y otra basada en el m´etodo de vecino m´as pr´oximo (grafo KNN ) donde se realiza un mapeo de cada pixel en un espacio nuevo de caracter´ısticas y donde se puede 40 A. Estudio de la segmentaci´on definir libremente el n´umero de vecinos a usar. En el caso de usar un grafo GRID, la funci´on que define la similitud entre los dos pixels conectados por una arista, viene dada por su diferencia de color. Como propone el autor, usamos la distancia Eucl´ıdea L2, w((vi, vj)) = kC(vi)−C(vj)k=v u u t N X t=1 |C(vi)t−C(vj)t|(A.3) donde C(v) es el vector de color del v´ertice v, siendo C(v) = {r, g, b}en espacio de color RGB yC(v) = {a, b}en espacio de color Lab. En el otro caso, usando grafo KNN se realiza un mapeo de cada v´ertice en el espacio {x, y, C(x, y)}, donde (x, y) es la localizaci´on del v´ertice en la imagen y C(x, y) representa el color del punto que depender´a del modelo usado. Del mismo modo que con el grafo GRID usamos la distancia Eucl´ıdea L2para definir los pesos de las aristas, pero ahora tambi´en tiene influencia la posici´on del pixel en la imagen. La ventaja de usar KNN frente a GRID, es que en el primero, el poder seleccionar un n´umero variable de vecinos y capturar en la funci´on de similitud la posici´on junto con el color, permite que las conexiones de los p´ıxeles sean m´as flexibles pudiendo conectarse regiones f´ısicamente separadas. En cambio, usando grafo GRID tenemos una estructura r´ıgida en la que solo podemos realizar conexiones locales. La influencia del modelo de color: RGB vs Lab El art´ıculo original realiza la segmentaci´on de la imagen usando el espacio de col- or RGB. A pesar de que los resultados son buenos, no sirven totalmente para nuestros prop´ositos. Al trabajar sobre el espacio de color RGB, tratan del mismo modo todos los pixels de la imagen y no tienen en cuenta que en una regi´on pueda haber variaciones de luminosidad producidas por sombreado. Por ello, seguimos los estudio de Funt et al. [FDB91] y decidimos utilizar el modelo de color Lab que, por la forma en que est´a definido, nos permite abstraernos de las variaciones de luminosidad en el color de los materiales y trabajar directamente con la cromaticidad. El modelo de color Lab caracteriza cada color con la ayuda de un par´ametro de intensidad correspondiente a la luminancia y de dos par´ametros de crominancia que describen el color. Ha sido especialmente estudiado para que las distancias calculadas entre colores correspondan a las diferencias percibidas por el ojo humano. En concreto, los tres par´ametros est´an definidos del siguiente modo: 1. La componente L es la luminosidad, que va de 0 (negro) a 100 (blanco). 41 A.2. Segmentaci´on eficiente basada en grafo 2. La componente a representa la gama de rojo (valor positivo) a verde (negativo) pasando por el blanco (0) si la luminosidad vale 100. 3. La componiendo b representa la gama de amarillo (valor positivo) a azul (negativo) pasando por el blanco (0) si la luminosidad vale 100. Por su parte, RGB es un modelo de color basado en la s´ıntesis aditiva, con lo que cada color viene representado mediante la mezcla por adici´on de los tres colores primarios: rojo, verde y azul. La diferencia entre usar uno u otro modelo, en nuestro caso, es sustancialmente importante ya que con Lab conseguimos que una regi´on con un albedo constante, pero sometida a un foco de luz y por ello con un gradiente de intensidad, sea segmentada como un ´unico cluster y no como varios como ocurre err´oneamente en los ejemplos de las Figuras A.2 y A.3 para el caso de RGB. (a) Imagen original (b) Segmentaci´on RGB (c) Segmentaci´on Lab Figura A.2: Comparaci´on de segmentaci´on RGB vs Lab. Los mejores resultados se obtienen con espacio de color Lab A.2.1. Experimentos realizados En los experimentos hemos realizado pruebas modificando el valor del umbral adaptativo ky probando distintos tipos de grafos. En las Figuras A.5 y A.6 se pueden ver los resultado para dos im´agenes muy distintas y que en s´ı, abarcan la mayor´ıa de los casos que vamos a tratar. La primera se trata de una imagen donde el tama˜no de los clusters es grande en relaci´on con el tama˜no de la imagen y hay poca variaci´on crom´atica apreciable a simple vista. Por el contrario, la segunda imagen tiene un tama˜no de clusters en proporci´on mucho menor y las diferencias de cromaticidades son mucho m´as pronunciadas. Si observamos los resultados de estas podemos comprobar como el nivel de detalle de la segmentaci´on aumenta seg´un disminuye el valor del umbral. Esto se debe a que este valor controla, en las primeras iteraciones de la segmentaci´on, el peso m´aximo que puede tener una arista para formar parte de un cluster (ver F´ormula A.2). Es decir, mide la m´axima diferencia crom´atica que pueden tener dos pixels que se encuentren en el mismo cluster. Seg´un aumenta el tama˜no de los clusters, este umbral deja de tener tanto peso y el criterio para decidir si un pixel pertenece o no a un cluster viene dado por la propia coherencia 42 A. Estudio de la segmentaci´on Grid Knn 5 Knn 10 Knn 20 RGB Lab Figura A.3: Comparaci´on de segmentaci´on RGB vs Lab. Los mejores resultados se obtienen con grafo KNN y espacio de color Lab interna del mismo. Para nuestro prop´osito, puesto que necesitamos que los clusters identifiquen correctamente fragmentos de color constante y no demasiado peque˜nos, un umbral de 25 o 50 resultar´ıa v´alido (ver Figuras A.5 y A.6). Respecto al tipo de grafo a usar, comprobamos que los resultados son muy parecidos en todas las versiones del grafo KNN. No obstante, s´ı se aprecia diferencia respecto a usar grafo GRID, ya que este ´ultimo ha cometido errores no deseables en la segmentaci´on: ha divido regiones de la imagen de albedo constante pero con variaciones de iluminaci´on que deber´ıan haberse considerado como una sola. Hemos considerado aceptable la segmentaci´on con grafo KNN y cinco vecinos y hemos realizado una segunda fase de pruebas. Partiendo de los primeros resultados obtenidos, hemos realizado otro conjunto de pruebas para asegurarnos de elegir los par´ametros ´optimos. En la Figura A.7 vemos los resultados de la segmentaci´on fijando el tipo de grafo a KNN con 5 vecinos y modificamos el umbral con valores de 25, 50 y 75. Como ya hab´ıamos pensado, la segmentaci´on m´as correcta se da para un umbral de 50, obteniendo una segmentaci´on muy poco detallada seg´un aumentamos de valor. Asimismo, en la Figura A.8 vemos los resultados fijando el valor del umbral a 50 y variando el tipo de grafo. A simple vista, puede parecer que la segmentaci´on con grafo GRID es mejor ya que obtenemos un mayor n´umero de clusters, sin embargo, si ejecutamos el algoritmo de normalizaci´on sobre estas im´agenes podemos comprobar que no es as´ı. En la Figura A.4 vemos un ejemplo de error de segmentaci´on con grafo GRID y por tanto error en la normalizaci´on final. Este problema es debido a que usando grafo GRID tenemos una estructura r´ıgida: cada pixel se conecta con sus 8- vecinos m´as pr´oximos. En cambio, el grafo KNN realiza las conexiones de tal modo que se agrupan los pixels m´as parecidos en color a pesar de que no est´en f´ısicamente conectados. Los resultados en KNN son muy similares para los tres casos, por tanto, decidimos usar el grafo KNN con cinco vecinos ya que el tiempo de computaci´on es inferior a usar diez o treinta. 43 A.2. Segmentaci´on eficiente basada en grafo (a) (b) (c) Figura A.4: Error en la normalizaci´on. La imagen (a) representa la luminancia original. En (b) vemos, en la parte superior la segmentaci´on con grafo GRID y en la parte inferior la normalizaci´on final. Podemos comprobar como esta es err´onea ya que no mantiene el gradiente de iluminaci´on. En (c) tenemos el resultado usando grafo KNN. En este caso s´ı se han mantenido los gradientes de iluminaci´on de manera correcta. 44 A. Estudio de la segmentaci´on GRID KNN 5 KNN 10 KNN 30 10 25 50 100 (a) (b) (c) Figura A.5: Exploraci´on de par´ametros en la segmentaci´on 45 A.2. Segmentaci´on eficiente basada en grafo GRID KNN 5 KNN 10 KNN 30 10 25 50 100 Figura A.6: Exploraci´on de par´ametros en la segmentaci´on 46 A. Estudio de la segmentaci´on Image original 25 50 75 Figura A.7: Resultados segmentaci´on (parte 1). La primera imagen representa la imagen original y las siguientes son resultados de la segmentaci´on utilizando un grafo KNN con 5 vecinos y modificando el umbral adaptativo con los valores: 10, 25 y 50. 47 C.1. Resultados (a) Imagen original y luminancia perceptual (b) Nuestra descomposición: reflectancia e iluminación (c) Reflectancia e iluminación de Shen [STL08] (d) Reflectancia e iluminación de Tappen [TFA05] (e) Trazos de usuario, reflectancia e iluminación de Bousseau [BDP09] Figura C.2: Comparaci´on con otros m´etodos de descomposici´on 54 C. Resultados y aplicaciones (d) Trazos del usuario, reflectancia e iluminación de Bousse [BDP09] (a) Imagen Original y luminancia perceptual (b) Reflectancia e iluminación de Tappen [TFA05] (c) Reflectancia e iluminación de Shen [STL08] (e) Nuestra descomposición: reflectancia e iluminación Figura C.3: Comparaci´on con otros m´etodos de descomposici´on 55 C.2. Aplicaciones C.2. Aplicaciones En este cap´ıtulo se muestran ejemplos de distintas aplicaciones de nuestro algoritmo de descomposici´on en im´agenes intr´ınsecas. C.2.1. Shape from Shading Como ya se ha comentado en la introducci´on, el problema del Shape from Shading consiste en estimar la forma 3D de un objeto a partir de una sola fotograf´ıa del mismo. Debido a la ausencia de variables que acoten el problema, nos resulta imposible obtener una reconstrucci´on precisa del objeto. Numerosos m´etodos se han desarrollado y cada uno afronta el problema desde una perspectiva distinta, sin embargo, todos coinciden en realizar fuertes asunciones sobre la naturaleza de los objetos. En general, bas´andose en estudios de percepci´on, todos asumen que los objetos son globalmente convexos [LB00] y parten de la idea de dark is deep, es decir, cuanto m´as oscuro se considera m´as lejano y m´as claro m´as cercano. Como se puede intuir, esta ´ultima asunci´on, no va a dar resultados correctos cuando tratemos objetos con variaciones de albedo debidas a textura. Por este motivo, los resultados de este proyecto son una pieza clave en este tipo de algoritmos, ya que eliminamos estas variaciones de textura manteniendo las variaciones por geometr´ıa. En la Figura C.4 vemos un ejemplo del algoritmo de Shape From Shading de Wei et al. [WH97] que resultar´ıa beneficiado por nuestra descomposici´on. Figura C.4: Resultado real de Shape from Shading. Imagen Original y diferentes puntos de vista mostrando la reconstrucci´on tridimensional. C.2.2. Retexturizaci´on y reiluminaci´on Una de las aplicaciones m´as b´asicas de la descomposici´on en im´agenes intr´ınsecas es el cambio de la textura de los materiales. Una vez que hemos separado la iluminaci´on de la reflectancia podemos estimar el mapa de normales de la imagen y aplicarlo a la imagen modificada de la reflectancia de forma similar a como lo hace Fang et al. [FH04a]. 56 C. Resultados y aplicaciones Otros algoritmos de edici´on de materiales a partir de una sola imagen como el de Khan et al. [KRFB06] obtendr´an mejores resultados gracias a esta descomposici´on. (a) Figura C.5: Edici´on de materiales de Khan et al. [KRFB06] Del mismo modo que podemos modificar los materiales de la imagen, tenemos la capacidad de reiluminarla de manera mucho m´as realista y precisa que realizar simples retoques con Photoshop. En la Figura C.6 vemos un ejemplo de esta posibilidad. Aunque para construirla nos hemos limitado a variar la componente de iluminaci´on de una manera muy simple, podemos comprobar como se respetan las sombras producidas por la geometr´ıa y el resultado est´a m´as estilizado. (a) (b) Figura C.6: Ejemplo de reiluminaci´on con nuestro algoritmo de descomposici´on. (a) Imagen Original. (b) Imagen reiluminada 57