WaveletsAluno: Marcos Corrêa – maccjcin@gmail.comDisciplina: Rede de Computadores

ROTEIRO▫Conceitos Básicos▫História das Wavelets▫Transformada de Wavelet▫Transformada Inversa de Wavelet▫Análise de Wavelet▫Lista de Wavelets▫Comparação com a Transformada de

Fourier▫Aplicações Variadas – Exemplos▫Referências

Conceitos Básicos• O que são Wavelets?

▫ Funções matemáticas

• Características▫ Para ser considerada uma wavelet uma função deve:

Ter a área total sob a curva da função igual a zero (Admissibilidade – integral é zero);

Energia da função ser finita (Regularidade - Bem localizada);

Outra necessidade técnica é a rapidez e facilidade para calcular a transformada wavelet e a transformada inversa (Inversibilidade);

Conceitos Básicos• Por que Wavelet são importantes?

▫ São Blocos Construtores de Funções Uma função pode ser representada como uma combinação linear de funções

Wavelets.

▫ Existem teoricamente infinitas possibilidades de se projetar wavelets com propriedades especiais, voltadas para aplicações específicas.

▫ Possuem Localização Tempo-Freqüência Tempo via translação ou deslocamento Frequência/Escala Via dilatação

▫ Têm Algoritmos Rápidos

▫ Muitas classes de funções podem ser representadas em wavelets de forma mais compacta, como funções com descontinuidade ou picos

Conceitos Básicos•Aspectos de Wavelet

Meyer Haar

Daubechies D10

Morlet Mexican hat Fonte: wikipedia

Conceitos Básicos• Diversas Áreas de Aplicações de Wavelets

▫Visão Computacional▫Compressão de Dados

Compressão de Impressões Digitais no FBI▫Recuperação de Dados afetados por Ruído▫Detecção de Comportamento Similar▫Tons Musicais▫Astronomia▫Meteorologia▫Processamento Numérico de Imagens▫Muitas Outras

História das Wavelets• 1807 - Fourier (Análise em freqüências)

▫ Com o trabalho de Fourier os matemáticos gradualmente saíram da análise em freqüência para a noção de análise em escala.

▫ • 1909 - Haar (Análise em escala)

▫ Apareceu a primeira menção a wavelet.

• 1930 - P. Levy (Movimento Browniano)▫ Levy estudou o Movimento Browniano um tipo de sinal aleatório e

acreditava que as funções de Haar eram superiores as de Fourier para estudar detalhes complicados do Movimento Browniano.

• 1930 – Littlewood, Paley e Stein (Cálculo de Energia)▫ Este grupo trabalhando independentemente de Levy provocou

inquietação na comunidade científica pois os resultados que eles estavam obtendo indicavam que a energia não se conservava, depois descobriram uma função que variava em escala e mostravam que a energia se conservava.

História das Wavelets• 1980 - Grossman e Morlet (Definição de Wavelets)

▫ Um físico e um engenheiro definiram wavelet no contexto da física quântica. Eles forneceram uma maneira de pensar em wavelet baseado na intuição física.

• 1985 – Mallat (Digital Signal Processing)▫ Deu um novo ponto de partida com seu trabalho em

processamento digital de sinais.

• 1985 - Meyer (Primeira Wavelet não-trivial)

• -- - Daubechies (Bases Ortonormais de Wavelets)▫ Construiu um conjunto de wavelets que talvez seja o

conjunto mais elegante e que hoje tornou-se fundamental nas aplicações envolvendo wavelet.

Transformada de WaveletA transformada de wavelet decompõe uma função definida no domínio do tempo em outra função, definida no domínio do tempo e no domínio da frequência. Ela é definida como:

que é uma função de dois parâmetros reais, a e b. Se definirmos ψa,b(t) como:

Podemos reescrever a transformada como o produto interno das funções f(t) e ψa,b(t):

