Algorytmy tworzenia mozaik obrazkowych - czy istnieje szybszy sposób niż ten?

Bawiłem się tworzeniem mozaik obrazowych. Mój skrypt pobiera dużą liczbę obrazów, skaluje je do rozmiaru miniatury, a następnie używa ich jako kafelków w celu przybliżenia obrazu docelowego.

Podejście to jest całkiem przyjemne:

Obliczam średni błąd kwadratowy dla każdego kciuka w każdej pozycji kafelka.

Najpierw użyłem chciwego miejsca: połóż kciuk z najmniejszym błędem na kafelku, który najlepiej pasuje, a następnie następny i tak dalej.

Problem z zachłannością polega na tym, że w końcu kładziesz najróżniejsze kciuki na najmniej popularnych kafelkach, niezależnie od tego, czy pasują do siebie, czy nie. Tutaj pokazuję przykłady: http://williamedwardscoder.tumblr.com/post/84505278488/making-image-mosaics

Następnie wykonuję losowe zamiany, dopóki skrypt nie zostanie przerwany. Wyniki są całkiem OK.

Losowa zamiana dwóch płytek nie zawsze jest ulepszeniem, ale czasami obrót o trzy lub więcej płytek powoduje ogólną poprawę, tzn. A <-> BMoże się nie poprawić, ale A -> B -> C -> A1może ..

Z tego powodu po wybraniu dwóch losowych płytek i odkryciu, że się nie poprawiają, wybieram kilka płytek, aby ocenić, czy mogą one być trzecim kafelkiem w takim obrocie. Nie badam, czy którykolwiek zestaw czterech płytek można z zyskiem obracać i tak dalej; to wkrótce będzie bardzo drogie.

Ale to wymaga czasu. Dużo czasu!

Czy istnieje lepsze i szybsze podejście?

Aktualizacja nagrody

Testowałem różne implementacje i powiązania Pythona metody węgierskiej .

Zdecydowanie najszybszy był czysty Python https://github.com/xtof-durr/makeSimple/blob/master/Munkres/kuhnMunkres.py

Mam przeczucie, że przybliża to optymalną odpowiedź; kiedy uruchomiono na obrazie testowym, wszystkie inne biblioteki zgodziły się na wynik, ale ten kuhnMunkres.py, choć jest o rząd wielkości szybszy, osiągnął bardzo, bardzo, bardzo blisko wyniku, co uzgodniły inne implementacje.

Prędkość jest bardzo zależna od danych; Mona Lisa przeszła przez kuhnMunkres.py w 13 minut, ale szkarłatna papuga długoogonowa zajęła 16 minut.

Wyniki były prawie takie same jak losowe zamiany i rotacje dla papugi długoogonowej:

(kuhnMunkres.py po lewej, losowe zamiany po prawej; oryginalny obraz do porównania )

Jednak w przypadku obrazu Mona Lisa, z którym testowałem, wyniki zostały zauważalnie poprawione, a jej zdefiniowany „uśmiech” prześwitywał:

(kuhnMunkres.py po lewej, losowe zamiany po prawej)

Tak, istnieją dwa lepsze i szybsze podejścia.

• Prostszy problem: dla każdego kafelka wybierz najlepszy kciuk (z możliwym powieleniem). Ok, to oszustwo, ale może tylko doprowadzić do lepszego efektu wizualnego.
• Twoje ujęcie jest algorytmicznie bardziej interesujące i sprowadza się do „problemu liniowego przypisania”, zakładając, że bierzesz MSE jako koszty dopasowania, których suma musi być minimalna. Taki problem można rozwiązać w czasie wielomianowym, np. „Metodą węgierską”

Następnie możesz skorygować koszty, zastępując MSE bardziej wizualnie dokładną odległością, bez zmiany podstawowego algorytmu.

Jestem dość pewien, że to trudny problem z NP. Aby znaleźć „idealne” rozwiązanie, musisz wyczerpująco wypróbować każdą możliwość, a to wykładnicze.

Jednym z podejść byłoby użycie chciwego dopasowania, a następnie próba jego ulepszenia. Może to polegać na zrobieniu źle umieszczonego zdjęcia (jednego z ostatnich) i znalezieniu innego miejsca do umieszczenia go, a następnie zrobieniu tego zdjęcia i przeniesieniu go i tak dalej. Skończysz, gdy (a) skończy Ci się czas (b) dopasowanie jest „wystarczająco dobre”.

Jeśli wprowadzisz element probabilistyczny, może on ulec symulowanemu podejściu do wyżarzania lub algorytmowi genetycznemu. Być może wszystko, co próbujesz osiągnąć, to równomierne rozłożenie błędów. Podejrzewam, że zbliża się to do tego, co już robisz, więc odpowiedź brzmi: dzięki właściwemu algorytmowi możesz szybciej uzyskać lepszy wynik, ale nie ma magicznego skrótu do Nirvany.

Tak, jest to podobne do tego, co już robisz. Chodzi o to, aby zapomnieć magiczną odpowiedź i pomyśleć w kategoriach 2 algorytmów: najpierw wypełnij, a następnie zoptymalizuj.

Wypełnienie może być: losowe, najlepsze dostępne, pierwsze najlepsze, wystarczająco dobre, pewnego rodzaju hot spot.

Optymalizacja może być losowa, naprawić najgorsze lub (jak sugerowałem) symulowany algorytm wyżarzania lub algorytm genetyczny.

Potrzebujesz metryki „dobroci” i czasu, na który jesteś gotowy poświęcić i po prostu eksperymentować. Lub znajdź kogoś, kto to zrobił.

Jeśli Twoim ostatnim problemem są ostatnie kafelki, spróbuj jakoś wcześniej je umieścić;)

Jednym z podejść byłoby przyjrzenie się kafelkowi, który znajduje się najdalej od górnego x% swoich dopasowań (intuicyjnie wybrałbym 33%) i umieścić go na najlepszym dopasowaniu. To i tak najlepszy mecz, jaki można uzyskać.

Ponadto możesz zrezygnować z najlepszego dopasowania dla najgorszego kafelka, ale tego, w którym wprowadza on najmniejszy błąd w porównaniu do najlepszego dopasowania dla tego pola, abyś nie wyrzucał całkowicie swoich najlepszych wyników ze względu na „ kontrola uszkodzeń".

Inną rzeczą, o której należy pamiętać, jest to, że ostatecznie tworzysz obraz, który ma być przetwarzany przez oko. Więc tak naprawdę chcesz użyć detekcji krawędzi, aby określić, które pozycje na obrazie są najważniejsze. Podobnie to, co dzieje się na samym obrzeżu obrazu, ma niewielką wartość dla jakości efektu. Nałóż te dwie masy i uwzględnij je w obliczeniach odległości. Wszelkie drgania, które dostaniesz, powinny zatem grawitować w kierunku granicy i z dala od krawędzi, a tym samym przeszkadzać znacznie mniej.

Również po wykryciu krawędzi możesz chcieć umieścić pierwszy% y łapczywie (być może dopóki nie spadniesz poniżej pewnego progu „zjadliwości” w lewych kafelkach), aby „gorące punkty” były traktowane naprawdę ładnie, a następnie przejdź do „kontroli szkód” dla reszty.