Comment les arbres permettent-ils de compresser des images ? - Grand Oral NSI

Thèmes abordés

NSI Numérique et Sciences Informatiques, compression d'une image, volume de données, arbre informatique, arbre de Huffman, Quadtree

Résumé du document

En 2010, d'après les estimations, le volume de données numériques créé à l'échelle mondiale était de 2 zettaoctets selon Statista et Seagate, soit 2 milliards de téraoctets. En 2020, ce chiffre s'élevait à 64 zettaoctets, soit 64 milliards de téraoctets.
On peut alors légitimement se demander si les infrastructures actuelles pourront continuer d'absorber un volume de données toujours plus grand. Néanmoins, des solutions existent pour réduire considérablement la taille des données, ces solutions permettent de réduire la taille d'un fichier tout en gardant son contenu quasi intact ou même totalement intact.
Certaines de ces méthodes utilisent une structure de données bien connue dans le domaine de l'informatique : les arbres. Ce sera ici le point central de mon oral, nous allons plus spécifiquement voir l'utilisation de ces méthodes appliquées à la compression des images, un domaine où le volume de données est particulièrement important.

Extraits

[...] Vous vous demandez sûrement comment reconstruire l'image à partir de l'arbre. On vas tout simplement effectuer un parcours en profondeur de l'arbre On commence par le noeud racine si c'est une feuille on dessine le carré de la couleur avec la taille et les coordonnées correspondante sinon on appelle récursivement la fonction de reconstruction avec son premier enfant (par exemple, le quadrant supérieur gauche). Une fois que cet enfant (et tous ses descendants) a été traité, on fais de même pour le deuxième enfant (supérieur droit), puis le troisième (inférieur gauche), et enfin le quatrième (inférieur droit). [...]

[...] Comment les arbres permettent-ils de compresser des images ? - Grand Oral NSI Introduction En 2010, d'après les estimations le volume de données numériques créé à l'échelle mondial était de 2 zettaoctets selon Statista et Seagate, soit 2 milliard de téraoctets, en 2020 ce chiffre s'élevait à 64 zettaoctets soit 64 milliard de téraoctets. On peut alors légitimement se demander si les infrastructures actuelles pourront continuer d'absorber un volume de données toujours plus grand. Néanmoins des solutions existent pour réduire considérablement la taille des données, ces solutions permettent de réduire la taille d'un fichier tout en gardant son contenue quasi intacte ou même totalement intacte. [...]

[...] Ce principe, pourtant simple, permet de compresser des images de façon très efficace et sans aucune perte d'information. Imaginons une image représentée par le code suivant : NNNNNWWWBBW ou N represent un pixel noir, w un pixel blanc et B un pixel bleu. La première étape du codage huffman est de compter les fréquences. Dans notre cas on ales fréquence suivante: N : 5 w : 4 2 On vas ensuite construire l'arbre de huffman qui vas nous permettre de créer les codes binaire compressé de chaque couleurs pixel: On prend les deux plus petites fréquences , dans notre cas w et b. [...]

[...] Dans un premier, comme l'algorithme sans perte, on prend l'image de base comme racine. On vérifie ensuite si l'image est homogène, mais cette fois-ci avec un seuil d'homogénéité on considérera les couleurs proches comme une seule zone. Si l'image n'est pas homogène, on la divise en quatre zones qui deviennent les enfants du n?ud . jusqu'à trouver une zone homogène (qui dans notre cas prendre la couleur dominante de la zone) ou atteindre une taille de 1 pixel Grâce à cette méthode, au lieu de stocker chaque pixel individuellement dans une zone uniforme, le Quadtree stocke une seule valeur pour l'ensemble de la zone, ce qui réduit considérablement la quantité de données. [...]

[...] on peut dès lors se demander : Comment les arbres permettent-ils de compresser des images ? Nous allons voir dans une première partie une méthode de compression sans perte grâce au codage huffman et dans une deuxième partie, nous verrons une méthode de compression avec perte avec la structure de quadtree. I. Compression sans perte - L'arbre de Huffman Dans cette partie nous allons voir comment la méthode du codage huffman permet de compresser des images. Cette méthode a été créée par David Albert Huffman en 1952, durant sa thèse au MIT. [...]