A função ψ(t) que equivale a ψ1,0(t) é chamada de wavelet mãe (do inglês mother wavelet) enquanto as outras funções ψa,b(t) são chamadas de wavelets filhas. O parâmetro b indica que a função ψ(t) foi transladada no eixo t

de uma distância equivalente a b, sendo então um parâmetro de translação. Já o parâmetro a causa uma mudança

de escala, aumentando (se a > 1) ou diminuindo (se a < 1) a wavelet formada pela função. Por isto o parâmetro a é conhecido como parâmetro de escala (do inglês scaling parameter).

Fonte: wikipedia

Transformada de Wavelet

Fonte: http://users.rowan.edu/~polikar/WAVELETS/WTpart1.html

Transformada Inversa de WaveletComo usamos wavelets para transformar uma função, precisamos também da transformada inversa, de forma a recompor o sinal no domínio do tempo a partir da sua decomposição. Se chamarmos de Ψ(ω) a transformada de Fourier da função ψ(t):

e se W(a,b) for a transformada de wavelet da função f(t) usando a wavelet ψ(t), então temos que a transformada inversa é dada por: onde

Este parâmetro C necessita ser finito e positivo, o que nos leva a uma

nova restrição. Esta restrição sobre o valor de C é a condição de admissibilidade já citada.

Fonte: wikipedia

Análise de WaveletA análise de wavelet é feita pela aplicação sucessiva da transformada de wavelet com diversos valores para os parâmetros a e b, representando a decomposição do sinal original em diversos componentes localizados no tempo e na freqüência, de acordo com estes parâmetros. Cada wavelet possui melhor ou pior localização nos domínios da freqüência e do tempo, por isso a análise pode ser feita com wavelets diferentes de acordo com o resultado desejado.A análise wavelet traz consigo uma análise em resoluções múltiplas, onde o nível de resolução é dado pelo índice a. Nesta análise em resoluções múltiplas, geramos uma seqüência de subespaços encaixantes, onde as funções de base numa escala

a0 não "enxergam" detalhes de tamanho menor que .

Fonte: wikipedia

Lista de Wavelets• Wavelets discretas

▫ Beylkin ▫ BNC wavelets▫ Coiflet ▫ Cohen-Daubechies-Feauveau wavelet (Sometimes

referred to as CDF N/P or Daubechies biorthogonal wavelets)

▫ Daubechies wavelet ▫ Binomial-QMF▫ Haar wavelet▫ Mathieu wavelet▫ Legendre wavelet▫ Villasenor wavelet▫ Symlet Fonte: wikipedia

Lista de Wavelets• Wavelets contínuas• Valores Reais

▫Beta wavelet▫Hermitian wavelet▫Hermitian hat wavelet▫Mexican hat wavelet▫Shannon wavelet

• Valores Complexos▫Complex mexican hat wavelet▫Morlet wavelet▫Shannon wavelet▫Modified Morlet wavelet

Fonte: wikipedia

Comparação com a Transformada de Fourier• A principal diferença é que wavelets estão localizados tanto em tempo

quanto em frequência enquanto a Transformada Fourier é só localizada em frequência;

• A complexidade computacional da transformada de wavelet discreta é O(N) enquanto que da transformada rápida de Fourier é O(N log N);

• Mais uma diferença é que funções wavelet individuais estão bem localizadas no espaço, funções seno e cosseno Fourier não estão;

• Transformadas wavelet não têm um conjunto de funções básicas como a transformada de Fourier, que utiliza senos e cossenos. Em vez disso transformada de wavelet tem um conjunto infinito de possíveis funções;

• Por conta da teoricamente infinita quantidade de funções, nós vamos buscar a melhor função para representar um sinal, essa melhor função é a forma de onda adaptada.

Comparação com a Transformada de Fourier

Fonte: http://www.vision.ime.usp.br/~creativision/publications/pdf/DoutoradoSilvia.pdfFigura (a) – Ondas Senoidais (b) – Chapéu Mexicano

Aplicações Variadas - Exemplos• Transformada Wavelet em Compressão de Imagens

