UNIVERSITATEA TEHNICA DIN CLUJ-NAPOCAFACULTATEA DE ELECTRONICA, TELECOMUNICATII SI

TEHNOLOGIA INFORMATIEISpecializarea Tehnologii şi sisteme de Telecomunicaţii

Contribuţii la analiza şi implementarea unor metode de extragere a caracteristicilor din imagini în vederea clasificării lor

Lucrare de licenţă

PRESEDINTE COMISIE, DECAN,Prof. dr. ing Gavril Toderean Prof.dr.ing. Marina ŢOPA

CONDUCATOR, ABSOLVENT,Asist. ing. Anca Apătean Alexandru Mihu

2010

UNIVERSITATEA TEHNICA DIN CLUJ-NAPOCAFACULTATEA DE ELECTRONICA, TELECOMUNICATII SI

TEHNOLOGIA INFORMATIEICATEDRA DE COMUNICAŢII

Titlul temei: Contribuţii la analiza şi implementarea unor metode de extragere a caracteristicilor din imagini în vederea clasificării lor

Enunţul lucrarii de licenţă:

Proiectul trebuie să conţină metodologia de alegere a caracteristicilor extrase din imagini, implementarea unei aplicaţii Matlab de extragere a trăsăturilor din imaginile bazei de date pentru clasificarea acestora. Obiectivele sunt documentarea metodelor de extragere a trăsăturilor deja existente, clasificarea imaginilor pe baza trăsăturilor extrase şi realizarea din punct de vedere aplicativ a unei interfeţe grafice de extragere a trăsăturilor şi clasificare a imaginilor.

Locul de executie: Laborator 211

Data emiterii temei: 20 februarie 2009

Termen de predare: 24 iunie 2010

ŞEF CATEDRĂ, ABSOLVENT,Prof.dr.ing. Virgil DOBROTA Alexandru Mihu

CONDUCATOR,Asist.ing. Anca Apătean

FACULTATEA DE ELECTRONICĂ, TELECOMUNICAŢII ŞI TEHNOLOGIA INFORMAŢIEI

Declaraţia autorului

Subsemnatul declar prin prezenta că ideile, partea de implementare şi experimentală, rezultatele, analizele şi concluziile cuprinse în această lucrare constituie efortul meu propriu, mai puţin acele elemente ce nu-mi aparţin, pe care le indic şi le recunosc ca atare.

Declar de asemenea, că după ştiinţa mea, lucrarea în această formă este originală şi nu a mai fost niciodată prezentată sau depusă în alte locuri sau altor instituţii decât cele indicate în mod expres de mine.

În calitate de autor, cedez toate drepturile de utilizare şi modificare a lucrării de licenţă către Universitatea Tehnică din Cluj-Napoca.

Cluj-Napoca, 24 iunie 2010

ABSOLVENT,

Alexandru Mihu

1. absolvent Alexandru Mihu

2. asist. ing. Anca Apătean

SINTEZA LUCRARII DE LICENŢĂ

Contribuţii la analiza şi implementarea unor metode de extragere a caracteristicilor (trăsăturilor) din imagini în vederea clasificării lor

Imaginile digitale, costul redus de realizare şi stocare al acestora, precum şi utilizarea lor în tot mai multe domenii ale ştiinţei şi ingineriei, au introdus o creştere a cererii de aplicaţii de analiză şi clasificare a imaginilor cu o precizie cât mai mare şi într-un timp cât se poate de scurt.

Lucrarea urmăreşte extragerea trăsăturilor din imaginile unor obstacole ce se pot găsi în scenele rutiere pentru a obţine o acurateţe a clasificării cât mai mare. Imaginile sunt grupate în patru categorii: maşini, pietoni, animale şi garbage, fiind în număr de 200 pentru fiecare clasă. Aceste obiective au fost realizate prin studierea mai multor referinţe bibliografice. Soluţia adoptată este reprezentată de utilizarea unor metode de extragere a trăsăturilor ce fac parte din metodologia de formare a vectorului de caracteristici al clasificatorului WND-CHARM [9].

Numărul de trăsături extrase a fost redus, prin renunţarea la metodele ineficiente de extragere în ceea ce priveşte performanţele de clasificare, la 318 atribute pe imagine comparativ cu 1024 atribute pe imagine folosite pentru formarea vectorului de trăsături din cadrul clasificatorului WND-CHARM. Astfel, timpul de extragere al trăsăturilor tuturor imaginilor din baza de date, precum şi timpul de clasificare au fost micşorate semnificativ (de aproximativ 11 ori pentru timpul de extragere al trăsăturilor tuturor imaginilor din baza de date şi de aproximativ 3 ori pentru timpul de clasificare al celor 20% din imaginile ficărei clase destinate testării).

Prin modificarea bazei de imagini aplicaţia realizată poate fi utilizată în probleme de detecţie sau recunoaştere din diverse domenii.

ABSTRACT

Digital images, cheap costs of acquisition and storage, as well as increasing use in many fields of science and engineering, introduces a demand of image analysis and classification with high accuracy and lower classification time.

This thesis follows feature extraction from obstacle images that can be found in traffic scenes with high classification accuracy. The images are grouped in four main groups, each with with 200 images ilustrating cars, pedestrians, animals and backgrounds. This objectives were achieved by studying several bibliographic references. The adopted solution is reprezented by use of feature extraction methods that are part of feature vector forming described in WND-CHARM classifier [9]. Number of features per image have been reduced from 1024 attributes per image used in WND-CHARM feature vector to 318 attributes per image, by removing the inefficient extraction methods in terms of clasification performance. Thus, the time needed for feature extraction for all database images and classification time was reduced significantly (approximately 11 times for feature extraction time, respectively 3 times for test images classification time).

By changing the image database the application can be used in detection and recognition problems in many field of science and engineering.

CURRICULUM VITAE

Name and surname: Alexandru MihuDate of birth: 16th of November 1986

Studies: High School: Colegiul Naţional „Lucian Blaga”, Sebeş Tehnical University of Cluj Napoca

Professional activity: Internship at RDS & RCS S.A., technical advisor

Technical Knowledge: Advanced PC operating and programming skills:

Microsoft Windows and Office suite; Pascal , FoxPro, C , C++ , C# , embedded C, Java.

Electronical and mechanical CAD skills: OrCAD suite , AutoCAD

Known languages: English: Writing, Reading, Speaking: Very Good German: Writing: Acceptable, Reading: Acceptable, Speaking: Acceptable

Contact address: Address: Str.Valea Frumoasei 5C/8, Sebeş, Alba Telephone: 0746 041 672 E-mail address: mihu_alexandru_ioan@yahoo.com

I the undersigned, Alexandru Ioan Mihu, declare that all the data in this Curriculum Vitae can be used by The Faculty of Electronics, Telecommunications and Information Technology of the Technical University of Cluj- Napoca, for promotional pourposes and professional orientation, in the following conditions:

Without prior consult After prior consult I do not agree

Cuprins

1. Stadiul actual...............................................................................................................................1

2. Fundamentare teoretică...............................................................................................................2

2.1. Introducere.........................................................................................................................2

2.2 Transformata Wavelet continuă şi discretă........................................................................3

2.2.1 Transformata Wavelet continuă.................................................................................3

2.2.2 Transformata Wavelet discretă...................................................................................4

2.2.3 Familii de wavelet-uri:...............................................................................................5

2.2.4 Aplicaţii ale wavelet-urilor.........................................................................................5

2.3 Transformata FFT...............................................................................................................6

2.3.1 Definirea transformatei FFT......................................................................................6

2.3.2 Aplicaţii ale transformatei FFT..................................................................................7

2.4 Transformata Radon............................................................................................................7

2.4.1 Definirea transformatei Radon...................................................................................7

2.4.2 Aplicaţii ale transformatei Radon..............................................................................8

2.5 Caracteristicile Tamura.......................................................................................................8

2.5.1 Granularitatea............................................................................................................8

2.5.2 Contrastul...................................................................................................................9

2.5.3 Direcţionalitatea.........................................................................................................9

2.6 Polinoamele Zernike..........................................................................................................10

2.6.1 Definirea polinoamelor Zernike...............................................................................10

2.6.2 Aplicaţii ale polinoamelor Zernike...........................................................................11

2.7 Histograme multi-scală.....................................................................................................11

2.8 Filtre orientate în patru direcţii pentru obţinerea "primelor 4 momente"........................11

2.9 Algoritmul KNN................................................................................................................12

2.9.1 Avantajele algoritmului KNN...................................................................................13

2.9.2 Dezavantajele algoritmului KNN.............................................................................13

2.10 Fişiere MEX (MEX-files).................................................................................................14

3. Implementarea soluţiei adoptate...............................................................................................14

3.1 Baza de imagini.................................................................................................................15

3.2 Metoda de extragere a caracteristicilor............................................................................17

3.2.1 Metoda de extragere a caracteristicilor din WND-CHARM....................................19

3.2.2 Metoda de extragere a caracteristicilor adoptată....................................................20

3.2.3 Evaluarea trăsăturilor în Weka...............................................................................23

3.2.4 Evaluarea trăsăturilor în Matlab.............................................................................25

3.3 Determinarea parametriilor transformatei Wavelet..........................................................25

3.4 Modul de împărţire a datelor pentru învăţare şi testare...................................................27

3.5 Îmbunătăţirea performanţelor...........................................................................................28

3.5.1 Reducerea numărului de trăsături extrase din fiecare imagine……………………...35

3.5.2 Transformarea aplicaţiei într-un executabil.............................................................29

3.6 Interfaţa grafică a aplicaţiei..............................................................................................30

3.6.1 Extragerea trăsăturilor.............................................................................................31

3.6.2 Clasificarea imaginilor.............................................................................................31

3.6.3 Testarea clasificatorului KNN şi cu alte imagini decât cele din baza de date.........31

4. Rezultate experimentale.............................................................................................................31

4.1 Rezultate experimentale Weka...........................................................................................32

4.2 Rezultate experimentale din Matlab şi din aplicaţia executabilă......................................30

5. Concluzii....................................................................................................................................35

6. Bibliografie................................................................................................................................37

7. Anexe..........................................................................................................................................39

7.1 Anexa 1..............................................................................................................................39

Codul Matlab al funcţiei de realizare a transformatei Wavelet..................................................39

7.2 Anexa 2..............................................................................................................................39

Codul Matlab pentru obţinerea fişierului ce conţine trăsăturile imaginilor din baza de date.....39 7.3 Anexa 3..............................................................................................................................39

Codul Matlab al funcţiei de extragere trăsături............................................................................39

7.4 Anexa 4..............................................................................................................................41

Codul Matlab pentru obţinerea fişierului cu liniile vectorului de caracteristici permutate.........41

Codul Matlab pentru funcţia prelucrarefisierIN...........................................................................41

Codul Matlab pentru functia preiaDatelePtPrel...........................................................................42

7.5 Anexa 5..............................................................................................................................43

Codul Matlab pentru clasificarea KNN.........................................................................................43

7.6 Anexa 6..............................................................................................................................44

Codul Matlab al aplicaţiei GUI.....................................................................................................44

Codul Matlab pentru metodele de extragere folosite în aplicaţia GUI.........................................63

Codul Matlab pentru extracţia trăsăturilor din fiecare imagine în funcţie de metodele alese în aplicaţia GUI.................................................................................................................................64

Lista de figuri

Figura 1.1 Schema procesului de recunoaştere şi clasificare automată a imaginilor......................3Figura 2.1 Arborele cu primele trei nivele de descompunere DWT(arborele Mallat)....................4Figura 2.2 Arborele Mallat cu primele trei nivele de reconstrucţie ale semnalului original...........4Figura 2.3 Familii de wavelet (a) Haar (b) Daubechies4 (c) Coiflet1 (d) Symlet2 (e)Meyer(f) Morlet(g) Mexican hat.....................................................................................................................5Figura 2.4 Cele două forme ale transformatei Radon- ecuaţia (7) şi (9)........................................7Figura 2.5 Valorile Zernike în unitatea de disc.............................................................................10Figura 3.1 Imagini din baza de date...............................................................................................16Figura 3.2 Schema bloc a metodelor de extragere a trăsăturilor...................................................17Figura 3.3 Schema de formare a vectorului de trăsături din cadrul WND-CHARM....................19Figura 3.4 Grupele de caracteristici din WND-CHARM..............................................................22Figura 3.5 Schema de formare a vectorului de trăsături................................................................22Figura 3.6 Structura fişierului ARFF la modul general.................................................................23Figura 3.7 Structura fisierului ARFF utilizat în acestă lucrare......................................................23Figura 3.8 Matricele de confuzie pentru învăţare, respectiv testare..............................................24Figura 3.9 Transformata Wavelet a unei imagini..........................................................................27Figura 3.10 Schema bloc a clasificării KNN.................................................................................27Figura 3.11 Schema bloc de realizare a executabilului.................................................................29Figura 3.12 Interfaţa grafică a lucrării...........................................................................................30Figura 4.1 Matrice de confuzie Weka (numărul de vecini=1).......................................................32Figura 4.2 Matricele de confuzie pentru k=3 (a), respectiv k=5 (b) obţinute în Weka.................32Figura 4.3 Matricele de confuzie pentru setul de testare (k=1,3 şi 5) obţinute în Weka...............33Figura 4.4 Matricele de confuzie pentru setul de testare obţinute în Matlab.................................33Figura 4.5 Graficul timpilor de clasificare KNNR şi KNNC în funcţie de numărul de trăsături..........................................................................................................................................34Figura 4.6 Graficul timpului de clasificare în funcţie de numărul de trăsături..............................34Figura 4.7 Graficul timpului de extragere coeficienţi în funcţie de numărul de trăsături.............35Figura 4.8 Graficul acurateţii în funcţie de numărul de trăsături...................................................35

Lista de tablele

Tabel 3.1 Metode de extragere a trăsăturilor analizate..................................................................22Tabel 4.1 Rezultate obţinute în Matlab..........................................................................................33Tabel 4.2 Rezultate obţinute prin transformarea aplicaţiei într-un executabil..............................34

1. Stadiul actual

Stadiul actual în ceea ce priveşte recunoaşterea formelor şi clasificarea automată a imaginilor este unul avansat, reuşindu-se dezvoltarea unor aplicaţii care au o acurateţe a clasificării foarte ridicată şi un timp de clasificare sau de detecţie foarte bun (detecţie sau clasificare în timp real), şi care încet-încet promit a se apropia ca performanţă de modul natural cu care fiinţa umană tratează această problemă.

Imaginile digitale, stocarea ieftină şi utilizarea acestora în tot mai multe domenii ale ştiinţei şi ingineriei, au introdus o creştere a cererii de aplicaţii de analiză şi clasificare a imaginilor cu o precizie cât mai mare. Aceste aplicaţii includ teledetecţia, descrisă în [1], recunoaşterea facială, despre care se pot găsi informaţii în [2], [3] sau [4] şi clasificarea imaginilor medicale şi biologice [5], [6], [7] sau [8].

Sistemele de vedere artificială sunt proiectate după modelul sistemelor biologice, în special cel uman. În dezvoltarea unor astfel de sisteme ne lovim, de foarte multe probleme. Cea mai importantă dintre ele este imposibilitatea de a reproduce modul nostru de gândire în sistemele artificiale. Pentru noi oamenii, recunoaşterea unui obiect se face cu uşurinţă, chiar dacă acel obiect nu este văzut în întregime, dar în general nu putem explica ştiinţific cum am reuşit să realizăm recunoaşterea. Prin urmare, nu putem dezvolta un algoritm sau o tehnică de inteligenţă artificială care descrie iterativ şi exact acest proces.

Deşi în ultimii ani au atras o atenţie deosebită, analiza şi clasificarea imaginilor sunt deocamdată considerate probleme competitive în sistemele de prelucrare şi clasificare pe baza conţinutului imaginilor (CBIR - Content Based Image Retrieval), datorită complexităţii subiectului în ceea ce priveşte imaginile reale şi dificultatea de extragere cantitativă a trăsăturilor de similitudine sau diferenţiere dintre imagini. Aceste trăsături în general includ caracteristici de culoare, textură sau formă. Caracteristicile sunt obţinute global, prin extragerea informaţiilor pe baza mediei histogramelor de culoare (pentru caracteristicile de culoare), pe baza granularităţii, contrastului şi directivităţii imaginilor (pentru caracteristicile de textură) şi pe baza trăsăturilor de curbură, momente invariante, circularitatea şi excentricitatea imaginilor (pentru caracteristicile de formă). Cu toate acestea, extragerea trăsăturilor din imagini se face diferit în funcţie de detaliile particulare ale aplicaţiei şi performanţele dorite.

În lucrarea de faţă sunt propuse mai multe metode deja existente de extragere a caracteristicilor pentru formarea vectorului de trăsături şi clasificarea imaginilor pe baza vectorului obţinut.

Scopul principal al acestei lucrări este testarea mai multor metode de extragere a trăsăturilor. Pentru a vedea eficienţa metodelor de extragere a caracteristicilor s-a realizat clasificarea imaginilor pe baza vectorului de caracteristici prin intermediul clasificatorului IBk din Weka (echivalentul KNN- K Nearest Neighbor) şi KNN implementat în Matlab. Aceste obiective au fost realizate prin studierea mai multor referinţe bibliografice. Soluţia adoptată este reprezentată de utilizarea unor metode de extragere a trăsăturilor ce fac parte din metodologia de formare a vectorului de caracteristici al clasificatorului WND-CHARM (Weighted Neighbor Distances using a Compound Hierarchy of Algorithms Representing Morphology[9]) - distanţa ponderată dintre vecini utilizând o ierarhie compusă de algoritmi morfologici. Pentru mai multe detalii a se consulta [9].

Trăsăturile vectorului de caracteristici includ descompunerea polinomială (reprezentată de polinoamele Zernike), elementele de statistică a pixelilor (media, deviaţia standard, skewness- oblicitatea, kurtosis- planitatea, histogramele multi-scală) şi caracteristicile de textură (contrast, granularitate şi direcţionalitate). Aceste caracteristici au fost extrase din imaginile pe nivele de gri, precum şi din imaginile rezultate în urma transformatelor Wavelet (a imaginii pe nivele de gri şi a transformatei FFT- Fast Fourier Transform a imaginii pe nivele de gri). O altă transformată utilizată este transformata Radon a imaginii pe nivele de gri, care este folosită pentru extragerea informaţiei spaţiale.

1

Metodele aplicate asupra imaginilor pentru formarea vectorului de trăsături fac parte din metodologia descrisă în [9]. Contribuţia adusă la formarea vectorului de trăsături constă în selectarea din varietatea de metode de extragere doar a celor care oferă o performanţă de clasificare mai ridicată. Pentru o aplicare eficientă a transformatei Wavelet s-au stabilit valorile parametrilor: familia de wavelet şi nivelul de descompunere wavelet. Celelate metode utilizate, precum şi implementările lor în Matlab pot fi descărcate gratuit şi utilizate în scopuri ştiinţifice şi de cercetare de pe site-ul: http://www.openmicroscopy.org.

Vectorul de trăsături este utilizat apoi pentru clasificarea imaginilor de test într-un set de clase de imagini predefinit (clasa maşini, pietoni, animale şi garbage) cu ajutorul utilitarului Weka. Deoarece apelarea din Matlab a utilitarului Weka este foarte complicată şi datorită faptului că s-a dorit dezvoltarea unei aplicaţii de sine stătătoare în Matlab, s-a ales implementarea în Matlab a unui algoritm de clasificare. În luarea deciziei asupra clasei imaginii de test s-a folosit algoritmul KNN. Din punct de vedere al evaluatorului s-a ales folosirea KNN deoarece este un clasificator rapid, eficient şi uşor de implementat. Pentru a nu permite clasificatorului să înveţe inclusiv ordinea de preluare a imaginilor s-a realizat permutarea imaginilor din vectorul de caracteristici.

Din punct de vedere aplicativ, lucrarea conţine o interfaţă grafică dezvoltată cu ajutorul toolbox-ului GUIDE (Graphical User Interface Design Environment) din Matlab. Această aplicaţie permite utilizatorului să selecteze diferite variante de formare a vectorului de trăsături, precum şi posibilitatea testării clasificatorului KNN cu alte imagini decât cele din baza de date. Vectorul de trăsături poate avea, în funcţie de metodele selectate de utilizator, o dimensiune minimă de 72 caracteristici şi maximă de 318 caracteristici. Toate atributele sunt extrase pe baza imaginilor pe nivele de gri, astfel informaţiile de culoare nefiind utilizate.

2. Fundamentare teoretică

2.1. Introducere

În realizarea unei aplicaţii de recunoaştere a formelor şi clasificare automată a imaginilor, după cum se poate observa în figura 1.1, în general se parcurg următoarele etape:a) preprocesarea imaginii - etapă în care se realizează îmbunătăţirea calităţii imaginilor prin aplicarea unor algoritmi DIP (digital image processing).[10]

