Departamento de Ciência da
Computação - IME - USP
“As soon as we started programming, we found to our surprise that
it wasn’t as easy to get programs right as we had thought. Debugging had to be discovered.
I can remember the exact instant when I realized that a large part
of my life from then on was going to be spent in finding mistakes in my own programs.”
Maurice Wilkes discovers debugging, 1949
O objetivo desse segundo exercício-programa (EP) é treinar Recursão, Registros e structs, Alocação dinâmica de memória e Listas encadeadas.
Para isso, neste EP vocês escreverão um programa que lê de um arquivo de configuração que contém uma representação de uma imagem formada por "arranjo" de linhas verticais e horizontais. A partir dessa representação o programa
Resumo retirado da Wikipedia
Ele foi um importante contribuinte para o movimento artístico De Stijl, fundado por Theo van Doesburg. Ele desenvolveu uma forma não-representacional que ele chamou de neoplasticismo. Sua técnica consistia em pintar, sobre um fundo branco, uma grade de linhas verticais e horizontais pretas e as três cores primárias.
Para saber mais e ver alguns de seus quadros clique aqui.
Para desenvolver o EP precisamos representar imagens no computador. Isto é feito através das chamadas imagens digitais.
Uma imagem digital ou simplesmente
imagem é basicamente uma
matriz, com, digamos, altura nL (número de Linhas) e largura nC
(número de Colunas).
Cada elemento da matriz é chamada
de pixel (
Na sua forma mais básica podemos representar um pixel como
aceso ("branco"), ou apagado ("preto").
As imagens em que cada pixel possui apenas um dentre dois
"níveis" possíveis são chamadas de imagens binárias.
Imagens binárias podem ser representadas de maneira bastante compacta,
basta reservarmos apenas 1
Em geral, no entanto, dois nívels são insuficientes para representar o que costumamos chamar de imagens em preto e branco, pois estas, em geral, possuem vários níveis ou tons de cinza. Uma forma comum de representar uma imagem com vários tons de cinza é reservando um byte (8 bits) para cada pixel. Desta forma podemos representar imagens com até 256 níveis de cinza por pixel. Chamamos as imagens em que cada pixel pode ter vários tons de cinza de imagens com nível de cinza.
Já uma imagem colorida requer ainda mais informação para cada pixel. A representação mais comum é obtida decompondo uma cor nas componentes básicas 'R' (red - vermelho), 'G' (green - verde) e 'B' (blue - azul). Vermelho, verde e azul são chamadas de cores primárias, já que com combinações dessas cores podemos representarmos um espéctro grande de cores. Para a maioria das aplicações essas três cores são suficientes, pois a visão humana é tricromática.
Para simplificar a representação de imagens nesse exercício programa e torná-la independente de plataforma, dispositivo e formato, decidimos considerar a seguinte definição para uma imagem:
typedef struct {
int nL; /* numero de linhas da imagem */
int nC; /* numero de colunas da imagem */
float **pixel; /* matriz com a imagem */
} Imagem;
onde nL e nC correspondem ao número de linhas e
colunas de pixels da imagem,
e pixel é um ponteiro para a matriz que contem as "cores" (níveis de cinza)
dos pixels. O tipo float foi adotado para facilitar a manipulação das imagens.
Neste EP você escreverá um programa em C que cria imagens "Mondrian", ou simplesmente Mondrian, como saída. Dividiremos a sua tarefa nas seguintes partes:
#define TIPO_HORIZONTAL 'H'
#define TIPO_VERTICAL 'V'
struct lineStruct {
char tipo; /* pode ser 'H'=horizontal ou 'V'=vertical */
int pos, ini, fim; /* define as posicoes dos pixels nos extremos da linha */
struct lineStruct *prox;
};
typedef struct lineStruct Linha;
O campo tipo contém um caractere que indica o tipo da linha, 'H'
para horizontal e 'V'
para vertical.
Os campo pos, ini e fim indicam índices de linhas ou colunas
de uma imagem dependendo do conteúdo do campo tipo:
Você deve utilizar, obrigatoriamente, os registros Imagem e Linha definidos anteriormente, para implementar as funções de desenho a seguir.
#define COR_FUNDO 1.0 #define COR_BORDA 0.0
struct celPixel {
int x, y; /* posicao do pixel */
struct celPixel *prox;
};
typedef struct celPixel CelPixel;
struct celRegiao {
int tamanho; /* numero de pixels na regiao */
CelPixel cabpix; /* celula cabeca da lista de pixels na regiao */
};
typedef struct celRegiao CelRegiao;
Durante a varredura da imagem *img, a cada pixel com cor COR_FUNDO encontrado a função segmentaRegioes deve inicializar uma nova posição do vetor cabecas. Essa nova posição deve ser inicializada com os valores obtidos através de uma chamada da função juntaPixels. Nessa chamada o pixel com cor COR_FUNDO encontrado fará o papel de pixel semente e a cor utilizada para pintar a região deve ser qualquer uma diferente de COR_FUNDO.
Para auxiliar a depuração do seu programa, sua função segmentaRegioes deve imprimir, para cada região segmentada, o número de pixels dessa região (dê uma olhada no exemplo de execução do programa).
Ao invés de criarmos um novo registro para cada pixel de uma imagem RGB, utilizaremos uma imagem com nível de cinza para representar a intensidade ou ton de cada uma das cores primárias. Assim, teremos uma imagem com nível de cinza para R, outra para G e outra para B. Cada uma dessas imagens é chamada de um canal de cor.
Escreva uma função:
Você deve desenvolver um programa que cria um Mondrian a partir de um arquivo de configuração e salva o resultado em um arquivo ppm (portable pixmap format). O nome dos arquivos devem ser recebidos pela linha de comando da seguinte maneira:
Para usar esse programa digite: ep2 <nomeArquivoDeEntrada> <nomeDaImagemDeSaida> Exemplo: ep2 entrada.txt saidaRGB
O arquivo de configuração determina o tamanho da imagem e o arranjo das linhas verticais e horizontais que compõem o Mondrian. A função leMondrian que faz a leitura desse arquivo é fornecida no esqueleto (ou seja, você não precisa implementá-la).
Após carregar as linhas, seu programa deve criar uma imagem onde as linhas devem ser desenhadas e uma borda deve ser desenhada ao redor da imagem.
Utilize a função segmentaRegioes para determinar o número de regiões e obter o agrupamento de pixels de cada região. Seu programa deve imprimir, para cada agrupamento conexo de pixels, o número de pixels contidos no agrupamento.
Deixamos a seu critério a forma para colorir cada região. Uma tabela com cores é fornecida mais adiante, mas você pode utilizar outras cores se desejar, ou utilizar apenas algumas delas (como só R, G e B, além do preto e branco). O seu programa, no entanto, precisa utilizar obrigatoriamente a função pintaRegiao e gerar uma imagem colorida RGB (na forma de 3 canais de nível de cinza). Por exemplo, você pode sortear uma cor da tabela para cada região.
A imagem RGB gerada deve ser salva utilizando a função salvaImagemRBG, também fornecida no esqueleto.
float getPixel(Imagem *img, int x, int y); void setPixel(Imagem *img, int x, int y, float cor); void pintaImagem(Imagem *img, float cor); void copiaImagem (Imagem *destino, Imagem *origem); Imagem *criaImagem(int nLins, int nCols); void desenhaLinha(Imagem *img, Linha *lin, float cor); void desenhaBorda(Imagem *img, float cor); int juntaPixels(Imagem *img, int x, int y, float corNova, celPixel *cabeca); int segmentaRegioes(Imagem *img, celRegiao cabecas[MAX_REGIOES]); void pintaRegiao(celPixel *cab, Imagem *R, Imagem *G, Imagem *B, float cor[3]);
Para a linha
R 480 640temos que 480 é a altura ou número de linhas (nL) da imagem, e 640 é a largura ou número de colunas (nC) da imagem.
Para a linha
V 150 100 479temos que o caractere 'V' indica que a linha é vertical que está na coluna 150 da imagem. Como uma imagem digital é uma matriz, os índices das colunas da imagem (linhas verticais) podem assumir valores entre 0 (zero) e nC-1. A posição da linha é esse índice. No presente exemplo temos a representação de uma linha vertical em que os extremos estão nas posições (100,150) e (479,150) da imagem
Já para a linha
H 300 430 639representa uma linha horizontal que tem seus extremos nas posições (300,430) e (300,639) da imagem.
R 480 640 V 170 0 479 V 430 0 479 V 320 0 200 V 250 200 350 V 350 200 350 V 300 350 479 H 180 430 639 H 300 430 639 H 200 0 430 H 350 170 430a função leMondrian produz as mensagens:
Arquivo de entrada com a definicao do desenho: entrada.txt Resolucao da Imagem: 480 linhas x 640 colunas Linha 1: Tipo V com pos = 170, inicio = 0 e fim 479 Linha 2: Tipo V com pos = 430, inicio = 0 e fim 479 Linha 3: Tipo V com pos = 320, inicio = 0 e fim 200 Linha 4: Tipo V com pos = 250, inicio = 200 e fim 350 Linha 5: Tipo V com pos = 350, inicio = 200 e fim 350 Linha 6: Tipo V com pos = 300, inicio = 350 e fim 479 Linha 7: Tipo H com pos = 180, inicio = 430 e fim 639 Linha 8: Tipo H com pos = 300, inicio = 430 e fim 639 Linha 9: Tipo H com pos = 200, inicio = 0 e fim 430 Linha 10: Tipo H com pos = 350, inicio = 170 e fim 430
A função leMondrian devolve essas 10 linhas em uma lista ligada com cabeça. O seu programa precisa apenas chamar essa função e percorrer a lista para desenhar cada linha.
Assim o seu programa deve gerar a seguinte imagem (observe que a origem do desenho fica no canto inferior esquerdo)
A seguir o seu programa deve processar a imagem e segmentá-la em regiões, produzindo uma lista de regiões como a seguinte:
Grupos de pixeis conexos: Grupo 0 tem 33631 pixels Grupo 1 tem 29651 pixels Grupo 2 tem 21691 pixels Grupo 3 tem 37232 pixels Grupo 4 tem 24752 pixels Grupo 5 tem 46982 pixels Grupo 6 tem 11771 pixels Grupo 7 tem 14751 pixels Grupo 8 tem 11771 pixels Grupo 9 tem 37024 pixels Grupo 10 tem 16512 pixels Grupo 11 tem 16512 pixels
Por fim, seu programa deve associar uma cor a cada região, como por exemplo:
float CORES[12][3]=
{
{1.0, 0.0, 0.0}, /* 0 red */
{0.0, 1.0, 0.0}, /* 1 green */
{0.0, 0.0, 1.0}, /* 2 blue */
{1.0, 1.0, 0.0}, /* 3 yellow */
{1.0, 0.0, 1.0}, /* 4 magenta */
{0.0, 0.0, 0.0}, /* 5 black */
{0.2, 0.7, 0.4}, /* 6 green 2 */
{0.7, 0.4, 0.2}, /* 7 marrom */
{0.0, 1.0, 1.0}, /* 8 cyan */
{0.5, 0.5, 0.5}, /* 9 cinza */
{1.0, 1.0, 1.0}, /* 10 branco */
{0.0, 0.0, 0.0} /* 11 preto */
};
O seu programa pode utilizar cores diferentes e utilizar outros esquemas para associar
uma cor a uma região.
Teste seu programa (sua função) com arquivos de entrada diferentes (invente os seus), assim como distribuição de cores diferentes. Inicialmente teste com imagens bem pequenas e desenhos bem simples.
O executável mondrian resolve o problema. Compare os resultados obtidos pelo seu programa com o do executável fornecido.