Matching orientations of 2-d arrays of values - using fft?

[n00bot]

Matching orientations of 2-d arrays of values -- using fft?

I was discussing the following problem (a subproblem of a personal project I'm working on) with a professor:

we're given two 2-d arrays of values. We know them to be identical, but they might not be oriented corrected -- i.e.,

0 0 7 0
7 7 0 7
0 7 0 8
0 9 9 0

and

0 7 8 0
7 0 0 9
0 7 7 9
0 7 0 0

I'm working with much much bigger arrays, and was saying that checking to see if they line up, recalculating/turning and checking again was going to be a huge time sink. He suggested that I look into Fast Fourier Transforms.

I'm an undergrad, currently taking Diff Eq, and I've never dealt with Fourier transforms. So far, it seems to me that in order to use FFTs, I'll have to extrapolate (somehow? I think using diff eqs?) a function describing arrays, and then, using another function (the Fourier transform), transform one function into another function, so that I'm just comparing functions. (Does that make any sense?)
As is probably obvious, I'm having a hard time understanding Fourier transforms and how this relates. Can anyone help point me in the right direction? Thanks!

 

[pmsrw3]

Google "image rotation FFT" and you'll find tons on this.

 

[n00bot]

pmsrw3 -- thanks, not sure why I was having so much trouble before. I did find some good explanations and I have a better, though still vague, idea of how this works now.

My understanding is that when you apply the Fourier transform equation (for a 2-D image) to your image, you come up with the new function you'll be manipulating. So, this new function is what you'd change the phase of to 'rotate' it. Am I understanding this right?

If so, then an implementation question:
The formula I've seen for 2d arrays uses x, y sums -- How do you take into account the 3-tuple color values in the 2-d array? Are we taking an average or maintaining a 3-tuple sum?

Thanks again.