recunoastere optica de caractere

5/8/2018 Recunoastere Optica de Caractere - slidepdf.com

http://slidepdf.com/reader/full/recunoastere-optica-de-caractere 1/52

Introducere

Proiectul de diplomă cu titlul „Recunoaştere optică de caractere” reprezintă un

program realizat în Visual C++.NET care interpretează o imagine luată cu un aparat de

fotografiat digital sau un telefon care are autofocus şi transformă litere din imagine în text

care poate fi editat. Condiţiile pe care trebuie să le îndeplinească imaginea sunt:

• Poza să fie făcută cu un aparat digital sau cu telefonul mobil

• Focalizare foarte bună (de preferat aparat cu autofocus)

• Literele să fie de culoare mult mai închisă decât background-ul

• Rezoluţia imaginii: aproximativ 3 Megapixeli pentru o pagină A5

• Poza să fie făcută la lumină naturală (dacă este făcută la lumină artificială se poate ca

recunoaşterea să nu fie foarte bună decât pentru aparatele de fotografiat profesionale).

Contribuţiile mele la acest proiect sunt următoarele:

• Crearea algoritmului, a programului şi a documentaţiei

Programul şi algoritmul fiind originale, folosesc metode de recunoaştere a textului

total diferite de programele existente pentru Recunoaştere Optică de Caractere. Dintre toate

programele OCR (Optical Character Recognition), singurul pe care l-am găsit pentru

recunoaşterea imaginilor luate cu un aparat de fotografiat a fost ABBY FineReader. Toate

celelalte programe pentru OCR găsite sunt numai pentru imagini luate cu scanerul. Ajuns la

versiunea 9.0, ABBY FineReader oferă o recunoaştere foarte bună a textului, dar are unele

limitări:

• în unele condiţii face confuzii între litere (când literele sunt foarte

asemănătoare sau sunt puţin confuze)

• nu respectă capetele de început şi sfârşit ale rândurilor din imaginea originală

• nu respectă încadrarea în pagină (dacă în imaginea originală este o singură

pagină, programul o intrpretează ca fiin 2, 3 sau 4 pagini

• nu recunoaşte formule matematice (deşi este la versiunea 9)

Aceste limitări se datorează folosirii inteligenţei artificiale (atribiue probabilităţi

pentru litere) şi folosirii funcţiilor oferite de Microsoft pentru deschiderea programului

Word şi introducerea textului în el (nu crează un fişier Word octet cu octet).

1



Fundamente teoretice

Variabila este o locaţie de memorie în care se încarcă o valoare de un anumit tip(număr întreg, caracter, valoare adevărată sau falsă).

Funţia este o secvenţă de program care se execută de câte ori este apelată.

Clasa este o structură care conţine funcţii şi variabile. În Visual C++, dacă funcţiile şi

variabilele sunt membre ale unei clase, ele pot fi folosite şi în alte clase. O clasă trebuie să

aibă cel puţin o funcţie constructor şi o singură funcţie destructor. Funcţia constructor se

apelează automat la instanţierea clasei (crearea unui obiect de o anumită clasă) şi are rolul de

a da valori iniţiale pentru variabilele acelei clase. În momentul în care se crează un obiect de oanumită clasă, se încarcă în memorie toate funcţiile şi variabilele acelei clase. La apelarea

destructorului, toate funcţiile şi variabilele unei clase se şterg din memorie.

Obiectul este folosirea efectivă a unei clase. Atunci când se crează o clasă, în aceasta

se introduc funcţii şi variabile, dar nu sunt folosite în programul principal dacă nu se crează

un obiect de clasa respectivă. Nu pot folosi funcţiile dintr-o clasă în programul principal dacă

nu creez un obiect de tipul clasei din care vreau să apelez funcţiile.

Pentru proiectul Licenta 2009 am folosit următoarele clase oferite de Microsoft:• CImage – oferă funcţii pentru prelucrarea imaginilor (crearea de imagini în

memorie, setarea pixelilor în imagine, scoaterea pixelilor din imagine)

• CString – operarea cu şiruri de caractere (concatenare, lungimea unui şir,

obţinerea unui caracter dintr-un şir)

• CFile – prelucrarea de fişiere (citirea octeţilor dintr-un fşier, scrierea de octeţi

într-un fişier, salvarea fişierului)

Funcţiile din clasa Cimage pe care le-am folosit în proiectul Licenta 2009:Create (Width, Height, nr_biţi_pe_pixel, flag) – crează o nouă imagine [2]

GetHeight() – oferă înălţimea imaginii [3]

GetWidth() – oferă lăţimea imaginii [4]

GetPixel(x, y) – oferă un pixel de coordonate x, y sub formă de număr întreg [5]

Load(string) – încarcă o imagine [6]

Save(string) – salvează o imagine [7]

SetPixel(x, y, culoare) – setează culoarea într-un pixel de coordonate x, y [8]

2



Crearea proiectului în limbajul de programare Visual C++ .NET

1. Modul design [1]

Creearea proiectului începe în modul design. În acest mod se aşează controalele grafice

(butoane, controale Picture Control, controale Progress Control). Deoarece o aplicaţie de tip

Windows Forms aşteaptă un eveniment (click cu mouse-ul, apăsarea unei taste, trecerea cu

mouse-ul pe suprafaţa unui control grafic), trebuie creeat un eveniment pentru unul sau mai

multe controale grafice.

Pentru proiectul Licenta 2009 în care am realizat recunoaşterea optică de caractere, amaşezat următoarele controale grafice în fereatra de dialog: butonul Deschide fişier, butonul

Începe recunoaşterea, controlul Picture Control şi controlul Progress Control (Fig. 1). Con-

troalele grafice se iau prin Drag and Drop din fereastra Toolbox.

Fig. 1 Proiectul Licenta 2009 în modul design

3



2. Codul sursă [1]

Când se execută dublu click pe butonul Deschide fisier, mediul de programare creează o

funcţie membră a clasei Clicenta2009Dlg.cpp numită OnBnClickedButton1(), deschide

automat fişierul Clicenta2009Dlg.cpp şi poziţionează cursorul la această funcţie. Pentru butonul Începe recunoaşterea se procedează similar, dar funcţia de răspuns la evanimentul de

click se va numi OnBnClickedButton2().

Pentru a avea acces la un control grafic trebuie creată o variabilă pentru acel control.

Pentru a creea o variabilă asociată controlului Progress Control se execută click-dreapta pe

acesta şi va apare următoarea fereastră de dialog:

Fig. 2 Crearea unei variabile asociate controlului Progress Control

În textbox-ul Variable name se scrie numele variabilei şi se apasă butonul Finish. După ce

am adăugat variabila asociată controlului grafic Progress Control, am acces din codul sursă la

funcţiile acestui control. Astfel, când scriu într-o funcţie membră a clasei CLicenta 2009Dlg

numele variabilei şi operatorul punct (.), apar funcţiile şi variabilele pentru acest control:

Fig. 3 Funcţiile asociate controlului Progress Control

4



Pentru controlul Picture Control trebuie schimbat din fereastra Proprietes ID-ul din

IDC_STATIC în alt nume pentru că nu se poate adăuga o variabilă la un control cu acest ID.

Eu l-am numit IDC_PICTURE. Variabila asociată controlului Picture Control am numit-o

picture_box.

Butonului Deschde fişier i-am asocia numele b_1 şi butonului Începe recunoasterea i-

am asociat numele b_2. Pentru ambele butoane am creat un eveniment de click care execută o

bucată de cod.

În proiectul Licenta 2009 am două clase principale: CLicenta2009Dlg şi Litere şi încă

două care se crează automat pentru proiect: CAboutDlg şi Clicenta2009App.

În clasa CLicenta2009Dlg am următoarele funcţii create de mine: cadrane(void),

cauta_pixel(void), Copiaza_Libie(void), creaza_fisier(void), desparte(void), functie_h(void),

functie_v(void), functie_zoom(void), linie_1(void), linie_2(void), numara(void),

PentruButonul2(void), Seteaza_Pixel(void), Sterge_Linie(void) şi alte funcţii generate

automat de limbajul de programare la crearea proiectului.

În clasa litere am funcţia getLitera(void); Funcţia getLitera este de tip char şi nu are

nici un parametru.

5



Algoritmul care desparte literele de background

şi funcţiile care implementează acest algoritm

Cel mai dificil lucru în proiectarea unui program de recunoaştere optică de caractere

este creearea unui algoritm care să decidă dacă un pixel de coordonate x şi y aparţine unei

litere sau aparţine background-ului. Într-o imagine, doi pixeli identici pot să aparţină unul

literei şi unul background-ului (Fig. 4).

Pixelul de coordonate 0, 0 şi pixelul de coordonate 477, 256 sunt identici (R = 115, G

= 109, B = 119). Primul aparţine background-ului şi al doilea aparţine unei litere (litera v).RGB = 115, 109, 119 x = 0 y = 0 RGB = 115, 109, 119 x = 477 y = 256

Fig. 4 Doi pixeli identici, unul aparţinând literei şi unul background-uluiDeoarece iniţial programul a fost realizat în Visual C# s-a folosit o funcţie din acest

limbaj de programare care oferă intensitatea luminoasă dintr-un pixel sub formă de număr

zecimal între 0 şi 1. Această funcţie se numeşte GetPixel(x, y).GetBrightness(). Pentru pixelul

de coordonate 0, 0 din figura 4, intensitatea luminoasă este 0.4470588. În tabelul următor sunt

readaţi pixeli în nuanţe de gri în care intensitatea luminoasă a pixelului actual diferă de

intensitatea luminoasă a pixelului următor cu 0.1:

IntensitateaLuminoasă

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

ComponenteleRGB

Fig. 5 Intensitatea luminoasă dintr-un pixel

În limbajul Visual C++ nu există o funcţie care să returneze intensitatea luminoasă,

informaţia despre un pixel de coordonate x, y fiind doar un număr întreg pozitiv care

corespunde conversiei în baza 10 a celor 24 de biţi pe care îi are un pixel. Orice pixel dintr-o

6

pixel

2R =

25G =

25G=

4



imagine JPG sau BMP este un şir de 24 de biţi (8 biţi pentru Red, 8 biţi pentru Green şi 8 biţi

pentru Blue). Dacă se va citi binar un fişier bitmap se va observa că la octeţii alocaţi unui

pixel de coordonate x, y ordinea este inversă: primul octet este Blue, al doilea Green şi al

treilea Red. Deci structura culorii unui pixel pe 24 de biţi este în realitate Blue, Green, Red.

Exemplu:

În Paint setez culorile: R = 80 În Realitate ele sunt: 100, 90, 80

G = 90

B = 100

Din acest motiv, când se face conversia din binar în zecimal trebuie ţinut cont de

această ordine a culorilor. Dacă doresc să obţin culoarea unui pixel în Visual C++, trebuie să

creez un obiect de clasă Cimage şi să apelez funcţia GetPixel(x, y), în care x şi y sunt

coordonatele pixelului. Această funcţie returnează un număr întreg între 0 şi 16777215.

Pentru separarea background-ului de literă am folosit echivalentul unei funcţii

GetPixel.GetBrightness() din Visual C#. Astfel, dacă ştiu că în Visual C++ culorile sunt de la

negru (0) la alb (16777215) în ordinea creşterii luminii, tot ce se află într-un anumit interval

are intensitate a luminii foarte apropiată.

Exemplu: culorile de la 61440 la 65 535 cu un decalaj de 15 de culori:

00000000 11100001 00000000 = 57 600 (B = 0, G = 225, R = 0)

00000000 11111111 11111111 = 65 535 (B = 0, G = 255, R = 255)

Fig. 6 Culorile de la 57 600 la 65 635

Pentru a decide dacă un pixel aparţine de o literă sau de background se procedează astfel:

1. Se împarte imaginea în fragmente de 50 x 50 pixeli. Pentru imaginea din Fig. 7

care are o rezoluţie de 2044 x 1336 pixeli se obţine un total de 1040 de fragmente a câte 50

pixeli (40 de fragmente pe orizontală şi 26 pe verticală) plus 40 de fragmente pe orizontală cu

rezoluţia 50 x 36 pixeli şi 26 de fragmente pe verticală cu rezoluţia 44 x 50 pixeli.

7



Fig. 7 Împărţirea imaginii originale în fragmente de 50 x 50 pixeli

2. Pentru fiecare fragment se analizează care interval de culori predomină pentru a

stabili culorea de background pentru acel fragment. Intervalele de culori sunt următoarele:

• între 6710886 şi 8355710, echivalentul pentru intensitatea luminoasă 0.4 – 0.5• între 8355710 şi 10066329, echivalentul pentru intensitatea luminoasă 0.5 – 0.6

• între 10066329 şi 11711155, echivalentul pentru intensitatea luminoasă 0.6 – 0.7

• mai mare ca 11711155, adică mai mare ca intensitatea luminoasă 0.7

Fiecărui interval i-am asociat o variabilă: pentru echivalentul intensităţii luminoase

0.4 – 0.5, adică pentru intervalul de pixeli 6710886 – 8355710 am asociat variabila numara_4.

Aceasta este o variabilă de tip întreg care iniţial are valoarea 0. Când este îndeplinită condiţia

ca pixelul de coordonate x, y să fie în acest interval variabila numara_4 se incrementează(creşte cu 1). După ce s-a parcurs tot fragmentul de 50 x 50 pixeli, una dintre variabilele

asociate fiecărui interval va fi cea mai mare sau în cel mai rău caz, unele variabile vor fi egale

între ele.

Prima dată se verifică dacă pixelul de coordonate x, y este în intervalul 8355710 –

10066329 (adică în intervalul 0.5 – 0.6 ca şi intensitate luminoasă). Probabilitatea cea mai

mare este să fie în acest interval. Dacă 8355710 <= pixel(x, y) < 10066329, variabile

numara_5 creşte cu 1 şi căutarea se opreşte pentru că sigur nu se află în celelalte intervale.Dacă nu este îndeplinită condiţia de mai sus, se continuă căutarea în intervalul

8



10066329 – 11711155 (echivaletul întensităţii luminoase 0.6 – 0.7) deoarece probabilitatea

cea mai mare este să fie în acest interval. Dacă se îndeplineşte condiţia 10066329 <= pixel(x,

y) < 11711155, se incrementează variabila numara_6 şi căutarea se opreşte pentru că în

intervalele următoare sigur nu mai este.

Dacă pixelul de coordonate x, y nu se află nici în acest interval, căutarea se continuă

cu intervalul de pixeli mai mari ca 11711155 (adică pixelii care au intensitatea luminoasă mai

mare ca 0.7). Dacă este îndeplinită condiţia pixel(x, y) > 11711155, variabila numara_7 îşi

creşte valoarea cu 1 şi căutarea se opreşte.

Dacă nu este îndeplinită nici condiţia de mai sus, se verifică şi ultima condiţie: pixelul

să fie între 6710886 şi 8355710. Această condiţie este cel mai puţin probabil să apară şi este

echivalentul intervalului 0.4 – 0.5 a intensităţii luminoase, deci culori foarte întunecate. Dacă

6710886 <= pixel(x, y) < 8355710, variabila numara_4 creşte cu o unitate.

Dacă să întâmplă ca pixelul de coordonate x, y să nu fie în nici unul din intervalele de

mai sus, atunci are intensitatea luminoasă mai mică de 0.4 (deci este sub 6710886) şi este prea

întunecat ca să fie culoare de background.

Exemplu:

Pentru fragmentul de 50 x 50 pixeli din Fig. 8 se simulează funcţionarea codulului de

program care desparte background-ul de literă.

Fig. 8 Fragment de 50 x 50 pixeli pentru care se caută intervalul predominant

void CLicenta2009Dlg::numara(void){

for (y = y_1; y < y_2; y++)for (x = x_1; x < x_2; x++){

predomina();}

desparte();kx++;

}

Functia numara() parcurge fragmentul pixel cu pixel şi pentru fiecare pixel se

apelează funcţia predomina() care verifică condiţiile pentru intervalele explicate mai sus.

După ce s-au parcurs toţi ce 50 x 50 pixeli, se apelează funcţia desparte() care va decide, în

funcţie de intervalul care a predominat, dacă pixelul de coordonate x, y aparţine literei sau

aparţine background-ului.

9



Exemplu: simularea funcţiei numara() pentru fragmentul x_1 = 0, x_2 = 49, y_1 = 0, y_2 =

49:

Pasul 1: x = 0, y = 0 Apelez funcţia predomina()

void CLicenta2009Dlg::predomina(void)

{if (Imagine.GetPixel(x, y) < 10066329)

if (Imagine.GetPixel(x, y) >= 8355710){

numara_5++;return;

}

Dacă pixelul de coordonate 0, 0 este mai mare sau egal cu 8355710 şi este mai mic

decât 10066329 (ceea ce înseamnă că are intensitatea luminoasă cuprinsă între 0.5 şi 0.6),

căutarea se opreşte pentru pixelul de coordonate 0, 0 prin comanda return. Dacă nu s-a

îndeplinit condiţia, programul continuă:if (Imagine.GetPixel(x, y) < 11711155)


numara_6++;return;

}

Verific următorul interval (0.6 – 0.7 în intensitate luminoasă sau 10066329 -

11711155 în pixeli). Dacă este îndeplinită condiţia, funcţia predomina() se opreşte aici. Dacă

nu, continuă:


numara_7++;return;

}

