Tehnici de adnotare automată a imaginilor

FACULTATEA DE INFORMATICĂ

LUCRARE DE LICENȚĂ

Tehnici de adnotare automată a imaginilor

propusă de

Mihai Pîțu

Sesiunea: Iulie, 2012

Coordonator științific

Dr. Adrian Iftene

UNIVERSITATEA “ALEXANDRU IOAN CUZA” IAŞI

FACULTATEA DE INFORMATICĂ

Tehnici de adnotare automată a imaginilor

Mihai Pîțu

Sesiunea: Iulie, 2012

Coordonator științific Dr. Adrian Iftene

Declaraţie privind originalitate şi respectarea drepturilor de autor

Prin prezenta declar că Lucrarea de licenţă cu titlul „Tehnici de adnotare automată a imaginilor” este scrisă de mine și nu a mai fost prezentată niciodată la altă facultate sau instituție de învățământ superior din țară sau străinătate. De asemenea, declar că toate sursele utilizate, inclusiv cele preluate de pe Internet, sau indicate în lucrare, cu respectarea regulilor de evitare a plagiatului:

 toate fragmentele de text reproduse exact, chiar și în traducere proprie din altă limbă, sunt scrise între ghilimele și dețin referința precisă a sursei;

 reformularea în cuvinte proprii a textelor scrise de către alți autori deține referința precisă;

 codul sursă, imagini etc. preluate din proiecte open-source sau alte surse sunt utilizate cu respectarea drepturilor de autor și dețin referințe precise;

 rezumarea ideilor altor autori precizează referința precisă la textul original.

Iași,

Absolvent: Mihai Pîțu _______________

Declaraţie de consimţământ

Prin prezenta declar că Lucrarea de licenţă cu titlul „Tehnici de adnotare automată a imaginilor”, codul sursă al programelor şi celelalte conţinuturi (grafice, multimedia, date de test etc.) care însoţesc această lucrare să fie utilizate în cadrul Facultăţii de Informatică. De asemenea, sunt de acord ca Facultatea de Informatică de la Universitatea Alexandru Ioan Cuza Iaşi să utilizeze, modifice, reproducă şi să distribuie în scopuri necomerciale programele-calculator, format executabil şi sursă, realizate de mine în cadrul prezentei lucrări de licenţă.

Iași,

Absolvent: Mihai Pîțu _______________________

Acord privind proprietatea dreptului de autor

Facultatea de Informatică este de acord ca drepturile de autor asupra programelor- calculator, format executabil şi sursă, să aparţină autorului prezentei lucrări, Mihai Pîțu.

Încheierea acestui acord este necesară din următoarele motive:

Iași,

Decan: Dr. Adrian Iftene Absolvent: Mihai Pîțu

_______________________ _______________________

Cuprins

1. Introducere ... 6

1.1. Motivație ... 6

1.2. Competiția ImageCLEF – Annotation Task ... 7

1.3. Concluziile capitolului ... 9

2. Definiții și exemple ...10

2.1. Extragerea trăsăturilor imaginilor folosind PEF (Profile Entropy Features) ...10

2.2. Clasificarea datelor folosind SVM (Support vector machines) ...11

2.3. Ontologii ...14

2.4. Codebooks - dicționare de cuvinte vizuale ...14

2.5. Extragerea cuvintelor vizuale...16

2.6. Exploatarea tag-urilor definite de utilizatori ...22

2.7. Exploatarea coloristicii imaginilor - Momentele culorilor ...23

2.8. Detectarea fețelor ...25

2.9. Concluziile capitolului ...26

3. Abordări în sistemele existente ...27

3.1. Participări la ImageCLEF 2009 Annotation Task ...27

3.2. Participări la ImageCLEF 2011 Annotation Task ...28

3.3. Concluziile capitolului ...29

4. Descrierea sistemului ...30

4.1. Cerințe ...30

4.2. Detalii de implementare ...31

4.3. Extragerea trăsăturilor imaginilor ...32

4.4. Clasificarea imaginilor de test ...34

4.5. Postprocesare ...38

4.6. Evaluare ...39

4.7. Concluziile capitolului ...41

5. Contribuții personale, rezultate și direcții de viitor ...42

Bibliografie ...43

1. Introducere 1.1. Motivație

Procesarea automată a imaginilor cu ajutorul agenților constituie o ramură provocatoare a inteligenței artificiale, cu impact important asupra unor arii largi de aplicații cum ar fi indexarea și căutarea de imagini după categorii pe Web, recunoașterea de modele în domenii precum medicina, rețele sociale, construcții și altele. Sistemele actuale de căutare de imagini, Google Image sau Bing Images se bazează pe descrieri și adnotări textuale ale imaginilor, fără a analiza conținutul acestora, așadar acestea nu pot fi folosite pentru căutare în colecții de imagini neadnotate.

Viziunea calculatoarelor (Computer Vision) este un domeniu de actualitate cu aplicații în lumea aplicațiilor 3D, robotică sau aplicații Web. Tehnicile folosite pentru a proiecta un software care să înțeleagă obiectele sau mediul dintr-o anumită imagine sunt strâns legate de algoritmii folosiți în Machine Learning (învățarea automată a mașinilor), antrenând mai întâi programul prin exemple. Pentru procesarea imaginilor algoritmii existenți fac parte din categoria metodelor de învățare supervizată. Această metodă presupune un set de date de intrare prelucrat (imagini care au conținutul cunoscut) suficient de semnificativ astfel încât să se poată deduce o funcție numită clasificator (dacă output-ul este discret) sau funcție de regresie (dacă output-ul este continuu).

Tehnici precum: Support Vector Machines¹ (SVM) [1], Generative Models², Boosting³, multiple instance learning, active learning și altele au fost folosite pentru a clasifica și indexa imagini până în prezent.

1 http://www.support-vector-machines.org/

2 http://en.wikipedia.org/wiki/Generative_model

3 http://www.cs.princeton.edu/~schapire/boost.html

1.2. Competiția ImageCLEF – Annotation Task

ImageCLEF reprezintă o competiție organizată de CLEF⁴ (Cross Language Evaluation Forum) cu aplicații în domeniul CBIR⁵ - Regăsirea bazată pe conținutul imaginilor (Content- Based Image Retrieval); acest lucru presupune „regăsirea” de imagini dintr-o colecție mare de date folosind doar informațiile vizuale conținute de aceste imagini, pe baza unor interogări textuale. Organizatorii au propus mai multe sarcini precum: CBIR cu interogări în diferite limbi internaționale; Medical CBIR presupune regăsirea de imagini similare privind o anumită temă medicală; Adnotarea automată de fotografii (Annotation task); Adnotarea automată de fotografii cu temă medicală.

Nevoia adnotării automate de imagini a apărut datorită creșterii exponențiale de informații vizuale pe Web și nu numai, așadar sunt necesare sisteme care să indexeze, să caute pe baza conținutului sau să organizeze aceste informații vizuale. Aceste sisteme sunt încă imperfecte, iar din acest motiv nu sunt încă acceptate pe scară largă. În competiția ImageCLEF - Annotation Task organizată în 2011 (rezultate – Tabelul 1), participanții au trebuit să adnoteze un set de test de 10,000 de imagini publice de pe site-ul de partajare a imaginilor, Flickr⁶, folosind 99 de concepte vizuale predefinite. Această sarcină putea fi rezolvată folosind următoarele abordări:

1. Adnotarea automată folosind doar informații vizuale (V)

