Quels coefficients temps-fréquence la transformée en ondelettes calcule-t-elle?

La transformation de Fourier rapide prend les opérations , tandis que la transformation rapide en ondelettes prend . Mais que calcule précisément le FWT?$\mathcal O(N \log N)$$\mathcal O(N)$

Bien qu'ils soient souvent comparés, il semble que les FFT et FWT soient des pommes et des oranges. Si je comprends bien, il serait plus approprié de comparer les STFT (FFT de petits morceaux dans le temps) avec le Morlet WT complexe , car ce sont deux représentations temps-fréquence basées sur des sinusoïdes complexes (veuillez me corriger si je me trompe ). Ceci est souvent montré avec un diagramme comme celui-ci:

( Un autre exemple )

La gauche montre comment le STFT est un tas de FFT empilés les uns sur les autres au fil du temps (cette représentation est à l'origine du spectrogramme ), tandis que la droite montre le WT dyadique, qui a une meilleure résolution temporelle à hautes fréquences et une meilleure fréquence résolution aux basses fréquences (cette représentation est appelée un scalogramme ). Dans cet exemple, pour le STFT est le nombre de colonnes verticales (6), et une seule opération FFT calcule une seule ligne de coefficients à partir de échantillons. Le total est de 8 FFT de 6 points chacune, soit 48 échantillons dans le domaine temporel.O ( N log N ) N $N$$\mathcal O(N \log N)$$N$$N$

Ce que je ne comprends pas:

• Combien de coefficients une seule opération FWT calcule-t-elle et où sont-ils situés sur le graphique temps-fréquence ci-dessus? $\mathcal O(N)$

• Quels rectangles sont remplis par un seul calcul?

• Si nous calculons un bloc de surface égale de coefficients temps-fréquence en utilisant les deux, obtenons-nous la même quantité de données?

• Le FWT est-il toujours plus efficace que le FFT?

Exemple concret utilisant 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.        ]))

Il crée deux ensembles de 4 coefficients, c'est donc le même que le nombre d'échantillons dans le signal d'origine. Mais quelle est la relation entre ces 8 coefficients et les tuiles du diagramme?

Mise à jour:

En fait, je faisais probablement mal, et je devrais utiliser wavedec(), qui fait une décomposition DWT à plusieurs niveaux:

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.        ])]

Vous avez raison de dire que le FWT est mieux considéré comme un "cousin" du STFT plutôt que du FT. En fait, le FWT n'est qu'un échantillonnage discret de la CWT (transformée en ondelettes continue), car le FFT / DFT est un échantillonnage discret de la transformée de Fourier. Cela peut sembler être un point subtil, mais il est pertinent lorsque vous choisissez comment discrétiser la transformation.

