Od 3-10 lat - układanie puzzli
| Maciej Gawron macgaw@gmail.com |
| Raport wykonany w ramach projektu z
kursu "Metody sztucznej inteligencji" |
| Prowadzący: |
| dr inż. Witold Paluszyński |
| Data: 29.01.2013 |
From 3 to 10 years - assembly jigsaw puzzles
| Maciej Gawron macgaw@gmail.com |
| The project described in this report
has been completed to fulfill the requirements for the course:
'Methods of artificial intelligence'. |
| Instructor: |
| Witold Paluszynski, Ph.D |
| Date: January 29th, 2013 |
Abstract[1] propose Mahalanobis Gradient Compatibility (MGC) to calculate similatiry between edges of each puzzles. Then it uses a tree-based reassembly that greedily merges components. It is woriking very similar to Kruskal's algorithm. It finds a minimum spanning tree for connected weighted graph. Edges of graph are calculated by MGC. Puzzles are connected to bigger pieces and then those pieces to whole picture. Working process of an algorithm is very similar to human behavior during assembling of puzzles. First section describes Mahalanobis Gradient Compatibility proposed by [1]. Second section shows an algorithm to connect each puzzles to bigger pieces. Next section is about implementation of algorithm in C++ using openCV library. Last two sections describes results of this project and most valueable conclusions. It occurs proposed algorithm is really fast and his solutions are very close to orginal image. The quality of assembled pictures depends on count of pixels on edge of each pieces. When pieces have got many pixels assembled picture is usually the same as orginal picture. |
Wstęp
Wbrew pozorom układnie puzzli jest bardzo trudnym zadaniem. Od dawna jest to bardzo popularna łamigłówka dla znudzonych ludzi. Dzieje się tak, gdyż ilość możliwości z jaką można połączyć poszczególne puzzle jest nieprawdopodobnie duża. Problem w przypadku nie znanego położenia i orientacji poszczególnych puzzli jest zadaniem NP-trudnym. Z tej przyczyny nie jest możliwe stworzenie algorytmu, który szybko rozwiązywałby to zadanie.Wielu badaczy od lat zainteresowanych jest tym problemem. Po za bardzo przyjemnym hobby, układanie puzzli może być przydatne w przypadku składania zniszczonych dokumentów, pociętych zdjęć, czy też artefaktów archeologicznych (np. zniszczonej porcelany). Pierwszy algorytm wykonujący to zadanie został przedstawiony blisko 50 lat temu przez Freemana i Grandera w [2]. Od tego czasu problem ten nie został zaniedbany. Współczesne algorytmu są w stanie ułożyć bezbłędnie puzzle o wymiarach blisko 10000 kawałków w ciągu niecałych 24 godzin.
Podczas pracy nad tym projektem rozważany był jedynie proces układania obrazów z kwadratowych puzzli o losowej orientacji i losowym położeniu początkowym. Ilość kombinacji w jaką można ułożyć K puzzli w taki sposób wynosi K!*4^K (przy założeniu, że znamy wymiar obrazka). Naturalnie istnieją publikacje dotyczące składania obrazów pociętych na kawałki o różnych wymiarach i kształtach (np. [6]) jednak często praca takiego algorytmu nie jest w pełni autonomiczna.
W przypadku układania obrazów z kwadratowych puzzli o stałym wymiarze krawędzi bardzo dobre wyniki dają metody dopasowywania do siebie puzzli bazujące na minimalizacji sumy kwadratu różnic pomiędzy poszczególnymi kolorami RGB na łączonych krawędziach (RGB SSD - opisana w [4]) lub metody probabilistyczne - maksymalizujące prawdopodobieństwa pojawienia się obok siebie poszczególnych puzzli szerzej opisanej w [5]. W pracy [1] przedstawione jest porównanie skuteczności dopasowywania puzzli tych dwóch metod z metodą opartą na gradiencie Mahalanobisa (MGC) (szerzej opisaną w drugiej sekcji opisu tego projektu). Wynika z niego, że metoda probabilistyczna jest najsłabszą z wymienionych, a dwie pozostałe dają porównywalne wyniki z minimalną przewagą MGC.
Sam proces układanie puzzli można podzielić na 2 etapy:
1) dopasowanie do siebie poszczególnych puzzli na zasadzie największego podobieństwa wynikającego z pewnej funkcji celu,
2) połączenie poszczególnych puzzli w większą całość, która nie nachodzi się na siebie.
Projekt ten zakłada implementację algorytmu układania kwadratowych puzzli o losowej orientacji i położeniu początkowym zaproponowanego w [1] i sprawdzenie w jaki sposób i z jaką dokładnością radzi on sobie z postawionym przed nim zadaniem. Ponadto zakładamy, że rozmiary obrazka nie są dane przez co algorytm sam musi znaleźć ramę i dopasować do niej puzzle.
Dopasowanie puzzli
W [1] zaproponowano metodę dopasowania puzzli opartą nazwaną Mahalanobis Gradient Compatibility. Polega ona na obliczaniu gradientów na krawędziach poszczególnych kawałków i promowaniu połączeń krawędzi, które kontynuują ten gradient na łączeniu i przy swoich krawędziach. W celu promowania ciągłych gradientów kolorów wykorzystany jest do oceny łączeń dystans Mahalanobisa.Wyliczanie wartości wagi połączenia między dwoma krawędziami
zaczynamy od obliczenia gradientu dla pierwszej krawędzi dla każdego z kolorów:
gdzie:
1) x - oznaczenie kawałka,
2) i - numer kawałka,
3) P - rząd pikseli w kawałku tuż przy krawędzi,
4) P-1 - rząd pikseli w kawałku odsunięty o 1 od krawędzi,
5) p - kolumna pikseli w kawałku,
6) c - kolor (RGB).
Następnie wyliczana jest średnia gradientu dla całej krawędzi dla poszczególnych kolorów:
Po tym wyliczana jest wartość macierzy kowariancji
dla wyliczonych wcześniej gradientów (każdy kolor jest jedną kolumną dla danych przy wyliczaniu macierzy kowariancji). W tym celu do 
zostało dopisanych na końcu 9 wektorów ([0 0 0], [1 1 1], [-1 -1 -1], [0 0 1], [0 1 0], [1 0 0], [-1 0 0], [0 -1 0], [0 0 -1]) zapobiegających osobliwości uzyskanej macierzy kowariancji. Teraz pozostaje jedynie wyliczyć gradient pomiędzy krawędziami, których wagę chcemy policzyć:
i wartość wagi łączenia pomiędzy jednym, a drugim kawałkiem:
Uzyskana waga nie jest identyczna w drugą stronę (z prawej do lewej krawędzi), gdyż macierz kowariancji jest liczona jedynie dla lewej krawędzi. Dlatego należy powtórzyć wyżej opisany proces dla drugiej krawędzi. W ten sposób ostateczna waga pomiędzy tymi dwoma krawędziami jest dana wzorem:
i jest ona taka sama dla każdej z tych dwóch krawędzi. Uzyskane wyniki należy znormalizować, aby algorytm grupujący puzzle nie łączył w grupy puzzli, które do siebie nie pasują. Normalizacja odbywa się za pomocą podzielenia wszystkich wyników dla danej krawędzi przez wartość drugiego najniższego wyniku dla tej krawędzi. Dopasowywanie oparte na tej normalizacji jest określane jako SIFT - szerzej opisanej w [3]. Założenie opiera się na tym, że najlepiej dopasowane połączenia będą miały tę wartość znacznie mniejszą od pozostałych, które będą w okolicach 1. Algorytm dopasowywania zakończy swoją pracę, gdy wartości połączeń będą większe od 1.25.
Składanie puzzli w całość
Został zaimplementowany algorytm łączenia ze sobą puzzli przypominający ludzkie działanie. Na początku wszystkie puzzle są osobno. Pierwszym krokiem jest połączenie ze sobą najbardziej pasujących puzzli w grupy kawałków. Później tak stworzone grupy są ze sobą łączone w co raz większe rysunki. Ostatecznie powstanie jeden duży rysunek złożony z wszystkich kawałków. Zastosowany algorytm jest w zasadzie algorytmem Kruskala z narzuconymi ograniczeniami:1) każdy kawałek może zostać połączony jedynie z 4 innymi kawałkami, gdyż ma tylko 4 krawędzie,
2) łączenie ze sobą grup kawałków nie może powodować, że kawałki się ze sobą nachodzą.
W przypadku, gdy największą wagę posiada łączenie krawędzi, których połączenie powoduje nachodzenie się rysunku nie dochodzi do połączenia grup. Połączenie takie jest odrzucane i brane jest następne o najwyższej wadze. Proces sprawdzania, czy jest możliwe przyłączenie następnego kawałka jest wykonywany przy każdej próbie przyłączenia nowego kawałka. Zastosowany algorytm jest zachłanny i nie sprawdza, czy jego rozwiązanie jest poprawne. Podczas procesu łączenia rozpatrywane jest jedynie jedno połączenie pomiędzy dwoma krawędziami dwóch różnych puzzli - nawet jeżeli nowy kawałek jest dopasowywany do luki i po wklejeniu do układanki będzie miał wszystkich sąsiadów. Może to spowodować błędy z orientacją, a nawet z lokalizacją w przypadku kilku podobnych krawędzi we wszystkich puzzlach.
Po wstępnym dopasowaniu puzzli odbywa się oszacowanie rozmiarów rysunku i przycięcie go w przypadku, gdyby jakieś fragmenty widocznie odbiegały od prostokąta. Jest to wykonywane maksymalizując ilość kawałków leżących w prostokącie o wymiarach zapewniających pomieszczenie wszystkich puzzli. Odcięte kawałki są rozrywane na pojedyncze puzzle i ponownie dopasowywane do rysunku. Wykorzystywany jest do tego wcześniej opisany algorytm. Tym razem jednak stworzony rysunek nie może przekroczyć oszacowanych wymiarów. Jednocześnie metoda dopasowania odciętych puzzli promuje przyłączenie puzzli do największej utworzonej grupy puzzli. Po mimo tych dodatkowych ograniczeń możliwe jest, że wszystkie puzzle nie zostaną przyłączone do największego rysunku - możliwe jest, że jakaś grupa puzzli zostanie ze sobą połączona i w przypadku dodania jej do największego kawałka wychodziłaby po za wcześniej oszacowaną ramę lub powodowała nachodzenie na siebie puzzli. W celu rozwiązania tego problemu można przyłączyć te kawałki do krawędzi po czym ponownie wykonać proces dopasowywania ramy i odcięcia wystających puzzli.
Implementacja
W ramach projektu zostały napisane trzy programy:1) jigsaw - dzieli rysunek na kawałki o losowym położeniu i orientacji,
2) from3to10years - dokonuje połączenia wcześniej podzielonych kawałków,
3) checker - sprawdza jakość dostarczonego przez from3to10years rozwiązania,
Wszystkie programy zostały napisane w C++ przy użyciu biblioteki openCV.
jigsaw
Jest to prosty program, którego wywołanie wygląda:>> ./jigsaw obraz.jpg pieceCount pieceSize scramble.png data.txt
gdzie:
- obraz.jpg - plik z obrazem, który chcemy podzielić (możliwe także inne formaty wejściowe - np. png, bmp),
- pieceCount - maksymalna ilość puzzli jaką chcemy uzyskać,
- pieceSize - ilość pikseli na krawędzi obrazu,
- scramble.png - nazwa obrazu wynikowego z losowo rozmieszczonymi, z losową orientacją kwadratowymi puzzlami (zalecany format to .png w celu pominięcia kompresji),
- data.txt - nazwa pliku do którego zostaną zapisane dane dotyczące pomieszania obrazu (wykorzystywane w sprawdzaniu poprawności uzyskanego obrazu).
Na podstawie maksymalnej ilości kawałków obliczana jest ilość puzzli w pionie i poziomie, taka aby utworzony obraz miał stosunek krawędzi podobny do zadanego obrazu. Jeżeli uzyskany stosunek krawędzi jest inny niż w bazowym obrazie, obraz przed podzieleniem jest przycinany na krawędziach, potem skalowany do odpowiedniego wymiaru (wynikającego z wyliczonej ilości klocków i ich rozdzielczości), a potem cięty na mniejsze kawałki, które w losowy sposób są umieszczane w obrazie wynikowym.
Przykładowe działanie programu dla obrazu:
Rys. 1. Obraz wejściowy
Zwróci rezultat:
1) do konsoli:
~$ ./jigsaw obraz.jpg 100 50 scramble.jpg data.txt
number of cols: 12
number of rows: 8
number of pieces: 96
2) w pliku scramble.png obraz:
Rys. 2. Obraz przeskalowany, podzielony i pomieszany
3) do pliku data.txt:
12 8 50
25 0
28 0
67 2
57 2
77 2
88 1
3 1
0 3
56 0
27 2
24 2
46 1
94 2
45 3
53 0
78 2
20 2
75 1
68 2
61 1
...
gdzie pierwsza linia zawiera ilość kolumn, ilość rzędów oraz rozmiar pojedynczego kawałka. Pozostałe linie (jest ich tyle na ile został podzielony obraz) zawierają pozycję i orientację w jakiej zostały umieszczone kolejne kawałki na rysunku scramble.png.
from3to10years
Jest to program układający puzzle. Jego wywołanie wygląda:~$ ./from3to10years scramble.png pieceSize out.txt
gdzie:
- scramble.jpg - jest obrazem zawierającym pomieszane puzzle,
- pieceSize - rozmiar w pikselach pojedynczego kawałka,
- out.txt - plik do którego zostaną zapisane dane wyjściowe.
Program from3to10years nie wykorzystuje żadnej wiedzy o obrazie pochodzącej z scramble.jpg (np. proporcje XY) po za samymi kawałkami, które odczytuje znając ich rozmiar.
Wynikiem działania programu dla:
1) w konsoli:
~$ ./from3to10years scramble.jpg 50 out.txt
data loaded
computing pieces
a = 10
a = 20
a = 30
a = 40
a = 50
a = 60
a = 70
a = 80
a = 90
normalizing pieces (1)
b = 10
b = 20
b = 30
b = 40
b = 50
b = 60
b = 70
b = 80
b = 90
connecting pieces (1)
0 ( 1, 1, 0.177901)
ended first stage
searching dimensions
time: 1
init done
opengl support available
ended
picture complite
2) w pliku 1.jpg:
Rys. 3. Obraz złożony
checker
Zadaniem programu jest sprawdzenie jakości dostarczonego rozwiązania. Jego egzystencja jest niezbędne jeżeli chcemy założyć zupełną niezależność programów jigsaw i from3to10years. Wykorzystuje on do tego celu pliki tekstowe utworzone podczas tworzenia układanki przez jigsaw i generowania rozwiązania przez from3to10years. Program checker wylicza:1) ilość klocków w odpowiedniej lokalizacji w stosunku do całkowitej ilości klocków (OL),
2) ilość klocków w odpowiedniej orientacji w stosunku do całkowitej ilości klocków (OO),
3) ilość klocków w odpowiedniej orientacji i lokalizacji w stosunku do całkowitej ilości klocków (OLO),
Orientacja obrazu ułożonego przez from3to10years nie ma wpływu na wyliczone kryteria. Jest tak, gdyż checker wyszukuje najbardziej korzystną orientację obrazu wynikowego dla pierwszego kryterium po czym wylicza dla nowej orientacji pozostałe kryteria. W przypadku, gdy obraz wyjściowy ma inne wymiary niż obraz wejściowy i nie da się go dopasować kryteria oceny przyjmą wartość 0.
Jego wywołanie może wyglądać następująco:
~$ ./checker data.txt dataOut.txt
gdzie:
- data.txt - plik tekstowy z danymi wygenerowanymi przez jigsaw,
- dataOut.txt - plik tekstowy z danymi wygenerowanymi przez from3to10years.
Poniżej znajduje się przykładowe wywołanie programu:
~$ ./checker ../from3to10years/pictures/z1 ../from3to10years/pictures/o1.txt
OP = 1
OO = 1
OPO = 1
Testy
Do testów została stworzona baza 10 obrazów nie wykorzystywana podczas tworzenia algorytmów. Jest ona dostępna w [7]. Są to obrazy wysokiej rozdzielczości o różnych proporcjach boków.Testy jakości układanych puzzli
Zostały przeprowadzone testy mające na celu sprawdzenie jakości ułożonych puzzli w zależności od ilości puzzli i ich rozmiaru. Do oceny rozwiązania został wykorzystany program checker. Rezultaty testów widoczne są w tabeli poniżej:
Rys. 4. Tabela pomiarowa
Duża niedokładność w przypadku obrazu 4 wynika z nie prawidłowej pracy funkcji dopasowującej ramkę i obcinającej skrawki obrazu. Przykładowy nie prawidłowy rezultat dla obrazu 4 widoczny jest na rysunku 5.
Rys. 5. Obraz nieprawidłowo złożony - obraz wejściowy nr 4 - 500 puzzli, rozmiar krawędzi 50 pikseli
Z testów wynika, że obrazy są lepiej dopasowywane, gdy ilość pikseli z których jest złożony pojedynczy puzzel jest największa. Dla 50 pikseli udało się ułożyć 11 z 20 obrazów (10 obrazów 500 puzzli i 10 obrazów 250 puzzli). W przypadku 40 pikseli i 28 pikseli na krawędź ilość ułożonych obrazów wynosi kolejno 8 i 7.
Układanie wielu obrazów jednocześnie
Zaimplementowany algorytm umożliwia ułożenie dwóch lub więcej zestawów puzzli wymieszanych ze sobą. Po zablokowaniu w programie wyszukiwania ramki i docinania obrazu (ze względu na implementację uniemożliwiającą złożenie więcej niż jednego obrazu) zostały przeprowadzone testy na wymieszanych puzzlach z dwóch obrazów o różnych rozmiarach (rozmiar każdego puzzla wynosił 50 pikseli). Rezultat widoczny jest na rysunku 6.
Rys. 6. Obraz złożony z dwóch obrazów
Ilość puzzli
Program from3to10years działa bardzo dobrze dla większej ilości puzzli. Jakość rozwiązania zmienia się jedynie nieznacznie w zależności od ilości kawałków z którego ma zostać ułożone rozwiązanie. Największy bezbłędnie ułożony obraz miał rozmiar 2000 puzzli (50 pikseli na krawędź). Został on ułożony w ciągu 10 minut. Obrazy o rozmiarach 3000 puzzli zostały ułożone z pojedynczymi błędami w ciągu mniej więcej jednej godziny. Na rysunku nr 7 widoczny jest obraz pomieszanych 2000 puzzli. Na rysunku 8 puzzle te zostały złożone za pomocą from3to10years.
Rys. 7. 2000 pomieszanych puzzli
Rys. 8. Obraz złożony z 2000 puzzli
Wnioski końcowe
Z analizy ułożonych obrazów wynika (rysunek 4), że w przypadku obrazów, które posiadają wiele pól bardzo podobnych do siebie może nastąpić złe dopasowanie pojedynczych puzzli w początkowej fazie układania obrazu. Niestety algorytm nie sprawdza, czy taka pomyłka nastąpiła i nigdy nie odrywa puzzli od układanki jeżeli znajdują się one w przewidywanym rozmiarze obrazu. Z tego powodu czasami nie jest możliwe połączenie ze sobą dwóch większych grup kawałków (gdyż źle dopasowany puzzle nachodziłby na inne puzzle) przez co często obraz wynikowy jest nie prawidłowo ułożony. Z tego powodu algorytm radzi sobie lepiej dla obrazów szybkozmiennych. Jakość ułożonych obrazów zmniejsza się wraz ze wzrostem ilości puzzli. Jest to spowodowane zwiększoną ilością możliwych dopasowań.Zaimplementowany algorytm pozwala układać puzzle na normalnym domowym komputerze osobistym. Ułożenie obrazu z 250 puzzli trwa poniżej 10 sekund. W przypadku obrazu złożonego z 500 kawałków komputer powinien wykonać swoje zadanie w ciągu 1 minuty. Obraz złożony z 2000 puzzli składa się w czasie 10 minut.
Bibliografia
[1] A. Gallagher. Jigsaw Puzzles with Pieces of Unknown Orientation. Proc. CVPR, 2012[2] H. Freeman and L. Gardner. Apictorial jigsaw puzzles: The computer solution of a problem in pattern recognition. IEEE. Trans. on Electronic Computers, 1964.
[3] D. Lowe. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 2004.
[4] D. Pomeranz, M. Shemesh, and O. Ben-Shahar. A fully automated greedy square jigsaw puzzle solver. In Proc. CVPR, 2011.
[5] T. S. Cho, S. Avidan, and W. T. Freeman. A probabilistic image jigsaw puzzle solver. In Proc. CVPR, 2010.
[6] E. Justino, L. Oliveria, and C. Freitas. Reconstructing shredded documents through feature matching. Forensic Science International, 2006.
[7] Maciej Gawron. Zbiór obrazów testowych wysokiej rozdzielczości znaleziony na images.google.com (proszę o kontakt na macgaw@gmail.com), 2012.