Transformations en ondelettes discrètes.

6.3.3.1. Informations générales sur les transformations en ondelettes.

La transformée en ondelettes des signaux est une généralisation de l'analyse spectrale, dont un représentant typique est la transformée de Fourier classique.

Les transformées en ondelettes (WT) sont divisées en discrètes (DWT) et continues (CWT). DWT est utilisé pour la conversion et le codage du signal, CWT est utilisé pour l'analyse du signal.

Dans l'analyse par ondelettes, le rôle des fonctions de base est joué par des fonctions d'un type particulier, appelées ondelettes. Le terme « ondelette » traduit de l’anglais signifie « petite onde (courte) ». Les ondelettes sont un nom généralisé pour les familles de fonctions thématiques d'une certaine forme, locales en termes de temps et de fréquence, et dans lesquelles toutes les fonctions sont obtenues à partir d'une fonction de base (génératrice) au moyen de ses déplacements et étirements le long de l'axe du temps.

Les transformées en ondelettes considèrent les fonctions temporelles analysées en termes d'oscillations localisées en temps et en fréquence.

Une particularité de l’analyse par ondelettes est qu’elle peut utiliser des familles de fonctions qui implémentent différentes versions de la relation d’incertitude. En conséquence, le chercheur a la possibilité de choisir entre elles de manière flexible et d'utiliser les fonctions d'ondelettes qui résolvent le plus efficacement les problèmes.

Le principal domaine d'application des transformées en ondelettes est l'analyse et le traitement de signaux et de fonctions non stationnaires dans le temps, lorsque les résultats de l'analyse doivent contenir non seulement la réponse en fréquence du signal (distribution de l'énergie du signal sur la fréquence composants), mais également des informations sur les coordonnées locales auxquelles certaines fonctions se manifestent, des groupes de composants de fréquence ou dans lesquelles se produisent des changements rapides dans les composants de fréquence d'un signal.

Sur la figure 3.1, le signal analysé est constitué de deux déésiens modulés. La transformée en ondelettes de Morlet montre clairement leur localisation spatiale et fréquentielle, tandis que le spectre de Fourier ne donne que la localisation fréquentielle.

L'une des idées principales et particulièrement fructueuses de la représentation en ondelettes des signaux est de diviser les fonctions d'approximation du signal en deux groupes : l'approximation - grossière, avec une dynamique temporelle de changements assez lente, et le détail - avec une dynamique locale et rapide de changements dans le contexte d'une dynamique douce, avec leur fragmentation et leur détail ultérieurs à d'autres niveaux de décomposition du signal. Ceci est possible à la fois dans les domaines temporel et fréquentiel de la représentation en ondelettes des signaux.

Dessin

Figure 3.1 – transformée en ondelettes d'un signal

6.3.3.2. Fonctions de base des transformées en ondelettes.

Les ondelettes se présentent sous la forme de paquets d'ondes courtes de valeur moyenne nulle, localisés le long de l'axe d'argument, invariants au décalage et linéaires à l'opération de mise à l'échelle. En termes de localisation dans la représentation temporelle et fréquentielle, les ondelettes occupent une position intermédiaire entre les fonctions harmoniques localisées en fréquence et la fonction Dirac localisée dans le temps.

La fonction de base d'ondelette représente une oscillation « courte ». De plus, la notion de fréquence d'analyse spectrale a été remplacée par une échelle, et un décalage des fonctions dans le temps a été introduit pour couvrir tout l'axe du temps avec des « ondes courtes ». La base des ondelettes sont des fonctions temporelles du type :

, (3.1)

où b est le décalage ;

une – échelle.

La fonction doit avoir une aire nulle. La transformée de Fourier de ces fonctions est nulle à fréquence nulle et a la forme d'un filtre passe-bande. Différentes valeurs du paramètre d'échelle "a" correspondent à un ensemble de filtres passe-bande. Des familles d'ondelettes dans le domaine temporel ou fréquentiel sont utilisées pour représenter des signaux et des fonctions sous forme de superpositions d'ondelettes à différents niveaux d'échelle de décomposition du signal.

Fonction suivante

ne dépend pas des paramètres et . Le vecteur défini par la fonction a une longueur constante dans l'espace :

.

En pratique, la fonction est souvent utilisée comme fonction de base

appelé chapeau mexicain.

6.3.3.3. Transformation en ondelettes continue.

Soit une fonction et une fonction - une fonction de base. La transformée en ondelettes continue est décrite par une expression de la forme :

. (3.2)

Si la fonction de base est décrite par l'expression :

,

