Informatika | Tanulmányok, esszék » Optikai karakterfelismerés

1 1 Tartalomjegyzék 1 TARTALOMJEGYZÉK 1 2 RÖVID TARTALMI ÖSSZEFOGLALÓ 4 3 AZ OPTIKAI KARAKTERFELISMERÉS FŐBB PROBLÉMÁI 5 3.1 Általánosan az optikai karakterfelismerésről 3.11 Az OCR néhány definíciója 3.12 Alkalmazási területek 5 7 7 3.2 A dokumentumok fajtái 3.21 Strukturált cikkek 3.22 Nem strukturált cikkek 3.23 Reklámok 3.24 Fedőlapok és címoldalak 3.25 Félig kötetlen struktúrájú dokumentumok 3.26 Postai bélyegek és banki csekkek 3.27 Űrlapok és táblázatszerű dokumentumok 3.28 Térképek 3.29 Műszaki rajzok 3.210 WWW dokumentumok és videó frémek 8 8 8 8 9 9 9 9 10 11 11 3.3 A dokumentumok zajai 3.31 Bevezetés 3.32 A dokumentum zajainak fajtái 3.33 A dokumentum minőségének mérése 12 12 12 14 3.4 Az egyes karakterfelismerési munkafázisok és problémáinak áttekintése 3.41 A dokumentum ferdeségének felderítése és javítása 3.42 Oldalszegmentáció 3.43 Az egyedi karakterek szegmentálása 15 15 16 19 4 4.1

A BINARIZÁCIÓ ELEMZÉSE, A SPECIFIKÁCIÓ KIDOLGOZÁSA A binarizációs folyamat 21 21 4.2 A szűrők elemzése 4.21 A szűrő fogalma és célja 4.22 A szűrők fajtái 4.23 A digitális képfeldolgozásban használatos szűrők rövid áttekintése 21 21 22 23 4.3 A küszöbölés elemzése 4.31 Alapfogalmak 4.32 Egyszerű globális küszöbölés 4.33 Többszörös küszöbölés 4.34 Semi-küszöbölés (fél-küszöbölés) 24 24 24 25 26 2 4.35 4.36 4.37 4.38 4.39 Küszöbölés p-ed résznél Automatikus küszöbölés Optimális küszöb Adaptív küszöbölés A határkarakterisztika használata a hisztogram javítására 26 26 28 28 28 5 A LÉTEZŐ BINARIZÁCIÓS ELJÁRÁSOK ELEMZÉSE A SZAKIRODALOM ALAPJÁN 30 5.1 Bernsen módszere 30 5.2 Chow és Kaneko módszere 30 5.3 Eikvil és mások módszere 30 5.4 Mardia és Hainsworth módszere 30 5.5 Niblack módszere 31 5.6 Taxt és mások módszere 31 5.7 Otsu algoritmus 31 5.8 Yanowitz és

Bruckstein módszere 31 5.9 Parker módszere 32 5.10 White és Rohrer Integrált függvény algoritmusa 32 5.11 Trier és Taxt módszere 32 5.12 Isodata (Yanni) 32 5.13 OGorman alkalmazása 33 5.14 Liu módszere 33 5.15 Yang küszöbölési algoritmusa 33 6 A MEGOLDÁSI MÓDSZER KIVÁLASZTÁSA, A VÁLASZTÁS INDOKLÁSA 34 6.1 A szűrők kiválasztása 34 6.2 A binarizációs módszer kiválasztása 35 7 A RÉSZLETES SPECIFIKÁCIÓ LEÍRÁSA 37 3 8 A TERVEZÉS SORÁN VÉGZETT MUNKAFÁZISOK ÉS TAPASZTALATOK LEÍRÁSA 38 8.1 Hibajavító szűrők tervezése 8.11 Az egyes szűrők egyenkénti vizsgálata Matlab-ban 8.12 A filterek kombinációja statisztikai elemzés alapján 38 38 40 8.2 A binarizációs folyamat tervezése 42 9 A MEGVALÓSÍTÁS LEÍRÁSA 43 9.1 Szükséges paraméterek és változók ismertetése 9.11 Paraméterek 9.12 Fontosabb változók 43 43 43 9.2 Kötegelt feldolgozás és előfilterezés 9.21 Kötegelt feldolgozás

9.22 Előfilterezés 44 44 44 9.3 Quadtree eljárás 44 9.4 Az egyes részek binarizációja 45 9.5 Utófilterezés 47 10 TESZTELÉS 48 11 A MEGVALÓSÍTÁS ELEMZÉSE, ALKALMAZÁSÁNAK ÉS TOVÁBBFEJLESZTÉSI LEHETŐSÉGEINEK SZÁMBAVÉTELE 53 12 54 IRODALOMJEGYZÉK 13 A SZAKDOLGOZAT TARTALMI ÖSSZEFOGLALÓJA MAGYARUL ÉS EGY IDEGEN NYELVEN 58 13.1 Összefoglalás magyarul 58 13.2 Summary 58 4 2 RÖVID TARTALMI ÖSSZEFOGLALÓ Jelen dolgozat arra hivatott, hogy betekintést adjon az optikai karakterfelismerés szerteágazó feldolgozási menetébe, abból a szempontból, hogy a digitalizálás során szinte mindig előfordul valamiféle hibajelenség. Áttekintem az optikai karakterfelismerés történetét, jelentését, alkalmazásait, majd az egyes feldolgozási fázisok részletein keresztül vizsgálódom azok alkalmazási lehetőségeiben és hibái forrásaiban. Ezen felül fontosnak tartottam a dokumentumok és a hibák fajtáinak részletes

ismertetését. A dolgozat második felében az OCR (Optical Character Recognition) egy feldolgozási fázisát kiemeltem a többi közül: a binarizációs folyamatot, amely bináris képek létrehozására hivatott. A szakirodalomban kutatva feltérképeztem a szűrők és a küszöbölések széleskörű választékát, majd ezután a konkrét megvalósítási példákat sorakoztattam fel. A szakirodalom széleskörű vizsgálata a megírt binarizációs program létrejöttéért történt, mivel ezekből, a meglévő megoldásokból felhasználtam egyes algoritmusokat programom egyes részeiben. Olyan program került megírásra, amely bemeneti adatként szürkeárnyalatos képeket kapva binarizációt hajt végre, egyes hibákat kiküszöbölve. Ismertetem e program specifikációját, tervezését, megvalósítását és tervezését, majd a dolgozat legvégén levonom eredményeinek következtetését. 5 3 AZ OPTIKAI KARAKTERFELISMERÉS FŐBB PROBLÉMÁI 3.1 Általánosan

az optikai karakterfelismerésről A látó élőlények a szem által közvetített képet használják alakfelismerésre. A számítástechnika is ezt a sémát követi, amikor valamely képfelvevő eszköz előállította kép tartalmát igyekszik felderíteni, azonosítani. Az OCR a katonai célokra használt alakfelismerésből alakult ki. Nagyban kötődik a papír alapú feldolgozáshoz, mivel az adatokat eredetileg onnan visszük fel. Gyakran használják archívumok digitalizálásához A másik nagy nyitási terület a formanyomtatványok világa. Mindennapjainkban számtalan formanyomtatvány kitöltésével bíbelődünk, de ez mind semmi azon gondokhoz képest, amit az ilyen papír alapú nyomtatványok feldolgozása jelent a kibocsátó számára. Ezt kívánják megkönnyíteni azok a képfeldolgozó szoftverek, amelyek a kitöltetlen táblázatokat beszkennelve, azok struktúráját, szerkezetét felismerve segítenek az elektronikus változatot megalkotni,

biztosítva egyben az elektronikus kitöltés lehetőségét. Új kihívás napjaink robbanásszerűen terjedő állókép-előállító (Still Image Capturing) eszköze, a digitális fényképezőgép. Egy ilyen eszközzel akár az utcán lekapott falragasz szövegét is OCR-ezhetjük, amennyiben a program képes például háromdimenziós ferdeségkorrekcióra, valamint a mai digitális fényképezőgépek készítette alacsonyabb felbontású kép megfelelő feldolgozására. Mindenesetre a jövő OCR programjai bizonyára alapozni fognak a digitális fényképezőgépek nyújtotta üzleti lehetőségekre. Mielőtt a karaktert felismerné egy program, egy sor lépést kell megtennünk, amit összefoglalóan kép-előfeldolgozásnak nevezünk. Ahhoz, hogy az OCR-felismerő algoritmus (vagy még inkább algoritmusok gyűjteménye) jó munkát végezzen, megfelelően pozícionált, csak a felismerendő szöveget tartalmazó tiszta képrészeket kell kapnia. A digitalizált képek

lehetnek színesek, szürkeárnyalatosak és bináris formátumúak. A most már megfelelően pozícionált képről ezután el kell távolítani az oda nem illő, például 6 szennyeződések okozta foltokat, pöttyöket. E feladat különösen kritikus, ha arra gondolunk, hogy az ékezeteket, jeleket kifejezetten káros lenne eltávolítandó objektumoknak tekinteni. A következő lépés az egyes képrészek, vagyis a lapszerkezet azonosítása. Meg kell határozni, mi szöveg és mi nem szöveg (kép, fotó, grafika). Következik annak meghatározása, hogy a felismerőmotor (OCR engine) milyen sorrendben fogja az egyes szövegrészeket, mondjuk, egy szövegszerkesztőnek átadni. A felismerés során nem csak a karakter kódjára vonatkozó információkat kapjuk meg, sokat megtudunk a karakter attribútumáról (dőlt, aláhúzott, kövér, betűméret stb.) is, sőt a pontos elhelyezkedéséről a lapon. Ezek az adatok a kódokkal együtt átadhatók egy intelligens

szövegszerkesztőnek, így a lap teljes formátuma tovább él, azaz minden a helyén van, csak éppen a szöveges képrészek már szövegként szerepelnek. Az OCR-folyamat első lépése a szegmentálás, amely nem más, mint az egyes karaktereket alkotó képpontok csoportosítása, összerendelése. Ilyen a blokkszegmentáció, a szószintű szegmentáció és a karakterszintű szegmentáció. A következő lépés a feature extraction (jellemzők kigyűjtése): numerikus értékek sorozatát (tulajdonságvektor) rendeljük a karakter alakjához. Az ideális tulajdonságvektornak két, egymással konfliktushelyzetben álló követelményt kell teljesítenie. Tudnia kell megkülönböztetni egymástól a hasonló alakú karaktereket (például 5 és S, C és G), miközben rugalmasan kell tudnia kezelni az azonos karakterek különböző variációit (például különböző fontoknál). Végül is ezeket a követelményeket nem lehet mindig maradéktalanul teljesíteni. Vannak

karakterek, amelyek csak néhány képpontban különböznek egymástól. Az ilyenfajta eseteknél karakterspecifikus szabályokat kell alkalmazni. A szegmentálási problémák, valamint a hasonlóságokból adódó gondok a tipikus forrásai az OCR-hibáknak. Az egyes OCR-megoldások, nem tudván a hagyományos képfeldolgozó eszközökkel tovább növelni a felismerés pontosságát, kivétel nélkül szótárak és spellchecking (helyesírás-ellenőrző) modulok támogatását veszik igénybe a felismerési folyamatban. A legkevesebb, hogy a helyesírás-ellenőrző rámutat a nem megfelelő szavakra, azonban az OCR-szoftverek ennél tovább mennek, a fel nem ismert karaktereket a legvalószínűbb megoldást jelentő szóval helyettesítik. Lehetnek viszont szép számmal 7 szavak, amelyeket a szótárak, illetve helyesírás-ellenőrzők nem tartalmaznak, és persze elég nehéz azt automatikusan eldönteni, hogy vajon ezek korrekcióra szorulnak-e. A másik probléma,

