Dank an Calvins Hobbys, die meine Herausforderungsidee in die richtige Richtung gelenkt haben.
Betrachten Sie eine Reihe von Punkten in der Ebene, die wir Sites nennen , und ordnen Sie jeder Site eine Farbe zu. Jetzt können Sie die gesamte Ebene malen, indem Sie jeden Punkt mit der Farbe der nächstgelegenen Stelle einfärben. Dies wird als Voronoi-Karte (oder Voronoi-Diagramm ) bezeichnet. Grundsätzlich können Voronoi-Karten für jede Entfernungsmetrik definiert werden, aber wir verwenden einfach die übliche euklidische Entfernung r = √(x² + y²)
. ( Hinweis: Sie müssen nicht unbedingt wissen, wie man eines davon berechnet und rendert, um in dieser Herausforderung bestehen zu können.)
Hier ist ein Beispiel mit 100 Sites:
Wenn Sie eine Zelle betrachten, befinden sich alle Punkte in dieser Zelle näher an der entsprechenden Stelle als an einer anderen Stelle.
Ihre Aufgabe ist es, ein bestimmtes Bild mit einer solchen Voronoi-Karte anzunähern. Sie sind das Bild in jedem geeigneten Rastergrafikformat, sowie eine ganze Zahl gegeben N . Sie sollten dann bis zu N Standorte und eine Farbe für jeden Standort erstellen , sodass die auf diesen Standorten basierende Voronoi-Karte dem Eingabebild so nahe wie möglich kommt.
Sie können das Stapel-Snippet unten in dieser Herausforderung verwenden, um eine Voronoi-Karte aus Ihrer Ausgabe zu rendern, oder Sie können sie selbst rendern, wenn Sie dies bevorzugen.
Sie können integrierte Funktionen oder Funktionen von Drittanbietern verwenden, um eine Voronoi-Karte von einer Reihe von Standorten aus zu berechnen (falls erforderlich).
Dies ist ein Beliebtheitswettbewerb, daher gewinnt die Antwort mit den meisten Netto-Stimmen. Die Wähler werden aufgefordert, die Antworten nach zu beurteilen
- wie gut die Originalbilder und ihre Farben angenähert sind.
- Wie gut der Algorithmus auf verschiedenen Arten von Bildern funktioniert.
- wie gut der Algorithmus funktioniert für kleine N .
- ob der Algorithmus Punkte in Bereichen des Bildes, die mehr Details erfordern, adaptiv gruppiert.
Bilder testen
Hier sind einige Bilder zum Testen Ihres Algorithmus (einige unserer üblichen Verdächtigen, einige neue). Klicken Sie auf die Bilder für größere Versionen.
Der Strand in der ersten Reihe wurde von Olivia Bell gezeichnet und mit ihrer Erlaubnis eingeschlossen.
Wenn Sie eine zusätzliche Herausforderung möchten, probieren Sie Yoshi mit einem weißen Hintergrund aus und achten Sie darauf, dass seine Bauchlinie stimmt.
Sie finden alle diese Testbilder in dieser Bildergalerie, wo Sie sie alle als zip-Datei herunterladen können. Das Album enthält auch ein zufälliges Voronoi-Diagramm als weiteren Test. Als Referenz hier sind die Daten, die es erzeugt haben .
Bitte fügen Sie Beispieldiagramme für eine Vielzahl verschiedener Bilder und N , z. B. 100, 300, 1000, 3000 (sowie Pastebins zu einigen der entsprechenden Zellenspezifikationen) bei. Sie können schwarze Ränder zwischen den Zellen nach Belieben verwenden oder weglassen (dies kann auf einigen Bildern besser aussehen als auf anderen). Fügen Sie die Websites jedoch nicht hinzu (außer in einem separaten Beispiel, wenn Sie natürlich erläutern möchten, wie Ihre Website-Platzierung funktioniert).
Wenn Sie eine große Anzahl von Ergebnissen anzeigen möchten , können Sie auf imgur.com eine Galerie erstellen , um die Größe der Antworten angemessen zu halten. Alternativ können Sie Thumbnails in Ihren Beitrag einfügen und sie mit größeren Bildern verknüpfen, wie ich es in meiner Referenzantwort getan habe . Sie können die kleinen Thumbnails erhalten, indem Sie s
an den Dateinamen im Link imgur.com anhängen (z . B. I3XrT.png
-> I3XrTs.png
). Sie können auch andere Testbilder verwenden, wenn Sie etwas Schönes finden.
Renderer
Fügen Sie Ihre Ausgabe in das folgende Stapel-Snippet ein, um Ihre Ergebnisse zu rendern. Das genaue Listenformat ist irrelevant, solange jede Zelle durch 5 Gleitkommazahlen in der Reihenfolge angegeben wird x y r g b
, in der x
und y
die Koordinaten des Zellstandorts und r g b
die roten, grünen und blauen Farbkanäle im Bereich sind 0 ≤ r, g, b ≤ 1
.
Das Snippet bietet Optionen zum Angeben einer Linienbreite der Zellenkanten und zum Anzeigen der Zellenstandorte (letztere hauptsächlich zu Debugging-Zwecken). Beachten Sie jedoch, dass die Ausgabe nur dann neu gerendert wird, wenn sich die Zellenspezifikationen ändern. Wenn Sie also einige der anderen Optionen ändern, fügen Sie den Zellen ein Leerzeichen hinzu.
Dank an Raymond Hill für das Schreiben dieser wirklich schönen JS Voronoi-Bibliothek .
Verwandte Herausforderungen
quelle
Antworten:
Python + Scipy + Scikit-Image , gewichtetes Poisson-Disc-Sampling
Meine Lösung ist ziemlich komplex. Ich bearbeite das Bild vorab, um Rauschen zu entfernen und eine Abbildung zu erhalten, wie 'interessant' jeder Punkt ist (unter Verwendung einer Kombination aus lokaler Entropie und Kantenerkennung):
Dann wähle ich Abtastpunkte mit einer Poissonscheibensampling mit einer Verdrehung: Die Entfernung des Kreises wird durch das zuvor bestimmte Gewicht bestimmt.
Sobald ich die Abtastpunkte habe, teile ich das Bild in voronoi Segmente auf und ordne jedem Segment den L * a * b * Durchschnitt der Farbwerte in jedem Segment zu.
Ich habe viele Heuristiken und ich muss auch ein bisschen rechnen, um sicherzustellen, dass die Anzahl der Stichprobenpunkte in der Nähe liegt
N
. Ich bekommeN
genau durch ein leichtes Überschießen und dann einige Punkte mit einer Heuristik fallen.In Bezug auf die Laufzeit ist dieser Filter nicht billig , aber es dauerte mehr als 5 Sekunden, bis ein Bild unten erstellt wurde.
Ohne weiteres:
Bilder
Jeweils
N
100, 300, 1000 und 3000:quelle
C ++
Mein Ansatz ist ziemlich langsam, aber ich bin sehr zufrieden mit der Qualität der erzielten Ergebnisse, insbesondere in Bezug auf die Kantenschonung. Hier sind zum Beispiel Yoshi und die Cornell Box mit jeweils nur 1000 Standorten:
Es gibt zwei Hauptteile, die es ticken lassen. Die erste Funktion, die in der
evaluate()
Funktion enthalten ist, nimmt eine Reihe von Standortkandidaten auf, legt die optimalen Farben für sie fest und gibt eine Punktzahl für das PSNR der gerenderten Voronoi-Tesselation im Vergleich zum Zielbild zurück. Die Farben für jede Site werden durch Mitteln der Zielbildpixel bestimmt, die von der Zelle um die Site abgedeckt werden. Ich verwende den Welford-Algorithmus , um sowohl die beste Farbe für jede Zelle als auch das resultierende PSNR mit nur einem Durchgang über das Bild zu berechnen, indem ich die Beziehung zwischen Varianz, MSE und PSNR ausnütze. Dies reduziert das Problem auf die Suche nach den besten Standorten ohne besondere Berücksichtigung der Farbe.Der zweite Teil, verkörpert in
main()
, versucht diese Menge zu finden. Es beginnt mit der zufälligen Auswahl einer Reihe von Punkten. Dann wird in jedem Schritt ein Punkt entfernt (Round-Robin) und ein Satz zufälliger Kandidatenpunkte getestet, um ihn zu ersetzen. Derjenige, der den höchsten PSNR des Bündels ergibt, wird akzeptiert und beibehalten. Tatsächlich bewirkt dies, dass die Site an eine neue Position springt und das Bild im Allgemeinen Stück für Stück verbessert. Beachten Sie, dass der Algorithmus absichtlich nicht die ursprüngliche Position als Kandidat beibehält. Manchmal bedeutet dies, dass der Sprung die Gesamtbildqualität verringert. Wenn Sie dies zulassen, können Sie vermeiden, dass lokale Maxima eingehalten werden. Es gibt auch ein Anhaltekriterium; Das Programm wird beendet, nachdem eine bestimmte Anzahl von Schritten ausgeführt wurde, ohne die bisher besten gefundenen Websites zu verbessern.Beachten Sie, dass diese Implementierung ziemlich einfach ist und Stunden CPU-Kernzeit in Anspruch nehmen kann, insbesondere wenn die Anzahl der Sites zunimmt. Es berechnet die komplette Voronoi-Karte für jeden Kandidaten neu und Brute Force testet die Entfernung zu allen Standorten für jedes Pixel. Da bei jeder Operation jeweils ein Punkt entfernt und ein anderer hinzugefügt wird, sind die tatsächlichen Änderungen am Bild bei jedem Schritt ziemlich lokal. Es gibt Algorithmen, mit denen ein Voronoi-Diagramm effizient inkrementell aktualisiert werden kann, und ich glaube, sie würden diesem Algorithmus eine enorme Geschwindigkeit verleihen. Für diesen Wettbewerb habe ich mich jedoch entschieden, die Dinge einfach und brachial zu halten.
Code
Laufen
Das Programm ist eigenständig und hat keine externen Abhängigkeiten über die Standardbibliothek hinaus, erfordert jedoch Bilder im binären PPM- Format. Ich verwende ImageMagick , um Bilder in PPM zu konvertieren, obwohl es auch GIMP und einige andere Programme können.
Speichern Sie das Programm zum Kompilieren unter
voronoi.cpp
und führen Sie dann Folgendes aus:Ich erwarte, dass es wahrscheinlich unter Windows mit den neuesten Versionen von Visual Studio funktioniert, obwohl ich dies nicht ausprobiert habe. Sie sollten sicherstellen, dass Sie mit C ++ 11 oder höher kompilieren und OpenMP aktiviert ist, wenn Sie dies tun. OpenMP ist nicht zwingend erforderlich, trägt aber wesentlich dazu bei, die Ausführungszeiten erträglicher zu machen.
Um es auszuführen, mache etwas wie:
Die spätere Datei wird mit den Site-Daten aktualisiert. Die erste Zeile enthält die Breite und Höhe des Bildes, gefolgt von Zeilen mit x-, y-, r-, g- und b-Werten, die zum Kopieren und Einfügen in den Javascript-Renderer in der Problembeschreibung geeignet sind.
Mit den drei Konstanten oben im Programm können Sie die Geschwindigkeit im Verhältnis zur Qualität einstellen. Der
decimation
Faktor vergröbert das Zielbild bei der Bewertung einer Reihe von Standorten für Farbe und PSNR. Je höher der Wert, desto schneller wird das Programm ausgeführt. Wenn Sie den Wert auf 1 setzen, wird das Bild in voller Auflösung verwendet. Diecandidates
Konstante steuert, wie viele Kandidaten für jeden Schritt getestet werden sollen. Je höher, desto besser ist die Chance, eine gute Stelle zum Springen zu finden, aber desto langsamer wird das Programm. Schließlichtermination
ist es die Anzahl der Schritte, die das Programm ausführen kann, ohne seine Ausgabe zu verbessern, bevor es beendet wird. Erhöhen kann zu besseren Ergebnissen führen, dauert jedoch geringfügig länger.Bilder
N
= 100, 300, 1000 und 3000:quelle
IDL, adaptive Verfeinerung
Diese Methode ist inspiriert von Adaptive Mesh Refinement aus astronomischen Simulationen sowie Subdivision Surface . Dies ist die Art von Aufgabe, auf die sich IDL rühmt, was Sie an der großen Anzahl integrierter Funktionen erkennen können, die ich verwenden konnte. : D
Ich habe einige der Zwischenprodukte für das Yoshi-Testbild mit schwarzem Hintergrund ausgegeben
n = 1000
.Zuerst führen wir eine Graustufendarstellung für das Bild durch (mithilfe von
ct_luminance
) und wenden einen Prewitt-Filter an (prewitt
siehe Wikipedia ), um eine gute Kantenerkennung zu erzielen:Dann kommt die eigentliche Grunzarbeit: Wir unterteilen das Bild in 4 und messen die Varianz in jedem Quadranten im gefilterten Bild. Unsere Varianz wird durch die Größe der Unterteilung (die in diesem ersten Schritt gleich ist) gewichtet, damit "kantige" Regionen mit hoher Varianz nicht immer kleiner und kleiner unterteilt werden. Anschließend verwenden wir die gewichtete Varianz, um Unterteilungen mit mehr Details anzustreben, und unterteilen jeden detailreichen Abschnitt iterativ in weitere vier Abschnitte, bis wir die Zielanzahl von Standorten erreicht haben (jede Unterteilung enthält genau einen Standort). Da wir jedes Mal, wenn wir iterieren, 3 Sites hinzufügen, erhalten wir letztendlich
n - 2 <= N <= n
Sites.Ich habe für dieses Bild ein .webm des Unterteilungsprozesses erstellt, das ich nicht einbetten kann, aber es ist hier . Die Farbe in jedem Unterabschnitt wird durch die gewichtete Varianz bestimmt. (Ich habe zum Vergleich die gleiche Art von Video für das Weiß-Hintergrund-Yoshi gemacht, wobei die Farbtabelle umgekehrt wurde, sodass es in Richtung Weiß statt Schwarz geht. Es ist hier .) Das Endprodukt der Unterteilung sieht folgendermaßen aus:
Sobald wir unsere Unterteilungsliste haben, durchlaufen wir jede Unterteilung. Der endgültige Standort ist die Position des Minimums des Prewitt-Bildes, dh des am wenigsten "kantigen" Pixels, und die Farbe des Abschnitts ist die Farbe dieses Pixels; Hier ist das Originalbild mit den markierten Websites:
Dann verwenden wir die integrierte Funktion
triangulate
, um die Delaunay-Triangulation der Sites zu berechnen, und die integrierte Funktionvoronoi
, um die Eckpunkte jedes Voronoi-Polygons zu definieren, bevor jedes Polygon in seiner jeweiligen Farbe in einen Bildpuffer gezeichnet wird. Schließlich speichern wir einen Schnappschuss des Bildpuffers.Der Code:
Rufen Sie dies über
voro_map, n, image, output_filename
. Ich habe auch einewrapper
Prozedur eingefügt, die jedes Testbild durchlief und mit 100, 500 und 1000 Sites lief.Die hier gesammelten Ausgaben und hier einige Miniaturansichten:
n = 100
n = 500
n = 1000
quelle
Python 3 + PIL + SciPy, Fuzzy k-means
Der Algorithmus
Die Kernidee ist, dass k-means Clustering das Bild auf natürliche Weise in Voronoi-Zellen aufteilt, da Punkte an den nächstgelegenen Schwerpunkt gebunden sind. Allerdings müssen wir die Farben irgendwie als Einschränkung hinzufügen.
Zuerst konvertieren wir jedes Pixel in den Lab-Farbraum , um eine bessere Farbmanipulation zu erreichen.
Dann machen wir eine Art "Randerkennung für Arme". Für jedes Pixel betrachten wir seine orthogonalen und diagonalen Nachbarn und berechnen die mittlere quadratische Farbdifferenz. Wir sortieren dann alle Pixel nach diesem Unterschied, wobei die Pixel am ähnlichsten zu ihren Nachbarn am Anfang der Liste sind und die Pixel am verschiedensten zu ihren Nachbarn am Ende (dh mit größerer Wahrscheinlichkeit ein Randpunkt). Hier ist ein Beispiel für den Planeten: Je heller das Pixel ist, desto mehr unterscheidet es sich von seinen Nachbarn:
(Die oben wiedergegebene Ausgabe weist ein klares gitterartiges Muster auf. Laut @randomra liegt dies wahrscheinlich an der verlustbehafteten JPG-Codierung oder an der imgur-Komprimierung der Bilder.)
Als Nächstes verwenden wir diese Pixelreihenfolge, um eine große Anzahl von Punkten abzutasten, die gruppiert werden sollen. Wir verwenden eine Exponentialverteilung, bei der Punkte, die kantenähnlicher und "interessanter" sind, Vorrang haben.
Für das Clustering wählen wir zunächst die
N
Zentroide aus, die zufällig unter Verwendung derselben Exponentialverteilung wie oben ausgewählt werden. Eine anfängliche Iteration wird durchgeführt, und für jeden der resultierenden Cluster weisen wir eine mittlere Farbe und eine Farbvarianzschwelle zu. Dann für eine Reihe von Iterationen, wir:(Klicken für volle Größe)
Schließlich wird eine große Anzahl von Punkten unter Verwendung einer gleichmäßigen Verteilung abgetastet. Mit einem anderen kd-Baum ordnen wir jeden Punkt seinem nächsten Schwerpunkt zu und bilden Cluster. Wir approximieren dann die Medianfarbe jedes Clusters mit einem Hill-Climbing-Algorithmus und geben die endgültigen Zellfarben an (Idee für diesen Schritt dank @PhiNotPi und @ MartinBüttner).
Anmerkungen
Neben einer Textdatei für das Snippet Ausgeben (
OUTFILE
), wennDEBUG
gesetzt istTrue
das Programm wird auch ausgegeben , und die Bilder oben überschreiben. Der Algorithmus benötigt für jedes Bild ein paar Minuten, daher ist dies eine gute Möglichkeit, den Fortschritt zu überprüfen, ohne die Laufzeit zu verkürzen.Beispielausgaben
N = 32:
N = 100:
N = 1000:
N = 3000:
quelle
Mathematica, Random Cells
Dies ist die Grundlösung, damit Sie eine Vorstellung davon bekommen, welches Minimum ich von Ihnen verlange. Mit dem Dateinamen (lokal oder als URL) in
file
und N inn
wählt der folgende Code einfach N zufällige Pixel aus und verwendet die bei diesen Pixeln gefundenen Farben. Das ist wirklich naiv und funktioniert nicht besonders gut, aber ich möchte, dass ihr das doch besiegt. :)Hier sind alle Testbilder für N = 100 (alle Bilder verweisen auf größere Versionen):
Wie Sie sehen können, sind diese im Wesentlichen nutzlos. Während sie auf expressionistische Weise einen künstlerischen Wert haben mögen, sind die Originalbilder kaum wiederzuerkennen.
Für N = 500 hat sich die Situation etwas verbessert, aber es gibt immer noch sehr merkwürdige Artefakte, die Bilder sehen verwaschen aus und viele Zellen werden auf Regionen ohne Detail verschwendet:
Du bist dran!
quelle
Dimensions@ImageData
und nichtImageDimensions
? Sie können die LangsamkeitImageData
insgesamt vermeiden, indem Sie verwendenPixelValue
.Mathematica
Wir alle wissen, dass Martin Mathematica liebt. Lassen Sie mich es mit Mathematica versuchen.
Mein Algorithmus verwendet zufällige Punkte von den Bildrändern, um ein erstes Voronoi-Diagramm zu erstellen. Das Diagramm wird dann durch eine iterative Anpassung des Netzes mit einem einfachen Mittelwertfilter verschönert. Dies ergibt Bilder mit hoher Zelldichte in der Nähe kontrastreicher Bereiche und optisch ansprechenden Zellen ohne verrückte Winkel.
Die folgenden Bilder zeigen ein Beispiel für den Vorgang. Der Spaß wird durch Mathematicas schlechtes Antialiasing etwas verdorben, aber wir bekommen Vektorgrafiken, die etwas wert sein müssen.
Dieser Algorithmus ohne die Zufallsstichprobe ist in der
VoronoiMesh
Dokumentation hier zu finden .Testbilder (100,300,1000,3000)
Code
quelle
Graphics@Table[ Append[mp, VertexColors -> RGBColor /@ ImageValue[img, First[mp]]], {mp, MeshPrimitives[voronoiRelaxed, 2]}]
Python + SciPy + Emcee
Der von mir verwendete Algorithmus ist der folgende:
Der Algorithmus scheint sehr gut zu funktionieren. Leider kann es nur sinnvoll auf kleineren Bildern laufen. Ich hatte keine Zeit, die Voronoi-Punkte auf die größeren Bilder anzuwenden. Sie könnten an dieser Stelle verfeinert werden. Ich hätte die MCMC auch länger laufen lassen können, um bessere Minima zu erzielen. Der Schwachpunkt des Algorithmus ist, dass er ziemlich teuer ist. Ich hatte keine Zeit, über 1000 Punkte hinauszuwachsen, und einige der 1000-Punkte-Bilder werden noch verfeinert.
(Klicken Sie mit der rechten Maustaste und zeigen Sie das Bild an, um eine größere Version zu erhalten.)
Links zu größeren Versionen sind http://imgur.com/a/2IXDT#9 (100 Punkte), http://imgur.com/a/bBQ7q (300 Punkte) und http://imgur.com/a/rr8wJ (1000 Punkte)
Unscharf maskierte Bilder sehen wie folgt aus. Zufällige Punkte werden aus dem Bild ausgewählt, wenn eine Zufallszahl kleiner als der Wert des Bildes ist (normiert auf 1):
Ich poste größere Bilder und die Voronoi-Punkte, wenn ich mehr Zeit habe.
Bearbeiten: Wenn Sie die Anzahl der Wanderer auf 100 * Npts erhöhen, ändern Sie die Kostenfunktion so, dass sie zu den Quadraten der Abweichungen in allen Kanälen gehört, und warten Sie lange (und erhöhen Sie die Anzahl der Iterationen, auf die die Schleife abgebrochen werden soll) 200) ist es möglich, einige gute Bilder mit nur 100 Punkten zu machen:
quelle
Verwenden der Bildenergie als Punktgewichtskarte
Bei meiner Herangehensweise an diese Herausforderung wollte ich eine Möglichkeit finden, die "Relevanz" eines bestimmten Bildbereichs auf die Wahrscheinlichkeit abzubilden, dass ein bestimmter Punkt als Voronoi-Schwerpunkt ausgewählt wird. Ich wollte jedoch immer noch das künstlerische Gefühl des Voronoi-Mosaiks bewahren, indem ich zufällig Bildpunkte auswählte. Außerdem wollte ich große Bilder bearbeiten, damit ich beim Downsampling nichts verliere. Mein Algorithmus sieht ungefähr so aus:
Ergebnisse
N
= 100, 500, 1000, 3000quelle