INF2310 vår 2018 - Løsningshint 9

Oppgave 1 - Konvolusjonsteoremet

1. Sirkelkonvolusjon i bildedomenet tilsvarer punktmultiplikasjon i Fourier-domenet, og omvendt.
2. Siden konvolusjonsteoremet sier at effekten av å sirkelkonvolvere et konvolusjonsfilteret og et bilde i bildedomenet er det samme som å punktmultiplisere 2D DFT-en til filteret med 2D DFT-en til bildet i Fourier-domenet, vil verdiene i Fourier-spekteret til filteret direkte reflektere hvilke frekvenser som dempes og hvilke som bevares.
3. Ved å designe filtre i Fourier-domenet kan vi lage vi konvolusjonsfiltre med bestemte frekvensegenskaper.
   Filtrene vi designer i Fourier-domenet bør være konjugert symmetriske fordi dette er ekvivalent med at representasjonen av filtret er reelt i bildedomenet.
   Det er naturlig å la realdelverdiene ligger i intervallet [0,1] og sette imaginærdelverdiene til 0. Førstnevnte gjør at vi ikke forsterker noen frekvenser og sammen gjør de to kriteriene at det designede konvolusjonsfilteret kun påvirker Fourier-spekteret til bildet det anvendes på, og er dermed lettere å kontrollere og tolke ((en mild versjon av) det første kriteriet trengs fordi realdelene må være ikke-negative for å ikke påvirke fasen).
4. Det første spekteret er et vertikalt lavpassfilter, dvs. et filter som demper høyere vertikale frekvenser og bevarer lavere vertikale frekvenser. Dette passer med det første konvolusjonsfilteret ettersom det filteret vil vertikalt smøre ut bildet det konvolveres med. Det andre spekteret er et horisonalt høypassfilter, dvs. et filter som demper lavere horisontale frekvenser og (stort sett) bevarer høyere horisontale frekvenser. Dette passer med det andre konvolusjonsfilteret ettersom det filteret tilnærmer den deriverte i horisontal retning.
   Alternativt kunne man resonnert at summen av det første konvolusjonsfilteret er større enn 0, mens summen av det andre konvolusjonsfilteret er lik 0. Dette gjør at DC av det første filteret må være positivt, mens DC av det andre filteret må være 0, og dermed får man assosieringene mellom konvolusjonsfiltrene og Fourier-spektrene.
5. Fra konvolusjonsteoremet vet vi at punktmultiplikasjonen av 2D DFT-ene tilsvarer å sirkelkonvolvere nullutvidelsen av de to opprinnelige konvolusjonsfiltrene i bildedomenet. Siden konvolusjonsfiltrene, som har størrelse 3x1 og 1x3, har blitt nullutvidet til 200x200 før sirkelkonvolusjon, så er vi garantert at ikke-null koeffisienter av det ene filteret kun overlapper ikke-null koeffisienter av det andre filteret i ett 3x3-område (når vi skal beregne responsen i pikselposisjonene til 200x200-filtrene, dvs. bevare "inn-bildets" størrelse). I dette 3x3-området vil responsen være konvolusjonen av de opprinnelige filtrene i bildedomenet når vi antar nullutvidelse, som er:

   1 0 -1
   2 0 -2
   1 0 -1

   Konvolusjonsfilteret som har det viste Fourier-spekteret er nullutvidelsen av dette 3x3-filteret til en størrelse på 200x200. (Vi gjenkjenner forøvrig 3x3-filteret som den horisontale estimatoren i Sobel-operatoren.)

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

1. P = 512; Q = 512;
   D0 = 0.2;
   H1 = zeros(P,Q);
   for i = 1:P
       for j = 1:Q
           if sqrt( ((i-floor(P/2+1))/(P/2))^2 + ...
                    ((j-floor(Q/2+1))/(Q/2))^2 ) <= D0
               H1(i,j) = 1;
           end
       end
   end
   figure(1); imshow(H1); axis on;

2. figure(2); imshow(fftshift(imag(ifft2(ifftshift(H1)))), []); axis on; colorbar;

3. figure(1); imshow(fftshift(real(ifft2(ifftshift(H1)))), []); axis on;

   Ringingen i den romlige representasjonen er forårsaket av de maksimalt raske overgangene mellom 0 og 1 i Fourier-domenet.

