Synthèse de bancs de filtres adaptés

Banc de filtres, ondelettes et lifting scheme 2-D

   Les signaux bi-dimensionnels que nous considérons sont des images numériques à support fini. Nous pouvons représenter une image ayant N` lignes et Nc colonnes par une matrice X rectangulaire de dimension N` × Nc. Introduisons également l’opérateur vec qui, appliqué à une image X, met toutes ses colonnes les unes audessous des autres (la première en haut et la dernière en bas) pour obtenir un vecteur vec(X) de dimension N`Nc. Les opérations de sous-échantillonnage, sur-échantillonnage, filtrage se généralisent, comme cela est bien connu, pour s’appliquer à des signaux 2-D. Notons Y l’image obtenue après une décomposition appliquée à X. Par linéarité, cette opération s’écrit vec(Y) = A · vec(X), où A est une matrice. Quand la décomposition consiste à appliquer une transformation A` sur les lignes et une transformation Ac sur les colonnes de X, c’est-à-dire quand Y = AcXAT` (l’ordre d’application ne modifie pas le résultat), elle est dite séparable. En général dans les lifting schemes qui s’adaptent aux images les filtres prédicteurs ne sont pas séparables.

Lifting schemes adaptés en compression

   L’adaptation du lifting scheme en fonction du signal d’entrée est principalement utilisée dans un cadre de codage de signaux et principalement des images. Nous recensons dans cette section les structures de ce type qui existent déjà. Certaines ont été développées pour du codage avec pertes, mais il est facile de rendre les structures réversibles (voir le §2.4.2.3 au chapitre suivant) pour les utiliser dans un cadre sans perte.
Adaptation par sélection de l’ordre du prédicteur La structure en lifting scheme proposée par Claypool et al. [34] utilise un prédicteur basé sur les propriétés locales de l’image, de sorte que dans la fenêtre de prédiction, les contours qui correspondent aux non stationnarités, soient “évités”. Pour chaque fenêtre de prédiction, les données sont analysées. Si ces dernières présentent une certaine régularité, alors l’ordre du filtre prédicteur est grand. Dans le cas contraire, les pixels responsables de cette “irrégularité” sont déterminés et classifiés comme étant des pixels appartenant à un contour. À proximité de ces contours, l’ordre du filtre prédicteur est réduit, de sorte que le voisinage utilisé pour la prédiction ne chevauche pas le contour. De cette manière, les grandes erreurs de prédiction sont évitées à proximité des contours. La figure 1.13 illustre la procédure de sélection de l’ordre du filtre prédicteur à proximité d’un contour.
Adaptation sous contrainte Les travaux menés par A. Gouze [50] portent sur la transformée en ondelettes appliquée en compression d’images. L’objectif central était la factorisation d’un banc de filtres bi-dimensionnels non séparables en lifting scheme. Ce dernier est par la suite construit en fonction des propriétés statistiques de l’image, dans le but de fournir un algorithme de compression approprié et efficace pour des images directement échantillonnées en quinconce. La méthode proposée se base sur un lifting scheme à deux pas. Le processus d’optimisation définit en premier lieu un opérateur de prédiction. L’auteur part du principe que le codage est plus performant sur un signal de faible variance. Le critère retenu pour définir le pas de prédiction consiste, par conséquent, en la minimisation de la variance de l’image de la sous-bande haute fréquence. Une contrainte est imposée permettant de garder une moyenne nulle aux coefficients de la sous-bande haute fréquence. Cela se traduit par une somme égale à 1 des coefficients du filtre prédicteur.
Adaptation pour des signaux WSS avec post-traitement nonlinéaire Dans le cas de la compression sans perte des images, une méthode de calcul des filtres prédicteurs optimaux d’un lifting scheme est proposée par N.V. Boulgouris et al. [27]. Plusieurs cas sont traités suivant le choix de la décomposition polyphase (en quinconce ou non) de l’image à coder. Dans chaque cas, l’efficacité des prédicteurs linéaires est améliorée en utilisant une non-linéarité. Un post-traitement directionnel est employé dans le cas d’un sous-échantillonnage en quinconce. Dans le cas d’un sous-échantillonnage séparable, le post-traitement consiste en une adaptation de la longueur du filtres prédicteur. Le schéma traité est un lifti Adaptation basée sur l’algorithme du gradient stochastique Une structure en lifting scheme adaptative basée sur l’algorithme du gradient stochastique a été proposée par Gerek et Çetin [46, 47]. Les coefficients du filtre prédicteur sont mis à jour au fur et à mesure du balayage des pixels de l’image.

Le codage arithmétique

   Le codage arithmétique attribue un “mot de code” à chaque ensemble de données. Ces “mots de code” correspondent à des intervalles semi-ouverts disjoints inclus dans [0, 1[. Les “mots de code” sont construits en spécifiant suffisamment de bits pour distinguer des autres intervalles celui correspondant à l’ensemble actuel de données. Les codes les plus courts sont associés aux intervalles les plus larges, qui représentent les ensembles de données les plus probables. Dans la pratique, l’intervalle est raffiné successivement en utilisant les probabilités d’occurrence p(yi) des symboles. Un codage entropique doit être accompagné, aux différents points de codage, d’un modèle d’estimation de probabilité pour chaque symbole possible. Ce modèle de probabilité n’a pas besoin de décrire le processus qui génère les données, il doit tout simplement fournir une distribution de probabilité des données, qui n’est pas nécessairement exacte. Toutefois, le débit sera d’autant plus faible que la distance de Kullback-Leibler entre les distributions de probabilité (réelle et estimée) sera faible [37]. Le modèle peut être adaptatif (estimation dynamique de la probabilité de chaque symbole en fonction des événements qui précèdent), semi-adaptatif (en effectuant un passage préliminaire dans le fichier à coder pour estimer les statistiques) ou non-adaptatif (en utilisant des probabilités fixes pour tous les fichiers). Les modèles non-adaptatifs sont arbitraires et souvent peu performants [122]. Le codage adaptatif est du type “un seul passage” mais a une plus grande complexité. En revanche le codage semi-adaptatif exige un double passage et la transmission du modèle de données comme information supplémentaire. Si la transmission du modèle est bien optimisée il peut fournir une meilleure compression que le codage adaptatif. En général, le coût de transmission du modèle semi-adaptatif est presque le même que celui de l’apprentissage du modèle adaptatif notamment pour des données codées sur 8 à 10 bits [55].

Prédiction linéaire basée sur des moments d’ordres supérieurs à 2

   Les cumulants d’ordres supérieurs peuvent être très utiles dans des applications impliquant des signaux non-gaussiens. Comme les images d’erreur de prédiction linéaire sont généralement bien modélisées par une distribution laplacienne [59], les images naturelles peuvent être considérées comme non gaussiennes [107]. La prédiction linéaire basée sur des cumulants a été décrite dans [102]. Des filtres de type ARMA mono-dimensionnels, basés sur des statistiques d’ordres supérieurs, ont été introduits dans [30] pour de la prédiction. Ils sont une extension des filtres MA proposés dans [31]. Dans [52], les prédicteurs linéaires de type ARMA basés sur des cumulants d’ordres 2 et 3 ont permis d’obtenir des images plus nettes à l’œil nu, grâce à l’exploitation des statistiques d’ordre 3. Cependant, les auteurs ont remarqué que ces filtres ne sont pas optimaux au sens de l’erreur quadratique moyenne. Une autre illustration de cette sous-optimalité en compression de données peut être trouvée dans [79]. Les prédicteurs linéaires sont parfois inadéquats, notamment quand le signal à coder est non gaussien et lorsque la dépendance entre les échantillons est non linéaire. Nous présentons maintenant des prédicteurs non linéaires.

Table des matières

Notations
Introduction générale
1 Banc de filtres, ondelettes et lifting scheme adaptés 
1.1 Introduction 
1.2 Banc de filtres à reconstruction parfaite 
1.2.1 Sous- et sur-échantillonnage
1.2.2 Analyse et synthèse par bancs de filtres
1.2.3 Représentation polyphase d’un banc de filtres
1.3 Ondelettes et lifting scheme 
1.3.1 Analyse multi-résolution et ondelettes
1.3.2 Lifting scheme
1.4 Banc de filtres optimal en codage avec pertes
1.4.1 Le banc de filtres à optimiser
1.4.2 Le signal à coder
1.4.3 Les quantificateurs
1.4.4 Position du problème d’optimisation
1.4.5 Cas d’un banc de filtres biorthogonal
1.4.6 Cas d’un banc de filtres orthogonal
1.5 Banc de filtres, ondelettes et lifting scheme 2-D 
1.6 Lifting schemes adaptés en compression
1.6.1 Adaptation par sélection de l’ordre du prédicteur
1.6.2 Adaptation sous contrainte
1.6.3 Adaptation pour des signaux WSS avec post-traitement nonlinéaire
1.6.4 Adaptation basée sur l’algorithme du gradient stochastique
1.7 Conclusion
2 Compression d’images 
2.1 Introduction 
2.2 Compression avec pertes
2.2.1 Transformation
2.2.2 Quantification
2.2.2.1 La quantification scalaire
2.2.2.2 La quantification vectorielle
2.2.3 Allocation optimale
2.2.3.1 Allocation de débit
2.2.4 Codage entropique
2.2.4.1 Le codage de Huffman
2.2.4.2 Le codage arithmétique
2.2.4.3 Codage universel
2.3 Codage progressif 
2.3.1 Progressivité en résolution
2.3.2 Progressivité en qualité
2.4 Compression sans perte 
2.4.1 Schéma général
2.4.2 Prédiction
2.4.2.1 Prédiction linéaire
2.4.2.2 Réseaux de neurones
2.4.2.3 Lifting scheme réversible
2.5 Principaux systèmes de compression sans perte 
2.5.1 LOCO-I
2.5.2 CALIC
2.5.3 JPEG 2000
2.5.4 Autres systèmes à base de lifting schemes adaptés
2.6 Conclusion 
3 Synthèse de bancs filtres adaptés proposée 
3.1 Introduction 
3.2 Justification du critère de minimisation de la variance
3.3 Structure en lifting scheme généralisé
3.3.1 Schéma de principe pour des signaux 1D
3.3.2 Extension aux signaux 2D
3.3.3 Réversibilité de la structure proposée
3.3.4 Décomposition multi-résolution
3.3.5 Adaptation de la structure 2D proposée
3.4 Méthode d’adaptation globale (GAE)
3.4.1 Choix du critère
3.4.2 Calcul rapide de la matrice du système
3.5 Méthode d’adaptation locale (LAE) 
3.5.1 Choix du critère
3.5.2 Algorithme de décomposition
3.6 Application à des signaux synthétiques
3.6.1 Construction des signaux
3.6.2 Résultats
3.7 Conclusion 
4 Application à la compression sans perte des images réelles 
4.1 Introduction 
4.2 Ajustement des paramètres par famille d’images
4.2.1 La méthode GAE
4.2.1.1 Choix du type de sous-échantillonnage
4.2.1.2 Choix des ordres des filtres
4.2.1.3 Nombre de niveaux de décomposition
4.2.1.4 Utilisation de la transformation S (décomposition SGAE)
4.2.1.5 La méthode GAE améliorée (GAEa)
4.2.1.6 En-tête du flot de bits
4.2.2 La méthode LAE
4.2.3 Choix de l’algorithme d’adaptation
4.2.3.1 Traitement des bords
4.2.3.2 Choix du type de sous-échantillonnage
4.2.3.3 Choix de l’ordre des filtres prédicteurs
4.2.3.4 Choix du facteur d’oubli
4.2.3.5 En-tête du flot de bits
4.2.4 Complexité
4.3 Performances en compression sans perte
4.3.1 Avec mesure de débit par entropie d’ordre 1
4.3.2 Avec débit réel
4.3.3 Codage progressif en résolution
4.3.4 Analyse des résultats
4.4 Peux-on faire du codage progressif en qualité ? 
4.4.1 Schéma LAE modifié
4.4.1.1 Un niveau de décomposition
4.4.1.2 Plusieurs niveaux de décompositions
4.4.2 Description du codec
4.4.3 Estimation des coefficients de pondération
4.4.4 Évaluation des performances à hauts débits
4.4.4.1 La méthode GAEa
4.4.4.2 La méthode LAE modifiée
4.5 Conclusion
Conclusion générale
Bibliographie
Annexes 
A Courbes débit/distorsion relatives à la section 4.4.4 
B Images utilisées dans les tests 
B.1 Les mages naturelles
B.2 Images médicales IRM
B.3 Images satellitaires
B.4 Images de textures et empreintes digitales
C Transformations en ondelettes de Z dans Z 
C.1 La transformation S
C.2 La transformation (2, 2) ou 5/3
C.3 La transformation (4, 2)
C.4 La transformation (2,4)
C.5 La transformation (2+2,2)
C.6 La transformation (4,4)
C.7 La transformation (6,2)
C.8 La transformation 9 − 7
C.9 Les transformations S+P et TS

Télécharger le rapport complet