Podziękowania dla hobby Calvina za popchnięcie mojego pomysłu na wyzwanie we właściwym kierunku.
Rozważ zestaw punktów w płaszczyźnie, które nazwiemy witrynami , i skojarzmy kolor z każdą witryną. Teraz możesz pomalować całą płaszczyznę, kolorując każdy punkt kolorem najbliższego miejsca. Nazywa się to mapą Voronoi (lub diagramem Voronoi ). Zasadniczo mapy Voronoi można zdefiniować dla dowolnej metryki odległości, ale użyjemy zwykłej odległości euklidesowej r = √(x² + y²)
. ( Uwaga: niekoniecznie musisz wiedzieć, jak obliczać i renderować jeden z nich, aby konkurować w tym wyzwaniu).
Oto przykład ze 100 stronami:
Jeśli spojrzysz na dowolną komórkę, wszystkie punkty w tej komórce są bliżej odpowiedniego serwisu niż do dowolnego innego serwisu.
Twoim zadaniem jest przybliżenie danego obrazu za pomocą takiej mapy Voronoi. Dostaniemy obraz w dowolnym, wygodnym formacie grafiki rastrowej, jak również całkowitą N . Następnie powinieneś stworzyć do N stron i kolor dla każdej strony, tak aby mapa Voronoi oparta na tych stronach była jak najbardziej zbliżona do obrazu wejściowego.
Możesz użyć fragmentu stosu u dołu tego wyzwania, aby wyrenderować mapę Voronoi na podstawie wyników lub możesz ją renderować samodzielnie, jeśli wolisz.
Państwo może wykorzystać funkcje wbudowane lub innych firm w celu obliczenia mapy Voronoi ze zbioru stron (jeśli trzeba).
To konkurs popularności, więc wygrywa odpowiedź z największą liczbą głosów netto. Zachęca się wyborców do oceniania odpowiedzi według
- jak dobrze oryginalne obrazy i ich kolory są przybliżone.
- jak dobrze algorytm działa na różnych rodzajach obrazów.
- jak również algorytm działa dla małych N .
- czy algorytm adaptacyjnie grupuje punkty w obszarach obrazu, które wymagają więcej szczegółów.
Testuj obrazy
Oto kilka zdjęć, na których można przetestować algorytm (niektórzy z naszych zwykłych podejrzanych, niektórzy nowi). Kliknij zdjęcia, aby zobaczyć większe wersje.
Plaża w pierwszym rzędzie została narysowana przez Olivię Bell i uwzględniona za jej zgodą.
Jeśli chcesz dodatkowego wyzwania, wypróbuj Yoshi na białym tle i popraw jego linię brzucha.
Wszystkie te obrazy testowe można znaleźć w galerii imgur, z której można pobrać wszystkie w postaci pliku zip. Album zawiera również losowy schemat Voronoi jako kolejny test. Dla porównania, oto dane, które je wygenerowały .
Proszę dołączyć przykładowe diagramy dla różnych obrazów i N , np. 100, 300, 1000, 3000 (a także przypisy do niektórych odpowiednich specyfikacji komórek). Możesz używać lub pomijać czarne krawędzie między komórkami według własnego uznania (może to wyglądać lepiej na niektórych obrazach niż na innych). Nie dołączaj jednak witryn (z wyjątkiem osobnego przykładu, być może jeśli chcesz wyjaśnić, jak działa umieszczanie witryny).
Jeśli chcesz pokazać dużą liczbę wyników, możesz utworzyć galerię na imgur.com , aby zachować rozsądny rozmiar odpowiedzi. Ewentualnie umieść miniatury w swoim poście i umieść w nich linki do większych zdjęć, tak jak zrobiłem to w mojej referencji . Małe miniatury można uzyskać, dołączając s
do nazwy pliku w linku imgur.com (np. I3XrT.png
-> I3XrTs.png
). Ponadto, jeśli znajdziesz coś fajnego, skorzystaj z innych zdjęć testowych.
Renderer
Wklej dane wyjściowe do następującego fragmentu kodu, aby wyświetlić wyniki. Dokładny format listy nie ma znaczenia, o ile każda komórka jest określona przez 5 liczb zmiennoprzecinkowych w kolejności x y r g b
, gdzie x
i y
są współrzędnymi miejsca komórki, i r g b
są kanałami koloru czerwonego, zielonego i niebieskiego w zakresie 0 ≤ r, g, b ≤ 1
.
Fragment zapewnia opcje określania szerokości linii krawędzi komórki i określania, czy witryny komórek powinny być pokazywane (te ostatnie głównie w celu debugowania). Pamiętaj jednak, że dane wyjściowe są ponownie renderowane tylko wtedy, gdy zmieniają się specyfikacje komórek - więc jeśli zmodyfikujesz niektóre inne opcje, dodaj spację do komórek lub czegoś innego.
Ogromne podziękowania dla Raymonda Hilla za napisanie tej naprawdę miłej biblioteki JS Voronoi .
Powiązane wyzwania
źródło
Odpowiedzi:
Python + scipy + scikit-image , ważone próbkowanie płyt Poissona
Moje rozwiązanie jest dość złożone. Robię wstępne przetwarzanie obrazu, aby usunąć szum i uzyskać mapowanie, jak „interesujący” jest każdy punkt (używając kombinacji lokalnej entropii i wykrywania krawędzi):
Następnie wybieram punkty próbkowania za pomocą próbkowania dysku Poissona ze skrętem: odległość koła zależy od ciężaru, który ustaliliśmy wcześniej.
Następnie, gdy mam punkty próbkowania, dzielę obraz na segmenty voronoi i przypisuję średnią L * a * b * wartości kolorów w każdym segmencie do każdego segmentu.
Mam dużo heurystyki, a także muszę trochę matematyki, aby upewnić się, że liczba próbnych punktów jest zbliżona
N
. Dostaję sięN
dokładnie przez nieznaczne przeregulowanie , a następnie upuszczenie niektórych punktów heurystycznie.Pod względem czasu działania ten filtr nie jest tani , ale wykonanie poniższego zdjęcia nie zajęło więcej niż 5 sekund.
Bez zbędnych ceregieli:
Zdjęcia
Odpowiednio
N
wynosi 100, 300, 1000 i 3000:źródło
C ++
Moje podejście jest dość powolne, ale jestem bardzo zadowolony z jakości wyników, które daje, szczególnie jeśli chodzi o zachowanie krawędzi. Na przykład, oto Yoshi i Cornell Box z zaledwie 1000 stron każda:
Są dwie główne części, które sprawiają, że tyka. Pierwszy, wcielony w
evaluate()
funkcję, przyjmuje zestaw lokalizacji kandydujących na strony, ustawia na nich optymalne kolory i zwraca wynik dla PSNR renderowanej teselacji Voronoi względem obrazu docelowego. Kolory dla każdej witryny są określane przez uśrednienie docelowych pikseli obrazu pokrytych komórką wokół witryny. Korzystam z algorytmu Welforda, aby pomóc obliczyć zarówno najlepszy kolor dla każdej komórki, jak i wynikowy PSNR, używając tylko jednego przejścia obrazu, wykorzystując związek między wariancją, MSE i PSNR. Zmniejsza to problem do znalezienia najlepszego zestawu lokalizacji witryny bez szczególnego uwzględnienia koloru.Druga część, wcielona w
main()
, próbuje znaleźć ten zestaw. Zaczyna się od losowego wyboru zestawu punktów. Następnie na każdym kroku usuwa jeden punkt (przechodząc do rundy) i testuje zestaw losowych punktów kandydujących, aby go zastąpić. Ten, który daje najwyższy PSNR w grupie, jest akceptowany i przechowywany. W efekcie strona przeskakuje do nowej lokalizacji i ogólnie poprawia obraz krok po kroku. Należy pamiętać, że algorytm celowo nie zachowuje oryginalnej lokalizacji jako kandydata. Czasami oznacza to, że skok obniża ogólną jakość obrazu. Zezwolenie na to pomaga uniknąć utknięcia w lokalnych maksimach. Daje także kryteria zatrzymania; program kończy się po przejściu określonej liczby kroków bez ulepszania najlepszego zestawu dotychczas znalezionych witryn.Należy pamiętać, że ta implementacja jest dość podstawowa i może z łatwością zająć wiele godzin rdzenia procesora, zwłaszcza gdy liczba witryn rośnie. Ponownie oblicza pełną mapę Voronoi dla każdego kandydata, a brutalna siła testuje odległość do wszystkich miejsc dla każdego piksela. Ponieważ każda operacja wymaga usunięcia jednego punktu na raz i dodania kolejnego, rzeczywiste zmiany w obrazie na każdym kroku będą miały charakter lokalny. Istnieją algorytmy efektywnego przyrostowego aktualizowania diagramu Voronoi i wierzę, że znacznie przyspieszyłyby ten algorytm. W tym konkursie postanowiłem jednak zachować prostotę i brutalność.
Kod
Bieganie
Program jest samodzielny i nie ma zewnętrznych zależności poza standardową biblioteką, ale wymaga obrazów w formacie binarnym PPM . Korzystam z ImageMagick do konwertowania obrazów do PPM, chociaż GIMP i wiele innych programów też to potrafi.
Aby go skompilować, zapisz program jako,
voronoi.cpp
a następnie uruchom:Spodziewam się, że prawdopodobnie będzie działać w systemie Windows z najnowszymi wersjami programu Visual Studio, chociaż nie próbowałem tego. Musisz się upewnić, że kompilujesz się w C ++ 11 lub lepszej wersji i jeśli to zrobisz, masz włączony OpenMP. OpenMP nie jest absolutnie konieczne, ale bardzo pomaga w zwiększeniu tolerancji czasów wykonania.
Aby go uruchomić, zrób coś takiego:
Późniejszy plik będzie aktualizowany wraz z danymi witryny. Pierwszy wiersz będzie miał szerokość i wysokość obrazu, a następnie wiersze wartości x, y, r, g, b odpowiednie do kopiowania i wklejania do mechanizmu renderującego Javascript w opisie problemu.
Trzy stałe w górnej części programu pozwalają dostroić go do prędkości względem jakości.
decimation
Czynnikiem coarsens obraz docelowy przy ocenie zestaw stron dla koloru i PSNR. Im wyższy, tym szybciej program będzie działał. Ustawienie wartości 1 powoduje użycie obrazu w pełnej rozdzielczości. Nacandidates
stałe kontrole ilu kandydatów do testowania na każdym kroku. Wyższe daje większą szansę na znalezienie odpowiedniego miejsca, do którego można skoczyć, ale powoduje spowolnienie programu. Na koniec,termination
ile kroków może przejść program, nie poprawiając swoich wyników przed zakończeniem pracy. Zwiększenie go może dać lepsze wyniki, ale może nieco dłużej.Zdjęcia
N
= 100, 300, 1000 i 3000:źródło
IDL, udoskonalenie adaptacyjne
Ta metoda jest inspirowana przez Adaptive Mesh Refinement z symulacji astronomicznych, a także powierzchnię podrejonową . Jest to zadanie, z którego szczyci się IDL, o czym będziesz wiedział dzięki dużej liczbie wbudowanych funkcji, z których mogłem korzystać. :RE
Mam kilka produktów pośrednich dla obrazu testowego Yoshi na czarnym tle, z
n = 1000
.Najpierw wykonujemy skalę szarości luminancji na obrazie (używając
ct_luminance
) i stosujemy filtr Prewitt (prewitt
patrz wikipedia ) dla dobrego wykrywania krawędzi:Potem następuje prawdziwa pomruk: dzielimy obraz na 4 i mierzymy wariancję w każdej ćwiartce przefiltrowanego obrazu. Nasza wariancja jest ważona rozmiarem podziału (który w tym pierwszym kroku jest równy), dzięki czemu regiony „ostre” o dużej wariancji nie stają się coraz mniejsze. Następnie używamy ważonej wariancji, aby kierować poddziały z większą liczbą szczegółów, i iteracyjnie dzielimy każdą sekcję zawierającą szczegółowe informacje na 4 dodatkowe, aż osiągniemy docelową liczbę witryn (każda podgrupa zawiera dokładnie jedną witrynę). Ponieważ dodajemy 3 witryny za każdym razem, gdy wykonujemy iterację, powstają
n - 2 <= N <= n
witryny.Zrobiłem .webm procesu podziału dla tego obrazu, którego nie mogę osadzić, ale jest tutaj ; kolor w każdej podsekcji zależy od ważonej wariancji. (Zrobiłem ten sam rodzaj wideo dla yoshi na białym tle, z odwróconą tablicą kolorów, więc staje się biały zamiast czarnego; jest tutaj .) Końcowy produkt podziału wygląda następująco:
Gdy mamy już naszą listę poddziałów, przechodzimy przez każdą z poddziałów. Ostateczną lokalizacją witryny jest pozycja minimum obrazu Prewitt, tj. Najmniej „ostry” piksel, a kolor przekroju to kolor tego piksela; oto oryginalny obraz z zaznaczonymi witrynami:
Następnie używamy wbudowanego
triangulate
do obliczania triangulacji Delaunaya miejsc, a wbudowanegovoronoi
do definiowania wierzchołków każdego wielokąta Voronoi, zanim narysujemy każdy wielokąt w buforze obrazu w odpowiednim kolorze. Na koniec zapisujemy migawkę bufora obrazu.Kod:
Zadzwoń do tego przez
voro_map, n, image, output_filename
. Dołączyłem równieżwrapper
procedurę, która przeszła przez każdy obraz testowy i działała z 100, 500 i 1000 stron.Dane wyjściowe zebrane tutaj , a oto kilka miniatur:
n = 100
n = 500
n = 1000
źródło
Python 3 + PIL + SciPy, Fuzzy k-znaczy
Algorytm
Podstawową ideą jest to, że k-oznacza grupowanie naturalnie dzieli obraz na komórki Voronoi, ponieważ punkty są powiązane z najbliższym środkiem ciężkości. Musimy jednak jakoś dodać kolory jako ograniczenie.
Najpierw konwertujemy każdy piksel do przestrzeni kolorów Lab , aby lepiej manipulować kolorami.
Następnie robimy coś w rodzaju „wykrycia krawędzi biedaka”. Dla każdego piksela patrzymy na jego ortogonalnych i ukośnych sąsiadów i obliczamy średnią kwadratową różnicę koloru. Następnie sortujemy wszystkie piksele według tej różnicy, z pikselami najbardziej podobnymi do ich sąsiadów na początku listy, a pikselami najbardziej niepodobnymi do sąsiadów z tyłu (tj. Bardziej prawdopodobne, że są punktem krawędzi). Oto przykład planety, gdzie im jaśniejszy jest piksel, tym bardziej różni się od swoich sąsiadów:
(Na renderowanym wyjściu powyżej jest wyraźny wzór podobny do siatki. Według @randomra jest to prawdopodobnie spowodowane stratnym kodowaniem JPG lub kompresowaniem obrazów przez Imgur).
Następnie używamy tej kolejności pikseli do próbkowania dużej liczby punktów do zgrupowania. Używamy rozkładu wykładniczego, nadając priorytet punktom bardziej zbliżonym do krawędzi i „interesującym”.
W przypadku grupowania najpierw wybieramy
N
centroidy, losowo wybierane przy użyciu tego samego rozkładu wykładniczego, jak powyżej. Przeprowadzana jest początkowa iteracja, a dla każdej z powstałych klastrów przypisujemy średni kolor i próg wariancji kolorów. Następnie dla szeregu iteracji:(Kliknij, aby zobaczyć pełny rozmiar)
Na koniec próbkujemy dużą liczbę punktów, tym razem stosując równomierny rozkład. Używając innego drzewa KD, przypisujemy każdy punkt do jego najbliższego środka ciężkości, tworząc klastry. Następnie przybliżamy medianę koloru każdej gromady za pomocą algorytmu wspinania się na wzgórze, podając nasze ostateczne kolory komórek (pomysł na ten krok dzięki @PhiNotPi i @ MartinBüttner).
Notatki
Oprócz wyprowadzania pliku tekstowego dla snippet (
OUTFILE
), jeśliDEBUG
jest ustawionyTrue
na program, program również wypisze i nadpisuje powyższe obrazy. Algorytm zajmuje kilka minut dla każdego obrazu, więc jest to dobry sposób na sprawdzenie postępu, który nie wydłuża strasznie czasu pracy.Przykładowe wyniki
N = 32:
N = 100:
N = 1000:
N = 3000:
źródło
Mathematica, Random Cells
To podstawowe rozwiązanie, więc masz pojęcie o minimum, o które cię proszę. Biorąc pod uwagę nazwę pliku (lokalnie lub jako URL)
file
i N don
, poniższy kod po prostu wybiera N losowych pikseli i używa kolorów znalezionych w tych pikselach. To jest naprawdę naiwne i nie działa niewiarygodnie dobrze, ale chcę, żebyście to jednak pokonali. :)Oto wszystkie obrazy testowe dla N = 100 (wszystkie obrazy prowadzą do większych wersji):
Jak widać, są one zasadniczo bezużyteczne. Choć mogą mieć wartość artystyczną, w ekspresjonistyczny sposób oryginalne obrazy są ledwo rozpoznawalne.
W przypadku N = 500 sytuacja nieco się poprawiła, ale nadal istnieją bardzo dziwne artefakty, obrazy wyglądają na wyprane, a wiele komórek jest marnowanych na regiony bez szczegółów:
Twoja kolej!
źródło
Dimensions@ImageData
czy nieImageDimensions
? MożeszImageData
całkowicie uniknąć spowolnienia , używającPixelValue
.Matematyka
Wszyscy wiemy, że Martin kocha Mathematicę, więc pozwól mi spróbować z Mathematica.
Mój algorytm wykorzystuje losowe punkty z krawędzi obrazu, aby utworzyć początkowy diagram voronoi. Schemat jest następnie utrwalany przez iteracyjne dopasowanie siatki za pomocą prostego filtra średniego. Daje to obrazy o wysokiej gęstości komórek w pobliżu regionów o wysokim kontraście i przyjemnych wizualnie komórek bez szalonych kątów.
Poniższe obrazy pokazują przykład procesu w akcji. Zabawa jest nieco zepsuta przez Matematicas złe antyaliasing, ale dostajemy grafikę wektorową, która musi być coś warta.
Algorytm ten, bez losowego próbkowania, można znaleźć w
VoronoiMesh
dokumentacji tutaj .Obrazy testowe (100,300,1000,3000)
Kod
źródło
Graphics@Table[ Append[mp, VertexColors -> RGBColor /@ ImageValue[img, First[mp]]], {mp, MeshPrimitives[voronoiRelaxed, 2]}]
Python + SciPy + emcee
Algorytm, którego użyłem, jest następujący:
Algorytm wydaje się działać bardzo dobrze. Niestety może rozsądnie działać tylko na małych obrazach. Nie miałem czasu, aby wziąć punkty Voronoi i zastosować je do większych zdjęć. W tym momencie można je udoskonalić. Mógłbym również uruchomić MCMC dłużej, aby uzyskać lepsze minima. Słabym punktem algorytmu jest to, że jest raczej drogi. Nie miałem czasu, aby przekroczyć 1000 punktów, a kilka z 1000 punktów wciąż jest udoskonalanych.
(kliknij prawym przyciskiem myszy i zobacz obraz, aby uzyskać większą wersję)
Linki do większych wersji to http://imgur.com/a/2IXDT#9 (100 punktów), http://imgur.com/a/bBQ7q (300 punktów) i http://imgur.com/a/rr8wJ (1000 punktów)
Nieostre zamaskowane obrazy wyglądają następująco. Punkty losowe są wybierane z obrazu, jeśli liczba losowa jest mniejsza niż wartość obrazu (znormalizowana do 1):
Opublikuję większe zdjęcia i punkty Voronoi, jeśli będę miał więcej czasu.
Edycja: Jeśli zwiększysz liczbę spacerowiczów do 100 * npts, zmień funkcję kosztu na niektóre z kwadratów odchyleń we wszystkich kanałach i poczekaj długo (zwiększając liczbę iteracji, aby wyjść z pętli do 200), możliwe jest wykonanie dobrych zdjęć za pomocą zaledwie 100 punktów:
źródło
Wykorzystanie energii obrazu jako mapy masy punktowej
W moim podejściu do tego wyzwania chciałem sposobu odwzorowania „istotności” określonego obszaru obrazu na prawdopodobieństwo, że określony punkt zostanie wybrany jako centroid Voronoi. Jednak nadal chciałem zachować artystyczny styl mozaiki Voronoi, losowo wybierając punkty obrazu. Dodatkowo chciałem operować na dużych obrazach, więc nie tracę niczego w procesie próbkowania w dół. Mój algorytm jest mniej więcej taki:
Wyniki
N
= 100, 500, 1000, 3000źródło