INF2310 v?r 2014 - UKEOPPGAVER 8

Bildene til oppgavene under finnes under http://www.uio.no/studier/emner/matnat/ifi/INF2310/v14/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.