Forums

How to cross-correlate in polar coordinate using FFT?

Started by Unknown February 22, 2007
Hi,

We all know the FFT-based cross-correlation in cartesian coordinate is
given by:

C = IFFT[ FFT[ f(x,y) ] * Conj[ FFT[ h(x,y) ] ]

Here is the question: how is it possible to do this in polar? I do not
think if this is the answer:

C = IFFT[ FFT[ f(r,p) ] * Conj[ FFT[ h(r,p) ] ]

where f(r,p) and h(r,p) are the polar transformation of f(x,y) and
h(x,y).

On 23 Feb, 02:44, sav...@hotmail.com wrote:
> Hi, > > We all know the FFT-based cross-correlation in cartesian coordinate is > given by: > > C = IFFT[ FFT[ f(x,y) ] * Conj[ FFT[ h(x,y) ] ] > > Here is the question: how is it possible to do this in polar? I do not > think if this is the answer: > > C = IFFT[ FFT[ f(r,p) ] * Conj[ FFT[ h(r,p) ] ] > > where f(r,p) and h(r,p) are the polar transformation of f(x,y) and > h(x,y).
Are these images? If so, what do you mean by "the polar transformation of f(x,y) and h(x,y)"? As a general rule of thumb, correlation properties should be preserved by a linear transform. However, if you use some other transform than the DFT, there is no reason to expect that the computations are easier or results are easier to interpret than in time domain. Rune
On 23 Feb, 08:19, "Rune Allnor" <all...@tele.ntnu.no> wrote:
> On 23 Feb, 02:44, sav...@hotmail.com wrote: > > > Hi, > > > We all know the FFT-based cross-correlation in cartesian coordinate is > > given by: > > > C = IFFT[ FFT[ f(x,y) ] * Conj[ FFT[ h(x,y) ] ] > > > Here is the question: how is it possible to do this in polar? I do not > > think if this is the answer: > > > C = IFFT[ FFT[ f(r,p) ] * Conj[ FFT[ h(r,p) ] ] > > > where f(r,p) and h(r,p) are the polar transformation of f(x,y) and > > h(x,y). > > Are these images? If so, what do you mean by "the polar > transformation of f(x,y) and h(x,y)"?
Yes, they are images. You can transform from cartesian to polar or log- polar by resampling.
> > As a general rule of thumb, correlation properties should be > preserved by a linear transform. However, if you use some > other transform than the DFT, there is no reason to expect > that the computations are easier or results are easier to > interpret than in time domain.
The question is if correlation in polar corrdinate can be done simply by a polar transform followed by the normal DFT-based correlation; or, the other transforms like Fourier-Mellin or henkel should be used.
> > Rune
On Feb 23, 8:08 am, sav...@hotmail.com wrote:
> We all know the FFT-based cross-correlation in cartesian coordinate is > given by: > C = IFFT[ FFT[ f(x,y) ] * Conj[ FFT[ h(x,y) ] ] > Here is the question: how is it possible to do this in polar? I do not > think if this is the answer: > C = IFFT[ FFT[ f(r,p) ] * Conj[ FFT[ h(r,p) ] ] > where f(r,p) and h(r,p) are the polar transformation of f(x,y) and > h(x,y).
Forget about the FFT for a moment, and try to write down what the convolution formula even looks like in polar coordinates. It is a mess (if you want to compute the same correlation function C), because convolutions involve translations in space and this is ugly in polar coordinates. Think about the formula for adding the vector (r,p) with (r',p') -- it's not (r+r', p+p')! I think you need to think a bit more about what operation you want to compute, *before* you look for fast algorithms to do it. Regards, Steven G. Johnson
On 24 Feb, 00:10, stev...@alum.mit.edu wrote:
> On Feb 23, 8:08 am, sav...@hotmail.com wrote: > > > We all know the FFT-basedcross-correlationin cartesian coordinate is > > given by: > > C = IFFT[ FFT[ f(x,y) ] * Conj[ FFT[ h(x,y) ] ] > > Here is the question: how is it possible to do this inpolar? I do not > > think if this is the answer: > > C = IFFT[ FFT[ f(r,p) ] * Conj[ FFT[ h(r,p) ] ] > > where f(r,p) and h(r,p) are thepolartransformation of f(x,y) and > > h(x,y). > > Forget about the FFT for a moment, and try to write down what the > convolution formula even looks like inpolarcoordinates. It is a > mess (if you want to compute the samecorrelationfunction C), because > convolutions involve translations in space and this is ugly inpolar > coordinates. > > Think about the formula for adding the vector (r,p) with (r',p') -- > it's not (r+r', p+p')! > > I think you need to think a bit more about what operation you want to > compute, *before* you look for fast algorithms to do it. > > Regards, > Steven G. Johnson
The desired operation is simply the numerical calculation of the correlation of two functions in polar coordinate: / 2Pi / R C(r, p) = | | f(r, p) h*(r - r', p - p') r' dr' dp' / 0 / 0 I am not sure if the correlation theorem is be invariant to coordinate transform or not. I have seen a paper (sorry the reference is not available to me right now) mentioning the use of FFT for the calclulation of the above correlation by linear correlation in r direction and cyclic correlation in p direction. This can be simply done by zero-padding in r direction and with a length of at least (R - 1). However, I am not convinced that the polar cross correlation can be simply given in the form of Fourier transform by: C(r, p) = IFT[ FT[ f(r, p) ] . Conj[ FT[ h(r, p) ] ] where f and h are zero-padded in r direction.
saveez@hotmail.com wrote:

> / 2Pi / R > C(r, p) = | | f(r, p) h*(r - r', p - p') r' dr' dp' > / 0 / 0
You need monospaced font *AND no tabs!* Jerry -- Engineering is the art of making what you want from things you can get. &macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;
On Feb 24, 2:05 pm, sav...@hotmail.com wrote:
> The desired operation is simply the numerical calculation of the > correlation of two functions in polar coordinate: > > / 2Pi / R > C(r, p) = | | f(r, p) h*(r - r', p - p') r' dr' dp' > / 0 / 0
This is just an ordinary two-dimensional correlation. The fact that you interpret the two arguments as radius and angle is completely irrelevant (except for the boundary conditions, see below)...all that matters is the form of the computation you are trying to perform. So, yes, you can use an FFT for this, no problem. As usual, however, an FFT computes a cyclic convolution, so you have to be careful whenever your boundary conditions are not periodic. Here, only the r dimension is not periodic. To get a linear convolution, you would zero-pad. But in this case, you have the boundary condition f(-r, p) = f(r, p + Pi), so you should pad in such a way as to enforce this.
> I am not sure if the correlation theorem is be invariant to coordinate > transform or not.
It's most certainly not. The above formula is a totally different operation from a convolution/correlation in Cartesian coordinates. Regards, Steven G. Johnson