2. Adnotarea automată bazată pe meta-datele imaginii sau adnotările manuale ale utilizatorilor (T)

3. Abordări multi-modale, ce implică o combinație între abordările de mai sus (M) Câteva dintre cauzele dificultății adnotării imaginilor sunt:

 Diversitatea conceptelor la nivelul unei singure imagini

 Subiectivitatea adnotării conceptelor prezente (precum sentimentele) în datele de antrenament

 Volumul de date dezechilibrat (sunt mai multe exemple relevante pentru un anumit concept decât pentru altul, în setul de antrenament)

4 http://clef-campaign.org/

5 http://en.wikipedia.org/wiki/Content-based_image_retrieval

6 http://imageclef.org/2012/photo-flickr/

 Calitatea imaginii

Colecția de imagini de test au avut adnotări manuale pentru cele 99 de concepte. Aceste concepte variază de la diferite scene în care a fost făcută fotografia (în aer liber, din interior, panoramic, macro, etc.), obiecte prezente în imagine (animale, persoane, etc.), reprezentarea imaginii (portret, pictură, etc.) până la calitatea imaginii (neclară, supraexpusă, subexpusă, etc.).

În anul 2011 au fost evaluate și sentimentele prezente în imagine – Figura 1 (clasificate după modelul din [2]), față de competițiile din anii trecuți.

Figura 1: Sentimentele transmise de imagini au fost asignate manual folosindu-se aplicația MTurk⁷ [3]

Grupul Locul F-measure

ISIS 1 0.62

LIRIS 14 0.57

TUBFI 17 0.56

CEALIST 42 0.50

LAPI 70 0.39

Tabelul 1: Rezultate pentru o parte din echipele participante la ImageCLEF 2011

În competiția ImageCLEF - Annotation Task organizată în 2012, organizatorii au stabilit 94 de concepte⁸ grupate în 18 categorii:

 Momentul zilei: zi, noapte

7 www.mturk.com

8 http://imageclef.org/2012/photo-flickr/concepts

 Corpuri cerești: soare, lună, stele

 Vreme: cer senin, cer acoperit de nori, cer parțial acoperit de nori, curcubeu

 Combustie: flăcări, fum, artificii

 Iluminare: umbre, reflecție, siluetă, efect de lentile,

 Panoramă: munte, deșert, pădure, ţărm de mare, oraș, rural, graffiti

 Apă: subacvatic, ocean, lac, râu, alte contexte în care apare apa

 Floră: copaci, plante, flori, iarbă

 Faună: pisică, câine, cal, pește, pasăre, insectă, păianjen, reptilă, rozătoare

 Număr de persoane: nicio persoană, o persoană, două persoane, trei persoane, grup mic, grup mare

 Sexul persoanei: masculin, feminin

 Relațiile dintre persoane: familie sau prieteni, colegi de muncă, străini

 Calitatea imaginii: fără estompare, estompare parțială, estompare completă, estompare de mișcare, artefacte

 Stilul imaginii: imagine în imagine, distorsiune circulară, text pe imagine, alb-negru

 Vizualizarea: portret, macro, în interiorul unei clădiri, în exteriorul unei clădiri

 Cadru: viața de oraș, petrecere, acasă, recreere, mâncare

 Sentimente: bucuros, calm, inactiv, melancolic, neplăcut, înfricoșător, activ, euforic, amuzant

 Tipul de transport: bicicletă, mașină, camion, tren, transport pe apă, transport aerian Problema subiectivității și a faptului că este posibil ca o imagine să nu fie adnotată cu toate conceptele existente în imagine (de exemplu, în setul de imagini de training, doar 40% sunt adnotate cu sentimente) rămâne și în competiția din acest an.

1.3. Concluziile capitolului

În acest capitol am făcut o scurtă introducere în domeniul Computer Vision și a problemei adnotării automate de imagini, prin prisma participării la competiția ImageCLEF 2012 Annotation Task. Această competiție presupune detectarea unui număr de 94 de concepte prestabilite într-un set de imagini de test, pe baza unui set de imagini de antrenare.

2. Definiții și exemple

2.1. Extragerea trăsăturilor imaginilor folosind PEF (Profile Entropy Features) Pentru a clasifica conținutul unei imagini, se calculează un descriptor de imagine (capabil să surprindă particularitățile fiecărei imagini) folosind anumite caracteristici extrase din imagine.

Majoritatea tehnicilor implementate până în prezent se bazează pe distribuția culorilor în imagine (color histogram⁹). O nouă tehnică propusă în [4] numită Profile Entropy Features (PEF) are avantajul combinării caracteristicilor texturii cu formele prezente în imagine, precum și o viteză sporită în execuție.

Această tehnică presupune normalizarea¹⁰ imaginii RGB actualizând canalele Red, Green și Blue astfel: r = R/l, g=G/l, b=1-r-g, unde l=(R+G+B)/3.

reprezintă proiecția ortogonală a pixelilor pe axa orizontală X, respectiv

, proiecția ortogonală a pixelilor pe axa verticală Y, unde op este operatorul de proiecție, care poate fi media aritmetică sau media armonică a valorilor luminanţei (en. luminance¹¹) pentru fiecare pixel. Apoi pentru fiecare canal roșu, verde, albastru și operator op se calculează

( ) (

) , unde I este imaginea dată, pdf reprezintă funcția probabilităților distribuite¹² pe N intervale (N = √ , S = lungimea unei linii de pixeli sau a unei coloane de pixeli), definită în [5]. Se folosesc apoi componentele entropiei normalizate:

( ) ⁽

( ))

, ( ) ⁽

( ))

, ( ) ^{( ( ))} , Unde H este funcția entropie pentru histograme:

( ) ∑ ( )

9 http://www.jatit.org/volumes/research-papers/Vol6No1/13Vol6No1.pdf

10 http://www.aishack.in/2010/01/normalized-rgb/

11 http://www.drdrbill.com/downloads/optics/photometry/Luminance.pdf

12 http://mathworld.wolfram.com/ProbabilityDensityFunction.html

Acest algoritm se repetă pentru fiecare din cele 3 regiuni (Figura 2) din imagine împărțite în mod egal din imaginea originală.

Figura 2: Împărțirea imaginii originale în regiuni pentru a surprinde textura imaginilor panoramice (partea de sus, de obicei cerul, partea de mijloc, obiectul din imagine, iar partea de jos, gazon, apă, etc.)

În final, caracteristicile PEF reprezintă concatenarea valorilor , și , rezultând un vector de 45 de elemente (3 canale RGB * 5 trăsături * 3 regiuni).

2.2. Clasificarea datelor folosind SVM (Support vector machines)

SVM¹³ (Mașini cu vectori suport) constitute o tehnică eficientă de clasificare a datelor.

Această tehnică presupune un set de date pentru antrenare (training) și un set de date de test¹⁴. Fiecare instanță din setul de antrenament este deja clasificată ca aparținând unei anumite clase, iar acest set de date este folosit pentru a creea un model care este capabil să eticheteze instanțele din setul de test ca aparținând unei anumite clase. Așadar pentru un set de date de învățare S, o instanță este de forma (xi, yi), i {1, 2, …, l}, xi ϵ Rⁿ and yi {-1, 1}, iar acest set este liniar separabil dacă există astfel încât ( ) . SVM caută soluția problemei de optimizare [6]:

min_w,b,ξ w^Tw + C ∑ yi (w^T (w) + b) 1 - ,

13 http://www.support-vector-machines.org

