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@gmail.com> wrote:
2012/3/24 Stéfan van der Walt <stefan@sun.ac.za>
Hi Mike
On Sat, Mar 24, 2012 at 2:16 PM, Mike Sarahan <msarahan@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