INF01046 – Fundamentos de Proces

INF01046 – Fundamentos de Processamento de Imagens

Projeto Final

Colorização de Imagens em Tons de Cinza

Professor: Manuel Menezes de Oliveira
Semestre: 2007/2

Alunos: Rafael von Hoonholtz Magrin ([email protected])
Lucas Enrique Guaycochea ([email protected])

Introdução

O presente trabalho foi feito como projeto final da disciplina Fundamentos de Processamento de Imagens. O desafío consistiu em procurar um asunto de interés para nos relacionado com trabalhos sobre imagens, pesquisar sobre ele e desenvolver um pequeno software para aplica-o.

Logo de ter visto alguns artigos publicados em distintos congresos, agente gostou de um que falaba da colorização de imagens (image colorization) e decidimos trabalhar sobre ele. A idéia foi obtida de [1], mas para lograr implementa-o foi escolhido o algoritmo mostrado em [2] e [3].

Objetivo

O objetivo do trabalho é: dada uma imagem em tons de cinza e uma imagem análoga com algumas marcações de cores, gerar uma imagem colorida de forma automatizada.

Nas figuras 1, 2 e 3, podemos ver, respectivamente, uma imagem em tons de cinza, a imagem análoga com marcações de cores e uma imagem colorizada utilizando a implementação apresentada em [1].


Figura 1: imagem em tons de cinza.	Figura 2: imagem com marcações	Figura 3: imagem colorizada

Idéia

Como temo uma imagem com ausença de cor, a ideia é trabalhar sobre um espaço de cor onde temos um canal pra a luminância e outros dois pra a crominância, por exemplo os espaços conhecidos como YUV, YIQ ou YCbCr. Então o primeiro paso de nosso trabalho é levar as imagens presentadas geralmente em RGB, a um espaço de luminância e crominância, em nosso caso YUV.

Agora, simplemente com olhar a imagem em tons de cinza, podemos intuir que em regiões onde temos uma alteração brusca de luminância, é onde deve existir uma transição de cores; análogamente, dentro duma mesma região onde o luminância mostra-se constante ou com poucas variações vamos ter o mesmo cor, com leves cambios na saturação dele. (Entende-se por saturação a claridade ou oscuridade da cor).

Algoritmo

Básicamente o algoritmo presentado em [2] e [3], aquele que nos escolhimos para implementar, consiste em pegar cada pixel sem cor na imagem marcada e dar-lhe cor a partir duma ponderação de todas as cores presentes na imagem marcada introduzidas pelo usuario. A ponderação será feita a partir duma distancia intrínseca entre o pixel e cada cor, obtendo-se um peso para ponderar que será inversamente proporcional a ela.
A seguinte fórmula da ima idéia do que foi expressado:

Agora vamos entrar num maior detalhe matemático de manera de explicar melhor a fórmula emcima.

Desta forma, define-se:

Logo da transformação do espaço RGB ao espaço YUV, para cada pixel p da imagem, Y(p) é o valor da luminância dele, e U(p) e V(p) os valores nos canais das respetivas crominâncias. Como a ponderação vai ser a mesma pra o canal U e o canal V, no algoritmo chamaremos indistintamente a qualquer dos dois como Crom(p).
Para dois pixels 8-conectados, ou seja, vizinhos numa 8-vizinhança, s e t, define-se a distancia intrínsica (dist) entre eles como o valor absoluto da diferença entre suas luminâncias:

Se os pixels não são vizinhos, define-se um caminho (C) 8-conexo entre eles, esto é um caminho entre pixels 8-vizinhos que comença em s até chegar a t, onde calcula-se a distancia do caminho como a soma das distancias entre pares de pixels vizinhos em ele; e finalmente toma-se como distancia intrínsica entre s e t a mínima distancia calculada para todos os caminhos que conectam eles:

onde: e

Das marcações introduzidas pelo usuario vamos ter para cada uma delas um conjunto de pixels com a mesma cor: Então podemos definir agora a distancia dum pixel s a uma cor como a mínima distancia do pixel s a qualquer pixel t que pertence ao conjunto dessa cor:

• Alem disso, a função peso, pra lograr que ele seja maior quanto a distancia é menor e menor quanto a distancia seja maior, é da forma:

• Finalmente, depois de ter tudo melhor definido, a primeira fórmula apresentada pode ser re-escrivida como:

Até aqui temos apresentada a idéia do trabalho conceptual e algorítmicamente. A continuação vamos a descrever como foi feita a implementação. Mas antes, achamos que vale a pena falar sobre uma coisa. Se o letor teve prestado atenção, pode ter pensado que para a resolução do algoritmo é possivel implementar o algoritmo de Dijkstra para achar o caminho mínimo entre cada pixel e as distintas cores. Realmente é um problema que pode ser resolvido desta manera ja que vai ter um grafo e o peso (distancia intrínseca) para as conexões entre os vértices(pixels); só que o grafo vai ser muito grande e com muitas conexões(muitos caminhos possíveis), o que vai dar um custo computacional muito elevado. Então a continuação vai ser apresentada uma possibilidade de implementação muito mais económica e com resultados ótimos como vamos mostrar ao final.