14 Introducere Învățare automată: http://robotics.stanford.edu/~nilsson/MLBOOK.pdf

Funcția mapează vectorii de training într-un spațiu dimensional mai mare, deoarece acest lucru simplifică problema separării celor două clase. Valoarea C reprezintă penalitatea pentru valorile de eroare (Figura 3 - distanța de la fiecare instanță din setul de training pană la linia separatoare). O valoare mică pentru C conduce la un model SVM mai permisiv, iar o valoare mare pentru C minimizează numărul de puncte incorect clasificate în datele de antrenament.

Figura 3: Linia separatoare dintre cele două mulțimi Figura 4: Funcția kernel¹⁵

Funcția kernel pentru mașini cu vector suport este caracterizată de următoarea teoremă:

Teorema lui Mercer:

Fie o funcție simetrică. Există o funcție astfel încât:

( ) ( ) ( ) dacă și numai dacă ∫ ( ) ( ) ( )

Pentru orice funcție f astfel încât ∫ ( ) este finit. Această teoremă spune că matricea Gram¹⁶ ( ( ^{( ) ( )}), unde ^{( ) ( )}, sunt instanța i, respectiv j din datele de antrenare) asociată funcției kernel trebuie să fie simetrică și pozitiv semidefinită (condiție necesară și suficientă), iar funcția nu mai trebuie calculată.

Dacă și sunt funcții kernel ce respectă teorema lui Mercer, atunci se pot construi și alte funcții kernel , astfel:

15 Funcții SVM Kernel: http://crsouza.blogspot.com/2010/03/kernel-functions-for-machine-learning.html

16 http://mathworld.wolfram.com/GramMatrix.html

 ( ) ( ) ( )

 ( ) ( ), unde a ϵ

 ( ) ( ) ( )

Pentru o clasificare non-liniară, se folosesc și alte funcții pentru a separa mulțimile numite kernel-uri (Figura 4). Dintre acestea cele mai folosite sunt:

 Linear: ( )

 Polinomial: ( ) ( ) , unde d este gradul polinomului

 RBF: ( ) ( ) (sau ( ) ( )) unde ||p|| = poziția unui punct într-un spațiu Euclidian¹⁷

 Sigmoid: r ( ) ( ), unde tanh este funcția tangentă hiperbolică¹⁸

 Chi-square: χ²(x, y) = ∑ ^{( )}

( )

, acest kernel vine de la distribuția chi-square¹⁹ și a dat rezultate bune pentru clasificarea de imagini în sistemele actuale.

Parametrii γ, d și r sunt de obicei diferiți de la o problemă la alta.

Pentru a învăța un clasificator SVM folosind un set de date de training, se urmează următorii pași²⁰:

1. Se transformă datele de intrare (trăsăturile imaginii) în formatul svmLight²¹.

2. Se scalează datele de intrare: acest pas este important pentru a evita lucrul cu numere mari și pentru a evita debalansarea problemei (de exemplu în cazul folosirii kernelului RBF).

Valorile atributelor trebuie să fie în intervalul [-1, 1] sau [0, 1]. Această scalare trebuie făcută și pe datele de test.

3. Se alege un kernel pentru clasificator (pentru început ar trebui considerat RBF, apoi pentru clasificarea de imagini se poate considera kernelul χ²).

17 http://xlinux.nist.gov/dads/HTML/euclidndstnc.html

18 http://en.wikipedia.org/wiki/Hyperbolic_function

19 http://mathworld.wolfram.com/Chi-SquaredDistribution.html

20 http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf

21 http://svmlight.joachims.org/

4. Se folosește cross-validation pentru a găsi cei mai buni parametrii C și γ deoarece acești parametri sunt diferiți în funcție de problemă. Tehnica de cross-validation (secțiunea 4.5) presupune selectarea unui set de test din datele de training pentru a verifica acuratețea clasificării. Acest lucru previne problema supraestimării.

5. Se folosesc parametrii C și γ generați de cross-validation pentru a antrena întreg setul de intrare.

În domeniul clasificării imaginilor, apare problema apartenenței unei imagini la mai multe clase (o imagine poate conține mai multe concepte, de exemplu elemente de natură cât și oameni, etc.). Acest lucru presupune un tip de clasificare diferit de cel tradițional, iar una din cele mai folosite tehnici este clasificarea binară. Această clasificare este o extensie a metodei One- Against-All [7] și presupune etichetarea imaginilor ce conțin exemple relevante pentru un concept dat, ca fiind exemple pozitive, restul imaginilor din setul de date training fiind etichetate ca fiind exemple negative. Se antrenează câte un Svm pentru fiecare concept prezent în datele de training.

2.3. Ontologii

O ontologie (în informatică) definește o structură formală a lucrurilor și a relațiilor dintre ele. Folosind o mulțime de concepte structurate într-o ontologie, se pot face presupuneri asupra altor concepte similare cu unul asignat deja. De exemplu, dacă într-o imagine se află nori, se poate infera că fotografia este făcută spre cer, sau că imaginea este de tip panoramă. Acest lucru poate fi folosit pentru a genera și alte adnotări pentru o imagine în care s-a identificat cel puțin un concept. În setul de date de antrenare oferit de Image CLEF, imaginile adnotate respectă în relațiile semantice dintre concepte, de exemplu, dacă o imagine a fost adnotată cu weather_lightning, aceasta va conține (cu probabilitate mare) și conceptul view_outdoor.

2.4. Codebooks - dicționare de cuvinte vizuale

Pentru a evita folosirea multor proprietăți vizuale ale imaginii (lucru care îngreunează clasificarea), se folosesc așa numitele transformări codebook. Se definește întâi o mulțime de cuvinte vizuale (en. codewords – un set de exemple sau parametrii ce poate fi comparat cu un

pattern similar – Figura 5), apoi se folosește o distribuție a frecvențelor codeword-urilor ca un set compact de trăsături ce reprezintă imaginea. Astfel, un codeword este reprezentativ pentru mai mulți descriptori vizuali similari. Această abordare a fost inspirată din metoda „sacului de cuvinte” (bag of words²²) din domeniul procesării limbajului natural²³, în care se definește un set de cuvinte cu ajutorul căruia se construiesc tabele de frecvențe pentru diferite documente text.

Figura 5: Modelul codebook: o imagine reprezentată sub forma unei mulțimi de regiuni (bag-of-regions), fiecare regiune fiind reprezentată de cel mai bun codeword din vocabularul (codebook-ul) predefinit

Pentru a construi un codebook, se extrag trăsături dintr-un set de imagini de antrenament.

Una din cele mai folosite metode pentru a defini codewords este “rețeaua de pătrate” (Figura 5), în care imaginea este segmentată, obținându-se astfel patch-uri locale ce descriu diferite texturi prezente în imagine. O altă tehnică pentru a obține codewords este folosirea algoritmilor (ex.

SIFT, SURF, Harris-Laplace) ce identifică puncte de interes locale și definesc descriptori (vectori) de lungime fixă în jurul acestor puncte de interes (Figura 6). Acești descriptori ar trebui să fie invarianți²⁴ la rotiri, scalări, schimbări în iluminare sau alte transformări, astfel încât în momentul în care se dorește compararea acestora, proprietățile lor să rămână neschimbate.

Avantajul construirii unui codebook este în primul rând viteza procedeului de potrivire a imaginilor și faptul că acest proces se face folosind cele mai importante cuvinte vizuale în raport cu imaginea.