Funcţionarea este identică: dacă se îndeplineşte condiţia, funcţia se opreşte aici. Dacă

nu, continuă cu ultima verificare:

if (Imagine.GetPixel(x, y) < 8355710)if (Imagine.GetPixel(x, y) >= 6710886){

numara_4++;return;

}

De fiecare dată când condiţia a fost îndeplinită, variabila corespunzătoare intervalului

s-a incrementat: numara_4++ înseamnă că variabila numara_4 ia valoarea pe care a avut-o

plus 1.

După ce s-a terminat de executat funcţia predomina(), coordonatele se mută la

următorul pixel: x = 1, y = 0.

10



Pasul 2 …. Pasul 49: x = 1, y = 0 ….. x = 49, y = 0

Din nou se apelează funcţia predomină care stabileşte în ce interval se încadrează

pixelul de coordonate 1, 0. Apoi coordonatele se mută la 2, 0 şi se verifică intervalul, apoi la

3, 0 şi ciclul acesta continuă până când s-a parcurs toată linia pe orizontală (50 pixeli). După

ce s-a parcurs prima linie pe orizontală (s-a încheiat ciclul while pentru x), se trece la

următoarea linie pe orizontală (y devine 1 şi se intră din nou în ciclul while pentru x).

Funcţionarea este similaară cu cea descrisă mai sus în care y = 0 şi x variază de la punctul de

început al fragmentului până la punctul de sfârşit al fragmentului.

Pasul 50: x = 49, y = 0

De fiecare dată când s-a încheiat parcurgerea pe orizontală (s-a ieşit din ciclul while

pentru x), y creşte cu 1 (se trece la următoarea linie).

Pasul 2500: x = 49, y = 49

Când y = y_2 se iese din ciclul while pentru y pentru că anterior (când y a fost egal cu

y – 1) s-a parcurs şi ultima linie din fragment.

În acest moment s-a finalizat de parcurs tot fragmentul de 50 x 50 pixeli şi pentru

fiecare pixel s-a incrementat o variabilă (numara_4, numara_5, numara_6 sau numara_7)

asociată unui interval. Pentru fragmentul din Fig. 8: numara_4 = 167, numara_5 = 168,

numara_6 = 160, numara_7 = 1821. Sub intervalul 6710886 (adică sub intensitatea luminoasă

0.4) sunt ceilalţi 184 pixeli până la totalul de 2500.

Se apelează funcţia desparte() care, în funcţie de intervalul care a predominat pentru

un fragment, desparte litera de background, adică decide dacă un pixel de coordonate x, y

aparţine literei sau aparţine background-ului. Intervalul care a predominat este dat de cea mai

mare valoare pe care o are una din cele patru variabile asociate fiecărui interval. Pentru Fig. 8,

variabila cu cea mai mare valoare este numara_7. Aceasta înseamnă că a predominat

intervalul de pixeli peste 11711155 (sau intensitate luminoasă peste 0.7). Algoritmul este

astfel construit încât toţi pixelii care sunt sub intensitatea luminoasă mai mică cu 0.1 decât cea

care predomină să fie consideraţi literă, ceilalţi să fie consideraţi background. În exemplul din

Fig. 8 unde predomină intensitatea luminoasă 0.7 (pixeli peste 11711155), toţi pixelii care au

intensitatea luminoasă sub 0.6 (adică sunt sub 10066329) sunt setaţi pe literă, ceilalţi pe

background. Setarea pe literă se face prin colorarea pixelului de coordonate x, y a unei

imagini negre cu dimensiunile imaginii originale în alb.

În momentul în care încarc imaginea originală, creez trei imagini colorate în negru

care au dimensiunile imaginii originale. Aceste trei imagini se numesc Imagine_Alb_Negru,Imagine_Sterge şi Imagine_Seteaza_Pixel. Fiecare dintre ele vor fi folosite ulterior în scopuri

11



diferite. Pentru exemplul din Fig. 8, codul de program din funcţia desparte() care setează

pixelii de culoare albă pentru litere este următorul:

if (numara_7 >= numara_6)if (numara_7 >= numara_5)

if (numara_7 >= numara_4){

for (y = y_1; y < y_2; y++)for (x = x_1; x < x_2; x++){

if (Imagine.GetPixel(x, y) < 10066329){

Imagine_Alb_Negru.SetPixel(x, y, RGB(255,255,255));Imagine_Sterge.SetPixel(x, y, RGB(255,255,255));

}}return;

}

Funcţionarea acestui cod de program este foarte asemănătoare cu cea din funcţianumara(): se parcurge fragmentul de 50 x 50 pixeli de la coordonata x_1 până la coordonata

x_2 pe orizontală şi de la y_1 la y_2 pe verticală şi pentru fiecare pixel se verifică dacă este

mai mic de 10066329 (0.6 în intensitate luminoasă). Dacă pixelul de coordonate x, y este mai

mic decât 10066329 în Imagine_Alb_Negru şi în Imagine_Sterge (care sunt complet negre) se

setează la coordonatele x, y culoarea alb. Din fragmentul colorat din Fig. 8 obţin două

fragmente alb-negru (Fig. 9).

Imagine_Alb_Negru

Imagine_Sterge

Fig. 9 Un fragment de 50 x 50 pixeli înainte şi după despărţirea background-ului de litere

Funcţia completă care decide dacă pixelul de coordonate x, y aparţine sau nu de o literă

este următoarea (decizia se ia în funcţie de intervalul care predomină şi este pentru un

fragment de 50 x 50 pixeli sau pentru fragmentele ce rămân la capete) :

void CLicenta2009Dlg::desparte(void){ if (numara_5 >= numara_7)

if (numara_5 >= numara_6) if (numara_5 >= numara_4)

{for (y = y_1; y < y_2; y++)

for (x = x_1; x < x_2; x++)

{ if (Imagine.GetPixel(x, y) < 6710886){

12




}}

return;}

if (numara_6 >= numara_7)if (numara_6 >= numara_5) if (numara_6 >= numara_4)

{for (y = y_1; y < y_2; y++)

for (x = x_1; x < x_2; x++){



}

} return;}


{for (y = y_1; y < y_2; y++)

for (x = x_1; x < x_2; x++){


Imagine_Alb_Negru.SetPixel(x, y, RGB(255,255,255));Imagine_Sterge.SetPixel(x, y, RGB(255,255,255));}

} return;

}


{for (y = y_1; y < y_2; y++)

for (x = x_1; x < x_2; x++)

{ if (Imagine.GetPixel(x, y) < 5000269){


}}

return;}

}

Funcţia de mai sus primeşte valorile x_1, x_2, y_1 şi y_2 de la alte două funcţii: una

pentru parcurgerea fragmentelor pe orizontală (functie_h) şi una pentru parcurgerea

fragmentelor pe verticală (functie_v).

13



Funcţia care parcurge fragmentele pe orizontală:

void CLicenta2009Dlg::functie_h(void){

while (kx <= h_p){

x_1 = x_1 + 50;x_2 = x_2 + 50;

numara();numara_7 = 0;numara_6 = 0;numara_5 = 0;numara_4 = 0;progress_bar.SetRange(0, interval);progress_bar.SetStep(1);progress_bar.SetPos(pozitia);progress_bar.StepIt();pozitia = pozitia + 1;

}

kxx++;x_1 = x_1 + 50;x_2 = Imagine.GetWidth() - 2;numara();numara_7 = 0;numara_6 = 0;numara_5 = 0;numara_4 = 0;

}

Variabila kx reprezintă poziţia pe orizontală a fragmentului la care s-a ajuns. Această

variabilă se incrementează în funcţia numara() descrisă anterior. Variabila h_p reprezintănumărul de fragmente de 50 x 50 pixeli pe orizontală fără fragmentul de la capăt, care în

exemplul din Fig. 7 are dimensiunea 44 x 50 pixeli. Iniţial variabila x_1 are valoarea -48 şi

variabila x_2 are valoarea 2. Atât timp cât rămân în ciclul while pentru parcurgerea

fragmentelor spre dreapta, variabilele x_1 şi x_2 cresc cu 50. Pentru primul fragment x_1 =

-48 + 50 = 2 şi x_2 = 2 + 50 = 52.

Motivul pentru care se lasă doi pixeli de culoarea backgroundului pe marginea din stânga

a imaginii este acela că voi avea nevoie ulterior de un punct de referinţă de culoarea background-ului faţă de care să scad 1 pixel. Întotdeauna pixelul de referinţă este unit cu un

pixel de culoare albă. Uneori acest punct fi de coordonată x = 1. Dacă aş fi lăsat o margine de

doar un pixel, referinţa ar fi ajuns 0 (primul pixel din stânga imaginii) la care aş fi scăzut 1 şi

aş fi ajuns la coordonata x = -1, moment în care aş fi ieşit din imagine şi programul ar fi dat

eroare. Marginea de doi pixeli se lasă şi în dreapta imaginii deoarece uneori, faţă de punctul

de referinţă va trebui să adun 1 pixel. Dacă punctul de referinţă este exact pe marginea din

dreapta şi adaug 1 pixel ies din imagine şi programul dă eroare.

14



Funcţia care parcurge fragmentele pe verticală:

void CLicenta2009Dlg::functie_v(void){

while (kxx <= v_p){

kx = 1;x_1 = -48; x_2 = 2;y_1 = y_1 + 50;y_2 = y_2 + 50;functie_h();

}kx = 1;x_1 = -48; x_2 = 2;y_1 = y_1 + 50;y_2 = Imagine.GetHeight() - 2;functie_h();

//resetez valorile dacă doresc să încarc încă o imaginenumara_7 = 0;

numara_6 = 0;numara_5 = 0;numara_4 = 0;x_1 = -48, x_2 = 2, y_1 = -48, y_2 = 2, kx = 1, kxx = 1;progress_bar_1 = 0, pozitia = 0, interval;progress_bar.SetPos(0); //golesc controlul grafic Progress Control

}

Variabila kxx reprezintă linia pe care se află fragmentul actual sau poziţia pe verticală.

Variabila v_p reprezintă numărul total de fragmente pe verticală fără fragmentul din capăt,

care în exemplul din Fig. 7 are dimensiunea de 50 x 36 pixeli. Se reiniţializează valorile

pentru kx, x_1 şi x_2 deoarece de fiecare dată după ce am parcurs funcţia functie_h() acestevalori s-au modificat. Se pregătesc coordonatele pe verticală: y_1 = y_1 + 50 şi y_2 = y_2 +

50. Iniţial y_1 = -48 şi y_2 = 2. Se lasă margini de 2 pixeli pentru marginea de sus şi pentru

cea de jos din acelaşi motiv ca şi la functie_h(): va trebui să scad în sus sau să adun în jos un

pixel şi să nu iasă din imagine. Se apelează funcţia functie_h() care parcurge fragmentele pe

orizontală. Se resetează variabilele kx, x_1 şi x_2, se trece la următoarea linie de fragmente

(kxx = 2, y_1 = 52, y_2 = 102) şi se intră din nou în parcurgerea pe orizontală. După ce kxx =

v_p, se parcurge şi ultima linie, care pentru Fig. 7 este formată din 40 de fragmente dedimensiunea 50 x 36 pixeli.

După ce am terminat de parcurs toate fragmentele din imagine trebuie să resetez

valorile kx, x_1, x_2, kxx, y_1 şi y_2 pentru o nouă imagine.

15



Fig. 10 Despărţirea background-ului de litere la momentul kxx = 6 şi kx = 17

După ce s-au parcurs toate cele 1040 de fragmente a câte 50 pixeli plus cele 40 de

fragmente pe orizontală cu rezoluţia 50 x 36 pixeli şi cele 30 de fragmente pe verticală cu

rezoluţia 44 x 50 pixeli (Fig. 8), se vor obţine două imagini identice (Imagine_Alb_Negru şiImagine_Sterge) în care vor exista doar două culori: alb pentru literă şi negru pentru

background (Fig. 11).

16

)functie_h(functiacu parcurgeredesensul



Fig. 11 Imaginea originală din Fig.8 după despărţirea background-ului de litere

17



Căutarea unui pixel de culoarea literei

După ce am obţinut imaginile Imagine_Alb_Negru şi Imagine_Sterge în care ştiu că

pixelii de culoare alb sunt litere şi cei de culoare negru sunt background, programul trebuie să

extragă fiecare zonă în care pixelii de culoare albă sunt uniţi şi să analizeze dacă acea zonă

este o literă.

Se parcurge fiecare linie orizontală de la stânga la dreapta până se găseşte un pixel de

culoare abă. Funcţia care face acest lucru se numeşte cauta_pixel() şi conţine două cicluriwhile: unul pentru parcurgerea unei linii orizontale şi unul pentru înaintarea pe verticală în

jos. În momentul în care s-a terminat de parcurs o linie orizontală şi nu s-a găsit nici un pixel

alb, se iese din primul ciclu while şi se intră în al doilea unde se mută coordonata y mai jos cu

un pixel. După ce s-a mutat coordonata y, x devine 0 şi se intră din nou în ciclul while pentru

parcurgerea liniei orizontale. Această alternanţă de intrare în ciclul while pentru x,

parcurgerea liniei, ieşirea din acest ciclu, intrarea în ciclul while pentru y, incrementarea

variabilei y şi intrarea din nou în ciclul while pentru x, se repetă până când se găseşte un pixel

alb sau până când y este egal cu înălţimea imaginii.

Funcţia caută pixel():

void CLicenta2009Dlg::cauta_pixel(void){x = 2; y = 2; //resetez valorile pt ca au mai fost folosite la

trecerea in alb-negrurand_actual = "";while (trecere_litera_y == true){

while (trecere_litera_x == true) //gaseste pixel alb, face

conturul, copiaza litera, o recunoaste si se deplaseazaspre dreapta pana ajunge la capatul randului{

if (Imagine_Alb_Negru.GetPixel(x, y) == 16777215){//se execută funcţii pentru recunoaşterea unei litereposibile care începe cu pixelul găsit

}x++;

}

Secvenţa de cod de mai sus face următoarele: porneşte căutarea unui pixel alb, de lacoordonatele x = 2 şi y = 2 şi parcurge fiecare pixel dintr-o linie orizontală până când se

găseşte un pixel alb sau până când s-a ajuns la capătul liniei. Parcurgerea unei linii orizontalese face cu un ciclul while, unde condiţia de ieşire din ciclu este ca variabila trecere_litera_x să

18



fie false (aceasta se întâmplă când s-a ajuns la capătul liniei). Deci atât timp câttrecere_litera_x este true se continuă căutarea pe orizontală. Când s-a găsit un pixel alb seapelează funcţii pentru copierea şi recunoaşterea unei litere posibile care începe cu pixelulgăsit. Indiferent dacă s-au găsit sau nu pixeli de culoarea literei, când s-a ajuns la capătul uneilinii orizontale se iese din ciclul while pentru acea linie şi se intră în ciclul while pentru

înaintarea pe verticală în jos.if (x == Imagine.GetWidth() - 1){

x = 1;capat_rand = true;trecere_litera_x = false;

}//secvenţă de cod pentru revenirea în punctul în care s-a găsitpixel de culoarea literei deoarece se poate ca rândul să fieînclinat şi primul pixel găsit să fie la jumătatea rânduluisau în interiorul rândului (să nu fie la începutul rândului)

if (y == Imagine.GetHeight() - 1){

trecere_litera_y = false;}trecere_litera_x = true;y++;}

}

Când s-a intrat în ciclul while pentru înaintarea în jos, coordonata y creşte cu 1 pixel.

Atât timp cât nu s-a ajuns la ultima linie din imagine (cea mai de jos) se intră din nou în ciclul

while pentru coordonata x (parcurgerea pe orizontală).

Fig. 12 Găsirea unui pixel de culoarea literei

Copierea unei litere într-o nouă imagine

19

La poziţia 644, 2 s-a găsit primul pixel de culoarea literei



După ce am găsit un pixel care are culoarea literei, trebuie să separ litera de restul

imaginii. Pentru aceasta trebuie parcurs conturul exterior al literei şi trebuie coipat într-o nouă

imagine tot ce se află în interiorul conturului. În momentul în care se parcurge conturul

exterior al literei, o funcţie va marca începutul fiecărei linii orizontale (capătul din stânga al

unei linii care începe cu culoarea literei). Apoi se parcurge din nou conturul literei şi când se

ajunge la sfârşitul unei linii orizontale (capătul din dreapta al unei linii care se termină cu

culoarea literei) se copiază linia formată din cele două puncte: capătul de sfârşit şi capătul de

început care l-am marcat la trecerea anterioară.

Algoritmul care face conturul unei litere

Orice literă este formată din pixeli de culoare albă (Fig. 13).

Fig. 13 Pixeli de culoare albă ce formează o literă

Pentru ca să parcurg conturul exterior al punctelor de culoare albă ce reprezontă litera,

aleg 4 perechi pe pixeli, fiecare pereche fiind formată dintr-un pixel alb şi unul negru aşezaţi

orizontal sau vertical. Obţin astfel următoarele perechi:

• ambii pixeli orizontali, primul negru, următorul alb

• ambii pixeli orizontali, primul alb, următorul negru

• ambii pixeli verticali, cel de jos alb, cel de sus negru

• ambii pixeli verticali, cel de jos negru,cel de sus alb

Aceste perechi sunt redate în Fig. 14:

20



Fig. 14. Cele 4 perechi de pixeli cu care parcurg conturul exterior al literei

Aceste perechi de pixeli le-am numit astfel: orizontal alb negru, orizontal negru alb,

vertical negru alb, vertical alb negru. Fiecărei perechi i-am atribuit în codul sursă o variabilă

de tip boolean:

• h_n_a pentru orizontal negru alb

• h_a_n pentru orizontal alb negru

• v_n_a pentru vertical negru alb

•

v_a_n pentru vertical alb negruPentru o mai bună înţelegere a modului în care am gândit algoritmul, am făcut o analogie

de denumiri cu algoritmul care implementează un automat (ex: automatul care serveşte cafea).

În construirea unui autiomat care seveşte cafea intervin noţiunile de stări. Iniţial mă aflu într-o

anumită stare şi trec dintr-o stare în alta. Exemplu:iniţial mă aflu în starea 1; din stare 1 trec în

starea 2, din starea 2 în starea 3, din starea 3 în starea 1 şi după o succesiune de treceri dintr-o

stare în alta, obţin rezultatul final. Din proiectarea unui automat eu am împrumutat noţiunea

de „stare”: starea h_a_n (orizontal alb negru), starea h_n_a (orizontal negru alb), starea v_a_n

(vertical alb negru) şi starea v_n_a (vertical negru alb). Cele 4 variabile, fiind de tip boolean

pot lua doar două valori: true şi false. Când mă aflu în starea orizontal negru alb, setez

variabila h_n_a pe valoarea true. Când am trecut în altă stare (ex: vertical alb negru) setez

variabila h_n_a pe valoarea false (nu mai sunt în starea orizontal alb negru) şi variabila v_a_n

pe true (sunt în starea vertical alb negru). Trecerea dintr-o stare în alta este ilustrată în Fig. 15.

21



a) b)

c) d)

Fig. 15 Trecerea dintr-o stare în alta pentru parcurgerea conturului exterior al unei litere

Întotdeauna pixelul de referinţă din fiecare pereche de stări va fi cel de culoare neagră.

În Fig. 15 a) este ilustrată trecerea din starea h_n_a în: starea v_n_a dacă în dreapta pixelului

de referinţă se află un pixel alb, starea v_a_n dacă sub pixelul de referinţă şi pe diagonală se

află pixeli de culoare neagră şi rămânerea în starea h_n_a dacă sub pixelul de referinţă se află

un pixel de culoare neagră şi în diagonala din dreapta jos se află un pixel de culoare albă.

Săgeata orientată în jos indică faptul că rămân în starea h_n_a dar mă deplasez un pixel în jos.În Fig. 15 b) trec din starea h_a_n în starea v_n_a deasupra punctului de referinţă şi pe

diagonală se află câte un pixel negru, trec în starea v_a_n dacă deasupra punctului de referinţă

se află un pixel alb şi rămân în starea h_a_n dacă deasupra punctului de referinţă se află un

pixel negru şi pe diagonala din stânga sus se află un pixel alb. Săgeata orientată în sus indică

faptul că rămân în starea h_a_n dar mă deplasez în sus cu un pixel.

În Fig. 15 c) trec din starea v_n_a în starea h_n_a dacă în stânga pixelului de referinţă

şi pe diagonală se află câte un pixel negru, trec în starea h_a_n dacă în stânga pixelului de

referinţă se află un pixel alb şi rămân în starea v_n_a dacă în stânga pixelului de referinţă se

22



află un pixel negru şi pe diagonala din stânga jos se află un pixel alb. Săgeata orientată înspre

stânga indică faptul că rămân în starea v_n_a dar mă deplasez înspre stânga cu un pixel.

În Fig. 15 d) trec din starea v_a_n în starea h_a_n dacă în dreapta pixelului de

referinţă şi pe diagonală se află câte un pixel negru, trec în starea h_n_a dacă în dreapta

pixelului de referinţă se află un pixel alb şi rămân în starea v_a_n dacă în dreapta pixelului de

referinţă se află un pixel negru şi pe diagonala din dreapta sus se află un pixel alb. Săgeata

orientată spre dreapta indică faptul că rămân în starea v_a_n dar mă deplasez spre dreapta cu

un pixel.

Exemplu de parcurgere al conturului unui fragment din litera din Fig. 13 (în roz sunt pixelii ce

i-am parcurs, în albastru pixelul la care am ajuns; aceste culori nu apar în program):

a) sunt în starea h_n_a b) din starea h_n_a trec în starea v_n_a (referinţa nu se mută)

c) rămân tot în v_n_a dar mut spre stânga d) din v_n_a trec în h_n_a (referinţa se mută)

e) din h_n_a trec în v_n_a (referinţa nu se mută) f) din v_n_a trec în h_n_a (referinţa se mută)

g) din h_n_a trec în v_n_a (referinţa nu se mută) h) din v_n_a trec în _h_n_a (referinţa se mută)

23

9 8 7 6 5 4 3 2 1 0

0

12

9 8 7 6 5 4 3 2 1 0012

9 8 7 6 5 4 3 2 1 0012

9 8 7 6 5 4 3 2 1 0012

9 8 7 6 5 4 3 2 1 0012

9 8 7 6 5 4 3 2 1 0012

3

3

9 8 7 6 5 4 3 2 1 00

12

9 8 7 6 5 4 3 2 1 001234



i) rămân în starea h_n_a dar mut referinţa 1 pixel în jos j) rămân în h_n_a dar mut referinţa în jos

k) din h_n_a trec în v_a_n (referinţa se mută) l) rămân în v_a_n dar mut referinţa 1 pixel spre dreapta

m) rămân în starea v_a_n dar mut spre dreapta n) rămân în v_a_n şi mut referinţa

o) din v_a_n trec în h_a_n (referinţa se mută) p) rămân în h_a_n dar mut referinţa 1 pixel în sus

q) rămân în h_a_n dar mut referinţa 1 pixel în sus r) din h_a_n trec în v_a_n (referinţa nu se mută)

s) rămân în v_a_n dar mut referinţa 1 pixel spre dreapta ş) din v_a_n trec în h_a_n (referinţa se mută)

24

9 8 7 6 5 4 3 2 1 0012345

9 8 7 6 5 4 3 2 1 00123456

9 8 7 6 5 4 3 2 1 001234567

9 8 7 6 5 4 3 2 1 001234567

9 8 7 6 5 4 3 2 1 001234567

9 8 7 6 5 4 3 2 1 001234567

9 8 7 6 5 4 3 2 1 00

1234567

10 9 8 7 6 5 4 3 2 112345678

10 9 8 7 6 5 4 3 2 11234

5678

10 9 8 7 6 5 4 3 2 11234

5678

10 9 8 7 6 5 4 3 2 112345678

10 9 8 7 6 5 4 3 2 112345678



t) din h_a_n trec în v_a_n (referinţa nu se mută) ţ) rămân în v_a_n dar mut referinţa spre dreapta

u) rămân în starea v_a_n şi mut referinţa

1 pixel spre dreapta

v) Conturul parcurs din litera din Fig. 13

Fig. 16 Parcurgerea conturului exterior al unui fragment din litera din Fig. 13

Conform algoritmului de căutare a unui pixel de culoarea literei, după ce s-a parcursimaginea linie cu linie pe orizontală, s-a găsit primul pixel alb la coordonatele 8, 2 (Fig. 16 a).

Dacă la coordonatele 8, 2 este un pixel alb, înseamnă că în stânga cestui pixel alb se află sigur

un pixel de culoarea backgroundului (pixel negru). Perechea formată din primul pixel alb

găsit la coordonatele 8, 2 şi pixelul negru din stânga lui formează starea orizontal negru alb.

Din această stare trebuie să trec în starea vertical negru alb (v_n_a), în starea vertical alb

negru (v_a_n) sau să rămân în starea orizontal negru alb (h_n_a) dar să mă deplasez un pixel

în jos (Fig. 15 a).În Fig. 16 a, pentru prima pereche h_n_a găsită, pixelul de referinţă este la

coordonatele 7, 2 (pixelul negru din perechea h_n_a). Prima dată programul încearcă să

rămână în starea h_n_a şi să mute referinţa în jos. Condiţia este ca sub pixelul de referinţă să

fie un pixel negru şi pe diagonala din dreapta jos să fie un pixel alb. Această condiţie nu este

îndeplinită deoarece sub pixelul de referinţă se află un pixel alb (la coordonatele 7, 3).

Secvenţa de cod care încearcă rămânerea în starea h_n_a este următoarea (se verifică şi dacă

s-a ajuns la punctul de unde a început conturul pentru ca să nu se învârtă la infinit în jurulliterei):

25

10 9 8 7 6 5 4 3 2 112345678

1110 9 8 7 6 5 4 3 2 112345678

121110 9 8 7 6 5 4 3 2 112345678

1110 9 8 7 6 5 4 3 2 1 001234567



if (h_n_a == true) if (Imagine_Alb_Negru.GetPixel(xx, yy + 1) == 0) if (Imagine_Alb_Negru.GetPixel(xx + 1, yy + 1) == 16777215)

{yy = yy + 1;

if (t_x == xx) if (t_y == yy){

trecere = false;}

}

Deoarece nu s-a reuşit rămânerea în starea h_n_a, se încearcă trecerea în starea v_a_n.

Codul care încearcă trecerea în starea v_a_n este următorul:

if (h_n_a == true)if (Imagine_Alb_Negru.GetPixel(xx, yy + 1) == 0)

if (Imagine_Alb_Negru.GetPixel(xx + 1, yy + 1) == 0)

{xx = xx + 1; yy = yy + 1;v_a_n = true;h_n_a = false;

}

Condiţiile nu sunt îndeplinite (7, 3 şi 8, 3 nu sunt pixeli negri). A mai rămas o singură

variantă: trecerea în starea v_n_a. Secvenţa de cod care face această trecere este următoarea:

if (h_n_a == true) if (Imagine_Alb_Negru.GetPixel(xx, yy + 1) == 16777215)

{v_n_a = true;h_n_a = false;

}

Din starea v_n_a se încearcă rămânerea în această stare: condiţia este ca în stânga

punctului de referinţă să existe un pixel negru şi pe diagonala din stânga jos să existe un pixel

alb. În exemplul din Fig. 16 c) condiţia este îndeplinită: pixelul de coordonate 6, 2 este negru

şi cel de coordonate 6, 3 este alb. Codul care încearcă rămânerea în starea v_n_a este

următorul (referinţa se mută cu 1 pixel spre stânga):

if (v_n_a == true) if (Imagine_Alb_Negru.GetPixel(xx - 1, yy) == 0)

if (Imagine_Alb_Negru.GetPixel(xx - 1, yy + 1) == 16777215){

xx = xx - 1;}

Din starea v_n_a se încearcă rămânerea în această stare. Condiţia nu este îndeplinită(pixelul 5, 3 nu este un pixel alb) şi se încearcă trecerea în starea h_n_a. Secvenţa de cod careîncearcă această trecere este următoarea:if (v_n_a == true) if (Imagine_Alb_Negru.GetPixel(xx - 1, yy) == 0) if (Imagine_Alb_Negru.GetPixel(xx - 1, yy + 1) == 0)

{xx = xx - 1; yy = yy + 1;

h_n_a = true;v_n_a = false;

26



if (t_x == xx) if (t_y == yy)

{trecere = false;

}}

În Fig. 16 d) este îndeplinită condiţia de trecere din starea v_n_a în starea h_n_a: pixelul de coordonate 5, 2 este negru şi cel de coordonate 5, 3 este tot negru. Când a trecut înstarea h_n_a, referinţa s-a mutat de la 6, 2 la 5, 3. Tot în această secvenţă de cod se verificădacă s-a ajuns la punctul în care s-a început conturul. De fiecare dată când ajung în stareah_n_a fac această verificare.

Din starea h_n_a se încearcă rămânerea în această stare (codul care face aceasta a fost prezentat mai sus). Condiţia de rămânere în starea h_n_a nu este îndeplinită (pixelul decoordonate 5, 4 nu este negru). Programul încearcă să treacă în starea v_n_a. Condiţia esteîndeplinită (sub pixelul de referinţă există 1 pixel alb: pixelul 5, 4). Codul care face trecerea afost prezentat şi explicat la un exemplu anterior. Coordonatele nu se schimbă, dar nu mă maiaflu în starea h_n_a, ci în starea v_n_a (Fig. 16 e).

Din nou se încearcă rămânerea în starea v_n_a. Nu se reuşeşte şi se încearcă trecereaîn starea h_n_a. Condiţiile sunt îndeplinite (pixel negru la 4,3 şi la 4, 4 – Fig. 16 f). Până laFig. 16 i) toţi paşii sunt similari cu cei descrişi anterior. În Fig. 16 i) se încearcă rămânerea înstarea h_n_a. Se reuşeşte rămânerea în starea h_n_a atât în Fig. 16 i) cât şi în Fig. 16 j). Seîncearcă rămânerea în starea h_n_a, dar condiţiile nu sunt îndeplinite. Se încearcă trecerea dinh_n_a în v_a_n. În Fig. 16 k) este ilustrată această trecere. Referinţa se mută de la 3, 7 la 4, 8.Din starea v_a_n încerc să rămân tot în această stare. Secvenţa de cod care face acest lucrueste următoarea:if (v_a_n == true) if (Imagine_Alb_Negru.GetPixel(xx + 1, yy - 1) == 16777215) if (Imagine_Alb_Negru.GetPixel(xx + 1, yy) == 0)

{ xx = xx + 1;}

Condiţiile sunt îndeplinite (5, 7 este pixel alb şi 5, 8 este pixel negru). Rămân în stareav_a_n şi mut referinţa la 5, 8 (Fig. 16 l). Până la Fig. 16 o) rămân tot în starea v_a_n şideplasez referinţa spre dreapta. În Fig. 16 o) se încearcă rămânerea în starea v_a_n dar condiţiile nu sunt îndeplinite (pixelul 8, 7 este negru). Se încearcă trecerea în starea h_a_n:condiţiile sunt îndeplinite (pixelii 8, 7 şi 8, 8 sunt negri). Codul care face trecerea din v_a_n înh_a_n este următorul:if (v_a_n == true) if (Imagine_Alb_Negru.GetPixel(xx + 1, yy - 1) == 0) if (Imagine_Alb_Negru.GetPixel(xx + 1, yy) == 0)

{xx = xx + 1; yy = yy - 1;h_a_n = true;v_a_n = false;

if (t_x == xx)

if (t_y == yy){

trecere = false;}

}

În această parte de cod se verifică şi dacă nu am ajuns la punctul în care a început

căutarea (uneori căutarea se face de la dreapta la stânga şi se începe cu starea h_a_n).

27



În continuare programul încearcă să rămână în starea h_a_n. Condiţiile sunt

îndeplinite deoarece deasupra punctului de referinţă există un pixel negru şi pe diagonala din

stânga sus există un pixel alb. Referinţa se mută 1 pixel mai sus: de la 8, 7 la 8, 6 (Fig. 16 p).

Codul care încearcă rămânerea în starea h_a_n este următorul:

if (h_a_n == true) if (Imagine_Alb_Negru.GetPixel(xx - 1, yy - 1) == 0) if (Imagine_Alb_Negru.GetPixel(xx, yy - 1) == 0)

{xx = xx - 1; yy = yy - 1;v_n_a = true;h_a_n = false;

}

În următorul pas (Fig. 16 q) se întâmplă acelaşi lucru: rămân în starea v_a_n şi mut

referinţa de la 8, 6 la 8, 5. Faţă de referinţa 8, 5 se încearcă condiţiile pentru rămânerea în

starea h_a_n: 7, 4 să fie alb şi 8, 4 să fie negru. Condiţia nu este îndeplinită deoarece pixelul8, 4 este alb. Se încearcă trecerea din starea h_a_n în starea v_n_a: 7, 4 să fie negru şi 8, 4 să

fie negru. Secvenţa de cod care încearcă această trecere este următoarea:

if (h_a_n == true) if (Imagine_Alb_Negru.GetPixel(xx - 1, yy - 1) == 0) if (Imagine_Alb_Negru.GetPixel(xx, yy - 1) == 0)

{xx = xx - 1; yy = yy - 1;v_n_a = true;h_a_n = false;

}

Condiţia nu este îndeplinită deoarece 7, 4 şi 8, 4 sunt pixeli de culoare albă. Seîncearcă şi ultima variantă: din h_a_n în v_a_n. Secvenţa de cod care încearcă această trecere

este următorea:

if (h_a_n == true) if (Imagine_Alb_Negru.GetPixel(xx, yy - 1) == 16777215)

{v_a_n = true;h_a_n = false;

}

Când se face trecerea din starea h_a_n în starea v_a_n coordonatele nu se schimbă

(Fig. 16 r). Din starea v_a_n prima încercare este de a rămâne în această stare. Condiţiile sunt

îndeplinite (pixelul 9, 4 este alb şi pixelul 9, 5 este negru). Coordonatele punctului de referinţă

se mută spre dreapta cu 1 pixel (de la 8, 5 la 9, 5 - Fig. 16 s). Din starea v_a_n având referinţa

9, 5 încerc să rămân în această stare. Nu se îndeplinesc condiţiile (pixelul 10, 4 este negru) şi

încerc trecerea în starea h_a_n. Condiţiile sunt îndeplinite pentru trecerea în starea h_a_n şi

referinţa se mută la 10, 4 (Fig. 16 ş). Din starea h_a_n încerc să rămân în această stare, dar să

mut referinţa 1 pixel în sus. Deoarece pixelul de coordonate 10, 4 este alb, nu pot să rămân în

această stare. Încerc trecerea în starea v_n_a. Nu se poate face această trecere deoarece la

28



coordonatele 9, 3 şi 10, 3 nu se află pixeli negri. Ultima variantă posibilă este trecerea în

starea v_a_n. Atât în Fig. 16 ţ) cât şi în Fig. 16 u) rămân în starea v_a_n dar mut coordonatele

punctului de referinţă spre stânga.

În Fig. 16 am descris o parte din secvenţele rulează la parcurgerea conturului exterior

al unei litere. Unele treceri dintr-o stare în alta încă nu au fost aplicate. Acestea sunt:

• trecerea din starea v_n_a în starea h_a_n

Fig. 17 Trecerea din starea v_n_a în starea h_a_n (referinţa nu se mută)

Codul care face această trecere este următorul (verifică şi dacă referinţa este punctul de la

care a început parcurgerea conturului ca să nu se învârtă la infinit în jurul literei):


{h_a_n = true;v_n_a = false;

if (t_x == xx)

if (t_y == yy){

trecere = false;}

}

• trecerea din starea v_a_n în starea h_n_a

Fig. 18 Trecerea din starea v_a_n în starea h_n_a (referinţa nu se mută)

Secvenţa de cod care face această trecere este următoarea (se verifică şi dacă referinţa este

aceeaşi cu punctul unde s-a început conturul):if (v_a_n == true)

if (Imagine_Alb_Negru.GetPixel(xx + 1, yy) == 16777215){

h_n_a = true;v_a_n = false;


{trecere = false;

}

}

29



Algoritmul este astfel creat încât să existe următoarea ordine de treceri dintr-o stare în

alta:

• pentru h_a_n: se încearcă rămânerea în această stare; dacă nu se reuşeşte, se încearcă

trecerea în starea v_n_a; dacă nici aici nu s-a reuşit trecerea, a mai rămas o singurăvariantă posibilă: trecerea în starea v_a_n care sigur se va îndeplini.

• Pentru v_a_n: încerc să rămân în această stare; dacă nu reuşesc, încerc să trec în

starea h_a_n; dacă nu a reuşit trecerea în h_a_n, condiţiile se vor îndeplini pentru

trecerea în starea h_n_a.

• pentru h_n_a: se încearcă rămânerea în această stare; dacă nu se îndeplinesc

