[FIXED] How to add neighboring elements of 2D array in Python without having to use nested loops?

Issue

I want to add neighboring elements "3x3" of an array and create new array. When using nested loops, it takes time since this piece of code will be called thousands of times.

import tensorflow as tf
import numpy as np

rows=6
cols=8

array1 = np.random.randint(10, size=(rows, cols))
print(array1)

array2=np.zeros((rows-2,cols-2))

for i in range(rows-2):
    for j in range(cols-2):
        array2[i,j]=np.sum(array1[i:i+3,j:j+3])# print()
        
print("output\n",array2)


##My output
    [[9 4 9 6 1 4 9 0]
     [2 3 4 2 0 0 9 0]
     [2 8 9 7 6 9 4 8]
     [6 3 6 7 7 0 7 5]
     [2 1 4 1 7 6 9 9]
     [1 1 2 6 3 8 1 4]]
    output
     [[50. 52. 44. 35. 42. 43.]
     [43. 49. 48. 38. 42. 42.]
     [41. 46. 54. 50. 55. 57.]
     [26. 31. 43. 45. 48. 49.]]

With vectorization, this can be solved. However, I tried different techniques but never had luck with any such as reshaping then adding arrays, using only one loop with size rows or cols. note: in my project, the size of rows and cols can be very big. it is similar to 2D convolution with kernal of ones. the question is, is there anyway to implement this without using loops? or at least reduce it to have smaller time complexity "to take only rows or cols as size of loop".

Solution

I got the solution that i find better for this cases. Use the function convolve2d from scipy.signal module I used the function np.ones and np.array to declare your input as a numpy array and used the convolve2d to apply your kernel to each an every part of your image. This is called Convolutional Filters and Kernels and it is used a lot in image processing with python.

In [50]: import numpy as np

In [55]: np.ones((3,3))
Out[55]: 
array([[1., 1., 1.],
       [1., 1., 1.],
       [1., 1., 1.]])

In [59]: input_matrix
Out[59]: 
array([[9, 4, 9, 6, 1, 4, 9, 0],
       [2, 3, 4, 2, 0, 0, 9, 0],
       [2, 8, 9, 7, 6, 9, 4, 8],
       [6, 3, 6, 7, 7, 0, 7, 5],
       [2, 1, 4, 1, 7, 6, 9, 9],
       [1, 1, 2, 6, 3, 8, 1, 4]])

In [60]: kernel
Out[60]: 
array([[1., 1., 1.],
       [1., 1., 1.],
       [1., 1., 1.]])

In [61]: from scipy.signal import convolve2d

In [63]: convolve2d(input_matrix, kernel, 'valid')
Out[63]: 
array([[50., 52., 44., 35., 42., 43.],
       [43., 49., 48., 38., 42., 42.],
       [41., 46., 54., 50., 55., 57.],
       [26., 31., 43., 45., 48., 49.]])

Also, as a matter of fact the speed of this is quite fast. As you can see, even in a 1000x1000 matrix it's fast enough.

In [68]: %timeit convolve2d(input_matrix, kernel, 'valid')
5.24 µs ± 21.2 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [69]: input = np.random.randint(10, size=(1000, 1000))

In [70]: %timeit convolve2d(input_matrix, kernel, 'valid')
41.6 ms ± 555 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Answered By - trenixjetix