22 http://www.cs.huji.ac.il/~daphna/course/student%20lectures/noam%20aigerman.pdf

23 http://en.wikipedia.org/wiki/Natural_language_processing

24 http://books.google.ro/books?id=dp2xHfJz2d0C&printsec=frontcover&hl=ro#v=onepage&q&f=false

Figura 6: Patch-uri extrase folosind SURF Figura 7: Patch-uri extrase folosind SURF din două clustere (sursa [8])

Construcția unui codebook presupune folosirea algoritmului de clustering, k-means – Tabelul 2. Algoritmul minimizează numărul inițial de trăsături la un număr de clustere k predefinit. Se asignează apoi fiecărei trăsături un singur codeword (centru de cluster) reprezentativ, tehnică denumită și hard-assignment²⁵ - Figura 7.

Init: selectează k centre de clustere aleatoriu Repeat:

-Asignează puncte din mulțimi către cei mai apropiați clusteri -Actualizează centrul clusterului folosind media distanței euclidiene a punctelor clusterului.

-Șterge centrele clusterilor: reactualizează aleator Until: Nicio schimbare

Tabelul 2: Algoritmul k-means²⁶

2.5. Extragerea cuvintelor vizuale

Cercetările din ultimii ani din domeniul Computer Vision și-au îndreptat atenția către extragerea de trăsături locale ale imaginilor deoarece acestea tind să captureze mai bine semantica imaginilor decât cele globale (histograme de culori, intensități, texturi, etc.) și să asigure invarianța la transformări afine. Aceste trăsături locale sunt asociate cu diferite modele prezente în anumite părți ale imaginii (puncte, margini sau mici patch-uri). După ce aceste puncte de

25 http://nlp.stanford.edu/IR-book/html/htmledition/flat-clustering-1.html

26 https://www.ai-class.com/course/video/videolecture/68

interes au fost identificate în imagine, se calculează diferite măsurători în vecinătate, construindu- se astfel descriptori.

Top-Surf²⁷ este o librărie capabilă să extragă puncte de interes folosind SURF (Speeded Up Robust Features) [9] și să identifice cuvintele vizuale prezente în imagine pe baza unui dicționar de cuvinte vizuale (codebook) preconstruit.

SURF (Speeded Up Robust Features) este un algoritm inspirat din descriptorul SIFT²⁸ (Scale-invariant feature transform) care optimizează partea de construcție a descriptorului vizual.

SURF folosește o măsură bazată pe distribuția trăsăturilor de tip Haar²⁹ și matricea Hessiană³⁰ a imaginii pentru a detecta punctele de interes³¹. În cazul SURF, punctele de interes sunt extrase din punctele de extrem peste întreg spațiul de scalări folosind determinatul matricei Hessiene [8]:

(( ) ) [ ( ) ( )

( ) ( )]

Unde ( ), se referă la convoluția (derivarea) imaginii de ordinul 2 cu kernelul Gaussian, la scalarea . În plus, imaginea este analizată la mai multe scalări pentru a obține invarianță la modificări ale dimensiunii (Figura 8), iar descriptorul conține orientarea dominantă pentru fiecare punct de interes pentru a obține invarianță la rotire (Figura 9).

Figura 8: Construcția spațiului de scalare folosind metoda reprezentării piramidale³². Scalările sunt obținute prin aplicări succesive ale unui filtru Gaussian [9]

27 http://press.liacs.nl/researchdownloads/topsurf/

28 http://www.cs.berkeley.edu/~malik/cs294/lowe-ijcv04.pdf

29 http://grail.cs.washington.edu/pub/stoll/wavelet1.pdf

30 http://www.math.vt.edu/people/dlr/m2k_svb11_hesian.pdf

31 http://nichol.as/papers/Schmid/Evaluation%20of%20Interest%20Point%20Detectors.pdf

32 http://web.mit.edu/persci/people/adelson/pub_pdfs/pyramid83.pdf

Figura 9: Selecția orientării descriptorului. Se calculează o sumă a intensităților pixelilor (roșu) cuprinși de fereastra glisantă (gri) formându-se vectori orientați. Vectorul cu modul cel mai mare determină orientarea

descriptorului [9]

Numărul de puncte de interes găsite poate să varieze între 0 și câteva mii, în funcție de dimensiunea sau detaliile imaginii (de exemplu dacă imaginea este monocoloră, niciun punct de interes nu va fi returnat). Într-un experiment prezentat în [24], într-o imagine se găsesc în medie 176 de puncte de interes cu o deviație standard de 85.3 (experiment realizat pe 100,000 de imagini redimensionate la o rezoluție de 256x256 pixeli). Deoarece fiecărui punct de interes îi corespunde un descriptor (ce conține un vector de 64 de elemente în cazul SURF³³, 128 de elemente în cazul SIFT) se pune problema potrivirii acestor descriptori (Figura 10) cu cei prezenți într-o bază de date, acest lucru fiind posibil folosind, de exemplu, ca măsură distanța euclidiană dintre doi vectori.

Pentru construcția codebook-ului, au fost extrase 33.5 milioane de puncte de interes dintr- o bază de date cu imagini, fiecare punct de interes fiind considerat o locație în R⁶⁴. Apoi se aplică o metodă de clusterizare³⁴ astfel încât fiecare punct de interes să aparțină unui singur cluster, această tehnică aplicându-se de mai multe ori. Centrele acestor clustere reprezintă cuvintele dicționarului vizual nou creat.

33 http://www.vision.ee.ethz.ch/~surf/eccv06.pdf

34 http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/

Figura 10: Descriptorul Top-Surf. Cele mai frecvente 100 de cuvinte vizuale

Asemenea abordărilor în ceea ce privește procesarea limbajului natural, acestor cuvinte vizuale li se pot atribui greutăți în funcție de importanța lor în documente (de exemplu cuvintele vizuale ce au o frecvență ridicată de apariție în toate documentele, pot fi considerate mai puțin importante (stop-words³⁵) decât cele care apar cu frecvență mare în documente specifice). O măsură ce s-a dovedit de succes [11] în acest sens este tehnica tf-idf weighting. Frecvența unui termen (term frequency - tf) reprezintă numărul de apariții al unui cuvânt (vizual) într-un document, care poate fi normalizat pentru a preveni discriminarea documentelor cu număr mai mic de cuvinte. Frecvența inversă a unui termen într-un document (Inverse document frequency - idf) este o măsură care determină dacă un cuvânt este rar într-un set de documente.

( )

Unde t este un cuvânt vizual, #D – cardinalitatea mulțimii de documente D, iar d un document din D.

( ) ( ) ( ) (tf-idf weighting)

35 http://en.wikipedia.org/wiki/Stop_words

Folosind această măsură, fiecare cuvânt vizual din descriptorul Top-Surf va primi un scor, iar distanța dintre doi descriptori (vectori din R^N) poate fi calculată folosind similaritatea cosinus³⁶ sau diferența absolută.

Formula de calcul a similarității cosinus dintre doi vectori poate fi derivată din definiția produsului scalar:

( ) ( )

| | | | ∑

√∑ ( ) √∑ ( )

Unde d1 * d2 reprezintă produsul scalar (intersecția) dintre cei doi descriptori, iar ||d|| reprezintă norma vectorului d. Deoarece descriptorii sunt formați din greutăți tf-idf (strict pozitive) pentru fiecare cuvânt vizual, scorul de similaritate cosinus va aparține intervalului [0, 1] (unghiul dintre cei doi vectori nu depășește 90 grade), 1 pentru descriptori identici, 0 pentru descriptori absolut diferiți.