alors le résultat est la transformée de Fourier habituelle (dans ce cas le paramètre n'est pas utilisé).

Pour couvrir tout l'axe temporel de l'espace avec une fonction d'ondelette, l'opération de décalage (déplacement le long de l'axe temporel) est utilisée : , où la valeur b pour NVP est une valeur continue. Pour couvrir toute la gamme de fréquences, une opération de mise à l'échelle temporelle des ondelettes est utilisée avec un changement continu de la variable indépendante : . Ainsi, en se déplaçant le long de la variable indépendante (t-b), l'ondelette a la capacité de se déplacer le long de tout l'axe numérique d'un signal arbitraire, et en changeant la variable d'échelle « a » (en un point fixe de l'axe (t-b)) « visualiser » le spectre de fréquences du signal sur un certain intervalle à proximité de ces points.

Ainsi, la transformée en ondelettes continue est la décomposition du signal en tous les déplacements et compressions/extensions possibles d'une fonction finie localisée - l'ondelette. Dans ce cas, la variable « a » détermine l'échelle de l'ondelette et est équivalente à la fréquence dans la transformée de Fourier, et la variable « b » est le déplacement de l'ondelette le long du signal depuis le point initial dans la région de son définition dont l'échelle répète l'échelle de temps du signal analysé.

Le concept d'échelle VP a une analogie avec l'échelle des cartes géographiques. Les grandes valeurs de zoom correspondent à une vue globale du signal, tandis que les faibles valeurs de zoom permettent de distinguer les détails. En termes de fréquence, les basses fréquences correspondent à des informations globales sur le signal, et les hautes fréquences correspondent à des informations détaillées et à des caractéristiques de faible étendue, c'est-à-dire L'échelle d'ondelettes, en tant qu'unité de l'échelle de représentation temps-fréquence des signaux, est l'inverse de la fréquence. La mise à l'échelle, une opération mathématique, agrandit ou compresse un signal. Les valeurs à grande échelle correspondent aux expansions du signal, et les petites valeurs correspondent aux versions compressées. Dans la définition des ondelettes, le facteur d'échelle UN est au dénominateur. Respectivement, UN> 1 élargit le signal, UN < 1 сжимает его.

6.3.3.4. Transformation en ondelettes discrète.

En principe, lors du traitement de données sur un PC, une version discrétisée de la transformée en ondelettes continue peut être réalisée en spécifiant des valeurs discrètes des paramètres d'ondelette (a, b) avec des étapes arbitraires a et b. Le résultat est un nombre excessif de coefficients, dépassant de loin le nombre d'échantillons du signal d'origine, qui n'est pas requis pour la reconstruction du signal.

La transformée en ondelettes discrète (DWT) fournit suffisamment d'informations à la fois pour l'analyse du signal et pour sa synthèse, tout en étant économique en nombre d'opérations et en mémoire requise. DVP fonctionne avec des valeurs de paramètres discrètes UN Et b, qui sont généralement spécifiées sous forme de fonctions de puissance :

,

,

Où ;

Nombres entiers ;

Paramètre d'échelle ;

Paramètre de décalage.

Base de l'espace en représentation discrète :

Coefficients de transformation directe en ondelettes :

. (3.5)

La valeur de "a" peut être arbitraire, mais elle est généralement définie sur 2 et la conversion est appelée transformée en ondelettes dyadique. Pour la transformation dyadique, un algorithme de calcul rapide a été développé, similaire à la transformée de Fourier rapide, qui a prédéterminé son utilisation généralisée dans l'analyse de tableaux de données numériques.

Transformation discrète inverse pour les signaux continus avec une base d'espace d'ondelettes orthogonale normalisée :

. (3.6)

Le nombre d'ondelettes utilisé par le facteur d'échelle m spécifie le niveau décomposition signal, tandis que le niveau zéro (m = 0) est généralement considéré comme le niveau de résolution temporelle maximale du signal, c'est-à-dire le signal lui-même et les niveaux ultérieurs (m< 0) образуют ниспадающее arbre à ondelettes. Dans les logiciels de calcul, pour éviter l'utilisation d'une numérotation m négative, le signe moins est généralement reporté directement dans la représentation suivante des fonctions de base :

6.3.3.5. Localisation temps-fréquence de l'analyse par ondelettes.

Les vrais signaux sont généralement limités. Le spectre de fréquence des signaux est inversement proportionnel à leur durée. En conséquence, une analyse basse fréquence assez précise du signal doit être effectuée à de grands intervalles de son affectation et une analyse haute fréquence à de petits intervalles. Si la composition fréquentielle d'un signal subit des changements significatifs au cours de l'intervalle de son affectation, alors la transformée de Fourier ne fournit que des données moyennées sur la composition fréquentielle du signal avec une résolution en fréquence constante. Une certaine localisation temps-fréquence de l'analyse est créée par le fonctionnement d'une transformée de Fourier fenêtrée, qui donne des familles de spectres de fréquence localisés dans le temps, mais dans une largeur constante de la fenêtre de la fonction fenêtre, et donc également avec une valeur constante de la résolution fréquentielle et temporelle.

Contrairement à la transformée de Fourier en fenêtre, la transformée en ondelettes, avec des valeurs discrètes similaires de décalages b, donne des familles de spectres de facteurs d'échelle UN compression-tension :

. (3.8)

Si l’on suppose que chaque ondelette a une certaine « largeur » de sa fenêtre temporelle, qui correspond à une certaine fréquence « moyenne » de l’image spectrale de l’ondelette, inverse de son facteur d’échelle UN, alors les familles de coefficients d'échelle de la transformée en ondelettes peuvent être considérées comme similaires aux familles de spectres de fréquence de la transformée de Fourier fenêtrée, mais avec une différence fondamentale. Les facteurs d'échelle modifient la « largeur » des ondelettes et, par conséquent, la fréquence « moyenne » de leurs images de Fourier et, par conséquent, chaque fréquence a sa propre durée de fenêtre temporelle d'analyse, et vice versa. Si petites valeurs de paramètres UN, caractérisant les composantes rapides des signaux, correspondent aux hautes fréquences et les grandes valeurs correspondent aux basses fréquences. En changeant d'échelle, les ondelettes sont capables de détecter des différences à différentes fréquences, et en décalant (paramètre b) analyser les propriétés du signal en différents points tout au long de l'intervalle de temps étudié. La fenêtre temporelle multidimensionnelle de la transformée en ondelettes est adaptée pour identifier de manière optimale les caractéristiques basse et haute fréquence des signaux.

Ainsi, aux hautes fréquences, la résolution temporelle est meilleure, et aux basses fréquences, la résolution fréquentielle est meilleure. Pour la composante haute fréquence du signal, on peut indiquer plus précisément sa position temporelle, et pour la composante basse fréquence, sa valeur fréquentielle.

Les informations haute fréquence (à petite échelle) sont calculées sur la base de longs intervalles de signal, et les informations basse fréquence sont calculées sur la base d'intervalles de signal longs. Étant donné que les signaux analysés sont toujours finis, lors du calcul des coefficients aux limites de la spécification du signal, la région de fiabilité dépasse le signal, et pour réduire l'erreur de calcul, le signal est complété en spécifiant les conditions initiales et finales.

6.3.3.6. Avantages et inconvénients de l'analyse par ondelettes.

Les avantages de l’analyse par ondelettes comprennent :

Les transformées en ondelettes présentent tous les avantages des transformées de Fourier ;

Les bases d'ondelettes peuvent être bien localisées à la fois en fréquence et en temps ;

Lors de l'identification de processus multi-échelles bien localisés dans des signaux, on peut considérer uniquement les niveaux de décomposition d'échelle qui sont intéressants ;

Les bases d'ondelettes, contrairement à la transformée de Fourier, ont de nombreuses fonctions de base différentes, dont les propriétés sont axées sur la résolution de divers problèmes.

L’inconvénient des transformées en ondelettes est leur relative complexité.

6.3.3.7. Propriétés de l'analyse par ondelettes.

L'obtention d'informations objectives sur le signal repose sur les propriétés de la transformée en ondelettes, communes aux ondelettes de tous types. Considérons les principales de ces propriétés. Pour désigner l’opération de transformée en ondelettes de fonctions arbitraires x(t), nous utiliserons l’indice TW.

Linéarité.

TW[α x 1 (t)+β x 2 (t)] = α TW+β TW.

Invariance de décalage. Un décalage temporel du signal de t 0 entraîne également un décalage du spectre des ondelettes de t 0 :

TW = X(a, b-t o).

Invariance d'échelle. L'étirement (compression) du signal entraîne une compression (étirement) du spectre d'ondelettes du signal :

TW = (1/a o)·X(a/a o,b/a o).

Différenciation.

D n (TW)/dt n = TW.

TW = (-1) nx(t)dt.

Cela ne fait aucune différence s'il faut différencier la fonction ou l'ondelette d'analyse. Si l’ondelette de suppression est donnée par une formule, cela peut être très utile pour la suppression de signaux. Les caractéristiques d'ordre élevé ou les variations à petite échelle du signal x(t) peuvent être analysées tout en ignorant les composantes polynomiales à grande échelle (tendance et fond régional) en différenciant le nombre requis de fois soit l'ondelette, soit le signal lui-même. Cette propriété est particulièrement utile lorsque le signal est spécifié sous forme de série discrète.

Analogue du théorème de Parseval pour les ondelettes orthogonales et biorthogonales.

X 1 (t) x 2 *(t) = X ψ -1 a -2 X(a,b) X*(a,b) da db.

Il s’ensuit que l’énergie du signal peut être calculée grâce aux coefficients de transformée en ondelettes.

Fondamentaux du traitement du signal numérique : manuel / Yu.A. Brioukhanov, A.A. Priorov, V.I. Dzhigan, V.V. Khryachchev ; Yarosl. État Université nommée d'après P.G. Demidova. – Iaroslavl : YarSU, 2013. – 344 p. (p. 270)

• Tutoriel

Les ondelettes sont désormais populaires. Même les personnes inexpérimentées en mathématiques ont probablement entendu dire qu'avec leur aide, il est possible de compresser des images et des vidéos tout en conservant une qualité acceptable. Mais qu’est-ce qu’une ondelette ? Wikipédia répond à cette question avec tout un tas de formules derrière lesquelles il n'est pas si facile de voir l'essence.

Essayons d'utiliser des exemples simples pour comprendre d'où viennent les ondelettes et comment elles peuvent être utilisées en compression. On suppose que le lecteur connaît les bases de l'algèbre linéaire, n'a pas peur des mots vecteur et matrice et sait également comment les multiplier. (Et nous essaierons même de programmer quelque chose.)

Compression d'images

Pour faire simple, une image est un tableau dont les cellules stockent les couleurs de chaque pixel. Si nous travaillons avec une image en noir et blanc (ou, plus précisément, grise), alors au lieu de la couleur, les valeurs de luminosité du segment sont placées dans les cellules. Dans ce cas, 0 correspond au noir, 1 au blanc. Mais il n'est pas pratique de travailler avec des fractions, c'est pourquoi les valeurs de luminosité sont souvent considérées comme des nombres entiers compris entre 0 et 255. Chaque valeur occupera alors exactement 1 octet.

Même les petites images nécessitent beaucoup de mémoire pour être stockées. Ainsi, si nous codons la luminosité de chaque pixel avec un octet, alors l'image d'une image FullHD (1920x1080) prendra près de deux mégaoctets. Imaginez combien de mémoire serait nécessaire pour stocker un film d’une heure et demie !

Les images ont donc tendance à être compressées. Autrement dit, codez-le de manière à ce que moins de mémoire soit nécessaire pour le stockage. Et lors de la visualisation, nous décodons les données enregistrées en mémoire et obtenons l'image originale. Mais ce n’est qu’un idéal.

Il existe de nombreux algorithmes de compression de données. Leur nombre peut être jugé par les formats pris en charge par les archiveurs modernes : ZIP, 7Z, RAR, ACE, GZIP, HA, BZ2, etc. Il n'est pas surprenant que grâce au travail actif des scientifiques et des programmeurs, le degré de compression des données se rapproche désormais de la limite théorique.

La mauvaise nouvelle est que pour l’imagerie, cette limite théorique n’est pas si grande. Essayez d'enregistrer une photo (en particulier une photo comportant de nombreux petits détails) au format PNG - la taille du fichier résultant peut vous frustrer.

Cela se produit car dans les images du monde réel (photos par exemple), les valeurs de luminosité sont rarement les mêmes, même entre pixels voisins. Il y a toujours de minuscules fluctuations imperceptibles à l’œil humain, mais que l’algorithme de compression essaie honnêtement de prendre en compte.

Les algorithmes de compression adorent quand il y a un modèle dans les données. Les longues séquences de zéros sont mieux compressées (le modèle ici est évident). En fait, au lieu d'écrire 100 zéros en mémoire, vous pouvez simplement écrire le nombre 100 (bien sûr, en précisant qu'il s'agit exactement du nombre de zéros). Le programme de décodage « comprendra » qu’il s’agit de zéros et les reproduira.

Cependant, si dans notre séquence il s’avère soudainement qu’il y a une unité au milieu, alors nous ne pourrons pas nous limiter au nombre 100.

Mais pourquoi encoder absolument chaque détail ? Après tout, lorsque nous regardons une photographie, le motif global est important pour nous et nous ne remarquerons pas de légères fluctuations de luminosité. Cela signifie que lors de l'encodage, nous pouvons légèrement modifier l'image pour qu'elle soit bien encodée. Dans ce cas, le taux de compression augmentera immédiatement. Certes, l’image décodée différera légèrement de l’originale, mais qui le remarquera ?

Transformation des cheveux

Notre objectif est donc de transformer l’image pour qu’elle soit bien compressée par les algorithmes classiques. Réfléchissons à la façon dont nous devons le modifier pour obtenir de longues chaînes de zéros.

Les images « réelles », telles que les photographies, ont une caractéristique : la luminosité des pixels voisins diffère généralement légèrement. En fait, il est rare d’observer des changements de luminosité brusques et contrastés dans le monde. Et s’ils existent, ils n’occupent qu’une petite partie de l’image.

Considérons un fragment de la première ligne de luminosité de la célèbre image « Lenna » (sur la figure).

154, 155, 156, 157, 157, 157, 158, 156

On voit que les nombres voisins sont très proches. Pour obtenir les zéros souhaités, ou du moins quelque chose qui s'en rapproche, vous pouvez coder le premier nombre séparément, puis considérer uniquement les différences entre chaque nombre et le précédent.

On obtient :

154, 1, 1, 1, 0, 0, 1, -2.

Déjà mieux ! Cette méthode est actuellement utilisée et s’appelle le codage delta. Mais il présente un sérieux inconvénient : il n’est pas local. Autrement dit, vous ne pouvez pas prendre un morceau de la séquence et découvrir exactement quelles luminosités y sont codées sans décoder toutes les valeurs​​avant ce morceau.

Essayons de procéder différemment. N'essayons pas d'obtenir une bonne séquence tout de suite, essayons de l'améliorer au moins un peu.

Pour ce faire, divisons tous les nombres en paires et trouvons les demi-sommes et demi-différences des valeurs dans chacun d’eux.

(154, 155), (156, 157), (157, 157), (158, 156)
(154.5, 0.5), (156.5, 0.5), (157, 0.0), (157, -1.0)

Pourquoi des demi-sommes et des demi-différences ? Et tout est très simple ! La demi-somme est la valeur de luminosité moyenne d'une paire de pixels. Et la demi-différence contient des informations sur les différences entre les valeurs de la paire. Évidemment, connaissant la demi-somme a et la demi-différence d, vous pouvez trouver les valeurs elles-mêmes :
première valeur de la paire = a - d,
deuxième valeur de la paire = a + d.

Cette transformation fut proposée en 1909 par Alfred Haar et porte son nom.

Où est la compression ?

Les nombres obtenus peuvent être regroupés selon le principe « mouches séparément, côtelettes séparément », en divisant moitié sommes et moitié différences :

154.5, 156.5, 157, 157; 0.5, 0.5, 0.0, -1.0.

Les nombres dans la seconde moitié de la séquence seront généralement petits (le fait qu’ils ne soient pas des nombres entiers ne vous dérange pas pour l’instant). Pourquoi est-ce ainsi ?

Comme nous l'avons découvert précédemment, dans les images réelles, les pixels voisins diffèrent rarement de manière significative les uns des autres. Si la valeur de l’un est grande, alors l’autre l’est aussi. Dans de tels cas, les pixels voisins sont dits corrélés.

En fait, considérons les 2000 premières paires de pixels voisins et représentons chaque paire comme un point sur le graphique.

Tous les points sont alignés le long d’une ligne droite. Et ainsi dans presque toutes les images réelles. Les coins supérieur gauche et inférieur droit de l’image sont presque toujours vides.

Regardons maintenant un graphique dans lequel les points sont des demi-sommes et des demi-différences.

On constate que les demi-différences se situent dans une plage de valeurs beaucoup plus étroite. Cela signifie que vous pouvez y consacrer moins d’un octet. Une sorte de compression.

Utilisons les mathématiques !

Essayons d'écrire des expressions mathématiques décrivant la transformée de Haar.

Nous avions donc une paire de pixels (vecteur) et nous voulons en obtenir une paire.

Cette transformation est décrite par la matrice.

En effet , c'est ce dont nous avions besoin.

Le lecteur attentif aura sans doute remarqué que les motifs de points sur les deux derniers graphiques sont les mêmes. La seule différence est la rotation à un angle de 45°.

En mathématiques, les rotations et les étirements sont appelés transformations affines et sont décrits précisément en multipliant une matrice par un vecteur. C’est ce que nous avons obtenu ci-dessus. Autrement dit, la transformée de Haar consiste simplement à faire pivoter les points afin qu'ils puissent être codés de manière pratique et compacte.

Certes, il y a ici une nuance. Lors de transformations affines, l'aire d'une figure peut changer. Non pas que ce soit mauvais, mais plutôt bâclé. Comme on le sait, le coefficient de changement de superficie est égal au déterminant de la matrice. Voyons ce qu'il en est pour la transformation Haar.

Pour que le déterminant devienne égal à un, il suffit de multiplier chaque élément de la matrice par . Cela n’affectera pas l’angle de rotation (et donc le « pouvoir compressif » de la transformation).

On se retrouve avec une matrice

Comment décoder ?

Comme on le sait, si une matrice a un déterminant qui n'est pas égal à zéro, alors il existe pour elle une matrice inverse qui « annule » son action. Si l'on trouve la matrice inverse de H, alors le décodage consistera simplement à multiplier par elle les vecteurs avec des demi-sommes et des demi-différences.

D'une manière générale, trouver l'inverse d'une matrice n'est pas une tâche si simple. Mais peut-être pouvons-nous d’une manière ou d’une autre simplifier cette tâche ?

Regardons de plus près notre matrice. Il se compose de deux vecteurs lignes : et . Appelons-les v 1 et v 2.

Ils ont des propriétés intéressantes.

Premièrement, leurs longueurs sont égales à 1, c'est-à-dire. Ici, la lettre T signifie transposer. La multiplication d'un vecteur ligne par un vecteur ligne transposé est un produit scalaire.

Deuxièmement, ils sont orthogonaux.

Une matrice dont les lignes ont les propriétés spécifiées est dite orthogonale. Une propriété extrêmement importante de telles matrices est que leur matrice inverse peut être obtenue par simple transposition.

La validité de cette expression peut être vérifiée en multipliant la matrice inverse H. Sur la diagonale, nous obtenons des produits scalaires de lignes vectorielles entre elles, c'est-à-dire 1. Et en dehors des diagonales, nous obtenons des produits scalaires de lignes vectorielles entre elles, c'est-à-dire 0. En conséquence, le produit sera égal au matrice d'identité.

Nous adorons les matrices orthogonales !

Augmenter le nombre de points

Tout ce qui précède fonctionne bien sur deux points. Mais que se passe-t-il s’il y a plus de points ?

Dans ce cas, il est également possible de décrire la transformation avec une matrice, mais de plus grande taille. La diagonale de cette matrice sera constituée de matrices H, ainsi des paires seront sélectionnées dans le vecteur de valeurs initiales auxquelles la transformée de Haar sera appliquée indépendamment.

C'est-à-dire. le vecteur original est simplement traité indépendamment par paires.

Filtres

Alors maintenant que nous savons comment effectuer la transformation de Haar, essayons de comprendre ce que cela nous donne.

Les «demi-sommes» résultantes (du fait que nous ne divisons pas par 2, nous devons utiliser des guillemets) sont, comme nous l'avons déjà découvert, les valeurs moyennes en paires de pixels. Autrement dit, les valeurs de la demi-somme sont une copie réduite de l'image originale ! Réduit car les demi-sommes sont deux fois plus petites que les pixels d'origine.

Mais quelles sont les différences ?

Ils représentent la moitié des valeurs de luminosité moyennes, c'est-à-dire qu'ils « filtrent » les pics aléatoires de valeurs. Nous pouvons considérer cela comme une sorte de filtre de fréquence.

De même, les différences « mettent en évidence » les « pics » interpixels parmi les valeurs et éliminent la composante constante. Autrement dit, ils « filtrent » les basses fréquences.

Ainsi, la transformée de Haar est une paire de filtres qui séparent le signal en composantes basse fréquence et haute fréquence. Pour obtenir le signal original, il vous suffit de combiner à nouveau ces composants.

Qu'est-ce que cela nous donne ? Prenons une photo de portrait. La composante basse fréquence transporte des informations sur la forme générale du visage et les changements fluides de luminosité. La haute fréquence est constituée de bruit et de petits détails.

Habituellement, lorsque nous regardons un portrait, nous nous intéressons davantage à la composante basse fréquence, ce qui signifie que lors de la compression, certaines données haute fréquence peuvent être supprimées. De plus, comme nous l’avons découvert, ses valeurs sont généralement plus petites, ce qui signifie qu’il est codé de manière plus compacte.

Le taux de compression peut être augmenté en appliquant la transformée de Haar à plusieurs reprises. En fait, la composante haute fréquence ne représente que la moitié de l’ensemble des nombres. Mais qu’est-ce qui nous empêche d’appliquer à nouveau notre procédure aux données basse fréquence ? Après une application répétée, les informations à haute fréquence occuperont 75 %.

Bien que nous ayons parlé jusqu’à présent de chaînes de nombres unidimensionnelles, cette approche fonctionne également bien pour les données bidimensionnelles. Pour effectuer une transformation Haar bidimensionnelle (ou similaire), il vous suffit de l'effectuer pour chaque ligne et pour chaque colonne.

Après une application répétée, par exemple, sur une photographie du château du Liechtenstein, nous obtenons l'image suivante.

Les zones noires correspondent à une faible luminosité, c'est-à-dire des valeurs proches de zéro. Comme le montre la pratique, si la valeur est suffisamment petite, elle peut alors être arrondie ou même remise à zéro sans trop endommager l'image décodée.

Ce processus est appelé quantification. Et c’est à ce stade que certaines informations se perdent. (À propos, la même approche est utilisée en JPEG, seulement là, au lieu de la transformation de Haar, une transformation en cosinus discrète est utilisée.) En modifiant le nombre de coefficients remis à zéro, vous pouvez ajuster le degré de compression !

Bien sûr, si vous mettez trop à zéro, la distorsion deviendra visible à l’œil nu. Tout a besoin de modération !

Après toutes ces actions, nous nous retrouverons avec une matrice contenant de nombreux zéros. Il peut être écrit ligne par ligne dans un fichier et compressé avec une sorte d'archiveur. Par exemple, le même 7Z. Le résultat sera bon.

Le décodage s'effectue dans l'ordre inverse : décompressez l'archive, appliquez la transformation de Haar inverse et écrivez l'image décodée dans un fichier. Voilà !

Où la transformation de Haar est-elle efficace ?

Quand la transformation Haar produira-t-elle les meilleurs résultats ? Évidemment, lorsque nous obtenons beaucoup de zéros, c'est-à-dire lorsque l'image contient de longues sections de mêmes valeurs de luminosité. Toutes les différences seront alors remises à zéro. Il peut s'agir par exemple d'une radiographie ou d'un document numérisé.

On dit que la transformation de Haar élimine la composante constante (c'est aussi le moment d'ordre zéro), c'est-à-dire qu'elle convertit les constantes en zéros.

Mais néanmoins, sur les photographies réelles, il n'y a pas tellement de zones avec la même luminosité. Essayons d'améliorer la transformation afin qu'elle réinitialise également la composante linéaire. Autrement dit, si les valeurs de luminosité augmentent linéairement, elles seront également réinitialisées.

Ce problème et d'autres plus complexes (élimination des moments d'ordres supérieurs) ont été résolus par Ingrid Daubechies, l'une des créatrices de la théorie des ondelettes.

Transformation Daubechies

Pour notre transformation améliorée, deux points ne suffiront pas. Nous prendrons donc quatre valeurs, décalées de deux à chaque fois.

Autrement dit, si la séquence initiale est 1, 2, 3, 4, 5, 6,…, N-1, N, alors nous prendrons les quatre (1, 2, 3, 4), (3, 4, 5 , 6) etc. Les quatre derniers « mordent la séquence par la queue » : (N-1, N, 1, 2).

De la même manière, essayons de construire deux filtres : haute fréquence et basse fréquence. Nous remplacerons chaque quatre par deux nombres. Puisque les quatre se chevauchent, le nombre de valeurs après la transformation ne changera pas.

Soit les valeurs de luminosité dans le quad égales à x, y, z, t. Ensuite on écrit le premier filtre sous la forme

Les quatre coefficients qui forment le vecteur ligne de la matrice de transformation nous sont encore inconnus.

Pour rendre le vecteur ligne des coefficients du deuxième filtre orthogonal au premier, prenez les mêmes coefficients mais réorganisez-les et changez les signes :

La matrice de transformation ressemblera à :

L'exigence d'orthogonalité est automatiquement satisfaite pour les première et deuxième lignes. Nous exigeons que les lignes 1 et 3 soient également orthogonales :

Les vecteurs doivent avoir une longueur unitaire (sinon le déterminant ne sera pas unitaire) :

La transformation doit réinitialiser une chaîne de valeurs identiques (par exemple, (1, 1, 1, 1)) :

La transformation doit réinitialiser une chaîne de valeurs croissantes linéairement (par exemple, (1, 2, 3, 4)) :

À propos, si ce quatre est réinitialisé à zéro, tous les autres croissants ou décroissants linéairement seront également réinitialisés. Vous pouvez facilement le vérifier en écrivant l’équation correspondante et en divisant tous les coefficients par le premier facteur.

Nous avons reçu 4 équations reliant les coefficients. En les résolvant, nous obtenons :

En les substituant dans la matrice, nous obtenons la transformation souhaitée. Après l'avoir appliqué aux photographies, nous obtiendrons plus de zéros et de petits coefficients, ce qui nous permettra de compresser davantage l'image.

Une autre fonctionnalité intéressante est que les artefacts après quantification ne seront pas aussi visibles.

Cette transformation est appelée ondelette D4 (le lecteur est invité à percer en toute autonomie le mystère de ce nom alphanumérique).

Autres ondelettes

Bien entendu, nous ne pouvons pas nous arrêter là et exiger l’élimination de la composante parabolique (moment du 2e ordre), etc. En conséquence, nous obtenons des ondelettes D6, D8 et autres.

Pour éviter de tout compter manuellement, vous pouvez rechercher les coefficients sur Wikipédia.

Daubechies a découvert une manière très intéressante d’obtenir les coefficients de ces transformations, mais hélas, cela dépasse le cadre de notre article.

Devoirs

Pour enfin comprendre les bases, je suggère d'écrire un programme dans votre langage préféré qui ouvre une image, effectue une transformation Haar (ou même D4), quantifie le résultat, puis enregistre le résultat dans un fichier. Essayez de compresser ce fichier avec votre archiveur préféré. Est-ce que ça compresse bien ?

Essayez la conversion inverse. Comment expliquez-vous la nature des artefacts présents dans l’image ?

Conclusion

Nous avons donc brièvement examiné les idées de base de la transformée en ondelettes discrète.

Bien entendu, cet article n’a pas abordé de nombreux détails mathématiques intéressants ni des applications pratiques des transformées en ondelettes. Mais on ne peut pas embrasser l’immensité. Et beaucoup de choses sont difficiles à expliquer sans élever le niveau de langage. J'espère que ce que j'ai écrit a été utile à quelqu'un.

Ajouter des balises

Transformation en ondelettes continue

Propriétés de la transformée en ondelettes

Exigences pour les ondelettes

Pour implémenter la transformée en ondelettes, les fonctions en ondelettes doivent satisfaire aux critères suivants :

1. L’ondelette doit avoir une énergie finie :

2. Si la transformée de Fourier pour, c'est-à-dire

alors la condition suivante doit être remplie :

Cette condition est appelée condition d'admissibilité, et il en résulte qu'une ondelette avec une composante de fréquence nulle doit satisfaire à la condition ou, dans un autre cas, l'ondelette doit avoir une moyenne égale à zéro.

3. Un critère supplémentaire est présenté pour les ondelettes complexes, à savoir que pour elles la transformée de Fourier doit être à la fois réelle et doit décroître pour les fréquences négatives.

4. Localisation : l'ondelette doit être continue, intégrable, avoir une porteuse compacte et être localisée à la fois en temps (dans l'espace) et en fréquence. Si une ondelette se rétrécit dans l'espace, sa fréquence moyenne augmente, le spectre de l'ondelette se déplace vers la région des fréquences plus élevées et s'étend. Ce processus doit être linéaire : le rétrécissement de l'ondelette de moitié devrait doubler sa fréquence moyenne et sa largeur spectrale.

1. Linéarité

2. Invariance de décalage

Un décalage temporel du signal de t0 entraîne également un décalage du spectre des ondelettes de t0.

3. Invariance d'échelle

L'étirement (compression) du signal entraîne une compression (étirement) du spectre d'ondelettes du signal.

4. Différenciation

La transformée en ondelettes pour un signal continu par rapport à une fonction ondelette est définie comme suit :

où signifie le conjugué complexe pour, le paramètre correspond au décalage temporel et est appelé paramètre de position, le paramètre spécifie la mise à l'échelle et est appelé paramètre d'étirement.

Fonction de poids.

Nous pouvons définir une fonction normalisée comme suit

ce qui signifie un décalage temporel de b et une mise à l'échelle temporelle de a. Ensuite, la formule de transformation de poids deviendra

Le signal d'origine peut être restauré à l'aide de la formule de transformation inverse

Dans le cas discret, les paramètres de mise à l'échelle a et shift b sont représentés par des valeurs discrètes :

L’ondelette d’analyse a alors la forme suivante :

où m et n sont des nombres entiers.

Dans ce cas, pour un signal continu, la transformée en ondelettes discrète et sa transformée inverse s'écriront par les formules suivantes :

Les quantités sont également appelées coefficients d'ondelettes.

il y a une normalisation constante.

La transformée en ondelettes est une transformation similaire à la transformée de Fourier (ou beaucoup plus à la transformée de Fourier fenêtrée) avec une fonction d'évaluation complètement différente. La principale différence réside dans la suivante : la transformée de Fourier décompose le signal en composantes sous forme de sinus et de cosinus, c'est-à-dire fonctions localisées dans l'espace de Fourier ; en revanche, la transformée en ondelettes utilise des fonctions localisées à la fois dans l'espace réel et dans l'espace de Fourier. En général, la transformée en ondelettes peut être exprimée par l'équation suivante :

où * est le symbole de la conjugaison complexe et la fonction ψ - une certaine fonction. La fonction peut être choisie arbitrairement, mais elle doit satisfaire à certaines règles.

Comme vous pouvez le constater, la transformée en ondelettes est en réalité un nombre infini de transformations différentes selon la fonction de notation utilisée pour la calculer. C'est la raison principale pour laquelle le terme « transformée en ondelettes» utilisé dans des situations très différentes et pour différentes applications. Il existe également de nombreux types de classification des variantes de transformée en ondelettes. Ici, nous montrerons uniquement la division basée sur l’orthogonalité des ondelettes. Peut être utilisé ondelettes orthogonales pour la transformée en ondelettes discrète et ondelettes non orthogonales pour continu. Ces deux types de transformation ont les propriétés suivantes :

1. La transformée en ondelettes discrète renvoie un vecteur de données de la même longueur que l'entrée. Généralement, même dans ce vecteur, la plupart des données sont presque nulles. Cela correspond au fait qu’il est décomposé en un ensemble d’ondelettes (fonctions) orthogonales à leur translation et mise à l’échelle parallèles. Par conséquent, nous décomposons un tel signal en un nombre identique ou inférieur de coefficients de spectre d’ondelettes au nombre de points de données du signal. Un tel spectre d'ondelettes est très adapté au traitement et à la compression du signal, par exemple, car nous ne recevons pas ici d'informations redondantes.
2. En revanche, la transformée en ondelettes continue renvoie un tableau d'une dimension plus grand que les données d'entrée. Pour les données unidimensionnelles, nous obtenons une image du plan temps-fréquence. Vous pouvez facilement suivre l’évolution des fréquences du signal sur sa durée et comparer ce spectre avec celui d’autres signaux. Parce qu'il utilise un ensemble d'ondelettes non orthogonales, les données sont fortement corrélées et présentent une redondance élevée. Cela permet de voir le résultat sous une forme plus proche de la perception humaine.

Des détails supplémentaires sur la transformation en ondelettes sont disponibles auprès de milliers de ressources en ondelettes en ligne, ou par exemple ici.

La bibliothèque de traitement de données Gwyddion implémente ces deux transformations et les modules utilisant la transformée en ondelettes sont disponibles dans le menu Informatique → Transformations intégrales.

Transformation en ondelettes discrète

La transformation en ondelettes discrète (DWT) est une implémentation d'une transformation en ondelettes utilisant un ensemble discret d'échelles et de traductions en ondelettes qui obéissent à certaines règles spécifiques. En d'autres termes, cette transformée décompose le signal en un ensemble d'ondelettes mutuellement orthogonales, ce qui constitue la principale différence avec la transformée en ondelettes continue (CWT), ou sa mise en œuvre pour des séries temporelles discrètes, parfois appelée transformée en ondelettes continue à temps discret (DT- CWT).

Une ondelette peut être construite à partir d'une fonction d'échelle qui décrit ses propriétés d'évolutivité. La limitation est que la fonction d'échelle doit être orthogonale à ses transformations discrètes, ce qui implique certaines restrictions mathématiques qui sont mentionnées partout, c'est-à-dire équation d'homothétie

Où S- facteur d'échelle (généralement choisi comme 2). De plus, l'aire sous la fonction doit être normalisée et la fonction de mise à l'échelle doit être orthogonale à ses traductions numériques, c'est-à-dire

Après avoir introduit quelques conditions supplémentaires (puisque les restrictions ci-dessus ne conduisent pas à une solution unique), nous pouvons obtenir le résultat de toutes ces équations, c'est-à-dire : ensemble fini de coefficients un k qui définissent la fonction de mise à l'échelle ainsi que l'ondelette. L'ondelette est obtenue à partir de la fonction de mise à l'échelle comme N Où N- un entier pair. L’ensemble des ondelettes forme alors une base orthonormée, que l’on utilise pour décomposer le signal. Il convient de noter qu'en général, seuls quelques coefficients un k sera non nul, ce qui simplifie les calculs.

La figure suivante montre quelques fonctions de mise à l'échelle et ondelettes. La famille d'ondelettes orthonormées la plus connue est la famille des Daubechies. Ses ondelettes sont généralement désignées par le nombre de coefficients non nuls un k, on parle donc généralement d'ondelettes de Daubechies 4, de Daubechies 6, etc. En gros, à mesure que le nombre de coefficients d’ondelettes augmente, les fonctions deviennent plus fluides. Ceci est clairement visible en comparant les ondelettes Daubechies 4 et 20 présentées ci-dessous. Une autre des ondelettes mentionnées est l'ondelette de Haar la plus simple, qui utilise une ondelette carrée comme fonction d'échelle.

Fonction de mise à l'échelle Haar et ondelette (à gauche) et leurs composantes de fréquence (à droite).

Fonction de mise à l'échelle et ondelette de Daubechies 4 (à gauche) et leurs composantes fréquentielles (à droite).

Fonction de mise à l'échelle et ondelette de Daubechies 20 (à gauche) et leurs composantes fréquentielles (à droite).

Il existe plusieurs types d'implémentation de l'algorithme de transformée en ondelettes discrète. Le plus ancien et le plus célèbre est l’algorithme Mull (pyramide). Dans cet algorithme, deux filtres - lissage et non lissage - sont composés de coefficients d'ondelettes et ces filtres sont appliqués de manière récurrente pour obtenir des données pour toutes les échelles disponibles. Si l’ensemble des données complet est utilisé D=2N et la longueur du signal est L, les données sont d'abord calculées J/2 pour l'échelle L /2N-1, puis les données ( J /2)/2 pour l'échelle L /2N-2, ... jusqu'à ce qu'à la fin vous obteniez 2 éléments de données pour l'échelle L/2. Le résultat de cet algorithme sera un tableau de la même longueur que l'entrée, où les données sont généralement triées de la plus grande échelle à la plus petite.

Gwyddion utilise un algorithme pyramidal pour calculer la transformée en ondelettes discrète. La transformation en ondelettes discrète en deux dimensions est disponible dans le module DWT.

La transformée en ondelettes discrète peut être utilisée pour éliminer rapidement et facilement le bruit d'un signal bruyant. Si l'on ne prend qu'un nombre limité des coefficients les plus élevés du spectre de la transformée en ondelettes discrète, et qu'on effectue la transformée en ondelettes inverse (avec la même base), on peut obtenir un signal plus ou moins débarrassé du bruit. Il existe plusieurs manières de sélectionner les coefficients que vous souhaitez enregistrer. Gwyddion implémente un seuil universel, un seuil adaptatif à l'échelle et un seuil adaptatif à l'échelle et à l'espace. Pour déterminer le seuil dans ces méthodes, nous définissons d'abord une estimation de la variance du bruit donnée par

Où Oui ij correspond à tous les coefficients de la sous-gamme la plus élevée de l’échelle de décomposition (où la majeure partie du bruit devrait être présente). Ou encore, la dispersion du bruit peut être obtenue de manière indépendante, par exemple comme la dispersion du signal AFM lorsque le balayage n'est pas en cours. Pour la sous-bande de fréquence la plus élevée (seuil universel), ou pour chaque sous-bande (pour le seuil adaptatif d'échelle), ou pour l'environnement de chaque pixel de la sous-bande (pour le seuil adaptatif d'échelle et d'espace), la variance est calculée comme suit :

