Wrocław, 15 czerwca 2009

Raport przygotowany na zaliczenie przedmiotu: "Metody i algorytmy sztucznej inteligencji."

Autor: Tomasz Kwiatkowski, Piotr Spędzia

Identyfikacja ciągów znaków japońskich

Abstrakt

Celem projektu było napisanie programu, który będzie rozpoznawał ciągi znaków zapisane alfabetem japońskim (hiraganą). Projekt został zrealizowany w środowisku C, do przetwarzania obrazów użyto funkcje z biblioteki OpenCv, a do rozpoznawania użyto sieci neuronowych dostępnych w bibliotece fann. Wejściem sieci był wektor binarny reprezentujący wartości pikseli. Pokazano, że w alfabecie japońskim istnieje grupa liter, które są do siebie bardzo podobne i nawet złożone sieci nie radzą sobie z ich rozpoznawaniem. W praktycznych zastosowaniach należałoby użyć bardziej skomplikowanych algorytmów ekstrakcji cech.

Wrocław, June 15 2009

This report has been prepared as a requirement for the course: "Methods and algorithms of artificial intelligence."

Author: Tomasz Kwiatkowski, Piotr Spędzia

Japanese character sequence recognition

Abstract

The aim of this project was to design a program, which would recognize a sequence of Japanese characters, written in hiragana. The project was implemented in C (programming language), image processing - with use of OpenCV library and recognition - with artificial neural network (FANN library). The input of the network was a binary vector representing values of image piksels. It was show that in Japanese written alphabet - hiragana exist a group of letters which are very similar to each other and even complex neural network are not capable of correct recognition. To achieve more satisfactory results more sophisticated feature extraction algorithms should be used.

Keywords: character recognition, neural-network, hiragana, ocr

Wstęp

Rozpoznawanie pisma jest możliwe dzięki zastosowaniu metod z dziedziny rozpoznawania wzorców zaliczanej do sztucznej inteligencji. Oprogramowanie OCR wykorzystuje różne metody segmentacji obrazu, aby wyodrębnić poszczególne znaki, które następnie są najczęściej osobno klasyfikowane jako poszczególne litery. Zwykle w tym procesie wykorzystywane są sieci neuronowe. Wraz ze wzrostem popularności komputerów tłumaczenie drukowanych dokumentów na formę elektroniczną staje się coraz ważniejsze. W tym miejscu zauważyć można jak ważną rolę pełni oprogramowanie OCR. O ile oprogramowanie takie dla większości "zachodnich języków" jest dość popularne oraz szeroko stosowane, języki dalekiego wschodu, takie jak język japoński czy chiński, ze względu na charakterystykę języka i nieco mniejsze zapotrzebowanie są rzadziej spotykane. Projekt ten jest próbą zmierzenia się z tą ciekawą tematyką.

Pismo japońskie

Pismo japońskie wywodzące się z pisma chińskiego jest jednym z najbardziej skomplikowanych rodzajów pism. Chińskie znaki (słowo kanji - znaczy "znaki cesarstwa Han") oparte są bowiem na piśmie obrazkowym, gdzie jeden znak symbolizuje jedną ideę.

Żeby czytać i pisać po japońsku, należy znać: około 2000 znaków kanji, dwa alfabety sylabiczne kana, czyli hiragana i katakana, dodatkowo rōmaji - w tłumaczeniu: 'znaki łacińskie' (większość polskich), czyli zapis alfabetem łacińskim - używany głównie w materiałach dla obcokrajowców.

Tradycyjnie język japoński zapisywany był, podobnie jak inne języki wschodnioazjatyckie, w pionowym formacie tategaki. Znaki zapisywane były w kolumnach, od góry do dołu, a kolumny następowały w kolejności od prawej do lewej.

Hiragana cieszyła się początkowo dużą popularnością zwłaszcza wśród dam dworu cesarskiego i dlatego uważana była za pismo kobiece (onnade 女手). Składa się z 46 znaków i jest alfabetem sylabicznym. W piśmie japońskim nie wyróżnia się bowiem poszczególnych głosek, lecz jedynie całe sylaby. Hiragana powstała z potrzeby przystosowania chińskich znaków do gramatyki języka japońskiego. Oddaje ona jedynie dźwiękową stronę języka i jest używana m.in. do zapisu końcówek fleksyjnych (temat wyrazu zapisuje się z reguły znakiem chińskim). Japońskie dzieci jako pierwszy system pisania poznają właśnie hiragana i właśnie w niej zapisana jest większość książek dla dzieci.

Poniżej przedstawiono alfabet sylabiczny hiragana.

hiragana

Opis narzędzi

OpenCV

OpenCV (Open Source Computer Vision Library) jest biblioteką funkcji wykorzystywanych podczas obróbki obrazu, opartą o otwarty kod i zapoczątkowaną przez Intela. Jest ona zoptymalizowana pod kątem operacji w czasie rzeczywistym. Posiada własny system zarządzania oknami, niezależny od systemu operacyjnego. Biblioteka pozawala m.in. na:

przechwytywanie strumieni obrazów z kamer
pobieranie pojedynczych klatek
zapis i odczyt strumieni obrazów a także pojedynczych klatek na/z dysku
wykonywanie operacji na obrazach (operacje logiczne, splot, zmiana przestrzeni kolorów)
rysowanie w obrazach dowolnych kształtów

FANN