condiţiile se încearcă trecerea în starea v_a_n; dacă nici aici nu se îndeplinesc

condiţiile sigur se vor îndeplini pentru trecerea în starea v_n_a.

• pentru v_n_a: prima dată se încearcă rămânerea în această stare; dacă nu se

îndeplinesc condiţiile, se încearcă trecerea în starea h_n_a; dacă nu s-a intrat în starea

h_n_a, sigur se va intra în starea h_a_n.

Pentru litera din Fig. 16 v) se prezintă conturul la care s-a ajuns în două momente diferite:

a) conturul când referinţa a ajuns la 14, 22 b) conturul când referinţa a ajuns la 7, 0

Fig. 19 Conturul literei la două momente diferite

30

22

14

07



Algoritmul care setează pixelul de început al fiecărei linii

Pentru ca o literă să poată fi copiată trebuie să cunosc începutul şi sfârşitul fiecărei

linii ce o compune (deoarece o copiez linie cu linie). După ce s-a găsit un pixel de culoarea

literei se apelează o funcţie care parcurge conturul exterior al literei şi setează într-o imagine

separată pixelii de început ai fiecărei linii ce compun litera. Pixelii de început ai unei linii

reprezintă toate stările h_n_a (orizontal negru alb). Imaginea în care se setează aceşti pixeli

este o imagine care are dimensiunile egale cele ale imaginii Alb_Negru şi în care toţi pixelii

sunt de culoarea background-ului. Această imagine se numeşte Imagine_Seteaza_Pixel. Când

algoritmul ce parcurge conturul a ajuns în starea h_n_a, în imaginea Imagine_Seteaza_Pixel

se setează punctul la care s-a ajuns. Acest punct marchează începutul unei linii din literă.

Exemplu de setare a pixelului ce reprezintă începutul unei linii din literă (culoarea albastră

din Imagine_Alb_Negru nu apare în prgram):

Imagine_Alb_Negru Imagine_Seteaza_Pixel



31

9 8 7 6 5 4 3 2 1 0

012

9 8 7 6 5 4 3 2 1 0012

9 8 7 6 5 4 3 2 1 0012

9 8 7 6 5 4 3 2 1 001

2

9 8 7 6 5 4 3 2 1 00123

9 8 7 6 5 4 3 2 1 00123






Imagine_Alb_Negru Imagine_Setează_Pixel

Fig. 20 Setarea unui pixel ce reprezintă începutul de linie

Funcţia care setează pixelul de început al fiecărei linii se numeşte Seteaza_Pixel().

Această funcţie este alcătuită dintr-un ciclu while care parcurge conturul exterior al literei.

Condiţia de ieşire din ciclu este ca variabila booleană trecere să ia valoarea false. Această

variabilă ia valoarea false când am ajuns la punctul în care s-a început parcurgerea

conturului. Pentru contur se foloseşte algoritmul explicat mai sus. Codul de program care

setează pixelul de referinţă în imaginea Imagine_Seteaza_Pixel este următorul:

• din starea h_n_a rămân în această stare dar mut referinţa;

if (h_n_a == true) if (Imagine_Alb_Negru.GetPixel(xx, yy + 1) == 0) if (Imagine_Alb_Negru.GetPixel(xx + 1, yy + 1) == 16777215)

32

9 8 7 6 5 4 3 2 1 00123

9 8 7 6 5 4 3 2 1 00123

4 4

9 8 7 6 5 4 3 2 1 00123

9 8 7 6 5 4 3 2 1 00123

4 4

5 5

9 8 7 6 5 4 3 2 1 00123

9 8 7 6 5 4 3 2 1 00123

4 45 5

9 8 7 6 5 4 3 2 1 00123

9 8 7 6 5 4 3 2 1 00123

4 45 56 6



{yy = yy + 1;

Imagine_Seteaza_Pixel.SetPixel(xx, yy, RGB(255,255,255));

if (xx < x_stanga)

{ x_stanga = xx;}


{trecere = false;

}}

• din starea v_n_a ajung în starea h_n_a


if (Imagine_Alb_Negru.GetPixel(xx - 1, yy + 1) == 0){

xx = xx - 1; yy = yy + 1;h_n_a = true;v_n_a = false;


if (xx < x_stanga){

x_stanga = xx;}


{trecere = false;

}}

• din starea v_a_n ajung în starea h_n_a

if (v_a_n == true) if (Imagine_Alb_Negru.GetPixel(xx + 1, yy) == 16777215)

{

h_n_a = true;v_a_n = false;


if (xx < x_stanga){

x_stanga = xx;}


{

trecere = false;}}

33



Se observă că de fiecare dată când am ajuns în starea h_n_a se verifică dacă punctul la

care s-a ajuns este cel mai din stânga punct din literă. Pe măsură ce se parcurge conturul

literei se verifică şi celelalte extreme din literă (extrema din dreapta, de sus şi de jos).

Pixelul cel mai din dreapta se verifică atunci când intru în starea h_a_n:

if (xx > x_dreapta){

x_dreapta = xx;}

Pixelul cel mai de sus este verificat când sunt în starea v_n_a:

if (yy < y_sus){

y_sus = yy;}

Cel mai de jos punct din literă se verifică în starea v_a_n:

if (yy > y_jos){

y_jos = yy;}

După ce am terminat de parcurs conturul literei cu funcţia Seteaza_Pixel(), am obţinut

următoarele informaţii (Fig. 21 – litera implică şi conturul negru exterior care s-a parcurs):

• punctele de început pentru fiecare linie (pixelii de culoare albă din imaginea

Imagine_Seteaza_Pixel);

•

cel mai din stânga punct din literă (valoarea variabilei x_stanga);• cel mai din dreapta punct din literă (valoarea variabilei x_dreapta);

• cel mai de sus punct din literă (valoarea variabilei y_sus);

• cel mai de jos punct din literă (valoarea variabilei y_jos);

]a) Imagine_Alb_Negru (culoarea albastră nu apare în program) b)Imagine_Seteaza_Pixel

34

1110 9 8 7 6 5 4 3 2 1 0012345

67

1110 9 8 7 6 5 4 3 2 1 0012345

67

x_dreapta

23

x_stanga

y_jos

y_sus

21



Fig. 21 Găsirea punctelor de extrem şi setarea începutului de linie

Pentru Fig. 21 a) punctele de extrem sunt următoarele:

• x_dreapta = 21

•

x_stanga = 0• y_sus = 0

• y_jos = 23

Când s-a ieşit din funcţia Seteaza_Pixel() se calculează următoarele două valori:

• jumatate_v (jumătatea înălţimii unei litere)

jumatate_v = (y_jos - y_sus) / 2 + y_sus;

•

jumatate_h (jumătatea lăţimii unei litere)jumatate_h = (x_dreapta - x_stanga) / 2 + x_stanga;

Algoritmul care copiază fiecare linie ce compune o literă

După ce am setat începutul fiecărei linii, trebuie să fac din nou conturul literei şi de

fiecare dată când am ajuns în starea h_a_n să copiez toţi pixelii care se află între punctul de

referinţă la care am ajuns şi punctul care l-am setat în funcţia Seteaza_Pixel(). Pentru aceasta

se creează o nouă imagine numită Imagine_Litera care are dimensiunile literei. Codul care

crează imaginea Imagine_Litera este următorul:

Imagine_Litera.Create(x_dreapta - x_stanga+1, y_jos - y_sus+1, 24, 0);

Starea h_a_n reprezintă sfârşitul unei linii. Pentru copierea liniei se apelează funcţia

Copiaza_Linie. Aceasta parcurge conturul exterior al literei cu algoritmul folosit şi la funcţia

Seteaza_Pixel() şi de fiecare dată când ajunge în starea h_a_n intră într-un ciclu while care

copiază toţi pixelii de la stânga punctului în care s-a ajuns până la punctul de început al liniei

setat în imaginea Imagine_Seteaza_Pixel.

Exemplu de copiere a unei linii dintr-o literă (linia dintre 18, 3 şi 3, 3 – culorile albastru şi

roz nu apar în program ):


35

01

2345

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 001

2345

01

2

345

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 001

2

34

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0



Imagine_Litera x = 18, y = 3 Imagine_Litera x = 17, y = 3








36

01

2345

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 001

234

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

01

2345

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 001

234

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

01

2345

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

01

234

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

01

2345

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 001

234

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

01

2345

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 001

234

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

01

234

5

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 001

234

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

01

2345

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 001

234

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

01

2345

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 001

2

34

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0



Fig. 22 Copierea unei linii dintr-o literă din Imagine_Alb_Negru în Imagine_Litera

Codul de program care face copierea liniei y = 3 prezentată în Fig. 22 este următorul:

if (h_a_n == true) if (Imagine_Alb_Negru.GetPixel(xx, yy - 1) == 0)

if (Imagine_Alb_Negru.GetPixel(xx - 1, yy - 1) == 16777215){

yy = yy - 1;

l_x = xx;

if (Imagine_Seteaza_Pixel.GetPixel(l_x, yy) == 16777215) //sanu suprapuna 2 pixeli (pixelul de referninta cu linia copiata){

l_x = xx - 1;}while (capat_linie == false){

Imagine_Litera.SetPixel(l_x - x_stanga, yy - y_sus,Imagine_Alb_Negru.GetPixel(l_x, yy));

if (Imagine_Seteaza_Pixel.GetPixel(l_x, yy) == 16777215){

capat_linie = true;}l_x--;

}capat_linie = false;

if (yy == jumatate_v) //Nu pot sa calculez x_d si x_s laSeteaza_Pixel() pt ca nu am jumatate_v

if (xx > x_d){

x_d = xx;}

if (t_x == xx)if (t_y == yy){

trecere = false;}

}

Variabila l_x reprezintă coordonata pe orizontală pentru copierea liniei. Aceasta iniţial

primeşte valoarea coordonatei xx (punctul la care s-a ajuns când s-a intrat în starea h_a_n).

Variabila l_x se decrementează (scade cu o unitate) pe măsură ce se copiază linia. Când în

imaginea Imagine_Seteaza_Pixel s-a ajuns la pixelul alb înseamnă că am ajuns la începutul

liniei. Aici opresc copierea şi ies din ciclul while. Parcurgerea unei linii din imaginea

Imagine_Alb_Negru se face în paralel cu parcurgerea aceleaşi linii din imaginea

Imagine_Seteaza_Pixel. Diferenţa dintre cele două imagini este aceea că în imaginea

Imagine_Alb_Negru se află linia întreagă iar în imaginea Imagine_Seteaza_Pixel se află

numai începutul liniei. După cum se observă în exemplul prezentat în Fig. 22 o linie este

compusă din pixeli albi şi negri. Capetele liniei sunt întotdeauna pixeli negri.

37



Deoarece algoritmul prezentat în Fig. 22 se repetă pentru fiecare linie a literei, în

următorul exemplu se va prezenta o literă în diferite faze ale copierii.

Exemplu pentru diferite linii copiate în imaginea Imagine_Litera (culorile roz şi albastru

nu apar în program):