La valeur seuil est calculée sous sa forme finale comme

Lorsque le seuil pour une échelle donnée est connu, on peut supprimer tous les coefficients inférieurs à la valeur seuil (seuil dur) ou on peut réduire la valeur absolue de ces coefficients de la valeur seuil (seuil souple).

La suppression du bruit DWT est disponible dans le menu Informatique → Transformations intégrales→ Suppression du bruit DWT.

Transformation en ondelettes continue

Transformation en ondelettes continue (CWT) - Une implémentation de la transformée en ondelettes utilisant des échelles arbitraires et des ondelettes essentiellement arbitraires. Les ondelettes utilisées ne sont pas orthogonales et les données obtenues lors de cette transformation sont fortement corrélées. Pour des séquences temporelles discrètes, cette transformée peut également être utilisée, avec la contrainte que les plus petites traductions d'ondelettes doivent être égales à l'échantillonnage des données. Ceci est parfois appelé transformation en ondelettes continue en temps discret (DT-CWT) et constitue la méthode la plus couramment utilisée pour calculer la CWT dans les applications du monde réel.

En principe, la transformée en ondelettes continue fonctionne en utilisant la définition directe de la transformée en ondelettes, c'est-à-dire nous calculons la convolution du signal avec une ondelette mise à l'échelle. Pour chaque échelle on obtient ainsi un ensemble de même longueur N, identique au signal d'entrée. En utilisant M.échelles arbitrairement choisies, nous obtenons un champ N×M, qui représente directement le plan temps-fréquence. L'algorithme utilisé pour ce calcul peut être basé sur la convolution directe ou la convolution par multiplication dans l'espace de Fourier (parfois appelée transformée en ondelettes rapide).

