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:
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.