Utilisateur:E.Le Morvan/Brouillon

• Pascal Boyer, Petit compagnon des nombres et de leurs applications, Calvage et Mounet, 2019, 648 p. (ISBN 978-2-916352-75-6)
• musée de la pharmacie de Heidelberg (de)

Réduction du nombre de couleurs d'une image

Portrait d'Ada Lovelace peint par Alfred Edward Chalon en 1840. L'image non retouchée comprend environ 700 000 pixels qui affichent près de 131 000 couleurs différentes.

L'algorithme des k-moyennes peut être utilisé pour réduire le nombre de couleurs d'une image sans que cela ne nuise trop à sa qualité. L'espace de couleur du système RGB de codage des couleurs consiste essentiellement à représenter une couleur par trois nombres entiers compris entre 0 et 255 qui représentent les intensités respectives du rouge, du vert et du bleu dans la couleur à afficher. Cela donne 256³ couleurs possibles, soit environ 16 millions. L'œil humain non-entraîné peine à distinguer autant de couleurs et il est donc possible de remplacer deux couleurs proches par une seule sans grande perte de qualité ; ce peut être utile à des fins de compression ou pour permettre l'affichage optimal d'une image sur un écran ou une imprimante n'offrant pas une grande variété de couleurs.

L'algorithme des k-moyennes peut être utilisé pour réduire le nombre de couleurs (en) à seulement k couleurs. On initialise une liste de k couleurs puis chaque pixel de l'image est associé à celle des k couleurs dont il est le plus proche. La couleur de tous les pixels d'une catégorie est alors remplacée par la moyenne de leurs couleurs. Le partitionnement des pixels puis le remplacement de leur couleur par une couleur moyenne est itéré jusqu'à ce que l'image ne soit plus modifiée par le procédé.

Les paramètres qui influent sur le résultat sont :

• la valeur de k ;
• le choix d'initialisation des couleurs ;
• l'arrêt éventuel de l'exécution avant que les couleurs ne soient complètement stabilisées.

Nombre d'itérations

La complexité de l'algorithme des k-moyennes est linéaire en le nombre d'itérations des partitionnements et des moyennes. Cependant le nombre d'itérations à effectuer avant la convergence de l'image, bien que généralement bas, peut être très élevé dans le pire des cas. L'influence des dernières itérations peuvent cependant ne pas engendrer de grandes différences de rendu.

• Évolution d'une image réduite à 15 couleurs au fil des itérations de l'algorithme.
• 
  Initialisation avec couleurs aléatoires.
• 
  Fin de l'itération 1.
• 
  Fin de l'itération 2.
• 
  Fin de l'itération 3.
• 
  Fin de l'itération 4.
• 
  Fin de l'itération 5.
• 
  Résultat final (itération 48).

Choix d'initialisation des couleurs

L'exécution de l'algorithme des k-moyennes est dépendante du choix d'initialisation des k couleurs qui servent à effectuer la première partition. Deux initialisations différentes peuvent en effet donner deux résultats différents dont la proximité n'est en théorie pas garantie. En pratique cependant deux exécutions initialisées différemment donneront généralement un résultat proche.

Deux initialisations différentes de l'algorithme pour une réduction à 15 couleurs. Première initialisation. Seconde initialisation.

Les deux résultats finaux correspondant aux deux initialisations ci-contre. Premier rendu. (48 itérations) Second rendu. (50 itérations)

Choix du nombre de couleurs

Le choix de la valeur de k résulte généralement d'un compromis entre d'une part le fait de ne pas avoir de couleurs superflues et d'autre part le fait de limiter la baisse de qualité de l'image. Dans la pratique, on choisit généralement k de telle sorte qu'une valeur plus petite diminuerait sensiblement la qualité de l'image tandis qu'une valeur plus grande ne l'améliorerait que peu.

Ainsi l'exemple ci-dessous montre qu'en dessous de 10 couleurs, changer la valeur de k modifie grandement le rendu final tandis que l'on n'observe que peu de variations lorsque k est au-delà de 15. Un bon compromis se situerait donc pour k entre 10 et 15.

• Différence de rendu suivant le nombre k de couleurs à réduire.
• 
  2 couleurs.
  (17 itérations)
• 
  5 couleurs.
  (42 itérations)
• 
  10 couleurs.
  (48 itérations)
• 
  15 couleurs.
  (48 itérations)
• 
  20 couleurs.
  (79 itérations)
• 
  25 couleurs.
  (144 itérations)