Normalised cross correlation

[Mike Sarahan]

Hi Tony,

Glad you figured this out.

I'm also not a huge fan of the Matlab-style padding.  I guess
theoretically, it gives your match greater range - beyond the bounds
of the image.  In practice, I found that such behavior in the presence
of noise often gave me a peak outside the image, when I knew I wanted
my peak inside the image.

I'm mixed on the input padding.  Intuitively, I think the high value
at template center is easier to understand for a human looking at the
cross correlation result image.  I know that this confused me a lot
when I first encountered cross correlation using OpenCV.  However, any
subsequent analysis (peak finding, for example) would have to account
for the difference, and I think this would be more of a headache than
a benefit to people.  I can imagine a lot of careless analyses with
offsets of exactly half the template dimensions.

Your proposed method for the padding makes more sense to me than
Matlab's.  I would recommend defaulting to no padding, and also
recommend a little documentation that warns the user about the offset
they will have to account for if using the pad option.

I can't think of a use case for padding the output with zeros.  If
anyone else knows one, I'll be happy to learn, though.

Best,
Mike

On Sat, Mar 24, 2012 at 4:03 PM, Tony Yu <tsyu80 at gmail.com> wrote:
>
>
> 2012/3/24 Stéfan van der Walt <stefan at sun.ac.za>
>>
>> Hi Mike
>>
>> On Sat, Mar 24, 2012 at 2:16 PM, Mike Sarahan <msarahan at gmail.com> wrote:
>> > I'm out of time for now, but I hope this helps a little.  I will
>> > investigate further when time allows, provided you all don't beat me
>> > to it.
>>
>> Thanks for looking into this, and for identifying the boundary issue.
>> The fact that there are differences even with padding is
>> disconcerting; I'll see if I can review this soon.
>>
>> Stéfan
>
>
> Ok,... so it turns out I made a stupid with the convolution-to-correlation
> translation. Fixing that gives comparable *looking* results to matlab (after
> Mike's padding patch). BUT, I also get NaN values with the padded output.
> These NaNs come from the sqrt of negative values (see code which solves the
> denominator). I *think* the argument of the sqrt should (mathematically) be
> zero, but round-off errors are causing it to go negative. If that's the
> case, then it's an easy fix to check that the argument is positive, but
> someone should check my math to make sure the the code matches the equation.
>
> As for the padding---that was a hack. I noticed the original implementation
> clipped the image to (M-m+1, N-n+1) so I padded *the result* with zeros to
> make the output (M, N). Also, the way I padded it (all padding on bottom and
> right) meant that the output has a high value when "origin" (i.e. top-left
> corner) of the template matches, as opposed to the center. This could be
> done by padding the image with half the template width to the left and
> right, and half the template height to the top and bottom.
>
> Padding *the input* sounds like a good idea, but I think it should be done
> in such a way that the output is (M, N)---i.e. same size as the input image.
> I'm not a huge fan of the Matlab output size (but maybe some people expect
> this output?).
>
> Is there a "right" way to do the padding? Or maybe "pad_output" should be
> changed to "mode" (to match scipy.signal.convolve) with values 'valid' (no
> padding; output (M-m+1, N-n+1)), 'same' (pad input with image mean), and
> 'zeros' (pad output with zeros)?
>
> -T