Imagine_Alb_Negru Imagine_Litera (s-a copiat linia y = 4)




Imagine_Litera după ce s-au copiat 9 linii Imagine_Litera după ce s-au copiat 18 linii

38

01

2345

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 001

2345

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

01

23

45

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 001

23

45

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

01

2345

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 001

2345

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 001

2345

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

0

1234567

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

01234567

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0



Imagine_Alb_Negru

Imagine_LiteraImagine_Litera după ce s-au copiat toate liniile Exemplu de extragere a unei litere

Fig. 23 Copierea unei litere din imaginea Imagine_Alb_Negru în imaginea Imgine_Litera

După ce am terminat de parcurs funcţia Copiaza_Linie() am următoarele informaţii: x_d,

x_s şi litera copiată în imaginea Imagine_Litera. Variabila x_d reprezintă cel mai din dreapta

punct din literă care este pe axa jumatate_v, variabila x_s reprezintă cel mai din stânga punct

din literă care este pe axa jumatate_v şi variabila jumătate_v reprezintă axa y care se află la

jumătatea înălţimii literei.

39

0

1234567

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

891011

23

x_sx_d

jumatate_v



Împărţirea literei în patru cadrane

Până în acest moment am separat litera de restul imaginii astfel încât ştiu că toţi pixelii de

culoare albă din imaginea Imagine_Litera aparţin unei singure litere. În imaginea Imagine_

Alb_Negru pixelii de culoare albă aparţineau de mai multe litere şi nu se ştia dacă doi pixeli

de culoare albă luaţi la întâmplare aparţin aceleaşi litere. Următorul pas este atribuirea unui

nume acelei litere: a, b, c, A, B, C, literă neidentificată, paranteză. Până acum cuvântul

„literă” a avut sensul de orice zonă în care pixelii de culoare albă sunt uniţi. Şi dacă se găseşte

un singur pixel izolat el este analizat cu etapele descrise până acum: setarea începutului de

linie şi copierea liniei.

Din acest moment, cuvântului „literă” i se va asocia un sens nou: literă identificată şi

transformată într-un caracter şi literă neidentificată şi ştearsă din imagine. Începând cu această

parte a programului se face trecerea de la o literă care nu poate fi editată (imagine, mulţime de

pixeli) la o literă pe care o pot edita (un

caracter de tip Unicode). Pentru aceasta

se începe analizarea pixelilor de culoare

albă din imaginea Imagine_Litera şi

încercarea de a găsi unele caracteristici

unice pe care le are o anumită formaţiune

de pixeli. Se începe prin a împărţi

formaţiunea de pixeli în patru cadrane

(Fig. 24).

Fig. 24 Împărţirea literei în patru cadrane

Pentru exemplul din Fig. 24 cadranele sunt următoarele:

• cadranul 1: 1...9 x 1...10

• cadranul 2: 10...20 x 1...10

• cadranul 3: 1...9 x 11...22

40

01234567

2120191817161514131211 10 9 8 7 6 5 4 3 2 1 0

891011

23

1

2

34



• cadranul 4: 10...20 x 11...22

În general, delimitarea cadranelor se face astfel:

• cadranul 1: x = x_stanga + 1 ...... y = jumatate_h

y = y_sus + 1 ...... y = jumatate_v – 1• cadranul 2: x = jumatate_h ...... x = x_dreapta - 1

y = y_sus + 1 ...... y = jumatate_v – 1

• cadranul 3: x = x_stanga + 1 ...... x = jumatate_h

y = jumatate_v ...... y = y_jos - 1

• cadranul 4: x = jumatate_h ...... x = x_dreapta - 1

y = jumatate_v ...... y = y_jos - 1

Pentru fiecare dintre cele 4 cadrane se calculează cât la sută reprezintă fiecare staredintre cele foloite la parcurgerea conturului: h_n_a, h_a_n, v_n_a şi v_a_n (de data aceasta se

ia în calcul şi interiorul literei, nu doar conturul exterior prezentat în Fig. 19).

Exemplu : (culoarea albastră nu apare în program):

• Pentru cadranul 1 (număr total de stări: 21):

Stările h_n_a 6 (28%) Stările h_a_n 4 (19%) Stările v_a_n 7 (33%) Stările v_n_a 4 (19%)


Stările h_n_a 8 (27%) Stările h_a_n 10 (34%) Stările v_a_n 5 (17 %) Stările v_n_a 6 (20 %)

• Pentru cadranul 3 (numar total de stări: 33):

41

1234

5678910

9 8 7 6 5 4 3 2 1

12345

678910

1920181716151413121110

1234

5678910

9 8 7 6 5 4 3 2 1

1234

5678910

9 8 7 6 5 4 3 2 1

12345678910

9 8 7 6 5 4 3 2 1

12345

678910

1920181716151413121110

12345

678910

1920181716151413121110

12345

6

7

8910

1920181716151413121110

11

9 8 7 6 5 4 3 2 1

11

22

9 8 7 6 5 4 3 2 111

22

9 8 7 6 5 4 3 2 1

11

22

9 8 7 6 5 4 3 2 1






Fig. 25 Cadranele ce apar în litera din Fig. 24 şi procentul de stări pentru fiecare cadran

Motivul pentru care numărul total de procente nu este 100 este acela că, atunci când se

calculează procentele se memorează ca număr întreg şi limbajul Visual C++ trunchiază un

număr real la cel mai mic întreg. Dacă în cadranul 4 sunt în total 41 de stări şi se calculează

cât la sută din ele reprezintă cele 9 stări v_a_n, rezultatul exprimat printr-un număr real este

9,2141

1009=

⋅

. Variabila care trebuie să memoreze acest număr este de tip real şi valoarea

21,9 este trunchiată la cel mai mic întreg adică 21. Astfel, procentul care reprezintă stareav_a_n din cadranul 4 este memorat ca 21 şi nu ca 21,9 (valoarea exactă) sau 22 (cel mai

apropiat întreg).

După ce s-au obţinut cele 16 variabile (4 stări pentru fiecare din cele 4 cadrane) se

compară fiecare din aceste variabile cu cele din baza de date. Baza de date reprezintă o clasă

separată în care am 16 intervale pentru fiecare literă, 1 interval pentru fiecare variabilă.

Aceste intervale sunt procente de stări calculate pentru mai multe litere cu acelaşi nume (mai

multe litere de a, mai multe litere de b, etc). Modul de creare al intervalelor este următorul:Se introduc într-o imagine mai multe litere cu acelaşi nume (Fig. 26).

Fig. 26 Litere pentru crearea intervalelor

42

22

192018171615141312111011

22

192018171615141312111011

22

192018171615141312111011

22

192018171615141312111011

22



Se verifică procentele pentru prima literă şi se găsesc următoarele valori:

cadran_1_h_a_n = 3

cadran_1_h_n_a = 19

cadran_1_v_a_n = 30

cadran_1_v_n_a = 46

cadran_2_h_a_n = 33

cadran_2_h_n_a = 20

cadran_2_v_a_n = 13

cadran_2_v_n_a = 33

cadran_3_h_a_n = 19

cadran_3_h_n_a = 31

cadran_3_v_a_n = 29

cadran_3_v_n_a = 19

cadran_4_h_a_n = 35

cadran_4_h_n_a = 21

cadran_4_v_a_n = 32

cadran_4_v_n_a = 10

Se verifică procentele pentru a doua literă şi se compară valorile cu cele anterioare.

Dacă valorile găsite acum sun diferite de cele găsite anterior, se procedează în felul următor:

capătul din stânga al intervalului pentru starea h_a_n va fi cea mai mică valoare din cele două

şi capătul din dreapta va fi cea mai mare valoare din cvele două. La fel se procedează şi cu

celelalte stări. Se verifică procentele şi pentru următoarea literă. Din nou se compară valorile

găsite cu intervalul creat anterior. Dacă o valoare găsită acum este mai mică dect capătul din

stânga al intervalului, capătul din stânga devine acea valoare. Dacă valoarea găsită este mai

mare dect capătul din dreapta , capătul din dreapta devine acea valoare. Diferenţa dintre

capătul din stâng al intervalului şi cel din dreatpa nu trebuie să fie mai mare de 30. Dacă

diferenţa dintre capătul din stânga şi cel din dreapta este mai mare de 30, valoarea găsită nu

va deveni un nou capăt stânga sau dreapta. Pentru Fig. 26 s-au obţinut următoarele intervale

cu diferenţa maximă dintre capete 30:

Capătul din stânga Stare Capătul din dreapta0 cadran_1_h_a_n 11

19 cadran_1_h_n_a 3421 cadran_1_v_a_n) 40

31 cadran_1_v_n_a 4827 cadran_2_h_a_n 41

43



13 cadran_2_h_n_a 2010 cadran_2_v_a_n 1924 cadran_2_v_n_a 4214 cadran_3_h_a_n 2326 cadran_3_h_n_a 36

29 cadran_3_v_a_n 3615 cadran_3_v_n_a 2127 cadran_4_h_a_n 3518 cadran_4_h_n_a 2330 cadran_4_v_a_n 3510 cadran_4_v_n_a 16

Intervalele găsite pentru Fig. 26

Aceste intervale sunt introduse într-un fişier text în felul următor:

if ((0 <= cadran_1_h_a_n) && (cadran_1_h_a_n <= 11))

if ((19 <= cadran_1_h_n_a) && (cadran_1_h_n_a <= 34))if ((21 <= cadran_1_v_a_n) && (cadran_1_v_a_n <= 40))

if ((31 <= cadran_1_v_n_a) && (cadran_1_v_n_a <= 48))


if ((13 <= cadran_2_h_n_a) && (cadran_2_h_n_a <= 20))

if ((10 <= cadran_2_v_a_n) && (cadran_2_v_a_n <= 19))


if ((14 <= cadran_3_h_a_n) && (cadran_3_h_a_n <= 23))if ((26 <= cadran_3_h_n_a) && (cadran_3_h_n_a <= 36))




if ((18 <= cadran_4_h_n_a) && (cadran_4_h_n_a <= 23))


if ((10 <= cadran_4_v_n_a) && (cadran_4_v_n_a <= 16))După ce am scris într-un fişier textul de mai sus, îl copiez în codul sursă. Acest text

reprezină secvenţa de cod pentru verificarea intervalelor pentru litera a. Dacă, atunci când se

analizează o imagine nouă, pentru o literă găsită se potrivesc toate cele 16 intervale, atunci

litera găsită este interpretată ca şi litera "a".

Până în acest punct, programul a găsit o zonă în care pixelii sunt uniţi, a copiat acei

pixeli într-o imagine separată, a împărţit formaţiunea de pixeli în patru cadrane şi a calculat

procentele de stări pentru fiecare din cele 4 cadrane, obţinând 16 variabile. Dacă cele 16

variabile se potrivesc cu cele din baza de date, litera este identificată şi este returnată sub

44



formă de caracter. Dacă litera nu este identificată, acea literă este ştearsă din imaginea

Imagine_Alb_Negru. Funcţia care şterge litera este exact ca şi funcţia care copiază litera cu

