Algorithme des K-Moyennes locales

Avant Dekker, on avait essayé un algorithme de post-clustering avec l'algorithme bien connu des K-moyennes. Celui-ci donne en théorie de bons résultats mais est d'une complexité trop grande pour être utilisé pour la quantification de la couleur sur des images.

Par contre, un algorithme de K-moyennes Locales (LKM), developpe par Verevka et Buchanan, produit de meilleurs résultats.

Il s'agit d'un cas particulier de SOM (self-organizing map). Mais contrairement à Neuquant, il utilise l'algorithme des K-moyennes locales dans la recherche des plus proches voisins, pour trouver rapidement une bonne approximation de la palette optimale.

Ce procédé est similaire aux techniques de gradient de quantification utilisées pour le codage des images à niveaux de gris. L'algorithme converge vers un minimum local, et ce plus rapidement qu'un algorithme de K-moyennes.

Comparez :

Les K-moyennes locales et ses rivaux : Médian-cut et Octree avec Klimt comme support.
Voyez les résultats sur Lena.

Pour plus d'informations...

Un article de Buchanan et Verevka en postscript
La page d'Oleg Verevka.

Revenir à l'index.