IN2070 - Vår 2021

IN2070 vår 2021 - UKEOPPGAVER 9

Disse oppgavene omhandler anvendelser av 2D diskret Fourier-transform (2D DFT).

Bildene til oppgavene under finnes under http://www.uio.no/studier/emner/matnat/ifi/INF2310/v20/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 nullfrekvensen, (u=0,v=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 H1 av størrelse PxQ som er 0 for alle frekvenser (u,v) lengre enn en gitt terskel D0 fra nullfrekvensen, og 1 ellers. Sett P=Q=512 og D0=0,2, og visuelt anslå at det resulterende filteret har omtrent 50 ikke-null elementer langs aksene på hver side av nullfrekvensen. Tips: Ta gjerne utgangspunkt i eksempelet på s. 17 i forelesningsnotatet.
  2. Beregn 2D IDFT av filteret H1 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 nullfrekvensen har koordinat (1,1). Hint: Dersom imaginærdelen av resultatet inneholder store ikke-null verdier betyr det at H1 ikke oppfyller symmetriegenskapen; se s. 17 i forelesningsnotatet for implementasjonstips og forklaring.
  3. Visualiser den romlige representasjonen av filteret H1. Hvilken egenskap ved filteret H1 (i Fourier-domenet) forårsaker den såkalte "ringingen" i den romlige representasjonen?
  4. Lag lavpassfilteret H2 som er likt som filteret H1 med unntak av at D0=0,4. Visualiser den romlige representasjonen av filteret H2 og forklar hvorfor dette filteret vil utjevne mindre, sammenlignet med å konvolvere den romlige representasjonen av filteret H1 og bildet.
  5. Last inn bildet car.png. Filtrer bildet med filtrene H1 og H2, og behandl bilderandproblemet med nullutvidelse. Sammenlign de to filtrerte resultatene i bildedomenet, med hverandre og med originalbildet. Hint: H1 og H2 er definert slik at de ikke trenger å 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. 24 i forelesningsnotatet). Utfør filtreringene i punkt e med høypassfiltrene som er definert ut fra lavpassfiltrene H1 og H2. 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 HHP(u,v) på begge sider av likhetstegnet i likningen HLP(u,v) = 1-HHP(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. 258), og konvolusjonsteoremet får vi at f(x,y) = gLP(x,y) + gHP(x,y) der f er det opprinnelige gråtonebildet, og gLP og gHP 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 - Analyse av konvolusjonsfiltre

Velg endel kjente konvolusjonsfiltre, nullutvid dem til en passende størrelse for et bilde og visualiser Fourier-spektrene til de nullutvidede filtrene. Forklar overordnet hvorfor hvert Fourier-spekter ser ut som det gjør og bruk det til å beskrive det tilhørende konvolusjonsfilterets effekt (når det brukes til konvolusjon). Bruk gjerne konvolusjonsfiltrene og Fourier-spektrene på s. 28-29 i forelesningsnotatet. Nullutvid noen konvolusjonsfiltre til flere størrelser og merk at den overordnede strukturen forblir identisk.

Oppgave 4 - Aliasing

Last inn bildet forresampling.png og studer dets Fourier-spekter. Dann en mengde med nedsamplede bilder hvor du velger ut hvert d-te piksel for d=1,2,3,4. Studer bildene visuelt og legg merke til den tydelige aliasingen i bildene når d er større enn 2. Studer bildenes Fourier-spektre og legg merke til de stadig tydeligere "falske" frekvensene når stadig flere markante frekvenser i originalbildet ikke lenger kan representeres med den gitte samplingsfrekvensen. Du kan finne det nyttig å repetere samplingsteoremet og aliasing fra andre forelesning; Sampling og kvantisering. Tips: I MATLAB kan du enkelt hente ut hvert d-te piksel i matrisen f ved å bruke fd = f(1:d:end,1:d:end).

Oppgave 5 - Vindusfunksjoner og Fourier-spektre

Last inn bildet lena.png. Generer et 2D Tukey-vindu med samme størrelse som bildet og med alpha lik 0.5 (se s. 37 (slide 110 i PDF-filen) i forelesningsnotatet eller bruk tukeywin-kommandoen, jfr. s. 34). Inspiser vindusfunksjonen visuelt. Studer Fourier-spekteret til bildet både med og uten bruk av vindusfunksjonen (en vindusfunksjon brukes i bildedomenet ved å punktmultiplisere den med bildet). Verifiser at bidragene langs aksene er redusert og forklar hvorfor.

Oppgave 6 (ekstraoppgave) - Konvolusjonsteoremet -- øke forståelsen litt ved hjelp av Matlab/Python

For å gjøre ting litt lettere, ser vi på det endimensjonale tilfellet. Lag to N=512 lange sekvenser med henholdsvis (heltallige) frekvenser u1 og u2. ( N = 512; i = 0:N-1; x1 = sin( -2*pi*u1.*i/N ); x2 = sin( -2*pi*u2.*i/N ); )

  1. Anta først at u1=u2. Hva blir resultatet om vi sirkel-konvolverer de to sekvensene? Verifiser visuelt at frekvensen på det resulterende signalet er lik u1 (og u2). Benytt funksjonen cconv (sirkelkonvolusjon). Feks: x = cconv(x1,x2,N);
  2. La så u1 være ulik u2. Hva blir resultatet av konvolusjonen da?
  3. La oss så si at sekvensene våre, x1 og x2, består av et sett med frekvenser. Linearitetsegenskapen til konvolusjonsfiltre sier at man enten kan ta våre originale sekvenser og konvolvere de sammen, eller man kan dekomponere sekvensene, konvolvere alle kombinasjoner, for så å legge sammen resultatet. Forklar med ord hva dette innebærer ved dekomponering ved hjelp av DFT.
  4. La oss si at sekvensen x er resultatet etter konvolusjonen av x1 med x2, og X = fft(x). Basert på hva vi kom frem til i a) og b), hvilke "konvolusjons-frekvenskombinasjoner" bidrar til koeffisienten i (for eksempel) X(5)?
  5. Hvordan kan disse resultatene bidra til å forklare at en konvolusjon i det romlige domenet kun er enkle multiplikasjoner i frekvensdomenet?

Oppgave 7 - (ekstraoppgave) 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. 238-240 i DIP). Slik støy vil forekomme når man skanner de aller fleste normale utskrifter. Figur 4.21 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 D0=0,1 (alternativt vba. tilhørende cut-off-frekvens, D0N/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å?
  4. Filterer det nullutvidede bildet med et notch-stoppfilter med Butterworth-overganger av orden n=2 og med cut-off D0=0,1 (alternativt vba. tilhørende cut-off-frekvens, D0N/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.
 
    Publisert 13. jan. 2021 07:55 - Sist endret 17. mars 2021 16:01
    Del på e-post