UNIVERSITATEA TEHNICA DIN CLUJ-NAPOCAFACULTATEA DE ELECTRONICA, TELECOMUNICATII SI

TEHNOLOGIA INFORMATIEISpecializarea Tehnologii i sisteme de Telecomunicaii

Contribuii la analiza i implementarea unormetode de extragere a caracteristicilor din

imagini n vederea clasificrii lorLucrare de licen

PRESEDINTE COMISIE, DECAN,Prof. dr. ing Monica Borda Prof.dr.ing. Marina OPA

CONDUCATOR, ABSOLVENT,Asist. ing. Anca Aptean Alexandru Mihu

2010

UNIVERSITATEA TEHNICA DIN CLUJ-NAPOCAFACULTATEA DE ELECTRONICA, TELECOMUNICATII SI

TEHNOLOGIA INFORMATIEICATEDRA DE COMUNICAII

Titlul temei: Contribuii la analiza i implementarea unor metodede extragere a caracteristicilor din imagini n vederea clasificrii lor

Enunul lucrarii de licen:

Proiectul trebuie s conin metodologia de alegere a caracteristicilor extrase din imagini,implementarea unei aplicaii Matlab de extragere a trsturilor din imaginile bazei de date pentruclasificarea acestora. Obiectivele sunt documentarea metodelor de extragere trsturi dejaexistente, clasificarea imaginilor pe baza trsturilor extrase i realizarea practic a unei aplicaiide extragere trsturi i clasificare imagini.

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 Aptean

Declaraia autorului

Subsemnatul declar prin prezenta c ideile, partea de implementare i experimental,rezultatele, analizele i concluziile cuprinse n aceast lucrare constituie efortul meu propriu, maipuin acele elemente ce nu-mi aparin, pe care le indic i le recunosc ca atare.

Declar de asemenea, c dup tiina mea, lucrarea n aceast form este original i nu a mai fostniciodat prezentat sau depus n alte locuri sau altor instituii dect cele indicate n mod expresde mine.

n calitate de autor, cedez toate drepturile de utilizare i modificare a lucrrii de licen ctreUniversitatea Tehnic din Cluj-Napoca.

Cluj-Napoca, 24 iunie 2010

ABSOLVENT,Alexandru Mihu

FACULTATEA DE ELECTRONIC, TELECOMUNICAII I TEHNOLOGIA INFORMAIEI

1. absolvent Mihu Alexandru Ioan

2. asist. ing. Aptean Anca

SINTEZA LUCRARII DE LICEN

Contribuii la analiza i implementarea unor metode de extragere a caracteristicilor(trsturilor) din imagini n vederea clasificrii lor

Imaginile digitale, costul redus de realizare i stocare al acestora, precum i utilizarea lorn tot mai multe domenii ale tiinei i ingineriei, au introdus o cretere a cererii de aplicaii deanaliz i clasificare a imaginilor cu o precizie ct mai mare i ntr-un timp ct de poate de scurt.

Lucrarea urmrete extracia de trsturi din imaginile ce compun baza de date pentru aobine o acuratee de clasificare (KNN) ct mai mare. Extracia trsturilor s-a realizat prinmetode deja existente, folosite n cadrul clasificatorului WND-CHARM. Acest clasificator faceparte din mediul OME (Open Microscopy Environment). Numrul de trsturi extrase a fostredus prin renunarea la metodele ineficiente de extragere n ceea ce privete performanele declasificare la 318 atribute pe imagine fa de 1024 atribute pe imagine folosite pentru formareavectorului de trsturi din cadrul clasificatorului WND-CHARM. Astfel, timpul de extragere altrsturilor tuturor imaginilor din baza de date, precum i timpul de clasificare au fost micoratesemnificativ (de la 48 de ore la 3 ore i 11 minute , respectiv de la 2 secunde la mai puin de osecund).

Prin modificarea bazei de imagini aplicaia realizat poate fi utilizat n probleme dedetecie sau recunoatere din diverse domenii.

ABSTRACT

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

This thesis follows feature extraction from database images to obtain a high KNNclasification accuracy. Feature extraction was achieved by existing methods used in WND-CHARM classifier, which is part of the OME environment (Open Microscopy Environment).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 extractionmethods in terms of clasification performance. Thus, the time needed for feature extraction forall database images and classification time was reduced significantly (from 48 hours to 3 hours,respectively from 2 seconds to less than one second).

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

CURRICULUM VITAE

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

Studies: High School: Colegiul Naional Lucian Blaga, Sebe

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, AlbaTelephone: 0746 041 672E-mail address: mihu_alexandru_ioan@yahoo.com

I the undersigned, Alexandru Ioan Mihu, declare that all the data in this Curriculum Vitaecan be used by The Faculty of Electronics, Telecommunications and Information Technology of theTechnical University of Cluj-Napoca, for promotional pourposes and professional orientation, in thefollowing 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 ..................................................................................3

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

2.2.4 Aplicaii ale wavelet-urilor ........................................................................................5

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

2.3.1 Definire transformat FFT.........................................................................................6

2.3.2 Aplicaii ale transformatei FFT .................................................................................6

2.4 Transformata Radon............................................................................................................6

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

2.4.2 Aplicaii ale transformatei Radon ..............................................................................7

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

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

2.5.2 Contrastul...................................................................................................................8

2.5.3 Direcionalitatea ........................................................................................................8

2.6 Polinoamele Zernike............................................................................................................9

2.6.1 Definirea polinoamelor Zernike.................................................................................9

2.6.2 Aplicaii ale polinoamelor Zernike...........................................................................10

2.7 Histograme multiscalare ...................................................................................................10

2.8 Filtre orientate n patru direcii pentru obinerea "primelor 4 momente"........................10

2.9 Algoritmul KNN................................................................................................................10

2.9.1 Avantajele algoritmului KNN...................................................................................11

2.9.2 Dezavantajele algoritmului KNN .............................................................................12

2.10 Fiiere MEX (MEX-files).................................................................................................12

3. Implementarea soluiei adoptate ...............................................................................................13

3.1 Baza de imagini .................................................................................................................14

3.2 Metoda de extragere a caracteristicilor............................................................................15

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

3.2.2 Metoda de extragere a caracteristicilor n lucrarea de fa....................................18

3.2.3 Evaluarea trsturilor n Weka...............................................................................21

3.3.4 Evaluarea trsturilor n Matlab .............................................................................22

3.3 Determinarea parametriilor transformatei Wavelet .........................................................23

3.4 Modul de mprire a datelor pentru nvare i testare...................................................24

3.5 mbuntirea performanelor...........................................................................................25

3.5.1 Reducerea numrului de trsturi extrase din fiecare imagine.35

3.5.2 Transformarea aplicaiei ntr-un executabil ............................................................27

3.6 Interfaa grafic a aplicaiei .............................................................................................27

3.6.1 Extragerea trsturilor ............................................................................................28

3.6.2 Clasificarea imaginilor ............................................................................................28

3.6.3 Testarea clasificatorului KNN i cu alte imagini dect cele din baza de date ........28

4. Rezultate experimentale ............................................................................................................28

4.1 Rezultate experimentale Weka...........................................................................................29

4.2 Rezultate experimentale din Matlab i din aplicaia executabil

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

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

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

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

Codul Matlab al funciei de transformare Wavelet......................................................................39

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

Codul Matlab pentru obinerea fiierului cu vectorul de trsturi...............................................39

7.3 Anexa 3 ..............................................................................................................................39

Codul Matlab al funciei de extragere trsturi ...........................................................................39

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

Codul Matlab pentru obinerea fiierului cu liniile vectorului de caracteristici permutate.........41

Codul Matlab pentru funcia 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 aplicaiei GUI ....................................................................................................44

Codul Matlab pentru metodele de extragere folosite n aplicaia GUI ........................................63

Codul Matlab pentru extracia trsturilor din fiecare imagine n funcie de metodele alese naplicaia GUI.................................................................................................................................64

Lista de figuri

Figura 1.1 Schema procesului de recunoatere 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 reconstrucie 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- ecuaia (7) i (9)........................................7Figura 2.5 Valorile Zernike n unitatea de disc ...............................................................................9Figura 3.1 Imagini din baza de date ..............................................................................................14Figura 3.2 Schema bloc a metodelor de extragere a trsturilor ...................................................15Figura 3.3 Schema de formare a vectorului de trsturi din cadrul WND-CHARM....................17Tabel 3.1 Metode de extragere a trsturilor analizate .................................................................20Figura 3.5 Schema de formare a vectorului de trsturi................................................................20Figura 3.6 Structura fiierului ARFF la modul general.................................................................21Figura 3.7 Structura fisierului ARFF utilizat n acest lucrare .....................................................21Figura 3.8 Matricele de confuzie pentru nvare, respectiv testare..............................................22Figura 3.9 Transformata Wavelet a unei imagini..........................................................................24Figura 3.10 Schema bloc a clasificrii KNN.................................................................................25Figura 3.11 Schma bloc urmat de toolbox-ul deploytool ............................................................27Figura 3.12 Interfaa grafic a lucrrii...........................................................................................27Figura 4.1 Matrice de confuzie Weka (numrul de vecini=1) ......................................................29Figura 4.2 Matricele de confuzie pentru k=3 (a),..........................................................................29Figura 4.3 Matricele de confuzie pentru setul de testare (k=1,3 i 5) obinute n Weka...............30Figura 4.4 Matricele de confuzie pentru setul de testare obinute n Matlab ................................30Figura 4.5 Graficul timpului de clasificare n funcie de numrul de trsturi .............................31Figura 4.6 Graficul timpului de clasificare n funcie de numrul de trsturi .............................31Figura 4.7 Graficul timpului de extragere coeficieni n funcie de numrul de trsturi .............32Figura 4.8 Graficul acurateii n funcie de numrul de trsturi ..................................................35

Lista de tablele

Tabel 3.1 Metode de extragere a trsturilor analizate .................................................................20Tabel 4.1 Rezultate obinute n Matlab .........................................................................................33Tabel 4.2 Rezultate obinute prin transformarea aplicaiei ntr-un executabil ..............................34

11. Stadiul actual

