algorytm.org

Tworzenie obrazów - algorytm genetyczny

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Tworzenie obrazów - algorytm genetyczny
Ocena użytkowników:***** / 22
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 25 listopada 2011 20:03

Załóżmy, że mamy dany obraz wejściowy i chcemy wygenerować obraz jak najbardziej do niego podobny składający się z zadanej liczby elementów o określonym kształcie. Do rozwiązania tego problemu posłużymy się algorytmem genetycznym. Na początek przyjrzymy się wersji, w której elementy składowe są trójkątami. A więc do roboty...

Obraz wejściowy oznaczymy jako Oorg
Obraz wyjściowy ma taki sam rozmiar jak obraz wejściowy i opisany jest przez n elementów składowych element1, element2, ... elementn. Z kolei każdy element opisany jest przez jego kształt i kolor. Dla trójkąta będą to trzy współrzędne jego wierzchołków oraz kolor.
W algorytmach genetycznych posługujemy się pokoleniami. W każdym pokoleniu znajduje się grupa p osobników (populacja). W przypadku naszego problemu osobnikami będą obrazy wyjściowe. Zatem pokolenie t zdefiniowane jest przez zbiór obrazów wyjściowych O1t, O2t, ..., Opt

W naszym zadaniu chodzi o wygenerowanie obrazu jak najbardziej podobnego do oryginału. Musimy więc wprowadzić funkcję, która oceni stopień podobieństwa pomiędzy obrazem oryginalnym a obrazem wyjściowym. Wynik będzie tym lepszy im wyższa wartość tej funkcji. A więc żeby ocenić jak bardzo obraz wyjściowy jest podobny do oryginału musimy narysować wszystkie jego elementy składowe, a następnie każdy punkt wygenerowanego obrazu porównać z punktem obrazu oryginalnego. Każdy punkt naszych obrazów opisany jest przez trzy składowe r, g, b odpowiadające trzem kolorom podstawowym - czerwony (red), zielony (green), niebieski (blue). Różnicę pomiędzy punktem obrazu oryginalnego Porg a punktem obrazu wyjściowego Pwyj zdefiniujemy jako:

\sqrt{(Porg_{r}-Pwyj_{r})^{2} + (Porg_{g}-Pwyj_{g})^{2} + (Porg_{b}-Pwyj_{b})^{2}}

Niech suma różnic wszystkich punktów składających się na obraz wynosi d. Wówczas stopień podobieństwa zdefiniujemy jako: (dmax - d) / dmax, gdzie:
dmax jest maksymalną różnicą pomiędzy obrazami zdefniowaną jako (zakładamy, że składowe kolorów mają wartości od 0 do 255):

wysokoscObrazu * szerokoscObrazu * \sqrt{255^{2}*3}


Mamy zatem zdefiniowaną funkcję dzięki, której możemy ocenić każdy osobnik (obraz) w populacji. Jak wspomniałem wcześniej pokolenie składa się z p osobników, ale kandydatami do następnego pokolenia jest tylko e osobników (e < p) o największej wartości funkcji podobieństwa (elita). Pozostałe osobniki odrzucane są przez ewolucję jako "nieprzystosowane".

Najlepsze osobniki (obrazy), krzyżują się ze sobą tworząc nowe pokolenie. Proces krzyżowania polega na wzięciu dwóch osobników (hipotetycznego "ojca" i "matki") i wyprodukowaniu na ich podstawie potomka. W naszym przypadku proces ten będzie przebiegał następująco:
Wylosuj liczbę od 0 do 1, jeżeli wylosowana liczba jest mniejsza od 0.5 weź element1 z "ojca" w przeciwnym wypadku weź go z "matki".
Wylosuj liczbę od 0 do 1, jeżeli wylosowana liczba jest mniejsza od 0.5 weź element2 z "ojca" w przeciwnym wypadku weź go z "matki".
...
Wylosuj liczbę od 0 do 1, jeżeli wylosowana liczba jest mniejsza od 0.5 weź elementn z "ojca" w przeciwnym wypadku weź go z "matki".

Dodatkowo w trakcie procesu kopiowania elementów z rodziców, z pewnym zadanym prawdopodobieństwem m może nastąpić mutacja. A więc podczas kopiowania elementu z jednego z rodziców losuję się liczbę od 0 do 1. Jeżeli jest ona mniejsza od m wówczas element zostaje skopiowany bez wprowadzania żadnych zmian, w przeciwnym razie element zostaje skopiowany ale jego parametry zostają zmienione o jakąś losową wartość. W przypadku trójkątów mutacja polega na zmianie jednego z trzech wierzchołków bądź koloru (założyłem też że wartość zmiany ma rozkład Gaussa).

