FFT image registration fails for multiples of 8

[Harlequinade]

I'm trying to do some image registration in LabVIEW on the spectral properties of two arrays. With the formula below I'm trying to get the offsets in x and y for the two 2D arrays by using the Fast Fourier Transforms.

However, when I try different array sizes, I realise it doesn't work for array sizes that are multiples of 8. Am I doing something mathematically wrong or programmatically (or is LV again unfriendly)? Does someone has a idea how to solve this?

[Charles_CLA]

You do realize that in order to do an FFT you MUST have an array size that is a power of 2 right? Any array size that is not 2^N would require a DFT (Discreet Fourier Transform). I can't remember if the particular function that you are using automatically switches between DFT and FFT or not.

[Harlequinade]

Uhm, I made a mistake by saying it is in multiples of 8. I rather notice is for number that are the power of 2 (8, 16, 32, 64, 128, 256, 512 ...).

[Charles_CLA]

Could you re-state the question please? I want to be sure that I understand the problem.

Charles

[Harlequinade]

So then why should the FFT then actually work for the non power of 2 in the first place?

[Harlequinade]

I'm doing image registration on images with different sizes. However, I noticed that for the images (which are 2D arrays) with sizes of the power of 2 don't succeed at all and thus don't find the applied shift.

[altenbach]

---

@Charles_CLD wrote:

You do realize that in order to do an FFT you MUST have an array size that is a power of 2 right? Any array size that is not 2^N would require a DFT (Discreet Fourier Transform).

---

That's only true for the Cooley–Tukey algorithm, there are many other FFTs, and most don't have that restriction.

[altenbach]

Can you re-attach your snipped containing some typical default data in the controls (especially data that causes it to fail)

What is your definition of "does not work" (unexpected result, no output, error popup, computer crashes)?

[Harlequinade]

I can do that tomorrow. I'm working on it, but I can't think straight anymore at this hour.

[Harlequinade]

Here I have attached an example made in LV2010 SP1.

By pressing the boolean button, it removes the first row and column and making the 16x16 array an 15x15 array.

It's obviously seen by eye that the 'image' has shifted regarding the 'template' with 2 pixels to the left and 1 pixel up. When it's a 15x15 array, the algorithm finds that, when it's a 16x16 array, it 'fails' to find the offset.