1

Notas de Aula da Disciplina

Introdução à

Teoria da Informação

Leonardo Vidal Batista

2005

2

Conteúdo

Capítulo 1 Introdução ....................................................................................................................................................... 3 1.1 Codificação....................................................................................................................................................... 4 1.2 Compressão de dados ....................................................................................................................................... 6 1.3 Códigos de Prefixo ........................................................................................................................................... 7 1.4 Informação e Entropia .................................................................................................................................... 11 1.5 Modelagem ..................................................................................................................................................... 12

Capítulo 2 Codificadores Estatísticos ............................................................................................................................. 15 2.1 O Algoritmo de Huffman................................................................................................................................ 15 2.2 Codificação Aritmética ................................................................................................................................... 16 2.3 Codificação por Comprimento de Seqüência ................................................................................................. 19

Capítulo 3 Codificação Baseada em Dicionário ............................................................................................................. 22 3.1 O LZ77 ........................................................................................................................................................... 22 3.2 O LZ78 ........................................................................................................................................................... 25 3.3 O LZW............................................................................................................................................................ 27

Capítulo 4 Panorama dos Compressores sem Perdas ..................................................................................................... 32 Capítulo 5 Compressão com perdas Baseada no Paradigma TQC ................................................................................. 34

5.1 O Paradigma TQC .......................................................................................................................................... 34 5.2 O padrão JPEG ............................................................................................................................................... 42

3

Capítulo 1

INTRODUÇÃO

A teoria da informação é um ramo do conhecimento humano cujos objetivos envolvem a conceituação matemática do termo informação e a construção de modelos capazes de descrever os processos de comunicação. O artigo “A Mathematical Theory of Communications”, publicado em duas partes pelo matemático e engenheiro norte-americano Claude Shannon, no Bell Syst. Tech. Journal, em 1948, lançou as bases para a moderna teoria das comunicações. Qualquer processo de comunicação envolve transferência de informação entre dois ou mais pontos. De acordo com Claude Shannon,

“O problema fundamental das comunicações é o de reproduzir em um ponto, exatamente ou aproximadamente, uma mensagem selecionada em um outro ponto.”

A Figura 1 representa esquematicamente um sistema de comunicação genérico. Uma fonte de informação ou, simplesmente, fonte, é um elemento participante de um processo de comunicação que produz informação, enquanto que um destinatário é um elemento que recebe a informação produzida por uma fonte. Em uma conversação os participantes costumeiramente se revezam nos papéis de fonte e destinatário, e a informação circula na forma de palavras possivelmente selecionadas de um vocabulário conhecido por todo o grupo. Considere-se uma fonte S cujas saídas são seqüências de elementos selecionados de um conjunto A = {a0, a1, a2,...}. Este conjunto é o alfabeto da fonte e os seus elementos ai, i = 0, 1, 2... são denominados letras ou símbolos. Uma seqüência particular de símbolos gerada pela fonte é também denominada de mensagem. Vejamos alguns exemplos que ajudarão a esclarecer estes conceitos. Uma fonte de dígitos decimais tem um alfabeto A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} cujas letras são os dígitos decimais. A seqüência 59012688512238054667533321 é uma mensagem que poderia ser gerada por uma fonte de dígitos decimais. Analogamente, uma fonte binária tem um alfabeto A = {0, 1} cujas letras são os dígitos binários.

4

Fonte

De Informação

Transmissor

MensagemM

Canal Ruído

Receptor Destinatário

Da Informação

MensagemM~

Sinal s~

Sinal s

Figura 1. Diagrama esquemático de um sistema de comunicação genérico (Shannon, 1948)

Há diversas fontes reais que geram símbolos não numéricos. É o caso dos semáforos, que utilizam um alfabeto de três cores, vermelho, amarelo e verde. Uma mensagem gerada por um semáforo tradicional é uma sucessão temporal de cores, tais como verde amarelo vermelho verde amarelo vermelho. O transmissor transforma a mensagem em um sinal adequado à transmissão através do canal. Em um sistema de telefonia, por exemplo, o transmissor transforma a informação sonora produzida pela fonte em sinais elétricos que podem ser transmitidos por fios condutores. O canal é o meio usado para transmitir o sinal do transmissor para o receptor. Em sistema de comunicações real, o canal pode ser um fio de cobre, um cabo de fibra ótica, o espaço vazio, o ar, um disquete, um CD-ROM ou DVD, o HD de um computador, etc. O objetivo do receptor é a de reconstruir a mensagem gerada pela fonte a partir do sinal enviado pelo transmissor, enquanto que o destinatário representa o destino final da mensagem enviada pela fonte. Qualquer canal real está sujeito a interferências, ou ruído, de origens diversas. O ruído pode distorcer o sinal enviado pelo transmissor. Se estas distorções forem demasiadamente elevadas, podem ocorrer erros de comunicação, de forma que a mensagem M~ recebida pelo destinatário não será idêntica a mensagem M enviada pela fonte.

1.1 CODIFICAÇÃO

Muitas vezes é de interesse alterar a maneira como a informação gerada por uma fonte é representada. Para processamento por computador, por exemplo, seria necessário representar em binário as mensagens da fonte decimal e do semáforo acima descritos. O sistema Braille, por outro lado, representa dígitos, letras e palavras por intermédio de agrupamentos de pontos lisos ou em relevo gravados em uma superfície adequada. O ato de representar a informação em uma forma específica é denominado codificação.

5

Considere-se uma fonte de informação cujos símbolos correspondem a radiação luminosa nas cores azul, verde e vermelho. A informação de interesse originalmente produzida pela fonte de informação, portanto, consiste em radiação luminosa colorida. Para representar uma mensagem típica gerada por essa fonte em um texto em língua inglesa, por exemplo, pode ser mais conveniente representar os símbolos da fonte pelas palavras Red, Green e Blue ou, abreviadamente, pelas letras R, G e B. Neste último caso, uma mensagem típica poderia ser representada como GBRRRRGBBR. Se a informação produzida deve ser processada em um computador digital, em algum momento a representação dos símbolos precisará ser convertida para seqüências binárias. Assim, o vermelho pode ser representado por 00, o verde por 01 e o azul por 10, por exemplo. Há, obviamente, uma quantidade ilimitada de maneiras de representar a informação relevante, ou seja, são as cores emitidas pela fonte, utilizando dígitos decimais, letras, sons, sinais elétricos, etc. O contexto em que a informação será utilizada define as formas mais adequadas de representação. O processo de representação da informação produzida por uma fonte é denominado codificação. Uma palavra-código é uma representação específica para um símbolo ou para um agrupamento de símbolos. Um conjunto de palavras-código capaz de representar todas as saídas possíveis de uma fonte constitui um código para a fonte de informação. A Tabela 1 ilustra alguns códigos capazes de representar a saída de uma fonte de dígitos decimais:

Tabela 1. Alguns códigos para uma fonte de dígitos decimais

Decimal ASCII Binário 1 Binário 2 Binário 3 Octal Alfabético 0 3016 00002 002 1111112 008 a 1 3116 00012 012 1111102 018 f 2 3216 00102 102 1111012 028 k 3 3316 00112 11002 1111002 038 m 4 3416 01002 11012 11102 048 n 5 3516 01012 11102 11012 058 b 6 3616 01102 1111002 11002 068 z 7 3716 01112 1111012 102 078 x 8 3816 10002 1111102 012 108 p 9 3916 10012 1111112 002 118 s

Nos códigos da tabela acima, a cada possível símbolo de saída da fonte corresponde uma palavra-código diferente, e a cada palavra-código corresponde um símbolo diferente. Em geral, um código nem sempre é biunívoco. Um código para a fonte anterior, onde algumas palavras-código representam dois ou mais símbolos da fonte, está apresentado na Tabela 2. Codificadores são elementos (seres humanos, circuitos, programas, etc) que representam as mensagens geradas pela fonte empregando um código específico. Um decodificador é responsável por desfazer o mapeamento realizado por um codificador. Conforme será visto em breve, para que a decodificação tenha sucesso, algumas condições devem ser satisfeitas. Alguns códigos muito utilizados são: 1. Códigos de compressão: o codificador procura reduzir o número de bits necessários ä

representação binária da mensagem da fonte. 2. Códigos corretores de erros: o codificador representa a mensagem visando aumentar a

confiabilidade da transmissão da mesma através de um canal ruidoso. O código de Hamming para correção de erros e o código de Reed-Solomon, utilizados em CDs são exemplos bem conhecidos.

6

3. Códigos de criptografia: o codificador representa a mensagem visando dificultar a decodificação da mensagem original por observadores indesejados.

Tabela 2. Outro código para a fonte de dígitos decimais

Saída da Fonte Palavra-Código 000 00002 22 00012 0 00102 1 00112 2 01002 3 01012 4 01102 5 01112 6 10002 7 10012 8 10102 9 10112

1.2 COMPRESSÃO DE DADOS

Conforme visto anteriormente, o objetivo dos códigos de compressão é reduzir o número de bits necessário à representação binária da mensagem da fonte. O processo de codificação não altera a informação gerada, apenas encontra uma representação idealmente mais econômica para a informação. Para que o processo seja útil, deve ser possível construir um decodificador capaz de restaurar perfeitamente a representação original. Compressão de dados, por outro lado, é um processo mais genérico, contemplando a possibilidade de eliminação de informação considerada, sob algum critério, pouco importante ou irrelevante. Além de possivelmente eliminar informação pouco importante, um compressor também procura reduzir a representação da informação não descartada. Um processo de compressão que não envolve eliminação de informação é denominado de compressão sem perdas. Compressores sem perdas empregam exclusivamente algum tipo de código de compressão, e o processo de descompressão consiste em decodificar a mensagem original. Quando há eliminação de informação, a mensagem original não pode mais ser perfeitamente reconstruída. Por este motivo, esta modalidade é chamada de compressão com perdas. Neste caso, a descompressão constrói apenas uma aproximação para a mensagem original, exigindo a adoção de medidas que permitam aferir a distorção entre a mensagem original e a mensagem descomprimida. Algumas medidas de distorção populares serão estudadas nas etapas finais deste curso. Considere-se, por exemplo, um esquema de eliminação de informação que consiste em descartar os caracteres de um texto em posições múltiplas de 5 (o primeiro caractere ocupa a posição 0, o segundo a posição 1 e assim por diante). O trecho abaixo

probema undaenta da omuncaçã é rprodzir m umpont exaamene ouaproimadment umamensgem eleconad em utropont.

é o resultado da aplicação do esquema acima descrito sobre o texto

7

O problema fundamental da comunicação é reproduzir em um ponto exatamente ou aproximadamente uma mensagem selecionada em outro ponto

Com este mecanismo de descarte de informação, não há como garantir a reconstrução perfeita de um texto arbitrário. Após o descarte de informação pouco importante, um compressor tipicamente procura minimizar a representação da informação preservada, aplicando algum código de compressão. Deve estar claro que a etapa de eliminação da informação aumenta as chances de obter-se um grau de compressão mais elevado, e estas chances tendem a aumentar à medida que a quantidade de informação eliminada aumenta. A compressão com perdas procura um compromisso adequado entre dois objetivos normalmente conflitantes: o grau de compressão obtido e a distorção resultante. Na situação mais freqüente, as entradas de um compressor são mensagens já codificadas em binário. Nesses casos, a medida mais comumente usada para quantificar o grau de compressão é a chamada razão de compressão ou, abreviadamente, RC. Se o número de bits usados na representação da mensagem original (entrada do compressor) é n e o número de bits usados na representação da mensagem comprimida (saída do compressor) é m, a RC é definida como:

RC = n / m É também comum expressar a RC na forma (n / m):1. A taxa de bits ou, simplesmente, taxa, de uma mensagem é definida como a razão entre o número de bits usados na representação da mensagem e o número de elementos na mensagem original. Abreviaremos a taxa de bits por R (do inglês rate, taxa). Um texto com 10 caracteres codificados em ASCII utiliza 8x10 = 80 bits. A taxa é, portanto, R = 80/10 = 8. Se este texto é comprimido (com ou sem perdas) gerando uma seqüência de 40 bits, tem-se RC = 80/40 = 2, ou RC = 2:1, e R = 40/10 = 4.

1.3 CÓDIGOS DE PREFIXO

