Cel projektu
Stworzenie systemu umożliwiającego klasyfikowanie zjawisk przedstawionych za pomocą punktowych map zasięgów. Jako przykład wybrano punktowe mapy rozmieszczenia gatunków roślin w Polsce. Podstawą do wydzielenia klas w przypadku tego projektu jest charakter występowania gatunku, czyli m.in. ilość punktów i sposób ich rozmieszczenia. W analizie nie uwzględnia się geograficznego położenia punktów i ich skupisk. Przykładami tak określonych klas mogą być następujące wzorce: punkty pojedyncze (wyraźnie oddalone od siebie), skupiska (wiele punktów blisko siebie), gradienty (skupisko oraz rozchodzące się od niego coraz bardziej rozproszone punkty).Charakterystyka danych
Zbiór obrazów rastrowych (pozyskanych np. poprzez przeskanowanie), zawierające tło, punkty oraz inne obiekty.Przykładowa mapa:
 |
Osadzenie projektu w dziedzinie rozpoznawania obrazów
| Cecha metod rozpoznawania obrazów | Grupa metod |
|---|---|
| Obecność uczenia | brak(1) |
| Sposób analizy zawartości obrazu | globalne |
| Metoda podejmowania decyzji | wektorowe |
| Obecność modułu ekstrakcji cech/opisu | podejścia niebezpośrednie |
| Sposób wnioskowania | oparte na cechach |
| Wzajemne relacje przpływu danych i przepływu informacji | rozpoznawanie sterowane obrazem |
Zastosowane podejście
Przyjęte rozwiązanie można podzielić na następujące trzy duże etapy:- wykrycie punktów na mapie - przejście od obrazu rastrowego do informacji w postaci tablicy współrzędnych punktów,
- określenie cech rozmieszczenia punktów - utworzenie wektora cech opisującego charakter rozmieszczenia na podstawie informacji o położeniu poszczególnych punktów,
- klasyfikacja map - znajdowanie klas rozmieszczeń (oraz przypisywanie do nich poszczególnych obrazów) w oparciu o utworzone wektory cech.
Pierwszy etap stanowią operacje wykonywane na wczytanym z pliku obrazie rastrowym. Są to kolejno:
- przejście z obrazu RGB na obraz jednokanałowy (skala szarości),
- zastosowanie filtra medianowego - celem tej operacji jest wyeliminowanie drobnych szumów, co służy przede wszystkim do usunięcia błędów powstałych w procesie skanowania,
- adaptatywna binaryzacja - usunięcie większości niepotrzebnych informacji z mapy,
- erozja - eliminacja drobnych elementów pozostałych po poprzedniej operacji,
- zastępowanie grup punktów na ekranie (pikseli) pojedynczymi punktami - założeniem dla tej operacji jest to, że poprzedzające ją przetwarzanie pozostawiło jedynie te fragmenty oryginalnego obrazu, które są poszukiwanymi punktami na mapie lub częściami tych punktów,
- odczytanie współrzędnych pikseli pozostałych na obrazie.
Kolejne operacje wykonywane dla przykładowej mapy:
 |
Oryginalna mapa oraz okno interfejsu pozwalającego sterować parametrami poszczególnych operacji |
 |
Po zamianie RGB na skalę szarości |
 |
Po zastosowaniu filtra medianowego |
 |
Po wykonaniu adaptatywnej binaryzacji |
 |
Po wykonaniu erozji |
 |
