Análise Multiresolução em Detecção e
Classificação de Sinais Transientes
Francisco M. Garcia
Instituto de Sistemas e Robótica - Instituto
Superior Técnico
Organização da apresentação
• Descrição do problema.
• Problema de detecção e classificação clássico; caso estacionário e
não estacionário; decomposição de Karhunen-Loève.
• Esquema de processamento em tempo real.
• Transformada wavelet discreta; parametrização de filtros.
• Escolha das famílias de wavelets, componentes principais e
intervalo de amostragem; redução da complexidade computacional
mantendo a qualidade do processador, distância de Chernoff.
• Exemplo.
• Conclusões.
Caracterização do problema e objectivos
• Sinais gaussianos de curta duração e passa-banda
• Ruído gaussiano e ruído impulsivo
• Ambiente multicaminho (acústica submarina)
• Baixa relação sinal-ruído
• Processadores em tempo real
• Avaliação da complexidade computacional dos processadores
• Avaliação de limites de desempenho
Ruído
n(t )
Sinal emitido por
uma de entre várias
si (t )
fontes possíveis
Canal
yi (t )
+
r (t )
c
r (t )  yi (t )  n(t ) na hipótese H i ,
com
yi (t )  f [ si (t ), c]
• Sinal determinístico ou estocástico
• Canal conhecido ou desconhecido
• Distribuição do ruído conhecida
• Energia do sinal conhecida ou desconhecida
Sinal observado
no receptor
Classificador Bayesiano
Dado um vector de observações X e um conjunto de hipóteses Hi ,
i=0,…,N-1, escolhe-se a hipótese Hk tal que
P(Hk|X) > P(Hi|X), i  0,..., N  1, i  k
Caso de sinais gaussianos de média nula em ruído gaussiano:
l
ki

1
1
Hk
i
k
>
<
X (Q  Q ) X
T
ki ,
Hi
Em que  ki depende apenas das probabilidades a-priori das hipóteses Hk e Hi
e das respectivas matrizes de covâriancia.
Para N hipóteses possíveis, existem C2N combinações de testes para efectuar,
embora seja apenas necessário efectuar N-1 cálculos quadráticos. De facto,
lki  lk 0  li 0 , k , i  1,..., N  1, k  i
• O processo X é em geral fortemente correlacionado e de elevada dimensão
•A cada li0 pode-se aplicar uma transformação linear Mi (H0 ruído branco):
li0 
X
T
M i(
I

2
 M Ti Q
1
i
T
M i) M i
X
• A transformação óptima no sentido de reduzir o número de coeficientes
é a decomposição de Karhunen-Loève
• Os coeficientes obtidos pela DKL são incorrelacionados (matriz de
covariância diagonal)
• Caso estacionário - a DKL é a série de Fourier
• Caso não estacionário - DKL diferentes para cada classe de sinais diferentes
Diagrama de blocos do detector binário
Td
Ts
Processo de
observação
Filtro
Passa-baixo
ideal
Memória
dim = Nd
Amostragem
Decisão
H1
<
>
H0
Limiar de
comparação
Decomposição
linear
Redução de ordem
Tt
Rácio de
verosimilhança
Memória
dim = Nc
Teste de verosimilhança
Nd - Comprimento dos vectores de decomposição
Nc - Número de coeficientes de decomposição
Ts - Intervalo de amostragem
Td - Ritmo de decomposição
Tt - Ritmo de execução dos testes de verosimilhança
Decomposição wavelet discreta
c0
H
2
G
2
c1
d1
H
2
G
2
H - Filtro passa-baixo
c2
d2
H
2
cJ
G
2
dJ
G - Filtro passa-alto
Propriedade de translação:
seja
Então,
TW[c0(n)] = [d1(n) d2(n) … dJ(n) cJ(n)].
TW[c0(n-k2J) ] = [d1(n-k2(J-1)) d2(n-k2(J-2)) … dJ(n-k) cJ(n-k)].
Filtros equivalentes hjk e gjk
cj(k) = <c0(n),hjk(n)> = <C0(W),Hjk(W)>
dj(k) = <c0(n),gjk(n)> = <C0(W),Gjk(W)>
Desenho de filtros G e H de suporte compacto
- H é Passa-baixo
 h( n) 
