Une ondelette pour les compresser toutes - Deux (deux ?) minutes pour...

[Musique] en 1988 la mathématicienne belge Ingrid dobbechies mais au point une famille de fonction au propriétaire remarquables les onglets de dobbechies saison de lettre trouvons une application très concrète une dizaine d'années plus tard le standard de compression d'image JPEG 2000 il faut dire que la théorie des ondelettes est un champ de la recherche mathématique aujourd'hui particulièrement fertile aux applications très variées reconstruction d'images numériques détection des ondes gravitationnelles imagerie médicale j'ai aux sciences et cetera mon application préférée c'est tout de même la compression d'image et ça tombe bien j'ai 2 minutes pour en parler [Musique] prenons cette jolie photo comment peut-on décrire précisément son contenu on peut dire qu'il s'agit d'une splendide vue aérienne du village de motovule en Croatie mais ce n'est pas vraiment la question comment peut-on la décrire précisément d'un point de vue informatique on peut commencer par dire qu'il s'agit d'une image de 1024 pixels sur 1024 pixels soit 1 million 48576 pixel en tout pour décrire l'image il suffit donc de lister tous ces pixels les uns à la suite des autres pour décrire la couleur d'un pixel il n'existe plusieurs codages le plus élémentaire et le code RVB on décrit la quantité de rouge de vert et de bleu qui composent la couleur par exemple le premier pixel de cette photo est un carré bleu charrette constitué de 48% de rouge 62 % de verre et 74 % de bleu en ramenant chaque pourcentage sur une échelle de 0 à 255 ce pixel a donc pour code RVB 123 160 189 le code RVB d'une couleur c'est donc trois nombres entiers entre 0 et 255 puisqu'il faut un octet pour coder de tels entiers chaque pixel demandera donc 3 oct ma photo croisé son mignon pixel demandera donc 3 millions d'octets pour être sauvegardés c'est-à-dire 3 mes billes octets pour une photo de cette taille c'est beaucoup trop il va falloir user un peu pour minimiser la taille et changer de point de vue pour coder une couleur on a vu que l'on a besoin de trois nombres sa quantité de rouge de vert et de bleu mais c'est loin d'être la seule façon de définir une couleur par trois nombres on peut par exemple définir une couleur parfaitement en indiquant uniquement la quantité de rouget de bleu mais en ajoutant sa luminance on a alors d'un côté la luminance l'image en niveau de gris et de l'autre les chrominance qui caractérise les couleurs de l'image et cette décomposition à un avantage non négligeable elle est bien plus adaptée à la façon dont un être humain typique perçoit les couleurs l'œil humain est en effet beaucoup plus sensible aux différences de luminosité qu'aux différences de couleur une idée pour gagner de la place sans trop gêner les yeux c'est alors de légèrement dégradé le codage des couleurs dans les deux images de chrominance je peux par exemple remplacer chaque carré de 10 ans 8XL survie pixels par leur moyenne ces deux composantes de l'image vont donc prendre 64 fois moins de place on peut alors reconstituer l'IM original elle fait un peu illusion quand on y regarde pas de trop près bon j'y suis allé un peu avec mes gros sabots personne ne compresses des images comme ça mais il y a tout de même derrière cette première approche des idées intéressantes il faut oublier l'idée de coder l'image pixel par pixel on va travailler bloc par bloc en découpant l'image en carré de 8 pixels sur 8 pixels prenons donc un de ces carrés de 64 pixels pour simplifier on va travailler que sur la composante des luminance mais gardons en tête que tout cela s'applique également aux composantes de crominance on a donc à présent sous la main un bloc de 64 pixels c'est-à-dire une matrice de 64 nombres qu'il faut chercher à décrire de façon efficace une façon de faire c'est de le voir comme une somme de pixel unité 188 fois le premier pixel + 187 fois le deuxième pixel plus 186 fois le troisième pixel et ainsi de suite de manière générale n'importe quelle image de dimension 16 par 16 pourra s'exprimer comme somme de ses pixels unités on dit que c'est pixels forment une base de l'espace de toutes les images mais ce n'est qu'une façon de faire parmi bien d'autres plutôt que de prendre des pixel unité comme base on peut plutôt partir sur une sélection de motifs bien choisis il faut exprimer notre image comme une somme de motif mais quel motif utiliser les adeptes de la théorie du signal ont une réponse parfaite la théorie de Fourier résumons dans les grandes lignes cette théorie si je prends un signal périodique comme celui-là il existe toujours un moyen de le décomposer sous la forme d'une somme de signaux périodique de plus ou moins haute fréquence des fonctions sinus et cosinus la beauté de cette décomposition c'est que si on ne conserve que les signaux de plus basse fréquence la forme globale du signal sera conservée j'ai déjà fait une superbe vidéo sur ce sujet je vous invite à la visionner au plus vite ce principe de Fourier peut s'adapter en deux dimensions n'importe quelle image de 8 pixels sur 8 pixel pour un t-elle exprimé en une somme de ses 64 motifs de plus ou moins haute fréquence pour coder une image de 64 pixels sur cette base de motif il faut donc les 64 coefficients de la Somme l'image obtenue par cette décomposition est en théorie identique mais présente en pratique quelques différences mineures à cause des erreurs d'arrondi mais si on accepte de dégrader très légèrement l'image on peut se permettre de ne conserver qu'une partie de ces nombres ce qui correspondent aux fréquences les plus basses brusques de lumière ou de couleur dans la photographie elles sont donc plus rares cela fait donc encore moins de coefficient à sauvegarder et donc une image qui prend moins de place en mémoire la contrepartie c'est que notre photographie pourra présenter quelques artefacts qui trahissent la compression et son découpage en bloc cette décomposition d'une image en bloc exprimée en somme de motivé fourrière c'est le cœur du format de compression d'image JPEG celui que l'on utilise tous les jours dès que l'on manipule n'importe quelle photographie numérique malheureusement cette belle compression JPEG en somme de motif de Fourier a de nombreux défauts le plus flagrant c'est cette présence d'artefact de compression assez visible lorsque l'image est découpée en bloc une approximation de Fourier effectuée sur un bloc donné n'a aucune raison d'être dans le prolongement de celui du bloc voisin lorsque l'image est fortement compressée c'est discontinuités ressortent particulièrement mais surtout le vrai problème de cette compression via la théorie de Fourier c'est sa difficulté à bien appréhender les changements brusques dans une image lorsque l'on cherche à proximer une fonction discontinue par une somme de fonction cosinus et sinus on pourra observer une sorte le sursaut au niveau des discontinuités c'est ce que l'on appelle le phénomène de gypse et il faut l'éviter bref la théorie de Fourier c'est très bien mais on s'y sent parfois à l'étroit le cœur de cette théorie ce sont les fonctions trigonométriques des fonctions périodiques définies partout tout le temps si on veut modéliser avec ça un signal court dans le temps comme un coup de tonnerre ou un bruit de cymbale on va vite déchanter il nous faudrait des ondes plus courtes borné dans le temps mais qui permettent tout de même de reconstruire des signaux quitte à les déplacer ou à les dilater on donnera dans les années 80 à ces petites ondes le nom d'omelette historiquement la première anglaise a été mise au point par Alfred are au début du 20e siècle la théorie des andelettes devient très solide dans les années 80-90 grâce aux travaux de nombres mathématiciens en particulier Yves Meyer qui sera récompensé du prix Abel l'autre récompense la plus prestigieuse en mathématiques pour comprendre l'idée derrière les onglets on va prendre la plus simple d'entre elles l'onglet de art c'est simplement une fonction qui vaut 0 partout sauf entre 0 et 1 où elle vaut soit - 1 soit plus un faisons un petit exemple avec cette onglet on va tenter de coder un signal que l'on va représenter par une suite ici de 8 nombres 4 6 7 8 8 9 7 on commence par appliquer cette onglet sur les deux premiers nombres de la liste ce qui consiste à prendre négativement le premier et positivement le deuxième moins 4 + 6 ça fait 2 on fait de même sur le couple de nombre suivant moins 7 + 8 = 1 on poursuit le processus ce qui nous donne finalement 4 coefficients qui correspondent aux différences des nombres de la liste on met de côté ces quatre coefficients et on va maintenant remplacer chaque couple de nombres par leur moyenne on a alors la liste 5 7 et demi 8 8 on recommence alors à la première étape on calcule les différences de chaque paire ce qui nous donne 2,5 et 0 que l'on met de côté et on remplace nos nombres par leur moyenne on a maintenant 6,25 et 8 on effectue une dernière fois le calcul de la différence 1,75 et de la moyenne 7,125 on met enfin les deux nombres de côté la liste de 8 noms que l'on obtient 2 1 0 - 2,5 0 1, 115 7,125 code alors les variations sur différentes échelles de ma liste de départ de plus il est possible de reconstruire cette liste de départ en remontant le processus en partant du nombre d'arrivés 7,125 il suffit d'ajouter ou de retirer la moitié de la différence pour trouver les deux nombres que l'on a formé en poursuivant on retrouve bien la liste de départ cette transformation de art il est possible de l'appliquer en deux dimensions pour encoder les différences d'une image pour cela on va prendre des pixels de l'image par bloc de 4 dans chacun de ces petits blocs on va calculer d'une part les différences horizontales verticales et diagonales des valeurs de ces pixels et on va d'autre part calculer la moyenne une fois que tous les calculs sont faits on se retrouve avec 4 images 3 qui correspondent aux différences horizontales verticales et diagonales dans l'image de départ et une dernière qui est l'image de départ diminue en taille d'un facteur 4 on peut alors répéter l'opération sur cette image là jusqu'à ce que l'image originale soit réduite à un seul point le processus peut lui aussi être remonté de façon à retrouver l'image originale après cette transformation on obtient alors une image qui représente les différences entre les pixels dans toutes les directions et à différents niveaux d'échelle ce que l'on remarque surtout c'est que cette image a été essentiellement noire c'est pixel noir correspondent en fait aux zones de l'image de départ ou les variations de lumière sont très faibles tandis que les pixels clairs indiquent les changements plus prononcés cette façon de coder l'image permet donc de mettre l'accent sur ce qui est essentiel aux yeux dans une image les changements brusques de fréquence pour compresser une image il nous suffit alors de ne pas sauvegarder ses pixels noirs cette compression vient les omelettes permet donc de mieux mettre en valeur ses discontinuités tout en ayant l'avantage de ne pas être trop gourmand en terme de calcul le format de compression JPEG existe aujourd'hui sous plusieurs standards le standard classique qui utilise les transformations de Fourier et le standard jpec 2000 qui s'appuie sur les transformer en anglais ce n'est pas long de l'aide de art qui est utilisé en pratique mais celle de dobbechies plus précisément l'ondelette biorthogonale CDF 9 7 de Cohen dobbechies et Fauveau la théorie des ondelettes est un sujet de recherche mathématique très actif notamment à zen l'Institut de Mathématiques de Marseille placé sous la tutelle du CNRS d'Aix-Marseille Université et de l'École centrale de Marseille la mathématicienne Sandrine Antoine qui m'a beaucoup aidé à l'écriture de cette vidéo travaille par exemple sur les problèmes inverse en imagerie médicale lorsque l'on passe une IRM ou un PET scan par exemple on veut obtenir une belle image de notre intérieur pour cela il est nécessaire de résoudre ce que l'on appelle un problème inverse celui de la reconstruction 3D en effet c'est scanner ne mesure pas directement ce que l'on voit de l'objet mais plutôt les projections de son intérieur sous différents angles dans un PET scan par exemple les mesures opérées forment ce que l'on appelle des intégrales de ligne et le passage de cet ensemble de mesures à l'objet final n'a rien de très évident il n'est en effet possible que dans d'acquérir un nombre fini on ajoute à ce manque d'information les incertitudes sont les mesures elles-mêmes ce qui fait qu'une méthode d'inversion simple pourra produire des reconstructions bourritée pour résoudre ces problèmes on peut concevoir des onglets et des modèles sur ses coefficients ayant les bonnes propriétés mathématiques et qui seront adaptées au type d'objets que l'on cherche à reconstruire ainsi l'onglet pour modéliser un cerveau humain ne sera pas tout à fait la même que celle utilisée pour observer l'intérieur d'un muscle par exemple cette application des ondelettes à l'imagerie médicale n'est qu'un exemple parmi tant d'autres les onglets peuvent aussi être utilisées pour enlever le flou d'une observation issue d'un microscope pour modéliser les turbulences d'un fluide pour construire des images et cetera et cetera bref maison de l'aide c'est bien mangez-moi cette vidéo a été réalisée en partenariat avec Eco sciences provençale-côte d'Azur dans le cadre des vidéos écho scientifique elle a été écrite en collaboration avec Sandrine Antoine mathématicienne Ali 2M pour en savoir plus sur les onglets retrouver mon interview de Sandrine sur la chaîne déco science en lien dans la description