Po zamianie grup pikseli na pojedyncze punkty |
Drugi etap czyli tworzenie wektora cech wykonywany jest w oparciu analizę minimalnego drzewa rozpinającego (ang. minimum spanning tree, MST) utworzonego z punktów, których współrzędne zostały wyekstrahowane w pierwszym kroku. Utworzenie drzew (algorytm Prima) umożliwia pobieranie cech strukturalnych poszczególnych map. Analizując drzewa braliśmy pod uwagę następujące cechy:
- liczbę krawędzi drzewa
- średnią długość krawędzi
- wariancję długości krawędzi
- stopień wierzchołka
- wariancja stopnia wierzchołka
Trzeci etap stanowi analiza skupień (clustering), która w uproszczonym modelu przyjmuje jako dane po jednym wektorze na mapę (wyznaczonym w opisanym powyżej kroku) oraz zadaną oczekiwaną ilość klas (klastrów). Wynikiem tego jest przypisanie każdego z wektorów (i tym samym map) do klastra. W bardziej zaawansowanym modelu analiza skupień wykonywana jest jednak dwukrotnie:
- na danych utworzonych przez wektory opisujące rozerwane drzewa (czyli w ilości znacznie większej niż ilość map). W wyniku otrzymywane jest przypisanie do klastrów poddrzew, które stanowi podstawę do utworzenia wektora cech dla każdej z map. Jest to wykonywane w następujący sposób: wymiarami w tym wektorze są klastry poddrzew a wartościami w poszczególnych wymiarach dla każdej mapy ilość poddrzew danego typu z których składa się drzewo tej mapy,
- na danych uzyskanych w powyżej opisanym kroku, w celu przypisania każdej z map do klastra.
Środowisko realizacji projektu oraz wykorzystane narzędzia
Na rozwiązanie składa się kilka niezależnych programów, realizujących poszczególne etapy. Zostały one napisane w języku C++ z wykorzystaniem narzędzia Borland C++ Builder 6. Oto krótki opis programów:
- map_reader program służący do przetwarzania obrazów rastrowych zawierających mapy zasięgowe. Wykorzystuje on bibliotekę Open Computer Vision dającą możliwość bardzo szybkiego wykonywania operacji na obrazach, której dodatkową zaletą jest prostota użycia i bogactwo możliwości. Program ten posiada dwa tryby działania: pierwszy, w krórym za pomocą interfejsu użytkownik może ustawić parametry poszczególnych operacji wykonywanych na obrazach (wykorzystywany jest tu GUI dołączany do OpenCV) oraz z lini poleceń w oparciu o plik z parametrami. Standardowy przebieg pracy z programem to uruchomienie interfejsu dla przykładowej mapy celu stworzenia pliku konfiguracyjnego, a następnie wywołanie poprzez skrypt systemu operacyjnego programu zgodnie z ustalonymi parametrami dla pozostałych map.
- tree_gen program budujący minimalne drzewa rozpinające dla tablic współrzędnych punktów oraz wyznaczający wektory cech dla tych drzew. Program posiada plik konfiguracyjny pozwalający ustalić wartość od której rozrywane są krawędzie w drzewie, oraz jakie cechy mają się znaleźć w obliczanych wektorach. Dodatkową opcją programu jest wizualizacja konstruowanego drzewa (w postaci pliku graficznego), co jest wykonywane również z użyciem przedstawionej powyżej biblioteki OpenCV.
- my_clust program wykonujący analizę skupień. Implementuje on algorytm aglomeracyjny (hierarchiczny, wstępujący) dla wyznaczania klastrów. Użytą miarą podobieństwa jest odległość euklidesowa pomiędzy obiektami, natomiast odległości klastrów wyznaczane są jako odległość pomiędzy najbliższymi obiektami, pomiędzy najbardziej oddalonymi lub jako uśredniona odległość pomiędzy wszystkimi obiektami.
Dodatkowo istnieje również kilka małych programów, których głównym zastosowaniem jest transformacja danych pomiędzy tymi trzema głównymi, oraz polepszenie sposobu przedstawienia wyników użytkownikowi. Jeden z tych programów tworzy skrypt, wywołujący program montage z pakietu ImageMagick, który generuje miniatury map łącząc je w pliki zgodnie z podziałem na klastry.
Uzyskane wyniki
Jakość wykonywania etapu pierwszego (pobieranie współrzędnych punktów z map) można ocenić w pełni subiektywnie, ponieważ miarą jest tu fakt rozpoznania
wszystkich punktów oraz jednocześnie nie zakwalifikowanie jako punkt żadnego innego obiektu (np. granic). Jak wykazały testy programu jest to wykonywane z niemalże
pełną skutecznością dla dobrze dobranych parametrów operacji realizowanych w tym kroku. Jedyne (dosłownie pojedyncze) punkty zostały pominięte przez
program w przypadku bardzo mocno wypełnionych map (rzędu 3000 punktów) co stanowi promile ich całkowitej ilości i w żaden sposób nie wpływa na dalsze etapy.
Pozostałe etapy mają charakter typowo badawczy i ich rezultaty można odnosić do wyznaczanych w literaturze klas. Należy jednak zaznaczyć, że badania zostały
przeprowadzone na stosunkowo małej ilości map (70), z pewnością dla większej ich liczby możnaby uzyskać ciekawsze rezultaty. Dodatkowo warto też podkreślić
mnogość parametrów, którymi można wpływać na przetwarzanie, jak choćby:
- całościowa analiza map lub wstępna analiza poddrzew,
- parametr mówiący od jakiej odległości traktować składowe niezależnie,
- różne kombinacje wartości cech drzew (zaproponowane w naszym systemie oraz dużo innych możliwych),
- żądana ilość klastrów,
- metoda analizy skupień, itp.
 |
 |
 |
 |
Kolejna tabela pokazuje natomiast w jaki sposób zostały podzielone na klastry badane mapy:
 |
 |
 |
 |
 |
 |