Stadiul actual n ceea ce privete recunoaterea formelor i clasificarea automat aimaginilor este unul avansat, reuindu-se dezvoltarea unor aplicaii care au o acuratee aclasificrii foarte ridicat i un timp de clasificare sau de detecie foarte bun (detecie sauclasificare n timp real), i care ncet-ncet promit a se apropia ca performan de modul naturalcu care fiina uman trateaz aceast problem.

Imaginile digitale, stocarea ieftin i utilizarea acestora n tot mai multe domenii aletiinei i ingineriei, au introdus o cretere a cererii de aplicaii de analiz i clasificare aimaginilor cu o precizie ct mai mare. Aceste aplicaii includ teledetecia, descris n [1],recunoaterea facial, despre care putei gsi informaii n [2], [3] sau [4] i clasificareaimaginilor medicale i biologice [5], [6], [7] sau [8].

Sistemele de vedere artificial sunt proiectate dup modelul sistemelor biologice, nspecial cel uman. n dezvoltarea unor astfel de sisteme ne lovim, de foarte multe probleme. Ceamai important dintre ele este imposibilitatea de a reproduce n sistemele artificiale, modulnostru de gndire. Pentru noi oamenii, recunoaterea unui obiect se face cu uurin, chiar dacacel obiect nu este vzut n ntregime, dar n general nu putem s explicm tiinific cum amreuit s realizm recunoaterea. Prin urmare, nu putem dezvolta un algoritm sau o tehnic deinteligen artificial care descrie iterativ i exact acest proces.

Dei n ultimii ani au atras o atenie deosebit, analiza i clasificarea imaginilor suntdeocamdat considerate probleme competitive n sistemele de prelucrare i clasificare pe bazaconinutului imaginilor (CBIR - Content Based Image Retrieval), datorit complexitiisubiectului n ceea ce privete imaginile reale i dificultatea de extragere cantitativ a trsturilorde similitudine sau difereniere dintre imagini. Aceste trsturi pot include caracteristici deculoare, textur sau form, descriptori ce sunt obinui global prin extragerea informaiilor pebaza mediei histogramelor de culoare (pentru caracteristicile de culoare), pe baza granularitii,contrastului i directivitii imaginilor (pentru caracteristicile de textur) i pe baza trsturilor decurbur, momente invariante, circularitatea i excentricitatea imaginilor (pentru caracteristicilede form). Cu toate acestea, extragerea trsturilor din imagini se face diferit n funcie dedetaliile particulare ale aplicaiei i performanele dorite.

n lucarea de fa sunt propuse mai multe metode deja existente de extragere acaracteristicilor pentru formarea vectorului de trsturi i clasificarea imaginilor pe bazavectorului obinut.

Scopul principal al acestei lucrri este testarea mai multor metode de extragere atrsturilor, nu neaparat obinerea unor performane superioare. Pentru a vedea eficienametodelor de extragere s-a realizat clasificarea imaginilor pe baza vectorului de caracteristiciprin intermediul clasificatorului IBk din Weka (echivalentul KNN- k nearest neighbor) i KNNimplementat n Matlab. Pentru realizarea acestor obiective m-am inspirat din mai multe referine,dar cea mai semnificativ este metodologia de extragere a trsturilor pentru formarea vectoruluide caracteristici din cadrul clasificatorului WND-CHARM (Weighted Neighbor Distances usinga Compound Hierarchy of Algorithms Representing Morphology - distana ponderat dintrevecini utiliznd o ierarhie compus de algoritmi morfologici). Pentru mai multe detalii a seconsulta [9].

Trsturile vectorului de caracteristici includ descompunerea polinomial (reprezentatde polinoamele Zernike), statisticile pixelilor (media, deviaia standard, oblicitatea, planitatea,histograme multiscalare) i caracteristicile de textur (contrast, granularitate i direcionalitate).Aceste caracteristici au fost extrase din imaginile pe nivele de gri, precum i din imaginilerezultate 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 transformataRadon a imaginii pe nivele de gri, care este folosit pentru extragerea informaiei spaiale.

Metodele aplicate asupra imaginilor pentru formarea vectorului de trsturi fac parte dinmetodologia descris n [9]. Contribuia adus la formarea vectorului de trsturi const n

2selectarea din varietatea de metode de extragere doar a celor care ofer o performan declasificare mai ridicat. Pentru o aplicare eficient a transformatei Wavelet s-au stabilit valorileparametrilor (familia de wavelet i nivelul de descompunere wavelet). Celelate metode utilizate,precum i implementrile lor n Matlab pot fi descrcate gratuit i utilizate n scopuri tiinifice ide cercetare de pe site-ul: http://www.openmicroscopy.org.

Vectorul de trsturi este utilizat apoi pentru clasificarea imaginilor de test ntr-un set declase de imagini predefint (clasa maini, pietoni, animale i garbage) cu ajutorul utilitaruluiWeka. Deoarece apelarea din Matlab a utilitarului Weka este foarte complicat i datoritnecesitii utilizrii unui clasificator n interfaa grafic realizat, s-a ales implementarea nMatlab a unui algoritm de clasificare. Astfel, luarea deciziei asupra clasei imaginii test s-arealizat cu algoritmul KNN. Din punct de vedere al evaluatorului s-a ales folosirea KNNdeoarece este un clasificator rapid, eficient i uor de implementat. Pentru a nu permiteclasificatorului s nvee inclusiv ordinea de preluare a imaginilor (deoarece clasificatorul preluape rnd cele patru clase) s-a realizat permutarea imaginilor din vectorul de caracteristici.

Din punct de vedere aplicativ, lucrarea conine o interfa grafic dezvoltat cu ajutorultoolbox-ului GUIDE (Graphical User Interface Design Environment) din Matlab. Aceastaplicaie permite utilizatorului s selecteze diferite variante de formare a vectorului de trasturi,precum i posibilitatea testrii clasificatorului KNN cu alte imagini dect cele din baza de date.Vectorul de trsturi poate avea, n funcie de metodele alese, o dimensiune minim de 72caracteristici i maxim de 318 caracteristici. Toate atributele sunt extrase pe baza imaginilor penivele de gri, astfel informaiile de culoare nefiind utilizate.

2. Fundamentare teoretic

2.1. Introducere

n realizarea unei aplicaii de recunoatere a formelor i clasificare automat a imaginilor,dup cum se poate observa n figura 1.1, n general se parcurg urmatoarele etape:a) preprocesarea imaginii - etap n care se realizeaz mbuntirea calitii imaginilor prinaplicarea unor algoritmi DIP (digital image processing).[10]

Deoarece imaginile din baza de date, format pentru acest lucrare, nu necesit altembunatiri ale calitii, n acest etap s-a realizat doar conversia imaginilor color n imagini penivele de gri. n multe situaii pentru clasificarea imaginilor sunt extrase pe lng trsturile detextur i de form, i cele de culoare. S-a renunat la aceste caracteristici deoarece nu se poaterealiza o difereniere a claselor pe baza culorii.b) extragerea atributelor sau descriptorilor de imagine - reprezint etapa cea mai importantdeoarece influeneaz n mod direct performanele de clasificare.[10]

Tipul trsturilor folosite n clasificare i descrise n aceast lucrare se mpart n treicategorii: descompunere polinomial, statisticile pixelilor i textura. n descompunereapolinomial este generat un polinom ce aproximeaz imaginea n funcie de gradul de fidelitate,iar coeficienii acestui polinom sunt utilizai ca descriptori ai coninutului imaginii. Trsturilede textur se refer la variaia n intensitate ntre pixelii imaginii pentru diferite direcii irezoluii. Statisticile pixelilor se bazeaz pe distribuia pixelilor din imagine i includ histogramei momente.

n aceast etap, pentru extragerea trsturilor, asupra imaginilor s-a aplicat transformataWavelet (transformata Wavelet a imaginii pe nivele de gri i a transformatei FFT a imaginii penivele de gri), iar din rezultatele obinute au fost extrase caracteristicile de statistic apixelilor("primele 4 momente", histogramele multiscalare) i de textur (caracteristicile Tamura).Din imaginile originale (imaginile pe nivele de gri), fr a aplica asupra acestora nici otransformat, sunt extrase caracteristicile de statistic a pixelilor i de textur menionate maisus, precum i cele de descompunere polinomial (polinoamele Zernike). Din vectorul de

3trsturi mai fac parte i rezultatele obinute n urma transformatei Radon a imaginii pe nivele degri.c)evaluarea atributelor sau descriptorilor - este o etap n care sunt evaluate datele din vectorulde caracteristici i care are ca rezultat n mod obinuit, o valoare numeric unidimensional saumultidimensional (un vector), care relev distana vectorului de trsturi fa de granieleregiunilor sau fa de "bornele de clasificare".[10]

Evaluarea atributelor s-a realizat cu ajutorul clasificatorului KNN, prin testareaevaluatorului cu datele de nvare.d) clasificarea imaginii - este etapa care mbin rezultatele msurtorilor multiple anterioare, itotodat etapa final.

Prin clasificare se stabilete apartenena formei, obiectului sau imaginii - descris prinvectorul de trsturi, la un setul de clase de imagini predefinite.[10]Clasificarea imaginilor de test, precum i stabilirea atributelor imaginilor care ne ofer cea maibun performan s-a realizat cu ajutorul algoritmului KNN.

Figura 1.1 Schema procesului de recunoatere 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 lamprirea funciilor de timp continue n unde mai mici.

Ecuaia transformatei wavelet continu este urmtoarea:

XWT(,s)= ||() (1)

unde x(t) este semnalul ce trebuie analizat, (t) este wavelet-ul mam sau funcia de baz [11].Toate funciile folosite n transformare sunt derivate din funcia de baz prin translatare (shiftare)i scalare (dilatare sau compresie). Parametrul de translaie se refer la locaia funciei waveletn timpul parcurgerii semnalului, acesta corespunznd informaiei de timp a transformatei.Parametrul de scalare s este definit ca |1/frecven| i corespunde informaiei de frecven.Scalarea fie dilateaz (extinde) sau comprim semnalul. n prelucrrile de imagini, de obicei, sedorete compresia lor, pentru ca timpul necesar prelucrrii s fie ct mai redus.Pe o scar larg de frecvene joase semnalul este dilatat, fiind furnizate detaliile ascunse dinsemnal, n timp ce pe o scar redus (frecvene nalte) semnalul este comprimat, furnizndu-seinformaia global referitoare la semnal.Transformata Wavelet realizeaz convoluia semnalului i prelucrarea acestuia cu funcia debaz.

