Je tombe parfois sur des photographies dont les couleurs me sont particulièrement plaisantes. Dans ces cas là, j'ai souvent envie d'analyser le bidule pour étudier quelle palette de couleurs a été utilisée pour donner un résultat aussi attirant, peut être pour essayer d'obtenir un résultat similaire durant la phase de post-traitement.

Il existe des outils qui permettent, à partir d'une photographie, d'extraire une palette de couleurs.

Une journée de désœuvrement, je me suis piqué de curiosité et ai tenté d'analyser le fonctionnement de ce type d'outils. Pour ceux que ça intéresse, voici un petit résumé.

Comment déterminer la palette de couleur d'une photo ?

Une photographie est composée de plusieurs centaines voire milliers de couleurs. Extraire une palette pertinente revient à réduire ces couleurs à 5 ou 6 entrées significatives, ce qui revient à essayer de reproduire l'image d'origine avec un nombre réduit de couleurs.

En informatique, ce genre de processus s'appelle la « segmentation d'une image », et revient à en simplifier le contenu en vue d'en faciliter l'analyse.

Il existe de très nombreuses recherches sur le sujet, car l'analyse d'image est un sujet complexe et qui présente d'innombrables applications industrielles : imagerie médicale, recherche astronomiques, sécurité, intelligence artificielle, etc.

Nous allons pour notre part nous pencher sur le sujet pour une seule et bonne raison : le fun ! Nous n'étudierons donc qu'un seul algorithme ; il existe bien évidemment d'innombrables de parvenir au même résultat.

L'algorithme des K-moyennes

L'algorithme des K-moyennes (k-means en anglais) est l'un des plus intuitifs et les plus visuels pour résoudre ce genre de problèmes. Le but de cet algorithme est de séparer des données en un nombre de sous-groupes distincts (on parle de « clusters », comme le fameux acteur Kluster Keaton).

Imaginez que vous soyez un supermarché, et vouliez segmenter votre clientèle en sous-groupes cohérents, afin de cibler vos campagnes publicitaires. Hop ! K-moyennes à la rescousse. Ici, au lieu de regrouper des clients en fonction de leurs habitudes d'achat, nous regroupons des pixels en fonction de leur couleur, ce qui est tout de même bien moins barbant.

Évidemment, si je décompose mon image en 150000 pixels bleu et trois pixels rose, ma palette n'est pas significative. Le but est donc d'obtenir des groupes les plus éloignés possible les uns les autres, avec des tailles à peu près équivalentes.

L'algorithme des k-moyennes fonctionne ainsi. Imaginons que je veuille obtenir, à partir d'une image, une palette de 5 couleurs (mais ce serait pareil avec 3, 15 ou 150 couleurs).

1) L'algo va commencer par sélectionner 5 pixels, n'importe où au hasard dans l'image, et note la couleur de chacun de ces pixels.

2) Ensuite, je vais parcourir tous les pixels de mon image un par un. Pour chaque pixel, je vais calculer quel est, parmi mes 5 pixels d'origine, celui qui a la couleur la plus proche. Je vais ainsi répartir tous mes pixels en cinq groupes distincts.

3) Une fois que j'ai fini de parcourir mon image, chaque pixel a été affecté à l'un des groupes. Je vais alors calculer la couleur moyenne de chaque groupe en fonction des pixels qui le composent.

4) Ces cinq couleurs moyennes vont devenir mes nouvelles couleurs de référence, et je vais répéter les opérations 2) et 3), jusqu'à ce que mes groupes de pixels soient à peu près stables.

Une fois terminé, j'ai découpé mon images en 5 plages de couleurs, qui constituent alors ma palette.

Jouons avec l'algorithme des k-moyennes

Nous avons atteint notre but, c'est à dire générer une palette de couleurs. Pour finir sur une note ludique, jouons un peu avec l'algorithme.

Pour calculer la distance entre deux pixels, nous avons considéré un seul paramètre : l'écart entre les deux couleurs. Mais rien ne nous empêche de considérer d'autres critères.

Conclusion

Je suis certain que vous aussi rêvez de vous amuser avec les k-moyennes. Essayez donc avec votre propre image (notez qu'il vous faudra pour cela un navigateur moderne (Firefox, Chrome, Safari, Opera…) et raisonnablement à jour). Notez que pour d'obscures raisons techniques, cela peut ne pas fonctionner en fonction de l'url de l'image. Les photos provenant de Flickr ou Wikimedia commons ne poseront pas de problèmes.

Dans le billet suivant, nous étudierons une implémentation concrète de l'algorithme.