Conceitos Básicos em
Codificação com Perdas
1
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Em codificação sem perdas:
 Limite da taxa de compressão atingível (em bits/símbolo)
é dado pela entropia da fonte
de acordo com a Teoria da Informação de Shannon.
Em codificação com perdas:
 Há um compromisso entre a taxa de compressão
e a qualidade do sinal reconstruído.
TE073 – Processamento Digital de Sinais II
2
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Codificação com perdas:
 Maior distorção possível: Perda total do sinal
Taxa de compressão máxima!
Isto é, não necessita enviar dado nenhum.
 Menor distorção possível: Codificação sem perdas
Taxa de compressão dada pela entropia da fonte.
Teoria da Distorção pela Taxa
(Rate Distortion Theory)
TE073 – Processamento Digital de Sinais II
3
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Otimizar um codificador:
 Obter a menor distorção possível para uma dada
taxa de compressão.
(imposição do meio de armazenamento ou canal de comunicação)
Como medir a distorção??
TE073 – Processamento Digital de Sinais II
4
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
7.3. Critérios de Distorção
O que é a distorção??
É uma medida de quanto o sinal reconstruído se diferencia do sinal original.
A fidelidade da reconstrução depende do usuário final.
Medidas subjetivas:
O usuário final define, subjetivamente, a qualidade da reconstrução.
Geralmente feito através de uma pesquisa de opinião com um
grande número de pessoas para não recair em particularismos.
Ex.: Avaliação de uma pintura e avaliação de um rascunho de uma casa.
Avaliação de um trecho de música clássica e de um discurso político.
TE073 – Processamento Digital de Sinais II
5
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Medidas subjetivas da distorção:
O usuário final define, subjetivamente, a qualidade da reconstrução.
Geralmente feito através de uma pesquisa de opinião com um
grande número de pessoas para não recair em particularismos.
Ex.: Avaliação de uma pintura e avaliação de um rascunho de uma casa.
Avaliação de um trecho de música clássica e de um discurso político.
Baseado em escores:
Excelente, ótimo, bom, aceitável, ruim, péssimo,
inaceitável, horroroso, pior que isso não poderia ser, etc.
TE073 – Processamento Digital de Sinais II
6
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Problemas com este tipo de medida:
Difícil de se computar, pois depende muito de pessoa para
pessoa. Para se obter uma medida independente de “gostos”,
deve-se trabalhar com um número muito grande de pessoas.
O que torna a medida muito complicada e trabalhosa de ser realizada.
Logo: definição de medidas objetivas da distorção facilita
muito o projeto dos codificadores.
TE073 – Processamento Digital de Sinais II
7
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Medidas objetivas da distorção:
Geralmente baseadas em erros entre o sinal original e o reconstruído:
1 N
d p ( x, y)   xn  yn
N n1
p
Onde: d p ( x, y) É a distorção de ordem p entre o sinal original x
e o sinal reconstruído y.
N é o número de componentes (dimensões) dos sinais.
TE073 – Processamento Digital de Sinais II
8
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Medidas mais comuns:
1 N
d1   xn  yn
N n1
Média das diferenças absolutas
1 N
  d 2   xn  yn 2 Erro médio quadrático (EMQ)
Mean Squared Error (MSE)
N n1
2
d
Distância Euclidiana ao quadrado
....
d   max xn  yn
n
Erro máximo.
Usado em casos onde o erro só é percebido
Acima de um determinado limiar (threshold)
TE073 – Processamento Digital de Sinais II
9
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Considerando que a distorção imposta ao sinal original como
sendo um ruído de codificação: y  x  d
Podemos ter medidas baseadas na relação Sinal-Ruído
 x2
SNR  2
d
Energia do Sinal
Energia do Ruído (d2,EMQ,MSE)
  x2 
Medida em dB
SNR[dB]  10. log10  2 
d 
2
 xmax
 Relação sinal ruído de pico
PSNR[dB]  10. log10  2 
Muito usado em imagem: x2max=2552

 d 