2.2.2 Transformata Wavelet discret

Transformata Wavelet discret (DWT- discrete wavelet transform) este o versiunesimplificat a transformrii wavelet continu, bazat pe codarea n sub-band. Avantajul acesteitransformate const n simplitatea implementrii, reducerea timpului de execuie i nivelul maisczut de resurse necesare.

La transformata CWT, semnalele sunt analizate folosind un set de funcii de baza care

4realizeaz o simpl scalare i translaie. n cazul transformatei DWT, o reprezentare n domeniultimp a unui semnal digital este obinut prin utilizarea tehnicilor de filtrare digital, semnalul(imaginea) ce trebuie analizat fiind trecut prin filtre cu diferite frecvene de tiere la nivelediferite.

Transformata DWT este realizat prin filtrri trece jos i filtrri trece sus succesive, ale unuisemnal 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 numr ntreg, filtrarea trece joseste realizat de blocul G0, la ieirea lui obinnd aproximarea grosier a coeficienilor(notata[n]) , iar filtrarea trece sus este realizat de H0, la iesire obinnd informaia detaliat (notatd[n]).

Filtrele care mpart banda n jumtate produc semnale ce ocup doar jumtate din bandade frecven. Filtrarea i descompunerea vor continua pn cnd se ajunge la nivelul dorit,numrul maxim de nivele de descompunere depinznd de lungimea semnalului (dimensiuneaimaginii).

Reconstrucia semnalului original pe baza coeficieniilor transformatei DWT esteprocesul invers descompunerii (figura 2.2).

Figura 2.2 Arborele Mallat cu primele trei nivele de reconstrucie ale semnalului original[11]

n Figura 2.2, d[n] reprezint coeficienii de detaliu ai semnalului, a[n] aproximrilegrosiere, iar blocurile H1 i G1 reprezint filtrele trece sus, respectiv filtrele trece jos de sintetizarea semnalului original.

Procesul de reconstrucie al semnalului original continu pn cnd este atins numrul denivele de descompunere ale semnalului.

5Condiiile ce trebuie ndeplinite pentru a avea o reconstrucie perfect sunt:

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

G0(z)*G1(z)+H0(z)*H1(z)=2 (3)unde G0(z) i G1(z) sunt filtrele trece jos de analiz, respectiv de sintez, iar H1(z)i H0(z) suntfiltre trece sus de analiz, respectiv de sintez[11].

Prima condiie impune ca reconstrucia s se fac fr alias, iar cea de-a doua condiieimpune ca distorsiunile de amplitudine sa aib valoarea egal cu 1.

2.2.3 Familii de wavelet-uri:

Exist un anumit numr de funcii de baz care pot fi folosite ca funcii mam pentrutransformata wavelet, dar pentru utilizarea eficient a acestora, trebuie luate n consideraredetaliile particulare ale aplicaiei care folosete 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 funcii wavelet. Wavelet-ul Haar este unul din celemai vechi si simple wavelet-uri, de aceea orice discuie despre wavelet-uri ncepe cu acesta.Pentru mai multe detalii legate de principalele tipuri de wavelet-uri a se consulta [12].

2.2.4 Aplicaii ale wavelet-urilor

Exist o gam larg de aplicaii pentru transformarea wavelet, ele fiind utilizate n diferitedomenii, de la procesarea semnalelor pn la domeniul biometriei.

Wavelet-urile au un rol important n compresia datelor, n vederea mbunatiriiperformanelor 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. Dintreprincipalele tipuri de transformate aplicate imaginilor n vederea compresiei lor (ex. transformatacosinus discret, transformata Fourier discret 2D etc.), transformata wavelet asigur asigur ofoarte bun rat de compresie.

Transformata Wavelet este aplicat n aceast lucrare pe imaginile pe nivele de gri,precum i pe imaginea obinut n urma aplicrii transformatei FFT asupra imaginii pe nivele degri. Parametrii transformatei, nivelul de descompunere i familia wavelet, au fost stabiliiparcurgnd urmtoarele etape:

6a) extragerea trsturilor imaginilor din baza de date cu metoda I (vezi figura 3.5 pentru maimulte detalii) pentru diferite nivele de descompunere wavelet (36) i pentru diferite familii dewavelet-uri.

b) clasificarea imaginilor pe baza vectorului de trsturi obinut prin metoda de mai sus pentru aobserva care nivel, respectiv familie wavelet ofer o performan de clasificare ct mai bun.Wavelet-urile sunt folosite att n metoda I de extragere a trsturilor (reprezentat de metodadescris mai sus), precum i n metoda II de extragere a trsturilor (vezi figura 3.5)

2.3 Transformata FFT

FFT este abrevierea din limba englez pentru fast Fourier transform (transformataFourier rapid), fiind un algoritm eficient de calcul al transformatei DFT - discrete Fouriertransform (transformata Fourier discret), precum i a inversei sale IDFT (inverse discret FourierTransform).

2.3.1 Definire transformat FFT

FFT produce exact aceleai rezultate ca i DFT, singura diferen fiind reprezentat derapiditatea transformatei FFT.

Fie ,, , , numere complexe. Transformata DFT este definit de urmtoareaformul:

(+ 1) = (+ 1) , k=0,1, ,N-1 (4),iar inversa ei IDFT este:

(+ 1) = (+ 1) , n=0,1, ,N-1 (5),

unde j este unitatea imaginar, = i N= lungime(x) [13].Evalund ecuaia (4), observm c aceasta necesit operaii: sunt N ieiri i fiecare ieirenecesit o sum de N termeni. Transformata FFT reprezint orice metod de obtinere a aceluiairezultat ca i DFT n N log N operaii. Pentru mai multe informaii legate de transformata FFT itipurile de algoritmi FFT a se consulta [13],[14] sau [15].

n lucrarea de fa transformata FFT este utilizat n cadrul metodei II de extragere atrsturilor, fiind aplicat asupra imaginii pe nivele de gri, iar apoi asupra acesteia se va aplicatransformata Wavelet (vezi figura 3.5 pentru mai multe detalii).

2.3.2 Aplicaii ale transformatei FFT

Aplicaiile transformatei FFT sunt urmatoarele:- aproximri pe baza polinoamelor trigonometrice, compresia datelor (ex. MP3)- analiza spectral a semnalelor- filtrare- rspunsul n frecven a unui sistem- ecuaiile parial difereniale- convoluia n domeniul frecven: - intercorelare

- multuplicarea de numere ntregi mari- multiplicarea simbolic a polinoamelor

2.4 Transformata Radon

Transformata Radon i transformata Hough sunt strns legate una de cealalt, Radon fiindo form particular a transformatei Hough.

72.4.1 Definirea transformatei Radon

O reprezentare util a unei drepte este ecuaia sa n coordonate polare: + = (6)

unde unde reprezint distana dintre dreapt i origine, iar este unghiul dintre axa x pozitivi dreapta [16].Transformata Radon se definete ca integral de-a lungul unei drepte inclinate cu unghiul fade axa x pozitiv i situat la distana fa de origine [17]. Se noteaz n general cu g(,).

g(,)= (,)( + )

(7)unde reprezint funcia Dirac i este ilustrat n [16] astfel:

() = +,= 00 , 0(8)

Figura 2.4 Cele dou forme ale transformatei Radon- ecuaia (7) i (9) [17][18]

Ecuaia ilustrat n [17]:g(,)= ( ,+ )

(9),

este echivalent cu ecuaia (2), fiind obinut prin rotirea axelor de coordonate cu unghiul ,unde:

= + = = + = + (10)

Transformata Radon reprezint o imagine ca un set de proiecii de-a lungul diferitordirecii, realiznd legtura dintre spaiul de coordonate (x,y) i spaiul proieciilor (,).

Transformata Radon calculeaz proiecia intensitii pixelului pe o linie radial dincentrul imaginii la un unghi specificat. Aceasta este utilizat, de obicei, pentru extraciainformaiei spaiale unde pixelii sunt corelai la un unghi specific.

n metoda de extragere caracteristici propus, trsturile Radon sunt calculate pentruunghiurile 0, 45, 90 i 135. Apoi, fiecare set de valori rezultat este transformat ntr-ohistogram cu trei benzi, rezultnd astfel un vector cu 4x3=12 valori. Transformata Radon estecalculat pentru imaginea pe nivele de gri i mpreun cu "histogramele multiscalare", "primele 4monemte " i caracteristicile Tamura formeaz metoda III de formare a vectorului de trsturi(vezi figura 3.5 pentru mai multe detalii).

2.4.2 Aplicaii ale transformatei Radon

Transformata are aplicaii 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 viruii- n rezolvarea ecuaiilor hiperbolice parial difereniale

8- detecia de form

2.5 Caracteristicile Tamura

Dintre proprietaile Tamura folosite n acest proiect se numar:- granularitatea- contrastul- direcionalitatea.Aceste trsturi au fost selectate de Tamura, Mori i Yamawaki pe baza experimentelorpsihologice.

2.5.1 Granularitatea se refer la distana dintre variaiile spaiale notabile a nivelelor degri. Procedura compiutaional propus, consider diferenele dintre valoarea medie asemnalelor corespunztoare ferestrelor de diferite dimensiuni care nu se suprapun, urmrindpaii de mai jos :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 diferena absolut Ek(x,y) dintre perechile valorilor medie cenu se suprapun n direciile: orizontal i vertical.3. Pentru fiecare pixel, caut valoarea lui k ce maximizeaz diferena Ek(x,y) n orice direcie iseteaz dimensiunea cea mai buna Sbest(x,y)=2k.4. Calculeaz trstura 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-oimagine g i a cror distribuie este direcionat spre alb i negru. Pentru definirea contrastului sefolosesc momentele centrale de ordinul al doilea i cele normalizate de ordinul al patrulea,reprezentate de variana standard - , respectiv indicele de aplatizare - 4:

= (11),unde =

(12); = ( )Pr

(13); = ( ) Pr (/) (14) i

m este media nivelelor de gri.[19]

2.5.3 Direcionalitatea

Gradul de direcionalitate este msurat folosind distribuia spectral a muchiilor localeorientate fa de unghiurele direcionale ale acestora. Soloditatea muchiei e(x,y) i unghiuldirecional a(x,y) sunt calculate folosind detectorul de muchii Sobel, aproximnd "pixel-wise" xi derivata y a imaginii: (,) = 0.5(|(,)| + (,)) (15)(,) = ((,)/(,)) (16)n ecuaiile de mai sus x(x,y) i y(x,y) sunt diferenele pe vertical i orizontal a nivelelor degri dintre pixelii vecini [19]. Diferenele sunt msurate utiliznd urmtorii operatori fereastra dedimensiune 3x3 [19]:

1 0 1 1 1 11 0 1 0 0 01 0 1 1 1 1

O histogram Hdir(a) a valorilor direciei cuantizate a este construit prin numrareanumrului de pixeli muchie care un anumit unghiul direcional i soliditatea muchiei mai maredect un prag predefinit. Histograma este relativ uniform pentru imaginile fr o orientare

9accentuat i evideniaz vrfurile pentru imaginile cu un grad al direcionalitii ridicat. Graduldirecionalitii este legat de ascuimea vrfurilor:

= 1 ( ) (17),n ecuaia (17) este numrul de vrfuri, ap este poziia vrfului p, wp este gama deunghiuri atribuite vrfului p, r indic un factor de normalizare legat de nivelele de cuantizare aleunghiului a, i a este unghiul direcional cuantizat (n modulo 180o).[19]

Aceste proprieti texturale Tamura sunt calculate pe imaginea pe nivele de gri astfel:- 3 valori: contrastul, direcionalitatea i granularitatea- o histogram a granularitii cu 3 benziAstfel, rezult astfel un vector de caracteristici cu 6 valori.

Trsturile Tamura sunt utilizate n acest lucrare n cadrul metodelor I, II i III deextragere a trsturilor (vezi Figura 3.5).

2.6 Polinoamele Zernike

Polinomele Zernike au fost dezvoltate la nceputul secolului XX de ctre fizicianulgerman Frits Zernike (faimos pentru invenia microscopului faz-contrast, pentru care a cstigatpremiul 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 att n sistemul cartezian (x,y), ct i n coordonate polare(r,). Cea mai utilizat form, este descris n [21] ca fiind cea polar:

, = + 1 ()2 cos( q) , 0 (18), = + 1 ()2 sin( q) , 0 (19)

= + 1(), = 0 (20)unde

() = ()()!

!!

!( )/ (21)

Valorile lui m i n sunt ntotdeauna ntregi i satisfac condiile mn i n-m=impar. Indexul jreprezint modul de ordonare al numerelor, fiind o funcie j(m,n).Condiia de ortogonalitate pentru polinoamele Zernike ilustrat n [21] este:

() = (22),unde:

10

() = , 10, > 1(23)2.6.2 Aplicaii ale polinoamelor Zernike

Baza acestor funcii este definit pe o suprafa circular, caracteristic planelor pupilelorn procesarea clasic de imagini, pentru lungimi de und optice i inflaroii, printr-un sistem delentile i oglinzi cu un diametru finit.

Descompunera polinomial Zernike este utilizat n urmtoarele domenii:- prelucrare optic, pentru a caracteriza erorile observate n analizele interferometrice, cu scopulde a obine performana dorit.-optometrie i oftalmologie, la descrierea devierii corneei sau lentilelor pentru o form idealsferic, care au ca rezultat erori de refracie.- optica adaptiv, la nlturarea distorsiunilor atmosferice. Aplicaiile n acest domeniu suntastronomia IR (inflarou) sau vizual i pentru redarea imaginilor din satelit. De exemplu, unuldintre factorii Zernike (pentru m=0 i n=2) este denumit "de-focus". Prin cuplarea iesirii acestuifactor la un sistem de control, poate fi implementat o focalizare automat. [21]

Coeficienii Zernike sunt valori complexe, n descrierea imaginilor folosindu-se valoareaabsolut a acestora. Polinoamele Zernike sunt aplicate asupra imaginii pe nivele de gri,constituind metoda IV de extragere a trsturilor (pentru mai multe detalii vezi figura 3.5).

2.7 Histograme multiscalare

Pentru acest set de trsturi sunt calculate histograme cu un numr variabil de benzi(3,5,7 i 9), dup modelul propus n [9]. Fiecare domeniu de frecvene corespunde uneihistograme diferite, i astfel numrul variabil de benzi permite msurarea coninutului ntr-undomeniu de frecvene foarte larg. Maximul histogramelor este folosit pentru normalizareavectorului de caracteristici rezultat, care are un numr de 1x24 elemente. Histogramelemultiscalare sunt aplicate asupra transformatei Wavelet, transformatei FFT i asupra imaginiioriginale (imagine pe nivele de gri) contribuind astfel cu un numr total de 3x24 elemente laformarea vectorului de trsturi al imaginilor.

Histogramele multiscalare sunt utilizate n cadrul metodelor I, II i III de formare avectorului de trsturi.(pentru mai multe detalii vezi figura 3.5)

2.8 Filtre orientate n patru direcii pentru obinerea "primelor 4 momente"

Pentru acest set de trsturi, imaginea este subdivizat ntr-un set de "dungi" n patruorientri diferite (0, 90, +45 i 45). "Primele 4 momente" (media, deviaia standard,oblicitatea i planitatea ("kurtosis") ) sunt calculate pentru fiecare "dung" i fiecare set de"dungi" este transformat ntr-o histogram cu 3 benzi. Avnd astfel patru momente n patrudirecii cu histograme cu trei benzi, rezult un vector de trsturi care conine 4x4x3=48elemente.[9]

"Primele 4 momente" sunt utilizate, lafel ca i histogramele multiscalare n cadrulmetodelor I, II i III de extragere a trsturilor din imaginea original.

2.9 Algoritmul KNN

KNN este abrevierea din limba englez pentru K-Nearest Neighbor (cei mai apropiai kvecini), fiind un algoritm de nvaare supervizat utilizat n special n problemele de clasificare.Scopul acestui algoritm este acela de a clasifica un nou obiect pe baza atributelor sale n finciede setul de date de antrenare cunoscut.

11

Prin aceast tehnic, folosit n special pentru clasificarea datelor n mai multe posibileclase, un obiect nou este clasificat pe baza majoritii voturilor vecinilor si, fiindu-i atribuitclasa cea mai frecvent ntlnit printre cei k cei mai apropiai vecini.

Acei k cei mai apropiai vecini se aleg pe baza distanei minime dintre obiect i toatecelelalte obiecte din setul de date de antrenare (setul de date cunoscut).Fiecare obiect este reprezentat n setul de date printr-un vector de trsturi, care n cazulimaginilor poate s conin caracteristici de form, de textur sau de culoare.

Exist mai multe tipuri de distane folosite pentru calculul distanei minime dintre noulvector i vectorii din setul de date:- distana euclidian- distana euclidian standardizat- distana city block (Manhattan)- distana cosinus- distana coeficientului de corelaie (distana Pearson r)- distana hamming- distana Maholonobis- distana Minkowski- etc

Cea mai frecvent distan utilizat n cadrul acestui algoritm este distana euclidian.Fiind dat o matrice X de dimensiune [mxn], care conine "m" vectori linie (vectorii de trasturide dimensiune [1xn]) , ,, , unde =(,,, ), putem defini metricile (distanele)dintre dou obiecte (doi vectori) oarecare i (r,s=1m) dup cum sunt ilustrate i n [22],astfel:- distana euclidian:

=( )( )= ( ) (24)- distana euclidian standardizat

=( )( ) , unde D este matricea diagonal, ce are ca elementedispersia vectorului =(, , ), notat , rezultnd:

= (

)

(25)

- distana city block (Manhattan) = | | (26)

- distana cosinus

=1 ()() (27)- distana coeficientului de corelaie (distana Pearson r)

=1 ()( )()()( )( ), unde = (28)

- etc, pentru mai multe tipuri de metrici a se consulta [22]Pentru a ntelege i mai bine funcionarea algoritmul KNN pe un exemplu numeric a se

consulta consulta [24].

2.9.1 Avantajele algoritmului KNN

Unul dintre avantajele sale este uurina implementrii, fiind unul dintre algoritmii declasificare cei mai uor de nteles.

12

O alt calitate a acestei tehnici este eficacitatea sa, n cazul n care, setul de date deantrenare este afectat de zgomot (n special n cazul n care se foloseste ca metric inversulptratului distanei ponderate). Obinerea distanei ponderate se face prin ierarhizarea fiecreitrsturi n funcie de scopul propus. Astfel distana euclidian ponderat va avea urmatoareaexpresie:

= ( ) (29),unde =1, iar este ponderea atributului (caracteristicii) i [23] .A nu se confunda ponderarea atributelor cu ponderarea distanelor.

O metod foarte ntlnit de ierarhizare a distanelor, este aceea de a-i da fiecarui vecin opondere de 1/d , unde d este distana pna la vecin. Astfel vecini mai apropiai vor avea ocontribuie mai mare la clasificarea unui obiect. Studiile au aratat c ponderarea distanelor numbuntete performanele algoritmului KNN.

2.9.2 Dezavantajele algoritmului KNN

La aplicarea algoritmului KNN n practic ne lovim de urmtoarele probleme:a)"Ce metric utilizm pentru performane ct 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 cresterea timpului de clasificare.

Timpul de clasificare depinde n special de numrul de obiecte din setul de date. Pentruseturile de date cu un numr foarte mare de obiecte este necesar o reducere a numrului deatribute pentru fiecare obiect n etapa de preclasificare, prin alegerea unor puncte cheie care sdiferenieze ntre ele ct mai bine posibil instanele setului de date.

k optim se obine prin testarea algoritmului de mai multe ori, modificnd numrul devecini.

