Cautarea bazata pe similaritate a imaginilor folosind structuri de index

În ultimii ani, din ce în ce mai multă informaţie multimedia în format digital este generată şi pusă la dispoziţia diverşilor utilizatori. În multe domenii de activitate precum biomedicină, meteorologie, comerţ, explorarea spaţiului, educaţie, divertisment, apărare, etc., cantităţi voluminoase de date apar în format imagine.

Ca rezultat, a apărut nevoia dezvoltării unor noi metode de organizare şi găsire a datelor dintr-o bază de date multimedia. Aşa au apărut sistemele CBIR (“content based image retrieval”), bazate pe mecanisme de extragere a imaginilor din baza de date în funcţie de conţinutul lor.  Aceasta a constituit o mare provocare pentru cercetătorii ultimei decade, datorită complexităţii cuantificării unei imagini într-o mulţime adecvată de caracteristici şi a găsirii unei modalităţi eficiente de aflare a imaginilor similare pe baza acestor caracteristici. Într-un sistem vizual uman, culoarea şi forma sunt aspecte fundamentale.  Deci, şi într-un sistem CBIR, se vor utiliza în principal caracteristici ale imaginilor precum culoare şi formă.

            Mai mult, întrucât bazele de date multimedia sunt în general voluminoase, este foarte important ca, determinarea porţiunilor din baza de date care sunt relevante pentru cererile utilizatorilor, să se facă rapid şi eficient. De aceea, procesul de extragere a imaginilor în funcţie de conţinut, trebuie să fie susţinut de tehnici adecvate de indexare care să suporte execuţia interogărilor bazate pe similaritate. 

            În continuare, vom prezenta o metodă de regăsire a imaginilor dintr-o bază de date, pe baza conţinutului acestora.  Metoda utilizează structura de index numită arbore M (M-tree).

            Elaborarea metodei presupune parcurgerea mai multor etape. Întâi, imaginile sunt procesate cu scopul de a obţine pentru fiecare imagine un vector de caracteristici, compus din elemente care descriu forma obiectelor din imagine şi din elemente care descriu culoarea imaginii.  Apoi, aceşti vectori caracteristici se vor indexa în arbore. Măsura de similaritate utilizată în rezolvarea interogărilor este metrica d din cadrul arborelui M. Este o măsură calculată ca o combinaţie liniară a două distanţe: pentru elementele de formă se calculează distanţa euclidiană, iar pentru cele de culoare se calculează distanţa Manhattan, în final însumându-se cu ponderi diferite cele două valori obţinute.

            Vom prezenta pe larg etapele amintite mai sus.

1.2 Procesarea imaginilor

Vom presupune că imaginile au un conţinut oarecum omogen, deci ne vom concentra atenţia asupra unor caracteristici simple şi imediate, cum ar fi forma şi culoarea.

Extragerea caracteristicilor constă din doi paşi (Fig. 3): determinarea vectorului caracteristic pentru formă şi determinarea vectorului caracteristic pentru culoare (vezi Anexa A). În final, imaginea va fi reprezentată de un vector compus din elementele celor doi vectori.

 

Fig. 3: Procesarea imaginilor

1.3 Indexarea vectorilor caracteristici

 

Fiecare obiect al bazei de date care se va indexa, nu va fi reprezentat de imaginea în sine, ci de vectorul caracteristic corespunzător imaginii.

Amintim că arborele M (utilizat pentru indexare) poate fi văzut ca o ierarhie de regiuni sferice. O regiune este definită de un obiect O_i al bazei de date şi de raza r(O_i) care reprezintă maximul distanţei dintre O_i şi oricare alt obiect din regiunea lui O_i. Fiecare nod al arborelui M poate conţine mai multe intrări corespunzătoare obiectelor care fac parte din regiunea centrată în jurul obiectului părinte O_p, stocat într-un nod de la un nivel mai înalt. Regiunea de obiecte din rădăcină reprezintă întregul univers, deoarece aceste obiecte nu mai au nici un alt obiect părinte. 

În cadrul aplicaţiei, structura de index rezidentă pe disc este construită prin inserări succesive de tipul “tuple insertion”, adică fiecare vector caracteristic al unei imagini este inserat separat.

Un nod frunză este conceptual o sferă şi are următoarele câmpuri: un centru de tipul unui vector multi-dimensional de elemente numerice (care este chiar vectorul caracteristic pentru o imagine din baza de date), o rază care este 0, şi distanţa până la părintele său aflat pe un nivel imediat mai înalt în arbore.

Un nod intern are aceleaşi câmpuri, exceptând faptul că raza este mai mare ca 0, iar nodul rădăcină are distanţa către părintele său egală cu 0.

În vederea construirii indexului, s-au stabilit şi următorii parametri: 

§  capacitatea minimă a nodurilor (numărul minim de obiecte care pot fi grupate într-un nod intern);

§  capacitatea maximă a nodurilor (numărul maxim de obiecte care pot fi grupate într-un nod intern);

§  numărul maxim de noduri care se poate memora într-un bloc ce se va scrie pe disc;

§  nivelul ţintă (“target level”) pentru interogări (implicit 0).

Divizarea nodurilor pline se face după strategia hiperplan (“generalized hyperplane”) care conduce la divizări ne-echilibrate.

Amintim, de asemenea, că arborele M este complet parametrizat de o distanţă specifică d, pe baza căreia se măsoară distanţele relative între obiecte iar apoi se  partiţionează şi se stochează aceste obiecte în nodurile sale.

Distanţa d se va utiliza ca o măsură de similaritate în rezolvarea interogărilor. Arborele M este flexibil în sensul că permite definirea oricărei funcţii d, care să respecte numai axiomele unei metrici (pozitivitate, simetrie şi inegalitate a triunghiului).

În cadrul aplicaţiei am utilizat o distanţă d, calculată ca o combinaţie lineară afină a două metrici L_p. Distanţa între două obiecte este, de fapt, distanţa între două sfere ale căror centre sunt reprezentate de vectori caracteristici  multi-dimensionali.

Fie  şi cei doi vectori caracteristici, unde N este numărul elementelor caracteristice pentru formă iar M este numărul elementelor caracteristice pentru culoare.

Vom combina forma şi culoarea – calităţi primare ale unei imagini, astfel: pentru elementele caracteristice de formă vom calcula distanţa Euclidiană, pentru elementele caracteristice de culoare vom calcula distanţa Manhattan, iar în final vom însuma cele două valori cu ponderi diferite:

Distanţa Euclidiană (normă L₂):

Distanţa Manhattan (normă L₁):

Distanţa d: , unde a+b=1

 

Fiecare dintre cele două norme are avantajele şi dezavantajele ei atunci când se aplică la regăsirea imaginilor pa baza similarităţii. De exemplu, norma L₁ poate cauza ca prea puţine din imaginile care ar trebui returnate să fie efectiv găsite, iar  norma L₂ poate cauza ca prea multe imagini (şi cele care sunt prea puţin similare) să fie returnate.

Combinând cele două norme în distanţa utilizată, vom reduce din efectul negativ al fiecăreia în parte. În plus, se poate accentua contribuţia unui anume set de caracteristici care sunt considerate mai importante în descrierea unei imagini.

Se observă imediat că funcţia d respectă cele trei axiome ale unei metrici.

software.ucv.ro/Cercetare/Rapoarte_tehnice/.../Raport_Academie2.doc