OCR (optical character recognition) rozpoznávání textu v obraze Martin Koní ek, I46
programová dokumentace
1. Úvod Tento projekt vznikl na MFF UK a jeho cílem bylo vytvo it algoritmus schopný rozpoznávat text v obraze (OCR). Algoritmus pochází od autora a nepoužívá žádné dob e známé metody (jak se do tete dále) a jeho výsledky jsou velmi uspokojivé (jak si m žete vyzkoušet). Cht l bych pod kovat Dejvovi, že mi jej umožnil vyvíjet jako m j zápo tový program, jelikož mi tato tematika p ipadá zajímav jší, než ostatní nabízené na cvi ení.
2. Metodika Po vyzkoušení programu si možná íkáte: „A jak to tedy funguje?“ Správná otázka, protože to je samoz ejm to hlavní, o em tento dokument pojednává. Jádrem je algoritmus, který dokáže analyzovat obsah obrazu a výsledky analýzy porovnat s obsahem databáze, p íp. je do databáze p idat.
2.1. Analýza Obraz je projížd n svislými linkami zleva doprava a je zkoumán pro souvislé neprázdné oblasti. Vždy, když skon í zapo atá neprázdná oblast, máme další svislý pás, který m žeme podrobn zkoumat. Tedy každé 2 znaky musí být možno odd lit svislou linií. Z toho ihned vyplývají 2 omezení: znaky se nemohou p ekrývat a musí být „horizontáln “ souvislé. Máme-li pás, najdeme ješt horní a dolní hranici znaku, ímž získáme ohrani ující obdélník a zábava m že za ít. O znaku uvnit obdélníku jsou zjišt ny následující parametry. Parametry: -
pr b h linie zleva pr b h linie zprava pr b h linie zespodu pr b h linie shora po et pr se ík s horizontální linií po et pr se ík s vertikální linií po et pr se ík s diagonální linií pom r ší ka / výška
Význam parametr : Pr b h linie (celkový vzhled znaku) Nejjednodušší je to na p íkladu. P edstavte si písmeno „A“. To vypadá z takto: -
zleva má charakter „vlevo“ (p jdeme-li odshora dol po jeho levé linii, p jdeme vlevo) zprava má charakter „vpravo“ (stejný d vod) zespodu má charakter „nahoru, rovn , dol “ (p jdeme-li zleva doprava po jeho spodní linii, p jdeme nahoru, pak chvíli rovn , pak dol ) shora má charakter „nahoru, dol “ (stejný d vod)
Tyto 4 parametry sta í na jednozna nou identifikaci velké ásti abecedy (!). N která písmena (H, L, T, F, E, I) by však obdržela naprosto stejnou charakteristiku (jsou rovné ze všech stran). Proto byly p idány další parametry. Po et pr se ík P es obdélník jsou taženy 3 linie a spo teny po ty pr se íku s plnou oblastí (tj. když postupující „paprsek“ vstoupí na plný pixel).
Ší ka / výška Reálné íslo ur ující pom r stran ohrani ujícího obdélníku (tak se dob e pozná nap . I od L).
Implementace zjišt ní parametr : Pr b h linie Vezm me si jeden ze 4 p ípad , ostatní jsou obdobné. Nap . levá strana: M íme vzdálenost od levého okraje a porovnáváme s p edchozí vzdáleností a ve 3 prom nných si po ítáme, kolikrát už vzdálenost vzrostla, klesla, resp. z stala konstantní. Pokud vzdálenost vzroste (klense, nezm ní se), zvýšíme po et r st (pokles , nem n) o 1 a ostatní 2 po ty snížíme. Tyto 3 prom nné se tedy p etahují o dominanci, až jedna z nich zvít zí – dosáhne p ednastavené hodnoty (TOLERANCE). Na obrázku je po et pokles posupn : 1, 2, 3, 2 (nár st - zelen ), 3, 4 – poklesy zvít zily, dosáhly hodnoty 4, která byla nastavena jako tolerance. Prohlásíme tedy úsek za „vlevo“ a ostatní 2 hodnoty (r sty a nem ny) vynulujeme. erná linie na obrázku by takto dostala charakteristiku: „vlevo, rovn , vpravo“. Po et pr se ík Jsou taženy 3 paprsky (horizontální, vertikální, diagonální – ne p esn po uhlop í ce, odvozeno experimentáln ) a p i vstupu na vypln ný pixel se zapo ítá pr se ík. Ší ka / výška Vyd lení 2 ísel.
2.2. Databáze V databázi jsou uložené znakové sady – skupiny znak . Každá z nich obsahuje znaky a u každého z nich jméno (m že být i dlouhé) + zmín ných 8 parametr . Databázi jsem pojal pro p ehlednost jako soubor na disku ve formátu XML, takže jsem si mohl vyzkoušet i napsat jednoduchý „XML parser“. Ten jsem kv li rekurzivní struktu e formátu XML implementoval jako rekurzivní funkci. Po analýze znaku z obrazu je možno ho pojmenovat a p idat do databáze.
Vlastní rozpoznání textu v obraze probíhá tak, že se každý znak analyzuje zvláš , získané parametry se porovnají se vším v aktuální znakové sad , vybere se maximální shoda a jméno tohoto znaku z databáze se prohlásí za výsledek. Výsledky pro jednotlivé znaky se poskládají a máme text.
2.3. Vlastní implementace Program byl vytvo en v Delphi 7. Vše je zapouzd eno v t íd TAnalyzer (jednotka Analyzer.pas), jejíž hlavní metody jsou: function CharSimilarity(L1, L2 : TCharInfo) : real; - vrací, jak moc jsou si 2 struktury typu TCharInfo (používané pro ukládání znak ) podobné procedure AnalyzeFrom(Can : TCanvas; Left, Top, W, H, Tlr : integer); - z dané oblasti na daném canvasu analyzuje znak a získanými parametry naplní strukturu AnalyzedChar function GetAnalyzedCharInfo : TCharInfo; - vrací strukturu AnalyzedChar function GetAnalyzedString : string; - vrací celkový poskládaný výsledek function LoadCharsFrom(FileName : string) : boolean; function SaveCharsTo(FileName : string) : boolean; - na te xml soubor do pole FCharsets pat ícího t íd TAnalyzer / uloží zp t do souboru procedure SetCharsetIdx(idx : integer); - vybere aktuální znakovou sadu function GetResultPrecision : real; - vrátí, jak „úsp šná“ byla celková analýza obrazu, tj. jak podobné byly znaky v obraze t m v databázi Zbytek je okomentován ve zdrojovém kódu. Ostatní jednotky (Main.pas, TeachDlg.pas, EditChar.pas) obsahují formulá e a slouží jako grafické rozhraní pro demonstraci použití t ídy TAnalyzer.
3. Záv r a další práce Musím se p iznat, že jsem byl sám p ekvapený, jak dobré výsledky za al program podávat po p idání dostatku parametr pro znaky. První verze pracovala naivn jen s analýzou levé a pravé linie (už i to ale sta ilo na naprosto bezpe né rozpoznání A od B ). Po p idání horní a dolní strany se vyskytl zmi ovaný problém písmen T, L, H apod. Byly tedy ješt p idány 3 linie, které asov tém zadarmo poskytly daleko p esn jší výsledky. Algoritmus opravdu funguje dob e jak na znakové sad písmen kreslených myší (obdoba PDA a dotykové tužky), tak na b žných znakových sadách. Jeho návrh ho ale p edur uje k rozpoznávání písmen velikosti alespo 20 pixel – znak musí být dost velký na to, aby se na n m bylo „ eho chytit“. Tady hraje velmi d ležitou úlohu nastavená tolerance. Pro menší písmo je samoz ejm daleko vhodn jší mensí tolerance, protože tak m že být úsek vysoký 10px ozna en za „vlevo, rovn , vpravo“, p i emž p i vyšší toleranci by byl ozna en jen jako „rovn “, p ípadn by nebyl ozna en v bec a byl by považován za „hrbol“. Program nyní také pracuje pouze s jedním ádkem textu, což by nebyl problém v další verzi zm nit. Možná by se dal použít i pro p e tení naskenované strany textu, p i dostate né velikosti obrazu. Pro tento ú el nebyl však nebyl navržen. Zajímavostí je, že rozpoznávané znaky nemusí být jen písmena. Sta í znak analyzovat a pojmenovat. Program tak m že poznat domek, tank, letadlo a spoustu dalších v cí.
