2^o Exercício Colaborativo:

"Quantização de Imagens"

Grupo:

Professora: Wu Shin Ting

          Para explicar o processo de quantização, será tomado por base o programa presente no sistema operacional UNIX : ppmquant.c. A partir deste programa serão  analisadas e discutidas as funções utilizadas, enfatizando a viabilidade de cada uma . Ao final é mostrado o resultado encontrado para algumas imagens trabalhadas.

         Programa ppmquant

           Def:  Programa para quantização de imagens no formato ppm (especificado em infoppm.html), para determinados número de cores.

           Parâmetros de entrada: Para a executação do programa ppmquant.c, é necessária a seguinte linha de comando:

           ppmquant [-floyd|-fs]  número de cores  imagem ppm  >saida.ppm

 sendo:

          ppmquant – chamada do executável do arquivo fonte ppmquant.c

          [-floyd|-fs] – opção de propagação de erro

          número de cores – representa a quantidade de cores da imagem de saída

          imagem ppm – imagem original a ser quantizada

         saida.ppm – imagem quantizada de saída

           Descrição do arquivo fonte ppmquant.c:

           O programa é dividido basicamente em 4 partes, correspondentes a:

1-    Leitura da imagem a ser quantizada

2-    Construção do Histograma

3-    Aplicação do algoritmo de corte de mediana e criação da nova tabela de cores

4-    Mapeamento das cores da imagem usando a nova tabela de cores

1-    Leitura da imagem

             A leitura da imagem a ser quantizada é realizada de forma bastante simples no programa. É utilizada a função ppm_readppm da seguinte forma:

              Pixels = ppm_readppm(ifp, &cols, &rols, &maxval)

 onde:

          ifp – especifica a abertura do arquivo (acesso ao arquivo)

          &cols – especifica o número de colunas ou largura da imagem

          &rols – especifica o número de linhas ou altura da imagem

          &maxval – especifica o máximo valor da imagem

2-Construção do Histograma

             Após a leitura do arquivo, é construído o histograma da imagem, através do uso da rotina, já pronta, ppm_computecolorhist, da seguinte forma:

                 chv = ppm_computecolorhist (pixels, cols, rows, MAXCOLORS, &colors);

             A saída do histograma pode ser visualizada através do executável do UNIX do programa ppmhist.c, da seguinte forma:

                 ppmhist <imagem ppm>

 aparecendo na tela cinco colunas, com os níveis R, G e B, nas 3 primeiras colunas, lum na quarta, e counter (frequência) na última coluna.

           A tabela a seguir, mostra parte do histograma da figura aries.ppm:

 r   g   b      lum     count

--- --- ---     ---     -----

 19  19  27     20      367027

 45  23   0     27      21814

 44  24   0     27      2990

 47  23   0     28      2601

 19  20  25     20      1895

OBS: Foram realizadas duas tentativas de construção do histograma:

 I- A primeira tentativa, foi o programa histo.m, construído pelo grupo mentor. Os problemas foram:

1-    Necessidade de converter a imagem para o formato tiff, já que o Matlab não trabalha com imagens no formato ppm;

2-    Foram construídos os histogramas de cada cor (R,G e B), sendo que há a necessidade de se construir um histograma tridimensional;

3-    Processamento muito demorado, já que o uso de loops com comandos for no Matlab é ineficiente.

II- Segunda tentativa, programa histpaulo.c, construído pelo aluno Paulo.

             3- Aplicação do algoritmo de corte de mediana

             O processo de corte de mediana necessita, primeiramente, do número de níveis de quantização desejado, por exemplo 256 (8 bits).

            O algoritmo de corte de mediana está explicado em mediana.html, retirada do livro Computação Gráfica I  (Jonas Gomes e  Luiz Velho).

            Os passos desse algoritmo são basicamente:

            1-    Encontrar o paralelepípedo de volume mínimo que contém todas as cores na imagem;

2-    Ordenar as cores ao longo das arestas

3-    Dividir o paralelepípedo em duas regiões utilizando a mediana

4-    Repetir os passos anteriores, até que o espaço de cor original tenha sido dividido no número de níveis de quantização requeridos (células).

            Desta forma, cria-se a nova tabela de cores, pelo comando:

             Colormap = mediancut(chv, colors, rows*cols, maxval, newcolors);

 onde:

          chv – arquivo que contem o histograma da imagem original

          colors – quantidade de cores da imagem original

          newcolors -  nova quantidade de cores

          4- Mapeamento das cores da imagem usando a nova tabela de cores

           Nesta parte, aplica-se o novo mapa de cor na imagem original. Neste processo, utiliza-se algum tipo de algoritmo para minimizar erros, como problemas de borda das células (citadas no item 3).

          O algoritmo utilizado no programa foi o Floyd-Steinberg, que está discutido em floyd.html.

            Resultados do processo:  

 OBS: As imagens originais e de saída foram convertidas para o formato jpeg para possibilitar a publicação. A visualização dessas imagens, no entanto, é a mesma.