Le CWT et le STFT sont tous deux des analyses redondantes d'un signal. En d'autres termes, vous avez plus de "coefficients" (dans le cas discret) que vous n'en avez besoin pour représenter pleinement un signal. Cependant, une transformée de Fourier (ou disons une transformée en ondelettes utilisant une seule échelle) intègre un signal de -infini à + infini. Ce n'est pas très utile sur les signaux du monde réel, donc nous tronquons (c'est-à-dire la fenêtre) les transformations à des longueurs plus courtes. Le fenêtrage d'un signal modifie la transformation - vous multipliez par la fenêtre dans le temps / espace, donc dans l'espace de transformation vous avez la convolution de la transformation de la fenêtre avec la transformation du signal.

Dans le cas de la STFT, les fenêtres ont (généralement) la même longueur (étendue non nulle) à tout moment et sont indépendantes de la fréquence (vous affichez un signal à 10 Hz de la même largeur qu'un signal à 10 kHz). Vous obtenez donc le spectrogramme à grille rectangulaire comme vous l'avez dessiné.

Le CWT a ce fenêtrage intégré par le fait que les ondelettes raccourcissent (dans le temps ou l'espace) à mesure que l'échelle diminue (comme une fréquence plus élevée). Ainsi, pour des fréquences plus élevées, la fenêtre effective est plus courte et vous vous retrouvez avec un scalogramme qui ressemble à ce que vous avez dessiné pour le FWT.

La façon dont vous discrétisez le CWT dépend quelque peu de vous, bien que je pense qu'il y ait un minimum d'échantillonnages à la fois en décalage et en échelle pour représenter pleinement un signal. Typiquement (au moins comment je les ai utilisés), pour l'échelle la plus basse (fréquence la plus élevée), vous échantillonnerez à tous les emplacements de décalage (temps / espace). Au fur et à mesure que vous augmentez l'échelle (plus basse en fréquence), vous pouvez échantillonner moins souvent. La raison en est que les basses fréquences ne changent pas aussi rapidement (pensez à un crash de cymbale par rapport à une guitare basse - le crash de cymbale a des transitoires très courts, alors que la guitare basse prendrait plus de temps à changer). En fait, à l'échelle la plus courte (en supposant que vous échantillonnez à tous les emplacements de décalage), vous avez la représentation complète d'un signal (vous pouvez le reconstruire en utilisant uniquement les coefficients à cette échelle). Je ne suis pas sûr de la justification de l'échantillonnage de l'échelle. JE' Nous avons vu cela comme étant logarithmique, avec (je pense) un espacement plus étroit entre des échelles plus courtes. Je pense que c'est parce que les ondelettes à des échelles plus longues ont une transformée de Fourier plus large (donc elles "captent" plus de fréquences).

J'avoue que je ne comprends pas bien le FWT. Mon intuition est qu'il s'agit en fait de l'échantillonnage minimum en décalage / échelle, et n'est pas une représentation redondante. Mais je pense que vous perdez la capacité d'analyser (et de jouer avec) un signal en peu de temps sans introduire d'artefacts indésirables. J'en lirai plus à ce sujet et, si j'apprends quelque chose d'utile, j'en rendrai compte. J'espère que d'autres aimeront commenter.

Prenons le cas des ondelettes Haar. La transformation rapide en ondelettes subdivise récursivement votre signal et calcule la somme et la différence des deux moitiés à chaque fois. La différence est la magnitude de la transformation pour l'ondelette actuelle et la somme est renvoyée à l'appelant pour calculer la magnitude de la transformation pour une ondelette dilatée avec la moitié de la fréquence. Ainsi, le FWT couvre le plan temps-fréquence en utilisant le modèle décrit dans le diagramme que vous avez donné.

Notez que le diagramme que vous avez donné est un peu trompeur. Ce qu'ils essaient vraiment de vous dire, c'est que vous obtenez un échantillon à la fréquence la plus basse, deux échantillons au double de cette fréquence, quatre échantillons au quadruple de cette fréquence et ainsi de suite. Les propriétés temps-fréquence de chaque ondelette ne sont pas telles qu'elles recouvrent leur tuile. En pratique, chaque ondelette couvrira une zone infinie car elles ont un support compact et doivent donc être complètement délocalisées en termes de fréquence. Donc, vous devriez juste penser au centre de ces tuiles.

En outre, le FWT nécessite une ondelette discrète qui doit respecter un critère d'admissibilité beaucoup plus restrictif que les ondelettes continues pour le CWT. Par conséquent, les propriétés temps-fréquence des ondelettes discrètes sont généralement affreuses (par exemple, les ondelettes Daubechies sont pleines de caractéristiques nettes ou ont une fréquence changeante) et l'utilité du plan temps-fréquence est considérablement diminuée dans le contexte du FWT. Cependant, des ondelettes continues sont utilisées pour calculer les représentations temps-fréquence des signaux.

Votre référence l'a:

Une séquence de coefficients basée sur une base orthogonale de petites ondes finies, ou ondelettes.

Pour plus, vous aimerez peut-être la page DWT . Il y présente les ondelettes Haar, les ondelettes Daubechies et autres. Il montre comment

• Les ondelettes ont un emplacement - l'ondelette (1,1, –1, -1) correspond au "côté gauche" par rapport au "côté droit", tandis que les deux dernières ondelettes ont un support du côté gauche ou du côté droit, et l'une est une traduction de l'autre.
• Les ondes sinusoïdales n'ont pas d'emplacement - elles se propagent dans tout l'espace - mais ont une phase - les deuxième et troisième ondes sont des traductions l'une de l'autre, correspondant à un déphasage de 90 °, comme le cosinus et le sinus, dont ce sont des versions discrètes .

Si, au lieu d'ondelettes discrètes, vous voulez maintenant parler des ondelettes continues ou des ondelettes complexes, vous pouvez commencer par des séries d'ondelettes .

Au-delà de wikipedia, un manuel et un cours pourraient vous faire du bien.

$O(N^2)$

$O(N)$$O(N\log(N))$$O(\cdot)$

Commencez par le STFT fenêtré générique (forme continue). Si vous branchez une fenêtre infinie de hauteur unitaire, vous récupérez la transformée de Fourier comme un cas spécial. Que vous pouvez discrétiser (et obtenir la DFT) et la rendre rapide (et obtenir la FFT).

Commencez à partir d'un CWT (formulaire continu). Le CWT continu admet une quantité incroyable de formes d'ondelettes potentielles. Ils ne peuvent être discrétisés exactement qu'avec des modèles d'échantillonnage (en temps ou en échelle) qui respectent une certaine inégalité de "Heisenberg": un échantillon par unité de surface. Ces motifs dépendent de l'ondelette. Dans la majorité des cas, les motifs font une CWT discrétisée qui est redondante et produisent une trame d'ondelettes.

Certains l'ont voulu non redondant, avec une échelle dyadique (DWT). Seules très peu d'ondelettes (toujours un nombre infini, mais vous ne pouvez pas les trouver par hasard) le permettent. Parmi les premières figuraient les ondelettes Haar, Franklin et Meyer. Si vous imposez ensuite que le support d'ondelettes est fini, alors Haar était tout à fait le seul pendant longtemps. Il est presque impossible d'obtenir une ondelette orthogonale à partir "d'ondelettes continues naturelles", c'est pourquoi celles de Daubechies ont été construites, et plus tard Symmlets et Coiflets . Ces ondelettes de forme bizarre n'ont pas de formules agréables et simples comme l'ondelette de Morlet.

$O(N)$

En fait, le FWT est juste un échantillonnage discret du CWT

DWT (ou FWT) est exact, comme le DFT / FFT. La plupart des autres CWT discrétisés (avec n'importe quelle ondelette) le sont à peu près (sans trop de mal si vous avez une redondance suffisante).

Alors:

• $k$$k$$k$$8$$0$$4T$$2\times 4$$2$$4$$[\omega/2,\omega]$$4$$2\times2$$2$$[\omega/8,\omega/4]$$[1,1,2,4]$
• $k$
• $+$$\times$$O(N)$

Les images suivantes révèlent comment une version continue de l'ondelette Haar

peut être échantillonné en une ondelette orthogonale discrète:

Notez que certaines ondelettes discrètes, en particulier les longues (comme les splines), sont parfois calculées à l'aide d'une FFT :)