Quelles propriétés rendent certaines ondelettes «meilleures» que d'autres en compression d'image?

J'essaie d'en apprendre davantage sur la compression d'image à l'aide de la méthode de transformation en ondelettes. Ma question est la suivante: en quoi certaines ondelettes les rendent-elles préférables lors de la compression d'images? Sont-ils plus faciles à calculer? Produisent-ils des images plus lisses? Etc...

Exemple: JPEG 2000 utilise l' ondelette 9/7 de Cohen-Daubechies-Feauveau ... pourquoi celui-ci?

Vue d'ensemble

La réponse courte est qu'ils ont le nombre maximum de vanishing momentspour une donnée support(c'est-à-dire le nombre de coefficients de filtre). C'est la propriété "extremal" qui distingue les ondelettes de Daubechies en général. En gros, plus le nombre de moments disparus est élevé, plus la compression est bonne et moins le calcul est synonyme de support. En fait, le compromis entre les moments nuls et la taille du filtre est si important qu’il domine la façon dont les ondelettes sont nommées. Par exemple, vous verrez souvent l' D4ondelette appelée soit D4ou db2. Le 4fait référence au nombre de coefficients, et le2fait référence au nombre de moments disparus. Les deux font référence au même objet mathématique. Ci-dessous, je vais expliquer plus en détail ce que sont les moments (et pourquoi nous voulons les faire disparaître), mais pour l’instant, comprenez simplement que cela se rapporte au fait que nous pouvons "replier" la plupart des informations contenues dans le signal en un signal plus petit. nombre de valeurs. La compression avec perte est obtenue en gardant ces valeurs et en jetant les autres.

Maintenant, vous avez peut-être remarqué que CDF 9/7, qui est utilisé dans JPEG 2000, a deux chiffres dans le nom, plutôt qu'un. En fait, il est également appelé bior 4.4. C'est parce que ce n'est pas du tout une ondelette "standard". En fait, techniquement, il ne conserve même pas l'énergie contenue dans le signal, et cette propriété est la raison principale pour laquelle les gens ont été si enthousiasmés par le DWT! Les nombres 9/7et 4.4font toujours référence aux supports et aux moments d’annulation, respectivement, mais il existe maintenant deux ensembles de coefficients qui définissent l’ondelette. Le terme technique est que plutôt que d'être orthogonal, ils sont biorthogonal. Plutôt que de plonger trop profondément dans ce que cela signifie mathématiquement, je

JPEG 2000

Vous trouverez une analyse beaucoup plus détaillée des décisions de conception relatives à l’ondelette CDF 9/7 dans le document suivant:

Usevitch, Bryan E. Tutoriel sur la compression d’images en ondelettes avec pertes modernes: Fondements de JPEG 2000 .

Je vais juste passer en revue les points principaux ici.

1. Assez souvent, les ondelettes orthogonales de Daubechies peuvent en réalité augmenter le nombre de valeurs requises pour représenter le signal. L'effet s'appelle coefficient expansion. Si nous effectuons une compression avec perte, cela peut ou non avoir de l'importance (puisque nous jetons quand même des valeurs à la fin), mais cela semble définitivement contre-productif dans le contexte de la compression. Une façon de résoudre le problème consiste à traiter le signal d'entrée comme périodique.

2. Le simple fait de traiter l'entrée de manière périodique entraîne des discontinuités aux arêtes, plus difficiles à compresser, et ne sont que des artefacts de la transformation. Par exemple, considérons les sauts de 3 à 0 dans l'extension périodique suivante: . Pour résoudre ce problème, nous pouvons utiliser une extension périodique symétrique du signal, comme suit: . L’élimination des sauts sur les bords est l’une des raisons pour lesquelles la transformation en cosinus discrète (DCT) est utilisée à la place de la TFD en JPEG. La représentation d'un signal avec des cosinus suppose implicitement que le signal d'entrée est "bouclé de l'avant à l'arrière". Nous voulons donc des ondelettes ayant la même propriété de symétrie.$[0,1,2,3] \rightarrow [...0,1,2,3,0,1,2,3,...]$$[0,1,2,3] \rightarrow [...,0,1,2,3,3,2,1,0,0,1...]$

3. Malheureusement, la seule ondelette orthogonale qui possède les caractéristiques requises est l’ondelette de Haar (ou D2, db1), qui ne représente qu’un moment d’évanouissement. Pouah. Cela nous conduit aux ondelettes biorthogonales, qui sont en fait des représentations redondantes et ne préservent donc pas l'énergie. La raison pour laquelle les ondelettes CDF 9/7 sont utilisées dans la pratique est qu’elles ont été conçues pour être sur le point de préserver l’énergie. Ils ont également bien testé la pratique.

