Tehnici inteligente pentru analiza si clasificarea colectiilor de imagini (CBIR - Content Based Image Retrieval)

Program de cercetare stiintifica pentru elaborarea tezei de doctorat

Tehnici inteligente pentru analiza si clasificarea colectiilor de imagini

(CBIR - Content Based Image Retrieval)

Tema propusa

Domeniul CBIR isi propune rezolvarea problemei de gasire a unor imagini similare intr-o baza de date multimedia, utilizand ca si elemente de cautare componentele descriptive ale imaginii: culoare, textura si forma..

Tehnica clasica, utilizata de primele sisteme de cautare in bazele de date multimedia, se bazeaza pe adnotarea fiecǎrui fisier multimedia utilizand metadate, dar acestea sunt dificil de completat si de foarte multe ori ineficiente. Alaturi de algoritmii de cautare a imaginilor dupa continut se utilizeaza si tehnici de relevance feedback, care folosesc feedback-ul utilizatorilor sistemului pentru imbunatǎtirea rezultatelor cautǎrii in baza de date. Tema propusa are ca scop imbunatatirea, optimizarea algoritmilor existenti si creearea de noi algoritmi utilizati in sistemele de cautare a imaginilor dupa continut si a tehnicilor de relevance feedback pe care le insotesc.

Prezentarea proiectului

Primele lucrari care isi propuneau descrierea continutului multimedia, utilizand vectori de descriptori, au aparut in anii '80 si inceputul anilor '90 (Ballard and Brown 1982, Levine 1985, Haralick and Shapiro 1993), in timp ce primele sisteme de cautare a continutului media QBIC( Query By Image Content) abia la mijlocul anilor '90: Kato 1992, Flickner 1995 si Virage Bach 1996. Alaturi de tehnicile clasice care utilizeaza caracteristicile de nivel jos ale imaginilor, sistemele CBIR au integrate metode de retinere a feedback-ului utilizatorului, denumite "relevance feedback" datorita similaritatii cu tehnicile mai vechi de imbunatatire a sistemelor de cautare a documentelor text.

Relevanta ariei tematice in care se incadreaza tema propusa

Este simplu de observat ca imaginile sunt utilizate in foarte multe aspecte ale vietii obisnuite. Spre exemplu, influenta televiziunii sau a jocurilor pe calculator in societatea de astazi este usor de vizualizat. Deci, cel mai comun si simplu motiv pentru adunarea, transmisia si afisarea de imagini este in scopul recreearii si distractiei, crearii de retelele sociale (ex: gasire imagini asemanatoare pentru persoane diferite). De asemeni, fotografia e un domeniu care a luat amploare exponentiala in ultimii 20 de ani, odata cu aparitia camerelor digitale si a internetului. Galeriile de arta online, cat si imaginile cu vedete/sportive/artisti, sunt de asemeni un alt exemplu de utilizare a imaginilor pe internet.

Alaturi de utilizarea clasica a imaginilor, exista numeroase domenii profesionale, cu diverse constrangeri, care necesita diverse tehnici de optimizare.

Medicina si profesiile asociate utilizeaza la scara larga imaginile in procesul de diagnosticare si prevenire, utilizand o gama variata de aparate imagistice: raze X, ultrasunete etc. Sistemele CBIR sunt utilizate in diagnosticare si monitorizare in domenii ca oncologie, ortopedie, medicina interna, neurologie, radiologie.

Moda si design - Imaginile sunt foarte importante in creatiile de modǎ si in designul industrial. Vizualizarea diverselor pǎrti componente sunt esentiale in procesul de creatie, dar in acelasi timp, observarea creatiilor deja existente cu elemente asemanatoare. Tehnici de modelare 2D si 3D sunt utilizate pentru vizualizarea noilor produse in perioada de proiectare si compararea acestora cu imagini deja existente.

Arhitectura si designul ingineresc sunt alte doua domenii cu utilizare intensiva a imaginilor. Fotografiile sunt utilizate in arhitectura pentru a inregistra interiorul si exteriorul clǎdirilor, si utilizarea lor in diverse scopuri: publicitate, cǎutare de modele s.a.m.d. in inginerie, sau pentru proiectare, utilizand tehnologiile de proiectare CAD 2D si 3D.

Alte domenii importante de utilizare a sistemelor de cautare dupa continut sunt: securitate, publicitate, arheologie, aplicatii militare, robotica, proprietate intelectuala, cultura, educatie si lista poate continua cu usurinta.

Importanta stiintificǎ a temei propuse si caracterul de cercetare fundamental

