Laborator IXTransformata KLT. Analiza in Componente Principale

In analiza statistica, masivele de date sunt organizate sub forma unei matrice MxN unde M reprezintă numărul indivizilor iar N numărul caracteristicilor. Pentru o asemenea colecție de date, se pune problema analizei corelației/legăturii care exista intre caracteristicile măsurate prin intermediul matricei de covarianța precum si reprezentarea mai compacta a masivului de date : trecerea dintr-un spațiu RN (spațiul caracteristicilor) intr-un spațiu redus RK definit de o serie de vectori care aproximează cel mai bine datele masivului.I. Corelația liniara intre doua variabile. Matricea de covarianța.

Sa consideram perechile (x,y) de pixeli vecini dintr-o imagine monocromatica. Mulțimea perechilor (x,y) poate fi considerata ca o serie de realizări pentru doua variabile aleatoare X si Y. Reprezentarea grafica in planul 2D ne sugerează faptul ca exista o anumita direcție de aliniere a punctelor (x,y), ceea ce indica existenta unei corelații intre cele doua variabile, corelație determinata de redundanta pixelilor vecini intr-o imagine naturala. O măsura a corelației dintre doua variabile X1 si X2 este matricea de covarianța :

Direcția principala in care punctele variază este data de axa U iar direcția secundara de axa V, ortogonala acesteia. Daca originea sistemului de coordonate (U,V) este plasata in punctul mediu (centrul de greutate) al punctelor (x,y), se obține o reprezentare mai compacta a datelor in sensul ca in noua reprezentare (u,v) datele vor fi complet decorelate.

Pentru un set de date, Analiza in Componente Principale se refera la determinarea sistemului de axe definit de principalele direcții in care datele variază : axele U si V. Daca in plus, variația lui V este redusa in raport cu variatia lui U, setul de date ar putea fi reprezentat doar prin intermediul lui U, ducând astfel la reducerea dimensiunii problemei.a) Rulati prima parte a scriptului labklt.m pentru a observa aspectele explicate anterior.II. Corelația dintre componentele R, G si B ale unei imagini color.

Componentele principale se pot calcula prin intermediul valorilor si vectorilor proprii ai matricei de covarianța. Vectorul propriu corespunzător celei mai mari valori proprii reflecta direcția cu cea mai mare variație, cel corespunzător următoarei valori proprii a doua direcție de variație ca importanta, s. a. m. d. Vectorii proprii sunt ortogonali si de obicei specificați in forma normalizata. Λ – reprezintă matricea diagonala ce are pe diagonala principala valorile proprii iar celelalte elemente sunt nule.

Pentru o imagine color, ne propunem studiul redundantei in sensul corelației liniare care exista intre componentele R, G si B. Decorelarea completa a celor 3 componente se realizează prin intermediul transformatei KLT; in practica însa se prefera o serie de transformate liniare in alte spatii de culoare (ex. YUV, YCbCr) pentru decorelarea parțiala a celor 3 componente spectrale. Care credeți ca este motivul acestei alegeri ?a) Rulați a doua parte a scriptului labklt.m pentru a observa corelarea care exista intre valorile R, G si B din cadrul unei imagini color. b) Refaceți imaginea RGB doar prin considerarea a 2 dintre cei 3 vectori proprii.c) Cuantificați componenta Y1 cu un pas de cuantificare ales (ex. 10) si refaceți imaginea.

III. Recunoașterea fetelor prin metoda EigenFacesRecunoașterea faciala constituie un exemplu practic de folosire a analizei in componente principale, prin reducerea numărului de variabile pentru reprezentarea unei fete. Vom considera ca avem la dispoziție un număr de imagini de aceeași dimensiune pentru un număr de persoane dintr-o baza de date; pentru aceeași persoana putem avea una sau mai multe ipostaze. Vom considera ca in orice imagine fata unei persoanei este centrata.

Astfel, fiecare pixel al unei imagini poate fi considerat o variabila iar o fata se reprezintă astfel ca un vector de P variabile (unde P reprezintă numărul de pixeli). Numărul acestor variabile fiind foarte mare, vom încerca sa reducem complexitatea comparării a doua fete prin aproximarea unei fete printr-un număr mai mic de variabile. O imagine de n pixeli poate fi considerata astfel un punct in spațiul imaginilor (spațiu n-dimensional). Fie vectorul linie px = (i1; i2; i3; … in) unde i1, i2 … reprezintă intensitățile pixelilor. Vectorul se formează prin transformarea imaginii intr-un vector linie; astfel pentru o imagine de 128x128 vom avea dimensiunea 16384 (16K) :

Avand la dispoziție N imagini, fiecare de n pixeli, intregul set de imagini poate fi reprezentat ca o matrice D de dimensiuni N x n, in care fiecare imagine reprezintă o linie:

Primul pas in PCA (Analiza in Componente Principale) este mutarea originii datelor in mijlocul celor n variabile, operație ce este echivalenta cu scăderea valorii medii a variabilelor din fiecare imagine. In cazul nostru, imaginea medie (fata medie) se calculează făcând media pe toate coloanele matricei D. Aceasta fata medie urmează a fi extrasa din fiecare imagine a setului de date D. Matricea diferența obținuta astfel va fi notata cu U. Pe exemplul considerat media celor n coloane este :

