10
$\begingroup$

I have successfully tested 1D phase correlation algorithm to determine vertical shift between two synthetic images.

When I moved to real images, however, it is not able to detect translation at all (the peak is located at 0, which is wrong result).

I have the following images:

enter image description here enter image description here

And resulting phase correlation (Magnitude, Real, Imaginary):

enter image description here

enter image description here

enter image description here

The first scanline of the image is completely white, but the shift is obviously larger (20 pixels).

The expected result is white line on 20th row which happens only on synthetic images or light noise.

My algorithm is very simple - for each image column:

  1. Compute 1D FT of source and target image columns (a=FT(A), b=FT(B))
  2. Compute cross-power spectrum (cross_power = a *. conj(b) / |a *. conj(b)|) - *. denotes pointwise mutliplication, conj(x) denotes complex conjugate
  3. Compute phase correlation (phase = IFT(cross_power))
  4. Find maximum magnitude in every column of phase.
  5. Find consensus peak location (e.g. median of detected peak locations)

Can you please advise me how to improve baseline phase correlation algorithm to deal with real-world (noisy) images?

Should I rather use NCC (Normalized Cross Correlation) instead of FFT-based phase correlation?

UPDATE

I was experimenting with zero padding to rule out errors introduced by circular shifting (only simple linear shifting of images is desirable) and tested this on original images from Wikipedia:

enter image description here enter image description here

The single peak is clearly there as it should be:

enter image description here

However - if I perform slight smoothing (Gaussian blur) to reduce noise and actually improve the result, the phase correlation comes out totally mangled:

enter image description here enter image description here

enter image description here

Here is the enhanced version - the original peak is weaker (why??) and there appeared new peaks around zero shifts (why??):

enter image description here

Improve this question
$\endgroup$
11
  • $\begingroup$ As I see, on your phase-correlated image max peak shows corresponding shift. However, I don't know what is real amplitudes of cross-correlation between those images. $\endgroup$
    – Eddy_Em
    Apr 26, 2013 at 19:50
  • $\begingroup$ @Eddy_Em I will generate separate images for real and imaginary part and add it to the post in a while. So far there is only magnitude information. $\endgroup$
    – Libor
    Apr 26, 2013 at 19:51
  • $\begingroup$ Your reference in Wikipedia says to use 2D Fourier transforms. Why are you using 1D transforms? $\endgroup$
    – Peter K. ♦
    Apr 26, 2013 at 19:58
  • 1
    $\begingroup$ Well, yes, but you need to compare apples with apples. Just comparing the same columns in each image will not get you what you want. If the movement is large enough, there is no correlation whatsoever between columns. You need to consider the image as a whole. One way that might work is to sum the rows in both images, and do the 1D work on that. $\endgroup$
    – Peter K. ♦
    Apr 26, 2013 at 20:04
  • 1
    $\begingroup$ @PeterK. This was 2D - I have checked that the phase correlation came out as in the Wiki article, only flipped (probably due to flipped multipliers when computing cross-power spectrum or flipped input/output). I found that smoothing (Gaussian window) really hurts the final result, but not sure why. I will finally use Normalized Cross-Correlation instead, as the Phase Correlation seems to be weak when dealing with low frequency data. $\endgroup$
    – Libor
    Apr 26, 2013 at 23:56

2 Answers 2

Reset to default
10
$\begingroup$

One-dimensional version

The one-dimensional version that you list won't work. When there is a large enough shift in images (more than one or two pixels in real-world images), there will be nothing relating the column pixels.

For an example of this, try:

I5 = rand(100,100)*255;
I6 = zeros(100,100);
I6(11:100,22:100) = I5(1:90,1:79);

So that we have I5:

enter image description here

and I6:

enter image description here

Then the one-dimensional phase correlation is just:

enter image description here

whereas the two-dimensional phase correlation is:

enter image description here

It's a bit hard to see, but there is a very high peak in the bottom-righthand corner of the image. No clear peak exists in the one dimensional version.

Why doesn't smoothing help? #1

What correlation is trying to do is to find "similar" variations in each image. If the underlying signals are sufficiently random, then this will work well: the correlation of white noise with itself gives a really nice peak at the origin, and close-to-zero elsewhere.

Smoothing a "random" image with a Gaussian will have the effect of smoothing out the correlation your expecting --- spreading the energy in any peaks over a wider area.

Smoothing has the opposite effect of "pre-whitening" the image. Pre-whitening (as the name suggests) tries to make the image more like white noise --- which has the best form if we are doing correlation-based detection (in that the peak is well-localized).

What you are better off doing is using the matlab diff operation for a simplistic, but surprisingly effective, way of pre-whitening images.

See this example.

Why doesn't smoothing help? #2

Why does smoothing cause the extra peaks?

If you smooth each image with a kernel $k(x,y)$ then we get: $$ h_a = g_a \star k\\ h_b = g_b \star k $$ where $\star$ is convolution.

Now, $$ H_a = K G_a\\ H_b = K G_b\\ R = \frac{H_a H_b^*}{|H_a H_b^*|} = \frac{|K|^2G_a G_b^*}{|K|^2|G_a G_b^*|}\\ = \frac{G_a G_b^*}{|G_a G_b^*|} $$

What I suspect is happening (though I am not sure) is that perhaps your kernel has near-zero values in the frequency domain, causing numerical problems?

If I apply a kernel:

K = one(5,5);

to my random images, then I get:

enter image description here

for the two-dimensional correlation, which makes the peak more spread out, but does not exhibit the problems you are seeing.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Great answer, thanks! The problem I have is that the peak is not only badly localized, but it appears in completely wrong position. I have eventually read J.P.Lewis: "Fast Normalized Cross-Correlation" which says that phase correlation have troubles with varying image energy at different locations and thus pre-filtering should be applied - a Laplacian filter is proposed for signal whitening although any high-pass filter would do. The problem remains that the cutoff frequency is unknown beforehand and too high or too low threshold will again hurt the matching. But I will try it. $\endgroup$
    – Libor
    Apr 27, 2013 at 20:56
  • 1
    $\begingroup$ Off Topic: It is funny that Google search for "signal whitening" will teach you a lot about toothpaste :D $\endgroup$
    – Libor
    Apr 27, 2013 at 20:57
3
$\begingroup$

The easiest way to get good performance from phase correlation by whitening the signal is to take the log of the magnitude. You can also filter out the noise from the resulting correlation surface. For details see “Improving Phase Correlation for Image Registration”, Proceedings of (ICVNZ2011) Image and Vision Computing New Zealand 2011, p.488-493, , http://www98.griffith.edu.au/dspace/bitstream/handle/10072/44512/74188_1.pdf?sequence=1

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.