Projecto Integrado
Arquitecturas de Computadores (AC2005)
e
Programação Imperativa (PI2005)
Este documento descreve o único tema disponível para a realização do projecto integrado das disciplinas em epígrafe.
Os assuntos referentes à organização do trabalho e à realização, entrega e avaliação do projecto, são descritos em regulamento
próprio.
|
Índice
- Objectivos de formação e resultados de aprendizagem
- Tema: Processamento de Imagem
- Formato de Imagem PNM
- PBM: Portable BitMap? Format
- PGM: Portable GrayMap? Format
- PPM: Portable PixMap? Format
- Primeira fase (Fase 1)
- Segunda fase (Fase 2)
- Terceira fase (Fase 3)
- Pautas musicais
- Músicas populares
Objectivos de formação e resultados de aprendizagem
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
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
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
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
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
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)
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):
- Compactar P1 em P4
- Descompactar P4 em P1
- Binarizar P2 em P1
- Binarizar P3 em P1
- Descompactar e Binarizar P5 em P1
- Descompactar e Binarizar P6 em P1
Segunda fase (Fase 2)
Nesta fase, pretende-se que as/os estudantes executem as seguintes tarefas:
- 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.
- 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).
- Codificar os algoritmos propostos, comentando-os e documentando-os adequadamente (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.
- 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).
- 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).
- 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).
- 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).
- 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.
- 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)
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
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:
- O desenho da pauta fica ao teu critério: espessura das linhas, dimensões das notas, ...
- Uma pauta é constituída por cinco linhas horizontais espaçadas uniformemente. As notas colocam-se sobre as linhas ou nos espaços
entre elas.
- 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.
- 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 |
- 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
- 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