Costul de calcul este destul de mare, deoarece trebuie s calculm distana dintre o nouainstana 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. Am ales acest algoritm datorit simplitii lui, a performanelorbune de clasificare, att n ceea ce privete acurateea ct i a timpului de clasificare.

2.10 Fiiere MEX (MEX-files)

MEX este abrevierea din limba englez pentru MATLAB Executable (executabileMatlab). Fiierele MEX sunt subrutine dinamice realizate n mediile de programare C, C++ sauFortran, coduri surs care compilate pot fi rulate din Matlab n acelai mod cum sunt rulate ifiierele M (M- files) sau orice alt funcie care este deja implementat n Matlab. Funciileexterne de interfaare realizeaz transferul de date ntre MEX- files i Matlab, oferind totodat iposibilitatea de a chema funcii Matlab din programele C, C++ sau Fortran.

Principalele motive de a creea n loc de un M-file un MEX- file sunt urmtoarele:- abilitatea de a apela o gam larg de rutine C, C++ sau Fortran deja existente direct din Matlabfr a fi nevoii s le rescriem ca un M -files- viteza de execuie; 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 uneiimagini, precum i pentru implementarea clasificatorului KNN. Aceste MEX- files sunt realizatede dezvoltatorii clasificatorului WND-CHARM, respectiv de Roger Jang i pot fi descrcategratuit de pe site-urile:http://www.openmicroscopy.org, respectiv http://mirlab.org/jang/matlab/toolbox/dcpr/.

13

3. Implementarea soluiei adoptate

Scopul lucrrii de fa este acela de a testa diferite caracteristici care s codeze cel maibine imaginile din baza de date i nu neaparat clasificarea acestora. Totui, pentru a verificaeficiena metodelor de extragere a trsturilor s-a folosit clasificatorul KNN.

n general, un sistem de recunoatere al obiectelor trebuie s:1- extrag atributele care grupez imaginile ntr-o anumit clas i difereniaz imaginile dinclase diferite2- s clasifice aceste atribute3- s elimine alarmele false - de aceea avem clasa garbage4- n cazul deteciei obstacolelor s identifice clasa imaginii pe baza acestor atribute5- s urmreasc obiectele de-a lungul scenei rutiere pn n momentul n care se pierd n afaraei i nu mai reprezint nici un pericol (modul de "tracking" (urmrire)).

n aceast lucrare s-a presupus c obiectele sunt deja segmentate (detectate), baza de datefiind format din imagini care ncadreaz doar obiectele i nu din scene ntregi de mai multeobiecte. Astfel, n aceast lucrare este tratat numai modul de extragere al atributelor pentruclasificare, precum i clasificarea obiectelor.

La nceput s-a ncercat extragerea caracteristicilor din imagini numai pe bazatransformatei Wavelet. Imaginile din baza de date au diferite dimensiuni (unele ilustreaz obiectemai apropiate avnd implicit dimensiuni mai mari- maxim 434x768 pixeli, altele obiecte maideprtate, avnd dimensiuni mai mici- minim 89x69 pixeli), iar pentru clasificare este necesarobinerea unui numr fix de caracteristici pentru fiecare imagine. Din aceast cauz, nainte de aaplica transformata Wavelet asupra imaginilor este necesar redimensionarea lor la aceleaivalori. Rezultatele obinute n urma clasificrii KNN a imaginilor nu au fost satisfctoare. Dinacest motiv s-a renunat la redimensionare i s-a ncercat gsirea unor metode de extragere atrsturilor care prin aplicarea lor asupra imaginilor s returneze un numr fix de coeficieniindiferent de dimensiunea imaginii.

Sistemele de clasificare folosesc diferite caracteristici pentru definirea obiectelor dinimagini. Aceste caracteristici reprezint ablonul (pattern-ul) obiectului, iar sabloanele obiectelorcare aparin mai multor clase vor fi eseniale pentru procesul de invare i testare al sistemului.Pentru obinerea caracteristicilor s-au folosit o serie de transformri, combinaii de transformrii de metode de extragere:- transformata Wavelet- transformata FFT- transformata Radon- caracteristicile Tamura- histogramele multiscalare- filtre orientate n patru direcii pentru obinerea "primelor 4 momente"- polinoamele Zernike.

n pasul de clasificare, algoritmul de evaluare se bazeaz pe calculul de distane ntrevectorii de caracteristici corespunztori obiectelor. Pentru a detecta i a recunoatecaracteristicile altor obiecte noi, sistemul trebuie nvat apriori cu aceste abloane prinintermediul caracteristicilor extrase. Sistemul odat nvat, poate fi folosit doar pentru testare,iar dac se dorete adugarea de noi instane n setul de antrenare, se va mai trece nc o dat prinetapa de nvare. Astfel, au fost studiate metodele de extragere enumerate mai sus pentruformarea setului de antrenare i testare. Acestea sunt utilizate de clasificator (KNN) pentru a serealiza recunoaterea automat obiectelor.

n lucrare de fa s-a utilizat algoritmul de clasificare KNN, datorit simplitiiimplementrii i al performaelor bune de clasificare.

14

3.1 Baza de imagini

Baza de imagini este construit din 800 de imagini color, mprite n patru clase dupcum urmeaz:- 200 de imagini cu maini- 200 de imagini cu pietoni- 200 de imagini cu animale (cini, pisici, vaci, oi, cai)- 200 de imagini alctuind clasa "garbage".

Baza de date a fost preluat de pe internet din diferite baze de imagini disponibile gratuitpe site-ul http://pascallin.ecs.soton.ac.uk/challenges/VOC/databases.html, deoarece nu a mai fostcreat pn acum o astfel de baz de imagini. Dup cum se poate observa n figura 3.1 imaginileau fost selectate manual i au fost extrase doar obiectele de interes din acestea. Apoi imaginile aufost transformate n imagini pe nivele de gri.

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

Figura 3.1 Imagini din baza de date

Dup ce caracteristicile au fost extrase din imagini, ele au fost introduse n clasificatorpentru a realiza clasificarea imaginilor n cele patru clasele. Dup cum se poate observa n figura3.1, imaginile care alctuiesc clasa garbage au fost obinute din fundalul imaginilor celorlalteclase. Aceast clas este util la detectarea alarmelor false, cnd imaginea nu face parte din niciuna din clasele maini, pietoni sau animale.

n general pentru crearea unei baze de imagini care s fie ct mai bun, sunt respectateurmtoarele principii:

15

- toate imaginile s fie realizate cu aceleai procedee (s fie realizate cu acelai aparat defotografiat sau camer de filmat)- parametrii mijloacelor de captare a imaginilor s fie identici pentru toate imaginile- s aibe un numr de imagini care s permit obinerea unor rezultate de clasificaresatisfctoare.

Deoarece nu a mai fost creat o baz de imagini ca i cea utilizat n lucrarea de fa irealizarea unei astfel de baze de imagini necesit foarte mult timp, au fost folosite imagini carefac obiectul altor baze de date. Bine neles c baza de imagini format, nu este la fel de bun cacea care respect principiile enumerate mai sus.

3.2 Metoda de extragere a caracteristicilor

Dup crearea bazei de imagini, s-a realizat extragerea caracteristicilor din imagini prinintermediul diferitor transformate de imagini (transformata Wavelet, transformata FFT,transformata Radon) i alte moduri de extragere ("primele 4 momente", histograme multiscalare,caracteristicile Tamura - granularitatea, contrastul i direcionalitatea, i polinomurile Zernike).

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

Figura 3.2 Schema bloc a metodelor de extragere a trsturilor

16

Metodele de extragere a trsturilor, dup cum se poate vedea n figura 3.2, au fostdenumite metoda I, metoda II, metoda III i metoda IV pentru ca referirea la acestea s serealizeze mult mai uor.

Privind figura 3.2 se poate observa c metoda I i metoda II difer ca i structur numaiprin prizma imaginilor pe care sunt aplicate (metoda I se aplic pe imaginea obinut n urmatransformatei Wavelet a imaginii pe nivele de gri, iar metoda II pe cea obinut n urmatransformatei Wavelet a transformatei FFT). Numrul de trsturi obinute prin aplicarea acestordou metode este acelai 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 atransformatei FFT) i indiferent de dimensiunea acesteia, doarece cele trei blocuri "primele 4momente", histograme multiscalare i caracteristicile Tamura contribuie cu un numr fix laformarea vectorului de caracteristici (48, 24, respectiv 6).

Astfel, asupra transformatei Wavelet a imaginii, ct i asupra transformatei Wavelet atrasnformatei FFT, se vor aplica urmtoarele funcii de compresie a numrului de coefieni:a) Histogramele multiscalare - funcie care transform imaginea de intrare n patru tipuri dehistograme, cu 3, 5, 7 i 9 benzi, rezultnd astfel 24 de valori. Aceste valori sunt normalizate cumaximul lor.b) "Primele 4 momente" - funcie care returneaz un numr de 48 de coeficieni, prin parcurgereaimaginii:- pe diagonal (att din strnga jos pna n dreapta sus, ct i din dreapta jos pn n stnga sus)cu un pas care depinde de valoarea rotujit a mpririi dimensiunii pe verical a imaginii la zece(round(dim_verticala/10)). La fiecare pas se calculeaz valoarea mediei, deviaiei standard,oblicitii i planitii pixelilor parcui. Coloanele matricei astfel obinut (care are stocate pefiecare linie cele patru valori menionate) sunt transformate n histograme cu 3 benzi, rezultndun numr de 4x3=12 atribute pentru fiecare imagine.- pe orizontal i pe vertical, cu deosebirea c fa de parcurgerea pe diagonal cea realizat peorizontal se va face cu un pas care depinde de dimensiunea vertical a imaginii, iar ceavertical se va face cu un pas care depinde de dimensiunea orizontal a imaginii. n rest seprocedeaz la fel ca i la parcurgerea pe diagonal.

Aadar, pentru cele patru parcurgeri (dou pe diagonal, una pe vertical i una peorizontal) se obin un numr de [4 parcurgeri]x[4 coloane]x[3 benzi ale histogramelor]=48trsturi pentru orice imagine asupra creia s-a aplicat aceast metod de reducere a trsturilor.c) Trsturile Tamura care se compun din directionalitatea imaginii, contrastul, granularitatea io histogram a granulitaii cu 3 benzi.

