Lz77

Lz77
A codificação consiste em:
•  Ler para uma janela de tamanho predefinido uma sequência de dados a comprimir
•  Dividindo a janela em duas partes, buffer de histórico buffer de dados a codificar,
procurar no buffer de histórico, da direita para a esquerda, a maior sequência de símbolos
igual à sequência de símbolos no buffer de dados a codificar, que começa no primeiro
símbolo.
•  Inicialmente apenas o buffer de dados a comprimir irá ser preenchido com o fluxo de
dados original
•  A distância do ponteiro que aponta para o início dasequência de símbolos igual até ao
início do buffer de dados a codificar chama-se de deslocamento (offset)
•  O número de símbolos iguais (no buffer de histórico buffer de dados a codificar) chamase de comprimento (length)
•  Uma vez encontrada a sequência com maior numero de símbolos iguais, o codificador gera
um código triplo, (o, l, c), onde oé o deslocamento (offset), lé o comprimento (length) e c
(codeword) é símbolo que sucede a sequência de símbolos iguais. A razão para o envio do
terceiro elemento cé para o caso de não ser encontrada nenhuma sequência de símbolos
igual no buffer de histórico
•  Deslocar a janela no fluxo de dados com um deslocamento igual à quantidade de símbolos
codificados no passo anterior (l+ 1)
Algoritmo de codificação:
Carregar dados para o buffer (janela)
Enquanto (buffer de dados a codificar não está vazio)
Obter referência da sequência igual mais longa (o, l)
Se comprimento > 0
Ouput (deslocamento, comprimento, próximo símbolo)
Senão
Outout (0, 0, primeiro símbolo no buffer de dados a codificar)
Deslocar a janela (l+ 1) posições

Quantificação escalar uniforme

Na Era da informação na qual vivemos facilmente nos deparamos com situações que exigem armazenamento ou transferência de ficheiros mídia (audio, imagem, video). Uma vez que os dispositivos de armazenamento e/ou transferência têm  limites físicos (largura de banda, armazenamento, etc…) foram desenvolvidas técnicas e métodos de manipular a informação de formato mídia.

Uma das estratégias de maior sucesso é a compressão multimédia. Trata-se de um conjunto de métodos e técnicas que têm por objectivo diminuir o tamanho dos ficheiros. Um dos métodos chama-se quantificação escalar uniforme. Este método é parte constituinte de diversos algoritmos com perda (sem que o ser humano seja capaz de detectar a informação que está em falta). Usado de forma mais frequente em imagens, pode também ser utilizado em qualquer outro tipo de multimédia.

Neste método é necessário encontrar o valor máximo e mínimo por elemento de mídia(amostra,pixel, frame). O número de níveis de quantificação irá decidir a técnica a adoptar. Entre as várias técnicas, as mais simples são o quantificador midtread e quantificador midrise. As técnicas referidas distinguem-se na utilização do valor 0 (utilizado pelo midtread) e na simetria(midraise). Estas técnicas serão explicitadas de forma mais profunda no decorrer do artigo.

Transformada Move to Front

Move-to-front é um algoritmo que esta a receber uma considerável atenção nos últimos anos devido à sua simplicidade e eficácia em pré-processamento de dados para compressão.
Sendo um método cada vez mais usado em compressão sem perdas torna-se assim uma excelente área de estudo em técnicas de compressão de dados.

Move to front é um algoritmo de transformação que não compacta os dados, mas pode ajudar a reduzir a redundância em alguns dos casos.

Foi desenvolvido para aumentar a eficácia de técnicas de codificação de entropia e quando implementado eficientemente, a sua rapidez compensa a sua inclusão como mais um passo em algoritmos de compressão de dados.

Este método apresenta bons resultados, se o stream de dados de entrada tiver concentrações de símbolos iguais (propriedade da concentração), e no pior caso a sua performance é um pouco pior que a da codificação de Huffman, enquanto no seu melhor, a sua performance é significativamente superior.

 

O artigo completo sobre a Transformada Move to  Front irá ser publicado no Portal da Compressão Multimédia, em http://multimedia.ufp.pt , onde será disponibilizada uma applet java que ilustra o detalhadamente o funcionamento deste método de compressão.

Técnicas e Normas de Compressão de Voz – ADPCM

