Ondelettes dyadiques et nouvelles représentations multirésolution

Introduction aux représentations multirésolution

Sur la scalabilité Le terme scalabilité est un néologisme directement emprunté de l’anglais scalability qui peut approximativement être traduit par le terme échelonnabilité. La scalabilité est la Ondelettes dyadiques et nouvelles représentations multirésolution  caractéristique d’un objet ou d’un signal à être représentable sur plusieurs niveaux de résolution ou de qualité. Une transformation sera ainsi dite scalable si elle est en mesure de représenter un signal sur plusieurs niveaux de résolution ou de qualité. La notion de scalabilité est en fait très générale et il existe plusieurs types de scalabilité. Dans le cas d’un signal monodimensionnel, on parlera de scalabilité en résolution pour désigner le fait qu’un signal puisse être décrit par un nombre variable d’échantillons. Dans le cas d’une image, la scalabilité spatiale qualifie la propriété de pouvoir représenter une image sur plusieurs niveaux de résolution spatiale, comme illustré en Fig. 1.1. 1/4 1/2 1/1 FIG. 1.1 – Scalabilité spatiale. Exemples de facteurs de résolution dyadiques obtenus avec le codec scalable JPEG-2000. Il est aussi possible de représenter un signal sur différents niveaux de qualité, où chaque échantillon ou coefficient peut être décrit avec une précision plus ou moins grande. On parlera dans ce cas de scalabilité en qualité. La Fig. 1.2 montre un exemple de scalabilité en qualité où chaque point de l’image est décrit avec plus ou moins de précision en fonction du débit qui lui est accordé. d = 0.04 bpp d = 0.1 bpp d = 0.2 bpp FIG. 1.2 – Scalabilité en qualité. Exemples de différentes qualités obtenues avec le codec JPEG-2000 lors du décodage à différents débits, exprimés en bits par pixel. Il existe d’autres types de scalabilité : dans le cas d’une séquence vidéo, on parlera de scalabilité temporelle pour désigner la propriété de pouvoir la représenter à plusieurs fréquences temporelles, exprimées en nombre d’images par seconde. D’autres types de scalabilité peuvent être définis comme la scalabilité en complexité, en objets ou en délai mais nous ne les aborderons pas dans ce document.  Motivation et cas d’utilisation Avec l’explosion des applications multimédia et le besoin croissant de diffusion de contenu à destination de récepteurs hétérogènes, la scalabilité est devenue indispensable dans la conception d’un schéma de compression d’image ou de codage vidéo. Cette propriété permet ainsi de pouvoir diffuser un unique flux vidéo compressé, capable d’être adapté par les nœuds d’un réseau ou d’être décodé par une grande variété de récepteurs. Il existe de nombreux cas d’utilisation nécessitant une description scalable et parcimonieuse d’un contenu multimédia, relevant pour la plupart du domaine de l’adaptation de contenu. Par exemple, les images présentes sur Internet sont souvent disponibles sous deux voire trois résolutions (aperçu thumbnail, résolution moyenne et haute résolution) en fonction de la façon dont elles sont visualisées. De plus, il est souvent nécessaire de posséder un morceau de musique compressé sous plusieurs débits, en fonction de la qualité désirée et de la place disponible. Enfin, les opérateurs commerciaux de diffusion de contenus multimédia ont tout intérêt à utiliser un format scalable. Un opérateur de téléphonie mobile pourra ainsi diffuser un flux vidéo TV destiné à un parc hétérogène de récepteurs dont les écrans sont de tailles différentes. De plus, la scalabilité est une propriété très utile lors de la diffusion de contenu multimédia dans un environnement enclin aux erreurs de transmissions, comme les réseaux IP sans fil. En effet, elle permet l’adaptation du débit du flux compressé en fonction de la capacité du canal, susceptible de varier selon les conditions de transmission, et augmente la robustesse d’un schéma de codage en cas de pertes, d’erreurs ou d’encombrements. Ces nombreux cas d’utilisation poussent depuis quelques années les organismes internationaux de normalisation ITU, JPEG et MPEG à concevoir des algorithmes de compression d’images et de codage vidéo scalables. La norme de compression d’images fixes JPEG-2000, scalable en résolution et en qualité a ainsi été normalisée en 2000. Le futur algorithme de codage vidéo scalable SVC décrit dans la section 2.1.4, est quant à lui en cours de normalisation. On trouvera dans l’appel à proposition [6] qui a précédé sa création, les nombreuses motivations industrielles et cas d’utilisation auxquels il répond. Techniques classiques de description scalable Comment créer une représentation scalable d’un signal ? On peut tout d’abord penser naïvement à une solution de type Simulcast. C’est une stratégie brutale qui consiste simplement à proposer simultanément plusieurs versions du même contenu multimédia. C’est en effet une forme de description scalable mais qui est loin d’être parcimonieuse. Une autre classe de solutions existe : les schémas de codage prédictif en couches. Dans ce type de stratégie, chaque version du contenu multimédia constitue une couche et un mécanisme existe pour permettre la prédiction d’une couche à partir d’une autre, réduisant ainsi la redondance comparée à une stratégie Simulcast. Un exemple simple de schéma de codage prédictif en couches peut être imaginé par un format de musique compressé, où chaque couche représente une qualité différente, obtenue par différence avec la couche de qualité inférieure. Cependant, l’efficacité de ce type de représentation repose principalement sur l’opérateur de prédiction utilisé entre couches et est susceptible de chuter si le nombre de couches est trop important. Enfin, la scalabilité offerte par les schémas en couches est grossière et statique : seules les couches disponibles peuvent fournir une version du contenu compressé et ces dernières doivent être connues au moment de l’encodage.

 Ondelettes dyadiques

L’analyse multirésolution par ondelettes d’un signal, d’une image ou plus généralement d’une fonction f ∈ L 2 (IRN ) consiste en sa projection sur des bases de fonctions, donnant des approximations de moins en moins fines de la fonction originale. Nous rappelons tout d’abord dans cette section le concept d’analyse multirésolution par ondelettes et voyons ensuite comment un algorithme de transformée rapide en ondelettes peut être mis en œuvre sous forme de banc de filtres. Après avoir établi un panorama d’ondelettes classiquement utilisées en compression d’image, nous décrivons alors plusieurs algorithmes de codage de coefficients d’ondelettes utilisés dans ce domaine. 

Bases d’ondelettes Analyse multirésolution

La construction d’espaces multirésolution aptes à représenter plus ou moins grossièrement une fonction f ∈ L 2 (IR) a été proposée par Mallat et Meyer [79, 80, 89] pour fournir un cadre formel permettant l’analyse d’une fonction f sur plusieurs niveaux de résolution. On définit une approximation multirésolution comme une suite de sous-espaces vectoriels fermés {Vj}j∈Z de L 2 (IR) emboîtés selon la relation : ∅ ⊂ . . . ⊂ V2 ⊂ V1 ⊂ V0 ⊂ V−1 . . . ⊂ L 2 (IR) (1.1) La projection d’une fonction f ∈ L 2 (IR) sur un espace Vj représente alors une approximation de f au niveau de résolution j. Du fait de l’emboîtement des espaces {Vj}, l’approximation de niveau j sera nécessairement plus précise que celle du niveau j + 1 car l’espace Vj dispose de plus de fonctions que l’espace Vj+1 pour représenter f. On suppose alors l’existence d’une fonction φ ∈ L 2 (IR), appelée fonction d’échelle ou ondelette père telle que ses translatées {t 7→ φ(t−k)}k∈Z forment une base orthonormale de V0. On affirme enfin que les fonctions de Vj+1 sont obtenues par dilatation d’un facteur 2 des fonctions de Vj selon la relation : ∀ j ∈ Z, t 7→ f(t) ∈ Vj ⇔ t 7→ f ³ t 2 ´ ∈ Vj+1 (1.2) permettant ainsi de caractériser intuitivement les propriétés de l’analyse multirésolution et de supputer que l’approximation de f sur Vj+1 est deux fois plus grossière que celle sur Vj . On peut alors introduire la notion d’échelle et définir la projection de f sur Vj comme l’approximation de f à l’échelle 2 j , où j est le niveau de résolution. L’utilisation de la relation de dilatation (1.2) nous permet alors d’affirmer que les fonctions {φj,k}k∈Z obtenues par dilatations et translations de φ et définies par : φj,k = t 7→ 1 2 j/2 φ ³ t 2 j − k ´ , k ∈ Z (1.3) forment une base orthonormale de Vj . 19 Bases d’ondelettes orthogonales La relation d’emboîtement implique que les projections de f sur Vj sont de plus en plus grossières, au fur et à mesure que j croît. La différence entre l’approximation sur Vj et celle sur Vj+1 représente ainsi l’information de détail perdue par incrémentation du niveau de résolution j. Il est cependant possible de définir l’espace de détail Wj+1 contenant les fonctions nécessaires à représenter cette information perdue, en utilisant l’opérateur de sommation directe ⊕ de sous-espaces vectoriels : Vj = Vj+1 ⊕ Wj+1 (1.4) On peut alors montrer l’existence d’une fonction ψ appelée ondelette mère telle que ses translatées {t 7→ ψ(t − k)}k ∈ Z forment une base orthonormale de W0. On montre de même que les fonctions {ψj,k}k ∈ Z définies par : ψj,k = t 7→ 1 2 j/2 ψ ³ t 2 j − k ´ , k ∈ Z (1.5) forment une base orthonormale de Wj . Enfin, en exploitant les conditions limites de l’analyse multirésolution, on conclut que l’ensemble des fonctions {ψj,k}(j,k) ∈ Z2 forme une base d’ondelettes orthogonales de L 2 (IR). Si f est une fonction discrète alors pour toute fonction φ, il existe un niveau de résolution j suffisamment petit tel que f appartienne à Vj . On peut donc translater le niveau de résolution et fixer j = 0 pour que f appartienne à V0. La transformée en ondelettes d’une fonction f ∈ V0 sur n niveaux est alors définie comme la projection de cette fonction sur les espaces Vn et {Wj}1≤j≤n car V0 = Vn ⊕ hLn j=1 Wj i . Les coefficients de projection sur Vj sont notés aj [k] et nommés coefficients d’approximation tandis que ceux sur Wj sont notés dj [k] et nommés coefficients d’ondelette ou coefficients de détail. On a alors : aj [k] = hf, φj,ki (1.6) dj [k] = hf, ψj,ki (1.7) où h·, ·i représente le produit scalaire dans L 2 (IR). Ces relations nous permettent de calculer explicitement les coefficients de la transformée en ondelettes de f sur n niveaux. Cependant, l’intégration sur IR qu’elles nécessitent les rendent très lourdes à utiliser. Nous verrons dans la section 1.2.2 qu’il est possible de construire un algorithme de calcul rapide des coefficients aj [k] et dj [k]. Enfin, on remarquera que la transformée en ondelettes est une application linéaire, inversible et orthogonale. C’est donc une isométrie qui préserve la norme ℓ2, c’est à dire l’énergie d’un signal. On a alors P k aj [k] 2 = P k aj+1[k] 2 + dj+1[k] 2 .