Volumul muncii de cercetare a algoritmilor de cautare a imaginilor dupa continut este in continua crestere, insa nu se poate spune ca sistemele au atins o performanta semnificativa pentru sisteme generale, rezultatele fiind relevante doar daca se utilizeaza pentru un singur tip de imagini (exemplu: imagini medicale). De asemeni sunt cercetate diverse metode pentru segmentarea imaginilor si extragerea obiectelor din background, cat si noi paradigme pentru imbunatatirea tehnicilor de extragere a descriptorilor, dar si noi metode de reprezentare mai apropiate de sistemul de vizualizare/recunoastere uman.

Un sistem clasic de cautare a imaginilor dupa continut are trei componente de baza: Indexator, Retriever si Browser. in figura 1 este prezentat o schema tipica a unui sistem de cautare dupa continut.

Pentru interogarea bazei de date se utilizeaza asa zisul concept query by example (interogare prin exemple). Utilizatorul incarca in sistem imaginea dorita pentru cautare, iar sistemul calculeaza descriptorul asociat acestei imagini si il compara cu descriptorii stocati in baza de date.

Figura 1: Schema tipica a unui sistem de descriere a continutului si cautare a imaginilor.

Un alt model de sistem CBIR il reprezinta sistemele care permit cautarea unor anumite obiecte din imagini (subquery). Aceste sisteme au incorporate un sistem de segmentare a obiectelor din imagini[10], fiecare obiect fiind inregistrat in baza de date ca imagini separate. Apoi, cautarea se face tinand cont de obiectele compoente[8] sau de distributia acestora in imagine.

Figura 2: Schema tipica a unui sistem de descriere a continutului si cautare a imaginilor utilizand tehnici de sub-query

Pe langa cercetarea tehnicilor prezentate anterior, importante studii se fac pentru inlaturarea efectului de "semantic gap". "Diferenta semantica" caracterizeaza diferenta dintre doua descrieri ale unui obiect, utilizand diferite reprezentari lingvistice si simbolice. În Computer Vision Conceptual este relevant atunci cand incercam sa reprezentam diferite scene utilizand o reprezentare computationala. Interpretarea semantica a unei imagini are, de foarte multe ori, o foarte mica legatura cu corelatia statistica a valorilor pixelilor.Un exemplu explicativ il gasim in figura 3:

Un alt exemplu relavant de semantic gap il gasim in figura 4:

Figura 4: Cele doua imagini au forma, textura si forma asemanatoare, dar sensuri complet diferite.

Pentru inlaturarea acestei probleme se utilizeaza algoritmi de relevance feedback. Ideea principala din spatele acestui concept consta in prezentarea utilizatorului unui set de imagini candidat, acesta marcheaza imaginile relevante si irelevante dupa care sistemul va modifica spatiul descriptorilor, spatiul semantic sau spatiul de clasificare, astfel incat sa reflecte feedbackul acordat de utilizator. În mod particular, relevance feedback poate fi privit ca o tehnica de clasificare de patern, sistemul utilizand raspunsul returnat de utlizator pentru o antrenare continua a sistemului.

Stadiul actual al cunoasterii in aria in care se incadreaza tema

Studiul sistemelor de cautare a imaginilor a inceput la sfarsitul anilor '80 si s-a dezvoltat cu rapiditate odata cu marirea tehnologiilor hardware de procesare si de stocare. Imaginile au fost utilizate pentru:

Ilustrarea unor texte (cum ar fi emotiile, care sunt greu de descris)

Date detaliate (ex: radiografii pentru diagnostic si determinare evolutie)

Înregistrare componente de proiectare

Pentru a accesa si a cauta imagini este nevoie de un set de interogari, care trebuie adresate sistemului, iar acestea ar putea fi spre exemplu:

prezenta unei anumite combinatii de culoare, textura, forma

prezenta unui aranjament specific a unor obiecte (ex: mai multe obiecte asezate intr-o anumita forma)

prezenta unei persoane/ locatii/ eveniment (ex: 1 Decembrie - parada militara)

emotii subiective (ex: bucurie, suparare)

metadate ajutatoare

Exista trei tipuri de interogari pe care un sistem CBIR le poate primi, in functie de gradul de abstractizare a interogarii. Eakins [1998] a definit trei nivele de interogari:

nivelul 1: foloseste descriptori primitivi precum culoarea, textura, forma, distributia spatiala a elementelor unor imagini

