INF2310 vår 2015 - Løsningshint 7

Oppgave 1 - 2D DFT-beregning

1. Bildet inneholder to hele perioder vertikalt, dermed er vertikal frekvens, u, 2. Bildet inneholder tre hele perioder horisontalt, dermed er horisontal frekvens, v, 3. Cosinus-bildet har dermed frekvens (2,3).
2. Følger hintet ved f.eks. å forskyve hver rad én piksel til høyre, flytte det siste elementene først (både sinus og cosinus er periodiske) og negere. Får da sinus-bildet med frekvens (2,3) og størrelse 8x12:

   0	-1	0	1	0	-1	0	1	0	-1	0	1
   -1	0	1	0	-1	0	1	0	-1	0	1	0
   0	1	0	-1	0	1	0	-1	0	1	0	-1
   1	0	-1	0	1	0	-1	0	1	0	-1	0
   0	-1	0	1	0	-1	0	1	0	-1	0	1
   -1	0	1	0	-1	0	1	0	-1	0	1	0
   0	1	0	-1	0	1	0	-1	0	1	0	-1
   1	0	-1	0	1	0	-1	0	1	0	-1	0

3. Summen av punktproduktet av bildet og cosinus-bildet er 13. Summen av punktproduktet av bildet og sinus-bildet er 1. 2D DFT-koeffisienten til frekvens (2,3) er dermed 13+i.
4. Vi vet at DC-komponenten er summen av gråtoneverdiene i bildet (se s. 25 i forelesningsnotatet). For bildet i c er summen 160, så 2D DFT-koeffisienten til frekvens (0,0) er 160.

Oppgave 2 - Sinus- og cosinus-bildene

f = double(imread('car.png'));
F = fft2(f);
N = size(f,2);
i = (0:N-1)';

1. figure(1); imshow(log( abs(fftshift(F)) + 1 ), [0 max(log( abs(F(:)) + 1 ))]); axis on;
   % colormap('default'); colorbar;
   figure(2); imshow(angle(F), [-pi pi]); axis on;

2. F(1,1)
   sum(f(:))

3. u = 5;
   v = 7;
   sine = sin(-2*pi*(u.*repmat(i,1,N) + v.*repmat(i',N,1)) / N);
   figure(3); imshow(sine, [-1 1]); axis on;

4. sum(f(:) .* sine(:))
   imag(F(u+1,v+1))

5. cosine = cos(2*pi*(u.*repmat(i,1,N) + v.*repmat(i',N,1)) / N);
   sum(f(:) .* cosine(:))
   real(F(u+1,v+1))

Oppgave 3 - Sinus- og cosinus-bildene og ortogonalitet

M = 256;
N = 512;
x = (0:M-1)';
y = (0:N-1);

1. u = 10;
   v = 10;
   sine = sin(-2*pi*(u.*repmat(x,1,N)/M + v.*repmat(y,M,1)/N));
   figure(1); imshow(sine, [-1 1]); axis on;

2. cosine = cos(2*pi*(u.*repmat(x,1,N)/M + v.*repmat(y,M,1)/N));
   sum(sine(:) .* cosine(:))

3. u = 86;
   v = 45;
   sine2   = sin(-2*pi*(u.*repmat(x,1,N)/M + v.*repmat(y,M,1)/N));
   cosine2 = cos( 2*pi*(u.*repmat(x,1,N)/M + v.*repmat(y,M,1)/N));
   sum(sine2(:)  .* cosine2(:))
   sum(sine(:)   .* sine2(:))
   sum(sine(:)   .* cosine2(:))
   sum(cosine(:) .* sine2(:))
   sum(cosine(:) .* cosine2(:))

4. u = 246;
   v = 502;
   sine2   = sin(-2*pi*(u.*repmat(x,1,N)/M + v.*repmat(y,M,1)/N));
   cosine2 = cos( 2*pi*(u.*repmat(x,1,N)/M + v.*repmat(y,M,1)/N));
   figure(2); imshow(-sine2,  [-1 1]); axis on;
   figure(3); imshow(cosine,  [-1 1]); axis on;
   figure(4); imshow(cosine2, [-1 1]); axis on;
   all(abs(sine(:)   + sine2(:))   < 10^-10)
   all(abs(cosine(:) - cosine2(:)) < 10^-10)

5. sum(sine(:)   .* sine(:))
   sum(cosine(:) .* cosine(:))

Oppgave 4 - Kompresjon ved redusert basis

Forslag til løsning ved bruk av car.png:

f = double(imread('car.png'));
F = fft2(f);
t = 1;
while t < 10000000
    F2 = F;
    F2(abs(F) < t) = 0;
    f2 = ifft2(F2);
    subplot(1,2,1); imshow(f2, [0 255]);       title(['Rekonstruksjon, t = ' num2str(t)]);
    subplot(1,2,2); imshow(fftshift(F2 ~= 0)); title([num2str(sum(F2(:) ~= 0)) ' ikke-null koeffisienter']);
    pause;
    t = 10 * t;
end

Oppgave 5 - Fjerning av periodisk støy

f = double(imread('lena_periodicNoise.png'));
F = fft2(f);

1. figure(1); imshow(log( abs(fftshift(F)) + 1 ), [0 max(log( abs(F(:)) + 1 ))]); axis on;

   Ved visuell inspeksjon peker parene (89, 29) og (169, 229), og (189, 69) og (69, 189) seg ut (skrevet med én-indeksering og etter skifting slik at senterpikselet er DC).

2. F_centered = fftshift(F);
   F_centered( 88: 90,  28: 30) = 0;
   F_centered(168:170, 228:230) = 0;
   F_centered(188:190,  68: 70) = 0;
   F_centered( 68: 70, 188:190) = 0;
   figure(2); imshow(log( abs(F_centered) + 1 ), [0 max(log( abs(F_centered(:)) + 1 ))]); axis on;
   f2 = ifft2(ifftshift(F_centered));
   figure(3); imshow(f2, [0 255]);

3. f = double(imread('lena_periodicNoise2.png'));
   F = fft2(f);
   figure(1); imshow(log( abs(fftshift(F)) + 1 ), [0 max(log( abs(F(:)) + 1 ))]); axis on;
   % Paret (89, 29) og (169, 229) peker seg ut.
   % Et drastisk forslag til løsning:
   F_centered = fftshift(F);
   F_centered(  1:end,  28: 30) = 0;
   F_centered( 88: 90,   1:end) = 0;
   F_centered( 84: 94,  24: 34) = 0;
   F_centered(  1:end, 228:230) = 0;
   F_centered(168:170,   1:end) = 0;
   F_centered(164:174, 224:234) = 0;
   figure(2); imshow(log( abs(F_centered) + 1 ), [0 max(log( abs(F_centered(:)) + 1 ))]); axis on;
   f2 = ifft2(ifftshift(F_centered));
   figure(3); imshow(f2, [0 255]);

Oppgave 6 - 2D DFT av symmetriske bilder

Imaginærdelene vil alltid bli 0. Slike 2D DFT-er er derfor reelle og symmetriske.

Oppgave 7 - Antall uavhengige/"unike" koeffisienter

Galt. Pga. symmetrien i cosinus-bildene og anti-symmetrien i sinus-bildene vil kun halvparten av realdelene være uavhengige og halvparten av imaginærdelene være uavhengige. For å representere hele 2D DFT-en trenger man derfor bare å lagre én av hver halvdel, som tilsammens utgjør akkurat like mange tall som den romlige representasjonen.