Índice

1. Objectivos de formação e resultados de aprendizagem
2. Tema: Processamento de Imagem
   1. Formato de Imagem PNM
      1. PBM: Portable BitMap? Format
      2. PGM: Portable GrayMap? Format
      3. PPM: Portable PixMap? Format
   2. Primeira fase (Fase 1)
   3. Segunda fase (Fase 2)
   4. Terceira fase (Fase 3)
      1. Pautas musicais
         1. Músicas populares

Objectivos de formação e resultados de aprendizagem

[Voltar ao índice]

Este projecto tem como objectivos principais a formação genérica e específica de estudantes em fundamentos de computação em áreas de informática afins e interligadas, a programação imperativa e a arquitectura de computadores.

Os objectivos de formação genérica incluem: (i) a pesquisa, análise e selecção de informação, (ii) o treino de trabalho de grupo na resolução de problemas, (iii) o desenvolvimento da capacidade de análise e compreensão de textos em língua inglesa, e (iv) o desenvolvimento da capacidade de comunicação escrita e oral.

Os objectivos de formação específica incluem: (i) a análise da especificação e do problema, (ii) o desenvolvimento de algoritmos e consequente programação numa linguagem imperativa, (iii) a execução e realização de testes de conformidade, (iv) a análise da execução desses programas numa dada arquitectura de computadores (IA-32), e (v) a aplicação de técnicas de optimização de algoritmos/programas/códigos, com vista a melhorar o desempenho.

A avaliação dos resultados esperados de aprendizagem irão verificar se as/os estudantes conseguem demonstrar ter adquirido o seguinte conjunto de competências genéricas e específicas:

• competências genéricas

  • a capacidade de trabalho em grupo e respectiva comunicação efectiva e eficiente entre os elementos do grupo;
  • a capacidade de comunicação escrita e oral na apresentação e discussão dos processos usados e resultados obtidos;
  • a capacidade de utilização de utilitários genéricos de informática em ambiente Linux e de elaboração de documentos anotados

• competências específicas de Programação Imperativa

  • a capacidade de desenvolver algoritmos para resolver problemas, de forma criativa, criteriosa e crítica, e inserida/o num grupo de trabalho
  • o conhecimento e a capacidade de codificar algoritmos e estruturas de dados segundo os princípios da programação estruturada
  • a capacidade e aptidões práticas para gerar, executar e testar programas codificados em C, usando um conjunto adequado de utilitários (GNU)
  • o conhecimento e as aptidões de desenvolver e aplicar testes de conformidade e de analisar situações de fronteira na execução de programas
  • capacidade e aptidões na produção de documentação adequada à manutenção por terceiros dos programas desenvolvidos

• competências específicas de Arquitectura de Computadores

  • a capacidade de pesquisar, seleccionar, analisar e interpretar a informação necessária para completar a especificação inicial do projecto (em língua inglesa, e relacionada com formas de representação de informação) (Fase1);
  • o conhecimento e a capacidade de identificar e descrever formas de representação binária de informação gráfica (Fase1);
  • o conhecimento e a capacidade de identificar, compreender e caracterizar as técnicas de codificação de estruturas típicas de controlo e dos métodos de acesso e manipulação de dados estruturados, no processo de compilação de uma linguagem imperativa (gcc) (Fase2);
  • a aptidão para efectuar a análise de código em assembly e utilizar ferramentas de baixo nível de depuração (gdb) de programas (Fase2);
  • o conhecimento, a capacidade e a aptidão para a aplicação de técnicas de engenharia inversa a código binário (Fase2);
  • o conhecimento e a capacidade de identificar e descrever métricas que caracterizem o desempenho da execução dos programas específicos deste trabalho (Fase 3);
  • aptidões na aplicação de técnicas de análise de desempenho baseadas no profiling de aplicações (Fase 3);
  • capacidades e aptidões para descrever, aplicar e avaliar técnicas de optimização de desempenho independentes e dependentes da máquina (Fase 3);

Tema: Processamento de Imagem

[Voltar ao índice]

Todos os projectos têm um tema subjacente. O tema escolhido para esta instância lectiva foi o processamento de imagem.

No contexto deste projecto, as imagens a processar estarão sempre no formato PNM (Portable aNyMap) que se descreve na secção seguinte.

Formato de Imagem PNM

[Voltar ao índice]

O PNM é um formato de imagem muito simples, fácil de ler a partir de um ficheiro e também fácil de escrever para um ficheiro. Actualmente uma imagem PNM pode pertencer a uma de três famílias, abaixo explicadas: PBM, PGM e PPM. Cada família tem duas

representações

uma textual e uma compactada.

