regasirea informatiei vizuale pe baza caracteristicii culoare

SISTEME DE REGASIRE A INFORMATIEI VIZUALE

Regasirea informatiei vizuale pe baza caracteristicii culoare

Profesor: Student:

Liana Stanescu Amza Ionut Catalin


Introducere

Culoarea este caracteristica vizuala care este imediat perceputa intr-o imagine. Sistemul de culoare folosit pentru a reprezenta informatia culoare intr-o imagine are o mare importanta in interogarea de imagini bazata pe continut, deci aceasta directie de cercetare a fost intens studiata.

Nu exista un sistem de culori care sa fie folosit universal, deoarece notiunea de culoare poate fi modelata si interpretata in diferite moduri. Fiecare sistem are modelele sale de culoare care reprezinta parametrii sistemului.

Au fost create cateva sisteme de culori, pentru diferite scopuri: RGB (pentru afisarea procesului), XYZ (pentru standardizarea culorilor), rgb, xyz (pentru normalizarea si reprezentarea culorii), etc.

Au fost propuse sisteme pentru regasirea pe baza de continut care utilizeaza diferite tehnologii pentru reprezentarea caracteristicilor culorii: histograme de culoare, momente de culoare, textura culorii, si altele. Acestea utilizeaza sisteme de culoare ca: RGB, HIS, L*a*b* sau L*u*v*.

Modele de culori

Modelul RGB este un model aditiv, având culorile fundamentale rosu, verde si albastru, celelalte culori constituindu-se din anumite procente ale culorilor de bazã. Culoarea alb are prezente toate culorile fundamentale, iar culoarea negru se caracterizeazã prin absenta lor. Modelul RGB este adesea reprezentat sub forma unui cub unitate, ca în figura 1

: Fig. 1. RGB color space

Originea (0, 0, 0) este consideratã culoarea negru, iar coltul opus (1, 1, 1) corespunde culorii alb. Diagonala care uneste aceste douã puncte conþine nivelurile de gri obtinute prin utilizarea aceluiasi procent din culorile de bazã.O altã metodã de clasificare a culorilor este prin nuantare (Hue), saturatie (Saturation) si intensitate (Intensity), rezultând modelul HSI.Nuanta reprezintã pozitia relativã a culorii în spectru si, în modelul HSI, corespunde unghiului pe care îl face culoarea în cercul de culori. Domeniul de nuantare se întinde de la 0 la 360 de grade.Saturatia reprezintã puritatea culorii. Valoarea saturatiei se exprimã în procente si variazã de la 0 (fãrã culoare) pânã la 100 (culoare purã, asa cum este definitã de valoarea nuantãrii).


Ultimul parametru reprezintã intensitatea culorii. O reprezentare simbolicã a modelului HSI este datã în figura 2. Nuanta determinã culoarea (unghi = 60° - Yellow, 180° - Cyan etc.) Saturaþia este mãsuratã în procente de la centrul cercului de bazã la suprafata conurilor.Intensitatea se mãsoarã pe linia Black-White.

Fig.2 HSI ModelModelul CMY are la bazã culorile Cyan, Magenta si Yellow, considerate culori secundare fatã de culorile Red, Green, Blue.Este utilizat pentru specificarea culorilor la dispozitivele de imprimare. Foloseşte acelaşi sistem de coordonate şi acelaşi subspaţiu al culorilor ca şi modelul RGB cu deosebirea că originea corespunde culorii alb, vîrful (1,1,1) culorii negru iar culorile primare sunt cian, magenta şi galben .In acest model, o culoare se specifică prin trei valori cuprinse între 0 şi 1, reprezentînd proporţiile în care trebuie să fie amestecaţi cei trei pigmenţi ce extrag componentele luminii albe. Culoarea negru se obţine amestecînd în proporţii maxime culorile primare. In general însă, datorită imperfecţiunilor cernelurilor, prin amestecul în proporţii maxime al celor trei pigmenţi nu se obţine negru. De aceea, în loc de CMY se utilizează sistemul CMYK:K= min(C,M,Y), C = C – K , M = M – K , Y = Y – KConversia unei culori din modelul RGB în modelul CMY şi invers este foarte simplă. Ea poate fi exprimată astfel:[C M Y] = [1 1 1] – [R G B]respectiv[R G B] = [1 1 1] – [C M Y]

Histograme de culoare

O metoda uzuala de a reprezenta o imagine este de a o transforma intr-o histograma.De exemplu, o imagine care contine diferite nivele de gri poate fi transformata intr-o histograma care defineste numarul de pixeli ai fiecarei culori(nivel de gri). Pentru imaginile color, histogramele de culoare pot avea o dimensiune mai mare decat 2, deoarece culorile sunt reprezentate ca vectori cu 3 componente.


Fig 2: Histograma pentru o imagine cu nivele de gri

Pentru o imagine specifica exista o singura histograma, dar diferite imagini pot sa aiba histograme identice.

Definitie: Distributia culorilor intr-o imagine, regiune sau obiect este reprezentata de o histograma.