Pn acum au fost trecute n revist primele dou metode de reducere a atributelor uneiimagini (metoda I i metoda II), iar n continuare vom aborda celelate dou metode - metoda IIIi metoda IV.

n cadrul metodei III de reducere a atributelor, blocurile: "primele 4 momente",histograme multiscalare, caracteristicile Tamura, au aceeai funcionare ca i n cazul blocurilorsimilare din metoda I i metoda II, cu deosebirea c acestea acioneaz asupra imaginii originale(imagine pe nivele de gri). Acestor blocuri i se adaug i transformata Radon.

Pentru a realiza transformata Radon s-a utilizat funcia deja implementat n Matlab:

R = radon(I, theta) care returneaz transformata Radon R a intensitaii imaginii I pentru un unghi de theta grade [23].

Au fost calculate transformatele Radon pentru patru valori ale lui theta - 0, 45, 90 i 135.Fiecare coloan a lui R va conine transfromata Radon pentru fiecare unghi din theta. Apoicoloanele matricei R sunt transformate n patru histograme a cte trei benzi fiecare. Astfel,transformata Radon particip cu un numr total de 4x3=12 trsturi la formarea vectorului decaracteristici.

Metoda IV de extragere a trsturilor const n descompunerea polinomial Zernike aimaginilor pe nivele de gri. Rezultatele obinute n urma aplicrii polinoamelor Zernike asupraimaginii sunt valori complexe, i de aceea descriptorii imaginii vor fi modulul acestor valori

17

(valoarea absolut a numerelor complexe obinute).La aceste metode s-a ajuns pornind de la cele descrise n [9] pentru formarea vectorului

de trsturi din cadrul clasificatorului WND-CHARM.3.2.1 Metoda de extragere a caracteristicilor din WND-CHARMMetoda propus pentru formarea vectorului de trsturi al clasificatorului WND-CHARM

este ilustrat n urmtoarea figur:

Figura 3.3 Schema de formare a vectorului de trsturi din cadrul WND-CHARM [9]

Dup cum se poate observa n figura 3.3 pentru formarea vectorului de trsturi s-auutilizat diferite transformate ale imaginilor (transformata Wavelet, transformata Chebyshev itransformata FFT), precum i combinaii ale acestor transformate (transformata Wavelet atransformatei FFT i transformata Chebyshev a transformatei FFT). Apoi din rezultatele obinuten urma acestor transformate, au fost extrase diferite trsturi, care sunt grupate n funcie detipul lor (caracteristici de mare contrast, de descompunere polinomial, de statistic i textur)n patru grupe astfel:

Figura 3.4 Grupele de caracteristici pentru formarea vectorului de trsturi din WND-CHARM[9]

n figura 3.4 este descris componena fiecrei grupe de caracteristici. Astfel, grupa Acuprinde urmtoarele caracteristici de contrast nalt(de form):

- statisticile muchiilor care sunt calculate pe gradientul imaginii originale i cuprind maimulte caracteristici cum ar fi media, variana, o histogram cu opt benzi a magnitudinii idireciei pixelilor, numrul total de pixeli muchie normalizat n raport cu dimensiunea imaginii,omogenitatea direciei i o histogram cu patru benzi care ilustreaz diferena direciei muchiilor.Astfel, prin extragerea acestor statistici din imagine se obine un numr de 28 de trsturi.

- coeficienii Gabor se obin prin utilizarea wavelet-urilor Gabor[9], obinndu-se unnumr de 7 coeficieni pentru fiecare imagine.

18

- statisticile obiectelor sunt calculate pe imaginea binarizat prin intermediul praguluiOtsu [9] i cuprind urmtoarele caracteristici: numrul lui Euler (diferena dintre numrul deobiecte i numrul de guri din imagine), centroizii imaginii, minimul, maximul, media, varianai o histogram cu zece benzi calculat pentru pixelii obiectelor i distana de la centroiziiobiectelor la centrul imaginii. n total statisticile obiectelor cuprind 34 de caracteristici.Dup cum se poate observa n figura 3.3 caracteristicile din grupa A sunt extrase numai dinimaginea original, contribuind astfel cu un numr de 28+7+34=69 caracteristici la formareavectorului de trsturi.

Grupa B reprezentat de caracteristicile de descompunere polinomial (de geometrie), aren componen urmtoarele trsturi:

- statisticile Chebyshev- Fourier sunt extrase prin aplicarea transformatei Chebyshev-Fourier asupra unei imagini, obinndu-se un numr de 32 de trsturi.

- statisticile Chebyshev sunt obinute prin transformarea coeficienilor rezultai n urmatransformrii Chebyshev a imaginii ntr-o histogram cu 32 de benzi.

- polinoamele Zernike - prin descompunerea polinomial Zernike se obin 72 decoeficieni compleci, 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 imagineaoriginal i imaginea rezultat n urma transformatei FFT a imaginii originale, contribuind astfelcu un numr de 2x(32+32+72)=272 caracteristici la formarea vectorului de trsturi.

Grupa C, dup cum se poate observa n figura 3.4 este compus din urmtoarelecaracteristici de statistic a pixelilor i de textur:

- primele 4 momente sunt reprezentate de media, deviaia standard, oblicitatea iplanitatea imaginii. Fiecare din cele patru caracteristici enumerate sunt formate dintr-ohistogram cu 12 benzi, rezultnd 48 de caracteristici.

- trsturile Haralick sunt calculate cu ajutorul matricelor concurente ale imaginilor.Aceste trsturi cuprind un numr de 28 valori.

- histograme multiscalare sunt obinute prin transformarea imaginii n patru tipuri dehistograme, cu 3, 5, 7 i 9 benzi, rezultnd astfel 24 de valori.

- caracteristicile Tamura se compun din direcionalitatea imaginii, contrastul,granularitatea i o histogram a granulitaii cu 3 benzi. Aceste trsturi contribuie cu un numrde 6 caracteristici la formarea vectorului de trsturi.Dup cum se poate observa n figura 3.3 caracteristicile din grupa C sunt extrase dintransformata Wavelet a imaginii originale i transformata Wavelet a transformatei FFT aimaginii originale, contribuind astfel cu un numr de 2x(48+28+24+6)=212 caracteristici laformarea vectorului de trsturi.

Grupa D este format din statisticile pixelilor i caracteristicile de textur ce fac parte dingrupa C la care se adaug i caracteristicile Radon a imaginii originale. Prin aplicareatransformatei Radon asupra unei imagini se obine un numr total de 4x3=12 trsturi.Dup cum se poate observa n figura 3.3 caracteristicile din grupa D sunt extrase din imagineaoriginal, transformata FFT a imaginii originale, transformata Chebyshev (a imaginii originale ia transformatei FFT a imaginii originale), contribuind astfel cu un numr de 4x(48+28+24+6+12)=472 caracteristici la formarea vectorului de trsturi.

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

3.2.2 Metoda de extragere a caracteristicilor n lucrarea de fan aceast lucrare formarea vectorului de caracteristici s-a realizat avnd ca referin

figura 3.3. Pentru obinerea unor timpi de extragere a trsturilor i de clasificare mai buni estenecesar a se utiliza un vector de trsturi cu o dimensiune ct mai mic. Astfel, pentru calcululvectorului de caracteristici, n lucrarea de fa se vor utiliza un numr mai redus de trsturi.

Pentru reducerea numrului de trsturi, dar i din cauza numrului foarte mare deposibiliti de formare a vectorului de trsturi (disponibile n figura 3.3), n aceast lucrare s-a

19

procedat astfel:- s-a plecat de la formarea vectorului de trsturi prin mprirea figurii 3.3 n mai nou

metode de extragere caracteristicilor (primele nou linii ale tabelului 3.1) i testarea fiecreimetode n parte.

- s-au relizat combinaii ale celor nou metode de extragere (dup cum se poate observan tabelul 3.1) pn cnd s-a ajuns la o performan de clasificare satisfctoare.

- nc de la nceput s-a renunat din grupa A la coeficienii Gabor (datorit numrului micde trsturi i timpului de obinere mai ridicat fa de celelalte caracteristici ale grupei), dingrupa B la statisticile Chebyshev-Fourier (deoarece utilizeaz pentru calcul o mare parte dinmemorie i timpul de obinere este foarte mare), din grupa C la trsturile Haralick (datorittimpului de obinere foarte mare i modului complicat de calcul).

Nr.crt. Metoda de extragere a trsturilor

Acuratee KNNWeka

[%]

Acuratee KNNMatlab

[%]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

Wavelt grupa C68 67.5 75.5 66.3 65.6 74

4. imagine transformata FFT transformata Chebyshev grupa D

64.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 transformataWavelet 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 imagineaoriginal

86.8 86.8 86.2 86.2 87.5 87.5

15.imagine transformata Wavelet grupa C +statisticile Chebyshev extrase din imagineaoriginal

73.7 71.2 73 70.6 70.6 70.6

16.

imagine transformata Wavelet grupa C +statisticile Chebyshev extrase din imagineaoriginal + statisticile Radon extrase dinimaginea original

82.5 85 85 82.5 82.5 80

20

Nr.crt. Metoda de extragere a trsturilor

Acuratee KNNWeka[%]

Acuratee KNNMatlab

[%]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 trsturilor analizate

n tabelul 3.1 se pot observa valorile acurateii de clasificare obinute att n Matlab ct i nWeka, prin intermediul clasificatorului KNN, respectiv IBk pentru un numr de vecini k= 1,3 sau5.

Dup cum se poate observa n tabelul 3.1, metoda de extracie a trsturilor care ofer ceamai mare acuratee este descris n ultima seciune a tabelului.

Nu s-a mai continuat testarea altor combinaii de metode de extragere a trsturilordeoarece s-a obinut o acuratee de clasificare satisfctoare i pentru c timpul de extragere atrsturilor pentru toate imaginile din baza de date s nu mai creasc (pentru c este i aa unulfoarte ridicat- 3 ore i 12 minute).

