Upload
jamal
View
21
Download
0
Embed Size (px)
DESCRIPTION
Conceitos Básicos em Codificação com Perdas. 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 : - PowerPoint PPT Presentation
Citation preview
1
Conceitos Básicos emConceitos Básicos em Codificação com Perdas Codificação com Perdas
TE073 – Processamento Digital de Sinais II 2
Setor de TecnologiaUniversidade 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 3
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Codificação com perdas:
Maior distorção possível: Perda total do sinalTaxa de compressão máxima!
Isto é, não necessita enviar dado nenhum.
Menor distorção possível: Codificação sem perdasTaxa de compressão dada pela entropia da fonte.
Teoria da Distorção pela Taxa(Rate Distortion Theory)
TE073 – Processamento Digital de Sinais II 4
Setor de TecnologiaUniversidade 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 5
Setor de TecnologiaUniversidade 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 6
Setor de TecnologiaUniversidade 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 7
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Problemas com este tipo de medida: Difícil de se computar, pois depende muito de pessoa parapessoa. 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 facilitamuito o projeto dos codificadores.
TE073 – Processamento Digital de Sinais II 8
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Medidas objetivas da distorção:
Geralmente baseadas em erros entre o sinal original e o reconstruído:
N
n
p
nnp yxN
yxd1
1),(
Onde: ),( yxd p É a distorção de ordem p entre o sinal original xe o sinal reconstruído y. N é o número de componentes (dimensões) dos sinais.
TE073 – Processamento Digital de Sinais II 9
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
N
nnn yx
Nd
11
1Média das diferenças absolutas
Medidas mais comuns:
N
nnnd yx
Nd
1
22
2 1 Erro médio quadrático (EMQ)Mean Squared Error (MSE)
Distância Euclidiana ao quadrado
....
nnn
yxd max Erro máximo.Usado em casos onde o erro só é percebidoAcima de um determinado limiar (threshold)
TE073 – Processamento Digital de Sinais II 10
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Considerando que a distorção imposta ao sinal original comosendo um ruído de codificação: dxy
Podemos ter medidas baseadas na relação Sinal-Ruído
2
2max
10
2
2
10
2
2
log.10][
log.10][
d
d
x
d
x
xdBPSNR
dBSNR
SNR
Energia do Sinal
Energia do Ruído (d2,EMQ,MSE)
Medida em dB
Relação sinal ruído de picoMuito usado em imagem: x2
max=2552
TE073 – Processamento Digital de Sinais II 11
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Medidas Objetivas: Matematicamente tratáveis.Não incorpora os aspectos da fidelidade perceptível
do ponto de vista humano.
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.
TE073 – Processamento Digital de Sinais II 12
Setor de TecnologiaUniversidade 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 sedeterminar 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:
Sistema Auditivo: modelo do ouvido e percepção de sons.Limitação 20Hz a 20KHz com resolução de 1000:11kHz a 20dB percepção semelhante a 50Hz a 50dB Mascaramento de nível sonoro e mascaramento espectral
02.0I
I
TE073 – Processamento Digital de Sinais II 13
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
7.5. Teoria da Distorção pela Taxa
0 10 20 30 40 500
100
200
300
400
500
600
700
800
900
1000
Taxa [kbits/seg]
Dis
torc
ao(E
MQ
)
cod1cod2
Ex.: 2 se cruzando (MPEG1 e MPEG2)
TE073 – Processamento Digital de Sinais II 14
Setor de TecnologiaUniversidade 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
221
,0
,log)(
2
D
DDR D
1002
0 20 40 60 80 100-0.2
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
Taxa
Dis
torc
ao
TE073 – Processamento Digital de Sinais II 15
Setor de TecnologiaUniversidade 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:
DeXhDRSLB ..2log)()( 21
Onde h(X) é a entropia diferencial da variável X
TE073 – Processamento Digital de Sinais II 16
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Problema: Para sinais reais é difícil definir sua função distribuiçãode probabilidade e assim calcular h(X).
Para distribuição Gaussiana: 221 ..2log)( eXh
Prova-se que h(X) da distribuição gaussiana é maior que qualqueroutra h(X) para a mesma variância (2).
TE073 – Processamento Digital de Sinais II 17
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
7.6. Modelos
7.6.1. Modelos Probabilísticos
Distribuição Uniforme:
outros
bxaparaabxf X
,0
,1
)(
Distribuição Gaussiana:
2
2
2
2.
2
1)(
x
X exf
Distribuição Laplaciana:
x
X exf2
2.
2
1)(
Distribuição Gamma:
2
34
.8
3)(
x
X ex
xf
Mais usada
Mais centrada em zero,Ex.: voz, dif. imagem
Mais centrada ainda em zero, menos tratável
modelo da ignorância
TE073 – Processamento Digital de Sinais II 18
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
TE073 – Processamento Digital de Sinais II 19
Setor de TecnologiaUniversidade 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
i
M
jnjnjinin bxax
1 1
Onde xn são as amostras do processo que desejamos modelare 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 20
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Se todos os bj forem zero. Fica apenas a componente autoregressiva.
N
ininin xax
1
Que é um filtro IIR com apenas pólos (all-pole) e também chamadomodelo autoregressivo de ordem N, AR(N), muito usado em compressãode voz.
Como a amostra atual depende apenas das N amostras anteriores:
),...,,|(,...),|( 2121 Nnnnnnnn xxxxPxxxP
Isto significa que um AR(N) é um processo de Markovde ordem N.
Ver exemplos no livro.
TE073 – Processamento Digital de Sinais II 21
Setor de TecnologiaUniversidade 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 detalhesoportunamente.
22
Quantização EscalarQuantização Escalar
TE073 – Processamento Digital de Sinais II 23
Setor de TecnologiaUniversidade 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 24
Setor de TecnologiaUniversidade 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,03,14159... 3,04,5 4,0 ou 5,0 (aleatoriamente).
TE073 – Processamento Digital de Sinais II 25
Setor de TecnologiaUniversidade 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 26
Setor de TecnologiaUniversidade 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 27
Setor de TecnologiaUniversidade 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 28
Setor de TecnologiaUniversidade 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 29
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Quantização Escalar
Códigos Saída 000 -3,5 001 -2,5 010 -1,5 011 -0,5 100 0,5 101 1,5 110 2,5 111 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 30
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Quantização Escalar
Ex: f(t) = 4.cos(2t), com amostras a cada 0,05 s
TE073 – Processamento Digital de Sinais II 31
Setor de TecnologiaUniversidade 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 32
Setor de TecnologiaUniversidade 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 33
Setor de TecnologiaUniversidade 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 34
Setor de TecnologiaUniversidade 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 35
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Quantizador Uniforme e Fonte Uniforme
O ruído de quantização se torna:
2
2
222
12
1dqqq
Assumindo que a variância dos valores de entrada no intervalo [ -Xmax , Xmax ] é:
12
2 22 maxs
X
TE073 – Processamento Digital de Sinais II 36
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Quantizador Uniforme e Fonte Uniforme
SNR: Signal Noise Ratio ou Razão Sinal Ruído:
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.
2
2
log10q
sdBSNR
TE073 – Processamento Digital de Sinais II 37
Setor de TecnologiaUniversidade 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 38
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
ImagemOriginal
1 bit/pixel
2 bits/pixel 3 bits/pixel
TE073 – Processamento Digital de Sinais II 39
Setor de TecnologiaUniversidade 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 40
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Erros de Combinaçã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.
idealModelos de distribuição
Parâmetros da distribuição{
TE073 – Processamento Digital de Sinais II 41
Setor de TecnologiaUniversidade 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 42
Setor de TecnologiaUniversidade 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 43
Setor de TecnologiaUniversidade 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 44
Setor de TecnologiaUniversidade 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 45
Setor de TecnologiaUniversidade 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).
Perda de resolução na amplitude.
Quantização uniforme.
TE073 – Processamento Digital de Sinais II 46
Setor de TecnologiaUniversidade 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 47
Setor de TecnologiaUniversidade 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 48
Setor de TecnologiaUniversidade 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 49
Setor de TecnologiaUniversidade 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 50
Setor de TecnologiaUniversidade 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 51
Setor de TecnologiaUniversidade 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 52
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Quantização Não Uniforme
TE073 – Processamento Digital de Sinais II 53
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Quantização Ótima ou Lloyd-MaxEncontrando {yj} e {bi}:
dxxf
dxxfxy
j
j
j
j
b
b x
b
b x
j
1
1
21 jj
j
yyb
Os valores de reconstrução são os centros das probabilidades em um determinado intervalo.
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 54
Setor de TecnologiaUniversidade 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 55
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Companded Quantization
Função similar à do quantizador não uniforme.
TE073 – Processamento Digital de Sinais II 56
Setor de TecnologiaUniversidade 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 57
Setor de TecnologiaUniversidade 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.
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.
Loyd-Max
58
QUANTIZAÇÃO QUANTIZAÇÃO VETORIALVETORIAL
TE073 – Processamento Digital de Sinais II 59
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
”Eu quis saber apenas como as coisas foram unidas."
TE073 – Processamento Digital de Sinais II 60
Setor de TecnologiaUniversidade 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 61
Setor de TecnologiaUniversidade 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 62
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia ElétricaQuantização Vetorial -
Funcionamento
Codificação:Agrupamento das amostras;Busca da “melhor” Codeword;Transmissão do Índice do Codebook;
Decodificação:Lookup Table;Desagrupamento;
TE073 – Processamento Digital de Sinais II 63
Setor de TecnologiaUniversidade 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;
2 2
j i iX Y X Y para todo Y C
L
i ixX1
22
A codeword Yj será a melhor representação do vetor X se:
TE073 – Processamento Digital de Sinais II 64
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
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
Vantagem da Quantização Vetorial sobre a Escalar
Quanto a distorção? Quanto a eficiência? Flexibilidade?
TE073 – Processamento Digital de Sinais II 65
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
1- Comece com um conjunto inicial de valores de reconstrução
onde: fixa-se k=0, D(0)=0 . Define-se o Threshold Miiy 1
)0(
O algoritmo de Lloyd Quantização Escalar
2- Determine os limites de decisão: j= 1, 2, 3 , ..., M-1.2
)()(1
kj
kjk
j
YYb
3- Compute a distorção:
M
i
b
b ik
ki
ki
dxxfxyxD1
2)()(
)(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;
)(
)1(1
)(
)1(1
)(
)()(
kj
kj
kj
kj
b
b
b
bkj
dxxfx
dxxxfxY
TE073 – Processamento Digital de Sinais II 66
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia ElétricaGeneralização do Algoritmo de Lloyd
(GLA)Quantização Vetorial
1- Comece com um conjunto inicial de valores de reconstrução {Yi(0)}i=1
M
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) ji} i=1, 2, ..., M-1;
3- Determine a distorção:
4- Se: ; pare, caso contrario, continue;
5- K=K+1. Determinar os próximos valores de reconstrução para {Yi(k)}i=1
M como as centróides do conjunto {Vi
(k-1)}
Retorne ao passo 2.
M
i
b
b
ki
kk
i
ki
dxxfxyxD1
2)()()(
)(1
)(
)(
)1()( )(k
kk
D
DD
TE073 – Processamento Digital de Sinais II 67
Setor de TecnologiaUniversidade 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 68
Setor de TecnologiaUniversidade 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 69
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Treinado os vetores1- 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=1
M são dadas por
Vi(k)={Xn : d(xn,Yi) < d(Xn,Yi) ji} 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: ; pare, caso contrario, continue;
5- k=k+1. Calcule novos valores de reconstrução {Yi(k)}i=1
M como a média dos vetores de cada região de quantização {Vi
(k-1)}
Retorne ao passo 2.
)(
)1()( )(k
kk
D
DD
TE073 – Processamento Digital de Sinais II 70
Setor de TecnologiaUniversidade 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 71
Setor de TecnologiaUniversidade 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 72
Setor de TecnologiaUniversidade 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 73
Setor de TecnologiaUniversidade 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 74
Setor de TecnologiaUniversidade 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 75
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
TE073 – Processamento Digital de Sinais II 76
Setor de TecnologiaUniversidade 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 77
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
Como definir a Sequência de Treino?
TE073 – Processamento Digital de Sinais II 78
Setor de TecnologiaUniversidade 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:Problemas:•Aumento da memória necessária ao Aumento da memória necessária ao CodebookCodebook•Aumento da complexidade computacional Aumento da complexidade computacional na codificaçãona codificação
TE073 – Processamento Digital de Sinais II 79
Setor de TecnologiaUniversidade 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 80
Setor de TecnologiaUniversidade 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 81
Setor de TecnologiaUniversidade Federal do ParanáDep. Engenharia Elétrica
TE073 – Processamento Digital de Sinais II 82
Setor de TecnologiaUniversidade 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
Q3
Q4
Classificador
índice1+indice2Vetor
TE073 – Processamento Digital de Sinais II 83
Setor de TecnologiaUniversidade 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 84
Setor de TecnologiaUniversidade 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.