30 maja 2006

Gra z komputerem w popularną grę
Kamień, Papier, Nożyce


Projekt wykonany na laboratorium z przedmiotu Metody i algorytmy sztucznej inteligencji.

Wykonali:
Krzysztof Dmitrowski [127614]
Tomasz Lis [127973]

Ogólne sformułowanie problemu

Celem naszego projektu było stworzenie programu komputerowego, zdolnego do gry z człowiekiem w popularną grę Kamień, Papier, Nożyce. Program ma z założenia starać się za wszelką cenę wygrać, nawet gdyby środkiem do osiągnięcia tego celu było oszustwo.
Program zczytuje obraz ręki za pomocą kamery cyfrowej podłączonej do komputera, rozpoznaje "symbol" pokazany przez człowieka, a następnie wyświetla swój symbol, taki, który daje mu zwycięstwo. Kluczem do tego typu działań jest prawidłowe rozpoznanie "gestu" pokazywanego przez człowieka. Do tego zadania posłużyliśmy się wielowarstwową siecią neuronową.
Cały projekt został napisany w języku C++ w środowisku Visual Studio 2005.

Teoretyczne podstawy działania sztucznych sieci neuronowych (SSN)

Sztuczne sieci neuronowe znajdują zastosowanie przede wszystkim w dziedzinach, gdzie umysł ludzki niepodzielnie góruje nad komputerem. Bo mimo, że komputer może wykonywać dużo szybciej, wydajniej i skuteczniej operacje "zmienno-przecinkowe" - nie radzi sobie z problemami typu rozpoznawanie lub kojarzenie. Dla klasycznych algorytmach komputerowych, nawet nieznaczna zmiana parametrów rozpoznawanego obiektu stanowi wielką trudność.
Budowa SSN:
Podstawowym elementem sztucznej (ludzkiej także) sieci neuronowej jest neuron. Jego schemat został opracowany przez McCullocha i Pittsa w 1943 roku i oparty został na budowie komórki nerwowej.

budowa neuronu


Jego działanie jest następujące:
Do wejść doprowadzane są sygnały dochodzące z neuronów warstwy poprzedniej. Każdy sygnał mnożony jest przez odpowiadającą mu wartość liczbową zwaną wagą. Wpływa ona na percepcję danego sygnału wejściowego i jego udział w tworzeniu sygnału wyjściowego przez neuron. Waga może być pobudzająca - dodatnia lub opóźniająca - ujemna; jeżeli nie ma połączenia między neuronami to waga jest równa zero. Zsumowane iloczyny sygnałów i wag stanowią argument funkcji aktywacji neuronu.
Wartość funkcji aktywacji jest sygnałem wyjściowym neuronu i propagowana jest do neuronów warstwy następnej. Funkcja aktywacji przybiera jedną z trzech postaci:
  • skok jednostkowy
  • funkcja liniowa
  • funkcja nieliniowa
funkcje aktywacyjne
Wybór funkcji aktywacji zależy od rodzaju problemu jaki stawiamy przed siecią do rozwiązania. Dla sieci wielowarstwowych najczęściej stosowane są funkcje nieliniowe, gdyż neurony o takich charakterystykach wykazują największe zdolności do nauki.

Do naszego projektu wykorzystaliśmy sieć wielowarstwową.

Uczenie sieci neuronowych:
Istenieje wiele metod uczenia sieci neuronowych. Można przeczytać na ten temat w konkretnej publikacji. W sprawozdaniu tym postanowiliśmy opisać jedynie metodę przez nas używaną.
Metoda wstecznej propagacji błędów:
Jest to uczenie z nadzorem lub inaczej - z nauczycielem.
Pierwszą czynnością w procesie uczenia jest przygotowanie dwóch ciągów danych: uczącego i weryfikującego. Ciąg uczący jest to zbiór takich danych, które w miarę dokładnie charakteryzują dany problem. Jednorazowa porcja danych nazywana jest wektorem uczącym. W jego skład wchodzi wektor wejściowy czyli te dane wejściowe, które podawane są na wejścia sieci i wektor wyjściowy czyli takie dane oczekiwane, jakie sieć powinna wygenerować na swoich wyjściach. Po przetworzeniu wektora wejściowego, nauczyciel porównuje wartości otrzymane z wartościami oczekiwanymi i informuje sieć czy odpowiedź jest poprawna, a jeżeli nie, to jaki powstał błąd odpowiedzi. Błąd ten jest następnie propagowany do sieci ale w odwrotnej niż wektor wejściowy kolejności (od warstwy wyjściowej do wejściowej) i na jego podstawie następuje taka korekcja wag w każdym neuronie, aby ponowne przetworzenie tego samego wektora wejściowego spowodowało zmniejszenie błędu odpowiedzi. Procedurę taką powtarza się do momentu wygenerowania przez sieć błędu mniejszego niż założony. Wtedy na wejście sieci podaje się kolejny wektor wejściowy i powtarza te czynności. Po przetworzeniu całego ciągu uczącego (proces ten nazywany jest epoką) oblicza się błąd dla epoki i cały cykl powtarzany jest do momentu, aż błąd ten spadnie poniżej dopuszczalnego. Jak to już było zasygnalizowane wcześniej, SSN wykazują tolerancję na nieciągłości, przypadkowe zaburzenia lub wręcz niewielkie braki w zbiorze uczącym. Jest to wynikiem właśnie zdolności do uogólniania wiedzy.

