IN3370 h?st 2024 - UKEOPPGAVER 6

Bildene til oppgavene under finnes under /studier/emner/matnat/ifi/IN3370/h24/undervisningsmateriale/bilder/

Oppgave 1 - 2D DFT og Fourier-basisbildene (sin- og cos-bildene)

Last inn bildet car.png. Benytt kommandoen np.fft.fft2 til ? gj?re en 2D DFT av bildet.

1. Vis og studer Fourier-spekteret og fase-bildet ved ? benytte feks imshow-funksjonen (se s. 45 i forelesningsnotatet). Pr?v gjerne ? vise fram bildets colorbar etter at bildet er fremvist. Hint: np.angle-kommandoen resulterer i tall i intervallet [-pi, pi].
2. Verifiser at koordinat (0,0) i 2D DFT-en (u=0,v=0) er lik summen av alle gr?toneverdiene i originalbildet. Forklar hvorfor det er slik.
3. Bildet du lastet inn er kvadratisk med N=256. Lag NxN sinus-bildet for frekvensen (u,v) = (5,7) (se s. 16 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].
4. Punktvis multipliser originalbildet og sinus-bildet fra punkt c, og summer alle verdiene i den resulterende matrisen. (Dette kalles indreproduktet mellom bildene.)  Verifiser at denne summen er lik imagin?rdelen til 2D DFT-en for samme frekvens som beregnet ved fft2-kommandoen.
5. 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.

Oppgave 2 - Sin- og cos-bildene og ortogonalitet

I denne oppgaven er M=256 og N=512.

1. 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).
2. 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.
3. (Om tid) 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 alle st?r ortogonale p? hverandre (alle indreprodukter er 0).
4. (Om tid) 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.
5. (Om tid) 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.

Oppgave 3 - 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 forelesningene om kompresjon og koding, 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 4 - Fjerning av periodisk st?y

Bildet lena_periodicNoise.png inneholder periodisk st?y. Din oppgave er ? pr?ve ? fjerne denne st?yen.

1. Finn frekvensene som denne st?yen hovedsakelig best?r av. Hint: Let etter topper i Fourier-spekteret blant de h?yere frekvensene.
2. 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. (Kommandoen ifft gj?r en inverstransform.)
3. 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 (jfr. s. 36 i forelesningsnotatene). Studer Fourier-spekteret og pr?v ? fjerne st?yen ved ? sette aktuelle Fourier-koeffisienter til 0.

Oppgave 5 - Haar-transform

Her er en lenke til en programsnutt som viser Haar-transform-basisbilder.  Forklar hvorfor vi kan hente ut basisbildet for koeffisient (i,j) ved ? kj?re en inverstransform p? en null-initialisert matrise hvor (i,j) er satt til en, som programsnutten gj?r.

Oppgave 6 (om tid) - 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. 23/28 i forelesningsnotatet), og sinus-funksjonen er anti-symmetrisk, alts? er sin(-x) = -sin(x).

Oppgave 7 (om tid) - 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 representasjonen (den vanlige pikselvise representasjonen).

Hint: Se s. 24/25 i forelesningsnotatet. Alternativt kan man bruke at n?r input-bildet er reelt (som det for oss alltid er!) s? er 2D DFT-en konjugert symmetrisk.