Implementação

O primeiro passo é pegar as duas imagens de entrada, aquela que está em tons de cinza e tem a informação da luminância (L) e aquela outra que tem as marcações de cores feitas (M), para converter elas para um espaço de luminância e crominância (YUV).

Desta manera, se gera uma imagem (W) para trabalhar onde:

Para todo pixel posicionado en (x,y): W(x, y).Y = L(x, y).Y

Se o pixel tem cor na imagem marcada: W(x, y).U = M(x, y).U e W(x, y) V = M(x, y).V

E se o pixel não tem cor na imagem marcada, simplemente, W(x, y).U = 0 e W(x, y) V = 0

Logo para cada pixel (p) da imagem cria-se uma estructura vazía (S(p)) onde serão armazenadas pares ordenados (cor_i, dist(p,cor_i)). Idealmente devería ser enchido para todo cor_i presente na imagem marcada, mas o artigo [3] fala que obtem-se um resultado aceptável com armazenar os três cores com a menor distância intrínseca.

Inicializa-se agora um conjunto ActiveSet com as estructuras dos pixels coloridos na imagem marcada com seu primeiro par ordenado com sua cor e distância igual a 0. Então, començamos a fazer o seguinte algoritmo iterativo:

Enquanto ActiveSet não estiver vazio:

Para cada pixel w em ActiveSet:

• Remover S(w) de ActiveSet;

• Propagar as crominâncias contidas em S(w) para seus pixels vizinhos {p1, ..., p8}, actualizando a distancia dist=dist+dist(w,p_n). Para cada pixel p_nda vizinhança, o par ordenado vai ser adicionado a seu S(p_n) se aquela crominância (cor) não está ja presente na estructura com uma distancia menor.

• Se a estructura S(p_n) for modificada adicionar ela ao ActiveSet;

Finalmente quando o algoritmo iterativo acaba, todos os pixels vão ter sua estructura S completa. Então, só temos que dar cor a cada pixel usando a ponderação vista antes na seção do algoritmo, ja que temos para ponderar as três cores mais próximas e suas distancias intrínsicas para obter o respectivo peso.

Demais está dizer que a imagem ja colorida W é passada ao espaço RGB pra logo ser exibida e salvada.

Resultados e Concluções

Nesta seção apresentaremos os resultados obtidos e vamos compara-os com os resultados obtidos por os softwares que acompanham os artigos pesquisados. Achamos que geralmente o resultado em Levin[1] foi melhor na maioría dos casos, e que nossos resultados são muito parecidos a aqueles conseguidos com o software de Yang[3], o que é esperavel porque foi seguida a mesma implementação. Mas, as vezes, nosso resultado foi melhor que o resultado obtido por Levin[1].

Desta forma, podemos concluir que o resultado vai depender muito das propiedades da imagem e de como foram feitas as marcações pelo usuario.

Finalmente, nossos resultados e as comparações estam a continuação:

Nenem


grayscale image (input)	marked image (input)

Nosso resultado	Resultado em Levin[1]

Sunset


grayscale image (input)	marked image (input)	Mask (só as marcações)

Resultado em Levin[1]	Nosso resultado	Resultado em Yang [3]

Winter


grayscale image (input)	marked image (input)	Mask (só as marcações)

Resultado em Levin[1]	Nosso resultado	Resultado em Yang [3]

Jennifer


grayscale image (input)	marked image (input)	Mask (só as marcações)

Resultado em Levin[1]	Nosso resultado	Resultado em Yang [3]

Lilies


grayscale image (input)	marked image (input)	Mask (só as marcações)

Resultado em Levin[1]	Nosso resultado	Resultado em Yang [3]

Pepper


grayscale image (input)	marked image (input)	Mask (só as marcações)

Resultado em Levin[1]	Nosso resultado	Resultado em Yang [3]

Dessert


grayscale image (input)	marked image (input)	Mask (só as marcações)

Resultado em Levin[1]	Nosso resultado	Resultado em Yang [3]

Referencias

• [1] A. Levin, D. Lischinski, and Y. Weiss, “Colorization using Optimization”, in Proc. ACM SIGGRAPH Conf., 2004, pp. 689-694.

Project Page: http://www.cs.huji.ac.il/%7Eyweiss/Colorization/index.html#still

• [2] L. Yatviz and G. Sapiro, “Fast Image and Video Colorization Using Chrominance Blending”, in IEEE Transactions On Image Processing, Vol.15, No.5, May 2006, pp. 1120-1129.

Project Page: http://mountains.ece.umn.edu/%7Eliron/colorization/index.html

• [3] M. Yang, “Still Image Colorization”, ECE Dept. Northwestern Univ., March 10, 2005.

Project Page: http://www.ece.northwestern.edu/~mya671/Colorization.htm