Le choix de l’ondelette à utiliser dans la décomposition temps-fréquence est la chose la plus importante. Avec ce choix, nous pouvons influencer la résolution du résultat en temps et en fréquence. Nous ne pouvons pas modifier les caractéristiques de base de la transformée en ondelettes de cette manière (les basses fréquences ont une bonne résolution en fréquence et une mauvaise résolution temporelle ; les hautes fréquences ont une mauvaise résolution en fréquence et une bonne résolution en fréquence). résolution temporelle), mais nous pouvons augmenter légèrement la fréquence globale ou la résolution temporelle. Ceci est directement proportionnel à la largeur de l'ondelette utilisée dans l'espace réel et de Fourier. Si, par exemple, nous utilisons une ondelette de Morlet (la partie réelle est une fonction cosinus amortie), alors nous pouvons nous attendre à une résolution haute fréquence, puisqu'une telle ondelette est très bien localisée en fréquence. au contraire, en utilisant l'ondelette Dérivée de Gauss (DOG), nous obtenons une bonne localisation dans le temps, mais une mauvaise localisation en fréquence.

La transformation en ondelettes continue est implémentée dans le module CWT, disponible dans le menu Informatique → Transformations intégrales→ CWT.

Sources

A. Bultheel : Bull. Belge. Mathématiques. Soc.: (1995) 2