Asfel, s-a ajuns la urmtoarea schem de formare a vectorului de caracteristici, care esteutilizat mai departe n aceast lucrare:

Figura 3.5 Schema de formare a vectorului de trsturi

21

Figura 3.5 reprezint schema de formare a vectorului de caracteristici pentru care s-a obinut oacuratee de clasificare satisfctoare prin intermediul clasificatorului IBk din Weka iclasificatorului KNN implemantat n Matlab.

Metodele de extragere a trsturilor ilustrate n figura 3.5 sunt descrise mai amnunit nn figura 3.2 i n seciunea 3.2 a lucrrii de fa.

Astfel, dup cum se observ n figura 3.5 vectorul de caracteristici al fiecrei imagini vafi format din 318 trsturi. Pentru ntreaga baz de imagini vectorul de trsturi va fi format din318 trsturi x 800 de imagini.

3.2.3 Evaluarea trsturilor n Weka

Weka este un sistem foarte puternic cu ajutorul cruia se poate realiza numai clasificareaobiectelor (nu i extragerea caracteristicilor).Utilitarul poate fi descrcat gratuit de pe site-ul: http://www.cs.waikato.ac.nz/ml/weka/. Acestaa fost utilizat pentru a aplica o metod de nvare aupra vectorului de caracteristici i pentru aanaliza rezultatele obinute. nainte de aplicarea oricrui algoritm de clasificare asupra datelor,acestea trebuie convertite n fisiere ARFF ("Attribute-Relation File Format").

Structura fiierului ARFF trebuie s respecte urmtoarea form:

Figura 3.6 Structura fiierului ARFF la modul general

Figura 3.6 ilustrez modul de formare al unui fiier ARFF, n vederea antrenrii i testrii unuiclasificator ales din Weka cu trsturile extrase din imaginile cuprinse n baza de date.

Astfel, pentru vectorul de caracteristici format pe baza schemei din figura 3.5, structurafiierului ARFF va fi urmtoarea:

Figura 3.7 Structura fisierului ARFF utilizat n acest lucrare

n figura 3.7 este prezentat schema de formare a fiierului ARFF adaptat la aceastlucrare.

Aadar, fiecare atribut trebuie descris n headerinformaii att despre tipul fiecrui atribut, precum i despre clasa din care face parte respectivulobiect.

Clasa fiecrui obiect trebuie s fie cunoscut, pentru ca la testare s se poat comparaclasa prezis de clasificator cu clasadatelor se obine o matrice de confuzie ("confusion matrix") avnd dimensiunea [numr_clase xnumr_clase], n cazul nostru 4x4, care arat numrul instanelorobiecte. Dac toate instanele au fost clasificate corect atunci doar elementele diagonaleiprincipale ale matricei de confuzie sunt diferite de zerourmtoarele matrice de confuzie

Figura 3.8 Matrice

Notaiile realizate n figura 3.8 au urmtoarele seminificaii: Mpietoni, A - clasa animale i G