4. D0 = 0.4;
   H2 = zeros(P,Q);
   for i = 1:P
       for j = 1:Q
           if sqrt( ((i-floor(P/2+1))/(P/2))^2 + ...
                    ((j-floor(Q/2+1))/(Q/2))^2 ) <= D0
               H2(i,j) = 1;
           end
       end
   end
   figure(2); imshow(fftshift(real(ifft2(ifftshift(H2)))), []); axis on;

   Filteret H₂ vil utjevne mindre fordi det bruker et mindre naboskap til å utjevne enn det filteret H₁ gjør (og filtrene ellers har lik relativ nedgang fra sitt senterpunkt). Filteret H₂ vil derimot forårsake mindre markant ringing fordi ringene vil forekomme nærmere intensitetskantene og hver ring vil utbre seg kortere enn for H₁.

5. f = double(imread('car.png'));
   [M, N] = size(f);
   F = fftshift( fft2(f, P, Q) );
   gLP1 = real( ifft2( ifftshift( F.*H1 ) ) );
   gLP1 = gLP1(1:M, 1:N);
   gLP2 = real( ifft2( ifftshift( F.*H2 ) ) );
   gLP2 = gLP2(1:M, 1:N);
   figure(1); imshow(f,    []); axis on;
   figure(2); imshow(gLP1, []); axis on;
   figure(3); imshow(gLP2, []); axis on;

6. gHP1 = real( ifft2( ifftshift( F.*(1-H1) ) ) );
   gHP1 = gHP1(1:M, 1:N);
   gHP2 = real( ifft2( ifftshift( F.*(1-H2) ) ) );
   gHP2 = gHP2(1:M, 1:N);
   figure(1); imshow(f,    []); axis on;
   figure(2); imshow(gHP1, []); axis on;
   figure(3); imshow(gHP2, []); axis on;

7. all(abs(gLP1(:) + gHP1(:) - f(:)) < 10^-10)
   all(abs(gLP2(:) + gHP2(:) - f(:)) < 10^-10)

   Ringingen i bildedomenet er bølgelignende intensitetsvariasjoner som visuelt ser ut til å utgå fra kantene i det filtrerte bildet. Disse variasjonene vil alternere mellom å påvirke intensitetene negativt og positivt i forhold til det opprinnelige bildet. Dersom et filtrert bilde har markant ringing og summen av det bildet og et annet bilde skal bli lik det opprinnelige (altså ufiltrerte) bildet, må det andre bildet ha tilsvarende markant ringing som "demmer opp mot" det filtrerte bildets intensitetsavvik. Derfor må et lavpassfilter og det tilhørende høypassfilteret forårsake tilsvarende grad av ringing, men med omvendt påvirkningsretning av intensitetene (positivt og negativt eller negativt og positivt) - ettersom summen av de filtrerte bildene skal være lik det opprinnelige bildet. (En detalj er at det lavpassfiltrerte resultatet ringer rundt den opprinnelige intensitetsverdien, mens det høypassfiltrerte resultatet ringer rundt 0.)

Oppgave 4 - Aliasing

f = double(imread('forresampling.png'));
[M N] = size(f);
for d = 1:4
    figure(d); imshow(f(1:d:end,1:d:end), [0 255]); axis on;
end
for d = 1:4
    lnFdS = log( abs(fftshift(fft2(f(1:d:end,1:d:end)))) + 1 );
    figure(d); imshow(lnFdS, [0 max(lnFdS(:))]); axis on;
end

Oppgave 5 - Vindusfunksjoner og Fourier-spektre

f = double(imread('lena.png'));
[M,N] = size(f);
alpha = 0.5;
w = (tukeywin(N,alpha)*tukeywin(M,alpha)')';
figure(1); imshow(w); axis on;
lnFS = log( abs(fftshift(fft2(f))) + 1);
figure(2); imshow(lnFS, [0 max(lnFS(:))]); axis on;
lnFwS = log( abs(fftshift(fft2(f.*w))) + 1);
figure(3); imshow(lnFwS, [0 max(lnFwS(:))]); axis on;

To forklaringer på hva vindusfunksjoner gjør (to sider av samme sak):

• Reduserer bidraget i Fourier-spekteret som er forårsaket av diskontinuiteten langs bilderanden.
• Glatter Fourier-spekteret.