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 <-> B
Może się nie poprawić, ale A -> B -> C -> A
1
moż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)