Défi d’algorithme: Générer un jeu de couleurs à partir d’une image

Contexte

Je travaille donc sur une nouvelle itération d’une application Web. Et, nous avons constaté que nos utilisateurs sont obsédés par la paresse. Vraiment paresseux. En fait, plus nous travaillons pour eux, plus ils aiment le service. Une partie de l’application existante nécessite que l’utilisateur sélectionne un jeu de couleurs à utiliser. Cependant, nous avons une image (une capture d’écran du site Web de l’utilisateur), alors pourquoi ne pouvons-nous pas simplement satisfaire leur paresse et le faire pour eux? Réponse: Nous pouvons et ce sera un exercice de programmation amusant! 🙂

Le défi

Étant donné une image, comment créez-vous un schéma de couleurs correspondant? En d’autres termes, comment sélectionnez-vous les couleurs X principales dans une image (où X est défini par l’application Web). L’image utilisée dans notre situation particulière est une capture d’écran du site Web de l’utilisateur, prise en pleine résolution (par exemple, 1280×1024). ( Remarque: décrivez simplement votre algorithme – il n’est pas nécessaire de publier un pseudo-code.)

Points bonus (points de rues, pas de points SO réels) pour:

  • Décrire un algorithme simple mais efficace. Code est la façon dont nous créons – restz simple et beau.
  • Permettre à l’utilisateur de modifier la palette de couleurs en fonction de diverses «humeurs» telles que «coloré», «shiny», «atténué», «profond», etc. (a la Kuler )
  • Décrire une méthode permettant de déterminer de manière fiable la couleur de texte principale utilisée dans la capture d’écran du site Web (cela nécessitera probablement son propre algo séparé).

Inspiration

Il existe plusieurs sites existants qui remplissent une fonction similaire. N’hésitez pas à les vérifier et à vous demander: “Comment pourrais-je reproduire cela? Comment pourrais-je l’améliorer?”

  • http://www.pictaculous.com/
  • http://www.cssdrive.com/imagepalette/index.php
  • http://kuler.adobe.com/#create/fromanimage

  1. Pour trouver les couleurs X principales, screencap l’application. Exécutez un histogramme de couleur sur l’image. Les X couleurs supérieures dans l’histogramme sont le thème. Edit: si des dégradés sont utilisés, vous voudrez choisir des “pics” de couleurs distincts; c’est-à-dire que vous pouvez avoir tout un tas de couleurs autour de “orange” si l’orange est l’une des couleurs principales utilisées dans les dégradés. Effectivement, il suffit d’appliquer une certaine distance entre vos couleurs choisies dans l’histogramme.

  2. Il est préférable de modifier le schéma de couleurs dans l’espace HSV; Convertissez vos couleurs en espace HSV et, si les utilisateurs le souhaitent, augmentez la valeur si vous souhaitez qu’il soit plus “coloré”, augmentez la saturation, etc.

  3. La meilleure façon de déterminer la couleur du texte est de caractériser les zones de grande variabilité (haute fréquence dans l’espace de Fourier). Dans ces zones, vous devriez avoir soit: deux couleurs, texte et arrière-plan, auquel cas votre texte est la couleur la moins utilisée; ou vous aurez plusieurs couleurs, couleurs de texte et images d’arrière-plan, auquel cas la couleur du texte est la couleur la plus courante.

Vous pouvez regarder:

https://github.com/dcollien/Dreamcoat

qui fait cela dans CoffeeScript (café alphabétisé, donc c’est bien documenté)

Démo ici: http://dcollien.github.io/Dreamcoat/test.html

Il a à la fois une approche de quantification des couleurs et une approche KMeans qui sont combinées.

La quantification des couleurs est le même processus que celui utilisé pour choisir la palette pour les GIF de couleur basse. Pour obtenir une palette de couleurs à partir d’une image photographique, j’ai utilisé le quantize.js de Nick Rabinowitz, basé sur la MMCQ (quantification de la coupe médiane modifiée) de Leptonica.

meemoo capture d'écran Application web en direct , à propos de .

Je le fais pour trouver la palette utilisée pour les images (des illustrations).

  1. Je commence avec imagemagick et redimensionne une grande image à une taille exploitable (c.-à-d. 400 px dans la plus grande dimension).

  2. Parcourez chaque pixel présent dans l’image redimensionnée, lisez les valeurs RVB pour chaque pixel, convertissez le RVB en HSB et stockez les valeurs HSB dans un tableau.

  3. Pour chaque couleur de pixel trouvée, je divise ensuite la plage de teinte (0,255) par 16, la plage de saturation (0,100) par 10 et la plage de luminosité (0,100) par 10. Arrondissez le résultat en nombre entier. Cela permet de regrouper les pixels en catégories de couleurs similaires.

    Donc, un pixel avec HSB de 223,64,76 serait dans la catégorie 14,6,8

    Dans chaque catégorie, vous pouvez toujours trouver la couleur exacte de chaque pixel, mais la plupart du temps, les catégories elles-mêmes correspondent à la couleur de l’image source.

    Choisissez de diviser le HSB en divisions plus fines si vous souhaitez une meilleure réplication des couleurs à partir des catégories. c’est à dire. diviser chaque H, S, B par 8,5,5 au lieu de 16,10,10.

  4. Comptez les catégories de couleurs les plus courantes, sortingez et affichez. Je rejette les catégories de couleurs avec très peu de pixels.

