Wrocław, 16.06.2008
Metody i algorytmy sztucznej inteligencji
Raport z projektu
UKŁADANIE PUZZLI
Autor: Marek Korczyński
Methods and algorithms of artificial intelligence
Project report
Puzzle-solving problem
Author: Marek Korczyński
Introduction:
The goal of the project was to solve the puzzle-solving problem. The task was to slice the picture into squares of defined sizes, mix them and then reorganize them. In order to do this two heuristic functions were written. They were minimalised by swapping of two randomly chosen puzzle pieces. The puzzles were arranged on a plane 9 times greater than picture size. Attempts were made to implement modifications based on human behaviour with puzzle-solving, that included separate assembling of borders and center of the puzzle as well as grouping of pieces which fit together. Research was done on *.jpg images of two types: "fast-changing" and "slow-changing" and with different amount of pieces to organize - 48, 192, 768. Work was done in Matlab environment using the "Image Processing Toolbox".
Wstęp
Celem projektu była próba rozwiązania problemu układania puzzli. Zadanie polegało na pocięciu obrazka w kwadraty o zadanym wymiarze, losowe pomieszanie ich uporządkowanie. W celu ułożenia puzzli skonstruowano dwie funkcje heurystyczne, które minimalizowano przez losową zamianę miejscami dwóch losowo wybranych puzzli. Puzzle układano na płaszczyźnie 9 razy większej niż wielkość obrazu i próbowano wprowadzić modyfikacje wzorowane na zachowaniu człowieka przy rozwiązywaniu problemu układania puzzli, czyli układanie osobno krawędzi osobno części wewnętrznej obrazu oraz grupowaniu puzzli pasujących od siebie. Badania prowadzono na obrazach *.jpg w dwóch rodzajach: 'szybkozmiennym' i 'wolno zmiennym' oraz przy różnych ilościach elementów do układania - 48, 192, 768. Prace oparto na środowisku Matlab i korzystano z narzędzia 'Image Processing Toolbox'.
Opis rozwiązania
Zadanie polegało na napisaniu aplikacji automatycznie układającej puzzle. Etapy działania aplikacji:
Wczytanie zadanego obrazka *.jpg
Pocięcie go na fragmenty - użytkownik musi określić liczbę przez którą dzieli się zarówno liczba pikseli pionowych jak i poziomych, na tej podstawie ustalana jest ilość puzzli w programie
Pocięty obraz jest przechowywany w macierzy pięciowymiarowej (x,y,a,b,c) gdzie: x,y – położenie puzzla na płaszczyźnie, a,b,c – (a,b,1) – macierz R obrazu, (a,b,2) – macierz G obrazu, (a,b,3) – macierz B obrazu.
Puzzle zostają pomieszane losowo – osobno mieszane są puzzle brzegowe, osobno środkowe obrazu. Zakłada się puzzle narożne są niemieszane, ponieważ człowiek jest w sanie zawsze je wyróżnić. Ponadto założono, że orientacja puzzli jest poprawna.
Układanie polega na minimalizacji funkcji celu, przez losowanie dwóch puzzli, zamienianie ich miejscami i obserwacji zmiany wartości funkcji celu.
Funkcje heurystyczne
W celu poprawnego dopasowania elementów układanki zbudowano funkcje heurystyczne.
Różnica jednej brzegowej wartości puzzla z puzzlem sąsiadującym. Jako brzegowa wartości są brane sumy wartości każdego z kolorów R G B trzech pikseli. Funkcja porównuje każdy puzzel ze swoim prawym i dolnym sąsiadem. Wynik powyższych operacji jest ubezwzględniany i pierwiastkowany.
Różnica trzech brzegowych wartości puzzla z puzzlem sąsiadującym. Jako brzegowa wartości są brane sumy wartości każdego z kolorów R G B trzech pikseli. Funkcja porównuje każdy puzzel ze swoim prawym i dolnym sąsiadem. Wynik powyższych operacji jest ubezwzględniany i pierwiastkowany.
Przykład działania
Wszystkie układania puzzli zostały przeprowadzone na 1000 próbach zamiany puzzli miejscami.
Obraz wolno zmienny
Przykładowa sesja z programem:
>> obraz
Wymiar obrazka X=600, Y=800
Puzli w programie: 48
Czekaj ...
Brzeg:
Funkcja celu 1 (minimum)= 328.406051
Przesuniec= 30 ,Osiagnieta wart. f celu= 764.519028
Srodek:
Funkcja celu 1 (minimum)= 626.155994
Przesuniec= 31 ,Osiagnieta wart. f celu= 1485.798376
Brzeg:
Funkcja celu 2 (minimum)= 813.411233
Przesuniec= 29 ,Osiagnieta wart. f celu= 1698.587674
Srodek:
Funkcja celu 2 (minimum)= 1421.933718
Przesuniec= 22 ,Osiagnieta wart. f celu= 2710.815161
>>
>> obraz
Wymiar obrazka X=600, Y=800
Puzli w programie: 192
Czekaj ...
Brzeg:
Funkcja celu 1 (minimum)= 691.363171
Przesuniec= 67 ,Osiagnieta wart. f celu= 1840.874164
Srodek:
Funkcja celu 1 (minimum)= 2880.804790
Przesuniec= 149 ,Osiagnieta wart. f celu= 10405.810363
Brzeg:
Funkcja celu 2 (minimum)= 1456.428835
Przesuniec= 78 ,Osiagnieta wart. f celu= 2651.278537
Srodek:
Funkcja celu 2 (minimum)= 6895.997354
Przesuniec= 141 ,Osiagnieta wart. f celu= 18336.407800
>> obraz
Wymiar obrazka X=600, Y=800
Puzli w programie: 768
Czekaj ...
Funkcja celu 1 (minimum)= 1891.412398
Przesuniec= 111 ,Osiagnieta wart. f celu= 3160.439084
Funkcja celu 1 (minimum)= 18869.589295
Przesuniec= 340 ,Osiagnieta wart. f celu= 49697.844988
Funkcja celu 2 (minimum)= 2708.347657
Przesuniec= 115 ,Osiagnieta wart. f celu= 5396.654616
Funkcja celu 2 (minimum)= 29104.943871
Przesuniec= 329 ,Osiagnieta wart. f celu= 86215.909945
>>
Obraz szybkozmienny
Przykładowa sesja z programem:
>> obraz
Wymiar obrazka X=600, Y=800
Puzli w programie: 48
Czekaj ...
Brzeg:
Funkcja celu 1 (minimum)= 537.116923
Przesuniec= 29 ,Osiagnieta wart. f celu= 1332.798717
Srodek:
Funkcja celu 1 (minimum)= 1154.754061
Przesuniec= 26 ,Osiagnieta wart. f celu= 2169.437294
Brzeg:
Funkcja celu 2 (minimum)= 1440.990251
Przesuniec= 26 ,Osiagnieta wart. f celu= 2347.981968
Srodek:
Funkcja celu 2 (minimum)= 2687.494308
Przesuniec= 25 ,Osiagnieta wart. f celu= 3501.183851
>>
>> obraz
Wymiar obrazka X=600, Y=800
Puzli w programie: 192
Czekaj ...
Brzeg:
Funkcja celu 1 (minimum)= 922.880681
Przesuniec= 61 ,Osiagnieta wart. f celu= 1860.408641
Srodek:
Funkcja celu 1 (minimum)= 5649.720876
Przesuniec= 116 ,Osiagnieta wart. f celu= 12648.232613
Brzeg:
Funkcja celu 2 (minimum)= 2475.312002
Przesuniec= 70 ,Osiagnieta wart. f celu= 3409.229936
Srodek:
Funkcja celu 2 (minimum)= 13393.470366
Przesuniec= 122 ,Osiagnieta wart. f celu= 21769.477269
>>
>> obraz
Wymiar obrazka X=600, Y=800
Puzli w programie: 768
Czekaj ...
Brzeg:
Funkcja celu 1 (minimum)= 2244.852112
Przesuniec= 94 ,Osiagnieta wart. f celu= 3179.618218
Srodek:
Funkcja celu 1 (minimum)= 25413.520208
Przesuniec= 336 ,Osiagnieta wart. f celu= 59519.900268
Brzeg:
Funkcja celu 2 (minimum)= 4018.327561
Przesuniec= 111 ,Osiagnieta wart. f celu= 5621.192107
Srodek:
Funkcja celu 2 (minimum)= 52101.278877
Przesuniec= 333 ,Osiagnieta wart. f celu= 100824.998028
>>
Wnioski
Problem układania puzzli niewątpliwie do prostych nie należy. Początkowy układ determinuje wszystkie dalsze działania programu co przy tak przyjętej funkcji celu jest niedobrym rozwiązaniem. Dopasowanie dwóch puzzli nastąpi nawet wtedy, jeśli do siebie zupełnie nie pasują, a minimalizują funkcje celu. Funkcja celu jest minimalizowana zawsze, pod warunkiem odpowiednio dużej liczby prób zamian puzzli i szczęścia w losowym wybieraniu puzzli do zamiany. Wraz ze wzrostem ilości puzzli wzrasta ilość zamian ich miejscami (co jest naturalnym zjawiskiem).
Badania pokazują że duża liczba zamian puzzli zawsze powoduje wzrost uporządkowania – widać to w przypadku układania brzegu fragmenty uporządkowane trafiają się często nawet przy dużej liczbie puzzli. W zależności od układu puzzli pomieszanych i kolejności losowań funkcja celu prawie zawsze dojdzie do etapu, gdzie każda zamiana będzie powodować jej wzrost. Niezależnie od obrazu (wolno zmienny, szybkozmienny) i ilości puzzli układanie jest podobne. Funkcja celu w każdym z przypadków zbliża się do dwukrotnej wartości funkcji celu minimalnej. Ostatecznie stwierdza się że takie funkcje heurystyczne przy tak dobranych parametrach układania nie są w stanie poradzić sobie z zadaniem przy takiej (lub większej) ilości prób zamian puzzli miejscami.
Wykorzystane materialy
Zygmunt Wróbel, Robelrt Koprowski: Przetwarzanie obrazu w programie Matlab
Zygmunt Wróbel, Robelrt Koprowski: Przetwarzanie obrazu w programie Matlab