hogy az OCR-hibák tipikusan csoportokban jelentkeznek, gyakorta a szó betűszáma is más, mint az eredetiben, így különösen nehéz automatikus becsléseket tenni. Tekintettel az ilyen típusú gondokra, csak az vezethet megfelelő eredményre, amikor szoros kapcsolat van a szó képe és a nyelvi információ között. Noha az OCR-programok mind pontosabbak, el kell fogadnunk, hogy akadnak hibák. Attól függően, hogy az egyes algoritmusokat hogyan írták meg, más-más OCR-ek más-más típusú hibákat vétenek és azokat következetesen. Ha egy OCR program téveszt egy karaktert, akkor azt kétféleképpen teheti meg: egy adott betűt más betűvel helyettesít, vagy nem tudja megmondani, hogy milyen karakter. Napjainkra az OCR meglehetősen kiforrott technológia lett, s könnyen hozzáférhető mindenki számára. A szkenner mindennapi eszközzé vált, és ma már a legolcsóbb szkennerhez is adnak valamilyen OCR-t, amely a legegyszerűbb igényeket képes is

kielégíteni. [1] 3.11 Az OCR néhány definíciója Az OCR (Optical Charactor Recognition) egy kép szavainak olyan szerkeszthető dokumentummá konvertálásának folyamata, amelyet aztán a szövegszerkesztők vagy az asztali kiadványszerkesztő programok felhasználhatnak. [2] Az a folyamat, amelynek során a számítógép a beszkennelt szöveg karaktereit a saját tárolt karaktereivel való összehasonlítás nyomán azonosítja, és ezek alapján digitális szövegfájlt hoz létre. [3] 3.12 Alkalmazási területek A legfőbb cél az OCR-nél, hogy automatikusan felismerjük a szöveget és képelemeket a digitalizált dokumentumból minél kisebb hibával. A mai kutatási területek a következők: táblázatos szövegek értelmezése, szövegek és képek elkülönítése, 8 oszlopdiagramok értelmezése, elektronikus jelek szimbólummá alakítása, szimbólumok és szövegek kiolvasása térképből, szimbólumok és kapcsolataik mérnöki rajzokon,

irányítószám borítékról való leolvasása, matematikai szimbólumok értelmezése más szövegből, duplán szereplő dokumentumok felderítése képi adatbázisokból és egyéb alkalmazások.[4] Ezeken felül már nagyon hosszú ideje használják a könyvek, dokumentumok digitalizálására, amely rengeteg emberi munkát képes megtakarítani. 3.2 A dokumentumok fajtái 3.21 Strukturált cikkek Ezek a dokumentumok számos szegmenstípust tartalmazhatnak (sokszínű fontkészletet, betűméretet, különböző grafikai elemet és lehetnek binárisak, szürkeárnyalatosak és színesek is). Általában az egyes szegmensek jól elkülönülnek egymástól, habár gyakran előfordul, hogy a köztük lévő lyukak elég keskenyek. Néhány esetben a szövegek be vannak építve egyes grafikai elemek közé; a háttérszínhez képest lehetnek sötétebbek (normál nyomtatás) vagy világosabbak (inverz nyomtatás). 3.22 Nem strukturált cikkek Ebbe a fajtába azok a

dokumentumok tartoznak bele, amelyeket nem lehet más típusba sorolni, vagyis a tervezése egyedi. 3.23 Reklámok Általában magazinokban, újságokban fordul elő, de gyakran találkozhatunk vele az Interneten is elektronikus formában. A struktúrája sokkal szabadabb, mint az újságoknak A ferdeség sokszoros az előforduló szövegek és képek miatt. 9 3.24 Fedőlapok és címoldalak Ezekben a dokumentumokban szereplő képek gyakran színesek és a szövegek beágyazottak az egyes képekbe, valamint méretük és fontkészletük elég nehezen meghatározható. Ezekben az esetekben a karakterfelismerés könnyebb, ha a nem-textuális tulajdonságokat gyűjtjük ki, mint az éleket, a textúrát és a színeket. 3.25 Félig kötetlen struktúrájú dokumentumok Megtalálható benne a strukturáltság - a felhasználónak külön el kell helyezni plusz információt, de ezen információk száma nincs meghatározva. 3.26 Postai bélyegek és banki csekkek Ezek a tipikus

példák félig kötetlen struktúrájú dokumentumok, mivel előre meg van határozva a cím, a pénz értékének a helye, de mégis előfordulnak opcionális mezők. Ezek a dokumentumok lehetnek binárisak, szürkeárnyalatosak és színesek főként bonyolult textúrával a háttérben. Ennél a típusnál a következők okoznak nagy problémát: o az összetett háttér nehézzé teszi a binarizációt vagy a szegmentálást o a különböző gépi nyomtatások és a kézi írások érintik, vagy átszelik a bázisvonalat o megvilágítási gondok o tetszés szerinti írásirány mozgó platformon o a feldolgozási idő megszabott 3.27 Űrlapok és táblázatszerű dokumentumok A kérdőívekhez hasonlóan ezek is mezőkből és cellákból állnak, ahova kézzel vagy géppel kell írni. Az eredeti dokumentumok nagy többségében bináris képek formájában jelennek meg, habár léteznek színes formanyomtatványok is. Mivel a háttér szinte mindig homogén, ezért viszonylag

könnyű a szegmentáció. A szövegeken kívül a számlák tartalmazhatnak kisméretű képeket is, például logókat. Az űrlapok és a táblázatos 10 dokumentumokat tehát félig-strukturált dokumentumoknak foghatjuk fel melyekben elválasztó elemek szerepelnek az egyes szövegek között. A legfőbb feladat e típusoknál, hogy a szövegeket elválasztó elemeket eltávolítsuk. Az űrlapoknál két lehetőség áll fent. Az egyik, hogy ismerjük az űrlap típusát, és ha már beazonosítottuk, akkor meghatározott az elválasztó elemek koordinátái. A másik típusú, hogy nem tudjuk milyen típusú adatlappal állunk szemben. Ennek a feldolgozása sokkal költségesebb és kevésbé eredményesebb az előzőnél. A költség növekszik, ha a szöveges adatok kívülre esnek az elválasztó elemeken, mivel így nehéz behatárolni a szöveget. A képekkel végzett transzformációk ugyancsak nehezítik a feldolgozást. További zajok forrásai, ha egy dokumentumot

átfaxolunk, mivel gyakran gyenge minőségű; a bélyegzők is hasonló gondokat okoznak. 3.28 Térképek A térképeknél elvárt, hogy szürkeárnyalatos, vagy színes legyen a részletek megjelenítése érdekében. A színes térképek több különböző színes rétegből állnak, amelynél minden réteg valamilyen információt hordoz magában. A kisméretű és ritkán előforduló szöveges elemek szabálytalanul be vannak ágyazva a grafikai elemek közé. Számos térképfajta létezik (kataszteri, topográfiai, stb.), de általában a feldolgozást három részre oszthatjuk: szöveg/grafika elválasztása, karakterfelismerés és grafikai vektorizálás. A színes képeknél a színek szeparációja már a szkenneléskor történik külön erre a célra alkalmazott szkennerrel. A térképek széleskörű változatai miatt egy alkalmazás általában csak egy típus feldolgozására képes. A fő probléma itt is az, hogy a grafikai elemeket érintik, vagy átszelik az

egyes karakterek, valamint nagyon különböző mértékű a távolság a szomszédos karakterek között és néhány grafikai elem hasonlít egyes karakterekre. 11 3.29 Műszaki rajzok Itt is hasonló problémákkal kell megküzdeni, mint a térképeknél. A különbség az, hogy általában bináris vagy szürkeárnyalatos formátumban vannak, kevesebb szöveg és keskenyebb geometriai alakok találhatók. 3.210 WWW dokumentumok és videó frémek Ez a dokumentumok egy új osztálya, mivel eredetileg elektronikus formában vannak, nem kell alkalmazni szkennelést, így a feldolgozása nagyban különbözik az előzőekétől. Tipikusan színes formában fordulnak elő, viszonylag kis felbontással a gyors feldolgozás érdekében. A fő elemei szövegek és képek tetszőleges elrendezésben A WWW lapon a szövegek lehetnek karakter és kép formában. A videó frémeknél a komplex képek a jellemzőek. A karakterek sokszor 3-szor, 4-szer kisebbek 200-300 dpi-s felbontásnál,

ami más típusú dokumentumoknál megszokott, ezért a detektálást és a felismerést nehézzé teszi. Nyugodtan besorolhatjuk ezeket a nem-strukturált dokumentumfajták közé, mivel a kinézetük előre nem definiált szabályokon épülnek, valamint a videófrémeknél legtöbbször lehetetlen bármilyen szabályosságot felállítani. Itt a legfőbb teendő az, hogy a képekbe beágyazott szövegeket kiemeljük. A legfőbb problémák, amelyek a felismerést akadályozzák a következők: a) A szöveg és a háttér színe túl közel van egymáshoz, ami a kis felbontásnak köszönhető, vagy szöveg kontrasztja túl kicsi a háttérhez képest (például a szöveg egy bonyolult textúrájú háttérbe van beültetve). b) A szövegösszetevők egy hajlított vonalhoz igazodik, vagy a legrosszabb esetben szabálytalan hullámban igazodnak. c) A szövegkomponensek eltérő színűek lehetnek és különböző alrészekre lehetnek osztva (nem a zaj, hanem a dizájn miatt) d) A

videónál fellépő mozgás. 12 3.3 A dokumentumok zajai 3.31 Bevezetés A dokumentum zajainak vizsgálódásánál először is fel kell derítenünk a nyomtatásból, fotómásolásból, faxolásból és szkennelésből származó hibákat. Továbbá az OCR-es feldolgozásában ismert hiba, hogy egy gyenge minőségű képet próbálnak feldolgozni. Az OCR számításának eredményessége nagyban függ a tanítóminta nagyságától és minőségétől, valamint, hogy milyen feature-okat és klasszifikáló algoritmusokat választunk. [5] 3.32 A dokumentum zajainak fajtái A zaj értelmezése: Minden olyan hiba, amely különbözik az ideális dokumentum állapotától, például a kis felbontás miatti eldurvulás, a tinta kifogyása okozta elhalványodások és foltok, geometriai deformációk, stb. Ha felvennénk egy olyan alapmodellt, amelyben leírnánk, hogy milyen karakterek és grafikus elemek, hogyan néznek ki, akkor beszélhetnénk egy ideális oldalképről.

Mióta a szakirodalom rámutatott a szövegdegradációkra, azóta főként csak a nagy kontrasztú szövegeket (monokrómikus, fekete-fehér szövegek) végtelen mintavételezéssel tekinti ideálisnak. Tekintsünk néhány példát, hogy miből keletkezhetnek a képek hibája: o Egy fizikai úton történő cselekvés útján (pl. a szkennerbe ferdén helyezi be valaki a papírt) o A képek megjelenése több mint egy nyomtatási fázis során készül el o Az előállítandó kép fizikai megjelenése nem kontrollálható, így a modellezés véletlen események során statisztikai úton áll elő A fizikum lehet globális és lokális természetű is. Az egész lap torzulhat geometriailag, mint például a 0 foknál nagyobb oldalferdeség. Egy egyedülálló karakter viszont lehet zajos a tintapatron kifogyása miatt. Továbbá a pixelszinten is előfordulhatnak zajok, például termálszenzor zaj miatt. Eszerint a zajok lehetnek oldal-, szimbólum- és 13 pixelszintűek és

