Quais coeficientes tempo-frequência que a Wavelet transforma calcula?

26

A Transformação rápida de Fourier realiza operações , enquanto a Transformação rápida de wavelet realiza O ( N ) . Mas o que, especificamente, o FWT calcula?O(NlogN)O(N)

Embora muitas vezes sejam comparados, parece que o FFT e o FWT são maçãs e laranjas. Pelo que entendi, seria mais apropriado comparar o STFT (FFTs de pequenos pedaços ao longo do tempo) com o complexo Morlet WT , uma vez que ambas são representações de frequência de tempo baseadas em sinusóides complexos (por favor, corrija-me se estiver errado ) Isso geralmente é mostrado com um diagrama como este:

Grades mostrando como os coeficientes da FFT e WT correspondem ao plano de tempo-frequência

( Outro exemplo )

A esquerda mostra como o STFT é um monte de FFTs empilhados uns sobre os outros à medida que o tempo passa (essa representação é a origem do espectrograma ), enquanto a direita mostra o WD diádico, que tem melhor resolução de tempo em altas frequências e melhor frequência resolução em frequências baixas (essa representação é chamada de escalograma ). Neste exemplo, para o STFT é o número de colunas verticais (6) e uma única operação O ( N log N ) FFT calcula uma única linha de N coeficientes de N amostras. O total é de 8 FFTs de 6 pontos cada, ou 48 amostras no domínio do tempo.NO(NlogN)NN

O que eu não entendo:

  • Quantos coeficientes calcula uma única operação FWT e onde eles estão localizados no gráfico de tempo-frequência acima? O(N)

  • Quais retângulos são preenchidos por uma única computação?

  • Se calcularmos um bloco de área igual de coeficientes de frequência de tempo usando ambos, obteremos a mesma quantidade de dados?

  • O FWT ainda é mais eficiente que o FFT?

Exemplo concreto usando PyWavelets :

In [2]: dwt([1, 0, 0, 0, 0, 0, 0, 0], 'haar')
Out[2]:
(array([ 0.70710678,  0.        ,  0.        ,  0.        ]),
 array([ 0.70710678,  0.        ,  0.        ,  0.        ]))

Ele cria dois conjuntos de 4 coeficientes, portanto, é o mesmo que o número de amostras no sinal original. Mas qual é a relação entre esses 8 coeficientes e os blocos no diagrama?

Atualizar:

Na verdade, eu provavelmente estava fazendo isso errado e deveria estar usando wavedec(), o que faz uma decomposição DWT em vários níveis:

In [4]: wavedec([1, 0, 0, 0, 0, 0, 0, 0], 'haar')
Out[4]: 
[array([ 0.35355339]),
 array([ 0.35355339]),
 array([ 0.5,  0. ]),
 array([ 0.70710678,  0.        ,  0.        ,  0.        ])]
endólito
fonte
2
Para entender melhor como essas decomposições de wavelets funcionam, uma ferramenta útil seria fazê-lo em sinais da vida real: sinal de áudio, por exemplo (por exemplo, tenho uma pergunta nessa direção dsp.stackexchange.com/ Perguntas / 12694 / stft-e-dwt-wavelets )
Basj
@ endolith Sua pergunta ainda é solicitada? Nesse caso, posso adicionar outras dicas #
Laurent Duval
@LaurentDuval Sim, ainda está aberto e eu ainda não entendo. Eu posso estar confuso porque o CWT usa coisas como Morlet e o DWT usa coisas como Haar ou Daubechies. Não tenho certeza se o FWT rápido é apenas Haar ou também pode usar outros tipos de wavelets.
endolith
2
@ndolith Apenas um comentário para este: o CWT contínuo admite uma quantidade incrível de possíveis formas de wavelets. Eles podem ser discretizados exatamente apenas com padrões de amostragem (em tempo ou escala) que respeitam alguma desigualdade "Heisenberg". Esses padrões dependem da wavelet. Na maioria dos casos, os padrões produzem um CWT discretizado que é redundante. Alguns o querem não redundante, com uma escala diádica. Apenas muito poucas wavelets permitem isso. Se você, em seguida, impor o apoio wavelet ser finito, então Haar é um, quase impossível obter w / "wavelets naturais", que aqueles por que Daubechies' foram construídos
Laurent Duval