nivelul 2: cautarea unor imagini care contin anumite obiecte (asa numita tehnica de

subquery). Poate fi impartita in doua tipuri de interogari:

cautare a unor obiecte de un anumit tip

(ex: imagini cu masini, animale etc)

cautare a unor obiecte anume (ex: imagini cu turnul din Pisa)

nivelul 3: cautarea se face dupa termeni abstracti, sistemele avand nevoie de putere de procesare considerabila, si au rolul de interpretare si intelegere a scenelor din imagini.

Acest nivel contine mai multe tipuri de interogari:

regasirea unor evenimente si tipuri de activitati (ex: gaseste imaginile in care se joaca hora)

regasirea de imagini care contin emotii sau semnificatii religioase (ex: gaseste o imagine care contine un botez)

Cele mai importante studii au fost efectuate pentru sisteme de nivel 1. Dupa cum am aratat acestea utilizeaza trei tipuri de informatie: culoare, textura si forma.

Culoarea este principala tehnica de descriere a imaginilor. Majoritatea tehnicilor de descriere se bazeaza pe tehnici de histograma: histograma normala, augmentata, netezita, ponderata, fuzzy, utilizand diverse spatii de culoare: grayscale, RGB, HSV, Lab, HMMD, YcbCr etc.

Textura e o alta tehnica de descriere a imaginilor. Pentru descrierea imaginilor utilizand texturi, se folosesc parametrii statistici ca: matricea de coocurenta (parametrii Haralick), corelograma, autocorelograma, matricea de izosegmente (parametrii Gallaway, Chu si Dasarathy), masuri de entropie, analiza fractala si metode auto-regresive.

Forma, in metodele traditionale, este descrisa de catre diversi parametrii de forma: arie, perimetru, raze, anvelope, skeletron, momente statistice impreuna cu invariantii Hu, semnatura formei, descriptori Fourier de contur si transformata Hough.

Primul standard oficial pentru descrierea imaginilor dupa continut a fost MPEG 7. Acesta contine mai multe grupuri de descriptori: culoare, textura, forma, miscare, localizare si sunet. Culoarea are definite cinci descriptori pentru descrierea imaginii:

Dominant Color Descriptor (DCD)

Scalable Color Descriptor (SCD)

Color Structure Descriptor (CSD)

Color Layout Descriptor (CLD)

Group of frame (GoF) or Group-of-pictures (GoP)

Color Histogram Descriptor reprezinta o cuantizare a spatiului culorilor, putand utiliza diverse nivele de cuantizare cat si spatii de culoare distincte: RGB, HSV, YCbCr si nou definitul HMMD. Color layer Descriptor preia distributia culorilor in imagine intr-un grid de dimensiuni 8x8 si apoi acestea sunt codate, utilizand transformata DCT. Color Structure Descriptor utilizeaza un element structurant de dimensiuni diverse si baleiaza imaginea, formand o histograma ponderata.

MPEG 7 defineste doua tipuri de descriptori de textura: descriptori omogeni si neomogeni. Descriptorii omogeni creeaza partitii in domeniul frecventei, utilizand transformate Gabor 2D si calculeaza energia si deviatia de energie intre aceste canale. Descriptorii neomogeni calculeaza distributia spatial a 5 tipuri de muchii: orizontal, vertical, 135, 45 si nondirectional dupa care se construieste o histograma a muchiilor pentru diverse zone ale imaginii.

Pentru descrierea formelor se definesc patru tipuri de descriptori: Region-based Descriptor, Contour-based Shape Descriptor, 2D/3D Shape Descriptor si 3D Shape Descriptor.

Algoritmii de relevance feedback au aparut spre sfarsitul anilor '90, ca urmare a descoperirii neajunsurilor descrierii imaginilor, utilizand descriptori de nivel 1. Primele abordari au utilizat algoritmi de relevance feedback din domeniul sistemelor de documente text, cum ar fi Rochio, impreuna cu o multime de variante derivate, dupa care, pe piata au aparut versiuni de algoritmi ce se bazau pe modificarea metodelor de calcul a distantelor dintre imagini, utilizand feedback-ul utilizatorilor(algoritmi de estimare a importantei feature-lor si algoritmul Robertson Sparck-Jones).

Principalele doua abordari in creearea de algorimi de relevance feedback au fost:

- abordari statistice

- abordari utilizand retele neurale.