Deoarece imaginile din baza de date formată pentru acestă lucrare nu necesită alte îmbunatăţiri ale calităţii, în acestă etapă s-a realizat doar conversia imaginilor color în imagini pe nivele de gri. În multe situaţii, pentru clasificarea imaginilor sunt extrase pe lângă trăsăturile de textură şi de formă, şi cele de culoare. S-a renunţat la aceste caracteristici deoarece nu se poate realiza o diferenţiere a claselor pe baza culorii şi obiectele vizate de aplicaţia de faţă se găsesc într-un mediu exterior, unde informaţia de culoare este foarte bogată şi variată.b) extragerea caracteristicilor sau trăsăturilor din imagine - reprezintă etapa cea mai importantă deoarece influenţează în mod direct performanţele de clasificare.[10]

Tipul trăsăturilor folosite în clasificare şi descrise în această lucrare se împart în trei categorii: descompunere polinomială, statisticile pixelilor şi textură. În descompunerea polinomială este generat un polinom ce aproximează imaginea în funcţie de gradul de fidelitate, iar coeficienţii acestui polinom sunt utilizaţi ca trăsături ai conţinutului imaginii. Caracteristicile de textură se referă la variaţia în intensitate între pixelii imaginii pentru diferite direcţii şi rezoluţii. Statisticile pixelilor se bazează pe distribuţia pixelilor din imagine şi includ histograme şi momente.

În această etapă, pentru extragerea trăsăturilor, asupra imaginilor s-a aplicat transformata Wavelet (transformata Wavelet a imaginii pe nivele de gri şi transformata Wavelet a transformatei FFT a imaginii pe nivele de gri), iar din rezultatele obţinute au fost extrase

2

caracteristicile de statistică a pixelilor ("primele 4 momente", histogramele multi-scală) şi de textură (caracteristicile Tamura). Din imaginile originale (imaginile pe nivele de gri), fără a aplica asupra acestora nici o transformată, sunt extrase caracteristicile de statistică a pixelilor şi de textură menţionate mai sus, precum şi cele de descompunere polinomială (polinoamele Zernike). Din vectorul de trăsături mai fac parte şi caracteristicile obţinute în urma transformatei Radon a imaginii pe nivele de gri. c)evaluarea caracteristicilor sau trăsăturilor - este o etapă în care sunt evaluate datele din vectorul de caracteristici şi care are ca rezultat în mod obişnuit, o valoare numerică unidimensională sau multidimensională (un vector). Această valoare numerică relevă distanţa vectorului de trăsături faţă de graniţele regiunilor sau faţă de "bornele de clasificare".[10]

În lucrarea de faţă evaluarea trăsăturilor s-a realizat cu ajutorul clasificatorului KNN, cu un numărul de vecini k=1,3 sau 5. S-a ales o valoare impară a numărului de vecini doarece s-a dorit evitarea cazurilor în care clasificatorul poate atribuii imaginea de test la două clase diferite în acelaşi timp. d) clasificarea imaginii - este etapa care îmbină rezultatele măsurătorilor multiple anterioare, şi totodată reprezintă etapa finală a sistemului.

Prin clasificare se stabileşte apartenenţa formei, obiectului sau imaginii - descrisă prin vectorul de trăsături, la un set de clase de imagini predefinite.[10]

Clasificarea imaginilor de test, precum şi stabilirea atributelor imaginilor care ne oferă cea mai bună performanţă s-a realizat cu ajutorul algoritmului KNN.

Figura 1.1 Schema procesului de recunoaştere şi clasificare automată a imaginilor[10]

2.2 Transformata Wavelet continuă şi discretă

2.2.1 Transformata Wavelet continuă

Transformata wavelet continuă (CWT- Continuous Wavelet Transform) este folosită la împărţirea funcţiilor de timp continue în unde mai mici.

Ecuaţia transformatei wavelet continuă este următoarea:

XWT(τ,s)=

1

√¿ s∨¿∫ x (t )∗ψ¿ ( t−τs )dt ¿ (1),

unde x(t) este semnalul ce trebuie analizat şi ψ(t) este wavelet-ul mamă sau funcţia de bază [11]. Toate funcţiile folosite în transformare sunt derivate din funcţia de bază prin translatare (shiftare) şi scalare (dilatare sau compresie). Parametrul de translaţie τ se referă la locaţia funcţiei wavelet în timpul parcurgerii semnalului, acesta corespunzând informaţiei de timp a transformatei. Parametrul de scalare s este definit ca |1/frecvenţă| şi corespunde informaţiei de frecvenţă. Scalarea fie dilatează (extinde) sau comprimă semnalul. În prelucrările de imagini, de obicei, se doreşte compresia lor, pentru ca timpul necesar prelucrării să fie cât mai redus. Pe o scară largă de frecvenţe joase semnalul este dilatat, fiind furnizate detaliile ascunse din semnal, în timp ce pe o scară redusă (frecvenţe înalte) semnalul este comprimat, furnizându-se informaţia globală referitoare la semnal. Transformata Wavelet realizează convoluţia semnalului şi prelucrarea acestuia cu funcţia de bază.

3

2.2.2 Transformata Wavelet discretă

Transformata Wavelet discretă (DWT- Discrete Wavelet Transform) este o versiune simplificată a transformării wavelet continuă, bazată pe codarea în sub-bandă. Avantajul acestei transformate constă în simplitatea implementării, reducerea timpului de execuţie şi nivelul mai scăzut de resurse necesare. La transformata CWT, semnalele sunt analizate folosind un set de funcţii de bază care realizează o simplă scalare şi translaţie. În cazul transformatei DWT, o reprezentare în domeniul timp a unui semnal digital este obţinută prin utilizarea tehnicilor de filtrare digitală, semnalul (imaginea) ce trebuie analizat fiind trecut prin filtre cu diferite frecvenţe de tăiere la nivele diferite. Transformata DWT este realizată prin filtrări trece jos şi filtrări trece sus succesive, ale unui semnal discret în domeniul timp (figura 2.1).

Figura 2.1 Arborele cu primele trei nivele de descompunere DWT(arborele Mallat)[11]

În figura de mai sus semnalul este notat cu x[n], unde n este un număr întreg, filtrarea trece jos este realizată de blocul G0, la ieşirea lui obţinând aproximarea grosieră a coeficienţilor (notată a[n]), iar filtrarea trece sus este realizată de H0, la iesire obţinând informaţia detaliată (notată d[n]).

Filtrele care împart banda în jumătate produc semnale ce ocupă doar jumătate din banda de frecvenţă. Filtrarea şi descompunerea vor continua până când se ajunge la nivelul dorit, numărul maxim de nivele de descompunere depinzând de lungimea semnalului (dimensiunea imaginii).

Reconstrucţia semnalului original pe baza coeficienţilor transformatei DWT este procesul invers descompunerii (figura 2.2).

Figura 2.2 Arborele Mallat cu primele trei nivele de reconstrucţie ale semnalului original[11]

4

În Figura 2.2, d[n] reprezintă coeficienţii de detaliu ai semnalului, a[n] aproximările grosiere şi blocurile H1 şi G1 reprezintă filtrele trece sus, respectiv filtrele trece jos de sintetizare a semnalului original.

Procesul de reconstrucţie al semnalului original continuă până când este atins numărul de nivele de descompunere ale semnalului.

Condiţiile ce trebuie îndeplinite pentru a avea o reconstrucţie perfectă sunt:

G0(-z)*G1(z)+H0(-z)*H1(z)=0 | (2)

G0(z)*G1(z)+H0(z)*H1(z)=2z−d (3),

unde G0(z) şi G1(z) sunt filtrele trece jos de analiză, respectiv de sinteză, iar H1(z)şi H0(z) sunt filtre trece sus de analiză, respectiv de sinteză[11].

Prima condiţie impune ca reconstrucţia să se facă fără alias, iar cea de-a doua condiţie impune ca distorsiunile de amplitudine sa aibă valoarea egală cu 1.

2.2.3 Familii de wavelet-uri:

Există un anumit număr de funcţii de bază care pot fi folosite ca funcţii mamă pentru transformata Wavelet, dar pentru utilizarea eficientă a acestora, trebuie luate în considerare detaliile particulare ale aplicaţiei care foloseşte wavelet-uri. Principalele familii de wavelet-uri:

Figura 2.3 Familii de wavelet (a) Haar (b) Daubechies4 (c) Coiflet1 (d) Symlet2 (e) Meyer (f)Morlet (g) Mexican hat [11]

Figura 2.3 ilustrează cele mai utilizate funcţii wavelet. Wavelet-ul Haar este unul din cele mai vechi şi simple wavelet-uri, de aceea orice discuţie despre wavelet-uri începe cu acesta. Pentru mai multe detalii legate de principalele tipuri de wavelet-uri a se consulta [12].

2.2.4 Aplicaţii ale wavelet-urilor

Există o gamă largă de aplicaţii pentru transformata Wavelet care este utilizată în diferite domenii, de la procesarea semnalelor până la domeniul biometriei.

Wavelet-urile au un rol important în compresia datelor, în vederea îmbunatăţirii performanţelor de prelucrare a imaginilor (de compresie a imaginilor). FBI utilizează wavelet-urile ca şi compresie standard a amprentelor, pentru stocarea lor în baza de date. Dintre

5

principalele tipuri de transformate aplicate imaginilor în vederea compresiei lor (ex. transformata cosinus discretă, transformata Fourier discretă 2D etc.), transformata Wavelet asigură asigură o foarte bună rată de compresie.

Transformata Wavelet este aplicată în această lucrare pe imaginile pe nivele de gri, precum şi pe imaginea obţinută în urma aplicării transformatei FFT asupra imaginii pe nivele de gri. Parametrii transformatei, nivelul de descompunere şi familia wavelet, au fost stabiliţi parcurgând următoarele etape:

a) extragerea trăsăturilor imaginilor din baza de date cu metoda I (vezi figura 3.2 pentru mai multe detalii) pentru diferite nivele de descompunere wavelet (36) şi pentru diferite familii de wavelet-uri.

b) clasificarea imaginilor pe baza vectorului de trăsături obţinut prin metoda de mai sus pentru a observa care nivel, respectiv familie wavelet oferă o performanţă de clasificare cât mai bună.

Wavelet-urile sunt folosite atât în metoda I de extragere a trăsăturilor precum şi în metoda II (vezi figura 3.2).

2.3 Transformata FFT

FFT este abrevierea din limba engleză pentru Fast Fourier Transform (Transformata Fourier Rapidă), fiind un algoritm eficient de calcul al transformatei DFT - Discrete Fourier Transform (Transformata Fourier Discretă), precum şi a inversei sale IDFT (Inverse Discret Fourier Transform).

2.3.1 Definirea transformatei FFT

FFT produce exact aceleaşi rezultate ca şi DFT, singura diferenţă fiind reprezentată de rapiditatea transformatei FFT. Fie x0 , x1 , …, x N−1, numere complexe. Transformata DFT este definită de următoarea formulă:

X (k+1 )=∑n=0

N −1

x (n+1)W Nkn , k=0,1,… ,N-1 (4),

iar inversa ei IDFT este:

X (n+1 )= 1N∑k=0

N −1

X (k+1)W N−kn, n=0,1, … ,N-1 (5),

unde j este unitatea imaginară, W N=e− j 2π

n şi N= lungime(x) [13].

Evaluând ecuaţia (4), observăm că aceasta necesită N2 operaţii: sunt N ieşiri X k şi fiecare ieşire necesită o sumă de N termeni. Transformata FFT reprezintă orice metodă de obtinere a aceluiaşi rezultat ca şi DFT în N log N operaţii. Pentru mai multe informaţii legate de transformata FFT şi tipurile de algoritmi FFT a se consulta [13],[14] sau [15].

În lucrarea de faţă transformata FFT este utilizată în cadrul metodei II de extragere a trăsăturilor, fiind aplicată asupra imaginii pe nivele de gri, iar apoi asupra acesteia se va aplica transformata Wavelet (vezi figura 3.2 pentru mai multe detalii).

6

2.3.2 Aplicaţii ale transformatei FFT

Transformata FFT are aplicaţii în următoarele domenii:- compresia datelor (ex. MP3)- analiza spectrală a semnalelor- filtrare- obţinerea răspunsului în frecvenţă a unui sistem- rezolvarea ecuaţiilor parţial diferenţiale- convoluţia în domeniul frecvenţă: - intercorelare - multuplicarea de numere întregi mari - multiplicarea simbolică a polinoamelor

2.4 Transformata Radon

Transformata Radon şi transformata Hough sunt strâns legate una de cealaltă, Radon fiind o formă particulară a transformatei Hough.

2.4.1 Definirea transformatei Radon

O reprezentare utilă a unei drepte este ecuaţia sa în coordonate polare:

xcosθ+ ysinθ=ρ (6),

unde unde ρ reprezintă distanţa dintre dreaptă şi origine, iar θ este unghiul dintre axa x pozitivă şi dreapta ρ [16].

Transformata Radon se defineşte ca integrală de-a lungul unei drepte înclinate cu unghiul θ faţă de axa x pozitivă şi situată la distanţa ρ faţă de origine [17]. Se notează în general cu g(ρ , θ) şi are următoarea formulă:

g(ρ , θ)=∬−∞

+∞

f ( x , y )δ (xcosθ+ ysinθ−ρ)dxdy(7),

unde δ reprezintă funcţia Dirac şi este ilustrată în [16] astfel:

δ (x )={+∞, x=00 , x ≠ 0

(8)

7

Figura 2.4 Reprezentarea grafică a celor două forme ale transformatei Radon- ecuaţia (7) şi (9) [17][18]

Ecuaţia ilustrată în [17]:

g(ρ , θ)=∫−∞

+∞

f (scosθ−u sinθ, ssinθ+u cosθ )du (9),

este echivalentă cu ecuaţia (2), fiind obţinută prin rotirea axelor de coordonate cu unghiul θ ,unde:

s= xcosθ+ y sinθ x=scosθ−u sinθ (10)

u=−x sinθ+ y cosθ y=x sinθ+u cosθ

Transformata Radon reprezintă o imagine ca un set de proiecţii de-a lungul diferitor direcţii, realizând legătura dintre spaţiul de coordonate (x,y) şi spaţiul proiecţiilor (ρ , θ).

Transformata Radon calculează proiecţia intensităţii pixelului pe o linie radială din centrul imaginii la un unghi specificat. Aceasta este utilizată, de obicei, pentru extracţia informaţiei spaţiale unde pixelii sunt corelaţi la un unghi specific.

În metoda de extragere a caracteristicilor din imagini, în lucrarea de faţă trăsăturile Radon sunt calculate pentru unghiurile 00, 450, 900 şi 1350. Apoi, fiecare set de valori rezultat este transformat într-o histogramă cu trei benzi, rezultând astfel un vector cu 4x3=12 valori. Transformata Radon este calculată pentru imaginea pe nivele de gri şi împreună cu "histogramele multi-scală, "primele 4 monemte" şi caracteristicile Tamura formează metoda III de formare a vectorului de trăsături (vezi figura 3.2 pentru mai multe detalii).

2.4.2 Aplicaţii ale transformatei Radon

Transformata Radon are aplicaţii în mai multe domenii cum ar fi:- domeniul medical, în cazul tomografiei compiuterizate- seismologie, în cazul reflexiei seismice- ultramicroscopia ansamblurilor macromoleculare, cum sunt proteinele şi viruşii- în rezolvarea ecuaţiilor hiperbolice parţial diferenţiale- detecţia de formă

2.5 Caracteristicile Tamura

Dintre proprietaţile Tamura folosite în acest proiect se numară:- granularitatea- contrastul- direcţionalitatea.

Aceste trăsături au fost selectate de Tamura, Mori şi Yamawaki pe baza experimentelor psihologice. Pentru mai multe detalii a se consulta [19].

2.5.1 Granularitatea se referă la distanţa dintre variaţiile spaţiale notabile a nivelelor de gri. Procedura compiutaţională propusă, consideră diferenţele dintre valoarea medie a semnalelor corespunzătoare ferestrelor de diferite dimensiuni care nu se suprapun, urmărind paşii de mai jos :

8

1. Pentru fiecare pixel (x,y), calculează şase valori medii pentru ferestrele de dimensiunea 2k × 2k, k=0,1,...,5 în jurul fiecarui pixel.

2. Pentru fiecare pixel, calculează diferenţa absolută Ek(x,y) dintre perechile valorilor medie ce nu se suprapun în direcţiile: orizontală şi verticală.

3. Pentru fiecare pixel, caută valoarea lui k ce maximizează diferenţa Ek(x,y) în orice direcţie şi setează dimensiunea cea mai bună Sbest(x,y)=2k.

4. Calculează trăsătura de granularitate Fcrs prin medierea Sbest(x,y) asupra întregii imagini.

2.5.2 Contrastul relevă modul în care nivelele de gri q, q=0,1,..., qmax, variază într-o imagine g şi a căror distribuţie este direcţionată spre alb şi negru. Pentru definirea contrastului se folosesc momentele centrale de ordinul al doilea şi cele normalizate de ordinul al patrulea, reprezentate de varianţa standard - σ, respectiv indicele de aplatizare - α4:

F con=σ

α 4n

(11 ),

unde: α 4=μ4

σ4 (12 ); σ 2=∑q=0

q max

(q−m )2 Pr ( qg )(13); μ4=∑

q=0

qmax

(q−m)4 Pr (q /g) (14) şi m este

media nivelelor de gri.[19]

2.5.3 Direcţionalitatea

Gradul de direcţionalitate este măsurat folosind distribuţia spectrală a muchiilor locale orientate, faţă de unghiurile direcţionale ale acestora. Soliditatea muchiei e(x,y) şi unghiul direcţional a(x,y) sunt calculate folosind detectorul de muchii Sobel, aproximând "pixel-wise" x şi derivata y a imaginii:

e (x , y )=0.5 (|∆x (x , y )|+|∆y ( x , y )|) (15)

a ( x , y )=tan−1(∆ y ( x , y ) /∆x ( x , y )) (16)

În ecuaţiile de mai sus Δx(x,y) şi Δy(x,y) sunt diferenţele pe verticală şi orizontală a nivelelor de gri dintre pixelii vecini [19]. Diferenţele sunt măsurate utilizând următorii operatori fereastră de dimensiune 3x3 [19]:

−1 0 1         1   1   1 −1 0 1         0   0   0 −1 0 1       −1 −1 −1

Histograma Hdir(a) a valorilor direcţiei cuantizate a este construită prin numărarea pixelilor muchie care un anumit unghi direcţional şi soliditatea muchiei mai mare decât un prag predefinit. Histograma este relativ uniformă pentru imaginile fără o orientare accentuată şi evidenţiază vârfurile pentru imaginile cu un grad al direcţionalităţii ridicat. Gradul direcţionalităţii este legat de ascuţimea vârfurilor şi este descrisă de următoarea ecuaţie:

9

Fdir=1−r npeaks∑p=1

n peaks

∑a∈w p

(a−ap )2 H dir (a) (17),

În ecuaţia (17) npeaks este numărul de vârfuri, ap este poziţia vârfului p, wp este gama de unghiuri atribuite vârfului p, r indică un factor de normalizare legat de nivelele de cuantizare ale unghiului a, şi a este unghiul direcţional cuantizat (în modulo 180o).[19]

Aceste proprietăţi texturale Tamura sunt calculate pe imaginea pe nivele de gri astfel: - 3 valori: contrastul, direcţionalitatea şi granularitatea - o histogramă a granularităţii cu 3 benziAstfel, rezultă astfel un vector de caracteristici cu 6 valori.

Trăsăturile Tamura sunt utilizate în acestă lucrare în cadrul metodelor I, II şi III de extragere a trăsăturilor (vezi Figura 3.2).

2.6 Polinoamele Zernike

Polinomele Zernike au fost dezvoltate la începutul secolului XX de către fizicianul german Frits Zernike (faimos pentru invenţia microscopului fază-contrast, pentru care a câstigat premiul Nobel pentru Fizică în 1953).

Figura 2.5 Valorile Zernike în unitatea de disc [20]

2.6.1 Definirea polinoamelor Zernike

Aceste caracterisitici Zernike sunt un set de polinoame definite pe unitatea de disc (figura 2.5), ce pot fi reprezentate atât în sistemul cartezian (x,y), cât şi în coordonate polare (r,). Cea mai utilizată formă, este descrisă în [21] ca fiind cea polară:

Z j ,impar=√n+1 Rnm (r ) √2cos ( m) , m≠ 0 (18)

10

Z j , par=√n+1 Rnm (r ) √2 sin (m) , m≠ 0 (19)

Z j=√n+1 Rn0 (r ) , m=0 (20),

unde:

Rnm (r )= ∑

s=0

(n−m)/2 (−1 ) s (n−s) !

s !( n+m2

−s)!( n−m2

−s)!rn−2 s

(21)

Valorile lui m şi n sunt întotdeauna întregi şi satisfac condiţile m≤n şi n-m=impar. Indexul j reprezintă modul de ordonare al numerelor, fiind o funcţie j(m,n).

Condiţia de ortogonalitate pentru polinoamele Zernike ilustrată în [21] este:

∫W (r )Z j Zk d2 r=π δ jk(22),

unde:

W (r )={1π

, pentrur ≤ 1

0 , pentru r>1 (23)

2.6.2 Aplicaţii ale polinoamelor Zernike

Baza acestor funcţii este definită pe o suprafaţă circulară, caracteristic planelor pupilelor în procesarea clasică de imagini, pentru lungimi de undă optice şi inflaroşii, printr-un sistem de lentile şi oglinzi cu un diametru finit.

Descompunera polinomială Zernike este utilizată în următoarele domenii:- prelucrare optică, pentru a caracteriza erorile observate în analizele interferometrice, cu scopul de a obţine performanţa dorită.-optometrie şi oftalmologie, la descrierea devierii corneei sau lentilelor pentru o formă sferică ideală, care au ca rezultat erori de refracţie.- optica adaptivă, la înlăturarea distorsiunilor atmosferice. Aplicaţiile în acest domeniu sunt astronomia vizibilă sau inflaroşie (IR) şi redarea imaginilor din satelit. De exemplu, unul dintre factorii Zernike (pentru m=0 şi n=2) este denumit "de-focus". Prin cuplarea iesirii acestui factor la un sistem de control, poate fi implementată o focalizare automată. [21]

Coeficienţii Zernike sunt valori complexe, în descrierea imaginilor folosindu-se valoarea absolută a acestora. Polinoamele Zernike sunt aplicate asupra imaginii pe nivele de gri, constituind metoda IV de extragere a trăsăturilor (pentru mai multe detalii vezi figura 3.2).

2.7 Histograme multi-scală

Pentru acest set de trăsături sunt calculate patru histograme cu un număr variabil de benzi (3, 5, 7 şi 9), după modelul propus în [9]. Fiecare domeniu de frecvenţe corespunde unei histograme diferite, şi astfel numărul variabil de benzi permite măsurarea conţinutului într-un domeniu de valori foarte larg. Maximul histogramelor este folosit pentru normalizarea vectorului de caracteristici rezultat, care are un număr de 1x24 elemente. Histogramele multi-scală sunt aplicate asupra transformatei Wavelet, transformatei FFT şi asupra imaginii originale (imagine

11

pe nivele de gri) contribuind astfel cu un număr total de 3x24 elemente la formarea vectorului de trăsături al imaginilor.

Histogramele multi-scală sunt utilizate în cadrul metodelor I, II şi III de formare a vectorului de trăsături (pentru mai multe detalii vezi figura 3.2).

2.8 Filtre orientate în patru direcţii pentru obţinerea "primelor 4 momente"

Pentru acest set de trăsături imaginea este subdivizată într-un set de "dungi" pentru patru orientări diferite (00, 900, +450 şi −450). "Primele 4 momente" (media, deviaţia standard, skewness şi kurtosis) sunt calculate pentru fiecare "dungă" şi fiecare set de "dungi" este transformat într-o histogramă cu 3 benzi. Având astfel patru momente în patru direcţii transformate în histograme cu trei benzi, rezultă un vector de trăsături care conţine 4x4x3=48 elemente.[9]

"Primele 4 momente" sunt utilizate, la fel ca şi histogramele multi-scală în cadrul metodelor I, II şi III de extragere a trăsăturilor din imaginea originală.

2.9 Algoritmul KNN

KNN este abrevierea din limba engleză pentru K-Nearest Neighbor (cei mai apropiaţi k vecini), fiind un algoritm de învaţare supervizat utilizat în special în problemele de clasificare. Scopul acestui algoritm este acela de a clasifica un nou obiect pe baza atributelor sale în funcţie de setul cunoscut de date de antrenare. Prin această tehnică folosită în special pentru clasificarea datelor în mai multe clase, un nou obiect este clasificat pe baza majorităţii voturilor vecinilor săi, fiindu-i atribuită clasa cea mai frecvent întâlnită printre cei “k” cei mai apropiaţi vecini. Acei “k” cei mai apropiaţi vecini se aleg pe baza distanţei minime dintre obiect şi toate celelalte obiecte din setul de antrenare (setul de date cunoscut).Fiecare obiect este reprezentat în setul de date printr-un vector de trăsături, care în cazul imaginilor poate să conţină caracteristici de formă, de textură sau de culoare.

Există mai multe tipuri de metrici folosite în cadrul algoritmului KNN pentru calculul distanţei minime dintre “noul vector” şi “vectorii” din setul de antrenare:

- distanţa euclidiană- distanţa euclidiană standardizată- distanţa city block (Manhattan)- distanţa cosinus- distanţa coeficientului de corelaţie (distanţa Pearson r)- distanţa hamming- distanţa Maholonobis- distanţa Minkowski- etc

Cea mai frecventă distanţă utilizată în cadrul acestui algoritm este distanţa euclidiană.Fiind dată o matrice X de dimensiune [mxn], care conţine "m" vectori linie (vectorii de trăsături de dimensiune [1xn]) x1,x2,…,xm, unde xk=(x1

k , x2k,…, xn

k), putem defini metricile (distanţele) dintre două obiecte (doi vectori) oarecare xr şi xs (r,s=1m), după cum sunt ilustrate şi în [22], astfel:

- distanţa euclidiană:

12

drs=√ ( xr−x s )(xr−xs)' = √∑

i=1

n

(x ir−x i

s)2 (24)

- distanţa euclidiană standardizată:

dsrs=√ ( xr−x s ) D−1( xr−xs)',

unde D este matricea diagonală, ce are ca elemente dispersia vectorului X i=(x i1 , …, x i

m ), notată d i2,

rezultând:

dsrs=√∑i=1

n

( (xir−x i

s)d i

)2

(25)

- distanţa city block (Manhattan)

dcrs=∑i=1

n

|xir−x i

s| (26)

- distanţa cosinus

dcosrs=(1−xr xs

'

(xr xr' )

12 (xs xs

' )12 ) (27)

- distanţa coeficientului de corelaţie (distanţa Pearson r)

rrs =1−(xr−xr)(xs− xs)

'

√(xr−xr)( xr−xr)'√(xs−xs)(x s−xs)

' , unde xr=∑i=1

n

x ir (28)

- etc, pentru mai multe tipuri de metrici a se consulta [22].

Pentru a întelege şi mai bine funcţionarea algoritmul KNN pe un exemplu numeric a se consulta consulta [24].

2.9.1 Avantajele algoritmului KNN

Unul dintre avantajele sale este uşurinţa implementării, fiind unul dintre algoritmii de clasificare cei mai uşor de înţeles.

O altă calitate a acestei tehnici este eficacitatea sa, în cazul în care, setul de date de antrenare este afectat de zgomot (în special în cazul în care se foloseste ca metrică inversul pătratului distanţei ponderate). Obţinerea distanţei ponderate se face prin ierarhizarea fiecărei trăsături în funcţie de scopul propus. Astfel distanţa euclidiană ponderată va avea urmatoarea expresie:

dw rs= √∑i=1

n

w i(xir−x i

s)2 (29),

13

unde ∑i=1

n

wi=1, iar w i este ponderea atributului (caracteristicii) i [23] .

A nu se confunda ponderarea atributelor cu ponderarea distanţelor. O metodă foarte întâlnită de ierarhizare a distanţelor, este aceea de a-i da fiecarui vecin o

pondere de 1/d , unde d este distanţa pâna la vecin. Astfel vecini mai apropiaţi vor avea o contribuţie mai mare la clasificarea unui obiect. Studiile au aratat că ponderarea distanţelor nu îmbunătăţeşte performanţele algoritmului KNN.

2.9.2 Dezavantajele algoritmului KNN

La aplicarea algoritmului KNN în practică ne lovim de următoarele probleme:a)"Ce metrică utilizăm pentru performanţe cât mai bune?"b)"Care este valoarea optimă pentru k?"c)"Trebuie să folosim toate atributele sau numai anumite atribute ale obiectelor?"

Toate aceste probleme au ca efect creşterea timpului de clasificare.Timpul de clasificare depinde în special de numărul de obiecte din setul de date. Pentru seturile de date cu un număr foarte mare de obiecte, în etapa de preclasificare este necesară o reducere a numărului de atribute pentru fiecare obiect. Acest lucru se realizează prin alegerea unor puncte cheie care să diferenţieze între ele instanţele setului de antrenare cât mai bine.

Numărul optim de vecini se obţine prin testarea algoritmului de mai multe ori, modificând numărul acestora.

Costul de calcul este destul de mare, deoarece trebuie să calculăm distanţa dintre noua instanţă şi fiecare instanţă din setul de antrenare. Acest cost poate fi redus prin utilizarea metodei "K-D tree".[25]

Pentru a vedea eficacitatea metodelor de extragere a caracteristicilor, în această lucrare s-a folosit clasificatorul KNN. A fost ales acest algoritm datorită simplităţii lui, a performanţelor bune de clasificare, atât în ceea ce priveşte acurateţea cât şi timpul de clasificare.

2.10 Fişiere MEX (MEX-files)

MEX este abrevierea din limba engleză pentru MATLAB Executable (Executabile Matlab). Fişierele MEX sunt subrutine dinamice realizate în mediile de programare C, C++ sau Fortran, coduri sursă care compilate pot fi rulate din Matlab în acelaşi mod cum sunt rulate şi fişierele M (M- files) sau orice altă funcţie deja implementată în Matlab. Funcţiile externe de interfaţare realizează transferul de date între MEX- files şi Matlab, oferind totodată şi posibilitatea de a chema funcţii Matlab din programele C, C++ sau Fortran.

Principalele motive de a creea în loc de un M-file un MEX- file sunt următoarele:- abilitatea de a apela o gamă largă de rutine C, C++ sau Fortran deja existente direct din Matlab fără a fi nevoiţi să le rescriem ca un M -file.- viteza de execuţie; putem rescrie programele care folosesc de exemplu bucle FOR ca şi MEX- files pentru eficienţă. Pentru mai multe detalii legate de realizarea MEX- files a se consulta [26].

În această lucrare MEX- files sunt folosite pentru calculul polinoamelor Zernike ale unei imagini, precum şi pentru implementarea clasificatorului KNN. Aceste MEX- files sunt realizate de dezvoltatorii clasificatorului WND-CHARM, respectiv de Roger Jang şi pot fi descărcate gratuit de pe site-urile:http://www.openmicroscopy.org, respectiv http://mirlab.org/jang/matlab/toolbox/dcpr/.

3. Implementarea soluţiei adoptate

14

Scopul lucrării de faţă este acela de a testa diferite caracteristici care să codeze cel mai bine imaginile din baza de date. Pentru a verifica eficienţa metodelor de extragere a trăsăturilor s-a folosit clasificatorul KNN.

În general, un sistem de recunoaştere al obiectelor trebuie să: 1- să extragă atributele care grupeză imaginile într-o anumită clasă şi diferenţiază imaginile din clase diferite2- să clasifice aceste atribute 3- să elimine alarmele false - de aceea avem clasa garbage 4- să identifice clasa imaginii pe baza acestor atribute5- în cazul detecţiei obstacolelor, există posibilitatea apariţiei unui modul de „tracking” sau urmărire care să realizeze urmărirea obiectelor de-a lungul scenei rutiere până în momentul în care se pierd în afara ei şi nu mai reprezintă nici un pericol.

În această lucrare s-a presupus că obiectele sunt deja segmentate (detectate), baza de date fiind formată din imagini care încadrează doar obiectele şi nu din scene întregi care să includă mai multe obiecte. Astfel, în această lucrare este tratat numai pasul de extragere al trăsăturilor pentru modulul de clasificare.

La început s-a încercat extragerea caracteristicilor din imagini doar pe baza transformatei Wavelet, ceea ce implică redimensionarea imaginilor la aceeaşi scală pentru a obţine acelaşi număr de coeficienţi. Imaginile din baza de date au diferite dimensiuni (unele ilustrează obiecte mai apropiate având implicit dimensiuni mai mari- maxim 434x768 pixeli, altele obiecte mai depărtate, având dimensiuni mai mici- minim 89x69 pixeli), iar pentru clasificare este necesar obţinerea unui număr fix de caracteristici pentru fiecare imagine. Folosirea caracteristicilor wavelet în multiple surse bibliografice ne-au făcut să concluzionăm că performanţele scăzute obţinute se datorează redimensionării imaginilor şi nu transformatei Wavelet. Din acest motiv s-a renunţat la redimensionare şi s-a încercat găsirea unor metode de extragere a trăsăturilor care prin aplicarea lor asupra imaginilor să returneze un număr fix de coeficienţi indiferent de dimensiunea imaginii.

Sistemele de clasificare folosesc la intrare vectori de caracteristici care definesc obiectele din imagini. Aceste caracteristici reprezintă şablonul (pattern-ul) obiectului, iar sabloanele obiectelor care aparţin mai multor clase vor fi esenţiale pentru procesul de învăţare şi testare al sistemului. Pentru obţinerea caracteristicilor s-au folosit o serie de transformate, combinaţii de transformate şi de metode de extragere printre care se pot enumera:- transformata Wavelet- transformata FFT- transformata Radon- caracteristicile Tamura- histogramele multi-scală- filtre orientate în patru direcţii pentru obţinerea "primelor 4 momente"- polinoamele Zernike.

În pasul de clasificare, algoritmul de evaluare se bazează pe calculul de distanţe între vectorii de caracteristici corespunzători obiectelor. Pentru a detecta şi a recunoaşte caracteristicile altor obiecte noi, sistemul trebuie învăţat apriori cu aceste şabloane prin intermediul caracteristicilor extrase. Sistemul odată învăţat, poate fi folosit doar pentru testare, iar dacă se doreşte adăugarea de noi instanţe în setul de antrenare, se va mai trece încă o dată prin etapa de învăţare. Metodele de extragere enumerate mai sus au fost studiate pentru evaluarea performanţelor ce se pot obţine cu ajutorul lor, sau chiar prin diferite combinaţii ale lor. Caracteristicile extrase au fost utilizate de clasificator (KNN) pentru a se realiza recunoaşterea automată a obiectelor.

3.1 Baza de imagini

15

Baza de date este formată din imaginile unor obstacole ce pot fi întâlnite de conducătorul unei maşini pe durata deplasării. Există posibilitatea ca obstacolele întâlnite să nu fie observate la timp sau să distragă atenţia conducătorului. Din acest motiv au fost dezvoltate sisteme de detecţie şi recunoaştere a obstacolelor care să atenţioneze conducătorul asupra pericolelor reprezentate de acestea.

În mediul urban obstacolele ce pot fi întâlnite sunt reprezentate de alte maşini sau de pietoni. Faţă de mediul urban, în mediul rural se pot întâlni şi alte obstacole cum sunt animalele. De aceea baza de imagini va fi formată din clasele maşini, pietoni şi animale.

Baza de imagini este construită din 800 de imagini color, împărţite în patru clase după cum urmează:- 200 de imagini cu maşini- 200 de imagini cu pietoni- 200 de imagini cu animale (câini, pisici, vaci, oi, cai)- 200 de imagini alcătuind clasa garbage.

După cum se poate observa în figura 3.1 imaginile au fost selectate manual şi au fost extrase doar obiectele de interes din acestea. Apoi imaginile au fost transformate în imagini pe nivele de gri.

Un sistem unitar presupune existenţa detecţiei şi recunoaşterii (clasificării) robuste. Detecţia şi clasificarea bazată doar pe imaginile din domeniul vizibil în general nu oferă performanţe prea bune în orice condiţii, de aceea sistemele actuale folosesc şi alţi senzori pentru realizarea detecţiei şi recunoaşterii obstacolelor. Cum în lucrarea de faţă recunoaştere automată a obstacolelor se realizează numai pe baza imaginilor din domeniul vizibil ne aşteptăm ca sitemul de clasificare să dea rateuri. De aceea a fost introdusă şi clasa de imagini garbage.

După cum se poate observa în figura 3.1, imaginile care alcătuiesc clasa garbage au fost obţinute din fundalul imaginilor celorlalte clase. Această clasă este utilă la detectarea alarmelor false.

În figura de mai jos sunt ilustrate diferite imagini din fiecare clasă:

Maşini:

Pietoni:

Animale:

16

Garbage:

Figura 3.1 Imagini din baza de date

După ce caracteristicile au fost extrase, ele au fost introduse în clasificator pentru a

realiza clasificarea imaginilor în cele patru clasele. În general pentru crearea unei baze de imagini care să fie cât mai bună (din punct de

vedere al rezultatelor de clasificare), sunt respectate următoarele principii:- toate imaginile să fie realizate cu aceleaşi procedee (cu acelaşi aparat de fotografiat sau cameră de filmat)- parametrii mijloacelor de captare să fie identici pentru toate imaginile (rezoluţie, contrast, dimensiune, etc)- să aibe un număr de imagini care să permită obţinerea unor rezultate de clasificare satisfăcătoare.

Deoarece nu a mai fost creată o bază de imagini ca şi cea utilizată în lucrarea de faţă şi realizarea unei astfel de baze de imagini necesită foarte mult timp, au fost folosite imagini care fac obiectul altor baze de date disponibile gratuit pe site-ul: http://pascallin.ecs.soton.ac.uk/challenges/VOC/databases.html.

Bine înţeles că baza de imagini formată, nu este la fel de bună ca cea care respectă principiile enumerate mai sus, deoarece procedeul de înregistrare, rezoluţia, contrastul şi dimensiunile imaginilor diferă de la o bază de imagini la alta.

3.2 Metoda de extragere a caracteristicilor

După crearea bazei de imagini, s-a realizat extragerea caracteristicilor din imagini prin intermediul diferitor transformate de imagini (transformata Wavelet, transformata FFT, trans-formata Radon) şi altor moduri de extragere ("primele 4 momente", histograme multiscalare, caracteristicile Tamura - granularitatea, contrastul şi direcţionalitatea, şi polinoamele Zernike).

După cum se poate observa în figura 3.2, aceste transformate şi celelalte procedee de extragere a caracteristicilor enumerate anterior, sunt distribuite în patru metode de extragere a caracteristicilor, astfel:

Metoda I

Metoda II

17

Metoda III

Metoda IV

Figura 3.2 Schema bloc a metodelor de extragere a trăsăturilor

Metodele de extragere a trăsăturilor, după cum se poate vedea în figura 3.2, au fost denumite metoda I, metoda II, metoda III şi metoda IV pentru ca referirea la acestea să se realizeze mult mai uşor.

Privind figura 3.2 se poate observa că metoda I şi metoda II diferă ca şi structură numai prin prizma imaginilor pe care sunt aplicate (metoda I se aplică pe imaginea obţinută în urma transformatei Wavelet a imaginii pe nivele de gri, iar metoda II pe cea obţinută în urma transformatei Wavelet a transformatei FFT). Numărul de trăsături obţinute prin aplicarea acestor două metode este acelaşi indiferent de imaginea pe care sunt aplicate (imagine pe nivele de gri, cea rezultată în urma transformatei Wavelet sau cea rezultată în urma transformatei Wavelet a transformatei FFT) şi indiferent de dimensiunea acesteia, doarece cele trei blocuri "primele 4 momente", histograme multi-scală şi caracteristicile Tamura contribuie cu un număr constant de trăsături la formarea vectorului de caracteristici (48, 24, respectiv 6).

Astfel, asupra transformatei Wavelet a imaginii, cât şi asupra transformatei Wavelet a trasnformatei FFT, se vor aplica următoarele funcţii de compresie a numărului de coefienţi:a) Histogramele multi-scală - funcţie care transformă imaginea de intrare în patru tipuri de histograme, cu 3, 5, 7 şi 9 benzi, rezultând astfel 24 de valori. Aceste valori sunt normalizate cu maximul lor.b) "Primele 4 momente" - funcţie care returnează un număr de 48 de coeficienţi, prin parcurgerea imaginii:- pe diagonală (atât din strânga jos pâna în dreapta sus, cât şi din dreapta jos până în stânga sus) cu un pas care depinde de valoarea rotujită a împărţirii dimensiunii pe vericală a imaginii la zece (round(dim_verticală/10)). La fiecare pas se calculează valoarea mediei, deviaţiei standard, skewness şi kurtosis a pixelilor parcuşi. Coloanele matricei astfel obţinută (care are stocate pe fiecare linie cele patru valori menţionate) sunt transformate în histograme cu 3 benzi, rezultând un număr de 4x3=12 trăsături pentru fiecare imagine.- pe orizontală şi pe verticală, cu deosebirea că faţă de parcurgerea pe diagonală cea realizată pe verticală se va face cu un pas care depinde de dimensiunea orizontală a imaginii, iar cea

18

verticală se va face cu un pas care depinde de dimensiunea orizontală a imaginii. În rest se procedează la fel ca şi la parcurgerea pe diagonală.

Aşadar, pentru cele patru parcurgeri (două pe diagonală, una pe verticală şi una pe orizontală) se obţin un număr de [4 parcurgeri]x[4 coloane]x[3 benzi ale histogramelor]=48 trăsături pentru orice imagine asupra căreia s-a aplicat această metodă de reducere a caracteristicilor.c) Trăsăturile Tamura se compun din directionalitatea imaginii, contrastul, granularitatea şi o histogramă a granulitaţii cu 3 benzi, rezultând 6 caracteristici pentru fiecare imagine.