TE073 – Processamento Digital de Sinais II
10
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Vimos 2 formas de medidas da fidelidade da reconstrução:
Medidas Subjetivas:
Medidas precisas da fidelidade baseada nos aspectos
e limitações humanas.
São matematicamente difíceis de se manusear e usar no
projeto de codificadores.
Medidas Objetivas:
Matematicamente tratáveis.
Não incorpora os aspectos da fidelidade perceptível
do ponto de vista humano.
TE073 – Processamento Digital de Sinais II
11
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Medida ótima?
Aquela que modela matematicamente as limitações humanas.
Porém essas limitações (de ordem biológica) são difíceis de se
determinar matematicamente, logo usa-se aproximações e modelos.
Ex.:
Sistema Visual: modelo do olho e percepção de imagens e vídeo
Sistema passa baixas com persistência temporal.
Razão de Weber: I  0.02
I
Sistema Auditivo: modelo do ouvido e percepção de sons.
Limitação 20Hz a 20KHz com resolução de 1000:1
1kHz a 20dB percepção semelhante a 50Hz a 50dB
Mascaramento de nível sonoro e mascaramento espectral
TE073 – Processamento Digital de Sinais II
12
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
7.5. Teoria da Distorção pela Taxa
1000
cod1
cod2
900
800
Distorcao(EMQ)
700
600
500
400
300
200
100
0
0
10
20
30
40
50
Taxa [kbits/seg]
Ex.: 2 se cruzando (MPEG1 e MPEG2)
TE073 – Processamento Digital de Sinais II
13
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Problema: Como calcular a função Distorção(Taxa) R(D) ?
- Resultado depende do modelo usado
Ex.: Fonte Gaussiana e distorção medida pelo erro médio quadrático:
2

1

log
,
D



D
R( D)   2
2

0
,
D



2
1.6
1.4
1.2
Distorcao
1
0.8
0.6
0.4
0.2
0
-0.2
0
20
40
60
80
100
Taxa
 2  100
TE073 – Processamento Digital de Sinais II
14
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
A função R(D) da distribuição Gaussiana possui a propriedade de
ser a maior função R(D) para qualquer outra distribuição que
possua a mesma variância (2).
Logo pode ser vista como um limite superior.
Shannon demonstrou em seu artigo de 1948 que o limite inferior
da função R(D) para uma variável aleatória contínua medida pelo
erro médio quadrático, é dada por:
RSLB ( D)  h( X )  12 log2 .e.D
Onde h(X) é a entropia diferencial da variável X
TE073 – Processamento Digital de Sinais II
15
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Problema:
Para sinais reais é difícil definir sua função distribuição
de probabilidade e assim calcular h(X).
Para distribuição Gaussiana:

h( X )  log 2 .e.
1
2
2

Prova-se que h(X) da distribuição gaussiana é maior que qualquer
outra h(X) para a mesma variância (2).
TE073 – Processamento Digital de Sinais II
16
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
7.6. Modelos
7.6.1. Modelos Probabilísticos
Distribuição Uniforme:
Distribuição Gaussiana:
Distribuição Laplaciana:
Distribuição Gamma:
 1
, para a  x  b

f X ( x)   b  a

, outros
0
modelo da ignorância
f X ( x) 
f X ( x) 
f X ( x) 

1
2 2
.e
2 2
 2x
1
2 2
4
 x   2
.e
3
8 x

Mais usada
Mais centrada em zero,
Ex.: voz, dif. imagem
 3x
.e
2
TE073 – Processamento Digital de Sinais II
Mais centrada ainda
em zero, menos tratável
17
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
TE073 – Processamento Digital de Sinais II
18
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
7.6.2. Modelos baseados em Sistemas Lineares
Uma grande classes de processos podem ser modelados pela
Equação de Diferenças:
N
M
i 1
j 1
xn   ai xni   b j n j   n
Onde xn são as amostras do processo que desejamos modelar
e n é uma sequência de ruído branco.
Em DSP nada mais é que um filtro digital com N pólos e M zeros.
Em estatística é chamado um modelo média móvel autoregressivo
(ARMA – Autoregressive Moving Average) ARMA(N,M)
TE073 – Processamento Digital de Sinais II
19
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Se todos os bj forem zero. Fica apenas a componente autoregressiva.
N
xn   ai xni   n
i 1
Que é um filtro IIR com apenas pólos (all-pole) e também chamado
modelo autoregressivo de ordem N, AR(N), muito usado em compressão
de voz.
Como a amostra atual depende apenas das N amostras anteriores:
P( xn | xn1 , xn2 ,...)  P( xn | xn1 , xn2 ,...,xn N )
Isto significa que um AR(N) é um processo de Markov
de ordem N.
Ver exemplos no livro.
TE073 – Processamento Digital de Sinais II
20
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
7.6.3. Modelos Físicos
Modelos baseados na física da fonte do sinal.
Geralmente complicados e não bem tratáveis matematicamente.
Uma exceção é a geração de voz que será vista em detalhes
oportunamente.
TE073 – Processamento Digital de Sinais II
21
Quantização Escalar
22
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantização Escalar


