[Numpy-discussion] fast SSD

[Warren Weckesser]

On Tue, Jun 21, 2011 at 7:09 PM, Alex Flint <alex.flint at gmail.com> wrote:

> Is there a fast way to compute an array of sum-of-squared-differences
> between a (small)  K x K array and all K x K sub-arrays of a larger array?
> (i.e. each element x,y in the output array is the SSD between the small
> array and the sub-array (x:x+K, y:y+K)
>
> My current implementation loops over each sub-array and computes the SSD
> with something like ((A-B)**2).sum().
>

You can use stride tricks and broadcasting:

-----
import numpy as np
from numpy.lib.stride_tricks import as_strided

a = np.arange(24).reshape(4,6)

k = np.array([[1,2,0],[2,1,0],[0,1,1]])

# If `a` has shape (4,6), then `b` will have shape (2, 4, 3, 3).
# b[i,j] will be the 2-D sub-array of `a` with shape (3, 3).
b = as_strided(a,
        shape=(a.shape[0]-k.shape[0]+1, a.shape[1]-k.shape[1]+1) + k.shape,
        strides=a.strides * 2)

ssd = ((b - k)**2).sum(-1).sum(-1)


print a
print k
print ssd
-----

It's a neat trick, but be aware that the temporary result b - k will be nine
times the size of a.  If a is large, this might be unacceptable.

Warren



> Cheers,
> Alex
>
>
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion at scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20110621/c58386ce/attachment.html>