Il existe d'autres moyens de résoudre les divers problèmes (mentionnés brièvement dans le document), mais ce sont les grandes lignes des facteurs en cause.

Moments de disparition

Alors, quels sont les moments, et pourquoi nous nous soucions d'eux? Les signaux lisses peuvent être bien approximés par des polynômes, c'est-à-dire des fonctions de la forme:

Les moments d'une fonction (c'est-à-dire d'un signal) mesurent sa similarité avec une puissance donnée de x. Mathématiquement, cela s'exprime comme un produit intérieur entre la fonction et la puissance de x. Un moment de fuite signifie que le produit intérieur est égal à zéro et que la fonction ne "ressemble" donc pas à la puissance de x, comme suit (pour le cas continu):

Désormais, chaque ondelette orthogonale discrète est associée à deux filtres FIR , qui sont utilisés dans le DWT . L’un est un filtre passe-bas (ou d’échelle) , et l’autre est un filtre passe-haut (ou en ondelettes)$\phi$$\psi$. Cette terminologie semble varier quelque peu, mais c'est ce que je vais utiliser ici. À chaque étape du DWT, le filtre passe-haut est utilisé pour "décoller" une couche de détails, et le filtre passe-bas fournit une version lissée du signal sans ce détail. Si le filtre passe-haut a des moments nuls, ceux-ci (c'est-à-dire les entités polynomiales d'ordre faible) se verrouillent dans le signal lissé complémentaire plutôt que dans le signal de détail. En cas de compression avec perte, nous espérons que le signal de détail ne contiendra pas beaucoup d’informations et que nous pourrons donc en éliminer la plus grande partie.

Voici un exemple simple utilisant l'ondelette Haar (D2). Un facteur d'échelle de impliqué, mais je l'omets ici pour illustrer le concept. Les deux filtres sont les suivants: $1/\sqrt{2}$

Le filtre passe-haut disparaît pour le zéroième moment, c'est-à-dire , il n'a donc qu'un moment. Pour voir cela, considérons ce signal constant: . Maintenant, intuitivement, il devrait être évident qu'il n'y a pas beaucoup d'informations là-bas (ou dans un signal constant). Nous pourrions décrire la même chose en disant "quatre deux". Le DWT nous donne un moyen de décrire cette intuition de manière explicite. Voici ce qui se passe lors d'un seul passage du DWT utilisant l'ondelette de Haar:$x^0 = 1$$[2,2,2,2]$

Et que se passe-t-il lors du second passage, qui opère uniquement sur le signal lissé:

Remarquez comment le signal constant est complètement invisible pour les détails (qui sont tous égaux à 0). Notez également comment quatre valeurs de ont été réduites à une seule valeur de . Maintenant, si nous voulions transmettre le signal original, nous pourrions simplement envoyer le et le DWT inverse pourrait reconstruire le signal original en supposant que tous les coefficients de détail sont nuls. Les ondelettes avec des moments de fuite d'ordre supérieur permettent des résultats similaires avec des signaux bien approximés par des lignes, des paraboles, des cubiques, etc.8 $2$$8$$8$

Lectures complémentaires

Je passe en revue beaucoup de détails pour que le traitement ci-dessus reste accessible. Le document suivant a une analyse beaucoup plus approfondie:

M. Unser et T. Blu, Propriétés mathématiques des filtres d’ondelettes JPEG2000 , IEEE Trans. Image Proc., Vol. 12, non. 9 septembre 2003, pages 1080-1090.

note de bas de page

L'article ci-dessus semble suggérer que l'ondelette JPEG2000 s'appelle Daubechies 9/7 et est différente de l'ondelette CDF 9/7.

Nous avons dérivé la forme exacte des filtres d’échelle JPEG2000 Daubechies 9/7 ... Ces filtres résultent de la factorisation du même polynôme que [10]. La principale différence est que les filtres 9/7 sont symétriques. De plus, contrairement aux splines biorthogonales de Cohen-Daubechies-Feauveau [11], la partie non régulière du polynôme a été divisée de la manière la plus uniforme possible.$Daubechies_{8}$

[11] A. Cohen, I. Daubechies et JC Feauveau, «Bases biorthogonales d'ondelettes à support compact», Comm. Pure Appl. Math., Vol. 45, non. 5, pages 485 à 560, 1992.