az más olyan szinten, amelyet az oldal struktúrája tartalmaz (szövegblokkok, szövegsorok). De nem minden zajt lehet elvonatkoztatni csupán a szimbolikus elrendezésre: például, ha a tinta kifogyása miatt az oldal nem egységes intenzitással lesz nyomtatva, akkor az nagyobb szintű, mint a pixel, de kisebb a szimbólum szintjénél. A hibaforrások ennél fogva igen széles skálában jelennek meg és legtöbbször egy logikai szegmenshez lehet kötni. Egy dokumentum feldolgozásnál sok hibajavítás történik, az esetek többségében ezek: o Fókuszálás o Binarizáció (pl. fix és adaptív küszöbölés) o Papírpozízionálás (pl. ferdeségkorrekció) o Szakadások és összetapadások javítása o Alacsony nyomtatási kontraszt o Nem egységes megvilágítás o Pixelérzékelés eltérősége o A szedés tökéletlensége o Kopás és papírgyűrődés miatti halvány körvonal o A nyomtatópatron miatti szétszóródás o Vibráció a nem egységes

berendezésmozgás miatt o Additív vagy multiplikatív elektromos komponens miatti zaj o Szabálytalan pixel-elhelyezkedés o Véges számú mintavételezés a bemeneti dokumentumok esetén o Egyenetlen papírfelszín o Nem egyenes vonalú kameraállás (pl. perspektíva torzió) 14 Persze meg kell jegyeznünk, hogy ez a lista nem teljes. [5] 3.33 A dokumentum minőségének mérése Ebben a fejezetben csak a kétcsatornás monokróm képekről lesz szó a színes képek elhanyagolásával. A képek hibáit ritkán tárgyalják meg kvantitatív módon Sok esetben használják a célkép beszkennelése során felállítható karakterisztikákat. Továbbá széles körben használnak denzitométert (feketedésmérőt) a pontvisszaverődés számítására. Speciális eszközöket fel tudnak használni arra, hogy a nyomtatott lap kontrasztarányát mérni tudják. Kvantitatívan kifejezve: (Rω - RB) / Rω, ahol Rω = egy nagyobb fehér pont visszaverődési erőssége és RB = egy

kisebb fekete pont visszaverődési erőssége. Az alapértelmezett binarizációs küszöbérték a dokumentumszkennereknél a kontrasztarány segítségével van definiálva, amelynek tipikus értéke [0.5 07] A kontrasztarány mérése lehetőséget nyújt, hogy megkülönböztessük a karakterek, üres helyek és tintapatron által okozott foltok pixeleit. Egy másik megközelítése a dokumentum minőség mérésére [7], hogy egy PC-ből, hozzátartozó szoftverből és egy speciálisan kalibrált monokróm szürkecsatornás dokumentumszkennerrel kontrasztot, pontvisszaverődést a és automatikusan kiszámítja struktúratulajdonságokat, a ilyen nyomtatási például a szövegmezőből kilógó részek felderítése. Nagyon gyakori jelenség a dokumentum minőségének qvantitatív meghatározására törekvő alkalmazások fejlesztésekor, hogy a nehézségek miatt félbehagyják a projektet. [5] 15 3.4 Az egyes karakterfelismerési munkafázisok és

problémáinak áttekintése 3.41 A dokumentum ferdeségének felderítése és javítása Dokumentumok szkennelésekor a bevitt lapok sokszor ferdén kerülnek bevitelre. Az ilyen eseteket kezdetben emberek felügyelték és ferdeség esetén a szkennelést megismételték. Ma már számos algoritmus létezik az oldalferdeség felkutatására és javítására. A kezdeti törekvések az oldalnézetet és az oldalferdeséget kívánták felderíteni. Egy korai példa szerint Akiyama és Hagita olyan technikát használt, ami a vízszintes és függőleges projection profiles-t használta bináris képekkel dolgozva. Az eljárás főleg a globális jellemzőket részesítette előnyben, ami grafikus elemeknél működött hatékonyabban. A globális megközelítések legfőbb hibaforrása a nem-textuális adatok előfordulása, amik mindig hatással vannak a projection profile-ra. Erről az esetről először a következő emberek számoltak be: Hinds, Fisher és DAmato. Olyan

algoritmust terveztek, amely meghatározza a dokumentumok orientáltságát - a rövid futásidővel meghatározható vízszintes és függőleges színhisztogram alapján. Számos algoritmus létezik ennek a problémának a részleges megoldására. A legtöbb lassúsága miatt kevésbé használható. Talán az egyik legjobb a Hinds, Fisher és DAmato által javasolt, Hough transzformációt használó algoritmus. [7] Egy javasolt oldalferdeség és oldalorientáltsági módszeren keresztül bemutatásra kerül, hogy miként zajlik ennek az eljárásnak menete: Elsőként a karakter külső élén meglévő zajokat könnyedén el tudjuk távolítani a run-length simító eljárással – ami eredetileg a dokumentumok blokkszintű szegmentálására lett kifejlesztve. Legyenek a fekete pixelek 1-gyel reprezentálva, a fehér háttérszín pedig 0-val, a vízszintes run-length simító eljárás elsimítja a vízszintes fekete meneteket, ha az egymás mellett lévő fehér

pixelek száma kisebb, mint az előre megadott T küszöbérték. 16 A folyamat következő lépéseként ki kell emelni a bázisvonalakat és redukálni az adatmennyiséget, amelyek a Hough transzformációt költségessé teszik. Először is függőleges irány mentén haladjunk végig az egyes képpontokon, majd megkeressük az összes fekete-fehér átmenetet, ezután lecseréljük azon fekete pixeleket fehérre, amelyek a fekete-fehér átmenetet képezik. Eredményül azt kapjuk, hogy a soroknál szembetűnőbb lesz a bázisvonal képe. Az eredeti Hough transzformációnál szükséges számításba venni számos különböző paraméterértéket minden lehetséges vonalra, amit a fekete pixelekből nyerhetünk az eredeti képen. (egy egyenes meghatározásához két paraméter szükséges a polárkoordinátás egyenlet szerint: “ρ – x cos θ + y sin θ”) Ez a transzformáció sok adat feldolgozását követeli meg, ami függ a fekete pixelek és a paramétertér

dimenzióinak számától. Eszerint érdemes polárkoordinátákkal dolgozni Ezenfelül, mivel két pont egyértelműen meghatározza a rajtuk áthaladó egyenest nem kell meghatározni a végtelen számú egy ponton átmenő egyeneseket. Csak összesíteni kell a lehetséges θ paraméterek segítségével a párhuzamos egyeneseket a ρ paraméter figyelmen kívül hagyásával egydimenziós paramétertérben. Végezetül a θ értéket megkapva a legnagyobb értéket kiválasztásával megkapjuk a ferdeség szögét.[8] Zaj: Az állónézetben sokkal jobban megoldott a probléma, mint fekvő helyzetben. Alkalmazhatóság: A jelenlegi kereskedelmi forgalomban lévő ScanFixTM szoftver is ezen eljárás segítségével fedezi fel és javítja az oldalferdeséget. Az automatikus dokumentum-feldolgozásnál és az optikai szkennelésnél használják. [7] 3.42 Oldalszegmentáció Az az eljárás, amely során jelentésben elkülönülő egységeket szeparálunk el egymástól,

amelyeket különböző típusú objektumokként foghatunk fel (pl. képek, táblázatok, stb.) A karakterfelismerés és egyéb objektum-felismerés első lépése, hogy az oldalt szegmentáljuk, viszont ezt nem lehet megoldani egy egyszerű küszöbölő algoritmussal. A korai oldalszegmentálási és klasszifikálási megközelítéseknél szükség volt 17 megadni, hogy a karakterek milyen méretűek. Ezen felül több - felhasználó által kötelezően megadásra kerülő segédadattal is dolgoztak Az oldalszegmentációnak két fajtája van: a fizikai és a logikai szegmentáció. A fizikai oldalszegmentáció felosztja a lapot homogén zónákra. Mindegyik zónában egyetlen típusú objektum található (szöveg, táblázat, ábra, kép, stb.) A logikai szegmentációnál viszont összerendelést végez az egyes fizikai zónák között az olvasási egymásutániság szerint. Ezáltal egy hierarchikus dokumentumstruktúrát képeznek az egyes részekből és

alrészekből. Ezen belül tovább lehet csoportosítani a két fő részt textúra alapú és nem-textúra alapú alcsoportokra, amelyek lehetnek top-down (modellvezérelt), bottom-up (adatvezérelt), hibrid és egyéb végrehajtási típusúak. A bottom-up metódusban kis blokkokra osztjuk a dokumentumot, amelyek az egyes karaktereket tartalmazzák, majd később egyesítjük nagyobb blokkokra – szavakká és sorokká. Az egyesítés folyamataként foltokat, legközelebbi szomszédokat kereshetünk; a fő egyesítő metódusok a Voronoi diagramok. A feldolgozási idő nagyon széles spektrumú, függ a metódusoktól. Ezen metódusok gyakran érzéketlenek a ferdeségre (néha még a többszörös ferdeségre is) és a rendezetlen struktúrára. A feldolgozási időt nagyban lecsökkenthetjük, ha egy előre definiált négyzetes blokkot használunk szűrőnek, amely egyszerre több pixelt vizsgál egy időben. Számos megközelítés alapszik a bináris képeknél a

háttér elemzésén. A legeredményesebb eljárások úgynevezett fehér mozaikokat alkalmaz. Itt elsőként létrehozza a téglalapok olyan hálózatát, ahol minden téglalap a legnagyobb egybefüggő fehér tartományt alkot, majd kiszámolja az ezen hálózat által meghatározott régiót. Az eljárás egy rugalmas adatábrázolást eredményez és nem vár el ferdeségkorrekciót, valamint gyors, mivel a pixelalapú feldolgozás csak egyszer történik. A képek zajainak javítására az RLS algoritmust használják. A bonyolultabb színű dokumentumoknál a legtöbb eljárás azt használja ki, hogy a karakterek viszonylag egyszínűk, egy bázisvonalhoz igazodnak, és színük elüt a háttértől. 18 A top-down módszerben ennek az ellenkezője történik, miszerint nagyobb egységekre osztjuk szét a dokumentumokra (high-level), majd ezután kisebbekre (lowerlevel). A legtöbb top-down technika az RLS (Run Length Smoothing) algoritmust használja Érdemes itt egy kis

figyelmet szentelni a már sokszor emlegetett RLS algoritmus működésére: az algoritmus felszegmentálja a szöveget úgy, hogy a karaktereket szavakká olvasztja össze az egyes objektumok távolságának küszöbölése segítségével, vagyis ha két objektum egy megadott értéknél távolabb van egymástól, akkor azokat elszeparálja egymástól. Legyenek a karakterek fekete pixelek és az üres helyek fehér pixelek; ha a fehér pixelek száma elég kevés két karakter között, akkor egy objektumba sorolja a karaktereket, egyébként pedig különbözőbe. A hibrid módszer ötvözi a bottom-up és top-down módszer előnyeit, de találkozhatunk olyan egyéb módszerekkel is, amelyek teljesen eltérő módon dolgoznak. Két főbb konkrét megközelítést emelek ki a többi sorai közül, amelyeket a gyakorlatban igen közkedvelten használnak: az egyik a simításon alapuló kétlépéses algorimus (two-step block segmentation algorithm) és a másik a szabályalapú

