How to cross-correlate in polar coordinate using FFT?

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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

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