Notas de aula da disciplina Introducao à Teoria da Informacao

Notas de Aula da Disciplina
Introdução à
Teoria da Informação
Leonardo Vidal Batista
2005
1
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
2
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.
3
Fonte
De
Informação
Mensagem
M
Transmissor
Sinal
s
Canal
Destinatário
Da
Informação
Mensagem
~
M
Receptor
Ruído
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.
4
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
0
1
2
3
4
5
6
7
8
9
ASCII
3016
3116
3216
3316
3416
3516
3616
3716
3816
3916
Binário 1
00002
00012
00102
00112
01002
01012
01102
01112
10002
10012
Binário 2
002
012
102
11002
11012
11102
1111002
1111012
1111102
1111112
Binário 3
1111112
1111102
1111012
1111002
11102
11012
11002
102
012
002
Octal
008
018
028
038
048
058
068
078
108
118
Alfabético
a
f
k
m
n
b
z
x
p
s
Nos códigos da tabela acima, a cada possível símbolo de saída da fonte corresponde uma palavracó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.
5
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
000
22
0
1
2
3
4
5
6
7
8
9
1.2
Palavra-Código
00002
00012
00102
00112
01002
01012
01102
01112
10002
10012
10102
10112
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
6
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
7
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 palavracó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.
8
Tabela 3. Um código binário para as vogais
Vogal
a
e
i
o
u
Palavra-Código
11
000
110
001
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
a
e
i
o
u
Palavra-Código
102
0002
1102
0012
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
32
103
0
1
...
255
Palavra-Código
12
012
0000000000
0000000001
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.
9
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
A
B
C
D
E
F
G
H
I
J
K
L
M
N
Palavra-Código
0012
00002
011012
01112
01100102
01100112
112
10102
1002
0102
000102
10112
0110002
000112
10
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) = log 2
1
bits
P( x = ai )
Se x1x2. . .xN-1 são os elementos gerados por S, a entropia da fonte é definida como
1
G N bits/símbolo
N →∞ N
H ( S ) = lim
onde
M −1M −1
M −1
i0 = 0 i1 = 0
i N −1 = 0
GN = − ∑ ∑ ...
∑ P( x
0
= ai0 , x1 = ai1 ,..., xN −1 = ai N −1 ) log2 P( x0 = ai0 , x1 = ai1 ,..., xN −1 = ai N −1 )
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:
M −1
H ( S ) = − ∑ P ( x = ai ) log 2 P( x = ai ) bits /símbolo
i =0
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:
H =−
1
400
200
1
(400. log
+ 200. log
+ 254.1. log
) = 3,90 bits/símbolo
2
2
2
854
854
854
854
Como, no exemplo citado, R = 3,91 bits/símbolo, o código se aproxima muito do melhor
resultado possível.
11
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.
12
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:
13
k
~
xi = ∑ a j xi − j
j =1
onde ~
xi é 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.
14
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.
15
O algoritmo de Huffman pode ser usado em conjunção com os modelos semi-adaptativos, nãoadaptativos 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
16
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
s
a
i
n
r
Probabilidade
4/10
3/10
1/10
1/10
1/10
Faixa
[0, 0.4)
[0.4, 0.7)
[0.7, 0.8)
[0.8, 0.9)
[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
a
s
s
a
s
s
i
n
a
r
li
0.0
0.0 + 1.0 * 0.4 = 0.4
0.4 + 0.3 * 0.0 = 0.4
0.4 + 0.12 * 0.0 = 0.4
0.4+0.048*0.4=0.4192
0.4192
0.4192
0.4208128
0.42099712
0.421006336
0.4210125568
hi
1.0
0.0 + 1.0 * 0.7 = 0.7
0.4 + 0.3 * 0.4 = 0.52
0.4 + 0.12 * 0.4=0.448
0.4+0.048*0.7=0.4336
0.42496
0.421504
0.4210432
0.42102016
0.421013248
0.421013248
ri
1.0
0.3
0.12
0.048
0.0144
0.00576
0.002304
0.0002304
0.00002304
0.000006912
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
17
a
s
s
a
l(a)
l(a) + r(a).l(s)
l(a) + r(a).l(s) + r(a).r(s).l(s)
...
h(a)
l(a) + r(a).h(s)
l(a)+r(a).l(s)+ r(a).r(s).r(s)
...
r(a)
r(a).r(s)
r(a).r(s).r(s)
...
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
0.421013
0.070043333
0.175108333
0.437770833
0.125902777
0.314756944
0.786892361
0.86892361
0.689236108
0.96412036
Símbolo
a
s
s
a
s
s
i
n
a
r
lsi
0.4
0.0
0.0
0.4
0.0
0.0
0.7
0.8
0.4
0.9
rsi
0.3
0.4
0.4
0.3
0.4
0.4
0.1
0.1
0.3
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.
•
18
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.
a
• Quando hi e li coincidem na 1 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
A
s
S
a
s
s
i
n
a
r
low
0.0
0.4
0.4
0.4
0.0
0.192
0.192
0.192
0.208128
0.08128
0.099712
0.1006336
0.06336
0.125568
0.25568
high
1.0
0.7
0.52
0.448
0.48
0.336
0.2496
0.21504
0.210432
0.10432
0.102016
0.1013248
0.13248
0.13248
0.3248
range
1.0
0.3
0.12
0.048
0.48
0.144
0.0576
0.02304
0.002304
0.02304
0.002304
0.0006912
0.06912
0.006912
0.06912
saída
4
2
10
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
19
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?
20
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.
21
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.
0
8
16
24
32
40
48
56
Segmentos são os componentes do programa. Finalm ente, programas
dicionário
área de
previsão
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
22
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:
8
0
16
24
32
40
Segmentos são os
Terno de saída: 0, ‘S’
8
0
16
24
32
40
S egmentos são os
Terno de saída: 0, ‘e’
8
0
16
24
32
40
Se gmentos são os c
Terno de saída: 0, ‘g’
8
0
16
24
32
40
Seg mentos são os co
Terno de saída: 0, ‘m’
8
0
16
24
32
40
Segm entos são os com
Terno de saída: 1, 45, ‘n’
8
0
16
24
32
40
Segmen tos são os compo
Terno de saída: 0, ‘t’
(. . .)
0
8
16
24
32
40
Segmentos são os componentes do programa. Finalm ente, programas
Coincidências: (n = 1, i = 1); (n = 3, i = 4) e (n = 4, i = 23)
23
Terno de saída: 4, 23, ‘,’
0
8
16
24
32
40
ntos são os componentes do programa. Finalmente, programas são c
Terno de saída: 9, 26, ‘s’
0
8
16
24
32
40
s componentes do programa. Finalmente, programas 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:
0
Lê-se 0, ‘S’ Æ Decodifica-se ‘S’
16
8
24
32
40
S
0
Lê-se 0, ‘e’ Æ Decodifica-se ‘e’
16
8
24
32
40
Se
0
Lê-se 0, ‘g’ Æ Decodifica-se ‘g’
16
8
24
32
40
Seg
0
Lê-se 0, ‘m’ Æ Decodifica-se ‘m’
16
8
24
32
40
Segm
0
Lê-se 1, 45, ‘n’ Æ Decodifica-se ‘en’
16
8
24
32
40
Segmen
(. . .)
24
Lê-se 4, 23, ‘,’ Æ Decodifica-se ‘ente,’
16
8
24
32
40
0
ntos são os componentes do programa. Finalmente,
(. . .)
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 ‘’
1 ‘S’
10 ‘sã’
11 ‘o ’
20 ‘o p’
21 ‘r’
30 ‘l’
31 ‘me’
40 ‘ã’
41 ‘o c’
25
2 ‘e’
3 ‘g’
4 ‘m’
5 ‘en’
6 ‘t’
7 ‘o’
8 ‘s’
9 ‘ ’
12
13
14
15
16
17
18
19
‘os’
‘ c’
‘om’
‘p’
‘on’
‘ent’
‘es’
‘ d’
22
23
24
25
26
27
28
29
‘og’
‘ra’
‘ma’
‘.’
‘ F’
‘i’
‘n’
‘a’
32
33
34
35
36
37
38
39
‘nt’
‘e,’
‘ p’
‘ro’
‘g’
‘ram’
‘as’
‘ s’
42
43
44
45
‘omp’
‘ost’
‘os ’
‘ta’
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’
26
2 - ‘e’
5 - ‘m’
6. ‘t’ Æ Sáida: 0, ‘t’
Dicionário
0 - ‘’
3 - ‘en’
1 - ‘S’
4 - ‘g’
2 - ‘e’
5 - ‘m’
7. ‘o’ Æ Sáida: 0, ‘o’
Dicionário
0 - ‘’
3 - ‘en’
1 - ‘S’
4 - ‘g’
2 - ‘e’
5 - ‘m’
6 - ‘t’
6 - ‘o’
7 - ‘t’
8. ‘s’ Æ Sáida: 0, ‘s’
Dicionário
0 - ‘’
3 - ‘en’
1 - ‘S’
4 - ‘g’
2 - ‘e’
5 - ‘m’
6 - ‘o’
7 - ‘s’
8 - ‘t’
9. ‘ ’ Æ Sáida: 0, ‘ ’
Dicionário
0 - ‘’
3 - ‘e’
1-‘ ’
4 - ‘en’
2 - ‘S’
5 - ‘g’
6 - ‘m’
7 - ‘o’
8 - ‘s’
9 - ‘t’
10. ‘sã’ Æ Saída: 8, ‘ã’
Dicionário
0 - ‘’
3 - ‘e’
1-‘ ’
4 - ‘en’
2 - ‘S’
5 - ‘g’
6 - ‘m’
7 - ‘o’
8 - ‘s’
9 - ‘sã’
10 - ‘t’
6 - ‘m’
7 - ‘o’
8 - ‘o ’
9 - ‘s’
10 - ‘sã’
11 - ‘t’
11. ‘o ’ Æ Saída: 7, ‘ ’
Dicionário
0 - ‘’
3 - ‘e’
1-‘ ’
4 - ‘en’
2 - ‘S’
5 - ‘g’
(. . .)
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
27
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.
28
Dicionário:
0 ‘ ’
1 ‘,’
2 ‘.’
3 ‘F’
4 ‘S’
5 ‘a’
6 ‘c’
7 ‘d’
8 ‘e’
9 ‘g’
10
11
12
13
14
15
16
17
18
19
‘i’
‘l’
‘m’
‘n’
‘o’
‘p’
‘r’
‘s’
‘t’
‘ã’
20
21
22
23
24
25
26
27
28
29
‘Se’
‘eg’
‘gm’
‘me’
‘en’
‘nt’
‘to’
‘os’
‘s ’
‘ s’
30
31
32
33
34
35
36
37
38
39
‘sã’
‘ão’
‘o ’
‘ o’
‘os ’
‘ c’
‘co’
‘om’
‘mp’
‘po’
40
41
42
43
44
45
46
47
48
...
‘on’
‘ne’
‘ent’
‘te’
‘es’
‘s d’
‘do’
‘o p’
‘pr’
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:
29
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.
30
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;
}
}
31
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).
32
Codificadores
Baseados em
Dicionários
Estatísticos
Huff
R=4,99
P=18
LZJ
R=4,00
P=12
LZ77
R=3,94
P=11
LZ78
R=4,13
P=15
LZR
R=4,12
P=14
LZSS
R=3,43
P=9
LZW
R=4,71
P=17
LZB
R=3,18
P=5
LZH
R=3,30
P=7
LZC
R=4,26
P=16
DAFC
R=4,02
P=13
WORD
R=2,76
P=3
LZMW
R=3,32
P=8
PPMC
R=2,48
P=1
DMC
R=2,74
P=2
MTF
R=3,24
P=6
LZFG
R=2,95
P=4
LZT
R= 3,76
P=10
33
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.
34
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:
2
Xk =  
N
1/ 2
N −1
 ( 2n + 1) kπ 
