Trabalho de "Compressão e Codificação de Dados"

2004/2005

Este trabalho destina-se aos alunos de licenciatura e deve ser realizado por grupos de dois alunos.

O prazo de entrega coincide com o último dia da época de avaliação do 1º semestre.

A implementação pode ser levada a cabo em qualquer linguagem de programação à escolha. Embora se sugira MATLAB, qualquer aluno com alguma experiência não terá nenhuma dificuldade em realizar o trabalho com outra linguagem, tal como C, C++, Visual Basic, etc...

O relatório deverá incluir, para além dos resultados pedidos, a sua análise crítica bem como uma descrição dos algoritmos implementados. Com o relatório, o qual deve ser entregue impresso (não se aceitam entregas por “email”), deve ser entregue um CD ou “diskette” com todos os programas implementados.

O trabalho fica sujeito a uma possível discussão oral, para a qual serão convocados os grupos que o professor responsável da disciplina entender. Nesta discussão pode ser avaliada a total compreensão, por ambos os elementos do grupo, de todos os programas implementados e resultados obtidos.

A classificação obtida no trabalho tem peso 50% na nota final da disciplina.

1. Obtenha os ficheiros cadeiaDeMarkov.txt e texto.txt contidos nos arquivos http://www.lx.it.pt/~bioucas/ccd04/trabalho/textos.zip. O primeiro é constituído por uma sequência de símbolos do alfabeto A={a,b,c,d,e,f,g,h,i,j} gerada por uma cadeia de Markov; O segundo é um texto em português.

· Estime para a sequência cadeiaDeMarkov as probabilidades {p₁,..., p₁₀} de cada um dos símbolos do alfabeto A e a matriz de transição. Estime a taxa de entropia da cadeia de Markov e compare com a entropia de uma fonte independente e identicamente distribuída com probabilidade estimadas {p₁,..., p₁₀}.

· Implemente o algoritmo de compressão LZ77. O algoritmo deve aceitar como parâmetros a dimensão das janelas de procura e de codificação. Pode usar tripletos ou dupletos e “flags”. Pode ainda aplicar codificação entrópica à sequência gerada. Com o algoritmo obtido, comprima o ficheiro cadeiaDeMarkov.txt. Estude a taxa de compressão obtida em função das dimensões das janelas. Compare as taxas de compressão obtidas com a taxa de entropia estimada.

· Com o algoritmo desenvolvido na alínea anterior, comprima o ficheiro texto.txt para diferentes dimensões de janelas. Compare com os resultados obtidos com as taxas de compressão, sobre o mesmo texto, dos algoritmo ZIP ou PKZIP.

2. Obtenha os ficheiro de imagens contidos nos arquivos http://www.lx.it.pt/~bioucas/ccd04/trabalho/faces.zip. Este arquivo contêm um conjuntos de imagens com 40 faces humanas.

· Desenhe, implemente e teste um esquema de compressão preditiva em que o preditor de x(i,j) , i.e. elemento de imagem da linha i e coluna j, é uma função dos elementos de imagem x(i,j-1), x(i-1,j) e x(i-,j-1). Trate as fronteiras considerando que a primeira linha e coluna da imagem é constituída por zeros. A figura abaixo esquematiza o preditor descrito. O quantizador escalar deve ter em conta a estatística do erro de predição.

· Considere que o preditor é a média aritmética de x(i,j-1), x(i-1,j) e x(i-,j-1). Estime, para o conjunto de imagens obtido utilizando quantizadores de 1 a 8 bits, o erro médio quadrático das imagens depois de descodificadas.

· Proceda como na alínea anterior, mas agora com o preditor linear óptimo dado pela equação de Yule-Walker.