Codificação Diferencial
1
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Introdução

Formas de quantização (perdas):


Quantização Escalar

Uniforme / não-uniforme

Side information
Quantização Vetorial



Codebook e Codeword
Ótimas taxas
Complexo computacionalmente
TE073 – Processamento Digital de Sinais II
2
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Introdução

Codificação Diferencial




Codificação das diferenças
Aplicação: Voz
Sinal amostrado {xn}
Ex 1. Senóide
dn = { xn – xn-1 }


Menor Faixa Dinâmica
Menor Variância:
Amostras mais centradas
em zero.
TE073 – Processamento Digital de Sinais II
3
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Ex 2. Imagem Sinan
Histograma original
Histograma das diferenças
8 bits

7 bits
99%-> 5bits
TE073 – Processamento Digital de Sinais II
4
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Exemplo 3:
Considere a sequência:
x={6.2 9.7 13.2 5.9 8.0 7.4 4.2 1.8}
A sequência diferença será:
d [n]  x[n]  x[n  1]
d={6.2 3.5 3.5 -7.3 2.1 -0.6 -3.2 -2.4}
Se codificarmos sem perdas, voltamos à seqüência original fazendo:
Porém:
Quantizando com perdas [-6 -4 -2 0 2 4 6]: x[n]  x[n  1]  d [n]
d={6 4 4 -6 2 0 -4 -2}
Reconstruindo temos: xq={6 10 14 8 10 10 6 4}
n
Que corresponde ao erro de quantização:
xq [n]  x[n]   q[k ]
{0.2 -0.3 -0.8 -2.1 -2.0 -2.6 -1.8 -2.2}
k 1
crescente!
TE073 – Processamento Digital de Sinais II
5
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Mesmo erro de quantização tendo média zero, pode causar overflow
x[n]
+
d[n]
Q
-
z-1
dq[n] dq[n]
Q-1
+
xq[n-1]
x[n-1]
xq[n]
+
z-1
d [n]  x[n]  x[n  1]
•Solução:
x[n]
+ d[n]
-
Q
dq[n]
+
+
z-1
xq[n-1]
d[n]  x[n]  xq [n  1]
dq[n]
xq[n]
+
Q-1
+
xq[n-1]
z-1
xq[n]
TE073 – Processamento Digital de Sinais II
6
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Ex 4. Sinal senoidal
Aproximação I
•
Intervalo dinâmico de
diferenças: [-0,2 0,2]
•
Passo do quantizador = 0,1
Aproximação II
•
Intervalo dinâmico de
diferenças: [-0,4 0,4]
•
Passo do quantizador = 0,2
TE073 – Processamento Digital de Sinais II
7
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Generalização:
Preditor:
Se:
p[n]  f  xq [n 1], xq [n  2], xq [n  3],...., xq [0]
p[n]  xq [n  1] Temos o DPCM
(Differential Pulse Code Modulation)
TE073 – Processamento Digital de Sinais II
8
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Adaptativo


Direto

Side information transmitida ao decodificador

Separação em blocos (estimativas por bloco)
Reverso



Não há necessidade de side info – adaptação obtida da saída
do decodificador.
Mais utilizado
Algoritmo de Jayant
TE073 – Processamento Digital de Sinais II
9
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Modulação Delta

Quantizador de 1-bit (2 níveis)
Variação da taxa de amostragem

Slope overload

TE073 – Processamento Digital de Sinais II
10
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Ex.: Codificação de Voz

Principal aplicação de codificadores
diferenciais (ADPCM)


Vários padrões ITU (G.721, G.723, G.722,...)
G.726
Quantização adaptativa reversa
 Algoritmo de quantização similar a Jayant
 Predição reversa adaptativa
 Combinação linear dos 2 últimos valores reconstruídos
 Uso dos 6 últimos diferenças quantizadas para a predição
 (40, 32, 24 e 16 kbits)
 8000 amostras
 5, 4, 3, 2 bits/amostra
Comparando com PCM (8bits /amostra):
Taxas de compressão 1,6:1 2:1 2,67:1
4:1
respectivamente

TE073 – Processamento Digital de Sinais II
11
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Codificação de Imagem

Comparação com JPEG
PSNR=31.42dB
PSNR=41.60dB
TE073 – Processamento Digital de Sinais II
12
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
PSNR=38.28dB
PSNR=41.60dB
TE073 – Processamento Digital de Sinais II
13
Conceitos Básicos para
Transformadas, Subbandas e
Wavelets
14
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Para entendermos os conceitos utilizados em codificação
por transformada, subbandas e wavelets é necessário um
conhecimento prévio dos seguintes assuntos:
• Espaços Vetoriais
• Série de Fourier
• Transformada de Fourier
• Sistemas Lineares
• Amostragem
• DFT
• Transformada Z
Já vistos em DSP-I
TE073 – Processamento Digital de Sinais II
15
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
11.3. Espaços Vetoriais
Representação de um vetor no espaço 2-D:
v  4.u x  3u y
3
4
v 
3 
4
Logo: um vetor pode ser representado como uma decomposição
em vetores base (ux, uy).
Qualquer vetor neste espaço 2-D pode ser decomposto.
TE073 – Processamento Digital de Sinais II
16
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Então, dado um vetor A e um conjunto base, a decomposição
significa encontrar os coeficientes os quais ponderam os vetores
unitários do conjunto base.
Ferramenta matemática: Produto Escalar ou Interno
TE073 – Processamento Digital de Sinais II
17
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
11.3.1. Produto Escalar ou Produto Interno
Dado dos vetores:
a1 
a 
 a2 