SG Chang, B. Yu, M. Vetterli : IEEE Trans. Traitement d'images, (2000) 9 p. 1532

SG Chang, B. Yu, M. Vetterli : IEEE Trans. Traitement d'images, (2000) 9 p. 1522

Ondelettes(de l'anglais ondelette), éclate sont des fonctions mathématiques qui vous permettent d'analyser diverses composantes fréquentielles des données. Les coefficients d'ondelettes sont déterminés par la transformation intégrale du signal. Les spectrogrammes d'ondelettes résultants sont fondamentalement différents des spectres de Fourier conventionnels dans le sens où ils fournissent une référence claire du spectre de diverses caractéristiques du signal dans le temps.

Pour traiter les signaux discrets, la transformée en ondelettes discrète (DWT) est utilisée.

Le premier DVP a été proposé par le mathématicien hongrois Alfred Haar. Pour un signal d'entrée représenté par un tableau de 2 n nombres, la transformée en ondelettes de Haar regroupe simplement les éléments par 2 et en forme des sommes et des différences. Le regroupement des sommes s'effectue de manière récursive pour former le niveau de décomposition suivant. Le résultat est 2 n −1 différence et 1 somme totale. Nous commencerons par un tableau de données unidimensionnel composé de Néléments. En principe, ces éléments pourraient être des pixels d’image adjacents ou des fragments sonores successifs. Un exemple serait un tableau de nombres (2,9,12,10,9,8, 8,7). Tout d'abord, calculons les quatre valeurs moyennes (Fig. 40)

Il est clair que la connaissance de ces quatre demi-sommes ne suffit pas à restituer l'ensemble du tableau, nous allons donc également calculer quatre demi-différences

(2 - 9)/2 = - 4,5,

(12 - 10)/2 = 1,

(9 – 8)/2 = 0,5,

(8 – 7)/2 = 0,5,

que nous appellerons coefficients de détail. Les nombres moyens peuvent être considérés comme une résolution à grande échelle de l'image originale, et des détails sont nécessaires pour reconstruire les détails fins ou les corrections. Si les données source sont corrélées, la résolution à grande échelle répétera l'image originale et les détails seront petits.

Un tableau composé de quatre demi-sommes et de quatre demi-différences peut être utilisé pour reconstruire le tableau original de nombres. Le nouveau tableau comporte également huit nombres, mais ses quatre derniers composants, les demi-différences, ont tendance à devenir plus petits, ce qui est bon pour la compression.

Répétons notre procédure pour les quatre premiers (grands) composants de notre nouveau tableau. Elles sont converties en deux moyennes et deux demi-différences. Nous laisserons les quatre composants restants inchangés. La prochaine et dernière itération de notre processus convertit les deux premiers composants de ce tableau en une moyenne (qui est en fait égale à la moyenne des 8 éléments du tableau d'origine) et une demi-différence.

Graphique 3.18. Illustration du fonctionnement d'une transformée en ondelettes unidimensionnelle.

En conséquence, nous obtenons un tableau de nombres appelé transformée de Haar en ondelettes tableau de données d'origine.

La transformée en ondelettes de Haar unidimensionnelle est facilement transférée au cas bidimensionnel. La décomposition standard (Fig. 3.19) commence par calculer les transformées en ondelettes de toutes les lignes de l'image. Toutes les itérations du processus sont appliquées à chaque ligne jusqu'à ce que l'élément le plus à gauche de chaque ligne soit égal à la moyenne des nombres de cette ligne et que tous les autres éléments soient égaux aux différences pondérées. Le résultat est une image dont la première colonne contient la moyenne des colonnes de l'image d'origine. Après cela, l’algorithme standard effectue une transformation en ondelettes sur chaque colonne. Le résultat est un tableau bidimensionnel dans lequel l'élément du coin supérieur gauche est égal à la moyenne de l'ensemble du tableau d'origine. Les éléments restants de la rangée supérieure seront égaux aux différences moyennes pondérées, les différences moyennes se trouvent en dessous et tous les autres pixels sont convertis en différences correspondantes.

La décomposition pyramidale calcule la transformée en ondelettes en appliquant alternativement des itérations aux lignes et aux colonnes. Dans la première étape, les demi-sommes et les demi-différences sont calculées pour toutes les lignes (une seule itération, pas la transformation en ondelettes entière). Cette action produit des moyennes dans la moitié gauche de la matrice et des demi-différences dans la moitié droite. Lors de la deuxième étape, les demi-sommes et demi-différences sont calculées pour toutes les colonnes de la matrice résultante.

Graphique 3.19. Transformation en ondelettes bidimensionnelle standard

Graphique 3.20. Transformation en ondelettes 2D pyramidale

Le résultat de la transformée en ondelettes bidimensionnelle est un ensemble de matrices correspondant à diverses composantes spectrales de l'image originale. Dans ce cas, dans le coin supérieur gauche se trouve une composante basse fréquence LL4 (Fig. 3.21), qui a été créée uniquement sur la base de demi-sommes et est une copie réduite de l'image originale.

Graphique 3.21. Composants de la transformée en ondelettes bidimensionnelle

Les composants restants de la transformation peuvent être utilisés pour restaurer l'image d'origine. Dans le même temps, les composants haute fréquence se prêtent bien à la compression à l'aide des algorithmes RLE et Huffman. Il convient également de noter que lors d'une compression avec perte d'informations, il est également possible d'utiliser la quantification, ainsi que la suppression directe d'une partie des composants. Le résultat de telles opérations est un bon taux de compression. Sur la fig. La figure 3.22 montre un exemple de codage d'image utilisant la transformée en ondelettes.

Il convient de noter que la transformée en ondelettes bidimensionnelle nécessite des ressources de calcul importantes lorsqu'elle est mise en œuvre à l'aide de méthodes logicielles conventionnelles. Cependant, l'algorithme de transformation en ondelettes consiste en un grand nombre de transformations simples qui se prêtent bien à la parallélisation. En conséquence, cette conversion est bien réalisée en matériel utilisant du matériel spécialisé.

Graphique 3.22. Un exemple de transformation en ondelettes d'une image.

La transformée en ondelettes est utilisée dans la norme de compression d'image JPEG2000 et est également fournie comme outil au format MPEG-4.