2
n
- G é Passa-alto
 g ( n)  0
n
- G e H são ortonormados
HG*=0
- Condições de decomposição e reconstrução
H*H + G*G = 1
- Outras restrições: regularidade, simetria, etc...
=> O desenho de filtros QMF com reconstrução perfeita (PR) para
um determinado objectivo corresponde a um problema de
minimização com restrições.
Zou e Tewfik mostraram que todos os filtros de comprimento 2M
são parametrizáveis por um conjunto livre de parâmetros qi,
i=1,…,M-1.
Problema de optimização
Objectivos: - Escolher o intervalo de amostragem, família de wavelets e
no. de coeficientes de forma a reduzir ao máximo a
complexidade computacional
Restrições: - Garantir a qualidade do processador
• Complexidade computacional reduzida se:
- Os Filtros de decomposição forem curtos
- O número de coeficientes fôr pequeno
- As matrizes de covariância forem esparsas
• Qualidade do processador:
- Erro quadrático médio E[e2(t)]: Não é fiável
- Ideal: Probabilidade de erro (computacionalmente incomportável)
- Utilizada: Distância de Chernoff
Distância de Chernoff
 1  sC  (1  s )C
d (C0 , C1 )  max  ln  0 s (1 s ) 1
s
 2  C0 C1
 
 ,
 
s  0,1
Válida para:
- Matrizes definidas positivas
- Processos decompostos na mesma base
Permite obter limiares superior e inferior da probabilidade de erro:
1
e s  exp  d (C0 , C1 )
2
1
e i  1  1  4e s2
2


Funcionais de optimização computacional
da matriz de covariância
i) Sejam E[(dij)2] os elementos da diagonal da matriz de covariância

J1  Ts  E (d i j ) 2
j

2
i
ii) Para uma determinada escala j:

J 2 ( j )   E (d i j ) 2
i
Seja Lij o instante médio do suporte de gij:


1
j 2
E (d i ) 
2
em que
 / Ts

2
S ( L T ,  ) G (Ts ) d ,
j
i s
j
 / Ts
S (t ,  )  TF k (t , t   )( )

Algoritmo de optimização
1 - Encontrar Ts máximo (Tlim), tal que d(Cref,CTs) < e
2 - Para Ts < Tlim e para dim(G,H) = N0, calcular
argmax J i ,
i {1,2}
Ts ,G , H
3 - Com os parâmetros calculados em 2, calcular a matriz de
coeficientes wavelets Cw equivalente a CTs
4 - Eliminar os termos menos importantes da diagonal de Cw,
bem como os respectivos termos cruzados, enquanto
d(Cref,Cw) < e
5 - Avaliar a complexidade computacional. se não fôr satisfatória,
voltar a 2 e repetir para um valor diferente de dim(G,H).
Complexidade computacional
Decomposição KL: - comprimento do sinal N
- No. de vectores próprios P
=> (N+2)xP multiplicações no total (decomposição + forma quadrática)
Transformada Wavelet: - Filtros G e H de comprimento L
- Matriz
I
1
(
 M Ti Q
i
M)
i

com M elementos não nulos
- Vector de coeficientes com K elementos
- Decomposição entre as escalas J1 e J2
2
 J 2 1 j J 2  J1 k 
=> Decomposição:   2   2   L multiplicações
k 0
 j 0

=> Termo quadrático: M+K multiplicações
Não é fácil optimizar os parâmetros directamente no número de multiplicações
Exemplo
Conclusões
• Para sinais transientes, de curta duração, de banda larga, a transformada
wavelet traz vantagens computacionais comparativamente à
decomposição de Karhunen-Loève.
• Os parâmetros do processador podem ser obtidos pela maximização
de funcionais que utilizam os termos da diagonal da matriz de
covariância
• A escolha do intervalo de amostragem influencia fortemente a carga
computacional do processador.
• A família de wavelets, de suporte compacto, pode ser escolhida numa
biblioteca de bases, ou optimizada através de uma parametrização
sem restrições.
• A qualidade das aproximações efectuadas deve ser monitorizada. A
distância de Chernoff é a medida adequada em problemas de detecção.