O produto interno é definido por:
e
b1 
b 
b2 
a  b  a1b1  a2b2
Dois vetores são ditos ortogonais se seu produto interno é zero.
Um conjunto de vetores é dito ortogonal se cada vetor for ortogonal
a todos os outros vetores do conjunto.
TE073 – Processamento Digital de Sinais II
18
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
O produto interno entre um vetor e um vetor unitário de um
conjunto base ortogonal nos fornece o coeficiente correspondente
a aquele vetor.
E pode ser visto também como a projeção do vetor sobre o vetor
da base.
1 
0
Ex.: Seja a base ortogonal: u x    , u y   
0
1 
Claramente: ux  u y  0
E um vetor a pode ser decomposto em:
a  u x  a1 1  a2  0  a1
a  u y  a1  0  a2 1  a2
TE073 – Processamento Digital de Sinais II
19
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
u
y
b
a
ux
O produto interno entre dois vetores pode representar, com
um certo cuidado, uma medida de similaridade entre eles
a é mais próximo de ux logo:
a  ux  a  u y
TE073 – Processamento Digital de Sinais II
20
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
11.3.2. Espaço Vetorial
Generalizando os conceitos vistos em 2-D e 3-D:
Espaço vetorial consiste em um conjunto de elementos
chamados vetores que têm as operações de adição vetorial
e multiplicação escalar definidas. Os resultados destas operações
são também elementos deste espaço vetorial
TE073 – Processamento Digital de Sinais II
21
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Adição Vetorial:
Sejam os vetores:
Definimos:
a1 
a  a2  ,
a3 
b1 
b  b2 
b3 
a1  b1 
a  b  a2  b2 
a3  b3 
Multiplicação Escalar:
Multiplicação de um vetor por um numero real ou complexo.
Para que o conjunto de elementos seja um espaço vetorial
é necessário que cumpra os seguintes axiomas:
TE073 – Processamento Digital de Sinais II
22
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Seja: V um espaço vetorial
x,y,z vetores e  e  números escalares
1. x+y=y+x comutatividade
2. (x+y)+z=x+(y+z) e
()x= (x) associatividade
3. Existe elemento  em V tal que x+ =x para todo x V
4. (x+y)= x+ y
e
(+)x= x+x distributividade
5. 1.x=x e 0.x= 
6. Para todo x V existe elemento (-x) tal que x+(-x)= 
Ex.: Um exemplo de espaço vetorial são os números reais,
neste conjunto: zero= 
TE073 – Processamento Digital de Sinais II
23
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Outro exemplo de espaço vetorial: conjunto das funções f(t)
2
que possuem energia finita:

 f (t ) dt  

Neste caso: (t)=0
E o espaço vetorial é chamado L2
TE073 – Processamento Digital de Sinais II
24
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
11.3.3. Subespaço
Um subespaço S de um espaço vetorial V é um subconjunto
de V cujos membros satisfazem todos os axiomas do espaço
vetorial e têm a propriedade adicional que se x e y  S,
e  é um escalar, então x+y e x estão também em S.
Ex.: Considere S o conjunto das funções limitadas ao
intervalo [0,1]. Então S é um subspaço de L2
TE073 – Processamento Digital de Sinais II
25
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
11.3.4. Bases
Uma das formas de se gerar um subespaço é fazendo
combinações lineares de um conjunto de vetores.
Se o conjunto de vetores for linearmente independente, o
conjunto é chamado de base para o subespaço.
Um conjunto de vetores {x1,x2,...} é dito linearmente
independente se nenhum vetor do conjunto puder ser escrito
como uma combinação linear dos outros vetores do conjunto.
TE073 – Processamento Digital de Sinais II
26
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Teorema:
Um conjunto de vetores X={x1,x2,...,xN} é linearmente independente
N
Se e somente se a expressão
 i x i  
i 1
Implicar que i  0 para todo i=1,2,...,N
TE073 – Processamento Digital de Sinais II
27
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
T,
Seja
o
espaço
vetorial
V
dos
vetores
definidos
por
[a
b]
Ex.:
onde a e b são números reais.
1  0 
X 1    ,   
0 1  
e
1 0 
X 2    ,   
1 1  
São bases de V.
Quaisquer 2 vetores não paralelos formam uma base para V.
O número de vetores necessários para gerar o espaço é chamado
dimensão do espaço vetorial.
No exemplo: Dimensão 2
No exemplo anterior, espaço das funções limitadas [0,1] de L2
possui dimensão infinita.
TE073 – Processamento Digital de Sinais II
28
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
3 
Ex.: Seja o vetor a   
 4
1  0
a  3   4 
0 1 
1
1 
a  4   (1) 
1
0
Então a representação de a na base X1 é (3,4) e na
base X2 é (4,-1)
TE073 – Processamento Digital de Sinais II
29
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
11.3.5. Definição formal do produto interno
O produto interno pode ser denotado como:
x  y  x, y
Satisfaz os seguintes axiomas:
1.
2.
3.
4.
<x,y>=<y,x>*
<x+y,z>=<x,z>+<y,z>
<x,y>= <x,y>
<x,x>0 com equalidade se e somente se x=
x, x  x
É chamada norma de x e é análogo à distância
TE073 – Processamento Digital de Sinais II
30
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
11.3.6. Conjuntos Ortogonais e Ortonormais
No espaço Euclidiano, dois vetores são ditos ortogonais se seu
produto interno for zero.
Se selecionarmos conjunto base formada por vetores ortogonais
e ainda se a norma desses vetores for unitária, o conjunto é
chamado
Base Ortonormal.
TE073 – Processamento Digital de Sinais II
31
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Dada um espaço vetorial SN com uma base ortonormal
{xi} i=1,2..N. Dado um vetor y no espaço SN podemos
escrever y como uma combinação linear dos vetores xi
N
y   i x i
i 1
Para encontrar os coeficientes i , podemos tirar o produto
Interno de ambos os lados com respeito a xi
N
y, x k   i x i , x k
i 1
TE073 – Processamento Digital de Sinais II
32
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Como a base é ortonormal:
Logo:
xi , x k
1, i  k

0, i  k
y,x k  k
TE073 – Processamento Digital de Sinais II
33
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Conclusões:
• Vetores não são simplesmente pontos nos espaços 2-D e 3-D.
Funções do tempo podem serem vistas como elementos de um espaço
vetorial.
• Conjuntos de vetores que satisfazem a certos axiomas formam um espaço
vetorial
•Todos os membros de um espaço vetorial podem ser representados como
combinações lineares dos vetores bases (podem ter diferentes bases para um
mesmo espaço). As bases formadas por vetores de magnitude unitária e
ortogonais são conhecidas como bases ortonormais.
•Se uma base é ortonormal os coeficientes podem ser obtidos tirando o
produto interno do vetor com cada vetor da base.
TE073 – Processamento Digital de Sinais II
34
Codificação Por Transformada
35
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Introdução