Embora não seja um requisito da especificação PNM, existe a convenção de que a imagem deve ser armazenada de cima para baixo e da esquerda para a direita. Cada pixel da imagem é armazenado num byte, valor 0 = preto, valor 255 = branco. Os componentes de cor são armazenados na ordem habitual RGB ("red", "green" and "blue"), um valor para o nível de vermelho, um valor para o nível de verde e um valor para o nível de azul.

PBM: Portable BitMap? Format

[Voltar ao índice]

Esta família corresponde a imagens contendo apenas duas cores, branco (1) e preto (0), normalmente designadas por bitmaps.

A sua forma textual pode ser descrita da seguinte maneira:

• qualquer linha iniciada pelo carácter # é um comentário; os comentários só poem aparecer nas linhas do cabeçalho, ou seja, antes dos valores dos pontos da imagem.
• a primeira linha contem o identificador do tipo da imagem: P1

• a segunda linha contem um par de valores que definem respectivamente o decimal correspondente ao número de colunas (largura da imagem em pixeis), por exemplo: 9, e o decimal correspondente ao número de linhas (altura da imagem em pixeis), por exemplo:

• as linhas restantes contêm uma lista de valores decimais, em que cada valor corresponde a um pixel da imagem e estão organizadas de acordo com os valores definidos nas linhas anteriores. Com os exemplos dados nos itens anteriores teríamos 7 linhas cada uma com 9 valores separados por espaço (cada valor corresponde a um byte, 0-255, que no caso das imagens do tipo P1 apenas assume valores no intervalo [0,1])

Um exemplo de uma imagem neste formato poderia ser:

P1
# PBM example 
9 7
 0 0 0 0 0 0 0 0 0 
 0 1 1 1 1 0 0 1 0 
 0 1 0 0 1 0 0 1 0 
 0 1 1 1 1 0 0 1 0
 0 1 0 0 0 0 0 1 0
 0 1 0 0 0 0 0 1 0
 0 0 0 0 0 0 0 0 0

Se analisar um pouco a imagem que esta representa um banner com fundo preto e letras a branco. Neste caso, a imagem contem a string "PI". Note também que, para este caso do banner, a primeira linha, a última linha, a primeira e última colunas são pretas e que entre duas letras há duas colunas pretas de separação.

A sua forma compactada resulta da constatação de que um byte é uma sequência de 8 0's e 1's. Assim, um byte pode guardar 8 pixeis da imagem. A única alteração ao formato é o identificador que passa a: P4.

A seguir apresenta-se o exemplo anterior agora compactado:

P4
# PBM example 
9 7
0 0
121 0
73 0
121 0
65 0
65 0
0 0 

Note que, apenas para efeitos de visualização, introduziram-se espaços entre os valores da forma compactada. Nas formas compactadas PNM, não há espaços de separação entre os valores. A informação é guardada em ficheiro em bytes sequenciais.

PGM: Portable GrayMap? Format

[Voltar ao índice]

Esta família corresponde a imagens definidas com vários níveis de cinzento.

A sua forma textual pode ser descrita da seguinte maneira:

• qualquer linha iniciada pelo carácter # corresponde a um comentário e deverá ser ignorada.
• a primeira linha contem o identificador do tipo da imagem: P2

• a segunda linha contem um par de valores que definem respectivamente o decimal correspondente ao número de colunas (largura da imagem em pixeis), por exemplo: 9, e o decimal correspondente ao número de linhas (altura da imagem em pixeis), por exemplo:

• a terceira linha contem o maior valor decimal que é possível encontrar para a definição de um pixel: [0,65536] (2 elevado a 16), vamos designá-lo por MAX. Normalmente, tenta-se que o intervalo seja [0,255] pois apenas nesta situação se pode falar em compactação e no formato P5. Se MAX estiver no intervalo [0,255] é utilizado apenas um byte por cada pixel da imagem. Caso contrário, MAX esteja no intervalo [256,65535], são utilizados dois bytes por cada pixel da imagem; o byte mais significativo aparece primeiro.
• as linhas restantes contêm uma lista de valores decimais, em que cada valor corresponde a um pixel da imagem e estão organizadas de acordo com os valores definidos nas linhas anteriores. Com os exemplos dados nos itens anteriores teríamos 7 linhas cada uma com 9 valores separados por espaço (cada valor corresponde a um pixel: 0-MAX).
• cada linha não deverá ter mais de 70 valores.
• o valor 0 corresponde à cor preta e o valor MAX corresponde à cor branca.

Um exemplo de uma imagem neste formato poderia ser:

P2
# PBM example 
9 7
15
 0 0 0 0 0 0 0 0 0 
 0 15 15 15 15 0 0 12 0 
 0 15 0 0 15 0 0 12 0 
 0 15 15 15 15 0 0 12 0
 0 15 0 0 0 0 0 12 0
 0 15 0 0 0 0 0 12 0
 0 0 0 0 0 0 0 0 0

Se analisar um pouco a imagem que esta representa um banner com fundo preto e letras a branco. Neste caso, a imagem contém a string "PI". Note também que, para este caso do banner, a primeira linha, a última linha, a primeira e última colunas são pretas e que entre duas letras há duas colunas pretas de separação.

A sua forma compactada resulta da eliminação dos espaços nas linhas da imagem e apenas para o caso em que MAX está no intervalo [0,255]. A única alteração ao formato é o identificador que passa a: P5.

PPM: Portable PixMap? Format

[Voltar ao índice]

Esta secção ficará em branco. Espera-se que os alunos "investiguem" e que a preencham um pouco à semelhança das outras.

Nas secções seguintes descrevem-se as diferentes fases do projecto e referem-se os requisitos que serão avaliados. Cada requisito está devidamente identificado e poderá será avaliado apenas numa das disciplinas.

Primeira fase (Fase 1)

[Voltar ao índice]

Nesta fase, pretende-se que as/os estudantes executem as seguintes tarefas:

• pesquisar a Web para caracterizar sucintamente os formatos de imagem JPEG e GIF (avaliação exclusiva de AC), e para completar o enunciado na descrição do formato PPM;
• procurar na Web produtos que, em ambiente Linux (preferencial) convertam ficheiros de imagem/gráficos em formato JPEG ou GIF para um dos formatos PNM (PBM, PGM ou PPM), e testar pelo menos um dos produtos que satisfaça os requisitos (avaliação exclusiva de AC)";
• desenvolver um conjunto de algoritmos elementares para transformar imagens PNM; mais concretamente, seguindo a descrição feita na secção anterior pretende-se transformar imagens do tipo P2, P3, P5 e P6 em imagens do tipo P1 ou P4 (avaliação exclusiva de PI);
• codificar os algoritmos propostos, documentando-os adequadamente (avaliação exclusiva de PI);
• preparar um conjunto de ficheiros de entrada para teste, que permita validar, além de outras, as de condições limite (avaliação exclusiva de PI);
• criar programas executáveis, usando o ambiente de desenvolvimento da GNU, e seleccionando o nível de optimização -O2 ;
• integrar e testar o produto final (da Fase 1) usando comandos da shell para (i) leitura de um ficheiro JPEG ou GIF e sua conversão para PNM, (ii) leitura de um ficheiro PNM (P2, P3, P5 ou P6) e sua conversão para noutro ficheiro PNM (P1 ou P4) e (iii) visualização da imagem usando ImageMagick? (avaliação exclusiva de PI);
• refinar o interface com o utilizador, construindo um menu de operações e permitindo mais que uma operação em cada sessão (avaliação exclusiva de PI);
• apresentar os resultados destas tarefas num relatório redigido em LaTeX? ; a sua estrutura deverá conter, para além do título e lista de autores, um resumo (máx. 600 caracteres), uma introdução com caracterização do problema a resolver, uma breve exposição/relato dos aspectos relevantes de cada uma das fases/tarefas, as conclusões, uma lista da bibliografia pertinente para a resolução do trabalho, e, em anexo, uma listagem do código.

A título de curiosidade, apresentam-se algumas das operações que se poderão oferecer ao utilizador (se tiver tempo utilize a sua imaginação para criar mais):

1. Compactar P1 em P4
2. Descompactar P4 em P1
3. Binarizar P2 em P1
4. Binarizar P3 em P1
5. Descompactar e Binarizar P5 em P1
6. Descompactar e Binarizar P6 em P1

Segunda fase (Fase 2)

[Voltar ao índice]

Nesta fase, pretende-se que as/os estudantes executem as seguintes tarefas:

1. Corrigir e/ou completar as tarefas solicitadas na 1ª fase e que não foram realizadas, ou foram-no de modo menos correcto ou adequado; estas incluem: (i) a produção de textos sobre JPEG/GIF/PPM, (ii) a selecção/teste de conversores JPEG/GIF para PNM (PBM, PGM ou PPM), (iii) o desenvolvimento dos algoritmos e respectiva codificação, teste e integração (com os comentários pertinentes) na transformação de imagens do tipo P2, P3, P5 e P6 em imagens do tipo P1 ou P4 , e (iv) a produção de um texto em LaTeX? para posterior integração no relatório da 2ª fase e respectiva compilação para PDF.
2. Desenvolver um conjunto adicional de algoritmos para: (i) efectuar sobre imagens PNM as operações de rodar, negativo, média-vizinhos e binarização-adaptativa (opcional), em que a descrição destas operações se encontra a seguir; e (ii) procurar os objectos contidos numa imagem colorindo-os com cores diferentes, à medida que os encontra (esta operação é apenas para imagens P1 e o resultado deverá ser uma imagem P3), de acordo com as indicações dadas no fim. Do ponto de vista de interface com o utilizador, esta novas operações solicitadas devem ser integradas com as conversões iniciais no menu de opções da Fase 1, permitindo mais que uma operação em cada sessão (avaliação exclusiva de PI).
3. Codificar os algoritmos propostos, comentando-os e documentando-os adequadamente (avaliação exclusiva de PI).
4. Criar programas executáveis, usando o ambiente de desenvolvimento da GNU, e seleccionando o nível de optimização -O2.
5. Preparar um conjunto de ficheiros de entrada para teste dos algoritmos/código das funções solicitadas, que permita validar, além de outras, as condições limite (avaliação exclusiva de PI).
6. Analisar o código assembly produzido pelo gcc no processo de compilação (apenas) do código C de uma das funções pedidas (média-vizinhos, no formato P5), dedicando uma secção do relatório a esta análise, com a seguinte informação: (i) apresentação do código em assembly, claramente identificando o corpo da função e as componentes de arranque e término da função, e incluindo comentários no corpo da função semelhantes a código C; (ii) identificação dos registos e/ou células de memória onde foram alocadas as variáveis locais da função; (iii) apresentação da estrutura e conteúdo da stack frame no início da execução do corpo da função; algumas destas tarefas deverão também ser executadas durante a defesa do trabalho (avaliação exclusiva de AC).
7. Efectuar o reverse engineering de uma função que converte uma imagem P5 noutra P5, modificada: dado o executável obter uma possível versão do código da função em C, estruturada de uma forma correcta e elegante (avaliação exclusiva de AC).
8. Integrar e testar o produto final (da Fase 2) usando comandos da shell para (i) leitura de um ficheiro JPEG ou GIF e sua conversão para PNM, (ii) leitura de um ficheiro PNM e aplicação de uma das operações pedidas, gerando um outro ficheiro PNM e (iii) visualização da imagem usando ImageMagick? (avaliação exclusiva de PI).
9. Apresentar os resultados destas tarefas num relatório redigido em LaTeX? (que terá de ser submetido já compilado para PDF, num ficheiro cujo nome contém a indicação de "Fase2" seguido da identificação do grupo (por ex., "Fase2-3.15")); a estrutura do relatório deverá ser idêntica à solicitada na Fase 1 ("conter, para além do título e lista de autores, um resumo (máx. 600 caracteres), uma introdução com caracterização do problema a resolver, uma breve exposição/relato dos aspectos relevantes de cada uma das fases/tarefas, as conclusões, uma lista da bibliografia pertinente para a resolução do trabalho, e, em anexo, uma listagem do código") e deverá incluir uma versão reformulada/corrigida/completa do relatório da Fase 1.
10. Preparar uma apresentação oral do trabalho de grupo feito até à data, (sem slides!) que não deverá ocupar mais de 5 min do tempo de defesa do trabalho.

Detalhe das operações de manipulação de imagem acima referidos (para PI):

rodar()

a imagem é rodada 90 graus para a direita.

negativo()

o valor dos pixeis da imagem é invertido de acordo com a fórmula: MAX - valor_corrente

media-vizinhos(nvizinhos)

cada pixel da imagem vai tomar um novo valor que será igual à média dos valores dos seus nvizinhos vizinhos, de acordo com a seguinte interpretação: nvizinhos=2 inclui os vizinhos da esquerda e direita; nvizinhos=4 inclui os vizinhos da esquerda, direita, cima e baixo; e nvizinhos=8 inclui os vizinhos anteriores e ainda os quatro das diagonais.

bin-adapt()

esta operação será opcional e consiste em criar uma nova versão das conversões para P1; em vez de se considerar o valor médio (Max/2) como o valor de threshold para a binarização, considere-se o valor médio da diferença entre o valor máximo e a média dos pixeis da imagem ((Max-Média)/2).

Relativamente à procura de objectos em imagens a preto-e-branco e sua coloração, os objectos a procurar são pixeis contíguos (horizontal, vertical ou diagonalmente) com o mesmo valor, e podem ser pontos, linhas ou áreas; por exemplo, se se considerar uma imagem P1 com as letras "PI" em cima, o resultado seria uma P3 com o "P" a uma cor (azul, por exemplo) e o "I" a outra cor (vermelho, por exemplo).