Remarque: cette fonction est vraiment conçue pour les illustrations comportant très peu de pixels avec des valeurs de couleur identiques (peintures avec des ombres et des dégradés).

Pour la plupart, une page HTML a probablement plus de pixels qui correspondent exactement à une valeur de couleur spécifique (c.-à-d. Couleur d’arrière-plan, couleur du texte, etc.).

  1. Divisez l’image de l’écran en une grid de plusieurs rectangles, dans une “grid” n par m, chacune avec la largeur (largeur totale / n) et la hauteur (hauteur totale / m).

    1a. Atsortingbuez une pondération aux zones les plus visibles de l’écran, telles que la zone centrale gauche.

    1b. Pour chaque rectangle, assignez les pixels dans un espace de ( couleur , fréquence )

  2. Pour chaque rectangle R, dissortingbution de fréquence f_R et poids W_R:

    2a. Déterminez la couleur du schéma i (par exemple, i = 1 <-> couleur de fond) en balayant la “fréquence supérieure”, la “deuxième fréquence” (par exemple, f_R [ i ,:]) pour chaque bloc.

    2b. Pour chaque i , mettez-le dans un tableau de résultats ( color_i , score ) où score = f_R [ i , “fréquence”] * W_R

    2c. Le meilleur buteur pour chacun sera la couleur de l’ i- ème schéma.

Théoriquement, si vous avez beaucoup de “bleu sur blanc” ou de “rouge sur noir”, vous devriez par exemple avoir le primaire blanc, le secondaire bleu ou le primaire noir, le rouge secondaire.

Pour votre couleur de texte, basez-la directement sur un calcul de couleur d’arrière-plan ou choisissez une couleur secondaire, et si la différence V de HSV est trop faible, basez la couleur de la couleur de schéma calculée, mais augmentez la valeur V.

PseudoCode:

float[][] weights = { { 1.0, 3.0, 5.0, 5.0, 3.0, 1.0, 1.0, 1.0, 1.0 }, { 2.0, 6.0, 7.0, 7.0, 6.0, 2.0, 3.0, 3.0, 2.0 }, { 2.0, 8.0, 9.0, 9.0, 7.0, 3.0, 6.0, 6.0, 3.0 }, { 2.0, 8.0, 9.0, 9.0, 7.0, 2.0, 3.0, 3.0, 2.0 }, { 2.0, 7.0, 9.0, 9.0, 7.0, 2.0, 1.0, 1.0, 1.0 }, { 2.0, 6.0, 7.0, 7.0, 6.0, 2.0, 3.0, 3.0, 1.0 }, { 1.0, 3.0, 5.0, 5.0, 3.0, 2.0, 6.0, 6.0, 2.0 }, { 1.0, 1.0, 2.0, 2.0, 1.0, 2.0, 6.0, 6.0, 2.0 }, { 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 3.0, 3.0, 1.0 } }; // Leave the following implementations to the imagination: void DivideImageIntoRegions( Image originalImage, out Image[][] regions ); void GetNthMostCommonColorInRegion( Image region, int n, out Color color ); TKey FindMaximum( Map map ); // The method: Color[] GetPrimaryScheme( Image image, int ncolors, int M = 9, int N = 9 ) { Color[] scheme = new Color[ncolors]; Image[][] regions = new Image[M][N]; DivideImageIntoRegions( image, regions ); for( int i = 0; i < ncolors; i++ ) { Map colorScores = new Map(); for( int m = 0; m < M; m++ ) for( int n = 0; n < N; n++ ) { Color theColor; GetNthMostCommonColorInRegion( region, i, theColor ); if( colorScores[theColor] == null ) { colorScores[theColor] = 0; } colorScores[theColor] += weights[m][n]; } scheme[i] = FindMaximum( colorScores ); } return scheme; } 

En regardant ce qui précède, il est clair que s'il y a une région avec peu de variabilité, elle aura la même couleur la plus commune que la couleur la plus courante. Pour ajuster, la deuxième couleur la plus courante dans un tel cas pourrait être nulle, ce qui pourrait être évité:

  if( theColor != null ) continue; if( colorScores[theColor] == null ) { colorScores[theColor] = 0; } colorScores[theColor] += weights[m][n]; } 