Fonte é decomposta ou transformada em componentes
de modo que a energia fique concentrada em poucas
amostras.

Para uma fonte gaussiana a entropia é dada por:
1
log 2e 2
2

O aumento da variância causa um aumento na
entropia, o que mede a quantidade de informação
contida no sinal.
TE073 – Processamento Digital de Sinais II
36
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Ex: Analisando a sequência de dois números,
representando peso e altura:
Peso
Altura
65
170
75
188
60
150
70
170
56
130
80
203
68
160
50
110
40
80
50
153
69
148
62
140
76
164
64
120
TE073 – Processamento Digital de Sinais II
37
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Podemos observar que os valores estão ao redor da reta
y=2.5x

Podemos rotacionar o conjunto de valores usando:
  Ax
 cos sin  
A

 sin  cos 
 x0 
x 
 x1 
 0 
  
 1
Onde  é o ângulo da reta com eixo x   arctan  2.5  68o
TE073 – Processamento Digital de Sinais II
38
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
 0,37139068 0,92847669
A


0
,
92847669
0
,
37139068


Peso
Altura
1o
2o
65
170
182
3
75
188
202
0
60
150
162
0
70
170
184
-2
56
130
141
-4
80
203
218
1
68
160
174
-4
50
110
121
-6
40
80
90
-7
50
153
161
10
69
148
163
-9
62
140
153
-6
76
164
181
-9
64
120
135
-15
  A.x
TE073 – Processamento Digital de Sinais II
39
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica



A energia foi compactada no primeiro elemento.
Desenhando o gráfico temos:
Podemos ignorar a segunda coordenada de , causando um
erro, porém reduzindo a quantidade de dados pela metade!
TE073 – Processamento Digital de Sinais II
40
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Fazendo a anti-transformação podemos recuperar os dados x.
cos  sin  
A1  

 sin  cos 
Reconstruído
Original
1o
2o
Peso
Altura
Peso
Altura
182
0
68
169
65
170
202
0
75
188
75
188
162
0
60
150
60
150
184
0
68
171
70
170
141
0
53
131
56
130
218
0
81
203
80
203
174
0
65
162
68
160
121
0
45
112
50
110
90
0
34
84
40
80
161
0
60
150
50
153
163
0
61
151
69
148
153
0
57
142
62
140
181
0
67
168
76
164
135
0
50
125
64
120
x  A .
1
TE073 – Processamento Digital de Sinais II
41
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
O erro de reconstrução foi pequeno pois nessa transformação
em particular temos:
N 1
  xi  xˆi 
i 0



2
N 1

  i  ˆi
i 0

2
Neste exemplo foi utilizada apenas duas dimensões, mas
o princípio pode ser expandido para mais dimensões.
Com duas dimensões podemos reduzir os dados em um
fator de 2, com mais dimensões esse fator pode aumentar.
Descartar as componentes com menor quantidade de
informação (menor entropia) (menor variância)
TE073 – Processamento Digital de Sinais II
42
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica




Prova-se que a melhor compactação ocorre quando
descorrelacionamos as amostras da transformada.
A descorrelação de dados discretos foi introduzida
em 1933 por Hotteling.
Em 1947, Karhunen e em seguida, 1948, Loève
desenvolveram a transformação para funções
contínuas.
Kramer e Mathew em 1956 utilizaram esses
conceitos da descorrelação, para codificação de
sinais, gerando então o termo codificação por
transformada.
TE073 – Processamento Digital de Sinais II
43
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

A codificação por transformada consiste em três
passos:


A seqüência de dados é dividida em blocos de tamanho N
e mapeada em seqüências transformadas, usando um
mapeamento reversível.
Quantizar a seqüência transformada




Taxa de bits que eu desejo conseguir?
A estatística dos elementos transformados?
Efeitos de distorções causados pela quantização?
Binary encoding
TE073 – Processamento Digital de Sinais II
44
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
A Transformada

Todas as transformadas que veremos são transformadas
lineares, podendo serem representadas por:
N 1
 n   xi an,i
i 0
N 1
xn  i bn,i
i 0
O tamanho N do bloco é definido por considerações práticas,
tais como: Taxa de compressão versus complexidade computacional

Em sinal de voz mudanças radicais como a passagem do
silêncio para a conversa dificultam a implementação de N
grandes. O mesmo acontece em imagem.
TE073 – Processamento Digital de Sinais II
45
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

A transformada pode ser escrita na forma matricial:
  Ax
x  B

onde A e B são matrizes N×N
A : Matriz Transformada Direta
B : Matriz Transformada Inversa
[ A]i , j  ai , j
[ B]i , j  bi , j
AB  BA  I

Se a transformada é ortonormal ela tem a propriedade de que a
inversa é a própria transposta.
B  A 1  A T
TE073 – Processamento Digital de Sinais II
46
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica


A eficiência da transformada depende da compactação de
energia.
Uma das maneiras de medir a compactação é tirar a média
aritmética da variância dos coeficientes de transformação.
GTC
1
 N
2

i  0 i

N 1
N 1
i 0


1
2
i
N
Ganho de Codificação da Transformada
TE073 – Processamento Digital de Sinais II
48
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Ex: Considere a matriz
1 1 1 
A
1  1
2



Note que a primeira linha representa um filtro passa-baixa
e a segunda um passa alta
Supondo a sequência de entrada sendo ( ,  )
 0 
1 1 1     2 

  
1  1    
2
   0 
 1
TE073 – Processamento Digital de Sinais II
Coeficiente de
baixa-frequência
49
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica


Analisando duas outras seqüências (3,1) e (3,-1)
A segunda é mais alta frequência que a primeira, pois
difere de 4 enquanto a outra de 2. Teremos:
 0  1 1 1  3 2 2 

  
1  1 1  
2
   2 
 1
 0  1 1 1   3   2 

  
1  1  1  
2
   2 2 
 1

Observe que a energia da sequência transformada é igual a da
original, caracterizando uma transformada ortonormal.
2
2  ( 2 2 ) 2  12  32
TE073 – Processamento Digital de Sinais II
50
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Transformada Karhunen-Loéve