Până acum au fost trecute în revistă primele două metode de reducere a atributelor unei imagini (metoda I şi metoda II), iar în continuare vor fi abordate celelate două metode - metoda III şi metoda IV.

În cadrul metodei III de reducere a atributelor, blocurile: "primele 4 momente", histograme multi-scală, caracteristicile Tamura, au aceeaşi funcţionare ca şi în cazul blocurilor similare din metoda I şi metoda II, cu deosebirea că acestea acţionează asupra imaginii originale (imagine pe nivele de gri). Acestor blocuri i se adaugă şi transformata Radon.

Pentru a realiza transformata Radon s-a utilizat funcţia deja implementată în Matlab:R = radon(I, theta) care returnează transformata Radon R a intensitaţii imaginii I pentru un unghi de theta grade [23].

Au fost calculate transformatele Radon pentru patru valori ale lui theta - 00, 450, 900 şi 1350. Fiecare coloană a lui R va conţine transformata Radon pentru fiecare unghi din theta. Apoi coloanele matricei R sunt transformate în patru histograme a câte trei benzi fiecare. Astfel, transformata Radon participă cu un număr total de 4x3=12 trăsături la formarea vectorului de caracteristici.

Metoda IV de extragere a trăsăturilor constă în descompunerea polinomială Zernike a imaginilor pe nivele de gri. Rezultatele obţinute în urma aplicării polinoamelor Zernike asupra imaginii sunt valori complexe, şi de aceea descriptorii imaginii vor fi modulul acestor valori (valoarea absolută).

La aceste metode s-a ajuns pornind de la cele descrise în [9] pentru formarea vectorului de trăsături din cadrul clasificatorului WND-CHARM.

3.2.1 Metoda de extragere a caracteristicilor din WND-CHARM

Metoda propusă pentru formarea vectorului de trăsături al clasificatorului WND-CHARM este ilustrată în următoarea figură:

19

Figura 3.3 Schema de formare a vectorului de trăsături din cadrul WND-CHARM [9]

După cum se poate observa în figura 3.3 pentru formarea vectorului de trăsături s-au utilizat diferite transformate ale imaginilor (transformata Wavelet, transformata Chebyshev şi transformata FFT), precum şi combinaţii ale acestor transformate (transformata Wavelet a transformatei FFT şi transformata Chebyshev a transformatei FFT). Apoi din rezultatele obţinute în urma acestor transformate, au fost extrase diferite trăsături, care sunt grupate în funcţie de tipul lor (caracteristici de mare contrast, de descompunere polinomială, de statistică şi textură) în patru grupe astfel:

Figura 3.4 Grupele de caracteristici din WND-CHARM [9]

În figura 3.4 este descrisă componenţa fiecărei grupe de caracteristici. Astfel, grupa A cuprinde următoarele caracteristici de contrast înalt (de formă): - statisticile muchilor care sunt calculate pe gradientul imaginii originale.Prin extragerea acestor statistici se obţin 28 de trăsături.- coeficienţii Gabor se obţin prin utilizarea wavelet-urilor Gabor [9], obţinându-se un număr de 7 coeficienţi pentru fiecare imagine.- statisticile obiectelor sunt calculate pe imaginea binarizată prin intermediul pragului Otsu [9]. În total statisticile obiectelor cuprind 34 de caracteristici.

După cum se poate observa în figura 3.3 caracteristicile din grupa A sunt extrase numai din imaginea originală, contribuind astfel cu un număr de 28+7+34=69 caracteristici la formarea vectorului de trăsături.

Grupa B reprezentată de caracteristicile de descompunere polinomială (de geometrie), are în componenţă următoarele trăsături:- statisticile Chebyshev- Fourier sunt extrase prin aplicarea asupra imaginii a transformatei Chebyshev- Fourier. Vectorul obţinut prin intermediul acestei transformate va fi transformat într-o histogramă cu 32 de benzi. Astfel se vor obţine un număr de 32 de caracteristici Chebyshev- Fourier.- statisticile Chebyshev sunt obţinute prin transformarea coeficienţilor rezultaţi în urma transformării Chebyshev a imaginii într-o histogramă cu 32 de benzi.- polinoamele Zernike - prin descompunerea polinomială Zernike se obţin 72 de coeficienţi complecşi, dar ca descriptori ai imaginii se folosesc valorile absolute ale acestora.

După cum se poate observa în figura 3.3 caracteristicile din grupa B sunt extrase din imaginea originală şi imaginea rezultată în urma transformatei FFT a imaginii originale, contribuind astfel cu un număr de 2x(32+32+72)=272 caracteristici la formarea vectorului de trăsături.

Grupa C, după cum se poate observa în figura 3.4 este compusă din următoarele caracteristici de statistică a pixelilor şi de textură: - primele 4 momente sunt reprezentate de media, deviaţia standard, skewness şi kurtosis imaginii.

20

Fiecare din cele patru caracteristici enumerate este formată dintr-o histogramă cu 12 benzi, rezultând 48 de trăsături pentru fiecare imagine. - trăsăturile Haralick sunt calculate cu ajutorul matricelor concurente ale imaginilor. Aceste trăsături cuprind un număr de 28 valori. - histograme multi-scală sunt obţinute prin transformarea imaginii în patru tipuri de histograme, cu 3, 5, 7 şi 9 benzi, rezultând astfel 24 de valori. - caracteristicile Tamura se compun din direcţionalitatea imaginii, contrastul, granularitatea şi o histogramă a granularităţii cu 3 benzi. Aceste trăsături contribuie cu un număr de 6 caracteristici la formarea vectorului de trăsături.

După cum se poate observa în figura 3.3 caracteristicile din grupa C sunt extrase din transformata Wavelet a imaginii originale şi transformata Wavelet a transformatei FFT a imaginii originale, contribuind astfel cu un număr de 2x(48+28+24+6)=212 caracteristici la formarea vectorului de trăsături.

Grupa D este formată din statisticile pixelilor şi caracteristicile de textură ce fac parte din grupa C la care se adaugă şi caracteristicile Radon a imaginii originale. Prin aplicarea transformatei Radon asupra unei imagini se obţine un număr total de 4x3=12 trăsături.

După cum se poate observa în figura 3.3 caracteristicile din grupa D sunt extrase din imaginea originală, transformata FFT a imaginii originale, transformata Chebyshev (a imaginii originale şi a transformatei FFT a imaginii originale), contribuind astfel cu un număr de 4x(48+28+24 +6+12)=472 caracteristici la formarea vectorului de trăsături.

Pentru mai multe detalii despre modul în care au fost calculate caracteristicile din grupele A, B, C şi D a se consulta [9].

3.2.2 Metoda de extragere a caracteristicilor adoptată

În această lucrare formarea vectorului de caracteristici s-a realizat având ca referinţă figura 3.3. Pentru obţinerea unor timpi de extragere a trăsăturilor şi de clasificare mai buni este necesar a se utiliza un vector de trăsături cu o dimensiune cât mai mică. Astfel, pentru calculul vectorului de caracteristici, în lucrarea de faţă se vor utiliza un număr mai redus de trăsături.

Pentru reducerea numărului de trăsături, dar şi din cauza numărului foarte mare de posibilităţi de formare a vectorului de trăsături (disponibile în figura 3.3), în această lucrare s-a procedat astfel: - s-a plecat de la formarea vectorului de trăsături prin împărţirea figurii 3.3 în mai nouă metode de extragere caracteristicilor (primele nouă linii ale tabelului 3.1) şi testarea fiecărei metode în parte.

- s-au realizat combinaţii ale celor nouă metode de extragere (după cum se poate observa în tabelul 3.1) până când s-a ajuns la o performanţă de clasificare satisfăcătoare.

- încă de la început s-a renunţat din grupa A la coeficienţii Gabor (datorită numărului mic de trăsături şi timpului de obţinere mai ridicat comparativ cu celelalte caracteristici ale grupei), din grupa B la statisticile Chebyshev-Fourier (deoarece utilizează pentru calcul o mare parte din memorie şi timpul de obţinere este foarte mare), din grupa C la trăsăturile Haralick (datorită timpului de obţinere foarte mare şi modului complicat de calcul).

Nr.crt. Metoda de extragere a trăsăturilor

Acurateţe KNN Weka [%]

Acurateţe KNN Matlab

[%]k k

1 3 5 1 3 51. imagine → transformata Wavelet → grupa C 70.6 68 70 70 62 68.32. imagine → transformata Chebyshev → grupa D 66.1 66.5 62.7 65.7 64.4 63.73. imagine → transformata FFT → transformata 68 67.5 75.5 66.3 65.6 74

21

Wavelt → grupa C4. imagine → transformata FFT → transformata

Chebyshev → grupa D64.8 65.4 65.3 63.2 61.3 63.2

5. imagine → transformata FFT → grupa B 68.9 67.2 65.8 68 67.3 65.86. imagine → transformata FFT → grupa D 59 53.3 60 56.9 51.9 58.57. imagine → grupa A 62.7 62.7 60.4 63 64.3 61.38. imagine → grupa B 81.5 80.7 83.5 80.6 81.9 82.89. imagine → grupa D 82.5 83.5 82.5 85 86.2 87

10.imagine → transformata Wavelet → grupa C +imagine → grupa A 70 71 73 69.3 70.6 70

11.imagine → transformata Wavelet → grupa C +imagine → grupa A + imagine → transformata FFT → transformata Wavelet→ grupa C

70.6 73.7 72 69.3 71.2 70

12.imagine → transformata Wavelet → grupa C +imagine → grupa A + imagine → grupa B 70 71 73 69.3 70.6 70

13.imagine → transformata Wavelet → grupa C+ imagine → transformata FFT → grupa B 81 80.5 79.8 81.8 81.2 80.6

14.imagine → transformata Wavelet → grupa C +statisticile Radon extrase din imaginea originală

86.8 86.8 86.2 86.2 87.5 87.5

15.imagine → transformata Wavelet → grupa C + statisticile Chebyshev extrase din imaginea originală

73.7 71.2 73 70.6 70.6 70.6

16.

imagine → transformata Wavelet → grupa C + statisticile Chebyshev extrase din imaginea originală + statisticile Radon extrase din imaginea originală

82.5 85 85 82.5 82.5 80

Nr.crt. Metoda de extragere a trăsăturilor

Acurateţe KNN Weka [%]

Acurateţe KNN Matlab

[%]k k

1 3 5 1 3 517. imagine → transformata Wavelet → grupa C +

imagine → grupa D85.6 85 82.5 87 88.7 88

18.imagine → transformata Wavelet → grupa C +imagine → grupa D + imagine → grupa B 87.5 87.8 85 90 86.9 87.5

19.imagine → transformata Wavelet → grupa C +imagine → grupa D+ imagine → grupa B+ imagine → transformata FFT → transformata Wavelet → grupa C

87.9 87.5 85.6 91.3 86.3 86.3

Tabel 3.1 Metode de extragere a trăsăturilor analizate

În tabelul 3.1 sunt ilustrate valorile acurateţii de clasificare (pentru metodele specificate de extreagere a trăsăturilor) obţinute atât în Matlab cât şi în Weka, prin intermediul clasificatorului KNN, respectiv IBk pentru un număr de vecini k= 1, 3 sau 5.

După cum se poate observa în tabelul 3.1, metoda de extracţie a trăsăturilor care oferă cea mai mare acurateţe este descrisă în ultima secţiune a acestuia.

22

Nu s-a mai continuat testarea altor combinaţii de metode de extragere a trăsăturilor deoarece s-a obţinut o acurateţe de clasificare satisfăcătoare şi pentru ca timpul de extragere a trăsăturilor pentru toate imaginile din baza de date să nu mai crească (pentru că este şi aşa unul foarte ridicat- 3 ore şi 12 minute).

Asfel, s-a ajuns la următoarea schemă de formare a vectorului de caracteristici, care este utilizat mai departe în această lucrare:

Figura 3.5 Schema de formare a vectorului de trăsături

Figura 3.5 reprezintă schema de formare a vectorului de caracteristici pentru care s-a obţinut o acurateţe de clasificare satisfăcătoare prin intermediul clasificatorului IBk din Weka şi clasificatorului KNN implemantat în Matlab.

Metodele de extragere a trăsăturilor ilustrate în figura 3.5 sunt descrise mai amănunţit în în figura 3.2 şi în secţiunea 3.2 a lucrării de faţă.

După cum se observă în figura 3.5 vectorul de caracteristici al fiecărei imagini va fi format din 318 trăsături. Pentru întreaga bază de imagini vectorul de trăsături va fi format din 800 de imagini x 318 trăsături.

3.2.3 Evaluarea trăsăturilor în Weka

Weka este un sistem foarte puternic cu ajutorul căruia se poate realiza numai clasificarea obiectelor (nu şi extragerea caracteristicilor).Utilitarul poate fi descărcat gratuit de pe site-ul: http://www.cs.waikato.ac.nz/ml/weka/. Acesta a fost utilizat pentru a aplica o metodă de învăţare aupra vectorului de caracteristici şi pentru a analiza rezultatele obţinute. Înainte de aplicarea oricărui algoritm de clasificare asupra datelor, acestea trebuie convertite în fisiere ARFF ("Attribute-Relation File Format").

Structura fişierului ARFF trebuie să respecte următoarea formă:

23

Figura 3.6 Structura fişierului ARFF la modul general

Figura 3.6 ilustreză modul de formare al unui fişier ARFF, în vederea antrenării şi testării unui clasificator ales din Weka cu trăsăturile extrase din imaginile cuprinse în baza de date.

Astfel, pentru vectorul de caracteristici format pe baza schemei din figura 3.5, structura fişierului ARFF va fi următoarea:

Figura 3.7 Structura fisierului ARFF utilizat în acestă lucrareÎn figura 3.7 este prezentată schema de formare a fişierului ARFF adaptată la această

lucrare. Aşadar, fiecare atribut trebuie descris în header-ul fişierului ARFF, fişierul conţinind

informaţii atât despre tipul fiecărui atribut, precum şi despre clasa din care face parte respectivul obiect.

Clasa fiecărui obiect trebuie să fie cunoscută, pentru ca la testare să se poată compara clasa prezisă de clasificator cu clasa reală a obiectului respectiv. Dupa antrenarea (învăţarea) datelor se obţine o matrice de confuzie ("confusion matrix") având dimensiunea [număr_clase x număr_clase], în cazul nostru 4x4, care arată numărul instanţelor atribuite fiecărei clase de obiecte. Dacă toate instanţele au fost clasificate corect atunci doar elementele diagonalei principale ale matricei de confuzie sunt diferite de zero. Un exemplu de matrice de confuzie obţinute în Weka este ilustrat în figura 3.8.

==Matricea de confuzie==

M P A G160 0 0 0 |M=1

0160 0 0 | P=2

==Matricea de confuzie==

M P A G40 0 0 0 |M=10 36 3 1 | P=21 2 34 3 |A=3

24

0 0 160 0 |A=3

0 0 0160 |G=4

(a)

3 0 9 28 |G=4

(b)

Figura 3.8 Matricele de confuzie pentru învăţare, respectiv testare

Notaţiile realizate în figura 3.8 au următoarele seminificaţii: M - clasa maşini, P - clasa pietoni, A - clasa animale şi G -clasa garbage.

În figura 3.8 se poate observa că la învăţare toate obiectele au fost atribuite corect claselor din care fac parte (figura 3.8 a). În etapa de testare (figura 3.8 b):- toate obiectele din clasa maşini (prima linie a matricei din figura 3.8 b) au fost clasificate corect

- din clasa pietoni (a doua linie a matricei din figura 3.8 b) 36 de imagini au fost clasificate corect, 3 au fost clasificate ca făcând parte din clasa animale şi 1 din clasa garbage.

- din clasa animale 34 de imagini au fost clasificate corect (a treia linie a matricei din figura 3.8 b), 1 a fost clasificată ca fiind din clasa maşini, 2 au fost atribuite clasei pietoni şi 3 clasei garbage

- din clasa garbage (ultima linie a matricei din figura 3.8 b) 28 de imagini au fost clasificate corect, 3 au fost clasificate ca aparţinând clasei maşini şi 9 clasei animale.Figura 3.8 prezintă matricele de confuzie pentru învâţare (cu 80% din imaginile din baza de date), respectiv testare (cu 20% din imaginile din baza de date) obţinute în Weka cu clasificatorul IBk. Numărul de vecini al clasificatorului IBk este egal cu unu, iar pentru formarea vectorului de trăsături s-a utilizat schema prezentată în figura 3.5.

Pentru învăţare şi testare vectorul de caracteristici al tuturor imaginilor din baza de date a fost împărţit manual în 80% instanţe pentru învăţare şi 20% pentru testare, astfel încât să avem un număr de 160 de imagini din fiecare clasă pentru antrenare (din întreaga baza de date un total de 640 de imagini) şi 20% din fiecare clasă pentru testare (din întreaga bază de date un total de 160 de imagini).

Programul Weka pune la dispoziţie un număr mare de algoritmi de învăţare şi testare. Deoarece în lucrarea de faţă s-a pus accentul pe extragerea trăsăturilor şi nu pe analiza performanţelor diferiţilor clasificatori, pentru a evalua calitatea trăsăturilor extrase din imagini a fost utilizat numai clasificatorul IBk.

3.3.4 Evaluarea trăsăturilor în Matlab

Deoarece apelarea din Matlab a utilitarului Weka este foarte complicată şi datorită faptului că s-a dorit dezvoltarea unei aplicaţii de sine stătătoare în Matlab, s-a ales implementarea în Matlab a unui algoritm de clasificare. Datorită simplităţii şi uşurinţei de implementare, pentru evaluarea trăsăturilor în Matlab s-a ales utilizarea clasificatorului KNN.

În această lucrare au fost utilizate pentru compararea performanţelor de clasificare două versiuni ale clasificatorului KNN:

KNNC (KNN Classify) care este un clasificator implementat cu ajutorul funcţiei deja existente în Matlab:

Class = knnclassify(Sample, Training, Group, k, distance) [23].

Funcţia knnclassify returnează vectorul Class, care conţine rezultatul clasificării

25

imaginilor din vectorul Sample în funcţie de imaginile din vectorul Training.Această funcţie are ca şi parametrii:

- vectorul Sample conţine pe fiecare linie trăsăturile extrase din imaginile de test - vectorul Training conţine pe fiecare linie trăsăturile extrase din imaginile de antrenare, fiind folosit la clasificarea obiectelor din vectorul Sample. Numărul de coloane a celor doi vectori Sample şi Training trebuie să fie egal.- vectorul Group conţine clasele imaginilor din setul de antrenare- k este numărul de vecini utilizat în clasificare - distance este metrica utilizată în clasificare

KNNR (KNN Rule) este implementat de Roger Jang şi poate fi descărcat gratuit de pe site-ul: http://mirlab.org/jang/matlab/toolbox/dcpr/.Cu acest clasificator se obţine exact aceeaşi acurateţe, dar un timp de clasificare mult mai

bun. Acest lucru se datorează utilizării MEX-files, care au rolul de a reduce timpul necesar în mod normal Matlab-ului să realizeze operaţiile dorite.

În interfaţa grafică va fi utilizat numai clasificatorul KNNR datorită performanţelor de clasificare superioare (în ceea ce priveşte timpul de clasificare).

Astfel utilitarul Weka este folosit pe lângă stabilirea metodei de extragere a trăsăturilor şi la verificarea implementării în Matlab a celor două clasificatoare KNN.

3.3 Determinarea parametrilor transformatei Wavelet

În această lucrare s-a utilizat transformata Wavelet discretă pentru semnale bidimensionale. În Matlab această transformată are următoarea sintaxă:

[cA,cH,cV,cD] = dwt2(X,'wname') [23]

Prin această transformată se calculează matricea coeficienţilor aproximaţi cA şi matricele coeficienţilor detaliaţi cH, cV şi cD (pe orizontală, verticală şi respectiv pe diagonală) prin descompunerea wavelet a matricei de intrare X (care poate fi reprezentată de o imagine).

Transformata Wavelet are ca parametru numele familiei wavelet utilizat în descompu-nere. Tot un parametru al transformatei Wavelet poate fi considerat şi nivelul de descompunere wavelet.

Descompunerea wavelet se poate realiza pe mai multe nivele astfel:- mai întâi se realizează transformata Wavelet a imaginii prin metoda descrisă mai sus (utilizată pentru obţinerea primului nivel de descompunere wavelet)- pentru obţinerea celui de-al doilea nivel al descompunerii se va aplica transformata Wavelet pe una din matricele coeficienţilor (cA, cH, cV sau cD) sau pe o combinaţie a acestor matrice. - se continuă aplicarea transformatei Wavelet pe noile matrice de coeficienţi până când se atinge nivelul de descompunere dorit.

