Logotipo UNICAMP - Projeto 2


:: Julho de 2003 ::


Projetos em Computação Gráfica - 2º Projeto
IA725 - Computação Gráfica 1º Semestre de 2003	Prof.a Wu, Shin-Ting DCA/FEEC/UNICAMP

Projetos

1º Projeto

2º Projeto

3º Projeto

1) Descrição do Programa

O objetivo deste programa é implementar os algoritmos de ordered dithering e floyd-steinberg para reduzir imagens com 255 tons de cinza em imagens preto-e-branco. Devemos também comparar os resultados obtidos e comentar ainda como seriam as imagens em preto-e-branco se forem utilizados os algoritmos de clustered-dot ordered dithering.

O algoritmo foi desenvolvido na linguagem de programação Borland C++ 5.02 com o uso das funções do OpenGL 95, sob o sistema operacional Windows Millenium.

O programa dithering (dithering.cpp/dithering.exe) lê um arquivo texto que contém uma matriz numérica utilizada para carregamento e visualização de uma imagem. Para isso, foram utilizados dois arquivos como exemplo: lena.pgm e gray_scale.pgm. Nestes arquivos, são analisados qual a resolução da imagem, descartando as linhas de comentário. Feito isso, a matriz numérica deve ser carregada em função destes parâmetros (largura e altura) para que possa, através das funções do OpenGL, mostrar a imagem.

Em primeira instância, fiz uma leitura completa da matriz e a carreguei em uma lista (chamada no programa de matglu). Para que a matriz seja usada nas funções do OpenGL, precisei converter esta lista em um array de display. Porém, o seu descarregamento deve ser feito na ordem inversa, ou seja, do fim para o começo dos elementos, evitando que a imagem apareça invertida ("de cabeça para baixo").

Com o array de display inicial pronto (array matjanela), é necessário aplicar os algoritmos de dithering para conversão da imagem, de acordo com a escolha do usuário (citado mais adiante). Nesta fase, os elementos do array são convertidos para as cores preto ou branco (array matdisplay), eliminando assim os tons de cinza da imagem inicial. Após esta conversão, entramos com as funções do OpenGL, responsáveis pela visualização da figura.

Para melhor compreensão do exercício, precisamos conhecer os conceitos utilizados na sua aplicação.

1.1) Conceito de Dithering

Dithering é o processo de renderização de uma imagem em um dispositivo capaz de aproximar uma cor pela mistura de outras cores, quando a original (ou requerida) não está disponível. Em outras palavras, seria mostrar uma quantidade menor de cores que as originais da imagem.

Podemos citar, como exemplo, a ocorrência de dithering nos monitores que não suportam a grande quantidade de cores que uma imagem possa ter, ou a conversão de imagens coloridas em preto e branco.

1.2) Floyd-Steinberg Dithering

Esta técnica é um aprimoramento da técnica de Threshold. Quando o valor da intensidade (para cada pixel) da imagem passa de um determinado limite, este é pintado com a intensidade mais alta do dispositivo. Caso contrário, ele será pintado com a intensidade mais baixa. Em relação ao algoritmo de Floyd-Steinberg, ele busca "suavizar" este erro, distribuindo-o entre os pixels adjacentes. Assim, o erro de quantização local é distribuído, minimizando globalmente as diferenças de intensidade entre a imagem original e a processada.

1.3) Ordered Dithering

Foi uma técnica desenvolvida inicialmente para melhorar a qualidade da reprodução de imagens em aparelhos de TV, que se mostrou mais tarde bastante eficaz no processamento de imagens digitalizadas. A idéia é comparar a intensidade da imagem no ponto (x,y), I(x,y), com um conjunto de valores de threshold, arranjados numa matriz nxn chamada matriz de dither. Os pontos principais desta técnica são a escolha dos valores do threshold e de seus posicionamentos na matriz de dither.

2) Executando o Programa

Para iniciar o programa, devemos passar os parâmetros para escolha dos algoritmos, como mostrado abaixo:

C:\dither> dithering lena.pgm 0 0

C:\dither> dithering lena.pgm 0 1

C:\dither> dithering lena.pgm 1

C:\dither> dithering lena.pgm 2

Onde,

o primeiro parâmetro recebe o nome completo do arquivo texto a ser analisado;
o segundo, o tipo de dithering a ser aplicado (0 para Ordered, 1 para Limiar e 2 para Floyd-Steinberg);
o terceiro, é referente ao tipo de Ordered dithering (0 para dispersed e 1 para clustered), não sendo aplicado para o algoritmo de Floyd-Steinberg.

Podemos ver estas informações em tela digitando "dithering" no prompt de comando.

Um detalhe: o programa mostra a imagem original seguida da imagem
com a aplicação do dithering escolhido. Portanto, é necessário esperar
um segundo (em tempo de programação) para que vejamos o resultado.

Um problema encontrado no desenvolvimento do programa foi o reposicionamento da imagem no momento de um re-display da janela. Os testes realizados sob o Windows Millenium revelaram uma suposta falha: a imagem, após alguns segundos na tela, era recriada no canto superior esquerdo do monitor, fora da sua janela de visualização. Quando testei o programa num computador com Windows 98, Windows 2000 Professional, Windows 2000 Server e Linux, com a mesma versão de Borland C++ e OpenGL (com exceção do Linux, que tinha o Mesa instalado), a imagem saiu perfeita, sem alterações. Testei então a função glViewport() para forçar o display na janela, mas o erro persistiu.

Após o problema ser colocado na lista de discussão da disciplina, vimos que a versão do fabricante das dlls encontradas no sistema operacional e utilizadas pelo OpenGL poderiam afetar o programa. Copiei então os arquivos glut32.dll e glu32.dll do Windows 98 no Windows Millenium. Porém, o problema persistiu.

Figura 1 - "Falha" de reposicionamento da imagem no Windows Millenium

3) Análise Comparativa dos Algoritmos

Em relação aos algoritmos, vemos que o dithering de Floyd-Steinberg faz uma leitura mais complexa dos pixels, gerando melhores resultados. Porém, isso torna o método um pouco mais lento. Já os algoritmos de Ordered, apesar de serem mais simples e mais rápidos, não são tão exatos e produzem algumas "hachuras" no lugar das cores da imagem. No algoritmo clustered ordered, estas hachuras tendem a deixar algumas áreas da imagem mais "escuras" e no algoritmo de dispersed ordered os efeitos são mais leves. Para avaliarmos melhor a diferença entre os tipos limiar e floyd-steinberg, foram colocados diferentes valores de threshold: 127 para limiar e 135 para floyd.

Vejamos agora o resultado das imagens: