Rozpoznawanie znaków alfabetu Tengwar - pisma elfów
Autor: Dorota Moskal
Prowadzący: dr inż. Witold Paluszyński
Raport wykonany w ramach projektu z przedmiotu "Metody i Algorytmy Sztucznej Inteligencji"
28.01.2012
Recognition of Tengwar alphabet - the Elvish script
Author: Dorota Moskal
Instructor: dr inż. Witold Paluszyński
The project described in this report has been completed to fulfill the requirements for the course: Methods of artificial intelligence.
28.01.2012
AbstractThe project was done under Matlab([1])with use of Bioinformatics Statistic and Image Processing Toolboxes. As input data it takes letters saved on separate images. Feature extraction is done with m-files written by Dinesh'a Dileep([2]), changed to meet the Tengwar characteristic. Classification is done with support vector machines([3]), which are commonly used for OCR problems. The results are compered to ones obtained with use of naive Bayesian classifier and binary trees. The system uses specific structure of tengwas (Elvish letters) to divide the classification into five sequential stages, instead of classfying each tengwa separately, making the system more effective. |
Opis zadania
Celem projektu ma być stworzenie systemu rozpoznającego litery alfabetu Tengwar - elfickiego pisma stworzonego przez J.R.R. Tolkiena. Zadanie to jest typowym przykładem problemu OCR(z ang. Optical Character Recognition). Można je podzielić na dwa etapy: przetwarzanie obrazu z pojedynczym znakiem oraz jego klasyfikacja.Do klasyfikacji znaków wykorzystane zostały maszyny wektorów nośnych([3]), będące powszechnie stosowane w systemach OCR. W celach porównawczych klasyfikacja została również przeprowadzona za pomocą naiwnego klasyfikatora Bayesowskiego oraz drzew binarnych. Stworzony system wykorzystuje charakterystyczną budowę tengw (liter alfabetu Tengwar) i dzieli klasyfikację na pięć etapów, pozwalając na efektywniejszą naukę klasyfikatorów.
Projekt wykonany został z wykorzystaniem programu Matlab([1]) z toolbox'ami Bioinformatics, Statistic oraz Image Processing. W toolbox'ie Bioinformatic dostępne są funkcje związane z svm: svmtrain pozwalająca na naukę maszyny oraz svmclassify dokonująca klasyfikacji danych za pomocą wytrenowanej wcześniej maszyny. Danymi wejściowymi są litery znajdujące się w osobnych plikach. Do ekstrakcji cech służą m-pliki bazujące na plikach autorstwa Dinesh'a Dileep (udostępnionych na stronie Matlaba([2])), zmodyfikowane na potrzeby omawianego zagadnienia.
Tengwy([4])
Podstawowy alfabet, tzw. Tengwar Fëanora, podzielony jest (według zasad fonetycznych) na cztery serie (tema) oraz 6 stopni (tyelle).Każda tengwa składa się z rdzenia „telco” oraz łuku („lúva”). Telco jest linią pionową, jego rozmiar i pozycja wyznacza tyelle: telco może być normalny( tyelle 1 i 2), podwyższony (3 i 4) lub krótki (5 i 6). Lúva, czyli łuk, przypisuje literze temę i częściowo tyelle; może być pojedynczy (parzyste tyelle) lub podwójny (nieparzyste tyelle), zamknięty (tema II i IV) lub otwarty (I i III), zwrócony w lewą (I i II) lub prawą stronę (III i IV).
Budowa tengw
Zestawienie liter Tengwaru
Dane wejściowe
Do realizacji projektu potrzebna była znaczna liczba danych - obrazów zawierających pojedyncze tengwy. Obrazy te zostały pozyskane z internetu - na wielu stronach poświęconych J.R.R. Tolkienowi przedstawiany jest alfabet elfów. Wyszukane zostały 192 obrazy, po 8 dla każdej z liter, zapisane za pomocą różnorakich czcionek. Litery przeskalowano do wielkości 50 na 50 pikseli za pomocą programu JBatch It ([5]). Następnie poszczególne tengwy zostały ręcznie dopasowane, tak aby wszystkie miały mniej więcej podobny rozmiar i położenie na rysunku.W przyszłości warto zgromadzić większą liczbę danych, co nie zostało zrobione ze względu na znaczną czasochłonność zadania.
Przykład zebranych danych - litery 'tinco' i 'ungwe'
Ekstrakcja cech
Jak zostało to wspomniane, do ekstrakcji cech wykorzystane zostały m-pliki Dinesh'a Dileep'a. Na początku procesu obraz zamieniany jest na binarny a następnie uzyskiwany jest jego szkielet. Potem rysunek dzielony jest na kilka części. Dostępne są dwa sposoby ekstrakcji, zapisane w dwóch różnych plikach: jedna bazująca na podziale całości na 9 obszarów (w dalszej części raportu określanego jako 'podział I') oraz druga bazująca na dwóch podziałach: na 3 poziome oraz 3 pionowe obszary (w dalszej części określanego jako 'podział II'). Dla każdego z wydzielonych obszarów wyliczane jest 9 znormalizowanych cech:- liczba pionowych linii,
- liczba poziomych linii,
- liczba skośnych linii /,
- liczba skośnych linii \,
- suma długości pionowych linii,
- suma długości poziomych linii,
- suma długości skośnych linii /,
- suma długości skośnych linii \,
- łączna powierzchnia szkieletu.
Ponadto wyliczane były cechy dla całej litery:
- liczba eulera,
- stosunek liczby pikseli w literze do łącznej liczby pikseli obrazu,
- średnica najmniejszej elipsy opisującej szkielet.
Największą poprawę uzyskano za pomocą dwóch zabiegów. Przede wszystkim należało odwrócić rysunek, tak by zamienić tło z obiektem (operacja ta nie występuje w bwmorph, jest jednak oczywiście bardzo prosta do wykonania - w tabeli została określona jako 'inverse'). Drugim kluczowym elementem było wykorzystanie dla podziału I operacji 'thin' zamiast 'skel' i obcięcie przetwarzanego obrazu do samej litery .
Poza zmianami w obrazie, zwiększenie skuteczności klasyfikacji przyniosło rozszerzenie wektora cech o elementy opisujące całą literę uzyskane za pomocą funkcji regionprops wyliczające pewne statystyki obrazu. I tak dodane zostały współrzędne ośmiu skrajnych punktów szkieletu (jak na rysunku) oraz położenie i wielkość obszaru litery na rysunku (ang. bounding box).
Ostatecznie, za najlepszą znalezioną kombinację funkcji przetwarzania obrazu i ekstrakcji cech uznano:
- dla podziału I: thicken -> inverse -> thin -> crop to bounding box,
- dla podziału II: inverse -> skel,
- dodanie danych statystycznych o skrajnych punktach i bounding box.
Skrajne punkty obiektu
Klasyfikacja
Proces klasyfikacji liter przebiegał dość niestandardowo, wykorzystano bowiem omówioną wcześniej charakterystyczną budowę tengw. Wytrenowane zostało pięć maszyn wektorów nośnych, które prawie niezależnie klasyfikowały literę, każda ze względu na wybraną cechę. Uzyskany w ten sposób pięcioelementowy, binarny wektor jednoznacznie wskazuje położenie litery w tabeli pokazanej powyżej.Klasyfikacja I
Rozstrzyga długość telco - do jednej grupy (w wektorze binarnym jedynka) zalicza dłuższe rdzenie, a więc telco normalne i podwyższone, do drugiej (w wektorze 0) - krótki rdzeń. W efekcie określa, czy litera należy do tyelli od 1 do 4 czy do 5 lub 6.Klasyfikacja II
Uruchamiana tylko w przypadku, kiedy klasyfikacja I zwróciła 1. Rozstrzyga poziom telco - do jednej grupy (w wektorze binarnym jedynka) zalicza normalne rdzenie, do drugiej (0) podwyższone. W efekcie określa, czy litera należy do tyelli od 1 lub 2 czy do 3 lub 4.Klasyfikacja III
Rozstrzyga liczbę lúva - do jednej grupy (1) zalicza litery o pojedynczym łuku, do drugiej (0) - o podwójnym. W efekcie określa, czy litera należy do tyelli nieparzystej czy parzystej.Klasyfikacja IV
Rozstrzyga, w którą stronę zwrócony jest lúva - do jednej grupy (1) zalicza te ozwrocie w prawo, do drugiej (0) - w lewo. W efekcie określa, czy litera należy do tema I lub II czy tema III lub IV.Klasyfikacja V
Rozstrzyga o zamknięciu lúva - do jednej grupy (1) zalicza litery o otwartym łuku, do drugiej (0) - o zamkniętym. W efekcie określa, czy litera należy do tema nieparzystej czy parzystej.Przykładowo załóżmy, że otrzymany wektor ma postać [1 0 1 1 0]. Uzyskujemy więc literę o dłuższym telco [1 0 1 1 0], podwyższonym [1 0 1 1 0] i lúva pojedynczym [1 0 1 1 0], zwróconym w prawo [1 0 1 1 0] i zamkniętym [1 0 1 1 0]. Jest więc to formen (tyelle 3, tema II).
Zaproponowane rozwiązanie posiada szereg zalet w stosunku do klasycznego podejścia rozpoznawania każdej litery osobno. Tengwy mają bardzo podobną budowę, poszczególne litery niewiele się różnią. Klasyfikacja kaskadowa pozwala na wytrenowanie klasyfikatorów właśnie ze względu na te szczególne różnice, co znacznie poprawia prawdopodobieństwo prawidłowej klasyfikacji. Dodatkowo dla wszystkich liter potrzebujemy tylko 4 lub 5 przebiegów do uzyskania odpowiedzi. Poza tym wymaga mniejszej liczby danych potrzebnych do nauki klasyfikatora - na każdym z etapów wykorzystuje się wszystkie dane w jednakowym stopniu (z wyjątkiem klasyfikatora drugiego, który wykorzystywany jest dla 2/3 danych).
Badania
Każde badanie wykonywane było 300 razy. Za każdym razem do treningu losowano (zaimplementowanym w Matlabe generatorem liczb pseudolosowych) pewną grupę obrazów, w której znajdowała się taka sama liczba rysunków każdej tengwy. Pozostałe obrazy stanowiły grupę testową. Następnie dokonywana była klasyfikacja - osobno dla pierwszej i drugiej grupy. W przypadku zestawu uczącego prawie zawsze uzyskiwano 100% poprawność. Skuteczność klasyfikatora określana była przez rezultaty otrzymane dla grupy testowej. Liczony był procent błędnych odpowiedzi dla każdego z trzystu przebiegów, po czym wyznaczano średnią błędu:- dla każdej z klasyfikacji osobno,
- łącznie dla wszystkich klasyfikacji,
- łączny procent błędnie sklasyfikowanych tengw (około 20%-25% błędnie sklasyfikowanych tengw miało błąd w co najmniej dwóch klasyfikacjach).
Testy przeprowadzono pod trzema kątami:
- przetwarzaniem obrazu tengwy (omówione wyżej); w tym wypadku funkcja swmtrain uruchamiana była z domyślnymi ustawieniami, zaś zestaw treningowy miał 72 litery,
- dobór typu maszyny svm; również w tym wypadku zestaw treningowy miał 72 litery; wykorzystano najlepszą znalezioną ekstrakcję cech,
- wielkość danych wykorzystanych do uczenia; wykorzystano najlepszą znalezioną ekstrakcję cech i domyślne ustawienia swmtrain.
Dobór maszyn svm
Funkcja swmtrain pozwala na dobór szeregu opcji dla maszyny svm. Testy przeprowadzone zostały dla 4 rodzajów jądra: liniowego, kwadratowego, sześciennego oraz gaussowskiego. Jądro gaussowskie zupełnie się nie sprawdziło, również kwadratowe dało stosunkowo słabe wyniki. Pomiędzy liniowym a sześciennym różnica była niewielka, na korzyść liniowego.Następnie sprawdzone zostały różne metody wyznaczania hiperpłaszczyzny rozdzielającej dane. Jako domyślna wykorzystywana jest Sequential Minimal Optimization, inne dostępne to Quadratic programming(z Optimization Toolbox) oraz metoda najmniejszych kwadratów. Dwie pierwsze dały bardzo zbliżone rezultaty, ostatnia wypadła najgorzej.
Jako trzeci parametr sprawdzana była pojemność c wykorzystywana przy wyliczaniu funkcji błędu, jednak jej zmiany nie przynosiły widocznych efektów w jakości klasyfikacji.
Liczebność zestawów
Maszyny svm uczone były kolejno na zestawach zawierających 48, 72, 96 i 120 obrazów. Rozszerzenie zestawu uczącego do 96 poprawiło jakość klasyfikacji, jednak dodanie kolejnych 24 obrazów niewiele pomogło. Natomiast zmniejszenie go do 48 spowodowało znaczne zwiększenie liczby błędów.Inne klasyfikatory
Dla porównania przeprowadzono klasyfikację za pomocą naiwnego klasyfikatora bayesowskiego oraz drzew binarnych, wykorzystując pięcioetapowy system klasyfikacji. Ze względu na bardzo wolne działanie dla klasyfikatora bayesowskiego badanie powtórzono tylko 10 razy. W obu przypadkach uzyskano niecałe 70% skuteczności,co pokazuje jak dużą przewagę przy rozwiązywaniu problemów OCR mają maszyny wektorów nośnych. Ponadto w około 10% klasyfikator Bayesowski w ogóle nie znajdował odpowiedziZebrane wyniki wybranych badań pokazuje tabela.
|
charakterystyka badania |
klasyfikacja |
suma błędów |
błędnych liter |
||||
|
I |
II |
II |
IV |
V |
|||
|
Badania operacji morfologicznych |
|||||||
|
Oryginalne funkcje ekstrakcji cech* |
0.1491 |
0.1233 |
0.2772 |
0.1059 |
0.1322 |
0.7878 |
0.4998 |
|
Dodatkowe operacje: oba podziały: invert |
0.0147 |
0.0230 |
0.0841 |
0.0631 |
0.2052 |
0.3970 |
0.3135 |
|
Dodatkowe operacje: oba podziały: thicken -> invert -> thin -> crop to box |
0.0023 |
0.0117 |
0.1017 |
0.0583 |
0.1015 |
0.275 |
0.2240 |
|
Dodatkowe operacje: podział I: thicken -> invert -> thin -> crop to box podział II: invert -> thin |
0.0016 |
0.0095 |
0.0923 |
0.0376 |
0.0971 |
0.2381 |
0.2014 |
|
Dodatkowe operacje: oba podziały: invert -> thin |
0.0108 |
0.0154 |
0.0981 |
0.0391 |
0.1122 |
0.2755 |
0.2296 |
|
Dodatkowe operacje**: podział I: thicken -> invert -> thin -> crop to box podział II: invert -> skel |
0.0017 |
0.0108 |
0.0866 |
0.0264 |
0.0999 |
0.2254 |
0.1787 |
|
Dodatkowe operacje: podział I: thicken -> invert -> skel -> crop to box podział II: invert -> skel |
0.0011 |
0.0091 |
0.0957 |
0.0441 |
0.0858 |
0.2357 |
0.2016 |
|
Badania svm |
|||||||
|
Jądro liniowe, metoda Sequential Minimal Optimization, pojemność c = 1** |
0.0017 |
0.0108 |
0.0866 |
0.0264 |
0.0999 |
0.2254 |
0.1787 |
|
Jądro kwadratowe |
0.0108 |
0.0174 |
0.0971 |
0.0343 |
0.2122 |
0.3718 |
0.3066 |
|
Jądro sześcienne |
0.0064 |
0.0132 |
0.0521 |
0.0329 |
0.1178 |
0.2224 |
0.1866 |
|
Jądro gaussowskie |
0.3287 |
0.4408 |
0.4697 |
0.4697 |
0.4659 |
2.2748 |
0.9157 |
|
Metoda Quadratic programming |
0.0015 |
0.0106 |
0.0826 |
0.0266 |
0.0963 |
0.2177 |
0.1713 |
|
Metoda minimalnych kwadratów |
0.0114 |
0.0162 |
0.1090 |
0.0516 |
0.1124 |
0.3005 |
0.2243 |
|
Pojemność C = 0.1 |
0.0019 |
0.0104 |
0.0853 |
0.0279 |
0.0939 |
0.2194 |
0.1735 |
|
Pojemność C = 5 |
0.0020 |
0.0113 |
0.0841 |
0.0274 |
0.1019 |
0.2268 |
0.1780 |
|
Badania wielkości zestawu uczącego |
|||||||
|
48 |
0.0026 |
0.0109 |
0.1031 |
0.0317 |
0.1148 |
0.2630 |
0.2113 |
|
72** |
0.0017 |
0.0108 |
0.0866 |
0.0264 |
0.0999 |
0.2254 |
0.1787 |
|
96 |
0.0007 |
0.0103 |
0.0708 |
0.0249 |
0.0949 |
0.2016 |
0.1593 |
|
120 |
0.0003 |
0.0099 |
0.0638 |
0.0268 |
0.0998 |
0.2005 |
0.1589 |
|
Inne metody |
|||||||
|
Naiwny klasyfikator bayesowski |
0.0083 |
0.0083 |
0.3667 |
0.0667 |
0.1000 |
0.5500 |
0.4667 |
|
Drzewa binarne |
0.0261 |
0.0315 |
0.1386 |
0.0988 |
0.0884 |
0.3833 |
0.3075 |
* bez dodatkowych cech - bounding box i skrajnych punktów – uwzględnionych we wszystkich kolejnych badaniach
** te same badania, wstawione w celach porównawczych w obrębie danej grupy
Wnioski
Podstawowym problemem okazało się przetworzenie obrazów. Elfickie czcionki często zawierają ozdobniki, które znacznie utrudniają klasyfikację. Podczas wykonywania operacji morfologicznych niektóre z tengw o otwartym łuku były zamykane, zaś próby niedopuszczenia do takich sytuacji powodowały, że tengwy o miejscowo wyjątkowo cienkiej linii były przerywane. Widoczne jest to w wynikach - największy odsetek błędów pojawił się przy klasyfikacji III - pomiędzy podwójnym a pojedynczym lúva.W przyszłości, w celu uzyskania lepszych wyników największą uwagę prawdopodobnie należałoby poświęcić właśnie tej części projektu.
W przypadku samych maszyn svm zdecydowanie najgorzej wypadło wykorzystanie jądra gaussowskiego oraz metody najmniejszych kwadratów. W pozostałych przypadkach wyniki były podobne.
Uzyskana skuteczność wyniosła prawie 85%. Jest to wynik dobry, jednak oczekiwać można by lepszych efektów. W przyszłości warto poprawić zwłaszcza operacje morfologiczne na obrazach, tak aby nie pojawiały się wspomniane błędy w tworzeniu szkieletu. Pod uwagę można też wziąć rozszerzenie zestawu danych ze względu na dużą różnorodność czcionek.
Materiały źródłowe
- Strona programu Matlab
http://www.mathworks.com/ - Strona autora projektu i źródło
http://www.ece.iisc.ernet.in/~dileep
http://www.mathworks.com/matlabcentral/fx_files/24624/6/feature_extraction.zip
- Omówienie maszyn wektorów nośnych
www.cs.put.poznan.pl/jstefanowski/ml/SVM.pdf - Strona poświęcona pismu Tengwar
http://tengwar.art.pl/tengwar/tengwar.php - strona programu JBatch It, w projekcie wykorzystano wersję trial
http://www.batchimage.com/product/jbatchit/