Definição:
Representar uma infinidade de valores em um
conjunto limitado de códigos; ou seja, poucos
códigos de saída para muitos valores de entrada;
Mais simples métodos de compressão com perdas;
Ex: Valores de amostras entre -10 e 10:
TE073 – Processamento Digital de Sinais II
23
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantização Escalar

Esquema do quantizador:
Representar o valor de cada entrada em uma
saída com o valor do numero inteiro mais próximo:
-2,47  -2,0
3,14159...  3,0
4,5  4,0 ou 5,0 (aleatoriamente).
TE073 – Processamento Digital de Sinais II
24
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantização Escalar

Para os infinitos valores entre -10 a 10, o alfabeto de
saída se reduz a apenas 21 valores:
{-10,.....,0,.....,10}
Quando um valor de saída é “3”, qual foi a sua
entrada?
2.95 ?
3.1415 ?
2,51 ?
TE073 – Processamento Digital de Sinais II
25
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
O Problema da Quantização




O compressor divide a faixa de entradas em intervalos,
{-10,.....,0,.....,10};
Intervalo = palavra de código;
Como vários valores de entrada podem cair em um mesmo
intervalo,
o código somente informa que a amostra pertence aquele
intervalo.
8,01  código x1  8
8,20  código x2  8
7,51  código x3  8
TE073 – Processamento Digital de Sinais II
26
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
O Problema da Quantização

Esta perda de informação é irrecuperável;

Também chamado de “Ruído de Quantização”.

Como o código representa um intervalo, então o
decodificador gera um valor que melhor represente os
valores do intervalo.
TE073 – Processamento Digital de Sinais II
27
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantização Escalar
Quando as entradas são analógicas, o processo é
também conhecido como “conversão analógico-digital”
A/D.
A reconstituição do código em valor analógico se
chama “conversão digital-analógico” D/A.
Aplicação mais conhecida:
Digitalização de áudio, PCM30 (telefonia)
TE073 – Processamento Digital de Sinais II
28
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantização Escalar
Códigos
Saída
000
001
010
011
100
101
110
111
-3,5
-2,5
-1,5
-0,5
0,5
1,5
2,5
3,5
Definição dos intervalos de
entrada e os respectivos códigos.
Valores de saída para os códigos
(níveis de reconstrução).
TE073 – Processamento Digital de Sinais II
29
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantização Escalar
Ex: f(t) = 4.cos(2t), com amostras a cada 0,05 s
TE073 – Processamento Digital de Sinais II
30
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Ruído de Quantização
Definição:
q2 = msqe: é a média quadrada da diferença entre a entrada
[x] e a saída [y = Q(x)] do quantizador.
onde:
fX(x) = função probabilidade da entrada
M = número de intervalos
msqe = mean squared quantization error.
TE073 – Processamento Digital de Sinais II
31
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Taxa do Quantizador
Para palavras código fixas, o próprio comprimento do
código especifica a taxa do quantizador.
Se o número de saídas do quantizador é M então a taxa é dada por:
R = log2M
Em códigos de tamanhos variáveis, a taxa é função da
probabilidade de ocorrência de cada código, e do seu respectivo
comprimento[ li ]:
TE073 – Processamento Digital de Sinais II
32
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantizador Uniforme
• Intervalos igualmente espaçados (entrada e saída)
• Idem para os limites de decisão e valores de reconstrução.
Espaço = 
Quantizador Midrise
• Não possui o nível “0”
• Número de saídas pares
Quantizador Midtread
• Possui o nível “0”
• Número de saídas impares
TE073 – Processamento Digital de Sinais II
33
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantizador Uniforme e Fonte Uniforme
• Fonte uniformemente distribuída pelo intervalo.
• Intervalo [ -Xmax , Xmax ] dividido em M partes iguais ()
• Ruído de quantização para fonte uniforme: q = x - Q(x)
TE073 – Processamento Digital de Sinais II
34
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantizador Uniforme e Fonte Uniforme
O ruído de quantização se torna:

2


2
2
1

2
2
 q   q dq 

12
Assumindo que a variância dos valores de entrada no
intervalo [ -Xmax , Xmax ] é:


2 X max 

2
2
s
12
TE073 – Processamento Digital de Sinais II
35
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantizador Uniforme e Fonte Uniforme
SNR: Signal Noise Ratio ou Razão Sinal Ruído:
  s2 
SNRdB   10 log  2 
 
 q
SNR = 6,02.n [dB]
• A cada bit adicionado (n) no quantizador, ocorre um
aumento de 6,02 dB na razão sinal ruído.
• A cada bit retirado do esquema do quantizador, o ruído
inserido é 4 vezes maior que o esquema anterior.
TE073 – Processamento Digital de Sinais II
36
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Compressão de Imagens
• Modelo de probabilidade para imagens: quase impossível
• Aproximação  Pixels distribuídos entre: 0 e 2b-1, onde b é o
número de bits por pixel. Assume-se que os valores dos pixels
variam de 0 a 255.
• 1 bit/pixel  dividir [0, 255] em [0, 127] e [128, 255]; com
limites de decisão [0, 128, 255] e valores de reconstrução
{64, 196}.
• 2 bit/pixel  limites de decisão [0, 64, 128, 196, 155] e valores
de reconstrução {32, 96, 160, 224}.
TE073 – Processamento Digital de Sinais II
37
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Imagem
Original
1 bit/pixel
2 bits/pixel
3 bits/pixel
TE073 – Processamento Digital de Sinais II
38
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Nota-se que para distribuições não uniformes, a divisão das
entradas e saídas em partes igualmente separadas não é
satisfatória.
TE073 – Processamento Digital de Sinais II
39
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Erros de Combinação
 ideal
{
Modelos de distribuição
Parâmetros da distribuição
Diferenças entre os modelos escolhidos e os modelos reais.
1º caso: Variância assumida  Variância real.
2º caso: Modelo de distribuição  Tipo do quantizador.
TE073 – Processamento Digital de Sinais II
40
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Erros de Combinação
Variância assumida  Variância real.
Quantizador uniforme com distribuição Gaussiana
TE073 – Processamento Digital de Sinais II
41
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Erros de Combinação
Modelo do quantizador não casa com o modelo da distribuição
TE073 – Processamento Digital de Sinais II
42
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantização Adaptativa
•
Eliminar problemas de erros de combinação
• Adaptar o quantizador () em relação à estatística da fonte.
•
Método I: Forward Adaptive Quantization
•
Método II: Backward Adaptive Quantization
TE073 – Processamento Digital de Sinais II
43
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Forward Adaptive Quantization
Passos:
•
Fonte dividida em blocos de dados,
•
Parâmetros analisados e ajustados antes da quantização,
• Dados + ajustes enviados.
Desvantagens:
• Atraso por processamento dos blocos,
• Envio de informação lateral.
•
Ponto ótimo entre:
Blocos pequenos  Muita informação lateral
Blocos extensos  Demora no processamento
TE073 – Processamento Digital de Sinais II
44
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
• Exemplo 8.5.1: Palavra “test”, digitalizada com 8000
amostras/s e 16 bits/amostra.
• Comprimida com quantização de 6 níveis (3 bits).
Quantização
uniforme.
Perda de resolução na amplitude.
TE073 – Processamento Digital de Sinais II
45
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
•
Blocos de 128 amostras
•
Obtenção do desvio padrão dos blocos e quantizado com 8 bits.
• Amostras normalizadas com o desvio padrão.
TE073 – Processamento Digital de Sinais II
46
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
• Exemplo 8.5.2: Blocos de 8 x 8 pixels,
• 3 bit Forward Adaptive Uniform Quantization,
• Informação lateral:
Valores máximos e mínimos dos bloco (8x8) = 8 bits.
3 bits/pixel
TE073 – Processamento Digital de Sinais II
47
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Backward Adaptive Quantization
• Análise de amostras quantizadas antigas.
Como obter informação de erro somente com a saída do
quantizador, e sem conhecer o valor da amostra original?
A noção do erro na distribuição das saídas se dá por uma
extensa análise da própria saída do quantizador.
TE073 – Processamento Digital de Sinais II
48
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Backward Adaptive Quantization
• Quando a distribuição de entrada combina com o quantizador,
tem-se o  ideal. Caso contrário, varia-se o tamanho de .
• Se  < ideal, a maioria das amostras incidirão nos níveis mais
elevados do quantizador,   .
• Se  > ideal, a maioria das amostras incidirão nos níveis mais
baixos do quantizador,   .
Outros: Ex.: Quantizador de Jayant
TE073 – Processamento Digital de Sinais II
49
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantização Não Uniforme
• Distribuição concentrada próximo à origem
Vantagem:
Reduz a distorção onde a distribuição é mais densa
(mais informação).
Desvantagem:
Erros maiores na região de baixa probabilidade de amostras.
TE073 – Processamento Digital de Sinais II
50
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantização Não Uniforme
•  menor na região próxima à origem,
•  aumenta ao se afastar da origem,
• Quanto mais afastado da origem, maior o ruído de quantização.
Porém o seu msqe é menor que em um quantizador uniforme.
• Construção mais complexa,
Definir os limites de decisão e níveis de reconstrução que
minimizam o msqe.
TE073 – Processamento Digital de Sinais II
51
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantização Não Uniforme
TE073 – Processamento Digital de Sinais II
52
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantização Ótima ou Lloyd-Max
Encontrando {yj} e {bi}:
bj
yj



b j 1
bj
b j 1
x f x x  dx
f x x  dx
Os valores de reconstrução são os centros das probabilidades em
um determinado intervalo.
bj 
y j 1  y j
2
Os limites de decisão são os pontos centrais entre dois valores
de reconstrução vizinhos.
Como estimar fX(x)?
TE073 – Processamento Digital de Sinais II
53
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Companded Quantization
Variar  proporcionalmente à probabilidade da distribuição.
• A entrada é mapeada por uma função compressora
Expande as regiões onde a probabilidade é maior e encolhe
onde é menor.
• Quantizada por um quantizador uniforme.
• Para a saída os valores quantizados são expandidos para voltar
voltar à sua forma original.
TE073 – Processamento Digital de Sinais II
54
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Companded Quantization
Função similar à do quantizador não uniforme.
TE073 – Processamento Digital de Sinais II
55
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Padrões conhecidos:
•Lei 
Compressão em 8159 intervalos de igual amplitude
Fator de compressão 0 ~ 255
Usado em Telefonia  = 255
EUA e Japão
•Lei A
Compressão em 4096 intervalos de igual amplitude
Fator de compressão 1 ~ 100
Usado em Telefonia A = 87,6
Europa e Brasil
TE073 – Processamento Digital de Sinais II
56
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Entropy-Coded Quantization
Atribuição de códigos aos intervalos de quantização.
Taxa do quantizador é o fator de desempenho do processo.
Loyd-Max
Para um quantizador Lloyd-Max de 32 níveis é preciso:
• 5 bits por amostra se a taxa for constante,
• 3,799 (entropia) para distribuição Laplaciana.
TE073 – Processamento Digital de Sinais II
57
QUANTIZAÇÃO VETORIAL
58
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
TE073 – Processamento Digital de Sinais II
59
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantização Vetorial


Vimos que em codificação sem-perdas, a
codificação de sequências de símbolos é mais
eficiente que a codificação dos símbolos
independentemente.
Em codificação com perdas temos a mesma
idéia. Isto é:


Para uma dada Taxa temos menor Distorção
Para uma dada Distorção temos uma menor Taxa
TE073 – Processamento Digital de Sinais II
60
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica


Procurar tirar vantagem da estrutura da
fonte.
Vetor = sequência ou blocos de amostras


Vetor L-dimensional corresponde a L amostras do
sinal a ser codificado.
Dicionário de Códigos : CodeBook

Codewords (ou Codevectors) de
Tamanho K e Dimensão L
TE073 – Processamento Digital de Sinais II
61
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantização Vetorial - Funcionamento
Codificação:
Decodificação:
Agrupamento das amostras;
Busca da “melhor” Codeword;
Transmissão do Índice do Codebook;


Lookup Table;
Desagrupamento;
TE073 – Processamento Digital de Sinais II
62
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Algumas definições




Unidade de medida bits por amostra;
Tamanho do codebook K;
Dimensão do vetor de entrada L;
Exemplo:




Codebook C com K Codewords;
O número de bits por vetor : log2K;
Taxa de quantização de (log2K)/L [bits/amostra]
Medida de distorção: usaremos o erro quadrático;
A codeword Yj será a melhor representação do vetor X se:
X  Yj
2
 X  Yi
2
para todo Yi  C
TE073 – Processamento Digital de Sinais II
X
2
 i 1 xi2
L
63
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Vantagem da Quantização Vetorial sobre a Escalar
EXEMPLO:
•Entrada (peso, altura);
•Peso: variação uniforme, 40~80;
•Altura: variação uniforme de 40~240
•Quantização Escalar: 3 + 3 bits = 6 bits



Quanto a distorção?
Quanto a eficiência?
Flexibilidade?
TE073 – Processamento Digital de Sinais II
64
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
O algoritmo de Lloyd
Quantização Escalar
y 
(0) M
i
i 1
1- Comece com um conjunto inicial de valores de reconstrução
onde: fixa-se k=0, D(0)=0 . Define-se o Threshold 
2- Determine os limites de decisão: b j 
k
3- Compute a distorção:
D
(k )
Y j(k1)  Y j( k )
j= 1, 2, 3 , ..., M-1.
2
bi( k )
 i 1  ( k ) ( x  yi ) 2 fx( x)dx
M
bi 1
4- Se D(k)-D(k-1)<, pare, caso contrário, continue;
5- k=k-1, Calcular os novos valores de reconstrução;
Volte ao passo 2;
Yj
(k )


b (j k )
b (j k11)

b (j k )
b (j k11)
TE073 – Processamento Digital de Sinais II
xfx( x)dx
fx( x)dx
65
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Generalização do Algoritmo de Lloyd (GLA)
Quantização Vetorial
1- Comece com um conjunto inicial de valores de reconstrução {Yi(0)}i=1M
onde: fixamos k=0, D(0)=0. Definindo-se o Threshold .
2- Determine a região de quantização:
Vi(k)={X:d(x,Yi) < d(X,Yi) ji} i=1, 2, ..., M-1;
3- Determine a distorção:
(k )
( k 1)
(
D

D
)
4- Se:

D (k )
D
(k )
bi( k )
 i 1  ( k ) x  y
M
bi 1
(k ) 2
i
fx( x)dx
; pare, caso contrario, continue;
5- K=K+1. Determinar os próximos valores de reconstrução para {Yi(k)}i=1M como as
centróides do conjunto {Vi(k-1)}
Retorne ao passo 2.
TE073 – Processamento Digital de Sinais II
66
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
O Algoritmo Linde-Buzo-Gray (LBG)
- Publicado em 1980
-É uma implementação prática do Algoritmo de Loyd
Generalizado;
- Semelhante ao K-Means
TE073 – Processamento Digital de Sinais II
67
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Algoritmo K-means
-Muito usado em Reconhecimento de Padrões
-Definição:
Seja um grande conjunto de amostras, chamada sequência de
treino (ST) e um conjunto de k amostras representativas desta
ST.
Aloque a cada amostra da ST a uma das k amostras
representativas, através de alguma medida de distância.
Atualize o valor das k amostras representativas pela centroide
(média) dos vetores que foram alocadas a cada uma.
TE073 – Processamento Digital de Sinais II
68
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Treinado os vetores
1- Comece com um conjunto inicial de valores de reconstrução {Yi(0)}i=1M e os vetores de
treinos {xn}n=1N, defina k=0, D(0)=0. Define-se o Threshold 
2- As região de quantização: {Vi(k)}i=1M são dadas por
Vi(k)={Xn : d(xn,Yi) < d(Xn,Yi) ji} i=1, 2, ..., M;
obs: Assumimos que nenhuma das regiões de quantização estão vazias
3- Determine a distorção média D(k) entre os vetores de treino e o valor de reconstrução;
4- Se:
( D ( k )  D ( k 1) )

D (k )
; pare, caso contrario, continue;
5- k=k+1. Calcule novos valores de reconstrução {Yi(k)}i=1M como a média dos vetores de
cada região de quantização {Vi(k-1)}
Retorne ao passo 2.
TE073 – Processamento Digital de Sinais II
69
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Inicialização do LBG


Um dos problemas encontrados é que o codebook
projetado é extremamente dependente do
conjunto inicial escolhido.
Alternativas para a inicialização:




Vetores Randômicos
Escolha randômica a partir da ST
Pairwise Nearest Neighbor (PNN)
Split (proposto em conjunto com o LBG)
TE073 – Processamento Digital de Sinais II
70
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Exemplo do algoritmo LBG com Split.
Vetores de treino dentro da região rosa.
TE073 – Processamento Digital de Sinais II
71
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Problema que pode aparecer no LBG


Surgimento de região vazia = nenhum vetor alocado à
codeword
Solução: substituir a codeword por outra que atenda a
um dos critérios:



Seleção da centróide da região com maior número de vetores
Seleção da centróide da região com maior distorção (MSE)
Para que seja spliteada.
TE073 – Processamento Digital de Sinais II
72
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Uso do LGB na compactação de imagem
- Utilização de blocos de pixels de tamanho NxM
- Vetor de treinamento dimensão L=N.M com N=M
TE073 – Processamento Digital de Sinais II
73
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Quantização da imagem Sinan
-Dimensão do vetor 16
= Blocos de 4x4 pixeis;
- Codebook de tamanho 64,
256, e 1024
TE073 – Processamento Digital de Sinais II
74
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
TE073 – Processamento Digital de Sinais II
75
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica

Taxa de compressão
para cada codebook;

índice: (log2 k) bits;

L : dimensão do vetor

taxa (log2 K)/L bits/pixel

Coodebook: BxLxK bits
imagem: 256x256 pixels
TE073 – Processamento Digital de Sinais II
76
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Como definir a Sequência de Treino?
TE073 – Processamento Digital de Sinais II
77
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Problemas da Quantização Vetorial

A teoria da Distorção pela Taxa de Shanon diz
que, para uma mesma taxa, quanto maior a
sequência (dimensão) menor é a distorção.


Isso implica que:
codificar com codebook de L=8 e k=16 (0.5
bits/amostra) gera mais distorção que usar um
codebook de L=20 e k=1024 (0.5 bits/amostra)
Se quisesse: 4x4 pixels a 2 bits/pixel: qual K?
Problemas:
•Aumento da memória necessária ao
Codebook
•Aumento da complexidade computacional
– Processamento Digital de Sinais II
naTE073
codificação
78
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Soluções

Métodos de Busca Rápida da melhor codeword





Distância Parcial (codebook ordenado)
Desigualdade Triangular (pontos de âncora)
KD-Tree (pode errar!)
outros...
Quantização Vetorial Estruturada:




Tree-Structured VQ
Piramid VQ
Lattice VQ
outros...
TE073 – Processamento Digital de Sinais II
79
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
Variações sobre VQ

Gain-Shape VQ


Normalizar as codewords e enviar, além do
índice, o Ganho a ser usado quantizado
escalarmente.
Mean-Removed VQ

Retirar a Média das codewords e enviá-la
quantizado escalarmente.
TE073 – Processamento Digital de Sinais II
80
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica
TE073 – Processamento Digital de Sinais II
81
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica

Classified VQ

Classificar a entrada em classes definidas e
treinar um codebook para cada classe.
(ex.: bordas e homogêneo)
Q1
Q2
Vetor
Q3
índice1+indice2
Q4
Classificador
TE073 – Processamento Digital de Sinais II
82
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica

Multistage VQ

Usar cascata de VQs para quantizar os
erros das etapas anteriores
TE073 – Processamento Digital de Sinais II
83
Setor de Tecnologia
Universidade Federal do Paraná
Dep. Engenharia Elétrica

Adaptive VQ




Codebook Adaptativo
Conjunto de Codebooks
Forward e Backward approaches
Entropy Coded VQ

índices do codebook codificados com
códigos de tamanho variável, dependente
da probabilidade de ocorrência.
TE073 – Processamento Digital de Sinais II
84