Dado o código binário para vogais apresentado na

8

Tabela 3, a mensagem <iaaoa> seria codificada como <110111100111>. Percorrendo-se a mensagem codificada da esquerda para a direita, pode-se decodificá-la, por exemplo, como <iaaoa> ou <auaoa>. Diz-se que o código não é unicamente decodificável. Isto acontece porque a palavra-código que representa o elemento <a> (11) é também o início da palavra-código que representa o elemento <i> (110). Diz-se que a palavra-código 11 é um prefixo da palavra-código 110.

9

Tabela 3. Um código binário para as vogais

Vogal Palavra-Código a 11 e 000 i 110 o 001 u 011

Considere-se um código C com palavras-código {c0, c1, ..., cM-1}. Se, para i ≠ j, ci não é um prefixo de cj, com i, j = 0, 1,... , M – 1, diz-se que C é um código de prefixo. Códigos de prefixo permitem uma decodificação simples e sem ambigüidades. O código apresentado na Tabela 4 é um código de prefixo:

Tabela 4. Um código de prefixo

Vogal Palavra-Código a 102 e 0002 i 1102 o 0012 u 0112

Com este código, qualquer cadeia de palavras-código pode ser univocamente decodificada percorrendo-se a cadeia da esquerda para a direita e substituindo-se cada palavra-código encontrada no processo pela vogal correspondente. O código ASCII utiliza oito bits para representar 256 caracteres diferentes. Assim, uma cadeia qualquer com n caracteres ocupa 8n bits quando codificada em ASCII. Uma mensagem com 854 caracteres codificados em ASCII exigirá 854*8 = 6832 bits. Este esquema é simples, mas pode ser pouco eficiente quanto à quantidade de bits utilizados. Considere-se, por exemplo, que a mensagem é composta por 400 ocorrências do valor 32, 200 do 103 e uma única ocorrência de cada um dos demais valores. Um compressor poderia aproveitar a desigualdade no número de ocorrências de cada caractere, e codificá-los de acordo com a Tabela 5.

Tabela 5. Um código de compressão para caracteres ASCII

Caractere Palavra-Código 32 12 103 012 0 0000000000 1 0000000001 ...

255 0011111101

O comprimento L, em bits, da cadeia de saída do compressor seria

L = 1 x 400 + 2 x 200 + 10 x 254 = 3340 bits,

o que resulta em RC = 2,04:1, PC = 51,11% e R = 3,91 bits/símbolo.

10

Pode-se construir códigos de prefixo para qualquer alfabeto colocando-se os símbolos da fonte como folhas de uma árvore binária, e atribuindo-se um bit ‘0’ a cada filho esquerdo, e ‘1’ a cada filho direito, ou vice-versa. A palavra-código para qualquer símbolo da fonte é obtida concatenando-se os bits encontrados no caminho que leva da raiz à folha correspondente ao símbolo. Como exemplo, vamos construir um código de prefixo para uma fonte cujos símbolos são as 14 primeiras letras (de A até N) do alfabeto inglês. Uma possível árvore e o código de prefixo correspondente estão apresentados na Figura 2 e na Tabela 6, respectivamente.

Figura 2. Uma árvore binária para construção de um código de prefixo

Tabela 6. Código de prefixo correspondente à árvore da Figura 3

Letra Palavra-Código A 0012 B 00002 C 011012 D 01112 E 01100102 F 01100112 G 112 H 10102 I 1002 J 0102 K 000102 L 10112 M 0110002 N 000112

11

1.4 INFORMAÇÃO E ENTROPIA

Seja S uma fonte com alfabeto A = {a0 , a1 , ... aM-1}. Um elemento x gerado por S pode ser considerado uma variável aleatória que assume o valor ai com probabilidade P(x = ai), i = 0, 1,..., M-1. Define-se a auto-informação, I(ai), associada ao símbolo ai como

I(ai) = )(

1log2iaxP =

bits

Se x1x2. . .xN-1 são os elementos gerados por S, a entropia da fonte é definida como

NNG

NSH 1lim)(

∞→= bits/símbolo

onde

),(log),(1

0

1

0

1

01102110

0 1 1

110110,...,,...,...∑∑ ∑

−

=

−

=

−

=−−

−

−−======= −

M

i

M

i

M

iiNiiiNiiN

N

NNaxaxaxPaxaxaxPG

Se as variáveis aleatórias que constituem a mensagem são independentes e identicamente distribuídas (IID), a equação pode ser simplificada para expressar a entropia de ordem 1 de S:

∑−

=

==−=1

02 )(log)()(

M

iii axPaxPSH bits /símbolo

Shannon mostrou que é possível codificar sem perdas a saída de uma fonte qualquer com

taxa arbitrariamente próxima à entropia, mas não inferior a ela. Assim, pode-se usar a entropia para avaliar a eficiência da codificação efetuada, sendo o código ótimo aquele cujo comprimento médio é igual à entropia. Mais ainda, para atingir este comprimento médio mínimo, cada símbolo deve ser representado com um número de bits igual à sua auto-informação. Se um símbolo a tem probabilidade de ocorrência P(a) = 0,95, sua auto-informação é de 0,074, e assim uma codificação ótima deverá atribuir a ele exatamente 0,074 bit. O problema de como construir tal código foi resolvido com a introdução da codificação aritmética, que será apresentada no próximo capítulo.

Retornando a um exemplo apresentado na Seção 1.3, considere-se uma mensagem composta por 854 caracteres codificados em ASCII, contendo 400 ocorrências do valor 32, 200 do 103 e uma única ocorrência de cada um dos demais valores. A probabilidade de ocorrência de cada caractere pode ser estimada pela sua freqüência relativa. Por exemplo, P(x = 32) = 400/854 e P(x = 0) = 1/854. As probabilidades assim estimadas permitem calcular uma estimativa para a entropia da fonte:

90,3)854

12log.1.254

854200

2log.200854400

