2D Convolution of Image using a complex Numpy algorithm with constant speed-up.

convolution.py

import numpy as np

def convolve(image, kernel):
  # We start off by defining some constants, which are required for this code
  kernelH, kernelW = kernel.shape
  imageH, imageW = kernel.shape
  h, w = imageH + 1 - kernelH, imageW + 1 - kernelW
  
  # filter1 creates an index system that calculates the sum of the x and y indices at each point
  # Shape of filter1 is h x kernelW
  filter1 = np.arange(kernelW) + np.arange(h)[:, np.newaxis]
  
  # intermediate is the stepped data, which has the shape h x kernelW x imageH
  intermediate = image[filter1]
  
  # transpose the inner dimensions of the intermediate so as to enact another filter
  # shape is now h x imageH x kernelW
  intermediate = np.transpose(intermediate, (0, 2, 1))
  
  # filter2 similarly creates an index system
  # Shape of filter2 is w * kernelH
  filter2 = np.arange(kernelH) + np.arange(w)[:, np.newaxis]
  
  # Apply filter2 on the inner data piecewise, resultant shape is h x w x kernelW x kernelH
  intermediate = intermediate[:, filter2]
  
  # transpose inwards again to get a resultant shape of h x w x kernelH x kernelW
  intermediate = np.transpose(intermediate, (0, 1, 3, 2))
  
  # piecewise multiplication with kernel
  product = intermediate * kernel
  
  # find the sum of each piecewise product, shape is now h x w
  convolved = product.sum(axis = (2,3))
  
  return convolved

flex_convolve.py

import numpy as np

# If you get this without any context, you are a legend.
def convolve(image, kernel):
  return (np.transpose(np.transpose(image[np.arange(kernel.shape[1]) + np.arange(image.shape[0] + 1 - kernel.shape[0])[:, np.newaxis]], (0, 2, 1))[:, np.arange(kernel.shape[0]) + np.arange(image.shape[1] + 1 - kernel.shape[1])[:, np.newaxis]], (0, 1, 3, 2)) * kernel).sum((2,3))

flex_sliding_window.py

import numpy as np

def sliding_window(image, kernel_shape):
  return np.transpose(np.transpose(image[np.arange(kernel_shape[1]) + np.arange(image.shape[0] + 1 - kernel_shape[0])[:, np.newaxis]], (0, 2, 1))[:, np.arange(kernel_shape[0]) + np.arange(image.shape[1] + 1 - kernel_shape[1])[:, np.newaxis]], (0, 1, 3, 2))

sliding_window.py

import numpy as np

def sliding_window(image, kernel_shape):
  # We start off by defining some constants, which are required for this code
  kernelH, kernelW = kernel_shape
  imageH, imageW = image.shape
  h, w = imageH + 1 - kernelH, imageW + 1 - kernelW
  
  # filter1 creates an index system that calculates the sum of the x and y indices at each point
  # Shape of filter1 is h x kernelW
  filter1 = np.arange(kernelW) + np.arange(h)[:, np.newaxis]
  
  # intermediate is the stepped data, which has the shape h x kernelW x imageH
  intermediate = image[filter1]
  
  # transpose the inner dimensions of the intermediate so as to enact another filter
  # shape is now h x imageH x kernelW
  intermediate = np.transpose(intermediate, (0, 2, 1))
  
  # filter2 similarly creates an index system
  # Shape of filter2 is w * kernelH
  filter2 = np.arange(kernelH) + np.arange(w)[:, np.newaxis]
  
  # Apply filter2 on the inner data piecewise, resultant shape is h x w x kernelW x kernelH
  intermediate = intermediate[:, filter2]
  
  # transpose inwards again to get a resultant shape of h x w x kernelH x kernelW
  final = np.transpose(intermediate, (0, 1, 3, 2))
  
  return final

slow_convolution.py

import numpy as np

# For the sake of your time, don't use this method! It is inefficient and extemely slow.
def convolve(image, kernel):
  # We start off by defining some constants, which are required for this code
  imageH, imageW = image.shape
  kernelH, kernelW = kernel.shape
  h, w = imageH + 1 - kernelH, imageW + 1 - kernelW
  
  # Array of shape h x w that is to be filled
  arr = np.zeros((h, w))
  for i in range(h):
    for j in range(w):
      # update array with the total sum of the (sliced window * kernel)
      arr[i, j] = np.sum(image[i:i+kernelH, j:j+kernelW] * kernel)
  return arr