Zastosowania sieci neuronowych:
  • Rozpoznawanie wzorców (znaków, liter, kształtów, sygnałów mowy, sygnałów sonarowych)
  • Klasyfikowanie obiektów
  • Prognozowanie i ocena ryzyka ekonomicznego
  • Prognozowanie zmian cen rynkowych (giełdy, waluty)
  • Ocena zdolności kredytowej podmiotów
  • Prognozowanie zapotrzebowania na energię elektryczną
  • Diagnostyka medyczna
  • Dobór pracowników
  • Prognozowanie sprzedaży
  • Aproksymowanie wartości funkcji

Metoda wykonania zadania

Realizację projektu można podzielić na cztery zasadnicze etapy:
  1. Połączenie oraz pobieranie obrazu z kamery internetowej.
  2. Przetworzenie pobranego obrazu.
  3. Rozpoznanie obrazu (testowanie sieci).
  4. Generowanie przez komputer wyników, oraz ich interpretacja..
ad.1.
Do pobierania obrazu z kamery internetowej wykorzystaliśmy gotowe biblioteki, dostarczone wraz ze środowiskiem MS Visual Studio - Windows Multimedia SDK. Pobrany obraz w postaci bitmapy wyświetlany jest w głównym oknie programu. Częstotliwość odświeżania jest zmienna i w trybie gry zależy od zmiennej ustawionej w oknie programu, a także od czasu wykonywania jednej pętli rozpoznawania (pobieranie obrazu, przetwarzanie obrazu, testowanie sieci oraz wyświetlanie wyników).

Wykorzystane funkcje:
  • hWndC = capCreateCaptureWindow ( "Capture Window", WS_CHILD |WS_DLGFRAME, 0, 0, 320, 240, GetSafeHwnd(), 11011); - funkcja tworzy kontrolkę, która przyjmie obraz z kamery,
  • capDriverConnect (hWndC, 0); - podłączenie kontrolki do sterowników kamery,
  • capGrabFrame(hWndC); - pobranie pojedynczej ramki ze strumienia kamery,
  • capEditCopy(hWndC); - kopiuje do schowka bitmapę,
  • capSetVideoFormat(hWndC,NULL,1); - makro ustawiające format pobieranych danych video,
ad.2.
Przetwarzanie obrazu realizowane jest przy pomocy biblioteki CxImage - image processing and conversion library. W pierwszym etapie obraz przetwarzany jest na czarno-biały przy użyciu funkcji progującej. Wartość progowa jest określona jako Mean()+30, gdzie Mean() to wartość średnia jasności obrazu. Następnie obraz zmniejszany jest do rozmiaru 20x16 pikseli korzystając z konwersji dokładnej (bicubic spline interpolation). Przetworzony obraz wyświetlany jest w oknie głównym programu jako rozciągnięta do wielkości pierwotnej bitmapa.

Wykorzystane funkcje:
  • CreateFromHANDLE(hBitmap); - konstruktor zasobów bitmapy,
  • MakeBitmap(m_snap.GetDC()->m_hDC); - przesłanie obrazka do uchwytu bitmapy,
  • Threshold((unsigned char)image->Mean()+30); - konwertuje obrazek do czarno-białego przy zastosowaniu progu o wartości Mean()+30. Funkcja Mean() umożliwia dobranie odpowiedniej wartości progowej,
  • Resample(20,16,2); - zmiana rozmiaru obrazu przy użyciu 'bicubic spline interpolation' (dokładna konwersja),
  • Stretch(m_picture.GetDC()->m_hDC,0,0,352,288,SRCCOPY); - rozciągnięcie obrazka do innego rozmiaru,