Calculul caracteristicilor faciale / componentelor principalePrimul pas in determinarea componentelor principale ale matricei D este calculul matricei de covarianța a matricei U; se poate observa foarte usor ca datorita extragerii valorii medii de pe fiecare coloana a matricei D, matricea de covarianța de dimensiuni nxn se poate exprima astfel : C = UT x U / N.Se calculează apoi valorile proprii si vectorii proprii ai matricei de covarianța. In urma normalizării vectorilor proprii, mulțimea lor φ va forma o baza ortonormata in spațiul Rn:Vom exprima acum toate liniile matricei U (fostele fete din care s-a scăzut fata medie) in baza formata din vectorii proprii. Fiecare vector propriu corespunde unei valori proprii care reprezintă variația datelor matricei U de-a lungul vectorului propriu corespunzător. Prin urmare, in loc sa folosim toți cei n vectori proprii vom folosi doar m (m<<n) reprezentativi care corespund celor mai mari m valori proprii. In mod obișnuit, pentru problema recunoașterii faciale valoarea lui m este destul de mica (intre 20 si 50). Astfel, vom exprima liniile matricei U in baza m-dimensionala formata din cei m vectori aleși:

Fiecare linie va avea m coeficienți care se obțin prin proiecția liniei respective (produsul scalar) pe fiecare dintre vectorii aleși. Astfel, o imagine px = (i1; i2; i3; … in) se exprima in noul spațiu al vectorilor aleși (spațiul componentelor principale) astfel :Am reușit astfel sa reducem reprezentarea imaginii de la un spațiu n-dimensional (n=128x128) la un spațiu m-dimensional (m=20-50). Imaginea px inițiala poate fi de asemenea reconstruita aproximativ din cei m vectori prin aplicarea transformării inverse: Se poate arata ca prin alegerea celor m vectori proprii corespunzatori celor mai mari m valori proprii se minimizează eroarea pătratica de reconstrucție a matricei D (orice alți vectori conduc la o eroare mai mare). Alegerea lui m depinde însa de setul de date D; pentru aceasta se poate căuta un m folosind coeficientul PSNR intre imaginea originala si cea reconstruita sau se poate adopta următoarea metoda. Având in vedere ca suma valorilor proprii este egala cu suma variațiilor pe cele n direcții date de vectorii

proprii corespunzători, se poate calcula procentajul de „variație” păstrat prin alegerea a i vectori principali astfel : Se alege m=i astfel ca procentajul sa fie cel puțin egal cu un prag dat (ex. 95%).Recunoasterea unei feteAvând data o imagine de test py, din ea se va scădea imaginea medie si apoi aceasta va fi exprimata (proiectata) in baza m-dimensionala a vectorilor proprii aleși, rezultând un set de coeficienți w=(w1,w2, …, wm). Imaginea cea mai apropiata fata de imaginea de test va fi determinata prin evaluarea unei distante (ex. euclidiana) intre vectorul w si vectorii w’ din baza de imagini :

Implementarea si testareIn directorul specific acestui laborator veți găsi setul de imagini de invatare (training) precum si doua directoare cu imagini de test (test si strangers).

a) Rulați treptat scriptul learn.m pentru a vedea modul in care sunt implementate ideile anterioare si cum este construita matricea vectorilor de caracteristici w din spatiul m-dimensional. b) Completați apoi scriptul recognise_stud.m pentru a testa validitatea metodei.c) Ce influenta au asupra metodei următorii parametri : numărul de imagini/persoana, numărul de coeficienți m, distanta aleasa ?

IV. Compresia imaginilor prin transformatele KLT si DCT In ultima parte a acestui laborator ne propunem sa vedem modul in care transformata KLT si analiza in componente principale poate fi aplicata la compresia imaginilor, comparând totodată performantele acesteia cu mult mai cunoscuta transformata DCT.

Analiza unei imagini se va face prin impartirea acesteia in blocuri 8x8; fiecare bloc 8x8 se va scrie apoi ca o linie de 64 de pixeli iar apoi toate blocurile vor fi puse intr-o matrice de MxN/64 linii si 64 coloane (procedeu asemănător celui folosit in metoda Eigenfaces).In continuare se va proceda in mod similar ca si in cazul recunoașterii faciale: se va face descompunerea matricei formate in componente principale si vom alege K din cei 64 vectori proprii pentru reconstrucția fiecărui bloc al imaginii. Blocurile astfel reconstruite (linii de 64 valori) trebuiesc repuse la locul lor in cadrul imaginii. Aceasta constituie reprezentarea imaginii folosind doar K coeficienți KLT.Pentru metoda DCT, vom proceda astfel : fiecare bloc 8x8 va fi aproximat prin cei mai reprezentativi K coeficienți DCT considerați in ordinea zigzag (a se vedea functiile zigzag.m si izigzag.m). Blocurile sunt apoi reconstruite prin transformata DCT inversa si repuse in cadrul imaginii.Scriptul kltdct.m contine implementarea ideilor descrise anterior.a) Testați diferite valori pentru K si observați diferențele intre imaginea originala si reconstrucția ei prin intermediul coeficientului PSNR.b) Testați scriptul pentru diferite imagini : lena, baboon, etc. Cum variază numărul de coeficienți K ales pentru PSNR=40dB ? Explicați.c) De ce nu s-a adoptat transformata KLT in standardul de compresie JPEG deși oferă rezultate superioare fata de transformata DCT ?