INF2310 v?r 2014 - 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.

Publisert 20. jan. 2014 08:47 - Sist endret 7. mars 2014 17:52