3.38e11?  As pointed out in other posts. you definitely need to
scale .  Your image size is 640x480, so after transforming each image,
you should be dividing by 640x480.  After that, conjugate one of them,
multiply the two and inverse transform.

Your star points in the two images aren�t to far apart (about +9x and
+9y pixels image 2 relative to image 1), so you should be getting a
cross correlation peak displaced by 9x, 9y after the inverse (and
where this point shows up relative to the DC point depends on which
image you�re conjugating in the frequency domain).  This all presumes
that you don�t have one of the problems below.

How big is your DC (i.e.: 0, 0) point of each image after the
transform?  Are they large numbers relative to all the rest?  Are
there other large numbers at low frequencies?  If so, then you�ve
probably got some significant correlation between the two image
backgrounds.  I don�t know exactly how you generated the images, but
if all you did was to move one of the star points, then that may be
the case.  If so, then the cross correlation is only going to tell you
that �the zillions of non-zero pixels in image 1 correlate perfectly
with the zillions of non-zero pixels in image 2,� and the cross
correlation peak will be at 0,0.  This will also tend to swamp any
other correlation that shows up around the 0,0 point in the result, as
will be the case for your data.

Some kind of normalization or whitening is usually applied to prevent
this.  The simplest way is to zero out the DC value of each image
after transforming it.  If your transform also contains some strong
low frequencies (i.e.: close to 0,0), then a more robust technique may
be called for.  Another option is to apply a sharpening filter on each
image in the time domain before doing the cross correlation
(alternately, one can also apply them in the frequency domain).  This
usually results in a much stronger cross correlation.

You might also diminish the effects of a correlated background by
cropping your images and doing the cross correlation on smaller sizes
(e.g.: 100x100).

One other possible problem;  are you actually getting a peak, but it
shows up in the wrong place?  I don�t know which image you�re
conjugating , nor if you�re rotating your outputs to put the �DC� or
�no motion� point in the center of the cross correlation surface.

So maybe it�s just a scaling problem. Maybe it�s a correlated
background, or your peak is somewhere you didn�t intend it to be (and
I hope you�re not trying to transform .png files directly, because
they�re formatted).

Kevin

On May 6, 5:15&#4294967295;am, Johannes Bauer <dfnsonfsdu...@gmx.de> wrote:
> Hi group,
>
> I want to implement fast cross correlation using DFT. Therefore, what I
> do is take two pictures, FT them, complex conjugate one, multiply them
> and IFT them again.
>
> Then, looking at the picture, I should see a peak at a position, which
> indicates how the two original images are shifted against each other.
>
> In theory, it works great (sample pictures with lots of black and very
> distinct pattern).
>
> Now I simulate pictures which look more like what I'm dealing with (it's
> an astrophysical application, I'm photographing the sky):
>
> http://img379.imageshack.us/img379/6784/image1mod.pnghttp://img4.imageshack.us/img4/8433/image2mod.png
>
> i.e. tons'o'noise(tm), but a distinct star can be seen, which moves.
>
> When I now perform my algorithm, the results are totally unusable (i.e.
> the IDFTed picture has virtually a zero dynamic range, all values of
> around 3.38E11 +- 1E6.
>
> I'm guessing I'm doing something wrong in "real life" which is not
> mentioned in the textbooks (i.e. for practical application some kind of
> scaling or normalization needs to be applied beforehand or something
> along the lines).
>
> Any guess on what I'm doing wrong?
>
> Thanks in advance,
> Johannes
>
> --
> "Meine Gegenklage gegen dich lautet dann auf bewusste Verlogenheit,
> verl&#4294967295;sterung von Gott, Bibel und mir und bewusster Blasphemie."
> &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;-- Prophet und Vision&#4294967295;r Hans Joss aka HJP in de.sci.physik
> &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;<48d8bf1d$0$7510$54022...@news.sunrise.ch>

I have implemented the standard 1D Pearson Normalized Correlation with
FFT's with no issues, as Rune said, normalizing and zero padding the
original data was required (your FFT size doubles).  Did you try the
non FFT Correlation?

On 6 Mai, 11:15, Johannes Bauer <dfnsonfsdu...@gmx.de> wrote:
> Hi group,
>
> I want to implement fast cross correlation using DFT. Therefore, what I
> do is take two pictures, FT them, complex conjugate one, multiply them
> and IFT them again.

I assume you use the 2D DFT and uses proper zero-padding
to avoid wrap-around effects, etc.

If you don't know what I am talking about, make sure you
zero-pad both images to sizes (2Mm-1,2Nm-1) where
Mm = max(M1,M2) and Nm = max(N1,N2), and (M1,N1) and (M2,N2)
are the largest dimensions of images 1 and 2.

...
> I'm guessing I'm doing something wrong in "real life" which is not
> mentioned in the textbooks (i.e. for practical application some kind of
> scaling or normalization needs to be applied beforehand or something
> along the lines).
>
> Any guess on what I'm doing wrong?

Provided you already do the zero-padding, I'd look for
scaling constants. First of all, scale both images by
1/(MN) where M and N are the dimensions of the image.

Second, you might scale each image by their L2 norm:

        N   M
N_L2 = sum sum |x(n,m)|^2
       n=1 m=1

and scale the images by 1/N_L2.

If you do all this correctly [*] you get correlation
measures in the range [-1, 1].

Rune

[*] Plenty of details need to be considered for this
    to work:
    - The first scales might have to be some power
      of M and N, like 1/(N^2M^2) or something like that.
    - You need to coose the correct dimensions to use.
      It could be the original (M,N), or it could be the
      zero-padded (Mm,Nm).
    All of these details depend to a large extent on
    implementation details in the FFT you use.

Hi group,

I want to implement fast cross correlation using DFT. Therefore, what I
do is take two pictures, FT them, complex conjugate one, multiply them
and IFT them again.

Then, looking at the picture, I should see a peak at a position, which
indicates how the two original images are shifted against each other.

In theory, it works great (sample pictures with lots of black and very
distinct pattern).

Now I simulate pictures which look more like what I'm dealing with (it's
an astrophysical application, I'm photographing the sky):

http://img379.imageshack.us/img379/6784/image1mod.png
http://img4.imageshack.us/img4/8433/image2mod.png

i.e. tons'o'noise(tm), but a distinct star can be seen, which moves.

When I now perform my algorithm, the results are totally unusable (i.e.
the IDFTed picture has virtually a zero dynamic range, all values of
around 3.38E11 +- 1E6.

I'm guessing I'm doing something wrong in "real life" which is not
mentioned in the textbooks (i.e. for practical application some kind of
scaling or normalization needs to be applied beforehand or something
along the lines).

Any guess on what I'm doing wrong?

Thanks in advance,
Johannes

-- 
"Meine Gegenklage gegen dich lautet dann auf bewusste Verlogenheit,
verl�sterung von Gott, Bibel und mir und bewusster Blasphemie."
         -- Prophet und Vision�r Hans Joss aka HJP in de.sci.physik
                         <48d8bf1d$0$7510$5402220f@news.sunrise.ch>