ad.3.
Do rozpoznania obrazu z kamery internetowej oraz klasyfikacji poszczególnych "gestów" użyliśmy wielowarstwowej sieci neuronowej. Aplikacja do stworzenia oraz testowania sztucznej sieci neuronowej wykorzystuje rozbudowane biblioteki Fast Artificial Neural Network Library. Po przetworzeniu obrazu (20x16) piksele podawane są na wejścia sieci neuronowej. Wcześniej nauczona sieć generuje wyjścia, które skojarzone są z rozpoznawanymi "gestami"; (3 neurony wyjściowe). Wartości wag neuronów wyjściowych wyświetlane są w oknie głównym programu. Więcej informacji o użytej sieci neuronowej zawiera punkt "Wykorzystana sieć neuronowa."

Wykorzystane funkcje:
  • ann = fann_create_from_file("siec.net"); - wczytanie zapisanej sieci neuronowej,
  • calc_out = fann_run(ann, tab); - testowanie sieci danymi zawartymi w tablicy,
  • train_data = fann_read_train_from_file("ucz.txt"); - stworzenie struktury do uczenia sieci za pomocą danych zawartych w pliku,
  • ann = fann_create_standard(num_layers, train_data->num_input, num_neurons_hidden, train_data->num_output); - tworzy standardową w pełni połączoną sieć neuronową z wsteczną propagacją błędów,
  • fann_set_activation_function_hidden(ann, FANN_SIGMOID_SYMMETRIC_STEPWISE); - ustawia funkcję aktywacji dla ukrytej warstwy neuronów. FANN_SIGMOID_SYMMETRIC_STEPWISE - przybliżenie liniowe funkcji aktywacji wykorzystującej tangens hiperboliczny, funkcja zwraca wartość z przedziału -1..1.
  • fann_set_activation_function_output(ann, FANN_SIGMOID_STEPWISE); - funkcja pozwalająca ustawić rodzaj funkcji aktywacji dla neuronów warstwy wyjściowej (output). FANN_SIGMOID_SYMMETRIC - funkcja aktywacji wykorzystująca tangens hiperboliczny, zwracająca wartość z przedziału -1..1,
  • fann_train_on_data(ann, train_data, max_epochs, epochs_between_reports, desired_error); - uczenie sieci,
  • fann_save(ann, "siec.net"); - zapisanie zbudowanej sieci do pliku,
  • fann_destroy_train(train_data); - zniszczenie danych treningowych,
ad.4.
Program sprawdza, czy wartość na którymś z wyjść jest większa niż 0.95 gdy na pozostałych jest mniejsza niż 0.05. Jeśli tak, to stwierdza, że sieć rozpoznała "gest" i ustala swój symbol, na taki, który daje mu zwycięstwo. Zarówno rozpoznany symbol jak i wygenerowany przez komputer jest wyświetlany w oknie głównym wraz z informacją o wyniku gry.

Wykorzystana sieć neuronowa

W projekcie naszym użyta została sieć wielowarstwowa o 320 neuronach wejściowych (1 neuron na każdy piksel), 3 neuronach wyjściowych oraz 80 neuronach w warstwie ukrytej. Na wejście neuronu podawane są wartości -1 lub 1, odpowiadające kolorowi czarnemu lub białemu w poszczególnych pikselach. Sieć uczona jest metodą wstecznej propagacji błędów, która została opisana powyżej. Sieć jest uczona do momentu, gdy błąd jest mniejszy niż 0.0001 lub ilość iteracji przekroczy 300. Funkcja aktywacji jest ustawiona jako tangens hiperboliczny zwracający wartość -1..1
tangens hiperboliczny
Funkcja aktywująca

Struktura programu

struktura projektu
Na strukturę naszego programu składają się trzy projekty.
  • KNP - główny projekt
  • CxImage - projekt do przetwarzania obrazu (kompilowany do bibliotek statycznych)
  • libfann - projekt zawierający obsługę sztucznych sieci neuronowych (kompilowany do bibliotek statycznych)
Każdy z tych projektów może być dowolnie modyfikowany.
Szczegółowy opis działania programu umieszczony jest w komentarzach kodu źródłowym.


Aby skompilować i uruchomić program należy dołączyć do projektu biblioteki podane w niniejszym sprawozdaniu. Wysłaliśmy projekt w wersji "odchudzonej" ze względu na wymagania co do wielkości oddawanego zadania. Wszystkie potrzebne biblioteki można znależć w podanych przez nas źródłach.

Praca z programem

Działanie programu składa się z dwóch trybów pracy:
  1. uczenie sieci
  2. gra z komputerem