[Computação Gráfica]▫ http://www.cos.ufrj.br/index.php?option=com_publicacao&task

=visualizar&id=687

• On wavelet techniques in atmospheric sciences [Ciências Atmosféricas]▫ http://www.lac.inpe.br/~margarete/JASRWavelet.pdf

Aplicações Variadas – Exemplos 2• Teoria Wavelet e sua aplicação em sistemas de

energia eletrica [Engenharia Elétrica]▫ http://libdigi.unicamp.br/document/?code=vtls000113855

• Uma comparação entre Redes Neurais Wavelet, LMS, MLP e RBF para classificação de DPOC [Redes Neurais – Ciênc. da Computação]▫ http://www.simulab.uel.br/hoto/publica/ferrari-hoto-foz2006.pd

f

Aplicações Variadas – Exemplos 3• Predição de séries temporais econômicas por meio de

redes neurais artificiais e transformada Wavelet: combinando modelo técnico e fundamentalista [Processamento de Sinais de Instrumentação – Eng. Elétrica]▫ http://www.teses.usp.br/teses/disponiveis/18/18152/tde-110420

08-111842/

• Aplicação de transformada wavelet no processamento de sinais ultra-sônicos para caracterização de escoamentos bifásicos ar-água [Engenharia de Produção]▫ http://www.qprocura.com.br/dp/79486/Aplicacao-de-transforma

da-wavelet-no-processamento-de-sinais-ultra_sonicos-para-caracterizacao-de-escoamentos-bifasicos-ar_agua.html

Aplicações Variadas – Exemplos 4• Reconhecimento de Voz usando Wavelets

[Processamento de Sinais – Comput. Aplicada]▫ http://ncg.unisinos.br/robotica/reconvoz.html

• Aplicação de transformada wavelet no processamento de sinais ultra-sônicos para caracterização de escoamentos bifásicos ar-água [Engenharia de Produção]▫ http://www.qprocura.com.br/dp/79486/Aplicacao-de-transform

ada-wavelet-no-processamento-de-sinais-ultra_sonicos-para-caracterizacao-de-escoamentos-bifasicos-ar_agua.html

Aplicações Variadas – Exemplos 5• Prognóstico de Congestionamento de Tráfego de

Redes usando Wavelets [Redes de Computadores - Ciências da Computação]

▫ http://www.larces.uece.br/~jlcs/tese.pdf

Referências• DOVICCHI, João Cândido. Introdução à Teoria das

Wavelets. Univ. Fed. Uberlândia, 2003.▫ Disponível em: http://www.inf.ufsc.br/~dovicchi/papers-jcd/wav-intro.ps

• FERREIRA et al. Proposta de Utilização de Transformadas de Wavelet para Detecção de Ataques em Redes Ad Hoc Sem Fio. CEFETMT, UFU e UFMT, 2008. ▫ Disponível em:http://www.dppg.cefetmt.br/index.html/index.php?

option=com_phocadownload&view=category&id=10:&download=41:p-p&Itemid=86

Referências• WAVELET. Wikipedia, 2009.

▫ Disponível em: http://en.wikipedia.org/wiki/Wavelet

• VIDAKOVIC, Brani and MUELLER, Peter. Wavelet For Kids. Duke University, 2008. ▫ Disponível em:http://www.isye.gatech.edu/~brani/wp/kidsA.pdf

Referências• FARIA, Regis. Wavelets e as Artes

Multiresolucionárias, 1997. ▫ Disponível em: http://www.lsi.usp.br/~regis/wlets.html

• GRAPS, Amara. An Introduction to Wavelets. IEEE, 1995.▫ Disponível em:http://www.amara.com/IEEEwave/IEEEwavelet.html

Referências• DEVORE, Ronald. Wavelets, 1991.

▫ Disponível em: https://www.gprt.ufpe.br/~ajcj/artigos/Wavelets/wavelets.pdf

• Alguns papers sobre Wavelets▫ Disponível em:http://www-math.mit.edu/~gs/papers/recent_wt_papers.html