2log.400(854

1=++−=H bits/símbolo

Como, no exemplo citado, R = 3,91 bits/símbolo, o código se aproxima muito do melhor

resultado possível.

12

1.5 MODELAGEM

Vimos na última seção anterior que a entropia fornece o limite mínimo para o número médio de bits necessários para a codificação de uma mensagem, e que para atingir este limite deve-se atribuir a cada símbolo um número de bits igual à sua auto-informação. Como o número ótimo de bits em cada palavra-código é, em geral, não inteiro, esquemas de codificação restritos a palavras-código de comprimento inteiro nem sempre são capazes de atingir uma taxa de bits igual à entropia. Estes codificadores, quando bem projetados, procuram gerar palavras-código com comprimentos próximos do ótimo.

A auto-informação associada a um símbolo, por sua vez, depende da probabilidade de ocorrência do símbolo, de forma que a construção de um codificador ótimo exige que se faça uma estimativa das probabilidades de todos os símbolos do alfabeto da fonte. A codificação de compressão, portanto, pode ser vista como um processo de duas etapas, a primeira envolvendo a modelagem estatística da fonte e segunda consistindo na construção de um codificador a partir do modelo obtido. Em alguns casos, uma etapa de modelagem determinística é também incluída, como será visto adiante. A separação do processo em modelagem e codificação foi um dos grandes avanços na teoria e prática da compressão de dados nas últimas décadas, permitindo tratar uma enorme variedade de compressores como a associação entre alguns poucos modelos e codificadores básicos diferentes. As próximas seções discutem alguns modelos estatísticos e a técnica de modelagem determinística denominada predição.

1.5.1 Modelagem Estatística

O conceito de entropia e, conseqüentemente, de código ótimo, está diretamente relacionado com a definição das probabilidades associadas aos símbolos gerados pela fonte, bem como com as considerações a respeito de dependência estatística. Em outras palavras, a entropia é calculada a partir da definição de um modelo estatístico para a fonte de informação. Na verdade, qualquer processo de codificação está associado a um modelo subjacente, que pode ou não ser explicitamente definido. Por exemplo, a atribuição de um número fixo de bits a cada um dos elementos de uma seqüência, como no código ASCII de oito bits, é ótimo para fontes que seguem um modelo IID com a mesma probabilidade de ocorrência para todos os símbolos do alfabeto.

Diz-se que um modelo que captura mais precisamente as características reais da fonte “reduz sua entropia”, aumentando as oportunidades de compressão. Por exemplo, se os elementos de uma mensagem são estatisticamente dependentes, a entropia associada a um modelo que expresse este comportamento será menor do que aquela associada a um modelo IID.

Enquanto a codificação ótima é um problema já solucionado, a modelagem permanece um ativo campo de pesquisa. A definição de um modelo que leve à menor entropia para uma fonte genérica é um problema sem solução definida, e ganhos de compressão podem sempre ser obtidos com a construção de modelos mais precisos.

Considere-se uma fonte com alfabeto A = {ao, a1,..., aM-1}. Um modelo estatístico simples consiste em assumir que os elementos gerados pela fonte são independentes e assumem o valor ai com probabilidade P(x = ai), i = 0, 1,..., M-1. Quando a suposição de independência não é satisfatória, os modelos de Markov estão entre os mais comumente usados para representar a relação entre os símbolos. Uma mensagem segue um modelo de Markov de k-ésima ordem se a distribuição de probabilidades de um elemento depende unicamente dos k símbolos que o antecedem. É necessário, portanto, estimar as probabilidades P(xn = ai | xn-1, xn-2,..., xn-k,), i = 0, 1,..., M-1. Os k símbolos precedentes constituem o contexto a partir do qual a probabilidade de ocorrência do próximo elemento é estimada, e por este motivo os modelos de Markov de k-ésima ordem são também conhecidos como modelos de contexto finito. Note-se que o IID é um modelo de Markov de ordem zero.

13

Se uma fonte gera símbolos que dependem estatisticamente dos valores presentes em um contexto C de tamanho L, um modelo de Markov de ordem k, com k ≤ L, é capaz de representar com maior precisão as características da fonte do que um modelo de ordem k-1 e, conseqüentemente, conduz a uma maior redução na entropia. Seria natural empregar modelos de ordem elevada para obter boas compressões, mas alguns problemas práticos limitam a aplicabilidade da idéia. Com um modelo de ordem k e um alfabeto de tamanho M, tem-se Mk possíveis contextos, ou seja, o número de contextos diferentes cresce exponencialmente com a ordem do modelo. Se M = 256 e k = 5, haveria aproximadamente um trilhão de contextos diversos. Um número elevado de contextos leva a uma série de problemas práticos, relacionados aos requisitos de memória e ao cálculo das estimativas e transmissão para o decodificador das probabilidades condicionais. Por este motivo, os modelos de Markov de ordem zero e de primeira ordem são os mais utilizados em situações reais.

Qualquer que sejam as considerações a respeito da dependência estatística entre elementos sucessivos gerados pela fonte, as probabilidades de ocorrência dos símbolos podem ser estimadas de três formas: 1. Estimativa não-adaptativa ou estática: utiliza-se um conjunto fixo de probabilidades pré-

estimadas para uma determinada classe de fontes (por exemplo, arquivos de texto ASCII em inglês). O processo de codificação é simples, mas a eficiência de compressão pode ser baixa quando a distribuição de probabilidades dos símbolos de uma mensagem se desviar significativamente do modelo pré-estabelecido.

2. Estimativa semi-adaptativa: realiza-se uma verificação preliminar na mensagem, estimando-se a probabilidade de cada símbolo pela freqüência relativa observada, e usa-se a distribuição de probabilidades assim obtida para a criação do código. Esta abordagem apresenta pelo menos dois inconvenientes: • É necessário passar ao decodificador informações que possibilitem a construção do mesmo

código usado na codificação. • É necessário varrer previamente toda a mensagem para estimar as probabilidades, o que

torna a abordagem inadequada para codificação em tempo real. 3. Estimativa adaptativa: parte-se de uma estimativa inicial semi-adaptativa ou não-adaptativa, e

cada símbolo codificado é usado para atualizar o modelo. Assim, há a possibilidade de que, a cada símbolo codificado, todas as palavras códigos se alterem para refletir as mudanças no modelo, o que pode ter um custo computacional elevado.

1.5.2 Predição

Como alternativa ao uso de modelos estatísticos complexos para fontes com elementos dependentes, pode-se procurar aproximar o comportamento da fonte através de um modelo determinístico, cujo objetivo é proporcionar uma aproximação precisa para o valor de um elemento através da aplicação de uma função determinística f(C) a um contexto C formado pelos valores reais de outros elementos da mensagem. A função f é um mapa entre contextos e aproximações. Como o mapa é fixo e conhecido pelo codificador e pelo decodificador, apenas os erros entre os valores reais dos elementos e as aproximações precisam ser codificados. Se o esquema operar satisfatoriamente, a entropia dos erros será menor do que a da mensagem original.

Se o contexto empregado para construir a aproximação para o valor de um dado elemento contém apenas símbolos que o antecedem na mensagem, o processo é chamado de predição. Por outro lado, se há símbolos antecedentes e subseqüentes no contexto, tem-se uma interpolação.

Um preditor linear de ordem k calcula as aproximações a partir de uma combinação linear dos símbolos em um contexto composto pelos k símbolos prévios:

14

∑=

−=k

jjiji xax

1

~

onde ix~ é a aproximação para xi, e aj, j = 1, 2, ..., k, são valores (de ponto flutuante) que definem os pesos associados a cada símbolo prévio no cálculo da aproximação. Esses pesos podem ser pré-fixados ou calculados de maneira a minimizar o erro médio quadrático entre as predições e os valores reais. Os preditores lineares mais utilizados na prática são de ordem k ≤ 2.

A predição tende a gerar seqüências de erros mais descorrelacionados que os elementos da seqüência original, aumentando a eficiência da aplicação de modelos estatísticos simples, tais como o IID.

15

Capítulo 2

CODIFICADORES ESTATÍSTICOS

2.1 O ALGORITMO DE HUFFMAN

Examinemos o problema de construir um código de prefixo C com o objetivo de comprimir eficientemente uma mensagem gerada por uma fonte com alfabeto A = {a0, a1, ..., aJ-1}, onde o símbolo aj aparece nj vezes. Se a i-ésima palavra-código possui lj bits, com lj inteiro, devemos procurar minimizar o comprimento total em bits, L = n0.l0 + n1.l1 + ... + nJ-1.lJ-1 da mensagem codificada. A diferença entre o comprimento médio dos elementos na seqüência codificada e a entropia expressa a redundância do código.

O algoritmo de Huffman representa uma maneira sistemática de construir códigos de prefixo que efetivamente minimize L. Por este motivo, o código de Huffman é denominado código de redundância mínima. Observe-se que foi colocada na formulação do problema a restrição de utilização de palavras-códigos com um número inteiro de bits, e este foi o problema específico solucionado por Huffman. Códigos sem essa restrição podem apresentar redundância menor que o código de Huffman.

O algoritmo de codificação de Huffman associa uma árvore ponderada a cada símbolo do alfabeto da fonte de informação. Inicialmente, cada árvore possui um único nó, com peso igual à probabilidade de ocorrência do símbolo a ela associado. A cada iteração do algoritmo, as duas árvores de menor peso são substituídas por uma nova árvore cujo peso é a soma dos pesos das primeiras. A árvore de menor peso se torna a subárvore esquerda e a outra se torna a subárvore direita da nova árvore. Na ordenação dos pesos, empates são resolvidos por qualquer regra sistemática. O procedimento pára quando resta apenas uma única árvore. A palavra-código para qualquer letra é obtida percorrendo-se esta árvore desde a raiz até a folha correspondente à letra em questão, registrando 0 para cada ramo esquerdo e 1 para cada ramo direito.

O código de Huffman é o melhor código de comprimento inteiro possível, e o comprimento médio de suas palavras-código normalmente se aproxima muito da entropia da mensagem.

16

O algoritmo de Huffman pode ser usado em conjunção com os modelos semi-adaptativos, não-adaptativos e adaptativos descritos no capítulo anterior. A construção do código para os dois primeiros casos é trivial e não será discutida aqui. No terceiro caso, o mecanismo de adaptação do modelo permite muitas variações. Duas possibilidades são apresentadas a seguir.

2.1.1 Huffman Adaptativo de Incremento

O primeiro símbolo é codificado de acordo com uma estimativa inicial não-adaptativa da probabilidade de ocorrência dos símbolos. Por exemplo, pode-se considerar, como estimativa inicial, que todos os símbolos do alfabeto da fonte aparecem uma única vez na mensagem. Cada novo símbolo codificado e toda a sua ascendência na árvore de Huffman têm seu contador de ocorrências incrementado. Se for o caso, a árvore deve ser reconstruída para refletir a mudança.

2.1.2 Huffman Adaptativo de Decremento

O primeiro símbolo é codificado de acordo com uma estimativa inicial semi-adaptativa das probabilidades de ocorrência dos símbolos. Cada novo símbolo codificado, e toda a sua ascendência na árvore de Huffman, tem seu contador de ocorrências decrementado, corrigindo sua probabilidade de ocorrência a partir daquele ponto. Se for o caso, a árvore deve ser reconstruída para refletir a mudança.

2.1.3 Exercícios

1. Implemente um codificador de Huffman não-adaptativo para textos ASCII em língua portuguesa. Use textos obtidos na Biblioteca Virtual do Estudante Brasileiro (http://www.bibvirt.futuro.usp.br/index.html), com um total de no mínimo 2 Mbytes, para estimar as probabilidades dos símbolos.

2. Implemente um codificador de Huffman não-adaptativo para textos ASCII em língua inglesa. Use textos obtidos do Projeto Gutenberg (http://www.promo.net/pg/), com um total de no mínimo 2 Mbytes, para estimar as probabilidades dos símbolos.

3. Implemente o codificador de Huffman semi-adaptativo, adaptativo de incremento e de decremento.

4. Aplique todos os codificadores desenvolvidos a um conjunto único de textos (no mínimo 4 Mbytes, sendo metade relativa a textos em língua portuguesa e metade relativa a textos em língua inglesa) que não tenham sido usados nas estimativas das versões não-adaptativas. Calcule as RCs e comente os resultados. Observe-se que o tamanho em bytes do arquivo codificado deve incluir qualquer informação adicional necessária à decodificação.

2.2 CODIFICAÇÃO ARITMÉTICA

Na codificação aritmética, a seqüência original é codificada como um único número de ponto flutuante no intervalo [0, 1), que pode ser unicamente decodificado de forma a restaurar a seqüência original. Não há, portanto, atribuição de uma palavra-código a cada símbolo da fonte, como no método de Huffman.

Na codificação aritmética, a cada símbolo é atribuída uma fatia do intervalo [0, 1), com extensão igual à probabilidade de ocorrência do símbolo. Não há superposição entre as fatias. Normalmente, o símbolo com maior probabilidade recebe a primeira fatia, o símbolo com a segunda

17

maior probabilidade recebe a segunda fatia, e assim por diante. Na ordenação, empates são resolvidos por qualquer regra sistemática. As fatias para os símbolos da mensagem “assassinar” poderiam ser:

Símbolo Probabilidade Faixa

s 4/10 [0, 0.4) a 3/10 [0.4, 0.7) i 1/10 [0.7, 0.8) n 1/10 [0.8, 0.9) r 1/10 [0.9, 1.0)

Representemos por li e hi os limites inferior e superior, respectivamente, de um intervalo

fechado à esquerda e aberto à direita, inicialmente definido como [0, 1). A codificação aritmética utiliza os limites do intervalo associado ao símbolo na posição i da mensagem para atualizar li e hi: li = li-1 + ri-1 . lsi hi = li-1 + ri-1 . hsi onde lsi: limite inferior do intervalo associado ao símbolo na posição i hsi: : limite superior do intervalo associado ao símbolo na posição i ri = hi - li

Para a nossa mensagem, o processo seria: Símbolo li hi ri 0.0 1.0 1.0 a 0.0 + 1.0 * 0.4 = 0.4 0.0 + 1.0 * 0.7 = 0.7 0.3 s 0.4 + 0.3 * 0.0 = 0.4 0.4 + 0.3 * 0.4 = 0.52 0.12 s 0.4 + 0.12 * 0.0 = 0.4 0.4 + 0.12 * 0.4=0.448 0.048 a 0.4+0.048*0.4=0.4192 0.4+0.048*0.7=0.4336 0.0144 s 0.4192 0.42496 0.00576 s 0.4192 0.421504 0.002304 i 0.4208128 0.4210432 0.0002304 n 0.42099712 0.42102016 0.00002304 a 0.421006336 0.421013248 0.000006912 r 0.4210125568 0.421013248

A mensagem codificada pode ser qualquer número, com a menor quantidade possível de

casas decimais, no intervalo final, ou seja, em [0.4210125568, 0.421013248), tal como 0.421013. Na decodificação, deve-se verificar em que faixa o número de saída se encontra,

decodificando assim o símbolo correspondente a ela, retirar deste número o efeito do símbolo recém-decodificado, e repetir o processo até a decodificação da mensagem completa.

Para encontrar uma forma de retirar o efeito do símbolo decodificado do número, vamos considerá-lo igual ao low final e analisar o processo de codificação do início da mensagem do exemplo anterior, “assassinar” com mais detalhes. Se l(a), h(a), r(a), l(s), h(s), e r(s) denotam respectivamente o limite inferior, o limite superior e o comprimento do intervalo associado ao símbolo “a” e “s”, temos: Símbolo li hi ri

18

a l(a) h(a) r(a) s l(a) + r(a).l(s) l(a) + r(a).h(s) r(a).r(s) s l(a) + r(a).l(s) + r(a).r(s).l(s) l(a)+r(a).l(s)+ r(a).r(s).r(s) r(a).r(s).r(s) a ... ... ...

Observe-se que o efeito do símbolo inicial, “a”, sobre o intervalo [li, hi) se propaga por todo o processo. Este efeito fica explícito no valor l(a), que é a primeira parcela do somatório que constitui as expressões de li e hi, e no valor r(a), que multiplica todos as demais parcelas do somatório. Dado o número final que representa a mensagem codificada, o efeito do símbolo inicial poderia ser retirado subtraindo-se l(a) dos limites do intervalo final e dividindo o resultado por r(a).

De maneira geral, dado um valor v obtido pelo processo de codificação aritmética, a operação de retirada do efeito do i-ésimo símbolo, si, recém-decodificado é assim realizada:

v = (v – lsi) / rsi

A tabela a seguir ilustra o processo de decodificação da mensagem codificada com valor 0.421013.

Número Símbolo lsi rsi

0.421013 a 0.4 0.3 0.070043333 s 0.0 0.4 0.175108333 s 0.0 0.4 0.437770833 a 0.4 0.3 0.125902777 s 0.0 0.4 0.314756944 s 0.0 0.4 0.786892361 i 0.7 0.1 0.86892361 n 0.8 0.1 0.689236108 a 0.4 0.3 0.96412036 r 0.9 0.1

Observe-se que:

• li não decresce com i

Prova: li = li-1 + ri-1 . lsi, com ri-1 . lsi ≥ 0

• hi não cresce com i

Prova: hi = li-1 + ri-1 . hsi hi = hi-1 + li-1 - hi-1 + ri-1 . hsi hi = hi-1 - ri-1 + ri-1 . hsi hi = hi-1 - ri-1 . (1 – hsi) com ri-1 . (1 - hsi) ≥ 0

(Observe-se que hsi pode ser igual a 1) • hi é sempre maior do que li

Prova: hi - li = ri-1 . (hsi – lsi) com r0 = 1 e (hsi – lsi) > 0.

19

Conseqüentemente, • A saída será sempre um número no intervalo [0, 1). Assim, não precisamos escrever na saída a

parte inteira do número, pois esta será sempre zero e pode ficar implícita. A saída do nosso exemplo poderia ser, então, 421013.

• Quando hi e li coincidem na 1a casa decimal, esta não muda mais, e o dígito correspondente já pode ser enviado para a saída. Após a coincidência na 1a casa decimal, a mesma observação vale para a 2a casa, e assim sucessivamente. Isto sugere uma pequena mudança no algoritmo básico de codificação: após uma coincidência na 1a casa decimal de li e hi, multiplique-os por 10, jogando para a saída a parte inteira. Com esta mudança, teríamos:

Símbolo low high range saída 0.0 1.0 1.0 A 0.4 0.7 0.3 s 0.4 0.52 0.12 S 0.4

0.0 0.448 0.48

0.048 0.48

4

a 0.192 0.336 0.144 s 0.192 0.2496 0.0576 s 0.192 0.21504 0.02304 i 0.208128

0.08128 0.210432 0.10432

0.002304 0.02304

2

n 0.099712 0.102016 0.002304 a 0.1006336

0.06336 0.1013248 0.13248

0.0006912 0.06912

10

r 0.125568 0.25568

0.13248 0.3248

0.006912 0.06912

1 3

Observe-se que o resultado seria exatamente o mesmo se aplicássemos o fator multiplicativo

10000000 (107) a todos os valores, e os considerássemos desde o princípio como inteiros com sete dígitos.

Na prática, li, hi e ri devem ter um tamanho limitado, o que pode trazer vários problemas. Há mecanismos para contornar a limitação de precisão dos computadores, permitindo a implementação prática da codificação aritmética.

2.3 CODIFICAÇÃO POR COMPRIMENTO DE SEQÜÊNCIA

Os códigos de prefixo apresentam fraco desempenho quando a fonte gera um símbolo com probabilidade muito superior a 0,5. Um símbolo s com probabilidade 0,95, por exemplo, apresenta uma I(s) = 0,074 bit. Para codificação ótima, s deveria ser codificado com 0,074 bit, mas um codificador de Huffman atribuirá a ele uma palavra-código com 1 bit. Isto significa que praticamente 1 bit será desperdiçado, com relação à codificação ótima, em cada uma das freqüentes ocorrências de s.

A codificação por comprimento de seqüência (run-length encoding, ou RLE) atenua este problema, sendo comumente utilizado em associação com algum codificador estatístico. O termo RLE denota uma família de esquemas que fundamentalmente substituem seqüências de elementos repetidos pela informação sobre o número de elementos e o valor que se repete. O RLE tende a reduzir o número de elementos na mensagem e a probabilidade de ocorrência dos símbolos mais freqüentes, podendo constituir um compressor autônomo ou uma das etapas de métodos mais elaborados. Para ilustrar os conceitos que se seguem, consideremos uma mensagem-exemplo cujos

20

elementos sejam bytes. A fim de facilitar a visualização, os valores decimais dos elementos (binários) da mensagem-exemplo serão apresentados:

10 3 3 125 8 8 8 0 0 0 0 0 1 0 0

Considere-se agora um codificador que substitua agrupamentos de C (3 ≤ C ≤ 256) bytes consecutivos de valor igual a B na mensagem pelo par de bytes (C, B). A mensagem-exemplo codificada seria:

10 3 3 125 3 8 5 0 1 0 0

Não é possível prover um decodificador que restaure total ou parcialmente a mensagem original, pois não há como saber se um valor maior ou igual a três na mensagem codificada representa um valor de C ou de B.

Um codificador mais inteligente poderia substituir seqüências de três ou mais bytes iguais pela tríade (E, C, B), onde E é um byte que não existe no alfabeto da fonte (byte de escape), e C e B são os mesmos que no codificador anterior. Agora, apenas os valores dos bytes que se seguem a E na saída do codificador serão interpretados como valores de C. Com o conhecimento do valor de E, a saída da fonte pode ser facilmente recuperada. Este codificador só pode ser usado para fontes cujo alfabeto não inclua todos os possíveis bytes. Se o valor 255 não pertence ao alfabeto da fonte hipotética que gerou a mensagem-exemplo, esta seria codificada como:

10 3 3 125 255 3 8 255 5 0 1 0 0

O esquema sem perdas descrito obterá RCs elevadas se a fonte produzir freqüentemente longas seqüências de bytes repetidos, o que é comum em imagens com um número reduzido de cores).

A necessidade de empregar um símbolo de escape pode ser eliminada com um ligeiro acréscimo na complexidade do codificador. O processo se inicia com a escolha de um limiar L. Quando os elementos da mensagem são bytes, 0 ≤ L < 253, e o método obedece às regras abaixo: 1. Seqüências de C bytes consecutivos de valor B, com 2 ≤ C ≤ 255 - L, são substituídas pelo par

de bytes (C + L, B) 2. Bytes isolados de valor B > L são substituídos pelo par de bytes (L + 1, B) 3. Bytes isolados de valor B ≤ L não são alterados 4. Seqüências de C bytes consecutivos de valor B, com C > 255-L, são particionadas em

seqüências de comprimento 255-L, que são tratadas de acordo com a regra 1. Se, após o particionamento, sobrar uma última seqüência de comprimento no intervalo [1, 255 – L], esta será codificada de acordo com as regras 1, 2 e 3 .

Assim, na mensagem codificada:

• Um byte com valor B ≤ L representa um byte da mensagem original; • Um byte com valor B > L representa um comprimento de seqüência acrescido de L, ou seja,

representa C+L, e a ele segue-se o valor B dos bytes da seqüência. O formato gráfico PCX utiliza o esquema descrito acima, com um limiar L = 192. Por este

motivo, designaremos o método de RLE-PCX.

2.3.1 Exercícios

1. Interprete a operação do RLE-PCX para L = 0 e L = 253 2. Como o RLE-PCX seria alterada para operar com seqüências de palavras de dois bytes?

21

3. Implemente o RLE-PCX, com parâmetro L variável. Trace um gráfico de RC x L para todos os valores permitidos de L. Procure explicar o comportamento da curva gerada.

22

Capítulo 3

CODIFICAÇÃO BASEADA EM DICIONÁRIO

As técnicas de compactação baseadas em dicionários substituem seqüências de símbolos, aqui denominadas frases, por uma indicação da sua localização em um repositório de frases denominado dicionário. Praticamente todos os métodos baseados em dicionário são uma variação do LZ77, apresentado a seguir.

3.1 O LZ77

O algoritmo LZ77 foi apresentado em 1977 por Jacob Ziv e Abraham Lempel. Conceitualmente, sua estrutura principal consiste em uma janela que desliza sobre a seqüência a ser codificada. Esta janela compõe-se de duas partes: a primeira, denominada área de procura, contém os últimos símbolos codificados, e é utilizada como dicionário; a segunda contém os próximos elementos a serem codificados, e será aqui denominada área de look-ahead. Usualmente, a área de procura contém alguns milhares de símbolos, enquanto a área de look-ahead contém apenas algumas dezenas. Abaixo, vemos uma janela com 64 símbolos, sendo 48 na área de procura e 16 na área de look-ahead.

Segmentos são os componentes do programa. Finalm

área de previsão

dicionário

0 56 4840 32 248 16

ente, programas

O algoritmo consiste em procurar no dicionário a maior coincidência possível entre a frase

composta pelos símbolos iniciais da área de look-ahead e alguma frase presente no dicionário, e codificá-la como um terno (n, i, s), onde n é o número de elementos coincidentes, i é o índice do primeiro elemento da frase coincidente no dicionário, e s é o símbolo que se segue à frase na área de look-ahead. Em seguida, a janela é deslocada de n+1 elementos em direção ao final da mensagem, e o processo se repete. Se o primeiro símbolo da área de look-ahead não se encontra no

23

dicionário, a maior coincidência tem tamanho zero. Neste caso, a saída poderia ser escrita simplesmente como (0, i, s). Destaque-se que n = 0 faz com que o valor de i não importe, não

Como exemplo, vamos acompanhar a codificação da mensagem apresentada na última figura. O processo começa com o preenchimento integral da área de look-ahead com os primeiros elementos da mensagem. Como, neste ponto, o dicionário está vazio, o primeiro elemento da área de look-ahead, ‘S’, é codificado como (0, 0, ‘S’). A figura a seguir ilustra alguns passos do processo de codificação:

0 40 32 248 16

Segmentos são os

Terno de saída: 0, ‘S’

S0 40 32 248 16

egmentos são os

Terno de saída: 0, ‘e’

Se0 40 32 248 16

gmentos são os c

Terno de saída: 0, ‘g’

Seg0 40 32 248 16

mentos são os co

Terno de saída: 0, ‘m’

Segm0 40 32 248 16

entos são os com

Terno de saída: 1, 45, ‘n’

Segmen0 40 32 248 16

tos são os compo

Terno de saída: 0, ‘t’

(. . .)

Segmentos são os componentes do programa. Finalm0 40 32 248 16

ente, programas

Coincidências: (n = 1, i = 1); (n = 3, i = 4) e (n = 4, i = 23)

24

Terno de saída: 4, 23, ‘,’

ntos são os componentes do programa. Finalmente, 0 4032 24 8 16

programas são c

Terno de saída: 9, 26, ‘s’

s componentes do programa. Finalmente, programas 0 403224 8 16

são compostos t

Terno de saída: 1, 1, ‘s’ (. . .)

Neste exemplo, o arquivo codificado pelo LZ77 seria:

0, ’S’, 0, ’e’, 0, ’g’, 0, ’m’, 1, 45, ’n’, 0, ‘t’, ..., 4, 23, ‘,’, 9, 26, ’s’, 1, 1, ’s’,... O processo de decodificação é simples: para cada terno, decodifica-se a frase indicada,

incluindo-a na área de procura, da direita para a esquerda. Para o exemplo anterior, a decodificação seria assim realizada:

Lê-se 0, ‘S’ Decodifica-se ‘S’

S 0 403224 8 16

Lê-se 0, ‘e’ Decodifica-se ‘e’

Se 0 403224 8 16

Lê-se 0, ‘g’ Decodifica-se ‘g’

Seg 0 403224 8 16

Lê-se 0, ‘m’ Decodifica-se ‘m’

Segm 0 403224 8 16

Lê-se 1, 45, ‘n’ Decodifica-se ‘en’

Segmen 0 403224 8 16

(. . .)

25

Lê-se 4, 23, ‘,’ Decodifica-se ‘ente,’

ntos são os componentes do programa. Finalmente,0 403224 8 16

(. . .)

Observe-se que, quanto maiores as áreas de procura e de look-ahead, maior a probabilidade de se encontrar grandes coincidências, o que tende a aumentar a RC. Por outro lado, o aumento destas áreas implica aumento no tempo de processamento requerido para efetuar as buscas e também no número de bits das componentes i e n do terno emitido na codificação, o que leva a uma tendência contrária de redução da RC. Assim, os tamanhos ótimos para as áreas de previsão e de look-ahead dependem da mensagem específica a ser codificada, mas as implementações práticas do LZ77 costumam fixá-los em torno de 4K e 16 bytes, respectivamente. Com estes valores, são necessários 12 bits para i e 4 para n. Se os elementos da mensagem ocupam 8 bits, teremos 24 bits por terno. Assim sendo, cada vez que um ou dois elementos da mensagem original forem substituídas por um terno de 24 bits, teremos uma expansão na representação. Se estas situações forem muito freqüentes, ocorrerá uma degradação sensível na eficiência de compressão do LZ77.

3.2 O LZ78

O LZ78 abandona o conceito da janela deslizante. Agora, emprega-se um dicionário que de início contém unicamente uma string nula (ou seja, sem elementos) na posição zero. Cada elemento da mensagem a ser codificada é concatenado a uma string temporária, inicialmente nula, que denominaremos frase. Enquanto frase for encontrada no dicionário, ou seja, enquanto houver uma igualdade entre esta e alguma string já presente no dicionário, novos símbolos são a ela anexados.

Eventualmente, frase não mais será encontrada no dicionário. Neste momento, o codificador envia para a saída o índice da última string encontrada no dicionário, seguido pelo último símbolo de frase, que é então adicionada ao dicionário e anulada. O processo inteiro se repete, com a leitura e anexação de novos símbolos. Se frase tem um único símbolo e não se encontra no dicionário, o codificador envia o símbolo para a saída antecedido pelo índice 0 (índice da string nula). Para maior eficiência na procura das frases, as inserções no dicionário podem manter alguma ordenação pré-estabelecida.

O número de bits do índice determina o número máximo de frases que podem estar simultaneamente presentes no dicionário. Qualquer que seja este número, eventualmente ele pode ser atingido durante o processo de inserção de frases. Neste caso, há várias alternativas:

1. Retornar o dicionário ao seu estado inicial (só com a string nula). 2. Substituir frases presentes no dicionário por novas frases. 3. Parar de inserir novas frases. 4. Parar de inserir novas frases, mas monitorar, a partir deste momento, a taxa de compactação.

Se esta cair até um dado limiar, retornar o dicionário ao estado inicial.

O processo de decodificação é bastante simples, e será visto nos exemplos a seguir. Exemplo: Codificar a mensagem “Segmentos são os componentes do programa. Finalmente,

programas são compostos tam”, sem ordenação do dicionário. Dicionário: 0 ‘’ 10 ‘sã’ 20 ‘o p’ 30 ‘l’ 40 ‘ã’ 1 ‘S’ 11 ‘o ’ 21 ‘r’ 31 ‘me’ 41 ‘o c’

26

2 ‘e’ 12 ‘os’ 22 ‘og’ 32 ‘nt’ 42 ‘omp’ 3 ‘g’ 13 ‘ c’ 23 ‘ra’ 33 ‘e,’ 43 ‘ost’ 4 ‘m’ 14 ‘om’ 24 ‘ma’ 34 ‘ p’ 44 ‘os ’ 5 ‘en’ 15 ‘p’ 25 ‘.’ 35 ‘ro’ 45 ‘ta’ 6 ‘t’ 16 ‘on’ 26 ‘ F’ 36 ‘g’ 7 ‘o’ 17 ‘ent’ 27 ‘i’ 37 ‘ram’ 8 ‘s’ 18 ‘es’ 28 ‘n’ 38 ‘as’ 9 ‘ ’ 19 ‘ d’ 29 ‘a’ 39 ‘ s’ Saída codificada: 0, ‘S’, 0, ‘e’, 0, ‘g’, 0, ‘m’, 2, ‘n’, 0, ‘t’, 0, ‘o’, 0, ‘s’, 0, ‘ ’, 8, ‘ã’, 7, ‘ ’, 7, ‘s’, 9, ‘c’, 7, ‘m’, 0, ‘p’, 7, ‘n’, 5, ‘t’, 2, ‘s’, 9, ‘d’, 11, ‘p’, 0, ‘r’, 7, ‘g’, 21, ‘a’, 4, ‘a’, 0, ‘.’, 9, ‘F’, 0, ‘i’, 0, ‘n’, 0, ‘a’, 0, ‘l’, 4, ‘e’, 28, ‘t’ ...

Decodificação: • Lê-se 0, ‘S’, decodifica-se a frase ‘S’ e a inclui no dicionário. • Lê-se 0, ‘e’, decodifica-se a frase ‘e’ e a inclui no dicionário. • ... • Lê-se 2, ‘n’, decodifica-se a frase ‘en’ e a inclui no dicionário. • ... • Lê-se 8, ‘ã’, decodifica-se a frase ‘sã’ e a inclui no dicionário

Exemplo: Codificar “Segmentos são os componentes do programa. Finalmente, programas são compostos tam”, mantendo o dicionário crescentemente ordenado por código ASCII. 1. ‘S’ Saída: 0, ‘S’

Dicionário 0 - ‘’ 1 - ‘S’

2. ‘e’ Saída: 0, ‘e’

Dicionário 0 - ‘’ 1 - ‘S’ 2 - ‘e’

3. ‘g’ Saída: 0, ‘g’

Dicionário 0 - ‘’ 3 - ‘g’ 1 - ‘S’ 2 - ‘e’

4. ‘m’ Saída: 0, ‘m’

Dicionário 0 - ‘’ 3 - ‘g’ 1 - ‘S’ 4 - ‘m’ 2 - ‘e’

5. ‘en’ Saída: 2, ‘n’

Dicionário 0 - ‘’ 3 - ‘en’ 1 - ‘S’ 4 - ‘g’

27

2 - ‘e’ 5 - ‘m’ 6. ‘t’ Sáida: 0, ‘t’

Dicionário 0 - ‘’ 3 - ‘en’ 6 - ‘t’ 1 - ‘S’ 4 - ‘g’ 2 - ‘e’ 5 - ‘m’

7. ‘o’ Sáida: 0, ‘o’

Dicionário 0 - ‘’ 3 - ‘en’ 6 - ‘o’ 1 - ‘S’ 4 - ‘g’ 7 - ‘t’ 2 - ‘e’ 5 - ‘m’

8. ‘s’ Sáida: 0, ‘s’

Dicionário 0 - ‘’ 3 - ‘en’ 6 - ‘o’ 1 - ‘S’ 4 - ‘g’ 7 - ‘s’ 2 - ‘e’ 5 - ‘m’ 8 - ‘t’

9. ‘ ’ Sáida: 0, ‘ ’

Dicionário 0 - ‘’ 3 - ‘e’ 6 - ‘m’ 9 - ‘t’

1 - ‘ ’ 4 - ‘en’ 7 - ‘o’ 2 - ‘S’ 5 - ‘g’ 8 - ‘s’

10. ‘sã’ Saída: 8, ‘ã’

Dicionário 0 - ‘’ 3 - ‘e’ 6 - ‘m’ 9 - ‘sã’ 1 - ‘ ’ 4 - ‘en’ 7 - ‘o’ 10 - ‘t’ 2 - ‘S’ 5 - ‘g’ 8 - ‘s’

11. ‘o ’ Saída: 7, ‘ ’

Dicionário 0 - ‘’ 3 - ‘e’ 6 - ‘m’ 9 - ‘s’ 1 - ‘ ’ 4 - ‘en’ 7 - ‘o’ 10 - ‘sã’ 2 - ‘S’ 5 - ‘g’ 8 - ‘o ’ 11 - ‘t’

(. . .)

3.3 O LZW

A principal inovação do LZW em relação ao LZ78 consiste em iniciar o dicionário com todas as frases de um único símbolo. Assim, se o alfabeto da fonte consiste nos símbolos ao, a1, ..., aM-1, o dicionário seria pré-carregado com M frases, sendo a primeira ‘a0’, a segunda ‘a1’, e assim por diante.

Para descrever o LZW, vamos definir uma variável string, inicialmente nula, ou seja, sem elementos, e chamá-la de frase. O primeiro símbolo lido do arquivo a ser codificado é anexado a esta variável, e então procura-se no dicionário a string resultante. Obviamente ela está presente, devido à pré-carga do dicionário com yodas as frases possíveis de tamanho unitário. O próximo

28

símbolo, s, do arquivo é então concatenado a frase, que agora não se encontra no dicionário, sendo neste momento nele inserida. Após a inserção, o codificador LZW envia para a saída o índice da última string encontrada no dicionário. Reinicia-se, então, o processo, com frase = s. Continua-se a concatenar novos símbolos do arquivo a frase, até que a string resultante não mais seja encontrada no dicionário. Quando isto ocorre, envia-se para a saída o índice da última string encontrada, e anexa-se frase ao dicionário.

Na descrição que se segue, o símbolo + denota concatenação de strings. Codificação LZW 1. Pré-carregue o dicionário com todas as strings de tamanho 1 2. frase := ‘’ 3. s := próximo símbolo do arquivo 4. frase + s encontra-se no dicionário?

• Sim: frase := frase + s Vá para 3

• Não: Envie índice de frase para o arquivo codificado Insira frase + s no dicionário frase := s Vá para 3

Decodificação LZW 1. Pré-carregue o dicionário com todas as strings de tamanho 1 2. Cod : = Primeiro índice da mensagem codificada 3. Envie string de número Cod para a saída 4. Cod_Anterior := Cod 5. Cod := Próximo índice da mensagem codificada 6. Cod presente no dicionário?

• Sim: Envie string de índice Cod para a saída frase := string de índice Cod_Anterior s := Primeiro símbolo da string de índice Cod Adicione frase + s ao dicionário Cod_Anterior := Cod • Não: frase := string de índice Cod_Anterior

s := Primeiro símbolo de frase Envie frase + s para a saída e a inclua no dicionário. Cod_Anterior := Cod

7. Vá para 5

Exemplo: Codificar “Segmentos são os componentes do programa. Finalmente, programas são compostos tam” usando o LZW. Considere que a fonte gera apenas as letras e sinais de pontuação presentes na mensagem, e que o dicionário não precisa ser ordenado.

29

Dicionário: 0 ‘ ’ 10 ‘i’ 20 ‘Se’ 30 ‘sã’ 40 ‘on’ 1 ‘,’ 11 ‘l’ 21 ‘eg’ 31 ‘ão’ 41 ‘ne’ 2 ‘.’ 12 ‘m’ 22 ‘gm’ 32 ‘o ’ 42 ‘ent’ 3 ‘F’ 13 ‘n’ 23 ‘me’ 33 ‘ o’ 43 ‘te’ 4 ‘S’ 14 ‘o’ 24 ‘en’ 34 ‘os ’ 44 ‘es’ 5 ‘a’ 15 ‘p’ 25 ‘nt’ 35 ‘ c’ 45 ‘s d’ 6 ‘c’ 16 ‘r’ 26 ‘to’ 36 ‘co’ 46 ‘do’ 7 ‘d’ 17 ‘s’ 27 ‘os’ 37 ‘om’ 47 ‘o p’ 8 ‘e’ 18 ‘t’ 28 ‘s ’ 38 ‘mp’ 48 ‘pr’ 9 ‘g’ 19 ‘ã’ 29 ‘ s’ 39 ‘po’ ...

Saída codificada: 4, 8, 9, 12, 8, 13, 18, 14, 17, 0, 17, 19, 14, 0, 27, 0, 6, 14, 12, 15, 14, 13, 24, 18, 8, 28, 7, 32, 15, ...

Para aumentar a eficiência de tempo do codificador LZW, é comum utilizar hashing na busca e inserção de novas strings no dicionário. Se considerarmos cada nova string Frase + S a ser inserida no dicionário como filha da string Frase, podemos incluí-la como um par (Indice_Pai, S) e, com isto, reduzir sensivelmente o tamanho do dicionário. Uma função de hashing pode combinar Indice_pai com S, gerando um índice que indicará a posição do dicionário onde a inserção ocorrerá.

Com um dicionário de N entradas e M strings pré-carregadas, uma função de hashing ideal, além de simples, deveria gerar um índice diferente, entre M e N - 1, para cada diferente par (Indice_Pai, S) a ela passado. Na prática, a aplicação de fórmulas simples a este par costuma gerar colisões, ou seja, dois ou mais pares diferentes podem resultar no mesmo índice. Neste caso, a própria função deve resolver a colisão de alguma forma, o que representa tempo extra de processamento. Para reduzir a freqüência destas elaborações, utiliza-se um dicionário com mais do que N entradas para armazenar no máximo N strings.

Um algoritmo LZW com uso de hashing é apresentado a seguir. Neste, representamos o dicionário pelo vetor struct { int Indice; int Indice_Pai; char Caracter; } Dic [N’];

Considera-se ainda que cada string pré-carregada tem um índice fixo no dicionário, igual ao seu valor numérico, de forma que não é preciso incluí-las fisicamente no dicionário. Para arquivos organizados em bytes, M = 256.

Na descrição a seguir, a variável Prox_Livre é o próximo índice disponível para uma nova frase no dicionário, e Indice_Max é o maior índice permitido. Com um arquivo organizado em bytes e um dicionário com capacidade para 4K strings, por exemplo, Indice_Max seria igual a 212-1.

Codificação LZW2 1. Prox_Livre := M

Dic[i].Indice := Nao_Usado, para todo i; Frase := Primeiro elemento da mensagem

2. S := Próximo elemento da entrada 3. j := Hashing( Frase, S) 4. Dic[j].Indice usado?

• Sim:

30

Frase := Dic[j].Indice; Vá para 2

• Não: Se Prox_Livre ≤ Indice_Max Então: dic[j].Indice := Prox_Livre dic[j].Indice_Pai := Frase dic[j].Caracter := S Prox_Livre := Prox_Livre + 1 Saída := Frase Frase := S Vá para 2

Decodificação LZW2 1. Prox_Livre := M

Indice_Ant := primeiro índice da mensagem codificada S := char(Indice_Ant) Saída := S

2. Indice := próximo índice da mensagem codificada 3. Indice < Prox_Livre?

• Sim: j := Indice String_Saida := ‘’; Enquanto j ≥ M faça

String_Saida := Dic[j].Caracter + String_Saida j := Dic[j].Indice_Pai String_Saida := char(j) + String_Saida

• Não: j := Indice_Ant String_Saida := ‘S’

Enquanto j ≥ M faça String_Saida := Dic[j].Caracter + String_Saida j := Dic[j].Indice_Pai String_Saida := char(j) + String_Saida

4. S := 1o caracter de String_Saída Saída := String_Saída

5. Se Prox_Livre ≤ Max_Índice Então:

Dic[Prox_Livre].Indice_Pai := Indice_Ant Dic[Prox_Livre].Caracter := S Prox_Livre := Prox_Livre + 1

6. Indice_Ant := Índice 7. Vá para 2

A implementação em C de uma função de hashing muito semelhante à utilizada no programa compress do Unix é apresentada a seguir. As constantes nbits e tamanho_dic representam, respectivamente, o número de bits usados para os índices e o tamanho total do dicionário. A função produz bons resultados se tamanho_dic for um número primo pelo menos 20% maior que 2nbits. Se desejarmos trabalhar com índices de 12 bits (4K frases), por exemplo, deveríamos usar tamanho_dic = 5021, ou algum outro número primo superior a este.

31

unsigned int hashing(unsigned int Frase, unsigned int S) { int I, offset; I = ( S << (nbits - 8) ) ^ Frase; if ( I == 0) offset = 1; else offset = tamanho_dic - I; for( ; ; ) { if( Dic[I].Indice == nao_usado) return ( I ); if ( Dic[I].Indice_Pai == frase && Dic[I].Caracter == (char) S ) return ( I ); I = I - offset; if ( I < 0) I = I + tamanho_dic; } }

32

Capítulo 4

PANORAMA DOS COMPRESSORES SEM PERDAS

A árvore a seguir mostra a relação entre alguns dos mais importantes codificadores de compressão da atualidade. O esquema traz ainda informações extras, tais como a taxa de bits média, R, obtida por cada codificador em experimentos com o Calgary Compression Corpus, relatados por Timothy C. Bell, John G. Cleary e Ian H. Witten no livro Text Compression, e a posição ocupada pelo codificador nesses experimentos (P = 1 para o codificador com a menor taxa de bits, P = 2 para o codificador com a segunda melhor taxa de bits, e assim por diante).

33

Codificadores

Baseados em Dicionários

Estatísticos

LZ77 R=3,94 P=11

LZ78R=4,13P=15

LZR R=4,12 P=14

LZSS R=3,43

P=9

LZB R=3,18

P=5

LZH R=3,30

P=7

LZWR=4,71P=17

LZJ R=4,00 P=12

LZC R=4,26P=16

LZT R= 3,76

P=10

LZMWR=3,32

P=8

LZFGR=2,95

P=4

Huff R=4,99P=18

WORDR=2,76

P=3

DAFCR=4,02P=13

PPMC R=2,48

P=1

DMC R=2,74

P=2

MTFR=3,24

P=6

34

Capítulo 5

COMPRESSÃO COM PERDAS BASEADA

NO PARADIGMA TQC

Em determinadas situações, distorções leves introduzidas pela compressão são aceitáveis. Na compressão de sinais e imagens, por exemplo, alterações criteriosas podem até mesmo ser imperceptíveis sob condições normais de observação. A compressão com perdas é comumente aplicada a sinais e imagens. Em alguns casos, no entanto, tais como na compressão de imagens e sinais utilizados no diagnóstico médico, as modificações introduzidas no processo devem ser efetuadas com extrema cautela, ou até mesmo evitadas por completo.

Apenas no final dos anos 70 e início dos 80, pesquisadores começaram a trabalhar em técnicas de compressão com perdas realmente práticas. No final dos anos 80, o resultado deste trabalho foi comercialmente aplicado em co-processadores gráficos para estações Unix e Macintosh, capazes de comprimir imagens em até 95% sem degradação perceptível na qualidade.

Percebendo a extraordinária importância destas novas técnicas, os grupos internacionais CCITT e ISO juntaram esforços e, juntamente com setores industriais e acadêmicos envolvidos com compressão de imagens, criaram o grupo de padronização denominado Joint Photographic Experts Group (JPEG). O algoritmo definido pelo grupo JPEG segue um paradigma clássico de compressão baseado em três grandes etapas: transformada, quantização e codificação. O paradigma é descrito na seção seguinte.

5.1 O PARADIGMA TQC

Os compressores baseados no paradigma TQC aplicam três operações sucessivas (transformada, quantização e codificação) para obter o sinal comprimido.

35

5.1.1 Transformada

O paradigma TQC começa com a aplicação de uma operação matemática denominada transformada às amostras do sinal. A teoria das transformadas representa um papel dos mais importantes na área de processamento de sinais e imagens. As transformadas geram um conjunto de coeficientes a partir dos quais é possível restaurar as amostras originais do sinal. Assim sendo, esta etapa é invertível, ou seja, sem perdas. Uma transformada adequada à compressão de dados produz coeficientes estatisticamente descorrelacionados e concentra a energia do sinal em poucos coeficientes de valor absoluto elevado. As etapas seguintes podem então reduzir o número de bits usados na representação de coeficientes de valor absoluto reduzido, ou mesmo eliminá-los por completo, sem introduzir grandes distorções no sinal reconstruído. Além de simplificar a maneira como estas perdas são introduzidas, o descorrelacionamento dos coeficientes permite o emprego de modelos simples para a codificação de entropia.

Por sua capacidade de descorrelacionamento e de concentração de energia em poucos coeficientes, as transformadas cosseno discreta (discrete cosine transform, ou DCT) e a wavelet discreta (discrete wavelet transform, ou DWT) tornaram-se disparadamente as mais usadas em compressão dados. Por sua simplicidade e eficiência, nos ateremos aqui exclusivamente ao estudo da DCT, adotada nos padrões JPEG e MPEG e em muitos outros compressores de alto desempenho.

Se xn, n = 0, 1,..., N-1, são os elementos de uma seqüência x, a DCT unidimensional de x gera uma seqüência X cujos coeficientes Xk, k = 0, 1,..., N -1, são dados por:

110 ,2

)12(cos2 1

0

2/1

−=

+

= ∑

−

=

,...,N,kN

knxcN

XN

nnkk

π

onde

( )

==

=1-... 2, 1, para 1

0para 1/2 1/2

Nk kck

Esta operação leva vetores de um determinado domínio (comumente, do domínio do tempo

ou do espaço) para o chamado domínio da freqüência. O coeficiente X0, que representa a componente de freqüência zero e está relacionado diretamente com o valor médio de x, é conhecido como coeficiente DC (de direct current); os demais são os coeficientes AC (de alternating current).

A seqüência x pode ser recuperada aplicando-se a X a DCT inversa:

110 ,2

)12(cos2 1

0

2/1

−=

+

= ∑

−

=

,...,N,nN

knXcN

xN

kkkn

π

Há diversos algoritmos para o cálculo eficiente da DCT, mas, ainda assim, o custo

computacional quando a seqüência x contém muitos elementos pode ser elevado. Quando aplicada para compressão de dados, é prática comum particionar a seqüência em blocos consecutivos com tamanho fixo Lb, e efetuar o processamento bloco a bloco. Se Lb é muito pequeno tem-se uma degradação na RC; blocos demasiadamente grandes, por outro lado, exigem um longo tempo de processamento. Diversos experimentos indicam que aumentar o tamanho dos blocos acima de um certo ponto resulta em melhorias marginais ou mesmo em degradações no compromisso taxa-distorção, enquanto que o tempo de processamento aumenta significativamente. O valor ótimo para Lb depende da seqüência a ser comprimida. O padrão JPEG, por exemplo, emprega blocos com 8x8 pixels, apesar de existirem indícios de que é possível melhorar consideravelmente a relação entre compressão e distorção utilizando-se blocos com tamanho 16x16.

36

Para sinais bidimensionais, com elementos xmn, m, n = 0, 1,..., N-1, a DCT bidimensional gera uma seqüência cujos coeficientes Xkl, k, l = 0, 1,..., N -1, são dados por:

+

+

= ∑∑−

=

−

= Nln

Nkmxcc

NX

N

m

N

nmnlkkl 2

)12(cos2

)12(cos21 1

0

1

0

ππ , k, l = 0, 1,..., N-1

onde

( )

==

=1-... 2, 1, para 1

0para 1/2 1/2

Nk kck

A seqüência original pode ser recuperada aplicando-se a DCT bidimensional inversa:

+

+

= ∑∑−

=

−

= Nnl

NmkXcc

Nx

N

k

N

lkllkmn 2

)12(cos2

)12(cos21 1

0

1

0

ππ

5.1.2 Quantização

Muitos sinais de interesse são, por natureza, de amplitude e tempo contínuos. Os conversores A/D (Analógico-digital), através das operações de amostragem e quantização, permitem a representação discreta destas formas de onda. Neste contexto, a quantização é o processo de transformar amplitudes analógicas em discretas, sendo um fator determinante para a qualidade do sinal digital e para a taxa de bits necessária à sua representação.

O processo de quantização não se aplica unicamente à conversão de sinais analógicos em digitais. Se o sinal é digital por natureza, ou foi previamente convertido a esta forma, pode-se empregar quantização com o objetivo de reduzir a sua representação binária. Neste caso, a quantização atua essencialmente por redução de alfabeto: uma amplitude (ou um grupo de amplitudes), selecionada de um conjunto com M elementos, é transformada pela quantização em uma amplitude (ou um grupo de amplitudes) selecionada de um conjunto com K elementos, K < M. Quando os elementos dos conjuntos representam amplitudes individuais, tem-se uma quantização escalar; quando representam grupos de amplitudes, tem-se uma quantização vetorial.

Teoricamente, a quantização vetorial é mais eficiente, em termos de taxa-distorção, principalmente quando as amostras são estatisticamente dependentes ou correlacionadas. Por outro lado, a quantização escalar apresenta menor complexidade computacional. Em conseqüência, é comum o emprego de quantização escalar, com a inclusão de uma etapa prévia de descorrelação. Quando bem projetada, esta associação muitas vezes apresenta um compromisso taxa-distorção superior ao obtido por muitos esquemas de quantização vetorial, cuja implementação prática pode exigir simplificações intensas. O grau de correlação pode ser atenuado pela aplicação de uma transformada ao sinal original ou por uma etapa prévia de predição. Quantização Escalar Um quantizador escalar de K níveis é uma função Q(x) que mapeia dos reais para um conjunto de K números {r0, r1, ..., rK-1}:

Q(x) = rk se dk ≤ x < dk+1, k = 0, ..., K – 1 com d0 = -∞, dK-1 = ∞, e d0 < r0 < d1 < r1 < ... < rK-1 < dK. Os números dk, k =0, ..., K, são denominados níveis de decisão; os intervalos [dk, dk+1), k =0, ..., K-1, são os intervalos de decisão; e

37

os números rk, k =0, ..., K-1, são os níveis de reconstrução. No processo de quantização, portanto, um elemento com valor x, gerado pela fonte, será substituído por rk se dk ≤ x < dk+1.

Quando os níveis de decisão são igualmente espaçados, diz-se que a quantização é uniforme, e o espaçamento é denominado tamanho do passo de quantização. Os níveis de reconstrução não são necessariamente uniformemente espaçados, podendo ser definidos de forma a minimizar a distorção. Uma simplificação usual é posicionar os níveis de reconstrução no centro dos intervalos de decisão:

21++

= kkk

ddr

Como a quantização é um mapeamento de muitos-para-um, o processo é irreversível. Se a

quantização produz um nível de reconstrução rk em um determinado momento, tudo o que se pode concluir é que o valor originalmente gerado pela fonte localizava-se no intervalo [dk, dk+1), mas não há como saber qual era o valor exato. Em outras palavras, há perda de informação no processo, ou seja, a quantização gera distorção, e qualquer compressor que a utilize é, conseqüentemente, um compressor com perdas.

O projeto de um quantizador envolve a definição da quantidade e dos valores dos níveis de decisão e de reconstrução. Estes fatores, por sua vez, afetam a taxa de bits e a distorção.

Em um compressor/descompressor, a quantização é dividida em duas etapas. A primeira ocorre durante a compressão, e consiste em substituir os valores gerados pela fonte por identificadores (valores inteiros codificados em binário, por exemplo) para os intervalos de decisão em que se localizam. Na segunda etapa, que ocorre durante a descompressão, estes identificadores são substituídos pelos níveis de reconstrução correspondentes aos intervalos. Tornou-se comum empregar o termo quantização para designar a primeira etapa do processo, e o termo dequantização para a segunda etapa. Por este motivo, os identificadores dos intervalos, gerados durante o processo de quantização, são muitas vezes chamados de valores quantizados, enquanto os níveis de reconstrução são chamados de valores dequantizados.

Quando um dos níveis de decisão possui valor zero, o quantizador é denominado de midriser; caso contrário, tem-se um quantizador midtread. Por sua simplicidade, o quantizador uniforme midtread com níveis de reconstrução no centro dos intervalos de decisão, que será identificado por QUMC (Quantizador Uniforme, Midtread, reconstrução Central), é provavelmente o quantizador mais utilizado para compressão de imagens. O QUMC pode ser implementado através de divisão seguida por arredondamento para o inteiro mais próximo. Se x representa um valor gerado pela fonte de informação, o valor quantizado x̂ é obtido através da seguinte operação:

x̂ = x // q onde // denota divisão seguida por arredondamento para o inteiro mais próximo e q é um valor positivo. Pela própria definição da operação, x̂ ∈ Ζ. O valor dequantizado, ou nível de reconstrução, x~ , é dado por:

x~ = q x̂

Um número real qualquer, v, é arredondado para o inteiro i se e somente se i-0,5 ≤ v < i+0,5. Logo, na divisão seguida por arredondamento, um valor x será quantizado para i, e conseqüentemente dequantizado para o nível de reconstrução qi, quando i-0,5 ≤ x/q < i+0,5, ou seja, (i-0,5)q ≤ x < (i+0,5)q. Vê-se, portanto, que o nível de reconstrução qi encontra-se posicionado no centro do intervalo de decisão [(i-0,5)q, (i+0,5)q), para i = ...-2, -1, 0, 1, 2,... Como o espaçamento entre os níveis de decisão é q, a quantização por divisão seguida por arredondamento para o inteiro mais próximo é uniforme, sendo q o tamanho do passo de quantização.

38

Pode-se elaborar um pouco mais o processo empregando quantização com zona morta, dada por

<

=contrário caso //

se 0ˆ

qxt |x|

x

onde t é um valor positivo real que define o limiar abaixo do qual todos os elementos são quantizados para zero. Dado o valor quantizado x̂ , o nível de reconstrução é obtido, da mesma forma que na quantização uniforme, por

x~ = q x̂

Quantização Vetorial Em 1948, Shannon mostrou que codificar elementos agrupados em vetores é teoricamente mais eficiente que codificá-los isoladamente. Este resultado permanece válido mesmo quando os elementos gerados são independentes. Na quantização vetorial, a mensagem gerada pela fonte é particionada em blocos ou vetores com L elementos consecutivos. Um número K de vetores, denominados vetores-código, é selecionado, dentre todos aqueles que podem ser gerados pela fonte, e armazenados em uma tabela conhecida como codebook, disponível para o compressor e para o descompressor. Sejam ck, k = 0, 1,..., K-1, o k-ésimo vetor-código do codebook; ckj, j = 0, 1,..., L-1, o j-ésimo elemento de ck; vi, i = 0, 1,..., o i-ésimo vetor na mensagem produzida pela fonte; e vij, j = 0, 1,..., L-1, o j-ésimo elemento de vi. Para codificar vi, o quantizador calcula a distorção D(vi, ck), k = 0, 1, ..., K-1, entre este vetor e cada um dos vetores-código. A distorção é freqüentemente dada pelo erro médio quadrático:

21

0)(1),( ∑

−

=

−=L

jkjijki cv

LD cv

Se D(vi, ck) é mínima para k = k’, o índice k’ é anexado à mensagem comprimida. Durante a descompressão, k’ é substituído pelo vetor-código correspondente, ck’.

Note-se que, enquanto o compressor realiza uma série de comparações para encontrar o vetor-código que mais se aproxima do vetor de entrada, o descompressor precisa apenas retirar de uma tabela o vetor indexado. Isto faz da quantização vetorial uma opção atrativa para aplicações em que os recursos computacionais disponíveis durante a descompressão são consideravelmente menores que os disponíveis durante a compressão.

Para códigos de comprimento fixo, os índices são codificados com log2(K) bits. Como cada índice representa, na mensagem codificada, um vetor com L elementos, a taxa resultante é de log2(K)/ L bits/elemento.

Teoricamente, quanto maior L, mais eficiente a quantização. Na prática, a dimensão dos vetores é limitada por considerações de eficiência de processamento. O desempenho depende ainda do tamanho do codebook; da escolha dos vetores-código; e da medida de distorção utilizada. O codebook é gerado por um procedimento de treinamento, durante o qual uma quantidade normalmente elevada de mensagens é examinada. Os vetores considerados mais representativos (de acordo com o método de treinamento empregado) do conjunto de mensagens são selecionados como vetores-código. Desde sua introdução em 1980, o algoritmo LBG tem sido um método de treinamento muito popular, mas uma grande variedade de técnicas tem sido apresentada, inclusive com o emprego de redes neurais.

Se as mensagens de treinamento representam adequadamente as características encontradas nas mensagens reais, e se o codebook é bem definido, a distorção causada pela quantização será

39

baixa. Em muitas situações reais, no entanto, o elevado grau de variabilidade de aspectos relevantes das mensagens geradas pela fonte exigiria um conjunto de treinamento e um codebook de grandes dimensões, implicando tempo de treinamento e de compressão elevado.

5.1.3 Codificação de Entropia

A codificação de entropia dos coeficientes quantizados constitui a última etapa dos compressores baseados no paradigma TQC. Dada a capacidade de concentração da energia do sinal em poucos coeficientes importantes, a quantização tipicamente anula muitos coeficientes de valor absoluto baixo, o que tende a gerar longas seqüências de coeficientes nulos. Por este motivo, os compressores baseados em TQC freqüentemente incorporam à etapa de codificação de entropia algum tipo de adaptação do RLE para o caso em que se sabe a priori que longas seqüências de zero são particularmente comuns. Em associação com o RLE de zeros (RLEZ), pode-se usar qualquer outro codificador de entropia, tal como o Huffman e o aritmético. O padrão JPEG, que será estudado na próxima seção, associa um esquema simples de RLEZ com codificação de Huffman.

Em 1966, Golomb propôs um esquema simples de codificação de valores inteiros não negativos. Dado um parâmetro inteiro positivo m, o código de Golomb de um inteiro não negativo n é a concatenação da codificação unária de n / m com a codificação binária ajustada de n mod m.

A codificação unária de um inteiro não negativo v é uma seqüência de v bits com valor ‘1’ finalizada por um bit com valor ‘0’. Para descrever a codificação binária ajustada (Howard, 1994), considere-se um alfabeto de tamanho m = 2k+b, composto pela seqüência de inteiros 0, 1, 2,..., 2k+b-1, onde k é o maior inteiro tal que 2k ≤ m, e b é um inteiro não negativo. Na representação binária convencional, cada símbolo deste alfabeto seria codificado com log2 m bits. Assim, as palavras-código teriam k bits se b = 0, e k+1 bits se b ≠ 0. Para b = 0, a codificação binária ajustada é idêntica à codificação binária convencional mas, para b ≠ 0, parte dos símbolos é codificada com k bits, e o restante com k+1 bits. Mais especificamente, a codificação binária ajustada de um símbolo no intervalo [0, 1, ..., 2k-b-1] é simplesmente sua representação binária convencional com k bits, enquanto a codificação binária ajustada de um símbolo de valor w fora deste intervalo é a representação binária, com k+1 bits, de w + m - 2b. Para m = 5, por exemplo, tem-se k = 2 e b = 1. Neste caso, os símbolos 0, 1 e 2, na codificação binária ajustada, tornam-se 00, 01 e 10, respectivamente, enquanto que os símbolos 3 e 4 são codificados como 110 e 111.

O código de Golomb é ótimo, sob a restrição de atribuir-se um número inteiro de bits por palavra-código, para distribuições de probabilidade geométricas, também conhecidas como geométricas unilaterais, dadas por

P(x = n) = nρ)ρ1( − onde P(x = n) é a probabilidade de x assumir o valor inteiro n ≥ 0, e 0 < ρ <1. Pode-se mostrar que a variância desta distribuição é dada por

σ2 = 2ρ)1(ρ

−

Para distribuições geométricas unilaterais, definindo-se o parâmetro m como

m =

+1-ρlogρ)1log(

o código de Golomb produz o menor comprimento médio dentre todos os códigos unicamente decodificáveis.

40

A distribuição contínua de Laplace, também conhecida como exponencial bilateral ou dupla, centrada em zero, e a distribuição discreta geométrica bilateral centrada em zero têm sido freqüentemente consideradas boas aproximações para a distribuição de erros de predição e de coeficientes DCT e wavelet. A distribuição de Laplace de média zero é caracterizada pela densidade de probabilidade:

β

β

x

exf−

=21)(

com β > 0. A distribuição geométrica bilateral é dada por

P(x = n) = 2ρ)ρ1( n−

com 0 <ρ <1.

O seguinte mapeamento permite converter distribuições geométricas bilaterais em distribuições aproximadamente geométricas unilaterais, viabilizando o emprego do código de Golomb:

<

≥=

0202

)(nnnn

nM 1-

Rice deteve-se no estudo do subconjunto dos códigos de Golomb com parâmetro m = 2k. Este caso especial, que se tornou conhecido como codificação de Golomb-Rice, permite uma simplificação ainda maior, com o código para n sendo obtido pela concatenação da representação unária do valor n deslocado k bits para a direita, com os k bits menos significativos de n. Para distribuições geométricas unilaterais, a razão de compressão média obtida com um código de Golomb-Rice com parâmetro k ótimo é próximo à entropia. Dada uma seqüência cujos elementos seguem uma distribuição geométrica bilateral, uma estimativa do valor ótimo do parâmetro k a ser empregado na codificação da seqüência obtida após o mapeamento expresso anteriormente:

k = log2 a onde a é a média dos módulos dos valores da seqüência antes do mapeamento.

A codificação de Golomb e de Golomb-Rice tem sido muito aplicada à compressão de imagens, áudio, eletrocardiogramas e outros sinais. A Tabela 5.1 exemplifica a codificação de Golomb e de Golomb-Rice para diversos valores de n e m.

41

Tabela 5.1. Exemplos de códigos de Golomb e de Golomb-Rice.

n m =1

k = 0

m =2

k = 1

m = 3 m =4

k = 2

m =5

m =6

m =7

0 0 00 00 000 000 000 000

1 10 01 010 001 001 001 0010

2 110 100 011 010 010 0100 0011

3 1110 101 100 011 0110 0101 0100

4 11110 1100 1010 1000 0111 0110 0101

5 111110 1101 1011 1001 1000 0111 0110

6 1111110 11100 1100 1010 1001 1000 0111

7 11111110 11101 11010 1011 1010 1001 1000

8 111111110 111100 11011 11000 10110 10100 10010

... ... ... ... ... ... ... ...

5.1.4 Diagrama em blocos de um compressor/descompressor TQC

A Figura 5.1 resume a operação de um compressor/descompressor baseado no paradigma TQC. O sinal de entrada é primeiramente particionado em blocos. O sinal comprimido é composto pelos coeficientes das transformadas dos blocos, quantizados e codificados. Durante a descompressão, a transformada inversa é aplicada aos coeficientes decodificados e dequantizados, gerando uma aproximação x~ para x. Devido à quantização, em geral x~ ≠ x.

x

Transformada

blocos bi

Bi

x Canal

x~

iB̂

Quantização

Codificação Decodificação

Dequantização

iB~

TransformadaInversa

x

iB̂

Figura 5.1 Diagrama em blocos de um compressor/descompressor

baseado em transformada + quantização + codificação

A eficiência do esquema, em termos de taxa e distorção, depende da transformada, da

estratégia de quantização e da codificação. Uma transformada apropriada gera coeficientes pouco

42

correlacionados e concentra a maior parte da energia do bloco em um pequeno número de coeficientes. A quantização pode então ser efetuada de forma diferenciada: os coeficientes que concentram uma parcela menor da energia de x são menos importantes para a sua reconstrução, podendo ser quantizados mais grosseiramente, ou seja, com maior distorção e menor taxa. Apesar da descorrelação proporcionada pela transformada não implicar independência (a não ser para o caso gaussiano), observa-se na prática que o aumento de compressão da quantização vetorial com relação à escalar, para elementos descorrelacionados, normalmente não compensa o acréscimo na complexidade. Após a quantização, um modelo estatístico dos coeficientes quantizados é construído e passado ao codificador.

5.2 O PADRÃO JPEG

5.2.1 DCT

O processo de compressão JPEG inicia-se com a aplicação da DCT bidimensional a blocos adjacentes da imagem. Os blocos tem tamanho fixo em 8 x 8.

Podemos considerar uma imagem digital, f, com R linhas e C colunas, como uma matriz bidimensional R x C, cujos elementos são denominados pixels (picture element). Neste modelo, o valor numérico f(i, j) assumido pelo pixel na linha i e coluna j representa a intensidade luminosa ou nível de cinza da imagem naquele ponto:

f =

−−−−

−−

)1,1(...)1,1()0,1(............

)1,1(...)1,1()0,1()1,0(...)1,0()0,0(

CLfLfLf

CfffCfff

Se forem utilizados p bits/pixel, diz-se que a imagem possui 2p níveis de cinza, e seus

elementos podem assumir valores em [0, 2p - 1]. Na convenção usual um pixel f(i, j) com valor zero apresenta cor preta, e um pixel f(i, j) com valor 2p - 1 apresenta cor branca. Um pixel com valor maior que zero e menor que 2p - 1 é cinza, com valores próximos a zero representando tons escuros e valores próximos a 2p - 1 representando tons mais claros.

Imagens com 256 cores, por exemplo, utilizam 8 bits/pixel, e seus elementos podem assumir valores em [0,255]:

F =

......15512089188...77701546...205810...1902552140

O padrão JPEG especifica que os elementos da imagem de entrada devem ser deslocados do

intervalo [0, 2p-1] para o intervalo [-2p-1, 2p-1-1] antes do cálculo da DCT. Se p = 8, por exemplo, isto pode ser feito simplesmente subtraindo 128 de cada um dos elementos da imagem:

43

F =

......15512089188...77701546...205810...1902552140

F’ =

−−−−−−

−−−−

......2783960...515811382

...77120127128

...6212712612

Apresentamos abaixo alguns trechos de dimensões 4 x 4 e a DCT correspondente.

F =

148156145168167136155152147140152144140147144140

DCT =

−−−−

−−−−−

65,521,483,484,103,1407,447,488,042,378,890,321,1374,348,509,287,58

F =

168168168168152152152152144144144144140140140140

DCT =

−

−

00032,300049,800093,2800005,65

F =

152152152152144144144144168168168168140140140140

DCT =

−−−

00077,2600014,1400090,100005,65

5.2.2 Quantização

Normalmente, imagens digitais apresentam variações suaves de intensidade entre pixels adjacentes, o que significa que suas componentes de baixa freqüência são mais significativas que as de alta freqüência. Assim, coeficientes DCT mais afastados da componente DC tendem a contribuir menos para a composição da imagem, e podem ser quantizados de forma mais drástica sem degradação significativa da qualidade da imagem.

No padrão JPEG, uma matriz de quantização, Q, de dimensões idênticas aos blocos DCT, é empregada na quantização e dequantização. Cada elemento da matriz de quantização especifica o tamanho do passo de quantização, no intervalo [1,255], para o coeficiente DCT correspondente. A quantização é realizada pela divisão de cada coeficiente DCT pelo passo correspondente em Q, seguida pelo arredondamento para o inteiro mais próximo. A dequantização é realizada pela multiplicação de cada coeficiente DCT pelo passo correspondente em Q. Devido ao arredondamento, a dequantização não é, em geral, capaz de restaurar perfeitamente a matriz DCT original a partir da matriz DTC quantizada. As distorções e a compressão tendem a aumentar com o aumento do tamanho dos passos de quantização.

O comitê JPEG deixou livre a escolha da matriz de quantização a ser utilizada, mas divulgou uma série de matrizes, classificadas por taxa de compressão e qualidade, obtidas após testes exaustivos realizados em imagens de diferentes características.

Uma tabela de quantização simples, parametrizada por uma fator de controle de qualidade, fc, poderia ser definida por Q(i, j) = 1 + [(1 + i + j) x fc] ; i,j = 0, 1, ..., N-1

44

Neste caso, quanto maior fc, maior o potencial de compressão e menor a qualidade. Abaixo,

vemos uma matriz com fc = 2, seguida por uma com fc = 10. Qualquer uma delas poderia ser utilizada para a quantizar matrizes DCT 4 x 4.

1513119131197119759753

71615141615141315141312141312111

Tem-se a seguir uma das matrizes de quantização sugerida pelo JPEG:

991031001129895927210112012110387786449921131048164553524771031096856372218

16280875129221714566957402416131455605826191412126151402416101116

As figuras seguintes ilustram o processo de quantização e dequantização de um bloco 8x8

de uma imagem real com 8 bits/amostra, usando esta última matriz de quantização apresentada:

Bloco 8x8 da imagem original

158158158163161161162162157157157162163161162162157157157160161161161161155155155162162161160159159159159160160162161159156156156158163160155150156156156159156153151144155155155155153149144139

DCT do bloco anterior subtraído de 128

4,06,02,19,18,18,36,16,28,01,17,15,05,13,04,03,10,10,15,18,03,06,12,08,1

3,16,07,01,06,15,18,06,03,00,01,09,05,12,09,11,71,06,09,02,05,16,13,99,102,14,01,09,22,32,65,176,22

3,17,27,11,22,51,120,16,235

−−−−−−−−−−−−−−−

−−−−−−−

−−−−−−−−−−−−−

−−−−−

45

Bloco DCT Quantizado

00000000000000000000000000000000000000000000001100000012000001015

−−−−

−

Bloco DCT Dequantizado

00000000000000000000000000000000000000000000001314000000122400000100240

−−−−

−

Bloco reconstruído

158159161162161161159158158159161162162162161160157158160162164164164163156158160162163164163163155157159161162161161160155156157158158157156155156156156156154152150148156156156154152149146144

Há duas abordagens comuns para mensurar a degradação na qualidade da imagem

decorrente daquantização. Na primeira, faz-se uma aferição matemática da distorção entre as imagens originais e descomprimidas. Na segunda abordagem, procede-se a uma aferição psicofísiológica da importância das distorções para o ser humano.

Na aferição matemática, uma medida freqüentemente adotada para quantificar as perdas introduzidas pela quantização é a raiz do valor médio quadrático (root mean square - RMS) do erro entre a imagem original f e a descomprimida f~ :

Erms = ( )2/1

0 0

2),(~),(1

−∑∑

= =

R

i

C

jjifjif

RC

46

5.2.3 Compressão de Entropia

A última etapa do processo JPEG é a codificação sem perdas dos coeficientes DCT quantizados. Esta fase envolve três passos:

1. Substituição do coeficiente DC de cada bloco pela diferença entre o próprio coeficiente e o coeficiente DC do bloco antecedente. Para permitir a decodificação, o primeiro bloco retém o valor original do seu coeficiente constante.

2. RLEZ dos coeficientes de cada bloco empregando o percurso em zig-zag descrito a seguir. 3. Codificação de Huffman.

Uma vez que blocos adjacentes apresentam um grau elevado de correlação, a codificação

diferencial dos componentes DC, efetuada no passo 1, costuma gerar valores significativamente menores em módulo.

Para aumentar a probabilidade de encontrar seqüências maiores de zeros nos blocos quantificados, o codificador percorre os coeficientes no percurso em zig-zag apresentado na figura a seguir. Na figura, os números entre parênteses representam as coordenadas relativas ao bloco, e não à imagem inteira.

(0,2) (0,7) (0,6) (0,5) (0,4) (0,3) (0,1) (0,0)

(1,2)

(1,7) (1,6) (1,5) (1,4) (1,3) (1,1) (1,0)

(2,2) (2,7) (2,6) (2,5) (2,4) (2,3) (2,1) (2,0)

(3,2) (3,7) (3,6) (3,5) (3,4) (3,3) (3,1) (3,0)

(5,2) (5,7) (5,6) (5,5) (5,4) (5,3) (5,1) (5,0)

(4,2) (4,7) (4,6) (4,5) (4,4) (4,3) (4,1) (4,0)

(6,2) (6,7) (6,6) (6,5) (6,4) (6,3) (6,1) (6,0)

(7,2) (7,7) (7,6) (7,5) (7,4) (7,3) (7,1) (7,0)

Na codificação RLE de zeros do padrão JPEG, um coeficiente AC não nulo de valor a é representado em combinação com o comprimento c da seqüência de coeficientes AC nulos que o precedeu no percurso zig-zag. Cada par (c, a) é usualmente representado por um par de símbolos s1

= (c, b) e s2 = a, onde b é número de bits usado para codificar a. O símbolo s1 = (15, 0) é interpretado como uma seqüência de 16 zeros, sendo

obrigatoriamente seguido por outro símbolo s1. Seqüências de zeros de qualquer tamanho que se estendem até o final do bloco são representadas por s1 = (0,0).

47

O termo DC é similarmente estruturado, mas s1 traz apenas o número de bits usados para representar a amplitude a do coeficiente, ou seja, s1

= b e s2 = a. Analisando-se a equação que descreve a DCT bidimensional, nota-se que se os elementos da matriz de entrada do bloco DCT são inteiros de p bits no intervalo [-2p-1, 2p-1-1], os coeficientes AC quantizados se situam sempre no intervalo (-2p+2, 2p+2). Para p = 8, o padrão especifica a seguinte relação entre b e a, para os coeficientes AC: b a 1 -1, 1 2 -3, -2, 2, 3 3 -7, ..., -4, 4, ..., 7 4 -15,..., -8, 8, ... 15 5 -31, ..., -16, 16, ..., 31 6 -63, ..., -32, 32, ..., 63 7 -127, ..., -64, 64, ..., 127 8 -255, ..., -128, 128, ..., 255 9 -511, ..., -256, 256, ..., 511 10 -1023, ..., -512, 512, ..., 1023

Os coeficientes DC diferenciais podem exigir um bit a mais, ou seja, mais uma linha deve ser adicionada à tabela acima, com b = 11 para a no intervalo -2047, ... -1024, 1024, 2047.

Os símbolos s1 são finalmente codificados por Huffman ou codificação aritmética, e os símbolos s2 por um código fixo exemplificado abaixo: a Código -1 0 1 1 -3 00 -2 01 2 10 3 11 ... ...

Como ilustração, determinemos a codificação JPEG do bloco DCT quantizado:

15 0 -1 0 0 0 0 0 -2 -1 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Dados: • Valor do componente DC do bloco anterior: 12 • Código de Huffman para o s1 (DC) de valor 2: 011 • Código de Huffman para alguns símbolos s1 (AC):

48

s1 Código(0,0)

1010

(0,1)

00

(1,2)

11011

(2,1)

11100

Solução: Como o coeficiente DC do bloco anterior tem valor 12, o coeficiente DC do bloco atual será

substituído por 15-12 = 3. De acordo com a tabela apresentada anteriormente, que relaciona os valores de b e a, uma amplitude a = 3 será representada por b = 2 bits. Assim, o par (s1, s2) para este coeficiente DC é (2, 3).

No percurso zig-zag, o coeficiente AC quantizado de valor -2 é precedido por um zero. Assim, o par (s1, s2) que o representa é [(1, 2), -2]. Seguem-se então três coeficientes de valor -1 adjacentes, que são representados por três pares (s1, s2) idênticos, [(0, 1), -1], [(0, 1), -1], [(0, 1), -1]. Após estes três coeficientes de valor –1, tem-se dois zeros seguido por outro coeficiente de valor –1, que será representado pelo par (s1, s2) = [(2,1), -1]. A próxima seqüência de zeros estende-se até o fim do bloco, sendo representada pelo símbolo s1 = (0,0).

Usando as tabelas que contém o código binário fixo para as amplitudes e o código de Huffman para os símbolos s1, o bloco DCT codificado será: 011 11 11011 01 00 0 00 0 00 0 11100 0 1010. Considerando-se que a imagem original usava 8 bits por pixel, a RC resultante é de 64*8/31 = 16,5.