Respostas:

13

Você está certo de que o FWT é melhor pensado como um "primo" do STFT, em vez de o FT. De fato, o FWT é apenas uma amostragem discreta do CWT (transformada de wavelet contínua), pois o FFT / DFT é uma amostragem discreta da transformada de Fourier. Isso pode parecer um ponto sutil, mas é relevante ao escolher como você discretiza a transformação.

O CWT e o STFT são análises redundantes de um sinal. Em outras palavras, você tem mais "coeficientes" (no caso discreto) do que precisa para representar totalmente um sinal. No entanto, uma transformação de Fourier (ou seja, uma transformação de wavelet usando apenas uma escala) integra um sinal de-infinito a + infinito. Isso não é muito útil em sinais do mundo real; portanto, truncamos (ou seja, janela) as transformações para comprimentos menores. A janela de um sinal altera a transformação - você multiplica pela janela no tempo / espaço, portanto, no espaço da transformação, você tem a convolução da transformação da janela com a transformação do sinal.

No caso do STFT, as janelas têm (geralmente) o mesmo comprimento (extensão diferente de zero) o tempo todo e são independentes de frequência (você visualiza um sinal de 10 Hz com a mesma largura que um sinal de 10 kHz). Então você obtém o espectrograma de grade retangular como você desenhou.

O CWT tem essa janela embutida pelo fato de que as wavelets ficam mais curtas (no tempo ou no espaço) à medida que a escala diminui (como maior frequência). Portanto, para frequências mais altas, a janela efetiva é mais curta e você termina com um escalograma que se parece com o que você desenhou para o FWT.

A decisão de como discretizar o CWT depende de você, embora eu ache que há amostragens mínimas em turnos e escalas para representar totalmente um sinal. Normalmente (pelo menos como eu os usei), para a escala mais baixa (frequência mais alta), você fará uma amostra em todos os locais do turno (tempo / espaço). À medida que aumenta sua escala (menor frequência), você pode experimentar com menos frequência. A lógica é que as frequências baixas não mudam tão rapidamente (pense em uma queda de pratos versus um baixo - o impacto dos pratos tem transitórios muito curtos, enquanto o baixo levaria mais tempo para mudar). De fato, na escala mais curta (supondo que você faça uma amostragem em todos os locais do turno), você tem a representação completa de um sinal (você pode reconstruí-lo usando apenas os coeficientes nessa escala). Não tenho tanta certeza sobre a lógica de amostrar a escala. EU' Já vi isso sugerido como logarítmico, com (acho) um espaçamento mais próximo entre escalas mais curtas. Eu acho que isso ocorre porque as wavelets em escalas mais longas têm uma transformada de Fourier mais ampla (portanto, "captam" mais frequências).

Admito que não entendo completamente o FWT. Meu palpite é que na verdade é a amostragem mínima em turno / escala e não é uma representação redundante. Mas acho que você perde a capacidade de analisar (e mexer com) um sinal em pouco tempo sem a introdução de artefatos indesejados. Vou ler mais sobre isso e, se aprender alguma coisa útil, informarei de volta. Espero que outros gostem de comentar.