O altă tehnică folosită pentru a compara doi descriptori este diferența absolută³⁷, definită astfel:

( ) ∑

Unde |r| reprezintă modulul numărului real r, care în acest caz este egal cu diferența absolută a scorurilor tf-idf pentru cel de-al i-lea cuvânt vizual din cei doi descriptori. Această măsură tinde să discrimineze descriptorii cu lungimi de cuvinte vizuale diferite. Scorul calculat de distanța absolută aparține intervalului [0, ) (0 pentru descriptori absolut identici).

Mărimea descriptorului returnat de algoritmul SURF constituie o motivație pentru proiectarea Top-Surf (pentru o colecție de 100,000 de imagini descriptorii SURF necesită aproximativ 4.5Gb, iar descriptorii Top-Surf – Figura 10, aproximativ 80Mb). Pentru o imagine a cărui descriptor Top-Surf trebuie calculat, se extrag mai întâi punctele de interes SURF, acestea fiind agregate într-o histogramă de frecvențe, căutând cărui cuvânt vizual din codebook îi

36 http://www.ir-facility.org/scoring-and-ranking-techniques-tf-idf-term-weighting-and-cosine-similarity

37 http://users.cis.fiu.edu/~lli003/Music/cla/42.pdf

corespunde fiecare punct de interes (cu descriptorul său asociat) extras din imagine (Figura 11).

Se asignează mai apoi un scor fiecărui cuvânt vizual din histogramă folosind tf-idf weighting, iar primele N (o constantă definită) cuvinte vizuale cu scorul cel mai mare vor fi returnate ca fiind noul descriptor.

Figura 11: Histograma primelor 25 cuvintelor vizuale cu scorul tf-idf cel mai mare a imaginii din figura 7

Experimentele din [10] atestă faptul că pentru a extrage punctele de interes folosind algoritmul SURF este nevoie în medie de 0.37s, la care se mai adaugă 0.07s pentru calculul descriptorului Top-Surf. Dimensiunea constantei N nu afectează timpul de extragere a descriptorului deoarece frecvențele cuvintelor vizuale trebuie sortate indiferent de N, însă la momentul comparării descriptorilor, o valoare mai mare pentru N va determina un timp de execuție mai mare. De asemenea, mărimea codebook-ului este direct proporțională cu timpul de extragere al descriptorului. În schimb, pentru a compara descriptorul Top-Surf al unei imagini cu cei prezenți într-o bază de date, este nevoie în medie de 0.2ms (experiment realizat cu o bază de date de 100 000 imagini) deoarece sunt maxim N (de obicei 100) cuvinte vizuale de comparat în fiecare imagine, în contrast cu timpul de execuție al descriptorilor SURF pentru care fiecare punct de interes al imaginii trebuie comparat cu fiecare punct de interes al imaginilor din baza de date (numărul de puncte de interes poate ajunge la câteva mii).

0 0.01 0.02 0.03 0.04 0.05 0.06 0.07

8429 10778 11501 12639 21443 22719 37796 38357 43659 46721 46847 52273 56601 58760 62191 64041 65139 65726 100009 103432 104877 106957 107138 108055 111752

tf-idf

2.6. Exploatarea tag-urilor definite de utilizatori

În unele situații, informația vizuală nu este de ajuns pentru a da o interpretare semantică a conținutului imaginii. Atunci când sunt definite adnotări făcute de o persoană (tag-uri diferite de conceptele prezentate în secțiunea 1.2) putem exploata semantica acestora pentru a îmbunătăți

“judecata” sistemului bazat pe informații vizuale. Problemele ce apar la aceste abordări sunt legate de faptul că numărul de tag-uri (Figura 12) este relativ mic (sau 0) pentru o imagine (comparativ cu un document text), pot fi dintr-o multitudine de limbi, unele sunt subiective sau irelevante și pot fi alcătuite din mai multe cuvinte (de exemplu, rarebook, artgallery, selectivecolor, etc.) sau abrevieri (exemplu: b.w.). Aceste probleme împiedică buna funcționare a metodelor tradiționale folosite la procesarea limbajului natural.

Figura 12: Fotografie adnotată de un utilizator Flickr cu tag-urile: book, oldbook, rarebook, latin, greek, library, bornin1550, deadlanguage, libro

Grupul CEALIST [12] propune în participarea la ImageCLEF 2011 o măsură de similaritate dintre fiecare tag și conceptele vizuale pe baza ontologiei Wordnet³⁸ și a teoriilor privind rețelele sociale. Autorii din [13] au demonstrat faptul că o clasificare bazată pe teoria modelului spațial vectorial³⁹ ce folosește măsuri precum tf (frecvența unui termen) sau idf (frecvența inversă a unui termen) este inadecvată pentru analiza tag-urilor propuse de utilizatori din cauza problemelor prezentate în paragraful anterior. De exemplu, pentru conceptul însorit (en. sunny), cele mai frecvente tag-uri (experiment realizat la competiția ImageCLEF 2011) au fost: albastru (en.

blue), Cannon, Nikon, nori (en. clouds), însă există și concepte pentru care frecvența tag-urilor

38 http://wordnet.princeton.edu/

39 http://cogsys.imm.dtu.dk/thor/projects/multimedia/textmining/node5.html

corespunde cu semnificația conceptului. De asemenea, aceeași autori propun un kernel SVM liniar bazat pe cele mai frecvente tag-uri prezente în setul de antrenare, idee întâlnită și în abordările din [14] sau [15].

Această abordare presupune construcția unui vocabular de cuvinte ce conține tag-urile atașate imaginilor de antrenare, ce apar de cel puțin k ori (în experimentele din [13] s-a folosit k=3, respectiv k=16). Acest proces filtrează în mare parte tag-urile irelevante și rare, rezultând un număr de n tag-uri, ce vor fi folosite pentru a asigna fiecărei imagini un vector binar n- dimensional, a cărei i componentă va fi 1 dacă imaginea este adnotată cu tag-ul i din vocabular și 0, altfel. Kernelul liniar SVM ce clasifică astfel de vectori este următorul:

( )

Unde este produsul scalar dintre vectorul binar transpus și vectorul . Kernelul KG

numără câte tag-uri sunt partajate de cei doi vectori (corespondenți celor două imagini de comparat). Acest kernel conduce la o reprezentare multi-dimensională rară (multe valori nule între imagini), iar acest lucru poate afecta performanțelor clasificatorului, însă în combinație cu alte kernel-uri s-a arătat o îmbunătățire semnificativă a rezultatelor.

2.7. Exploatarea coloristicii imaginilor - Momentele culorilor

Momentele culorilor [16] (en. Color moments) reprezintă o măsură bazată pe caracteristicile culorilor (distribuțiile culorilor) din imagine, care a fost folosită cu succes în domeniul CBIR (Content-Based Image Retrieval).

Această metodă a fost dovedită a fi mai performantă (de aceeași autori din [16] și de experimentele din această lucrare) decât metodele convenționale bazate pe distribuția culorilor (e.g. histograme de culori). Construcția unei histograme de culori H(I) presupune redimensionarea imaginii astfel încât fiecare imagine din baza de date (în contextul CBIR) să conțină același număr de pixeli, iar apoi culorile din imagine să fie discretizate astfel încât fiecare interval din histogramă este numărul de apariții al culorii j in imaginea I. Cu toate acestea, histograma de culori nu este invariantă la modificări sensibile precum transformări afine, distorsiuni sau modificări ale iluminării (Figura 13).