Pentru determinarea parametrilor transformatei Wavelet s-a realizat următorul experiment:- pentru nivelul de descompunere au fost alese patru valori 3, 4, 5 şi 6 (nivelele 1 şi 2 nu oferă o compresie suficientă a coeficienţilor imaginii). Aşadar sunt patru valori ale nivelului de descompunere. În lucrarea de faţă pentru obţinerea nivelelor de descompunere wavelet superioare au fost utilizaţi numai coeficienţii aproximaţi cA.- pentru funcţiile mamă ale descompunerii wavelet s-au folosit funcţiile deja implementate în Matlab, precum: Daubechies, Coiflet, Symlet, biortogonale şi invers biortogonale (reverse biortogonal) .

Numele familiei de funcţii wavelet Daubechies se scrie dbN, unde N este ordinul, iar db este "prenumele" funcţiei wavelet. Funcţiile Coiflet (coifN) reprezintă o altă familie de funcţii discrete wavelet, descoperite de Ingrid Daubechies. Numele familiei de funcţii wavelet Symlet se

26

scrie symN, unde la fel ca şi la Daubechies, N este ordinul, iar sym este "prenumele" funcţiei wavelet. Funcţiile wavelet biortogonale se scriu biorNr.Nd, iar funcţiile inverse biortogonale, în comparaţie cu cele biortogonale, se scriu rbioNr.Nd.

Din varietatea de familii de wavelet-uri în acest experiment s-au utilizat următoarele funcţii: db1db15, coif1coif5, sym1sym15, bior 1.1bior6.8, rbio1.1rbio6.8 (în total un număr de 64 de familii de wavelet-uri).- s-a utilizat numai metoda I de extragere a trăsăturilor (descrisă în figura 3.2) din două motive:

1- utilizează transformata Wavelet

2- faţă de metoda II nu necesită o transformare prealabilă a imaginii şi astfel timpul de extragere al trăsăturilor din imagini este mai redus.

Astfel, prin utilizarea metodei I au fost obţinuţi vectorii de trăsături ai bazei de imagini pentru valorile parametriilor transformatei Wavelet stabilite mai sus. S-au obţinut un număr de 4x64=256 vectori de caracteristici, care au fost salvaţi în fişiere text. La sfârşitul fiecărei linii a fişierului s-a introdus clasa reală a imaginii (pentru a se putea calcula acurateţea de clasificare)- s-a realizat permutarea liniilor tuturor fişierelor, pentru a nu permite clasificatorului să înveţe inclusiv ordinea de preluare a imagnilor - pentru învăţare şi testare datele au fost împărţite asfel încât să se obţină 80% din imaginile fiecărei clase pentru învăţare şi 20% pentru testare (câte 160 de imagini din fiecare clasă pentru învăţare şi 40 de imagini din fiecare clasă pentru testare).- s-a realizat clasificarea imaginilor din cele 256 de fişiere prin intermediul clasificatorului KNN. S-a optat pentru obţinerea unei acurateţi de clasificare cât mai bună, în defavoarea unor timpi de calcul ai transformatei Wavelet mai ridicaţi (cu cât nivelul de descompunere wavelet este mai mare cu atât timpul necesar realizării transformatei Wavelet este mai ridicat, dar scade timpul de clasificare).

În urma acestui experiment s-a observat că acurateţea maximă se obţine pentru familia de wavelet-uri bior1.3 şi nivelul de descompunere wavelet egal cu 3.

Coeficienţii cA, cH, cV şi cD de nivlel 3 şi familie bior1.3 ai unei imagini arată astfel:

Figura 3.9 Transformata Wavelet a unei imagini

În figura 3.9 este prezentat rezultatul aplicării transformatei Wavelet de familie bior1.3 şi nivel de descompunere wavelet 3 asupra unei imagini oarecare din baza de date. În urma aplicării transformatei wavelet de nivel 3 şi familie bior1.3 s-a realizat reducerea numarului de trăsături ale imaginii prezentate în figura de mai sus de la [148x93] (valori ce reprezintă dimensiunea imaginii originale) pâna la [16x22]. După cum se poate observa în figura 3.2 din rezultatul transformatei Wavelet al imaginii sunt extrase caracteristicile: "primele 4 momente",

27

histogramele multi-scală şi caracteristicile Tamura, numărul de trăsături reducându-se de la [16x22=352] la 78 (48 pentru "primele 4 momente", 24 pentru histogramele multi-scală şi 6 pentru caracteristicile Tamura).

3.4 Modul de împărţire al datelor pentru învăţare şi testare

După cum se poate observa în figura 3.10, orice clasificator trebuie să aibe un set de date pentru antrenare şi altul pentru testare. Iesirea unui astfel de clasificator este un vector care conţine numărul asociat claselor imaginilor din setul de testare (clasa_testare care este un vector coloană).

Figura 3.10 Schema bloc a clasificării KNN

În funcţie de tipul clasificatorului setul de date de antrenare, respectiv de testare trebuie să aibe o anumită structură. Astfel pentru cele două variante ale clasificatorului KNN (KNNC şi KNNR) setul de antrenare şi cel de testare va fi compus astfel: - setul de antrenare este format din doi vectori - vector_trăsături_antrenare, care conţine pe fiecare linie trăsăturile imaginilor destinate antrenării şi clasa_antrenare, care este un vector coloană ce conţine pe fiecare linie clasa corespondentă imaginii sotocate pe aceeaşi linie în vectorul de antrenare.- setul de testare este format dintr-un singur vector care are acelaşi număr de coloane ca şi vector_trăsături_antrenare, conţinând pe fiecare linie trăsăturile unei imagini de test.

Numărul de linii al acestor vectori depind de procentul de imagini din baza de date destinate antrenării şi testării. Cum în lucrarea de faţă s-a ales un procent de 80% din imaginile fiecărei clase pentru antrenare şi 20% pentru testare, aceşti vectori vor avea următoarea dimensiune:- vector_trăsături_antrenare: 80% x 800 imagini = 640 imagini, iar pentru fiecare imagine s-au extras 318 trăsături. Astfel dimensiunea datelor de învăţare este [640 linii x 318 coloane].- vector_trăsături_testare: 20% x 800 imagini = 160 imagini, iar pentru fiecare imagine s-au extras 318 trăsături. Astfel dimensiunea datelor de testare este [160 linii x 318 coloane].- clasa_antrenare după cum a mai fost precizat este un vector coloană cu acelaşi număr de linii ca şi vector_trăsături_antrenare. Aşadar vom avea o dimensiune de [640 linii x 1 coloană]. - clasa_testare este tot un vector coloană care conţine acelaşi număr de linii ca şi vector_trăsături_testare rezultând astfel dimensiunea [160 linii x 1 coloană].

Testarea clasificatorului KNN s-a realizat pentru un număr de vecini k=1, 3 sau 5. După cum se poate observa k ia doar valori impare, din cauză că avem patru clase şi s-a dorit evitarea cazurilor în care clasificatorul poate atribuii imaginea la doua clase diferite în acelaşi timp.

Acurateţea clasificării a fost calculată ca raportul dintre instanţele corect clasificate şi număr total de instanţe clasificate. Determinarea instanţelor corect clasificate s-a realizat prin compararea claselor prezise de clasificator cu clasele reale (predefinite) ale imaginilor clasificate. Din acest motiv este necesar stocarea claselor reale ale imaginilor de test.

28

3.5 Îmbunătăţirea performanţelor

S-a încercat îmbunătăţirea performanţelor prin două metode:- reducerea numărului de trăsături extrase din fiecare imagine- transformarea aplicaţiei într-un executabil

3.5.1 Reducerea numărului de trăsături extrase din fiecare imagine

Prin reducerea numărului de trăsături extrase din imagini se vor îmbunătăţii timpul de extragere al caractersiticilor, precum şi timpul de clasificare.

După cum se poate observa în figura 3.5 formarea vectorului de trăsături se realizează prin aplicarea asupra imaginilor din baza de date a combinării celor patru metode de extragere: metoda I, metoda II, metoda III şi metoda IV.

În tabelul 3.1 nu au fost analizate rezultatele tuturor combinaţiilor posibile de formare a vectorului de trăsături. Astfel, s-a încercat reducerea numărului de trăsături extrase din fiecare imagine prin analiza tuturor modalităţilor posibile de formare a vectorului de trăsături pornind de la cele patru metode: metoda I, metoda II, metoda III şi metoda IV.

Deoarece avem un număr de patru metode de extragere a caracteristicilor, numărul de modalităţi posibile de obţinere a vectorului de trăsături este dat de:

C41+C4

2+C43+C4

4=4+6+4+1=15 modalităţi

Cele cincisprezece modalităţi de formare a vectorului de trăsături sunt obţinute prin aplicarea asupra imaginilor a următoarelor metode şi combinaţii de metode de extragere:1. metoda I2. metoda II3. metoda III4. metoda IV5. metoda I +metoda II6. metoda I + metoda III7. metoda I + metoda IV8. metoda II + metoda III9. metoda II + metoda IV10. metoda III + metoda IV11. metoda I + metoda II + metoda III 12. metoda I + metoda II + metoda IV13. metoda I + metoda III + metoda IV14. metoda II + metoda III +mrtoda IV15. metoda I +metoda II + metoda III + metoda IV

Au fost formaţi astfel cincisprezece vectori de caracteristici ai bazei de imagini, dimensiunea lor variind în funcţie de modalitatea de extragere a trăsăturilor (a se vedea tabelul 4.1 pentru mai multe detalii).

Pentru clasificarea celor cincisprezece vectori de caracteristici s-a procedat după cum urmează:- s-a realizat o aplicaţie de extragere a trăsăturilor din imaginile bazei de date pentru toate cele cincisprezece modalităţi de formare a vectorului de caracteristici. Vectorii astfel formaţi au fost salvaţi în fişiere text.- s-a realizat permutarea liniilor tuturor fişierelor, pentru a nu permite clasificatorului să înveţe inclusiv ordinea de preluare a imagnilor. - pentru învăţare şi testare datele au fost împărţite asfel încât să se obţină 80% din imaginile fiecărei clase pentru învăţare şi 20% pentru testare - s-a realizat clasificarea imaginilor din cei cincisprezece vectori de caracteristici prin

29

intermediul clasificatorului KNN- rezultatele de clasificare a celor cincisprezece vectori au fost comparate pe baza acurateţii de clasificare. Acurateţea dată de fiecare combinaţie de metode, a fost comparată cu rezultatele obţinute pentru combinaţia de metode metoda I+metoda II+metoda III +metoda IV (cea cu care s-a obţinut cea mai bună acurateţe de clasificare). Astfel s-a observat că modalităţile de extragere a trăsăturilor compuse din metoda III + metoda IV, metoda I + metoda III + metoda IV, metoda II + metoda III + metoda IV, se apropie foarte mult de acurateţea obţinută cu metoda I+metoda II+metoda III +metoda IV, fără a o depăşii (90.63 % faţa de 91.25%).

În cazul celor trei modalităţi (metoda III + metoda IV, metoda I + metoda III + metoda IV, metoda II + metoda III + metoda IV) se obţine un timp de clasificare mai bun (0.09 secunde faţă de 0.11) în comparaţie cu metoda cu care s-a obţinut cea mai bună acurateţe. Acest lucru se datorează numărului mai mic de trăsături pe imagine (pentru mai multe detalii consultaţi tabelul 4.1)

Totuşi, s-a optat pentru obţinerea unei acurateţi de clasificare cât mai bună în detrimentul unui timp de clasificare mai scăzut.

3.5.2 Transformarea aplicaţiei într-un executabil

S-a încercat îmbunătăţirea performanţelor în ceea ce priveşte timpii de clasificare şi timpii de extragere a trăsăturilor a tuturor celor cincisprezece combinaţii posibile de creare a vectorului de caracteristici. Acest lucru s-a realizat prin transformarea aplicaţie într-un fişier executabil. În acest scop a fost utilizat toolbox-ul deploytool din Matlab, care urmăreşte următoarea schemă bloc pentru realizarea unui astfel de fişier:

Figura 3.11 Schema bloc de realizare a executabilului [23]

În figura 3.11 este prezentat modul foarte simplu de realizare a unui fişier executabil. S-a ales acest mod de realizare a executabilului datorită simplităţii precum şi datorită

dorinţei de a obţine timpi de clasificare mai buni. Astfel cu ajutorul acestui toolbox şi urmărind paşii de mai sus s-a realizat transformarea aplicaţiei de obţinere şi clasificare a celor cincisprezece vectori de trăsături (dezvoltată în Matlab) într-o aplicaţie "standalone" (de sine stătătoare, care nu necesită instalarea Matlab-ului pentru rulare) pentru sistemul de operare Windows.

3.6 Interfaţa grafică a aplicaţiei

Pentru a realiza o prezentare a acestei lucrări s-a relizat o interfaţă grafică GUI (Graphical User Interface) cu ajutorul toolbox-ului GUIDE (Graphical User Interface Design Environment) din Matlab. Această aplicaţie a fost transformată într-una executabilă cu ajutorul deploytool.

Interfaţă grafică arată astfel:

30

Figura 3.12 Interfaţa grafică a lucrării

În figura 3.12 este prezentată aplicaţia GUI realizată prin intermediul toolbox-urilor Matlab (GUIDE + deploytool).

Interfată grafică este formată din trei părti:

- partea de extragere a trăsăturilor- partea de clasificare a imaginilor- partea de testare a clasificatorului KNN cu alte imagini decât cele din baza de date

3.6.1 Extragerea trăsăturilor

Interfaţa grafică permite utilizatorului să aleagă clasele de imagini din care să se realizeze extragerea trăsăturilor, precum şi metodele de extragere a trăsăturilor (poate să aleagă orice combinaţie a celor patru metode descrise în figura 3.2). După apăsarea butonului "Creare vector trăsături" se va realiza extragerea trăsăturilor prin metoda aleasă din imaginile claselor selectate.

Timpul de extragere al trăsăturilor tuturor imaginilor din baza de date va fi vizibil utilizatorului odată cu terminarea procesului de extragere al trăsăturilor în căsuţa numerotată cu "2", iar informaţiile legate de numărul de caracteristici al vectorului de trăsături astfel format vor fi vizibile în căsuţa numerotată cu "1".

3.6.2 Clasificarea imaginilor

Pentru clasificarea imaginilor s-a ales clasificatorul KNNR. Interfaţa permite setarea

31

numărului de vecini pentru care se face clasificarea (căsuţa "3") şi procentului din numărul total de imagini destinat procesului de învăţare (căsuţa 4). Procentul de imagini pentru care se face testarea se calculează automat prin scăderea din 100% a procentului de imagini de învăţare. Acesta este afişat odată cu setarea procentului de învăţare, în căsuţa "5".

Prin apăsarea butonului "Antrenare şi testare KNN" se realizează clasificarea imaginilor din setul de testare în funcţie de parametrii setaţi. Informaţiile legate de acurateţea clasificării şi timpul de clasificare vor fi afişate în căsuţele "6",respectiv "7".

3.6.3 Testarea clasificatorului KNN şi cu alte imagini decât cele din baza de date

Interfaţa grafică permite testarea clasificatorului KNN şi cu alte imagini decât cele din baza de date, în funcţie de vectorul de trăsături extras "on-line" sau în funcţie de vectorul de trăsături implicit obţinut în cadrul celei mai bune metode de extragere a caracteristicilor (metoda I+metoda II+metoda III+metoda IV).

Pentru a se realiza testarea, utilizatorul trebuie să aleagă o nouă imagine prin apăsarea butonului "Preia imagine" şi să selecteze vectorul de trăsături utilizat. Trăsăturile imaginii preluate vor fi extrase prin aceleaşi metode prin care s-a format şi vectorul de trăsături ales (cel format on-line sau cel implicit). Informaţiile legate de timpul de extragere al trăsăturilor, timpul de clasificare şi clasa imaginii noi vor fi afişate în căsuţele "8", "9", respectiv "10".

4. Rezultate experimentale

Toate experimentele din acestă lucrare au fost relizate pe un calculator desktop având următoarea configuraţie:

- placă de bază: ASUS M3N78-VM- procesor: AMD Athlon(tm) 64 3000+, având o frecvenţă de 1.8Ghz- RAM: 2 Gb DDR II- placaă video: Nvidia GeForce 8200 - HDD: 250 Gb, 7200 rpm- sistem de operare: Windows XP Service Pack 3

4.1 Rezultate experimentale Weka

Pentru a avea convingerea că trăsăturile din vectorul de caracteristici sunt destul de diferenţiate de la o clasă la alta, s-a folosit clasificatorul IBk (echivalentul KNN-ului) din Weka prin testarea acestuia cu datele de învăţare, obţinându-se următoarea matrice de confuzie;

==Matricea de confuzie==

M P A G200 0 0 0

|M=1

0

200 0 0

|P=2

32

0 0

200 0

|A=3

0 0 0

200

|G=4

Figura 4.1 Matrice de confuzie Weka (numărul de vecini=1)

Figura 4.1 prezintă matricea de confuzie obţinută în Weka prin testarea clasificatorului IBk cu datele de învăţare, pentru vectorul de trăsături construit după figura 3.5. În figura de mai sus se observă că în afară de diagonala principală celelalte elemente sunt zero, ceea ce înseamnă că toate imaginile au fost atribuite corect clasei din care fac parte. Ei bine, situaţia pentru cazul în care numărul de vecini este mai mare ca unu (respectiv k=3 sau 5) se schimbă, făcând ca acurateţea clasificării să nu mai fie de 100%. Astfel în acest caz s-au obţinut următoarele matrice de confuzie:

==Matricea de confuzie==

M P A G199 0 1 0 |M=11 193 6 0 |P=26 4 183 7 |A=37 3 15 175 |G=4

==Matricea de confuzie==

M P A G200 0 0 0 |M=11 197 3 0 |P=211 4 174 11 |A=311 3 19 167 |G=4

(a) (b)

Figura 4.2 Matricele de confuzie pentru k=3 (a), respectiv k=5 (b) obţinute în Weka

Figura 4.2 prezintă matricele de confuzie obţinute în Weka, prin testarea clasificatorului IBk cu datele de învăţare (pentru vectorul de trăsături construit după figura 3.5), ilustrând rezultatele diferite obţinute pentru k=3 (figura 4.2 a), respectiv k=5 (figura 4.2 b) faţă de primul caz (figura 4.1) când k=1.

După cum se poate observa în matricele de confuzie de mai sus celelate elemente în afara diagonalei principale nu sunt nule ca şi în figura 4.1, având şi imagini care nu sunt atribuite corect. Astfel, când k=3 pentru clasa maşini (notată cu M) au fost atribuite corect 199 de imagini din 200, una fiind atribuită incorect clasei animale (notată cu A), pentru clasa pietoni (notată cu P) - 193 corecte,7 incorecte, ş.a.m.d.

Acurateţea de clasificare scade la 93.75% (adică 750 imagini clasificate corect din totalul de 800) şi la 92.25% pentru k=5 (adică 738 de imagini clasificate corect din totalul de 800). Acest lucru relevă că pentru k=3 şi k=5 nu s-a realizat o diferenţiere suficientă între cele patru clase (existănd asemănări între acestea) şi după cum o să putem observa în cele ce urmează performaţele de clasificare cele mai bune se vor obţine pentru k=1. S-a ales pentru numărul de vecini valori impare (1, 3, respectiv 5) din cauză că sunt patru clase şi s-a dorit evitarea cazurilor în care clasificatorul poate atribuii imaginea la doua clase diferite în acelaşi timp.

De asemenea, Weka a fost utilizat şi pentru verificarea implementării clasificatoarelor KNN (KNNC şi KNNR) în Matlab.

Astfel, în etapa de testare, în Weka se obţin următoarele matrice de confizie:

==Matricea de confuzie== ==Matricea de confuzie== ==Matricea de confuzie==

33

M P A G40 0 0 0 |M=10 36 3 1 |P=21 2 34 3 |A=33 0 9 28 |G=4

M P A G39 0 1 0 |M=10 39 1 0 |P=23 3 30 4 |A=32 0 8 30 |G=4

M P A G39 0 1 0 |M=12 38 2 0 |P=24 2 29 5 |A=32 0 5 33 |G=4

(a) (b) (c)Figura 4.3 Matricele de confuzie pentru setul de testare (k=1,3 şi 5) obţinute în Weka

În figura 4.3 putem observa modul în care au fost atribuite imaginile din setul de testare (format din 20% din imaginile fiecărei clase, adică 40 de imagini din fiecare clasă) în urma evaluării imaginilor cu ajutorul clasificatorului IBk. Astfel, pentru k=1 s-a obţinut o acurateţe de clasificare de 86.25% (adică 138 de imagini clasificate corect din totalul de 160), pentru k=3 - 86.25%, iar pentru k=5 - 86.875% (adică 139 de imagini clasificate corect din totalul de 160).

În Matlab, în etapa de testare pentru ambele clasificatoare KNN (KNNC şi KNNR) s-au obţinut următoarele matrice de confuzie:

==Matricea de confuzie==

M P A G40 0 0 0 |M=10 38 1 1 |P=24 1 32 3 |A=30 0 4 36 |G=4

==Matricea de confuzie==

M P A G39 0 1 0 |M=10 38 0 2 |P=25 1 26 8 |A=30 1 5 34 |G=4

==Matricea de confuzie==

