Licenta2012 Daneliucanamaria Softwareocr [609407]

1
UNIVERSITATEA ALEXANDRU IOAN CUZA IAȘI
FACULTATEA DE INFORMATICĂ

LUCRARE DE LICENȚĂ
Augmented Reality – OCR și recunoaștere entit ăți
textuale semnificative

Absolventă: Coordonator științific:
Daneliuc A. Ana -Maria Lector Dr. Adrian Iftene

Sesiunea: iulie 2012

2
Declarație privind originalitate a și respectarea drepturilor de autor

Prin prezenta declar că Lucrarea de licență cu titlul “ Augmented Reality – OCR și
recunoaștere entități textuale semnificative ” este scrisă de mine și nu a mai fost prezentată
niciodată la o altă facultate sau instituție de învățământ superior din țară sau străinătate. De
asemenea, declar că toate sursele utilizate, inclusiv cele preluate de pe Internet, sunt indicate în
lucrare, cu respectarea regulilor de evitare a plagiatului:
– toate fragmentele de text reproduse exact, chiar și în traducere proprie din altă limbă,
sunt scrise în ghilimele și dețin referința precisă a sursei;
– reformularea în cuvinte proprii a textelor scri se de către alți autori deține referință
precisă;
– codul sursă, imagini etc. preluate din proiecte open -source sau alte surse sunt utilizate
cu respectarea drepturilor de autor și dețin referințe precise;
– rezumarea ideilor altor autori precizează refe rința precisă la textul original

Absolventă Ana -Maria Daneliuc ,
_________________________
(semnătura în original)

3
Declarație de consimțământ

Prin prezenta declar că Lucrarea de licență cu titlul “Augmented Reality – OCR și
recunoaștere entități tex tuale semnificative ”, codul sursă al programelor și celelalte conținuturi
(grafice, multimedia, date de test, etc.) care însoțesc această lucrare să fie utilizate în cadrul
Facultății de Informatică. De asemenea, sunt de acord ca Facultatea de Informatică de la
Universitatea Alexandru Ioan Cuza Iași să utilizeze, modifice, reproducă și să distribuie în
scopuri necomerciale programele -calculator, format executabil și sursă, realizate de mine în
cadrul prezentei lucrări de licență.

Absolventă Ana -Maria Daneliuc ,
_________________________
(semnătura în original)

4
Cuprins

Motivație ………………………….. ………………………….. ………………………….. ………………………….. ………………….. 6
Contribuții ………………………….. ………………………….. ………………………….. ………………………….. ………………… 7
Introducere ………………………….. ………………………….. ………………………….. ………………………….. ……………….. 8
I. Realitate augmentată (Augmented Reality) ………………………….. ………………………….. …………………….. 9
I.1 Introducere ………………………….. ………………………….. ………………………….. ………………………….. ………. 9
I.2 Platforme și aplicații de realitate augmentată existente ………………………….. ………………………….. ….. 10
I.2.1 Layar Reality Browser ………………………….. ………………………….. ………………………….. ………… 10
I.2.2 Wikitude World Browser ………………………….. ………………………….. ………………………….. …….. 11
I.2.3 Google Goggles ………………………….. ………………………….. ………………………….. ………………….. 12
I.2.4 Look! ………………………….. ………………………….. ………………………….. ………………………….. …….. 12
II. Recunoașterea optică a c aracterelor ………………………….. ………………………….. ………………………….. …. 13
II.1 Definiție și clasificare ………………………….. ………………………….. ………………………….. ………………….. 13
II.2 OCR cu rețele neuronale ………………………….. ………………………….. ………………………….. ……………… 14
II.3 Rețele neuronale artificiale ………………………….. ………………………….. ………………………….. …………… 16
II.3.1 Structură și comportament ………………………….. ………………………….. ………………………….. .. 16
II.3.2 Clasificare ………………………….. ………………………….. ………………………….. ………………………….. .. 18
II.3.3 Perceptroni ………………………….. ………………………….. ………………………….. …………………….. 19
II.3.4 Rețele neuronale multistratificate ………………………….. ………………………….. ………………….. 23
II.3.5 Concluzii: aplicabilitatea rețelelor neuronale artificiale ………………………….. ………………… 27
II.4 Tesseract ………………………….. ………………………….. ………………………….. ………………………….. ……….. 28
II.4.1 Scurt istoric ………………………….. ………………………….. ………………………….. ……………………. 28
II.4.2 Arhitectură și flux de lucru ………………………….. ………………………….. ………………………….. . 29
II.4.3 Concluzii ………………………….. ………………………….. ………………………….. ……………………….. 37
III. Recunoașterea entităților textuale de tip nume ………………………….. ………………………….. …………… 39
III.1 Introducere în domeniul Extragerii de Informații ………………………….. ………………………….. ……….. 39
III.2 Definirea recunoașterii entitӑților de tip nume ………………………….. ………………………….. ……………. 40
III.3 Tehnici pentru NER ………………………….. ………………………….. ………………………….. …………………… 41
III.4 LingPipe ………………………….. ………………………….. ………………………….. ………………………….. ………. 42
III.4.1 Algoritmul Best First pentru LingPipe Named Entity Recognizer ………………………….. ………. 43

5
III.4.2 Algoritmul N -Best pentru LingPipe Named Entity R ecognizer ………………………….. ………….. 44
III.4.3 Algoritmul Confidence pentru LingPipe Named Entity Recognizer ………………………….. ……. 45
III.5 Concluzii ………………………….. ………………………….. ………………………….. ………………………….. ……… 46
IV. Arhitect ura aplicației ………………………….. ………………………….. ………………………….. ………………….. 47
IV.1 Modulul OCR ………………………….. ………………………….. ………………………….. ………………………….. . 47
IV.1.1 Funcționalitate generală ………………………….. ………………………….. ………………………….. …… 47
IV.1.2 Integrare în proiect ………………………….. ………………………….. ………………………….. ………….. 48
IV.2 Modulul de traducere ………………………….. ………………………….. ………………………….. …………………. 55
IV.3 Modulul de recunoaștere a entităților textuale semnificative ………………………….. ……………………. 56
IV.3.1 Componente ………………………….. ………………………….. ………………………….. …………………… 56
IV.3.2 Funcționare ………………………….. ………………………….. ………………………….. ……………………. 57
IV.3.3 Rezultate ………………………….. ………………………….. ………………………….. ……………………….. 58
IV.4 Modulul de extragere a informațiilor externe ………………………….. ………………………….. …………….. 59
IV.5 Schema generalӑ a aplicației ………………………….. ………………………….. ………………………….. ……….. 60
V. Concluziile lucrӑrii și direcții de dezvoltare ………………………….. ………………………….. ………………….. 62
VI. Bibliografie ………………………….. ………………………….. ………………………….. ………………………….. ….. 63

6
Motivație

Smartphone -urile au devenit o componentӑ indispensabilӑ în viața de zi cu zi, înglobând
într-un singur dispozitiv atât un telefon, cât și un aparat de fotografiat/filmat, GPS, internet,
agendӑ și multiple aplicații care combinӑ aceste facilitӑți pentru a îmbunӑtӑți și facili ta
comunicarea, interacțiunea cu societatea, organizarea programului zilnic. Telefoanele au
configurații din ce în ce mai bune, care permit și efectuarea de taskuri complicate și costisitoare,
cu anumite limitӑri, bineînțeles, dar totuși transformӑ în real iate ceea ce odinioarӑ pӑ rea
imposibil pe un dispozitiv atât de mic.
Aplicațiile bazate pe realitatea augmentatӑ utilizeazӑ toate aceste capabilitӑți
extraordinare ale platformelor mobile puternice, pentru o experiențӑ vizualӑ și cognitivӑ
superioare. Majoritatea aplicațiilor de acest fel sunt de tip AR Browser, afișând pe suprafața
ecranului puncte de interes din diverse arii, de cele mai multe ori în funcție de poziția geograficӑ,
dar și de aproprierea sau depӑrtarea de anumite persoane, în cadrul unei r ețele sociale
personalizate.
Aplicațiile care se bazeazӑ pe recunoașterea sau clasificarea de imagini, text sau persoane
sunt însӑ mai puține, poate și datoritӑ complexitӑții algoritmilor și strategiilor ce stau la baza
acestor sarcini din domeniul inteli genței artificiale.
Prin prezentul proiect de licențӑ, am dezvoltat un sistem capabil sӑ pozeze un text, prin
încadrarea sa exactӑ, sӑ îl recunoascӑ (OCR), sӑ îl traducӑ și sӑ extragӑ din el entitӑți
semnificative de tip nume , pe care sӑ le afișeze apoi cu informații suplimentare, preluate de pe
internet. Astfel se realizeazӑ o augmentare a textului, lucrarea intrând in categoria de realitate
augmentatӑ descrisӑ mai sus. Tehnologiile folosite sunt alese astfel încât sӑ se preteze la
integrarea pe un telef on cu sistemul de operare Android. Este posibilӑ și distribuirea și stocarea
textului rezultat în diverse moduri.
Un use -case tipic ar fi pentru un turist aflat într -o țarӑ strӑinӑ, care nu cunoaște limba și ar
dori sӑ afle informații de interes despre dif erite locații și obiective turistice, într -o manierӑ cât
mai centralizatӑ cu putințӑ . Dat fiind cӑ pozarea unui text este mai rapidӑ dec ât tastarea sa și

7
ținând cont de calitatea ridicatӑ a imaginii camerelor de pe telefoanele “inteligente”, aplicația se
poate dovedi de un real ajutor.
Contribuții

Proiectul îmbinӑ ideile personale cu cele ale d -lui coordonator, pentru a realiza o
structurӑ unitarӑ, cu funcționalitӑți precise, ușor configurabile și afișare a rezultatelor într-o
manierӑ cât mai prietenoasӑ. Este scris în limbajul Java Android.
Arhitectura generalӑ a aplicației este conceputӑ în cea mai mare mӑsurӑ de mine, având
totuși ca repere [14], o aplicație pentru scanare coduri de bare, de la care m -am inspirat în lucrul
cu camera și [13], de la care am preluat modul de desenare al dreptunghiului de încadrare,
precum și pașii necesari pentru integrarea motorului OCR, mai ales în modul continuu. Codul
respectiv este însӑ adaptat la cerințele aplicației mele.
Folosesc Tesseract drept componentӑ OCR , care necesitӑ prelucrarea imaginii surprinse
de camerӑ într -un format corespunzӑtor , descӑrcarea fișierelor antrenate pe seturile de caractere,
precum și setarea unor parametri corespunzӑtori . Folosesc biblioteca Jtar pentru dezarhivarea
fișierelor antrenate descӑrcate.
Traducerea se realizeazӑ prin apeluri cӑtre un serviciu web, Microsoft Translator, cel mai
performant serviciu gratuit actual. Cu ajutorul biblioteca Gson, parsez rӑspunsul de la el.
Pentru componenta de recunoaștere a entitӑților textuale, folosesc o strategie proprie, care
presupune însӑ și integrarea unui NER cât mai lightweight , (LingPipe), antrenat statistic pentru
deducerea din context a tipului entitӑții. Pentru corectarea rezultatelor sale, folosesc o combinație
de expresii regulate, bazӑ de date predefinitӑ, euristici personale și feedback utilizator.
Modulul de extragere a informațiilor externe de pe Wikipedia și Google Maps este g ândit
și scris în totalitate de mine , folosindu -mӑ de biblioteca Jsoup pentru parsarea sursei html.
Toate tehnologiile sunt open -source (în cazul bibliotecilor) sau se încadreazӑ într -un plan
personal gratuit, cu numӑr de cuvinte limitat pe lunӑ (2 milioane), în cazul Microsoft Translator.

8
Introducere

În capitolul 1 al acestei lucrӑri voi face o introducere a paradigmei de Augmented Reality ,
în care am dorit sӑ integrez aplicația mea. Voi arӑta scopurile în care poate fi dezvoltatӑ, care nu
sunt doar pentru entertainment , ci pot aduce o contribuție realӑ societӑții sau unui anumit
segment de pu blic. Voi prezenta pe scurt aplicațiile de acest tip cele mai populare la ora actualӑ,
cu plusuri și minusuri, cea mai apropiatӑ de ideea lucrӑrii mele fiind Google Goggles.
În capitolul 2 dezvolt teoria recunoașterii optice a caracterelor, prin prezentare a extensivӑ
a rețelelor neuronale și a algoritmilor lor, care stau la baza clasificatorilor din motoarele de OCR –
izare. Continuu cu un studiu de caz asupra motorului Tesseract, cel mai performant dintre
motoarele open -source existente, prezentând fluxul de lucru, strategiile și algoritmii folosiți. La
sfârșit fac un bilanț al aspectelor pozitive și al celor negative, care îl împiedicӑ poate sӑ se
apropie mai mult de acuratețea soft -urilor comerciale.
Capitolul 3 reprezintӑ o incursiune în domeniul NLP ( Natural Language Processing ),
mai exact în ramura recunoașterii entitӑților de tip nume (NER), sumarizând câteva din tehnicile
folosite la ora actualӑ. Am efectuat și un studiu de caz asupra bibliotecii lightweight LingPipe, o
alternativӑ fezabilӑ pentru telefon la aplicațiile monolitice folosite la ora actualӑ de sistemele mai
performante . Sunt necesare însӑ și alte tehnici de corectare a rezultatelor .
În capitolul 4 voi descrie arhitectura aplicației mele, prezentând în parte f iecare din cele 4
module principale: modulul OCR, modulul de traducere, modulul de extragere a entitӑților de tip
nume semnificative și modulul colectӑrii de informații externe, descriindu -le detaliat pe fiecare
în parte. La sfârșit, atașez o schemӑ genera lӑ a funcționӑrii aplicației, care face vizibilӑ
conectarea acestor module, precum și explicații suplimentare.
Voi încheia cu concluziile învӑțate în urma lucrului la aceastӑ aplicație și voi enumera
direcții le de dezvoltare ulterioarӑ la care m -am g ândit, ce include mai multe funcționalitӑți, dar și
îmbunӑtӑțirea celor deja existente.

9
I. Realitate augmentată (Augmented Reality )

I.1 Introducere

Mult anticipata și experimentala tehnologie pe care odinioară o vedeam doar în filmele
science -fiction este acum realitate. Vorbim despre realitatea augmentată ( augmented reality ,
abreviat AR), cea mai nouă și sofisticat ă direcție software abordată în zilele noastre, cu un impact
decisiv asupra utilizatorului final.
Putem afirma despre acest concept că re prezintă atât o tehnologie, cât și un domeniu de
cercetare intensivă, proiecție a viitorului tehnologic, o industrie comercială ce înflorește cu pași
repezi, precum și un nou mediu de exprimare a creativității. [5]
O definiție formală ar fi următoarea [5]: “Realitatea augmentată combină conținut ul
grafic sau media generat pe calculator cu informații obținute în timp real , prezentându -le
utilizatorului într -o formă atractivă și interactivă .”. Se realizează astfel o întrepătrundere a
virtualului cu realul, o augmentare a acestuia din urmă, de unde și denumirea. Realitatea
imediată, cu care utilizatorul interacționează prin intermediul unui dispozitiv inteligent, capătă
noi dimensiuni cognitive, într -o manieră neașteptat de prietenoasă și intuitivă.
Platformele AR se află la intersecția mai multor domenii tehnice, incluzând grafica
digitală, machine vision , inteligență artificială, sisteme de senzori, sisteme de poziționare
geografică, servicii web, sisteme mobile etc. [5].
Precursoarea realității augmentate este realitatea virtuală [6], care îl introduce pe
utilizator într -o dimensiune complet artificială, din care îi este imposibil să mai perceapă lumea
reală. Spre deosebire de aceasta, AR suplimentează realitatea, nu o înl ocuiește total.
Scopul nu este doar enter tainmentul sau simpla informare. Aplicațiile ce se încadrează în
această paradigmă își propun să ajute utilizatorul sau un grup de utilizatori și chiar să faciliteze
munca într -un anumit domeniu, spre exemplu cel educațional (eLearning, lecții interactive),
aviație (simulatoare avansate de zbor ), medical (simulatoare de intervenții și practici medicale) ,

10
publicistic (informațiile din căr ți/articole “prind viață”, interacționând cu utilizatorul) , militar
(planificato are de strategii) , arhitectură (machete virtuale) etc.
I.2 Platforme și aplicații de realitate augmentată existente

Pentru ca o aplicație AR să funcționeze și să producă o experiență vizuală deosebită, o
combinație de GPS, busolă, cameră foto/video și o conexiune 3G/WiFi este mult recomandată.
Datorită existenței unei platforme mobile puternice, precum Android , dezvolta torilor software le
este mult mai uș or să creeze astfel de aplicații.
Trei dintre cele mai semnificative și populare aplicații AR dezvoltate pe această
platformă sunt Layar Reality Browser , Wikitude World Browser și Google Goggles .
I.2.1 Layar Reality Browser reușește să se mențină în topul preferințelor utilizatorilor
prin performanțele sale, în ciuda faptului că este printre primele aplicații de acest tip. Folosește o
combinație între camera foto, GPS și busolă, pentru a identifica locația utilizatoru lui și câmpul
său vizual , care este apoi îmbogățit prin afișarea pe ecran a informații lor despre locații de interes
din apropiere . Mai nou, Layar oferă și un API pentru programatorii care doresc să dezvolte
aplicații după acest model [6]. Observăm un inst antaneu mai jos:

Fig 1 – instantaneu din aplicația Layar Reality Browser1

1 http://compixels.com/441/top -5-augmented -reality -apps -for-android

11
Plusuri și minusuri ale acestei aplicații:
(+): posibilități de customizare a rezultatelor afișate , interactivitate, interfață user-friendly ,
acuratețe a detectării locațiilor , numeroase criterii de căutare a punctelor de interes și de
“straturi” de informații care pot fi adăugate peste imaginile capturate de cameră ;
(-): API-ul pentru dezvoltatori este limitat;
I.2.2 Wikitude World Browser este un browser ce se bazează pe conțin ut Qype,
precum și pe poziția geografică, pentru a afișa informații de pe Wikipedia în limba aferentă. Se
pot căuta informații despre orice punct de interes din cele 350,000 din baza de date, după
coordonatele GPS sau după adresă. Rezultatele sunt afișate sub formă de listă, hartă sau în stil
AR, ca și cum ar fi vizualizate cu camera2. Avem două instantanee mai jos :

Fig.2 – instantanee din aplicația Wikitude World Browser2

Plusuri și minusuri:
(+): multiple criterii de căutare (Wikipedia, Flickr, YouTube, Booking.com) pentru POI (puncte
de interes), API cuprinzător ce facilitează crearea mashup -urilor de către dezvoltatori ;
(-): multitudinea de categorii de puncte de interes poate fi derutantă inițal, și nec esită timp
pentru a învăța cum se interpretează rezultatele, unele feature -uri sunt încă în fază incipientă;

2 http://compixels.com/441/top -5-augmented -reality -apps -for-android

12
I.2.3 Google Goggles este contribuția gigantului mondial la această tehnologie
inovatoare. Se bazează pe recunoașterea imaginilor de text sau de obiect e de interes, captate cu
ajutorul camerei foto , iar apoi trimise către serverul de procesare SnapTell3. Sunt afișate apoi
rezultate relevante de pe web pentru acestea. Categoriile recunoscute sunt dintre cele mai
diverse: titluri de cărți, nume de produse comerciale, mo numente celebre, portrete ale unor
celebrități, coduri de bare etc. Mai jos avem un exemplu de recunoaș tere de text:

Fig.3 – instantanee din aplicația Google Goggles4
Plusuri și minusuri:
(+): informații rapide despre o gamă largă de produse, procesarea atât a unor imagini capturate
pe loc, cât și a celor stocate anterior, interfață user-friendly , tutorial introductiv;
(-): acuratețea rezultatelor afișate nu este întotdeauna cea dorită, nu se pot configura anumite
setări .
I.2.4 Look! este un framework creat recent pentru dezvoltarea de aplicații AR, cu
numeroase facilități pentru localizarea geografică atât indoor , cât și outdoor , precum și pentru
recunoașterea de imagini .5

3 http://www.snaptell.com/index.htm
4 http://compixels.com/441/top -5-augmented -reality -apps -for-android
5 http://www.lookar.net/en/

13
II. Recunoașterea optică a caracterelor

O ramură nu atât de mult explorată pe telefoanele mobile, datorită complexității sale, este
cea de OCR (recunoașterea optică a caracterelor). Totuși, folosirea unui dispozitiv mobil pentru
a fotografia un anumit text de interes spre a fi procesat, este un comportament firesc, având în
vedere că este mult mai rapid decât compunerea unui șir relevant de cuvinte pentru căutarea pe
web.
În următoarele secțiuni, voi detalia aspectele teoretice legate de OCR și rețele neuronale,
după care voi face o descriere detaliat ă a unei biblioteci open source axată pe acest domeniu –
Tesseract –, ce reprezintă o parte importantă a lucrării mele practice.

II.1 Definiție și clasificare

Recunoașterea optică a caracterelor (Optical character recognition , abreviat OCR )
este procesul prin care un sistem inteligent extrage secvențe de caractere − encodate în format
electronic − di n imagini ale acestora , obținute , de exemplu, prin scanare. Datorită acestei
tehnologii, avem astăzi varianta digitală a multor cărți și documente importante . OCR se îmbină
de multe ori cu tehnici de traducere automată, text-to-speech sau text mining , rezultând aplicații
complexe și deosebit de utile.
Există mai multe categorii de software de tip OCR:
i. Desktop/Server OCR – sisteme bazate pe inteligența a rtificială analitică, luând în
considerare mai degrabă secvențe de caractere, decât cuvinte întregi sau fraze.
După ce se face o potrivire inițială a caracterelor, se corectează alegerile făcute
prin consultarea unei baze de date cu cuvinte.
ii. WebOCR, Online OCR – noul trend care să acopere cererea mare și volumele mari
de informație care trebuie procesată. OnlineOCR se ocupă în special cu
recunoașterea scrisului de mână în timp real, o provocare mai ales pentru
producătorii de tablete și alte dispozitive mobi le cu stiletto.

14
iii. OCR orientat -aplicație – destinat să rezolve probleme frecvente în anumite
aplicații, referitoare la calitatea imaginilor ce trebuie procesate: fundaluri
complicate, granularitate mare, hârtie îndoită, rezoluție joasă, linii trasate,
simbol uri neobișnuite etc. Deoarece se concentrează doar pe anumite aspecte, se
mai numește și “Customized OCR ”. Exemple: Business -card OCR, Invoice OCR,
Screenshot OCR, ID card OCR, Driver -license OCR etc.
Pentru a -și îmbunătăți rata de succes, în special apli cațiile web care oferă servicii OCR
apelează de multe ori la sistemul reCAPTCHA6, patronat de Google. Astfel, anumite site -uri
abonate primesc imagini ale unor cuvinte ce nu au putut fi procesate corect în maniera OCR.
Acestea sunt apoi oferite utilizatori lor ca imagini CAPTCHA, în procesul obișnuit de
autentificare, înregistrare etc. Rezultatele sunt apoi returnate serviciului reCAPTCHA, care le
returnează, la rândul lui, aplicației OCR. Aceasta deoarece utilizatorii umani sunt cei care pot
recunoaște cel mai ușor greșelile și, astfel, ajusta tehnicile curente de recunoaștere a caracterelor.

II.2 OCR cu rețele neuronale

Una dintre cele mai populare astfel de tehnici este folosirea rețelelor neuronale
artificiale multistratificate , folosind algoritmul de retropropagare, concepte care vor fi
detaliate în următoarea secțiune.
După cum vom vedea, una dintre problemele principale este cum codificăm entitățile
concrete inițiale într-o secvenț ă de numere reale, ce va fi dată ca input rețelei. În cazul nostru,
lucrând cu imagini, putem avea mai multe abordări.
Etapa de antrenare a rețelei presupune introducerea unor imagini ale fiecărui caracter,
sub formă de matrice de pixeli . Valoarea fiecărui element din matrice va fi dată de
luminozitatea fiecărui pixel , sca lată pentru a se încadra într -un anumit interval impus de
constrângerile rețelei (-0.5 – 0.5, sau -1 – 1). Un exemplu concludent:

6 http://www.google.com/recaptcha

15

Fig.4 – exemplu de matrice bazată pe luminozitatea pixelilor din imaginea digitală a unui caracter7
Etapa de clasificare propriu -zisă presupune, printre altele, trecerea în sistemul alb -negru
a imaginii și apoi împărțirea ei în imagini de un singur caracter. Acești pași sunt realizați de
obicei de către o librărie de procesare a imaginilor, nu de către motorul propriu -zis d e OCR.
Apoi, aceste caractere sunt propagate în rețea pentru recunoaștere.
De obicei, pentru o rată de succes mare, este necesar a se cunoaște limba în care este
textul și o bază de date de cuvinte a sa, pentru a se corecta rezultatele obținute.
În prez ent, recunoașterea caracterelor latine nu are o acuratețe de 100% nici măcar în
cazul imaginilor clare. Rata de succes pentru majoritatea softurilor comerciale variază de la 71%
la 98%, potrivit unor statistici [4]. Pen tru atingerea maximului, este în totde auna nevoie de
feedback uman.
În ceea ce privește bibliotecile OCR open -source , cea mai performantă s -a dovedit a fi
Tesseract , care aparține acum de Google și va fi detaliată într -o secțiune următoare.

7 http://www.codeproject.com/KB/dotnet/simple_ocr.aspx

16
II.3 Rețele neuronale artificiale

II.3.1 Structură și comportament

După cum le spune și numele, rețelele neuronale artificiale ( Artificial Neural Networks ,
abreviat ANN ) sunt reprezentări ale unor scheme de învățare supervizată din inteligența
artificială, construite după modelul creierului bio logic. Acesta este privit ca o rețea complexă
alcătuită din unități mici interconectate – neuronii –, care comunic ă prin semnale, rezultând
raționamente inteligente [2].
La un nivel mai abstract, un neuron poate fi privit ca o funcție care, la primirea unor
parametri de intrare , va efectua calcule și va transmite semnal mai departe sau nu . Acești
parametri pot fi din exterior (de la simțuri) sau pot proveni de la alți neuroni și se pot raporta la
un prag, care, dacă este depășit, va determina propagarea semn alului.
ANN -urile simulează acest comportament, bineînțeles, într -un mod mai grosier . Astfel,
ele constau într-un număr de unități (noduri ) care primesc ca parametri de intrare ( input )
numere reale și produc o singură valoare reală, ca parametru de i eșire ( output ). Nodurile sunt
legate între ele prin arce, ce au o anumită pondere (cost) care va fi luată în calcul ul ieșirii .
Inputul unui nod po ate veni fie din exteriorul rețelei , fie de la un alt nod din rețea, iar outputul
poate merge în afara rețelei sau po ate intra în alt nod.
Ca metodă de învățare supervizată, utilizarea ANN -urilor presupune 2 etape. Prima este
cea de antrenare , când avem o serie de exemple (instanțe) și categoria corespunzătoare
fiecăruia , stabilită a priori și vrem ca rețeaua să deducă logica după care s -au făcut asocierile
respective, pentru a putea apoi să clasifice corect orice nouă instanță. Această etapă se bazează
pe ajustarea costului fiecărui arc , după cum vom vedea în cele ce urmează .
Cea de -a doua etapă este cea de clasificare (categorisire) propriu -zisă, când, odată
antrenată rețeaua, i se dă o instanță nouă și trebuie să decid ă în care categorie se încadrează cel
mai bine.

17
Topologia unei ANN arată, schematizat, astfel [1]:
o O mulțime de unități de intrare (input units) , care primesc din exterior datele (pattern –
urile ) ce trebuie să fie propagate în rețea, pentru învă țare sau categorisire și le afișează
sub formă de valori numerice . Acestea formează stratul de intrare (input layer ).
o O mulțime de unități ascunse (hidden units ), care își iau inputul din suma ponderată a
output -urilor unităților din stratul de intrare costul pe fiecare arc de la unitate și
produc propriul output pe baza unei funcții unice pe toată rețeaua , numită funcție prag .
Este denumit ă astfel, deoarece este setată să producă valori mici dacă suma ponderată nu
depășește un anumit prag și valori mai mari, dacă îl depășește. Cum în general, sunt mai
multe unități de intrare care “converg” într -o singură unitate ascunsă, rezultă că numărul
acestora din urmă este, de obicei, mai mic. Ele formează stratul ascuns (hidden layer ).
o O mulțime de unități de ieșire (output units) , care, în procesul de învățare, dictează
categoria în care se încadrează cel mai bine exemplul propagat în rețea. Ele își iau
intrarea analog ca mai sus, din tr-un strat ascuns , iar ieșirea lor este calculată de funcția
prag decisă mai sus . Împreună formează stratul de ieșire (output layer ).
O imagine a unei ANN generale :

Fig.5 – model general de rețea neuronală
artificială de tip feed forward, cu un singur strat ascuns [1]

18
Trebuie menționat e următoarele lucruri:
o toate arcele au costuri asociate (chiar dacă nu au mai fost incluse pentru a nu încărca
imaginea) ;
o mai multe straturi ascunse sunt posibile , intrarea unuia provenind din ie șirea celuilalt de
dinaintea sa .
o există și ANN -uri fără straturi ascunse, numite perceptroni, care au aplicații limitate, dar
vor fi analizate mai jos pentru a facilita trecerea către cele mai complexe.

II.3.2 Clasificare

Există două tipuri de rețele neuronale: rețele cu flux unidirecțional și rețele recurente [2].
O rețea cu flux unidirecțional (feed forward network ) este, practic, u n graf orientat aciclic
în care semnalele merg în aceeași direcție tot timpul . Rețelele de acest tip sunt de obicei
multistratificate, adică nodurile își primesc inputul doar de la straturi precedente și trans mit
outputul doar la straturi ulterioare din structura rețelei. Un exemplu de astfel de rețea este exact
cea ilustrată în Fi g.1 de mai sus.
Rețelele recurente permit cicl uri, ceea ce mărește numărul și complexitatea problemelor
ce pot fi reprezentat e, dar în același timp face mai dificilă analiza și evaluarea rețelei .
După cum am menționat mai sus, problema învățării într -o rețea neuronală se bazează
esențialmente pe asignarea corectă a costurilor pe fiecare arc. Așadar, sunt 2 decizii importante
care trebuie luate înaintea antrenării :
i. Arhitectura rețelei – cum mapăm datele inițiale în nodurile de intrare, câte straturi
ascunse să avem și cum ne folosim de outputul nodurilor de ieșire pentru a trage
concluziile de care avem nevoie.
ii. Funcția prag de calcul a outputului unui nod din inputul primit.

19
Prima problemă se rezolvă experimentând diferite arhitecturi, până când ceea ce obținem
este mai aproape de rezultatul dorit. Răspunsul la cea de -a doua îl vom oferi studiind două tipu ri
principale de ANN -uri: perceptroni și rețele multistratificate.
II.3.3 Perceptroni

Perceptronii sunt ANN -uri fără straturi ascunse si cu un singur nod în stratul de ieșire,
spre care converg toate nodurile de intrare. Astfel, problema arhitecturii se reduce doar la a găsi
o formă convenabilă și relevantă de a transforma exemplele și pattern -urile inițale de antrenare
sau categorisire , în numere reale , pe care să le afișăm în nodurile de intrare.
Pentru perceptroni, se folosesc funcții prag simple ca definiție, de exemplu una care
produce 1, dacă suma ponderată a inputurilor este mai mare decât un anumit prag și -1, altfel.
Vom lua un exemplu concret pentru a clarifica lucrurile.
Exemplu:
[1]Se consideră o ANN antrenată să clasifice o imagine de 2×2 pixeli albi sau negri,
astfel: dacă are 3 sau 4 pixeli negri, este întunecată; altfel, este luminoasă . Putem modela aceasta
printr -un perceptron cu 4 unități de intrare, câte una pentru fiecare pixel, afișând 1 dacă pixelul e
alb și -1 dacă este negru. Dacă alegem costurile ca în imaginea următoare, perceptronul va
categorisi corect orice imagine care resp ectă regulile noastre, lucru care poate fi verificat cu
ușurință.

Fig.6 – model de perceptron care clasifică o imagine de 2×2 pixeli albi sau negri [1]

20
De notat că, în general, costurile pe arce nu sunt aceleași și că valorile lor se iau cel mult
egale cu 1. S -a ales o valoare a pragului cât mai mică, dar aceasta nu era singura opțiune.
Pentru ca un perceptron să îndeplinească sarcina de categorisire cu succes, trebuie folosit,
după cum am mai menționat, un set de instanțe de antrenament pent ru a stabili costurile pe
fiecare arc și pragul pentru funcția aferentă.
Pentru simplificare, în cazul perceptronului, putem considera pragul ca fiind un cost
special, atașat unei muchii ce provine de la un nod de intrare cu ieșirea mereu 1 , ca în imagin ea
de mai jos :

Fig.7 – model de perceptron care trebuie antrenat pe costurile muchiilor și pe prag [1]

21
II.3.3.1 Descrierea algoritmului de antrenare a perceptronilor [1]

1) Inițial, costurile sunt asignate aleatoriu;
2) Instanțele de antrenament sunt folosite una după alta pentru a ajusta costurile pe fiecare
muchie, operaț ie cunoscută sub numele de regula de antrenare a perceptronilor
(perceptron training rule ):
2.1) Dacă exemplu curent, E, este cat egorisit greșit, atunci fiecare cost , pornind din
nodul de intrare cu ieșirea , va suferi transformarea
unde se calculează cu formula :
( ( ) ( ))
unde:
 ( ) – valoarea care ar fi trebuit să rezulte pentru exemplul E;
 ( ) – valoarea care a rezultat de fapt;
 o constantă pozitivă numită rată de învățare (learning rate ), care
controlează cât de departe poate merge ajustarea costurilor într-un pas . Se ia
de obicei o valoare foarte mică, de exemplu 0.1.
3) Pasul 2) se repetă până când toate instanțele de antrenament sunt categorisite corect . Aceasta
se întâmplă atunci când categoria decisă de rețea , adică cea care are output ul cel mai mare,
coincide cu cea cunoscută a priori .
Ajustarea costurilor are ca obiectiv găsirea unei erori globale minime , calculată în
funcție de proporția de exemple categorisite greșit. Astfel, constanta este responsabilă cu
finețea corecturii costurilor, pentru ca îmbunătățirea valorii unuia să nu fie în detrimentul sumei
ponderate totale. Dacă un cost chiar necesită o ajustare mare, atunc i acest lucru se va produce
iterând de mai multe ori prin setul de instanțe de antrenament și nu deodată. Dorim să evităm pe
cât posibil intrarea într -un minim local , din care ne va fi mai greu să ieșim, pentru a atinge
minimul global.

22
II.3.3.2 Aplicațiil e perceptronilor

După cum s -a arătat în lucrarea [3], perceptronii pot fi folosiți atunci când funcția de
categorisire este liniar separabil ă. Așadar, scopul funcției este apropiat de cel al funcțiilor
booleene, iar graficul său permite trasarea unei linii (sau un plan, dacă gândim în spațiu) care să
delimiteze clar, de o parte și de alta, valorile posibile. De aici și aplicabilitatea redusă a
perceptronilor în forma lor clasică.
Ca exemplu, vom lua chiar funcțiile booleene AND, OR și XOR, care pot afi șa valorile 1
și -1 (în loc de 0) după regulile cunoscute:
 AND( ) = 1 ⇔ , altfel -1
 OR( ) = 1 ⇔ , altfel -1
 XOR( ) = 1 ⇔ , altfel -1
Funcțiile AND și OR sunt liniar separabile și deci pot fi modelate cu ajut orul
perceptronilor, dar funcția XOR nu este liniar separabilă și deci nu poate fi reprezentată prin
acest tip de ANN. Următoarele figuri l ămuresc acest e concept e:

Fig.8 – funcțiile booleene AND și OR modelate prin perceptroni [1]

23

Fig.9 – graficele funcțiilor booleene care demonstrează dacă sunt sau nu liniar separabile [1]
II.3.4 Rețele neuronale multistratificate

După cum le spune și numele, sunt ANN -uri care au cel puțin un strat ascuns și pot fi
folosite pentru a modela o sumedenie de concepte și funcții , spre deosebire de perceptroni .
O altă diferență majoră este dată de funcția prag, care este de această dată diferențiabilă.
Funcțiile prag de la perceptroni nu sunt continue, deci nici diferențiabile.
O funcție care este folosită foar te des în acest scop este funcția sigma , definită astfel:
( )
,
unde S este suma ponderată primită ca input, iar e este baza logaritmilor naturali, egală cu
2.718…
Un exemplu de ANN multistratificată este următoarea:

Fig.10 – exemplu de rețea neuronală multistratificată, ce folosește funcția sigma ca funcție prag [1]

24
Avem mai jos valorile calculate pentru cazul când inputul (I1, I2, I3) = (10 30, 20) ,
categoria cu outputul cel mai mare , O2, fiind cea indicată de rețea în această fază :

Fig.11 – exemplu de valori calculate pentru rețeaua din Fig.10 [1]

25
II.3.4.1 Rutina de retropropagare (backpropagation) [1]

1) Ne modelăm arhitectura rețelei, care va conține atât noduri de intrare și ieșire, cât și noduri
ascunse, toate calculându -și ieșirea prin funcția sigma . Trebuie avut în vedere că, dacă
numărul de noduri interne este prea mare comparativ cu numărul instanțelor de antrenament,
algoritmul nu va generaliza suficient rețeaua, iar dacă numărul de noduri interne este prea
mic, rețeaua poate eșua în găsirea unei configurații compatibile cu setul de instanțe de
antrenament [2];
2) Inițial, costurile sunt asignate aleatoriu , cu valori între -0.5 și 0.5 ;
3) Instanțele de antrenament sunt folosite una după alta pentru a ajusta costurile pe fiecare
muchie (costuri notate cu , indicând arcul de la nodul i la nodul j) . Dacă un exemplu E
este încadrat în categoria greșită , atunci se urmează următorii pași:
3.1) Se calculează valorile așteptate, (E), pe care fiecare unitate de ieșire ar trebui s ă
o producă pentru E (1 pentru categoria corectă și 0 pentru celelalte) , valorile
efective rezultate la pasul curent pentru acestea, (E), precum și valorile
rezultate pentru nodurile ascunse , (E);
3.2) Pentru fiecare nod k de ieșire, se calculează eroarea specifică ( error term ):
( )( ( ))( ( ) ( )).
3.3) Cu ajutorul acestora, se calculează erorile specifice pentru nodurile ascunse (de
aici și termenul de retropropagare ):
( )( ( ))∑

3.4) Având calcula te aceste valori ale erorilor asociate cu fiecare nod (ascuns sau de
ieșire), putem calcula , care se va aduna la ; pentru costurile arcelor dintre
un nod de intrare și un nod ascuns :
,

26
iar pentru costurile arcelor dintre un nod ascuns și un nod de ieșire :
( )
4) După fiecare repetare a pasului 3), o condiție de terminare a algoritmului este
verificată. Aceasta deoarece, pentru această metodă, nu este garantată găsirea unor
costuri care să nu ducă la absolut nicio categorisire greșită a instanțelor de
antrenament . Așadar, o posibilă condiție de terminare (dar nu întotdeauna eficientă)
ar fi un număr limită (de obicei mic) de exemple clasificate greșit.

27
II.3.5 Concluzii: a plicabilitatea rețelelor neuronale artificiale

Când și pentru ce sarcini putem folosi ANN -urile în practică?
1) Atunci când conceptul care trebuie învățat poate fi “codificat“ de o funcție cu valori
reale , ceea ce înseamnă că atât inputul , cât și outputul pot fi mapat e la un set de
numere reale;
2) Dacă perioada de antrenare poate fi oricât de lungă (de la câteva minute la câteva
ore). Mulți factori, printre care număr ul instanțelor de antrenament, valoarea aleasă
pentru rata de învățare, arhitectura rețelei , influențează drastic timpul de învă țare;
3) Atunci când nu este important pentru utilizatori să înțeleagă exact calculele după care
funcționează rețeaua. Metoda utili zării ANN -urilor este de tip black box: observăm
rezultatele, dar nu putem privi “înăuntru”, ne este greu să analizăm mecanismele
interne;
4) Când, odată antrenată rețeaua, sarcina de categorisire trebuie să decurgă rapid;
5) Pentru probleme care nu au un algori tm general de rezolvare, sau ar fi prea complex
de construit unul.
Aplicații concrete care folosesc ANN -uri:
– recunoașterea caracterelor ;
– recunoașterea vorbirii ;
– recunoașterea semnalelor;
– predicția funcți onală,;
– modelarea sistemelor.

28
II.4 Tesseract
II.4.1 Scurt istoric

Dezvoltarea acestui motor OCR open -source a fost inițial suținut ă de către compania
Hewlett – Packard, între anii 1984 -1994, figurând în top 3 , conform UNLV Annual Test of OCR
Accuracy din 1995. Ulterior, pân ă în 2006, a intrat într -un con de umbr ă, pân ă când a fost
preluat de c ătre Google, de care aparține pân ă astăzi. Progresele aduse de atunci au fost
semnificative, poate și datorit ă faptului c ă, devenind open -source , și-au putut aduce contribuția și
sugestiile numeroși dezvoltator i.
Proiectul include și o bibliotec ă de proce sare a imaginilor – Leptonic a8 – și poate în
prezent recunoaște caractere din peste 40 de limb i, din varii formate de imagini (*.jpg, *.bmp,
*.tiff, *.png etc.).
Tesseract nu poate fi folosit îns ă ca un produs comercial și nici m ăcar ca unul de sine
stătător, deoarece , pe lâng ă lipsa unei interfețe grafice, nu conține func ții pentru analiz a avansat ă
a layout -ului paginilor sau pentru formatarea textului recunoscut , ca alte produse comerciale, gen
OmniP age9. Acest neajuns are la baz ă perioada dezvolt ării în laboratoarele HP, care aveau deja
unelte independente orientate înspre asemenea sarcini și care nu sunt open -source . Ele puteau fi
așadar îmbinate și Tesseract nu avea motive s ă conțină propriile astfel de mecanisme. Google nu
a preluat ulterior și aceste unelte, ele r ămânând sub proprietatea HP -ului. Așadar Tesseract poate
fi folosit în prezent doar ca o bibliotec ă inclus ă în cadrul unui proiect, focalizat ă pe recunoașterea
caracterelor, sarcina de procesare a imaginii date în diferite formate, revenind bibliotecii
Leptonica. Afișarea, eve ntual formatarea rezultatului, d evine sarcina programatorului.
Ultima versiune10, 3.02, lansat ă în februarie 2012, are îmbun ătățiri în ceea ce privește
detecția diacriticelo r, a alineatelor, a tab -urilor, precum și funcții noi, precum :
– detecția caracterelor din limbi a c ăror direcție de scriere este de la dreapta la stânga (ex.
limbile arabice) ;

8 http://www.leptonica.com/
9 http://www.nuance.com/for -business/by -product/omnipage/index.htm
10 http://tesseract -ocr.googlecode.com/svn/trunk/Re leaseNotes

29
– recunoașterea caracterelor din mai multe limbi prezente în ace lași document;
– detecția paragrafelor;
– un detector de ecuații experimental.
II.4.2 Arhitectur ă și flux de lucru

Precum am menționat anterior, Tesseract presupune c ă inputul este o imagine binar ă (un
bitmap ), eventual cu regiuni polig onale de text definite (asem ănătoare paragrafelor) . Arhitectura
general ă este de tip pipeline , cu unele elemente de inova ție. Vom detalia în subsecțiunile de mai
jos fiecare pas, incluzând algoritmii și unele formule folosite [7].
II.4.2.1 Gruparea biților imaginii în Blob -uri

Primul pas, care a p ărut o decizie costisitoare în termeni de eficienț ă la momentul
respectiv, const ă în analizarea felului în care componentele imaginii sunt conectate între ele, în
termeni de contururi ( outline s) imbricate . Aceste rezultate sunt stocate în structuri numite
Blobs (Binary Large Objects ). Ele reprezint ă o colecție de biți stocați ca o singur ă entitate.
Printre avantajele acestei abord ări, de a detecta practic “copiii” și “nepoții” unui contur,
se num ără detec ția cu ușurinț ă a textului alb pe fundal negru, invers faț ă de normal.
II.4.2 .2 Alcătuirea liniilor de text

Al doilea pas presupune gruparea blob-urilor în linii de text . Algoritmul funcționeaz ă și
pe text deformat oblic ( skewed ) (Fig. 1 2), fără a fi nevoie de “îndreptare”, operație care ar d ăuna
calității imaginii.
Fig.12 – exemplu de text deformat oblic ( skewed )11

11 http://www.yearbooks.biz/?event=FAQ.Detail&faq=12

30
Presupunând c ă etapa de analiz ă a layout -ului paginii d ă Tesseract -ului ca parametri de
intrare regiuni de text aproximativ uniform ca dimensiune, pentru a elimina situații precum drop
caps (Fig. 13) sau caractere care se intersecteaz ă vertical, se aplic ă un filtru percentil ă pentru
înălțime ( percentile height filter ).

Fig.13 – exemplu de drop caps12
Definiția percentilei13: o valoare din setul de date , asociat ă cu un număr de ordine ( rank)
în secvenț ă cresc ătoare , ce ne spune ce procent din date se g ăsește sub valoarea respectiv ă. Spre
exemplu, a 20 -a percentil ă e valoarea sub care se g ăsesc 20% din observații. Cea de -a 25-a
percentil ă se întâlnește frecvent sub termenul de prima quartil ă, iar a 50 -a percentil ă, sub
termenul de median ă sau a doua quartil ă.
Mediana în ălțimii aproximeaz ă dimensiunea textului din acea regiune și astfel, pot fi
filtrate blob-urile care sunt mai mici decât o anumit ă fracțiune din aceast ă median ă,
considerându -le semne de punctuație, diacritice sau noise.
Blob -urile filtrate sunt apoi mai ușor de încadrat într -o gril ă de linii paralele,
nesuprapuse, dar înclinate. Pentru aceasta, m ai întâi se sorteaz ă după abscis ă, astfel putând
asigna blob-urile la o unic ă linie, chiar și la o pant ă a textului mai mare (acel skew de care
menționam anterior).
Ulterior, liniile de baz ă (baseline -urile ) sunt aproximate prin calculul celei mai mici
mediane a p ătratelor ( least median of squares sau LMS, descris ă pe larg în [9]. Se bazeaz ă în
principiu pe minimizarea medianei p ătratelor erorilor reziduale, rezultate în urma aproxim ării
unor coeficienți de ecuații liniare). Ca idee, baseline -urile se presupune c ă sunt partițiile cele mai
populate de biți .

12 http://safalra.com/web -design/typography/css -drop -caps/
13 http://www.regentsprep.org/regents/math/algebra/AD6/quartiles.htm

31
Blob -urile care au fost filtrate în urma aplic ării medianei în ălțimii sunt apoi încadrate în
aceste linii. Cele care se suprapun pe orizontal ă măcar pân ă la jum ătate sunt grupate cu baza
corect ă de care aparțin, cum e în cazul diacriticelor sau a unor caractere fragmentate.
Mai jos avem o figur ă care menționeaz ă denumirile standard din tipografie ale anumitor
linii de încadrare a cuvintelor, termeni pe care îi vom folosi în cele ce urmeaz ă.

Fig.1 4 – denumirile liniilor de încadrare a cuvintelor în tipografie14

II.4.2.3 Alc ătuirea baseline -urilor

Odat ă ce au fost g ăsite liniile de text, baseline -urile, precum și celelalte linii importante
ilustrate în Fig. 14 , sunt aproximate mai precis prin aplicarea unor funcții spline p ătratice asupra
lor. Inițial, liniile au fost oblice. Acum sunt curbate , un element de inovație pe care îl aduce
Tesseract în rândul motoarelor OCR.

Fig.15 – liniile importante d in fig. 14 sunt cele colorate , ușor curbate de aceast ă dată [7]

Prin inspecția atent ă a figurii de mai sus, observ ăm că toate liniile sunt “paralele” și ușor
curbate. Se observ ă că ascender line , cea cyan (la printare, gri deschis), este curbat ă în raport cu
linia neagr ă dreapt ă de sus.

14 http://en.wikipedia.org/w iki/File:Typography_Line_Terms.svg

32
II.4.2.4 Separarea în cuvinte

Aceast ă etapă se bazeaz ă foarte mult pe distanța dintre caractere. Tesseract parcurge
fiecare linie de text g ăsită pentru a testa dac ă fontul folosit ocup ă același spațiu o rizontal pentru
fiecare caracter (fixed -pitch font sau monospaced font , cum este fontul Courier , de exemplu ).
Dacă da, atunci împarte linia direct în caractere, cuvintele putând fi ref ăcute ușor de aici
(deoarece și spațiul ocup ă aceeași l ățime) . Nu se mai aplic ă segmentatorul ( chopper ) și
asociatorul de la pa sul urm ător, de recunoaștere a cuvintelor.

Fig.16 – exemplu de cuvânt cu caractere fixed -pitch [7]

Dacă însă fontul nu respect ă regula de mai sus ( proportional font ), sarcina de împ ărțire
în cuvinte este mult mai grea. Figura de mai jos ilustreaz ă niște probleme tipice în acest sens .

Fig.17 – exemplu de text greu de împ ărțit în cuvinte [7]
Spre exemplu, nu exist ă deloc spațiu orizontal între chenarele ( bounding boxes ) care
încadreaz ă “of” și “financial”, iar spa țiul dintre “erated” și “junk” este mai mic decât normal .
Tesseract rezolv ă unele (dar nu toate) din aceste probleme m ăsurând golurile ( gaps )
dintr -un anumit interval dintre linia de baz ă si linia median ă (mean line ). Valorile apropiate de
prag devin fuzzy și o decizie final ă va fi f ăcută după etapa de recunoaștere a cuvintelor.

33
II.4.2.5 Segmentarea maximal ă a cuvintelor în caractere

Outputul segment ării de la etapa anterioar ă este dat clasificatorului. Dac ă am avut de -a
face cu font non-fixed -pitch , rezultatele nu vor fi satisf ăcătoare , cel ma i probabil și atunci se
aplic ă etape suplimentar e de segmentare.
Altfel, în special în cazul în care sunt caractere unite care nu au putut fi separate prin
metoda m ăsurării golurilor, se încearc ă segmentarea blob-ului în vârfurile concave din
aproximarea poligonal ă a conturului (fig. 18 ). Fiecare asemenea vârf are fie un alt vârf concav
opus sau un segment de linie. Primul caz are prioritate la segmentare . Spre exemplu , în im aginea
de mai jos, demarcarea va avea loc în punctele unde “r” se un ește cu “m”.

Fig.18 – puncte concave din contur ( outline ) pentru segmentarea caracterelor unite [7]
Fiecare segmentare, chiar dac ă nu îmbun ătățește rezultatul clasific ării, este p ăstrată
pentru a fi utilizat ă ulterior de c ătre asociator.
Dacă după ce s-au epuizat toate posibilit ățile de segmentare, cuvântul tot nu este
recunoscut cu succes, se paseaz ă unui asociator . Acesta aplic ă algoritmul A* ( best first ) de
căutare printre posibile combinații între elementele segmentate maximal, care nu au fost
clasificate anterior. În figura de mai jos este prezentat un exemplu în care aceast ă strategie se
dovedește util ă:

34

Fig.19 – combinații cu succes între blob-uri segmentate maximal [7]
II.4.2 .6 Clasificatorul de caractere

Versiunile anterioare de Tesseract foloseau pentru recunoașterea caracterelor și a
cuvintelor, segmentele din aproximarea lor poligonal ă. Aceast ă abordare, luat ă însă ca atare, nu
s-a dovedit robust ă în cazul caracterelor fragmentate, dup ă cum se poate vedea în imaginea de
mai jos :

Fig.20 – a) aproximarea poligonal ă a caracterului “h” normal (prima imagine), care difer ă de b)
aproximarea poligonal ă a caracterului “h” în cazul fragment ării;
c) trăsături suprapuse prototipurilor.

Soluția const ă nu în comparația direct ă dintre tr ăsăturile caracterului de identificat și
proto tipurile din setul de antrenare, ci în computarea unei distanțe între acestea, care sa fie cât
mai mic ă. Pentru a se realiza acest lucru, prototipurile din etapa de antrenare sunt laturi ale
poligonul ui ce aproximeaz ă caracterul, pe când tr ăsăturile extrase în etapa de recunoaștere sunt

35
segmente unitate (normalizate) . Acestea sunt confruntate many -to-one cu trăsăturile clusterizate
ale prototipurilor.
După cum se observ ă în fig. 20 c), liniile scu rte și groase reprezint ă trăsăturile caracterului
dat spre identificare, iar segmentele subțiri de dedesubt, pe cele ale prototipului (litera “h”). Cele
mai multe se potrivesc, așadar distanța care va fi computat ă va fi mic ă. Singurul dezavantaj este
costu l calcul ării acestei distanțe, care este destul de mare.
Se încearc ă recunoașterea, pe rând, a fiec ărui cuvânt, folosind un clasificator static (care
se bazeaz ă pe re țele neuronale , dar și pe clusterizare ). Fiecare cuvânt care este identificat cu o
rată de succes satisf ăcătoare, este pasat clasificatorului adaptiv ca instanț ă de antrenament. Pe
baza acestui input , el are ocazia s ă clasifice mai bine cuvintele care vor fi date ulterior spre
clasificare.
Întrucât clasificatorul adaptiv e posibil s ă fi “înv ățat” ceva util prea târziu pentru a putea
aduce o contribuție notabil ă în cazul caracterelor aflate mai înainte în pagin ă, imaginea este
parcurs ă încă o dat ă, pentru a se încerca o a doua recunoaștere a cuvintelor care nu au putut fi
identificate în prima etapă.
Faza final ă rezolv ă datele fuzzy și verific ă ipoteze alternative pentru x-height (Fig. 15),
pentru a localiza “majusculele mici” ( small caps ):

Fig.21 – exemplu de “majuscule mici” ( small caps )15

II.4.2 .7 Analiza lingvistic ă

Fiecare propunere de cuvânt rezultat ă în urma modulului de recunoaștere de cuvinte,
după clasificarea caracterelor, este confruntat cu o list ă de cuvinte din mai multe categorii:

15 http://en.wikipedia.org/wiki/File:True_vs_Scaled_Small_Caps.svg

36
– cel mai frecvent cuvânt;
– cuvânt de dicționar;
– cuvânt numeric;
– cuvânt UPPER case;
– cuvânt lower case;
– cuvânt lower case cu majuscul ă la început;
– cuvântul ales de cele mai multe ori de c ătre clasificator.
Din fiecare categorie, se alege cea mai bun ă variant ă și se adaug ă într-o list ă scurt ă de
opțiuni , iar varianta final ă este dat ă de distanța cea mai mic ă dintre cuvântul recunoscut și
cuvintele selectate. Ponderea fiec ăreia din categoriile de mai sus este o constant ă diferit ă de
celelalte.
Toate aceste categorii, în afar ă de ultima, presupun s ă se cunoasc ă limba în care este
textul și s ă fie furnizate seturi de date antrenate pentru fiecare limb ă în parte. Rezultatul
antren ării, care va fi pasat clasificatorului, trebuie dat într -un fișier inclus în proiect , cu extensia
.traineddata . Pe Google Repository -ul proiectului, sunt date indicați i despre cum se poate realiza
aceast ă antrenare folosind uneltele puse la dispoziție de ei16. Se detaliaz ă și ce structur ă ar trebui
să aibă fișierele efective cu tr ăsăturile fiec ărui set de caractere, a punctuației specifice, un
dicționar de cuvinte și mul te altele. Exist ă momentan asemenea fișiere pentru cel puțin 40 de
limbi și dialecte, disponibile pentru desc ărcare , în secțiunea http://code.google.com/p/tesseract –
ocr/downloads/list .

16 http://code.google.com/p/tesseract -ocr/wiki/TrainingTesseract3 – pentru antrenarea caracterelor pentru
versiuni de Tesseract 3.0x

37
II.4.3 Concluzii

Tesseract este la ora actual ă cel mai performant motor OCR open -source , însă are o rat ă
de succes sub majoritatea produselor comerciale, poate și datorit ă perioadei de latenț ă dintre anii
1995 -2006.
Punctul s ău forte este dat de comparația dintre tr ăsăturile caracterului ce se cere a fi
recunoscut și prototipul antrenat, bazat ă pe calculul unei distanțe și nu pe teste triviale de
egalitate. Alte plusuri ar fi:
(+) folosirea baseline -urilor curbate, sporind acuratețea detect ării liniilor;
(+) faptul c ă poate detecta cu ușurinț ă text alb pe negru;
(+) faptul c ă funcționeaz ă pe text înclinat ( skewed );
(+) faptul c ă recunoaște cu ușurint ă caracterele fragmentate ;
(+) faptul c ă folosește atât un clasificator static, cât și unul adaptiv.
Principalele minusuri și îmbun ătățiri care ar putea fi aduse :
(-) ineficiența dat ă de strategia segmentare -asociere, precum și posibilitatea de a pierde anumite
segmente importante astfel;
(-) folosirea funcțiilor spline p ătratice în loc de spline cubice [10], pentru aproximarea baseline –
urilor ;
(-) calculul distanței dintre caracterul ce se cere a fi recunoscut și prototip este costisitor; o
îmbun ătățire ar fi schimbarea inputului c ătre clasifi cator din aproximarea poligonal ă a
caracterului, în conturul său efectiv, brut , ca secvenț ă de pixeli [7];
(-) lipsa unui model de n -grame bazat pe modele Markov ascunse ( Hidden Markov Models )
pentru a recunoaște mai bine secvențe de c aractere grupate, care , individual, creeaz ă ambiguit ăți.
Spre exemplu [11], dacă "I" nu poate fi recunoscut f ără ambiguit ăți, deoarece "l" poate avea
aceeași form ă în unele fonturi, combinația “It" poate fi mult mai probabil ă decât “lt”.

38
Tesseract este implementat în C++ , dar datorit ă numărului mare de cereri și a utilit ății
cresc ute, au fost create wrappere în diferite limbaje de programare. O list ă complet ă a acestora,
precum și diferite AddOn -uri și proiecte open -source bazate pe acest motor OCR , se g ăsesc la
adresa http://code.google.com/p/tesseract -ocr/wiki/AddOns . Voi detalia în secțiunea dedicat ă
descrierii aplicație i cum am realizat eu concret integrarea .

39
III. Recunoașterea entit ăților textuale de tip nume

III.1 Introducere în domeniul Extragerii de Informații

Procesul de recunoaștere a entitӑților textuale de tip nume , mai cunoscut sub termenul de
Named Entity Recognition (NER), este o sarcin ă din categoria de Extragere de Informații
(Information Extraction ). Aceasta se ocupӑ cu selectarea, structurarea și combinarea unor date
explicite sau implicite din diferite texte, care sunt apoi folosite în scopuri precise . [20] Printre
acestea se numӑrӑ:
– realizarea de statistici ;
– detectarea sentimentelor ;
– detectarea relațiilor dintre persoane;
– reconstituirea unor situații ;
– ordonarea cronologicӑ a unor evenimente;
– clasificarea domeniului de care aparține textul etc.
Datoritӑ dificultӑții crescute, s -au dezvoltat tehnici focalizate pe texte aparținând unui
anumit domeniu precis (științific, militar, publicistic, juridic etc) . Odatӑ generalizate, acestea nu
mai dau rezultate la fel de bune.
Începând din anul 1987, au fost organizate competițiile din seria MUC ( Message
Understanding Conferences ), pentru a încuraja dezvoltarea de metode inovative și eficiente în
acest vast domeniu al extragerii de informații. Evaluarea și compararea rezultatelor au presupus
stabilirea unor standarde și metrici, dintre care cele mai cunoscute sunt precision, recal l și F-
measure. Acestea se definesc dupӑ cum urmeazӑ:

40
* + * +

* + * +
* +

Fig.22 – Formulele metricilor precision, recall și F-Measure17
III.2 Definirea recunoașterii entitӑților de tip nume

Sarcina de extragere sau adnotare a numelor proprii presupune identificarea unor entitӑți
semnificative (precum persoane, organizații, locații, date, numere), plasate într-un context
anume. În lipsa unor asemenea adnotӑri, este mult mai dificil, sau chiar imposib il, de efectuat
alte procesӑri sau de aplicat alți algoritmi, precum cei de detectare a sentimentelor sau a
relațiilor.
Un exemplu de text adnotat astfel este:

Fig.23 – Un exemplu adnotat cu entitӑți semnificative [21]
Este foarte importantӑ analiza pe bazӑ de context, pentru dezambiguizare. Spre exemplu,
dacӑ dorim sӑ cӑutӑm documente referitoare la țigӑri, cӑutând mențiuni ale companiei “Phillip
Morris”, nu dorim sӑ primim și documente care conțin acest nume, referindu -se însӑ la o altӑ
persoanӑ. [21]

17 http://en.wikipedia.org/wiki/Precision_and_recall

41
III.3 Tehnici pentru NER

De-a lungul timpului au fost dezvoltate numeroase tehnici pentru aceastӑ sarcinӑ , mai
simple sau mai laborioase, în funcție de context, resurse și aplicabilitate.
Printre cele mai simple metode se numӑrӑ aplicarea de expresii r egulate , care sunt ca
niște patternuri ce trebuie regӑsite în text. Aceastӑ metodӑ face însӑ dificil de clasificat entitӑțile
în categorii și poate conduce la extragerea și a unor cuvinte scrise cu majusculӑ, dar care nu sunt
entitӑți. De asemenea, în cazu l unui text capitalizat complet, sunt aproape inutile.
O altӑ metodӑ, bazatӑ pe tehnica mult mai generalӑ de dictionary matching , presupune
alcӑtuirea unei liste publice foarte mari de nume ( gazetteers ), împӑrțite în categorii și apoi
confruntarea ei cu textul, folosind algoritmi eficienți de cӑutare în șiruri, precum Aho -Corasick
[22]. Totuși, date fiind dimensiunile gazetteer -ului și ale textului, metoda poate deveni
ineficientӑ și, oricum, nu existӑ asemenea liste exhaustive. De asemenea, nici prin ace astӑ
metodӑ nu se poate realiza dezambiguizarea unui nume, în funcție de contextul în care a fost
gӑsit. De obicei se apeleazӑ la aceastӑ metodӑ în etapa de validare a unor rezultate obținute prin
mijloace mai elegante, bazate pe învӑțarea supervizatӑ sau nesupervizatӑ.
Pe lângӑ dezambiguizare, m otivul principal pentru care se apeleazӑ la aceste metode din
inteligența artificialӑ îl reprezintӑ necesitatea de a clasifica și entitӑți care nu sunt în baza de date
predefinitӑ, dar pot fi adӑugate, dacӑ dobânde sc un scor suficient de bun în urma procesului de
clasificare. Este nevoie de un sistem capabil sӑ deprindӑ el singur reguli dupӑ care sӑ clasifice
noi entitӑți în mod contextual , iar factorul uman sӑ intervinӑ doar pentru a corecta aceste
rezultate.
Adnot area manualӑ a unui volum mare de texte a putut servi la obținerea unor date de
antrenament pentru metoda de învӑțare supervizatӑ , folosindu -se și de un sistem de reguli
gramaticale specifice fiecӑrui limbaj și de statistici . Abordarea a avut rezultate bun e, mai ales cӑ
aceastӑ adnotare, deși laborioasӑ, se executӑ o singurӑ datӑ.
Deoarece pentru învӑțarea supervizatӑ este nevoie de un numӑr mare de instanțe pozitive
și negative, cercetӑrile actuale sunt orientate în direcția gӑsirii de metode de învӑțare

42
nesupervizatӑ , care descoperӑ patternuri în texte și le grupeazӑ dupӑ similaritӑți , generând
clustere .
III.4 LingPipe

Cele mai performante unelte pentru NER sunt cele de la universit ățile din Illinois18 și
Stanford19, dar sunt aplicații care necesitӑ multe resurse și au un cost computa țional mult prea
ridicat pentru a pute a fi folosite pe telefonul mobil. De aceea, am ales o soluție de o acuratețe
puțin mai joas ă, dar apropiat ă, îns ă mult mai lightweight , mai ușor de folosit și mai bine
documentat ă: LingPip e [16] .
Biblioteca utilizeazӑ o combinație de metode din cele descrise mai sus: învӑțare
supervizatӑ pe baza unui model statistic, dictionary matching , expresii regulate , sub interfața
Chunker . Modelele statistice necesitӑ date de antrenament adnotate dup ӑ tipurile lor, din același
domeniu ca textele pe care se va aplica apoi clasificarea. Spre exemplu, dacӑ folosim sistem
antrenat pe un model cu date din știri (unde se folosesc des formule de adresare precum Mr.) și
apoi rulat pe texte de pe bloguri, risc ӑm sӑ pierdem informații importante , precum adrese de e –
mail.
Biblioteca oferӑ 3 modele antrenate deja pe un numӑr mare de date furnizat de MUC -6
(ediția MUC din 1995 ) din 3 domenii, toate cu termeni în englezӑ:
– Știri (cel folosit în aplicația mea) ;
– Geneticӑ ;
– Biochimie ;
LingPipe folosește 3 tipuri de NER statisti c, fiecare aplicând un alt algoritm pentru a
ajunge la rezultatul sau rezultatele finale. Unele din ele oferӑ mai multe variante, care pot fi
selectate pe baza scor urilor lor. Ele sunt prezent ate în subsecțiunile ce urmeazӑ.

18 http://cogcomp.cs.illinois.edu/page/software_view/NETagger
19 http://nlp.stanford.edu/software/CRF -NER.shtml

43
III.4.1 Algoritmul Best First pentru LingPipe Named Entity Recognizer

Descrierea algoritmului este urmӑtorul , pentru cazul general al unui graf :

Fig.2 4 – Algoritmul Best-First [2]
Pentru a putea realiza o ordine între elemente , avem nevoie de o funcție euristicӑ de cost
asignatӑ, drept metricӑ a îmbunӑtӑțirii rezultatului parțial dupӑ fiecare iterație . Se observӑ cӑ , la
fiecare pas, se alege cel mai bun rezultat dintre cele existente atunci în structura de date.
Exemplu de ieșire a algoritmului, pentru un model antrenat pe date din geneticӑ:

Fig.2 5 – Exemplu de output pentru un First -Best Chunker LingPipe [16]
Chunkerul returneazӑ poziția de început și de sfârșit a fiecӑrei entitӑți în textul primit,
precum și tipul cӑreia îi aparține.
Este cel mai rapid algoritm, dar nu cu rezultatele cele mai bune.

44
III.4.2 Algoritmul N -Best pentru LingPipe Named Entity Recognizer

Spre deosebire de algoritmul prezentat anterior , nu se pӑstreazӑ doar cel mai bun rezultat
dupӑ fieca re iterație, ci și ipoteze alternative, în ordinea probabilitӑții lor. Un exemplu de ieșire
pe același model ca mai sus:

Fig.2 6 – Exemplu de output pentru un N-Best Chunker LingPipe [16]
Rezultatele sunt returnate în ordinea descendentӑ (logaritm în baz a 2) a probabilitӑții
mixte ( joint probability ). Astfel, dacӑ p1 = -182.735, iar p2 = -183.398, vom putea calcula
simplu cu cât este mai probabil primul rezultat fațӑ de al doilea:

Fig.2 7 – Cum se calculeazӑ joint probability [16]
Astfel, primul rezultat este de 1.62 ori mai probabil decât al doilea.
Algoritmul este mai lent decât First -Best, dar are rezultate mai bune.

45
III.4.3 Algoritmul Confidence pentru LingPipe Named Entity Recognizer

Acest algoritm este construit tot pe baza algoritmului de mai sus, însӑ returneazӑ entitӑțile
gӑsite ( chunks ) în ordinea probabilitӑții lor fațӑ de text: P(chunk / text) . Scorul obținut pentru
fiecare entitate se considerӑ ca fiind un log2 (logaritm în baza 2), de aceea, pentru o afișare mai
sugestivӑ, se ridicӑ 2 la puterea acestui scor. Exemplu de output al acestui algoritm, folosind
același model din geneticӑ :

Fig.2 8 – Exemplu de output pentru LingPipe Confidence Chunker [16]

Astfel, rezultatele sunt afișate în ordinea descrescӑtoare a confidenței.
Acest algoritm este util pentru a reflecta gradul de incertitudine al NER -ului pentru
fiecare entitate, nu pentru a afla care este cea mai bunӑ la fiecare pas .
Este cel mai lent dintre algoritmi, dar și cel cu rezultatele cele mai bune și mai ușor de
procesat, motive pentru care l -am ales în aplicația mea.

46
III.5 Concluzii

Extragerea entitӑților de tip nume nu este o sarcinӑ ușoarӑ dacӑ dorim și clasificarea
acestora în funcție de context. Metodele directe precum aplicarea de expresii regulate sau
utilizarea gazetteer -urilor nu dau rezultate satisfӑcӑtoare și nu sunt ușor de extins pe orice fel de
texte. Este nevoie ca un sistem sӑ poatӑ clasifica ușor entitӑți din afara ariei de texte cu care este
obișnuit, de unde rezultӑ necesitatea aplicӑrii unor metode de învӑțare supervizatӑ, semi –
supervizatӑ sau chiar nesupervizatӑ , care sӑ minimizeze pe cât posibil cantitatea de adnotӑri
manuale. Gazetteer -urile pot fi folosite pentru validare.
Biblioteca LingPipe folositӑ s -a dovedit a fi o alegere bunӑ pentru o aplicație pe telefon,
deoarece funcționeazӑ pe bazӑ de model antrenat, f ișier care se descarc ӑ o singurӑ datӑ și apoi
este stocat pe cartela SD. Așadar nu a fost necesar sӑ obțin și gazetteer -uri. De asemenea, fiind
textul scurt, timpul de execuție este acceptabil (câteva secunde).
Lungimea textului, care poate sӑ nu conținӑ toate pӑrțile de vorbire necesare stabilirii
unui context , este însӑ și o cauzӑ a unor rezultate eronate. Acestea sunt corectate printr -o
combinație de expresii regulate, cӑutare în bazӑ de date, euristici personale și feedback de la
utilizator, aspecte p e care le voi detalia în secțiunea din descrierea aplicației destinatӑ acestui
modul.

47
IV. Arhitectura aplicației

Arhitectura unei aplicații, în general, este deosebit de important ă în termeni de întreținere
și extindere, iar când vorbim de o aplicație mobi lă, unde resursele înc ă sunt mai reduse decât pe
un calculator, devine esențial ă și în termeni de funcționare.
Modelul arhitectural pe care l -am respectat se bazeaz ă pe șablonul general structurat pe 3
nivele ( 3-tier architecture20), în care elementele de interfață, de procesare și datele sunt separate.
Ca funcționalitate, exist ă 4 module principale: OCR , traducere , extragere entit ăți textuale
semnificative și augmentare cu informații specifice.
Le voi detalia pe fiecare din acestea în cele ce urmeaz ă, prec um și cum se conecteaz ă între
ele. În principiu, pentru a putea obține rezultate maxime de pe urma acestei aplicații, se recomand ă o
versiune de Android cel puțin egal ă cu 3.2 ( HoneyComb21, pentru tablete) și pentru telefon, 4.0 (Ice
Cream Sandwich22).

IV.1 Modulul OCR

IV.1.1 Funcționalitate general ă

Acest modul se ocup ă cu recunoașterea textului dintr -o regiune de interes selectat ă
manual de c ătre utilizator, pentru a nu conține elemente de fundal inutile. Primește ca parametru
de intrare un bitmap, alb-negru, pentru a se putea aplica apoi pe el tehnica numitӑ Adaptive
Thresholding [18], în urmӑ cӑreia se obține o imagine binarӑ. De asemenea, set ările includ:
– limba care se dorește a fi recunoscut ă;

20 http://en.wikipedia.org/wiki/Multitier_architecture#Three -tier_architecture
21 http://developer.android.com/about/versions/android -3.2.html
22 http://developer.android.com/about/versions/andro id-4.0-highlights.html

48
– modul de segmentare a paginii – cum s ă fie tratat ă și segmentat ă/preprocesat ă imaginea;
exemple : ca o singur ă linie de text, ca un singur cuvânt, ca o coloan ă de text , detecția
doar a orient ării și a tipului de scris ( OSD – Orientation and Script Detection [8]),
automat (segmentarea întregii pagini, f ără OSD) etc.
– setarea unei liste de caractere ce vor fi recunoscute ( whitelist )
– setarea unei liste de caractere ce nu vor fi recunoscute ( blacklist ). Spre exemplu , dacă
am vrea s ă detect ăm numai cifre, trebuie s ă complet ăm ambele liste.
– Folosirea modului de recunoaștere CUBE pentru unele seturi de caractere (momentan
exist ă date antrenate în acest sens doar pentru englez ă, hindi și arabic ă; ultima nu poate
fi recunoscut ă decât în acest mod) ; acuratețe mai bunӑ, dar vitezӑ mai micӑ.
Exist ă două moduri în care se poate realiza OCR -izarea: la ap ăsarea unui buton sau
continuu . Acest din urmӑ mod funcționeazӑ repede, fiind textul de dimenisuni mici și cu puțin
fundal, însӑ traducerea și extragerea informațiilor externe au vitezӑ mai micӑ și rӑmân în urmӑ.
De aceea, în acest mod ele sunt dezactivate .

IV.1.2 Integrare în proiect

IV.1.2.1 Compilarea surselor

Unul din add-on-urile pentru Tesseract, esențial pentru a putea integra acest motor într -o
aplicație mobil ă pe platforma Android, îl reprezint ă tesseract -android -tools , un set de unelte
pentru compilarea Tesseract, Leptonica și alte biblioteci JPEG pe sistemul de operare Android,
oferind o interfaț ă de programare în limbajul Java Android, cu ajutorul JNI (Java Native
Interface).
Eu am folosit o e xtindere a acestor unelte, pus ă la dispoziție de Robert Theis în regim
open -source, numit ă tess-two [12]. Ea adaug ă funcționalit ăți noi API-ului Java existent, prin
adăugarea urm ătoarelor funcții:

49
 TessBaseAPI::GetRegions()
 TessBaseAPI::GetTextlines()
 TessBaseAPI::GetStrips()
 TessBaseAPI::GetWords()
 TessBaseAPI::GetCharacters()
Aceste surse au fost compilate cu NDK -ul Android, rezultând un obiect de tip *.so
(Shared Object ), specific Linux (tipul kernelului din Android), prin care se pot apela funcții
scrise în cod nativ .
IV.1.2.2 Descӑrcarea fișierelor antrenate

Fișierele antrenate pentru seturile de caractere din limba ce se dorește a fi recunoscutӑ se
descarcӑ de pe Google Repository -ul Tesseract [ 8], printr -o cerere HTTP de tip GET. Stocarea se
realizeazӑ pe cartela SD, care are de obicei capacitate mai mare. În timpul descӑrcӑrii, se creeazӑ
un fișier cu extensia *.download , pentru a putea fi detectate descӑrcӑrile incomplete la o altӑ
rulare (cea curentӑ, în caz de eroare, se va întrerupe, iar aplicația se va închide) . Acest fișier se
șterge la sfârșit, dacӑ descӑrcarea a avut succes.
Fișierele sunt arhivate, de aceea folosesc biblioteca JTar23 pentru a le dezarhiva , tot pe
cartela SD. Ulterior, arhiva este ștearsӑ.
Aceastӑ descӑrcare are loc o singurӑ datӑ, la prima selectare a acelei limbi, dupӑ care sunt
citite de pe cartela SD. Se verificӑ însӑ de fiecare datӑ existența acelor fișiere, pentru a preveni
situațiile când sunt șterse manual de cӑtre utilizator.

23 http://code.google.com/p/jtar/

50
IV.1.2.3 Captarea și c onversi a imaginii

Pentru a putea elimina pe cât posibil elementele de fundal și pentru a încadra exclusiv
porțiunea de text pe care o dorim, pe suprafața vizualӑ ( Surface View ) sunt desenate
dreptunghiuri cu margini ușor ajustabile de cӑtre utilizator. Acesta definește exact regiunea de
text doritӑ , ca un dreptunghi de decupare . Pentru a fi evident acest lucru, tot ce este în afara
acest uia, este colorat cu un negru transparent, iar ceea ce e în cadrul lui, are nuanțӑ și
transparențӑ normale.
În figur a de mai jos avem o diagramӑ a modului cum lucreazӑ camera din Android:

Fig. 29 – fluxul de lucru al camerei din Android [17]
În vectorul de octeți byte[] data , se gӑsește imaginea în formatul YUV420
(YC BCR_420_SP/NV21 ). Trebuie sӑ convertim aceastӑ ima gine în format ARGB8 888, alb -negru
(grayscale ), pentru a o putea pasa ca parametru . Pentru aceasta, trebuie sӑ detaliem aceste
formate și algoritmul care se folosește.

51
În formatul RGB888, fiecare pixel ocupӑ 8 biți de roșu, 8 biți de verde și 8 biți de
albastru, deci în total 24 de biți /pixel . Formatul ARGB8888 ocupӑ încӑ 8 biți suplimentar, pentru
alpha, gradul de opacitate. Se poate salva spațiu, pânӑ la 16 biți/pixel, dacӑ stocӑm luminanța
(luminance ) și diferențele de culori.
În formatul YUV, Y este componenta alb -negru, care stocheazӑ intensitӑțile, iar U (se
mai noteazӑ și C B , Chrominance Blue ) și V (se mai noteazӑ și C R , Chrominance Red ) stocheazӑ
componentele cromatice. Imaginea de mai jos le prezintӑ, de sus în jos, începând cu imaginea
care le combinӑ și apoi cu componentele separate:

Fig. 30 – imaginea și componentele sale Y, U, V, de sus în jos24

Formulele lor sunt urmӑtoarele , scrise folosind aritmetica întregilor (pentru YUV444,
vom explica ulterior diferențele) ,

24 http://en.wikipedia.org/wiki/YUV

52

Fig. 31 – relația dintre YC BCR și RGB22
Deoarece ochiul uman percepe mai degrabӑ raportul între intensitӑți decât detalii de
culori, sunt necesari mai mulți biți pentru a stoca Y. Urmӑtoarea imagine ilustreazӑ acest lucru,
chiar în formatul YUV420, folosit de camera din Android .

Fig. 32 – dispunerea componentelor Y, U , V în vectorul returnat de camera din Android25
Se observӑ cӑ la pentru fiecare bloc de 4 octeți Y, avem cate un octet U și un octet V.
Având acest vector, notat cu yuv, put em calcula componentele și realiza transformӑri între
YUV420 și RGB. Ultima funcție o reprezintӑ formulele din Fig.31 .

Fig. 33 – calculul componentelor din formatul YUV42022

25 http://en.wikipedia.org/wiki/YUV

53
În cazul aplicației noastre, pentru a putea obține o imagine alb -negru din vect orul în
format YUV420 , trebuie sӑ obținem o imagine ARGB8888, în care, pentru fiecare pixel, sӑ avem
R = G = B = Y, iar A = 0xff . Algoritmul final, extras din sursa aplicației, este:

Fig. 34 – algoritmul de obținere a imaginilor ARGB8888 din datele în format YUV420. Outputul e în vectorul pixels
[sursa aplicației]
Trebuie avut grijӑ ca poza sӑ se realizeze cât mai perpendicular pe text. Tesseract nu dӑ
rezultate satisfӑcӑtoare când unghiul d e înclinare este prea mare (caracterele vor ieși curbate și
nu vor avea toate aceeași dimensiune). De asemenea, este necesar un contrast puternic între
fundal și text, fie cӑ este alb -negru sau negru -alb. Aceasta deoarece, în procesul de Adaptive
threshold ing pentru obținere a imaginii binare , menționat mai sus, va fi greu de distins între
pixelii aparținând textului și pixelii aparținând fundalului, dacӑ diferența de intensitate nu este
mare. Spre exemplu, combinații de culori precum cele de mai jos nu au dovedit rezultate deloc
satisfӑcӑtoare:

Fig. 35 – exemple de combinații de culori fond -text care nu dau rezultate bune cu Tesseract26

26 http://www.exoticindiaart.com/ , desktopul personal

54
IV.1.2.3 Afișarea rezultatului

În urma procesării și a OCR -izării, rezultatul este un obiect de tip String, reprezentând
textul recunoscut. Trebuie testat dacă este șirul vid sau null, pentru a ne da seama dacă OCR –
izarea a avut succes sau nu. Un alt lucru important care poate fi extras este mean confidence , care
ne dă măsura acurateții recunoașterii acelui text în imaginea dată.
Pentru a folosi aceastӑ ultimӑ metricӑ într -un mod prietenos utilizatorului neavizat, textul
rezultat este afișat pe un fundal de culoare albӑ, dar cu opacitate direct proporționalӑ cu mean
confidence . Astfel, cu cât rezultatul este ma i clar, cu atât culoarea are gradul alpha mai mare,
deci este mai opacӑ.

Fig. 36 – formula calculului opacitӑții fundalului pe care este afișat textul rezultat [sursa aplicației]
În cazul în care textul reprezintӑ un link, este afișat într -o manierӑ cor espunzӑtoare,
deschizând un browser pentru vizualizarea paginii referite.
De asemenea, prin apӑsarea lungӑ a TextView -ului textului recunoscut (și, similar, a celui
tradus) , apare un meniu contextual, care permite:
– ștergerea de pe ecran a textului;
– copie rea sa în clipboard;
– distribuirea prin SMS, e -mail, sau alte aplicații instalate;
– codificarea sa QR;
– cӑutarea sa pe Google, deschizând browserul cu linkul corespunzator introdus.

55
IV.2 Modulul de traducere

Textul recunoscut de c ătre motorul OCR este trimis unui serviciu web de la Microsoft
Translator [15], care returneaz ă rezultatul. Aceast ă etapă este cea mai lent ă și nu poate avea loc
în modul real-time, deoarece r ămâne mult în urma textului recunoscut, care se actualizeaz ă rapid
la fiecare mișcare oricât de mic ă a utilizatorului.
Pașii care trebuie urmați pentru a putea traduce un cuvânt sunt urmӑtorii:
1. Înregistarea aplicației pe Azure Marketplace, în urma cӑreia se obține un client_id și un
client_secret ;
2. Obținerea și stocarea unui token de aut entificare printr -un request de tip POST, în care
includem datele obținute la pasul anterior. Aceastӑ metodӑ respectӑ standardele web
OAuth27 actuale .
3. Solicitarea de traducere a cuvântului , printr -o cerere cӑtre serviciu de tip GET. Printre
parametrii neces ari se numӑrӑ:
– token -ul de autentificare obținut anterior;
– textul de tradus;
– limba de care aparține (opțional, dar îmbunӑtӑțește viteza);
– limba în care se dorește traducerea;
– tipul de conținut al textului ce se dorește tradus (content type) , în format MIME ;
momentan, sunt suportate doar text/plain și text/html .
Rӑspunsul este obținut în format JSON și parsat cu ajutorul bibliotec IV Gson28. Token -ul
de autentificare expirӑ la fiecare 10 minute și de aceea, înainte de fiecare traducere, trebuie
verificat dacӑ a trecut aceastӑ perioadӑ , pentru a retrimite cererea de obținere a token -ului.

27 http://oauth.net/
28 http://code.google.com/p/google -gson/

56
IV.3 Modulul de recunoaștere a entit ăților textuale semnificative

Acest proces, mai cunoscut sub numele de Named Entity Recognition (NER), are în
vedere recunoașterea entit ăților semnificative din textul recunoscut și afișarea informațiilor
centralizate despre acestea, într -o manier ă specific ă fiecărei categorii.
Momentan, sunt procesate dou ă categorii: orașe / ț ări (LOCATION ) și obiective turistice
(LANDMARK ), în funcție de care s e afișeaz ă informații specifice: la orașe, care sunt principalele
localuri și hoteluri , pe când la obiective, site-ul oficial , de pe care se pot afla informații precum
orele de vizitare .
Recunoașterea este atât pe baz ă de resurse, prin c ăutarea într-o baz ă de date, cât și pe
bază de context, caz în care se folosesc unelte specifice, mai precis un clasificator antrenat în
acest scop. La acestea se adaugӑ aplicarea de expresii regulate, euristici personale și feedback din
partea utilizatorului.
IV.3.1 Componente

Existӑ mai înt âi o bazӑ de date predefinitӑ, care se umple apoi cu rezultatele obținute pe
parcursul rulӑrii aplicației. Conține 2 tabele:
– entitӑți din categoriile de mai sus, în mare parte obținute inițial din gazetteer -ul folosit de
celebrul soft GATE ;
– nonentități ( stopwords și nume care nu sunt în categoriile de mai sus).
NER -ul antrenat statistic este Confidence Chunker -ul celor de la LingPipe, iar modelul îl
reprezintӑ fișierul antrenat pe texte din știri în limba englezӑ. Categoriile recunoscute de el sunt
LOCATION, ORGANIZATION și PERSON , cӑrora le corespund, în aplicația mea, tipurile
LOCATION, LANDMARK, OTHER.
Existӑ de asemenea o expresie regulatӑ complexӑ, care poate recunoaște nume proprii
variate, dar nu le poate cl asifica în funcție de context. Exemplu de nume proprii recunoscute:
Paris St. -Germain, Coeur d’Alene, N’djamena , dar și John J.Smith.

57
IV.3.2 Funcționare

O diagramӑ de activitӑți care rezumӑ algoritmul de recunoaștere a entitӑților este
urmӑtoarea:

Fig. 37 – diagrama de activitӑți care surprinde algoritmul de recunoaștere a entitӑților

58
Deoarece NER -ul e antrenat în limba englezӑ, dacӑ nici una din limbile setate în aplicație,
fie de recunoaștere, fie de traducere, nu este engleza, atunci se aplicӑ o traducere suplimentarӑ a
textului recunoscut în limba englezӑ .
Pentru simplificare, nu am inclus în diagramӑ și o anumitӑ euristicӑ pe care o folosesc
pentru corectarea rezultatelor NER -ului, pe care o voi descrie în continuare .
Algoritmul Confidence Ch unker -ului returneazӑ mai multe clasificӑri posibile pentru o
entitate. În cazu l în care clasificӑ un LOCATION drept ORGANIZATION sau invers, nu este o
problemӑ, diferența va fi datӑ fie de confruntarea cu baza de date, fie de confirmarea
utilizatorului.
Problema apare în momentul în care o entitate este clasificatӑ drept PERSON, dar și drept
un alt tip de interes în aplicație. În cazul în care raportul de scor este mai mic de 1.5, verific dacӑ
existӑ combinații de tipul “goes to X”, “go to X”, “near X” , “city X ”, “is in the north ”, “is
located ”, “is situated ”. În aceste cazuri, voi considera entitatea respectivӑ ca fiind de tip
LOCATION. Altfel, dacӑ nu existӑ asemenea patternuri și raportul de scor este mic, voi lӑsa
categoria cu scorul cel mai mare. Co nsider cӑ este mai puțin grav sӑ -mi considere drept entitate
semnificativӑ un nume de persoanӑ, decât sӑ nu îmi recunoascӑ o locație sau un obiectiv turistic.
Oricum, utilizatorul are decizia finalӑ, care va produce modificӑri în baza de date, pentru a
îmbunӑtӑți viitoarele cӑutӑri.
IV.3.3 Rezultate

Combinația de tehnici care sӑ poatӑ fi adaptate pentru dispozitivul mobil a dat rezultate
satisfӑcӑtoare , în raport cu timpul de lucru și memoria ocupatӑ .
Ele pot fi îmbunӑtӑțite dacӑ textul de interes este mai lung și conține cuvinte care
sugereazӑ localizarea, gen “ trip to ”, “is located ”, “is situated ” pentru a alcӑtui un context.
De asemenea, dacӑ sunt folosite nume proprii englezești cunoscute sau formule de
adresare tipice știrilor ( “Mr.” ), riscul de cl asificare greșitӑ a persoanelor scade semnificativ.

59
IV.4 Modulul de extragere a informațiilor externe

Pentru extragerea informațiilor de interes despre o anumitӑ entitate, am folosit rezultate
obținute de pe Wikipedia și de pe Google Maps. Astfel, imaginea, o scurtӑ descriere și linkul
sunt extr ase din sursa paginii Wikipedia, iar afișarea pe hartӑ a unor localuri și hoteluri se
realizeazӑ cu ajutorul unor cereri cӑtre Google Maps.
Pentru extragerea informațiilor de pe Wikipedia, am înlocuit spații le din numele entitӑții
cu “_” și am preluat sursa paginii de la adresa http://en.wikipedia.org/wiki/Nume_Entit .
Apoi, cu ajutorul bibliotecii JSoup29, am parsat html -ul primit pentru primul paragraf, prima
imagine, iar site -ul oficial, în cazul monumentelor, l -am cӑutat la secțiunea de linkuri externe
(External Links ). Dacӑ nu am gӑsit nimic de genul „ Official site” , atunci am returnat linkul
Wikipedia, la fel ca la locații.
Cererile pentru serviciil e web ale Wikipedia returneazӑ outputul într -un limbaj cu o
sintaxӑ specificӑ WikiMedia, greu de parsat. Uneltele care se ocupӑ de aceastӑ sarcinӑ sunt mari
și depind de multe alte biblioteci, de aceea am ales varianta parsӑ rii directe a sursei, fiind ușor de
ajuns la elementele de care aveam nevoie.
Pentru integrarea cu Google Maps, aplicație deja preinstalatӑ pe telefon, se realizeazӑ o
cerere cu un query -string sugestiv, gen „q=Coffee Shops near Paris, France” și se deschide un
nou ecran cu punctele plasate pe hartӑ. Nu este nevoie de alt API, avantaj al sistemului de
operare Android, de la Google.
Aceste operații se executӑ o singurӑ datӑ pentru fiecare entitate, rezultatele fiind stocate
în baza de date, pen tru a fi rapid afișate la urmӑtoarea detecție a entitӑții.

29 http://jsoup.org/

60
IV.5 Schema generalӑ a aplicației

La orice aplicație mobil ă sau doar cu interfaț ă grafic ă, în general, este esențial ca sarcinile
costisitoare ca timp s ă se desf ășoare pe alte threaduri decât cel principal, care aparține interfeței,
deoarece ar cauza bloc ări.
Android are un mecanism foarte flexibil pentru aceasta și anume definirea de taskuri ce
se execut ă asincron, pe threaduri din background , din thread pool -ul sistemului .
Acestea apoi trim it mesaje în coada de mesaje a thread -ului, când returneazӑ rezultatul
procesӑrii, prin intermediul unui handler.
Existӑ 2 thread -uri importante în aplicație: thread -ul interfeței grafice și un thread de
decode , care preia cadrele captate de camerӑ, le p roceseazӑ și, în funcție de modul de OCR -izare
(continuu sau nu), apeleazӑ el motorul de OCR -izare sau declanșeazӑ un AsyncTask. Acest
thread este de tip Looper , adicӑ primește mereu mesaje și este inițializat chiar dupӑ crearea
suprafeței vizuale.
Fieca re din aceste thread -uri are câte un handler atașat, care primește mesaje de la thread –
urile din background, atunci când sunt obținute rezultatele unei procesӑri costisitoare. Ele
comunicӑ între ele, astfel încât thread -ul interfeței grafice sӑ primeascӑ m ereu toate rezultatele
finale. Comunicarea se poate vedea mai ușor pe diagrama de pe pagina urmӑtoare.
Pentru simplificare, în figurӑ nu am reprezentat faptul cӑ, în procesul de extragere a
entitӑților, tot MainHandler -ul este cel care primește acest rezu ltat de la NERAsyncTask , deci
thread -ul principal este de fapt cel care lanseazӑ o nouӑ Activity în care sunt afișate entitӑțile
extrase și informațiile lor .
De asemenea, nu am reprezentat grafic testele de traducere activatӑ și extragere a
entitӑților ac tivatӑ.

61

62
V. Concluzii le lucrӑrii și direcții de dezvoltare

Datorită faptului că se lucrează cu texte de dimensiuni mici și încadrate cu precizie,
OCR -izarea s -a dovedit a fi lightweight, fiind sarcina care se execută cel mai repede și cu
acuratețea cea mai mare, nefiind nevoie de arhitectură client -server , cum gândisem inițial
problema. Se poate în continuare dezvolta acest modul prin afișarea regiunilor efective de
caractere recunoscute sau a împӑrțirii în cuvinte, pentru a înțelege și corecta eventuale le erori.
OCR -izarea și traducerea nu se pot însӑ realiza ambele în modul continuu, datorită vitezei
mici de obținere a rezultatului de la serviciul de traducere . Așadar, traducerea instantӑ unui text
pozat este o sarcinӑ încӑ nefezabilӑ.
Recunoașterea ent ităților are o acuratețe bună, datorită combinației de căutare pe bază de
expresii regulate și resurse , recunoaștere pe baza unui model statistic antrenat , euristici pesonale
și, nu în ultimul rând, feedback utilizator . Aceastӑ combinație a fost necesarӑ deoarece textul
pozat va fi, tipic, de dimensiune micӑ, ceea ce poate face dificilӑ înțelegerea contextului și, deci,
dezambiguizarea categoriei de care aparține o anumitӑ entitate. Dacӑ însӑ sunt prezente anumite
cuvinte cheie specifice persoanelor sau loc ațiilor, riscul de clasificare greșitӑ scade. Pe viitor, s –
ar putea adӑuga mai multe categorii de entitӑți de interes, precum magazine sau persoane celebre.
Viteza extragerii de entitӑți ar putea fi îmbunătățită prin mutarea pe un server a sarcinii
de NER pe bază de model antrenat, caz în care se poate încerca folosirea unui soft mai avansat,
precum GATE, Stanford NER sau Illinois Named Tagger . Trebuie în acest caz dezvoltat un
protocol de comunicare cât mai direct, eventual chiar TCP, deoarece modulul de t raducere a
dovedit cӑ mecanismul OAuth, deși asigurӑ securitate sporitӑ, îngreuneazӑ transferul datelor
client -server .
În concluzie, aplicația construită se poate dovedi de un real ajutor când nu dorim să
tastăm un text și să deschidem numeroase aplicații pentru a obține informații despre conținutul
lui, ci doar să realizăm o captură, iar de aici să avem interpretӑri diverse centralizate și
posibilitӑți multiple de distribuire și stocare a rezultatelor.

63
VI. Bibliografie

[1] S. Colton, J. Gow – Artificial Intelligence Course, Department of Computing, Imperial
College, London (http://www.doc.ic.ac.uk/~sgc/teaching/v231/lecture12.html și
http://www.doc.ic.ac.uk/~sgc/teaching/v231/lecture13.html )
[2] D.Cristea, I.Pistol, M.Ioniță – Inteligența Artificială , Editura Universității "Al.I.Cuza",
2007, p.15 -18
[3] M.Minsky , S.Papert – Perceptrons , The MIT Press , 1987
[4] R.Holley – How Good Can It G et? Analysing and Improving OCR Accuracy in Large
Scale Historic Newspaper Digitisation Programs , D-Lib Magazine , aprilie 2009
(http://www.dlib.org/dlib/march09/holley/03holley.html )
[5] G.Becker – Challenge, Drama & Social Engagement: Designing Mobile A ugmented
Reality Experiences , Prezentare pentru “ Web 2.0 Exp o”, San Francisco 2010
(http://www.web2expo.com/webexsf2010/public/schedule/detail/11960 )
[6] A. Arusoaie, A . I.Cristei, C . Chircu, M . A.Livadariu, V .Manea, A .Iftene – Augmen ted
Reality , SYNASC 2010 Submission , p.1-3
[7] R.Smith – An Overview of the Tesseract OCR Engine , 9th Int. Conf. on Document
Analysis and Recognition , IEEE, Curitiba, Brazil ia, Sep tembrie 2007
[8] Wiki -ul de pe Google Repository -ul motorului OCR open -source Tesseract
(https://code.google.com/p/tesseract -ocr/w/list )
[9] P.J. Rousseeuw – Least Median of Squares Regression , Journal of the A merican
Statistical Association, Decem brie 1984, Volumul 79
[10] P.J. Schneider – An Algorithm for Automatically Fitting Digitized Curves , inclus ă în A.S.
Glassner – Graphics Gems I , Morgan Kaufmann, 1990, p . 612 -626
[11] S.V. Rice, G. Nagy, T.A. Nartker – Optical Character Recognition: An Illustrated Guide
to the Frontier , ed. Kluwer Academic Publishers, USA 1999, p . 57-60

64
[12] Robert Theis – aplicația tess-two, o extindere open -source pentru tesseract -android -tools
(https://github.com/rmtheis/tess -two)
[13] Robert Theis – aplicația experimental ă android -ocr, o aplicație open -source, disponibil ă
pe Android Market, ce demonstreaz ă folosirea tehnologiei OCR și a motorului Tesseract
(https://github.com/rmtheis/android -ocr)
[14] Zxing Team – Barcode Scanner , o aplicație open -source, disponibil ă pe Android Market,
pentru scanarea codurilor de bare
(https://play.google.com/store/apps/details?id=com.google.zxing.client.android )
[15] Microsoft Translator API ( http://www.microsofttranslator.com/dev/ )
[16] LingPipe Named Entit y Recognizer ( http://alias -i.com/lingpipe/index.html ) și tutorialul
aferent acestui modul (http://alias -i.com/lingpipe/demos/tutorial/ne/read -me.html )
[17] Fluxul de lucru al captӑrii de imagini în Android
(http://www.touchqode.com/misc/20101025_jsug/201010 25_touchqode_camera.pdf )
[18] Shapiro, Linda G. & Stockman, George C. (2002) – Computer Vision , Ed. Prentice Hall
[19] Descrierea formatelor RGB și YUV
http://www.efg2.com/Lab/Graphics/Color s/YUV.htm
[20] J.Cowie, Y.Wilks – Information Extraction, 1996
[21] Andrei Mikheev, Marc Moens, Claire Grover – Named Entity Recognition without
Gazetteers , EACL 1999
[22] D. Gusfield – Algorithms on Strings, Trees and Sequences , Computer Science and
Computatio nal Biology. Cambridge, England, ed. Cambridge University Press, 2005.