Figura 13: Histogramele de culori pentru aceeași imagine însă cu iluminări diferite

Această măsură se bazează pe presupunerea că distribuția culorilor într-o imagine poate fi văzută ca o distribuție de probabilități peste o imagine. Acest lucru se face pe baza analizei tendinței centrale (statistică descriptivă) a distribuției culorilor folosind media, a împrăștierii valorilor culorilor folosind deviația standard și a asimetriei (skewness) distribuției culorilor în imagine. Pentru a caracteriza o culoare prezentă în imagine se poate folosi modelul de culori⁴⁰ RGB (roșu, verde, albastru) sau HSV (nuanță, saturație, luminozitate), fiecare model fiind reprezentabil într-un sistem 3-dimensional (cartezian pentru modelul RGB, cilindric pentru modelul HSV). Așadar fiecare dimensiune a modelului de culori ales, este caracterizată de 3 măsuri ale distribuției culorii (media, deviația standard și asimetria), rezultând un vector de 9 momente ce va caracteriza imaginea din punct de vedere coloristic.

∑

Unde este valoarea pixelului j din imagine în dimensiunea i a modelului de culori ales, iar N este numărul de pixeli din imagine. este media valorilor culorilor din imagine pentru dimensiunea i a modelului de culori.

40 http://software.intel.com/sites/products/documentation/hpc/ipp/ippi/ippi_ch6/ch6_color_models.html

√ ∑( )

Unde este deviația standard a distribuției culorilor pentru dimensiunea i a modelului de culori.

√ ∑( )

Unde este asimetria distribuția culorilor pentru dimensiunea i a modelului de culori.

Pentru a compara vectorii descriptivi ai imaginilor se poate folosi distanța euclidiană sau funcția de similaritate dintre două imagini , respectiv :

( ) ∑( | | | | | |)

Unde i reprezintă dimensiunea curentă a modelului de culori, sunt ponderi ce pot fi ajustate pentru a obține diferite rezultate (de exemplu, dacă este folosit modelul HSV, nuanța culorii poate avea o pondere și o importanță mai mare decât valoarea (intensitatea) culorii).

2.8. Detectarea fețelor

Unele concepte definite în secțiunea 1.2 au legătură cu prezența oamenilor în imagini (Numărul de persoane: nicio persoană, o persoană, două persoane, trei persoane; portret, etc.).

Deși aceste concepte nu sunt strict legate de apariția fețelor în imagine, există o probabilitate mare legată de faptul că dacă o persoană se află în imagine, aceasta să apară cu fața. Cu toate acestea, aproximativ 30% din imaginile din setul de antrenare propus de organizatorii ImageCLEF 2012 ce conțin fețe, nu sunt adnotate utilizând conceptul portret.

Algoritmul de detectare a fețelor propus de Voila și Jones⁴¹ presupune antrenarea unei cascade de clasificatori (mai mulți clasificatori în care al (k+1)-lea clasificator este dependent de

41 http://research.microsoft.com/en-us/um/people/viola/Pubs/Detect/violaJones_CVPR2001.pdf

output-ul clasificatorului k) de tip AdaBoost pentru extragerea (alegerea) de trăsături de tip Haar⁴². În a doua imagine din figura 14, se observă faptul că suma intensităților pixelilor din jurul ochilor este mai mare decât suma intensităților pixelilor de sub ochi (totodată, aceeași trăsătură Haar ar putea fi detectată în zona gurii, acest lucru întărind presupunerea că este vorba de o față umană), iar în a treia imagine se observă că suma intensităților pixelilor din jurul nasului este mai mare decât suma intensităților pixelilor de pe nas. Aceste trăsături sunt considerate a fi unice pentru fața umană.

Figura 14: Cele mai frecvente trăsături de tip Haar la fețele oamenilor [17]

În final, fiecare clasificator „slab” este agregat într-un clasificator „tare”⁴³, capabil să detecteze fețele umane. Imaginea este scanată la mai multe scalări pentru a detecta fețe, iar procesul poate fi optimizat folosind imagini integrale⁴⁴. Algoritmul este foarte rapid și precis, ce poate avea o rată de detecție de peste 95% dacă sunt aleși parametrii optimi.

2.9. Concluziile capitolului

În acest capitol am prezentat formal algoritmii și definițiile pe care se bazează această lucrare, atât din punct de vedere teoretic, cât și al implementării. Pentru etapa de învățare automată am definit (sumar) mașinile cu vectori suport (secțiunea 2.2), iar pentru etapa de extragere a trăsăturilor imaginii, algoritmii: Profile Entropy Features (pentru a surprinde textura și formele imaginii), cuvinte vizuale folosind TopSurf (pentru trăsăturile locale), momentele culorilor (coloristica imaginii) și abordarea textuală folosind tag-urilor definite de utilizatori.

42 http://dtpapers.googlecode.com/files/01544911.pdf

43 http://en.wikipedia.org/wiki/Boosting

44 http://www.cse.yorku.ca/~kosta/CompVis_Notes/integral_representations.pdf

3. Abordări în sistemele existente

3.1. Participări la ImageCLEF 2009 Annotation Task

În participarea UAIC la competiția ImageCLEF⁴⁵ Annotation Task din 2009 [18] s-a propus un sistem alcătuit din patru mari componente: prima componentă identifică fețele oamenilor (în cazul în care există în imagine - componentă utilă pentru categoriile ce conțin persoane), a doua componentă calculează similitudinea dintre imaginea de adnotat și fiecare imagine din setul de antrenament, a treia componentă extrage informații din fișierul Exif⁴⁶ asociat imaginii, iar a patra componentă asignează o valoare implicită în funcție de gradul de apariție în setul datelor de training.

În cadrul aceleiași competiție, în [19] H. Glotin et al. propune un sistem care explorează proprietățile unei imagini folosind mai multe abordări, printre care cea mai performantă s-a dovedit următoarea: imaginea se segmentează în 3 regiuni orizontale (câte o treime fiecare), iar pentru fiecare regiune se calculează histograma culorilor în spațiul HSV. Această abordare are rezultate bune pentru concepte panoramice precum: cerul, vegetația, oceanul, etc. Se antrenează un clasificator SVM optimizat pentru performanțe multivariate⁴⁷, deoarece problema adnotării este dezechilibrată (numărul de date pentru învățare diferă de la un concept la altul).

În participarea universității din Amsterdam [14] (clasată pe locul întâi la competiția din 2009), se descriu mai multe abordări cu privire la recunoașterea conceptelor, având în vedere că un obiect este greu de recunoscut dacă se schimbă perspectiva din care este observat (fotografiat).

Pentru a acoperi acest aspect, se folosesc detectorii Harris-Laplace⁴⁸ pentru punctele de interes, pe mai multe scalări ale imaginii (pentru a obține invarianță la scalare). Pentru concepte omogene, detectorii Harris-Laplace sunt ineficienți, se folosesc strategii de random și dense sampling [25]. Al doilea pas în implementarea echipei ISIS a fost extragerea de puncte SIFT, din diferite spații de culori. Pentru a reduce numărul de caracteristici ale imaginii, se folosesc transformări codebook. Pentru partea de clasificare, se folosește librăria LIBSVM, utilizându-se kernelul χ² (Chi-square kernel).

45 http://www.imageclef.org/

46 http://en.wikipedia.org/wiki/Exchangeable_image_file_format

