{"action":"created","issue":{"url":"https://api.github.com/repos/scikit-image/scikit-image/issues/1712","labels_url":"https://api.github.com/repos/scikit-image/scikit-image/issues/1712/labels{/name}","comments_url":"https://api.github.com/repos/scikit-image/scikit-image/issues/1712/comments","events_url":"https://api.github.com/repos/scikit-image/scikit-image/issues/1712/events","html_url":"https://github.com/scikit-image/scikit-image/issues/1712","id":107035602,"number":1712,"title":"feature.match_template gives out-of-range match values","user":{"login":"zpincus","id":174217,"avatar_url":"https://avatars.githubusercontent.com/u/174217?v=3","gravatar_id":"","url":"https://api.github.com/users/zpincus","html_url":"https://github.com/zpincus","followers_url":"https://api.github.com/users/zpincus/followers","following_url":"https://api.github.com/users/zpincus/following{/other_user}","gists_url":"https://api.github.com/users/zpincus/gists{/gist_id}","starred_url":"https://api.github.com/users/zpincus/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/zpincus/subscriptions","organizations_url":"https://api.github.com/users/zpincus/orgs","repos_url":"https://api.github.com/users/zpincus/repos","events_url":"https://api.github.com/users/zpincus/events{/privacy}","received_events_url":"https://api.github.com/users/zpincus/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":28,"created_at":"2015-09-17T17:41:17Z","updated_at":"2015-12-11T07:29:41Z","closed_at":null,"body":"Hello all,\r\n\r\nI have found that in at least certain modes, `skimage.feature.match_template` calculates very incorrect cross-correlation values, well outside of the [-1,1] range that is expected. I have attached a simple test case, with a large image and a small template. [This old StackOverflow answer](http://stackoverflow.com/questions/20102353/scikit-image-match-template-returns-undocumented-values) by @stefanv seems to suggest that such a bug was fixed a while ago, but if so, it's back.\r\n\r\nDifferent padding modes change the scale of the misbehavior, but even `pad_input=False` still yields wrong cross-correlation values.\r\n\r\n```python\r\nimport skimage\r\nskimage.__version__ # '0.12dev'\r\nfrom skimage import feature\r\nfrom skimage import io\r\ntemplate = io.imread('template.png')\r\nimage = io.imread('image.png')\r\npeaks = feature.match_template(image, template, pad_input=True, mode='edge')\r\npeaks.min() # -26.632982\r\npeaks.max() # 1.7565135\r\n```\r\n\r\nStrangely, if I crop the image a little, to include the positions of the erroneous min and max values, then the values change. But cross-correlation should be a local operation! Maybe the problem appears if the image is too large?\r\n\r\n```python\r\nimport numpy\r\nnumpy.unravel_index(peaks.argmin(), peaks.shape) # (2449, 885)\r\nnumpy.unravel_index(peaks.argmax(), peaks.shape) # (2494, 404)\r\nimage.shape # (2500, 1660)\r\ntemplate.shape # (76, 76)\r\nsmall = image[2000:, :1200]\r\npeaks_small = feature.match_template(small, template, pad_input=True, mode='edge')\r\npeaks_small.min() # -0.5584954\r\npeaks_small.max() # 0.82173121\r\n```\r\n\r\n\r\n![image](https://cloud.githubusercontent.com/assets/174217/9940631/9ce28896-5d36-11e5-93d2-13459eb34577.png)\r\n![template](https://cloud.githubusercontent.com/assets/174217/9940683/e6758ecc-5d36-11e5-8659-d26af9e0e85d.png)"},"comment":{"url":"https://api.github.com/repos/scikit-image/scikit-image/issues/comments/163864627","html_url":"https://github.com/scikit-image/scikit-image/issues/1712#issuecomment-163864627","issue_url":"https://api.github.com/repos/scikit-image/scikit-image/issues/1712","id":163864627,"user":{"login":"MartinSavc","id":13271582,"avatar_url":"https://avatars.githubusercontent.com/u/13271582?v=3","gravatar_id":"","url":"https://api.github.com/users/MartinSavc","html_url":"https://github.com/MartinSavc","followers_url":"https://api.github.com/users/MartinSavc/followers","following_url":"https://api.github.com/users/MartinSavc/following{/other_user}","gists_url":"https://api.github.com/users/MartinSavc/gists{/gist_id}","starred_url":"https://api.github.com/users/MartinSavc/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MartinSavc/subscriptions","organizations_url":"https://api.github.com/users/MartinSavc/orgs","repos_url":"https://api.github.com/users/MartinSavc/repos","events_url":"https://api.github.com/users/MartinSavc/events{/privacy}","received_events_url":"https://api.github.com/users/MartinSavc/received_events","type":"User","site_admin":false},"created_at":"2015-12-11T07:29:41Z","updated_at":"2015-12-11T07:29:41Z","body":"A 1D demonstration of the problem (as I perceive it) with the code:\r\n''''\r\nwin_size = 100\r\ns = np.float32((np.random.randn(10000)*100)**2)\r\ns_int = s.cumsum()\r\n\r\ns_int_win = (s_int[win_size:] - s_int[:-win_size])\r\ns_conv_win = fftconvolve(s, np.ones(win_size))\r\ns_conv_win = s_conv_win[win_size:-win_size+1]\r\n\r\nclf()\r\nsubplot(211)\r\nplot(s_int_win, label='filtered using int')\r\nplot(s_conv_win, label='filtered using conv')\r\nlegend(loc='best')\r\nsubplot(212)\r\nplot(s_int_win - s_conv_win,label='s_int_win - s_conv_win')\r\nlegend(loc='best')\r\n''''\r\n\r\n![conv_int_1d](https://cloud.githubusercontent.com/assets/13271582/11738080/c4fc5ffa-9fdf-11e5-9b0d-9899810302e7.png)\r\n\r\nAs you can see from the figure, the error between using convolution and integral images is not large. But the problem is, the error is growing with the number of samples. In template matching the results of this calculation (filtering) is used as a denominator. It's only when the sum is large enough does this manifest as an observable error. \r\n\r\nIf the convolution is calculated using DFT the issue is resolved by using the Cooley-Tukey or similar algorithm. Using that algorithm you avoid summing the values of the image sequentially (adding a small value to an already large partial sum). A direct DFT would most likely have a similar problem, when calculating the mean. "}}