Algorithme Octree
Cet algorithme réalise une partition de l'espace des couleurs. Cette partition est structurée selon un arbre dont la racine est l'espace R,G,B entier et les feuilles les couleurs.
L'algoritme regroupe certaines branches et certaines feuilles de manière récursive jusqu'à avoir un nombre de feuilles correspondant au nombre de couleurs desiré dans l'image finale.
On distingue trois phases :
1- Classification :
La racine de l'arbre est un cube de l'espace R,G,B contenant toutes les couleurs de l'image initiale.
A chaque noeud correspond un cube, que l'on divise en 8 petits cubes qui seront ses fils.
Cependant, lorsqu'un cube ne contient pas de couleurs de l'image originale, il est supprimé.
De plus, l'algorithme définit une profondeur maximale de l'arbre : (log2(taille de la palette finale).
Pour chaque pixel, l'algorithme parcourt l'arbre et trouve le noeud correspondant au cube (unique) dans lequel se trouve sa couleur.
A chaque noeud sont affectées les variables suivantes :
- n1 : nombre de pixels dont la couleur est dans le cube associé à ce noeud.
- n2 : nombre de pixels dont la couleur n'est pas representée dans un noeud situé plus bas dans l'arbre. (n2=0 au début mais change dans la phase de réduction).
- Sr, Sg et Sb : somme des composantes rouges (respectivement bleues et vertes) des couleurs qui ne sont pas representées plus bas dans l'arbre.
2- Réduction :
L'algorithme sélectionne la(les) feuille(s) de l'arbre pour laquelle n1 est le plus petit. Celle(s)-ci est(sont) "eliminée(s)" de l'arbre, et les variables n2, Sr, Sg et Sb sont modifiées pour le noeud père.
On recommence jusqu'à ce que le nombre de feuilles de l'arbre soit égal au nombre de couleurs de la palette finale.
3- Affectation :
A chaque couleur de l'image initiale est substituée la couleur représentative de la feuille de l'arbre où elle se trouve, ou en dessous de laquelle elle se trouvait. La couleur représentative d'une feuille a pour composantes Sr/n2, Sg/n2, Sb/n2.
Comparez l'algorithme Octree :
- avec l'algorithme des K-moyennes locales. Retrouvez Lena.
- avec en plus 2 variantes de l'algorithme Médian-cut. Admirez Klimt.
Pour plus d'informations...
Revenir à l'index.