ad. 1.
Po zazaczeniu opcji "Uczenie SSN" przechodzimy w tryb uczenia. Polega on na wprowadzaniu zdjęć opisujących konkretny "gest". Dane opisujące zdjęcia są przechowywane w pliku ucz.txt. Po przeprowadzeniu tego ciągu operacji i odznaczeniu opcji "Uczenie SSN" uaktywnia się przycisk trenuj, który pozwala na wytrenowanie sieci poprzez wcześniej zdefiniowany ciąg uczący. Dane opisujące nauczoną sieć znajdują się w pliku siec.net. Przy każdorazowym uruchomieniu programu, konfiguracja sieci ustalana jest na podstawie tego pliku.
W oddanych przez nas projekcie sieć nauczona jest za pomocą 199 zdjęć opisujących poczególne "gesty".

ad. 2.
W oknie programu widzimy dwa obszaru przedstawiające obraz ręki, którą pokazujemy do kamery cyfrowej. Obraz z lewej strony jest to oryginał obrazu odbieranego z kamery. W prawym obszarze widzimy obraz po przetworzeniu - każdy piksel tej bitmapy (przed rozciągnięciem) jest podawany na wejście sieci neuronowej.
W dolnej części okna pokazywane są wyniki rozpoznawania obrazu z kamery cyfrowej (klasyfikacja do jednego z trzech "symboli"). Po prawej stronie obszaru wizualizacji pokazany jest wynik przeprowadzonej potyczki.
W programie możemy ustalić częstotliwość odświeżania obrazu i przez to tempo gry (wartość teoretyczna, nieuwzględniająca opóźnień wynikających z procesu obliczeniowego).

Przykładowe screeny pokazujące działanie programu:

kamien

papier

nozyce

Wiedza zdobyta podczas realizacji projektu

Głównym celem realizacji projektu była chęć poznania działania sieci neuronowych, jako metody sztucznej inteligencji w rozpoznawaniu i klasyfikacji.
Sporą część czasu wykonania projektu zajęło nam gromdzenie informacji o dostępnych metodach i narzędziach umożliwiających pobranie obrazu z kamery cyfrowej, przetworzenie obrazu oraz zasadę działania sieci neuronowych. Po analizie dostępnych metod zdecydowaliśmy się na budowanie aplikacji w środowisku MS Visual Studio pod systemem operacyjnym Windows, ze względu na dobre "wsparcie techniczne" przy pobieraniu obrazu z kamery. Ważną kwestią przy rozpoznawaniu obrazu jest jego wstępna obróbka i przetwarzanie. Zdecydowaliśmy się na dość prymitywne rozwiązanie. Polega ono na tym, że jako wejście dla sieci neuronowej podajemy piksele. Nie rozwiązuje to problemu różnej orientacji obrazu. Podjęliśmy taką decyzję, gdyż uznaliśmy, że obraz z kamery cyfrowej jest podatny na wiele zakłóceń. Rozwiązaliśmy za to problem różnej jasności obrazu, poprzez zastosowanie zmiennej wartości progującej.
Kolejną barierą, która sprawiła nam problem było "zrozumienie" sieci neuronowych w podejściu praktycznym - czyli realizacji programowej (przełożenie teorii książkowej na implemtację w kodzie).

Uwagi i wnioski do programu

  1. Znaczący wpływ na jakość wczytywanego i przetwarzanego obrazu ma oświetlenie sceny oraz postać tła.
  2. Skuteczność rozpoznawania obrazu zależy od ilości danych uczących oraz ich jakości.
  3. Najlepiej jest uczyć sieć sekwencjami symboli (nie powinno się dawać kilka takich samych "gestów" w jednym ciągu, lecz mieszać nimi). Ma to istotny wpływ na ustalenie wag w sieci neuronowej.
  4. Obecnie sieć jest nauczona przez nas do rozpoznawania gestów tylko lewej ręki.
  5. Maksymalna częstotliwość odświeżania obrazu (a przez to także gry) jest wg nas dość duża; zależy też od mocy obliczeniowej komputera.
  6. Do prawidłowego funkcjonowania programu w systemie operacyjnym musi być zainstalowana kamera internetowa ze standardowymi sterownikami.
  7. W katalogu projektu musi znajdować się plik konfiguracyjny sieci sieć.net oraz plik biblioteki dynamicznej MSVCRTD.DLL


Bibliografia:
[1] Leszek Wojnar - "Praktyka analizy obrazu"
[2] Stanisław Osowski - "Sieci neuronowe do przetwarzania informacji"

Adresy internetowe:
  1. http://windowssdk.msdn.microsoft.com/library/default.asp?url=/library/en-us/Multimed/htm/_win32_multimedia_macros.asp
  2. http://www.xdp.it/cximage.htm
  3. http://fann.sourceforge.net/fann_pl.pdf
  4. http://l0co.webpark.pl/edu/fann/fann_ref.pdf