c k ∑ x n cos 
 , k = 0 ,1,...,N − 1
2N

n =0
onde
(1/2 )1/2
ck = 
1
para k = 0
para k = 1, 2, ...N - 1
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:
2
xn =  
N
1 / 2 N −1
∑c
k =0
k
 (2n + 1)kπ 
X k cos 
, n = 0,1,...,N − 1
 2N
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 taxadistorçã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.
35
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:
X kl =
N −1 N −1
 (2m + 1)kπ   (2n + 1)lπ 
ck cl ∑∑ xmn cos
 cos 2N  , k, l = 0, 1,..., N-1
2
N
2N


 
m=0 n=0
1
onde
(1/2)1/2
ck = 
1
para k = 0
para k = 1, 2, ...N - 1
A seqüência original pode ser recuperada aplicando-se a DCT bidimensional inversa:
xmn =
5.1.2
1
N −1 N −1
 (2k +1)mπ   (2l +1)nπ 
cos
2N   2N 
∑∑ck cl X kl cos
2N
k =0 l =0
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
36
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:
rk =
d k + d k +1
2
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.
37
Pode-se elaborar um pouco mais o processo empregando quantização com zona morta, dada
por
0
xˆ = 
 x // q
se |x| < t
caso contrário
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:
D( v i , c k ) =
1 L −1
∑ (vij − ckj ) 2
L j =0
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á
38
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) = (1 − ρ)ρ n
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 =
ρ
(1 − ρ) 2
Para distribuições geométricas unilaterais, definindo-se o parâmetro m como
 log(1 + ρ) 
