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

TRABALHO PRÁTICO 3

Bruno César Ribas e Silvio Boss

Resultado Final do RANK

A etapa final do rank foi executada dia 31 de outubro, com uma imagem de resolução de 2560x1920 pixels, a imagem original JPG possui 1.3MB e a versão PGM preta e branca possui 9.6MB.

Todas as execuções do rank e link para download das entradas acesse a página do RANK.

Gostaria de parabenizar todos os alunos que enviaram o trabalho para o sistema de rank.

Nome Input do Dia Tamanho Compactado Ratio Tempo Compactar Tempo Descompactar Ponto Extra
Raphael Ribas 9,6M ( 10022363 bytes) 272K (276205 bytes) .9724 1.83 1.15 - -
Eduardo Ribas 9,6M ( 10022363 bytes) 300K (306441 bytes) .9694 2.39 0.91 - -
Bruno Ribas 9,6M ( 10022363 bytes) 352K (356850 bytes) .9643 1.12 0.64 - -
William A. Lopes e Leonardo C. Sato 9,6M ( 10022363 bytes) 384K (390405 bytes) .9610 2.24 0.69 10
Douglas Ortlieb 9,6M ( 10022363 bytes) 420K (428330 bytes) .9572 0.63 0.70 10
Matheus e Maycon 9,6M ( 10022363 bytes) 488K (499339 bytes) .9501 1.28 0.67 10
gzip --best 9,6M ( 10022363 bytes) 512K (522122 bytes) .9479 7.49 0.05 - -
Renan Ribeiro 9,6M ( 10022363 bytes) 568K (581066 bytes) .9420 1.49 0.67 8
gzip --fast 9,6M ( 10022363 bytes) 924K (945725 bytes) .9056 0.14 0.07 - -
Douglas Marcal 9,6M ( 10022363 bytes) 1,1M (1105116 bytes) .8897 1.63 0.66 6
Dionei Michem 9,6M ( 10022363 bytes) 1,3M (1341369 bytes) .8661 0.26 0.48 6
JPG (original) - - 1,3M ( 1347977 bytes) .8655 - - - - - -
Fernanda Moreira 9,6M ( 10022363 bytes) 1,4M (1429474 bytes) .8573 1.13 0.93 4
PGM para JPG 9,6M ( 10022363 bytes) 2,0M ( 1996872 bytes) .8007 - - - - - -
Massucatto Andretta 9,6M ( 10022363 bytes) 2,0M (2069205 bytes) .7935 1.18 0.83 2
cadini stanga 9,6M ( 10022363 bytes) 2,0M (2092298 bytes) .7912 1.19 0.50 2
Dalmo Hollen 9,6M ( 10022363 bytes) 3,0M (3099400 bytes) .6907 0.88 0.75 2
Gil 9,6M ( 10022363 bytes) 2,3M (2359324 bytes) .7645 1.05 Descompactado Diferente do Original - -
Marcio 9,6M ( 10022363 bytes) 592K (603972 bytes) .9397 30.90 Descompactado Diferente do Original - -

Prólogo

Princesa Zelda está muito preocupada com a segurança e integridade dos moradores de seu reino. Em Hyrule muitos problemas já são conhecidos e para isso Link renasce em diferentes eras para resolver o problema, que geralmente é causado por Ganon. (uma possível cronologia dos fatos pode ser vista aqui)

Dessa vez o reino não corre um perigo catastrófico (e imediato) como de costume e por isso Zelda não pretende reencarnar Link nesse momento. Mas o problema ainda não deixa de ser grave. Moradores da Kakariko Village dizem ter avistado pequenos seres que dizem apenas uma palavra (alguns inclusive reportaram ter ouvido "Bulbasaur" de algo que parecia ser um sapo com uma planta em suas costas). Zoras dizem ter visto alguma construção com humanoides jamais vistos antes. E outros rumores podem ser vistos na internet como aqui

Antigos moradores de Dodongo's Cavern afirmam que esses novos seres não fazem parte do mundo que conhecemos e que o reino de Hyrule está em perigo caso esses seres continuem a aparecer em nosso ambiente.

Zelda baseada em todos esses rumores mandou instalar satélites que tiram muitas fotos de Hyrule em vários períodos do dia. Com essas imagens os peritos poderão analisar todo o perímetro de Hyrule e ainda dizer onde estão esses invasores. Porém alguns problemas já estão acontecendo com essas imagens.

O problema das imagens

A tecnologia atual em Hyrule possui alguns problemas e as imagens tiradas do satélite são em Preto e Branco, esse não é um problema ainda pois a equipe analisadora que vai se virar com ela.

O nosso problema é que os computadores de Hyrule não possuem uma grande capacidade de armazenamento e essa grande quantidade de fotos tiradas estão esgotando todo espaço que o castelo possuia.

Não temos tempo para esperar os discos chegarem, os novos invasores podem aproveitar dessa nossa falha para avançar e realizar novas construções sem nossa percepção. E por isso você foi contratado para compactar todo o acervo de fotos de Hyrule a fim de diminuir o espaço ocupado nos servidores.

Formato de Entrada

As imagens dos satélites 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:

Como os satélites guardam apenas imagens preto e branco o valor da cor mais clara sempre é 1.

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

  P2
  5 5
  1
  0 0 0 0 0
  0 0 0 0 0
  0 0 1 0 0
  0 0 0 0 0
  0 0 0 0 0

Compactação

Um dos engenheiros percebeu que várias imagens do satélite são muito parecidas com matrizes esparsas, e por isso aparentemente algum algoritmo que represente matriz esparsa em disco parece ser o suficiente para compactar as imagens, mas quanto mais compactar melhor.

O seu programa deverá receber pela entrada padrão uma imagem PGM preta e branca 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 < hyrule.pgm  > hyrule-compactado.cpgm
  time ./meuprograma < hyrule-compactado.cpgm > hyrule-descompactado.pgm

Onde "meuprograma" é o nome do executável do trabalho (pode ser outro nome qualquer), e "hyrule.pgm" é o arquivo que contém a foto do satélite. O arquivo "hyrule-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 'hyrule.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 'hyrule-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 hyrule-descompactado.pgm.

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

  diff hyrule.pgm hyrule-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)|sort -u|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 Preto e Branco basta executar o seguinte comando: 

  $ convert -monochrome -compress none imagemoriginal.jpg pretoebranco.pgm

Onde 'imagemoriginal.jpg' é alguma imagem que vocês queira converter (pode ser png, jpg, pdf, tiff, gif e muitos outros) e 'pretoebranco.pgm' é o nome que você quer salvar a sua imagem pgm ascii preto e branco, 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 compactado em .tar que o sistema copilará e executará.

Será avaliado o compress ratio, que contabiliza a diferença de tamanho do arquivo original para o arquivo e o tempo de execução.

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.

Curiosidades

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

---
Last Modified: Wed Oct 31 13:32:37 2012.