As linhas da transformada discreta KLT consiste nos
autovetores da matriz de autocorrelação da sequência.
A matriz de autocorrelação para um processo randômico X
é dada por:

[ R]ij  E X n X n i  j



A matriz construída desta forma reduz a variância dos
coeficientes da transformada. Resultando na Transformada
Ótima do ponto de vista de compactação da energia.
Transformada dependente do sinal: Grande informação
Lateral
TE073 – Processamento Digital de Sinais II
51
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Transformada Karhunen-Loéve


Ex: KLT tamanho 2
A matriz de autocorrelação de tamanho 2 é:
 Rxx (0) Rxx (1) 
R

R
(
1
)
R
(
0
)
xx
 xx


Resolvendo a equação
I  R  0

Temos os autovalores
1  Rxx (0)  Rxx (1)
2  Rxx (0)  Rxx (1)
TE073 – Processamento Digital de Sinais II
52
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Transformada Karhunen-Loéve

Os autovetores associados são
 
V1   
 


 
V2   
  
Impondo as condições de ortonormalidade
1
  
2
1 1 1 
A matriz da transformada é K 
1  1
2

TE073 – Processamento Digital de Sinais II
53
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Discrete Cosine Transform (DCT)

Tem este nome porque a matriz de transformada é obtida
em função do cosseno, segundo a regra:
C i, j






1
(2 j  1)i
cos
N
2N
i  0, j  0...N  1
2
(2 j  1)i
cos
N
2N
i  1...N  1, j  0...N  1
TE073 – Processamento Digital de Sinais II
54
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Funções base da DCT:
TE073 – Processamento Digital de Sinais II
55
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica


Parecida com a DFT porém a DCT é melhor para efeitos
de compactação
A DFT considera que a seqüência é periódica de período
N, introduzindo descontinuidades no final da seqüência,
interferindo nas altas frequências.
TE073 – Processamento Digital de Sinais II
56
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

A DCT duplica a seqüência N porém em espelho, não
gerando descontinuidades e gerando periodicidade na
seqüência 2N.
TE073 – Processamento Digital de Sinais II
57
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Discrete Sine Transform (DST)


A DCT obtém performance tendendo a KLT para
coeficientes de correlação altos e a DST para valores
baixos de correlação.
É utilizada de forma complementar a DCT em aplicações
de áudio e image
S ij 
2
 (i  1)( j  1)
sin
N 1
N 1
i, j  0,...N  1
TE073 – Processamento Digital de Sinais II
58
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Discrete Walsh-Hadamard Transform (DWHT)




Baixa complexidade computacional
Não tão eficiente quanto a DCT
Matrizes de Hadamard
DWHT: Ortonormal
logo:
1
H1 
1
1
1 1 1 
H2 


2 1 1
H2N
H N

H N
HN 
 H N 
1 1 1 1 
1 1 1 1
1 

H4 
4 1 1 1 1


1 1 1 1 
TE073 – Processamento Digital de Sinais II
59
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Quantização dos Coeficientes

Cada coeficiente possui uma quantidade de
informação diferente, logo alocar diferentes números
de bits para quantizar escalarmente cada coeficiente.

Duas approaches:



Alocar o número de bits baseado em estatísticas dos coeficientes
(variância). Coeficiente com > variância recebe mais bits.
Classificar várias matrizes de quantização de acordo com
características do sinal de entrada.
Quantizar vetorialmente o bloco de transformada:
Medida da distância ponderada pela variância dos
coeficientes.
TE073 – Processamento Digital de Sinais II
60
Codificação por Subbandas
61
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Introdução

Do que vamos tratar?



Uma descrição geral de sistemas de
codificação subbandas.
Uma descrição de uma aproximação
popular de alocação de bit.
Aplicações de compressão de áudio e
vídeo.
TE073 – Processamento Digital de Sinais II
62
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Introdução

Nós vimos:
Quantização Vetorial
Quantização Escalar
Codificação Diferencial
Porém, existem fontes que combinam várias características e
é difícil determinar qual tipo de codificação utilizar.

Codificação por Transformada = decompõe o sinal em uma
estrutura (bloco) artificial, gerando efeitos indesejáveis de
blocagem (Lapped Orthogonal Transform (LOT) - Malvar 92)

TE073 – Processamento Digital de Sinais II
63
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica



Decompor o sinal em diferentes partes sem uma
imposição de estrutura.
Usar a técnica de codificação que mais se adeque
a cada parte.
Adequar a alocação de bits de acordo com
características da percepção humana
TE073 – Processamento Digital de Sinais II
64
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Fazendo:
Filtragem PB
xn  xn 1
yn 
2
Filtragem PA
xn  xn 1 xn  xn 1
z n  xn  y n  xn 

2
2
Desta forma a seqüência {yn} e {zn} podem ser
codificadas independentemente, usando o esquema de
compressão que é mais adequado para cada seqüência.
TE073 – Processamento Digital de Sinais II
65
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Exemplo:

Suponha que quiséssemos codificar a seqüência:
xn = {10, 14, 10, 12, 14, 8, 14, 12, 10, 8, 10, 12}

Utilizando DPCM:
xn –xn-1= {10, 4, -4, 2, 2, -6, 6, -2, -2, -2, 2, 2}
Então utilizaremos M=2m níveis de quantização, Faixa
dinâmica [-6,6] e o intervalo de quantização (delta) será:
12

M
e o erro máximo de quantização:
TE073 – Processamento Digital de Sinais II
 6

2 M
66
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Vamos gerar então duas novas seqüências {yn} e {zn}:
xn=yn+zn
Então para yn temos:
{10, 12, 12, 11, 13, 11, 11, 13, 11, 10, 9, 11}
A sequência yn é mais suave que xn.
TE073 – Processamento Digital de Sinais II
67
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Considerando a seqüência das diferenças de yn:
{10, 2, 0, -1, 2, -2, 0, 2, -2, -1, -1, 2}
Note que a faixa dinâmica reduziu de [-6,6] para [-2,2]
TE073 – Processamento Digital de Sinais II
68
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Notamos que o passo de quantização agora é 4/M
e portanto o máximo erro de quantização será
2/M.
No entanto precisamos ainda transmitir zn
{0, 2, -2, 1, 1, -3, 3, -1, -1, -1, 1, 1}
Faixa dinâmica: 6, metade da faixa de {xn}.
Precisamos apenas 6/M níveis. Dando um erro
máximo de quantização de 3/M.
Erro de quantização total = 5/M
TE073 – Processamento Digital de Sinais II
69
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Então:


Para um mesmo número de bits teremos menos erro!
PORÉM
Teremos o dobro da taxa de bits! Pois temos o dobro
do número de amostras a quantizar e transmitir.
Como evitar?
Transmitindo apenas os número pares.
x2 n  x2 n 1
2
x x
z 2 n  2 n 2 n 1
2
y2 n 
Na reconstrução:
y2 n  z2 n  x2 n
y2 n  z2 n  x2 n1
TE073 – Processamento Digital de Sinais II
70
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Exemplo – (Conclusão)



Decompondo a seqüência {xn} em
subseqüência, não resulta num incremento dos
valores a serem transmitidos.
As duas subsequencias são distintas e podem
ser codificadas diferentemente.
Nós podemos usar a mesma aproximação na
decomposição das duas seqüências.
TE073 – Processamento Digital de Sinais II
71
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica


Então:
xn  xn 1
yn 
2
xn  xn 1
zn 
2
Podemos implementar estas operações
usando filtros discretos.
TE073 – Processamento Digital de Sinais II
72
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Filtros


Magnitude da Função de Transferência – relação da
magnitude da entrada e saída do filtro em função da
freqüência.
Filtro Ideal x Filtro Real
TE073 – Processamento Digital de Sinais II
73
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Filtros

Critério de Nyquist : fa = 2.fo





Sinais Passa-Banda: fa=2.B
Aliasing.
Forma geral da relação de entrada-saída de
um filtro:
FIR
IIR
N
M
i 0
i 1
yn   ai xn i  bi yn i
TE073 – Processamento Digital de Sinais II
74
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Alguns Filtros Usados na Codificação Subbanda


Filtros QMF (Quadrature Mirror Filter) – PR (Perfect Reconstruction)
Filtros Espelhados em Quadratura de Reconstrução Perfeita
Propriedades do Filtro QMF - Johnston:
 Passa baixa -> {hn}
n
 Passa alta -> {(-1) .hN-1-n}
 O filtro é simétrico ou seja:
hN-1-n = hn
n=0,1,...,N/2 -1
TE073 – Processamento Digital de Sinais II
75
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Passa  Baixas {hn }
Passa  Altas
TE073 – Processamento Digital de Sinais II
 1
n
hN 1n

76
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
TE073 – Processamento Digital de Sinais II
77
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica


Filtro Johnston
Filtro Smith-Barnwell
A freqüência de corte do
filtro smith-barnwell é bem
melhor definida do que a
freq. do filtro de Johnston.

TE073 – Processamento Digital de Sinais II
78
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Algoritmo de Codificação Subbanda
TE073 – Processamento Digital de Sinais II
79
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Quantização e Codificação


Alocação de bits entre as subbandas.
Cada subbanda possui uma quantidade
diferente de informação.

Exemplo: Forma de alocar 4 bits em 4 subbandas.
TE073 – Processamento Digital de Sinais II
80
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Síntese


Upsampling – insere zeros – filtragem pelos filtros de
reconstrução- Soma das componentes
3 maiores componentes do sistema:





análise e síntese de filtros;
esquema de alocação de bits;
esquema de codificação.
Separação em bandas ->Possibilidade de formas
inovadora para o uso dos algoritmos de compressão.
Percepção humana (audio e visual) depende da
frequência, logo podemos alocar melhor os bits.
TE073 – Processamento Digital de Sinais II
81
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Design de Bancos de Filtros

Vamos analisar:



downsampling
upsamplig
síntese de operação
TE073 – Processamento Digital de Sinais II
82
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Design de Bancos de Filtros
TE073 – Processamento Digital de Sinais II
83
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Design de Bancos de Filtros
TE073 – Processamento Digital de Sinais II
84
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Dowsampling e Upsampling
TE073 – Processamento Digital de Sinais II
85
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Dowsampling e Upsampling
TE073 – Processamento Digital de Sinais II
86
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Reconstrução Perfeita Usando Bancos de
Filtros de 2 Canais
TE073 – Processamento Digital de Sinais II
87
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Filtros de QMF-PR de dois canais.
TE073 – Processamento Digital de Sinais II
88
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Filtros FIR Fortemente Simétricos

Neste método o aliasing, distorção de
amplitude e fase podem ser
completamente eliminados.
TE073 – Processamento Digital de Sinais II
89
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Banco de Filtros QMF com M-Bandas
TE073 – Processamento Digital de Sinais II
90
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Banco de Filtros QMF com M-Bandas


Somente
é
viável
utilizá-los quando a
característica espectral
do filtro é boa.
Quando o número de
estágios
aumentam
ocorre a sobreposição
entre as bandas e
consequentemente
aliasing.
TE073 – Processamento Digital de Sinais II
91
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Banco de Filtros QMF com M-Bandas

o conjunto de filtros pode ser substituído por
apenas um filtro e em seguida ser feito a
redução das amostras.
A( z)  H L ( z).H L ( z 2 ).H L ( z 4 )
TE073 – Processamento Digital de Sinais II
92
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Alocação de Bits
Quanto recurso de codificação deve ser usado para codificar a saída de cada
filtro sintetizado. Em outras palavras, precisamos alocar os bits entre as
subbandas.
Suponhamos um sistema dividido em M subbandas onde a média de bits por
amostra é conhecida, então:
1
R
M
M
R
k 1
k
Desejamos encontra Rk tal que R seja minimizado e o erro de reconstrução
seja mínimo.
Onde na curva de distorção eu devo operar para que eu possa minimizar a
distorção média?
TE073 – Processamento Digital de Sinais II
93
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Alocação de Bits

Yaacov Shoham e Allen Gersho
(1988)
J k  Dk  .Rk

Como deve ser o valor de λ e como ele deve
variar entre as subbandas?


Deve-se buscar o lambda que melhor cumpra os
requerimentos do seu problema.
Mesmo lambda para todas as subbandas
TE073 – Processamento Digital de Sinais II
94
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Alocação de Bits