n figura 3.8 se poate observadin care fac parte (figura 3.8 an etapa de testare (figura 3.8 b):- toate obiectele din clasa maini (prima linie- din clasa pietoni (a doua liniecorect, 3 au fost clasificate ca fcnd parte din clasa animale i- din clasa animale 34 de imagini au fost clasifb), 1 a fost clasificat ca fiind din clasa magarbage- din clasa garbage (ultima linie acorect, 3 au fost clasificate ca aparinnd claseFigura 3.8 prezint matricele de confuzie penclasificatorul IBk. Numrul de vecini al clasificatorului IBk este egal cu unuvectorului de trsturi s-a utilizat schema prezentat n figura 3.5.

Pentru nvare i testarefost mprit manual n 80% instaneun numr de 160 de imagini din fiecare clas pentru ande 640 de imagini) i 20% din fiecare clas pentru testare (din ntreaga baz de date160 de imagini).

Programul Weka pune laDeoarece n lucrarea de fa sperformanelor diferiilor clasificatori, pentru a evalua calitatea trsturilor extrase din imagini sa utilizat clasificatorul IBk.

3.3.4 Evaluarea trsturilor n MatlabApelarea din Matlab a utilitarului Weka este una dificil. Din acest motiv, dar i datorit

necesitii folosirii unui clasificator n interfaa grafic a lucrrii de fa sMatlab a unui algoritm de clasificare. Da

22

este prezentat schema de formare a fiierului ARFF adaptat la aceast

Aadar, fiecare atribut trebuie descris n header-ul fiierului ARFF, fiierul coninindinformaii att despre tipul fiecrui atribut, precum i despre clasa din care face parte respectivul

Clasa fiecrui obiect trebuie s fie cunoscut, pentru ca la testare s se poat comparaasificator cu clasa real a obiectului respectiv. Dupa antrenarea (nvarea)

datelor se obine o matrice de confuzie ("confusion matrix") avnd dimensiunea [numr_clase xnumr_clase], n cazul nostru 4x4, care arat numrul instanelor atribuiteobiecte. Dac toate instanele au fost clasificate corect atunci doar elementele diagonalei

confuzie sunt diferite de zero. Dac spre exemplu vom aveade confuzie descrise n figura 3.8:

Matricele de confuzie pentru nvare, respectiv testare

Notaiile realizate n figura 3.8 au urmtoarele seminificaii: M - clasa maini, Pclasa animale i G -clasa garbage.

n figura 3.8 se poate observa c la nvare toate obiectele au fost atribuite corect claselorfigura 3.8 a).(figura 3.8 b):

toate obiectele din clasa maini (prima linie a matricei din figura 3.8 b) au fost clasificate corectdin clasa pietoni (a doua linie a matricei din figura 3.8 b) 36 de imagini au fost clasificate

corect, 3 au fost clasificate ca fcnd parte din clasa animale i 1 din clasa garbagedin clasa animale 34 de imagini au fost clasificate corect (a treia linie a matrice

asificat ca fiind din clasa maini, 2 au fost atribuite clasei

(ultima linie a matricei din figura 3.8 b) 28 de imagini au fost clasificatecorect, 3 au fost clasificate ca aparinnd clasei maini i 9 clasei animale.

le de confuzie pentru nvare, respectiv testare obinute. Numrul de vecini al clasificatorului IBk este egal cu unu

a utilizat schema prezentat n figura 3.5.i testare vectorul de caracteristici al tuturor imaginilor din baza de date a

instane pentru nvare i 20% pentru testare,160 de imagini din fiecare clas pentru antrenare (din ntreaga baza de date

) i 20% din fiecare clas pentru testare (din ntreaga baz de date

Programul Weka pune la dispoziie un numr mare de algoritmi de nvare i testare.Deoarece n lucrarea de fa s-a pus accentul pe extragerea trsturilor i nu pe analizaperformanelor diferiilor clasificatori, pentru a evalua calitatea trsturilor extrase din imagini s

Evaluarea trsturilor n MatlabApelarea din Matlab a utilitarului Weka este una dificil. Din acest motiv, dar i datorit

necesitii folosirii unui clasificator n interfaa grafic a lucrrii de fa sunui algoritm de clasificare. Datorit simplitii i uurinei de implementare

este prezentat schema de formare a fiierului ARFF adaptat la aceast

fiierului ARFF, fiierul coninindinformaii att despre tipul fiecrui atribut, precum i despre clasa din care face parte respectivul

Clasa fiecrui obiect trebuie s fie cunoscut, pentru ca la testare s se poat comparaobiectului respectiv. Dupa antrenarea (nvarea)

datelor se obine o matrice de confuzie ("confusion matrix") avnd dimensiunea [numr_clase xatribuite fiecrei clase de

obiecte. Dac toate instanele au fost clasificate corect atunci doar elementele diagonaleiDac spre exemplu vom avea

pentru nvare, respectiv testare

clasa maini, P - clasa

obiectele au fost atribuite corect claselor

) au fost clasificate corect) 36 de imagini au fost clasificate

din clasa garbagematricei din figura 3.8

au fost atribuite clasei pietoni i 3 clasei

28 de imagini au fost clasificate

tru nvare, respectiv testare obinute n Weka cu. Numrul de vecini al clasificatorului IBk este egal cu unu, iar pentru formarea

tuturor imaginilor din baza de date anvare i 20% pentru testare, astfel nct s avem

din ntreaga baza de date un total) i 20% din fiecare clas pentru testare (din ntreaga baz de date un total de

algoritmi de nvare i testare.a pus accentul pe extragerea trsturilor i nu pe analiza

performanelor diferiilor clasificatori, pentru a evalua calitatea trsturilor extrase din imagini s-

Apelarea din Matlab a utilitarului Weka este una dificil. Din acest motiv, dar i datoritnecesitii folosirii unui clasificator n interfaa grafic a lucrrii de fa s-a ales dezvoltarea n

torit simplitii i uurinei de implementare, pentru

23

evaluarea trsturilor n Matlab s-a ales utilizarea clasificatorului KNN.n aceast lucrare au fost utilizate pentru compararea performanelor de clasificare dou

versiuni ale clasificatorului KNN: KNNC (KNN Classify) care este un clasificator implementat cu ajutorul funciei deja

existente n Matlab:Class = knnclassify(Sample, Training, Group, k, distance) [23].

Funcia knnclassyfy returneaz vectorul Class, care conine rezultatul clasificriiimaginilor din vectorul Sample n funcie de imaginile cu ajutorul crora se realizeaz nvareaclasificatorului KNN.

Aceast funcie are ca i parametrii:- vectorul Sample care conine imaginile de testare i a crui linii vor fi clasificate n cele patruclase.- vectorul Training care conine imaginile de antrenare, fiind folosit la clasificarea obiectelor dinvectorul Sample. Numrul de coloane a celor doi vectori Sample i Training trebuie s fie egal.- vectorul Group conine clasele imaginilor din setul de antrenare- k este numrul de vecini utilizat n clasificare- distance este metrica utilizat n clasificare

KNNR (KNN Rule) care este implementat de Roger Jang i poate fi descrcat gratuit depe site-ul: http://mirlab.org/jang/matlab/toolbox/dcpr/.Cu acest clasificator se obine exact aceeai acuratee de clasificare, dar un timp de

clasificare mult mai bun. Acest lucru se datoreaz utilizrii MEX-files, care au rolul de a reducetimpul necesar n mod normal Matlab-ului s realizeze operaiile dorite.

n interfaa grafic va fi utilizat numai clasificatorul KNNR datorit performanelor declasificare superioare (n ceea ce privete timpul de clasificare).

Astfel utilitarul Weka este folosit pe lng stabilirea metodei de extragere a trsturilor ila verificarea implementrii n Matlab a celor dou clasificatoare KNN.

3.3 Determinarea parametriilor transformatei Waveletn aceast lucrare s-a utilizat transformata Wavelet discret pentru semnale

bidimensionale. n Matlab aceast transformat are urmtoarea sintax:[cA,cH,cV,cD] = dwt2(X,'wname') [23]

Prin aceast transformat se calculeaz matricea coeficienilor aproximai cA i matricelecoeficienilor detaliai cH, cV i cD (pe orizontal, vertical i respectiv pe diagonal) prindescompunerea 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 descompunerewavelet.

Descompunerea wavelet se poate realiza pe mai multe nivele astfel:- mai nti se realizeaz transformata Wavelet a imaginii prin metoda descris mai sus (utilizatpentru obinerea primului nivel de descompunere wavelet)- pentru obinerea celui de-al doilea nivel al descompunerii se va aplica transformata Wavelet peuna din matricele coeficienilor (cA, cH, cV sau cD) sau pe o combinaie a acestor matrice.- se continu cu aplicarea transformatei Wavelet pe noile matrice de coeficieni pn cnd seatinge nivelul de descompunere dorit.

Pentru determinarea parametriilor transformatei Wavelet s-a realizat urmtorulexperiment:

- s-a ales un nivel de descompunere egal cu 3, 4, 5 sau 6 (nivelele 1 i 2 nu ofer ocompresie suficient a atributelor imaginii). Aadar sunt patru valori ale nivelului dedescompunere.

- pentru funciile mam ale descompunerii wavelet s-au folosit funciile dejaimplementate in Matlab, precum: Daubechies, Coiflet, Symlet, biortogonale i inversebiortogonale (reverse biortogonal) .

24

Numele familiei de funcii wavelet Daubechies se scrie dbN, unde N este ordinul, iar dbeste "prenumele" funciei wavelet. Funciile Coiflet (coifN) reprezint o alt familie de funciidiscrete wavelet, descoperite de Ingrid Daubechies. Numele familiei de funcii wavelet Symlet sescrie symN, unde le fel ca i la Daubechies, N este ordinul, iar sym este "prenumele" funcieiwavelet. Functiile wavelet biortogonale se scriu biorNr.Nd, iar funciile inverse biortogonale lafel ca i cele biortogonale se scriu rbioNr.Nd.

Din varietatea de familii de wavelet-uri n acest experiment s-au utilizat urmtoarelefuncii: db1db15, coif1coif5, sym1sym15, bior 1.1bior6.8, rbio1.1rbio6.8 (n total unnumr de 64 de valori)

- s-a utilizat numai metoda I de extragere a trsturilor (descris n figura 3.2) avnd cascop a reducerea timpul de extragere pentru imaginile din baza de date.

Astfel, prin utilizarea metodei I au fost obinui vectorii de trsturi ai bazei de imaginipentru valorile parametriilor transformatei Wavelet stabilite mai sus. S-au obinut un numr de4x64=256 vectori de caracteristici, care au fost salvai n fiiere text. La sfritul fiecrei linii afiierului s-a introdus clasa real a imaginii (pentru a se putea calcula acurateea de clasificare)

- s-a realizat permutarea liniilor tuturor fiierelor, pentru a nu permite clasificatorului snvee inclusiv ordinea de preluare a imagnilor (deoarece clasificatorul prelua pe rnd cele 4clase, iar prin permutare imaginile sunt preluate aleator)

- pentru nvare i testare datele au fost mprite asfel nct s se obin 80% dinimaginile fiecrei clase pentru nvare i 20% pentru testare (cte 160 imagini din fiecare claspentru nvare i 40 imagini din fiecare clas pentru testare).

- s-a realizat clasificarea imaginilor din cele 256 de fiiere prin intermediulclasificatorului KNN. S-a optat pentru obinerea unei acuratei de clasificare ct mai bun, ndefavoarea unor timpi calcul a transformatei Wavelet mai ridicai (cu ct nivelul de descom-punere este mai mare cu att timpul necesar realizrii transformatei Wavelet este mai ridicat, darscade timpul de clasificare).

n urma acestui experiment s-a observat c acurateea maxim se obine pentru familia dewavelet-uri bior1.3 i nivelul de descompunere wavelet egal cu 3.Coeficienii 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 aplicrii transformatei Wavelet de familie bior1.3 inivel de descompunere wavelet 3 asupra unei imagini oarecare din baza de date. n urma aplicriitransformatei wavelet de nivel 3 i familie bior1.3 s-a realizat reducerea numarului de atribute alimaginii prezentate n figur de la [148x93] (valori ce reprezint dimensiunea imaginii originale)pna la [16x22]. Dup cum se poate observa n figura 3.2 din rezultatul transformatei Wavelet alimaginii sunt extrase caracteristicile: "primele 4 momente", histograme multiscalare icaracteristicile Tamura, numrul de trsturi reducndu-se de la [16x22=352] la 78 (48 pentru"primele 4 momente", 24 pentru histogramele multiscalare i 6 pentru caracteristicile Tamura).

3.4 Modul de mprire a datelor pentru nvare i testare

Dup cum se poate observa n figura 3.10, orice clasificator trebuie s aibe un set de datepentru antrenare i altul pentru testare. Iesirea unui astfel de clasificator este un vector care

25

conine numrul asociat claselor imaginilor din setul de testare (clasa_testare care este un vectorcoloan).

Figura 3.10 Schema bloc a clasificrii KNN

n funcie de tipul clasificatorului setul de date de antrenare, respectiv de testare trebuies aibe o anumit structur. Astfel pentru cele dou variante ale clasificatorului KNN (KNNC iKNNR) setul de antrenare i cel de testare va fi compus astfel:- setul de antrenare este format din doi vectori - vector_trsturi_antrenare, care conine pefiecare linie trsturile imaginilor destinate antrenrii i clasa_antrenare, care este un vectorcoloan ce conine pe fiecare linie clasa corespondent imaginii sotocate pe aceeai linei nvectorul de antrenare.- setul de testare este format dintr-un singur vector care are acelai numr de coloane ca ivector_trsturi_antrenare, coninnd pe fiecare linie trsturile unei imagini de test.

Numrul de linii al acestor vectori depind de procentul de imagini din baza de datedestinate antrenrii i testrii. Cum s-a ales un procent de 80% din imaginile fiecrei clase pentruantrenare i 20% pentru testare, aceti vectori vor avea urmtoarea dimensiune:- vector_trsturi_antrenare: 80% x 800 imagini = 640 imagini, iar pentru fiecare imagine s-auextras 318 trsturi. Astfel dimensiunea datelor de nvare este [640 linii x 318 coloane].- vector_trsturi_testare: 20% x 800 imagini = 160 imagini, iar pentru fiecare imagine s-auextras 318 trsturi. Astfel dimensiunea datelor de testare este [160 linii x 318 coloane].- clasa_antrenare dup cum a mai fost precizat este un vector coloan cu acelai numr de liniica i vector_trsturi_antrenare. Aadar vom avea o dimensiune de [640 linii x 1 coloan].- clasa_testare este tot un vector coloan care conine acelai numr de linii ca ivector_trsturi_testare rezultnd astfel dimensiunea [160 linii x 1 coloan].

Testarea clasificatorului KNN s-a realizat pentru un numr de vecini k=1,3 sau 5. Dupcum se poate observa k ia doar valori impare, din cauz c avem patru clase i s-a dorit evitareacazurilor n care clasificatorul poate atribuii imaginea la doua clase diferite n acelai timp (dacacesta gasete aceeai distan ntre vecinii si care fac parte din dou clase diferite).

Acurateea clasificrii a fost calculat ca raportul dintre instanele corect clasificate inumr total de instane clasificate. Determinarea instanelor corect clasificate s-a realizat princompararea claselor prezise de clasificator cu clasele reale (predefinite) ale imaginilor clasificate.Din acest motiv este necesar stocarea claselor reale ale imaginilor de test.

3.5 mbuntirea performanelorS-a ncercat mbuntirea performanelor prin dou metode:

- reducerea numrului de trsturi extrase din fiecare imagine- transformarea aplicaiei ntr-un executabil

3.5.1 Reducerea numrului de trsturi extrase din fiecare imagineDup cum se poate observa n figura 3.5 formarea vectorului de trsturi se realizeaz

prin aplicarea asupra imaginilor din baza de date a combinaiei celor patru metode de extragere:metoda I, metoda II, metoda III i metoda IV.

n tabelul 3.1 nu au fost analizate rezultatele tuturor combinaiilor posibile de formare avectorului de trsturi. Astfel, s-a ncercat reducerea numrului de trsturi extrase din fiecare

26

imagine prin analiza tuturor modalitilor posibile de formare a vectorului de trsturi pornind dela cele patru metode: metoda I, metoda II, metoda III i metoda IV.Deoarece avem un numr de patru metode de extragere, numrul de modaliti posibile deobinere a vectorului de trsturi este dat de:

+ + + = 4 + 6 + 4 + 1 = 15 modaliti

Cele cincisprezece modaliti de formare a vectorului de trsturi sunt obinute prin aplicareaasupra imaginilor a urmtoarelor metode i combinaii 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 III12. metoda I + metoda II + metoda IV13. metoda I + metoda III + metoda IV14. metoda II + metoda III +IV15. metoda I +metoda II + metoda III + metoda IV

Au fost formai astfel cincisprezece vectori de caracteristici ai bazei de imagini,dimensiunea lor variind n funcie de modalitatea de extragere a trsturilor (a se vedea tabelul4.1 pentru mai multe detalii).

Pentru clasificarea celor cincisprezece vectori de caracteristici s-a procedat dup cumurmeaz:- s-a realizat o