algoritmus (rule-based algorithm) fajta. Zaj: Egy blokk elkülönítési kritériumát nem lehet egyértelműen meghatározni, mert az függ a dokumentum analizálásától és annak alkalmazásától. A képeket szürkeárnyalatosnak kezelik, amelyből bináris képet képeznek. Fellép a klasszikus probléma, hogy a küszöbölés mely árnyalati értéknél történjen. Ez az eljárás érzékeny a háttérzajokra. Gyakorta előforduló hibák: o A leggyakoribb hiba az, hogy túl nagy területeket vesz egy szegmensbe, amely különböző típusú elemeket tartalmaz. o Az egyes blokkok túl nagy közelsége esetén összemosódhatnak a blokkok. Ez az elsimítás küszöbértékének változtatásával javítható. 19 Alkalmazhatóság: Egy analóg dokumentum bevitelekor ez az egyik első lépés, amit az előfeldolgozás során megtesznek, hogy később az egyes karaktereket fel lehessen ismerni. Tovább használják a szegmensek klasszifikációjánál, ahol

megállapítják, hogy az egyes szegmensek milyen típusú objektumok. [9], [10], [11], [12], [13], [14] 3.43 Az egyedi karakterek szegmentálása A jellemzők kigyűjtése (feature extraction) elvégzésekor numerikus értékek sorozatát (tulajdonságvektor) rendeljük a karakterek alakjaihoz. A legegyszerűbb eset, amikor egyesek és nullák kétdimenziós elrendezésével képezzük le a karakter képpontok geometriai elhelyezkedését. Ez, amit kezdetben az OCR pionírok is használtak, vagyis a mintaillesztő (matrix matching) algoritmus. Noha egyes esetekben ma is nagyon hasznos lehet ez a megközelítés, viszont a ma használt algoritmusok méret- és fontfüggetlen tulajdonságokat kezelnek: például a görbületek, hurkok száma, jellemző pontok helyzete, valamint más topológiai és statisztikai jellemzőket. Az ideális tulajdonságvektornak két - egymással konfliktushelyzetben álló követelményt kell teljesítenie. Tudnia kell megkülönböztetni egymástól a

hasonló alakú karaktereket (például 5 és S, C és G), miközben rugalmasan kell tudnia kezelni az azonos karakterek különböző variációit (például különböző fontoknál). Ezeket a követelményeket nem lehet mindig maradéktalanul teljesíteni, mivel ezek sokszor egymásnak ellentmondó feltételek. Vannak karakterek, amelyek csak néhány képpontban különböznek egymástól, az ilyenfajta eseteknél karakterspecifikus szabályokat kell alkalmazni. A szegmentálási problémák, valamint a hasonlóságokból adódó gondok a tipikus forrásai az OCR-hibáknak. [1] Feature kigyűjtés és kiválasztás (Feature extraction and selection) Olyan tulajdonságok kigyűjtését jelenti, amelyek egy karakterre jellemző képet ad és a későbbiek folyamán segít az objektum azonosításánál. o Fourier leíró (Fourier descriptors) 20 o Geometriai súlyállandó (Geometric moment invariant) o Zernike súlyozás (Zernike moments) o Wavelet leíró (Wavelet descriptor)

o Gradiens-alapú feature o Projection hisztogram o Gradiens struktúrájú konkávitás o Zónázás (Zoning) fix és változó felosztás Ezeknél a feature-öknél jellemzően meghatározunk egy felbontást. A zónázásnál például azt jelenti, hogy hány téglalapra osztjuk fel a képet. Általában nem kizárólag egy feature vektort használunk, hanem azok valamely kombinációját. 21 4 A BINARIZÁCIÓ ELEMZÉSE, A SPECIFIKÁCIÓ KIDOLGOZÁSA 4.1 A binarizációs folyamat A binarizáció azt jelenti, hogy színes, szürkeárnyalatos vagy bármely nem bináris képből bináris képet készítünk. Ezt úgy teszi meg, hogy az egyes pixelekhez az eredeti képen 0-át, vagy 1-et rendel különböző módszerek segítségével. Általában a feldolgozási folyamat binarizáció során előzetes filterekkel kezdődik, amelyek a dokumentumon lévő hibákat lehetőség szerint eltünteti. Ezután valamilyen küszöbérték szerint minden pixelhez hozzárendel 0-át, vagy

1-et. Végül, utófeldolgozásként utószűrőket használhatunk, valamint eltüntethetjük az árnyobjektumokat, amelyek nem képeznek karaktert. 4.2 A szűrők elemzése 4.21 A szűrő fogalma és célja Általában a bevitt képeknek van valamilyen hibájuk, például nem elég éles, egyes foltok szakadások léphetnek fel. Ezért szükséges a feldolgozás folyamán szűrőket alkalmazni, hogy ezeket a hibákat el tudjuk távolítani. Egy filter alkalmazásakor, egy maszkot, a képen keresztül pixelenként vonszoljuk, és a pontokra kiszámolja az ablak szerint az új pixelértéket. Léteznek olyan szűrők, amelyeket jó hatásfokkal lehet használni a binarizációs feldolgozáshoz. A szűrőktől a következőket várjuk el. Először is egy filternek meg kell szüntetni minden egyedülálló zajt, amelyek a küszöbölési procedúrát zavarják. A pixelek egy objektumba való tartozását könnyebb eldönteni, ha azonos intenzitásúak. Erre alkalmaznak Gauss

filtereket, vagy a fényességet simítják el, amennyire csak lehet. Fontos az is, hogy az objektumok élei és sarkai megmaradjanak, mert fontos az egyes mintafelismeréseknél. 22 4.22 A szűrők fajtái Két nagy csoportba oszthatjuk a szűrőket: Lineáris szűrők: A lineáris szűrési eljárásokat tulajdonképpen azért nevezzük lineárisnak, mivel a térben végrehajtott konvolúció a frekvenciatartományban és a műveletben résztvevő függvények közötti művelet a Furier transzformációról szorzásra egyszerűsödik. Nem-lineáris szűrők: A gyakorlatban igen eredményesen alkalmaznak olyan szűrő eljárásokat, melyek nem tekinthetők konvolúciónak, s ezért nem vihetők át lineáris műveletek formájában a frekvenciatartományba. A lineáris szűrő lehet konvolúciós és korrelációs. Az egyik a másiknak a 180 fokkal elforgatott mása. Adaptív filterek: a cella új értékét nem egy lineáris kifejezéssel számítjuk, hanem különféle

algoritmusokkal. Ilyen filterek a minimum, maximum, Medián és az él megőrző szűrők. A minimum és maximum filter az ablakon belüli pixelek legkisebb, illetve legnagyobb értékét adja vissza. A Medián filter az ablakon belüli pixelek értékeit sorba rendezi és a sor középső elemével tér vissza. Az él megőrző szűrő esetében a pixeleket 9 kategóriába soroljuk. A szűrési eljárások két fő csoportra oszthatók. Az első csoport simítja a képeket, csökkenti a kontrasztot, a második csoport éppen ellenkezőleg a kontraszt kiemelésére szolgál. Problémaként merülhet fel, hogy miként értelmezzük ezt és a további eljárásokat a szélső pixelek esetében. Legegyszerűbb az az eljárás, amikor a szűrő dimenziójának megfelelően csökkentik a szűrt kép dimenzióját: 3x3-as szűrő esetén az első és utolsó sorral valamint oszloppal, 5x5-ös szűrő esetén két-két sorral és oszloppal stb. Gyakran alkalmazzák azt a módszert, amikor az

érintett szélső pixelek szürkeségi értékeit változatlanul hagyják. 23 A nagyméretű szűrőmátrixok alkalmazása a futásidő szempontjából nem előnyös, ezért a szélesebb tartományra eső súlyozás szüksége esetén inkább kisebb szűrőmátrixszal végeznek többszöri szűrést. Számos szűrőt ismerünk, ezek közül a legtöbbet használatosak a Gauss és a Medián szűrők. Az előbbi képes a Gauss-féle zaj megszüntetésére, de kissé elmossa az éleket Az utóbbi az impulzív zajok eltüntetésére alkalmas a legjobban, továbbá az éleket rojtosan hagyja, és nem mossa el az egy régióban lévő pixeleket. 4.23 A digitális képfeldolgozásban használatos szűrők rövid áttekintése o Medián szűrő: az alkalmazott ablakkal (3x3, 5x5) egymás után lefedjük az eredeti kép valamennyi pixelét. Minden szűrőhelyzetben a lefedett képpixelek szürkeségi értékeit sorbaállítjuk és a helyzet középső pixelének szűrt értékét

egyenlővé tesszük a nagyság szerint középső szürkeségi értékkel. Ha valamely szűrő helyzetben a különböző szürkeségi értékek száma páros, úgy a középre szimmetrikus két szomszédos szürkeségi érték középértékét tekintik Mediánnak. A módszer alkalmazása kis ablakok esetén nem befolyásolja a jelentősebb élek (vonalak) leképződését a szűrt képen. o Minimum filter: Az n*n-es mátrixban a vizsgált pont helyére a legkisebb értékkel rendelkező pixelértéket írja be. Eróziós műveletet hajt végre o Maximum filter: Az n*n-es mátrixban a vizsgált pont helyére a legnagyobb értékkel rendelkező pixelértéket írja be. Dilatációs műveletet hajt végre o Unsharp maszk: A képet élesíti, egy elkent, nagy kontrasztú képet hoz létre. o Medián filter: A keretben lévő pixeleket sorba rendezi nagyság szerint, majd a vizsgált pixel helyére a sor közepén lévő értéket helyettesíti be (ha páros számú a sor, akkor a két

középső pixelérték számtani közepét). Képes zajok eltüntetésére a típusuktól függően. Egyik használata, hogy elkenje a durván szkennelt képeket, amelyek szemcsézett megjelenésűek. A zajok eltüntetése ebben az esetben a képeket sokkal lágyabbá teszi. 24 o Gauss filter: Elkeni a képet, megszünteti a zajokat és eltünteti a részleteket is. Éldetektálás előtt gyakran használják. Az élek és a kép elmosódik használatakor o Világosság és kontraszt filterek: A világosságot, valamint a kontrasztot manipuláló filterek. [15], [16], [17], [18], [19] 4.3 A küszöbölés elemzése 4.31 Alapfogalmak Legyenek a kép egyes pontjai f(x,y) függvénnyel reprezentálva és legyen T egy küszöbérték. Ha f(x,y) > T, akkor f(x,y) objektumpont, egyéb esetben pedig háttér A küszöbölés lehet egyszintű és többszintű is, ahol több objektumot különíthetünk el a háttértől. Ezek szerint a T-t felfoghatjuk egy ilyen függvényként: T =

T[x, y, p(x,y), f(x,y)], ahol p(x,y) jelenti az adott pixel egy lokális tulajdonságát. A küszöbölés során előállítunk egy g(x,y) függvényt, ahol, ha 1 az értéke akkor, ha f(x,y) > T és 0 egyébként. Ebben az esetben, ha 1, akkor objektumot, ha 0 hátteret jelöl. Ezekből kiindulva, ha a T érték csak f(x,y)-tól függ, akkor nevezzük globális küszöbnek, viszont, ha függ p(x,y)-tól, vagyis a lokális értékektől, akkor a T-t lokális küszöbnek nevezzük. Továbbá, ha T függ a térbeli koordinátáktól – x-től és y-tól -, akkor dinamikus, vagy adaptív küszöbölésről beszélhetünk. 4.32 Egyszerű globális küszöbölés A legegyszerűbb küszöbölési forma, ha a szürkeárnyalati hisztogramból kiszámolunk egy T küszöbértéket és ezt alkalmazzuk minden egyes pixelre aszerint, hogy magasabb, vagy alacsonyabb az értéke. Ennek a hatékonysága attól függ, hogy milyen minőségben határoztuk meg a T értéket. Ez az eljárás azokon

a képeken működik jól, ahol a háttér és az előtér kontrasztban vannak egymással homogén módon. 25 Sáv küszöbölés Az egyszerű küszöbölés egy fajtája; területekre osztja a képet, oly módon, hogy egy intervallumon belül eső szürkeségi értékekkel rendelkező pontokat egy csoportba rendez, az összes többit egy másikba. Ez az intervallum lehet egy D halmaz, amely a szürkeségi értékek halmaza. 4.1 ábra: Sávküszöbölés Ez a módszer jól használható határvonal detektálásra. Ha a D halmazt úgy határozzuk meg, hogy azokat a szürkeségi értékeket tartalmazza, amelyek a tárgy határvonalát alkotják. 4.33 Többszörös küszöbölés Ez a küszöbölés jól használható, ha a képen sok olyan objektum van, amit el akarunk különíteni egymástól. A szürkeségi értékek egy jól behatárolt halmaza alkotja majd a képet. 4.2 ábra: Többszörös küszöbölés 26 ahol Di a szürkeségi értékek részhalmaza 4.34

Semi-küszöbölés (fél-küszöbölés) Ennél a módszernél is a hátteret választjuk el a tárgytól, azzal a különbséggel, hogy itt a kiemelt tárgy pontjainak szürkeségi értékei megmaradnak. 4.3 ábra: Semi küszöbölés 4.35 Küszöbölés p-ed résznél A háttér- és az objektum pontok arányát ismerjük, mint például a nyomtatott szövegnél a karakterek 1/p részét alkotják a nyomtatott oldalnak. Felhasználva ezt az információt a nyomtatott felület és a karakterek arányáról, könnyedén megválaszthatjuk a T küszöbértéket (alapul véve a kép hisztogramját). Bonyolultabb módszerek a küszöbérték meghatározására a hisztogram alakját elemzik. 4.36 Automatikus küszöbölés Ha a kép hisztogramja evvel a tulajdonsággal rendelkezik, akkor a küszöbértéket meghatározhatjuk a hisztogram két maximuma közötti minimum helyen. Evvel a módszerrel a legkisebb a szegmentálási hiba. 27 4.4 ábra: Automatikus küszöbölés Többalakú

(multimodal) hisztogram: nem csak két maximum érték van a hisztogramon, és így több küszöbértéket is meg lehet határozni, bármely két lokális maximum érték között. A hisztogram kétalakisága (bimodality of histogram): a gyakorlatban nem könnyű meghatározni, hogy egy hisztogram két- illetve több alakú. Általában lehetetlen eldönteni, egy lokális maximum fontosságát. 4.5 ábra: Több alakú, vagy bimodális hisztogram 28 4.37 Optimális küszöb A módszer két vagy több Gauss-görbe összegének hisztogram becslésén (megközelítésén) alapszik. A cél, hogy válasszunk úgy küszöböt a két maximum hely között, hogy a szegmentálás hibája minimális legyen. 4.38 Adaptív küszöbölés Adaptív küszöbölésnél a bemenő kép szürke árnyalatos vagy színes lehet, az eredmény kép bináris lesz. A képet részekre bontjuk, minden részképre (pl képpontra) kiszámolunk egy küszöböt, ha nem tudjuk kiszámolni, akkor vesszük a

részkép szomszédait és azok küszöbértékeinek interpolálásával kapjuk meg. Minden részképet szegmentálunk, ha a pixel a küszöb alatt van, akkor a háttérhez soroljuk, ellenkező esetben feltételezzük, hogy a tárgyhoz tartozik. T = T(f,fC), ahol f: kép ; fc: részkép 4.39 A határkarakterisztika használata a hisztogram javítására Az előző módszerek vizsgálata során kiderül, hogy a küszöbérték meghatározása a hisztogramból sokkal hatásosabb, ha a hisztogramnak magas kiugrásai vannak, keskenyek, szimmetrikusak és szeparálva vannak széles völgyekkel. Sokkal hatásosabb, ha a hisztogram kevésbé függ az objektumok és hátterek relatív méretétől. Ezek szerint a kis objektum a nagy háttéren jobban binarizálható. Az ideális eset az lenne, ha bármely pixel vagy egyértelműen objektum, vagy háttér eleme lenne és így egy szimmetrikus hisztogramot kapnánk. Továbbá, ha ugyanannyi lenne a valószínűsége, hogy egy pixel objektum

eleme, minthogy háttér elem legyen tovább, növelné a hisztogram csúcsának szimmetriáját. A gradiens és Laplace operátor segítségével 29 a hisztogramban lévő csúcsokat szimmetrikusabbá, a völgyeket pedig mélyebbé tudjuk tenni. A legfőbb probléma, hogy eddig feltételezett volt, hogy ismerjük az objektum és a háttér közötti határvonalat, ami viszont nem áll rendelkezésünkre. Az előbbiekben már említett gradienst tudjuk használni erre a problémára, valamint a Laplace operátor segítségével meg tudjuk vizsgálni, hogy vajon egy pixel sötétebb, vagy világosabb régióban helyezkedik el. [16], [20] 30 5 A LÉTEZŐ BINARIZÁCIÓS ELJÁRÁSOK ELEMZÉSE A SZAKIRODALOM ALAPJÁN 5.1 Bernsen módszere Minden pixelre - x, y koordinátákkal reprezentálva legyen T(x,y) az egyes pixelekre vonatkoztatott küszöbérték és T(x,y) = (Zlow + Zhigh) / 2, ahol Zlow és Zhigh jelenti a legalacsonyabb és legmagasabb szürkeárnyalati szintet egy

r*r nagyságú ablakban. Ha C(x,y) = (Zhigh - Zlow) < l, akkor ezt az ablakot be lehet sorolni egyetlen osztályba háttér, vagy előtér. Egy kísérlet szerint l = r = 15 jó eredményhez vezetett [21] 5.2 Chow és Kaneko módszere Chow and Kaneko módszer a képet felosztja egymást átfedő részképekre (amiket egy tömbben tárol), és így keresi az optimális küszöböt, minden részképre hisztogramjaik kivizsgálásával. A részképek megoldásának interpolálásával kapja meg minden egyes pixelhez a küszöbértéket. A hátránya ennek a módszernek, hogy nagyon számítás igényes ezért nem használható valós idejű alkalmazásoknál. [22] 5.3 Eikvil és mások módszere Két ablak segítségével bejárjuk az egész képet úgy, hogy legyen egy kisebb méretű S ablak és koncentrikusan egy nagyobb méretű L ablak. Az S ablakkal bejárjuk az egész képet, hogy az S ablakban lévő pixeleket előtér vagy háttér osztályba soroljuk a nagyobb L ablak T

küszöbérték kiszámolása segítségével. [23] 5.4 Mardia és Hainsworth módszere Kezdetben alkalmaz egy egyszerűbb binarizálást, majd továbbiakat hajt végre addig, amíg ezek el nem érnek egy konvergenciát. [24] 31 5.5 Niblack módszere Egyetlen küszöb nem mindig elegendő az objektum és háttér szétválasztásához, ezért ilyenkor változó küszöbérték kell, amely követi az intenzitásváltozásokat. A küszöbértékeket a mintaközép és a szórás alapján változtatja. A küszöbértéket az egyes pixelekre (x,y) a következő képlet alapján számolja ki: T(x,y) = m(x,y) + k*s(x,y), ahol m(x,y) és s(x,y) az egyes mintaközép és szórásértékek és a k paramétert az egyes objektumok szomszédosságának átmenetére használják. Sötét objektumnál k<0, világos objektumnál k>0, valamint általában |k| ~ 0.2 A környezet mérete: elég kicsi ahhoz, hogy a lokális részleteket megőrizze, de elég nagy ahhoz, hogy a zajt elnyomja

(általában 15X15). [25] 5.6 Taxt és mások módszere A képet felosztjuk nem-átlapolható 32*32-es négyzetekre. Az egyes ablakokban a hisztogram a két Gauss eloszlás szerint lesz kiszámolva. A paraméterek az "Expectionmaximization (EM)" algoritmus alapján kerülnek meghatározásra Ez az eljárás kontrasztos átmenetet képez az egyes objektumok között. Eikvil metódusa kijavítja ezt a hibát két ablak használatával és Otsu módszere gyorsabb becslést használ az EM algoritmusnál. [26] 5.7 Otsu algoritmus A bemeneti kép L szürkeárnyalatot tartalmaz a normalizált hisztogram minden x szürkeértékhez megadja az előfordulási gyakoriságát (valószínűségét): pX. Az algoritmus lényege: keressük meg azt a T küszöbszámot, amely maximalizálja az objektum és a háttér közötti varianciát. [20] 5.8 Yanowitz és Bruckstein módszere Ez a megközelítés a gradienst használja ki a küszöbölési felszín kiszámításához. [27] 32

5.9 Parker módszere Először megkeresi a képen található éleket, majd az élek közötti részt kitölti: vagy háttérnek, vagy előtérnek. [29] 5.10 White és Rohrer Integrált függvény algoritmusa Az eljárás gradiensszerű operátort használ a kép aktivitásának felderítésére. Először meghatározzuk a 0 címkéjű pixeleket, mely manuális Ta küszöbérték segítségével áll elő. Ezután, ha a Laplace éloperátor a pixelen alkalmazva pozitív, akkor a pixele címkéje +, negatív esetben - lesz. Ennek segítségéve történik az objektumok feltérképezése, majd a lokális osztályok meghatározása. [28] 5.11 Trier és Taxt módszere Az előző algoritmushoz javasoltak 3 javítást. [30] 5.12 Isodata (Yanni) Inicializálás: a hisztogramot két részre osztjuk (célszerűen a felezőponton), majd további lépései a következők: 1) számoljuk ki szokásos módon a hisztogramból egy kezdeti T küszöböt 2) határozzunk meg két csoportot, legyen

G1 azon pixelek halmaza, amely nagyobb T-nél és G2 azoké, amelyek ebbe nem tartoznak bele. 3) számítsuk ki ennek a két csoportnak a µ1 és µ2 értékét, amelyek a két csoport mintaközepe. 4) számítsunk ki egy új T-t: T = 0.5 * (µ1 + µ2). 5) Folytassuk az eljárást a (2)-(4). lépésig, amíg a kapott T érték és az előző T érték különbsége kisebb nem lesz egy előre meghatározott T0 értéktől. 33 A T értékét válasszuk a szürkeárnyalati hisztogram átlagának, ha a háttér és az objektum nagyjából azonos arányban fedi le a képet. Ha nem, akkor sokkal jobb választás, ha vesszük a szürkeségi szint minimumának és maximumának a számtani közepét. [17] 5.13 OGorman alkalmazása Egy globális megközelítés, ahol a küszöbértéket a lokális összetartozásból számítja ki. [32] 5.14 Liu módszere Az erősen zajos és komplex háttérrel rendelkező dokumentumokkal foglalkozik. Szürkeárnyalati és "run-length"

hisztogramot használ az ún. "object attribute thresholding" eljárásban. 5.15 Yang küszöbölési algoritmusa Statisztikai ún. "largest static state difference" számításokat végez A küszöbértéket minden egyes pixelre vonatkoztatott statisztikai és tranziens tulajdonságérték szerint számolja. [34] [31], [35] 34 6 A MEGOLDÁSI MÓDSZER KIVÁLASZTÁSA, A VÁLASZTÁS INDOKLÁSA 6.1 A szűrők kiválasztása Olyan szűrők kombinációra van szükség a binarizációs folyamat előfeldolgozásaként, amely az összefüggő régiókat egységesebbé teszi, eltünteti a karakterektől elütő objektumokat, zajokat és a betűk-háttér közti kontrasztot növeli. Azért használom a szűrők valamely kombinációját, mert erre a sok feltételre egyetlen szűrő nem képes. Fontos szempont volt továbbá a szűrők kiválasztásánál, hogy ne legyen túl bonyolult, mivel igencsak lelassítaná az egész program futását, tekintve, hogy

több szűrőt használok. Maga a kiválasztási folyamat úgy történt, hogy a hasznosnak vélt szűrők egyedi, ideális paramétereit meghatároztam, majd ezek kombináció kipróbálásra kerültek. Ezután az adott mintaképekre lefuttatva felállítottam egy statisztikát, mely megmutatta, hogy mely kombinációra történt a legtöbb - vizuális szempontú – kiválasztás. (ld 8 fejezet) A felhasználandó filterek a következők voltak: o erózió o dilatáció o Medián o élesítés o Gauss filter A fentebb említett kiválasztás során a következőkre jutottam: dilatáció és erózió páros, Gauss filter, Medián filter, majd végül élesítés. Részletesebben a 8 fejezetben kerül ismertetésre. 35 6.2 A binarizációs módszer kiválasztása A szakirodalomban rengeteg binarizációs módszer állt rendelkezésemre (ld. 5 fejezet). Lényegében egy új módszer kifejlesztése volt a célom, más módszerek felhasználásával. Az alapprobléma az volt, hogy

a mai szkennerek nincsenek felkészülve arra, hogy a dokumentumot valamely fizikai hatás érte, gondolok itt a gyűrődésekre, a szakadásokra és egyéb hasonló váratlan hibákra. Sokszor előfordul például, hogy egy szétnyitott könyvet próbálunk bedigitalizálni szkenner segítségével. Ekkor a lap közepénél sötét foltot fogunk észlelni a binarizáció során. 6.1 ábra: Szkennelési probléma A további szkenneléssel kapcsolatos hiba, hogy ha a beolvasott üvegen a kijelölést megváltoztatjuk, akkor mindig megváltozik a binarizációs eredmény is, vagyis már ebből kiderül, hogy nem alkalmazkodik kezdetben a lokális viszonyokhoz. A következő ábra azt mutatja be, hogy miként változik a binarizáció, ha változik a dokumentum kijelölése: 36 6.2 ábra: A dokumentum kijelölésének befolyása Az ábrán látható, hogy minél jobban csökkentjük a kijelölés nagyságát az üvegen, annál inkább érvényesül a problémás hely lokális

tulajdonsága, vagyis egyre nagyobb szöveget tehetünk olvashatóvá. Ennek megoldására kerestem olyan ötletet, amely feltérképezi az egyes lokális területek összetartozását, vagyis olyan területekre való osztás, amely úgy osztja fel az adott képet alszegmensekre, hogy szegmenseikben a háttér és a szöveg intenzitása külön-külön közel homogén legyen. Ennek feltérképezésére a legjobb módszernek azt találtam, hogy a képet fel kell szegmentálni és az egyes alszegmensek szürkeárnyalati hisztogramja alapján össze lehet hasonlítani, hogy egy küszöbérték szerint megegyeznek-e, vagyis ha összevonnánk a két szegmenst, akkor fennállna-e a fent említett probléma. A szegmentálásra legjobban kedvelt módszer a szakirodalomban a Quadtree eljárás; gyorsasága és egyszerűsége miatt ezt választottam. Ha a szegmensek ily módon elkészültek, akkor végre kell hajtani rajtuk egy binarizációs eljárást. Itt egy olyan algoritmust választottam,

amely alkalmazkodni tud a háttér és a karakter előfordulásának arányához. Ez a heurisztikus ötleten alapuló Isodata (Yanni) algoritmus (ld. 512 fejezet) teljesíti továbbá a gyorsasági kritériumot is 37 7 A RÉSZLETES SPECIFIKÁCIÓ LEÍRÁSA A program egy binarizáló eljárás, ami azt jelenti, hogy bemeneti adatként szürkeárnyalatos képeket kapva - melyek jelen esetben általam beszkennelt újságcikkek – átalakítja a képeket bináris képpé. A dokumentum kisebb hibáira szűrők kombinációját használja. Az elsődleges szempont a karakterek formájának megőrzése és elkülönítése a háttértől. A feldolgozandó képeket egy – programban meghatározott – könyvtárba kell elhelyezni (TesztKepek), ahol minden képre végrehajtja a binarizációt és a kész képeket szintén egy előre meghatározott könyvtárba (Kesz) helyezi el. A program nem igényel bemeneti paramétereket. Kötegelt feldolgozása lévén az elsődleges feladata nagyobb

újságállományok szürkeárnyalatos bedigitalizált formájának binarizációja. 38 8 A TERVEZÉS SORÁN VÉGZETT MUNKAFÁZISOK ÉS TAPASZTALATOK LEÍRÁSA 8.1 Hibajavító szűrők tervezése 8.11 Az egyes szűrők egyenkénti vizsgálata Matlab-ban Erózió és dilatáció: Ez az úgynevezett nyitás-zárás technika. A dilatáció lebontja a pixeleket, az erózió pedig felépíti. Ezzel a kisebb objektumokat lehet megszüntetni, esetleg kis sugarú alkalmazásakor eltüntethetők az egypixeles hibák is. Matlab-ban elvégzett kísérlet: Ha kis sugárban végezzük a dilatációt, majd az eróziót, akkor hasonló eredményt hoz az egyes paraméterezéseknél. A line-nál (egy pixel környezetében vonalirányt végzi el a műveletet a megadott fokban) és a ball-nál (a pixel egy körszerű környezetében dolgozik a megadott sugárban egy mélységet hozzárendelve) 1 és 2 sugarú hatókör esetén kapunk elfogadható eredményt a square (a pixel körül négyzetként

jelenik meg) és disk (a pixel egy körszerű környezetében dolgozik a megadott sugárban) esetben csak az elsőnél. Ebből a line verziót fogom használni, mert gyorsaságban jobb a többinél. A line verziók közül elfogadható eredményt az 1 pixeles vonalméret - minden szögben - és a 2 pixeles vonalméret - 45 fokos szögben - hozott. Ezek közül a gyorsabb feldolgozás érdekében az 1 pixeles 0 fokos paraméterezést fogom használni. Gauss filter: A Gauss filter a Gauss-féle zaj eltüntetésére szolgál, ami az újságoknál gyakran előfordul. Itt, ennél a résznél érdemes először megnézni, hogy mi az a Gauss-féle zaj Ezt leginkább egy ábrával lehet szemléltetni: 39 8.1 ábra: Gauss-féle zaj Maga a szűrő elkeni a képet, megszünteti a zajokat és eltünteti a részleteket is. Az élek és a kép elmosódik használatakor. Matlab-beli használatakor két paramétert lehet állítani. Az egyik az ablakszélesség, a másik a szórás. A szórást

01-től 01-es lépésközzel vizsgáltam 12-ig, ahol még viszonylag felismerhető a kép. Az ablakméretet 2-től 4-ig Mindkét esetben a középérték bizonyult a legjobb megoldásnak, vagyis 3*3-as ablakméret és 0.6-es szórásérték A betűk mellett lévő Gauss zajt jól eltávolította a szűrő. A kisebb ablakméretnél kevesebb zajt tüntetett el, viszont a nagyobbnál nagyon elmosta a képet. A szórásnál szintén ez volt a helyzet. Medián filter: Itt kizárólag az ablakméretet lehet állítani. Impulzív zajok kiszűrésére használatos Ezek közül a 2*1-es és az 12-es ablakméret bizonyult jó megoldásnak, mivel az ezen felüli ablakméret túlzott elhomályosodást és adatvesztést eredményezett. A kettő közül a 2*1-es ablakméretet választom, bár megjegyzendő, hogy a kettő között nem volt semmilyen különbség. Élesítés: Egy paramétere van, egy 0-1 intervallumba tartozó, élességet meghatározó érték. Ezt a szűrőt aszerint kell

paraméterezni, hogy milyen fenti szűrőket választottunk hibajavításra, vagyis mennyire homályosodott el a kép. 40 8.12 A filterek kombinációja statisztikai elemzés alapján A vizsgált filtereket egymás után alkalmazom. Négy külön egység létezik: dilatáció és erózió páros, Gauss szűrő, Medián filter és élesítés. Összesen 2376 képet állítottam elő oly módon, hogy minden egyes bemeneti képre, amely 24 darabból állt, a lehetséges filterkombinációkat előállítottam. Először a dilatáció és erózió páros, Gauss és Medián szűrő permutációt és ezek párosításait végeztem el, majd mindegyikhez 11 élesítési szintet illesztettem. Vagyis a permutációkból 9 lehetséges kombináció állt elő és e kombinációk mindegyikéhez rendeltem hozzá az élesítési szinteket. Amikor előállt az összes kép vizuális szempontok alapján kiválasztottam az elfogadható képeket; összesen 476 kép felelt meg az elvárásoknak. Ezek

szempontok a következők voltak: o Az egyeses régiók minél egységesebbek legyenek o A betűk körüli zaj eltűnjön o Egyéb zajok eltűntek-e o A betűk minél jobban elkülönüljön a háttértől Az egyes filterkombinációk eloszlása: megfelelő képek száma Filterek kombinációjának eloszlása 150 100 Adatsor1 50 0 123 132 213 231 312 321 134 124 234 filterkombinációk 8.2 ábra: Filterek kombinációjának eloszlása 41 Ahol az X tengelyen lévő számoknak a következő a jelentésük: 1 - dilatáció és erózió; 2 – Gauss filter; 3 – Medián filter; 4 – nem jelent semmi féle filtert, csak a tesztelő program működése miatt volt szükséges. Az élesítésnél a következő statisztikát állítottam fel: Megfelelt képekben alkalmazottak száma Élesítési beállítás a megfelelt képeknél 15 10 Adatsor1 5 0 1 2 3 4 5 6 7 élesítési értékek 8 9 10 8.3 ábra: A filterkombinációkhoz illesztett élesítés Ahol az X tengelyen

lévő számoknak a következő a jelentésük: fentebb már említettem, hogy az élesítés paramétere 0-tól 1-ig terjedő szám lehet. Az 1 jelenti a 01-et és a 10 az 1-et. Ha túl kicsi az élesítés mértéke, akkor homályos marad a kép, ha túl nagy, akkor felerősíti túlzott módon a zajokat. Tapasztalatok: A megfelelő képeknél a betűk és egyéb objektumok sötétebbé váltak a kontraszt növelése következtében. A betűk körüli zaj csökkent Ezáltal elértük a kezdeti célt. Következtetések: A legjobb megoldás, ha a filtereket a dilatáció-erózió páros, Gauss filter, Medián filter sorrendben alkalmazzuk. Az élesítés pedig 02 értékben ad legjobb eredményt. 42 8.2 A binarizációs folyamat tervezése A program tervezésében igen nagy szerepet játszott, hogy Matlab-ban történt az implementálása. A filterek megtervezésénél igen nagy előnyt jelentett tömörsége és beépített függvényei, de a Quadtree eljárásban a

fastruktúra ábrázolásánál alkalmazkodni kellett a Matlab mátrixos ábrázolásához. A megoldandó kérdések közt fő helyen állt a Quadtree eljárásnál, hogy hol álljon meg a szegmentálási algoritmus. Az, hogy nem tartalmaz ez a script nyelv mutatókat és a szegmentálás megállásának problémája arra vezetett, hogy változtassak a “split and merge” algoritmus szokásos menetén, vagyis minden egyes alkép felszegmentálásakor meg kell nézni, hogy mely elemek vonhatók össze, különben a végén az összevonási fázis csak igen nehezen jöhetne létre a fastruktúra hiányában. Tehát, ha valamely szomszédja az adott alképnek összevonható valamely másik alképpel, akkor nem kell tovább szegmentálni azt, vagyis megáll az algoritmus. Továbbá figyelembe kell azt is venni, hogy ha túl kicsi az alkép, akkor nincs értelme tovább vizsgálni a környezetét. Ezért be kellett vezetni egy oldalhatár, amelynél még szegmentálhat az algoritmus.

Gondoskodni kell arról, hogy ha egy adott szegmenst megvizsgáltunk, akkor az már ne éljen, ne vegyük számításba, mint önálló alképet, mivel felbomlott – az őt alkotó – alszegmensekre. Ezt egy egyszerű listával lehetett megoldani, amin a megvizsgálandó szegmensek nevei szerepelnek. A tervezés során el kellett dönteni, hogy egy alkép négy részre osztásakor mely alképeket hasonlítsuk össze. A dokumentum jellegének változását és a feldolgozási időt számba véve, kizárólag a függőleges és vízszintes irányú vizsgálódás mellett döntöttem. A program futása közben keletkező adatok praktikus tárolásának módja után, a tervezés a fentebb említett módszerek (ld. 6 fejezet) egyszerű algoritmizálásából állt 43 9 A MEGVALÓSÍTÁS LEÍRÁSA 9.1 Szükséges paraméterek és változók ismertetése 9.11 Paraméterek A felhasználó-barátság érdekében a paraméterek legjobb kombinációját előre kikísérleteztem, ezért

azok értékei be vannak építve a program belsejébe és csak programozó által változtathatók. o BinSzam – megmondja, hogy hány binre osszuk fel az adott hisztogramot o H – két szegmens hisztogramjának binjeinek maximuma közt mennyi lehet a különbség, hogy hasonlónak mondhassuk őket o KisebbOldal – megmondja azt a legkisebb oldalméretet, ahol egy szegmenst fel lehet szegmentálni o T0 - A küszöb konvergálásánál ez a küszöbérték dönti el, hogy a Tuj és T elég közel vannak-e egymáshoz o Tmax, Tmin - Ezekkel figyeljük, hogy homogén-e egy adott szegmens vagyis megnézi, hogy az egyes küszöb nagyon eltolódott-e valamely szélsőérték közelébe, 9.12 Fontosabb változók A program későbbi működéséhez elengedhetetlen, hogy néhány fontosabb változót ismertessek: o AsszocM - A felszegmentált területek koordinátái o Merge - A sorai tartalmazza az egyes összetartozó területek szegmenseit o Observe – Az a lista, ahol nyilvántartjuk a

vizsgálandó szegmensek nevét 44 o Pairs – Megmondja a hasonló szegmensek nevét 9.2 Kötegelt feldolgozás és előfilterezés 9.21 Kötegelt feldolgozás A kötegelt feldolgozás érdekében egy külső ciklust kellett alkalmazni, amely addig dolgozik, amíg az előre meghatározott TesztKepek mappából, minden képet fel nem dolgozott. Amint kész van egy kép, a Kesz mappába helyezi ‘Bin ’ plusz az eredeti kép neve néven. Ez nagyon kényelmes feldolgozást jelent, mivel a feldolgozás során nem szükséges semmilyen felhasználói aktivitás. 9.22 Előfilterezés A 6.1 fejezetben ismertetett módon kiválasztásra kerülő filterek megvalósításával kezdődik a program lényegi része. Kezdetben végrehajtja a dilatáció-erózi párost, majd a Gauss-filtert követi a Medián szűrő, végül pedig az élesítés következik. 9.3 Quadtree eljárás Kezdeten felállítjuk az aktuális kép négy alszegmensét és eltároljuk őket változókba, és

koordinátáikat eltároljuk az AsszocM mátrixba. Ezután felállítjuk minden szegmensnek a hisztogramját, majd az előre meghatározott H küszöbszám segítségével megnézzük, hogy hisztogramjaik alapján hasonlóak-e az egyes szegmenspárok; ha hasonlóak, akkor eltároljuk őket a Pairs listába, ha pedig nem, akkor az Observe listába, vagyis tovább kell vizsgálni az adott szegmenst. Azokat a szegmenseket, amelyek hasonlóak voltak bármely más szegmenssel, azokat a Merge mátrixban eltároljuk, és abból összevonjuk azokat. Ezután belelépünk egy olyan ciklusba, amely ugyanazt teszi, mint az előző bekezdésben leírtak, csak mindig az adott aktuális szegmenssel, amit az Observe lista elejéről veszünk. A ciklus addig fut, míg az Observe listában fellelhető egy elem, vagy míg 45 egy szegmens oldalmérete el nem éri az előre megadott KisebbOldal kritikus határt, ahol már nem szegmentáljuk fel az aktuális szegmenst. 9.4 Az egyes részek

binarizációja Ha eddig a részig eljutottunk, akkor már megállapítottuk, hogy mely területeket tekintünk közel hasonló tulajdonságúnak. Ezeket, az összetartozó területeket most már nyugodtan binarizálhatunk egyetlen küszöbértékkel. Ebből következik, hogy ezt olyan ciklusban dolgozzuk fel, amely a Merge mátrix egyes sorain megy keresztül, ami az egyes összetartozó területek szegmensösszetevőit tartalmazza. Ennek a ciklusnak a részletes működését leginkább a következő állapotdiagramon keresztül lehet megérteni. A diagram után az egyes részek magyarázata következik. 46 9.1 ábra: A binarizáció állapotdiagramja Most az ábrán számmal jelölt részek részletes leírása következik: 1) Minden egyes összefüggő területre lefut a ciklus. Ezeket a Merge mátrix egyes soraiban tároltam, ezért annak soraira egyenként végighalad a ciklus. 47 2) Egy kezdeti T küszöbérték készítése. Az előállítás úgy történik, hogy az

egyes szegmensekre előállított hisztogramokat átlagoljuk az oszlopaik szerint, majd annak elemein végighaladva 1-től egy változó segítségével előállítjuk azt a számot, amely az addig előfordult pixeleknek a számát tárolja. Ha ennek a változónak az értéke eléri az összes pixel számának a felét, akkor a T érték ennek a hisztogramértékének X koordinátája lesz. 3) A G1 csoporton azon pixelek alkotják, amelyek nagyobbak a T értéktől és a G2 csoportot pedig azok, amelyek kisebbek, vagy egyenlők. 4) A µ1 és µ2 értékek a G1 ill. A G2 csoportok mintaközepei 5) Az új T küszöbérték meghatározása: T = 0.5 (µ1 + µ2) 6) Itt eldöntjük, hogy megfelelően konvergált-e a T, vagyis az előző T és az új T különbsége kisebb-e egy előre megadott T0 értéktől. 7) Ez az az eset, amikor megfelelő a T konvergenciája. A képet fizikálisan az új T küszöbérték szerint binarizáljuk. 9.5 Utófilterezés A kész képen egy nyitás-zárás

párost hajtok végre az esetleges 1 pixeles hibák eltüntetésére. 48 10 TESZTELÉS A könnyebb és automatikus tesztelés érdekében egy külön tesztprogramot készítettem, amely az eredeti program paraméterezhető verzióját használja fel az egyes paraméterek ciklikus kipróbálásával. Ez a tesztprogram először is meghatározott minden paraméternek egy alapértelmezett értéket. Ez úgy történt, hogy minden paraméternek meghatároztam azt az intervallumot, amit felvehet és annak körülbelül a középértékét tekinti az alapértelmezettnek: o BinSzam: 4, 8, 16, 32, 64, 128, 256 (minél nagyobb, annál pontosabban lehet megállapítani az egyes hisztogramok közötti távolságot) o H: 1-től a szegmensben található pixelek számáig (minél kisebb, annál több szegmenst fog létrehozni, annál pontosabb lesz a binarizálás) o KisebbOldal: 1-től bármeddig (minél kisebb, annál több szegmenst fog létrehozni, annál pontosabb lesz a binarizálás) o

T0: 0.256 (minél kisebb, annál tovább konvergál a T, és a küszöbölés egyre pontosodik remélhetőleg) o Tmax: 0.256 (minél kisebb, annál több területet fog homogénnak tekinteni a magas szürkeségi érték szerint) o Tmin: 0.256 (minél nagyobb, annál több területet fog homogénnak tekinteni az alacsony szürkeségi érték szerint) Megjegyzés: a középértéket nem mindig a fent megadott szélsőérték szerint számoltam, mivel az egyes szélsőértékek nem racionálisak, nem lehet velük számolni. Például a KisebbOldal-nál mindig az adott szegmens oldalaira kell vonatkoztatni. 49 Ezután minden paraméterre egy ciklust alkalmazok, amelyben az adott paraméter számára előre meghatározott értékeken keresztül végrehajtódik a főprogram a többi paraméter alapértelmezett értékével. Az egyes paraméterekre lebontva ezek az értékek a következők voltak: o BinSzam: 4, 8, 16, 32, 64, 128, 256 o H: 10, 20, 30, 50, 75, 100 o KisebbOldal: 6, 10,

20, 30, 50, 70, 100 o T0: 1, 3, 5, 7, 10, 15, 20 o Tmax: 250, 230, 220, 200, 190, 180, 160 o Tmin: 10, 30, 50, 60, 70, 90, 100 A tesztelés során 49 általam beszkennelt képpel dolgoztam, amit tematikusan állítottam össze aszerint, hogy az újságoknál előforduló típusok megjelenjenek. Ilyen szempontok voltak például – a már említett – szétnyitott könyv, gyűrődések, kisebbnagyobb szövegrészek együttes előfordulása, homogén szöveg, stb. A fent említett módon így 14.406 képet állítottam elő az egyes paraméterkombinációk segítségével, majd ezekből válogattam ki azokat a képeket, amelyek a következő vizuális szempontoknak megfeleltek: o A szöveg elkülönül-e a háttértől o A szöveg megőrizte-e betűinek épségét o A háttér mennyire zajos Az egyes paraméterek befolyása a képekre, az egyéni tapasztalatok alapján: o A BinSzam minél nagyobb, annál kevesebb zaj található a képen o A H minél nagyobb, annál kisebb

az árnyékobjektumok előfordulása o A KisebbOldal minél kisebb, annál pontosabb a szegmentálás 50 o A T0, ha túl nagy, akkor árnyékobjektumok keletkeznek, zajos lesz a kép és a karakterek formája is megsérül o A Tmax és a Tmin esetében az számított, hogy egy kritikus értéket elérjen, hogy ahol a homogén területeket homogénné tudjuk tenni. Az érthetőség kedvéért itt van rá egy példa: ha egy homogén, magas szürkeségi értékű terület küszöbölésén van a sor, ami megközelítőleg 210-től 256-ig helyezkedik el, akkor jó választás Tmax-nak a 210, hiszen, akkor a homogén hátteret egy osztályba fogja sorolni. Ugyanez vonatkozik a Tmin-re is. A fenti szempontok alapján összesen 469 képet találtam elfogadhatónak. Ezeket a képeket alapul véve az egyes paraméterkombinációkra statisztikát állítottam fel ugyancsak egy általam írt Matlab program segítségével, amely a következőképpen néz ki: 51 Lehetséges

paraméterkombinációk Paraméterkombinációk jósága 64 50 10 5 20 0 9 0 64 50 10 5 20 0 6 0 64 50 10 5 20 0 3 0 64 50 10 5 16 0 5 0 64 50 10 5 19 0 5 0 64 50 10 5 22 0 5 0 64 50 10 5 25 0 5 0 6 4 5 0 1 0 1 5 20 0 5 0 64 50 10 7 20 0 5 0 64 50 10 3 20 0 5 0 6 4 5 0 10 0 5 20 0 5 0 64 50 50 5 20 0 5 0 64 50 20 5 20 0 5 0 64 50 6 5 20 0 5 0 64 75 10 5 20 0 5 0 64 30 10 5 20 0 5 0 64 10 10 5 20 0 5 0 25 6 5 0 1 0 5 20 0 5 0 64 50 10 5 20 0 5 0 16 50 10 5 20 0 5 0 4 50 10 5 20 0 5 0 0 10 20 30 40 50 A megfelelt képeknél használt paraméterkombinációk 10.1 ábra: A paraméterkombinációk jósága A hisztogramból jól látható, hogy egy-két paraméterkombináció előfordulása a jónak vélt képek között igen kimagasló. Konkrétan a következő volt: o BinSzam = 64 o H = 50 ; 52 o KisebbOldal = 100 ; o T0 = 5 ; o Tmax = 200 ; o Tmin = 50 Mindezekből azt a következtetést vontam le, hogy a legjobban számító

paraméter az a Tmin és a Tmax volt. A tervezés az ideális paraméterek ilyenfajta meghatározásával befejeződött. 53 11 A MEGVALÓSÍTÁS ELEMZÉSE, ALKALMAZÁSÁNAK ÉS TOVÁBBFEJLESZTÉSI LEHETŐSÉGEINEK SZÁMBAVÉTELE Az általam végrehajtott kísérlet alapján bebizonyosodott, hogy az elsődleges minőségi elvárásoknak megfelel a program, viszont a másodlagos gyorsasági szempontból nem tűnik ki a hasonló megoldások közül. A megoldási technika kiválasztásában legnagyobb szerepet a saját kísérleteim adtak alapot, továbbá nagy segítséget jelentett a szakirodalom felkutatása. Alkalmazhatóság: A program megalkotása azt a célt szolgálja, hogy nagy tömegű bemeneti képet feldolgozzon emberi aktivitás nélkül, vagyis nagyszerűen használható nagyobb adatbázisok feldolgozásához, mint például könyvtárak papíralapú adatállományának binarizálására. Ezen felül egy komplett OCR program értékes részévé lehet tenni.

További tervek: Ezen kezdeti sikerek magukban hordozzák a további fejlesztés lehetőségét. Az egyik ilyen lehetőség természetesen a gyorsaság növelése, valamint az utófeldolgozás terén az árnyékobjektumok eltüntetése, hogy a felismerési folyamatot megkönnyítse. A gyakorlatbani felhasználás érdekében át kell ültetni más nyelvre, mivel a Matlab nem képes más környezetben futtatható fájl készítésére. Az ilyen irányú fejlesztésre az általam preferált nyelv a C++. 54 12 IRODALOMJEGYZÉK [1] Reszler Ákos - A Recognita mint technológia és mint üzlet http://www.kfkihu/(en,html3,hu)/~cheminfo/TermVil/kulonsz/k002/recognitahtml [2] Jacci Howard Bear -“OCR - mi az, és hogyan lehet jobban csinálni? (OCR - What It Is, How to Do it Better)” http://www.fairprinthu/cikkajanlo/2004/8html#OCR [3] Informatikai fogalomtár - http://gisfigyelo.geocentrumhu/informatika/kisokos ocrhtml [4] Thoma GR. (2001) ” Document image analysis and

understanding” R&D Internal R&D report to the Board of Scientific Counselors, CEB, LHNCBC, NLM; October 2001; 55pp. http://archivenlmnihgov/pubs/reports/mars2001-DIAU/mars2001-DIAUphp [5] Henry S. Baird, "The state of the art of document image degradation modelling" Xerox Palo Alto Research Center 3333 Coyote Hill Road, Palo Alto, CA 94304 USA www.parcxeroxcom/istl/members/baird [6] RDM Corp, 608 Weber St N., Waterloo, Ontario N2V 1K4, Canada és Clearwave Electronics, 8701 Buffalo Avenue, Niagara Falls NY 14304 [7] D. X Le, G Thoma, H Weschler, (1994) “Automated Page Orientation and Skew Angle Detection for Binary Document Images”, Pattern Recognition, Volume 27,Number 10, pp. 1325-1344, October 1994 http://archivenlmnihgov/pubs/doc class/prwordphp [8] P.Y Yin, (2001) "Skew detection and block classidfication of printed documents", Image and Vision Computing 19 (2001) 567-579 http://users.infounicaenfr/~jouvin/THESE/BIBLIO/YIN01PDF 55 [9] Q.

Yuan, C L Tan, "Page segmentation and text extraction from gray scale image in microfilm format" http://www.compnusedusg/labs/chime/da/paperdownload/yuan01spiepdf [10] Sean Chen, http://www.csqueensuca/home/chen/CompSci/thesis/node10html [11] S. Mao, T Kanungo, (2002) "Software architecture of PSET: a page segmentation evaluation toolkit", International Journal on Document Analysis and Recognition (IJDAR) 2002, 4: 205-217 http://lhncbc.nlmnihgov/lhc/docs/published/2000/pub2000003pdf [12] Shih, F.Y Shy-Shyan Chen,(1996) "Adaptive document block segmentation and classification", Systems, Man and Cybernetics, Part B, IEEE Transactions, Oct 1996, Volume: 26, Issue: 5 On page(s): 797-802 http://ieeexplore.ieeeorg/xpl/abs freejsp?arNumber=537322 [13] K. Y Wong, R G Casey, F M Wahl –( NOVEMBER 1982) "Document Analysis System" IBM J. RES DEVELOP ‘OL 26 NO 6 NOVEMBER 1982 http://www.researchibmcom/journal/rd/266/ibmrd2606Bpdf [14] O. Okum, D Doermann

and Matti Pietikainen,( November 1999) "Page Segmentation and Zone Classification: The State of the Art", MDA9049-6C-1250 November 1999 [15] Liying Fan, Chew Lim Tan and Lixin Fan, "EDGE-PRESERVING PREFILTERING FOR DOCUMENT IMAGE BINARIZATION", School of Computing, National University of Singapore, Singapore 117543 [16] Rafael C. Gonzalez and Richard E Woods (2002), "Digital Image Processing", Prentice hall, Upper Saddle River, NJ 07458 [17] Czimber Kornél, (2001), "Geoinformatika - elektronikus jegyzet", http://geo.efehu/hun/onlinejegyzet/geoinfo/geoinfo2htm#TOC36 56 [18] Dr. Sárközy Ferenc, (19970527) "Térinformatika - GIS Figyelő", http://gisfigyelogeocentrumhu/sarkozy terinfo/t33bhtm#lok [19] Mercury Computer Systems, Berlin (2004), http://www.amiraviscom/usersguide31/hximproc/HxImageEditorhtml [20] Dudás Krisztina, (2002), http://www.infuszegedhu/oktatas/jegyzetek/KubaAttila/texes/node5html [21] J. Bernsen, (1986)

"Dynamic thresholding of grey-level images", in Proc 8th Intl Conf. on Pattern Recognition, Paris, France, 1986, pp 1251-1255 [22] C.K Chow and T Kaneko, (1979) "Automatic detection of thet left ventricle from cineangiograms", Computers and Biomedical Research, vol. 5, pp 388-410, 1972 és Y Nakagawa and A. Rosenfeld, "Some experiments on variable thresholding", Pattern Recognition, vol. 11, no 3, pp 191-204, 1979 [23] L. Eikvil, T Taxt, and K Moen, (1991) "A fast adaptive method for binarization of document images", in Proc. First Intl Conf on Document Analysis and Recognition, SaintMalo, France, 1991, pp 435-443 [24] K.VMardia and TJ Haindsworth, (1988) "A spatial thresholding method for image segmentation", IEEE Trans. Pattern Analysis and Machine Intelligence, vol 10, no 6, pp 919-927, 1988. [25] W. Niblack, (1986) "An Introduction to Digital Image Processing", pp 115-116, Prendtice Hall, 1986. [26] T. Taxt, PJ Flynn, and

AK Jain, "Segmentation of document imagess", IEEE Trans Pattern Analysis and Machine Intelligence, vol. 11, no 12, pp 1322-1329 [27] S.D Yanowitz and AM Bruckstein, (1989) "A new method for image segmentation", Computer Vision, Graphics and Image Processing, vol. 46, no 1, pp 82-95, Apr 1989 57 [28] J.M White and GD Rohrer, (1983) "Image thresholding for optical character recognition and other applications requiring character image extraction", IBM J. Research and Developement, vol. 27, no 4, pp 400-411, July 1983 [29] J.R Parker, (1991) "Gray level thresholding in badly illuminated images", IEEE Trans. Pattern Analysis and Machine Intelligence, vol 13, no 8, pp 813-819, 1991 [30] O.D Trier and T Taxt, (1995) "Improvement of integrated function algorithm for binarization of document images", Pattern recognition letters, vol. 16, no 3, pp 277- 283, Mar. 1995 [31] Oivind Due Trier "Goal-Directed Evaluation of Binarization

Methods" - Student Member, IEEE, and Anil K. Jain, Fellow, IEEE [32] L. OGorman,(1994) "Binarization and multithresholding of document images using connectivity", CVGIP: Graph. Models Image Processing 56 (6) (1994) 496}506 [33] Y. Liu, R Fenrich, SN Srihari, (1993) "An object attribute thresholding algorithm for document image binarization", International Conference on Document Analysis and Recognition,ICDAR 93, Japan, 1993, pp. 278}281 [34] J. Yang, Y Chen, W Hsu, Adaptive thresholding algorithm and its hardware implementation, Pattern Recognition [35] J. Sauvola, M Pietikainen (1999) "Adaptive document image binarization" - Machine Vision and Media Processing Group, Infotech Oulu, University of Oulu, P.O BOX 4500, FIN-90401 Oulu, Finland, 1999 58 13 A SZAKDOLGOZAT TARTALMI ÖSSZEFOGLALÓJA MAGYARUL ÉS EGY IDEGEN NYELVEN 13.1 Összefoglalás magyarul Dolgozatom során sikerült betekintést adnom az optikai karakterfelismerésbe, és annak

hibaforrásainak, alkalmazásainak lehetőségeibe. A dokumentumok fajtái és zajai széles körűen ismertetve lettek, mivel a hibajavításhoz elengedhetetlen ezeknek alapos ismerete. Továbbá nagy jelentőséget tulajdonítottam annak, hogy áttekintsem a jelenleg legjobb, gyakorlatban is használt hibajavító szűrőket és küszöbölési technikákat. A 15 legígéretesebbnek tűnő globális és lokális binarizációs technika áttekintése után megalkottam egy saját fejlesztésű binarizációs programot, amely számos más – szakirodalomban fellelhető – megoldás előnyeit egyesíti magában. A program kötegelt feldolgozással a képeken egy filterkombinációt hajt végre a hibák kiszűrésére, Quadtree eljárással kiválasztja a hasonló tulajdonságú képrészeket, majd egy optimálishoz konvergáló küszöbérték segítségével binarizációt hajt végre. Utófeldolgozásként a kis hibákat leszűri egy újabb filter segítségével. A dolgozat végén

megállapítottam, hogy a tesztek alapján kezdeti céljaimat elértem, ismertettem a létrejött program előnyeit, hátrányait, alkalmazhatóságát és továbbfejlesztési lehetőségeit. 13.2 Summary In this paper I have introduced the Optical Character Recognition and the document process of error sources. Furthermore, the models of document image degradations is reviewed because of error fixing. I have looked across the most promising published thresholding techniques and filters. The application performs batch processing with error filtering. It selects the same segments with Quadtree process, and creates a treshold, which converge the optimal value. Thus, it can performs the binariztaion Finally, it performs a one pixel error fixing filter. In my extended essay I makes my conclusions: My 59 experimental results shows that this systematic approach is acceptable; I presents the advantages, disadvantages and applicability of this application and my future plans