CODAGE, COMPRESSION et ECHANGES D'IMAGES

DEA Signaux et Images en Biologie et Médecine CODAGE, COMPRESSION et ECHANGES D'IMAGES Sommaire PARTIE I : LA COMPRESSION D’IMAGES _______________________________________ 1 I.1) Introduction_______________________________________________________________ 1 I.2) Les Méthodes de Compression d'Images _______________________________________ 2 I.3) Efficacité et Qualité d'un Codage _____________________________________________ 4 I.4) Les Méthodes de Codage Statistique___________________________________________ 5 I.5) Les Méthodes de Codage Spatial ______________________________________________ 7 I.6) Les Transformations Orthogonales____________________________________________ 8 I.7) Les Méthodes Hiérarchiques ________________________________________________ 12 I.8) Les Décompositions par Bancs de Filtres ______________________________________ 13 I.9) Les Méthodes de Codage par Segmentation et Séparation en deux Composantes _____ 16 I.10) La Compression Fractale __________________________________________________ 19 I.11) La Compression de Séquences ______________________________________________ 20 I.12) Evaluation de la Qualité des Images Reconstruites après Codage Irréversible ______ 20 PARTIE II : LE TATOUAGE D’IMAGES_________________________________________ 21 II.1) Introduction _____________________________________________________________ 21 II.2) Les Méthodes de Tatouage d’Images_________________________________________ 21 II.3) Les Méthodes Robustes de Tatouage d’Images ________________________________ 23 II.4) Les Méthodes Fragiles de Tatouage d’Images _________________________________ 25 Christine CAVARO-MENARD Unité de Traitement d’Images Médicales - Équipe Signal et Image - LISA CNRS FRE 2656 Service de Médecine Nucléaire et de Biophysique - CHU d'Angers 4 rue Larrey - 49033 ANGERS Cedex 01 Tel : 02-41-35-56-59 - E-mail : christine.menard@univ-angers.fr fi fi fi fi DEA Signaux et Images en Biologie et Médecine LA COMPRESSION D’IMAGES I.1) Introduction I.1.1 Le Problème Résoudre les difficultés grandissantes d'archivage et de transmission des images biomédicales, pour l’exploitation des images au sein de réseaux. Caractéristiques des principales classes d'images biomédicales : Modalité Zone Taille de Nombre de Nombre bits Taille des d'acquisition explorée l'image coupes de codage fichiers Crâne 512*512 20 à 40 12 10 à 20 Mo TDM Thorax 512*512 Zone explorée 12 0,5 Mo 512*512 ou I.R.M. Crâne 20 10 Mo - 40 Mo 16 1024*1024 Cœur 256*128 10 (*synchro) 10 Mo 16 Radiologie - 2000*2000 - 16 8 Mo Les images médicales sont plus riches en niveaux de gris que la plupart des images. I.1.2 La Solution Réduction du volume représentatif des données de l'image ou COMPRESSION d'IMAGES (codage de source) En fait la compression d'images est : - une alternative de faible coût à l'augmentation de la capacité des systèmes d'archivage et des lignes de transmission, - indispensable à la réalisation des PACS (Picture Archiving and Communication Systems) : difficultés liées au volume important des données numériques à stocker, à transmettre et à gérer. I.1.3 L'Objectif de la Compression d'Images L'objectif principal de la compression d'images est de minimiser la quantité d'information (nombre de bits) nécessaire à une représentation fidèle de l'image originale. Cet objectif est réalisable vu l'importante corrélation spatiale présente dans une image (deux pixels voisins ont des valeurs comparables). Dans le cas de séquences d'images, les corrélations temporelles pourront être utilisées. Pour les images naturelles, les techniques de codage doivent satisfaire au seul critère de qualité visuelle des images reconstruites. Pour les images médicales, la compression doit impérativement éviter l'introduction de distorsions ayant pour effet d'entraîner des modifications dans : l'interprétation qualitative des images, la valeur des paramètres anatomiques ou fonctionnels reflétant l'état de l'organe étudié. Page 1 DEA Signaux et Images en Biologie et Médecine LA COMPRESSION D’IMAGES I.2) Les Méthodes de Compression d'Images I.2.1 Les Etapes Le codage d'images peut être décomposé en deux étapes : - l'extraction des informations contenues dans l'image : COMPRESSION. - l'assignation d'un code aux divers messages obtenus : CODAGE ou COMPACTAGE. La compression se décompose en une phase de décorrélation des données et une phase de quantification. + Calcul de l’erreur - de quantification Décorrélation Quantification + 1 1 + 0 0 La décorrélation permet de réduire la dépendance statistique qui existe entre les pixels voisins d'une image. Pour réduire le volume des images, cette étape est toujours combinée à la quantification et/ou au compactage. La quantification consiste à représenter un message en un nombre fini de bits. La quantification scalaire la plus simple consiste à diviser la dynamique du signal original en un ensemble d'intervalles identiques, le pas de quantification détermine la longueur moyenne des codes ainsi que la perte moyenne d'information. La quantification optimale minimise l’erreur quadratique moyenne entre le signal original et le signal quantifié. Pour définir le quantificateur optimal, il s’agit de trouver la partition et le dictionnaire qui minimisent la distorsion D. Cette optimisation conjointe n’admet pas de solution simple, mais il est possible de : - trouver la meilleure partition connaissant le dictionnaire, c’est la règle dite du plus proche voisin ; - trouver le meilleur dictionnaire connaissant la partition, c’est la condition du centre de gravité. L’algorithme de Lloyd-Max construit itérativement (en utilisant les 2 conditions précédentes) un dictionnaire de quantification de façon à minimiser la distorsion D. Pour cela, l’algorithme utilise un dictionnaire initial et modifie itérativement sa structure en fonction du partitionnement obtenu à chaque itération. Finalement un intervalle de quantification sera d’autant plus petit que la probabilité que x appartienne à cet intervalle est grande. La quantification vectorielle est une généralisation multidimensionnelle de la quantification scalaire. Le quantificateur vectoriel optimal peut être considéré comme un quantificateur de Llyod-Max multidimensionnel. L’algorithme LBG permet de calculer, pour un débit r donné, un dictionnaire de vecteurs quasi optimal. La quantification fait alors appel à une recherche dans le dictionnaire du vecteur le plus proche du vecteur d’entrée considéré (coûteux en temps de calcul). Ce coût de calcul peut être réduit en utilisant des algorithmes sous optimaux tels que la quantification vectorielle avec structure en arbre. Page 2 DEA Signaux et Images en Biologie et Médecine LA COMPRESSION D’IMAGES I.2.2 Classification des Méthodes de Compression Les méthodes de compression peuvent être classées en deux catégories : - les méthodes de Codage Pixel ou de 1ère génération, - les méthodes de Codage Global ou de 2éme génération. Ces méthodes peuvent être qualifiées de réversibles ou d’irréversibles. Les méthodes de codage pixel (ou syntaxiques) Ces méthodes analysent l'information pixel par pixel. Elles consistent à rechercher la redondance de l'information contenue dans l'image et à la coder de façon réduite, en faisant appel à des concepts de la théorie de l'information. Les méthodes de codage global (ou sémantiques) Ces méthodes extraient l'information contenue dans l'image non plus pixel par pixel mais selon les caractéristiques de l'image telles que les descriptions de contour ou de texture. Les méthodes réversibles Les techniques réversibles produisent un duplicata exact de l'image originale. Dans le domaine médical, le critère de réversibilité est primordial pour beaucoup de considérations d'ordre éthique. Les méthodes irréversibles Les techniques irréversibles ne restituent qu'une approximation des données initiales. C'est l'étape de quantification qui rend le codage irréversible. Seule la transmission de l'erreur de quantification permet alors de rendre la compression réversible. COMPRESSION CODAGE DECORRELATION QUANTIFICATION Quantification Scalaire Quantification Vectorielle Codage Pixel Codage Global Méthodes Méthodes Méthodes Décomposition par Spatiales hiérarchiques hiérarchiques bancs de filtres Par plages Par arbre Pyramide Décomposition en images Par blocs Par interpolation Laplacienne directionnelles Prédictives Transformation-S Fractales Ondelettes Codage Statistique Modèle Huffman Transformations Contour-texture Shannon-Fano Orthogonales Synthèse des hautes fréquences Arithmétique Karhunen-Loeve Segmentation : Lempel-Ziv Walsh Hadammard - Par Croissance des régions Fourier - ‘Split and merge’ Cosinus - JPEG - Par Extraction des contours Classification des méthodes de codage Page 3 ˛ £ d d d d d DEA Signaux et Images en Biologie et Médecine LA COMPRESSION D’IMAGES I.3) Efficacité et Qualité d'un Codage I.3.1 Calcul de l'Efficacité d'un Codage * Taux ou Facteur de compression Mesure la réduction opérée sur le volume des données lors du codage. Nombre total de bits avant codage TC = Nombre total de bits après codage * Nombre moyen de bits par pixel après codage * Éléments de théorie de l’information La théorie de l’information définit des bornes asymptotiques quant au nombre de bits nécessaires à la représentation d’une information. Ces bornes sont données par l’entropie H(S) de la source dans le cas d’un codage sans perte ou par une fonction débit-distorsion dans le cas du codage avec perte. Dans un codage avec perte et avec critère de qualité, l’alphabet de représentation optimal de la source est celui permettant de minimiser la fonction débit-distorsion R(D) = min I(X ,Y ) avec I(X,Y) l’information mutuelle (décorrélation information)