m= 
-1 
 log ρ 
o código de Golomb produz o menor comprimento médio dentre todos os códigos unicamente
decodificáveis.
39
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
1 −β
f ( x) =
e
2β
com β > 0. A distribuição geométrica bilateral é dada por
P(x = n) =
(1 − ρ)ρ
2
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:
2 n
M ( n) = 
2 n - 1
n≥0
n<0
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.
40
Tabela 5.1. Exemplos de códigos de Golomb e de Golomb-Rice.
n
m =1
m =2
k=0
k=1
0
0
00
00
1
10
01
2
110
3
m =5
m =6
m =7
000
000
000
000
010
001
001
001
0010
100
011
010
010
0100
0011
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
m =4
m=3
k=2
...
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
x
blocos bi
Transformada
Inversa
Transformada
~
Bi
Bi
Quantização
B̂
Dequantização
B̂
i
Codificação
x
Canal
x
i
Decodificação
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
41
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
5.2.1
O PADRÃO JPEG
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 (0,0)
 f (1,0)
f= 

...

 f ( L − 1,0)
f (0,1)
f (1,1)
...
f ( L − 1,1)
...
...
...
...
f (0, C − 1) 
f (1, C − 1) 

...

f ( L − 1, C − 1)
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]:
140 2 255 190...
 0