M P A G39 0 1 0 |M=10 38 0 2 |P=25 0 27 6 |A=30 1 5 34 |G=4

(a) (b) (c)

Figura 4.4 Matricele de confuzie pentru setul de testare obţinute în Matlab

În figura 4.4 este prezentat rezultatul atribuirii imaginilor fiecărei clase, pentru setul de testare, clasificarea fiind realizată în Matlab prin intermediul celor două clasificatoare KNN studiate. Aceste clasificatoare returnează acelaşi rezultat în ceea ce priveşte acurateţea şi matricele de confuzie, diferenţa majoră dintre ele fiind constituită de timpii de clasificare (vezi figura 4.5).

În comparaţie cu clasificatorul IBk din Weka, pentru cele din Matlab s-a obţinut o acurateţe de clasificare puţin mai mare, respectiv pentru k=1 (figura 4.4 a) s-a obţinut o acurateţe de 91.25% (adică 146 imagini clasificate corect din totalul de 160), pentru k=3 (figura 4.4 b) 86.25% (adică 137 de imagini clasificate corect din totalul de 160) şi pentru k=5 (figura 4.4 c) 86.25%.

4.2 Rezultate experimentale din Matlab şi din aplicaţia executabilă

Aplicaţia executabilă se referă la experimentul realizat pentru obţinerea celor cincisprezece combinaţii posibile de formare a vectorului de trăsături descris în secţiunea: 3.5.1 Reducerea numărului de trăsături extrase din fiecare imagine, a lucrării de faţă.

Diferenţa în ceea ce priveşte timpii de clasificare dintre cele două clasificatoare (KNNC şi KNNR) în funcţie de numărul de trăsături extrase (de combinaţia de metode utilizată pentru construirea vectorului de trăsături) poate fi observată atât în figura 4.5, cât şi în tabelul 4.1

34

Figura 4.5 Graficul timpilor de clasificare KNNR şi KNNC în funcţie de numărul de trăsături

În figura 4.5 sunt prezentate sunt prezentate următoarele grafice:- graficul timpului de clasificare KNNR (cel cu albastru) al celor cincisprezece vectori de caracteristici în funcţie de numărul de de trăsături extrase din imagini pentru fiecare combinaţie de metode (vezi tabelul 4.1) - graficul timpului de clasificare KNNC (cel cu roşu) al celor cincisprezece vectori de caracteristici în funcţie de numărul de de trăsături extrase din imagini pentru fiecare combinaţie de metode (vezi tabelul 4.1).

După cum se poate observa în figura 4.5 timpul de clasificare KNNR este mult mai bun, având valori mai mici decât timpul de clasificare KNNC. Timpul de clasificare KNNC este divizat cu zece pentru a se putea observa mai bine diferenţele între cele două grafice în fiecare punct.

Comparând valorile timpilor de clasificare KNNR din figura 4.6 obţinuţi în Matlab şi în aplicaţia executabilă putem observa că performanţele obţinute în Matlab nu diferă foarte mult de cele obţinute prin intermediul aplicaţiei executabile.

Figura 4.6 Graficul timpului de clasificare în funcţie de numărul de trăsături

Figura 4.6 prezintă variaţia timpilor de clasificare ai KNNR-ului obţinuţi în cadrul aplicaţiei Matlab (cu albastru), respectiv în cadrul aplicaţiei executabile (cu roşu) pentru cele cincisprezece moduri de formare a vectorului de trăsături.

35

Figura 4.7 Graficul timpului de extragere coeficienţi în funcţie de numărul de trăsături

Figura 4.7 prezintă graficul timpului de extragere a coeficienţilor (obţinut în Matlab- cu albastru şi în aplicaţia executabilă- cu roşu) în funcţie de numărul de trăsături.

După cum se poate observa în figura 4.7, diferenţele dintre timpul de extragere a caracteristicilor pentru toate imaginile din baza de date în cazul aplicaţiei Matlab, respectiv aplicaţiei standalone, sunt atât de mici încât reprezentările grafice a acestora în funcţie de numărul de trăsături extrase pentru fiecare imagine sunt suprapuse. Astfel, transformarea unei aplicaţii Matlab într-un executabil nu oferă performanţe cu mult mai bune în ceea ce priveşte timpii de execuţie, dar este utilă pentru rularea aplicaţiei Matlab pe calculatoarele care nu au instalat programul Matlab.

În tabelul 4.1 sunt prezentate rezultatele experimentale obţinute în Matlab, prin clasificarea tuturor celor cincisprezece posibilităţi de creare a vectorului de trăsături. După cum putem observa, tabelul informează asupra numărului de trăsături din vectorul de caracteristici construit conform metodei specificate, timpul de extragere al coeficienţilor tuturor imaginilor din baza de date, numărul de vecini k al clasificatoarelor KNNR şi KNNC pentru care s-a obţinut acurateţea de clasificare cea mai mare, acurateţea de clasificare pentru fiecare clasă de imagini din baza de date, acurateţea medie a celor patru clase de imagini, timpul necesar clasificatoarelor KNNR şi KNNC să clasifice setul de testare constituit din trăsăturile a 20% din imaginile fiecărei clase (40 de imagini din fiecare clasă).

În tabelul 4.2 sunt prezentaţi aceeaşi termeni de performanţă a clasificării şi extragere a trăsăturilor (cu excepţia timpului de clasificare KNNC) obţinuţi în urma transformării aplicaţie de obţinere a celor cincisprezece vectori de atribute şi de clasificare a acestora, într-o aplicaţie executabilă independentă de Matlab. Prin această transformare s-a încercat îmbunătăţirea performanţelor de extragere şi de clasificare prin reducerea timpilor de extragere a trăsăturilor, respectiv timpilor de clasificare a setului de testare pentru fiecare din cei cincisprezece vectori de trăsături.

36

Tabel 4.1 Rezultate obţinute în Matlab

Nr.crt

Combinaţia de Metode

Numărtrăsături

Timp extragere coeficienţi pe toată

baza de imagini

k Acurateţe [%] Acurateţeamedie[%]

Timpclasificare

KNNR[s]

Timpclasificare

KNNC[s]

1 3 5 Masini Pietoni Animale Garbage

1 I 78 1 min, 11 sec x 95 90 50 68 75.63 0.05 0.30

2 II 78 1 min, 41 sec x 88 88 60 47 70.63 0.07 0.21

3 III 90 17 min x 97 85 75 80 84.38 0.05 0.45

4 IV 72 2 h, 51 min x 100 97 45 85 81.88 0.04 0.20

5 I II 156 2 min, 51 sec x 97 95 70 72 83.75 0.06 0.62

6 I III 168 18 min x 97 85 75 85 85.63 0.07 0.65

7 I IV 150 2 h, 52 min x 100 97 50 85 83.13 0.06 0.68

8 II III 168 19 min x 97 85 75 82 85 0.07 0.80

9 II IV 150 2 h, 53 min x 100 97 55 90 85.63 0.06 0.73

10 III IV 162 3 h, 9 min x 100 95 78 90 90.63 0.09 0.79

11 I II III 246 20 min x 97 85 75 85 85.63 0.09 1.26

12 I II IV 228 2 h, 54 min x 100 97 60 90 86.88 0.08 0.97

13 I III IV 240 3 h, 10 min x 100 95 78 90 90.63 0.09 1.21

14 II III IV 240 3 h, 10 min x 100 95 78 90 90.63 0.09 1.27

15 I II III IV 318 3 h, 12 min x 100 95 80 90 91.25 0.10 1.30

Tabel 4.2 Rezultate obţinute prin transformarea aplicaţiei într-un executabil

33

34

Nr.crt

Combinaţia de Metode

Numărtrăsătur

i

Timp extragere coeficienţi pe

toată baza

k Acurateţe [%]

Acurateţeamedie[%]

TimpclasificareKNNR[s]1 3 5 Masini Pietoni Animale Garbage

1 I 78 1 min, 7 sec x 95 90 50 68 75.63 0.04

2 II 78 1 min, 34 sec x 88 88 60 47 70.63 0.04

3 III 90 16 min x 97 85 75 80 84.38 0.04

4 IV 72 2 h, 51 sec x 100 97 45 85 81.88 0.04

5 I II 156 2 min, 41 sec x 97 95 70 72 83.75 0.06

6 I III 168 18 min x 97 85 75 85 85.63 0.06

7 I IV 150 2 h, 52 min x 100 97 50 85 83.13 0.06

8 II III 168 18 min x 97 85 75 82 85 0.06

9 II IV 150 2 h, 52 min x 100 97 55 90 85.63 0.06

10 III IV 162 3 h,8 min x 100 95 78 90 90.63 0.08

11 I II III 246 19 min x 97 85 75 85 85.63 0.09

12 I II IV 228 2 h, 54 min x 100 97 60 90 86.88 0.08

13 I III IV 240 3 h, 9 min x 100 95 78 90 90.63 0.08

14 II III IV 240 3h, 9 min x 100 95 78 90 90.63 0.10

15 I II III IV 318 3 h, 11 min x 100 95 80 90 91.25 0.10

În figura de mai jos (figura 4.8) se poate observa rata de clasificare a celor patru clase (masini- în galben, pietoni- în roşu, animale- în verde şi garbage- în albastru), precum şi acurateţea medie (cu linie neagră întreruptă) în funcţie de numărul de trăsături al vectorului de caracteristici.

Figura 4.8 Graficul acurateţii în funcţie de numărul de trăsături

După cum se poate observa în figura 4.8 clasa cu cea mai bună rată de recunoaştere este clasa maşini, urmată de clasa pietoni, fapt ce poate fi explicat prin existenţa unui număr suficient de imagini, care să permită clasificatorului o învăţare eficientă. În cazul celorlalte două clase, animale şi garbage, acurateţea de clasificare este mai scăzută datorită varietăţii de fundale ale imaginilor.

5. Concluzii

Pe durata realizării acestei lucrări au fost studiate diferite metode deja existente de formare a vectorului de trăsături în vederea clasificării imaginilor.

Din multitudinea de metode studiate (vezi figura 3.3), s-a ajuns la schema de formare a vectorului de caracteristici prezentată în figura 3.5. În funcţie de acurateţea de clasificare, a fost aleasă combinaţia cea mai bună de metode de extragere a trăsăturilor din imaginile bazei de date.

Din punct de vedere aplicativ a fost dezvoltată o interfaţă grafică, care permite utilizatorului să selecteze diferite variante de formare a vectorului de trăsături, precum şi posibilitatea testării clasificatorului KNN cu alte imagini decât cele din baza de date. Vectorul de trăsături poate avea, în funcţie de metodele alese, o dimensiune minimă de 72 caracteristici şi maximă de 318 caracteristici.

Principalul avantaj al aplicaţiei realizate, în comparaţie cu metoda de extragere a caracteristicilor propusă în WND-CHARM (figura 3.3) este numărul mult mai redus de trăsături pe imagine, ceea ce are o influenţă foarte mare asupra timpului de extragere al coeficienţilor tuturor imaginilor din baza de date, precum şi asupra timpului de clasificare.

Astfel, timpul necesar extragerii trăsăturilor (pentru care se obţine acurateţea cea mai bună) este de 3 ore şi 11 minute, în comparaţie cu cele 48 de ore necesare extragerii caracteristicilor cu metoda propusă în WND-CHARM. De asemenea, s-a obţinut o acurateţe de clasificare mult mai bună, decât dacă se realiza extragerea caracteristicilor pe baza metodologiei descrisă în [9] (91.25% faţă de 68%). În ceea ce priveşte baza de imagini, s-a ajuns la concluzia că aceasta trebuie să aibe un

35

număr mai mare de imagini cel puţin pentru clasele animale şi garbage, pentru ca rezultatele clasificării să fie îmbunătăţite.

Acurateţea de clasificare nu creşte liniar odată cu extragerea mai multor trăsături din imaginile bazei de date (vezi figura 4.8).

Prin creşterea numărului de metode de extragere a caracteristicilor se măreşte timpul de extragere al trăsăturilor, precum şi timpul de clasificare. De aceea pentru a avea o clasificare într-un timp cât mai redus trebuie să se facă un compromis între dimensiunea vectorului de trăsături şi timpul de clasificare.

Prin transformarea aplicaţiei Matlab într-una executabilă nu se pot obţine timpi de execuţie mai buni, dar aceasta este folositoare la rularea aplicaţiei realizate în Matlab pe calculatoarele care nu au instalat acest program sau au instalate versiuni diferite ale acestuia.

În urma rezultatelor obţinute, Weka s-a dovedit un program foarte util în stabilirea metodelor eficiente de formare a vectorului de trăsături, precum şi în verificarea implementărilor Matlab a clasificatoarelor KNN (KNNC şi KNNR).

Problemele cele mai importante, întâmpinate în realizarea acestei lucrări au fost:- construirea unei baze de date care să conţină un număr suficient de imagini pe clasăAcurateţea de clasificare după cum se poate observa şi în figura 4.8 nu este aceeaşi pentru

toate clasele şi datorită faptului că nu a fost realizată o bază de date special concepută pentru această lucrare, imaginile care formează cele patru clase făcând parte din baze de imagini diferite.

- dimensiunea diferită a imaginilor din baza de dateAceastă problemă a fost rezolvată prin folosirea unor metode de extragere a trăsăturilor

care să aibe ca rezultat acelaşi număr de caracteristici indiferent de dimensiunea imaginii. Astfel, dimensiunea vectorului de trăsături nu variază de la o imagine la alta, fiind aceeaşi pentru toate imaginile. Această condiţie este necesară la clasificarea imaginilor. Extragerea unui număr constant de trăsături din fiecare imagine (indiferent de dimensiunea lor) se putea realiza şi prin redimensionarea tuturor imaginilor din baza de date la aceeaşi dimensiune, dar rezultatele obţinute au fost mai scăzute.

Aplicaţia realizată poate fi utilizată cu succes la dezvoltarea unor sisteme de recunoaştere de obstacole, întălnite de o maşină pe şosea, sisteme automate de supraveghere a parcărilor sau sisteme de utilaje automate în vederea efectuării unor lucrări agricole.Prin schimbarea bazei de imagini cu una constituită din imagini medicale, aplicaţia poate fi utilizată în domeniul medical pentru detecţia anomaliilor sau procesarea imaginilor biologice.

6. Bibliografie

36

[1] Smith, J.R., Chang, S.F., 1996. Local color and texture extraction and spatial query. Proc.IEEE International Conference on Image Processing, Lausanne, Switzerland, September 1996.

[2]Shen, L., Bai, L., 2006. MutualBoost learning for selecting Gabor features for face recognition, Pattern Recognition Letters, 27, 1758–1767.

[3] Jing, X.Y., Zhang, D., 2004. A Face and Palmprint Recognition Approach Based on Discriminant DCT Feature Extraction. IEEE Transactions on Systems, Man, and Cybernetics, 34, 2405–2414.

[4] Pentland, A., Choudhury, T., 2000. Face recognition for smart environments. Computer, 33, 50–55.

[5] Boland, M.V., Murphy, R.F., 2001. A Neural Network Classifier Capable of Recognizing the Patterns of all Major Subcellular Structures in Fluorescence Microscope Images of HeLa Cells. Bioinformatics, 17, 1213–1223.

[6] Awate, S.P., Tasdizen T., Foster N., Whitaker R.T., 2006. Adaptive Markov modeling for mutualinformation-based, unsupervised MRI braintissue classification. Medical Image Analysis, 10,726–739.

[7] Cocosco, A., Zijdenbos, P., Evans, A.C., 2004. A fully automatic and robust brain MRI tissue classification method. Medical Image Analysis, 7, 513–527.

[8] Ranzato, M., Taylor, P.E., House, J.M., Flagan, R.C., LeCun, Y., Perona, P., 2007. Automatic recognition of biological particles in microscopic images. Pattern Recognition Letters, 28, 31–39.

[9] http://www.phy.mtu.edu/~lshamir/publications/image_classifier.pdf

[10]http://www.upm.ro/facultati_departamente/stiinte_litere/conferinte/situl_integrare_europeana/Lucrari2/Ioan_Ispas.pdf

[11] http://www.dtic.upf.edu/~xserra/cursos/TDP/referencies/Park-DWT.pdf

[12] http://www.mathworks.com

[13] ac.upg-ploiesti.ro/cursuri/is/lab/IS_LUC%203.doc

[14] http://www.wisdom.weizmann.ac.il/~naor/COURSE/fft-lecture.pdf

[15] http://en.wikipedia.org/wiki/Fast_Fourier_transform#Cooley.E2.80.93Tukey_algorithm

[16] http://eivind.imm.dtu.dk/staff/ptoft/Radon/Radon.html

[17] http://imag.pub.ro/ro/cursuri/archive/radon.pdf

[18] http://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:Radon_transform.png

[19]http://www.cs.auckland.ac.nz/compsci708s1c/lectures/Glect- html/topic4c708FSC.htm#tamura

37

[20] http://en.wikipedia.org/wiki/Zernike_polynomials

[21] http://www.astronomy.ohio-state.edu/~martini/Astro890/Astro890L6.pdf

[22] http://inf.ucv.ro/~gorunescu/courses/curs/clustering.pdf

[23] Malab R2009b Help

[24] http://people.revoledu.com/kardi/tutorial/KNN/index.html

[25]http://www.autonlab.org/autonweb/14665/version/2/part/5/data/moore-tutorial.pdf?branch=main&language=en [26] http://www.mathworks.com/support/tech-notes/1600/1605.html#intro

7. Anexe

7.1 Anexa 1

38

Codul Matlab al funcţiei de transformare Wavelet

function [coef_img]=compresie_wavelet(imagine,nivel,tip_transformare)%imagine= imaginea asupra careia se va aplica transformata wavelet dwt2%nivel= nivelul de compresie al imaginilor%tp_transformare= familia de wavelet-uri folosita for i=1:nivel% extragem coeficientii aproximati, de pe orizontala, verticala si% diagonala[cA1,cH1,cV1,cD1] = dwt2(imagine,tip_transformare);imagine=cA1;end;coef_img=cA1;return;

7.2 Anexa 2Codul Matlab pentru obţinerea fişierului ce conţine trăsăturile imaginilor din baza de date

clcclose allclear all%fis- fisierul in care va fi salvat vectorul de trasaturifis=fopen('fisier_caracteristici.txt','w' ); for i=1:4 % Lista contine numele imaginilor din baza de date lista=strcat('Lista',num2str(i),'.txt'); % functia care realizeaza extragerea trasaturilor pentru fiecare % clasa pe rand citesteImaginiLista(lista,fis); endfclose all;

7.3 Anexa 3Codul Matlab al funcţiei de extragere trăsături

