Math behind scipy.ndimage.convolve

Question

While I have already found the documentation on scipy.ndimage.convolve function and I "practically know what it does", when I try to calculate the resulting arrays I can't follow the mathematical formula. Let's take for example:

a = np.array([[1, 2, 0, 0],`
             [5, 3, 0, 4],
             [0, 0, 0, 7],
             [9, 3, 0, 0]])

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

from scipy import ndimage

ndimage.convolve(a, k, mode='constant', cval=0.0)

# Why is the result like this ? 

array([[11, 10,  7,  4], 
       [10,  3, 11, 11],
       [15, 12, 14,  7],
       [12,  3,  7,  0]]) 

I would appreciate a step by step calculation.

Answer 1

Details on NDImage.convolve

I stumbled on this NDImage convolution eventhough I know the basic np.convolve, and the document is not much self explanatory, so I took the effort to crunch through and supplement the earlier explanatory post:

A. Basics:

Reference: refers to following if your concept on convolution is not so well grounded

https://en.wikipedia.org/wiki/Kernel_(image_processing),

https://en.wikipedia.org/wiki/Convolution

1. Essentially NDimage.convolve has 4 modes, this post focused on the Constant mode, for which you use the value as specified by cval=0 or whatever and add padded rows and columns as needed (will explain in a little bit)

2. The convolution essentially slides the kernel from left and right and then step down again and from left to right again until the needed (same number) number of convolved elements are achieved

3. The function will calculate the padded rows/columns needed. In this case the filter K is 3 x 3 matrix, and the source image is matrix a is 4 x 4, so you need two padded rows at top and bottom and two padded rows at left and right (4 + 2 = 6, and the number of rows or columns needed is 3 + 1 + 1 + 1 = 6, each slide will need the extra one row or column)

B. Operations:

1. Add a row and column of zeros to the top and left of Array a (to convolve a 3 x 3 to 4 x 4 evenly,

you need extra padded row/column at the 1st and 4th sliding window) and also one row/column of padded zeros to the bottom and right

2. Flip the kernel K as Kflip: [[0,0,1], [0,1,1], [1,1,1]] you can use numpy np.flip (why it need to be flipped basically relates to the concept of convolution vs correlation which are like twins in opposite direction)

3. Slide the flipped K matrix onto this size 6 x 6 expanded matrix [[0,0,0,0,0], [0,1,2,0,0], [0,5,3,0,4,0], [0,0,0,0,7], [0,9,3,0,0,0], [0,0,0,0,0]]

4. For the first step of sliding window (note the first row of column of the kernel will convolved with the padded zeros), you get:

Flipped K dot sum [[0,0,0], [0,1,2], [0,5,3]] = 11 (1*1+1*2+1*5+1*3, others are zeros)

(dot sum refers to sum of the inner dot element-wise multiplication, basically just multiply the corresponding elements in the same positions for the two given matrices)

5. Slide K one step to the right, you will have 10 (first row all zeros due to padded zeros, second row: 1*2+, third row 1*3 + 1*4, fourth row all zeros due to [0,0,0,0,7])

6. likewise you slide to the right for another two steps to get all four elements for the convolved matrix (note for the 4th of this row, again we partially convolved on expanded padded row/columns)(

7. Then you slide the K filter one row down and reset to the far left of the "expanded /padded matrix"

You will have again the same 10 (first row: 1*2+, second row 1*3 + 1*4), so on and so forth

Answer 2

Just to warm up consider

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

instead of your k, then if you

ndimage.convolve(a, k, mode='constant', cval=0.0)

you get

array([[4, 2, 4, 0],
       [5, 3, 7, 4],
       [3, 0, 0, 7],
       [9, 3, 0, 0]])

and note that any element is the sum of it's own position (due to the 2nd 1 in k) and the one below and to the right (due to the 1st 1 in k), ie the 4 in the top corner is from the original 1 in the top corner plus the 3 diagonally down from it.

The (possibly) confusing part is that the effect of the k is opposite of what you might expect, ie for the k above you might expect the first 1 to add the value above and to the left, instead of down and to the right.

Now back to yours: the 12 (3 down and 2 across) is the sum of 9+3+0+0+0+0.

Note that anything outside the matrix is assumed to be 0.