Transformadas e
Decomposição de Sub-banda
Joaquim Macedo
Departamento de Informática da Universidade do Minho &
Faculdade de Engenharia da Universidade Católica de Angola
Sumário




Tranformada Unitária 1-D
Transformada Discreta de Fourier 1-D
Transformada Discreta do Coseno 1-D
Filtragem Digital e Análise de sub-banda








Filtros Digitais
Análise de sub-banda
Transformadas e Filtragem Digital
Transforma Discreta Wavelet 1-D
Tranformada Unitária 2-D
Transformada Discreta de Fourier 2-D
Transformada Discreta do Coseno 2-D
Transforma Discreta Wavelet 2-D
Transformada Unitária 1-D
Seja f (n),0  n  N  1, uma sequência unidimensional
A transformada unitária(ortonorma
l) define- se como


N 1
F  U f , F (k )   U (k , n) f(n) 0  k  N  1
n 0

F  F (k ) é a matrizde coeficientes da transformada e
 u (0,0)

...


...

u ( N  1,0)
u (0, N  1) 

... ...
...
 é a matrizda transformada unitária

... ...
...

... ... u ( N  1, N  1)
... ...
Transformada Unitária 1-D
A transformada unitári a inversadefine - se como


N 1
f  U *T F , f (n)   F (k )u * (k , n) 0  n  N  1
n 0
* e T significam conjungação complexae a matriztransposta
A equação acima pode ser considerada a representação por séries
da sequência f(n)
u (k , n),0  n  N  1, colunasde U
*
base de U
*T
saõ consideradas os vectores
Transformada Unitária 1-D
A matrizé unitáriase se cumpriremas seguintescondições
N 1
*
u
(
k
,
n
)
u
( k 0 , n)   ( k  k 0 )

n 0
N 1
*
u
(
k
,
n
)
u
(k , n0 )   (n  n0 )

k 0
Onde  (k ) é a função discreta de impulso unitário
 1 se k  0
 (k )  
0 se k  0
Transformada Discreta de Fourier 1-D
f n 
- sequência
1
F k  
N
1
f n  
N
kn
N
W
discreta periódica com N amostras por período.
N 1
kn


f
n
W

N
0  k  N 1
DFT
n 0
N 1
 kn


F
n
W

N
0  n  N 1
k 0
e
 j 2kn
N
F k 
- k-ésimo
coeficiente DFT
IDFT
Transformada Discreta de Fourier 1-D
Matrizda transformada de Fourier dada por
 j 2 k


1
1

kn 
N
U  {u (k , n)}  
WN   
e

 N
  N

Matrizda transformada inversade Fourier dada por
U 1  U *T
j 2 k


1
1


*
*
 kn
N
 {u (k , n)}  {u (n, k )}  
WN   
e

 N
  N

Transformada Discreta de Fourier 1-D
Exemplo 5.1

Considere uma sequência de 4 pontos
f={2,5,7,6}. Calcule os correspondentes
coeficientes DFT. Reconstrua a
sequência de entrada a partir dos
coeficientes DFT e das funções de base
DFT
Transformada Discreta de Fourier 1-D
Transformada Discreta de Fourier 1-D
Par alternativo

Definição do DFT alternativa

Usada por muitas concretizações (MATLAB)
N 1
F k    f n WNkn
0  k  N 1
n 0
1 N 1
f n    F n WNkn 0  n  N  1
N k 0

Diferença apenas de escala
 Ortogonal mas mas não ortonormal ou unitária
Propriedades da DFT

Convulsão
f (n)  g (n)  F (k )G( K ) Convulsãono domíniodo tempo
f (n) g (n)  F (k )  G( K ) Convulsãono domínioda frequência


Rapidez da concretização
Conservação da Energia e Compactação
N 1
 f (n)
n 0
2
N 1
  F (k )
k 0
2
Convolução
f (n)  g ( n)  F ( k )G( k )
Convolução Circular
f (n)g ( n)  F (k )  G(k )
Fast Fourier Transform
 Os coeficientes da DFT de N pontos podem ser calculados
multiplicando a matriz de transformação 2D N  N pela matriz
1D N  1
 O cálculo directo da DFT 1D para uma sequência de N-pontos
requer N 2N*N operações
onde 1 operação = 1 multiplicação complexa + 1 adição complexa.
 Há disponíveis algoritmos especiais com uma complexidade muito
menor para calcular a DFT. Esses algoritmos são conhecidos como Fast
Fourier Transform (FFT).
Diferentes algoritmos FFT
Foram propostos na literatura vários algoritmos FFT.
Alguns dos mais populares são os seguintes:
 Radix-2
 Radix-4
 Split-Radix
 Winograd
 Prime Factor
Algoritmo Radix-2
 Radix-2 é um algoritmo popular para FFT.
 Para transformada de N pontos a complexidade computaciona é
( N / 2) log2 N borboletas
onde 1 borboleta = multiplicação complexa + 2 adições complexas
 O algoritmo FFT usa um arranjo dos dados que parece uma
borboleta.
Complexidade FT versus FFT
N
N2
(FT
Directo)
N log2 N
(FFT)
Ganhos
Computacionais
N2/N log2 N
32
1024
160
6.4
256
65536
2048
32
1024
1048576
10240
102
8192
67108864
106496
630
Conservação da Energia
A Transformada de Fourier preserva a energia do sinal.
A energia do sinal no domínio do tempo ou pixel é idêntica à
energia no domínio da frequência.
N 1

