Normalised cross correlation

[Tony Yu]

On Sat, Mar 24, 2012 at 7: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<https://github.com/tonysyu/scikits-image/commit/ff4d66305c35fc7c749ab0d3ff128d07657c5096>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<https://github.com/tonysyu/scikits-image/blob/skimage-template/skimage/feature/_template.pyx#L122> which
> solves the denominator<https://github.com/tonysyu/scikits-image/blob/skimage-template/skimage/feature/_template.pyx#L22>).
> 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<https://github.com/tonysyu/scikits-image/blob/skimage-template/skimage/feature/_template.pyx#L122>matches the
> equation<https://github.com/tonysyu/scikits-image/blob/skimage-template/skimage/feature/_template.pyx#L22>
> .
>
> 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
>

Just to follow up: This would be my preferred way to pad the
image.<https://github.com/tonysyu/scikits-image/commit/d1b0cb40af5e757e786216ae4536b2dcc31a2c26>
Here,
the maximum in the output corresponds to the center of the best
template-match.
-T
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scikit-image/attachments/20120324/54ac12fa/attachment.html>