Compresser une image à l'aide d'un QuadTree

Bonjour à tous,

Je souhaiterais réaliser un petit algorithme de compression d'image et j'aurais besoin de vos conseils et de votre aide pour l'implémenter en Java.

Principe de l'algorithme

Commençons par donner quelques explications…

Objectif de l'algorithme

Réduire le poids d'une image (c'est un algorithme de compression). On donne une image en entrée qui fait une taille de XXX. On obtient une image en sortie, qui fait la même taille.

Mais l'image de sortie est calculée à partir d'un arbre qui lui est issu de la compression. Et c'est précisément cet arbre qui a une taille plus petite que l'image.

Fonctionnement

On crée un QuadTree (arbre à 4 noeuds). Celui-ci sera utile, lisez la suite. Un noeud peut être un noeud-RGB, auquel cas il représente un bloc de pixel(s) et possède donc les attributs RGB. Un noeud peut être également un noeud-Children, auquel cas il ne contient pas d'attribut RGB, mais un attribut "children" qui est une liste de 4 noeuds (noeuds-Children ou bien noeuds-RGB en différentes proportions dans la liste ou bien uniquement des noeuds-Children ou bien uniquement des noeuds-RGB).

On divise l'image en 4 gros blocs : 2*2 (2 lignes et 2 colonnes quoi ). Je dis "gros blocs" car chacun d'eux est constitué de plusieurs pixels. Ces 4 gros blocs sont de même taille (l'image étant un carré de hauteur divisible par 2 on va dire).

On parcourt chacun des 4 blocs de l'image.

1. Si le bloc courant possède des pixels de même couleur, alors on crée un noeud-RVB ; ce noeud possédera les attributs RVB initialisés aux RVB du bloc courant. Puis on ajoute ce noeud dans l'arbre.

2. Sinon : on crée un noeud-Children ; ce noeud n'aura pas de RVB, mais son attribut "children" sera initialisé (ie. : = new ArrayList<>(4)). On indique à l'arbre que les prochains noeuds-RVB ou noeud-Children seront à placer dans celui-ci. Enfin, on fait un appel récursif : on divise ce bloc en 4 gros blocs, on les parcourt, si le bloc courant possède [blablabla…].

A la fin de ce processus, on devrait normalement tomber sur des "gros blocs" de 1*1 pixel, ce qui veut évidemment dire que le point n°2 ne sera pas lu : seul le point n°1 le sera. C'est donc une condition d'arrêt de la récursivité.

On peut faire un parallèle avec…

Un algorithme de flou, c'est un peu le même principe finalement.

Reconstruction de l'image

A l'issue de tout ce que j'ai expliqué, on obtient juste un QuadTree rempli avec des noeuds-RGB. Mais l'image en soi n'est pas retouchée.

L'idée est de créer une nouvelle image à partir de ce QuadTree.

La nouvelle image a la même taille que l'ancienne si je ne m'abuse. Par contre : la taille du QuadTree est bien plus petite car les noeuds-RGB peuvent très bien représenter chacun un gros bloc de pixelS !

On parcourt donc ce QuadTree, et quand on trouve un noeud-RGB, on le dessine, en tenant compte de sa taille. Quand on trouve un noeud-Children, on parcourt ses fils.

Mes questions

1. Comme vous avez pu le constater, je n'ai pas bien compris la reconstruction de l'image… Si vous pouviez m'aiguiller ce sera sympa !

2. Est-ce que vous avez déjà réalisé cet algo ? Est-ce très fastidieux à faire ? Y aurait-il moyen de m'inspirer de codes déjà faits, ou de pseudo-codes, pour que je puisse comprendre rapidement comment mettre tout ça en place ?

Merci d'avance et bonne continuation à vous !

Comme vous avez pu le constater, je n'ai pas bien compris la reconstruction de l'image…

C'est quoi que tu n'as pas compris ?

Est-ce que vous avez déjà réalisé cet algo ? Est-ce très fastidieux à faire ? Y aurait-il moyen de m'inspirer de codes déjà faits, ou de pseudo-codes, pour que je puisse comprendre rapidement comment mettre tout ça en place ?

Des quad-tree ? Oui. Dans ce cadre ? Non (car c'est probablement un exo sympa mais risque de pas être terriblement efficace sur une photo, sur un dessin beaucoup plus).

Peux-tu détailler ce que tu ne comprends pas ?

Bonjour Kje, désolé du retard !

Alors j'ai mieux réfléchi à l'algo de reconstruction de l'image à partir du Quad Tree, dont j'ai semble-t-il réussi la construction.

En fait cet algo fonctionne assez bien apparemment, sauf notamment lorsqu'un lui donne une image 32x32 comme celle-ci (carré noir sur fond blanc) :

Lorsque je donne cette image à mon programme, il y a dépassement du nombre de pixels de l'image : autrement dit, mon programme tente de colorier un ou plusieurs pixels de l'image qui n'existent pas.

Mon algo est (par manque de temps, je vais le résumer en français - ce soir, je détaillerais davantage) :

1. Soit une image de taille correcte (ie. : telle que tous les noeuds-feuilles de l'arbre puissent être dessinés dessus) ;

2. On parcourt noeud par noeud le quadtree ;

3. Si celui-ci est de type "non-feuille" (et possède donc 4 noeuds-enfants), on parcourt chacun de ses enfants ;

4. Sinon, on colorie le pixel de l'image qui correspond à ce noeud.

Je rappelle qu'un noeud du quad-tree est soit un pixel (feuille), soit un groupe de noeuds (donc de pixels ou de groupe) (non-feuille).

Mon algo, en d'autres termes, parcourt de gauche à droite puis de haut en bas chaque pixel de chaque noeud du quad-tree. Ie. : d'abord le bloc haut-gauche, puis le bloc haut-droit, puis le bloc bas-gauche et enfin le bloc bas-droit (l'image est découpée en 4blocs/noeuds puisque j'utilise un quad-tree).

Quand j'arrive en bas à droite du bloc haut-gauche, je replace l'ordonnée tout en haut pour pouvoir parcourir le bloc haut-droit à partir de son tout premier pixel en haut à gauche.

Même principe pour les blocs haut-droit (cette fois-ci , c'est juste l'abscisse), et bas-gauche (l'ordonnée est remontée similairement au bloc haut-gauche).