AUTORZY: Marcin Owsiany 133141, Szymon Szkultin 133169

Raport z projektu: Metody i Algortmy Sztucznej Inteligencji

DATA: 15 czerwca 2007

Temat projektu: Rozpoznawanie budynków za pomocą sieci neuronowej

Plan raportu

• 1. Opis zadania
  
• 2. Opis zastosowanej metody rozwiązania problemu
  
• 3. Opis implementacji programowej
  
• 4. Testy
  
• 5. Wnioski
  
• 6. Materiały wykorzystane podczas tworzenia projektu
  

1. Opis Zadania

  Naszym zadaniem było stworzyć system, który dokonywał by identyfikacji rodzajów budynków na zdjęciach. Dokładniej rzecz ujmując na wejściu programu użytkownik podawał będzie zdjęcie lub obrazek z budynkiem a program przyporządkuje go do odpowiedniej klasy. Do bazy programu zapisaliśmy zdjęcia budynków które chcemy rozpoznawać. Program korzysta z sieci neuronowej, która traktuje te podane obrazy, jako zbiór uczący, wzorzec do rozpoznawania kolejnych budynków.

2. Opis zastosowanej metody rozwiązania problemu

Rozpoznawanie budynków na zdjęciach jest rzeczą wielce skomplikowaną. Budynki znajdują się w sąsiedztwach innych budynków, drzew, słupów, mają różne barwy i niezliczoną ilość szczegółów. Trudno jest znaleźć/zrobić zdjęcie na której budynek posiadał by cechy charakterystyczne tylko dla tej jednej klasy budynków oraz by inne elementy nie należące do budynku, nie znajdowały się na zdjęciu. Aby wyeliminować większość niechcianych szczegółów, dokonywać będziemy identyfikacji na podstawie kształtu górnej części budynku.

W ramach projektu postanowiliśmy stworzyć kompleksowy program, który nie będzie wymagał "wspomagania" innymi systemami. W tym celu zmuszeni byliśmy do stworzenia systemu do przetwarzania obrazu oraz do zaimplementowania własnej sieci neuronowej. Zbudowaliśmy aplikację o definiowanych przez użytkownika parametrach sieci neuronowej, preprocessingu wektoryzującym obraz i podającym na wejście sieci znacznie zredukowany zbiór danych, wreszcie stworzyliśmy sieć o zadowalającej wydajności potrafiącą nauczyć się kilkudziesięciu dużych wzorców w kilka sekund. Oto krótki schemat działania:

Implementacja sieci neuronowej, odbywała się przy pomocy kodów źródłowych zawartych w książce "Sieci neuronowe w praktyce: Programowanie C++". W dalszej części raportu został umieszczony szczegółowy sieci neuronowej i zastosowanego algorytmu preprocessingu.

2.1.SIEĆ NEURONOWA

W naszym projekcie wykorzystujemy model sieci oparty na perceptronie wielowarstwowym, uczonej metodą wstecznej propagacji, z zaimplementowanymi elementami momentum. Poniżej przedstawiony został opis sieci.

2.1.1 Perceptron wielowarstwowy

Sieć neuronowa używana w projekcie to klasyczny perceptron wielowarstwowy, czyli uporządkowany zbiór warstw zawierających dowolną liczbę neuronów, w którym wyjście każdego neuronu warstwy poprzedniej wiąże się z wejściem każdego neuronu warstwy następnej. Zaletą takiego rozwiązania jest znaczne uproszczenie struktury sieci, wadą - konieczność operowania na ogromnej ilości wag. Sieć perceptronową można podzielić jednoznacznie na ściśle uporządkowane i rozłączne klasy elementów, zwane warstwami. Możemy wyróżnić warstwę wejściową (w naszej sieci rolę tą pełni zwykła tablica), wyjściową oraz znajdujące się między nimi warstwy ukryte. Perceptron nie zawiera połączeń między elementami należącymi do tej samej warstwy. Wszystkie połączenia skierowane są w stronę warstwy wyjściowej, nie można wprowadzać sygnałów zwrotnych. Każde wyjście neuronu warstwy n jest połączone ze wszystkimi neuronami warstwy n+1.

Po podaniu wzorca (w naszym przypadku obrazu budynku poddanego preprocessingowi) na wejścia xi sieci wyliczane są wartości wyjściowe neuronów każdej kolejnej warstwy. Wartości zwrócone przez warstwę wyjściową interpretujemy jako kod "1 z n", czyli wyjście neuronu najbardziej zbliżone do wartości optymalnej staje się rozwiązaniem zwróconym użytkownikowi - dzięki temu możemy procentowo określić które z odrzuconych rozwiązań może być również prawdziwe.

2.1.2. Uczenie sieci

Uczenie sieci odbywa się poprzez wsteczną propagację błędów. Metoda ta określa strategię doboru wag w sieci wielowarstwowej przy wykorzystaniu gradientowych metod optymalizacji. Propagacja wsteczna opiera się na minimalizacji funkcji energetycznej zdefiniowanej jako sumę kwadratów różnic między aktualnymi wartościami sygnałów wyjściowych sieci a wartościami zadanymi:

Na etapie uczenia sieci neuronowej musimy dysponować ciągiem danych uczących składających się ze zbioru sygnałów wejściowych xi oraz przyporządkowanych im oczekiwanych (wymaganych) sygnałów wyjściowych di. Proces uczenia przebiega iteracyjnie dla kolejnych danych uczących, uaktualnianie wag odbywa się po prezentacji każdej z próbek.
W celu określenia jakości działania sieci wyliczamy dla każdego neuronu wyjściowego oraz dla każdego wzorca błąd średniokwadratowy przedstawiający odstępstwo wartości zadanej od wartości otrzymanej, a następnie uzyskujemy z otrzymanych danych średnią arytmetyczną obrazującą, czy sieć zwraca zadowalające wyniki. Dzięki temu jesteśmy w stanie stwierdzić na jakim etapie zakończyć uczenie.

2.1.3. Unikanie minimów lokalnych

Zastosowanie nieliniowej funkcji aktywacji wprowadza nieliniowość do definicji funkcji energetycznej i tym samym stwarza jeden z najpoważniejszych problemów napotykanych przez osoby projektujące sieci perceptorowe - powstawanie minimów lokalnych. Zdecydowaliśmy się na użycie w projekcie dwóch metod - momentów oraz podawania różnych próbek obok siebie. Dzięki temu otrzymaliśmy zarówno niewielką liczbę iteracji algorytmu uczącego potrzebnych do uzyskania potrzebnego wyniku, jak i zminimalizowaliśmy czas trwania wstecznej propagacji dla pojedynczej próbki uczącej.

2.2 Preprocesing

Na wejścia sieci neuronowej podawać będziemy dane, które jak najlepiej oddają istotę rozpoznawanych obiektów. W tym celu obrazy , które służą do nauczania sieci, jak i te później rozpoznawane, należy poddać wstępnej obróbce. Gdyby zaprojektować sieć tak, aby przyjmowała informacje odczytane bezpośrednio z bitmapy (np. natężenia poszczególnych składowych koloru każdego piksela), otrzymałoby się bardzo rozbudowana i prawdopodobnie nieefektywnie działajacą sieć neuronowa. Dlatego zastosowaliśmy zupełnie odmienne podejście do problemu.Stwierdziliśmy, że aby odpowiednio sklasyfikować obiekt, niezbedna jest jedynie informacja o jego krawędzi. Wystarczy więc z obrazów wyekstrahować brzegi obiektów.Dodatkowo, aby uzyskać jeszcze wieksza wydajnosć, krawedzie dzielimy na mniej więcej równe odcinki i obliczamy dla każdego z nich sinus kata nachylenia do poziomu. Dopiero te sinusy będą podawane na wejścia sieci neuronowej. Zlikwidowane w ten sposób zostały problemy rozmiaru początkowego obrazu, kolorów, przesunieć i skalowania(jednak powstały inne o których będzie w dalszej części mowa). W programie obrazy wejściowe będą poddawane kilkuetapowej obróbce. Na początek kolory zmieniane będą na skale szarosci, aby nastepnie dokonać konwersji do bitmapy monochromatycznej. Gdy już otrzymamy obraz czarno-biały, nakładany jest na niego filtr wykrycia krawędzi.
1 1 1
1 -8 1
1 1 1
Tak przyszykowany kontur można przekazać do funkcji, która punkty obwódki obiektu uporzadkuje i wybierze z nich zadana ilość. W następnej kolejności wybrane punkty sa łaczone prostymi liniami i wyliczany jest sinus kata nachylenia każdego z nich. Wartości te zwracane będą na wejścia sieci neuronowej. Poza tym wycinana jest dolna część zdjęcia w której znajdują się nie istotne szczegóły.
Kolejne etapy przetwarzania obrazu wejściowego przedstawione są na poniższych ilustracjach:

Na powyższych ilustracjach pokazano proces wyodrębniania danych niezbędnych do dalszej analizy kształtu budynku. Wybrano jedynie 30 punktów (z około 2300) na krawędzi. Taka liczba w zupełności wystarczy do określenia kszałtu budynku, gdyż chodzi nam jedynie o przybliżony zarys, a nie dokładny kształt wraz ze szczegółami charakterystycznymi tylko dla tego budynku, a nie dla całej klasy budynków.
Niestety system przez nas stworzony nie jest idealny. Słabość tego systemu jest najczęstszą przyczyną tego, że budynki nie są przyporządkowywane do odpowiedniej klasy. Mimo usilnych starań nie udało nam się stworzyć takiego przerabiania obrazu, na którego wyniki, nie miały by wpływu zakłócenia takie jak występujące na zdjęciach chmury lub drzewa, nieodpowiednio padające światło itp. Te czynniki sprawiają, że niejednokrotnie kamienica jest rozpoznana jako zamek lub kościół. Sprawdzanie klasyfikatorem wybranych przez program cech (kątów nachylenia krawędzi) potwierdziło tylko małą elastyczność systemu. Sposobem na to jest robienie zdjęć tak aby zawierały charakterystyczny szczegół, przyporządkowany do jednej klasy budynków. Jednak jest to sposób mało "rzetelny", gdyż nawet fragment zamku można sfotografować tak aby wyglądał jak lepianka i na odwrót. Sposób ten nie jest także zgodny z naszym podejściem do problemu, którego rozwiązanie miało nie zależeć od rodzaju fotografii. Rozwiązaniem mogła by być ogromna baza ze zdjęciami na której nasza sieć neuronowa mogła by się uczyć. Niestety zebrany przez nas zbiór zdjęć budynków został zdziesiątkowany przez to, że program, dla znaczącej ilości zdjęć, nie jest w stanie wyłuskać kształtu budynku.

Jest to spowodowane tym, że kolor budynku jest zbyt jasny w stosunku do tła. Po obróbce na obraz czarno-biały program nie jest w stanie prawidłowo rozpoznać krawędzi.
Wielkość obrazu wejściowego w ogólności nie ma znaczenia, aczkolwiek powinna zawierać się w granicach rozsądku. Obraz powinien być więc na tyle duży, żeby w wydzielonym konturze nie znajdowało się zbyt wiele miejsc, które mogą spowodować nieprawidłowości . Z drugiej strony, rozpoznawanie dużej grafiki może zająć dość dużo czasu, co może znacznie wydłużyć czas tworzenia sieci przez aplikację. Optymalnie zaleca się wymiary pomiędzy 200x200 a 500x500 pikseli.

3. Opis implementacji programowej

Program został napisany w Borland Builder C++. Aplikacja rozpoznająca budynki została wyposażona w interfejs graficzny, podzielony na kilka zakładek:

3.1.Lista budynków

Na pierwszej zakładce znajdują się funkcje odpowiedzialne za wczytanie/zapisanie ustawień do pliku, druga z zakładek zawiera listę rodzajów budynków i przypisanych do nich próbek uczących:

Ilość wyjść perceptronu jest równa ilości zadeklarowanych gatunków. Zalecane jest aby liczby próbek z każdego gatunku były równe - zapobiegnie to błędom w ich ułożeniu podczas prezentacji w procesie uczenia. Próbki powinny być w zwykłym formacie .bmp, ich wielkość nie może przekraczać 400x400 pikseli. Jeżeli dana próbka jest zbyt mała i nie można uzyskać z niej wymaganej liczby wejść do perceptronu, wówczas generowany jest błąd i przerywana alokacja. Aby dodać grafikę do listy należy przeciągnąć ją z Eksploratora Windows do okna aplikacji. Wszystkie pliki zostaną przeniesione do pamięci operacyjnej po wywołaniu procedury alokującej sieć neuronową (przyspieszy to podawanie danych na wejście sieci w procesie uczenia), czyli po przyciśnięciu przycisku "Utwórz (...)" na zakładce "Projektowanie sieci".

3.2.Projektowanie sieci

Kolejna z zakładek zawiera narzędzia do projektowania sieci:

Można tutaj określić liczbę warstw ukrytych, liczbę neuronów w warstwach oraz liczbę wejść perceptronu. Możliwe jest dodanie lub usunięcie warstwy i edycja ilości zawartych w niej neuronów. Jeśli lista warstw prezentowana w lewej części okna jest pusta wówczas sieć posiada jedynie warstwę wyjściową. Po zaprojektowaniu sieci trzeba kliknąć przycisk "Utwórz sieć neuronową".

3.3.Uczenie sieci

• Z góry określona liczba iteracji (wszystkie próbki prezentowane są n razy, przy czym n jest liczbą odczytaną z pola ""Ilość cykli uczenia")
• Prezentacja wszystkich próbek aż do osiągnięcia na wyjściu błędu mniejszego, niż podany w polu "Docelowy błąd". Błąd ten jest uśrednionym po wyjściach neuronów, a następnie po próbkach uczących kwadratem różnicy między wartością zadaną a otrzymaną. Uczenie dla ok. 30 próbek i 2 warstw po 50 neuronów trwa mniej niż 10 sekund, przed jego rozpoczęciem należy pamiętać o zaalokowaniu perceptronu na zakładce "Projektowanie sieci"

3.4. Rozpoznawanie budynków

3.5. Test

Ostatnia zakładka jest prezentacją, funkci wyłuskującej krawędzie budynku:

Po uprzednim wyborze pliku w zakładce "Rozpoznawanie", wciskamy przycisk >Przetwórz< aby zobaczyc jakie krawędzie (konkretnie sinusy ich kątów nachylenia) podawane są na wejście sieci.

4. Testy

Do testów służyły nam cztery rodzaje budowli:dom jednorodzinny, kamienica, zamek, kościół. Dla tych klas budynków udało nam się zebrać największą bazę zdjęć, które przechodziły pomyślnie obróbke w naszym systemie. Uczenie odbywało się przez 100 iteracji. Parametry WU i WM były równe odpowiednio 0.5 i 0.1. Przy tych parametrach praktycznie pewne było, że każdy z obrazów, którego nauczyła się sieć, będzie rozpoznawany z prawdopodobieństwem przynajmniej 95%, gdyż błąd ustalony na wyjściu sieci był bardzo mały.. System testowaliśmy na trzy sposoby. W pierwszym dzieliliśmy losowo naszą bazę zdjęć (dla każdego rodzaju budynku) na dwa zbiory: uczący i testowy. Sieć uczyliśmy za pomocą zbiorów uczących i następnie sprawdzaliśmy jak rozpoznaje ona budynki na zdjęciach ze zbiorów testowych. Wyniki różniły się w zależności od tego jaki rodzaj budynków sprawdzaliśmy. Dla kamienic system spisał się średnio. Dla około połowy przypadków nie potrafił prawidłowo "nazwać" budynku.

Dla zamków i kościołów testy wypadły już znacznie lepiej. Około 70% sprawdzanych obiektów zostało prawidłowo przyporządkowanych.

Nie jest zaskoczeniem, że program najczęściej mylił zamek z kościołem i na odwrót. Jest to oczywiście spowodowane podobnym kształtem obydwu budynków.
Najlepsze wyniki wyszły jednak dla domów. W tym przypadku system niemal bezbłędnie rozpoznawał budynki.

Kolejnym rodzajem testów jakie przeprowadzili było stosowanie jako zbioru uczącego tylko tych zdjęć, które zawierały takie same cechy dla danego rodzaju budynku. Jednak takie podejście nie poprawiło znacznie wyników, gdyż to co dla nas wydawało się powtarzalną cechą, dla naszego systemu już takie nie było. Nie mówiąc już o tym, że zdjęcia które tych cech nie wykazywały były całkowicie losowo przyporządkowywane.
Ostatni rodzaj testów polegał na uczeniu sieci przy pomocy prawie całej bazy zdjęć jaką posiadaliśmy. Te, które nie użyliśmy w uczeniu były używane w testach. Dzięki temu nasza sieć zawierała znacznie większą ilość szczegółów, co odzwierciedlało się w testach. Wprawdzie kamienice dalej nie były najlepiej rozpoznawane, ale już dla kościołów i zamków nastąpiła poprawa. Domy były dalej rozpoznawane praktycznie bezbłędnie.

Robiąc testy zmienialiśmy także parametry sieci neuronowej, zmieniając ilość warstw ukrytych, albo ilość neuronów w poszczególnych. Relatywnie najlepsze wyniki osiągneliśmy dla jednej warstwy ukrytej składającej się ze 100 neuronów. Podobne wyniki wyszły dla dwóch warstw ukrytych po 50 neuronów każda. Podsumowując, najlepiej rozpoznawane były domy (w ponad 95% testów), kościoły i zamki prawidłowo przyporządkowane były w siedem na dziesięć prób. Rozpoznanie kamienicy było najgorsze, około 50% prawidłowych wyników.

5. Wnioski

Po przeprowadzeniu testów nasuwają się oczywiste wnioski. Tylko dobrze dobrane i wyselekcjonowane cechy pozwalają sieci neuronowej na prawidłowe rozpoznanie budynków. Taką sytuacje mamy dla klasy "dom". Zdjęcia są tak robione aby znajdujący się na nich kształt odpowiadał tylko tej jednej klasie obiektów. Dla domów jest to trójkątny kształt dachu. Sieć nie ma problemów z rozpoznaniem tak charakterystycznego i regularnego kształtu.
Rozpoznawanie kościołów i zamków ma się nieco gorzej. Ich kształty są do siebie podobne i sieć często nie radzi sobie z odróżnianiem ich od siebie. Poza tym zdjęcia tych budynków są bardzo różne (raz robione z bliska, raz z oddali, różnej jakości), tak że po przetworzeniu tego obrazu, kształty są bardzo rożne i nie wykazują cech charakterystycznych dla tych klas obiektów.
System słabo radzi sobie z rozpoznaniem kamienic. Przyczyną tego jest wspominana wcześniej słabość funkcji przetwarzającej obrazy. Zdjęcia kamienic, zawierają za dużo elementów, które mylą system. Często po obróbce takiego zdjęcia, wyłuskany kształt obiektu jest do niczego nie podobny, a już napewno nie do kamienicy, której kształty powinny przypominać prostokąt.
Tak jak już wyżej było wspominane, sieć radzi sobie z rozpoznaniem obiektu, ale wtedy gdy na wejście dostarczymy dane, które chociaż trochę będą odpowiadać danym, na których ta sieć się uczyła.

6. Materiały wykorzystane podczas tworzenia projektu