Le nom du type d’algorithme que vous souhaitez est la quantification des couleurs .

Malheureusement, je n’ai pas de code source disponible pour vous, mais je suis sûr qu’une recherche sur Google pourrait faire évoluer la situation.

En particulier, l’article du Dr. Dobb’s Journal sur le sujet semble prometteur.

Semblable à la solution de McWafflestix, les détails devront être peaufinés, mais mon approche générale serait …

(Je suis d’accord que HSV est le bon espace)

  1. Prenez un histogramme de l’image, filtrez-le pour lisser le bruit et trouvez le score le plus élevé où V et S se trouvent dans une gamme (éventuellement dynamic) de couleurs probables. Un oiseau rouge sur un ciel bleu exigera que nous soyons assez intelligents pour ne pas baser notre schéma sur le bleu, mais sur le rouge. Cela peut nécessiter quelques suppositions sur la composition des photos, comme l’parsing «centrée dans le cadre» et «la règle des tiers» pourrait vous donner une probabilité qu’une couleur soit pertinente. Indépendamment, c’est notre couleur de base.

  2. Sur le modèle de Kuler, calculez les couleurs qui complètent la base en déplaçant la roue chromatique. Des points supplémentaires pour un complément calculé s’il apparaît également en évidence dans l’histogramme de l’étape 1.

  3. Utilisez la couleur de base et les compliments calculés pour obtenir des couleurs complémentaires agréables, telles que des versions plus claires et plus sombres de chacune, plus ou moins saturées, etc.

Il y a déjà beaucoup de bonnes suggestions pour trouver les couleurs primaires et j’essaierais des approches similaires. Pour trouver la couleur du texte, j’ai une autre suggestion.

Calculez l’histogramme pour chaque ligne de l’image de haut en bas. Chaque fois que vous atteignez la ligne de base d’une ligne, la fréquence de la couleur du texte doit être fortement diminuée. La fréquence restra basse jusqu’à ce que vous atteigniez les lettres majuscules de la ligne suivante suivies d’une seconde étape lorsque vous atteindrez les lettres minuscules.

S’il y a un autre pic fort qui devient encore plus grand lorsque vous atteignez la ligne de base, vous avez trouvé la couleur d’arrière-plan. Un arrière-plan dégradé lisse ce pic et les modifications des pics – lorsque vous entrez ou quittez une nouvelle ligne – seront lissées par antialiasing.

Je suis un peu en retard, mais je mettrais en œuvre une carte Kohonen (http://en.wikipedia.org/wiki/Self-organizing_map) dans un espace couleur 3D. Le nombre de points sur la carte correspond au nombre de couleurs distinctes que vous souhaitiez pour votre palette, puis formez votre carte en utilisant tous les pixels de l’image. Je n’ai pas essayé moi-même mais je suis sûr que quelqu’un d’autre a déjà pensé à ça.

Vous trouverez ci-dessous quelques suggestions et discussions concernant différentes approches pour générer un jeu de couleurs à partir d’une image:

Tout d’abord, intégrez / tracez vos pixels dans un espace colorimésortingque. Cela peut être RVB, HSL ou un autre espace de couleur. Vous pouvez ensuite utiliser l’une des méthodes suivantes pour générer un jeu de couleurs:

  1. Création d’un histogramme de l’espace colorimésortingque – Cela implique de diviser l’espace en une grid et de compter les pixels dans chaque cellule de la grid. Sélectionnez les N cellules les plus élevées (compartiments d’histogramme) avec le plus de pixels et faites la moyenne des pixels dans chacun pour produire une couleur par cellule. Cela peut être votre schéma de couleurs.

  2. Median Cut ou une autre technique de partitionnement de l’espace – Il s’agit d’une belle amélioration par rapport à la première, car elle divisera l’espace en examinant les données.

  3. Clustering Pixels – Regroupez les pixels en groupes en utilisant l’une des nombreuses techniques de clustering (k-means, moyenne-shift, etc.). Faites ensuite la moyenne des pixels dans chaque groupe pour générer un jeu de couleurs.

J’ai écrit un article plus détaillé sur les trois approches ci-dessus

J’ai également écrit une application Web interactive qui vous permet de charger une image et de créer une palette de couleurs en utilisant l’une des trois approches ci-dessus. Vous pouvez trouver le code pour cela sur github

Moyenne de la teinte, de la saturation et de la luminosité séparément tout en conservant les valeurs min / max.

Verrouillez la teinte cible de toutes les couleurs à la moyenne et interpolez la saturation et la luminosité des points x entre les limites. Cela devrait renvoyer un schéma avec une dissortingbution de couleur identique à la photo mais avec une variation simple. Peut-être que vous aurez même le look Apple.

J’espère que vous n’obtiendrez pas 3 nuances de vomi de chien.