parte3

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

1
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Técnicas de Compactação e
Compressão
Profa. Débora Christina Muchaluat Saade
deborams@telecom.uff.br
TécnicasTécnicas dede CompactaçãoCompactação ee
CompressãoCompressão
Profa. Débora Christina Muchaluat Saade
deborams@telecom.uff.br
Departamento de Engenharia de Telecomunicações Departamento de Engenharia de Telecomunicações -- UFFUFF
2
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Técnicas de Compactação e CompressãoTécnicas de Compactação e Compressão
� Compactação X Compressão
� Classificação das técnicas de compressão
• Codificação por Entropia, na Origem e Híbrida
� Técnicas de Compactação
• Codificação por carreira
• Codificação por Shannon-Fano
• Codificação de Huffman
• Codificação de Lempel-Ziv-Welch (LZW)
• Codificação aritmética
3
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Técnicas de Compactação e CompressãoTécnicas de Compactação e Compressão
� Técnicas de Compressão
• Redução do domínio
• Redução do espaço de quantização
• Codificação preditiva
• Codificação por sub-bandas
• Codificação por transformadas
• Quantização vetorial
4
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Compactação x CompressãoCompactação x Compressão
� Compactação:
• Quando eliminamos apenas a redundância de um sinal
• Não há perda de informação
• Compressão sem perdas
• Podem ser usadas para qualquer sinal (mídia)
� Compressão:
• Quando, na redução dos dados, há perda de informação
• Compressão com perdas
• Algumas técnicas são usadas em sinais específicos
• Compressão perceptualmente sem perdas
– humanos não percebem
– Ex.: MP3 para áudio
5
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Classificação das Técnicas de CompressãoClassificação das Técnicas de Compressão
� Codificação por Entropia
• trata cadeias de bits sem levar em conta seu significado 
• técnica genérica, sem perda e totalmente reversível
– Ex.: técnicas de compactação: codificação por carreira, codificação de 
Huffman, codificação aritmética
� Codificação na Origem 
• leva em consideração a semântica dos dados
• processa o dado original distinguindo o dado relevante e o irrelevante
– removendo dados irrelevantes comprime o dado original
– Ex.: técnicas de compressão: codificação preditiva, codificação por 
sub-bandas, codificação por transformadas, quantização vetorial
� Codificações Híbridas
• Combinam técnicas com e sem perdas (várias técnicas são agrupadas 
para formar uma nova técnica de codagem)
– Ex.: JPEG, MPEG, H.263, ...
6
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
CompactaçãoCompactação
� Codificação por carreira (Run Length Coding)
� Técnica boa quando informação se repete
� OBS.: Toda técnica de compactação pode diminuir ou 
aumentar o volume de dados
7
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação por ShannonCodificação por Shannon--FanoFano
� A seqüência a ser compactada deve ser analisada previamente, 
identificando-se os caracteres e suas respectivas 
freqüências/probabilidades
� Ordene os símbolos de acordo com suas freqüências. Ex.: ABCDE
� Divida recursivamente em 2 partes, cada uma com 
aproximadamente o mesmo número de contagem
8
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação por ShannonCodificação por Shannon--FanoFano
� Seqüência ABDEACD...
• 00 01 110 111 00 10 110 ...
� Envia:
• símbolos
• árvore
• seqüência
9
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação de HuffmanCodificação de Huffman
� Codificação Estatística 
� A seqüência a ser compactada deve ser analisada 
previamente, identificando-se os caracteres e suas 
respectivas freqüências/probabilidades 
� Atribui menos bits a símbolos que aparecem mais 
freqüentemente e mais bits para símbolos que 
aparecem menos
10
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação de HuffmanCodificação de Huffman
� Algoritmo:
• Insira os nós (símbolos/freqüências) em uma lista
• Repita até que a lista contenha apenas um nó:
– Selecione os dois nós de mais baixa freqüência e crie 
um nó pai para ambos
– Atribua ao nó pai a soma das freqüências e insira-o na 
lista
– Atribua os códigos 0 e 1 aos dois ramos da árvore e 
retire os filhos da lista
11
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Exemplo Exemplo -- HuffmanHuffman
151115E
181106D
181016C
211007B
15015A
Subtotal
(# de bits)
CódigoFreqüênciaSímbolo
Total (# de bits) = 87
Compactação = 117 : 87
� Seqüência ABDEACD...
• 0 100 110 111 0 101 110 ...
13
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Huffman Huffman -- DecodificaçãoDecodificação
14
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação de HuffmanCodificação de Huffman
� Nem todos os caracteres precisam ter uma 
representação codificada na tabela de Huffman
• apenas os caracteres com alta probabilidade de 
ocorrência
• demais são codificados diretamente e marcados com 
flag especial
� Técnica útil quando o número de caracteres 
diferentes é muito grande mas apenas alguns 
deles têm uma alta probabilidade de ocorrência
15
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação AritméticaCodificação Aritmética
� Utiliza um único código por string de caracteres codificada
� A seqüência a ser compactada deve ser analisada previamente, 
identificando-se os caracteres e suas respectivas 
freqüências/probabilidades
• Ex.: e=0.3; n=0.3; t=0.2; w=0.1; .=0.1
� Precisa de um caracter marcando o fim de cada seqüência (.)
� Algoritmo:
• Dividir o intervalo de [0, 1] de acordo com a probabilidade de ocorrência 
de cada caracter na seqüência
• Repita até o caracter de fim de seqüência
– Escolha o intervalo correspondente ao próximo caracter e divida-o 
novamente de acordo com as probabilidades iniciais
• O código pode ser qualquer número dentro do último intervalo 
encontrado (ValorInicial <= código < ValorFinal)
16
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Exemplo Exemplo –– Codificação AritméticaCodificação Aritmética
17
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação AritméticaCodificação Aritmética
� O número de dígitos decimais no código aumenta 
linearmente com o número de caracteres na 
string
• O número máximo de caracteres em uma string é 
determinado pela precisão com a qual números de 
ponto flutuante são representados nos 
computadores de origem e destino
• Por essa razão, mensagens completas devem ser 
fragmentadas em várias strings menores e cada 
string deve ser codificada separadamente
18
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação de LempelCodificação de Lempel--ZivZiv
� Codificação de Lempel-Ziv (LZ)
• Ao invés de utilizar caracteres como a base da codificação, 
utiliza strings de caracteres
• É baseada na construção de um dicionário de frases (grupos 
de um ou mais caracteres) a partir do fluxo de entrada
• Quando uma nova frase é encontrada
– Ela é adicionada ao dicionário
• Se a frase encontrada já foi registrada
– ela é substituída pelo código no dicionário
• Esta técnica é boa para compressão de arquivos textos, onde 
temos uma grande repetição de frases
– exemplo em português: "ela", "Contudo", "onde" 
19
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação de LempelCodificação de Lempel--ZivZiv
� Codificação Lempel-Ziv (LZ)
• Exemplo de taxa de compactação
– suponha que temos um arquivo
de 10000 caracteres
– se nós representarmos o arquivo usando 8 bits por caracter, o 
arquivo requer 80000 bits para representá-lo
– assumindo que o arquivo tenha 2000 palavras ou frases das 
quais 500 são diferentes
• necessitamos de 9 bits como token para identificar cada palavra 
ou frase
• precisamos de 9*2000 bits para codificar o arquivo
– obtemos uma taxa de compressão de 80000:18000 (4,4)
• na prática, o dicionário também deve ser mantido/enviado
– baixando a taxa de compressão obtida
20
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Algoritmo LempelAlgoritmo Lempel--ZivZiv
� Primeiro passo: inicializar uma tabela de códigos com todos os 
caracteres existentes na string que pretendemos compactar
� A codificação se inicia definindo a seqüência de símbolos corrente S 
como o primeiro símbolo a codificar
� 1. Se não existem mais símbolos para codificar, dê como saída o 
código de S. Em caso contrário,
� 2. Pegue o próximo símbolo P e concatene a S, obtendo a nova 
seqüência SP
� 3. Se SP já estiver no dicionário, faça S = SP e volte para o passo 1. 
Em caso contrário,
� 4. Dê como saída o código de S
� 5. Adicione SP ao dicionário, se ainda houver espaço
� 6. Faça S = P e volte para o passo 1
21
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Exemplo de LempelExemplo de Lempel--ZivZiv
� Exemplo de compactação LZW
• Compressão da cadeia de caracteres ABACABA
• Primeiro passo: inicializar uma tabela de códigos com todos os 
caracteres existentes na string que pretendemos compactar: 
– #0 = A, #1 = B, #2 = C
• Caracter A (existe na tabela)
– representamos A por #0 
– AB recebe #3
• Caracter B (existe na tabela)
– representamos AB por #0#1
– BA recebe #4
• Caracter A (existe na tabela)
– representamos ABA por #0#1#0
– junta AC na tabela com índice #5
22
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Exemplo de LempelExemplo de Lempel--ZivZiv
� Exemplo de compressão LZW
• Compressão da cadeia de caracteres ABACABA
• Tabela atual: 
– #0 = A, #1 = B, #2 = C, #3 = AB, #4 = BA, #5 = AC
• Caracter C (existe na tabela)
– representamos ABAC por #0#1#0#2
– CA recebe #6
• Caracter AB (existe na tabela)
– representamos ABACAB por #0#1#0#2#3
– ABA recebe #7
• Caracter A (existe na tabela)
– representamos ABACABA por #0 #1 #0 #2 #3 #0
23
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação de LempelCodificação de Lempel--ZivZiv--Welch (LZW)Welch (LZW)
� Codificador e decodificador constroem o 
conteúdo do dicionário dinamicamente enquanto 
o texto é processado
� Inicialmente, o dicionário contém somente o 
conjunto de caracteres que foi usado na 
construção do texto (ex. ASCII 7 bits)
� As entradas restantes são utilizadas para 
codificar palavras que ocorrem no texto
� Exemplo: 
• This is simple as it is ...
24
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Exemplo de LempelExemplo de Lempel--ZivZiv--WelchWelch
25
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Exemplo de LempelExemplo de Lempel--ZivZiv--WelchWelch
26
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Algoritmo Algoritmo LZ77LZ77
� Variação do LZW usado em vários compactadores 
comerciais
• PKZIP/PKUNZIP (para o DOS)
• ARJ
• GZIP/GUNZIP 
• Compress/Uncompress (para o UNIX)
� Princípio de funcionamento:
• Em uma seqüência de caracteres, o algoritmo procura na 
janela corrente a maior sub-seqüência que casa com o início 
do lookahead buffer e dá como saída um ponteiro para o 
início da sub-seqüência na janela e o primeiro caracter no 
lookahead buffer que não casa com a seqüência. Se não 
houver sub-seqüência, a saída é um ponteiro nulo e o 
caracter na posição atual da seqüência original.
27
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Algoritmo Algoritmo LZ77LZ77
� Termos utilizados no algoritmo:
• Seqüência de entrada
– Seqüência de caracteres a ser comprimida
• Caracter:
– Elemento básico da seqüência de entrada
• Posição atual:
– Posição do caracter na seqüência de entrada que está sendo 
codificado no momento (início do lookahead buffer)
• Lookahead buffer:
– Seqüência de caracteres a partir da posição atual até o fim da 
seqüência de entrada
28
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Algoritmo Algoritmo LZ77LZ77
� Termos utilizados no algoritmo:
• Janela:
– Janela de tamanho W contém W caracteres a partir da 
posição atual em direção ao início da seqüência de 
entrada, i.e. os últimos W caracteres processados
• Ponteiro:
– Um ponteiro aponta para a seqüência que casa na 
janela e também indica seu comprimento (L)
29
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Algoritmo Algoritmo LZ77LZ77
� Algoritmo:
1. Faça posição atual igual ao início da seqüência de entrada
2. Encontre a maior sub-seqüência (longest match) na janela 
que casa como conteúdo do lookahead buffer
3. Dê como saída o par (P,C), onde:
• P é o ponteiro para a sub-seqüência na janela
• C é o primeiro caracter no lookahead buffer que não casa com 
a sub-seqüência
4. Se o lookahead buffer não estiver vazio, mova a posição 
atual (e a janela) L+1 caracteres para frente e volte para o 
passo 2 (L é o comprimento da sub-seqüência).
30
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Algoritmo Algoritmo LZ77LZ77
� Exemplo: seqüência AABCBBABC
� Processo de Codificação
CBABBCBAAChar
987654321Pos
(5,2) CCAB75
(2,1) BBB54
(0,0) CC--43
(1,1) BBA22
(0,0) AA--11
SaídaCharMatchPosStep
31
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Algoritmo Algoritmo LZ77LZ77
� Decodificação:
• A janela é mantida da mesma forma que na codificação.
• Em cada passo, o algoritmo lê o par (P,C) da entrada e dá 
como saída a seqüência da janela a partir de P seguida do 
caracter C
� Exemplo: (0,0)A (1,1)B (0,0)C (2,1)B (5,2)C
1. (0,0)A => W = nula, saída = A
2. (1,1)B => W = A, saída = AAB
3. (0,0)C => W = AAB, saída = AABC
4. (2,1)B => W = AABC, saída = AABCBB
5. (5,2)C = > W = AABCBB, saída = AABCBBABC
32
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Algoritmo Algoritmo LZ77LZ77
� Considerações principais:
• Boa taxa de compressão para vários tipos de dados
• Codificação pode ser lenta, já que várias 
comparações são feitas entre o lookahead buffer a a 
janela 
• Decodificação muito simples e rápida
• Requisitos de memória são poucos tanto para 
codificação quanto para decodificação
– A única estrutura mantida em memória é a janela, que 
normalmente tem tamanho entre 4 e 64 KB.
33
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Técnicas de CompressãoTécnicas de Compressão
� Compressão:
• Quando, na redução dos dados, há perda de informação
• Compressão com perdas
• Algumas técnicas são usadas em sinais específicos
• Compressão perceptualmente sem perdas
– humanos não percebem
– Ex.: MP3 para áudio
� Técnicas
• Redução do domínio
• Redução do espaço de quantização
• Codificação preditiva
• Codificação por sub-bandas
• Codificação por transformadas
• Quantização vetorial
34
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Redução do DomínioRedução do Domínio
� Idéia básica
• Simplesmente descarta algumas amostras
� Ex.: padrões para vídeo digital 
• Formatos 4:2:2, 4:2:0
• Informações de luminância são mais importantes 
que crominância, então o número de amostras de 
crominância pode ser menor
� Ex.: compressão em imagens 
• diminui a resolução geométrica
• aumenta o tamanho do pixel
35
Fundamentos de Sistemas MultimídiaFundamentos
de Sistemas Multimídia
Redução do domínio em imagensRedução do domínio em imagens
36
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Redução do Espaço de QuantizaçãoRedução do Espaço de Quantização
� Idéia básica
• Diminuir a quantidade de bits por amostra
� Ex.: compressão de imagens
• Imagem original com 24 bits por pixel (16 milhões 
de cores)
• Imagem comprimida com 8 bits por pixel (256 
cores) fazendo uma correspondência entre os 
códigos
37
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação PreditivaCodificação Preditiva
� Codificação diferencial ou codificação relativa
� Idéia básica
• Amplitude de uma amostra é grande, mas a diferença de 
amplitude entre amostras sucessivas é relativamente 
pequena
• Ao invés de codificar o valor de cada amostra, codifica a 
diferença entre seu valor e o anterior
– Utiliza menos bits e obtém o mesmo erro
• Ex.: 
– DPCM (Differential Pulse Code Modulation)
– ADPCM (Adaptive Differential Pulse Code Modulation)
38
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação por SubCodificação por Sub--BandasBandas
� Idéia básica
• Divisão da banda passante do sinal em várias sub-bandas codificadas de 
forma distinta
• Trata com maior precisão as sub-bandas mais importantes do sinal
� Por exemplo, sinal de voz:
• 300-800Hz – qualidade e timbre
– 8 bits por amostra
• 800-1400Hz – pouca informação
– 2 bits por amostra
• 1400-2400Hz – reconhecimento e intelegibilidade
– 8 bits por amostra
– Maior informação de conteúdo (ex.: voz metálica)
• 2400-3400Hz – pouca informação
– 3 bits por amostra
40
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação por TransformadasCodificação por Transformadas
� Idéia básica
• Transformar os dados para outro domínio matemático onde 
uma técnica de compressão seja melhor aplicada
– Ex.: Transformada de Fourier => transforma sinais no domínio 
do tempo para o domínio da freqüência
• Deve existir uma transformada inversa
• Transformadas eficazes para redução de dados são:
– DCT – Discrete Cosine Transform (JPEG)
– FFT – Fast Fourier Transform (MPEG-áudio)
42
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Transformadas em ImagensTransformadas em Imagens
� Existem várias similaridades entre amostras (no 
tempo) e pixels. Na verdade, podemos considerar 
os pixels como se fossem amostras do “sinal 
imagem”, só que amostras obtidas não no tempo, 
mas no espaço.
� É exatamente por isso que podemos aplicar todas 
as técnicas aplicadas em sinais contínuos nas 
imagens estáticas.
43
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação por TransformadasCodificação por Transformadas
44
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação por TransformadasCodificação por Transformadas
45
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Quantização VetorialQuantização Vetorial
� Fluxo de dados é divido em 
blocos
� Constrói uma tabela (ou usa 
uma predefinida) contendo o 
conjunto de valores que mais 
aparecem (valores padrões)
� Para cada bloco, a tabela é 
consultada para achar o padrão 
mais parecido
� Então cada bloco é codificado 
com o índice do vetor
� O decodificador deve conhecer a 
mesma tabela e usa os índices 
para gerar uma aproximação do 
fluxo de dados original
46
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Mídia Texto
Profa. Débora Christina Muchaluat Saade
deborams@telecom.uff.br
Mídia TextoMídia Texto
Profa. Débora Christina Muchaluat Saade
deborams@telecom.uff.br
Departamento de Engenharia de Telecomunicações Departamento de Engenharia de Telecomunicações -- UFFUFF
47
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Compressão de TextoCompressão de Texto
� Texto não tolera erros 
� Compactação = Compressão sem perdas
� Classificação das técnicas de compactação:
• Técnicas que usam caracteres únicos como base X 
Técnicas que usam strings de caracteres como base
• Codificação estática X Codificação dinâmica
48
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Compressão de TextoCompressão de Texto
� Técnicas que usam caracteres únicos como base
• Codificação por carreira
– Só usa se repetir no mínimo 4 vezes 
• (caracter, símbolo (!), número de vezes)
– entrada: ABCCCCCCCCDEFGGG
– saída: ABC!4DEFGGG
• Codificação de Shannon-Fano
• Codificação aritmética
• Codificação de Huffman
49
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Compressão de TextoCompressão de Texto
� Técnicas que usam strings de caracteres como base
• Codificação por carreira
– pode-se substituir seqüências maiores que um
– requer que o tamanho da seqüência seja codificado ou pode-se 
usar um caracter especial de fim 
• (símbolo (!), número de vezes, seqüência, delimitador de fim ($))
– entrada: UFYUGDUFHUFHUFHUFHUFHBFD
– saída: UFYUGD!5UFH$BFD
– Se símbolos especiais aparecerem nos dados (character stuffing)
• entrada: U!HIIIIID
• saída: U!!HI!1D
• Codificação de Lempel-Ziv-Welch
50
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Compressão de TextoCompressão de Texto
� Codificação estática
• Tabelas de códigos são conhecidas a priori (padronizadas)
• Tabelas de códigos são enviadas junto com a seqüência codificada
• Exemplos:
– Codificação de Shannon-Fano
– Codificação aritmética
– Codificação de Huffman
– Codificação de Lempel-Ziv
� Codificação dinâmica
• Tabelas de códigos são calculadas dinamicamente no momento da 
decodificação
• Exemplos:
– Codificação de Lempel-Ziv-Welch 
– Codificação de Huffman dinâmica
51
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação de Huffman DinâmicaCodificação de Huffman Dinâmica
� A árvore de Huffman é construída 
dinamicamente na codificação e na decodificação
� Não é necessário saber a freqüência dos símbolos 
a priori
� Se o caracter não estiver presente na árvore 
ainda (da primeira vez que aparece), ele não é 
compactado
� Usa o conceito de uma folha vazia que representa 
o local onde o próximo caracter será inserido na 
árvore
52
Fundamentos de Sistemas MultimídiaFundamentos de Sistemas Multimídia
Codificação de Huffman DinâmicaCodificação de Huffman Dinâmica