Fast Artificial Neural Network to biblioteka, napisana w języku C, implementująca wielowarstwowe sztuczne sieci neuronowe, daje możliwość pracy z PHP, C++, .NET, Ada, Python, Delphi, Octave, Ruby, Mathematica. Całość jest łatwa w użyciu (zaledwie kilka instrukcji by tworzyć, trenować oraz testować sieć). Sieć posiada kilka rodzajów funkcji aktywacji. Bardzo przydatną funkcją jest możliwość wczytywania i zapisywania całej sieci w jednym pliku tekstowym. Ponadto w wersji FANN 2.1 dostępny jest także interfejs graficzny pozwalający na wizualizację sieci.

Działanie programu

Fragmentacja obrazu na osobne litery i normalizacja do wartości binarnych
Obcięcie białych pasków po bokach litery
Normalizacja rozmiaru
Zamiana obrazu na wektor
Rozpoznawanie przez sieć neuronową kolejnych liter
Odkodowanie wyjścia sieci na identyfikator litery

Przetwarzanie obrazu

Obraz wczytywany jest za pomocą funkcji cvLoadImage, w programie jest reprezentowany jako macierz pikseli o wartościach z zakresu 0..255. W kolejnym kroku wyraz cięty jest na litery, z każdego podobrazu reprezentującego literę odcinane są skrajne białe paski. Każdą klatkę zawierającą literę poddajemy progowaniu. Na tym etapie mamy wektor liter. W kolejnym kroku litery są normalizowane do rozmiarów 20x20, tak przygotowana macierz jest zamieniana na wektor o długości 400 elementów. Wektor ten stanowi wejście sieci neuronowej. Wszystkie litery po kolei przechodzą proces rozpoznawania. Wyjście sieci neuronowej jest dekodowane, otrzymany numer stanowi identyfikator litery.

Budowa sieci neuronowej

Sień neuronowa tworzona jest za pomocą polecenia struct fann *ann = fann_create_standard(num_layers, num_input, num_neurons_hidden, num_output). Liczbę wyjść ustawiona na 6, jest to minimalna liczba bitów aby zakodować wszystkie badane litery. Zostały ustawione sigmoidalne funkcje aktywacji neuronów. Sieć była uczona aż do osiągnięcia błędu na poziomie 0.00001. Zastosowano algorytm uczenia z nauczycielem. W programie jest to realizowane za pomocą komendy fann_train_on_file(ann, "literkiWy20.txt", max_epochs, epochs_between_reports, desired_error).

Testy

Podczas testów badano procent poprawnie rozpoznanych liter w zależności od struktury sieci neuronowej (od liczby neuronów oraz liczby warstw). Zbiór danych uczących zawierał 276 liter. Wyniki analiz przedstawiają poniższe tabele. Znak '-' w tabeli oznacza, że sieć nie była w stanie się nauczyć danych uczących.

Wejściem był wektor długości 225 elementów, uzyskany z macierzy pikseli 15x15. Skalowanie litery do rozmiaru 15x15 powoduje zbyt wielką stratę informacji, dla tak przygotowanych danych sieć nie jest w stanie wychwycić różnic między literami, skutkuje to skutecznością rozpoznania nie przekraczającą 50%. Zwiększenie liczby warstw przynosi nieznaczną poprawę do 10% dla bardziej złożonych struktur. Zwiększanie liczby neuronów ukrytych (niezależnie od ilości wejść) powyżej 20 nie przynosi znaczącej poprawy zarówno dla dwóch jak i trzech warstw.

Wejściem był wektor długości 400 elementów, uzyskany z macierzy pikseli 20x20. Zwiększenie liczby wejść do 400 przynosi zauważalną poprawę. Zwiększenie złożoności sieci przez dodanie nowych warstw nie przekłada się na zwiększenie skuteczności rozpoznawania.

Wejściem był wektor długości 625 elementów, uzyskany z macierzy pikseli 25x25. Wektor ten niesie w sobie zbyt szczegółowe informacje. Zwiększenie liczby warstw powoduje zbyt duże skomplikowanie sieci, taka struktura wymaga większej ilości neuronów ukrytych. W projekcie odstąpiono od budowania skomplikowanej sieci, gdyż lepsze wyniki osiągnięto za pomocą mniej rozbudowanej struktury.

Przykład działania programu

Wnioski

Najlepsze wyniki uzyskano dla sieci o 400 wejściach, 2 warstwach ukrytych i 10 neuronach w każdej, sięgnęła ona 90% (247/276). Można zauważyć występowanie grup podobnych liter, które są najczęściej mylone przez sieć, m.in.: {a, o, chi}, {nu, me}, {ne, wa, re}, {ro, ru}. Podczas realizacji projektu zauważono, że nie można przesadzać ze złożonością sieci, większa liczba warstw i neuronów ukrytych nie powodu zwiększenia skuteczności rozpoznawania. Zwiększenie liczby warstw ukrytych ma jednak bezpośrednie przełożenie na skrócenie czasu uczenia. Stosunkowo krótki czas uczenia sieci może być pierwszym zwiastunem, że sieć nie będzie w sposób zadowalający radziła sobie z rozpoznawaniem. Jeśli podczas uczenia sieci błąd oscyluje wokół pewnej wartości znacznie przewyższającej błąd pożądany, należy przerwać proces uczenia - sieć nie jest w stanie nauczyć się danych.

Literatura

[1] Dokumentacja biblioteki - opis instalacji, http://opencvlibrary.sourceforge.net

[2] Wprowadzenie do programowania przy użyciu OpenCV, http://www.cs.iit.edu

[3] CV Manual, http://www.seas.upenn.edu

[4] Strona domowa biblioteki FANN, http://leenissen.dk

[5] Podstawy sieci neuronowych, http://panda.bg.univ.gda.pl

[6] Dokumentacja biblioteki. Pełny opis wraz z wyczerpującymi przykładami, http://prdownloads.sourceforge.net