function citesteImaginiLista(fisLst,fis)%fisLst - fisierul txt care contine denumirea imaginilor%fis - fisierul in care se va scrie vectorul de trasaturi % preiau nr de imagini in functie de numarul de linii al fisierului ListanumberOfLines = GiveNbOfLines(fisLst);fid_imagesLst=fopen(fisLst);% punem in variabila dirImagini folderul din care sa citeasca imaginilenume_lista = {'Lista1.txt','Lista2.txt','Lista3.txt','Lista4.txt'};T=strcmp(fisLst, nume_lista);currentfolder=pwd;dirImagini={strcat(currentfolder,'\cars\'),... strcat(currentfolder,'\persons\'),... strcat(currentfolder,'\animals\'),... strcat(currentfolder,'\garbage\')};[T,clasa]= sort(T,'descend');clasa=clasa(1);

39

dirImagini=dirImagini{clasa}; for i = 1:numberOfLines-1 % preiau numele fiecarei imagini din fisierul fid_imagesLstimgName = numeImagine(fid_imagesLst);% citesc imaginea si o transform din color in gray [imagine] = imread(strcat(dirImagini,imgName),'png');imagine=rgb2gray(imagine);imagine = im2double(imagine); %metoda I de extractie%aplicare transformata waveletcaracteristici_wavelet1=compresie_wavelet(imagine,3,'bior1.3');%aplicare first4moments, MultiScaleHistograms, TamuraTextures asupra%transformatei wavelet a imaginiifirst4moments = CombFirst4Moments(caracteristici_wavelet1);multiscalehist = MultiScaleHistograms(caracteristici_wavelet1);TamuraFeatures = TamuraTextures(caracteristici_wavelet1);vect_caracteristici=[first4moments,multiscalehist,TamuraFeatures];

%metoda II de extractie% aplicare FFT fftTrans=FourierTransform(imagine);caracteristici_wavelet_fft=compresie_wavelet(fftTrans(:,:,1),3,'bior1.3');%aplicare first4moments, MultiScaleHistograms, TamuraTextures asupra%transformatei wavelet a transformatei fft a imaginiifirst4moments = CombFirst4Moments(caracteristici_wavelet_fft);multiscalehist = MultiScaleHistograms(caracteristici_wavelet_fft);TamuraFeatures = TamuraTextures(caracteristici_wavelet_fft); vect_caracteristici=[vect_caracteristici,first4moments,multiscalehist,... TamuraFeatures]; %metoda III de extractie%aplicare first4moments, MultiScaleHistograms, TamuraTextures si % RadonTransform asupra imaginii originalefirst4moments = CombFirst4Moments(imagine);multiscalehist= MultiScaleHistograms(imagine);TamuraFeatures = TamuraTextures(imagine);radonTransStat = RadonTransformStatistics(imagine); vect_caracteristici=[vect_caracteristici,first4moments,multiscalehist,... TamuraFeatures,radonTransStat]; % metoda IV de extractie%aplicare polinoamele lui zernike asupra imaginii originalezvalues = ZernikePolynomials(imagine); vect_caracteristici=[vect_caracteristici,zvalues];%% salvam rezultatul in fisier lungime=size(vect_caracteristici,2); for j=1:lungime

40

fprintf(fis,'%.3f', vect_caracteristici(j)); fprintf(fis,'%c',','); end; fprintf(fis,'%d%c\n',clasa,','); end fclose(fid_imagesLst);

7.4 Anexa 4

Codul Matlab pentru obţinerea fişierului cu liniile vectorului de caracteristici permutate

close allclear allclc calea=strcat(pwd,'\fisiere\');% fisierul in care este salvat vectorul de trasaturifisierulmeu=strcat(calea,'fisier_caracteristici.txt');% functia care realizeaza permutarea datelor precum si impartirea lor in% 80% si 20% pentru invatare si testareprelucrareFisierIN(fisierulmeu); fclose all;

Codul Matlab pentru funcţia prelucrarefisierIN

function prelucrareFisierIN(fisierulmeu) % fac permutari de linii, pt ca sa nu-i dau posibilitatea% clasificatorului sa invete inclusiv ordinea obiectelor%preiau datele din fisier si le transform in 80% pentru invatare si 20 %%pentru testarexy=preiaDatelePtPrel(fisierulmeu);lungime=size(xy);clasa1=xy(1:lungime(1)/4,:);clasa2=xy(lungime(1)/4+1:2*lungime(1)/4,:);clasa3=xy(2*lungime(1)/4+1:3*lungime(1)/4,:);clasa4=xy(3*lungime(1)/4+1:lungime(1),:);size1=size(clasa1);size2=size(clasa2);size3=size(clasa3);size4=size(clasa4);clasa1_invatare=clasa1(1:0.8*size1(1),:);clasa1_test=clasa1(0.8*size1(1)+1:end,:);clasa2_invatare=clasa2(1:0.8*size2(1),:);clasa2_test=clasa2(0.8*size2(1)+1:end,:);clasa3_invatare=clasa3(1:0.8*size3(1),:);clasa3_test=clasa3(0.8*size3(1)+1:end,:);clasa4_invatare=clasa4(1:0.8*size4(1),:);clasa4_test=clasa4(0.8*size4(1)+1:end,:); date_invatare=[clasa1_invatare;clasa2_invatare;clasa3_invatare;clasa4_invatare];date_testare=[clasa1_test;clasa2_test;clasa3_test;clasa4_test];

41

%permutare liniidate_invatareperm = permutareLinii(date_invatare);date_testareperm = permutareLinii(date_testare);date=[date_invatareperm;date_testareperm]; %salvez datele in alt fisier -fis_testare_random1.txt calea=strcat(pwd,'\fisiere random\');fid_scriere=fopen(strcat(calea,'fisier_caracteristici_random.txt'),'w');%matricea cu parametrii imaginilor cu liniile permutate %scrierea matricei in noul fisier-fisier_caracteristici_random1.txt dim1=size(date); for k1=1:dim1(1) fprintf(fid_scriere,'%s',date{k1,1}); fprintf(fid_scriere,'\n'); endfclose(fid_scriere);Codul Matlab pentru functia preiaDatelePtPrel

function [xa] = preiaDatelePtPrel(fis)% functie cu care citesc datele dintr-un fisier .txt, linie cu linie% ca stringuri

numberOfLines = GiveNbOfLines(fis);fid_imagesLst_app=fopen(fis); clear xa;clear ya;clear nrul;nr_instante=((numberOfLines-1));

for i = 1:nr_instante %preluam fiecare linie ca un string si o salvam intr-o matrice de %stringuri tline = fgetl(fid_imagesLst_app); xa{i,1}=tline; end fclose(fid_imagesLst_app);

Codul Matlab pentru funcţia permutareLinii

function [rez] = permutareLinii(matrice)% face permutarea liniilor matricei de la intrare; structura lui "matrice"% ar trebui sa fie : pe linia se gaseste info despre obiectul 1 si tot asa,% iar pe coloane sunt caracteristicile si clasa obiectelordim=size(matrice);rez=matrice(randperm(dim(1)),:);

7.5 Anexa 5Codul Matlab pentru clasificarea KNN

close all

42

clear allclc%fisierul in care salvam rezultatele clasificariicalea=strcat(pwd,'/rezultate/');fis1=fopen(strcat(calea,'rezultateknn.txt'),'w'); calea= strcat(pwd,'/fisiere/'); %fisierul din care preluam vectorul de trasaturifisierulmeu=strcat(calea,'fisier_caracteristici.txt');[x y]=preiaDatelePtPrel(fisierulmeu); [dim1,dim2]=size(x);%din parametrii tuturor imaginilor 80% le retinem pentru antrenare si 20%%pentru testarenumber = round(8*dim1/10); %xapp- matricea de antrenarexapp=x(1:number,1:dim2-1); %xtest- matricea de testxtest=x(number+1:dim1,1:dim2-1); %yapp- vectorul care contine clasele imaginilor de antrenareyapp=y(1:number); %ytest- vectorul care contine clasele imaginilor de testareytest=y(number+1:dim1); timp=0;accuracy=0;% facem antrenarea si testarea KNN pentru k=1,3 si 5, unde k=numarul de% vecini for k=1:2:5 tic %clasificatorul KNNC %computedOutput=knnclassify(xtest,xapp,yapp,k); % clasificatorul KNNR DS.input=xapp'; DS.output=yapp'; TS.input=xtest'; knnrParam.k=k; [computedOutput, combinedComputedOutput, nearestIndex, knnrMat] =... knnr(DS, TS, knnrParam);%timpul de clasificaretimp=toc;accuracy=computeAccuracy(ytest,computedOutput')*100;perf=0.5*timp+0.5*(1-accuracy/100);%scrierea rezultatelor obtinute in fisierfprintf(fis1,'%d %.2f %.2f %.2f\n',k,timp,accuracy,perf);% matricea de confuzieconfusion=confusionmatrix(ytest',computedOutput);% calculul acuratetii de clasificare pentru fiecare clasaaccuracy_cars=confusion(1,1)/40;accuracy_persons=confusion(2,2)/40;

43

accuracy_animals=confusion(3,3)/40;accuracy_garbage=confusion(4,4)/40;%scrierea rezultatelor obtinute in fisierfprintf(fis1,'%.2f %.2f %.2f %.2f\n',accuracy_cars,accuracy_persons,accuracy_animals,accuracy_garbage); end; fclose all;

7.6 Anexa 6Codul Matlab al aplicaţiei GUI

function varargout = licentaexe(varargin)% LICENTAEXE M-file for licentaexe.fig% LICENTAEXE, by itself, creates a new LICENTAEXE or raises the existing% singleton*.%% H = LICENTAEXE returns the handle to a new LICENTAEXE or the handle to% the existing singleton*.%% LICENTAEXE('CALLBACK',hObject,eventData,handles,...) calls the local% function named CALLBACK in LICENTAEXE.M with the given input arguments.%% LICENTAEXE('Property','Value',...) creates a new LICENTAEXE or raises the% existing singleton*. Starting from the left, property value pairs are% applied to the GUI before licentaexe_OpeningFcn gets called. An% unrecognized property name or invalid value makes property application% stop. All inputs are passed to licentaexe_OpeningFcn via varargin.%% *See GUI Options on GUIDE's Tools menu. Choose "GUI allows only one% instance to run (singleton)".%% See also: GUIDE, GUIDATA, GUIHANDLES % Edit the above text to modify the response to help licentaexe % Last Modified by GUIDE v2.5 03-Jun-2010 12:06:20 % Begin initialization code - DO NOT EDITgui_Singleton = 1;gui_State = struct('gui_Name', mfilename, ... 'gui_Singleton', gui_Singleton, ... 'gui_OpeningFcn', @licentaexe_OpeningFcn, ... 'gui_OutputFcn', @licentaexe_OutputFcn, ... 'gui_LayoutFcn', [] , ... 'gui_Callback', []);if nargin && ischar(varargin{1}) gui_State.gui_Callback = str2func(varargin{1});end if nargout [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});else

44

gui_mainfcn(gui_State, varargin{:});end% End initialization code - DO NOT EDIT % --- Executes just before licentaexe is made visible.function licentaexe_OpeningFcn(hObject, eventdata, handles, varargin) % This function has no output args, see OutputFcn.% hObject handle to figure% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA)% varargin command line arguments to licentaexe (see VARARGIN)% afisarea imaginii NO_IMAGE de fiecare data cand aplicatia este rulata[imagine_init,map]=imread('no_image.jpg');imshow(imagine_init,map,'parent',handles.axes1);% Choose default command line output for licentaexehandles.output = hObject;% Update handles structureguidata(hObject, handles); % UIWAIT makes licentaexe wait for user response (see UIRESUME)% uiwait(handles.figure1); % --- Outputs from this function are returned to the command line.function varargout = licentaexe_OutputFcn(hObject, eventdata, handles) % varargout cell array for returning output args (see VARARGOUT);% hObject handle to figure% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Get default command line output from handles structurevarargout{1} = handles.output; % --- Executes on button press in radiobutton3 - masinifunction radiobutton3_Callback(hObject, eventdata, handles)% hObject handle to radiobutton3 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hint: get(hObject,'Value') returns toggle state of radiobutton3 % --- Executes on button press in radiobutton4 - pietonifunction radiobutton4_Callback(hObject, eventdata, handles)% hObject handle to radiobutton4 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hint: get(hObject,'Value') returns toggle state of radiobutton4 % --- Executes on button press in radiobutton5 - animale

45

function radiobutton5_Callback(hObject, eventdata, handles)% hObject handle to radiobutton5 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hint: get(hObject,'Value') returns toggle state of radiobutton5 % --- Executes on button press in radiobutton6 - garbagefunction radiobutton6_Callback(hObject, eventdata, handles)% hObject handle to radiobutton6 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hint: get(hObject,'Value') returns toggle state of radiobutton6 function edit1_Callback(hObject, eventdata, handles)%preluarea procentului de invatare si testareprocent_invatare=str2double(get(handles.edit1,'String'));if (isnan(procent_invatare)||(procent_invatare<=0)||procent_invatare>100) errordlg('Introduceti un numar mai mic sau egal cu 100',... 'Error'); else procent_testare=100-procent_invatare; set(handles.edit2,'String',num2str(procent_testare));end% hObject handle to edit1 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hints: get(hObject,'String') returns contents of edit1 as text% str2double(get(hObject,'String')) returns contents of edit1 as a double % --- Executes during object creation, after setting all properties.function edit1_CreateFcn(hObject, eventdata, handles) % hObject handle to edit1 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles empty - handles not created until after all CreateFcns called % Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white');end function edit2_Callback(hObject, eventdata, handles)% hObject handle to edit2 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB

46

% handles structure with handles and user data (see GUIDATA) % Hints: get(hObject,'String') returns contents of edit2 as text% str2double(get(hObject,'String')) returns contents of edit2 as a double % --- Executes during object creation, after setting all properties.function edit2_CreateFcn(hObject, eventdata, handles)% hObject handle to edit2 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles empty - handles not created until after all CreateFcns called % Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white');end function edit3_Callback(hObject, eventdata, handles)% hObject handle to edit3 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hints: get(hObject,'String') returns contents of edit3 as text% str2double(get(hObject,'String')) returns contents of edit3 as a double % --- Executes during object creation, after setting all properties.function edit3_CreateFcn(hObject, eventdata, handles)% hObject handle to edit3 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles empty - handles not created until after all CreateFcns called % Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white');end % --- Executes on button press in pushbutton1.function pushbutton1_Callback(hObject, eventdata, handles)% hObject handle to pushbutton1 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA)close all function edit4_Callback(hObject, eventdata, handles)% preluarea numarului de vecini pentru care sa se clasificenumar_vecini=str2double(get(handles.edit4,'String'));if (isnan(numar_vecini)||(numar_vecini<=0))

47

errordlg('Introduceti un numar intreg de preferabil impar',... 'Error');end; % hObject handle to edit4 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hints: get(hObject,'String') returns contents of edit4 as text% str2double(get(hObject,'String')) returns contents of edit4 as a double % --- Executes during object creation, after setting all properties.function edit4_CreateFcn(hObject, eventdata, handles)% hObject handle to edit4 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles empty - handles not created until after all CreateFcns called % Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white');end % --- Executes on button press in radiobutton8 - metoda Ifunction radiobutton8_Callback(hObject, eventdata, handles)dim_vect=str2double(get(handles.edit8,'String'));handles.dim_vect=dim_vect;% vedem daca metoda I va fi folositametoda1=get(handles.radiobutton8,'Value');%calculam si afisam numarul de trasaturi care va compune vectorul de%caracteristiciif (metoda1==0) dim_vect=handles.dim_vect; dim_vect=dim_vect-78; handles.dim_vect=dim_vect; set(handles.edit8,'String',num2str(dim_vect));else dim_vect=handles.dim_vect; dim_vect=dim_vect+78; handles.dim_vect=dim_vect; set(handles.edit8,'String',num2str(dim_vect));end% hObject handle to radiobutton8 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hint: get(hObject,'Value') returns toggle state of radiobutton8 % --- Executes on button press in radiobutton9 - metoda IIfunction radiobutton9_Callback(hObject, eventdata, handles)% vedem daca metoda II va fi folosita

48

dim_vect=str2double(get(handles.edit8,'String'));handles.dim_vect=dim_vect; metoda2=get(handles.radiobutton9,'Value');%calculam si afisam numarul de trasaturi care va compune vectorul de%caracteristiciif (metoda2==0) dim_vect=handles.dim_vect; dim_vect=dim_vect-78; handles.dim_vect=dim_vect; set(handles.edit8,'String',num2str(dim_vect));else dim_vect=handles.dim_vect; dim_vect=dim_vect+78; handles.dim_vect=dim_vect; set(handles.edit8,'String',num2str(dim_vect));end% hObject handle to radiobutton9 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hint: get(hObject,'Value') returns toggle state of radiobutton9 % --- Executes on button press in radiobutton10 - metoda IIIfunction radiobutton10_Callback(hObject, eventdata, handles)% vedem daca metoda II va fi folositadim_vect=str2double(get(handles.edit8,'String'));handles.dim_vect=dim_vect; metoda3=get(handles.radiobutton10,'Value');%calculam si afisam numarul de trasaturi care va compune vectorul de%caracteristiciif (metoda3==0) dim_vect=handles.dim_vect; dim_vect=dim_vect-90; handles.dim_vect=dim_vect; set(handles.edit8,'String',num2str(dim_vect));else dim_vect=handles.dim_vect; dim_vect=dim_vect+90; handles.dim_vect=dim_vect; set(handles.edit8,'String',num2str(dim_vect));end % hObject handle to radiobutton10 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hint: get(hObject,'Value') returns toggle state of radiobutton10 % --- Executes on button press in radiobutton11 - metoda IVfunction radiobutton11_Callback(hObject, eventdata, handles)

49

% vedem daca metoda II va fi folositadim_vect=str2double(get(handles.edit8,'String'));handles.dim_vect=dim_vect; metoda4=get(handles.radiobutton11,'Value');%calculam si afisam numarul de trasaturi care va compune vectorul de%caracteristiciif (metoda4==0) dim_vect=handles.dim_vect; dim_vect=dim_vect-72; handles.dim_vect=dim_vect; set(handles.edit8,'String',num2str(dim_vect));else dim_vect=handles.dim_vect; dim_vect=dim_vect+72; handles.dim_vect=dim_vect; set(handles.edit8,'String',num2str(dim_vect));end % hObject handle to radiobutton11 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hint: get(hObject,'Value') returns toggle state of radiobutton11 % --- Executes on button press in pushbutton2 - antrenare si testare KNNfunction pushbutton2_Callback(hObject, eventdata, handles)% toate butoanele disabledisableButtons(handles);% preluarea datelor din fisierul cu vectorul de trasaturi obtinut onlinefisier_carac=strcat(pwd,'\fisier_caracteristici.txt');fid_scriere=fopen(strcat(pwd,'\fisier_caracteristici_random.txt'),'w');xy = preiaDatelePtrandomizare(fisier_carac);lungime=size(xy);% preia valoarea pentru procentul de invatareprocent_invatare=str2double(get(handles.edit1,'String'))/100;% impartirea fiecarei clase in 80% pentru invatare si 20% pentru testare% in functie de numarul de claseif (lungime(1)==400) clasa1=xy(1:lungime(1)/2,:); clasa2=xy(lungime(1)/2+1:2*lungime(1)/2,:); size1=size(clasa1); size2=size(clasa2); clasa1_invatare=clasa1(1:round(procent_invatare*size1(1)),:);clasa1_test=clasa1(round(procent_invatare*size1(1))+1:end,:);clasa2_invatare=clasa2(1:round(procent_invatare*size2(1)),:);clasa2_test=clasa2(round(procent_invatare*size2(1))+1:end,:); date_invatare=[clasa1_invatare;clasa2_invatare];date_testare=[clasa1_test;clasa2_test];date_invatareperm = permutareLinii(date_invatare);

50

date_testareperm = permutareLinii(date_testare);date=[date_invatareperm;date_testareperm]; elseif (lungime(1)==600)clasa1=xy(1:lungime(1)/3,:);clasa2=xy(lungime(1)/3+1:2*lungime(1)/3,:);clasa3=xy(2*lungime(1)/3+1:3*lungime(1)/3,:); size1=size(clasa1);size2=size(clasa2);size3=size(clasa3); clasa1_invatare=clasa1(1:round(procent_invatare*size1(1)),:);clasa1_test=clasa1(round(procent_invatare*size1(1))+1:end,:);clasa2_invatare=clasa2(1:round(procent_invatare*size2(1)),:);clasa2_test=clasa2(round(procent_invatare*size2(1))+1:end,:);clasa3_invatare=clasa3(1:round(procent_invatare*size3(1)),:);clasa3_test=clasa3(round(procent_invatare*size3(1))+1:end,:); date_invatare=[clasa1_invatare;clasa2_invatare;clasa3_invatare];date_testare=[clasa1_test;clasa2_test;clasa3_test];date_invatareperm = permutareLinii(date_invatare);date_testareperm = permutareLinii(date_testare);date=[date_invatareperm;date_testareperm]; elseif (lungime(1)==800)clasa1=xy(1:lungime(1)/4,:);clasa2=xy(lungime(1)/4+1:2*lungime(1)/4,:);clasa3=xy(2*lungime(1)/4+1:3*lungime(1)/4,:);clasa4=xy(3*lungime(1)/4+1:lungime(1),:); size1=size(clasa1);size2=size(clasa2);size3=size(clasa3);size4=size(clasa4);clasa1_invatare=clasa1(1:round(procent_invatare*size1(1)),:);clasa1_test=clasa1(round(procent_invatare*size1(1))+1:end,:);clasa2_invatare=clasa2(1:round(procent_invatare*size2(1)),:);clasa2_test=clasa2(round(procent_invatare*size2(1))+1:end,:);clasa3_invatare=clasa3(1:round(procent_invatare*size3(1)),:);clasa3_test=clasa3(round(procent_invatare*size3(1))+1:end,:);clasa4_invatare=clasa4(1:round(procent_invatare*size4(1)),:);clasa4_test=clasa4(round(procent_invatare*size4(1))+1:end,:); date_invatare=[clasa1_invatare;clasa2_invatare;clasa3_invatare;clasa4_invatare];date_testare=[clasa1_test;clasa2_test;clasa3_test;clasa4_test];date_invatareperm = permutareLinii(date_invatare);date_testareperm = permutareLinii(date_testare);date=[date_invatareperm;date_testareperm]; end;

51

% scrierea datelor in fisierul randomdim1=size(date); for k1=1:dim1(1) fprintf(fid_scriere,'%s',date{k1,1}); fprintf(fid_scriere,'\n'); end % preluarea datelor din fisierul random pentru clasificare KNN [x y]=preiaDatelePtPrel(strcat(pwd,'\fisier_caracteristici_random.txt')); [dim1,dim2]=size(x); number = round(procent_invatare*dim1); %xapp- matricea de antrenare xapp=x(1:number,1:dim2-1); %xtest- matricea de test xtest=x(number+1:dim1,1:dim2-1); %yapp- vectorul care contine clasele imaginilor de antrenare yapp=y(1:number); %ytest- vectorul care contine clasele imaginilor de testare ytest=y(number+1:dim1); %preluare valoare numar vecini k=str2double(get(handles.edit4,'String')); tic %clasificare KNNR DS.input=xapp'; DS.output=yapp'; TS.input=xtest'; knnrParam.k=k; try [computedOutput] =knnr(DS, TS, knnrParam); catch error disp(error); errordlg('Numar vecini prea mare sau prea mic setul de date de antrenare',... 'Error'); enableButtons2(handles); end % timpul de clasificare KNNR timp=toc; % calculare performante accuracy=computeAccuracy(ytest,computedOutput)*100; perf=timp*(1-accuracy/100); % afisarea rezultatelor obtinute in EDITBOX-uri set(handles.edit5,'String',num2str(accuracy)); set(handles.edit6,'String',num2str(timp)); set(handles.edit7,'String',num2str(perf)); fclose all;enableButtons2(handles);

52

% hObject handle to pushbutton2 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) function edit5_Callback(hObject, eventdata, handles)% hObject handle to edit5 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hints: get(hObject,'String') returns contents of edit5 as text% str2double(get(hObject,'String')) returns contents of edit5 as a double % --- Executes during object creation, after setting all properties.function edit5_CreateFcn(hObject, eventdata, handles)% hObject handle to edit5 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles empty - handles not created until after all CreateFcns called % Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white');end function edit6_Callback(hObject, eventdata, handles)% hObject handle to edit6 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hints: get(hObject,'String') returns contents of edit6 as text% str2double(get(hObject,'String')) returns contents of edit6 as a double % --- Executes during object creation, after setting all properties.function edit6_CreateFcn(hObject, eventdata, handles)% hObject handle to edit6 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles empty - handles not created until after all CreateFcns called % Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white');end function edit7_Callback(hObject, eventdata, handles)

