IN2070 - V?r 2022

IN2070 v?r 2022 - UKEOPPGAVER 10

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 4. apr. 2022 21:45 - Sist endret 4. apr. 2022 21:45
    Del p? e-post