Regasirea informatiei vizuale pe baza caracteristicii culoare

În această faza se vor prezenta cinci metode utilizate în calcularea similitudinii color a imaginilor pe baza histogramelor. Aceste tehnici pot fi utilizate în sistemele de căutare şi regăsire a imaginilor pe baza caracteristicilor lor.

Aşa cum s-a precizat anterior, histogramele indică distribuţia culorilor într-o imagine sau regiune. Pentru că histogramele sunt distribuţii discrete, ele pot fi reprezentate ca vectori de caracteristici într-un spaţiu M-dimensional, unde M reprezintă numărul de culori distincte din histogramă. Acest spaţiu se defineşte ca fiind spaţiul histogramă, HM.

Spaţiul histogramă HM se consideră un spaţiu metric, iar histogramele h sunt puncte în acest spaţiu, dacă sunt adevărate următoarele condiţii: pentru fiecare pereche de histograme h i, hj

poate fi găsit un număr corespunzător v(hi,hj), numit distanţa între punctele hi si hj care satisface următoarele:

1. v(hi,hj) = 0 ( identitate )2. v(hi,hj) >= 0 ( ne-negativitate )3. v(hi,hj) = v(hj,hi) >= 0 (dacă hi # hj) (comutativitate / simetrie )4. v(hi,hq) <= v(hi,hj) + v(hj,hq) ( inegalitatea triunghiului )


1.Distanţe bazate pe forma Minkowski

Prima clasă de măsuri de disimilitudine se bazează pe forma Minkowski. Fie hq

histograma interogare şi ht histograma ţinta. Atunci distanţa între cele două histograme se defineşte astfel:

dq , tr =∑

m=0

M−1

|hq [m ]−ht [m ]|r

Aşa cum se vede şi în figura 3-1, măsurarea disimilitudinii histogramelor cu ajutorul formei Minkowski neglijează compararea elementelor din histograme care sunt similare, dar nu identice. De exemplu, o imagine roşu închis este egal diferită de o imagine roşie ca şi de o imagine albastră.

Complexitatea metodei este O(m*n) unde m reprezintă numărul de culori rezultate în urma procesului de cuantificare ( de exemplu: 166, sau 64 sau 512), iar n reprezintă numărul de imagini din baza de date.

Fig.Distanţele bazate pe forma Minkowski compară numai elementele identice ale histogramelor

m

hq[m]

m

ht[m]


2.Intersecţia histogramelor

Swain şi Ballard au fost cei care au investigat utilizarea intersecţiei histogramelor în regăsirea imaginilor color. Obiectivul lor a fost acela de a găsi, cu ajutorul histogramelor color, obiecte cunoscute în cadrul imaginilor. Atunci când mărimea obiectului q este mai mică decât mărimea imaginii t şi histogramele nu sunt normalizate, avem : | hq | <= | ht |.

Intersecţia histogramelor hq şi ht este dată de:

dq , t=1−∑m=0

M−1

min(hq[ m ] ,h t [m ])

|hq|

unde |h|=∑

m=0

M −1

h[ m ]

Ecuaţia de mai sus nu defineşte o distanţă validă pentru că nu este simetrică: dq,t # dt,q , dar poate fi modificată în acest sens astfel :

dq , t' =1−

∑m=0

M−1

min(hq[ m ] ,h t [m ])

min (|hq|,|h t|)

S-a arătat că atunci când histogramele sunt normalizate, astfel încât | hq | = | ht | intersecţia histogramelor este dată de:

dq , t=∑m=0

M−1

|hq [m ]−ht [m ]|

Se vede că dq,t este o metrică bazată pe forma Minkowski cu r=1.

Complexitatea metodei este O(m*n) unde m reprezintă numărul de culori rezultate în urma procesului de cuantificare ( de exemplu: 166, sau 64 sau 512), iar n reprezintă numărul de imagini din baza de date.


3.Distanţa euclidiană între histograme

Distanţa euclidiană este o metrică bazată pe forma Minkowski cu r=2. Dându-se două histograme hq si ht, atunci:

dq , t=∑m=0

M−1

(|hq [ m ]−ht [ m ]|)2

Complexitatea metodei este, de asemenea,O(m*n) unde m reprezintă numărul de culori rezultate în urma procesului de cuantificare, iar n reprezintă numărul de imagini din baza de date.

În vederea creşterii eficienţei calculului distanţei euclidiene între histograme, J.R.Smith în [3] a propus următoarea descompunere:

dq,t = hTqhq + hT

tht -2 hTqht

Atunci când | hq |= hTqhq =1 si | ht |= hT

tht =1, avem:

dq,t =2-2 hTqht

Conform acestei descompuneri, distanţa dq,t se calculează cu ajutorul produsului între histograma interogare hq şi cea ţintă ht.

4.Distanţa Hamming pentru seturi binare

Se consideră cazul special în care histogramele sunt aproximate prin seturi binare. Un set binar s este un vector binar în spaţiul binar M dimensional BM.

Distanţa Hamming între seturile binare sq şi st , unde

| s | = m s[m], este :

| sq - st |

dq,t =

| sq | | st |


Distanţa Hamming se calculează în mod eficient utilizând operatorul OR exclusiv. Deci, este uşor de calculat, de aceea se utilizează în aplicaţiile de baze de date cu imagini, baze de date de dimensiuni mari. Complexitatea metodei este O(m*n), unde m şi n au aceeaşi semnificaţie ca mai sus.

Fig.Distanţa Hamming între seturi color calculează OR exclusiv între elemente. " * " indică poziţiile în care biţii diferă.

5.Distanţa pătratică

Distanţa pătratică compară toate elementele histogramelor şi ponderează distanţa între elemente prin anumiţi factori.

6. Distanţa pătratică între histograme

Distanţa pătratică între histogramele hq şi ht este dată de formula:

dq , t=∑m0=0

M−1

∑m1=0

M−1

(hq [ m0 ]−ht [m0 ])am0 m1(hq[ m1]−ht [m1 ])

unde A=[a i,j] , iar a i,j reprezintă similitudinea între elementele cu indecşii i si j.

Metrica pătratică este o distanţă metrică adevărată când

a i,j = a j,i ( simetrie ) şi a i,i =1.

* * * * m

ht[m]

m

hq[m]


Fig.Distanţa pătratică compară toate elementele histogramelor şi ponderează distanţa între elemente prin elementele a i,j.

Într-o implementare obişnuită, calculul distanţei pătratice este mult mai complex decât cel al distanţelor bazate pe forma Minkowski, deoarece calculează similitudinea încrucişată între toate elementele.

Complexitatea metodei este O(m^2*n) unde m reprezintă numărul de culori rezultate în urma procesului de cuantificare ( de exemplu: 166, sau 64 sau 512), iar n reprezintă numărul de imagini din baza de date.

Tot în vederea scăderii timpului de lucru pentru distanţa pătratică între histograme, J.R.Smith a propus o descompunere asemănătoare cu cea din ecuaţia de mai sus, şi anume:

dq,t = (hq-ht)T A( hq-ht)

Precalculând q= hTqA hq , t= hT

tA ht şi t= A ht, avem:

dq,t = q + t -2hTqt

Fie M o permutare care sortează hq în ordinea descrescătoare. Aplicând această permutare şi asupra t, şi notând fq= Mhq şi t= Mt , obţinem


dq,t = q + t -2fTqt

Astfel, sortând histograma interogare, elementele vectorului t sunt accesate în ordinea descrescătoare a importantei lor pentru interogare. t se calculează uşor din histograma ht. În aceste condiţii avem:

M-1

dq,t = q + t -2 fq[m] t [m] m=0

Oprind însumarea la k<M-1, se obţine o bună aproximare a distanţei pătratice între histograme.

Această tehnică conduce la reducerea complexităţii algoritmului de calcul pentru distanţa pătratică între histograme.

S-a constatat că aproximativ 80% din energia histogramei color a unei imagini este conţinută în aproximativ k=10 din cele mai semnificative culori. Când se utilizează numai k culori, cele mai semnificative, complexitatea algoritmului este O(M logM +kN+N). Cele M logM operaţii sunt necesare pentru a sorta histograma color a imaginii interogare , N este mărimea bazei de date, iar M este numărul de culori utilizate.

7.Distanţa pătratică între seturi binare

Distanţa pătratică între două seturi binare sq şi st este dată de:

M-1 M-1

dq,t = (sq[m0] –st[m0]) am0,m1 ( sq[m1]-st[m1]) m0=0 m1=0

Complexitatea metodei este, ca şi în cazul distanţei pătratice între histograme O(m^2*n).

Tehnica de calcul prezentată în vederea reducerii complexităţii distanţei pătratice între histograme, se poate aplica şi la distanţa pătratică între seturi color. Pentru că s q BM (sq este un vector binar ), notând rt=Ast, avem :

dq,t = q + t -2 rt [m] , m unde

sq[m]=1

Utilizând această formulă, se vor lua în considerare numai elementele setului binar al imaginii interogare pentru care sq[m]=1.

Bibliografie


[1] Liana Stanescu: Visual Information – Processing, retrieval and applications, Editura Sitech, Craiova 2008

[2] http://users.ece.utexas.edu/~bevans/courses/ee381k/projects/spring08/saad/LitSurveyReport.pdf

[3] http://www.lifesciencesite.com/lsj/life1002/343_B01072life1002_2475_2487.pdf

[4] Raport tehnic 2008software.ucv.ro/SIBIM/raport_ceex_2008.doc

http://software.ucv.ro/SIBIM/raport_ceex_2008.doc

http://www.lifesciencesite.com/lsj/life1002/343_B01072life1002_2475_2487.pdf

http://users.ece.utexas.edu/~bevans/courses/ee381k/projects/spring08/saad/LitSurveyReport.pdf

http://users.ece.utexas.edu/~bevans/courses/ee381k/projects/spring08/saad/LitSurveyReport.pdf

regasirea informatiei vizuale pe baza caracteristicii culoare

Documents