How to calculate efficient local average of each coordinate of large matrix (average filter) in python

Question

I have large matrix, 4000x4000 I need to calculate local average of 11x11 window for each x,y of this matrix Generally it must be something like

for x in range(4000)
  for y in range(4000)
    b[x,y]=mean(a[x-5:x+5,y-5:y+5]

But this will run a lot of time Is it some more efficient way to do this? Thanks.

You don't want to do this calculation in Python code. numpy can probably do this, but their page is unusably slow at the moment. — Glenn Maynard, Nov 02 '10 at 14:50
Have you tried using xrange? How much more efficiency do you need? — Dana the Sane, Nov 02 '10 at 14:51

score 7 · Accepted Answer · edited May 23 '17 at 12:11

7

You essentially want a two-dimensional convolution. Scipy can do that for you: http://docs.scipy.org/doc/scipy/reference/generated/scipy.signal.convolve2d.html

In fact there's a similar answer right here on SO: 2d convolution using python and numpy

edited May 23 '17 at 12:11

Community

1
1

answered Nov 02 '10 at 14:52

Andrew Jaffe

26,554
4
50
59

score 4 · Answer 2 · answered Nov 02 '10 at 14:55

You can use a dynamic programming technique to make it many times faster. Preprocess the matrix by starting the top left corner and moving left to right, then top to bottom, setting each cell to be the sum of its value and the one above (if it exists) and the one to the left (if it exists). When you get to the end, the bottom right value should be the total sum of the whole matrix.

for x in xrange(4000):
    for y in xrange(4000):
        c[x,y] = a[x,y]
        if x > 0:
            c[x,y] += c[x-1,y]
        if y > 0:
            c[x,y] += c[x,y-1]

and now you can get the sum of any rectangular region by subtract the top left corner from the top right: eg. in this case, the sum of the 11x11 region will be

c[x+5,y+5]-c[x-5,y-5]

Then you can just divide by the size of the window to get the local average:

b[x,y] = (c[x+5+,y+5]-c[x-5,y-5])/121

Now instead of iterating over 121 spots for each element in the matrix, you only have to make 2 passes over the matrix with no iterations for each element.

How to calculate efficient local average of each coordinate of large matrix (average filter) in python

2 Answers2