RSS News FeedCross correlation with sub pixel accuracy
Message-ID:<gomch3$1l55$1@adenine.netfront.net>
Subject:
Cross-correlation with sub-pixel accuracy
Date:Wed, 4 Mar 2009 17:59:24 +0100
I'm performing phase only correlation between 2 images to find the displacement using FFT's, which gives a discrete correlation plain. Currently I'm finding the peak location simply from the maximum value of the correlation plane. Can anyone help me find a method to find the peak location with sub-pixel accuracy by looking at the neighbouring pixels around the peak? I've seen method that use curve fitting but this is too slow. I'm looking for a simple method that can be implemented quickly without iteration. Perhaps some kind of averaging of neighbouring locations using the values as weights? Peter
Message-ID:<49aec93d$0$31343$9b4e6d93@newsspool4.arcor-online.net>
Subject:
Re: Cross-correlation with sub-pixel accuracy
Date:Wed, 4 Mar 2009 19:32:24 +0100
Peter Bone schrieb: > I'm performing phase only correlation between 2 images to find the > displacement using FFT's, which gives a discrete correlation plain. > Currently I'm finding the peak location simply from the maximum value of the > correlation plane. Fine. > Can anyone help me find a method to find the peak > location with sub-pixel accuracy by looking at the neighbouring pixels > around the peak? Take a small region of the correlation plane around the peak, interpolate it to e.g. 4 times the resolution using a sinc kernel, then again find the maximum amplitude position. Hendrik vdH
Message-ID:<goolh4$hqt$1@adenine.netfront.net>
Subject:
Re: Cross-correlation with sub-pixel accuracy
Date:Thu, 5 Mar 2009 14:53:37 +0100
"Hendrik van der Heijden" <hvdh@gmx.de> wrote in message
news:49aec93d$0$31343$9b4e6d93@newsspool4.arcor-online.net...
> Take a small region of the correlation plane around the peak,
> interpolate it to e.g. 4 times the resolution using a sinc
> kernel, then again find the maximum amplitude position.
Thanks. It still sounds quite time consuming though.
Here's a simple method I just wrote that attempts to find a sub-pixel peak
location by analysing a 5x5 region centred on the peak (a). It averages
pixel coordinates using the pixel values as weights. It seems to give fairly
sensible results and is fast. Can you think of any reason why this is a bad
idea and why interpolation would be better?
This gives peak at (3.5,3.5) rather than (3,3) for the max peak location.
a = [-1 -1 -2 -2 -2 ;
-1 5 10 10 5 ;
-2 10 100 99 10 ;
-2 10 99 99 10 ;
-2 5 10 10 5 ];
x = 0;
y = 0;
sum = 0;
for r = 1 : 5
for c = 1 : 5
v = max(0, a(r,c));
sum = sum + v;
x = x + c * v;
y = y + r * v;
end
end
x = x / sum
y = y / sum
Message-ID:<49b000a8$0$31880$9b4e6d93@newsspool3.arcor-online.net>
Subject:
Re: Cross-correlation with sub-pixel accuracy
Date:Thu, 5 Mar 2009 17:41:05 +0100
Peter schrieb:
> Here's a simple method I just wrote that attempts to find a sub-pixel peak
> location by analysing a 5x5 region centred on the peak (a). It averages
> pixel coordinates using the pixel values as weights. It seems to give fairly
> sensible results and is fast. Can you think of any reason why this is a bad
> idea and why interpolation would be better?
This algorithm ("center of gravity") is fast but has two minor drawbacks.
The region around the peak needs to have small/zero values compared
to the peak amplitude.
And is has systematic error:
The FFT bin i corresponds to frequency i/N.
A frequency (i+d)/N, 0<d<1 spreads its energy over surrounding bins
in a way that CoG will find (i+d')/N instead of the right frequency.
However, I think there's a function which will map d' to d.
I remember this being explained in Rick Lyons' book
"Understanding DSP".
Hendrik vdH
Message-ID:<bb770182-256a-42bd-b2b3-cfeb6538fbef@t7g2000yqa.googlegroups.com>
Subject:
Re: Cross-correlation with sub-pixel accuracy
Date:Fri, 6 Mar 2009 09:40:21 +0100
> Can anyone help me find a method to find the peak > location with sub-pixel accuracy by looking at the neighbouring pixels > around the peak? I've seen method that use curve fitting but this is too > slow. Have you tried simple parabolic/quadratic interpolation? I have used this to find peaks in Hough space before and it's pretty simple and quick. You can treat the x and y axis separately, so perform two 1-D interpolations for speed. If the value of your function at your highest point on the curve Is B, and its neighbours are A and C, then the peak is located at: x = 0.5* (A-C) / (A-2B+C) I'm writing this from memory so you might want to doa quick check on that ;o) Hope that might help. Regards Jason www.visionexperts.co.uk
Message-ID:<dd7f267d-1871-4169-818e-a1e6e746c665@t7g2000yqa.googlegroups.com>
Subject:
Re: Cross-correlation with sub-pixel accuracy
Date:Fri, 6 Mar 2009 12:37:21 +0100
On Mar 4, 6:59=A0pm, "Peter Bone" <peterb...@hotmail.com> wrote: > I'm performing phase only correlation between 2 images to find the > displacement using FFT's, which gives a discrete correlation plain. > Currently I'm finding the peak location simply from the maximum value of = the > correlation plane. Can anyone help me find a method to find the peak > location with sub-pixel accuracy by looking at the neighbouring pixels > around the peak? I've seen method that use curve fitting but this is too > slow. I'm looking for a simple method that can be implemented quickly > without iteration. Perhaps some kind of averaging of neighbouring locatio= ns > using the values as weights? > Peter Check article by Hassan Foroosh "Extension of phase correlation to subpixel registration"
Message-ID:<gomch3$1l55$1@adenine.netfront.net>
Subject:
Cross-correlation with sub-pixel accuracy
Date:Wed, 4 Mar 2009 17:59:24 +0100
I'm performing phase only correlation between 2 images to find the displacement using FFT's, which gives a discrete correlation plain. Currently I'm finding the peak location simply from the maximum value of the correlation plane. Can anyone help me find a method to find the peak location with sub-pixel accuracy by looking at the neighbouring pixels around the peak? I've seen method that use curve fitting but this is too slow. I'm looking for a simple method that can be implemented quickly without iteration. Perhaps some kind of averaging of neighbouring locations using the values as weights? Peter
Message-ID:<49aec93d$0$31343$9b4e6d93@newsspool4.arcor-online.net>
Subject:
Re: Cross-correlation with sub-pixel accuracy
Date:Wed, 4 Mar 2009 19:32:24 +0100
Peter Bone schrieb: > I'm performing phase only correlation between 2 images to find the > displacement using FFT's, which gives a discrete correlation plain. > Currently I'm finding the peak location simply from the maximum value of the > correlation plane. Fine. > Can anyone help me find a method to find the peak > location with sub-pixel accuracy by looking at the neighbouring pixels > around the peak? Take a small region of the correlation plane around the peak, interpolate it to e.g. 4 times the resolution using a sinc kernel, then again find the maximum amplitude position. Hendrik vdH
Message-ID:<goolh4$hqt$1@adenine.netfront.net>
Subject:
Re: Cross-correlation with sub-pixel accuracy
Date:Thu, 5 Mar 2009 14:53:37 +0100
"Hendrik van der Heijden" <hvdh@gmx.de> wrote in message
news:49aec93d$0$31343$9b4e6d93@newsspool4.arcor-online.net...
> Take a small region of the correlation plane around the peak,
> interpolate it to e.g. 4 times the resolution using a sinc
> kernel, then again find the maximum amplitude position.
Thanks. It still sounds quite time consuming though.
Here's a simple method I just wrote that attempts to find a sub-pixel peak
location by analysing a 5x5 region centred on the peak (a). It averages
pixel coordinates using the pixel values as weights. It seems to give fairly
sensible results and is fast. Can you think of any reason why this is a bad
idea and why interpolation would be better?
This gives peak at (3.5,3.5) rather than (3,3) for the max peak location.
a = [-1 -1 -2 -2 -2 ;
-1 5 10 10 5 ;
-2 10 100 99 10 ;
-2 10 99 99 10 ;
-2 5 10 10 5 ];
x = 0;
y = 0;
sum = 0;
for r = 1 : 5
for c = 1 : 5
v = max(0, a(r,c));
sum = sum + v;
x = x + c * v;
y = y + r * v;
end
end
x = x / sum
y = y / sum
Message-ID:<49b000a8$0$31880$9b4e6d93@newsspool3.arcor-online.net>
Subject:
Re: Cross-correlation with sub-pixel accuracy
Date:Thu, 5 Mar 2009 17:41:05 +0100
Peter schrieb:
> Here's a simple method I just wrote that attempts to find a sub-pixel peak
> location by analysing a 5x5 region centred on the peak (a). It averages
> pixel coordinates using the pixel values as weights. It seems to give fairly
> sensible results and is fast. Can you think of any reason why this is a bad
> idea and why interpolation would be better?
This algorithm ("center of gravity") is fast but has two minor drawbacks.
The region around the peak needs to have small/zero values compared
to the peak amplitude.
And is has systematic error:
The FFT bin i corresponds to frequency i/N.
A frequency (i+d)/N, 0<d<1 spreads its energy over surrounding bins
in a way that CoG will find (i+d')/N instead of the right frequency.
However, I think there's a function which will map d' to d.
I remember this being explained in Rick Lyons' book
"Understanding DSP".
Hendrik vdH
Message-ID:<bb770182-256a-42bd-b2b3-cfeb6538fbef@t7g2000yqa.googlegroups.com>
Subject:
Re: Cross-correlation with sub-pixel accuracy
Date:Fri, 6 Mar 2009 09:40:21 +0100
> Can anyone help me find a method to find the peak > location with sub-pixel accuracy by looking at the neighbouring pixels > around the peak? I've seen method that use curve fitting but this is too > slow. Have you tried simple parabolic/quadratic interpolation? I have used this to find peaks in Hough space before and it's pretty simple and quick. You can treat the x and y axis separately, so perform two 1-D interpolations for speed. If the value of your function at your highest point on the curve Is B, and its neighbours are A and C, then the peak is located at: x = 0.5* (A-C) / (A-2B+C) I'm writing this from memory so you might want to doa quick check on that ;o) Hope that might help. Regards Jason www.visionexperts.co.uk
Message-ID:<dd7f267d-1871-4169-818e-a1e6e746c665@t7g2000yqa.googlegroups.com>
Subject:
Re: Cross-correlation with sub-pixel accuracy
Date:Fri, 6 Mar 2009 12:37:21 +0100
On Mar 4, 6:59=A0pm, "Peter Bone" <peterb...@hotmail.com> wrote: > I'm performing phase only correlation between 2 images to find the > displacement using FFT's, which gives a discrete correlation plain. > Currently I'm finding the peak location simply from the maximum value of = the > correlation plane. Can anyone help me find a method to find the peak > location with sub-pixel accuracy by looking at the neighbouring pixels > around the peak? I've seen method that use curve fitting but this is too > slow. I'm looking for a simple method that can be implemented quickly > without iteration. Perhaps some kind of averaging of neighbouring locatio= ns > using the values as weights? > Peter Check article by Hassan Foroosh "Extension of phase correlation to subpixel registration"