Abordarile statistice utilizeaza in principiu Naïve Bayes(PicHunter - I.J. Cox 2000) si retele bayesiene (Su Zhong, Hongjiang Zhang, Ma Shaoping 2003), dar si algoritmi cu arbori de decizie. Retelele neurale utilizate in clasificarea colectiilor de imagini au fost retele SOM (picSOM - Laaksonen, Jorma 2001), retelele SVM (Yunqiang Chen, Xiang Zhou, and Thomas S. Huang 2001), relele RBF, retele fuzzy etc.

Contributia potentiala la tematica stiintifica vizata de proiect

Domeniul "Content Based Image Retrieval" a aparut si s-a dezvoltat ca urmare a revolutiei informationale generatoare de cantitati enorme de informatie in domeniul multimedia.

Principalele directii actuale de cercetare in domeniu sunt:

Metode imbunatatite (noi features) si noi distante de similaritate pentru cautare si gasire a imaginilor si a fisierelor video similare

Integrarea aplicatiilor in sisteme distribuite web

O interactiune user-sistem imbunatatita, incluzand tehnici noi de image-browsing si de exploatare a feedbackului utilizatorului

Tehnici de segmentare automata, atat in imagini cat si video, facilitate de tipul query-by-motion si integrarea in sisteme de cautare video

Noi algoritmi de imbunatatire a performantelor utilizand informatii primite de la utilizator (relevance feedback)

Fezabilitatea contributiilor potentiale produse

Studile efectuate in acest domeniu au o aplicabilitate directa, asa cum am aratat anterior, in domenii diverse: medicina, multimedia, design, arhitectura, securitate, publicitate, arheologie, aplicatii militare, robotica, proprietate intelectuala, cultura, educatie. Avansul studiului in acest domeniu are un efect pozitiv asupra intelegerii cantitatii tot mai mare de date disponibile, a filtrarii si a cautarii acesteia.

Cercetarile mele se vor efectua in cadrul laboratorului de Analiza si Prelucrarea Imaginilor in Facultatea de Electronica, Telecomunicatii si Tehnologia Informatiei. Suportul software disponibil permite implementarea atat a bazelor de date centralizate cat si a celor distribuite.

Tema propusa are ca scop imbunatatirea, optimizarea algoritmilor existenti si creearea de noi algoritmi utilizati in sistemele de cautare a imaginilor dupa continut si a tehnicilor de relevance feedback pe care le insotesc.

Bibliografia

[1] C. Vertan, M. Ciuc: Cautarea imaginilor prin similaritatea continutului: o introducere, Ed. Printech, Bucuresti, 2002, ISBN 973-652-529-5

[2] I. Mironica, C. Vertan: "Relevance Feedback Approaches for MPEG-7 Content-based Biomedical Image Retrieval"

[3] A. W. Smeulders, M. Worring, S. Santini, A. Gupta, R. Jain - "Content-based Image Retrieval at the end of the Early years", IEEE Trans. on PAMI, vol. 22, no. 12, Dec. 2000, pp. 1349 - 1380.

[4] S. Santini - "Exploratory Image Databases Content-based Retrieval", Academic Press, 2001

[5] MPEG-7: ISO/IEC 15938-1: "Multimedia content description interface, part I: Systems", 2002

[6] M. Arrevallilo-Herraez, M. Zacares, X. Benavent, E. de Ves: "A relevance feedback CBIR algortihm based on fuzzy sets", Signal Procesing: Image Communications, vol. 23, 2008, pp. 490-504.

[7] Theo Pavlidis: "Limitations of Content-based Image Retrieval" Caracteristicile de baza ale domeniului procesarii de imagini

A.H.Kam, T.T.Ng, N.G.Kingsbury and W.J.Fitzgerald - "Content Based Image Retrieval through Object Extraction and Querying"

[9] Hui Hui Wang, Dzulkifli Mohamad: "Semantic Gap in CBIR: Automatic Objects Spatial Relationships Semantic Extraction and Representation"

Chad Carson, Megan Thomas, Serge Belongie, Joseph M. Hellerstein, and Jitendra Malik:

Blobworld: A System for Region-Based Image Indexing and Retrieval"

[11] John Eakins, Margaret Graham - University of Northumbria at Newcastle - "Content-based Image Retrieval"

[12] MICHAEL S. LEW Leiden University, The Netherlands and NICU SEBE University of Amsterdam, the Netherlands and CHABANE DJERABA LIFL, France and RAMESH JAIN University of California at Irvine, USA: "Content-based Multimedia Information Retrieval: State of the Art and Challenges"

[13] CNN.com - "Microsoft, Google expand search engine tools" https://edition.cnn.com/2009/ TECH/09/16/visual.web.bing.google/index.html