La version préliminaire de la norme JPEG2000 ( lien pdf ) que j'ai consultée appelle également le filtre officiel Daubechies 9/7. Il fait référence à cet article:

M. Antonini, M. Barlaud, P. Mathieu et I. Daubechies, «Codage d’images en utilisant la transformation en ondelettes», IEEE Trans. Image Proc. 1, pages 205-220, avril 1992.

Je n'ai lu aucune de ces sources et je ne peux donc pas dire avec certitude pourquoi Wikipedia appelle le fichier JPEG2 CDF 9/2 de JPEG2000. Il semble qu'il y ait peut-être une différence entre les deux, mais les gens appellent quand même le fichier JPEG2 CDF 9/7 officiel de JPEG2000 (car il repose sur les mêmes bases?). Quel que soit le nom, le papier de Usevitch décrit celui utilisé dans la norme.

La qualité des transformations de signal est évaluée sur deux métriques différentes: la compression et, dans le cas d'une compression avec pertes, la qualité. La compression est définie par le compactage énergétique mais la qualité est plus difficile.

Traditionnellement, la qualité était mesurée par l'erreur quadratique moyenne ou le rapport signal sur bruit moyen par pixel. Cependant, les humains n’ont pas tendance à évaluer les signaux avec MSE ou SNR. Les humains sont très sensibles au bruit structuré là où les MSE ont tendance à ne pas être. Le développement d'algorithmes fournissant des mesures de qualité similaires à celles d'un humain est un domaine de recherche actif. L’index de structure SIMILarity (SSIM) de Bovik est un bon point de départ.

En guise de réponse très courte, toute transformation est meilleure que toute autre transformation, ce que l’on appelle la "propriété de compactage énergétique", qui est expliquée ci-dessous:

"Lorsque seulement une petite fraction des coefficients de transformation ont une grande amplitude, le fait de ne garder que quelques coefficients d'efficacité et de rejeter ou de quantifier les autres permet encore une reconstruction proche de la perfection". Cette propriété est liée à la capacité de décorrélation des transformées unitaires. "

La propriété de transformation avec moins d'énergie de compactage est celle qui nécessitera le plus petit nombre de symboles et, par conséquent, moins de bits.

La transformée avec la propriété de compactage d'énergie la plus élevée est DCT.

Dipan.

Les images naturelles sont constituées de différentes caractéristiques. Nous pouvons les catégoriser de manière générale en caractéristiques, textures et bords lisses ou lents à varier. Une bonne méthode de compression est celle qui transforme une image en un domaine dans lequel toute l’énergie d’un signal est conservée avec seulement quelques coefficients.

La transformée de Fourier tente d'approcher une image à l'aide de sinus et de cosinus. Les sinus et les cosinus peuvent maintenant se rapprocher des signaux lissés de manière assez concise, mais sont notoirement mauvais pour approximer les discontinuités. Si vous connaissez le phénomène Gibbs, vous saurez qu'il faut un grand nombre de coefficients de Fourier pour éviter les artefacts de l'approximation d'une discontinuité dans le temps. Cependant, plus le nombre de coefficients est petit, meilleure est la compression. Par conséquent, il existe un compromis inhérent entre le nombre de coefficients et le facteur de perte de la méthode de compression, que nous appelons généralement le compromis distorsion des taux.

Lorsque vous recherchez un meilleur schéma de compression que jpeg, qui utilise des transformations de Fourier, nous aurions besoin d'une transformation pouvant s'approcher des discontinuités avec moins de coefficients que la transformation de Fourier, pour la même distorsion. Entrez des ondelettes qui offrent une meilleure approximation et donc une meilleure compression des singularités ponctuelles sans le phénomène de gibbs comme des artefacts. Les images ne sont jamais purement lisses dans la pratique et les ondelettes sont donc plus polyvalentes que fourier pour diverses caractéristiques d'image. Si nous devions comparer la meilleure approximation k-term d'une image contenant des arêtes à la fois en quadrilatère et en ondelettes, les erreurs se désintégreraient sous la forme et k - $k^{-2/3}$$k^{-1}$, respectivement. Pour le même nombre de termes, l'erreur décroît plus rapidement pour les ondelettes. Cela signifie que les ondelettes ont un meilleur compactage énergétique lorsque les images ne sont pas parfaitement lisses (variant lentement) et contiennent des singularités.

Cependant, nous n’avons pas encore de base ou de transformation unique pouvant s'approcher des traits lisses, des singularités de point, des arêtes et des textures.