47 http://svmlight.joachims.org/svm_perf.html

48 http://en.wikipedia.org/wiki/Harris_affine_region_detector

Grupul XRCE [20] (clasat pe locul doi în competiția din 2009) propune o metodă bazată pe utilizarea ontologiilor în momentul clasificării, lucru derivat din diversitatea conceptelor din datele de test (din competiția organizată în 2009). Acest lucru a fost folosit în adnotarea imaginii cu mai multe etichete și nu în etapa de training, în felul următor: după ce funcția clasificator asignează probabilități fiecărei etichete, se face o post-procesare pentru a se asigura consistența datelor clasificate cu cele din ontologie. Pentru a extrage trăsăturile locale ale imaginii, s-a folosit algoritmul SIFT și statisticile locale RGB. Dimensiunea vectorului de trăsături a fost redusă la 50 de elemente, folosind PCA (Principal Component Analysis).

Aceste trăsături sunt clasificate folosind tehnica vocabularelor vizuale [10]. Constrângerile ontologiei au fost implementate astfel: pentru concepte (detectate în imagine) care sunt disjuncte, probabilitățile lor sunt normalizate astfel încât suma lor să fie 1; pentru un concept părinte probabilitatea este mai mare sau egală cu probabilitatea maximă a copiilor; pentru un concept care implică un alt concept, se normalizează doar dacă cele două intră în conflict. Pentru a verifica adnotările făcute, se folosesc metodele Equal Error Rate (ERR) și Area under Curve (AUC).

3.2. Participări la ImageCLEF 2011 Annotation Task

Grupul TUBFI [15] reprezintă departamentul de Machine Learning al institutului de tehnologie FIRST din Berlin, ce a participat la competiția ImageCLEF Annotation Task din 2011 cu 4 rulări informații vizuale și o rulare multi-modală. Pentru abordarea folosind doar informații vizuale, aceștia au folosit descriptorii Harris-Laplace, SIFT și RGB-SIFT (descriptorul dezvoltat de grupul universității din Amsterdam [14]), agregate în modele „sacul de cuvinte vizuale” (Bag of visual words). Abordarea multi-modală exploatează semantica adnotărilor date de utilizatorii Flickr folosind o funcție kernel personalizată ce calculează distanța dintre două seturi de adnotări peste un vocabular selectat de cuvinte (se folosesc doar cele mai frecvente cuvinte prezente în setul de training).

Grupul LIRIS [21] a reprezentat universitatea din Lyon la competiția ImageCLEF Annotation Task din 2011, cu două rulări folosind doar informații textuale și două rulări multi- modale. În abordarea bazată pe informații vizuale, aceștia au construit o măsură care calculează

distanța semantică dintre o adnotare făcută de utilizator și un dicționar construit de aceștia, care conține cuvinte specifice fiecărui concept, folosind librăria WordNet. O altă metodă s-a bazat pe setul de cuvinte ANEW⁴⁹ (ce conține scoruri privind emoțiile generate de cuvinte) care calculează valența și nivelul de apropiere către un anumit sentiment pentru fiecare cuvânt asociat imaginii de test. În abordarea bazată pe informațiile vizuale, grupul LIRIS a folosit diferite proprietăți ale imaginii precum culoarea, textura, precum și caracteristici locale extrase folosind SIFT. Pentru etapa de clasificare, aceștia au utilizat diferite strategii precum Adaboost și SVMs.

Grupul „Laboratorul de Analiză și Prelucrarea Imaginilor” [22] au reprezentat Universitatea Politehnică din București, iar aceștia au participat la competiția din 2011 cu două rulări folosind doar informații vizuale. Aceștia au dezvoltat un descriptor capabil să rețină geometria contururilor din imagine și relațiile dintre ele, extrăgând apoi câteva proprietăți statistice ce vor fi asociate imaginii împreună cu histogramele de culori. Imaginile au fost redimensionate la o dimensiune de maxim 300 de pixeli (pe lungime sau lățime) pentru a scădea timpul de execuție, iar apoi au fost extrase liniile din imagine folosind un detector de muchii Canny⁵⁰ la 4 scalări diferite, fiecare linie fiind caracterizată de un număr de trăsături. În final imaginea este caracterizată de un vector de 916 elemente (extras în circa 40 de secunde utilizând un procesor de 2.6 GHz), iar pentru etapa de clasificare autorii au folosit metoda LDA⁵¹ (Linear Discriminant Analysis).

3.3. Concluziile capitolului

În sistemele prezentate în acest capitol, am analizat unele din cele mai bune abordări propuse până acum în domeniul adnotării automate a imaginilor, pentru a reliefa calitățile sau defectele acestora și pentru a descrie stadiul actual al cercetărilor din acest domeniu.

49 http://csea.phhp.ufl.edu/media/anewmessage.html

50 http://fourier.eng.hmc.edu/e161/lectures/canny/node1.html

51 http://research.cs.tamu.edu/prism/lectures/pr/pr_l10.pdf

4. Descrierea sistemului 4.1. Cerințe

Sistemul propus este capabil să adnoteze automat un set de imagini folosind conceptele definite în secțiunea 1.2, principalul scop al acestuia fiind participarea la ImageCLEF 2012. Baza de date ImageCLEF 2012 conține 15,000 de imagini de antrenare și 10,000 de imagini de test (Figura 15) (imagini preluate de pe site-ul de partajare a fotografiilor Flickr⁵²; imaginile de test și antrenare constituie un subset al colecției de imagini MIR FLICKR⁵³). Pentru competiția din acest an se pot înainta un număr de 5 rulări ale sistemului propus pe setul de imagini de test.

Datele de antrenare au fost lansate de către organizatori cu două luni înaintea termenului-limită (30.6.2012), iar datele de test cu 6 săptămâni înaintea termenului-limită.

Figura 15: Exemple de imagini de antrenare/test

O altă utilizare pentru acest sistem ar putea fi adnotarea automată a unui set mare de imagini, utilizare pentru care am propus o arhitectură client-server.

52 http://www.flickr.com/

53 http://press.liacs.nl/mirflickr/

4.2. Detalii de implementare

Sistemul propus a fost implementat în mare parte utilizând platforma Java, dar și C++, iar interfața cu utilizatorul este implementată în C# folosind tehnologia WPF (Windows Presentation Foundation – XAML⁵⁴ – Figura 16). Interfața grafică reprezintă o aplicație de tip client pentru aplicația principală (serverul), iar aceasta este capabilă să facă cereri de adnotare a unui set de imagini dintr-un director sau dintr-un fișier sub formatul prezentat în secțiunea 4.5, sau să permită editarea probabilităților returnate de server în vederea construirii unor teste.

Figura 16: Interfața grafică a sistemului

Aplicația este de tip server concurent, pentru care am conceput un protocol de comunicare capabil să răspundă la cererile venite de la utilizatori. Principala comandă utilizată este adnotarea automată a unei imagini folosind cele 94 de concepte de la ImageCLEF 2012 (comanda predict),

54 http://msdn.microsoft.com/en-us/library/ms754130.aspx

însă protocolul suportă și cereri pentru a vizualiza descriptorul Top-Surf (comanda visualize), cereri pentru detecția fețelor folosind librăria OpenCV ⁵⁵ (comanda facedetection) sau posibilitatea de a trimite serverului corectări privind adnotarea conceptelor (comanda post).

4.3. Extragerea trăsăturilor imaginilor

