INF2310 vår 2015 - UKEOPPGAVER 8

Bildene til oppgavene under finnes under http://www.uio.no/studier/emner/matnat/ifi/INF2310/v15/undervisningsmateriale/bilder/

Oppgave 1 - Konvolusjonsteoremet

1. Formuler konvolusjonsteoremet med ord.
2. Hvordan kan vi (rent praktisk) bruke 2D DFT-en til et konvolusjonsfilter til å finne hvilke frekvenser filteret demper og hvilke det bevarer?
3. Hvordan gir konvolusjonsteoremet oss muligheten til å designe konvolusjonsfiltre med bestemte frekvensegenskaper? Hvorfor bør filtrene vi designer i Fourier-domenet være konjugert symmetriske? Hvilke kriterier er det naturlig å ha for intervallet til realdelverdiene og verdien av imaginærdelene dersom vi skal designe enkle konvolusjonsfiltre i Fourier-domenet?
4. Under ser du Fourier-spektrene til konvolusjonsfiltrene [1 2 1]^T og [1 0 -1] etter de er nullutvidet til en størrelse på 200x200 (^T indikerer den transponerte). Fremvisningen er slik at DC, (0,0)-frekvensen, er midt i bildet og lyst indikerer høy verdi mens mørkt indikerer lav verdi. Hvilke konvolusjonsfiltre og Fourier-spektre hører sammen? Begrunn.

    

5. Hvis vi multipliserer de to nullutvidede filtrenes 2D DFT-er element for element, så får vi en 2D DFT som har magnitudebildet som er vist under. Hvilket konvolusjonsfilter er dette Fourier-spekteret til?

   

Oppgave 2 - Design av filtre i Fourier-domenet: Ideelle filtre

1. Lag et lavpassfilter H₁ av størrelse PxQ som er 0 for alle frekvenser (u,v) lengre enn en gitt terskel D₀ fra DC, og 1 ellers. Sett P=Q=512 og D₀=0,2, og visuelt anslå at det resulterende filteret har omtrent 50 ikke-null elementer langs aksene på hver side av DC. Tips: Ta gjerne utgangspunkt i eksempelet på s. 20 i forelesningsnotatet.
2. Beregn 2D IDFT av filteret H₁ og visualiser imaginærdelen av resultatet. Det er fordi filteret er reelt og symmetrisk i Fourier-domenet at denne imaginærdelen er 0. I praksis kan imaginærdelen av resultatet inneholde små ikke-null verdier dersom man bruker upresis flyttallsaritmetikk (som MATLAB gjør), pga. dette bruker vi i praksis kun realdelen til resultatet når vi vet at imaginærdelen skal være 0 (som generelt er når filteret/bildet er konjugert symmetrisk i Fourier-domenet). Tips: Husk at ifft2-kommandoen antar at DC har koordinat (1,1). Hint: Dersom imaginærdelen av resultatet inneholder store ikke-null verdier betyr det at H₁ ikke oppfyller symmetriegenskapen; se s. 20 i forelesningsnotatet for implementasjonstips og forklaring.
3. Visualiser det romlige representasjonen av filteret H₁. Hvilken egenskap ved filteret H₁ (i Fourier-domenet) forårsaker den såkalte "ringingen" i den romlige representasjonen?
4. Lag lavpassfilteret H₂ som er likt som filteret H₁ med unntak av at D₀=0,4. Visualiser den romlige representasjonen av filteret H₂ og forklar hvorfor dette filteret vil både utjevne mindre og gi mindre markant ringing dersom det konvolveres med et gråtonebilde, sammenlignet med å konvolvere den romlige representasjonen av filteret H₁ og bildet.
5. Last inn bildet car.png. Filtrer bildet med filtrene H₁ og H₂, og behandl bilderandproblemet med nullutvidelse. Sammenlign de to filtrerte resultatene i bildedomenet, med hverandre og med originalbildet. Hint: H₁ og H₂ er definert slik at de ikke trengs og nullutvides - det er tilstrekkelig å nullutvide bildet til samme størrelse (512x512) for å unngå wraparound-feil. fft2-kommandoen kan gjøre nullutvidelsen for deg ved at du spesifiserer hvilken størrelse det nullutvidede bildet skal ha; fft2(im, M, N) der M og N er henholdsvis antall rader og kolonner. Bildet blir da utvidet ved å legge til 0-er på slutten av bildet, en detalj du trenger å vite når du etter å ha beregnet 2D IDFT skal forminske bildet ved å fjerne pikslene inn-bildet ble utvidet med.
6. Et høypassfilter i Fourier-domenet kan defineres som 1 minus et lavpassfilter i Fourier-domenet (se s. 27 i forelesningsnotatet). Utfør filtreringene i punkt e med høypassfiltrene som er definert ut fra lavpassfiltrene H₁ og H₂. Sammenlign de to høypassfiltrerte resultatene i bildedomenet og merk at ringingen er mest markant for det høypassfilteret som tilsvarer lavpassfilteret med mest markant ringing.
7. Ved å addere H_HP(u,v) på begge sider av likhetstegnet i likningen H_LP(u,v) = 1-H_HP(u,v), ser vi at summen av et lavpassfilter og det tilhørende høypassfilteret er 1 i alle elementer. Ved å anvende lineæritetsegenskapen til 2D DFT, egenskap 2 i tabell 4.3 i DIP (s. 254), og konvolusjonsteoremet får vi at f(x,y) = g_LP(x,y) + g_HP(x,y) der f er det opprinnelige gråtonebildet, og g_LP og g_HP er det samme bildet konvolvert med henholdsvis et lavpassfilter og det tilhørende høypassfilteret. Hvordan kan denne sammenhengen benyttes til å forklare sammenhengen i punkt f; høypassfilteret med mest markant ringing tilhører lavpassfilteret med mest markant ringing.

