Re: Zero mean normalized cross correlation




einsteinhelpme@xxxxxxxxx wrote:
Hi:

I'm doing some template matching. Here are the formulae for the
different comparison methods I use (I denotes image, T - template, R -
result. The summation is done over template and/or the image patch:
x'=0..w-1, y'=0..h-1):


method=Cross_correlation:
R(x,y)=sumx',y'[T(x',y')·I(x+x',y+y')]

method=Normalized_cross_correlation:
R(x,y)=sumx',y'[T(x',y')·I(x+x',y+y')]/sqrt[sumx',y'T(x',y')2·sumx',y'I(x+x',y+y')2]

method=Cross_correlation_coefficient:
R(x,y)=sumx',y'[T'(x',y')·I'(x+x',y+y')],

where T'(x',y')=T(x',y') - 1/(w·h)·sumx",y"T(x",y")
I'(x+x',y+y')=I(x+x',y+y') - 1/(w·h)·sumx",y"I(x+x",y+y")

The latter might be called zero mean (something); T' and I' are zero
mean --- means subtracted.

method=Normalized_cross_correlation_coefficient:
R(x,y)=sumx',y'[T'(x',y')·I'(x+x',y+y')]/sqrt[sumx',y'T'(x',y')2·sumx',y'I'(x+x',y+y')2] (1)


IMHO, normalised and zero mean, assuming T' and I' are as in the
previous.

In ZMNCC, I think we have R(x,y) =1 if T' and I' are perfect matches at
displacement (x,y).

If there is an assumption that T and I are 'the same', I'm pretty sure
that ZMNCC is invariant under the affine transformation

vi = a.vt + b (2),

where vi is any pixel value in I and vt is any pixel value in T. Or is
it the other way round? Or is the inverse of (2) affine also?

My question is:

1- What's the difference between these and zero mean normalized cross
correlation? Can you give me any formula of the ZMNCC?

See above.


2- Is there some code to do ZMNCC?


(1) gives a pretty easy formula, but you have to cater for when you
fall off the edges of each image. If I and/or T are large, then FFT
will help; O(n^4) -> O(n^2) or less (?), where n ~ w, h.

If you want to play around with the mathematics, for example to verify
the invariance mentioned above, it will be a lot easier to start in
1-D, so that I, T are vectors and the sum of products is a scalar
product. In that case, normalisation is equivalent to vector
normalisation, i.e. reduce to unit length. I'm not sure there is any
bector equivalent of shifting to zero mean.

Incidentally, you will see SSD (sum of squared differences) also used
in certain cases.

Best regards,

Jon C.

.



Relevant Pages

  • Re: Cross Correlating Road Grade information
    ... Fred Marshall skrev: ... Template data, M points long, M>>N. ... Compute the mean of y', and subtract it from y'. ... It can be done in the frequency domain by zero padding x out to M+N-1 ...
    (comp.dsp)
  • Re: ifft(fft(a).*fft(b)) - explanation of results please
    ... The spike should therefore occur at the zero point of your ... your search template almost fills your data ... spike at location 2 in your correlation, whereas a lag of one sample ...
    (comp.soft-sys.matlab)
  • Re: Float comparison
    ... Are you saying there is a set of reals close to zero that can't be ... possible in the remainder of the significand. ... but that means a method of denoting the denormalization. ... normalisation. ...
    (comp.lang.c)
  • Re: Dynamic Content - Meta Tags
    ... Will check out the template deal. ... or a numeric position when it does find it. ... number other than zero, when casted to a boolean, is true, and zero is ... buffer (not really efficient unless you are using output caching or ...
    (comp.lang.php)
  • Re: No Type Library?
    ... derived class of the template itself. ... object the reference counter goes down to zero ... For the counter to go down to zero, ...
    (microsoft.public.vc.atl)