Bildene til oppgavene under finnes under http://www.uio.no/studier/emner/matnat/ifi/INF2310/v14/undervisningsmateriale/bilder/
Oppgave 1 - 2D DFT-beregning
I denne oppgaven skal du ikke benytte noen hjelpemidler.
- Hvilken frekvens har f?lgende 8x12-cosinus-bilde? Begrunn svaret ditt.
1 0 -1 0 1 0 -1 0 1 0 -1 0 0 -1 0 1 0 -1 0 1 0 -1 0 1 -1 0 1 0 -1 0 1 0 -1 0 1 0 0 1 0 -1 0 1 0 -1 0 1 0 -1 1 0 -1 0 1 0 -1 0 1 0 -1 0 0 -1 0 1 0 -1 0 1 0 -1 0 1 -1 0 1 0 -1 0 1 0 -1 0 1 0 0 1 0 -1 0 1 0 -1 0 1 0 -1 - Hvordan blir sinus-bildet med samme frekvens og st?rrelse?
Hint: Hver rad i et cosinus-bilde er en samplet cosinus i 1D (gjelder ogs? hver kolonne) (dette gjelder ogs? uten sampling, se s. 7 i forelesningsnotatet). En sinus er det samme som en cosinus forskj?vet pi/2 til h?yre (se s. 5 i forelesningsnotatet). Siden vi sampler fire ganger per periode i begge retninger s? tilsvarer denne forskyvningen n?yaktig én piksel. I tillegg er sinus-bildet negert i forhold til cosinus-bildet og denne forflytningen (se s. 14 i forelesningsnotatet). - Bruk cosinus-bildet og sinus-bildet til ? beregne 2D DFT-koeffisienten for den aktuelle frekvensen av bildet:
Hint: Realdelen og imagin?rdelen av koeffisienten er summen av punktproduktet av bildet og hhv. cosinus-bildet og sinus-bildet (se s. 14 i forelesningsnotatet).3 3 1 2 1 1 2 3 3 3 1 1 3 3 3 3 0 1 3 1 3 0 3 2 0 0 3 2 0 3 1 2 2 3 2 0 3 3 3 1 3 3 2 0 0 1 2 0 2 3 2 2 2 0 2 3 0 0 3 2 0 1 0 0 1 1 0 1 1 1 1 3 1 3 3 2 3 1 0 2 3 2 3 3 2 0 3 0 0 2 1 2 1 1 3 0 - Beregn DC-komponenten, dvs. 2D DFT-koeffisienten for frekvens (0,0), av bildet i punkt c.
Oppgave 2 - Sinus- og cosinus-bildene
Last inn bildet car.png. Benytt kommandoen fft2 til ? gj?re en 2D DFT av bildet.
- Vis og studer Fourier-spekteret og fase-bildet ved ? benytte imshow-kommandoen (se s. 46 i forelesningsnotatet). Pr?v gjerne og kj?r kommandoene colormap('default') og colorbar etter et bilde er vist. Hint: angle-kommandoen benytter atan2-kommandoen for ? beregne fasen, noe som resulterer i tall i intervallet [-pi, pi].
- Verifiser at koordinat (1,1) i 2D DFT-en er lik summen av alle gr?toneverdiene i originalbildet (se s. 25 i forelesningsnotatet og husk at MATLAB bruker én-indeksering).
- Bildet du lastet inn er kvadratisk med N=256. Lag NxN sinus-bildet for frekvensen (u,v) = (5,7) (se s. 8 og 14 i forelesningsnotatet). Vis bildet og verifiser at du ser 5 og 7 hele perioder av sinus-funksjonen i henholdsvis vertikal og horisontal retning. Hint: En uskalert sinus-funksjon (dvs. en med amplitude lik 1) resulterer i tall i intervallet [-1, 1].
- Punktvis multipliser originalbildet og sinus-bildet fra punkt c, og summer alle verdiene i den resulterende matrisen. Verifiser at denne summen er lik imagin?rdelen til 2D DFT-en for samme frekvens som beregnet ved fft2-kommandoen (se s. 14 i forelesningsnotatet).
- Lag cosinus-bildet av samme st?rrelse og frekvens som i punkt c og d (samplet 2D cosinus er definert akkurat som samplet 2D sinus med unntak av at sinus-funksjonen er erstattet med cosinus-funksjonen). Verifiser at summen av verdiene i det punktvise produktet mellom originalbildet og cosinus-bildet er lik realdelen til 2D DFT-en for samme frekvens som beregnet ved fft2-kommandoen (se s. 14 i forelesningsnotatet).
Oppgave 3 - Sinus- og cosinus-bildene og ortogonalitet
I denne oppgaven er M=256 og N=512.
- Lag og vis MxN sinus-bildet for frekvensen (u,v) = (10,10). Merk hvordan retning p? "b?lgene" er p?virket av den ikke-kvadratiske samplingen, mens antall hele perioder i hver retning forblir det samme (det er jo disse antallene vi spesifiserer med frekvensen).
- Lag MxN cosinus-bildet for samme frekvens som i punkt a. Summer resultatet av den punktvise multiplikasjonen av sinus-bildet i punkt a og dette cosinus-bildet. At denne summen av produkter er 0 betyr at disse bildene er ortogonale.
- Lag MxN sinus-bildet og MxN cosine-bildet for en vilk?rlig frekvens (u',v') (der u' og v' er heltall i intervallene 0 <= u' <= M-1 og 0 <= v' <= N-1) annen enn (u,v) = (10,10) og (u,v) = (246,502). Beregn summen av det punktvise produktet mellom det valgte sinus-bildet og det valgte cosine-bildet. Beregn ogs? denne summen av produkter for alle fire kombinasjoner av ett av disse to bildene og enten bildet i punkt a eller bildet i punkt b. Legg merke til at de er alle ortogonale.
- Lag MxN sinus-bildet og MxN cosine-bildet for frekvens (u,v) = (246,502). Vis bildene og sammenlign med bildene fra punkt a og b. Vis ogs? at hvert element av sinus-bildet er den negerte av det samme elementet i bildet i punkt a, og hvert element av cosinus-bildet er likt som i bildet i punkt b. Pga. upresis flyttallsaritmetikk b?r det ikke testes for absolutt negering eller likhet, men om absoluttverdien av elementsummen eller elementdifferansen er mindre enn en liten verdi, f.eks. 10^-10.
- Beregn til slutt summen av det punktvise produktet mellom bildet i punkt a med seg selv og bildet i punkt b med seg selv. Legg merke til at ogs? MN/2 = 65536.
Totalt har vi n? vist egenskap 10 og 11 i tabell 4.3 i DIP (s. 255); dersom bildet v?rt er en samplet 2D sinus eller 2D cosinus med heltallig frekvens (u,v) og amplitude 1, s? vil 2D DFT-en v?re 0 i alle andre punkter enn (u,v) og (-u,-v), der vil den ha magnitude MN/2. Dette er eksemplifisert p? s. 28-30 og 33-34 i forelesningsnotatet. (I spesialtilfellet der frekvensen er (0,0) s? vil bildet av 2D sinusen v?re 0-matrisen og bildet av 2D cosinusen v?re 1-matrisen, noe som gj?r at 2D DFT-en vil v?re hhv. 0-matrisen og matrisen med 0 i alle andre punkter enn (0,0), der vil den ha magnitude MN.)
Oppgave 4 - Kompresjon ved redusert basis
Last inn et bilde og gj?r en 2D DFT. Sett alle koeffisientene i Fourier-spekteret under en gitt terskel til null. Inverter 2D DFT-en og inspiser det resulterende gr?tonebildet visuelt. Vis ogs? et bilde av hvilke koeffisienter som blir bevart og skriv ut hvor mange dette er. Varierer terskelen og finn (omtrentlig) det minste antallet Fourier-koeffisienter man trenger for at det resulterende gr?tonebildet fortsatt skal se visuelt akseptabelt ut.
Bemerkning: Tilsvarende egenskap for den sterkt relaterte 2D diskret cosinus-transform (2D DCT) er grunnpilaren i JPEG-standarden. Dette kommer vi tilbake til i forelesning 11 (Kompresjon og koding II), men dersom du ?nsker ? foregripe begivenheten kan du f.eks. ta en titt p? Wikipedia fra http://en.wikipedia.org/wiki/JPEG#Block_splitting og utover.
Oppgave 5 - Fjerning av periodisk st?y
Bildet lena_periodicNoise.png inneholder periodisk st?y. Din oppgave er ? pr?ve ? fjerne denne st?yen.
- Finn frekvensene som denne st?yen hovedsakelig best?r av. Hint: Let etter topper i Fourier-spekteret blant de h?yere frekvensene.
- Sett koeffisientene til Fourier-spekteret til 0 i et omr?de rundt hver av frekvensene du fant i punkt a. Alts?, beregn 2D DFT, sett de ?nskede koeffisientene til 0, og inverter 2D DFT-en.
- lena_periodicNoise2.png inneholder ogs? periodisk st?y, men dette bildet inkluderer ikke et helt antall svingninger av st?yen. Dette resulterer i utsm?ring av Fourier-spekteret (sammenlign med s. 30-32 i forelesningsnotatet). Studer Fourier-spekteret og pr?v og fjern st?yen ved ? sette aktuelle Fourier-koeffisienter til 0.
Oppgave 6 - 2D DFT av symmetriske bilder
Anta at vi har et NxN symmetrisk gr?tonebilde f, alts? at f(x,y) = f(N-x,N-y). Hvis vi antar at bildet gjentar seg selv, vil dette si at f(x,y) = f(-x,-y).
Hva vil imagin?rdelene til 2D DFT-en av slike bilder v?re? Hva kan vi ut fra dette generelt si om slike 2D DFT-er? Hint: En imagin?rdel er summen av punktmultiplumet av originalbildet og et sinus-bilde (se s. 14 i forelesningsnotatet), og sinus-funksjonen anti-symmetrisk, alts? er sin(-x) = -sin(x).
Oppgave 7 - Antall uavhengige/"unike" koeffisienter
Diskuter f?lgende p?stand: Siden 2D DFT-en av et NxN bilde inneholder NxN reelle og NxN imagin?re tall, trenger vi ? lagre dobbelt s? mange tall for ? representere hele 2D DFT-en i forhold til hele den romlig representasjon.
Hint: Se s. 15 i forelesningsnotatet. Svaret er mer fremtredende dersom man studerer den komplette mengden av cosinus- og sinus-bilder for noe h?yere M og N enn i dette eksempelet. Alternativt, men kanskje mindre l?rerikt, kan man bruke at n?r f er reell s? er 2D DFT-en konjugert symmetrisk.