Nos dias de hoje encontra-se em todo lado no nosso dia-a-dia, desde aos nosso telemóveis passando pelos leitores de MP3, até a simples chamada de telemóvel/telefone que fazemos para contar as peripécias do nosso dia. Será mesmo essa mesma compressão de áudio digital que irá ser abordado no artigo. Mais propriamente  as técnicas e normas de compressão de voz usando a técnica ADPCM (Adpative Differential Pulse Code Modulation), que se trata de uma codificação preditiva.

A técnica ADPCM comprime amostra a amostra, e é preditiva porque assume que as amostras consecutivas de áudio digital são muito semelhantes, codificando apenas as diferenças entre essas amostras. Uma das implementações mais comuns é o algoritmo IMA que serve para a codificação do ADPCM.

O artigo completo sobre ADPCM irá ser publicado no Portal da Compressão Multimédia, em http://multimedia.ufp.pt , onde será disponibilizada uma aplicação javascript que ilustra o detalhadamente o funcionamento deste método de compressão.

DCT

A DCT é uma transformada relacionada com a transformada de Fourier, similar à Discrete Fourier Transform (DFT), mas que usa somente números reais. Existem cerca de 8 variantes standard da DCT, das quais 4 são bastante comuns. A mais comum e usado em tratamento de imagem é a type-II DCT, que é normalmente designada por “a DCT”; a sua inversa, a type-III DCT e designada por “iDCT”. O olho humano é mais sensível a mudanças no brilho do que a mudanças de cromaticidade. Por isso, os dados da imagem são primeiro divididos numa componente de luminância e dois de crominância, e os componentes de crominância são sub-amostrados relativamente à componente de luminância. A DCT reduz as componentes espaciais de altas-frequências da imagem, uma vez que o observador humano é mais sensível a erros de reconstrução de componentes de baixas frequências. Ou seja a DCT permite que os dados sejam representados em termos de coeficientes de frequência dos seus componentes[2][5][7]. Como quase todas as imagens são compostas por informações de baixa frequência, os componentes de uma imagem, de frequência alta podem ser descartados. Este algoritmo opera sobre os blocos de 8×8 pixels. Os coeficientes de baixa frequência ocorrem num dos cantos da grelha de 8×8, enquanto os de alta frequência no canto oposto da grelha. Na prática o DCT não faz qualquer operação de compressão aos dados, pois as operações que realiza são sem perda de informação, mas sim prepara o terreno para os passos seguintes.

Wavelet – Transformada de Haar

As Wavelets são ferramentas matemáticas para decompor funções hierarquicamente. De um modo geral, permitem descrever através de uma função, desde o detalhe mais genérico ao mais específico. Independentemente da função corresponder a uma imagem, uma curva, uma superfície, ou um sinal, as wavelets oferecem uma técnica elegante para representar os níveis de pormenor (Stollnitz, DeRose & Salesin, 1995).

No presente artigo aborda-se a transformada Haar, devido à sua simplicidade e ao fato de ser utilizada em variadas aplicações, em particular no processamento de imagens digitais. Apresenta-se ainda, a descrição dos algoritmos que permitem o cálculo dos coeficientes de wavelets (decomposição e reconstrução).

O artigo completo sobre Wavelets (transformada Haar) irá ser publicado no Portal da Compressão Multimédia, em http://multimedia.ufp.pt , onde será disponibilizada uma applet java que ilustra o detalhadamente o funcionamento deste método de compressão.

Golomb-Rice

O Golomb coding é uma técnica de codificação de entropia e como tal é um método de compressão sem perdas inventado por Solomon W. Golomb em 1960. Este é um código de comprimento variável como Huffman, contudo, é baseado no modelo de probabilidade dos valores. No final, será originado o divisor (parâmetro que contem a relação precisa entre tamanho e probabilidade).

Robert F. Rice inventou o Rice coding que utiliza como base o Golomb coding (logo Golomb-Rice). Este código é uma versão simples do Golomb coding onde o divisor em vez de ser um número inteiro (Golomb coding) é uma potência de 2. Isto permite que o código seja aplicado mais eficientemente na aritmética binária.

As aplicações mais relevantes do código Golomb-Rice são nos resíduos dos algoritmos de predição em imagens e em diversos codecs de áudio sem perda (entre eles o famoso ‘Apple Lossless Audio Codec’).

O artigo completo sobre Golomb-Rice irá ser publicado no Portal da Compressão Multimédia, em http://multimedia.ufp.pt , onde será disponibilizada uma applet java que ilustra o detalhadamente o funcionamento deste método de compressão.