1
8 205...

F =  46 15 70 77... 


188 89 120 155...

...
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:
42
140 2 255 190...
 0
1
8 205...

F =  46 15 70 77... 


188 89 120 155...

...
62... 
− 126 127
 12
− 128 − 127 − 120 77... 


F’ =  − 82 − 113 − 58 − 51...


27... 
− 39
−8
 60

...
Apresentamos abaixo alguns trechos de dimensões 4 x 4 e a DCT correspondente.
140
144
F= 
152

168
144
152
155
145
147
140
136
156
140
147
167

148
2,09
5,48 − 3,74
 58,87
− 13,21 − 3,90 − 8,78 − 3,42

DCT = 
 − 0,88 4,47 − 4,07 14,03 


− 4,83 4,21 − 5,65
 1,84
140
144
F= 
152

168
140
144
152
168
140
144
152
168
140
144
152

168
 65,05
− 28,93
DCT = 
 8,49

 − 3,32
0
0
0
0
0
0
0
0
0
0
0

0
140
168
F= 
144

152
140
168
144
152
140
168
144
152
140
168
144

152
 65,05
 − 1,90
DCT = 
 − 14,14

− 26,77
0
0
0
0
0
0
0
0
0
0
0

0
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
43
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.
3 5 7 9 
5 7 9 11


