# Algorithm for efficient creation of submatrices from original matrix

I wrote this code to simply visualise what happens to an image when it gets put through repeated convolutional filters is a CNN.

The code works fine and produces the expected result but the it is also very inefficient.

One thing I can't figure out is when we want to apply convolutional filters to the input image we need to create a number of submatrices of specified shape from the original matrix, but I can't see to figure out how to do this correctly. The current solution involves cycling through indices in both axes which has O(n^2) complexity. How can I do it more efficiently?

Also any other suggestions welcome.

import numpy as np
import matplotlib.pyplot as plt
from PIL import Image

"""
Load image, normalise, resize and convert to greyscale.

file_loc: image file location
new_size: resize original image to this size.
"""
with Image.open(file_loc) as f:
f = f.resize(new_size)
img = np.asarray(f)/255
# Convert to black/white
bw_img = np.mean(img, axis=2)
bw_img.reshape(1, -1)
return [bw_img]    # return a list because will need a list down the line

def init_filters(n: int, shape: tuple) -> list:
"""
Initialise random filters.

n: number of filters to create
shape: required shape of filters
"""
filters = [np.random.randint(-100, 100, shape) for i in range(n)]
return filters

def get_submatrix(matrix: np.ndarray, size: tuple, start_idx: tuple):
"""
Get a submatrix of a specified size from the original image array.
"""
ax0_slice = slice(start_idx[0], start_idx[0] + size[0])
ax1_slice = slice(start_idx[1], start_idx[1] + size[1])
return matrix[ax0_slice, ax1_slice]

def calculate_single_conv(
matrix: np.ndarray,
kernel: np.ndarray,
conv_size: tuple,
step: tuple
):
"""
Apply a single convolution filter to an image.

Parameters:
matrix: matrix of the input image
kernel: an array of size conv_size representing
convolutional filter.
conv_size: size of the colvolutional filter
step: number of pixels to traverse when applying
convolutional filter.
"""
m = matrix.shape[0]
k = kernel.shape[0]
res_shape = int(((m - k) / step[0]) + 1)
res = np.zeros((res_shape, res_shape))

for j in range(0, m, step[1]):
row_no = j // step[1]
for i in range(0, m, step[0]):
col_no = i // step[0]
start_idx = (i, j)

sub = get_submatrix(matrix, start_idx=start_idx, size=conv_size)
try:
pix = np.sum(np.matmul(sub, kernel))
try:
res[col_no, row_no] = pix
except IndexError:
pass
except ValueError:
try:
res[col_no, row_no] = 0
except IndexError:
pass
return res

def pool_result(res: np.ndarray, pool_size: int):
"""
Downscale (pool) the resulting image by taking the maximum
value of a submatrix of shape (pool_size, pool_size).

res: input image with convolutional filter applied
pool_size: dimension of m*m matrix.
"""
starts = [i for i in range(0, res.shape[0], pool_size) if (i + pool_size) <= res.shape[0]]
out = np.zeros((len(starts), len(starts)))
for idx_i, i in enumerate(starts):
for idx_j, j in enumerate(starts):
p = res[i:i + pool_size, j: j + pool_size]
try:
out[idx_i, idx_j] = p.max()
except ValueError:
pass
return out

def calculate_multiple_conv(list_of_mat: list,
n_kernels: int,
shape: tuple,
step: tuple,
pool_size: int = None):
"""
Calculate and plot convolutions for multiple images and multiple
convolutional filters.

Parameters:
list_of_mat: list of matrices (images) to apply filters to.
n_kernels: number of randomly generated filters.
shape: shape of convolutional kernel.
step: number of pixels to traverse with each new step.
pool_size: if integer defines the size of m * m downsampling
( max pooling) matrix. If None - no downsampling applied
to resulting matrix.
"""

filters = init_filters(n_kernels, shape)
cols = 4
n_mat = len(list_of_mat)

if n_kernels % 4 == 0:
rows = n_kernels  // 4
else:
rows = (n_kernels  // 4) + 1

out_mat = []

for m in list_of_mat:

fig, axs = plt.subplots(nrows=rows, ncols=cols, figsize=((20, 20)))

for (idx, axi), fil in zip(enumerate(axs.flat), filters):
img = calculate_single_conv(m, fil, conv_size=shape, step=step)
row = idx // cols
col = idx % cols

if pool_size is not None:
img = pool_result(img, pool_size=pool_size)
out_mat.append(img)
axi.imshow(img, cmap='gray')

print(out_mat[0].shape)
plt.show()
return out_mat

if __name__ == '__main__':
$$$$
`