Normalmente não temos a curva de taxa de
distorção.
Caso o número de amostras em cada subbanda
é o mesmo.
Do contrário:

É dado peso para cada subbanda, então:
J k   Dk  . k Rk
De forma geral:
J k   wk Dk  . k Rk
TE073 – Processamento Digital de Sinais II
95
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Aplicação para Codificação de Voz – G.722



Padrão da ITU para codificação em bandalarga.
Codificação de alta qualidade à 64kbps (56kbps e
48kbps).
Processo:



Saída de áudio passa por um filtro de 7kHz para prevenir
aliasing em seguida é amostrada em 16.000 amostras/s.
Cada amostra é quantizada com 14bits/amostra através de uma
quantizador uniforme.
As amostras são passadas em um banco de filtros (2 filtros FIR)
de 24 coeficientes cada.
TE073 – Processamento Digital de Sinais II
96
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Aplicação para Codificação de Voz – G.722





P.B -> freqüências menores que 4kHz. P.A.
outras.
A saída do filtro é decimada por um fator de 2.
A sequencia decimada é codificada utilizando
ADPCM.
O sistema ADPCM usa 6 bits/amostra para o
filtro P.B. e 2 bits/amostra para o P.A.
O sistema portanto possui:
Tx  (6[bits]  2[bits]).8k[amostras/ s]  64kbps
TE073 – Processamento Digital de Sinais II
97
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Aplicação para Codificação de Áudio –
MPEG Áudio

Esquema de codificação de áudio proposto pelo MPEG.

Atualmente já propôs 3 esquemas de codificação: Layer 1, Layer 2 e Layer 3 – Todos
com back compatibility (decoder layer N pode decodificar os anteriores).

Layers 1 e 2 – Banco de 32 filtros, dividindo a entrada em 32 bandas, cada um com
uma banda de fs/64.

fs permitidas são: 32k, 44,1k e 48k amostras/s.

A saída é quantizada utilizando um quantizador uniforme com um número variado
de bits. Número de bits é determinado pelo modelo psicoacústico.

Sinal de amplitude alta em uma freq. afeta a audibilidade do sinal em outra freq.,
então podemos tolerar mais erros de quantização nas bandas vizinhas e usar poucos
bits.
TE073 – Processamento Digital de Sinais II
98
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Aplicações na Compressão de Imagens.

O que fazer quando temos seqüências de dados
bidimensionais?







Utilizar filtros bidimensionais, ou seja, que separem a
saída da fonte em componentes baseadas nas freq.
verticais e horizontais.
Normalmente implementado em 2 x 1 dimensional.
Chamados filtros “separáveis”.
Filtros bidimensionais não-separáveis são extremamente
complexos.
Geralmente a imagem é filtrada linha a linha
utilizando filtros P.A. e P.B.
A saída do filtro é decimada por um fator de 2.
O mesmo é feito com as colunas.
Resultando numa imagem N/2 x N/2.
TE073 – Processamento Digital de Sinais II
99
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
TE073 – Processamento Digital de Sinais II
100
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
TE073 – Processamento Digital de Sinais II
101
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
TE073 – Processamento Digital de Sinais II
102
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
TE073 – Processamento Digital de Sinais II
103
Codificação baseada em wavelets
104
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
INTRODUÇÃO

Por que wavelets?
 Transformada de Fourier  Apenas resolução na
freqüência, sem resolução no tempo.
 Função temporal f(t)  Apenas resolução no tempo, sem
resolução na freqüência.
 Problema com a STFT (Short-Term Fourier Transform) 
Largura fixa da janela
TE073 – Processamento Digital de Sinais II
105
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
STFT
WAVELETS
TE073 – Processamento Digital de Sinais II
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Representação de função em termos de
wavelets 



localização no tempo e na freqüência
alta resolução em freqüência em baixas
freqüências (janela de tempo maior)
alta resolução no tempo em altas freqüências
(janela de tempo menor)
TE073 – Processamento Digital de Sinais II
107
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Itens:



construção de wavelets;
descrição de como obter uma
decomposição de um sinal utilizando
análise em multiresolução;
descrição de alguns esquemas populares
para compressão de imagens
TE073 – Processamento Digital de Sinais II
108
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Transformada wavelet contínua
w   
s,

s ,
(t ), f (t ) 
 f (t )

s ,
(t )dt
s = variável escala
= variável translação
 Transformada wavelet inversa:
f (t )   w( s, ) dds
s ,
TE073 – Processamento Digital de Sinais II
109
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
As wavelets são geradas a partir de uma única
wavelet básica (wavelet mãe), (t), através de
translações e escalamentos:
1  t  
 s, (t )  s   s 
s = fator de escala
 = fator de translação
s = normalização de energia
 As funções base wavelets não são especificadas.
Esta é uma diferença entre a transformada wavelet e
outras transformadas
TE073 – Processamento Digital de Sinais II
110
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Propriedades de wavelets

Condição de admissibilidade
 ( )
  d  
2
Pode ser utilizada para analisar e reconstruir um sinal sem perda de
informação.
Implica que:
 Wavelets têm espectro de potência passa-faixa
 ( )
2
 0
0
 O valor médio da wavelet no domínio do tempo é zero (tem
que ser oscilatória).
 (t )dt  0
TE073 – Processamento Digital de Sinais II
111
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
• Condição de regularidade
• A função wavelet deve ser suave
• diminuir rapidamente com a escala s
• ter concentração nos domínios do tempo e da freqüência.
• Exemplo de wavelet mãe
Wavelet de Haar:
 1
 (t )  
 1
0  t  0,5
0,5  t  1
TE073 – Processamento Digital de Sinais II
112
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Wavelets discretas
As versões discretas dos parâmetros de escala e de
translação devem estar relacionadas entre si: se a escala
é tal que as funções de base são estreitas, o passo de
translação deve ser pequeno, e vice-versa.
 s  s0  j
Selecionaremos s e  da seguinte maneira: 
j


k

s

0 0
Portanto:
 j ,k (t )  s0  ( s0 t  k 0 )