următoarele deosebiri:

Funcţia Copiaza_Linie() Funcţia Sterge_Linie()Liniile sunt copiate Liniile sunt şterse

Liniile se copiază în Imagine_Litera Liniile se şterg în Imagine_Alb_NegruVerifică punctele de pe jumătatea înălţimii

care sunt cel mai în stânga şi cel mai îndreapta în literă

Nu verifică nici un alt punct de pe literă

Imaginea Alb_Negru după ştergerea unei litere este cea din Fig. 26 b:

a) Imagine_Alb_Negu înainte de ştergerea literei b)Imagine_Alb_Negru după ştergerea litereiFig. 26 Ştergerea unei litere neidentificate

Dacă litera a fost identificată se procedează în felul următor:

• Dacă parcurgerea se face de la dreapta la stânga, se verifică coordonatele literei

găsite anterior pentru determinarea spaţiului dintre litere. De asemenea, se

verifică dacă nu s-a trecut pe alt rând, deoarece este posibil ca rândurile să fie

înclinate.

• Dacă parcurgerea se face de la stânga la dreapta, se verifică coordonatele literei

următoare pentru determinarea spaţiului dintre litere.

Determinarea spaţiului dintre litere şi urmărirea unui rând

Litera a fost identificată şi am următoarele informaţii despre literă: x_dreapta,

x_stânga, y_jos, y_sus, jumatate_h, jumatate_v, x_d şi x_s.

Se apelează funcţia litere_1() care verifică dacă litera găsită este din acelaşi rând cu

litera găsită anterior şi verifică distanţa dintre litera găsită şi litera anterioară.

Exemplu:

Pasul 1: Verific dacă litera găsită este pe acelaşi rând cu litera anterioară (Fig. 27):

45

gasitaliteraanterioaralitera



Fig. 27 Urmărirea unui rând

În exemplul din Fig. 27 litera găsită (litera „ă” din cuvntul „continuă”) nu este pe

acelaşi rând cu litera anterioară (litera „i” din „concluzii”). În acest moment se iese din

căutarea spre dreapta şi se porneşte căutarea spre stânga de la prima literă identificată în rând

(Fig. 28).

Fig. 28 Trecerea la căutarea spre stânga când a ajuns la capătul rândului

Codul de program care compară dacă litera găsită este pe acelaşi rând cu litera

anterioară este următorul (se compară şi diferenţa pe orizontală pentru spaţiul dintre litere):

if (jumatate_v_1 < y_jos_2) //compar diferenta pe verticala (caracterulactual(2)[indentificat anterior] cu urmatorul(1)[ultimul identificat])

{s_1 = s; //ca sa nu am ultima litera din randul actual luata

din randul de jos daca randul de jos este inclinat

if ((x_stanga_1 - x_dreapta_2) >= l.p_v)if (x_dreapta_2 != 0){

rand_actual = rand_actual + _T(" ");}

}else{

capat_rand = true;trecere_litera_x = false;

}

Pasul 2:

Dacă litera găsită este pe acelaşi rând cu litera anterioară, se măsoară distanţa dintre

cel mai din dreapta punct pentru litera găsită şi cel mai din stânga punct pentru litera

anterioară (Fig. 29).

46

x_stanga

x_dreapta

taidentificaliteraprima



a) x_stanga şi x_dreapta b) distanţa dintre litereFig. 27 Distanţa pe orizontală

În funcţie de distanţa dintre cele două litere se pune sau nu spaţiu între litere. Distanţa

se calculează pentru fiecare literă în funcţie de înălţimea ei. Pentru unele litere este suficient o

distanţă de jumătate din literă pentru că literele au o înălţime mică. Pentru alte litere, care auînălţimea mare, distanţa se calculează ca fiind o treime din literă.

Trecerea la rândul următor

47



Parcurgerea unui rând de litere se face astfel: se caută un pixel de culoarea literei, se copiază

litera într-o imagine separată, se împarte în 4 cadrane şi se încearcă să se identifice. Dacă s-a

identificat, se trece la următoarea literă. După ce s-a trecut la următoarea literă, se verifică

dacă aceasta este pe acelaşi rând cu litera găsită anterior. Dacă nu este pe acelaşi rând, s-a

ajuns la capătul rândului şi căutarea se reia de la prima literă găsită în rând. Dacă este pe

acelaşi rând, se încearcă identificarea ei şi dacă s-a identificat se trece la litera următoare. Se

continuă trecerea la litera următoare până când s-a ajuns la capătul imaginii. Când s-a ajuns la

capătul imaginii, se revine la prima literă găsită în rând şi se face căutarea spre stânga până se

ajunge la marginea din stânga a imaginii. În acest moment se trece la rândul următor de litere.

Fig. 28 Algoritmul de urmărire a unui rând

După ce s-a terminat de parcurs un rând, se trece la rândul următor astfel:

• Coordonata x se mută la începutul imaginii

Caută pixel deculoarea litereiSpre dreapta

Identificălitera

Compară distanţa peverticală cu literaurmătoare

Distanţă bună

Distanţămare Nu identifică

litera

Revine la prima

literă din rând şicaută spre stânga

Caută pixel de culoarealiterei spre stânga

Identificălitera

Nu identificălitera

Compară distanţa peverticală cu literaurmătoare

Distanţa bună

Distanţămare

Trece la rândulurmător

Când a ajuns la capătul

din stânga imaginii trecela rândul următor

48



• Coordonata y se mută la cel mai de jos punct din rând

De fiecare dată când s-a identificat o literă se compară dacă punctul cel mai de jos din

literă este mai mare dacât cel mai de jos punct din rând. Dacă este, cel mai de jos punct din

literă devine cel mai de jos punct din rând. Iniţial cel mai de jos punct din rând are valoarea 0.După ce s-a trecut la rândul următor, se reia din nou algoritmul descris în Fig. 28. Trecerea la

rândul următor se face atâta timp cât coordonata y este mai mică decât înălţimea imaginii – 2

pixeli (marginea de 2 pixeli care s-a făcut la trecerea în alb-negru). Când s-a terminat de

parcurs imaginea (y = înălţimea imaginii – 2) se deschide o fereastră de salvare a unui fişier în

care se cere calea unde să se salveze fişierul text care conţine literele.

Concluzii

Programul oferă o acurateţe bună pentru imaginile luate cu aparat de fotografiat digital

sau telefon care are autofocus, litere de culoare neagră tipărite pe foaie albă şi rezoluţie de 3 –

4 Megapixeli pentru pagini A5. De asemenea, literele trebuie de fonturi Arial. Programul nu

recunoaşte tabele, funcţii matematice sau imagini. De asemenea, nu recunoaşte nici semnele

de punctuaţie. Programul respectă structura unui rând şi nu împarte documentul în mai multe pagini. Un avantaj major este acela că, probabilitatea de a face confuzii între litere este foarte

mică.

49



Comparaţie între ABBY Fine Reader şi Licenţa 2009

Caracteristici ABBY Fine Reader Licenta 2009Recunoaştere text DA DA

Recunoaştere formule

matematice NU NU

Recunoaştere imagini DA NUConfuzii Uneori În cazuri excepţionale

Algoritmul pe care se

bazează

Inteligenţă Artificială şi

dicţionar de cuvinte

Despărţirea imaginii în 2

culori, extragerea fiecăreilitere şi împărţirea ei în 4

cadrane. Compararea fiecărei

litere cu 16 intervale unice

pentru un caracter Respectă numărul de pagini

din originalDA

Respectă capătul de început

şi de sfârşit al fiecărui rând NU DAEste limitat de funcţiile

oferite de Microsoft

(motivul)

DA – pentru că foloseşte

Automate pentru Word

NU – pentru că scrie un fişier

nou octet cu octet

Numărul de persoane care au

realizarat softul

(fără noţiunile de sintaxă ale

limbajului de programare)

Echipă de cel puţin 10

persoane1 persoană

Timpul de realizare al 20 de ani de experienţă în 8 luni din care 5 luni pentru

50



softuluiOCR din care cel puţin 5

pentru aparate de fotografiat

aparat de fotografiat (3 luni

puntru studierea sintaxei şi a

imaginilor luate cu scanerul)

Perspective

Inteligenţă artificială mai

bună, fără recunoaşterea

formulelor matematice

Crearea unui algoritm care să

recunoască şi formule

matematice

Anexa 1 – Funcţia de zoom

Deoarece Visual C++ nu are funcţie de zoom pentru vizualizarea unei imagini dintr-un

PictureControl, am realizat eu o funcţie care face zoom pentru imaginea încărcată şi apoi o

afişează în PictureControl. Codul funcţiei functie_zoom() este următorul:

void CLicenta2009Dlg::functie_zoom(void){

int raport_pixel, diferenta, raport_pixel_1 = 0, latime_zoom = 0,inaltime_zoom = 0;

raport_pixel = Imagine.GetHeight() / 271;diferenta = Imagine.GetHeight() - raport_pixel * 271;

if (diferenta != 0) //daca am o diferenta arpoximez la cea mai marevaloare din intreg (programul trunchiaza diferenta la cea mai mica valoaredin intreg)

{raport_pixel = raport_pixel + 1;

}

while (raport_pixel_1 < Imagine.GetWidth()){

latime_zoom = latime_zoom + 1;raport_pixel_1 = raport_pixel_1 + raport_pixel;

}

raport_pixel_1 = 0; //resetez valoarea pentru raport_pixel_1

while (raport_pixel_1 < Imagine.GetHeight()){

inaltime_zoom = inaltime_zoom + 1;raport_pixel_1 = raport_pixel_1 + raport_pixel;

}

int raport_pixel_x = 0, raport_pixel_y = 0; //am nevoie deraport_pixel_x si y pt parcurgerea imaginii originale

//functia de zoomImagine_Zoom.Create(latime_zoom, inaltime_zoom, 24, 0);for (int y_zoom = 0; y_zoom < Imagine_Zoom.GetHeight(); y_zoom++){

for(int x_zoom = 0; x_zoom < Imagine_Zoom.GetWidth(); x_zoom++){

Imagine_Zoom.SetPixel(x_zoom, y_zoom,Imagine.GetPixel(raport_pixel_x, raport_pixel_y));

raport_pixel_x = raport_pixel_x + raport_pixel;

}raport_pixel_x = 0;raport_pixel_y = raport_pixel_y + raport_pixel;

51



}

picture_box.SetBitmap(Imagine_Zoom);

raport_pixel_1 = 0; //resetez valoarea pentru raport_pixel_1 pentruurmatoarea imagine

latime_zoom = 0; //resetez valoarea pt urmatoarea imagininaltime_zoom = 0; //resetez valoarea pt urmatoarea imagine}

Bibliografie

[1] Emanuel Ciprian Sasu, Informatică Industrială, Editura Universităţii „Aurel Vlaicu” Arad

– 2005

[2] http://msdn.microsoft.com

52

http://msdn.microsoft.com/

http://msdn.microsoft.com/

recunoastere optica de caractere

Documents