Patrick
fonte
11
"é na verdade a amostra mínima em mudança / escala e não é uma representação redundante". Ah! Acho que você está certo, e isso explicaria por que é sempre comparado ao FFT, que também é uma representação mínima.
endolith 24/11/2009
3
O FWT é uma amostra crítica do CWT. Ainda estou tentando entender melhor, mas aprendi que o STFT e o CWT são ambos quadros. A teoria dos quadros está me ultrapassando, mas uma noção interessante é a fórmula da incerteza, que para o STFT, dw * dt> C (dw é a resolução de frequência e dt é a resolução de tempo). Em outras palavras, ao tentar resolver melhor a frequência, você perde a resolução do tempo. O CWT não tem essa limitação. Continuarei lendo e tentarei esclarecer minha resposta acima assim que esclarecer em minha mente.
11
Pelo que entendi, o CWT tem a mesma limitação, mas usa um trade-off melhor.
endolith
11
"STFT são análises redundantes de um sinal". Eu não acho que seja verdade. Se você tiver um sinal de 100 pontos, divida-o em pedaços de 10 pontos e faça uma FFT de 10 pontos em cada um deles, você ainda terá as mesmas informações armazenadas na mesma quantidade de amostras.
endolith
11

Considere o caso da wavelet de Haar. A Transformada rápida de wavelet subdivide recursivamente o seu sinal e calcula a soma e a diferença das duas metades de cada vez. A diferença é a magnitude da transformação para a wavelet atual e a soma é retornada para o chamador calcular a magnitude da transformação para uma wavelet dilatada com metade da frequência. Assim, o FWT cobre o plano de frequência do tempo usando o padrão descrito no diagrama que você forneceu.

Observe que o diagrama que você deu é um pouco enganador. O que eles realmente estão tentando lhe dizer é que você obtém uma amostra na frequência mais baixa, duas amostras no dobro dessa frequência, quatro amostras no quádruplo dessa frequência e assim por diante. As propriedades de frequência e tempo de cada wavelet não são tais que cobrem seu ladrilho. Na prática, cada wavelet cobrirá uma área infinita porque possui suporte compacto e, portanto, deve ser completamente deslocalizada em termos de frequência. Então, você deve apenas pensar nos centros dessas peças.

Além disso, o FWT exige uma wavelet discreta que deve aderir a um critério de admissibilidade muito mais restritivo do que as wavelets contínuas para o CWT. Consequentemente, as propriedades de frequência de tempo de wavelets discretas são geralmente terríveis (por exemplo, as wavelets de Daubechies estão cheias de características nítidas ou mudam de frequência) e a utilidade do plano de frequência de tempo é grandemente diminuída no contexto do FWT. No entanto, wavelets contínuas são usadas para calcular representações de sinais no tempo e na frequência.


fonte
Sim, entendo a localização dos coeficientes. É o mesmo que a FFT. Quando você diz "deve aderir", o que você quer dizer? É apenas um requisito se você estiver tentando obter uma representação mínima / não redundante do sinal? E se você estiver apenas tentando analisá-lo / visualizá-lo? Vou adicionar um exemplo mais concreto à pergunta.
endolith
11
A adesão ao critério de admissibilidade garante a existência de uma resolução da identidade, ou seja, que todos os sinais possam ser recuperados de suas transformadas de wavelets. Se você não aderir a ele, não poderá recuperar um sinal de sua transformação; nesse momento, deverá questionar o que exatamente está analisando (isso reflete alguma informação que estava no sinal ?!). Se você não precisar de uma representação mínima / não redundante, poderá usar o critério de negligência mais laxista do CWT (que permite definir wavelets mais "ideais").
11
Eu acho que você acharia minha tese de doutorado realmente útil. Vou colocá-lo on-line para você ...
Você colocou online? :)
endolith 25/02/10
2
Tenho certeza que sim: flyingfrogblog.blogspot.com/2010/02/…
3

Sua referência tem:

Uma sequência de coeficientes com base em uma base ortogonal de pequenas ondas finitas ou wavelets.

Para mais, você pode gostar da página DWT . Lá, introduz wavelets Haar, waubets Daubechies e outras. Aponta como

  • As wavelets possuem localização - a (1,1, –1, –1) corresponde ao "lado esquerdo" versus "lado direito", enquanto as duas últimas wavelets têm suporte no lado esquerdo ou no lado direito, e uma é uma tradução do outro.
  • As ondas sinusoidais não têm localização - elas se espalham por todo o espaço - mas possuem fase - a segunda e a terceira ondas são transladadas uma da outra, correspondendo a 90 ° fora de fase, como cosseno e seno, das quais são versões discretas .