Oppgave 3 - Design av filtre i Fourier-domenet: Praktisk eksempel

Last inn bildet tekna133.png. Bildet er hentet fra første utgave av Teknas studentmagasin i 2012 og skannet med oppløsningen som DIP oppgir (på s. 234) som typisk for magasiner; 133 dpi. Støyen på bildet danner et mønster som kalles Moiré-mønster (les mer på s. 233-235 i DIP). Slik støy vil forekomme når man skanner de aller fleste normale utskrifter. Figur 4.64 i DIP, som er vist ved flere anledninger i forelesningene, er forøvrig et annet eksempel på et bilde med Moiré-mønster.

1. Studer Fourier-spekteret til bildet i seg selv og etter nullutvidelse til dobbel størrelse i hver retning. Forårsaker periodisitetsantagelsen eller nullutvidelsen størst bidrag langs u- og v-aksene? Hvorfor?
2. Finn de fire parene av frekvenser som støyen hovedsakelig består av, både for det originale og for det nullutvidede bildet. Hint: Let etter topper i Fourier-spekteret blant de høyere frekvensene. Magnituden til en frekvens i det nullutvidede bildet er lik magnituden til den halve frekvensen i originalbildet.
3. Filterer originalbildet med et notch-stoppfilter med Butterworth-overganger av orden n=2 og med cut-off D₀=0,1 (alternativt vba. tilhørende cut-off-frekvens, D₀N/2 = 11,05). Sammenlign det filtrerte bildet (i bildedomenet) med originalbildet. Er støyen hovedsakelig fjernet? Finner du visuelt synlig wraparound-feil i det filtrerte bildet? Ser du ringing også? Hint: Se likning (4.10-5) på side 295 i DIP.
4. Filterer det nullutvidede bildet med et notch-stoppfilter med Butterworth-overganger av orden n=2 og med cut-off D₀=0,1 (alternativt vba. tilhørende cut-off-frekvens, D₀N/2 = 22,1). Sammenlign Fourier-spektrene til det filtrerte originalbildet fra punkt c og dette filtrerte nullutvidede bildet, og verifiser at de anvendte filtrene er tilsvarende mhp. orden (overgang) og cut-off (størrelse) relativt til sitt Fourier-spekter. Sammenlign de filtrerte bildene (i bildedomenet) som ble laget med og uten nullutvidelsen. Verifiser at wraparound-feil ikke lenger er til stede i det filtrerte bildet som ble laget med nullutvidelsen, men at dette bildet har samme ringing. Forklar hva som er årsaken til den nye visuelt synlige feilen i dette bildet.
5. De filtrerte bildene i de to foregående punktene hadde hver sin feil (utenom ringing, som de begge hadde). Hvordan kan vi (omtrentlig) unngå begge disse individuelle feilene samtidig? Utfør filtreringen og vurder resultatet.