Tartalomjegyzék 1
Abstract ............................................................................................................................. 4
2
Bevezetés .......................................................................................................................... 4
3
2.1
A probléma felvetése ................................................................................................ 4
2.2
A projekt célja ........................................................................................................... 5
Irodalomkutatás ................................................................................................................ 6 3.1
Hasonló rendszerek ................................................................................................... 6
3.2
Felhasználási módszerek ........................................................................................... 7
3.2.1 3.2.2
Rejtett Markov Modellek (Hidden Markov Models, HMMs) ............................ 7 Hibrid módszerek .................................................................................................. 9
3.2.3 Visszacsatolt mesterséges neuronhálózatok (Recurrent Artificial Neural Networks, RNNs) ....................................................................................................................... 9 3.3
Rendszerek összehasonlítása .................................................................................. 11
3.3.1
A HMM és RNN módszerek egy konkrét összevetése......................................... 11
3.3.2 2009)
ICDAR 2009 (International Conference On Document Analysis and Recognition ............................................................................................................................. 11
3.4
A feldolgozás lépései ............................................................................................... 13
3.4.1
Sorok kinyerése ............................................................................................... 13
3.4.2
Normalizálás .................................................................................................... 14
3.4.2.1
Sorok elforgatása ........................................................................................ 14
3.4.2.2
Írás dőltségének megszüntetése ................................................................. 14
3.4.2.3
Az írás régióinak normalizálása ................................................................... 15
3.4.2.4
A betűk szélességének normalizálása ......................................................... 15
3.4.2.5
A kép intenzitásértékeinek normalizálása .................................................. 16
3.4.3
Jellemzők kinyerése ............................................................................................ 16
3.4.4
Jellemzők feldolgozása ........................................................................................ 17
3.4.5
Címkézés.............................................................................................................. 17
3.4.6
Nyelvi- modellek, statisztikák és szótárak használata......................................... 17
3.4.6.1
Szótárak ....................................................................................................... 17
3.4.6.2
Nyelvi modellek ........................................................................................... 17
3.5
Az IAM adatbázis jellegzetességei ........................................................................... 18
3.6
Az irodalomkutatás összegzése ............................................................................... 20
4 Megvalósítás ....................................................................................................................... 21 4.1
A tesztadatok .......................................................................................................... 21
4.2
A vízszintes vonalak meghatározása ....................................................................... 21
4.2.1
Hough transzformáció ..................................................................................... 21
4.2.2
Vízszintes projekció ......................................................................................... 22
4.2.3
Peakiness érték számítás................................................................................. 24
4.2.4
Kontúrkeresés ................................................................................................. 26
4.3
A kézzel írt rész beforgatása ................................................................................... 27
4.4
A sorok szétválasztása ............................................................................................. 29
4.5
A sorok elforgatása ................................................................................................. 30
4.5.1
A ferdeség meghatározása lineáris regresszióval ........................................... 31
4.5.2
A ferdeség meghatározása Kendall-Theil regresszióval .................................. 31
4.5.3
A két módszer összehasonlítása...................................................................... 32
4.5.4
Az elforgatás megvalósítása ............................................................................ 33
4.6
5
Az írás dőltségének megszüntetése ........................................................................ 35
4.6.1
A dőlésszög meghatározása a függőleges projekció szórása által .................. 37
4.6.2
A globális dőlésszög meghatározása általánosított projekció által ................ 38
4.6.3
A lokális dőlésszög meghatározása általánosított projekció által ................... 39
4.7
Az írás régióinak normalizálása ............................................................................... 43
4.8
A betűk szélességének normalizálása ..................................................................... 45
4.9
A kép intenzitásértékeinek normalizálása .............................................................. 46
4.10
A normalizálás lépéseinek összefoglalása ........................................................... 47
4.11
A jellemzők kinyerése.......................................................................................... 48
Az elkészült program bemutatása................................................................................... 50 5.1
A modulok közti kapcsolat ...................................................................................... 50
5.2
A program működésének bemutatása .................................................................... 51
5.3
A kiszámolt adatok helyességének tesztelése ........................................................ 52
6
Összefoglalás ................................................................................................................... 54
7
Irodalomjegyzék .............................................................................................................. 55
8
Mellékletek...................................................................................................................... 58 8.1
Ábragyűjtemény ...................................................................................................... 58
8.2
A HMM és RNN módszerek egy konkrét összevetése............................................. 65
8.2.1 8.2.2
Az első tesztminta: .......................................................................................... 65 A második tesztminta .......................................................................................... 67
1 Abstract This thesis is about unconstrained offline handwritten text preprocessing, normalization and feature extraction, using the IAM database (what is available for the public for free) for testing purposes. This thesis summarizes the previous works about this topic, and then presents an own solution based on these works. The behavior of the used algorithms is described in detail, and their outcome is presented by examples. The further applications of the extracted features are also discussed, like handwritten text recognition by Hidden Markov Models or Recurrent Artificial Networks but these solutions are only presented, not implemented.
2 Bevezetés 2.1
A probléma felvetése Még manapság is gyakran találkozik az ember olyan feladatokkal, amik
egyszerűek,
egysíkúak,
unalmasak,
időigényesek
és
gépek
által
mégsem
automatizálhatóak. Ilyen például az adatrögzítés, kézzel írott dokumentumok, jegyzetek, piszkozatok begépelése, kérdőívek feldolgozása, tesztek, dolgozatok, vélemények kiértékelése. A kézzel írott szövegek felismerése lehetővé tenné azok indexelését, kereshetővé tételét. Ehhez például nem is szükséges a teljes szöveg összes szavának a sikeres felismerése, elég csak a nagy valószínűséggel felismert szavakat vizsgálni, és azokból a kulcsfontosságú szavakat meghatározni szövegbányászat segítségével [1], ami alapján a dokumentum témája besorolható, ezáltal kategorizálható. A keresés így nem automatizálódik teljesen, de csökkenti az emberi kereséshez szükséges időt, szűkíti a keresési teret. Ez hasznos lehet például levéltárakban lévő kézzel írott levelek, vagy az írógépek elterjedése előtt keletkezett dokumentumok esetében. A teljes mértékben felismert szöveget pedig (a keresésen túl) a gép már képes lenne felolvasni (például vakoknak) és ha szükséges, akkor a felolvasás előtt egy gépi fordítást is el tudna végezni, vagy bármi mást, amit a karakteres digitális szöveggel eddig is lehetett (átjavítás, kibővítés, statisztikák készítése, stb.).
4
2.2
A projekt célja A projekt célja egy olyan rendszer megépítése, ami az IAM adatbázisban [2]
szereplő tesztképeken lévő kézzel írt szöveget képes elkülöníteni, sorokra bontani és normalizálni, hogy lehetséges legyen a szövegből a jellemzőket kinyerni, amiket később fel lehet használni bemenetként egy valamilyen tanítóalgoritmus számára, ami a kézzel írt szöveg ASCII kóddá alakításáért felelős. A tanítóalgoritmus megvalósítása azonban már nem témája a dolgozatnak, csupán azok lehetséges megvalósítási módjait mutatja be nagyvonalakban, különös figyelmet fordítva a jellemzők felhasználásának mikéntjére. Az IAM adatbázis több mint hatszáz ember bevonásával készített, körülbelül 1600 oldalnyi lapolvasóval beolvasott formanyomtatvánnyal rendelkezik, oldalanként 5 – 10 sornyi szabad stílusú, kézzel írt szöveggel. Ez az adatbázis megfelelő a célra, mivel rengeteg különböző íráskép található meg benne, ezért változatos tesztadatokkal szolgál.
5
3 Irodalomkutatás 3.1
Hasonló rendszerek Már a hetvenes évek vége felé megjelentek az első olyan rendszerek, amik
kézzel írt számok felismerésére voltak képesek [3]. Ezek a rendszerek tipikusan egy behatárolt felhasználási területre összpontosítottak, ilyen területek például a kézzel írott postai címek felismerése, csekkeken lévő összeg beolvasása. Az ilyen problémák esetében a felismerendő szavak egy kis szótárban elférnek, amiben tipikusan városnevek, utcanevek szerepelnek, számok esetén pedig csak tíz különböző megoldás lehet. Ezek a kritériumok, valamint az, hogy a megnevezett szövegek adott sorrendben, adott helyen jelenhetnek meg, nagymértékben leegyszerűsítik a problémát. A formanyomtatványok kézzel történő kitöltése is hasonló eset. A számjegyek felismerése esetében például létezik már olyan rendszer, ami a mintáknak csak 0,35%-át ismeri fel tévesen [4]. Ez a rendszer egy sokrétegű (hat) sok neuronból álló (rétegenként pár ezer) feedforward neuronhálózat, ami tanuláskor a backpropagation algoritmust használja. A tanulási sebesség gyorsítása érdekében grafikus kártyákon futtatják az algoritmust. A levelek kézzel írott szöveggel való címzése (vagy egyáltalán a levelek küldése) egyre inkább háttérbe szorul az e-mail és a nyomtatott címzés miatt. Az internetes banki megbízások és hitelkártyák használata szintén egyre inkább kiszorítja a csekkek használatát. Mindezek ellenére még ma is sokat használják mindkét régebbi megoldást. A
szövegkörnyezet
független,
általános,
és
felhasználó
független
kézírásfelismerés azonban sokkal összetettebb probléma. Körülbelül húsz évvel ezelőttre tehető (’90-es évek vége), amikor létrejöttek az első folyóírással írt szavak felismerését megcélzó rendszerek. A szövegről itt csak annyit tudunk, hogy egy megadott nyelven írták [5]. Az íráskép rengeteg stílusú lehet, a szavak nem előre megadott pozícióban fordulnak elő. A különválasztott karakterek valamilyen osztályozó algoritmussal felismertethetők, de az egybe írt, összekötött betűk felismerése már nem egy mintafelismerésen alapuló probléma, sokkal inkább egy szekvencia-felismerésen alapuló (3.1 ábra). Vissza lehetne vezetni a problémát különálló karakterek
6
3.1 ábra: A szövegfelismerés fejlődése [6]. felismerésére úgy, hogy szegmentáljuk a szavakat karakterekké, és a karaktereket ismertetjük fel. Ahhoz azonban, hogy könnyen szegmentálni tudjunk karakterekké, ahhoz fel kell ismerni az egész szót. Ez egy körkörös függés amit Sayre paradoxonának szoktak nevezni [7]. A megoldás az, hogy egyszerre próbálunk meg szegmentálni és felismerni.
3.2
Felhasználási módszerek A kézírásfelismerés során dominánsan a rejtett Markov modelleket és a
mesterséges neuronhálózatokat használják fel, mint tanítóalgoritmusokat, illetve létezik e két módszer ötvözete, ahol mindkét módszert felhasználják külön-külön, majd szavazás alapján szavanként a legbiztosabb eredményt használják fel. 3.2.1
Rejtett Markov Modellek (Hidden Markov Models, HMMs)
A HMM-ek statisztikán és valószínűségszámításon alapuló modellek. A Markov-lánc tulajdonságait használja fel. Szekvencia mintázatokat képesek leírni. A szekvenciák állapotokból állnak. A HMM-ek betanítása során, statisztikai módszerekkel
7
megállapítható, milyen valószínűséggel követ egy állapot egy másik állapotot a szekvencián belül. Ezeket állapotátmeneteknek hívjuk. Továbbá egy állapotátmenet valószínűségét az is meghatározza, hogy az állapotot leíró megfigyelések milyen valószínűséggel következnek be, amikor az adott állapot áll fenn. A HMM esetében az állapotok nem ismertek, ezeket próbáljuk meg valószínűsíteni az előző állapot (ami szintén valószínűsített, kivéve a legelső állapotot), és a megfigyelések függvényében. A betanítás során épülnek fel a modellek, amik tartalmazzák a valószínűségi kapcsolatot az állapot és következő állapot, valamint az állapot és az állapot ideje alatt megfigyelt jellemzők között. A betanítás során a Baum-Welch-algoritmust alkalmazzák a megfigyelések súlyozásához, és az állapot váltások valószínűségének kiszámításához, vagyis a HMM paraméterezését kapjuk meg vele [8, 9]. A gyakorlatban az állapotok a címkék (pl.: beszédfelismeréskor egy fonéma, kézírásfelismeréskor egy karakter, bioinformatikában nukleotid bázisok, aminosavak (amiknek a szekvenciája fehérjéket épít fel). A megfigyelések pedig a jellemzők (jellemzővektor). Ezek beszédfelismeréskor lehetnek például: amplitúdó, frekvencia stb., kézírásfelismeréskor pedig a pixelek elhelyezkedése, eloszlása, stb. A tanítás alatt modellek jönnek létre (HMM-ek) minden állapothoz. Felismeréskor ezeket a modelleket próbálja rá a mintára a rendszer, amelyik a legjobban illeszkedik a szekvenciára, az lesz az új állapot. Az illeszkedés mértéke valamilyen valószínűség lesz, ezt a Viterbi-algoritmus felhasználásával kapjuk meg. A HMM-ek nagyon népszerűek a beszédfelismerés esetében, ugyanis a beszéd tekinthető egy szekvenciának, aminek állapotai nem véletlenszerűen váltják egymást, hanem felfedezhető az állapotok közt valamilyen statisztikai korreláció. A beszédben a fonémák egymásutánisága valamilyen rendszert alkot, ez nyelvenként változó. A kézírás felismerés esetében is hasonló a helyzet, csak ott a karakterek egymásutánisága alkot rendszert. A legegyszerűbb HMM-ek nem használatosak, mivel azok esetében egy állapot csak az előző állapottól függ. A gyakorlatban a Maximum Entrópia Markov-modellt (MEMM) és a feltételes valószínűségi mezőket (conditional random fields, CRF) alkalmazzák, mivel ezek nem csak egy kis lokális részt vesznek figyelembe a valószínűségek kiszámításánál.
8
3.2.2 Hibrid módszerek A hibrid módszerek több, különböző paraméterekkel felépített HMM-et használnak, és a végső eredményt a különböző rendszerek eredményeiből számítják ki, valamilyen „szavazással”. Például ha megkapjuk az összes rendszer eredményét egy felismerendő szóra, ahol az eredmények a legesélyesebb tíz megoldást tartalmazzák, akkor ezekből a rendezett listákból kiválasztjuk a legvalószínűbb megoldást [10]. A rendszerek nem csak HMM-ek lehetnek, hanem neuronhálózatok is, illetve egy
konkrét
rendszer
egyes
különböző
alrendszerei
lehetnek
mesterséges
neuronhálózatok és HMM-ek is keverve.
3.2.3 Visszacsatolt mesterséges neuronhálózatok (Recurrent Artificial Neural Networks, RNNs) A hagyományos, legegyszerűbb neuronhálózatok alkalmazása célszerű minták felismerése, osztályozása esetén. Szekvenciák osztályozására (címkézésére) viszont nem alkalmasak, mivel a szekvencia szegmensei összefüggésben állnak egymással, és ezt már nem képes figyelembe venni egy feedforward NN, nincs emlékezete. Ez különálló karaktereknél nem is okoz problémát. A visszacsatolt NN-ek (RNN) viszont rendelkeznek rövidtávú memóriával, amit számításba tudnak venni az adott időpillanatban beérkező inputok kiértékelésénél. Ez a kézírás felismerés esetében rendkívül fontos, mivel sokszor csak a kérdéses karakter környezetében lévő karakterek ismeretében
tudunk
következtetni
a
kérdéses
karakterre.
A
jellemzővektor
tulajdonságainak (az RNN inputja) időbeli változásának nagysága is fontos információ, és a tulajdonságok súlyozásával a lényeges információk akkor is megmaradnak, ha zajos az input.
9
3.2 ábra: A kézírás felismerés lépései RNN rendszer esetében [11]. Kifejezetten erre a problémára lett kifejlesztve a Long Short-Term Memory topológiájú RNN (LSTM RNN) (3.2 ábra), ami ezt a rövidtávú emlékezetet terjeszti ki, így nagyobb időintervallumot képes átfogni [11]. A kézírás felismerés esetében hasznos, ha nem csak az aktuális vizsgált pozíció előtti jellemzőket ismerjük az adott időpillanatban, hanem az utána lévőeket is. A kétirányú RNN-ek (Bidirectional RNN, BRNN), két külön rejtett réteggel rendelkeznek, az egyik balról jobbra dolgozza fel az inputokat, a másik jobbról balra, és ezek kimenetei közös kimeneti rétegre vannak kapcsolva. A bemeneti réteg annyi neuronból áll, amennyi jellemzőt kigyűjtünk a normalizált, előfeldolgozott képből (pl. 9), a kimeneti pedig annyiból, ahány karaktert meg szeretnénk különböztetni egymástól (pl. angol ábécé kisbetűi: 26 darab) plusz egy, ami a szóközért és egyéb nem osztályozható jellemzőkért felelős (pl. zaj, túl apró írásjel). Az RNN output rétegének egy olyan rétegnek kell lennie, ami a szegmentálatlan (a karakterek össze vannak kötve egymással), független lokális osztályozásokat (mivel minden időpillanat egy külön osztályozás) képes címkézni. A Connectionist Temporal Classification (CTC) egy pont e célból kifejlesztett output réteg, ami szegmentálatlan adatokon is képes a szekvenciák címkéinek valószínűségét meghatározni. Az output neuronok aktivációi valószínűségi eloszlást adnak, ezeket normalizálni kell úgy, hogy a címkék valószínűségének összege 1 legyen. Ezután, a normalizált aktivitásokat felhasználjuk úgy, hogy figyelembe vesszük a már feldolgozott szekvencia részeken kapott eredményeket (mindkét irányban). Ez egy feltételes valószínűséget fog adni minden címkére. Így tehát egy címke valószínűsége nem csak az adott időkeretben vett
10
jellemzők értékei alapján határozódik meg, hanem figyelembe vannak véve az adott időkeretet környező időkeretek is (mindkét irányban). Ez nagyban hasonlít a rejtett Markov-modellekre (HMM, Hidden Markov Model). Ezután ki kell választani azt az utat, ami a címkék valószínűségét számításba véve a legvalószínűbb. Ez gyakorlatilag azt jelenti, hogy egy olyan betűsorozatot kell találnunk, ami a leginkább értelmes szót adja. Ezt a lépést szótárakkal és nyelvi modellekkel lehet támogatni [11, 12]. Ezen módszerek kombinációjaként jön létre a BLSTM RNN, ami – mint majd az összehasonlításból kiderül – jobb felismerési arányokat ér el mint bármilyen HMM-en alapuló (vagy hibrid) rendszer [10].
3.3
Rendszerek összehasonlítása A két fő módszer összehasonlítása egy, a témával foglalkozó nemzetközi
konferencián megemlített eredmények figyelembe vételével, valamint egy konkrét példán keresztül.
3.3.1 A HMM és RNN módszerek egy konkrét összevetése A Berni Egyetem weboldalán létrehoztak egy web-alapú interfészt, ahol fel lehet tölteni saját kézzel írott sorokat, és a kiválasztott rendszer megpróbálja azt felismerni. A normalizálás és jellemzővektor kiszámítás fázisok mindkét rendszer esetében azonosak, a jellemzővektor feldolgozását viszont egy HMM és egy RNN alapú rendszerrel is elvégezhetjük [13]. Az ehhez tartozó ábrák az ábragyűjtemény 8.2-es fejezetében találhatóak meg.
3.3.2 ICDAR 2009 (International Conference On Document Analysis and Recognition 2009) Az ICDAR egy verseny, ahol a nevezők versenyeztethetik egymással a rendszereiket [10]. Az összes rendszer ugyanazon adatbázisból vett kézzel írott szavakat kellett hogy felismerjen. Továbbá a betanítás is közös adatbázisból történt (kivéve a ParisTech(1) nevű rendszert, ami saját adatbázison tanult). Az ICDAR 2009 esetében francia volt a szöveg, de a rendszereket összevetették úgy is, hogy a csak francia nyelvben szereplő karaktereket lecserélték angol karakterekre. A versenyre 10 rendszer
11
nevezett be, mindegyik HMM vagy hibrid alapú megoldással működött, kivéve egyet, amelyik a legjobban teljesített, ami BLSTM RNN alapú rendszer volt. Három alfeladat volt, mindegyikben első lett. A táblázatok a [10]-ben találhatóak meg. WR1: Az első feladatban a kézzel írott szavakról el kellett eldönteni, hogy az adott 100 lehetséges megoldás közül melyik a jó megoldás (Table 1). WR2: A rendszerek által használt szótár közös volt, és a szótárban csak azok a szavak szerepeltek, amik a felismerendő szavak voltak (1612 szó) (Table 2). WR3: Ugyanaz, mint a WR2, csak nagyobb szótárral (5334 szó) (Table 3). A táblázatokban a top10 azt jelenti, hogy a helyes megoldás benne volt e a rendszer által adott 10 legvalószínűbb megoldása közt. A top1 pedig azt jelenti, hogy a legvalószínűbb megoldás volt a helyes megoldás. A megvalósítandó projekt szempontjából a WR3-as feladat normalized GT (normalized Ground Truth, a francia nyelvre specifikus karakterek az angol abc karaktereivé lettek transzformálva a könnyebb felismerés érdekében) top1-es oszlopa a legérdekesebb, mivel ez tükrözi legjobban a körülményeket, amiben a rendszernek helyt kellene állnia.
12
1.3 ábra: Horizontális hisztogramok, különböző elforgatási szögek esetében [14].
3.4
A feldolgozás lépései Az egyes lépések szorosan egymásra épülnek, emiatt minden lépésben
keletkezett hiba összeadódik, ezért törekedni kell minden lépésnél a minél kisebb hibaarányú feldolgozásra. 3.4.1
Sorok kinyerése
A dokumentum képét el kell forgatni, ha szükséges, ezután a kézírást tartalmazó részeket kell meghagyni (e rendszer esetében ez utóbbi művelet elhagyható, mivel az inputról feltételezzük, hogy csak kézzel írott szöveg van rajta, nincsenek ábrák, vagy képek). A forgatást fokonként végezzük el, és annál a szögnél ahol a binarizált dokumentum vízszintes hisztogramja a legmélyebb völgyeket és legmagasabb csúcsokat mutatja, az lesz a megfelelő elforgatási szög (3.3 ábra). [14, 15] Ha pont fejjel lefelé sikerült ezáltal elforgatni a dokumentumot, az a rossz felismerési arányból szembetűnő lesz. Illetve hisztogram alapú ellenőrzéssel is meg tudjuk vizsgálni, mivel az írott betűk a talpukhoz közel sűrűbbek, a tetejüknél ritkábbak. Az alapvonal alá lógó betűrészek még ritkábbak, mint a magas betűk felső részei. A sorokat elválasztó egyenes meghatározható a kép vízszintes hisztogramjából. Ahol lokális minimumai vannak a hisztogramnak, ott lesz a két sort elválasztó egyenes (ábragyűjtemény: 8.1 ábra). Ha egy vonás átlóg a sorok között, akkor abba a sorba lesz besorolva, ahova a súlypontja esik [11]. A binarizálás történhet globális és lokális küszöböléssel is, szkennelt képek esetében a globális módszer is megfelelő lehet. Lokális módszer esetén a Niblack és a Sauvola algoritmusok jöhetnek szóba [16]. A lokális binarizálás nagyon lassú lehet, ezért előtte érdemes a képről integrálképet [17] készíteni, ezáltal a futásidő nem fog
13
3.4 ábra: A dőlt szöveg és a korrigált szöveg projekciói [18]. függeni a mozgó ablak méretétől [16]. Az integrálkép röviden megfogalmazva a pixelek intenzitásértékeinek akkumulált összege két dimenzióban. 3.4.2
Normalizálás
A normalizálás azért fontos, mert így az azonos, de kissé eldeformálva leírt karakterek valamilyen szinten azonos alakba hozhatóak, ezáltal csökkentve a karakterosztályok számát. Ha egy karakter ferdén van leírva, vagy méretbeli különbségek vannak, nem vethetőek össze egymással, de normalizálás után már igen, és kinyerhetjük belőlük a jellemzőiket. 3.4.2.1
Sorok elforgatása
Meg kell találni azt az egyenest, lineáris regresszióval, ami a betűk talpára a legjobban illeszkedik. Amint ez megvan, már könnyű kiszámolni a ferdeség fokát, és elforgatni a sort a megfelelő szöggel. A betűk talpát úgy találhatjuk meg, hogy egy 1 pixel széles mozgó ablakkal végigmegyünk a képen, és a legalsó fekete pixel helyét eltároljuk. Ezeket a helyeket használhatjuk fel a lineáris regresszió számításkor [8, 9]. 3.4.2.2
Írás dőltségének megszüntetése
Ennél a lépésnél függőleges hisztogramot készítünk a sorról (3.4 ábra). Elforgatjuk fokonként, és annál a szögnél ahol a függőleges hisztogram a legmagasabb csúcsokat adja, az lesz az a szög, amit a nyíró algoritmus a nyíró-mátrixban felhasznál. Ez lényegében az y koordináta és a szög függvényében tolja el az egész sort valamelyik irányba (kézírás esetében, ha jobbkezes ember írásáról van szó, akkor általában balra) [18].
14
3.5 ábra: (a) Az eredeti szöveg. (b) Szöveg a határoló egyenesekkel [8]. 3.4.2.3
Az írás régióinak normalizálása
A sort vízszintesen fel kell osztani három részre (3.5 ábra). Ezt két egyenessel tesszük meg. A felső alapvonal és az alsó alapvonal között az alacsony betűk vannak (pl.: a, o, u, stb.). Ezeket az egyeneseket szintén horizontális hisztogramok segítségével lehet kiszámolni. Meg kell találni a hisztogram deriváltjának két maximumát [8]. Ezt úgy kapjuk, ha kiszámoljuk a sorösszegek szomszédos értékeinek különbségeit, és vesszük a két legnagyobbat. További két egyenest kell még meghatározni, amik a sor tetejét és alját határozzák meg. Mivel a sorok úgy lettek kivágva a sorok kinyerése lépésben, hogy az írás alatt és felett nincs üres rész, ezért a legfelső és legalsó vonal a kép első és utolsó sorára esik. A legfelső egyenes határolja például a nagybetűk és a magas betűk tetejét, a legalsó egyenes pedig a lelógó betűk alját (pl. g, y, j, stb.) [9]. Miután megkaptuk a három régiót, mindhármat normalizálni kell, egy előre megadott magasságra. 3.4.2.4
A betűk szélességének normalizálása
Meg kell vizsgálni, hogy a középvonal mentén mennyi előtér- és háttérpixel váltás van. Ez jó becslést ad arra, hogy mennyi betű van az adott sorban. Azt, hogy egy karakter körülbelül hány pixel széles legyen, azt előre meg kell adni. Ez alapján már tudjuk normalizálni a betűket szélesség szerint is [8, 11].
15
3.4.2.5
A kép intenzitásértékeinek normalizálása
Mivel nincs megkötés arra, hogy a szöveget író személy milyen tollat használhat, ezért nagy eltérések fordulhatnak elő a leírt szöveg színében. Mivel az input képek szürkeárnyalatos képekként kerülnek beolvasásra, így a színinformáció elvész, de még így is lehetnek különbségek sötétebb és világosabb tónusú tollak esetében, valamint a papír színe is eltérő lehet az egyes esetekben, ezért az intenzitásértékeket normalizálni kell a képen [12].
3.4.3 Jellemzők kinyerése A normalizált képen vízszintesen végigmegyünk egy 1 pixel széles ablakkal. Ez lesz az időegység, ami a jellemzővektort tartalmazza. Beszédfelismerés esetében a beszéd az idő múlásának függvényében változik, ott a választott időegység, vagyis a választott időintervallum, amiből a jellemzőket kinyerik, például 50 ezredmásodperc. Kézírásfelismerés esetében az írás pozíciója az x koordinátatengelyen az „idő”, a választott „időegység” pedig például 1 pixel. A jellemzővektor kilencdimenziós, a következő jellemzőket tárolja (ábragyűjtemény: 8.13 ábra) [11]: a számtani közepe a pixelek szürkeárnyalatos intenzitásainak, a pixelek súlypontja, a súlypont másodrendű nyomatéka, a legfelső és legalsó pixelek helye, ezen helyek változásának mértéke a környező ablakokhoz képest, az előtér és háttér váltások száma a legfelső és legalsó pixelek között, az előtér pixelek eloszlása a legfelső és legalsó pixelek között.
16
3.4.4 Jellemzők feldolgozása Az elkészített jellemzővektorokat átadjuk inputként a kiválasztott osztályozónak (HMM vagy RNN).
3.4.5 Címkézés Az osztályozó outputja alapján egy címkéző eljárással felcímkézzük a szekvenciát. A gyakorlatban itt a fonémák, karakterek, nukleotid bázisok helyét kapjuk meg a szekvenciában.
3.4.6 Nyelvi- modellek, statisztikák és szótárak használata Végső lépésként alkalmazható módszerek, amik már a nyomtatott karaktereket felismerő OCR (Optical Character Recognition) rendszerekben is alkalmazásra kerültek. 3.4.6.1
Szótárak
Miután megvannak a valószínűsített karakterek, egybefűzzük őket, és megvizsgáljuk értelmes szó állt e elő. Ezt szótárak segítségével tehetjük meg. RNN rendszerek esetében minél nagyobb a szótár mérete, annál pontosabb a felismerés, HMM rendszerek esetében viszont egy bizonyos méret után romlik. [11] 3.4.6.2
Nyelvi modellek
A szavak közti összefüggéseket is érdemes figyelni. Bizonyos szófordulatok gyakoribbak
Az
megelőző
egy-két-három
szóból
valamilyen
valószínűséggel
„megjósolható”, hogy milyen szó fog következni, ami hasonlít a következő, már felismert szóra. Ezeket „n-grams”-nak hívják. Háromnál nagyobb szóösszetételeket nem érdemes keresni, nem javítják a felismerést. Az „n” jelöli, hogy hány szó hosszúak a figyelt szóösszetételek. Két szó esetében „bigrams”-nak hívják (vagy „digrams”), három esetén „trigrams” a neve [5].
17
3.5
Az IAM adatbázis jellegzetességei Az egyes normalizálási lépések szigorúan egymásra épülnek. Ebből kifolyólag
az egyes normalizálási lépéseket implementálásuk után alapos tesztelés alá kell vetni. Az input képek a Berni Egyetem Gépi Látás és Mesterséges Intelligencia Kutatási Csoport adatbázisából származnak [2, 19], amely folyóírással írt angol szövegek felismerését tanuló algoritmusok tanítása céljából lett létrehozva, de az adatbázis alkalmas a szövegírók azonosítása vagy verifikálása céljából létrehozott algoritmusok tesztelésére is. Az adatbázis 1539 beolvasott oldalból áll, amit 657 különböző ember írt, összesen 1353 sornyi szöveg, ami 115320 szót tartalmaz, amik fel is vannak címkézve, hogy a tanítóalgoritmusok a betanításnál fel tudják használni. Minden kézzel írott szöveghez megtalálható a megoldásuk is, továbbá néhány, a normalizálás során felhasznált paraméter is, mint például a sorok és az írás ferdeségének szöge, a sorok és a szavak helye, a binarizálás küszöbértéke, az írás három régióját meghatározó két egyenes paraméterei, satöbbi. Az egyes oldalakon lévő írások külön-külön több stílusú szöveget tartalmaznak, összesen tizenötöt, többek közt: újságcikkek, tudományos írások, vallásos témájú írások, regény részletek, stb. Mindegyik oldal be van sorolva egy kategóriába, ez esetleg segítheti a felismerést a szövegkörnyezet figyelembe vételével, továbbá több különböző szó jelenik meg az adatbázisban. Egy űrlap négy részből áll. Az első részben szerepel a „Sentence Database” felirat, és az adott űrlap kategóriája és a szövegrész azonosítója (az író azonosítója csak a fájlnévben szerepel). A második rész tartalmazza nyomtatottan azt a szöveget, amit a résztvevőknek kézzel le kellett írniuk, és a harmadik rész ahova azt írniuk kellett. A negyedik rész ahová az írók megadhatták a nevüket. Mindegyik rész egy vízszintes vonallal van elválasztva egymástól. Az üres űrlap mögé egy segédvonalakkal ellátott lapot helyeztek, hogy minél egyenesebb legyen az írás, továbbá ha nem fért ki az összes szöveg, amit le kellett volna írni, akkor azt nem szabadott odazsúfolni, ki kellett hagyniuk a résztvevőknek. Az íróeszközre nem volt megkötés, hogy minél több stílusú írás keletkezzen.
18
A lapolvasóval beolvasott dokumentumok 300dpi-s, 8 bites, szürkeárnyalatos, PNG képfájlok 2479*3542-es mérettel (pl.: 3.6 ábra és egy nagyobb kép az ábragyűjteményben: 8.2 ábra).
3.6 ábra: Egy mintakép az IAM adatbázisból.
19
3.6
Az irodalomkutatás összegzése Ahogyan az irodalom irodalomkutatásból kiderült, az előfeldolgozó lépések
megegyeznek a különböző tanítóalgoritmusok esetében is. A normalizáló lépések során számos jellemző eltűnik, mint például az írás dőltsége, azért, hogy a tanítóalgoritmusok betanítása során létrejövő karakterosztályok minél inkább konkrétabbak legyenek. Mivel egy dőlt „l” betűből és az egyenes „l” betűből is az „l” betű ASCII kódját akarjuk kapni, ezért a tanítóalgoritmus a dőlt és az egyenes „l” betűk jellemzőiből hoz létre egy karakterosztályt, ami nem szerencsés, mivel eléggé eltérőek lehetnek a jellemzőik, ezért szükséges a normalizálás, hogy az azonos betűk jellemzői minél inkább hasonlítsanak egymásra. Ezért fontos tehát egy hatékony előfeldolgozó- és normalizáló rendszer kifejlesztése. Az irodalomkutatás részeként bemutatásra kerültek a részletezett előfeldolgozó rendszert alkalmazó rendszerek. Ezeknek a rendszereknek az alapvető működése nem különbözik egymástól nagy mértékben. A tárgyalt előfeldolgozó rendszert tehát hasznosítani tudják olyan kézírás felismerő rendszerek, amik több különböző író által írt kézírást céloznak meg felismerni. Viszont nem feltétlen alkalmazható (vagy kevésbé hatékony) előfeldolgozóként olyan rendszerek esetében, ahol az író személyének beazonosítása vagy verifikálása a cél, ugyanis az íróra jellemző tulajdonságok egy része elveszik, mint például a ferdeség, dőlés, betűk nagysága, stb.
20
4 Megvalósítás 4.1
A tesztadatok Első lépésben a szkennelt dokumentumok orientációját kell megállapítani, hogy
korrigálni lehessen a lapolvasóba esetlegesen ferdén elhelyezett lapok ferdeségét. Erre azonban nem volt szükség egyetlen dokumentum esetében sem, mivel azok nagyon pontosan voltak beolvasva, legfeljebb egy fokos ferdeséggel. Ez a kis hiba nem befolyásolta a későbbi lépések hatásfokát, mivel a dokumentumon lévő szövegrészeket elválasztó vízszintes vonalak könnyedén megállapíthatóak e feltételek mellett is. A kézzel írott szövegrész pedig soronként korrigálva lesz ferdeség szempontjából, továbbá ha a dokumentum ferdén lett beolvasva, még nem biztos, hogy amit ráírtak kézzel szöveget az is pont olyan nagyságban és irányban van elferdülve, mivel például lehetséges az az eset, hogy a papírlap mögötti segédvonalakat tartalmazó papír egy kicsit ferdén volt mögé téve. Csak a nyomtatott betűkkel írt szövegrész ferdeségének beállítása volna lehetséges, például a szövegrészeket elválasztó vízszintes vonal ferdesége alapján korrigálni, de mivel a nyomtatott szövegrészre nincs szükség, ezért felesleges.
4.2
A vízszintes vonalak meghatározása A vonalak meghatározásához többféle módszer vizsgálatra került. A különböző
módszerek és az elért eredmények e szekcióban kerülnek részletezésre. 4.2.1
Hough transzformáció
A vízszintes elválasztó vonalak helyzete Hough transzformáció [20] segítségével került volna meghatározásra. Azonban mivel a Canny éldetektáló [21] a vonalak élpontjait nem egy összefüggő vízszintes egyenesként határozta meg, hanem kisebb recék és törések jelentek meg benne, ezért a Hough vonaldetektáló csak több kisebb
4.1 ábra: Fals-pozitív vonal a life szó alján.
21
szakaszt talált meg, és nem lehetett meghatározni a vonal pontos helyét. Továbbá több olyan egyenest is talált, amit nem szabadott volna. A Hough transzformáció paramétereit nagyon nehéz jól megválasztani, és ha sikerül is egy tesztkép esetében, más tesztképekre nem garantáltan ad kielégítő eredményt (4.1 ábra). 4.2.2
Vízszintes projekció
Az előző módszer tehát nem alkalmas e probléma megoldására. Egy másik lehetséges módszer, ha elkészítjük a kép vízszintes projekcióját, vagyis összegezzük a sorokban lévő pixelek intenzitását. Ezt a projekciót megfelelően elemezve, megkapható a hosszú fekete vízszintes vonalak helyzete (4.2 ábra). Egy másik vizsgálható adat, ha binarizáljuk a képet és soronként megszámoljuk a fekete-fehér váltások számát. A képet Otsu módszerével [22] érdemes binarizálni, amely egy globális binarizációs módszer, vagyis az egész képet figyelembe veszi. Ez a módszer akkor alkalmazható, ha a képen jellemzően előtér- és háttérpixelek vannak, mint például a papír (háttérpixelek) és a rajta lévő írás (előtér pixelek).
4.2 ábra: A kitöltött nyomtatvány vízszintes projekciója.
22
4.3 ábra: A kép hisztogramja, és a küszöbérték helye az Otsu módszer által meghatározva. Ez a kép hisztogramjából úgy tűnik ki, hogy két magas, egymástól könnyen elkülöníthető csúcsot produkál (4.3 ábra). (4.1 kifejezés) A küszöböt aszerint határozza meg, hogy a leendő két osztályon (előtér- és háttérpixelek) belüli variancia a legkisebb legyen. Otsu megmutatta, hogy a két osztályon belüli variancia minimalizálása azonos a két osztály közötti variancia maximalizálásával [22]. 4.1 kifejezés: keressük azt a t-t, amire a kifejezés a legnagyobb értéket adja. A
jelöli az osztályok közti varianciát, (a
„between” (közti) rövidítése), a t a küszöbérték, az
jelöli a varianciát a
b
a
az osztályba eső pixelek száma, a
az osztályba eső pixelek intenzitásainak átlaga. A bináris képen a soronkénti fekete fehér pixelek váltakozásának összeszámolása után, az eredmény a 4.4 ábrán látható. Ha kevés a váltakozás és az előzőleg kapott vízszintes projekció értéke viszonylag magas, ott feltehetőleg vízszintes fekete vonal található. A vízszintes projekciót alapul véve meghatározásra került az a három legvékonyabb csúcs, amiknek magassága legalább 20%-a a legmagasabb csúcsnak. Mivel a projekció nem a binarizált képből kerül számításra ezért a zaj kiszűrése miatt csak azok a sorok kerültek figyelembe, amik projekciója legalább 5%-a a legmagasabb projekció összegű sornak. Azért nem érdemes a binarizált képből készíteni a projekciót, mert a szürkeárnyalatos kép valamivel részletgazdagabb, az éleknél a színátmenet
23
4.4 ábra: A fekete-fehér váltások száma az egyes sorokban. súlyozottan számítódik az összegbe. Ezzel a módszerrel sikeresen meghatározásra kerültek a vízszintes vonalak, kivéve azokban az esetekben, amikor az író ráírta a legalsó vonalra a nevét, vagy a leírandó szöveget, ekkor ugyanis a legalsó vonal túl széles csúcsot eredményezett a projekcióban, így csak két vonalat talált az algoritmus és így nem lehetett meghatározni a kézzel írt szövegrészt. A fekete-fehér váltások számának figyelembe vétele nem javította az eljárás hatékonyságát. 4.2.3
Peakiness érték számítás
A csúcsok vizsgálatához felhasználható az úgynevezett peakiness számítási módszer, ami az egyes csúcsokhoz egy számértéket rendel, annak függvényében, hogy mennyire vékony és magas a csúcs (4.5 ábra, 4.2 kifejezés) [23]. A Va jelöli a csúcs kezdetének a magasságát, a Vb a csúcs végének a magasságát, a P a csúcs legmagasabb pontjának a magasságát, a W a csúcs szélességét, az N pedig a csúcs területét jelöli. A legrosszabb eset, ha
(ez az eset akkor állhat fenn, ha a csúcs egy téglalap)
ekkor ugyanis a jobb oldali tag zérus lesz, ezáltal az egész kifejezés zérus lesz, a peakiness érték pedig annál jobb, minél nagyobb szám jön ki. (4.2 kifejezés)
24
4.5 ábra: A hisztogramon bejelölt paraméterek [19].
A kép első 50 oszlopa levágásra került a szkennelés során kialakult bal oldali zaj miatt (ábragyűjtemény 8.4 ábra) és a kapott kép ez után binarizálva lett, hogy a zajtól minél inkább mentes legyen, és ebből került meghatározásra a kép vízszintes projekciója. A tesztfutások során nem sikerült olyan mintát találni a számadatokban, ami alapján a peakiness érték alkalmas lenne a vízszintes vonalak behatárolására, még akkor se, ha a binarizált kép vízszintes projekciója előtte simítva lett. Egy tetszőlegesen választott tesztmintán (ábragyűjtemény 8.5 ábra) A simítás több ablakmérettel és iteráció számmal is ki volt próbálva. A vízszintes projekcióból (ábragyűjtemény 8.6 ábra) kiszámított peakiness értékek (ábragyűjtemény 8.7 ábra) alapján nem lehet megállapítani, hogy melyik a keresett három vonal. A vízszintes projekciót simítva egy 5 egység széles átlagoló ablakkal, háromszori iteráció után, a csúcsok valamivel vékonyabbak és laposabbak lettek, de nem látványos a különbség (ábragyűjtemény 8.8 ábra). Az előbbi projekcióból számított peakiness értékek az ábragyűjtemény 8.9 ábráján vannak ábrázolva. Ezen értékekről szintén nem tűnnek ki a keresett vonalak, viszont jól látható, hogy így sokkal kevesebb csúcs keletkezett. Az ábragyűjtemény 8.10 ábráján az látható, hogy hogyan néz ki a projekció abban az esetben, amikor egy 9 egység széles átlagoló ablakkal simítjuk a projekciót, négyszeres iterációval. Ami kitűnik az az, hogy a csúcsok alacsonyabbak és szélesebbek lettek, szögletesebbek. Az
25
4.6 ábra: A vízszintes vonal körülvéve a befoglaló téglalapjával (kék téglalap). ezen adatokból számolt peakiness értékek az ábragyűjtemény 8.11 ábráján látszódnak. Jól kivehetően domináns három csúcs. Ezen három csúcs helye a tesztmintán az ábragyűjtemény 8.12 ábráján van bejelölve. Ez a három csúcs egyértelműen nem a három egyenest határozta meg. 4.2.4
Kontúrkeresés
Az ennél egyszerűbb és alkalmasabb megoldás az volt, ha a kép binarizálásra került, majd végre lett hajtva egy dilatáció, és ezután a kép kontúrjai kerültek kiszámításra. A dilatáció azért szükséges, mert a vonalakban nyomdahiba miatt esetleges kisebb, egy-két pixel széles szakadások keletkezhetnek, és így nem maradnak összefüggőek. A kapott képen kontúrkeresést végrehajtva meghatározásra kerülnek az egyes összefüggő komponensek befoglaló téglalapjai, és azok a komponensek lesznek a vízszintes vonalak, amiknek szélessége eléri a teljes kép szélességének 70%-át (4.6 ábra). Ez a megoldás akkor is működik, ha az író ráírt a vonalra, de ekkor az utolsó sor tartalmazni fogja az elválasztó vonalat is vagy az a sor teljes egészében lemarad (4.7, 4.8 ábra). Ezzel a módszerrel mind az 1539 dokumentumban sikeresen meghatározásra került a kézzel írott rész.
4.7 ábra: Az önkéntes ráírta a nevét a vonalra
4.8 ábra: Az önkéntes ráírta a kézzel írt sort a vonalra.
26
4.3
A kézzel írt rész beforgatása Nyomtatott
szövegek
esetében
a
sorok
ferdeségét
a
kép
Fourier
transzformáltjának magnitude (nagyság) spektrum részéből lehetséges megállapítani [24]. Ez a módszer a kézzel írt szövegek esetében is működik (4.9 ábra). Mivel az adatbázisban lévő képek között nem volt található ferdén írt szöveg, ezért utólag lett elferdítve két fokkal (ábra: 4.9 (a)), és az lett Fourier transzformálva (ábra: 4.9 (b)). A transzformáció után gamma korrekciót kell végezni a képen, majd növelni a kontrasztot (ábra: 4.9 (c)), ezután egy fix küszöbbel binarizálni a képet (ábra: 4.9 (d)) és a kapott mintából megállapítható a ferdeség foka. A szükséges elforgatás mértéke kiszámítható a legalsó-legbaloldaliabb és a középső fehér pixelek x tengelyen vett távolságából. Ez a lépés tulajdonképpen nem szükséges, mivel a későbbi lépésekben a kézzel írt sorok egyenként vízszintes irányba lesznek forgatva.
27
(a)
(b)
(c)
(d)
4.9 ábra: (a) Az eredeti szövegrész elforgatva 2 fokkal. (b) A Fourier transzformált kép (c) Gamma korrekció és kontraszt növelés után. (d) Binarizálás után.
28
4.10 ábra: Feketével: a kontúrvonalak és azok befoglaló téglalapjai. Zölddel: a sorok előzetesen megállapított befoglaló téglalapjai, valamint az egyes komponensek kontúrvonalainak súlypontjai.
4.4
A sorok szétválasztása Az input kép első 50 oszlopa levágásra kerül. Erre azért van szükség, mert a
szkennelés során a képek bal szélén valami oknál fogva zaj jelenik meg, és binarizálás után előtér pixelekké válnának (ábragyűjtemény: 8.4 ábra). Ez a rész eltávolítható, mivel biztosan nem tartalmaz írást, mert a lapolvasóba jobbra igazítva tették bele a lapokat, és ezért alakult ki zaj a kép bal oldalán. A képet Otsu módszerrel binarizálni kell és ezután készül vízszintes projekció, majd csak azok a sorok lesznek figyelembe véve csúcsként, ahol a projekció összege legalább a 10%-a a legnagyobb projekció összegnek. Ezután a projekcióban lévő csúcsok kezdő- és végpontjai meghatároznak egy-egy téglalapot az eredeti képen. Azokat a befoglaló téglalapokat veszi csak figyelembe, amik magassága eléri a legnagyobb befoglaló téglalap magasságának 30%át, ezáltal kiszűrhetőek a tévesen sornak észlelt sor részletek. Minden egyes sornak hat tulajdonsága lesz: a négy oldalának helye, a vízszintes felezővonalának a helye és egy kép, ami tartalmazza a sorban lévő írást, ami legelőször üres, csak később fognak belekerülni a kézzel írt vonások (4.10 ábra). Ezután a képen megkeresi az összes olyan kontúrt, aminek befoglaló téglalapjának területe legalább 25 pixel és van olyan pixelérték, ami 150-nél kisebb (sötétebb). Ezeket a kontúrokat besorolja az előzőleg meghatározott sorokba aszerint, hogy a kontúr súlypontja melyik sor közepéhez van a
29
4.11 ábra: A jobb alsó sarokban megjelent apró zaj. legközelebb. A sor határait kibővíti, ha szükséges, hogy ne lógjon le róla az írás, majd a sorhoz létrehozott képre ráírja az eredeti képről a kontúr befoglaló téglalapjának helyén lévő írást. Így minden sor egy különálló kép lesz, és a betűk teteje és alja nem vágódik le. Problémát okozhat, ha az utolsó sorba már csak egy rövid szó kerül, ugyanis ekkor a projekciója túl kicsi lesz ahhoz, hogy a 10%-os küszöbértéket elérje, ezért az utolsó előtti sorhoz csatolja az algoritmus. Ennek megoldására az elkészült képek közül azokat, amik másfélszer magasabbak, mint az átlagos képmagasság, ketté kell vágni. Légyegében arra az egy képre alkalmazni kell ugyanazt a módszert, amit az eredeti képre ahol még egyben volt az összes sor. Keletkezhetnek olyan sorok, amik csak valami maszatot vagy pontot tartalmaznak, ezek kis méretük miatt utólagosan könnyen kiszűrhetőek. Előfordulhatnak olyan sorok, amikben a zaj a sor végére kerül, és ez által egy felesleges üres rész jelenik meg a sor végén a zajjal (4.11 ábra). Ez utólagosan javítható függőleges projekció elkészítésével és vizsgálatával (a komponensenkénti zajszűrést nem érdemes szigorítani, mivel az kiszűrné a kisebb íráslejeket is). Az ábragyűjtemény 8.3 ábráján láthatóak az ábragyűjtemény 8.2 ábráján lévő kitöltött formanyomtatványból az ismertetett módszerrel kinyert sorok.
4.5
A sorok elforgatása A sorok elforgatásának első lépése a ferdeség megmérése. Erre két külön
módszer kerül bemutatásra, az egyik az egyszerű lineáris regresszió, a másik a TheilSen féle regresszió, vagy más néven Kendall-Theil regresszió. Mindkettő esetében az első lépés oszloponként végigmenni a képen, és a legalsó előtér pixel koordinátáit eltárolni egy listában, később ezt a listát felhasználva kapjuk meg a meredekségét a regressziós egyenesnek.
30
(a) (b) 4.12 ábra: (a) Lineáris regresszió, (b) Kendall-Theil regresszió Látható, hogy a Kendall-Theil regresszió esetében nem változik meg számottevően a regressziós egyenes pozíciója a kívülálló pontok miatt. A piros pixelek jelölik az oszlopban lévő legalsó pixelt, kékkel a regressziós egyenes látható. 4.5.1
A ferdeség meghatározása lineáris regresszióval
A lineáris regresszió meghatároz egy egyenest az adott pontok koordinátái alapján úgy, hogy az egyenes és pontok közti távolságok négyzetösszege minimális legyen [25]. A regressziós egyenes meredekségét a 4.3 kifejezés szerint kapjuk meg [25]. (4.3 kifejezés)
Ahol m a regressziós egyenes meredeksége, x és y a pontokhoz tartozó koordináták,
a pontokhoz tartozó x és y koordináták számtani közepe, n pedig az
x és y koordinátapárok (pontok) száma. 4.5.2
A ferdeség meghatározása Kendall-Theil regresszióval
E módszer esetében az összes pont koordinátái közt kiszámítjuk a meredekséget, és ezeknek a meredekségeknek a mediánja lesz a kiszámított meredekség (4.4 kifejezés) [26]. (4.4 kifejezés) Ahol m a regressziós egyenes meredeksége, j > i és i, j
{1..n} ahol n az x, y
koordinátapárok száma. Ez a módszer kevésbé érzékeny a kívülálló pontokra (4.12 ábra).
31
(a)
(b)
(c)
(d)
(e)
4.13 ábra: Felülről lefelé: (a) az eredeti kép, (b) lineáris regresszió, (c) Kendall-Theil regresszió, (d) a lineáris regresszió által megállapított meredekség alapján elforgatott kép, (e) a Kendall-Theil regresszió által megállapított meredekség alapján elforgatott kép. Első ránézésre nem szembetűnő, de a (d) képen a szöveg már inkább balról jobbra emelkedik, minthogy vízszintes lenne, igaz az eltérés igen csekélynek mondható. 4.5.3
A két módszer összehasonlítása
Jelen probléma esetében a Kendall-Theil regresszió alkalmazása hatékonyabb, mivel azoknak a betűk helyén, amiknek az alsó alapvonal alá lógó vonásaik vannak (pl. y, q, j, stb.) a legalsó előtérpixel jóval az alapvonal alá kerül és ezek „kívülállónak” fognak számítani. Az egyszerű lineáris regresszió viszont túlbecsülheti a ferdeség mértékét, és túl nagy szöggel fogja kompenzálni a ferdeséget a forgatásnál, emiatt az ellentétes irányban lesz ferde az írás (4.13 ábra).
32
4.5.4
Az elforgatás megvalósítása
Az affin transzformáció koordináták leképzésére alkalmas a meglévő koordináták függvényében, olyan műveleteknél, mint például az eltolás, átméretezés, forgatás, nyírás, vetítés tengelyre, tükrözés tengelyre, stb. és ezek konkatenáltja (egymás utáni alkalmazása egy lépésben), tehát az összes lineáris transzformáció elvégezhető vele, kiegészítve az eltolással. Ezek a transzformációk végrehajthatóak ha mátrixszorzással megszorozzuk a transzformálandó koordinátákat a transzformáló mátrixszal, ezáltal megkapjuk az új koordinátákat. Az affin transzformáció során a forgatáshoz felhasznált mátrix homogén koordinátás alakja a 4.5 kifejezésben látható, a koordinátákkal és a mátrixszorzással együtt.
(4.5 kifejezés)
Ahol a
az óramutató járásával ellentétes irányban történő forgatás fokban
megadva és kifejezhető a 4.6 kifejezés szerint. (4.6. kifejezés) Ha megvannak az új koordináták, akkor arra a helyre beírjuk az eredeti koordinátákon lévő pixelintenzitást. Ez a gyakorlatban fordítva működik, a célképen lévő koordinátákhoz keressük a hozzá tartozó eredeti koordináták értékeit, hogy ne maradjanak kitöltetlen helyek a célképen. Ezek a kitöltetlen helyek azért jöhetnének létre, mert ha a transzformáció során nem kizárólag csak egész számokkal dolgozunk, akkor olyan koordinátákat kapunk eredménynek, amik nem egész számok, a pixelek koordinátái pedig csak diszkrét értékeket vehetnek fel. Ez az eset a visszakereséskor is bekövetkezhet, ilyenkor a környező pixelek értékei alapján valamilyen módszerrel interpolálni kell. Interpolációs módszerek lehetnek például: Legközelebbi szomszéd: ha a legközelebbi pixel értékét választjuk, fűrészfogas élek jöhetnek létre, viszont nem keletkezik olyan intenzitású pixel az új képen, ami az eredetin nem volt.
33
Bilineáris interpoláció: ezen interpoláció esetén az élek természetesebbnek hatnak, viszont létrejöhetnek olyan intenzitású pixelek, amik eddig nem voltak. Bilineáris interpolációnál a négy szomszédos pixel intenzitásából számítódik ki az új intenzitás. A vízszintes irányban lévő szomszédok intenzitása súlyozottan átlagolásra kerülnek, a súly fordítottan arányos a szomszéd távolságával (ezért lineáris). Ez az átlagolás a függőleges szomszédokkal is kiszámításra kerül, majd ennek a két átlagnak a számtani átlaga határozza meg az új pixel intenzitását Bicubic interpoláció: más néven kettős köbös interpoláció, tizenhat szomszédot vesz figyelembe, simább képet eredményez, viszont az éleknél begyűrűződés jelenhet meg. Az egyes interpolációk előnyeit és hátrányait mérlegelve, a bilineáris interpoláció tűnik a legmegfelelőbbnek e probléma esetében, mert a legközelebbi szomszéd módszer túl durva közelítést ad, a kettős köbös esetében pedig az éleknél szellemkép jelenhet meg, a kézírás esetében pedig sok az él, sok a kontúr, ezért nem célszerű a bicubic interpoláció alkalmazása. Azon koordinátákon lévő pixelek értékei, amelyeknek koordinátái nem szerepelnek, az eredeti képen fehérek lesznek. Mivel az új kép mérete különböző lesz az eredeti kép méretétől, ezért a szöveget befoglaló téglalap mentén körbe kell vágni, hogy a kép ne tartalmazzon felesleges részeket.
34
4.6
Az írás dőltségének megszüntetése A probléma megoldására három különböző módszer került implementálásra és
összevetésre, két globális és egy lokális eljárás. Legelső lépésként mindhárom esetben a kép Otsu-binarizáláson esik át. A globális eljárás esetében a teljes kép azonos meredekség mellett affin transzformációval nyírásra kerül, lokális esetében pedig oszloponként eltérő is lehet a nyírás meredeksége [27]. Az affin transzformáció során a nyíráshoz felhasznált mátrix homogén koordinátás alakja a 4.7 kifejezésben látható.
(4.7 kifejezés)
Az mx az x tengellyel párhuzamos nyírás mértékét adja meg, az my pedig az y tengellyel párhuzamosat. A tx vízszintes, a ty függőleges eltolást eredményez. Jelen esetben az mx értékének a megtalálása a feladat, valamint a tx értékét beállítani az 4.8 kifejezés szerint, my és ty értékének nullának kell lennie. (4.8 kifejezés)
Ahol h a kép magassága. A nyírás soronként eltolja a szöveget vízszintes irányba, attól függően, hogy hányadik sorról van szó (4.14 ábra). A vízszintes irányú eltolásra azért van szükség, hogy a nyírás után ne lógjon le a képről a szöveg (4.15 ábra). Interpolációs eljárásnak szintén a bilineáris interpolációt választottam a 4.5-ös fejezetben tárgyalt okok miatt. Abban az esetben, ha egy pixelhez nem rendelhető szomszédos pixel az eredeti képről, a pixel intenzitás értéke 255 lesz, vagyis a pixel
4.14 ábra: Egy téglalap és annak nyíráson átesett változata.
35
4.15 ábra: Felül az eredeti szöveg, alatta a kiegyenesített változat eltolási korrekció nélkül, valamint az eredeti képre nem megfeleltethető pixelek feketével ábrázolva. Legalul fekete helyett fehérrel kitöltve a pixelek, és eltolva a kép, a szükséges mértékben és a megfelelő irányba. A példán globális módszerrel lett megállapítva a dőlésszög. fehér lesz. A képet -60° és +60° közt fokonként el kell nyírni, majd minden kapott képen általánosított- vagy függőleges projekciót kell számítani és ezekből egy dőlési térképet készíteni, amit később felhasználható a három különböző módszer bemeneteként.
36
4.16 ábra: Az X tengelyen a nyírási fokok -60-tól +60 fokig, az Y tengelyen a szórás. Az oszlopdiagram felett a vizsgált kép.
4.6.1
A dőlésszög meghatározása a függőleges projekció szórása által
A nyírt képekről függőleges projekció készül, minden egyes projekciónak kiszámításra kerül a szórása, ez összesen 121 projekció, mivel 121 különböző fokkal lett elnyírva a kép. Az eredmények a 4.16 ábrán láthatóak. A szórás pont a 60. oszlopban a legnagyobb, vagyis amikor 0 fokkal lett elnyírva a kép, ez a megoldás egyértelműen rossz, mivel ránézésre látszik, hogy a szöveg jobbra van dőlve. A vízszintes projekcióból számított szórással tehát nem lehetséges megállapítani, hogy dőlt-e a szöveg, a sejtés miszerint minél nagyobb a szórása a vízszintes projekciónak annál egyenesebbek a betűk, nem bizonyosodott be.
37
4.17 ábra: A dőlési térkép. Látható, hogy a szöveg körülbelül 30°-40° körül van eldőlve, mert a fehér csomók a kép alsó részén helyezkednek el. A legfelső sor a -60°kal nyírt szöveghez tartozik, a legalsó a +60°-kal nyírthoz. 4.6.2
A globális dőlésszög meghatározása általánosított projekció által
A módszer a [27] alapján került megvalósításra. Általánosított projekció esetében az egyes oszlopokban nem az előtérpixelek számát számoljuk meg, hanem súlyozásra kerülnek azok a pixelek, amik előtt szintén előtérpixelek vannak. A háttérpixelek közt egyedül álló előtérpixel értéke egy, viszont azon pixelek értéke, amit előtérpixel előz meg kettővel nagyobb, mint a megelőző pixel értéke. Ezen egybefüggő részsorozatok összegzésre kerülnek, majd az összeget négyzetre kell emelni. Ezeket a négyzetösszegeket végül összegezni kell, és ez adja majd meg az oszlopra vonatkozó általánosított projekciót. Ezzel a módszerrel az egybefüggő vonások négyzetesen súlyozva vannak hosszuk alapján. Ezt a projekciót minden nyírási szögre el kell végezni és így megkapunk egy dőlési térképet (4.17 ábra). A dőlési térképből megállapítható egy globális dőlési szög. Minél világosabb a terület, annál nagyobb az értéke az általánosított projekciónak az adott pontban. A sorokban lévő értékeket összegezni kell, a kapott sorösszegeket súlyozni kell az adott sorhoz tartozó sorszámmal, majd ezeket a súlyozott sorösszegeket össze kell adni, és az eredményt elosztani a sorok súlyozatlan sorösszegével (4.9 kifejezés). (4.9 kifejezés) Ahol i a sorok indexe (sorszáma), n az oszlopok száma, a a dőlési térkép mátrix egy értéke (adott fok adott oszlopában az általánosított projekció értéke), j pedig az oszlopindex. A p érték lesz a globális dőlési szög, ami alapján nyírni kell a képet, az eredmény a 4.18 ábrán látható.
4.18 ábra: A globális módszerrel kiegyenesített változata a 30. ábrán látható szövegnek.
38
4.19 ábra: Felül az eredeti kép, alul a sikertelen kiegyenesítés A kézzel írt szöveg globális dőlésszög alapján az esetek túlnyomó többségében megfelelő eredményt ad, mivel egy soron belül általában nem változik számottevően a dőlés mértéke. Egyes kutatások [27] azonban mégis azt az eredményt adták, hogy a lokális dőlésszög meghatározás 37,3%-ról 42,24%-ra javítja a szószintű felismerési arányt. A 4.19 ábrán egy általam készített tesztkép van, ami bemutatja, hogy a globális dőlésszög meghatározás nem működik olyan esetekben, ahol a dőlés mértéke és iránya változó. 4.6.3
A lokális dőlésszög meghatározása általánosított projekció által
Ez a módszer is a [27] alapján került megvalósításra. Lényege, hogy a képen oszloponként kerül meghatározásra a lokális optimuma a dőlésszögnek. Ehhez először a dőlési térképen lévő „csomókat” ki kell terjeszteni a környezetükben, ennek okai később lesznek tárgyalva. Ha megvannak a lokális optimumok, akkor függőleges irányban költséget kell számolni a lokális optimumtól való távolság és az általánosított projekció értékének függvényében. Ez azért szükséges, mert a végső lépésben meg kell határozni egy útvonalat, ami a lokális optimumokat a legjobban közelíti, és a szomszédos oszlopok közt a dőlési szög különbsége nem haladja meg az egy fokot. Ezt a dinamikus programozás módszerével lehet kiszámítani a költségek felhasználásával. A feltétel, hogy oszloponként ne legyen nagyobb a dőlés mértékének változása egy foknál, azért fontos, hogy ne legyen túl éles az átmenet és a betűk ne tűnjenek nagyon torznak. A következő oldalon áttekintés gyanánt, az egyes lépések részeredményei kerülnek ábrázolásra.
39
(a)
(b)
(c)
(d)
(e)
(f)
(g) 4.20 ábra: (a) eredeti szöveg, (b) általánosított projekció, (c) kiterjesztett általánosított projekció, (d) lokális optimumok, (e) költségek a lokális optimumoktól számítva, (f) költségek a globális optimum függvényében, és a globális optimumok, (g) kiegyenesített szöveg
40
Az általánosított projekció kiterjesztése (4.20 (c) ábra) azért szükséges, hogy a későbbi lépésben a globális optimum által meghatározott út ne legyen túl cikk-cakkos, a csomópontokon lehetőleg minél vízszintesebben haladjon át a globális optimumok által meghatározott egyenes. A kiterjesztés menete a következő: az egyes pozíciókban az általánosított projekció értékének négyzetgyökét szét kell teríteni vízszintes irányban jobbra is és balra is. Egy vizsgált pozíció új értéke fordítottan arányos a vizsgált csomópont és a pozíció távolságának négyzetével és egyenesen arányos a csomópontban lévő általánosított projekció értékének négyzetgyökével (4.10 kifejezés). Egy pozíció csak akkor kap új értéket, ha az nagyobb az aktuális értékénél, tehát ha két csomópont kiterjesztése átfedi egymást, akkor a dominánsabb érvényesül. (4.10 kifejezés) Ahol a az eredeti dőlési térkép, a’ a kiterjesztett dőlési térkép, i a sorindex, j az oszlopindex, l a távolság, X pedig a létező oszlopindexek halmaza. A lokális optimumok meghatározása (4.20 (d) ábra) hasonló, mint globális módszerrel az egész képre vonatkozó dőlési szög meghatározása, azonban itt csak a képnek az adott oszlopára kell végezni a számítást, nem az egész képre. Ha az oszlopösszeg zérus (tehát ha nincs előtér pixel az adott oszlopban), akkor a lokális optimum 0° lesz. A költségek meghatározása (4.20 (e) ábra) oszloponként történik. A költség négyzetesen arányos a lokális optimum és az aktuális pozíció közti távolsággal, viszont ha ez az érték meghaladja az oszlopban található legnagyobb általánosított projekció négyzetgyökét, akkor az utóbbi érték lesz figyelembe véve (4.11 kifejezés). (4.11 kifejezés) Ahol c a költségfüggvény, i a sorindex, j az oszlopindex, a’ a kiterjesztett dőlési térkép, p’ a lokális optimumok vektora, Y pedig a létező sorindexek halmaza.
41
(a) (b)
(c) 4.21 ábra: (a) eredeti szöveg, (b) globális dőlésszög meghatározással kiegyenesített szöveg, (c) lokális dőlésszög meghatározással kiegyenesített A legkevésbé költséges út meghatározása (4.20 (f) ábra) rekurzív módon a 4.12 kifejezés szerint kiszámolható. (4.12 kifejezés) Ahol q az akkumulált költségfüggvény, c a költségfüggvény, i a sorindex és j az oszlopindex. A rekurzív módszer számításigényesség szempontjából nem igazán mondható hatékonynak, de a dinamikus programozás módszerével, sokkal gyorsabban és egyszerűbben elvégezhető a feladat. Balról jobbra haladva, oszloponként minden pozícióra kiszámoljuk az előző oszlopba tartozó három szomszéd közül a legkisebb költségű költségének és az aktuálisan vizsgált pozíció költségének az összegét. A szomszédságnál három szomszéd van figyelembe véve, mivel ±1° valamint a 0° eltérés jöhet számításba a dőlésszög esetén a megszabott kritérium miatt. A részeredményeket egy mátrixban tároljuk. A mátrix utolsó oszlopában ki kell keresni a minimális elemet, ez lesz a globális optimum az utolsó oszlopban. Ezután visszafele haladva a három szomszéd közül mindig azt kell választani, amelyik értéke a legkisebb. Ezzel a módszerrel megkapjuk a legkisebb költségű utat és ezáltal minden oszlopra a dőlési szöget. Oszloponként elvégezve a nyírást az oszlophoz tartozó dőlési szöggel megkapjuk a kiegyenesített írást (4.20 (g) ábra). Látható, hogy a harmadik l betű nem lett sikeresen kiegyenesítve, mivel a dőlésszögnek túl gyorsan kellett volna változnia. Az ilyen esetek azonban viszonylag ritkán fordulnak elő természetes kézírás esetében. A lokális dőlésszög alapján történő kiegyenesítés egyes esetekben nem kívánatos hibákat produkál, ilyen látható például a 4.21 (a) ábrán.
42
4.22 ábra: A horizontális projekció és annak deriváltja
4.7
Az írás régióinak normalizálása Az írást három régióra kell osztani. Az alsó alapvonal és a felső alapvonal közt
van az írás legtöbb része. Meg kell határozni ezt a két vonalat, és ezután az ezek által meghatározott három régió magasságát egy előre megadott értékre be kell állítani, a benne lévő eredeti képet pedig ennek függvényében nyújtani vagy zsugorítani kell függőleges irányban [8]. A [9] szerint a horizontális projekció deriváltja nem ad megfelelő eredményt, ha az írás felfele vagy lefele ferdül, ezért más módszert ismertettek. Mivel azonban én az egyik megelőző lépésben már kijavítottam a ferdeséget (és a dőlést is), a horizontális projekció deriváltja megfelelő kiindulási alapot ad. Az általam ismertetett módszerrel viszonylag pontosan meghatározhatóak az alsó- és felső alapvonalak. E két alapvonal meghatározásához először Otsu módszerrel binarizálni kell a képet, majd horizontális projekciót készíteni róla és azt deriválni. A deriválás során az aktuális sor és a szomszédos sor projekciójának különbségének négyzete lesz a derivált érték minden egyes sorban (4.22 ábra). Azért a különbség négyzetével kell számolni, hogy súlyozva négyzetesen súlyozva legyen a különbség, mert az kisebb különbségek nem fontosak. Ezt következően ki kell számolni a derivált projekció súlypontját. Ez megad egy sorindexet (4.13 kifejezés). (4.13 kifejezés)
43
4.23 ábra: Pirossal a felső-, narancssárgával az alsó alapvonal látható. A kék vonalak a legjobb 20%-ba tartozó vonalak. Ahol i a sorindex, n a sorok száma és p a vízszintes projekció deriváltja. Ezután kiválasztásra kerül a derivált értékeket tartalmazó listából (p) a legjobb 20% értéke és sorindexe. Jóság alatt azt kell érteni, minél nagyobb az értéke, annál jobb. A megmaradt listaelemeken kiszámításra kerül a sorindexük és a súlypont sorindexe közti távolság négyzete. Ezekből a távolságokból szórást kell számítani, majd kiszűrni azokat a listaelemeket, amik távolsága a súlyponttól nagyobb, mint a szórás fele. A megmaradtak közül a legmagasabb sorindexű listaelem sorindexe lesz az alsó alapvonal y koordinátája, és a legmagasabb sorindexű listaelem sorindexe pedig a felső alapvonal y koordinátája lesz (4.23 ábra). A két vonal által meghatározható az írás három régiója. Ez a három régió egyenként 50 pixel magasságú lesz, ehhez át kell méretezni őket. Ez az érték szabadon választott, én 50-et választottam, így az egész szöveg magassága 150 pixel lesz. Abban az esetben, ha az eredeti képen a felső vagy az alsó régió magassága kisebb, mint a kép magasságának a hatoda, akkor az a régió nem kerül átméretezésre, hanem helyette az új képen csupa háttérpixelekből álló terület lesz. Ezek az esetek akkor fordulhatnak elő, ha egy olya betű sincs az írásban, amely az alsó alapvonal alá, vagy a felső alapvonal fölé lógna (4.24 ábra)
4.24 ábra: Felül az eredeti szöveg az alapvonalakkal, alatta a függőleges irányban méretre normalizált szöveg.
44
4.8
A betűk szélességének normalizálása Ez a lépés a [8]-ben megismertekre alapszik. Első lépésben itt is Otsu
módszerrel binarizálni kell a képet, majd kiszámolni a középvonal helyét, ami az alsó alapvonal és a felső alapvonaltól egyenlő távolságra helyezkedik el. Ezek után e vonal mentén végig kell haladni a képen, és megszámolni a az előtérpixelek és háttérpixelek váltakozásának a számát. Mivel egy vonás két ilyen váltásból áll (először fehérből feketébe, majd feketéből fehérbe), ezért felezni kell az összeszámolt értéket. Általánosságban egy betű két vonása halad át a középvonalon. Egyes betűknek három vonása, pl. m, egyes betűknek pedig csak egy, pl. t. Ezzel a módszerrel egy becslést lehet adni a sorban lévő betűk darabszámára, de pontosan nem lehet meghatározni, hiszen ahhoz fel kellene tudni ismerni a betűket, ami ebben a lépésben még nem lehetséges, mivel ez a lépés még az elő feldolgozás lépéseihez tartozik. Ezután a kép szélességét a kapott becsült darabszám valahányszorosára kell állítani, és átméretezni a képet ekkora méretűre. Én paraméternek a 100-at választottam, az így kapott eredmény a 4.25 ábrán látható.
4.25 ábra: Legfelül a szélességre normalizálatlan kép, középen zöld vonallal látható a középvonal, alul pedig a szélességre normalizált kép.
45
4.26 ábra: Egy sötét és egy halványabb íráskép.
4.9
A kép intenzitásértékeinek normalizálása A [12]-ben található módszer alapján lett megvalósítva. Erre a lépésre azért van
szükség, mert a jellemzővektor felépítésénél, az egyik jellemző az oszlopban lévő intenzitásértékek számtani átlaga lesz. Mivel nincs megkötés a toll típusára, ezért előfordulhat az, hogy egyes írásképek hol halványabbak, hol sötétebbek (4.26 ábra). Ezért a képen az intenzitásértékeket hisztogram széthúzásos módszerrel normalizálni kell, így a legkisebb érték 0, a legnagyobb pedig az egy bájton ábrázolható legnagyobb érték, 255 lesz. Ezt úgy lehet elérni, ha végigmegyünk az eredeti kép összes pixelén és kikeressük a legkisebb és legnagyobb intenzitásértéket, és utána még egyszer végigmegyünk az eredeti képen, és a 4.14 kifejezés szerint kiszámoljuk az új intenzitásértékeket minden pixelre. (4.14 kifejezés) Ahol f’(x,y) az új, f(x,y) pedig a régi képfüggvény. Max és min pedig a régi (eredeti) képen a legnagyobb és legkisebb intenzitásértékek. A művelet eredménye a 4.27 ábrán látható egy konkrét példán keresztül, ahol az utolsó előtti sor az eredeti kép, és az utolsó az intenzitásértékekre normalizált.
46
4.10 A normalizálás lépéseinek összefoglalása Áttekintésként, a normalizálás egyes lépései egy konkrét soron szemléltetve, hogy össze lehessen vetni az egyes lépések közti különbségeket és a kezdeti állapotot a végállapottal (4.27 ábra).
4.27 ábra: Felülről lefelé: az eredeti sor, az elforgatott sor, a dőltség megszüntetése, az írás függőleges régióinak normalizálása, az írás szélességének normalizálása, a kép intenzitásértékeinek normalizálása.
47
4.11 A jellemzők kinyerése A [11]-ben felsorolt jellemzőket használtam fel. Az eredeti képből két képet kell készíteni, az egyik az eredeti kép invertált változata, a másik kép pedig az Otsu binarizált változata. A képeken oszloponként végig kell menni, és az oszlopban található pixelekből a jellemzőket ki kell nyerni. Kilenc jellemző kerül kinyerésre, ezek az alábbiak: Az oszlopban található pixelek intenzitásátlaga. A pixelek súlypontja (4.15 kifejezés). A súlypont másodrendű nyomatéka (4.16 kifejezés). Az első fekete pixel pozíciója. Az utolsó fekete pixel pozíciója. Az előző oszlopban lévő első fekete pixel pozíciójának és a következő oszlopban lévő első fekete pixel pozíciójának a különbsége Az előző oszlopban lévő utolsó fekete pixel pozíciójának és a következő oszlopban lévő utolsó fekete pixel pozíciójának a különbsége A fekete-fehér váltások száma. A fekete és fehér pixelek számának aránya a legfelső és legalsó fekete pixel között.
4.28 ábra: A 4.27 ábrán lévő normalizált szöveg jellemzői ábrázolva egy diagramon.
48
Az intenzitásátlag kivételével tehát mindig a binarizált kép alapján kell számolni az értékeket. (4.15 kifejezés)
(4.16 kifejezés)
Ahol
a súlypont y koordinátája. Mivel egy oszlopvektorban keresünk, nincs
szükség az x koordinátára. C az oszlopvektor, y az aktuális sorindex, n a sorok száma. A kinyert jellemzők grafikus ábrázolása 4.28 ábrán tekinthetőek meg.
49
5 Az elkészült program bemutatása 5.1
A modulok közti kapcsolat A modulok kapcsolata viszonylag egyszerű, az egyik modul csak egy másik
modul kimenetétől függ (5.1 ábra).
Íráskép behatárolása
Sorok szétválasztása
Sorok elforgatása
A betűk szélességének normalizálása
Írás régióinak méretbeli normalizálása
Írás dőltségének megszüntetése
A kép intenzitásértékeinek normalizálása
Jellemzők kinyerése
5.1 ábra: A modulok függőségi sorrendje
50
5.2 ábra: A program futás közben
5.2
A program működésének bemutatása A program egy konzolalkalmazás. Hat paramétert vár, ezek sorrendben a
következők: A könyvtár elérési útja, ahol az IAM adatbázis képei vannak. A könyvtár, ahova a normalizált sorokat és jellemzőiket menti. Az egy nyomtatványhoz tartozó sorok, külön mappába kerülnek, a mappa neve a nyomtatvány azonosítója lesz. A mappán belül egy sor fájlneve a sor sorszáma lesz, ugyanezen a néven, de csv kiterjesztéssel pedig a jellemzői kerülnek mentésre. A felső alapvonal fölötti rész leendő magassága pixelben. Az alsó- és felső alapvonal közti rész leendő magassága pixelben. Az alsó alapvonal alatti rész leendő magassága pixelben. Egy betű leendő szélessége pixelben. Nyírás módja: o 0: globális o 1: lokális
51
Ha a felhasználó túl kevés, vagy hibás paramétert ad meg, a program tájékoztatja erről a felhasználót, és segítségül megjeleníti a várt paraméterek listáját és sorrendjét, és ezekről egy konkrét példát. A program sorban elkezdi feldolgozni az bemeneti képeket (5.2 ábra). A képekről kinyert sorokat párhuzamosan dolgozza fel, egy időben annyit normalizál, ahány processzormagot lát az operációs rendszer. A normalizált sorok szürkeskálás PNG képekként kerülnek mentésre, a jellemzők pedig egy pontosvesszővel tagolt szöveges fájlba kerülnek. A fájl első sora a kép első oszlopának felel meg, és így tovább. A sorokon belül a kilenc jellemző értéke pontosvesszővel van elválasztva egymástól. A jellemzők a 4.11-es fejezet szerinti sorrendben követik egymást.
5.3
A kiszámolt adatok helyességének tesztelése Az íráskép behatárolása modul szemrevételezéssel lett tesztelve. Ez megoldható
volt, ugyanis csak körülbelül 1500 tesztesetet kellett átnézni. A kontúrkereséses megoldással minden formanyomtatványon sikeresen meghatározásra került a kézírást tartalmazó régió. A sorok szétválasztása modul tesztelése sem volt automatizálható. Véletlenszerű minták alapján viszont behatárolható volt, milyen esetekben ad pontatlan eredményt az algoritmus, vagyis rosszul szegmentált sorokat. Ezek az esetek általában egymásba lógó sorok és egy-két szavas sorok esetében fordultak elő, valamint ha nagyobb mennyiségű tintapaca folyt a lap valamelyik részére, azt is besorolta egy – a legközelebb lévő – sorba az algoritmus. A sorok elforgatása esetében nemhogy nem automatizálható a tesztelés, hanem még ránézésre is nehéz megállapítani, hogy tökéletesen vízszintes-e a sor, mivel 1°-nál kisebb eltérés egyszerűen nem észrevehető. Annak géppel való megállapítása pedig, hogy mi lenne az optimális elforgatási szög, már megtörtént a normalizálás során, és korrigálva lett. A kapott eredményeket szúrópróbaszerűen megvizsgálva, nem találtam hibás eseteket. Az írás dőltségének megszüntetése szintén nem tesztelhető objektíven. Az viszont kitűnt, hogy a lokális dőlésszög meghatározásnál jelentkezhetnek olyan nem kívánt torzulások, amik furcsává teszik az írásképet. A globális dőlésszög meghatározás esetében nem jelentkeztek ilyen problémák, és a szúrópróbaszerűen megvizsgált
52
eseteknél nem is adott rosszabb eredményt, mint a lokális módszer. A [26] szerint viszont a lokális módszerrel javult a szófelismerési arány. Tesztelni tehát ezt a lépést, és a többi lépést is csak úgy lenne igazán érdemes, ha egy kézírásfelismerő-rendszerrel felhasználnánk inputként a normalizált képet. Természetesen két teszteset között csak egyetlen modul működését szabad befolyásolni. Ekkor ugyanis számszerűsített adatokat kapnánk, és ezek az adatok ráadásul nem azt tükröznék, hogy egy ember szubjektív véleménye szerint például mennyire találja egyenesnek a szöveget, hanem a kérdéses konkrét probléma szempontjából adna egy jósági értéket, vagyis arról, hogy az adott normalizációs lépés elősegíti-e a felismerést. Ugyanez igaz a betűk magasságának és szélességének normalizálására is, és az intenzitás normalizálására is, valamint a jellemzők kinyerésére is. Utóbbi esetben azt lenne célszerű vizsgálni, hogy milyen jellemzők használata esetén kapnánk jobb felismerési arányt. Az IAM adatbázis rendelkezik egy-két vizsgálható értékkel, amit a készítők által kifejlesztett algoritmus határozott meg, ilyenek például: a megállapított alsó és felső alapvonal pozíciója. Sajnos azonban ez sem felhasználható számomra, mivel a sorok szétválasztása lépésben az ő megoldásuk más eredményt ad, mint az én általam készített algoritmus, és ezért sokszor már a sorok magassága vagy a sorok befoglaló téglalapja sem azonos, emiatt a soron belüli alapvonalak pozíciója sem összeegyeztethető az én általam kapott pozíciókkal.
53
6 Összefoglalás A bemutatott rendszer képes tehát az IAM adatbázis képeit feldolgozni, a sorokat szétválasztani, azokat normalizálni és a sorok jellemzőit kinyerni. Ez a rendszer egy előfeldolgozó rendszer, ami lehetővé teszi, hogy egy szabadon választott tanítási módszerrel a kinyert jellemzők, és az inputképekhez tartozó megoldások alapján (amit szintén tartalmaz az IAM adatbázis) betanítsunk egy algoritmust az írás felismerésére. A sorok szétválasztása nem minden esetben tökéletes, a sorszétválasztó algoritmuson még lehetne javítani a későbbiekben. Számításigény szempontjából a legtöbb számítási kapacitást az írás dőltségének megszüntetése igényli, mivel 120-szor el kell nyírni a kérdéses képet. Mivel a nyírás és a forgatás is mátrixszorzásokkal megoldható, ezek a lépések általános célra is felhasználható grafikus gyorsító kártyák segítségével nagymértékben gyorsíthatóak. A sebesség azonban nem kritikus szempont, mivel az offline felismerés esetében nem szükséges valósidejű felismerés, mint például az online felismerés esetében.
54
7 Irodalomjegyzék [1] D. Tikk, R. Farkas, T. Kardkovács Zsolt, L. Kovács, T. Répási, Gy. Szarvas, S. Szaszkó és M. Vázsonyi, „Szövegbányászat”, Typotex, 2006, pp. 97 – 98 [2] U. Marti, H. Bunke és M. Zimmermann „A full English sentence database for off-line handwriting recognition”, Proceedings of the 5th International Conference on Document Analysis and Recognition, 1999, pp. 705 – 708, http://www.iam.unibe.ch/fki/databases/iam-handwriting-database/
Utolsó
látogatás: 2012.01.05. [3] F. Ali, T. Pavlidis, „Syntatctic Recognition of Handwritten Numerals”, IEEE Transactions on Systems, Man and Cybernetics, vol 7, Issue: 7, 1977, pp. 537 – 541 [4] Y. Lecun és C. Cortes, „MNIST handwritten digit database”, New York University Courant Institute, New York Google Labs, http://yann.lecun.com/exdb/mnist/
Utolsó
látogatás: 2012.01.05. [5] A. Vinciarelli, S. Bengio és H. Bunke, „Offline Recognition of Unconstrained Handwritten Texts Using HMMs and Statistical Language Models”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol 26, no. 6, 2004, pp. 709 – 720 [6] Parascript Kft., „ICR and OCR Technology from Parascript”, Colorado, Longmont, http://www.parascript.com/company2/tech_overview.cfm
Utolsó
látogatás:
2012.01.05. [7] K. M. Sayre, „Machine Recognition of Handwritten Words: A Project Report”, Pattern Recognition, vol. 5, no. 3, 1973, pp. 213 – 228 [8] U.-V. Marti és H. Bunke, „Handwritten Sentence Recognition”, Proceedings International Conference on Pattern Recognition, 2000, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.7716
Utolsó
látogatás: 2012.01.05. [9] M. Schüßler és H. Niemann, „A HMM-based System for Recognition of Handwritten Address Words”, Proceedings of Sixth International Workshop on Frontiers in Handwriting Recognition, Koreai Köztársaság, Taejon, 1998, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8998
Utolsó
látogatás: 2012.01.05. [10] E. Grosicki és H. El Abed, 10th International Conference on Document Analysis and Recognition, 2009, pp. 1398 – 1402
55
[11] A. Graves, M. Liwiczki, S. Fernández, R. Bertolami, H. Bunke és J. Schmidhuber, „A Novel Connectionist System for Unconstrained Handwriting Recognition”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol 31, no. 5, 2009, pp. 855 – 868 [12] M. Wienecke, Gernot A., G. Sagerer, „Experiments in Unconstrained Offline Handwritten Text Recognition”, In Proceedings of the 8th International Workshop on Frontiers in Handwriting Recognition, Ontario, Canada, August 2002 IEEE [13] H.
Bunke,
„Web-Based
Offline
Handwritten
Text
Line
Recognizer”,
Svájc, Berni Egyetem Gépi Látás és Mesterséges Intelligencia Kutatócsoport, http://www.iam.unibe.ch/fki/recognizer/welcome
Utolsó látogatás: 2012.01.05.
[14] E. Kavallieratou, N. Fakotakis és G. Kokkinakis, „Skew angle estimation for printed and handwritten documents using the Wigner-Ville distribution”, Image and Vision Computing 20, 2002, pp. 813 – 824 [15] R. Manmatha és J. L. Rothfeder, „A Scale Space Approach for Automatically Segmenting Word from Historical Handwritten Documents”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol 27, no. 8, 2005, pp. 1212 – 1225 [16] F. Shafait, D. Keysers és T. M. Breuel, „Efficient Implementation of Local Adaptive Thresholding Techniques Using Integral Images”, www.dfki.unikl.de/~shafait/papers/Shafait-efficient-binarization-SPIE08.pdf
Utolsó látogatás:
2012.01.05. [17] K. D. Derpanis, „Integral image-based representations” York University, Department of Computer
Science
and
Engineering,
http://www.cse.yorku.ca/~kosta/CompVis_Notes/integral_representations.pdf
Utolsó
látogatás: 2012.01.05. [18] M. Pastor, A. Toselli és E. Vidal, „Projection Profile Based Algorithm for Slant Removal”, Image analysis and recognition: internaional conference, ICIAR 2004, part 2, 2004, pp. 183 – 190 [19] U. Marti és H. Bunke, „The IAM-database: An English Sentence Database for Off-line Handwriting Recognition”, Int. Journal on Document Analysis and Recognition, Volume 5, 2002, pp. 39 – 46 [20] P.V.C. Hough, Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959 [21] J.F. Canny, „Finding Edges and Lines in Images”, Master’s thesis, MIT, 1983
56
[22] N. Otsu, „A threshold selection method from gray-level histograms". IEEE Transactions. Sys., Man., Cyber. 9 (1), 1979, pp. 62 – 66 [23] M. Shah, „Fundamentals of Computer Vision”, Mubarak Shah, 1997, pp. 56 – 57 [24] W. Postl, „Detection of linear oblique structure and skew scan in digitized documents”, Proceedings of International Conference on Pattern Recognition, 1986, pp. 687 – 689 [25] J.
Fidy,
G.
Makara,
„Biostatisztika”,
InforMed
http://www.tankonyvtar.hu/statisztika/biostatisztika-080904-56
2002 Utolsó
Kft,
2005, látogatás:
2012.01.05. [26] Civil and Environmental Engineering, Texas Tech University, „Alternative Regression Methods”, Data Analysis for Civil and Environmental Engineers, Summer 2010, pp. 1 – 4, http://cleveland2.ce.ttu.edu/teaching/ce_5333SU10/ce5333SU10Meeting07/AlternateRegression/F001-ce5333-AlternativeRegression.pdf Utolsó látogatás: 2012.01.05. [27] A. Kuhn, „Using Local Slant Correction to Normalize Handwritten Text Samples”, University of Bern, December 2005, http://scg.unibe.ch/archive/projects/Kuhn03a.pdf látogatás: 2012.01.05.
57
Utolsó
8 Mellékletek 8.1
Ábragyűjtemény
8.1 ábra: A sorok szétválasztásának lépései: (a) Eredeti kép. (b) Projekciós profil. (c) Simított projekciós profil. Láthatóak a csúcsok. (d) Sorok szétválasztása a simított projekciós profilban található csúcsok alapján.
58
8.2 ábra: Egy kitöltött formanyomtatvány az IAM adatbázisból [19].
59
8.3 ábra: Az ábragyűjtemény 8.2 ábráján található kitöltött formanyomtatványból kinyert sorok.
60
8.4 ábra: Az eredeti formanyomtatvány és binarizált változata. Jól kivehető a lap bal szélén a zaj miatt kialakult fekete csík.
61
8.5 ábra: a tesztkép peakiness módszerhez
8.6 ábra: a 8.5 ábráról készített vízszintes projekció
8.7 ábra: a 8.6 ábra értékeiből számított peakiness értékek
62
8.8 ábra: vízszintes projekció 5 szélességű átlagoló ablakkal, háromszori iteráció után
8.9 ábra: a 8.8 ábra értékeiből számított peakiness értékek
8.10 ábra: vízszintes projekció 9 szélességű átlagoló ablakkal, négyszeri iteráció után
63
8.11 ábra: a 8.10 ábra értékeiből számított peakiness értékek
8.12 ábra: a 8.11 ábra értékei alapján berajzolt három csúcs helye
64
8.2
A HMM és RNN módszerek egy konkrét összevetése A Berni Egyetem weboldalán publikusan elérhető kézírás felismerő rendszerrel
[13] elvégzett kézírás felismerés, az én kézírásommal tesztelve. Az én írásomat még nem ismerhette a rendszer, ezért nem is sikerült tökéletesen felismernie egyik módszerrel sem. Érdekes azonban megfigyelni, hogy a második tesztminta esetében az RNN-es módszer csak egy szót rontott el, azonban az az egy szó viszont pont jó a HMM-es módszer esetében. Egy RNN-HMM szavazásos hibrid módszer esetében, lehet, hogy tökéletes felismerést kaptunk volna.
8.2.1 Az első tesztminta:
A sor ferdeségének javítása után:
A szöveg dőlésének javítása után:
Az írás régióinak normalizálása után:
A betűk szélességének normalizálása után:
A végső, normalizált kép:
65
A jellemzővektorok kinyerése [13]:
8.13. ábra: a jellemzővektor grafikus ábrázolása [13]. Felismerés eredménye HMM-el: That's He'll evolution I've ever Isn't it . Felismerés eredménye RNN-el: This is a editing recognition bat
66
8.2.2 A második tesztminta Itt megpróbáltam szebben írni:
A sor ferdeségének javítása után:
A szöveg dőlésének javítása után:
Az írás régióinak normalizálása után:
A betűk szélességének normalizálása után:
A végső, normalizált kép:
67
A jellemzővektorok kinyerése: [13]
Felismerés eredménye HMM-el: They're I'd ' tend writing recognition Ted . Felismerés eredménye RNN-el: This is a hand riding recognition test .
68