j/2
j
j, k  Z
TE073 – Processamento Digital de Sinais II
113
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
• Normalmente, escolhemos s0=2, de tal maneira que
a amostragem do eixo da freqüência seja diádica.
• Escolhemos o fator de translação como 0=1, de
modo que a amostragem no eixo do tempo também
seja diádica.
 j ,k (t )  2  (2 t  k )
j/2
j
Os coeficientes wavelet são dados por:
w j ,k  f (t ), j ,k (t )
A função f(t) pode ser reconstruída a partir dos
coeficientes wavelet:
f (t )   w j ,k j ,k (t )
j
k
TE073 – Processamento Digital de Sinais II
114
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Filtro passa-faixa



É necessário um número infinito de escalamentos e
translações para calcular a transformada wavelet.
As translações das wavelets são limitadas
superiormente pela duração do sinal em questão.
Quantas escalas precisamos para analisar o sinal?
Como conseguimos uma fronteira inferior?
A wavelet tem um espectro de freqüências passafaixa. Sabemos que a compressão no tempo equivale
ao alargamento do espectro e a um deslocamento
para frente.
1  
F  f at 
F 
|a|  a 
TE073 – Processamento Digital de Sinais II
115
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
• Isso significa que uma compressão no tempo por um
fator 2 alargará o espectro da wavelet e deslocará
todos os componentes de freqüência por um fator 2.
• Podemos, então, cobrir o espectro finito do sinal com
os espectros de wavelets dilatadas, da mesma forma
que cobrimos o sinal no domínio do tempo com
wavelets transladadas
TE073 – Processamento Digital de Sinais II
116
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
• Logo, se uma wavelet pode ser vista como um filtro
passa-faixa, uma série de wavelets dilatadas pode ser
vista como um banco de filtros passa-faixas.
• A razão entre a freqüência central de um espectro de
wavelet e a largura deste espectro é a mesma para todas
as wavelets.
• Esta razão é normalmente chamada fator de fidelidade Q
de um filtro. No caso das wavelets, temos, então, um
banco de filtros com fator Q constante.
TE073 – Processamento Digital de Sinais II
117
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Função de escalamento


Como cobrir o espectro até a freqüência zero?
Neste caso, seria necessário um número infinito de
wavelets.
Solução: Utilizar uma espécie de “rolha” para tapar o
buraco, quando ele for suficientemente pequeno: um
espectro passa-baixas, que pertence à função de
escalamento.
TE073 – Processamento Digital de Sinais II
118
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Podemos considerar a função de escalamento como um sinal
com um espectro passa-baixas. Desta forma, podemos
decompô-lo em componentes wavelet:
 (t )   w j ,k j ,k (t )
j ,k
A expressão acima utiliza um número infinito de wavelets até uma
determinada escala j.
Se analisarmos um sinal utilizando uma combinação de função de
escalamento e wavelets, a função de escalamento cobre o espectro
até a escala j, enquanto o restante do espectro é coberto por
wavelets.
Se uma wavelet pode ser vista como um filtro passa-faixa e uma
função de escalamento é um filtro passa-baixas, então (uma série de
wavelets dilatadas + uma função de escalamento) pode ser vista
como um banco de filtros.
TE073 – Processamento Digital de Sinais II
119
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Codificação sub-banda



Transformada wavelet  banco de filtros 
Transformada de um sinal pode ser feita
passando o sinal através deste banco de filtros.
As saídas dos diferentes estágios de filtros são os
coeficientes das funções wavelet e escalamento.
Codificação sub-banda  Análise de um sinal
através de sua passagem por um banco de filtros.
TE073 – Processamento Digital de Sinais II
120
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
• Dividimos o espectro do sinal em duas partes iguais: uma
passa-baixas e outra passa-altas.
• A parte passa-altas contém os detalhes menores nos quais
estamos interessados e podemos parar aqui.
• Agora há duas faixas. Apesar disso, a parte passa-baixas
ainda contém alguns detalhes e podemos dividi-la novamente.
• E novamente, até estarmos satisfeitos com o número de
faixas de freqüência criadas.
• Desta maneira, construímos o banco de filtros.
Vantagem – Temos que projetar apenas dois filtros.
Desvantagem – A cobertura do espectro do sinal é fixa.
TE073 – Processamento Digital de Sinais II
121
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Banco de filtros dividindo o espectro de freqüências do sinal
TE073 – Processamento Digital de Sinais II
122
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Observamos, na figura anterior, que, após a repetida divisão do
espectro de freqüências, temos uma série de bandas passa-faixa com
duplicação da largura de faixa e uma banda passa-baixas.
Isto é o mesmo que aplicar a transformada wavelet ao sinal.
As wavelets nos dão as bandas passa-faixa, com duplicação da largura
de faixa, e a função de escala fornece a banda passa-baixa.
A partir disso, conclui-se que a transformada wavelet é equivalente ao
esquema de codificação sub-banda, utilizando um banco de filtros com
Q constante.
Logo, se implementarmos a transformada wavelet como um banco de
filtros iterado, não é necessário especificar as wavelets explicitamente.
TE073 – Processamento Digital de Sinais II
123
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Transformada wavelet discreta




Em aplicações práticas (como compressão de
imagens), o sinal de interesse é amostrado.
É necessário, portanto, que a transformada
wavelet seja também discreta.
As wavelets discretas não são discretas no tempo
(somente os passos de translação e de escala são
discretos).
Intuitivamente, deve-se implementar o banco de
filtros como um banco de filtros digitais
TE073 – Processamento Digital de Sinais II
124
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Se adicionarmos um espectro de wavelet ao espectro de
função de escala, teremos uma nova função de escala, duas
vezes mais larga que a primeira.
Podemos, então, expressar a primeira função de escala em
termos da segunda.
Formulação de multiresolução ou relação entre duas escalas:
 (2 j t )   h j 1 (k ) (2 j 1 t  k )
(*)
k
Podemos expressar,também, as wavelets nesta escala em
termos das funções de escala transladadas da escala
anterior:
 (2 t )   g j 1 (k ) (2 t  k )