7 9 11 13


9 11 13 15
11
21

31

41
21
31
41
51
31
41
51
61
41
51
61

71
Tem-se a seguir uma das matrizes de quantização sugerida pelo JPEG:
16
12
14
14
18
24
49
72
11
12
13
17
22
35
64
92
10
14
16
22
37
55
78
95
16 24 40
19 26 58
24 40 57
29 51 87
56 68 109
64 81 104
87 103 121
98 112 100
51 61
60 55
69 56
80 162
103 77
113 92
120 101
103 99
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:
139
144
150
159
159
161
162
162
Bloco 8x8 da imagem original
144 149 153 155 155 155
151 153 156 159 156 156
155 160 163 158 156 156
161 162 160 160 159 159
160 161 162 162 155 155
161 161 161 160 157 157
162 161 163 162 157 157
162 161 161 163 158 158
155
156
156
159
155
157
157
158
DCT do bloco anterior subtraído de 128
235,6 − 1,0 − 12,1 − 5,2 2,1 − 1,7 − 2,7 1,3
− 22,6 − 17,5 − 6,2 − 3,2 − 2,9 − 0,1 0,4 − 1,2
− 10,9 − 9,3 − 1,6 1,5
0,2 − 0,9 − 0,6 − 0,1
− 7,1 − 1,9
0,2
1,5
0,9 − 0,1 0,0
0,3
− 0,6 − 0,8
1,5
1,6 − 0,1 − 0,7 0,6
1,3
1,8
− 0,2
1,6
− 0,3 − 0,8 1,5
1,0 − 1,0
− 1,3 − 0,4 − 0,3 − 1,5 − 0,5 1,7
1,1 − 0,8
− 2,6
1,6
− 3,8 − 1,8 1,9
1,2 − 0,6 − 0,4
44
Bloco DCT Quantizado
15 0 − 1 0 0 0 0
− 2 −1 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
0
0
Bloco DCT Dequantizado
240
0
− 10 0 0 0 0
− 24 − 12 0 0 0 0 0
− 14 − 13 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
144
148
155
160
163
163
160
158
146
150
156
161
163
164
161
159
Bloco reconstruído
149 152 154 156
152 154 156 156
157 158 158 157
161 162 161 159
164 163 162 160
164 164 162 160
162 162 162 161
161 161 162 161
0
0
0
0
0
0
0
0
156
156
156
157
158
158
159
159
156
156
155
155
156
157
158
158
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 :
 1 R C
~
f (i, j ) − f (i, j )
Erms = 
∑∑
 RC i =0 j =0
(
2
)
1/ 2

45
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,0)
(0,1)
(0,2)
(0,3)
(0,4)
(0,5)
(0,6)
(0,7)
(1,0)
(1,1)
(1,2)
(1,3)
(1,4)
(1,5)
(1,6)
(1,7)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(2,5)
(2,6)
(2,7)
(3,0)
(3,1)
(3,2)
(3,3)
(3,4)
(3,5)
(3,6)
(3,7)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)
(4,5)
(4,6)
(4,7)
(5,0)
(5,1)
(5,2)
(5,3)
(5,4)
(5,5)
(5,6)
(5,7)
(6,0)
(6,1)
(6,2)
(6,3)
(6,4)
(6,5)
(6,6)
(6,7)
(7,0)
(7,1)
(7,2)
(7,3)
(7,4)
(7,5)
(7,6)
(7,7)
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).
46
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
-1
1
-3
-2
2
3
...
Código
0
1
00
01
10
11
...
Como ilustração, determinemos a codificação JPEG do bloco DCT quantizado:
15
-2
-1
0
0
0
0
0
0
-1
-1
0
0
0
0
0
-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
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):
47
s1
(0,0
)
(0,1
)
(1,2
)
(2,1
)
Código
1010
00
11011
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.
48