Laboratorium z rozpoznawania obrazów sem. 9 informatyki, rok 2008/09 Reguły gry



Pobieranie 32.95 Kb.
Data07.05.2016
Rozmiar32.95 Kb.


LABORATORIUM Z ROZPOZNAWANIA OBRAZÓW

Sem. 9 informatyki, rok 2008/09

Reguły gry:

Programy pisane są pojedynczo (tj. nie w grupach), kolejność oddawania i wybór zadań – wedle uznania. Język programowania: C, C++, Java, C#, Pascal lub Python. Zalecane jest pisanie programów konsolowych.



Zasady oceny:

Każde zadanie jest punktowane, a ocena uzależniona od liczby zdobytych punktów. Przy zaliczaniu zadania należy dobrze orientować się w kodzie źródłowym odpowiedniego programu. Prowadzący odpytuje studenta z jego znajomości, np. przez wykreślenie krótkich fragmentów programu, które student musi prawidłowo uzupełnić lub polecenie napisanie fragmentu programu pod okiem prowadzącego. Efektywność rozwiązania (szybkość generacji wyniku, oszczędność pamięci) ma pewne znaczenie dla oceny danego zadania.


Zależność ocen od liczby zdobytych punktów:

[ 0, 49) – ocena 2; [49, 60) – ocena 3;

[60, 70) – ocena 3.5; [70, 80) – ocena 4;

[80, 90) – ocena 4.5; [90, 100] – ocena 5.


Zadanie 1

Napisz program generowania żądanej liczby losowych punktów w d-wymiarowej przestrzeni cech:



  1. w obszarze kilku hiperkwadratów o zadanym boku ze środkiem w punkcie o zadanych współrzędnych. Rozkład punktów w obrębie hiperkwadratów – jednostajny (równomierny);

  2. w obszarze kilku hiperkwadratów o zadanym boku ze środkiem w punkcie o zadanych współrzędnych. Rozkład punktów w obrębie hiperkwadratów – jednostajny (równomierny), ale w odróżnieniu od punktu a) dozwolone są tylko współrzędne całkowite losowanych punktów;

  3. w obszarze kilku hiperkul o zadanych promieniach ze środkiem w punkcie o zadanych współrzędnych. Rozkład punktów w obrębie hiperkuli – jednostajny (równomierny). Wskazówka: należy losować punkty w obrębie hiperkwadratu opisującego daną hiperkulę, a następnie odrzucać punkty nie mieszczące się w hiperkuli.

Uwaga: parametry zadania, tj. położenie środka, bok/promień i liczba punktów są osobne dla każdego hiperkwadratu/hiperkuli!

Liczba klas (każdy hiperkwadrat/hiperkula jest osobną klasą) ograniczona do 3, wymiar do 10, liczba punktów (łącznie) w zbiorze uczącym do 3000. Zastosować metrykę euklidesową. Współrzędne punktów mają być losowane z dokładnością do 0.01.

Zapisać wygenerowany zbiór do pliku tekstowego.

Format pliku: pierwszy wiersz nagłówkowy – liczba klas, liczba cech, liczba punktów. Wartości oddzielone tabulatorami. W następnych wierszach dane: każdy punkt to jeden wiersz. Najpierw etykieta (numer) klasy, a potem po kolei wszystkie cechy. Wartości oddzielone tabulatorami. Tej konwencji zapisu danych w pliku będziemy się trzymać we wszystkich zadaniach!


Przykład (abstrakcyjny): mamy zbiór danych 3-wymiarowych (tj. o 3 cechach) z 2 klas.

Klasa 1 (3 punkty): (4,–1, 0); (2,0.5,–1.25); (–2,1,3.2);

Klasa 2 (2 punkty): (2,1,1); (–2, 3,0).

Postać pliku:

2 3 5

1 4.00 –1.00 0.00



1 2.00 0.50 –1.25

1 –2.00 1.00 3.20

2 2.00 1.00 1.00

2 –2.00 3.00 0.00

UWAGA. Dane w pliku nie zawsze muszą być ułożone klasami.

Poprawność wygenerowanych zbiorów można łatwo sprawdzić (wizualnie) w Excelu.


(5 + 3 + 5 = 13 pkt.)


Zadanie 2


Napisz procedurę dla standaryzacji danych 2 zbiorów (uczącego i testowego) parametrami wyznaczonymi z pierwszego z nich. Należy zaimplementować 2 metody standaryzacji:

  1. klasyczną, z wykorzystaniem średnich wartości cech oraz ich odchyleń standardowych;

  2. skalującą liniowo do przedziału [0, 1] (minimum przyjmowane przed daną cechę zostaje w wyniku standaryzacji „przetransformowane” do wartości 0, zaś maksimum – do wartości 1).

Dokładniej: w wersji a) xi,j’ := (xi,j – avg(j)) / sd(j), gdzie xi,j i xi,j’ są odpowiednio oryginalną i postandaryzowaną wartością j-tej cechy i-tej próbki danego zbioru, zaś avg(j) i sd(j) odpowiednio średnią i odchyleniem standardowym wartości j-tej cechy.
Proszę obsłużyć przypadek jednakowych wartości na pojedynczej cesze (przyjmuje się wówczas jako odch. stand. (lub czynnik skalujący w wersji b) wartość 1).
(4 + 3 = 7 pkt.)


Zadanie 3


Zaimplementować procedurę klasyfikacji przy użyciu reguły decyzyjnej k najbliższych sąsiadów (k-NN). Zbiory danych (uczący oraz testowy) będą dostarczone przez prowadzącego. Typ standaryzacji danych ( a) lub b) wg zadania 2, lub brak standaryzacji) będą podawane na starcie, jako opcja programu przekazywana z wiersza poleceń. Metryka – miejska lub euklidesowa (kolejna opcja czasu wykonania). Parametr k jest również wybierany przez użytkownika.

Proszę zadbać o odpowiednią szybkość klasyfikacji. Należy pomierzyć czas klasyfikacji. (Wskazówka: w C/C++ można wykorzystać funkcję clock().)

Dodatkowo program powinien mieć opcję wyboru metody rozstrzygania remisów. Np. dla k=5 i 3 klas może się zdarzyć, że wśród 5 najbliższych sąsiadów jakiejś próbki są 2 punkty z klasy pierwszej, 1 z klasy drugiej i 1 z klasy trzeciej. Jest remis między klasą 1 i 3. Do której klasy przypisać próbkę klasyfikowaną? Należy zaimplementować 4 warianty:


  1. próbkę przypisujemy do klasy z najmniejszym numerem wśród tych, które remisują;

  2. próbkę przypisujemy do klasy najbardziej licznej (w zbiorze uczącym, rzecz jasna) wśród tych, które remisują;

  3. wyboru klasy wśród „zwycięskich remisowych” dokonujemy losowo, z prawdopodobieństwem wybrania każdej klasy jednakowym (tj. jeśli są 3 zwycięskie klasy o takiej samej liczbie głosów, to każda ma szansę bycia wylosowaną 1/3);

  4. wyboru klasy wśród „zwycięskich remisowych” dokonujemy losowo, ale prawdopodobieństwa wyboru danej klasy są wprost proporcjonalne do liczności zwycięskich klas w zbiorze uczącym.
    Przykład: k=10, 4 klasy, liczności klas w zbiorze uczącym: 100, 200, 300, 100 punktów. Próbka x otrzymała 4 głosy z klasy pierwszej, 1 głos z klasy drugiej, 4 głosy z klasy trzeciej i 1 głos z klasy czwartej. Remis między klasą pierwszą i trzecią. Ponieważ jednak klasa pierwsza ma 100 próbek, a trzecia 400, więc prawdopodobieństwo wylosowania jako zwycięzcy klasy pierwszej ma wynosić 1/4, zaś klasy trzeciej 3/4.


Składnia:

kNNclassify zbior_ucz zbior_test std met remisy logfile.txt

kNNtrain – nazwa programu;
std: – stand. klasyczna: wartość 1, stand. do przedziału [0, 1]: wartość 2; brak standaryzacji: 3;
met – metryka (np. m | e, lub 0 | 1);
remisy – wariant rozstrzygania remisów (np. 0..3 lub a | b | c | d);
logfile.txt – plik, w którym będzie zapisane parametry wywołania programu oraz błąd na zbiorze uczącym).
Wskazówka:

Jeśli rozpatrywana próbka ze zbioru uczącego jest położona bliżej aktualnie badanej próbki zbioru testowego niż aktualny k-ty (według odległości) sąsiad próbki zbioru testowego, to uaktualniamy listę sąsiadów. Jest to procedura dość wolna w najgorszym przypadku, ale szybka w przypadkach typowych. Rozwiązanie oparte na sortowaniu odległości, a następnie wybieraniu k najbliższych jest w praktyce zbyt wolne (chyba że Pan / Pani udowodni prowadzącemu, że jest inaczej :-).


(8 pkt. za implementację któregokolwiek z wariantów rozstrzygania remisów +

po 2 pkt za implementację wariantów pozostałych = 14 pkt. (max))




Zadanie 4


Napisz program realizujący klasyfikator minimalnoodległościowy, będący de facto klasyfikatorem 1-NN ze zbiorem zredukowanym jedynie do obiektów będących środkami ciężkości poszczególnych klas. Na przykładzie zbioru IRIS.TEA oblicz procent błędów klasyfikacji przy następującej metodologii testów:

  1. zbiorem testowym jest cały zbiór, ale także dla całego zbioru wyznaczamy środki ciężkości klas;

  2. zbiór uczący stanowi suma mnogościowa pierwszej połowy każdej klasy (w przypadku zbioru Iris będzie to 25 obiektów wybranych z każdej klasy), a pozostałe tworzą zbiór testowy.

Uwaga: program ma działać z wiersza poleceń, z dwoma argumentami – nazwa pliku (np. Iris.tea) i identyfikator podzadania (czyli „a” lub „b”).
(4 + 3 = 7 pkt.)


Zadanie 5


Zaimplementować i przetestować klasyfikator voting k-NN
( http://szgrabowski.kis.p.lodz.pl/ro05/phd-final.doc , rozdz. 7.4, str. 137+; wyniki eksperymentów w rozdz. 7.6 ) na zbiorach Ferrites ( http://szgrabowski.kis.p.lodz.pl/knn/Ferrites.zip ) i Remotes250

( http://szgrabowski.kis.p.lodz.pl/knn/Remotes250.zip ).


(12 pkt.)


Zadanie 6

Zaimplementować 2 algorytmy redukcji zbioru odniesienia: algorytm Tomeka
(
http://szgrabowski.kis.p.lodz.pl/ro05/phd-final.doc , rozdz. 6.2, str. 104+ ) i algorytm Skalaka
(
http://szgrabowski.kis.p.lodz.pl/ro05/phd-final.doc , rozdz. 6.2, str. 108+, chodzi o pierwszy z dwóch przedstawionych algorytmów Skalaka ). Testy (redukcja + dalsza klasyfikacja) przeprowadzić na danych Ferrites: ftrain01.txt jest zbiorem uczącym (w przypadku naszego zadania: zbiorem poddawanym redukcji), a ftest01.txt jest zbiorem testowym. Przed redukcją należy oba zbiory postandaryzować zgodnie z procedurą z zad. 2a. Zmierzyć osobno czas redukcji oraz czas klasyfikacji przy użyciu zbioru zredukowanego. Wyniki eksperymentów (liczność zbioru zredukowanego, % błędów klasyfikacji, czas redukcji i czas klasyfikacji) mają być zapisane do pliku tekstowego (o nazwie np. log.txt). Ponieważ alg. Skalaka ma naturę probabilistyczną, należy wykonać go 5-krotnie i wszystkie 5 wyników (% błędów i czasy) zapisać w pliku log.txt.

(7 (S) + 6 (T) = 13 pkt.)



Zadanie 7

Podobieństwo między dokumentami tekstowymi (np. webowymi) mierzy się zwykle jako cosinus kąta między wektorami reprezentującymi te dokumenty. Wektory te mają tyle współrzędnych, ile jest słów w słowniku, tj. ile jest unikalnych słów w całej kolekcji dokumentów. Jedną z najprostszych metod przypisywania wag do „termów” (tj. słów) w obrębie wektora jest term count model, gdzie waga danego słowa to liczba jego wystąpień w danym dokumencie podzielona przez łączną liczbę słów w dokumencie.


Przykład (b. prosty): mamy 3 dokumenty:

Doc #1: this is a horse

Doc #2: she rode a black horse

Doc #3: a dog, a dog and two horses

Słownik: a, and, black, dog, horse, horses, is, rode, she, this, two

Wektor dla dokumentu #1: [1/4, 0, 0, 0, 1/4, 0, 1/4, 0, 0, 1/4, 0]

Wektor dla dokumentu #2: [1/5, 0, 1/5, 0, 1/5, 0, 0, 1/5, 1/5, 0, 0]

Wektor dla dokumentu #3: [2/7, 1/7, 0, 2/7, 0, 1/7, 0, 0, 0, 0, 1/7]


Cosinus kąta między wektorami V1, V­2 określa się wzorem: i jest to liczba z przedziału 0 (brak jakiegokolwiek podobieństwa) od 1 (pełne podobieństwo, tj. niekoniecznie dokumenty identyczne, ale np. posiadające ten sam zestaw słów, ale być może w innej kolejności, np. „Ala ma kota” i „kota ma Ala”).
W zadaniu należy policzyć wektory dla 15 dokumentów z angielskiej wikipedii, po 5 z kategorii: zoologia, muzyka poważna, informatyka, policzyć cosinusową miarę podobieństwa dla każdej pary, a następnie wypisać 10 par najbardziej do siebie podobnych dokumentów (wraz z wartościami miary podobieństwa) i 10 par najmniej do siebie podobnych dokumentów (również z wartościami miary podobieństwa).
Uwagi.

Można, ale nie trzeba użyć specjalnego parsera html – alternatywą jest „ręczne” wyciąganie tekstu wyłącznie między parami znaczników


i
(można założyć, że interesują nas tylko wiersze zaczynające się od
, a kończące na
), z pominięciem innych znaczników (np. usuwamy z interesujących nas paragrafów znaczniki , , , etc.).

Należy zignorować interpunkcję (aby np. „dog” i „dog,” nie zostały potraktowane jako różne słowa).

Nie należy rozróżniać małych i wielkich liter.

Przy tworzeniu zbiorczego słownika oraz (później) wektorów dla osobnych dokumentów należy zignorować tzw. stop words, tj. najbardziej popularne słowa w danym języku (w naszym przypadku: angielskim), gdyż zniekształcają / spłaszczają one wartości miary podobieństwa. Słowa te to „a”, “an”, „the”, „of”, „in”, „from”, „to” etc. (należy wpisać w programie ok. 20-30 takich słów).


(14 pkt.)

Zadanie 8

Zadanie polega na rozpoznawaniu kształtów obiektów na obrazach. Obiekty są elipsami o różnym mimośrodzie; wyróżnia się 3 klasy takich elips (od elips najbardziej zbliżonych do koła do najbardziej „wydłużonych”). Na podstawie obrazów tworzących zbiór uczący (7) należy sklasyfikować, przy użyciu reguły jednego najbliższego sąsiada, obiekty na obrazach testowych (5). Do klasyfikacji proszę użyć tylko jednej cechy: stosunku pola do kwadratu obwodu obiektu.

Obrazy zapisane są w 24-bitowym formacie BMP (bez kompresji), nagłówek pliku zajmuje 54 bajty, szerokość bitmapy zapisana jest na bajtach 19-tym i 20-tym (licząc od 1; bajt 19-ty jest mniej znaczący), zaś wysokość – na bajtach 23-tym i 24-tym (23-ty mniej znaczący). Oczywiście nie trzeba tych obrazów czytać „ręcznie”, można wykorzystać stosowną bibliotekę np. Javy.

UWAGI:


  1. Pole obiektu zamkniętego można policzyć przy użyciu operacji zalewania obszaru; najprostsza w implementacji jest procedura rekurencyjna (http://en.wikipedia.org/wiki/Flood_fill ).

  2. Obrazy są kiepskiej jakości (BMP  JPEG  BMP przy wysokim stopniu kompresji), dlatego zaleca się następujące postępowanie: obraz konwertujemy do odcieni szarości; binaryzujemy i dopiero wtedy liczymy obwód i pole obiektu.

  3. Ad 2: Obiekt nie musi być ciemniejszy od tła! Co więcej, kolor tła i kolor obiektu mogą być dość zbliżone, więc proszę nie progować z wykorzystaniem „sztywnego” progu (np. jasność 128). Zamiast tego można znaleźć dwie mody w histogramie i jako próg przyjąć ich średnią arytmetyczną.

(20 pkt.)

Ad 7, przykład:
Poniższe akapit, wzięty z

http://en.wikipedia.org/wiki/CPU_cache

jest traktowany jako (cały) dokument (nr 0):


The diagram on the right shows two memories. Each location in each memory has a datum (a cache line), which in different designs ranges in size from 8 to 512 bytes. The size of the cache line is usually larger than the size of the usual access requested by a CPU instruction, which ranges from 1 to 16 bytes. Each location in each memory also has an index, which is a unique number used to refer to that location. The index for a location in main memory is called an address. Each location in the cache has a tag that contains the index of the datum in main memory that has been cached. In a CPU's data cache these entries are called cache lines or cache blocks.
Poniższe 3 akapity, zaczerpnięte z

http://en.wikipedia.org/wiki/Johann_Sebastian_Bach

są traktowane jako osobne dokumenty (nr 1, 2, 3):

Johann Sebastian Bach (pronounced [jo'han/'jo?han ze'bastjan 'bax]) (31 March 1685 [O.S. 21 March] – 28 July 1750) was a German composer and organist whose sacred and secular works for choir, orchestra, and solo instruments drew together the strands of the Baroque period and brought it to its ultimate maturity.[1] Although he introduced no new forms, he enriched the prevailing German style with a robust contrapuntal technique, an unrivalled control of harmonic and motivic organisation in composition for diverse musical forces, and the adaptation of rhythms and textures from abroad, particularly Italy and France.

Revered for their intellectual depth, technical command and artistic beauty, Bach's works include the Brandenburg concertos, the Goldberg Variations, the English Suites, the French Suites, the Partitas, the Well-Tempered Clavier, the Mass in B Minor, the St. Matthew Passion, the St. John Passion, the Magnificat, The Musical Offering, The Art of Fugue, the Sonatas and Partitas for violin solo, the Cello Suites, more than 200 surviving cantatas, and a similar number of organ works, including the celebrated Toccata and Fugue in D Minor.

While Bach's fame as an organist was great during his lifetime, he was not particularly well-known as a composer. His adherence to Baroque forms and contrapuntal style was considered "old-fashioned" by his contemporaries, especially late in his career when the musical fashion tended towards Rococo and later Classical styles. A revival of interest and performances of his music began early in the 19th century, and he is now widely considered to be one of the greatest composers in the Western tradition, being included with Ludwig van Beethoven and Johannes Brahms as one of the "three Bs".

Oto wartości miary cosinusowej dla tych par dokumentów:

0 1 0.0245903704521 // b. mała wartość, bo Bach ma niewiele wspólnego z procesorami...

0 2 0.0300099424404 // j.w.

0 3 0.0192130139235 // j.w.

1 2 0.33996692133

1 3 0.42414659285 // maksimum dla pary (1, 3)

2 3 0.190704311925


Uwaga: bez wyrzucania stop words, wyniki wyszły dużo bardziej zbliżone:

0 1 0.258924116452

0 2 0.384754087479

0 3 0.325882731786

1 2 0.463556429717

1 3 0.53672340922



2 3 0.445769510621



Pobieranie 32.95 Kb.





©absta.pl 2020
wyślij wiadomość

    Strona główna