Pentru abordarea vizuală, am implementat descriptorul global prezentat formal în secțiunea 2.1 (Profile Entropy Features), descriptorul local prezentat în secțiunea 2.5 folosind librăria Top-Surf și descriptorul de culori prezentat în secțiunea 2.7. Extragerea acestor descriptori se face în aprox. 2 secunde (pe un procesor i7 Turbo Boost: 1.73GHz – 2.88GHz) Acești descriptori au fost datele de intrare pentru Mașinile cu vectori suport (Support Vector Machine SVM – secțiunea 2.2). În figura 17 am descris diagrama de pachete a aplicației principale (serverul), care are o structură modulară, astfel încât se pot adăuga și testa și alți algoritmi pentru extragerea trăsăturilor imaginilor.

Figura 17: Diagrama de pachete a aplicației principale

55 http://opencv.willowgarage.com/wiki/

Pentru algoritmul de extragere a cuvintelor vizuale (TopSurf) am creat o interfață JNI⁵⁶ (Java Native Interface) care asigură comunicarea dintre librăria dinamică nativă TopSurf (scrisă în C++ de B. Thomee⁵⁷ în 2010) și aplicația Java scrisă de mine. Deoarece librăria necesită un spațiu relativ mare de adrese de memorie (în testele pentru ImageCLEF 2012 am folosit un dicționar preconstruit de 300,000 de cuvinte vizuale), am decis să folosesc compilez librăria dinamică pentru platforma x64. De asemenea, parametrul de redimensionare al imaginilor folosit în acest sistem este de 512 pixeli și folosesc primele 256 de cuvinte vizuale returnate de descriptorul TopSurf.

Descriptorul PEF (Profile Entropy Features) a fost implementat de mine după specificațiile din secțiunea 2.1, în care m-am folosit de librăria JAI⁵⁸ (Java Advanced Imaging) pentru acces rapid la pixelii imaginilor.

Pentru algoritmul din secțiunea 2.6 am construit un dicționar de tag-uri definite de utilizatori cu k=16 (numărul minim de apariții al unui tag în adnotările imaginilor de antrenare) deoarece acest prag elimină mai multe cuvinte irelevante asociate imaginilor. De asemenea, am folosit serviciul online Bing Translator⁵⁹ (serviciu de traduce și detectare a limbilor străine) deoarece multe dintre tag-urile definite de utilizatori sunt în altă limbă decât engleza (spaniolă, arabă, etc.). Acest lucru a fost posibil datorită serviciului de detectare a limbii (dacă tag-ul definit de utilizator este diferit de limba engleză se încearcă traducerea) și existența unei librării⁶⁰ Java care implementează protocolul de comunicare cu acest serviciu. După această etapă, am aplicat un algoritm⁶¹ de obținere a rădăcinii cuvântului (en. stemming; de exemplu, tag-urile: stemmer, stemming, stemmed au ca rădăcină cuvântul stem.) pentru a nu trata diferit tag-urile provenite din același cuvânt.

Pentru exploatarea coloristicii imaginilor am implementat algoritmul de extragere a momentelor culorilor (secțiunea 2.7) și am folosit modelul de culori HSV (deoarece în urma testelor, prin folosirea acestui model se obțin rezultate mai bune), iar pentru funcția de

56 http://java.sun.com/docs/books/jni/

57 http://www.liacs.nl/~bthomee/

58 http://java.sun.com/javase/technologies/desktop/media/jai/

59 http://www.microsofttranslator.com/

60 http://code.google.com/p/microsoft-translator-java-api/

61 implementare: http://tartarus.org/~martin/PorterStemmer/java.txt

similaritate , am folosit (o pondere mai mare pentru parametrul de nuanță din modelul HSV).

4.4. Clasificarea imaginilor de test

Deoarece cerințele acestui sistem (Figura 17) au fost legate de faptul că o imagine poate fi adnotată cu mai multe concepte (multi-label classification ⁶²), am ales să antrenez câte un clasificator SVM pentru fiecare dintre cele 94 de concepte, iar outputul mașinilor cu vector suport (SVMs) va fi postprocesat asigurându-se astfel consistența relațiilor dintre adnotările făcute automat. O altă abordare⁶³ pe care am implementat-o (dar cu rezultate slabe) pentru a rezolva problema clasificării multi-label a fost următoarea: fiecare combinație de clase găsită în imaginile de antrenament a fost considerată o singură clasă pentru fiecare din instanțe (imagini care au aceleași combinații de concepte). Această abordare generează un număr mare de clase (combinații de concepte), cu un număr mic de instanțe reprezentative pentru fiecare din clasele respective.

Pentru implementarea mașinilor cu vector suport am folosit librăria Libsvm⁶⁴ (versiunea 3.11 cu mici modificări pentru a asigura compatibilitatea cu sistemul propus) utilizând kernelul preconstruit (en. Precomputed) (distanțele dintre imagini se calculează separat) ce necesită construcția unei matrice Gram⁶⁵ cu formatul din Tabelul 3:

Pentru un set de date de antrenare de 3 instanțe și un set de date de test de 1 instanță definite ca în exemplul următor:

15 1:1 2:1 3:1 4:1 45 2:3 4:3 25 3:1

15 1:1 3:1

Dacă se folosește kernelul linear, noile date de antrenare/test vor fi:

62 http://en.wikipedia.org/wiki/Multi-label_classification

63 Abordare inspirată din: http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/multilabel/

64 http://www.csie.ntu.edu.tw/~cjlin/libsvm/

65 http://www.encyclopediaofmath.org/index.php/Gram_matrix

15 0:1 1:4 2:6 3:1 45 0:2 1:6 2:18 3:0 25 0:3 1:1 2:0 3:1

15 0:? 1:2 2:0 3:1

? poate fi orice valoare.

Orice subset al acestor date este de asemenea valid. De exemplu:

25 0:3 1:1 2:0 3:1 45 0:2 1:6 2:18 3:0

Tabelul 3: Formatul libsvm pentru kernel-ul preconstruit, sursa: Libsvm Readme

O funcție kernel (folosită în cazul mașinilor cu vector suport) este o funcție continuă, simetrică și pozitiv semi-definită (Teorema lui Mercer – Secțiunea 2.2), iar aceasta poate fi gândită ca o funcție ce descrie apropierea (similaritatea) între două imagini. Pe baza descriptorilor vizuali descriși mai sus, am propus o funcție kernel ce combină toți cei patru descriptori:

( ) ( ) ( ) ( ) ( ) Unde , (astfel încât ) sunt contribuții pentru funcțiile kernel:

 ( ) ( ( ) ( )), sau ( ) ( ( ( ) ( ))) unde este funcția de similaritate cosinus (iar este distanța absolută) definită în secțiunea 2.5, ( ) este descriptorul TopSurf definit în aceeași secțiune, iar este parametrul de regularizare. În majoritatea testelor am folosit similaritatea cosinus.

 ( ) ( ) este kernel-ul RBF ce calculează distanța dintre descriptorii PEF (secțiunea 2.1).

 ( ) ^{( ) ( )} este kernel-ul definit în secțiunea 2.6 ce numără câte tag-uri definite de utilizatori (asociate imaginilor respectiv, ) sunt partajate, iar rezultatul este normalizat cu numărul de tag-uri prezente în vocabularul preconstruit.

 ( ) ( ( )) este kernel-ul bazat pe momentele culorii (secțiunea 2.7), fiind funcția de similaritate din aceași secțiune, iar este parametrul de regularizare.