Av: Malin Andersen, 770628-7526

Datum: 2000-09-11

Inlämningsuppgift 1b: PCA and Image Compression

Inledning

Bilddata kan komprimeras genom att dimensionen på data reduceras.

I denna inlämningsuppgift har principal komponent analys använts för att reducera dimensionen på bilddata. Resultatet har analyserats genom att datat visualiserats m.h.a matlab-komandot imagesc före och efter dimensionsreduceringen.

Utförande

En funtion pca.m i matlab implementerades för att utföra dimmensionsreduceringen, den fungerar enligt följande:

Matlab funktionen extract.m användes för att dela upp ursprungsbilden i delbilder av storlek 8 x 8 pixels, som sparades i en matris A.

För att utföra principal komponent analys av data x måste väntevärdet E(x) vara noll.

Medelvärdet av varje delbild, varje kolonn i matrisen A, beräknades därför.

Väntevärdet av varje delbild sattes sedan till noll genom att för varje delbild subtrahera medelvärdet., datat med väntevärdet noll lagras i en ny matris, B.

Då väntevärdet för en variabel x är noll representerar lösningen till egenvärdesproblemet RU=ΛU en ON-bas för datat i x.

R=kovariansmatrisen för x

U=en matris där kolonnerna är egenvektorerna till R

Λ=en diagonalmatris med egenvärdena till R i diagonalen

Den bästa principal komponent uppdelningen fås om de egenvektorer till x som korresponderar mot de största egenvärdena väljs till basvektorer.

För att utföra denna uppdelning användes matlab komandot cov för att beräkna kovariansmatrisen för matrisen B.

Matlabkommandot eig användes sedan för att beräkna egenvärdena och egenvektorerna för kovariansmatrisen.

Egenvärdena plottades i matlab för att visuallisera vilka egenvektorer som korresponderar mot stora egenvärden, och därför bör tas med som basvektorer.

De egenvektorer som motsvarar de N största egenvärdena valdes att utgöra basvektorer, de plottades också i matlab.

De utvalda egenvektorerna användes för att skapa en komprimmerad bild,

_m

X_kompr=∑a_ju_j där uj är egenvektorert till kovariansmatrisen, a=u_j^Tx=x^Tu_j,

^j=1

m< dimmension på ursprungsbilden

X_kompr beräknades i matlab, den komprimmerade bilden erhölls genom att addera medelvärdet för varje delbild. Matlabfunktionen reconstruct.m användes för att transformera on bilden till en 256x256 matris.

Slutresultatet visualiserades med kommandot imagesc i matlab, och jämfördes men ursprungsbilden som visualliserades på samma sätt.

Funktionen pca.m användes för att utföra och visuallisera dimmensionsreducering av alla bilderna i filen lab1bimages.mat.

Diskussion

Efter dimensionsreduceringen ser bilderna inte ut exakt som ursprungsbilderna. Bilderna får sämre upplösning, detaljer suddas ut.

Den komprimerade bilden har erhållits genom att varje delbild har projicerats på egenvektorerna till covariansmatrisen för bilden. Genom att ignorera de egenvektorer som har små egenvärden, dvs där variansen i egenvektorernas riktning för bilden är låg, har bildens dimmension minskat. I de komprimerade bilderna representeras delbilderna av linjärkombinationer av de N sista egenvektorerna, där N=10, dvs 55 egenvektorer ignoreras. Eftersom variansen inte är noll i de ignorerade egenvektorernas riktning kommer en del införmation från originalbilden ej att komma med i den komprimerage bilden, vilket gör att den blir suddigare och detaljfattigare.

De mest framträdande dragen från ursprungsbilden kommer att synas i den komprimerade bilden eftersom dessa korresponderar mot egenvektorer med stora egenvärden.

Komprimering av bilder genom dimmensionsreducering fungerar olika bra på olika bilder. Bilder med många små detaljer förlorar mer information vid dimmernsionsreduseringen än bilder med stora jämna ytor. Exempelvis är skillnaden mellan den komprimerade bilden av lena och originalbilden mindre än skillnaden mellan den komprimerade bilden av ladan och originalbilden på ladan, om samma antal basvektorer väljs för båda bilderna.

Allra minst är skillnaden mellan den kompimerade och den okomprimerade bilden av skogen.

Summan av felet i kvadrat för varje delbild i den komprimerade bilden som uppkom genom dimmensionsreduceringen kan skrivas som

_d

E_M=1/2*∑ λj

^j=N+1

Där d är antal egenvärden till kovariansmatrisen till datat, N är det antal egenvektorer som tas med som basvektorer i principal komponent analysen, λj för j>N är de N minsta egenvärdena till kovarians matrisen.

Felet beror alltså på de egenvärden som korresponderar mot egenvektorer som ej tas med i principal komponent analysen. Bilder med stora värden på dessa egenvärden får stora fel vid dimmensionsreducering med principal komponent analys.

Plotterna av egenvektorerna för barn, lena samt forest visar att bilden forest, som blir komprimerad med relativt små fel, har få höga egenvärden, medan barn har ganska många icke försumbara egenvärden. Om samma antal egenvektorer tas med vid komprimeringen av de olika bilderna blir därför felet mycket varierande från bild till bild.

egenvärden barn egenvärden lena

egenvärden forest

Graden av datakomprimering kan estimerasgenom att beräkna det antal bitar som krävs för att representera originalbilden, samt antal bitar som krävs för att lagra den komprimerade bilden.

Originalbilden bestod av en 256x256 matris. Antag att bilden representerades genom att varje matriselement tilldelats 8 bitar. Totalt använder bilden då 524288 bitar.

Vid dimensionsreduceringen delades bilden in i 1024 delbilder av storlek 8x8. Genom principalkomponent analys representeras varje delbild av tex bilden barn av 10 basvektorer. Varje basvektor tilldelas max 8 bitar. En delbild består av 64 matriselement. Antal bitar per matriselement i den komprimerade bilden är alltså max 10x8/64=1.25 bitar per matriselement.

Originalbilden representerades av 8 bitar per matriselement.

Detta innebär att hela bilden tar upp 1,25 *256*256=81920 bitar i komprimerad form, och 8*256*256i originalform, dvs bilden har komprimerats med en faktor 6,4.