j 1
j
(**)
k
TE073 – Processamento Digital de Sinais II
125
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Uma vez que o sinal f(t) pode ser expresso em termos
de wavelets dilatadas e transladadas até uma escala j-1,
f(t) pode ser expressa em termos de funções de escala
dilatadas e transladadas em uma escala j:
f (t )    j (k ) (2 t  k )
j
k
Se utilizarmos uma escala de j-1, temos que adicionar
wavelets, a fim de que tenhamos o mesmo nível de detalhes:
f (t )    j 1 (k ) (2 j 1 t  k )  w j 1 (k ) (2 j 1 t  k )
k
k
TE073 – Processamento Digital de Sinais II
126
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Se a função de escalamento  j ,k (t ) e as wavelets  j ,k (t )
forem ortonormais, os coeficientes  j1 (k ) e wj1 (k )
são encontrados a partir dos produtos internos:
 j 1 (k )  f (t ), j ,k (t )
w j 1 (k )  f (t ), j ,k (t )
Se substituirmos  j ,k (t ) e  j ,k (t ) nos produtos internos por
versões escaladas e transladadas de (*) e (**) e manipular
um bit, levando em consideração que o produto interno
também pode ser escrito como integração, chegamos a:
 j 1 (k )   h(m  2k ) j (m)
m
w j 1 (k )   g (m  2k ) w j (m)
m
TE073 – Processamento Digital de Sinais II
127
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
• h(k)  Filtro passa-baixas  Filtro de escalamento
• g(k)  Filtro passa-altas  Filtro wavelet
• É possível implementar a transformada wavelet como um banco de
filtros digitais.
• Os filtros de escalamento e wavelet têm um passo de 2 na variável k.
Portanto, o número de amostras do estágio seguinte é metade do
número de amostras do estágio atual.
• Normalmente, as iterações param quando o número de amostras é
menor que o tamanho do filtro de escalamento ou do filtro wavelet.
TE073 – Processamento Digital de Sinais II
128
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Compressão de imagens




Uma das aplicações mais populares de wavelets é na
compressão de imagens.
O padrão JPEG 2000 utiliza wavelets ao invés de DCT para
fazer a decomposição da imagem.
Na discussão anterior, sempre nos referimos a um sinal
unidimensional. Imagens, porém, são sinais bidimensionais.
Há duas maneiras de se fazer decomposição sub-banda de
um sinal bidimensional: utilizando filtros bidimensionais ou
transformadas separadas, que podem ser implementadas
usando filtros unidimensionais primeiro nas linhas e depois
nas colunas (como o JPEG 2000)
TE073 – Processamento Digital de Sinais II
129
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Começamos com uma imagem N X M. Filtramos cada
coluna e sub-amostramos, obtendo duas imagens N X M/2.
Então filtramos cada coluna e sub-amostramos as saídas
dos filtros, obtendo 4 imagens N/2 X M/2.
TE073 – Processamento Digital de Sinais II
130
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
TRANSFORMADA WAVELET DIRETA
TE073 – Processamento Digital de Sinais II
131
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
TRANSFORMADA WAVELET INVERSA
TE073 – Processamento Digital de Sinais II
132
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Exemplo: Utilizando o filtro 4-tap Daubechies
(Decomposição de primeiro nível)
TE073 – Processamento Digital de Sinais II
133
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Imagem de Sinan codificada
com 0,5 bits/pixel, utilizando o
filtro 8-tap Johnson
(codificação sub-banda)
Imagem de Sinan codificada
com 0,5 bits/pixel, utilizando o
filtro wavelet 4-tap Daubechies
TE073 – Processamento Digital de Sinais II
134
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Uma das decomposições mais populares é a (a). Após cada
decomposição, a imagem LL é decomposta em mais 4 sub-imagens,
resultando em 10 sub-imagens (organização de Mallat).
TE073 – Processamento Digital de Sinais II
135
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
ORGANIZAÇÃO DE MALLAT
TE073 – Processamento Digital de Sinais II
136
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
EXEMPLO DE ORGANIZAÇÃO DE MALLAT
TE073 – Processamento Digital de Sinais II
137
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
SISTEMA DE COMPRESSÃO WAVELET BÁSICO
TE073 – Processamento Digital de Sinais II
138
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Embedded Zerotree Wavelet (EZW) Coder
• Uma característica particular utilizada pelo EZW é que
há coeficientes de wavelets em diferentes sub-bandas que
representam a mesma localização espacial na imagem.
• Se a decomposição é tal que os tamanhos das subbandas são diferentes (caso da organização de Mallat),
um único coeficiente na sub-banda menor pode
representar a mesma localização espacial que múltiplos
coeficientes nas outras sub-bandas.
TE073 – Processamento Digital de Sinais II
139
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
a – raiz da árvore com
descendentes – a1, a2, a3
a1 – tem descendentes
a11, a12, a13, a14
a2  a21, a22, a23, a24
a3  a31, a32, a33, a34
Cada um desses
coeficientes tem 4
descendentes – total de
64 coeficientes nesta
árvore.
TE073 – Processamento Digital de Sinais II
140
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
TE073 – Processamento Digital de Sinais II
141
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Limiar T0 – Freqüentemente, um coeficiente tem
magnitude menor que um determinado limiar, e todos os
seus descendentes também são menores que T0.
TE073 – Processamento Digital de Sinais II
142
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Se determinarmos que todos os coeficientes partindo de
uma determinada raiz têm magnitudes menores que T0
e informarmos o decodificador, então necessitamos
apenas de 2 bits por amostra para este ramo da árvore.
Na figura anterior, o primeiro bit é o bit de sinal e o
segundo bit é o bit mais significativo da magnitude. A
informação de que um conjunto de coeficientes tem
valor menor que T0 equivale a dizer que o bit mais
significativo é 0.
Se há N coeficientes na árvore, isto poupará N bits.
TE073 – Processamento Digital de Sinais II
143
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
JPEG 2000



O padrão atual JPEG tem excelente performance em
taxas acima de 0,25 bits/pixel. Apesar disso, em
pequenas taxas, há uma grande degradação na
qualidade da imagem reconstruída.
O padrão JPEG-2000 é baseado na transformada
wavelet discreta, utilizando wavelets biortogonais de
Daubechies.
O padrão JPEG-2000 também utiliza modos recentes
de quantização escalar, modelamento no contexto e
codificação aritmética.
TE073 – Processamento Digital de Sinais II
144