La DCT a une très bonne compaction d’énergie pour de nombreux signaux communs et elle est également assez en rapport avec le fonctionnement de la diffraction (le processus physique sous-jacent en imagerie), dans la mesure où la diffraction peut être représentée sous la forme d’un noyau à quatre branches. Ceux-ci lui donnent beaucoup d'avantages.

Le problème est que les coefficients DCT sont nécessairement délocalisés sur toute la zone de transformation. Cela nécessite la création de nombreuses petites zones de transformation (blocs) afin que l’énergie d’une zone ne se répande pas dans une autre lors de la transformation. Cela limite à la fois la capacité de la transformation à compacter de l’énergie et introduit également des artefacts aux limites des nombreux blocs.

Je n'ai pas beaucoup utilisé les ondelettes, je peux donc me tromper, mais elles sont plus délocalisées, avec des coefficients différents représentant des compromis zone / fréquence différents. Cela permet des blocs plus grands avec moins d'artefacts. Pas sûr dans la pratique, quelle différence cela fait vraiment.

Lorsqu'on parle de meilleures ondelettes, il faut considérer qu'elles ont le même encodeur à l'arrière: les performances d'une transformation sont fortement liées à la quantification et à l'encodage. Les performances sont généralement les suivantes: meilleure compression pour la même qualité ou meilleure qualité pour la même compression. La compression est une mesure facile, pas la qualité. Mais supposons que nous en ayons un.

Maintenant, une ondelette (avec encodeur) peut être meilleure à un taux de compression (disons bas), et pire à un autre (disons haut). Seulement un peu en général, mais selon que vous compressiez haut ( ) ou faible ( ), vous pouvez choisir différentes ondelettes.× $\times 124$$\times 4$

Enfin, cela dépend de la classe d'images que vous souhaitez compresser: tout usage, ou ciblé, comme pour les images médicales, ou la compression de données sismiques, avec un type de données restreint et spécifique? Là encore, les ondelettes peuvent être différentes.

Maintenant, quelles sont les principales composantes morphologiques des images et comment les ondelettes les traitent-elles:

• tendances lentes, arrière-plans en évolution: les moments de disparition, qui éliminent les polynômes dans les sous-bandes d'ondelettes,
• bosses: ok avec les fonctions de mise à l'échelle,
• bords: attrapés par l'aspect dérivé des ondelettes,
• textures: oscillations capturées par l’aspect ondulé des ondelettes,
• le reste, ce qui est bruyant, non modélisé: géré par orthogonalité (ou proche aussi).

Ainsi, du point de vue de l'analyse, les meilleures ondelettes permettent de compacter globalement les caractéristiques ci-dessus. Du côté de la synthèse, les meilleures ondelettes atténuent les effets de compression, par exemple la quantification, pour donner un aspect agréable. Les propriétés requises lors de l'analyse / synthèse sont un peu différentes, c'est pourquoi les ondelettes biorthogonales sont agréables: vous pouvez séparer les propriétés d'analyse (moments nuls) / de synthèse (lissage), ce que vous ne pouvez pas faire avec des orthogonales, et provoquer une augmentation de la longueur du filtre , assez préjudiciable à la performance informatique. Des ondelettes supplémentaires biorthogonales peuvent être symétriques, bonnes pour les bords.

Enfin, souhaitez-vous une compression sans perte? Ensuite, vous avez besoin d’ondelettes (ou binlets) de type "entier".

Et tout ce qui précède est mélangé à des problèmes de calcul: ondelettes séparables, pas trop longues. Et le processus de normalisation au sein du comité JPEG.

Enfin, le 5/3 est assez bon pour sans perte, assez court. Certains des 9/7 sont bons aussi. Beaucoup mieux qu'une ondelette 13/7 ? Pas vraiment, et même si, dans le PSNR, ce n’est pas le meilleur pour la qualité d’image.

Ainsi, les meilleures ondelettes sont à portée de main, pour les images traditionnelles et les communications personnelles avec les auteurs de

M. Unser et T. Blu, Propriétés mathématiques des filtres d’ondelettes JPEG2000 , IEEE Trans. Image Proc., Vol. 12, non. 9 septembre 2003, pages 1080-1090.

faites-moi croire que le "meilleur" aspect du 9/7 n'est ni complètement expliqué, ni assuré.

Parce que vous pouvez gagner sensiblement plus avec d’autres banques de filtres (multi-bandes ou bande- ). Peut-être pas assez pour justifier une nouvelle norme.$M$