Módulo 6 – Compressão de
Imagem e Som
Sistema Multimédia
Ana Tomé
José Vieira
Departamento de Electrónica, Telecomunicações e
Informática
Universidade de Aveiro
Módulo 6 – Compressão de Imagem e Som
1
Sumário
• Codificação sem Perdas (continuação)
– RLE- Run length encoder
– Codificadores com dicionário (Lempel-Ziv-Welch)
• Codificação com Perdas para Imagem
– Estrutura geral do codificador
– Exemplo do JPEG em imagem
• Codificação com Perdas para Som
– Redundância e Irrelevância
– DPCM
– MPEG áudio
Módulo 6 – Compressão de Imagem e Som
2
Codificadores sem perdas
• Codificadores de símbolos
– Probabilísticos
– Exemplo: codificador de Huffman
• Codificadores de sequências de símbolos
– RLE- Run- length encoding
– Com dicionários : códigos associados a sequências
de símbolos de comprimento variável
– Exemplos: LZ77 e Lempel-Ziv-Welch (LZW).
Módulo 6 – Compressão de Imagem e Som
3
Run-Length Encoding
• Contar o número de ocorrências de um símbolo
• Codificar: símbolo e número de ocorrências do
símbolo
Ex1: AAAAAAAAAAAAABBBBAAAAA
Sequência Codificada:
A13 B4 A5
Aplicações: em imagens binárias/bitonais (ex:
digitalização de um fax)
Módulo 6 – Compressão de Imagem e Som
4
RLE- Run-length Encoding
000000000000000000000000000011111111111111000000000
000000000000000000000000001111111111111111110000000
000000000000000000000001111111111111111111111110000
000000000000000000000011111111111111111111111111000
000000000000000000001111111111111111111111111111110
000000000000000000011111110000000000000000001111111
000000000000000000011111000000000000000000000011111
000000000000000000011100000000000000000000000000111
000000000000000000011100000000000000000000000000111
000000000000000000011100000000000000000000000000111
000000000000000000011100000000000000000000000000111
000000000000000000001111000000000000000000000001110
28 14 9
26 18 7
23 24 4
22 26 3
20 30 1
19 7 18 7
19 5 22 5
19 3 26 3
19 3 26 3
19 3 26 3
19 3 26 3
20 4 23 3 1
RLE
Digitalização de uma imagem preto-branco
(um fax, por exemplo…)
Módulo 6 – Compressão de Imagem e Som
5
LZ77
• Em 1977, Lempel e Ziv criaram uma técnica de compressão de
texto baseada na observação empírica de que num texto
ocorrem com frequência repetições.
• Utiliza uma janela deslizante com 2k caracteres e uma janela
de observação de M carateres.
• Algoritmo
– Procura na janela de observação uma sequência contígua de carateres
que exista na janela deslizante;
– Caso encontre, transmite o índice na janela deslizante e o número de
carateres;
– Caso não encontre transmite o primeiro carater da janela de observação
Módulo 6 – Compressão de Imagem e Som
6
LZ77 – Exemplo
Texto a codificar: abxyndooyndkasa
8
Janela Deslizante
4
abxyndoo yndk
Janela de
Observação
+4
Saída do codificador: abxyndoo(4,3)kasa
Problemas:
• Se as repetições ocorrerem muito afastadas o algoritmo não as
codifica;
• Aumentar o tamanho da janela deslizante faz aumentar o
número de bits necessário para representar os ponteiros.
Módulo 6 – Compressão de Imagem e Som
7
Codificadores Baseados em Dicionário
• Supondo a existência de um dicionário
adequado ao ficheiro a codificar.
• Algoritmo
– Procurar no ficheiro ocorrências no dicionário
– Transmitir o índice da ocorrência no dicionário
• Problema
– Como criar o dicionário?
– Como transmitir o dicionário?
Módulo 6 – Compressão de Imagem e Som
8
Codificador de LZW – Lempel-Ziv-Welch
• Algoritmo
– Construção do dicionário em simultâneo com a
codificação (dicionário inicial rudimentar);
– Procura sequências de símbolos no dicionário;
– Devolve o índice “K” da sequência no dicionário;
– Insere nova palavra no dicionário: concatenação da
sequência com o símbolo seguinte da mensagem;
• Problemas
– O dicionário não pode ter um tamanho exagerado;
– O dicionário pode esgotar-se antes incluir todas as
sequências e limitar a compressão.
Módulo 6 – Compressão de Imagem e Som
9
LZW – exemplo
• Algoritmo de codificação do LZW
•
•
•
•
•
Dicionário inicial: a, aa, ab, aba, abaa, abaab, abaaa,
Mensagem a codificar: ...abaababbb...
Qual é a sequência mais longa no dicionário?... abaaba…
No dicionário com indíce K=6. Saída do codificador ….6….
E acrescentar dicionário com “abaaba”.
• Dicionário: a, aa, ab, aba, abaa,abaab,abaaa, abaaba
• Qual é a sequência mais longa no dicionário?... abbb…
• K=3….. Saída codificador:…..63….
• Etc.
• Demonstração com apllet Java
http://www.cs.sfu.ca/CC/365/li/squeeze/LZW.html
Módulo 6 – Compressão de Imagem e Som
10
Exemplos de Codificadores sem Perdas
para Imagem
• JBIG: compressão de imagem binária sem perdas (aplicações
de fax): RLE+Huffman. Norma de compressão de imagem
sem perdas;
• JPEG-LS: Utiliza predição linear entre pixéis adjacentes e
codificação de Huffman sobre o erro;
• GIF: Utiliza o algoritmo LZW para conseguir a compressão.
Palete de cores restringida a um máximo de 256;
• PNG: Utiliza predição linear e o algoritmo DEFLATE para
comprimir o erro. O algoritmo DEFLATE é inspirado no LZ77
e no LZW e é de utilização livre. Admite true color.
Módulo 6 – Compressão de Imagem e Som
11
Codificação com Perdas para
Imagem
• Estrutura geral do codificador
• Exemplo do JPEG em imagem
Módulo 6 – Compressão de Imagem e Som
12
Compressão com Perdas
Transformação
quantificação
Codificação
entropia
Disco
Canal
Transm.
Transformação
inversa
Reversão da
quantificação
Descodificação
entropia
Transformação: domínio da frequência
Quantificação: alocação de número bits diferentes por bandas de frequência (áudio, por exemplo)
Códigos entropia: Huffman ou aritmético.
Módulo 6 – Compressão de Imagem e Som
13
Exemplo: Imagem
Tabela: passos de quantificação
Codificador JPEG
Transformada : blocos 8×8
DCT
Quantização : aplicação de
tabelas de valores de acordo
com sensibilidade do sistema
visual humano
Passos de valor baixo mais
bits
Passos de valor elevado menos
bits.
Módulo 6 – Compressão de Imagem e Som
16
11
10
16
24
40
51
61
12
12
14
19
26
58
60
55
14
13
16
24
40
57
69
56
14
17
22
29
51
87
80
62
18
22
37
56
68
109
103
77
24
35
55
64
81
104
113
92
49
64
78
87
103
121
120
101
72
92
95
98
112
100
103
99
14
Exemplo em Matlab: para um Bloco
Espaço
-24
-32
-51
-57
-70
-75
-80
-81
-20
-28
-59
-68
-75
-78
-75
-80
-21
-25
-58
-76
-77
-75
-75
-80
-27
-28
-41
-69
-74
-76
-77
-81
Frequência
-34
-32
-44
-64
-76
-76
-75
-73
-33
-54
-64
-72
-77
-70
-73
-81
-30
-53
-64
-74
-76
-77
-77
-77
Bloco após subtrair 128
Módulo 6 – Compressão de Imagem e Som
-26
-55
-61
-71
-76
-81
-75
-80
-495
135
59
17
-5
2
-2
1
20
22
1
-3
-7
-10
-9
-7
-8 0 10
-3 -9 7
-1 -10 -9
9 -3 -14
14 3 -2
7 3 0
-1 3 3
0 -4 2
-1 -3 3
1 -3 0
-3 -1 3
1 6 -4
0 -1 0
-2 2 -4
3 1 -2
2 -1 -2
blkf=round(dct2(bloco1));
15
Exemplo: um Bloco
Frequência
-31
11
4
1
0
0
0
0
2 -1 0 0 0 0 0
2 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
xq=round(blkf./tabela)
Codificador entropia
Módulo 6 – Compressão de Imagem e Som
Versão(na frequência) aproximada
do original….
-496
132
56
14
0
0
0
0
22
24
0
0
0
0
0
0
-10
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
xq.*tabela
Descodificador entropia
16
Codificador de Entropia
Codificador Huffman aplicado ao bloco com varrimento em zig-zag
Sequência a codificar
[ -31 2 11 4 2 -1 0 0
Módulo 6 – Compressão de Imagem e Som
0 1 EOB ]
17
JPEG em Imagens a Cores
• Um codificador para cada plano de cor
• RGB não é eficiente
• Transformação para outro espaço de cor
– YCbCr (recomendação da norma)
– Uma imagem para a luminância (Y) e 2 imagens
para a crominância (CbCr) . Sub-amostragem nas
imagens de cor
– Exemplo: Para uma imagem 512×512
Y com 512×512, Cb com 256×256 e Cr com 256×256
• Dados entrelaçados ou separados
Módulo 6 – Compressão de Imagem e Som
18
Imagens a cores
Módulo 6 – Compressão de Imagem e Som
19
Conversão de Espaço de Cor
Red
Green
Blue
Y
Cb
Cr
Em Matlab:
Iycbcr= rgb2ycbcr(Irgb)
Módulo 6 – Compressão de Imagem e Som
20
Sub-Amostragem da Crominância
• A visão humana possui uma menor resolução para as cores.
Por este motivo, a informação de cor é normalmente
representada com uma menor amostragem espacial;
• Para representar a forma como a amostragem da Crominância
se relaciona com a amostragem da Luminância é utilizada a
seguinte norma definida em conjuntos de 8 pixéis com o
seguinte arranjo.
J:a:b
Pixel Y,Cr,Cb
Pixel Cr,Cb
Pixel Y
Módulo 6 – Compressão de Imagem e Som
J: Número de pixéis na horizontal. Em geral 4;
a: Número de pixéis de crominância na primeira linha;
b: Número de pixéis de crominância adicionais na
segunda linha.
21
Sub-Amostragem da Crominância
4:4:4
4:1:1
4:2:2
4:2:0
Para informação mais detalhada sobre a sub-amostragem da informação de crominância, pode consultar o seguinte documento.
Módulo 6 – Compressão de Imagem e Som
22
JPEG – Exemplo
Módulo 6 – Compressão de Imagem e Som
23
JPEG – Exemplo
Módulo 6 – Compressão de Imagem e Som
24
JPEG – Exemplo
Módulo 6 – Compressão de Imagem e Som
25
JPEG – Exemplo
Módulo 6 – Compressão de Imagem e Som
26
JPEG – Joint Photographic
Experts Group
• Este é o formato mais utilizado para armazenar imagens
do tipo fotografias
• Realiza uma codificação com “perdas” ou sem perdas
• O factor de qualidade permite reduzir o espaço
necessário para o armazenamento sacrificando a
qualidade
• Modos de operação
– Baseline (sequencial): blocos codificados em sequência e
armazenados em sequência
– Progressiva
– Hierárquica
Módulo 6 – Compressão de Imagem e Som
27
Modos de operação
Sequencial
Módulo 6 – Compressão de Imagem e Som
Progressivo
Hierárquico
28
Outros Formatos com Perdas para
Imagem
• TIFF (tagged image file format): vários tipos
de imagem, com perdas e sem perdas;
• JPEG (Joint Photographic Experts Group):
Compressão com perdas;
• JPEG2000: compressão com perdas e sem
perdas.
Módulo 6 – Compressão de Imagem e Som
29
Codificação com Perdas para
Som
• Redundância e Irrelevância
• DPCM
• MPEG áudio
Módulo 6 – Compressão de Imagem e Som
30
Redundância e Irrelevância
Fonte
Codifica
dor
Canal
Descodi
ficador
Receptor
Possibilidades de compressão:
•Diminuição da redundância do sinal gerado pela fonte
(implica conhecimento sobre o sinal da fonte).
•Diminuição da irrelevância do sinal para o receptor
(implica conhecimento sobre o receptor).
Módulo 6 – Compressão de Imagem e Som
31
Redundância
• Sinal de Voz
– Limitado em banda
– Harmónico: nas partes vocalizadas pode ser
modelizado como uma soma de sinusóides.
• Existem codificadores que tiram partido deste
conhecimento para reduzir a redundância
existente no sinal de voz.
Módulo 6 – Compressão de Imagem e Som
32
Irrelevância
• O sistema de audição humana possui algumas limitações que
podem ser exploradas
–
–
–
–
–
Limitação em frequência 20Hz - 20.000Hz.
Limiar de audição.
Mascaramento na frequência.
Mascaramento temporal.
Percepção harmónica.
• Os sistemas de compressão de sinais de música mais eficientes
como por exemplo o MPEG tiram partido deste conhecimento
sobre as limitações do sistema auditivo.
Módulo 6 – Compressão de Imagem e Som
33
Codificadores de Voz
• O sinal de voz possui uma grande redundância pelo
que é possível tirar partido deste conhecimento prévio
• Duas técnicas são usadas na compressão de voz
– Redução da redundância usando predição
– Redução da irrelevância usando quantização
• Os codificadores de voz dividem-se em duas
categorias
– Diferencias (bitrates até 32kbps)
– Vocoders (bitrates até 2kbps)
Módulo 6 – Compressão de Imagem e Som
34
Codificação por Predição Linear
• A codificação por predição linear significa que é possível prever
(com um erro pequeno) cada amostra de um sinal usando uma
combinação linear das anteriores;
• Exemplo de preditor linear de ordem zero;
ˆ = x(n -1)
x(n)
ˆ
e(n) = x(n) - x(n)
• A predição da amostra atual é obtida supondo que é igual à amostra
anterior do sinal.
• O erro é calculado como a diferença entre a prevista e a real.
• Para muitos sinais (voz, música, imagem,etc) o sinal de erro
apresenta um histograma mais concentrado em torno de zero
tornando assim possível usar um codificador de entropia como o
código de Huffman.
Módulo 6 – Compressão de Imagem e Som
35
Codificação por Predição Linear
x(n)
e(n)
+
Preditor
e(n)
xˆ ( n)
x(n)
+
Em geral a saída
do preditor linear é
obtida como uma
combinação linear
das N anteriores
amostras do sinal
x(n).
+
xˆ (n)
Preditor
N
ˆ = åa k x(n - k)
x(n)
k=1
Módulo 6 – Compressão de Imagem e Som
36
DPCM- Differencial Pulse Code
Modulation
• Neste tipo de codificadores para além do preditor
linear que reduz a redundância do sinal introduz-se
um quantizador do sinal de erro.
• Esta técnica permite reduzir alguma da irrelevância
no sinal uma vez que o ouvinte tolera algum ruído de
quantização sem grande impacto perceptual.
• Apenas o erro quantizado é transmitido e a
codificação é realizada de modo a que o
descodificador consiga obter o sinal de saída apenas a
partir do sinal de erro quantizado.
Módulo 6 – Compressão de Imagem e Som
37
DPCM- Differencial Pulse Code
Modulation
e(n)
x(n) +
Quantizador
eq(n)
Codificador
de Entropia
-
xˆ ( n)
Descodificador
de Entropia
Preditor
eq(n)
xq(n)
xq(n)
+
+
xˆ ( n)
Módulo 6 – Compressão de Imagem e Som
Preditor
38
Preditor Linear de 1ª Ordem –
Aplicação em Som
Preditor linear de 1ª ordem aplicado a um sinal de voz.
Módulo 6 – Compressão de Imagem e Som
39
Preditor Linear de 1ª Ordem –
Aplicação em Imagem
Módulo 6 – Compressão de Imagem e Som
40
Vocoders
• Codificadores específicos para sinais de Voz;
• Não podem ser usados para codificar outros tipos de sinais;
• São baseados num modelo matemático do trato vocal
Vídeo das cordas vocais a vibrar
Módulo 6 – Compressão de Imagem e Som
41
Modelo Matemático para a Produção
de Voz
Parâmetros
Pitch
Geração de
impulsos
Vozeada
Filtro do
Trato Vocal
Gerador de
ruído
Voz
Não-vozeada
• Os telemóveis GSM utilizam a Regular-Pulse Excitation
Long-Term Predictor;
• A norma G.728 utiliza Low Delay Code Excited Linear
Prediction
Módulo 6 – Compressão de Imagem e Som
42
Codificadores de Voz
Freq. de
Compressão Amostragem
(kHz)
Resolução
(bits)
Taxa de
transmissão
(kbps)
Qualidade
Norma
LB (Hz)
IMAADPCM
200-20000
ADPCM
8-44.1
4
32-350
Telefone, CD
G.711
200 – 3200
m-law PCM
8
8
64
Telefone
G.722
50 – 7000
DPCM
16
4
64
Rádio AM
G.728
200 – 3200
low-delay
CELP
8
2
16
Telefone
G.723
200 – 3200
ADPCM
8
8
5.3 ou 6.3
H.323
GSM
200-3200
RPE
8
?
13
Telefone
Nos codificadores ADPCM (Adaptive DPCM), os coeficientes do preditor
linear e o número de bits do quantizador, são adaptados ao longo do tempo às
características do sinal de entrada.
Módulo 6 – Compressão de Imagem e Som
43
Codificadores de Áudio
• Os codificadores para comprimir música com alta qualidade apenas
tiram partido da irrelevância presente no sinal. Ou seja, removem do
sinal as componentes tempo/frequência que o ouvinte não
conseguirá notar;
• Existentes três características / limitações do sistema auditivo
humano que os codificadores como o MP3 tiram partido apra
conseguir os ganhos de compressão:
– Limiar auditivo;
– Mascaramento na frequência
– Mascaramento no tempo.
• Devido à necessidade de realizar uma análise tempo/frequência do
sinal estes codificadores realizam sempre uma variante do
espectrograma.
Módulo 6 – Compressão de Imagem e Som
44
Limiar de Audição
Não é necessário
codificar esta
componente
Módulo 6 – Compressão de Imagem e Som
45
Mascaramento na Frequência
Não é necessário
codificar esta
componente
Módulo 6 – Compressão de Imagem e Som
46
Mascaramento no Tempo
Módulo 6 – Compressão de Imagem e Som
47
Codificadores de Áudio
Freq. de
Taxa de
Compressão Amostragem transmissão
(kHz)
(kbps)
Norma
LB (Hz)
Audio CD
20 – 20000
Linear PCM
44.1
1411.2 (stereo)
CD
MPEG-1
Layer I
MPEG-1
Layer III
MPEG-2/4
AAC
20 – 20000
sub-band
coding
sub-band
coding
sub-band
coding
32 – 48
256 – 448
near CD
32 – 48
128 – 320
CD
8 – 96
arbitrary
CD
20 – 20000
20 – 20000
Qualidade
Em geral, o codificador AAC a 128kbps oferece a mesma qualidade
perceptual que o codificador MP3 a 192kbps (estéreo).
Módulo 6 – Compressão de Imagem e Som
48
MPEG-I: áudio
Três camadas (Layers) para compressão com níveis de
complexidade diferente e taxas/rácios diferentes
• Layer 1:
–
–
–
–
Modelo psico-acústico com mascaramento na frequência
30 kbit/s (mono) a 448 kbit/s (stereo)
Qualidade semelhante com CD para 256–384kbit/s
Philips DCC (Digital Compact Cassette) –192kbit/s
Módulo 6 – Compressão de Imagem e Som
49
MPEG-I: áudio
• Layer 2:
– Modelo psico-acústico acrescenta o mascaramento no
tempo
– 64 kbit/s a 256 kbit/s(stereo)
– DVD
– DAB (Digital áudio broadcast)
– Qualidade semelhante ao CD para192 a 256 kbit/s
• Layer 3:
–
–
–
–
–
Camada mais complexa.
Maiores taxas de compressão
64 kbit/s (mono)
Qualidade semelhante ao CD para 128 a 192 kbit/s
Codificador com o maior atraso
Módulo 6 – Compressão de Imagem e Som
50
"!# $%&$'%( !) *!+ , - !. / 0) 1%&!
!
&7, #< *=>#+#?-*16#
&' ( #) *+, -+. #/011#2*, 3-1#45#&6#+7#8 9: #; 7' &) 1-#+%
$%
&< B#
) 10' -*@=*&7#&6#*=#*0#, *A17#?1%
Codificador MP3
!
!
!
!!!!!!!!!!!!!!!!!!!! "#$%&'( )'* +, - . '/ "0#%01 ', 2'3 4 5 6 78'90: &%'; '5 <- , / &%'=>, $%-&'?@AB'
'
Módulo !
6 – Compressão de Imagem e Som
!
51
Comparação entre MPEG
Layer
Target Bitrate
Ratio
Quality at 64
kbit/s
Quality at 128
kbit/s
Theoretic Min.
Delay
Layer 1
192 kbit/s
4:1
---
---
19ms
Layer 2
128 kbit/s
6:1
2.1–2.6
4+
35ms
Layer 3
64 kbit/s
12:1
3.6–3.8
4+
59ms
Qualidade : 5- perfeito; 4- ligeira diferenças; 3- ligeiro incómodo;
2- desagradável; 1- horrível.
Módulo 6 – Compressão de Imagem e Som
52
Testes de Audição
•
•
•
•
•
Sinal de teste "castanets.wav"
MP3 64kbps
MP3 32kbps
MP3 8kbps
MP3 45-85kbps
Módulo 6 – Compressão de Imagem e Som
53
Bibliografia
• Kristo Lehtonen, "GSM Codec". pdf
• Karlheinz Brandenburg, "MP3 and AAC Explained", AES 17th
International Conference on High Quality Audio Coding,
1999. pdf
• Ze-Nian Li and Mark S. Drew, "Fundamentals of Multimedia",
PEarson Education, 2004. Capítulos 13 e 14.
Módulo 6 – Compressão de Imagem e Som
54