Terceira fase (Fase 3)

[Voltar ao índice]

Relativamente à componente de Programação Imperativa e tendo em atenção o estado em que os trabalhos se encontram, após a segunda avaliação, foi decidido que a terceira fase será opcional e só deverá ser realizada pelos grupos que cumpriram integralmente os requisitos até ao momento e que querem obter uma classificação num dos últimos escalões (Muito Bom, Excelente).

Assim, e para grande maioria dos grupos, pede-se que implementem os requisitos das fases 1 e 2. Os restantes terão de desenvolver a aplicação cujos requisitos se apresentam a seguir.

Pautas musicais

[Voltar ao índice]

Desenvolve uma aplicação para a geração automática de pautas musicais coloridas. O programa deverá aceitar um ficheiro de texto com a descrição textual de uma música e deverá gerar uma imagem P3 ou P6 com a respectiva pauta musical.

Os requisitos para a aplicação são os seguintes:

1. O desenho da pauta fica ao teu critério: espessura das linhas, dimensões das notas, ...
2. Uma pauta é constituída por cinco linhas horizontais espaçadas uniformemente. As notas colocam-se sobre as linhas ou nos espaços entre elas.
3. Uma música é constituída por uma lista de compassos. Cada compasso deverá ser separado do seguinte por uma linha vertical de espessura ligeiramente inferior à das linhas da pauta.
4. A cor das notas não é livre e deverá seguir o seguinte esquema:

   Nota Musical	Descrição	Côr RGB em Hex
   C	Dó	FF0000
   C# ou Db	Dó sustenido ou Ré bemol	FF3300
   D	Ré	FF6600
   D# ou Eb	Ré sustenido ou Mi bemol	FFCC00
   E	Mi	FFFF33
   F	Fá	00FF00
   F# ou Gb	Fá sustenido ou Sol bemol	00AA00
   G	Sol	004400
   G# ou Ab	Sol sustenido ou Lá bemol	0000FF
   A	Lá	330033
   A# ou Bb	Lá sustenido ou Si bemol	990066
   B	Si	FF0066
   CM	Dó maior	FF0000

   
   
5. O ficheiro de entrada, onde é descrita a música em forma textual, tem a seguinte estrutura:

   • Na primeira linha tem o título da música.
   • Cada linha das que se seguem à primeira contem um compasso da música.
   • Numa linha de compasso cada nota é separada da que se lhe segue por um espaço.
   • Além de notas podem aparecer pausas e sinais de repetição (o tratmento destes é opcional).
   • A título de exemplo, apresenta-se a seguir a descrição de uma música popular portuguesa bem conhecida:

     O Chapéu de 3 bicos
     G
     CM G
     G F E
     F D
     D E
     F F G
     A G
     E
     Pausa
     G CM G G
     F E F D
     D E F
     G A G C
     Repete

   • O resultado esperado para o exemplo anterior pode ser visualizado em: O Chapéu de 3 bicos.

A seguir apresentam-se mais músicas para teste da aplicação final.

Músicas populares

[Voltar ao índice]

• O lencinho

  O lencinho
  G A
  G E
  C G A
  G E
  C C C
  D D C D
  E E D E
  F F E F
  G G A
  G E
  C G A
  G E
  C C C
  D D C D
  E F G A
  G F E D
  C C
  E F
  G
  Pausa E F
  G
  Pausa A Bb
  CM
  Pausa A Bb
  CM
  Pausa C C 
  C C Bb A
  G G G A
  G F E D 
  C C
  Repete

• Dança das Horas: nesta música existem acordes (notas que devem ser tocadas ao mesmo tempo); um acorde tem parentesis curvos a limitar as suas notas; as notas de um acorde devem ser desenhadas alinhadas verticalmente, ou seja, o centro do círculo de cada nota deve estar sobre a mesma linha vertical; o tratamento de acordes é um extra.

  Dança das Horas
  A
  F G
  C
  C
  G A
  F
  F A
  G F
  C
  C C
  G A
  F
  F Pausa
  (F A)
  (F A)
  (F A)
  Pausa C
  F

• O balão do João

  O balão do João
  G E E
  F D D
  C D E F
  G G G
  G E E
  F D D
  C E G G
  (G C E)
  Repete
  D D D D
  D E F
  E E E E 
  E F G
  G E E
  F D D
  C E G G
  (G C E)
  Repete

• Lagarto Pintado

  Lagarto Pintado
  C
  G CM G
  E C
  A A A
  A G
  G CM G
  E C
  F E D
  C
  Repete