Algoritmos e Estrutura de Dados I - AE22CP - 2012/2

TRABALHO PRÁTICO 3

Bruno César Ribas e Willian Zalewski

Prólogo

Parabéns! Finalmente você foi aceito para fazer parte do grupo do Rick, afinal após salvar a pele dele e do filho por diversas vezes você realmente merecia. Mas em uma conversa com Michonne, pude perceber que quem realmente avaliou a sua permanência no grupo foi o Carl.

Infelizmente não temos tempo para comemoração! O governador está solto em algum lugar que não sabemos e para evitar maiores problemas vamos colocar sensores para rastrear qualquer atividade.

Conseguimos encontrar diversas câmeras que funcionam com energia solar em um galpão abandonado, as câmeras são boas, embora consigam armazenar imagens apenas em tons de cinza, no formato PGM.

Precisamos armazenar todas as imagens para poder identificar potenciais ataques em nosso lar.

O problema das imagens

Recursos computacionais hoje em dia são extremamente raros e difíceis de conseguir, por isso você tem dar um jeito para armazenar todas essas imagens.

Daryl também pediu que você armazenasse todas as plantas de ambientes que já passamos para poder ter sempre em mãos quando necessário, afinal não sabemos onde nossa luta com o governador pode acontecer.

Glenn conseguiu apenas alguns pendrives de 128G para conseguir armazenar tudo e por isso você precisa compactar essas imagens para evitar o uso total dos nossos dispositivos.

Formato de Entrada

As imagens das câmeras são guardadas em formato PGM ascii.

O Formato PGM ascii em tons de cinza é bastante simples. O formato possui um cabeçalho de 3 linhas contendo, respectivamente, nas linhas:

As câmeras armazenam as imagens em tons de cinza com 8-bit de definição, então a nossa cor mais clara no máximo será 255.

Veja o exemplo de uma imagem que possui apenas um ponto branco no centro: 

  P2
  5 5
  255
  0 0 0 0 0
  0 0 0 0 0
  0 0 255 0 0
  0 0 0 0 0
  0 0 0 0 0

Compactação

O seu programa deverá receber pela entrada padrão uma imagem PGM em tons de cinza e deverá imprimir na saída padrão a imagem compactada.

A maneira de compactação fica a seu critério e o formato de saída também. A única exigência é que a imagem compactada comece com a linha 'cP2', que representa PGM ascii compactada.

Descompactação

Como qualquer programa que compacta algum conteúdo ele também deve descompactar e por isso sempre que seu programa receber na entrada padrão uma imagem compactada ele deve imprimir na saída padrão a imagem descompactada.

Um programa está certo quando a descompactação gera uma igual a imagem original.

Execução

A entrada e saída do programa devem ser feitas pela entrada e saída padrão ( como se estivesse lendo as informações pelo teclado)

exemplo de execução: 

  time ./meuprograma < mapa.pgm  > mapa-compactado.cpgm
  time ./meuprograma < mapa-compactado.cpgm > mapa-descompactado.pgm

Onde "meuprograma" é o nome do executável do trabalho (pode ser outro nome qualquer), e "mapa.pgm" é o arquivo que contém a foto da câmera, ou a planta de um ambiente. O arquivo "mapa-compactado.cpgm" é o arquivo que armazenará a saída do seu programa.

Quando executar o seu programa da forma indicada abaixo , o sinal '<' significa que o conteúdo do 'mapa.pgm' será passado ao programa como se ele estivesse sendo lido do teclado. E o sinal '>' significa que tudo que o seu programa imprimir na saída padrão será salvo em 'mapa-compactado.cpgm'. E 'time' é comando que contará o tempo de execução do seu programa.

A segunda execução significa que o programa receberá como entrada o arquivo compactado e imprimirá o mesmo descompactado, salvando em mapa-descompactado.pgm.

Para saber se o arquivo descompactado ficou igual ao original basta executar o comando: 

  diff mapa.pgm mapa-descompactado.pgm

Se o comando diff não imprimir nada na tela significa que os dois arquivos são iguais, caso contrário ele imprimirá as linhas com diferenças.

Como os compactadores estão específicos para imagem nem sempre o formato do arquivo descompactado pode ser igual ao original (pode ter diferença de linhas e colunas no arquivo mas com o mesmo conteúdo), por isso essa unicidade do compactador específico pode ser resolvida pelo comando: 

  (tr -d '\n' < original; echo; tr -d '\n' < descompactado)|uniq -d|wc -l

Onde 'original' é substituído pelo nome do arquivo de imagem original e o 'descompactado' pelo nome do arquivo gerado pelo processo da descompactação do seu programa. Se a resposta da execução for '1' significa que as duas imagens são identicas, se '2' é porque existe alguma diferença entre elas.

Exemplos de Entrada e Saída

Não se limite a esses exemplos, crie seus próprios exemplos!

Para converter alguma imagem em formato PGM ascii basta executar o seguinte comando: 

  $ convert -compress none imagemoriginal.jpg nova.pgm

Onde 'imagemoriginal.jpg' é alguma imagem que vocês queira converter (pode ser png, jpg, pdf, tiff, gif e muitos outros) e 'nova.pgm' é o nome que você quer salvar a sua imagem pgm ascii, o nome pode ser qualquer um mas tem que colocar a extensão pgm.

O comando convert vem pelo pacote 'imagemagick', no ambiente centralizado (boot pela rede) ele já está instalado, mas em sua casa basta instalar o pacote 'imagemagick', no ubuntu seria da seguinte forma pela linha de comando: 

  $ sudo apt-get install imagemagick

Ranking

O ranking será feito por disputas diárias. Para participar basta enviar o código que o sistema copilará e executará.

Para participar do Ranking o seu código deve funcionar em LINUX, recomendamos o uso do Ubuntu. Se o sistema não conseguir compilar seu programa apenas será avisado que não conseguiu e nada mais.

Prazos

Critérios da Correção

Curiosidades

A brincadeira com PGM também já foi feita AQUI e AQUI também

---
Last Modified: Mon Apr 15 23:59:42 2013.