Crédits à Calvin's Hobbies pour avoir poussé mon idée de défi dans la bonne direction.
Considérons un ensemble de points dans le plan, que nous appellerons des sites , et associons une couleur à chaque site. Maintenant, vous pouvez peindre tout le plan en coloriant chaque point avec la couleur du site le plus proche. C'est ce qu'on appelle une carte de Voronoï (ou diagramme de Voronoï ). En principe, les cartes de Voronoï peuvent être définies pour toute métrique de distance, mais nous utiliserons simplement la distance euclidienne habituelle r = √(x² + y²)
. ( Remarque: vous ne devez pas nécessairement savoir calculer et rendre l'un de ces éléments pour rivaliser dans ce défi.)
Voici un exemple avec 100 sites:
Si vous examinez une cellule, tous les points de cette cellule sont plus proches du site correspondant que de tout autre site.
Votre tâche consiste à approximer une image donnée avec une telle carte de Voronoï. Vous avez donné l'image dans un format graphique raster pratique, ainsi que d' un nombre entier N . Vous devez ensuite créer jusqu'à N sites et une couleur pour chaque site, de sorte que la carte de Voronoï basée sur ces sites ressemble le plus fidèlement possible à l'image d'entrée.
Vous pouvez utiliser l'extrait de pile au bas de ce défi pour rendre une carte de Voronoï à partir de votre sortie, ou vous-même si vous préférez, vous pouvez la restituer vous-même.
Vous pouvez utiliser des fonctions intégrées ou tierces pour calculer une carte Voronoï à partir d'un ensemble de sites (si vous en avez besoin).
Ceci est un concours de popularité, donc la réponse avec le plus grand nombre de votes nets gagne. Les électeurs sont encouragés à juger les réponses par
- comment bien les images originales et leurs couleurs sont approximées.
- comment l'algorithme fonctionne sur différents types d'images.
- comment l'algorithme fonctionne pour les petits N .
- si l'algorithme regroupe de manière adaptative des points dans des régions de l'image qui nécessitent davantage de détails.
Images d'essai
Voici quelques images pour tester votre algorithme (quelques-uns de nos suspects habituels, d'autres nouveaux). Cliquez sur les images pour les versions plus grandes.
La plage de la première rangée a été dessinée par Olivia Bell et incluse avec sa permission.
Si vous souhaitez relever un défi supplémentaire, essayez Yoshi avec un arrière - plan blanc et redressez sa ligne de ventre.
Vous pouvez trouver toutes ces images de test dans cette galerie imgur où vous pouvez toutes les télécharger au format zip. L'album contient également un diagramme de Voronoï aléatoire comme autre test. Pour référence, voici les données qui l’ont générée .
Veuillez inclure des exemples de diagrammes pour une variété d’images et de N différents , par exemple 100, 300, 1000, 3000 (ainsi que des corbeilles à coller conformes à certaines des spécifications de cellules correspondantes). Vous pouvez utiliser ou omettre les contours noirs entre les cellules à votre guise (cela peut sembler meilleur sur certaines images que sur d'autres). N'incluez cependant pas les sites (sauf dans un exemple séparé, si vous souhaitez expliquer le fonctionnement de l'emplacement de votre site, bien sûr).
Si vous souhaitez afficher un grand nombre de résultats, vous pouvez créer une galerie sur imgur.com , afin que la taille des réponses reste raisonnable. Vous pouvez également insérer des vignettes dans votre message et les lier à des images plus grandes, comme je l’ai fait dans ma réponse de référence . Vous pouvez obtenir les petites vignettes en ajoutant s
le nom de fichier dans le lien imgur.com (par exemple I3XrT.png
-> I3XrTs.png
). Aussi, n'hésitez pas à utiliser d'autres images de test, si vous trouvez quelque chose de bien.
Renderer
Collez votre sortie dans l'extrait de pile suivant pour rendre vos résultats. Le format de liste exact est sans importance, tant que chaque cellule est spécifiée par 5 nombres à virgule flottante dans l'ordre x y r g b
, où x
et y
sont les coordonnées du site de la cellule, et r g b
correspondent aux canaux de couleur rouge, vert et bleu de la plage 0 ≤ r, g, b ≤ 1
.
L'extrait de code fournit des options permettant de spécifier une largeur de trait des bords de la cellule et d'indiquer si les sites de cellules doivent être affichés (ce dernier principalement pour des fins de débogage). Notez toutefois que la sortie n'est restituée que lorsque les spécifications de la cellule changent. Par conséquent, si vous modifiez certaines des autres options, ajoutez un espace aux cellules ou à un autre élément.
Remerciements à Raymond Hill pour l’écriture de cette très belle bibliothèque de JS Voronoi .
Défis associés
la source
Réponses:
Python + scipy + scikit-image , échantillonnage pondéré du disque de Poisson
Ma solution est plutôt complexe. Je fais quelques pré-traitements sur l'image pour supprimer le bruit et obtenir une cartographie de l'intérêt de chaque point (en utilisant une combinaison d'entropie locale et de détection des contours):
Ensuite, je choisis des points d’échantillonnage en utilisant un échantillonnage de Poisson de Poisson avec une torsion: la distance du cercle est déterminée par le poids déterminé précédemment.
Ensuite, une fois que j'ai les points d'échantillonnage, je divise l'image en segments de voronoï et assigne la moyenne L * a * b * des valeurs de couleur à l'intérieur de chaque segment à chaque segment.
J'ai beaucoup d'heuristiques et je dois aussi faire un peu de calcul pour m'assurer que le nombre de points d'échantillon est proche de
N
. J'obtiensN
exactement en dépassant légèrement , puis en abandonnant certains points avec une heuristique.En termes de temps d’exécution, ce filtre n’est pas bon marché , mais aucune image ci-dessous ne prend plus de 5 secondes.
Sans plus tarder:
Images
Respectivement
N
100, 300, 1000 et 3000:la source
C ++
Mon approche est assez lente, mais je suis très contente de la qualité des résultats qu’elle donne, notamment en ce qui concerne la préservation des contours. Par exemple, voici Yoshi et la Cornell Box avec seulement 1000 sites chacun:
Il y a deux parties principales qui le font fonctionner. Le premier, incorporé dans la
evaluate()
fonction, prend un ensemble d'emplacements de sites candidats, y définit les couleurs optimales et renvoie un score pour le PSNR de la tessellation de Voronoï rendue par rapport à l'image cible. Les couleurs de chaque site sont déterminées en faisant la moyenne des pixels d’image cible couverts par la cellule autour du site. J'utilise l'algorithme de Welford pour calculer à la fois la meilleure couleur pour chaque cellule et le PSNR obtenu en un seul passage sur l'image en exploitant la relation entre la variance, la MSE et le PSNR. Cela réduit le problème à celui de trouver le meilleur ensemble d'emplacements de site sans considération particulière pour la couleur.La deuxième partie, incarnée dans
main()
, tente de trouver cet ensemble. Il commence par choisir un ensemble de points au hasard. Ensuite, à chaque étape, il supprime un point (va-et-vient) et teste un ensemble de points candidats aléatoires pour le remplacer. Celui qui donne le plus haut PSNR du groupe est accepté et conservé. Effectivement, le site accède à un nouvel emplacement et améliore l’image bit par bit. Notez que l'algorithme ne conserve pas intentionnellement l'emplacement d'origine en tant que candidat. Parfois, cela signifie que le saut diminue la qualité globale de l'image. Permettre que cela se produise aide à éviter de rester bloqué dans les maxima locaux. Il donne également un critère d'arrêt; le programme se termine après avoir franchi un certain nombre d'étapes sans améliorer le meilleur ensemble de sites trouvé jusqu'à présent.Notez que cette implémentation est assez basique et peut facilement prendre des heures de temps processeur, en particulier à mesure que le nombre de sites augmente. Il recalcule la carte complète de Voronoï pour chaque candidat et la force brute teste la distance à tous les sites pour chaque pixel. Comme chaque opération implique de supprimer un point à la fois et d’en ajouter un autre, les modifications apportées à l’image à chaque étape seront assez locales. Il existe des algorithmes pour la mise à jour incrémentielle efficace d'un diagramme de Voronoï et je pense qu'ils donneraient à cet algorithme une vitesse d'accélération considérable. Pour ce concours, cependant, j'ai choisi de garder les choses simples et brutales.
Code
Fonctionnement
Le programme est autonome et n'a pas de dépendances externes au-delà de la bibliothèque standard, mais nécessite que les images soient au format PPM binaire . J'utilise ImageMagick pour convertir les images en PPM, bien que GIMP et quelques autres programmes puissent le faire aussi.
Pour le compiler, enregistrez le programme sous
voronoi.cpp
et exécutez:Je pense que cela fonctionnera probablement sous Windows avec les versions récentes de Visual Studio, bien que je n’aie pas essayé cela. Vous devrez vous assurer que vous compilez avec C ++ 11 ou supérieur et qu'OpenMP est activé si vous le faites. OpenMP n'est pas strictement nécessaire, mais il aide beaucoup à rendre les temps d'exécution plus tolérables.
Pour l'exécuter, faites quelque chose comme:
Le fichier ultérieur sera mis à jour au fur et à mesure avec les données du site. La première ligne aura la largeur et la hauteur de l'image, suivies des lignes de valeurs x, y, r, g, b appropriées pour la copie et le collage dans le rendu Javascript dans la description du problème.
Les trois constantes en haut du programme vous permettent de l’accorder entre rapidité et qualité. Le
decimation
facteur grossit l'image cible lors de l'évaluation d'un ensemble de sites pour la couleur et le PSNR. Plus il est élevé, plus le programme sera exécuté rapidement. Le réglage sur 1 utilise l’image en pleine résolution. Lacandidates
constante contrôle le nombre de candidats à tester à chaque étape. Plus haut donne une meilleure chance de trouver un bon endroit pour sauter mais ralentit le programme. Enfin, iltermination
faut savoir combien d'étapes le programme peut franchir sans améliorer son résultat avant de quitter. L'augmenter peut donner de meilleurs résultats mais le faire prendre un peu plus longtemps.Images
N
= 100, 300, 1000 et 3000:la source
IDL, raffinement adaptatif
Cette méthode est inspirée du raffinement de maillage adaptatif issu de simulations astronomiques, ainsi que de la surface de subdivision . C'est le genre de tâche dont IDL est fier, ce que vous pourrez constater grâce au grand nombre de fonctions intégrées que j'ai pu utiliser. :RÉ
J'ai produit certains des éléments intermédiaires de l'image test yoshi sur fond noir, avec
n = 1000
.Tout d'abord, nous effectuons une échelle de gris de luminance sur l'image (en utilisant
ct_luminance
), et appliquons un filtre de Prewitt (prewitt
, voir wikipedia ) pour une bonne détection des contours:Vient ensuite le véritable travail de grognement: nous subdivisons l'image en 4 et mesurons la variance dans chaque quadrant de l'image filtrée. Notre variance est pondérée par la taille de la sous-division (qui dans cette première étape est égale), de sorte que les régions "énervées" à forte variance ne soient pas subdivisées de plus en plus petites. Ensuite, nous utilisons la variance pondérée pour cibler les subdivisions avec plus de détails et subdivisons chaque section riche en détails en 4 divisions supplémentaires, jusqu'à atteindre notre nombre cible de sites (chaque subdivision contient exactement un site). Comme nous ajoutons 3 sites à chaque itération, nous nous retrouvons avec des
n - 2 <= N <= n
sites.J'ai créé un fichier .webm du processus de subdivision pour cette image, que je ne peux pas intégrer, mais c'est ici ; la couleur dans chaque sous-section est déterminée par la variance pondérée. (J'ai réalisé le même type de vidéo pour le fond blanc yoshi, à des fins de comparaison, la table des couleurs étant inversée, elle passe au blanc au lieu du noir; c'est ici .) Le produit final de la subdivision ressemble à ceci:
Une fois que nous avons notre liste de subdivisions, nous parcourons chaque subdivision. L'emplacement final du site est la position du minimum de l'image de Prewitt, c'est-à-dire du pixel le moins "énervé", et la couleur de la section est la couleur de ce pixel; voici l'image originale, avec les sites marqués:
Ensuite, nous utilisons l’intégré
triangulate
pour calculer la triangulation de Delaunay des sites et l’intégrévoronoi
pour définir les sommets de chaque polygone de Voronoï, avant d’attirer chaque polygone dans un tampon d’image de sa couleur respective. Enfin, nous sauvegardons un instantané du tampon d’image.Le code:
Appelez ceci via
voro_map, n, image, output_filename
. J'ai également inclus unewrapper
procédure, qui passait en revue chaque image test et fonctionnait avec 100, 500 et 1000 sites.Résultats collectés ici , et voici quelques vignettes:
n = 100
n = 500
n = 1000
la source
Python 3 + PIL + SciPy, Fuzzy k-means
L'algorithme
L'idée centrale est que la classification par k-means divise naturellement l'image en cellules de Voronoï, car les points sont liés au centroïde le plus proche. Cependant, nous devons en quelque sorte ajouter les couleurs en tant que contrainte.
Nous convertissons d’abord chaque pixel dans l’ espace colorimétrique Lab , pour une meilleure manipulation des couleurs.
Ensuite, nous faisons une sorte de "détection de bord du pauvre". Pour chaque pixel, nous examinons ses voisins orthogonaux et diagonaux et calculons la différence de couleur au carré moyen. Nous trions ensuite tous les pixels en fonction de cette différence, les pixels les plus similaires à leurs voisins étant en tête de la liste et les pixels les plus dissemblables à leurs voisins à l'arrière (plus susceptibles d'être un point de contour). Voici un exemple pour la planète, plus le pixel est brillant, plus il est différent de ses voisins:
(Il y a un motif clair de type grille sur le rendu ci-dessus. Selon @randomra, cela est probablement dû à un encodage JPG avec perte ou à une compression imgur des images.)
Ensuite, nous utilisons cet ordre de pixels pour échantillonner un grand nombre de points à regrouper. Nous utilisons une distribution exponentielle, en donnant la priorité aux points qui sont plus proches et "intéressants".
Pour le clustering, nous choisissons d’abord des
N
centroïdes, choisis au hasard en utilisant la même distribution exponentielle que ci-dessus. Une itération initiale est effectuée et, pour chacune des grappes résultantes, nous attribuons une couleur moyenne et un seuil de variance de couleur. Ensuite, pour un certain nombre d'itérations, nous:(Cliquez pour agrandir)
Enfin, nous échantillonnons un grand nombre de points, cette fois en utilisant une distribution uniforme. En utilisant un autre arbre kd, nous assignons chaque point au centroïde le plus proche, formant des clusters. Nous estimons ensuite la couleur médiane de chaque groupe en utilisant un algorithme d’escalade en donnant les couleurs finales de nos cellules (idée de cette étape grâce à @PhiNotPi et @ MartinBüttner).
Remarques
En plus de générer un fichier texte pour l'extrait de code (
OUTFILE
), ifDEBUG
est défini surTrue
le programme permet également d'afficher et de remplacer les images ci-dessus. L'algorithme prend quelques minutes pour chaque image, c'est donc un bon moyen de contrôler les progrès sans ajouter beaucoup à la durée d'exécution.Exemples de sorties
N = 32:
N = 100:
N = 1000:
N = 3000:
la source
Mathematica, cellules aléatoires
C'est la solution de base, de sorte que vous obtenez une idée du minimum que je vous demande. Étant donné le nom du fichier (localement ou sous forme d'URL) in
file
et N inn
, le code suivant sélectionne simplement N pixels aléatoires et utilise les couleurs trouvées au niveau de ces pixels. C’est vraiment naïf et cela ne fonctionne pas incroyablement bien, mais je veux que vous réussissiez à le battre après tout. :)Voici toutes les images de test pour N = 100 (toutes les images sont liées à des versions plus grandes):
Comme vous pouvez le constater, ils sont essentiellement inutiles. Bien qu'elles puissent avoir une certaine valeur artistique, d'une manière expressionniste, les images originales sont à peine reconnaissables.
Pour N = 500 , la situation s’est un peu améliorée, mais il reste encore des artefacts très étranges, les images paraissent délavées et de nombreuses cellules sont gaspillées dans des régions sans détail:
À ton tour!
la source
Dimensions@ImageData
et pasImageDimensions
? Vous pouvez éviter le lentImageData
complètement en utilisantPixelValue
.Mathematica
Nous savons tous que Martin aime Mathematica, alors laissez-moi essayer avec Mathematica.
Mon algorithme utilise des points aléatoires à partir des bords de l'image pour créer un diagramme de voronoï initial. Le diagramme est ensuite prettifié par un ajustement itératif du maillage avec un simple filtre moyen. Cela donne des images avec une densité cellulaire élevée près des régions à contraste élevé et des cellules visuellement agréables sans angles fous.
Les images suivantes montrent un exemple du processus en action. Le plaisir est un peu gâché par le mauvais antialiasing de Mathematicas, mais nous obtenons des graphiques vectoriels, cela doit valoir quelque chose.
Cet algorithme, sans échantillonnage aléatoire, peut être trouvé dans la
VoronoiMesh
documentation ici .Images de test (100 300 100 000 000)
Code
la source
Graphics@Table[ Append[mp, VertexColors -> RGBColor /@ ImageValue[img, First[mp]]], {mp, MeshPrimitives[voronoiRelaxed, 2]}]
Python + SciPy + Emcee
L'algorithme que j'ai utilisé est le suivant:
L'algorithme semble très bien fonctionner. Malheureusement, il ne peut raisonnablement fonctionner que sur de petites images. Je n'ai pas eu le temps de prendre les points de Voronoï et de les appliquer aux images plus grandes. Ils pourraient être raffinés à ce stade. J'aurais aussi pu utiliser MCMC plus longtemps pour obtenir de meilleurs minima. Le point faible de l’algorithme est qu’il est plutôt coûteux. Je n’ai pas eu le temps d’augmenter au-delà de 1000 points et quelques images à 1000 points sont encore en train d’être affinées.
(clic droit et voir l'image pour obtenir une version plus grande)
Les liens vers des versions plus grandes sont http://imgur.com/a/2IXDT#9 (100 points), http://imgur.com/a/bBQ7q (300 points) et http://imgur.com/a/rr8wJ (1000 points)
Les images masquées non masquées ressemblent à ce qui suit. Des points aléatoires sont sélectionnés dans l'image si un nombre aléatoire est inférieur à la valeur de l'image (normée à 1):
Je posterai des images plus grandes et les points de Voronoï si je dispose de plus de temps.
Éditer: si vous augmentez le nombre de marcheurs à 100 * npts, modifiez la fonction de coût pour qu’elle soit l’un des carrés des déviations dans tous les canaux, et attendez longtemps (augmentation du nombre d’itérations pour sortir de la boucle). 200), il est possible de faire de bonnes images avec seulement 100 points:
la source
Utiliser l'énergie de l'image comme une carte de poids ponctuel
Dans mon approche de ce défi, je cherchais un moyen de cartographier la "pertinence" d'une zone d'image donnée par rapport à la probabilité qu'un point particulier soit choisi comme centre de Vroidoïro. Cependant, je voulais toujours préserver la sensation artistique du mosaïquage de Voronoï en choisissant au hasard des points d’image. De plus, je voulais utiliser de grandes images pour ne rien perdre du processus de sous-échantillonnage. Mon algorithme est à peu près comme ça:
Résultats
N
= 100, 500, 1000, 3000la source