n 0
N 1
f (n)   F (k )
2
2
k 0
Embora a energia total não mude no domínio de Fourier, a energia
é redistribuída entre os coeficientes de Fourier.
Exemplo 5.2

Construa um sinal unidimensional dos
valores de pixel da linha #100 da figura da
Lena a preto e branco. Para evitar o
componente DC torne o sinal com média 0
(substraia o valor da média de cada pixel).


Calcula a DFT e a energia total nos 20
primeiros coeficientes de Fourier.
Compare com a energia total do sinal.
Compactação de energia com a DFT
Linha horizontal (line# 100)
da imagem da lena
Espectro de Amplitude
Transformada Discreta do Coseno 1-D

A Transformada Discreta do Coseno (DCT) unidimensional
para a sequência de entrada f(n) é definida pelo seguinte
par:
(2n  1)k 

F (k )   (k ) f (n) cos
para 0  k  N  1

2N


n 0
N 1
(2n  1)k 

f (n)    (k ) cos
F (k ) para 0  n  N  1

2N


k 0
N 1
 1/ N
para k  0
 (k )  
 2 / N para 0  k  N  1
Matriz da Transformada
DCT 4 pontos
 1/ 2
v(0)
1/ 2
1/ 2
1 / 2  u (0)


 v(1) 

u
(
1
)
1
cos(

/
8
)
cos(
3

/
8
)
cos(
5

/
8
)
cos(
7

/
8
)





v(2)
2 cos(2 / 8) cos(6 / 8) cos(10 / 8) cos(14 / 8)  u (2)





v
(
3
)
u
(
3
)
cos(3 / 8) cos(9 / 8) cos(15 / 8) cos(21 / 8) 



Matriz da Transformada Inversa
1 / 2 cos( / 8) cos(2 / 8) cos(3 / 8)  v(0)
u (0)


 u (1) 

v
(
1
)

  1 1 / 2 cos(3 / 8) cos(6 / 8) cos(9 / 8)  

u (2)
2 1 / 2 cos(5 / 8) cos(10 / 8) cos(15 / 8)  v(2)





u
(
3
)
v
(
3
)
1 / 2 cos(7 / 8) cos(14 / 8) cos(21 / 8) 



V.B.-0
V.B.-1
V.B.-2
V.B.: Vectores de Base
V.B.-3
Exemplo 5.3

Considere uma sequência de 4 pontos
f={2,5,7,6}. Calcule os correspondentes
coeficientes DCT. Reconstrua a sequência
de entrada a partir dos coeficientes DCT.
Exemplo 5.3
Fig 5.3,pag. 92
Propriedades do DCT
Energia da Compactação
A DCT tem um excelente desempenho de compatação
de energia. Isto é demonstrado com um exemplo.
Exemplo 5.4
Considere a linha de varrimento da imagem do
Exemplo 5.2. Calcule o DCT e a energia total nos
primeiros 20 coeficientes de Fourier. Compare-a com a
Energia total do sinal. Compare o desempenho de
compactação da energia da DCT e DFT.
Compactação da Energia com a DCT
A DCT tem um excelente desempenho na compactação da energia
512 pixels: energia total =
11.3  105
Primeiros 20 coeficientes DFT capturam 76% daa energia
Primeiros 20 coficientes DCT capturam s 83% da energia
Relações com a DFT

Embora as funções de base da DCT sejam funções discretas de
coseno a DCT não é a parte real da DFT.
Contudo está relacionada com a DFT. A DCT da sequência Nx1
{ f (0), f (1),.....f ( N  1)}
está relacionada com a seguinte sequência DFT
{ f ( N  1), f ( N  2),....f (1), f (0), f (0),.....f ( N  1)}
 Existe uma transformada DCT rápida com uma complexidade
computacional de ordem
O( N log2 N )
Segundo, devido à simetria par da sequência equivalente DFT, o
sinal recosntruído dos coeficientes DCT quantificados terão uma
melhor representação das variações bruscas.
Filtragem Digital e Análise de
sub-banda

As transformadas unitárias


São muitos úteis para análise do contéudo
de frequência dum sinal
Métodos alternativos para análise de
frequência de sinais multimédia


Filtragem Digital
Análise de sub-banda
Filtragem Digital
Filtro


Um filtro é um componente que atenua ou
amplifica frequências particulares
Fácil de visualizar no domínio da frequência,
onde a filtragem é uma multiplicação:
H ( )  F ( )  G( )

Onde F é o espectro da função, G é o
espectro do filtro e H é a função filtrada. A
multiplicação é ponto a ponto.
Parâmetros de Filtros
Banda de passagem
Atenuação na
stopband
Ondulação
(Ripple)
Banda de transição
Banda de paragem
Frequência
Parâmetros do Filtro
Banda de Passagem: Os componentes da banda de frequência aos
quais é permitido a passagem.
Banda de Paragem: Os componentes da banda de frequência que são
suprimidos.
Banda de Transição: a banda de frequência entre a banda passagem e
a de paragem onde o sinal varia de alto para baixo ou vice-versa
Ondulação: a máxima variação do ganho nominal permitida na
banda de passagem ou de paragem.
Atenuação da Banda de Paragem: atenuação mínima dos
componentes na banda de paragem.
Tipos de Filtros
Lowpass
(Passa-Baixo)
 c
c
 c
Bandpass
(Passa-Banda)
 c 2  c1
c1
Highpass
(Passa-Alto)
c 2
Filtros ideais: 4 tipos básicos
c
Bandstop
(Para-Banda)
 c 2  c1
c1
c 2
Tipo de Filtros
Função: F
Filtro: G
Resultado: H

=
Passa-Baixo

=
Passa-Alto

=
Passa-Banda
Lowpass Filter
Transition
Passband
Band
Stopband
Filter Gain
Filter Gain
Tipos de Filtros
Highpass Filter
Frequency
Frequency
Filter Gain
Filter Gain
Frequency
Bandpass Filter
Bandstop Filter
Frequency
Tipos de Filtros Digitais
f (n) e y (n), entradae saída dum filtrodigital
N
M
k 0
k 0
y ( n)   b( k ) f ( n  k )   a ( k ) y ( n  k )
b(k ) - coeficientes que expressama dependência da saída
da amostraactualcom as N entradasprévias
a (k )  coeficientes que expressama dependência da saída
da amostraactualcom as M saídas prévias
 FIR(FiniteImpulseResponse) a(k)  0,k e N  
categoriasde filtros
IIR(Infinite ImpulseResponse) k : a(k)  0 ou N  
Tipos de Filtros Digitais
Filtros FIR (Finite Impulse Response)
Os filtros FIR são constituídos por funções de resposta com número
finito de pulsos que são fáceis de concretizar devido ao seu
comprimento finito.
Filtros
IIR(Infinite Impulse response)
Os filtros IIR requerem uma resposta com um número infinito de
pulsos que tornam a forma em convulsão difícil. Contudo, estes filtros
são realizáveis.
Filtros FIR e IIR
 Filtros Finite Impulse Response (FIR) Filters um númro finito de
impulsos na sua resposta de impulso. Relação típica entre entrada e
saída:
N
y( n )   b( k ) f ( n  k )
k 0
output
input
 Os filtros Infinite Impulse Response (IIR) têm um número infinito
de impulsos na sua resposta de impulso. Relação pica entre entrada e
saída:
N
M
k 0
k 1
y( n)   b( k ) f ( n  k )   a( k ) y( n  k )
Os filtros IIR têm geralmente um elemento de feedback
Tipos de Filtros Digitais
Frequência: pulso
Tempo: sinc
Fig. 5.6, pag. 95
Tipos de Filtros Digitais
Resposta de Impulso do Filtro Passa baixo
Truncagem
A resposta de impulso do FPB ideal tem um número infinito de impulsos
Janelas Rectangular & Hamming
• Janela Rectangular
1,
wn   
0,
• Janela Hamming
wn  0.54  0.46cos2    n N 
0  n  M 1
Para outros valores de
n
n  0,1,...,M  1
Janela "Hamming" M=35
Janela Rectangular M=35
1.5
1.2
1
1
0.8
0.6
0.5
0.4
0.2
0
0
0
50
100
150
200
250
0
5
10
15
20
25
30
35
Ganho de Resposta dos filtros P.B.
Ganho da resposta em dB
Concretização de Filtros com o MatLab
Passa Alto e Passa Baixo
Concretize um filtro P.F e P.A. com uma frequência de cortye de
3200 Hz para um sinal de áudio amostrado ao ritmo de 8000
amostras/seg.
Frequência de corte = 3200/8000 or 0.4.
filter_lowpass = fir1(8,0.4) ; % 8ª ordem, i.e. 9 implusos
filter_highpass = fir1(8,0.4,’high’) ;
Concretização de Filtros com o MATLAB
Passa Banda e Pára Banda
Concretize um filtro passa banda e outro para banda com
frequências de corte normalizadas de 0.4 e 0.8.
filter_bandpass = fir1(8,[0.4 0.8])
filter_bandstop = fir1(8,[0.4 0.8],’stop’)
Exemplo de Filtros
 Exemplos de filtros digitais FIR com 9 impulsos
 A frequência de corte dos filtros passa alto e baixo é 0.4
 As frequências de corte dos filtros para e passa banda são [0.4,0.8]
Filtro
Coeficientes
Passa-baixo
[-0.0061 –0.0136 0.0512 0.2657 0.4057 0.2657 0.0512 –0.0136 –0.0061]
Passa-alto
[-0.0060 0.0133 -0.0501 -0.2598 0.5951 -0.2598 0.0501 0.0133 0.0060]
Passa-banda
[0.0032 0.0478 -0.1802 -0.1363 0.5450 - 0.1363 0.1802 0.0478 0.0032]
Para-banda
[-0.0023 -0.0354 0.1336 0.1011 0.6061 0.1011 0.1336 -0.0354 -0.0023]
Características de Ganho na Frequência
Fitros de 9 Impulsos
Os filtros não têm ganhos com características escarpadas
Características de Ganho na Frequência
Filtros de 101-impulsos
Os filtros têm características de ganho escarpadas
Análise de sub-banda
Análise e síntese de sub-banda
Sub-bandas
Banco de
Filtros de
Análise
Sinal de
Entrada
1
2
N
Sub-bandas
Processamento/
Codificação/
Extracção de
características
1
2
N
Banco de
Filtros de
Síntese
Sinal de
Saída
Banco de Filtros de 2 bandas
FPB
~
Processamento
x0 (n)
h( n)
2
v0 (n)
^
2
x0 ( n )
FPB
h(n)
^
X 0 ( n)
^
X (n)
+
~
2
g (n)
x1 (n)
v1 (n)
FPA
2
2
g (n)
^
^
x1 ( n )
FPA
X 1 ( n)
X (n)
Características do Ganho de Frequência
do QMF
QMF: Quadrature Mirror Filter
Highpass band
Filter gain
Lowpass band
0
FS / 4
FS / 2
Categorias de Bancos de Filtros

Reconstrução do Sinal

Reversível (Irreversíveis)


a sequência de entrada (não)pode ser perfeitamente
reconstruída com os coeficientes não quantificados e o
banco de filtros de síntese
Para-unitários

A matriz de transformação num sentido é a inversa da
matriz de transformação no sentido contrário

Similar a uma transformada ortonormal
Condições de Para-Unitários
Um banco de filtros de 2 bandas é chamado para-unitário
se forem satisfeitas as 4 condições seguintes:
N 1
 h(n)h(n  2k )   (k )
……..(5.24)
h(n)  (1) n1 g~(n)
……..(5.25)
n 0
n 1 ~
~
g (n)  (1) h ( N  1  n)
……..(5.26)
~
g (n)  (1) h (n)
……..(5.27)
n
~
~( n ) , h ( n ) ,
Se se encontrar h(n )que satisfaça Eq. (5.24), g
g (n ) podem ser calculadas com as equações seguintes.
Bancos de Filtros
Condições para para-unitários
N 1
 h( n) h( n  2k )   ( K )
n 0
h(n)  (1)
~
g (n)  (1)
n 1
n 1
~
~
g ( n)
~
h( N  1  n)
g (n)  (1) h(n)
n
Exemplo 5.5
Considere o filtro passa-baixo :
h(n)  [0.4830, 0.8365, 0.2241,  0.1294]
Os outros filtros obtêm-se da forma seguinte:
h(0)   g~(0)
h(1)  g~(1)
h(2)   g~( 2)
h(3)  g~(3)
Filtro passa-alto de análise
g~(n)  [0.4830, 0.8365, - 0.2241,  0.1294]
Exemplo 5.5 (..cont.)
Filtro passa baixo de análise
g~(n)  [0.4830, 0.8365, - 0.2241,  0.1294]
~
~
~
g~(0)  h ( N  1)  h (3)
g~(1)  h (2)
~
~
g (2)  h (1)
Então
~
h (n)  [0.1294, 0.2241, 0.8365, 0.4830]
Filtro passa alto de síntese
~
~
g (0)  h (0) g (1)  h (1)
Então
~
~
g (3)  h (0)
~
g (2)  h (2)
~
g (3)  h (3)
g (n)  [0.1294,  0.2241, 0.8365, - 0.4830]
Exemplo 5.6
Considere o filtro passa baixo:


h(n)  1 / 2 1 / 2  [0.7071, 0.7071]
Os outros filtros podem ser obtidos da seguinte forma:
Filtro Passa alto de análise :
g~(n)  [0.7071, - 0.7071]
Filtro Passa baixo de análise
~
h (n)  [0.7071, 0.7071]
Filtro passa alto de síntese
g (n)  [0.7071, 0.7071]
Cálculo da saída de banco de filtros
Exemplo 5.7
Considere o banco de filtros do Exemplo 5.6.
Calcule a saída dos vários estágios do banco de filtros para a entrada:
x(n)  [1, 2, 5, 7, 8, 1, 4, 5]
Após o primeiro nível de filtros :
~
x0 (n)  x(n)  h (n)
 [2.1213 4.9497 8.4853 10.6066 6.3640 3.5355 6.3640 4.2426]
x 0 (0)  1  0.7071 2  0.7071 2.1213
x 0 (7)  5  0.7071 1  0.7071 4.2426
~(n)
x1 (n)  x(n)  g
 [-0.7071 - 2.1213 - 1.4142 - 0.7071 4.9497 - 2.1213 - 0.7071 2.8284]
Exemplo 5.7 (..cont)
Depois da dizimação:
v0 (n)  x0 (n)  2  [2.1213 8.4853 6.3640 6.3640]
v1(n)  x1(n)  2  [-0.7071 - 1.4142 4.9497 - 0.7071]
Depois da sobre-amostragem
xˆ0 (n)  [2.1213 0.0 8.4853 0.0 6.3640 0.0 6.3640 0.0]
xˆ1(n)  [-0.7071 0.0 - 1.4142 0.0 4.9497 0.0
- 0.7071 0.0]
Exemplo 5.7 (..cont)
Após filtro de síntese

x0 (n)  xˆ0 (n)  h(n)
 [1.500 1.500 6.000 6.000 4.500 4.500 4.500 4.500]

x1(n)  xˆ1(n)  g (n)
 [-0.50 0.50 - 1.00 1.00 3.500 - 3.500 - 0.500 0.500]
Saída reconstruída


ˆx(n)  x 0 (n)  x1 (n)  [1, 2, 5, 7, 8, 1, 4, 5]
Transformadas e Filtragem
Digital



As transformadas unitárias fornecem
coeficientes para diferentes frequências
Os coeficientes de sub-banda também
disponibilizam coeficientes para as diferentes
bandas idealmente não sobrepostas no
domínio da frequência
Pode ser mostrado que as transformadas de
bloco são um caso especial de banco de
filtros
Transformadas e Filtragem
Digital

Uma transformada de N-pontos pode ser
calculada usando um banco de filtros de N
bandas


Cada filtro corresponde ao conjugado complexo
de uma função de base
A saída de cada filtro é dizimada por N


Por cada conjunto de N amostras de entrada há uma
saída para cada um dos N filtros
Essas saídas são basicamente os coeficientes da
transformada.
Exemplo 5.8
Relação entre transformada e filtragem digital

Considere a sequência de 12 pontos
[{2,5,7,6},{1,3,9,4},{6,8,5,7}]


Calcule os coeficientes DCT de segunda
ordem para cada bloco de 4 coeficientes
Pode-se concretizar o DCT como banco de
filtros?
Exemplo 5.8 (cont.)
 Usando Eq. (5.18), os coeficientes de 2da ordem de cada bloco podem
ser calculados como de cada bloco podem ser calculados como
{-3.1543, -3.5834, -0.6069, 0.1585}.
 Sim, os coeficientes DCT podem também ser concretizados usando um
banco de filtros
Os coeficientes de segunda ordem podem ser calculados passando a
sequência de entrada através dum filtros digital com a resposta de
impulso h = [cos(pi/8), cos(3*pi/8), cos(5*pi/8), cos(7*pi/8)] que é a
função de base de segunda ordem
 Observe que quando o filtro digital está em operação cada bloco de 4
amostras de entrada produzirá uma amostra à saída do filtros de
segunda ordem.
Transformadas wavelet
Limitações da Transformada de Fourier e derivadas

Têm funções de base com muitos impulsos





Fraco desempenho para análise de sinais não
estacionários
Dificuldade de estimação das caraterísticas no
tempo ou do espaço a partir da amplitude do
espectro
Más características de flltragem
Boa decomposição de sub-banda


É ineficiente para muitas aplicações
Só para dados discretos
Características unitárias não disponíveis à partida
Porquê que funções de base longas
podem ser indesejáveis?
 As funções de base para FT contínuas são infinitamente longas.
 As funções de base para a transformada discreta de Fourier não são
infinitas mas são longas.
-- Por exemplo, para a DFT de 256 pontos há 256 funções de base
cada uma como 256 impulsos.
 Em muitas aplicações tal como compressão do sinal, essas funções base
longas não são desejáveis.
-- Para representar um pequeno pulso rectangular são necessários uma
série de componentes na frequência, o que pode degradar a taxa de
compressão
FT longas e curtas
Funções de base de Fourier (suporte infinito)
Funções de base de Fourier de tempo curto (suporte finito)
Resolução Tempo-Frequência
frequência
frequência
(a)
STFT
time
(b)
Wavelets
time
Funções de base de STFT e Wavelets
Transformada Discreta Wavelet 1-D

Transformada Wavelet

Ferramenta potente e recente




Diversas aplicações em ciências e engenharia
Melhores técnicas de transformada e decomposição em
sub-banda
Pode ser considerada uma transformada ou técnica de
decomposição em sub-banda
Não tem conjunto único de funções de base

Funções de base concebidas de acordo com a aplicação
Transformada Discreta Wavelet
Directa
 Uma dada transformada wavelet dyadic é definida de forma única
por um filtro FIR passa-baixo h[.] e um FIR passa-alto g[.] .
 Considere uma sequência discreta de N pontos
c 0,k
0  k  N 1
 Os coeficientes DWT são calculados recursivamente usando as
equações seguintes
Passa-baixo
c j 1,k   c j ,mh[m  2k ]
m
Passa-Alto
d j 1,k   c j ,m g[m  2k ]
m
Escala
Localização
0  k  N / 2 j 1  1
Decomposição Wavelet
Há uma série de observações a fazer:
 A sequência de entrada pode ser considerada como os
coeficientes DWT de escala 0
 c1,k pode ser obtido pela convulsão de c0,m com h[n]e
dizimando a saída da convulsão por 2 (devido ao factor 2k)
 d1,k pode ser obtido pela convulsão de c0,m com g[ne]
dizimando a saída da convulsão por 2
 A decomposição continua recursivamente. Apenas os
coeficientes passa baixo são decompostos.
Algoritmo em árvore
Cálculo dos coeficientes da DWT
h[n]
h[n]
2
cj
2
c j 2
2
d j 2
c j 1
g[n]
g[n]
2
d j 1
Decomposição de sinal com filtros de análise
Decomposição DWT usando matriz
 A decomposição pode ser feita através duma multiplicação de matrizes
 A DWT duma sequência de 8 pontos pode ser calculada com filtros
passa-baixo e passa-alto de 4 implusos com a seguinte multiplicação de
matrizes :
 c j1,0  h[0]
d  
 j1,0  h[3]
 c j1,1  

 
d
 j1,1  
c   
 j1,2  
d j1,2  
 c  h[2]
 j1,3  
d j1,3  h[1]
h[1] h[2] h[3]
- h[2] h[1] - h[0]
h[0] h[1] h[2] h[3]
h[3] - h[0] h[1] - h[0]
h[0] h[1] h[2]
h[3] - h[2] h[1]
h[3]
h[0]
- h[0]
h[3]
 c j,0 
 c 
  j,1 
 c j,2 
 c 
  j,3 
h[3] c j,4 
 
- h[0] c j,5 
h[1] c j,6 
 
- h[2] c j,7 
Transformada Inversa DWT
Síntese

Utilizando uma abordagem similar à
decomposição em wavelet

Os coeficientes duma dada escala podem
ser reconstruídos com coeficientes de
escala superior
c j ,m   c j 1,k h[m  2k ]   d j 1,l g[m  2l ]
k
l
Transformada Wavelet Inversa
 Os coeficientes wavelet duma duma escala podem ser reconstruídos
usando os coeficientes de escalas mais altas.
Os coeficientes reconstruídos podem ser expressos como se segue:
c j ,m   c j 1,k h[m  2k ]   d j 1,l g[m  2l ]
k
l
Os coeficientes wavelet duma da escala são sobreamostrados de 2 (i.e
inserir um zero entre coeficientes consecutivos)
 Os coeficientes sobreamostrados são passados por um conjunto de
filtros passa-baixo e passa-alto e a seguir adicionados para obter os
coeficientes wavelet da escala de resolução superior seguinte.
Algoritmo em árvore
Cálculo dos coeficientes da DWT
c j 1
2
h[n]

d j 1
2
cj  2
h[n]

g[n]
dj
2
g[n]
Reconstrução de sinal com filtros de síntese
c j 1
Matriz de Transformada Inversa
A DWT inversa de uma sequência de 8 pontos pode ser calculada com
filtros passa-baixo e passa-alto de 4 impulsos usando a seguinte
multiplicação de matrizes:
c j , 0  h[0] h[3]
c  
 j ,1   h[1]  h[2]
c j , 2  h[2] h[1]
c  
 j ,3    h[3]  h[0]
c j , 4  
c  
 j ,5  
c j , 6  
c j ,7  
 
h[0] h[3]
h[1]  h[2]
h[2] h[1] h[0]
h[3]  h[0] h[1]
h[2]
h[3]
h[2] h[1]   c j 1, 0 
d 

h[3]  h[0]  j 1,0 
  c j 1,1 
  d j 1,1 



h[3]
c
  j 1, 2 
 d j 1, 2 
 h[2]


h[1] h[0] h[3]   c j 1,3 

 h[0] h[1]  h[2]  d j 1,3 


Wavelet 1-D: Decomposição e
Síntese
Processamento
LPF
FPB
~
h (n)
x0 ( n )
2
v0 ( n )
xˆ 0 ( n ) FPB
LPF
2
h(n)
x (n )
FPA
FPA
g~( n )
2
x1 ( n )
g (n )
2
v1 ( n )
xˆ1 ( n )
?
x0 ( n )
?
?
x1 ( n )
xˆ ( n )
Wavelets Daubechies de fase mínima
# Imps n
h[n]
N=2
L=1
0
1
0.70710678
0.70710678
N=4
L=2
0
1
2
3
0.482962913144
0.836516303737
0.224143868042
-0.129409522551
N=8
L=4
0
1
2
3
4
5
6
7
0.230377813308
0.714846570552
0.630880767939
-0.027983769416
-0.18703481171
0.030841381835
0.032883011666
-0.010597401785
#
Imps
n
h[n]
N=12
L=6
0
1
2
3
4
5
6
7
8
9
10
11
0.111540743350000
0.494623890398000
0.751133908021000
0.315250351709000
-0.226264693965000
-0.129766867567000
0.097501605587000
0.027522865530000
-0.031582039318000
0.000553842201000
0.004777257511000
-0.001077301085000
DWT: Exemplo 5.9

Considere uma sequência de 4 pontos
f=[2,5,7,6]. Decomponha a sequência com
auxílio da wavelet de dois impulsos dada
na tabela 5.3 (Wavelet Haar). Reconstrua a
sequência de entrada a partir dos
coeficientes de Haar.
Exemplo 5.9 (cont.)
O coeficientes de Haar do 1º estágio (i.e., escala 1) podem ser calculdos
com:
0
0  c0,0  0.707 0.707
0
0  2  4.95 
 c1,0  h[0] h[1]
d  
  c  0.707  0.707
 5   2.12
h
[
1
]

h
[
0
]
0
0
0
0
1
,
0
0
,
1
 
   
   

 c1,1   0
0
h[0] h[1]  c0, 2   0
0
0.707 0.707  7   9.19 
  
  
  

d
c
0
0
h
[
1
]

h
[
0
]
0
0
0
.
707

0
.
707
6
0
.
71
  0,3  
  

 1,1  
Na segunda iteração da recursividade são usados apenas os coeficientes
passa baixo
 c2,0  h[0] h[1]  c1,0  0.707 0.707  4.95  10 
 
d   
c   




 2,0   h[1]  h[0]  1,1  0.707  0.707 9.19  3
Exemplo (..cont)
Após rearranjos os coeficientes de Haar ficam
[c2,0 , d 2,0 , d1,0 , d1,1 ]
= [10 -3 -2.12 0.71]
Reconstrução do sinal
c1,0  h[0] h[1]   c2,0  0.707 0.707   10  4.95

c   
d   





h
[
1
]

h
[
0
]
0
.
707

0
.
707

3
9
.
19
  2 ,0  
  

 1,1  
0
0   c1,0  0.707 0.707
0
0   4.95  2
c0,0  h[0] h[1]
c  
 d  0.707  0.707
  2.12 5 
h
[
1
]

h
[
0
]
0
0
0
0
0
,
1
1
,
0
 
   

 
c0, 2   0
0
h[0] h[1]   c1,1   0
0
0.707 0.707   9.19  7 
  
  

  
c
d
0
0
h
[
1
]

h
[
0
]
0
0
0
.
707

0
.
707
0
.
71
  1,1  

 6 
 0,3  
Funções de base para a Wavelet Haar
Fig. 5.13, pag 108
Transformadas 2D
Transformada Unitária 2-D

Transformada 1-D


Útil para análise de sinal 1-D
Transformada 2-D

Necessária para análise de sinais 2-D


Exemplo: imagens
Baseada na extensão dos conceitos 1-D
Transformada Unitária 2-D
A transformada directa e inversa 2-D são definida com
N 1 N 1
 (k , l )   (k , l; m, n)i(m, n)
m 0 n 0
N 1 N 1
i( m, n)   ( m, n; k , l ) ( k , l )
k 0 l 0
onde
Exemplo: Fourier
Cosine
I  i(m, n) = Imagem NxN
Wavelet
= Núcleo da t.directa
Hadamard
 (.)
Haar
= Núcleo da t.inversa
 (.)
Transformada Unitária 2-D
Propriedades

Conservação da Energia
N 1 N 1
N 1 N 1
 i(m, n)   (k , l )  I
2
m 0 n 0

2
2
 
2
m 0 n 0
Soma dos erros quadráticos
N 1 N 1
N 1 N 1
2
^
^
 i(m, n)  i(m, n)   (k , l )  (k , l )
m 0 n 0

m 0 n 0
Imagens de Base separáveis
   I
*
T
I   
*
T
2
Propriedades da Transforma 2-D
Conservação da energia
Pode ser mostrado que os coeficientes da transformada 2D
unitária satisfazem a relação de Parseval’s, i.e. A energia
total no domínio da frequência é igual à energia total no
domínio do tempo
N 1 N 1
 i(m, n)
m 0 n 0
2
N 1 N 1
   ( k , l )
2
k 0 l 0
 A transformada unitária preserva a energia do sinal ou de forma
equivalente o comprimento no espaço vectorial N-dimensional.
 Pode ser considerada simplesmente como uma rotação do vector no
espaço vectorial N-dimensional. Por outras palavras, a transformada
unitária roda as coordenadas de base e os componentes (coeficientes da
transformada) são as projeções no novo sistemas de coordenadas.
Soma dos quadrados de erros
 Assuma que valor de algun(s) dos coeficientes da tarsnformada
muda durante o processamento. Esta mudança pode ocorrer na
transmissão ou compressão de dados.
Se recosntruímos a imagem claculando a transformada inversa
usando os coeficientes mudados, a imagem reconstruída é diferente
da original.
Pode-se mostrar a seguinte igualdade é sempre verdadeira para
transformadas unitárias
N 1 N 1
N 1 N 1
 i(m, n)  iˆ(m, n)    (k , l )  ˆ(k , l )
m 0 n 0
Pixéis
originais
2
2
k 0 l 0
Píxeis
Reconstruídoss
Coeficientes
originais
Coeficientes
mudados
Imagens de base separáveis
 Alguns núcleos 2-D podem ser expressos como o produto de 2
funções ortogonais de base 1-D.
 Se o operador de transformada 1-D for designado por

as
transformadas directas e inversas podem ser expressas como
   * I T
I  T *
Uma transformada separável pode ser concretizada em 2 passos:
-- Calcular a transformada unitária de cada fila da matriz da
imagem .
-- Calcular a transformada unitária de cada coluna dos coeficientes
transformados intermédios .
Definição da DFT 2D
O par DFT unitário2D é definido por
1
 (k , l ) 
N
1
i (m, n) 
N
N 1 N 1
 i(m, n) W
m 0 n 0
km
N
ln
N
W
0  k, l  N  1
N 1 N 1
 (k , l )
k 0 k 0
onde
  j 2 
W N  exp

N


- km
N
W
-ln
N
W
0  m, n  N  1
Exemplo DFT 2D
Calcular a DFT e desenhar o espectro de amplitude da
seguinte image 32x32.
1
i(m, n)  
0
15  16  17 & 8  n  24
otherwise
 Observe que a imagem é basicamente um paralelepípedo
rectangular.
 A transformada de Fourier duma função rectangular 1-D é a
função sinc. Portanto, a transformada de Fourier duma função
rectangular 2-D é a função sinc 2-D.
Exemplo DFT 2D (cont.)
Ve r
t.
F re
que
ncy
ncy
e que
r
F
.
Ho r
 Por clareza, o espectro (sinc 2D) foi centralizado (a frequência DC no
meio).
 Observe que o rectângulo tem uma largura maior na horizontal quena
vertical. Isto reflecte-se no espectro. O espectro tem melhor resolução de
frequência na horizontal.
.
Propriedades da DFT 2D

A maior parte das propriedades da DFT
1D podem ser extendidas para a DFT
2D




Convolução
Correlação
Conservação da Energia
Soma mínima do erro quadrático
Propriedades da DFT 2D
Separabilidade

Pode ser mostrado que a DFT 2D é
separável

O cálculo da DFT para uma imagem pode
ser feito em dois passos simples

Calcular a DFT 1D de cada fila da imagem


A fila é substituída pelos respectivos coeficientes DFT
Calcular a DFT 1D de cada coluna da imagem

A coluna é substituída pelos respectivos coeficientes
DFT
Propriedades da DFT 2D
Separabilidade
N-1
(0,0)
n
u(m,n)
N-1
N-1
(0,0)
l
v´(m,l)
N-1
m
Transformada
das filas
l
v(k,l)
N-1
m
N-1
(0,0)
k
Transformada
das colunas
Exemplo
Usando a abordagem de separação, calcular a DFT 2D para a imagem
seguinte:
Transformada da Fila
2
1

2

2
3 4
5 2
4 9
7 1
7
8 
3

4
Imagem original
 8 6  j 4  12 6  j 4 


1 16  1  j 3  10  1  j 3


2 18  7  j
4
7 j


14
1

j
3
8
1

j
3


Transformada de fila dos
Coeficientes
Transformada de coluna
 8 6  j 4  12 6  j 4 


1 16  1  j 3  10  1  j 3


2 18  7  j
4
7 j


8
1  j3 
14 1  j 3
 56
 10  2 j
1
F (k , l ) 
4  4

 10  2 j
 1  3 j  26
19  7 j  16  2 j
1 3 j
10
7  3 j  16  2 j
 1  3 j
7  3 j 
 1  3 j

19  7 j 
Transformada de
Fila dos coeficientes
Coeficientes DFT 2D
depois da transformada
de coluna
Conjugado simétrico dos dados Reais
Se a imagem é real, os coeficientes DFT satisfazem as propriedades de
simetria seguintes
 (k , l )   * ( N  k , N  l )
2
1

2

2
3
5
4
7
56

 4 7


2 8   10  2 j

9 3
4


1 4 
 10  2 j
1 3 j
 26
 1  3 j

19  7 j  16  2 j 7  3 j 

 1  3 j 10  1  3 j 

7  3 j  16  2 j 19  7 j 
Compactação da Energia
A DFT disponibiliza uma compactação de energia significativa para
a maioria das imagens.
Espectro DFT
Coeficientes de
Baixa Frequência
Observa-se que a maior parte da energia está concentrada nos
quatro cantos da imagem que representam as baixas frequências.
Definição da DCT 2D
O par DCT NxN 2D é definido por

N 1 N 1
(2m 1)k
 ( k , l )   ( k ) ( l )   i ( m , n ) cos
2N
m 0 n 0

N 1 N 1
(2m 1)k
i ( m , n )     ( k ) ( l ) cos
2N
k 0 l 0

cos

cos
(2n 1)l
2N

(2n 1)l
 ( k ,l )
2N

0 k, l  N  1
0 m , n  N  1
Imagens de base para DCT 2D
Figura 5.17, pag. 116
Propriedades da DCT 2D

As propriedades da DCT 1D podem ser
prontamente expandidas para a 2D


Compactação da energia na região de
baixas frequências
A DCT 2D é separável

Os coeficientes podem ser calculados
usando as transformadas de fila e de
coluna
DCT 2D: Exemplo 5.12

Usando a abordagem da separabilidade
calcular a DCT 2D da imagem
2
1

2

2
3 4
5 2
4 9
7 1
7

8
3

4
Separabilidade
2
1

2

2
3 4
5 2
4 9
7 1
7
8 
3

4
4  1.37 5  5.92
Row Transform 

8

3
.
76
1

3
.
85


9
2
 4 2.99 


7
0
.
32

1

4
.
4


Column
Transform
2-D DCT
Coefficients
 3.41 0.5
 5.62
 14


 2.23  1.58 5.27  2.81



3
2
.
35
3
.
5

4
.
76





0
.
16
0
.
69

1
.
64
4
.
08


Energy Compaction
 As in the 1-D case, the 2-D DCT can compact energy of typical images
very efficiently.
DCT Coeff.
of Lena image
 Most of the energy is concentrated in the low frequency region (upper
left corner).
 It has been shown that DCT provides near optimal energy compaction
performance for most natural images.
 As a result, it has been accepted as the transform kernel for most
Propriedades da DCT 2D
Compactação da energia
Figura 5.18
DCT e DFT duma Imagem
DFT
DCT
Definição da DWT 2D


Tal como na 1D não há um único núcleo de
transformação
Há DWT 2D unitárias e outras que não


Há DWT 2D separáveis e outras que não



Wavelets bi-ortogonais (não unitárias) populares na
compressão de imagens
A maioria das DWT 2D são dyadic e separáveis
Na DWT 1D, cada nível de decomposição
corresponde a 2 bandas de dados(alta e baixa
resolução)
Na DWT 2D cada nível produz 4 bandas

Baixa, bandas altas verticais, horizontais e diagonais
Wavelets 2D Separáveis
Vertical
Edges
f(x,y)
b
(1,1)
L
Row
Transform
F(x,v)
H
Transform
a
Horizontal
Edges
HH
2-D
Image
2-D DWT
(1 Stage)
LL
Column
a
a
b
(1,1)
HL
LH
LL
HL
HH
b
(1,1)
LH
F(u,v)
Diagonal
Edges
Wavelets 2-D
L
H
Row
LL
HL
LH
HH
Column
Transform
Transform
HH
2-D
Image
2-D DWT
(1 Stage)
HL
LH
LL
Decomposição Wavelet da Imagem da Lena
Informacão Espacial e de Frequência
 Todas as sub-bandas disponibilizam informação espacial e de
frequência
A estrutura espacial da imagem é visível em todas as sub-bandas.
 Pode ser observada uma imagem na banda de mais baixa resolução.
 As bandas de alta frequência disponibilizam as informação detalhada
(arestas) nas várias escalas.
Representação Multi-Resolução
 A decomposição wavelet disponibiliza uma representação multiresolução da imagem.
 Uma imagem grosseira é disponibilizada na banda de baixa
frequência.
Pode-se obter uma imagem de resolução mais alta calculando a
tarnsformada inversa das 4 sub-bandas de menor resolução.
A imagem com resolução total obtém-se calculando a transformada
inversa das 7 sub-bandas
Compactação de energia
 As Wavelets têm um excelente desempenho na compactação da
energia.
 Os coeficientes de sub-bandas altas têm pequena magnitude.
Assim pode ser conseguida uma maior compactação das imagens
quantificando os coeficientes wavelet.
530.4
26.4
8.4
11.3
15.7
5.4
3.4
DWT 2D: Exemplo 5.13

Considere a imagem da Lena do Ex. 5.2. Calcule



A transformada wavelet de dois estágios usando a
wavelet de Daub com 4 impulsos
Coeficientes da transformada
Para os pixels das diferentes bandas calcule a raiz da
energia quadrática média