Speed up a image alignment function using FFT

[CNX]

Homework Statement

I need to speed up a image alignment function using FFT

Homework Equations

FFT, correlation coefficient (for deciding best alignment)

The Attempt at a Solution

This function works but a fail to see how it is any better that a naive evaluation of the correlation coefficient.

function [a, b] = Align(f, g)

    [h, w] = size(f);
    
    a = 0;
    b = 0;
    cmax = 0;
    
    G = fft2(g);
    G = conj(G);
    
    for j=1:h-1
        for k=1:w-1
            fs = circshift(f, [j,k]);
            F = fft2(fs);

            c = sum(F(:).*G(:));
            
            if c > cmax
                cmax = c;
                a = j;
                b = k;
            end
        end
    end
    
    return

 

[Nick Bruno]

i thought fft was fast Fourier transform

 

[Mene]

There are a few ways in which using FFT can speed up the image alignment function. One advantage is that FFT reduces the computational complexity of the correlation calculation from O(n^2) to O(nlogn), making it faster for larger images. Additionally, using FFT allows for the use of parallel processing techniques which can further improve the speed of the function.

To further optimize the function, instead of using a nested loop to compute the correlation at each possible shift, we can use the Fourier shift theorem to directly calculate the correlation at all shifts in one step. This eliminates the need for the loop and significantly speeds up the function.

Furthermore, we can use techniques such as zero-padding and windowing to improve the accuracy of the alignment and reduce the effects of noise in the images.

Overall, by utilizing FFT and implementing optimized techniques, we can significantly speed up the image alignment function while maintaining high accuracy.