Fourier acceleration

From Dynamo
Jump to navigation Jump to search

“Fourier Acceleration” is an informal term.

Determining the position of a (possibly rotated) template inside a particle requires "sliding" the matrix representing the template along the matrix representing the particle, centering the template at each pixel of the data particle. For each recentering o the template, the normalized cross correlation of shifted template and the data particle is computed. This operation is formally known as the correlation of two signals (template and data).

If just means that the operation of correlation of two matrices in direct space is equivalent to the inverse Fourier transform of the pixelwise multiplication of the Fourier transforms of the two original matrices.

As this computation is much, much faster than computing the convolution explicitly (i.e, moving the template for every shift position and then computing the CC between shifted template and data for that particular position), one talks about “acceleration”.

Fourier acceleration thus tests by construction all possible shifts of the template inside the data particle, even though generally most of the shifts are not allowed by the shift limiting policy used in the particular alignment project. Even though Fourier acceleration is benefitial compared to direct space computation, even if only very few shifts have to be tested, as a comparison of template and data will generally require computing the Fourier transport of both objects anyway, (in order to apply a bandpass, or to impose the missing wedge of the particle onto the template).