Se, em vez de wavelets discretas, você quiser agora sobre wavelets contínuas ou wavelets complexas, poderá começar com séries de wavelets .

Além da wikipedia, um livro e um curso podem ser úteis.


fonte
Eu não entendo essa resposta. Responde às minhas perguntas? Lado esquerdo e lado direito de quê? O que isso tem a ver com a representação da frequência do tempo?
endolith 24/11/2009
A descrição "lado esquerdo versus lado direito" é uma prévia extraída da página DWT, mostrando que essa página inclui um exemplo simples para explicar os méritos relativos da base sinusoidal e das wavelets de Haar. Você estava perguntando sobre a natureza dos coeficientes em uma transformação wavelet. Parecia que você estava procurando intuição. Eu pensei que você poderia achar esse exemplo (em seu contexto original) útil.
Sim, li os artigos da Wikipedia várias vezes antes de postar esta pergunta. Não sei se / o que sua resposta tem a ver com a minha pergunta sobre a representação de frequência e tempo. Se sim, você poderia conectar os pontos? Uma FFT de n amostras produzirá n coeficientes, que compõem uma única coluna do espectrograma STFT. Existe uma relação correspondente entre os coeficientes produzidos pelo TP e o escalograma? Se assim for, o que é? Quais das caixas no gráfico inferior direito são preenchidas por uma única execução no FWT?
endolith 24/11/2009
11
Quase tudo nas páginas da Wikipedia relacionadas a wavelets está errado no momento.
3

O(N2)

O(N)O(Nlog(N))O()

Comece pelo STFT genérico em janela (formulário contínuo). Se você conectar uma janela infinita de altura da unidade, recuperará a transformação de Fourier como um caso especial. Você pode discretizar (e obter a DFT) e torná-la rápida (e obter a FFT).

Comece de um CWT (formulário contínuo). O CWT contínuo admite uma quantidade incrível de possíveis formas de wavelets. Eles podem ser discretizados exatamente apenas com padrões de amostragem (em tempo ou escala) que respeitam alguma desigualdade "Heisenberg": uma amostra por unidade de superfície. Esses padrões dependem da wavelet. Na maioria dos casos, os padrões criam um CWT discretizado que é redundante e produz um quadro de wavelet.

Alguns o queriam não redundante, com uma escala diádica (DWT). Apenas muito poucas wavelets (ainda um número infinito, mas você não pode encontrá-las por acaso) permitem isso. Entre os primeiros, estavam as wavelets Haar, Franklin e Meyer. Se você, em seguida, impõe que o suporte da wavelet seja finito, Haar foi o único por um longo tempo. É quase impossível obter uma wavelet ortogonal a partir de "wavelets naturais contínuas", por isso as de Daubechies foram construídas e, posteriormente, Symmlets e Coiflets . Essas wavelets de formato estranho não têm fórmulas simples e agradáveis, como a wavelet de Morlet.

O(N)

De fato, o FWT é apenas uma amostra discreta do CWT

O DWT (ou FWT) é exato, como o DFT / FFT. A maioria dos outros CWT discretizados (com qualquer wavelet) é apenas aproximadamente isso (sem muito dano se você tiver redundância suficiente).

Tão:

  • kkk804T2×424[ω/2,ω]42×22[ω/8,ω/4][1,1,2,4]
  • k
  • +×O(N)

As figuras a seguir revelam como uma versão contínua da wavelet Haar wavelet contínuo de Haar

pode ser amostrada em uma wavelet discreta ortogonal: wavelet crítica discreta de Haar

Observe que algumas wavelets discretas, especialmente as longas (como splines), às vezes são calculadas usando uma FFT :)

Laurent Duval
fonte