53

% hObject handle to edit7 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hints: get(hObject,'String') returns contents of edit7 as text% str2double(get(hObject,'String')) returns contents of edit7 as a double % --- Executes during object creation, after setting all properties.function edit7_CreateFcn(hObject, eventdata, handles)% hObject handle to edit7 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles empty - handles not created until after all CreateFcns called % Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white');end function edit8_Callback(hObject, eventdata, handles)% hObject handle to edit8 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hints: get(hObject,'String') returns contents of edit8 as text% str2double(get(hObject,'String')) returns contents of edit8 as a double % --- Executes during object creation, after setting all properties.function edit8_CreateFcn(hObject, eventdata, handles)% hObject handle to edit8 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles empty - handles not created until after all CreateFcns called % Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white');end % --- Executes during object creation, after setting all properties.function radiobutton8_CreateFcn(hObject, eventdata, handles)% hObject handle to radiobutton8 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles empty - handles not created until after all CreateFcns called % --- Executes during object deletion, before destroying properties.function uipanel12_DeleteFcn(hObject, eventdata, handles)% hObject handle to uipanel12 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB

54

% handles structure with handles and user data (see GUIDATA) % --- Executes during object deletion, before destroying properties.function radiobutton8_DeleteFcn(hObject, eventdata, handles)% hObject handle to radiobutton8 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % --- Executes on button press in pushbutton3 - creare vector trasaturifunction pushbutton3_Callback(hObject, eventdata, handles) disableButtons(handles); % numarul de clase utilizate pentru crearea vectorului de caracteristici clasa1=get(handles.radiobutton3,'Value'); clasa2=get(handles.radiobutton4,'Value'); clasa3=get(handles.radiobutton5,'Value'); clasa4=get(handles.radiobutton6,'Value'); %verificam sa nu avem selesctata numai o clasa if (((clasa1) && ~(clasa2) && ~(clasa3) && ~(clasa4))||((clasa2) &&... ~(clasa1) && ~(clasa3) && ~(clasa4))||((clasa3) && ~(clasa1)... && ~(clasa2) && ~(clasa4))||((clasa4) && ~(clasa1) && ~(clasa2)... && ~(clasa3))) errordlg('Trebuie sa selectati cel putin doua clase de imagini',... 'Error'); enableButtons1(handles); end; currentfolder=pwd;% in functie de clasele selectate preluam imaginile din directorul% corespunzator if ((clasa1)&&(clasa2)&&(~(clasa3))&&(~(clasa4))) dirImagini={strcat(currentfolder,'\cars\'),... strcat(currentfolder,'\persons\')}; clasa=[1,2]; elseif ((clasa1)&&(clasa3)&&(~(clasa2))&&(~(clasa4))) dirImagini={strcat(currentfolder,'\cars\'),... strcat(currentfolder,'\animals\')}; clasa=[1,3]; elseif ((clasa1)&&(clasa4)&&(~(clasa2))&&(~(clasa3))) dirImagini={strcat(currentfolder,'\cars\'),... strcat(currentfolder,'\garbage\')}; clasa=[1,4]; elseif ((clasa1)&&(clasa2)&&(clasa3)&&(~(clasa4))) dirImagini={strcat(currentfolder,'\cars\'),... strcat(currentfolder,'\persons\'),strcat(currentfolder,'\animals\')}; clasa=[1,2,3]; elseif ((clasa1)&&(clasa2)&&(clasa4)&&(~(clasa3))) dirImagini={strcat(currentfolder,'\cars\'),... strcat(currentfolder,'\persons\'),strcat(currentfolder,'\garbage\')}; clasa=[1,2,4]; elseif ((clasa1)&&(clasa3)&&(clasa4)&&(~(clasa2))) dirImagini={strcat(currentfolder,'\cars\'),... strcat(currentfolder,'\animals\'),strcat(currentfolder,'\garbage\')};

55

clasa=[1,3,4]; elseif ((clasa1)&&(clasa2)&&(clasa3)&&(clasa4)) dirImagini={strcat(currentfolder,'\cars\'),... strcat(currentfolder,'\persons\'),... strcat(currentfolder,'\animals\'),... strcat(currentfolder,'\garbage\')}; clasa=[1,2,3,4]; elseif ((clasa2)&&(clasa3)&&(~(clasa1))&&(~(clasa4))) dirImagini={strcat(currentfolder,'\persons\'),... strcat(currentfolder,'\animals\')}; clasa=[2,3]; elseif ((clasa2)&&(clasa4)&&(~(clasa1))&&(~(clasa3))) dirImagini={strcat(currentfolder,'\persons\'),... strcat(currentfolder,'\garbage\')}; clasa=[2,4];elseif ((clasa2)&&(clasa3)&&(clasa4)&&(~(clasa1))) dirImagini={strcat(currentfolder,'\persons\'),... strcat(currentfolder,'\animals\'),strcat(currentfolder,'\garbage\')}; clasa=[2,3,4];elseif ((clasa3)&&(clasa4)&&(~(clasa1))&&(~(clasa2))) dirImagini={strcat(currentfolder,'\animals\'),... strcat(currentfolder,'\garbage\')}; clasa=[3,4];end;% metodele folosite la formarea vectorului de trasaturi met1=get(handles.radiobutton8,'Value'); met2=get(handles.radiobutton9,'Value'); met3=get(handles.radiobutton10,'Value'); met4=get(handles.radiobutton11,'Value'); metoda=[met1 met2 met3 met4]; handles.metoda=metoda; numar_clase=size(clasa); fis=fopen('fisier_caracteristici.txt','w'); tic % extragerea trasaturilor din imaginile claselor selectate for i=1:numar_clase(2)numberOfLines = GiveNbOfLines(strcat('Lista.txt'));fid_imagesLst=fopen(strcat('Lista.txt')); for j=1:numberOfLines-1 imgName = numeImagine(fid_imagesLst); % citesc imaginea, o transformam din color in gray [imagine] = imread(strcat(dirImagini{i},imgName),'png'); imagine = im2double(imagine); imagine=rgb2gray(imagine); % aplicarea metodelor selectate asupra imaginilor din clasele selectate vect_caract=extractie_vect_trasaturi(met1,met2,met3,met4,imagine); clear imagine;% salvam rezultatul in fisier

56

lungime=size(vect_caract,2); for k=1:lungime fprintf(fis,'%.3f,', vect_caract(k)); end; fprintf(fis,'%d%c\n',clasa(i),',');end;progressbar(i/numar_clase(2));end;% timpul de extragere a caracteristicilortimp=toc;timestr = sec2timestr(timp);% afisare timpset(handles.edit9,'String',timestr);enableButtons2(handles);set(handles.radiobutton12,'Enable','on');set(handles.radiobutton13,'Enable','on');set(handles.pushbutton2,'Enable','on');handles.output=hObject;guidata(hObject, handles); % hObject handle to pushbutton3 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) function edit9_Callback(hObject, eventdata, handles)% hObject handle to edit9 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hints: get(hObject,'String') returns contents of edit9 as text% str2double(get(hObject,'String')) returns contents of edit9 as a double % --- Executes during object creation, after setting all properties.function edit9_CreateFcn(hObject, eventdata, handles)% hObject handle to edit9 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles empty - handles not created until after all CreateFcns called % Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white');end function disableButtons(handles)%change the mouse cursor to an hourglassset(handles.figure1,'Pointer','watch'); %disable all the buttons so they cannot be pressedset(handles.edit1,'Enable','off');

57

set(handles.edit4,'Enable','off');set(handles.pushbutton1,'Enable','off');set(handles.pushbutton2,'Enable','off');set(handles.pushbutton3,'Enable','off'); set(handles.radiobutton3,'Enable','off');set(handles.radiobutton4,'Enable','off');set(handles.radiobutton5,'Enable','off');set(handles.radiobutton6,'Enable','off');set(handles.radiobutton8,'Enable','off');set(handles.radiobutton9,'Enable','off');set(handles.radiobutton10,'Enable','off');set(handles.radiobutton11,'Enable','off'); function enableButtons1(handles)%change the mouse cursor to an arrowset(handles.figure1,'Pointer','arrow'); %enable all the buttons so they can be pressed% set(handles.edit1,'Enable','on');% set(handles.edit4,'Enable','on');set(handles.pushbutton1,'Enable','on');set(handles.pushbutton2,'Enable','on');set(handles.pushbutton3,'Enable','on'); set(handles.radiobutton3,'Enable','on');set(handles.radiobutton4,'Enable','on');set(handles.radiobutton5,'Enable','on');set(handles.radiobutton6,'Enable','on');set(handles.radiobutton8,'Enable','on');set(handles.radiobutton9,'Enable','on');set(handles.radiobutton10,'Enable','on');set(handles.radiobutton11,'Enable','on'); function enableButtons2(handles)%change the mouse cursor to an arrowset(handles.figure1,'Pointer','arrow'); %enable all the buttons so they can be pressedset(handles.edit1,'Enable','on');set(handles.edit4,'Enable','on');set(handles.pushbutton1,'Enable','on');set(handles.pushbutton2,'Enable','on');set(handles.pushbutton3,'Enable','on'); set(handles.radiobutton3,'Enable','on');set(handles.radiobutton4,'Enable','on');set(handles.radiobutton5,'Enable','on');set(handles.radiobutton6,'Enable','on');set(handles.radiobutton8,'Enable','on');set(handles.radiobutton9,'Enable','on');set(handles.radiobutton10,'Enable','on');set(handles.radiobutton11,'Enable','on'); % --- Executes on button press in pushbutton4 - preia imagine pentru

58

% clasificarefunction pushbutton4_Callback(hObject, eventdata, handles)% preluare imagine noua pentru clasificarea ei pe baza fisierului implicit% sau obtinut onlinecla(handles.axes1,'reset'); try[imagine_init,map]=imread('no_image.jpg');imshow(imagine_init,map,'parent',handles.axes1); [filename, pathname] = uigetfile({'*.png';'*.jpg';'*.bmp';'*.*'}, 'Pick an Image File');S = imread([pathname,filename]);imshow(S,[0 255]);handles.S = S; catch error disp(error); selection=questdlg('Nu a fost selectata nici o imagine.Stop proces?',... 'Stop process',... 'Yes','No','Yes'); switch selection, case 'Yes' [imagine_init,map]=imread('no_image.jpg'); imshow(imagine_init,map,'parent',handles.axes1); set(handles.pushbutton5,'Enable','off'); return case 'No' pushbutton4_Callback(hObject, eventdata, handles); return end; set(handles.pushbutton5,'Enable','on'); end; set(handles.pushbutton5,'Enable','on'); handles.output=hObject;guidata(hObject, handles); % hObject handle to pushbutton4 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % --- Executes on button press in pushbutton5 - clasifica imaginefunction pushbutton5_Callback(hObject, eventdata, handles) S=handles.S;S=im2double(S);S=rgb2gray(S);% fisier online sau implicit?stare12=get(handles.radiobutton12,'Value');stare13=get(handles.radiobutton13,'Value');% in functie de optiunea selectata extrage caracteristicile de pe noua% imagine si o clasificaif (stare12)tic% extragere trasaturi

59

vect_caracteristici=extractie_vect_trasaturi(1,0,1,1,S); timp1=toc;set(handles.text41,'String',strcat(num2str(timp1),' s'));%preia datele din fisierul implicit[x y]=preiaDatelePtPrel(strcat(pwd,... '\fisier_caracteristici_random_implict.txt')); tic% computedOutput=knnclassify(double(vect_caracteristici),xapp,yapp,1); dim1=size(x); x=x(:,1:dim1(2)-1); % clasificare KNNR DS.input=x'; DS.output=y'; TS.input=double(vect_caracteristici)'; knnrParam.k=1; [computedOutput] =knnr(DS, TS, knnrParam); % timp clasificare timp2=toc; % afisarea rezultatelor obtinute - clasa, timp extractie trasaturi, % timp clasificare set(handles.text42,'String',strcat(num2str(timp2),' s')); if (computedOutput==1) clasa='Masini'; elseif (computedOutput==2) clasa='Pietoni'; elseif (computedOutput==3) clasa='Animale'; elseif (computedOutput==4) clasa='Garbage'; end; set(handles.text43,'String',clasa);% elseif (stare13) tic% extragerea trasaturilor noii imagini prin metodele selectate pentru% formarea fisierului onlinemetoda=handles.metoda;vect_caracteristici=extractie_vect_trasaturi(metoda(1),metoda(2),... metoda(3),metoda(4),S);% timp extractie trasaturitimp1=toc;set(handles.text41,'String',strcat(num2str(timp1),' s'));% preia datele din fisierul obtinut online pentru clasificare[x y]=preiaDatelePtPrel(strcat(pwd,'\fisier_caracteristici_random.txt')); tic% computedOutput=knnclassify(double(vect_caracteristici),xapp,yapp,1); dim1=size(x); x=x(:,1:dim1(2)-1); % clasificare KNNR DS.input=x'; DS.output=y';

60

TS.input=double(vect_caracteristici)'; knnrParam.k=1; [computedOutput] =knnr(DS, TS, knnrParam); % timp clasificare KNNR timp2=toc; % afisare timp clasificare in EDITBOX-ul aferent set(handles.text42,'String',strcat(num2str(timp2),' s'));% stabilirea clasei din care face parte imaginea de test if (computedOutput==1) clasa='Masini'; elseif (computedOutput==2) clasa='Pietoni'; elseif (computedOutput==3) clasa='Animale'; elseif (computedOutput==4) clasa='Garbage'; end; set(handles.text43,'String',clasa);end; guidata(hObject, handles);% hObject handle to pushbutton5 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % --- Executes on button press in radiobutton12 - fisier implicitfunction radiobutton12_Callback(hObject, eventdata, handles)%setarea starilor ridiobutoanelor 12 si 13stare13=get(handles.radiobutton13,'Value');stare12=get(handles.radiobutton12,'Value');if (stare12) set(handles.radiobutton13,'Value',0);elseif (stare13) set(handles.radiobutton12,'Value',0);elseif (~(stare12)) set(handles.radiobutton13,'Value',1);end; % hObject handle to radiobutton12 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hint: get(hObject,'Value') returns toggle state of radiobutton12 % --- Executes on button press in radiobutton13 - fisier obtinut onlinefunction radiobutton13_Callback(hObject, eventdata, handles)%setarea starilor ridiobutoanelor 12 si 13stare13=get(handles.radiobutton13,'Value');stare12=get(handles.radiobutton12,'Value');if (stare13) set(handles.radiobutton12,'Value',0);

61

elseif (stare12) set(handles.radiobutton13,'Value',0);elseif (~(stare13)) set(handles.radiobutton12,'Value',1);end; % hObject handle to radiobutton13 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hint: get(hObject,'Value') returns toggle state of radiobutton13 Codul Matlab pentru metodele de extragere folosite în aplicaţia GUI

function [vect_caracteristici1]=metoda1(imagine) vect_wavelet=compresie_wavelet(imagine,3,'bior1.3');% metoda I% aplicare CombFirst4Moments, MultiscaleHistograms, TamuraTextures% asupra transformatei wavelet a imaginiifirst4moments = CombFirst4Moments(vect_wavelet);multiscalehist = MultiScaleHistograms(vect_wavelet);TamuraFeatures = TamuraTextures(vect_wavelet);vect_caracteristici1=[first4moments,multiscalehist,... TamuraFeatures];clear first4moments;clear multiscalehist;clear TamuraFeatures;

function [vect_caracteristici2]=metoda2(imagine)% aplicare fft asupra imaginii originale% metoda II fftTrans=FourierTransform(imagine);% % aplicare CombFirst4Moments, MultiscaleHistograms, TamuraTextures% % asupra transformatei wavelet a transformatei FFTvect_wavelet=compresie_wavelet(fftTrans(:,:,1),3,'bior1.3');first4moments = CombFirst4Moments(vect_wavelet);multiscalehist = MultiScaleHistograms(vect_wavelet);TamuraFeatures = TamuraTextures(vect_wavelet);vect_caracteristici2=[first4moments,multiscalehist,... TamuraFeatures]; clear first4moments;clear multiscalehist;clear TamuraFeatures;

function [vect_caracteristici3]=metoda3(imagine)% % metoda III% % aplicate CombFirst4Moments, MultiscaleHistograms, TamuraTextures si% % transformata Radon asupra imaginii originalefirst4moments = CombFirst4Moments(imagine);multiscalehist = MultiScaleHistograms(imagine);

62

TamuraFeatures = TamuraTextures(imagine);radonTrans = RadonTransformStatistics(imagine);vect_caracteristici3=[first4moments,multiscalehist,... TamuraFeatures,radonTrans]; clear first4moments;clear multiscalehist;clear TamuraFeatures;clear radonTrans;

function [vect_caracteristici4]=metoda4(imagine)% metoda IV% % aplicare Zernike polinomials asupra imaginii originalezvalues = ZernikePolynomials(imagine)*1000;vect_caracteristici4=zvalues; clear zvalues;

Codul Matlab pentru extracţia trăsăturilor din fiecare imagine în funcţie de metodele alese în aplicaţia GUI

function [vect_caract]=... extractie_vect_trasaturi(met1,met2,met3,met4,imagine)% met1 - 0 1 daca metoda I este folosita pentru formarea vectorului de% trasaturi% met2 - 0 1 daca metoda II este folosita pentru formarea vectorului de% trasaturi% met3 - 0 1 daca metoda III este folosita pentru formarea vectorului de% trasaturi% met4 - 0 1 daca metoda IV este folosita pentru formarea vectorului de% trasaturi% vect_caract- vectorul de caracteristici obtinut in urma plicarii% metodelor de extractie asupra imainii if ((met1)&&(~(met2))&&(~(met3))&&(~(met4))) vect_caract=metoda1(imagine); elseif ((met2)&&(~(met1))&&(~(met3))&&(~(met4))) vect_caract=metoda2(imagine); elseif ((met3)&&(~(met1))&&(~(met2))&&(~(met4))) vect_caract=metoda3(imagine); elseif ((met4)&&(~(met1))&&(~(met2))&&(~(met3))) vect_caract=metoda4(imagine); elseif ((met1)&&(met2)&&(~(met3))&&(~(met4))) vect_caract=[metoda1(imagine),metoda2(imagine)]; elseif ((met1)&&(met3)&&(~(met2))&&(~(met4))) vect_caract=[metoda1(imagine),metoda2(imagine)]; elseif ((met1)&&(met4)&&(~(met2))&&(~(met3))) vect_caract=[metoda1(imagine),metoda4(imagine)];

63

elseif ((met2)&&(met3)&&(~(met1))&&(~(met4))) vect_caract=[metoda2(imagine),metoda3(imagine)]; elseif ((met2)&&(met4)&&(~(met1))&&(~(met3))) vect_caract=[metoda2(imagine),metoda4(imagine)]; elseif ((met3)&&(met4)&&(~(met1))&&(~(met2))) vect_caract=[metoda3(imagine),metoda4(imagine)]; elseif ((met1)&&(met2)&&(met3)) vect_caract=[metoda1(imagine),metoda2(imagine),... metoda3(imagine)]; elseif ((met1)&&(met2)&&(met4)&&(~(met3))) vect_caract=[metoda1(imagine),metoda2(imagine),... metoda4(imagine)]; elseif ((met1)&&(met3)&&(met4)&&(~(met2))) vect_caract=[metoda1(imagine),metoda3(imagine),... metoda4(imagine)]; elseif ((met2)&&(met3)&&(met4)&&(~(met1))) vect_caract=[metoda2(imagine),metoda3(imagine),... metoda4(imagine)]; elseif ((met1)&&(met2)&&(met3)&&(met4)) vect_caract=[metoda1(imagine),metoda2(imagine),... metoda3(imagine),metoda4(imagine)]; end;

64