Tak więc mamy już omówione wszystkie składowe potrzebne do uruchomienia algorytmu genetycznego generującego obraz z trójkątów. Pozostaje tylko kwestia wartości początkowej. Ja założyłem, że początkowa wartość obrazów to losowe rozłożone elementy o niewielkich rozmiarach (długość boku trójkąta nie przekracza dwóch punktów) i losowym kolorze.

Tak więc algorytm przebiega następująco:
Pokolenie pierwsze t = 1
Utwórz zbiór p obrazów składających się z losowo ułożonych elementów. Te obrazy to: O11, O21, ..., Op1.
Oceń podobieństwo każdego z tych obrazów, do obrazu Oorg.
Wybierz e najlepszych obrazów. Krzyżuj obrazy z elity uzyskując nowe pokolenie t = 2. Ja krzyżuje obraz 1 z 2, 1 z 3, 1, z 4, ... 1 z e, 2 z 1, 2, z 3, 2 z 4, ..., 2 z e, tak długo aż uzyskam p nowych obrazów.
Nowe obrazy po krzyżowaniu to: O12, O22, ..., Op2.
Oceń podobieństwo każdego z tych obrazów, do obrazu Oorg.
Wybierz e najlepszych obrazów. Krzyżuj obrazy z elity uzyskując nowe pokolenie t = 3.
...

Poniżej wynik generowania przykładowego rozwiązania. Początkowo prawdopodobieństwo mutacji elementu wynosiło 0.1, po pokoleniu 350-tym zostało zmniejszone do 0.05, po 700-tym do 0.02, po 1000-ym do 0.01. Większe prawdopodobieństwo i wielkość mutacji z początku przyśpiesza poprawianie wartości podobieństwa w kolejnych pokoleniach, ale po dojściu do pewnej wartości zaczyna je hamować - kolejne pokolenia są tak samo podobne bądź nawet gorsze od poprzednich. Należy wówczas zmniejszyć prawdopodobieństwo i wielkość mutacji tak by pomagała a nie przeszkadzała w dochodzeniu do optymalnego rozwiązania. Obraz oryginalny:

obraz wejściowy

pokolenie 5
czas generowania ~5 sekund
podobieństwo ~44%
pokolenie 100
czas generowania ~2 minuty
podobieństwo ~73%
pokolenie 250
czas generowania ~3 minuty
podobieństwo ~88%
tworzenie obrazu - 5 pokoleń tworzenie obrazu - 100 pokoleń tworzenie obrazu - 250 pokoleń
pokolenie 350
czas generowania ~4 minuty
podobieństwo ~90%
pokolenie 1000
czas generowania ~15 minut
podobieństwo ~93%
pokolenie 6000
czas generowania ~1.5 godziny
podobieństwo ~94.5%
tworzenie obrazu - 350 pokoleń tworzenie obrazu - 1000 pokoleń tworzenie obrazu - 6000 pokoleń


Utworzyłem również wersję, w której elementami składowymi są koła - opisane przez współrzędne środka, promień oraz kolor.

Przykład w JavaScript:

Ustaw ścieżkę do pliku (lub pozostaw tą domyślną), wczytaj plik a następnie użyj przycisku "Start" w celu sprawdzenia działania metody.
Ze względu na zabezpieczenia w przeglądarkach, skrypt otwiera wyłącznie pliki graficzne w obrębie naszego serwisu, np:
http://www.algorytm.org/images/stories/po/anaglif_lewy.jpg
http://www.algorytm.org/images/stories/po/orig.gif
http://www.algorytm.org/images/stories/mb/hsv.jpg

Plik:
Liczebność populacji:
Liczebność elity:
Liczba elementów:
Rodzaj elementów:tójkąty koła
Prawdopodobieństwo mutacji elementu:
Wielkość mutacji (1-100):
OryginałNajlepszyBieżący

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiJavaScriptFirefox 3.0+, Safari 3.0+, Chrome 3.0+, Opera 9.5+, IE 9.0+
.js
.js
***** / 3
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 26 sierpnia 2012 08:58
Komentarze
photo
0 # Tomasz Lubiński 2011-11-28 11:47
Zachęcam do tworzenia swoich elementów składowych (np.: kwadraty, gwiazdki, ....) i przysyłania kodów oraz wyników. Wystarczy w skrypcie załączonym do artykułu dodać klasę z następującymi trzema metodami:
Kod:
function geneticImageElementX()
{
//funkcja inicjująca element (np. niewielki element w losowym miejscu obrazu)
this.init = function()
{
}

//funkcja rysująca element w podanym kontekście obiektu canvas
this.draw = function(ctx)
{
}

//funkcja tworząca i zwracajaca kopie elementu, wprowadza również losowe mutacje
this.clone = function()
{
}
}
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz