Recunoașterea caracterelor scrise de mână folosin d [629624]
UNIVERSITATEA TEHNICĂ “GHEOGHE ASACHI” DIN IAȘI
FACULTATEA DE ELECTRONIC Ă, TELECOMUNICAȚII ȘI
TEHNOLOGIA INFOMAȚIEI
LUCRARE DE LICENȚĂ
Coordonator științ ific: Student: [anonimizat] g. Iulian Ciocoiu Mărmureanu Ciprian -Ioan
2014
2
UNIVERSITATEA TEHNICĂ “GHEOGHE ASACHI” DIN IAȘI
FACULTATEA DE ELECTRONIC Ă, TELECOMUNICAȚII ȘI
TEHNOLOGIA INFOMAȚIEI
Recunoașterea caracterelor scrise de mână folosin d
rețele neurale artificiale recurente
Coordonator științific : Student: [anonimizat]. Iulian Ciocoiu Mărmureanu Ciprian -Ioan
2014
3
Cuprins:
Rezumat……………………… ………………………………………………………………………………… .4
CAPITOLUL I: Analiza și recunoașterea documentelor
I.1 Introducere ……………………………………………………………………………. ………………… .6
I.2 Operații de preprocesare …………………………………………………………………………… .9
I.3 Analiza layout -ului unei pagini ………………………………………………………….. ………11
I.4 Segme ntarea unui șir de caractere ………………………………………………………. …….13
I.5 Extragerea trăsăturilor utilizând Transformata Cosinus Discretă ……………. …14
I.6 Recunoașterea cuvintelor …………………………………….. …………………………… ………16
I.7 Evoluția sistemelor de recunoaștere optică a caracterelor ……………………….. …19
CAPITOLUL II: Aspecte generale referitoare la recunoașterea
formelor
II.1 Introducere …………………… …………………………. …………………………………………22
II.2 Metrici invariante …………………………………………………………………………………26
II.3 Distanța de tip tangentă ………………. ……………………………………………………….28
II.4 Determinarea vectorilor tangenți …………………………………………………………. .33
II.5 Utilizarea altor tipuri de vectori tangenți ………………………. …………………….. .37
CAPITOLUL III: Retele neurale recurente de tip gradient
III.1 Introducere …………………………………………………………………… .…41
III.2 Modelul memoriei asociative invariante recurente ……………………………43
CAPITOLUL I V: Rezultate experimentale
IV.1 Baza de date USPS ………………………………………………………………………………… .50
IV.2 Rezultate experimentale ……………………………………………………….. ………………..51
Concluzii ……………………………………………………………………………………………………….55
Referințe bibliografice …………………………………………….. …………………………………….56
Anexă …………………………………………………………………………………………………………….5 7
4
Rezumat
De ce recu noașterea caracterelor scrise de mână? Deoar ece scrisul a reprezentat, de la
inventarea sa și până în prezent o modalitate sigură și ușoară de stocare și de transmitere a
informațiilor. Din punct de vedere evolutiv, caracterul social al omului a fost generat de
necesitatea creșterii șansei de suprav ețuire. Scrisul reprezintă poate cea mai importantă
invenție a omului, generând o revoluție în civilizația umană prin cele două avantaje majore pe
care le are față de comunicarea orală. Primul este capacitatea de stocare sigură a informaț iei,
nealterata de transm iterea acesteia pe cale orală. Al doilea avantaj este reprezentat de fap tul că
permite transferul cunoștințelor de la o generație la alta, f acilitând acumularea acestora ș i
impulsionând progresu l.
Lucrarea abordează o problemă particulară a recunoaș terii scrisului de mână, cea a
recunoaș terii cifrelor folosind rețele neurale de tip gradient. Aceasta urmărește în capitolul I
să redea o scurtă prezentare a celor mai semnificative probleme care pot apare în
recunoașterea caracterelor și a metodelor de rezolvare a acestora cu ajutorul rețelelor
neuronale .
În capitolul 2 se introduce este o nouă metrică invariantă local, numită distanța de tip
tangentă folosită în aplicația concretă care se referă la recunoașterea caracterelor scri se de
mână , urmând ca în capitolul 3 să se propună o noua abordare a recunoa șterii formelor
invariante pe baza unui tip de gradient special, recurent cu memorie asociativ ă analogică .
În capitolul 4 este prezentată baza de date United State s Postal Service (USPS) și ratele
de eroare date de experimentele folosind distanța de tip tangentă discutată in capitolul 2.
Urmează apoi anexele, formate din cod Matlab cu care s -a realizat simularea.
5
CAP ITOLUL I: Analiza și
recunoașterea documentelor
I.1 Introducere
I.2 O perații de preprocesare
I.3 Analiza layout -ului unei pagini
I.4 Segmentarea unui șir de caractere
I.5 Extragerea trăsăturilor utilizând
Transformata Cosinus Discretă
I.6 Recunoașterea cuvintelor
I.7 E voluția sistemelor de recunoaștere
optică a caracterel or
6
I.1 Introducere
Recunoașterea optică a caracterelor ( Optical character recognition ), abreviată și OCR ,
reprezintă translatarea mecanică sau electronică a imaginilor cu scris de mână, tipărit sau
printat (de obicei scanat) în text editabil.
În ultim ul deceniu, scăderea costului de cumpărare a documentelor, de depozitare si
prelucrare, precum și reînoirea interesului în Rețele Neurale Artificiale au contribuit la găsirea
unor noi soluții în rezolvarea diferitelor probleme ce apar în prelucrarea docum entelor.
Deși calculatoarele echipate cu camere sau scanere optice sunt capabile să citească
documente si să le reproducă electronic cu o precizie destul de bună, teancuri de documente
încă ocupă majoritatea birourilor. Acest lucru se întâmplă fi e din cauza prezenței zgomotului,
fie din cauza structurii imprevizibile a documentelor care face ca extragerea informației în
mod automat să fie mai dificilă.
Recunoașterea caracterelor se poate face online sau offline . Recunoașterea online
implică conve rsia automată a textului pe un dispozitiv digital special, unde un senzor preia
mișcările instrumentului de scris. Semnalul obținut este convertit în coduri ale caracterelor.
Recunoașterea offline presupune conversia automată a textului dintr -o imagine în coduri ale
caracterelor. Data obținută în această formă este vazută ca o reprezentare statică.
Pentru eliminarea problemelor ce se pot ivi în analiza și recunoașterea documentelor
foarte importantă este alegerea adecvată a unor arhitecturi neuronale și a unor sisteme de
învățare, iar cele mai multe aplicații în acest domeniu se bazează pe sisteme tradiționale de tip
Perceptron Multistrat (MLP). Printre aceste aplicații se numără filtrarea și eliminarea
zgomotului, precum și recunoașterea caracterelor, a cu vintelor și a elementelor grafice.
De cele mai multe ori, datele de intrare ce trebuiesc prelucrate sunt reprezentate sub
forma unui vector de trasături. De exemplu, zonarea (bazată pe gruparea trăsăturilor în regiuni
obținută prin suprapunerea unui grid p este caractere) este frecvent utilizată în recunoașterea
optică a caracterelor pentru alimentarea unei rețele neuronale cu eșantioane de caractere cu
dimensiuni variabile. Un alt tip de reprezentare folosit este reprezentarea structurală, potrivită
pentru toate aplicațiile care implică întreg documentul.
7
Operația de recunoaștere a caracterelor presupune o serie de etape de prelucrare a
datelor , descrise și în figura Fig.1.1:
Fig.1.1 Diagrama bloc a unui sistem de recunoaștere a caracterelor
Prima etapă în orice sistem de recunoaștere a caracterelor este reprezentată de
colectarea datelor . Se calculează un vector de trăsături alcătuit dintr -un set de măsurători
realizate cu ajutorul unor echipamente tehnice și convertite într -o formă numerică. Î n cazul
analizei unei imagini un astfel de echipament poate fi o cameră video sau un scanner. Datele
de intrare, indiferent în ce formă se află, sunt eșantionate la intervale fixe de timp și digitizate
pentru a fi reprezentate cu un număr prestabilit de bi ți pe măsură. Digitizarea unei imagini
este un proces de convertire a unei imagini în date numerice, imaginea fiind împărțită în
regiuni mici numite pixeli. Acest proces include eșantionarea imaginii și cuantificarea în
nivele de gri. Numărul de la fiecare pixel reprezintă intensitatea imaginii din acel punct.
Este posibil ca această etapă să includă stocarea auxiliară a datelor, necesară în situația
în care faza de recunoaștere nu poate fi efectuată simultan cu achiziția de date. În unele
situații estenece sară compresia datelor, pentru a crește cantitatea de informații ce poate fi
stocată, chiar dacă acest lucru presupune scăderea preciziei de reprezentare a datelor.
Compresia presupune reducerea rezoluției spațiale sau temporale a eșantioanelor de date sau
prezentarea măsurătorilor cu o precizie mai mică folosind un număr mai mic de biți pe
eșantion.
Procesul de înregistrare definește cadrul în care sistemul funcționează, astfel încât
acesta să știe ce să aștepte ca intrări valide. Intrările de date sunt ad esea însoțite de zgomot, iar
preprocesarea este utilă pentru reducerea efectelor zgomotului. Prin zgomot se înțelege orice
lucru care împiedică un sistem de recunoaștere în îndeplinirea misiunii sale. Datele
înregistrare și preprocesate sunt divizate în su bpărți care definesc entități semnificative pentru
clasificare. Blocul de segmentare poate adăuga fie informații despre limitele segmentelor
8
fluxului de date, fie copie toate segmentele în memorii tampon ( buffere ) separate și le redă pe
rând în următoarea etapă.
O caracteristică comună a mediilor în care se utilizează sisteme de recunoaștere o
reprezintă variația proprie a modelelor. În acest caz este utilă normalizarea care se realizează
prin utilizare algoritmilor de extragere de trăsături sau d e clasificare. Dacă normalizarea ar fi
făcută în mod ideal, creșterea dimensiunii cauzate de zgomot ar fi anulată. Un exemplu ar fi în
cazul scrisului de mână faptul că scrierea nu are o orientare dreaptă în sus, ci mai degrabă este
înclinată spre stânga s au dreapta, normalizarea realizându -se prin estimarea înclinării și
refacerea caracterului.
Extragerea trăsăturilor presupune obținerea celor mai relevante informații pentru
clasificare din datele disponibile. În cadrul acestui proces discutat mai în detal iu în cadrul
subcapitolului 1.3, are loc o reducere a dimensiunii datelor, necesară datorită limitării
memoriei programelor.
O altă etapă importantă în recunoașterea modelelor o reprezintă etapa de clasificare și
grupare. Operația de clasificare se poate d efini ca o transformare a datelor de intrare
cantitative în informații calitative de ieșire. Ieșirea clasificatorului poate fi fie o selecție din
mai multe clase predefinite sau un vector de valori reale ce definesc probabilități care
sugerează apartenența modelului la o anumită clasă. Un subiect strâns legat de clasificare este
cel de grupare, al cărui rol este de a grupa vectorii de trăsături în clustere în interiorul cărora
asemănarea dintre modele este mai mare decât între clustere. O ultimă etapă în re cunoașterea
modelelor este reprezentată de postprocesare, utilă în îmbunătățrea preciziei clasamentului
general, prin aducerea unor noi informații a priori despre mediul înconjurător în sistem.
Această etapă se realizează cu ajutorul unorsubrutine de norma lizare.
În cazul în care la intrare se aplică o singură cifră, un sistem de recunoaștere are
următoarea structură:
Fig. 1.2.: Sistem de recunoaștere când la intrare este un singur caracter
9
În majoritatea aplicațiilor, carac terele sunt scrise în locuri speciale pe formulare. Primul
pas după scanare este înregistrarea, prin care se determină modul în care forma originală este
translată și rotită pentru obținerea imaginii finale. Acest lucru se face prin selectarea unui
anumit număr de puncte din forma de la intrare. Fiind fixate coordonatele cadrelor de la
intrare, se calculează coordonatele formelor și se extrage imaginea cadrului. Procesul de
normalizare aduce toatecaracterele la aceeași înălțime și lățime și reduce variațiil e de
înclinare, rămânând doar diferențe deformă. Harta de biți obținută poate servi ca intrare într –
un clasificator sau pot fi extrase trăsături dinimagine pentru reducerea dimensiunii datelor.
Metode ușoare de extragere a trăsăturilor suntraportul dintre lățime și înălțime, numărul de
pixeli.
Deciziile de clasificare se iau în funcție de cost minim. O regulă de decizie are ca efect
împărțirea spațiului de intrare în regiuni, fiecare regiune corespunzând unei anumite clase.
Descoperiri recente domeniu de în vățare automată oferă noi direcții de cercetare, cum ar
fi preprocesarea, analiza layout -ului, segmentarea caracterelor, recunoașterea caracterelor și a
cuvintelor. În continuare se va face referire la aplicații care se ocupă cu imagini ale
documentelor, t ratându -se în mod special documentele offline .
I.2 Operații de preprocesare
Operațiile de preprocesare tipice în analiza și recunoașterea imaginii documentului,
precum și rezultatele cele mai semnificative în utilizarea rețelelor neuronale artifi ciale în
preprocesare sunt prezentate în tabelul următor.
Tabel 1.1: Operații de preprocesare
Operații Arhitectura Intrare
în rețeaua
neuronală Ieșirea rețelei
neuronale
binarizare Perceptron
Multistrat Fereastră
alunecătoare de
dimensiune 5×5 cu
trăsăt uri extrase Pixel în primplan
sau de
fond
Reconstituirea
imaginii Perceptron
Multistrat Fereastră
alunecătoare de
pixeli Valoarea
refăcută a
pixelului curent
Înclinarea
Perceptron
Trăsături calculate
Unghiul de
10
paginii Multistrat dintr -o pagină înclinare
Înclinarea
Simbolului Perceptron Trăsături calculate
pentru un simbol Unghiul de
înclinare
Subțierea
Simbolului Rețea de tip hartă
cu autoorganizare(
SOM „harta de biți ”
(bitmap) normalizată Simbol subțiat
Rezultatul operației de binarizare este o imagine ce conține 2 nivele de gri (alb și
negru), în care pixelul de fond este codat cu (alb), iar pixelul ce aparține obiectului (în prim
plan) este codat cu 1 . Perceptronul multistrat poate fi folosit prin alimentarea sa cu pixeli
dintr -o fereastră d e dimensiune fixă (5×5).
Rețelele neurale sunt frecvent utilizate în preprocesarea imaginii pentru învățarea unor
filtre specifice din exemple. Utilizarea unui singur perceptron multistrat pentru eliminarea
unei game mari de zgomote este foarte complicată. De aceea, se preferă folosirea mai multor
rețele de acest tip ca filtre, cu o fereastră de intrare pătrată pentru a modela inversa procesului
de distorsiune. Asfel se permite adaptarea filtrului prin reantrenarea unui perceptron multistrat
la fiecare pagi nă ce trebuie prelucrată.
Refacerea imaginii textului are scopul de a îmbunătăți calitatea imaginii înainte de
analiza layout -ului și recunoașterea propriu -zisă. Deoarece caractere distruse și întrerupte pot
fi generate neintenționat când se elimină liniil e suprapuse peste textul în verificare, o atenție
deosebită este acordată refacerii simbolurilor afectate (întrerupte) după eliminarea liniilor. De
asemenea, și paginile înclinate pot afecta citirea corectă a caracterelor. În literatură au fost
propuse sol uții pentru remedierea acestor defecte în care se folosesc un set de trăsături ce
descrie intrarea și un perceptron multistrat antrenat să reproducă estimarea unghiului de
înclinare.
În cazul algoritmilor de subțiere a caracterelor se poate utiliza un algo ritm bazat pe
structura în clustere (CBSA) implementat de Self-Organisation Maps (SOM -rețele de tip hartă
cu auto -organizare), concretizat în 2 pași: se stabilește un set de clustere corespunzătoare
pixelilor adiacenți și se construiește structura prin con ectarea centrilor clusterelor.
Valoarea fiecărui punct (dacă e umplut sau nu) este stocată în unul sau mai mulți biți de
date.
Rețelele neuronale artificiale au abilitatea de a învăța din exemple de relații de intrare –
ieșire neliniare compl exe, ce face posibilă o adaptare rapidă la diferite tipuri de zgomote.
Această proprietate este foarte utilă în aplicații de preprocesare.
11
Cu excepția metodelor de binarizare, metodele descrise folosesc imagini alb/negru. În
aplicații de preprocesare, rețe lele neuronale artificiale sunt folosite în general pentru regresie
(relație funcțională între două sau mai multe variabile prin intermediul căreia se pot face
predicții ale unei variabile, în funcție de altă valoarea).
I.3 Analiza layout -ului unei pagin i
O astfel de analiză este necesară pentru segmentarea documentului în regiuni uniforme
omogene (analiză fizică) și pentru etichetarea ulterioară (analiză logică) a acestora. Algoritmii
de segmentare în procesarea imaginii sunt repartizați în 3 categorii: clasificarea pixelilor,
clasificarea regiunilor și clasificarea paginilor.
Fig. 1.3: Nivele de clasificare ale aspectului paginii
Clasificare pixelilor a fost aplicată inițial pentru binarizarea imaginii unui document, și
mai târziu, s -a extins la clase suplimentare (texte, grafice). Acest tip de clasificare poate fi
utilizat pentru diferite tipuri de imagini (alb/negru, nivele de gri sau color), folosindu -se
informațiile pixelilor corespunzători.
Pentru segmentarea docume ntului, se poate folosi perceptronul multistrat în combinație
cu o reprezentare multidimensională a unui pachet de forme de undă. Trăsăturile utilizate sunt
puncte locale ale componentelor pachetului, calculate în ferestre locale la rezoluții diferite.
Pentru fiecare pixel, pot fi obținute estimări de clase diferite la rezoluții diferite. Clasa unui
12
pixel este estimată prin combinarea ieșirilor unui perceptron multistrat ce codifică apartenența
la o clasă cu o codare „ one-hot”, în care o unitate de ieșire e ste atribuită pentru fiecare clasă și
toate rezultatele unitaților de ieșire sunt stabilite la , cu excepția ieșirii corespunzătoare clasei
corecte care va avea valoarea 1. Pentru reducerea numărului de conexiuni și pentru
îmbunătățirea capacităților de ge neralizare, se folosesc doar un set de pixeli din fereastra de
intrare.
Clasificarea în regiuni a fost inițial realizată prin folosirea ca intrări în clasificatoare
liniare proiectate cu parametri definiți de utilizator, a unor trăsături globale din fiecar e
regiune. Similar, la utilizarea rețelelor neurale pentru clasificarea în regiuni, se calculează
trăsături din fiecare regiune (calculate cu ajutorul lățimii și înălțimii regiunii, numărului
pixelilor negri) și se folosesc ca intrări în clasificatoare neu rale. În cazul utilizării
caracteristicilor locale, particularitățile sunt calculate pentru fiecare pixel din regiune.
Clasificarea logică a regiunilor de text se realizează cu rețele recurente, în care blocurile
text sunt extrase începând din stânga sus p ână în colțul din dreapta jos, fiind organizate ca
„secvențe temporare”. Pentru fiecare secvență, intrarea conține informații cantitative a
blocului curent (dimensiune, poziție, numărul de linii și numărul de cuvinte), cât și informații
de la ieșirea blocu lui anterior.
Aspectul paginii este în general de natură ierarhică și poate fi reprezentat prin grafuri
sau arbori. Rețelele neuronale pot fi tratate cu reprezentări structurale folosind două abordări
principale: fie prin codarea reprezentării într -un vect or de trăsături cu dimensiune fixă sau
prin folosirea rețelelor recursive.
Rețelele neuronale sunt mult mai des folosite în analiza layout -ului pentru clasificarea
modelelor decât în preprocesare unde sunt folosite ca filtre neliniare antrenate, ieșirea fi ind o
decizie discretă dintre mai multe clase. Avantajele rețelelor neuronale folosite în clasificare
sunt abilitatea lor de a învăța din exemple și robustețea la zgomot în faza de antrenare.
La tratarea problemelor cu clasificarea în pixeli, pot apărea et ichetări greșite ale
pixelilor, cauzate de pixelii frontieră ce pot fi asociați la mai multe clase dacă fereastra
centrată pe acești pixeli acoperă regiuni diferite. În acest caz, abordarea cea mai potrivită este
eliminarea pixelilor frontieră. Clasificare a în pixeli poate duce la o mai bună segmentare în
anumite domenii (de exemplu documente video, pagini web) unde localizarea componentelor
unite în imagini color este dificilă.
13
I.4 Segmentarea unui șir de caractere
Un sistem complet de recunoaștere a s crisului de mână presupune segmentarea corectă
în caractere și găsirea cuvintelor.
Segmentarea caracterelor urmărește descompunerea unei secvențe de caractere în
simboluri individuale. Strategiile de segmentare pot fi împărțite în trei categorii: metoda
descompunerii (împarte imaginea de la intrare în subimagini), metodă bazată pe recunoaștere
(se bazează pe integrarea segmentării și recunoaștere) și abordări holistice. În metoda holistică
algoritmii folosesc cuvântul ca o unitate individuală și încearcă să -l recunoască folosind
caracteristicile lui.
Fig. 1.4: Segmentarea caracterelor utilizând rețele neurale
În segmentarea prin descompunere, caracterele unite sunt detectate fie în funcție de
mărimea lor sau printr -o lege de recunoaștere a unui clasificator antrenat să recunoască
caractere izolate. Acest tip de segmentare se poate realiza utilizând un perceptron multistrat
cu doi neuroni în stratul de ieșire, antrenat să recunoască caractere izolate din perechi de
caractere unite. Intrarea este o imagine normalizată (exemplu Fig.1.4). În figura de mai sus, în
1.4.a este reprezentat un perceptron multistrat folosit pentru numărarea caracterelor, în b)
perceptron multistrat pentru sugerarea locului potrivit pentru punctel e de segmentare, iar în
Fig.1.4.c este reprezentat un perceptron pentru indicarea punctelor de tăiere (segmentare) ce
utilizează un set de trăsături extrase la fiecare poziție orizontală. Pentru a face posibilă
recunoașterea s -a generat un set de antrenare cu peste 17 de perechi de caractere unite sau nu,
14
prin scanarea eșantioanelor a mai mult de 3 de fonturi comune. Fiecare pereche a fost
generată prin concatenarea a două caractere. Pentru detectarea punctelor de separație pentru
fiecare poziție x din șiru l de caractere se calculează trăsături (bazate pe poziția golurilor,
conturul din partea superioară a caracterelor, histograma liniilor suprapuse). În cazul în care o
subimagine conține două caractere (Fig1.4.b), se folosește un perceptron multistrat care
primește la intrare eșantioanele subimaginii obținute prin procesul de zonare realizat cu un
cadru de dimensiune 3 x 6 . Prin numărarea pixelilor negri în ferestre mici, nesuprapuse din
imaginea scalată se calculează un vector de 72 de elemente. Descrierea poziției punctelor de
separație se realizează folosind codarea „ one-hot” a celor 6 de ieșiri ale perceptronului.
Generalizând, o subeșantionare poate fi considerată ca intrare într -un clasificator neural
când cel puțin două caractere se găsesc într -o imag ine a unui cuvânt. În segmentarea
caracterelor unite sunt mai avantajoase rețelele neuronale artificiale datorită abilitații de a se
adapta la diferite nivele ale caracterelor ce se suprapun, precum și datorită timpului scurt de
executare a clasificării.
Cele mai multe metode neuronale de segmentare sunt limitate la separare liniară, unde
linia de separație este pe verticală.
I.5 Extragerea trăsăturilor
Prelucrarea imaginilor constă în detectarea liniilor de scriere dintr -o imagine (în cazul în
care carac terele sunt scrise pe mai mult de o linie), detectarea fiecărui caracter din imagine,
reprezentarea caracterelor într -o matrice de valori ce corespund pixelilor alb și negru și
extragerea trăsăturilor.
Pentru extragerea trăsăturilor dintr -o imagine este ne cesară scalarea imaginii fiecărui
simbol într -o matrice de elemente. Pentru că datele conținute în matrice corespund valorilor
fiecărei imagini de un caracter care urmează să fie folosit ca intrare într -o rețea neuronală, se
transformă matricea într -un vec tor de valori caracteristice. O metodă de extragere a
trăsăturilor des folosită este transformata DCTII.
Transformata DCTII are rolul de „concentrare” a energiei și anume informația unui
semnal este repartizată în principal pe coeficienții ce corespund arm onicelor de joasă
frecvență. Astfel, doar un număr mic de coeficienți sunt nenuli și pot fi utilizați pentru
reconstruirea imaginii inițiale prin transformata inversă.
15
(1.1)
unde u,v ia valoare de la 0 la N -1, iar și sunt definite de relațiile:
(1.2)
Relația (1.1) se aplică unei imagini formate din N*N pixeli. Transformata inversă este
definită de relația:
f(x,y )
(1.3)
Reducerea volumului de date compresate vine din suprimarea coeficienților nuli sau
aproape nuli, corespunzători frecvențelor înalte, într ucât reproducerea exactă a acestor
elemente nu este esențială pentru calitatea imaginii. Aplicând această transformată, va rezulta
o matrice cu aceleași dimensiune (N×N), cu valori în virgulă flotantă, slab corelate. Valorile
semnificative ale noii matrici se află în colțul din stânga sus.
Sortarea Zig -Zag este o metodă de vectorizare a matricii DCT, după regula prezentată în
figura de mai jos:
Fig.1.5. Sortare zig -zag
16
Deoarece transformata DCT bidimensională concentrează informația conținută î n
imaginea inițială în colțul din stânga sus a matricii rezultate, după sortarea Zig -Zag, aceeași
informație se va găsi în primele elemente ale vectorului.
I.6 Recunoașterea cuvintelor
Formele relevante a caracterelor scrise de mână sau de tipar pot fi l ocalizate prin
extragerea de trăsături. Există multe abordări în ce privește descrierea caracterelor. O metodă
ar fi utilizarea unui graf al căror noduri corespund formelor extrase din structură, iar muchiile
corespund pozițiilor comune dintre forme. Codar ea grafului se bazează pe repartizarea unor
sloturi predefinite a vectorului caracteristic pentru fiecare nod și muchie a grafului.
Așa cum se observă în Fig.1.6, în clasificatorii paraleli modulari, rețelele artificiale pot
fi folosite pentru implementare a fie a unor sisteme expert, fie a unui multiplexor (combiner).
În Fig.1.6.b este descrisă recunoașterea cifrelor, iar în Fig.1.6.c este prezentată implementarea
multiplexorului cu o rețea neurală în care neuronii din stratul de intrare sunt direct conecta ți la
neuronii din stratul de ieșire. Un clasificator paralel poate fi reprezentat ca în figura 1.6.d.
Un exemplu al unei arhitecturi pentru recunoașterea cifrelor scrise de mână propus
conține zece subrețele independente mai mici, fiecare reprezentând o c lasa separată. Rețele
independente dedicate separării claselor sunt clasificatori autoasociatori. Un autoasociator
(reprezentat în Fig.1.6e) este un perceptron multistrat cu același număr de unități atât la
intrare, cât și la ieșire și cu puțini neuroni în stratul ascuns care își construiește funcția
identitate prin alimentarea sa cu eșantioane din clasa corespunzătoare. Un clasificator poate fi
construit prin hrănirea unor asociatori în paralel (câte unul pentru fiecare clasă) și considerând
modul de deciz ie ce depinde de distanța minimă dintre ieșiri și exemplele introduse. Cu cât
distanța dintre eșantionul de intrare și autoasociatorul clasei corespunzătoare este mai mică,
cu atât este o asemănare mai mare între ele.
În cazul în care numărul claselor este mare, caracterele pot fi împărțite (de ex. în
majuscule, litere mici, cifre și simboluri speciale), iar o rețea separată poate activa un
clasificator specific, așa cum e prezentat în Fig.1.6f. Selectarea clasificatorilor următori se
poate face online sau offline. În selecția online, clasificatorul depinde de modelul de intrare,
iar în cea offline arhitectura este definită pe parcursul învățării în tot timpul clasificării.
17
Fig.1.6: Clasificatori paraleli modulari
Abordarea pe baza segmentării în cuvinte nu poate fi luată în considerare când
localizarea punctelor de separație este dificilă (de exemplu în cazul scrisului de mână). O
alternativă este folosirea recunoașterii holistice (Fig.1.7a) unde cuvintele sunt rec unoscute ca
unități individuale.
Această abordare este efectivă doar dacă cuvintele fac parte dintr -un mic lexicon (de
exemplu la citirea cecurilor bancare).
Au fost propuse multe tehnici de recunoaștere și segmentare integrate (ISR), printre care
numără ș i rețelele neurale cu timp de întârziere (TDNN -Time Delay Neural Network ).
Un algoritm de segmentare a imaginii cuvântului pentru a localiza un număr mare de
posibile puncte de tăiere este prezentat în figura 1.7b. Atunci când se utilizează rețele
neuronal e artificiale pentru tratarea caracterelor întrerupte ce pot apărea în timpul segmentării
eronate (Fig. 1.7b) se folosesc două abordări. În prima abordare se presupune că informația
poate fi furnizată chiar și de caracterele întrerupte și se introduc subcl ase specifice pentru
fiecare clasă. Astfel, un simbol întrerupt poate fi clasificat ca un simbol incomplet dintr -o
anumită clasă. În a doua abordare caracterul întrerupt va fi respins ca „zgomot” de un
18
clasificator, în favoarea găsirii unei alte combinații a unor puncte de separațire care va duce la
reprezentarea imaginii corecte a caracterului.
Fig.1.7: Abordări în recunoașterea unui cuvânt
Rețelele neurale cu timp de întârziere se folosesc în cazul secvențelor temporale și sunt
implementate cu un perceptron multistrat care este „mutat” în întreaga secvență oferind o
etichetare pentru fiecare poziție. În Fig.1.7.c este prezentat un astfel de tip de rețea neuronală
alimentat de o fereastră de mărime fixă ce scanează cuvântul o rizontal. O ieșire este activată
când fereastra acoperă porțiunea dintre două caractere (ieșire „necentrată”) și alta descrie
apartenența caracterului la o anumită clasă (utilizând codarea „ one-hot”) când fereastra este
centrată pe caracter.
Un subiect imp ortant în sistemele de prelucrare a documentelor îl reprezintă verificarea
semnăturilor. Multe abordări au luat în considerare problema recunoașterii falsurilor
aleatoare. Setul de antrenare poate fi construit prin colectarea semnăturilor a unor scriitori,
fară să necesite „falsuri”.
Trăsăturile aleatoare pot fi recunoscute cu un perceptron multistrat cu două ieșiri: una
pentru semnături originale, clasa ω1 și una pentru falsuri aleatoare, clasa ω2. Pentru
rezolvarea problemei, clasificatorul este antrenat numai cu semnăturile unui singur scriitor.
Practic, semnătura este împărțită în regiuni de dimensiuni egale.
19
I.7 Evoluția recunoașterii optice a caracterelor
Încercările inginerești de recunoaștere automată a caracterelor au început înainte de al
doilea război mondial. Dar până la începutul anilor 195 nu a existat o societate comercială
care să finanțeze cercetarea și dezvoltarea tehnologiei. Acest impuls a venit din partea unei
asociații de bancheri americani și a industriei serviciilor financiare. Ei au provocat pe toți
marii producători de echipamente de a veni cu un „limbaj comun” pentru procesarea automată
a cecurilor. Echipamentele primare de recunoaștere optică a caracterelor utilizau surse de
lumină, oglinzi, fante fixe pentru a lăsa să treacă l umina prin ele și un disc în mișcare cu fante
suplimentare. Imaginea reflectată era divizată în detalii discrete de alb și negru proiectate pe
un tub foto -multiplicator și converite electronic în biți. Documentele se rulau cu o viteză
constantă, iar datele imprimate trebuiau să apară într -o locație fixă pe fiecare formular.
Următoarea generație folosea un tub catodic, un creion cu lumină și foto -multiplicatori,
utilizând tehnica „urmărirea curbei”. Acest sistem oferea mai multă flexibilitate atât în
localiz area datelor și a fontului sau proiectarea caracterelor ce puteau fi citite.
Această tehnologie a introdus conceptul de recunoaștere a caracterelor scrisului de mână
automată.
În timp s -a urmărit creșterea acurateții de citit, reducerea sensibilității de s canare a
informațiilor de la intrare, eliminarea necesității unor fonturi speciale și citirea caracterelor
scrise de mână.
Sistemele de recunoaștere a caracterelor optice au progresat, iar aria de domenii în care
au fost aplicate s -a extins mult până în pr ezent: de la citirea cardurilor de credite în scopuri de
facturare, la citirea și transmiterea mesajelor dactilografice (scanner folosit de Forțele Aeriene
a Statelor Unite ale Americiii), în serviciile poștale (citire numelor și adreselor destinatarilor
și imprimarea unui cod de bare pe plic pe baza codului poștal, folosindu -se o cerneală special
vizibilă doar la lumină ultravioletă). Tot prin utilizarea acestei tehnologii s -a încercat crearea
unor mașini de citit pentru orbi.
Actualmente o serie de sistem e de recunoaștere online sau offline sunt disponibile atât
ca programe software cât și ca implementări în anumite dispozitive (telefoane mobile, PDA),
complexitatea fiind crescută de prezența „zgomotului de fond” ca rezultat al stilului de scris și
al vite zei de scriere. Pentru recunoașterea online este nevoie de un stilou special, o suprafață
sensibilă de atingere ce poate fi integrată cu un display adiacent și o aplicație software care
interpretează mișcarea stiloului și transformă curbele în text digital . Primul dispozitiv de acest
20
tip a fost Apple Newton care nu a avut succes comercial deoarece software -ul nu era destul de
performant. Astăzi, un sistem modern de recunoaștere de acest tip se poate găsi în sistemul de
operare Windows XP for Tablet PC, fiin d un notebook cu un ecran sensibil pe care se poate
scrie cu un stilou special.
Cercetătorii companiei Nestor Inc. din SUA au creat un sistem de calcul neuronal care
are ca și dispozitiv de intrare a datelor o tabletă digitizoare pe care se poate scrie. Re țeaua a
fost antrenată cu diferite scrisuri de mână, fiind capabilă să interpreteze un scris de mână
oarecare cu o precizie foarte bună.
21
CAP ITOLUL II: Aspecte generale
referitoare la recunoașterea formelor
II.1 Introducere
II.2 Metrici invariante
II.3 Distanța de tip tangentă
II.4 Determinarea vectorilor tangenți
II.5 Utilizarea altor tipuri de vectori
tangenți
22
II.1 Introducere
Prin recunoașterea formelor se înțelege în mod obișnuit acel ans amblu de metode și
tehnici cu ajutorul căruia se poate realiza o clasificare în cadrul unei mulțimi de obiecte,
procese sau fenomene. Setul de obiecte, procese sau fenomene care urmează a fi clasificate
pot fi obiecte (fenomene) fizice sau structuri intele ctuale, prin acestea înțelegând ansamblul
concretizat de procese legate de o activitate intelectuală coerentă (scris, vorbit, etc) .
Scopul recunoașterii formelor constă în determinarea clasei din care face parte o
colecție de observabile. Metoda este deose bit de utilă atunci când abordarile directe sunt
imposibile .
Stabilirea numărului de clase în care se împart formele este o problemă particulară care
depinde exclusiv de aplicațiile concrete ale metodei.
Acest capitol prezintă câteva metode cu ajutorul că rora se poate obține invarianța
procesului de clasificare în raport cu anumite transformări geometrice elementare. Ținând
cont că în capitolul de față obiectele particulare ce trebuie recunoscute sunt imagini
reprezentând caractere numerice scrise de mână , transformările tipice avute în vedere sunt:
translația pe orizontală și verticală, rotația, scalarea, deformările diagonale și variația grosimii
caracterelor .
Un exemplu al importanței invarianței în recunoașterea imaginilor este prezentat în Fig.
2.1, în care este prezentată o imagine a cifrei șapte ('7') scrisă de mână. Dacă este comparată
cu cele două referințe din partea dreaptă, un clasificator bazat pe distanța Euclidiană va
aprecia în mod eronat că imaginea corespunde cifrei nouă ('9'), deoarece diferența valorilor
pătratice medii este mai mică în cazul primei referințe decât în cazul celei de -a doua. În cazul
în care clasificatorul utilizat ar folosi o metrică invariantă la grosimea liniei desenelor, acesta
va aprecia corect „eticheta” cifrei rep rezentate .
Figura 2.1: Distanța Euclideană a imaginii din stânga este mai mică în raport cu imaginea din
centru decât față de cea din dreapta
23
În această lucrare o imagine X este considerată o matrice de valori reale, care reprezintă
de fapt nivelele de gri ale pixelilor, matrice aflată într -un spațiu discret al imaginilor
1,…….., 1,…….., I J I J
, adică
x
IJ
. Pe de altă parte, prin scanare coloană cu
coloană, o imagine poate fi transformată într -un vector unidimensional, cu dimensiunea
(lungimea vectorului) D = I
J. Nivelul de gri al unui pixel din poziția
,ij va fi notat în
general cu
ijx . Modelarea imagin ilor ar putea fi imaginată și pe domenii continue, caz în care
versiunea discretă se consideră că rezultă în urma unui proces de eșantionare.
Există o varietate de tehnici care asigură invarianța performanțelor de recunoaștere în
raport cu tipuri uzuale de transformări elementare. Astfel de tehnici includ prinre altele:
transformări integrale, calculul unor momente algebrice, utilizarea rețelelor neurale artificiale.
O reprezentare teoretică a invarianței poate fi dată după cum urmează: vom considera
obiect ele analizate ca fiind funcții dintr -un anumit set, de exemplu în recunoașterea imaginilor
:,ij x i j I J x
. Se presupune că există o funcție de clasificare care asociază obiectelor
clase de numere, de exemplu
: 1,…..,r x K
și se def inește un grup de transformări G care
acționează asupra setului de modele, de exemplu
g G:
1,g ijgx x i j , și nu afectează
membrii clasei. Astfel, funcția de clasificare dorită ar trebui să fie invariantă sub acțiunea
grupului, ceea ce înseamnă că
r gx r x g G. În practică, uneori se dorește
restricționarea acțiunii grupului, de exemplu pentru a se putea face deosebirea între numerele
'6' și '9' este necesar ca invarianța în raport cu rotația să fie limit ată la unghiuri mai mici de
180o. Alte proprietați de interes în clasificarea invariantă sunt discriminabilitatea,
complexitatea calculelor, ușurința și viteza de antrenare, posibilitațile de generalizare,
flexibilitatea și posibilitatea refacerii transfor mărilor (invertibilitatea). În unele cazuri se
dorește să se facă diferență între invarianțe globale și locale, în funcție de context și de datele
cunoscute
Un termen des întâlnit în contextul aplicațiilor de recunoaștere a formelor este
normalizare și se referă de obicei la construirea formei canonice a fiecărui model privitor la
transformările avute în vedere. Un inconvenient al acestei metode este acela că poate fi foarte
sensibilă la zgomotul și/sau distorsiunile din model.
Vom prezenta în continua re cîteva dintre metodele utilizate în extragerea de trăsături
invariante în raport cu transformări elementare uzuale:
24
Caracteristici bazate pe Transformata Fourier
Analizând natura caracteristicilor invariante care sunt extrase din imagini, se pot
distin ge două clase principale, una bazată pe invarianță algebrică, respectiv invarianțe care
sunt calculabile prin transformări integrale. Astfel de transformări sunt în general bazate pe
transformata Fourier (FT) și variante ale acesteia. Transformata Fourier continuă
unidimensională a unui semnal
ft și transformata Fourier inversă corespunzătoare sunt
definite prin relațiile:
exp cos sin F f t i t dt f t t i t dt
(2.1)
1exp2f t F i t d
(2.2)
Iar transformata Fourier discretă (DFT) a unui semnal unidimensional și inversa
acesteia pot fi definite prin:
1
02exp 0,1,…., 1M
mi mkF k f m k MM
(2.3)
1
012exp 0,1,….., 1M
ki kmf m F k m MMM
(2.4)
Transformata Fourier este un instrument important și binecunoscut în multe domenii, în
parte datorită existenței unui algoritm rapid de calcul numit Fast Fourier Transform –
Transformata F ourier Rapidă (FFT). Pentru extragerea caracteristicilor invariante o altă
proprietate a transformatei Fourier este importantă și anume: invarianța la translația modelului
a amplitudinii pătratice a spectrului FT (numit și spectrul de puteri). Aceasta are legătură cu
faptul că o translație a modelului corespunde unei schimbări de fază în domeniul Fourier, care
25
nu afectează amplitudinea. Utilizând această proprietate de invarianță a spectrului de puteri se
poate obține un set de caracteristici invariante la translație utilizând spectrul de puteri a unui
model dat ca vector caracteristic. Pentru a face aceasta trebuie luat în considerare faptul că
ignorând faza spectrului o parte importantă din informație este pierdută, ceea ce poate
influentă clasificarea. Da că transformata Fourier este aplicată unui obiect multidimensional,
de exemplu unei imagini, ecuațiile si proprietătile se determină analog.
Caracteristici bazate pe transformata Fourier -Mellin
Dacă se dorește invarianță și la alte transformări în afară de cele de translație, se pot
folosi variante ale transformatei Fourier, un exemplu fiind transformata Mellin. Aceasta este o
transformată Fourier evaluată pe o scară exponențială, care este invariantă la transformările de
scală. Dacă sunt combinate aspect e ale transformatei Fourier cu aspecte ale transformatei
Mellin și se face trecerea la coordonatele polare ale unei imagini (rezultand o transformată
Fourier circulară, sau o transformată Mellin radială), se poate obține invarianță la rotație,
scală și tra nslație simultan. Transformata este denumită Transformata Fourier -Mellin și poate
fi calculată după cum urmează:
se calculează spectrul de puteri al transformatei Fourier al intrării bidimensionale.
Acesta este invariant la translație.
se face conversia s pectrului de puteri în coordonate polare. Acesta realizează
conversia rotației în translație.
se realizează o mapare complex -logaritmică. Aceasta realizează conversia
transformărilor de scală în translație.
se calculează un nou spectru de puteri al transfo rmatei Fourier bidimensionale. Acesta
va fi invariant la rotație, translație și transformări de scală.
Caracteristici bazate pe momente
Momentele geometrice sau momentele regulate în două dimensiuni sunt definite astfel:
, ,pq
pqm x y f x y dxdy
(2.5)
și analog pentru funcții discrete ca imaginile digitale relațiile sunt date de:
,
11,IJ
pq
pq
ijm i j f i j
(2.6)
26
Unele dintre aceste momente admit o interpretare sugestivă, de exemplu
0,0m
corespunde suprafeței obiec tului, iar
1,0 0,0/mm corespunde primei coordonate a centrului de
gravitate. Pentru a fi invariant la translație, se pot folosi momentele centrale și imaginea
centralizată:
1,0 0,1
,
11 0,0 0,0,pqIJ
pq
ijmmi j f i jmm
(2.7)
Mai mult, pent ru a fi invariant la transformări de scală, se folosesc momentele
normalizate, descrise prin relația:
12
, , 0,0 / , 2,3,…pq
p q p q pq
(2.8)
Combinații de aceste momente de bază au fost propuse drept caracteristici invariante,
care sunt invariante la translație, rotație și transformări de scală. Aceste caracteristici
invariante lucrează bine numai cu modele binare, în absența distorsiunilor și/sau a
zgomotului. O altă formă a momentelor bazată pe perechi de polinoame ortogonale Zerni ke
sunt momentele Zernike , care sunt invariante la rotație și chiar RTS invariante dacă sunt
normalizate și depășesc în performanțe alte tipuri de momente.
II.2 Metrici invariante
În timp ce normalizarea și extragerea caracteristicilor semnificat ive au ca scop
asigurarea invarianței înaintea procesului efectiv de clasificare, invarianța poate fi de
asemenea încorporată direct în clasificator, prin folosirea unor metrici (distanțe) speciale. O
metrică invariantă ar avea, în mod ideal, proprietatea că distanța între două modele este
întotdeauna egală cu distanța minimă dintre cele mai apropiate două versiuni transformate ale
acestora. Un mod intuitiv de a introduce o astfel de metrică pornește de la definirea structurii
descrise de diversele versiuni transformate ale obiectelor analizate. Astfel, obiectul original,
ca și oricare alt obiect rezultat în urma aplicării unor transformări elementare, pot fi privite ca
puncte distincte aparținând unui spațiu multidimensional. Este rezonabil să ne imaginăm c ă
aceste puncte nu sunt însă răspândite la întâmplare în acest spațiu, ci se găsesc „aglomerate”
sub forma unor structuri specifice, în cazul cel mai simplu de tipul unor hiperplane. În
general, aceste structuri nu pot fi evaluate cu precizie, ci pot fi nu mai aproximate. Conceptul
27
riguros din punct de vedere matematic este cel denumit “varietate” ( manifold ), iar metricile
aferente unor aszfel de structuri poartă denumirea de distanță de tip manifold (manifold
distance ). Am putea spune că un manifold este un mod de a combina laolaltă bucăți din
n
.
Deși un manifold are aceleași proprietăți locale ca și
n
acesta poate avea proprietăți globale
diferite. Putem de asemenea privi un manifold ca pe o generalizare a noțiunii de suprafațăi în
n
. Principala problemă cu noțiunea de distanță manifold este aceea că în multe cazuri este o
problemă dificilă determinarea distanței minime, deoarece manifold -urile sunt dificil de
utilizat. O soluție la această problemă constă în a urmări suprafața manifold -ului în pași mici,
metodă care amintește de metoda Euler -Cauchy de rezolvare a ecuațiilor diferențiale.
Cea mai uzuală metrică este distanța Euclidiană (pătratică), care este specifică
distribuției normale (cu matricea identitate ca matrice de covarianță). Pentru imagini distanța
Euclidiană pătratică este definită de relația:
2 2
11,IJ
ij ij
ijd x x x
(2.9)
Există multe alte metrici (similare) folosite în recunoașterea formelor, cum ar fi
produsul scalar a doi vectori
1DT
dd dxx , care este folosit ca măsură a similarității și
este legată de unghiul
dintre doi vectori:
arccos cosTTxx
xx
(2.10)
unde cosinusul unghiului este numit produs scalar normalizat. O conexiune cu distanța
Euclidiană este dată de relația :
2 2 22Tx x x
(2.11)
care poate fi simplificată dacă cei doi vectori sunt normalizați la
1 x la
221Txx
.
28
Metricile nu sunt invariante la variații în imagine de tipul transformări de potrivire, de
fapt ele sunt foarte senzitive la astfel de distorsiuni. În contextul recunoașterii obiectelor
imagine Simard a introdus o nouă metrică invariantă local numită distanța de tip tangentă.
O cale simplă de a integra invarianța în clasificator este de a extinde baza de date
avută la dispoziție prin generarea unor date virtuale obținute prin aplicarea unor transformări
elementare asupra datelor originale. Eficiența metodei menționate constă în generarea tuturor
transformărilor posibile cu scopul de a se obține invarianță completă, dar această ab ordare
este dificil de aplicat în practică. Ca urmare, de obicei multiplicarea datelor se rezuma la
aplicarea unui subset limitat de transformări (de exemplu, translații cu un număr finit de pixeli
sau rotații cu un unghi maxim acceptabil). Metoda se aplic ă de obicei datelor de antrenare, dar
poate fi aplicată și pentru datele de test. Două dezavantaje ale acestei metode ar fi că
utilizatorul trebuie sa aleagă mărimea parametrilor transformărilor și numărul de imagini ce
vor fi generate, respectiv că datele generate sunt strâns corelate.
II.3 Distanța de tip tangentă
În 1993, SIMARD et al. a propus o metrică invariantă numită distanța tangentă (TD)
care s -a dovedit a fi foarte eficientă în special în domeniul aplicațiilor de recunoaștere a
caracterelor scrise de mână. Autorii au observat că transformări rezonabil de mici ale unor
anumite obiecte imagine nu afectează membrii claselor. Metricile usuale, simple, ca de
exemplu distanța Euclidiană nu au această proprietate, ele fiind foarte sensibile la transformări
ca translație, rotație, modificări ale scalei, deformarea axelor. Atunci când o imagine este
transformată (de exemplu este scalată sau rotatită) printr -o transformare
( , )tx care depinde
de L parametri
L
(de exemplu factorul de scalare sau unghiul de rotație), setul tuturor
formelor care au suferit transformări:
,:L I J
xM t x
(2.12)
definește un manifold de dimensiune L în spațiul formelor. Distanța dintre două forme poat e fi
definită acum ca minimul distanței (pătratice) dintre manifold -urile acestora, fiind cu adevărat
invariantă în raport cu cele L transformări:
29
2
,, min , ,
L
xManifold xd x t x t
(2.13)
Din păcate, calculul acestei distanțe manifold implică o problemă dificilă de optimizare
neliniară, iar manifold -urile, în general, nu au o expresie analitică, deoarece, de exemplu, o
simplă translație a imaginii corespunde unei transformări cu grad ridicat de neliniaritate în
spațiul multidi mensional al pixelilor. De aceea, mici transformări ale formei
x sunt
aproximate de un subspațiu tangent
xM la manifold -ul
xM în punctul
x . Acest subspațiu es te
obținut prin adăugarea unei combinații liniare a vectorilor
, 1, ,lx l L
la
x care realizează
învârtirea subspațiului tangent. Vectorii
, 1, ,lx l L
sunt derivate parțiale ale
( , )tx în
raport cu
l . Acești vectori tangenți
,
l
ltxx
sunt așa numitele derivate Lie ale
transformărilor. Utilizând aproximarea prin seria Taylor de ordinul întâi a transformatei
,t
în jurul l ui
0 se obține:
2
11,,LL
l l l
ll ltxt x x O x x
(2.14)
Expresia de mai sus reprezintă o aproximare de ordinul întâi a manifold -ului
xM , care
are avantajul considerabil de a fi o funcție liniară după
. De aceea este ușor manevrabilă din
punct de vedere analitic sau din punctul de vedere al complexității calculelor.
1:L
L I J
x l l
lM x x
(2.15)
Vectorii tangenți
lx pot fi calculați utilizând diferențele finite dintre imaginea originală
x
și o transformare rezonabil de mică a imaginii
x . Calculul vectorilor tangenți va fi detaliat
în cele ce urmează. Ex emple de imagini care au fost calculate cu relația (2.15) sunt prezentate
în figura de mai jos (imaginea originală se află în stânga figurii).
Figura 2.2: Exemple de vectori de tip tangentă corespunzători imaginii din stânga
Descrierea transformării de către aproximarea tangentă este local invariantă dar nu și
invariantă invariantă global. Acesta poate fi un dezavantaj în unele cazuri, dar poate fi de
30
asemenea și un avantaj, deoarece invarianța globală în multe cazu ri nu este dorită. De
exemplu nu este dorită invarianța completă la rotație în cazul recunoașterii cifrelor sau nu este
dorită pentru a compara toate imaginile la o scară de un pixel.
Câteva exemple de aproximare liniară sunt prezentate în figura de mai jo s, care
reprezintă imagini ale cifrei '5' obținute prin deplasarea imaginii originale și găsirea celei mai
apropiate imagini în subspațiul tangent al translație. În parte din dreapta este prezentată o
reprezentare schematică. Se poate observa că imaginea a proximată corespunde bine imaginii
translate pentru deplasamente de un pixel (a doua și a patra coloană), dar spațiul tangent liniar
nu poate descrie satisfăcător translații cu un număr mare de pixeli (spre exemplu în coloanele
exterioare, imaginile sunt a proape identice cu cele obținute prin deplasări cu un singur pixel).
Figura 2.3: a) Linia superioară conține imaginile originale, care corespund unor
translații cu 1 -2 pixeli spre stânga și dreapta. Pe linia inferioară sunt indicate imagini obținute
prin aproximări de tip tangentă aplicate imaginii din colțul din stânga sus;
b) Ilustrarea schematică a tangentei la manifold
Figura 2.4: Ilustrarea schematică a tangentei la manifold în cazul rotației
31
În ese nță, distanța de tip tangentă reprezintă distanța minimă dintre structurile de tip
manifold corespunzătoare celor 2 vectori comparați. Deoarece această structură este dificil de
calculat cu exactitate, se poate determina distanța dintre hiperplanele (tangente la vectorii
comparați) definite de s etul de vectori x l introduși în relația (2.15). Astfel, este posibilă
definirea unei distanțe tangentă utilizând aproximații determinate numai pentru unul dintre
vectorii de interes, caz în care distanța este denumită unilaterală ( single -sided ), sau pentru
ambii vectori, distanța fiind denumită bilterală ( double -sided ). Definițiile corespunzătoare
sunt date în relațiile de mai jos:
2
,
1, min
LL
SS x l l
ld x x x
(2.16)
2
,11, min
L
xLL
DS xl l l l
lld x x x
(2.17)
O reprezentare grafică sugestivă este indicată în Fig. 2.5, care ilustrează diferența dintre
distanța euclideană și distanța de tip tangentă.
Figura 2.5: Ilustrarea grafică a distanței de tip tangentă
32
Trebuie acordată atenție la extrapolarea acestei figur i la subspații de dimensiuni mai
mari, deoarece probabilitatea ca liniile (respectiv hiperplanele) să se intersecteze în spații de
dimensiuni mai mari este mult redusă.
Minimizarea poate fi ușor realizată deoarece problema de optimizare este liniară.
Aceasta presupune rezolvarea unei probleme de tip least squares , care în cazul distanței
unilaterale (calculate față de vectorul notat cu x) conduce la următoarea relație de calcul a
valorilor optime ale parametrilor α l:
1
11()
()T
opt xx x
T
xx x xT T x
T T T
(2.18)
Diferența dintre distanța euclideană și cea de tip tangentă este ilustrată în Fig. 2.6:
imaginea cifrei „3” este translată pe orizontală cu un număr de pixeli indicat pe axa
absciselor, după care se calculeaz ă distanța dintre imaginea astfel obținută și cele 10 imagini
prezentate pe linia inferioară. Astfel, se observă că pentru deplasări cu mai mult de 3 pixeli,
distanța euclideană dintre imaginea translată a cifrei „3” și imaginea cifrei „7 ” devine mai
mică decât distanța față de imaginea netranslată a cifrei ‚3’, astfel încât în acest caz rezultatul
clasificării ar fi eronat. În schimb, în cazul distanței de tip tangentă pot fi tolerate translații de
până la 6 pixeli și încă rezultatul clasificării este cor ect. Această concluzie își păstrează
valabilitatea și în cazul celorlalte transformări elementare.
Figura 2.6: Comparație între distanța euclideană și cea de tip tangentă
33
II.4 Determinarea vectorilor tangenți
Distanța de tip tangentă a fost introdusă i nițial în contextul aplicațiilor de recunoaștere a
caracterelor scrise de mână. Ca urmare, natura transformărilor elementare care pot interveni
se referă la translații pe axa orizontală și verticală, rotații în planul imaginii, variații de scală,
modificar ea grosimii caracterelor. La acest ea se adaugă 2 tipuri de distor siuni diagonale,
ilustrate în Fig. 2.7:
Figura 2.7: Exemple de caractere scrise de mână afectate de transformări:
Prima coloană: imaginea originală, coloanele 2 – 8: direcția pozitivă a tangentei,
coloanele 9 – 15 direcția negativă a tangentei
Deși aceste transformări s -au dovedit a fi utile în special pentru recunoașterea cifrelor
scrise de mână, distanța tangentă poate fi folosită în principiu cu orice transformare căreia îi
poate fi calculată derivata într -un anumit punct. În cele ce urmează va fi descrisă derivarea
celor șapte tangente de bază. Să considerăm transformările aplicate imaginilor descrise de
relația:
'
5 12
'
34 61
1ii
j j
(2.19)
Se pot determina derivatele x l corespunzătoare celor 7 transformări prin particularizarea
relației anterioare, după cum urmează:
34
translație orizontală:
''
5 0, 1,2,3,4,6l l i i j j
55
105,,, limx i j x i jx i j
(2.20)
translație verticală:
''
6 0, 1, ,5l l i i j j
66
206,,, limx i j x i jx i j
(2.21)
rotație:
''
2 3 2 1 0, 1,4,5,6l l i i j j j i
222
302,,, limx i j j i x i jx i j
(2.22)
222 2 2 2
0022, , , ,lim limx i j j i x i j i x i j i x i j
12,,jx i j ix i j
scalare:
''
1 4 1 1 0, 2,3,5,6l l i i i j j j
4 1 2, , ,x i j ix i j jx i j
(2.23)
deformarea axelor:
''
2 3 3 3 0, 1,4,5,6l l i i j j j i
5 1 2, , ,x i j jx i j ix i j
(2.24)
deformarea diagonalei:
''
1 4 4 4 0, 2,3,5,6l l i i i j j j
6 1 2, , ,x i j ix i j jx i j
(2.25)
deformarea datorată îngroșării liniei:
35
22
7 1 2, , ,x i j x i j x i j (2.26)
În cele ce urmează va fi prezentată o cale diferită de obținere a derivatelor tangentelor,
care permite să se țină cont ușor și de alte transformări ale imaginii procesate. Astfel,
imaginile sunt considerate ca funcții continue
:x
. Se va considera o transformare
a coordonatelor care definesc planul imaginii
:t
de forma:
1 2 1 2 5 3 4 6 , , , , 1 , 1t i j t i j t i j i j i j
(2.27)
Pentru fiecare punct al imaginii , derivatele parțiale în raport cu parmetrii transformărilor
se cal culează prin derivări succesive:
x x t
t
(2.28)
unde
x
t
este compus din gradienții locali după x și după y, ceea ce înseamnă că:
, , , ,x x xi j i j i jt i j
(2.29)
Următoarele două exemple ilustrează acestă abordare:
translație după x (
0, 1,2,3,4,6l l )
50
5| , 1,0tij
(2.30)
50
5, | , , , 1,0 ,T x x x xi j i j i j i ji j i
(2.31)
Aceasta înseamnă că derivata este gradientul după x.
scalare (
14 , ceilalți parametri sunt zero)
0 , | ,ti j i j
(2.32)
36
50
5, | , , , , , ,T x x x x xi j i j i j i j i i j j i ji j i j (2.33)
ceea ce confirmă rezultatul anterior.
Această derivare este mai ușor de extins pentru a se putea aborda și alte transformări, de
exemplu transformări de tipul:
1 2 5 3 4 6
12
7 8 7 811, , , , ,11i j i jt i j t i j t i ji j i j
(2.34)
Tangentele rezultate sunt aceleași pentru primii șase parametrii, iar pentru cei doi
rămași se obțin rezultatele:
22
7 1 2, , , , ,xxx i j i i j ij i j i x i j ijx i jij (2.35)
22
8 1 2, , , , ,xxx i j ij i j j i j ijx i j j x i jij (2.36)
Trebuie menționat în cele din urmă că există o a treia cale de a deriva tangente, utilizând
aproximarea Taylor de ordinul întâi cu valorile parametrilor pentru transformări de identitate
și apoi diferen țiind în raport cu parametrii transformărilor, metodă care dă rezultate similare
cu cele de mai înainte.
Pentru a determina derivatele pe direcțiile orizontală și verticală pentru locații
individuale ale pixelilor, trebuie aleasă o metodă potrivită naturi i discrete a imaginilor digitale
(deoarece noțiunea de derivată este un concept aplicabil în domeniul continuu). Pentru aceasta
există trei posibilități:
utilizarea diferențelor finite
convoluție cu o funcție de tip smooth kernel (lină, netedă), care gene rează o
funcție diferențiabilă, apoi aplicând derivarea
netezirea imaginii și utilizarea diferențelor finite
În acest sens se poate utiliza o funcție Gaussiană, a cărui parametru de dispersie
controlează localizarea vectorilor tangenți obținuți. În practic ă s-a utilizat cu succes
operatorul Sobel , care combină diferențierea cu filtrarea de tip smooth kernel . Cele patru
variante direcționale ale acestui operator sunt date mai jos:
37
/\1 0 1 1 2 1
112 0 2 0 0 0441 0 1 1 2 1
0 1 2 2 1 0
111 0 1 1 0 1442 1 0 0 1 2ijSS
SS
Pentru calcularea tangentei, doar filtrul vertical și cel orizontal sunt necesare, dar
utilizarea operatorilor diagonali ar putea fi o extensie folositoare, atunci când se dorește
modelarea deplasării pe o direcție dioagonală a pixelilor. În literatură se descrie și o variantă
ușor modificată a operatorulu i Sobel, descris în Fig. 2.8 (este descrisă numai matricea
corespunzătoare deplasării pe orizontală, cea valabilă pentru direcția verticală este rezultatul
rotirii cu 90°).
Figura 2.8: Operator Sobel modificat
II.5 Ut ilizarea altor tipuri de vectori tangenți
Folosirea vectorilor descriși anterior pentru evaluarea distanței de tip tangentă nu
reprezintă singura opțiune avută la dispoziție. În literatură a fost propusă și utilizată cu succes
o alternativă bazată pe alege rea drept set de coordonate a hiperplanului care aproximează
structurile de tip manifold a vectorilor generați prin metoda denumită Analiză pe Componente
Principale (PCA). În esență, acesta reprezintă o metodă optimală de compresie bazată pe
utilizarea une i transformate liniare descrise de o matrice ale cărei coloane sunt formate din
vectorii proprii semnificativi ai matricii de covarianță a datelor din setul de antrenare (în
prealabil, imaginile originale, presupuse de dimensiune (MxN), sunt transformate î n vectori
de aceeași lungime, prin concatenarea coloanelor corespunzătoare ). Algoritmul este
următorul:
38
1. Se calculează valoarea medie a imaginilor care formează setul de antrenare
(presupus a avea un număr total de K imagini):
KI
IK
jj
1
(2.37)
2. Se „centrează” imaginile originale (se aduc la valoare medie nulă):
II Ijcentrat
j (2.38)
3. Se calculează așa -numita scatter matrix , care reprezintă aproximarea matricii
de covarianță a imaginilor din baza de date (aproximarea este cu atât mai bună cu cât avem
mai multe imagini la dispoziție):
TAAKS1
(2.39)
unde matricea A are pe coloane câte o fotografie centrată:
kNMcentrat
kcentrat centratI I IA ……..2 1
(2.40)
Matricea S este simetrică și are dimensiuni (M*N) x(M*N).
4. Se calculează valorile și vectorii proprii ai matricii S
Observații:
– se poate utiliza un artificiu care reduce volumul de calcul (se calculează valorile și
vectorii proprii ai matricii
AAT și apoi se folosește relația cu valo rile și vectorii proprii ai
matricii S).
– valorile proprii ale matricii S sunt întotdeauna pozitive (deoarece S este reală și
simetrică).
Ca terminologie, vectorii tangenți calculați prin metoda descrisă în subcapitolul
precedent sunt denumiți vec tori a priori , iar cei calculați prin metoda PCA sunt denumiți
vectori estimați.
39
În Fig. 2.9 se prezintă setul de vectori tangenți corespunzători setului de 7 transformări
elementare descrise în paragraful anterior, respectiv vectorii obținuți prin aplica rea metodei
PCA.
a) b)
Figura 2.9: Exemple de vectori tangenți obținuți prin: a) aplicarea transformărilor
elementare;
b) metoda PCA
40
CAPITOLUL III: Retele neural e
recurente de tip gradient
III.1 Introducere
III.2 Modelul memoriei asociative invariante
recurente
41
III.1 Introducere
O noua abordare a recunoa șterii formelor invariante este propusă pe baza unui tip de
gradient special, recurent cu memorie asociativ ă analogică. Sistemul prezintă puncte stabile
de echilibru în poziții predefinite specificate de vectorii de trăsături extrași din setul de
antrenament, în timp ce invarianța la transformari geometrice se deduce cu ajutorul distanței
de tip tangentă. Rezultate experimentale privind recunoașterea caracterelor scrise de mână
indică faptul că abordarea propusă poate produce performanțe superioare față de soluțiile
clasice pe baza distanței euclidiene metrice. Extensi ile posibile față de modelul modular și
secvențial de recunoastere sunt prezentate în cele ce urmeaza.
Cum să deduci invarianța la transformările elementare a reprezentat unul dintre
aspectele cheie ale literaturii de recunoaștere a formelor în ultimele d ecenii. În funcție de
sarcina ce o avem de executat, această problemă se adaugă la o listă de alte aspecte dificile,
cum ar fi: de -a face cu un număr limitat de probe de pregătire, ocluzie parțială, sau
variabil itatea iluminării, pentru a enumera doar câte va. Robustețea împotriva transformărilor
geometrice fine, cum ar fi: translă ri, rotații, sau schimbări la scală este de obicei abordată de
către una dintre următoarele metode:
metoda cu algoritmi de preprocesare cu scopul de a extrage caracteristici invar iante
specifice de la modelele originale;
metoda in care efectul aplicării acestor transformări pot fi integrate în definiția însăși a
distanței metrice .
Metodele aparținând primei abordări sunt de obicei mai simple și exemplele (de ordin
superior) incl ud funcții de autocorelație , precum și caracteristicile spectrale ale imaginilor
diagramei polare . A doua clasă de metode este ilustrată de distanta ta ngentă (TD), de
imaginea distanț ei euclidiane (IMED), și metoda cu șabloane deformabile.
Proceduri stan dard de clasificare, cum ar fi: vecinii k cei mai apropiati sau regula
Bayesiana au fost utilizate pe scară largă în aplicații de recunoaștere a unui model, și un
corpus foarte mare de literatura de specialitate a fost dedicată analizei bazelor lor teore tice,
limitările, și performanțe practice. Cu toate acestea, mai multe tehnici recente de clasificare au
apărut, de asemenea, ca potențiale soluții alternative. Acestea au fost introduse în special în
42
contextul rețelelor neuronale, și exemplele includ Supp ort Vector Machines (SVM) ,
autoasociaț iile neuronale, precum si memoriile asociative. Prezenta contribuție introduce o
abordare noua pentru recunoaș terea formelor invariante bazate pe o combinație de două
elemente prezentate mai sus, și anume un tip specia l de memorie asociativă (recurentă ) și o
distanță metrica invariantă precum distanța tangentă (TD).
Memoriile asociative reprezintă una dintre cele mai interesante aplicații ale rețelelor
neuronale artificiale și multe soluții au fost raportate în literatu ra de specialitate. Practic, un
set de tipare este stocat prin utilizarea unei baze de date de pregătire și o procedură de învățare
corespunzătoare. În faza de testare, sistemul ar trebui să produca rezultatele corecte, chiar
dacă există date zgomotoase, i ncomplete sau denaturate ce sunt aplicate ca intrare. Două
strategii sunt utilizate în principal, în funcție de tipul de arhitectura care se utilizează:
a) pentru rețele feedforward (de obicei algebrice) se utilizeaza dependențe
funcționale între intrare res pectiv datele țintă , și sunt aproximate bazandu -se pe
informații de pregătire limitate. Dacă rețeaua are capabilități de generalizare,
s-ar ocupa cu succes de date de testare nevăzute anterior;
b) pentru rețele recurente, memoriile dorite sunt stocate ca stăr i stabile ale
sistemelor dinamice. Atunci când sunt îndeplinite anumite condiții astfel de
sisteme sunt în general stabile și dinamica va evolua de la orice stare inițială, la
un echilibru stabil particular și niciun alt comportament complex nu poate
apăre a . Astfel de sisteme ar trebui să respecte următoarele cerințe:
nicio amintire neautentica (stări stabile care nu corespund cu cele dorite) nu ar
trebui să existe;
numărul de echilibre dorite ar trebui să fie arbitrar de mare și dimensiunea
bazinelor afe rente de atracție trebuie să fie controlabilă;
adaugarea / eliminarea unui echilibru trebuie efectuată fără reproiectarea
întregului sistem.
Distanța tang entă a fost introdusă în aplicaț ii pentru recunoașterea optică a caracterelor
(OCR) ca o alternativ ă la distanța euclidiană clasică, distanța care este cunoscută a fi foarte
sensibilă la transformări geometrice, cum ar fi translari, rotații, sau schimbări la scară.
43
Această valoare este definită ca valoarea minimă (la pătrat) a distanței dintre toate var iantele
care sunt generate de un set de modelele transformate. Din moment ce aceste manifold -uri, în
general, nu au o expresie analitică, o solutie naturală este de a folosi o aproximare adecvată.
Simard a propus ca o aproximare valabilă subspaț iul tangen t obținut prin adăugarea la
vectorul curent o combinație liniară a vectorilor tangenti corespunzători a șapte transformări
distincte.
III.2 Modelul memoriei asociative invariante recurente
Detaliile de proiectare cu privire atât la memoria asoci ativă cât și la distanța metrică
implicată sunt prezentate mai jos. În timp ce cele două componente au fost folosite în mod
separat anterior, combinația lor este nouă și poate produce performanțe superioare în aplicații
de recunoaștere a modelelor invariante.
Princ ipalele dezavantaje ale soluțiilor existente pentru proiectarea memoriei asociative
țin de prezența a numeroase stări false și capacitatea memoriei care este limitată. În scopul de
a atenua acestea, vom folosi un sistem dinamic special de tip gradient definit în conformitate
cu:
(3.1)
în care V(X) reprezintă o funcție de tip Liapunov.
Deși utilizat cu succes pentru rezolvarea unor probleme practice import ante, modelul
prezintă unele limitări majore, printre care prezența unor puncte de echilibru stabil “parazite”
sau capacitatea de stocare redusă în aplicații de memorie asociativă. În literatură au fost
propuse soluții care să diminueze aceste dezavantaje, bazate de regulă pe modificarea funcției
de activare a neuronilor elementari. În mod concret, multe aplicații practice importante
necesită sinteza unor sisteme capabile să ofere următoarele caracteristici:
Un rezultat binecunoscut în teoria sistemelor din amice neliniare afirmă că punctele de
echilibru stabil ale unui sistem de tip gradient coincid cu minimele izolate ale funcției
Liapunov . Ținând cont de aceasta, o soluție interesantă la cerințele formulate anterior o
constituie definirea funcției Liapuno v într -o manieră particulară, sub forma unei sume de
44
funcții individuale cu selectivitate spațială, fiecare având un minim accentuat în dreptul unui
singur punct și fiind practic constante în rest .
1( ) ( )M
mm
mV X w g X
(3.2)
unde M este numărul de memorii ce urmeaza să fie stocate,
mw sunt ponderi scalare, și
funcțiile
()mgX sunt alese ca:
(3.3)
unde dp(X,X m) este distanța indusă prin măsura L p definită pe spațiul vectorial N-
dimensional.
Ca o consecință, ecuațiile care reglementează dinamica sistemului devin:
(3.4)
La utilizarea funcțiilor selective d e tip Gaussian a spațiului , ecuația (3.2) defineșt e o
functie specială (RBF) o extensie a functiei V(X) Lyapunov , unde punctele de echilibru
dorite acționează ca centre.
O imagine intuitivă asupra funcției Liapunov definite mai sus se prezintă în Fig. 3.1 (N=2,
M=4; punctele de echilibru sunt: ( -1,-1), (-1,1), (1, -1), (1,1), iar σ s=1).
În Tabelul 7.2 se prezintă ecuațiile corespunzătoare sistemului propus, pentru două tipuri
de distanțe, L2 (Euclidiană) și L1 (Manhattan). Atenție specială trebuie acordată cazului în care
se utilizează distanța L1, deoare ce funcția modul nu este derivabilă. O aproximație valabilă
pentru funcția modul este dată de:
x)( = (x)f ; x))( (1 = f(x) tanh coshln
(3.5)
45
,unde α este un parametru real care controlează panta derivatei în origine.
Fig. 3.1: Exemplu de funcție Liapunov cu valori minime izolate
Tabelul 3.1: Ecuațiile diferențiale care descriu sistemul de tip gradient cu funcția Liapunov
Distanța L2:
)x-x( = )XX,2s
iiN
1=is (d2
e)x-x(1- = ) e-(1
x – =
xV- = x22)2xsj-xj(N
1=j-
2s2)2xsj-xj(N
1=j-
siiM
1=s2M
1=si ii
Distanța L1:
|x-x| = )XX,s
iiN
1=is (d1
e)x-x(
21- = ) e-(1
x – =
xV- = x22|xsj-xj|N
1=j-
2s2|xsj-xj|N
1=j-
siiM
1=s2M
1=si ii
tanh
46
Procedu ra de proiectare propus ă are urmatoarele avantaje:
corespondența clară între setul de memorii care urmează să fie stocate și ecuațiile care
reglementează dinamica sistemului;
interpretare transparentă a efectu l parametrilor (centre, ponderi , lățime) pe ti mpul și
evoluția starii spațiului;
convergență garantată bazată pe teoria stabilității Lyapunov, și avantajele
inplementării în ceea ce privește numărul limitat de interconexiuni.
Modul de operare a memoriei asociativ recurente care acționează ca un clas ificator este
destul de unidirectional: atunci când un model de test este prezentat sistemului c ăruia îi este
aplicat ca o condiție inițială asupra sistemului dinamic (neuronal), care la rândul său se va
stabiliza în cele din urmă până la unul din punct ele de echilibru , sperăm să se stabilizeze la
unul obținut de la un model de formare a clasei corecte.
În conformitate cu pozițiile imaginilor de formare, bazine complexe de atrac ție sunt
dezvoltate în jurul punctelor de echilibru, care pot include în afa ră de imaginile de testare
disponibile, multe altele, de exemplu, cele corespunzătoare versiunilor neclare, distorsionate
sau zgomotose din setul de antrenare. În acest sens, este de remarcat faptul că alegerea corectă
a parametrilor individuali ofera o manieră suplimentară pentru modelarea bazinelor de
atracție.
Mai mult decât atât, clasificatorul neural propus prezintă modularitate implicită, în care
stocarea memoriilor suplimentare nu influențează pozițiile celor stocate anterior și, mai
importan t, dinamica sistemului , prin urmare, soluția finală este influențată doar de o mică
parte din existenta echilibrului stabil (în mod ideal, doar de un singur punct stabil al cărui
bazin de atracție a vectorului de testare în care se încadrează ).
În cazul în care abordarea propusă este superioară față de cel mai apropiat clasificator
standard vecin, merită să discutăm de ce vectorii de test mai aproape (în ceea ce privește
distanța euclidiană) de un model de formare specifică pot cădea în continuare în ba zinul de
atracție a altuia. Răspunsul este strâns legat de forma peisajului energiei corespunzătoare
V (X), care este puternic influențată de parametrii lățime . Avem două opțiuni:
47
Fig 3.2 Efectul parametrului lățime și distribui rea pe atractori a funcției Lyapunov (lățimi
inegale)
1) Folosind valori distincte pentru acei parametri, ca în figura de mai sus: modelul T se
încadrează în bazinul de atracție a modelului P2, datorită lățimii mai mari, deși T este
mai aproape de P1.
Acest lucru poate fi justificat de exemplu prin luarea în considerare formularea funcției
Lyapunov ca model combinat Gaussian (GMM), a cărui parametrii sunt obținuți prin
utilizarea (EM) algoritmului maximizarii asteptarilor. Oricum, pe langa binecunoscuta non –
unicitate a solu ției, procedura nu garantează că centrele care rezultă corespund cu cele dorite:
dacă centrele rezultate sunt prea apropiate unele de altele, acestea ar putea fuziona într -altul,
unul fals. Un efect motivat biologic cunoscut sub numele de amorsare (utilizat pe scară largă
pentru construirea de modele psihologice ale cunoașterii umane ), se poate crea , de asemenea,
folosind diferiti . Practic, efectul înseamnă atingerea mai rapidă unui anumit atractor dacă
a fost vizitat recent. Amor sare ar putea fi realizată prin creșterea probabilității de ajunge la un
anumit model vizitat recent prin extinderea bazinelor de atracție din jurul lui. Acest lucru este
implementat prin creșterea valorii parametrului lățime (și, dacă este necesar , cresterea
ponderii wm)
2) Folosind o valoare comună sm: Un alt model biologic cunoscut sub numele de efect
bandă poate explica eficiența acestei alegeri. Aceasta se referă la influența rec iprocă
între atractori, generată de distribuirea lor spațială. Exemp lul din Fig. 3.3 și 3.4 arată
că, deși punctul T este mai aproape de punctul P1, acesta încă evoluează spre P3.
48
Coordonatele specifice sunt urmatoarele: P1( 1, 0) , P2(0.5, 0.7) , P3(1, 0) , P4(0.5, 0.7),
T(0.1, 0). Distanțele dintre T și punctele P1 –P4 este {0.9, 0.922, 1.1, 0.992}.
Fig 3.3 Efectul parametrului lățime și distribuirea pe atractori a funcției Lyapunov
(lățimi egale) domeniu de definiție a funcț V(X)
Fig 3.4 Evoluția în timp pe perioda de convergență
49
CAPITOLUL IV: Rezulta te
experimentale
IV.1 Baza de date USPS
IV.2 Rezultate experimentale
50
IV.1 Baza de date USPS
Am efectuat pe calculator experimente ampl e folosind baza de date Unite d State s Postal
Service (USPS) . Acesta cuprinde 7291 de imagini de formare și 2007 d e imagini de test.
Fiecare imagine este formată din 16 x 16 pixeli cu valori de gri cuprinse între 0 și 255.
Exemple de imagini din această bază d e date sunt prezentate în Fig. 4 .1.
Figura 4 .1: Exemple de imagini din baza de date USPS
În vederea deter minării performanțelor de clasificare folosind distanța de tip tangentă,
au fost folosite relațiile de calcul a vectorilor tangenți descriși în capitolul anterior, în
versiunea bazată pe utilizarea operatorului Sobel, respectiv prin metoda PCA. Câteva exem ple
de vectori t angenți sunt prezentați în Fig.4 .2. Pentru evaluarea distanței de tip tangentă se
folosesc în primul caz 7 vectori corespunzători transformărilor elementare precizate, iar în
cazul PCA se poate folosi un număr variabil de vectori, care de obicei nu depășește valoarea
15.
51
Figura 4.2: Exemple de vectori tangenți pentru da te din baza de date USPS .
Prima coloană prezintă imaginile originale, urmate de tangente pentru translație pe
orizontală, translație pe ve rticală, deformări diagonal e, de formarea axelor, scalare, rotație și
grosimea liniei .
Vectorii de tip tangentă au fost calculați folosind Matlab, pornind de la o implementare
C care se află la dispoziția publicului.
IV.2 Rezultate experimentale
Experimentele au folosit următoarele setări (distanța de tip tangentă pe o singură parte a
fost utilizată pe durata tuturor încercărilor):
(a) imagini originale + distanțe euclidiene/ TD;
(b) centroizii + distanțe euclidiene/ TD;
(c) centroizii PCA -comprimați + distanțe euclidien e / TD;
(d) memorie asociativă +centroizii PCA -comprimați + distanțe euclidiene/TD.
Am raportat rezultatele pentru 8, 12, respectiv 16 centroizi selectați întotdeauna folosind
algoritmul “k means clustering algorithm”, cu peste 20 de studii independente (luând în
considerare faptul că dacă am avea mai mulți centroizi asta ar putea duce la grup ări având
prea puține puncte). Dimensiunea subspațiului de proiecție variază între 20 și 50, captându -se
mai mult de 90% din energia imaginilor originale. Ratele d e eroare de clasificare sunt
prezentate în tabelul 4.1.
52
Tabel 4.1 Rate de eroare de clasificare pentru baza da date USPS(%)
Rezultatele experimentale disponibile indică faptul că memoria autoasociativă ,de
obicei, se comportă mai bine decât abordările cu cel mai apropiat vecin . În toate configurările
experimentale atunci când folosim ra ndamentul distanță de tip tangentă observăm
performanțe superioare decât atunci când folosim metoda euclidiană. Cât timp nu se
depășește performanța abordării cu cel mai apropiat vecin , memoria autoasociativă poate
oferi în continuare eticheta de clasă corectă în cazuri precum cele prezentate în Fig. 4.2, unde
abordării cu cel mai apropiat vecin eșuează. Cu toate acestea, reciproca este deasemeni Date originale+
distanța L2 Date originale+
distanța TD Centroizi+L2 Centroizi+TD
Numărul centroizilor Numărul centroizilor
8 12 16 8 12 16
5.63 3.54 8.97 8.57 7.92 6.5 6.7 5.8
Numărul de
centroizi Dimensiunea subspațiului
de proiecție
20 30 40 50
L2 + Centroizi PCA
comprimați
8 10.2 10.1 9.1 9.2
12 9.6 8.1 8.2 8.5
16 9.3 8.3 8 7.6
TD + Centroizi PCA
comprimați
8 8.4 7.7 5.4 5.7
12 8.2 6.9 6.5 6.4
16 8.2 6.9 5.4 5.7
Memorie asociativă + L2 +
Centroizi PCA
comprimați
8 10.1 9.2 8.9 9.3
12 9.6 8.5 8.4 8.5
16 9.4 8.5 7.9 7.4
Memorie asociativă + L2 +
Centroizi PCA
comprimați
8 8.2 7.5 7 6.8
12 8.1 7 6.3 6
16 7.2 6.6 5.5 5.7
53
valabilă, și anume decizia celui mai apropiat vecin poate fi în continuare cea corectă, așa cum
este indicat în Fig. 4.3 (rezultate clasificare prezentate în fig. 4.2 și 4.3 au fost obținute în
același experiment).
Fig.4.2 Memoria asociativă poate produce corect eticheta de clasă, atunci când cel mai
apropiat vecin nu reușește
În figura 4.2 pe primul rân d sunt reprezentate imaginile de testare, pe al doilea rând sunt
centroizii care indică eticheta de clasă corespunzătoare dată regula de cel mai apropiat vecin
+ TD, iar pe al treilea rând este reprezentată eticheta clasei dată de memorie asociativă + TD.
Fig. 4.3 Cel mai apropiat vecin poate produce corect eticheta de clasă, atunci când memoria
asociativă nu reușește
54
În figura 4.3 pe primul rând sunt reprezentate imaginile de testare, pe al doilea rând sunt
centroizii care indică eticheta de c lasă corespunzătoare dată regula de cel mai apropiat vecin
+ TD, iar pe al treilea rând este reprezentată eticheta clasei dată de memorie asociativă + TD.
Dependența performanțelor cu privire la dimensiunea subspatiului PCA nu este
întotdeauna clară, cu t oate că dimensiunile mai mari par a fi favorizate. Destul de
interesant este că unele din rezultatele PCA de bază aduc îmbunătăți față de versiunile non –
comprimate pentru ambele metode și anume distanța euclidiană respectiv distanța de tip
tangentă (TD).
Baza de date USPS a fost folosită extensiv pentru a compara performanțele diferitelor
abordări de recunoaștere a unui model. În teza de doctorat “ Modeling of image variability for
recognition, D. Keysers”, se enumeră peste de 40 de soluții distincte, cu rată de recunoaștere
care variază de la 16% până la valori mai mici dec ât 2%. Cele mai bune rezultate indicate în
tabelul 4.1 plaseză design -ul nostru cu memorie asociativă invariantă în intervalul mediu de
performanță, cu toate că multe dintre metodele s uperioare folosesc ,in mod semnificativ mai
multe date de formare sau chiar le cresc numărul folosind cu probe virtuale.
55
Concluzii
Prelucrarea documentelor se realizează cel mai des cu rețele neurale artificiale datorită
abilităților ac estora de a rezolva probleme dificile prin învățarea datelor. În plus, rețelele
neuronale se adaptează cu ușurință la medii noi de învățare și pot trata cu informații afectate
de zgomot, fragmentate sau probabilistice.
De obicei se folosesc operații de pre procesare și extragere a trăsăturilor pentru
selectarea celor mai semnificative informații ale datelor de intrare. Aceste procese au rolul de
filtrare și concentrare a energiei cu scopul reducerii volumului mare de informații.
Folosind această distanță de tip tangentă s -a observat că transformări rezonabil de mici
ale unor anumite obiecte imagine nu afectează membrii claselor. Metricile usuale, simple, ca
de exemplu distanța Euclidiană nu au această proprietate, ele fiind foarte sensibile la
transformări ca translație, rotație, modificări ale scalei, deformarea axelor .
Atunci când se iau în considerare aspectele legate de implementare, este de remarcat
faptul că elementele cheie ale arhitecturii (calculul distantei celulelor și funcțiile Gausiene) au
fost d eja implementate în structurile VLSI . Oricum, prezența altor neliniarități, altele decât
funcțiile spaț iale selective g m(.) ar trebui evitate, deoarece acestea ar putea introduce puncte
de echilibru suplimentare care se pot degrada performan țele soluț iei.
Sistemul propus este unul hardwired, prin urmare, nu este nevoie de nicio fază de
formare față de alte sisteme ce vor lua în considerare, de asemenea procedurile de învățare
pentru a regla adaptiv poziția și forma bazinelor de atracție în jurul valo rii de echilibru
memorat, în scopul de de a face față la posibile grupă ri, non-staționare sau varierea continuă
a distribuției memoriei.
În concluzie, m emoriile asociative recurente pot reprezenta o alternativă atractivă la
clasificatorul clasic folosind cel mai apropiat vecin , în special în cazurile în care avem baze
de date mari care stochează modele prototip de mari dimensiuni, deoarece se evită calcul
explicit a distanțelor dintre modelele de testare precum și cele prototip (si etapa ulterioară de
comandă ).
56
Referin țe bibliografice :
[1] Ciocoiu, I., Rețele neurale artificiale , Editura Cantes, Iași, 2001
[2]Simone Marinai, Marco Gori, Fellow, IEEE, and Giovanni Soda, Member, IEEE
Computer Society, Artificial Neural Networks for Docume nt Analysis and Recognition, IEEE
TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL.
27, NO. 1, JANUARY 2005
[3] T. Hastie, P. Simard, “Metrics and Models for Handwritten Character Recognition”,
Statistical Science , 13(1):54 –65, 1998
[4] P. Simard, Y. Le Cun, J. Denker, B. Victor, “Transformation Invariance in Pattern
Recognition – Tangent Distance and Tangent Propagation”, G. Orr and K. -R. Muller (editors),
Neural networks: tricks of the trade , volume 1524 of Lecture Notes in C omputer Science ,
Springer, Heidelberg, pp. 239 –274, 1998
[5] J.Wood, “Invariant Pattern Recognition: A Review”, Pattern Recognition , 29(1):1 –
17, 1996
[6] Iulian B. Ciocoiu ,Invariant pattern recognition using analog recurrent associative
mem ories , Neurocomputing, journal homepage: www.elsevier.com/locate/neucom
[7] Tangent Distance implementation (C code, RWTH Aachen, Germany): http://www –
i6.informatik.rwth -aachen.de/~keysers/td/
[8] http://en.wikipedia.org/wiki/OCR
57
Anexă
function
[hit_rate,missed_test_digit,V_all_digit,wrong_class,I_all_digit]=test_TDlyap_usps_original();
global C_train_transfor m C_test_transform ssigma params
data_path= 'C:\Users \Cipri \Desktop \marmureanu licenta \licenta \data';
cd(data_path)
load data_train.asc %incărcare date de antrenare
load data_test.asc %incarcare date de test
% calcul distanț ă Eucli diană, imagini originale (0.9437)
size_img=[16 16];
C_train=0.5*(1+data_train(:,2:257))';
avg_img=mean(C_train')';
C_test=0.5*(1+data_test(:,2:257))';
%==================================
% calcul distanăță tangentă, imagini originale (0.9646)
params.normalize=0;
params.TDtype= '1S';
params.pre_comp_tang2=1;
params.height = size_img(1);
params.width = size_img(2);
params.choice=[1 1 1 1 1 1 1 0 0];
params.regpar=0;
params.TangType= 'standard' ;
params.TangComp= 'standard' ;
params.Vpca=1;
params.load_tan g=0;
%Aplicare distanță IMED
% load usps_16centroids.asc
% C_train=usps_16centroids;
% clear usps_16centroids
%params.numCentroids=size(C_train,2)/10;
C_test=0.5*(1+data_test(:,2:257))';
%==================================
% calcul distanță tangen tă + centroizi + preprocesare PCA
load usps_centroids_12centres_pca30.asc
C_train=usps_centroids_12centres_pca30;
clear usps_centroids_12centres_pca30
params.numCentroids=size(C_train,2)/10;
58
load Vpca_30.asc
Vpca=Vpca_30;
clear Vpca_30
params.Vpca=Vpca;
%load eigvals.asc
numTang=7;
%========================
% calcul vectori de trăsături
%========================
%PCA
C_train_pca=C_train;
C_test_pca=Vpca'*(C_test -repmat(avg_img,1,size(C_test,2)));
usps_centroids8=Vpca*C_train+repmat(avg_img,1,size(C_tr ain,2));
%==================================
% calcul Lyapunov + L2/TD
params.tf=150; %500;
params.psig=0.01;
params.W=ones(10*params.numCentroids,1);
params.choice=[1 1 1 1 1 1 1 0 0];
%params.choice=[0 0 0 0 0 0 0];
params.TangComp= 'standard' ; % 'dif1'
params.regpar=0; %inf (L2) % 0 (TD)
params.TangType= 'standard+PCA' ; % 'PCA'; 'standard'; 'standard+PCA'
params.avgImg=avg_img;
%params.eigvals=eigvals(1:size(Vpca,2),1);
params.opt=odeset( 'RelTol' ,1e-2,'AbsTol' ,1e-2,'NormControl' ,'on');
params.lo ad_tang=0;
%==========
% buclă principală
%==========
% Set sigma parameters
%C_train_pca=process('norm_global',C_train_pca',[0 1])';
%C_test_pca=process('norm_global',C_test_pca',[0 1])';
[N,M]=size(C_train);
ssigma=[];
invTangMat=[];
if params.regpa r == 0
if strcmp(params.TangType, 'standard' )
[Dsq,alpha,tang_all] = TDsq_matrix(C_train,C_train,params);
59
C_3=10^6*eye(M)+sqrt(Dsq);
params.Tang=tang_all;
elseif strcmp(params.TangType, 'standard+PCA' )
%[Dsq1,alpha,tan g_all] = TDsq_matrix(C_train,C_train,params);
[Dsq1,alpha,tang_all] = TDsq_matrix(usps_centroids8,usps_centroids8,params);
tang_all_pca=params.Vpca'*tang_all;
for i=1:size(C_train_pca,2)
tang=tang_all_pca(:,1+(i -1)*numTa ng:i*numTang);
t1=inv(tang' * tang)*tang';
invTangMat=[invTangMat;t1];
for j=1:size(C_train_pca,2)
orgdiff=C_train_pca(:,j) -C_train_pca(:,i);
alpha = t1* orgdiff;
diff = ta ng * alpha -orgdiff;
dsq = diff' * diff;
Dsq(i,j) = max(0,dsq);
end
end
Dsq=Dsq';
params.Tang=tang_all_pca;
params.invTangMat=invTangMat;
C_3=10^6*eye(M)+sqrt(Dsq);
C_train=C_train_pca;
C_test=C_test_pca;
elseif strcmp(params.TangType, 'PCA' )
load usps_tangPCA_8.asc
%params.Tang=process('norm',usps_tangPCA_8',[0 1])';
params.Tang=usps_tangPCA_8;
clear usps_tangPCA_8
C_3=10^6*eye(M)+dist(C_train',C_train);
end
params.load_tang=1;
elseif params.regpar == inf
if strcmp(params.TangType, 'standard' )
C_3=10^6*eye(M)+dist(C_train',C_train);
elseif strcmp(params.TangType, 'standard+PCA' )
C_train= C_train_pca;
C_test=C_test_pca;
C_3=10^6*eye(M)+dist(C_train',C_train);
%C_3=10^6*eye(M)+dist_mahalan(C_train,C_train,params.eigvals);
end
end
for m=1:params.numCentroids
ssigma1(m)=min(C_3(m,params.numCentroids+1:M));
end
for m=params.numCentroids+1:M -params.numCentroids
idx_digit=ceil(m/params.numCentroids) -1;
ssigma1(m)=min(C_3(m,[[1:idx_digit*params.numCentroids]
[1+(idx_digit+1)*params.numCentroids:M]]));
60
end
for m=M -params.numCentroids+1:M
ssigma1(m)=min(C _3(m,1:M -params.numCentroids));
end
for m=1:M
idx_digit=ceil(m/params.numCentroids) -1;
ssigma2(m)=min(C_3(m,1+idx_digit*params.numCentroids:(idx_digit+1)*params.numCentr
oids));
end
%ssigma=min(min(C_3))*ones(M,1);
ssigma=min(ssigma1)*ones(M,1 );
%ssigma=ssigma1';
%C_test=0.5*(1+digit2_test)';
%C_test=C_test(:,101:200);
%C_test=C_train+0.2;
[Mtest,Ntest]=size(C_test);
C_train_transform=C_train;
C_test_transform=C_test;
[hit_rate,idx_min_digit,C_digit,missed_test_digit,V_all_digit,I_all_dig it]=lyap_TD( 'USPS' );
%calcul hit_rate
hit_rate=0;
wrong_class=[];
alias_class=[];
for p=1:size(C_test,2)
label_digit=data_test(p,1);
if I_all_digit(p) >= 1+label_digit*params.numCentroids & I_all_digit(p) <=
(label_digit+1)*params.numCentroids
hit_rate=hit_rate+1;
else
if rem(I_all_digit(p),params.numCentroids) ~= 0
wrong_class=[wrong_class;label_digit floor(I_all_digit(p)/params.numCentroids)
I_all_digit(p) p];
%alias_class=[alias_class floor(I_all_digi t(p)/params.numCentroids)];
else
wrong_class=[wrong_class;label_digit I_all_digit(p)/params.numCentroids -1
I_all_digit(p) p];
end
end
end
hit_rate=hit_rate/Ntest;
save hitrate_lyap.asc hit_rate –ascii %salvare date
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Recunoașterea caracterelor scrise de mână folosin d [629624] (ID: 629624)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.