Two Dimensional Convolution Implementation in Python

Question

I am trying to implement a simple 2-D convolution function in Python using this formula: I wrote the following function:

def my_filter2D(X, H):

    # make sure both X and H are 2-D
    assert( X.ndim == 2)
    assert( H.ndim == 2)

    # get the horizontal and vertical size of X and H
    X_size_x = X.shape[1]
    X_size_y = X.shape[0]
    H_size_x = H.shape[1]
    H_size_y = H.shape[0]

    # calculate the horizontal and vertical size of Y (assume "full" convolution)
    Y_size_x = X_size_x + H_size_x - 1
    Y_size_y = X_size_y + H_size_y - 1

    # create an empty output array
    Y = np.zeros((Y_size_y,Y_size_x))


    # go over output locations
    for m in range(Y_size_y):
        for n in range(Y_size_x):

        # go over input locations
            for i in range(X_size_y):
                for j in range(X_size_x):
                     if (m-i >= 0) and (m-i < X_size_y ) and (n-j >= 0) and (n-j < X_size_x):
                             Y[m,n] = Y[m,n] + H[i,j]*X[m-i,n-j]
            # make sure kernel is within bounds

            # calculate the convolution sum

    return Y

However I am getting a boundary problem with the following example:

# test my 2-D convolution function

# 2-D input
X = np.array([[2, 1, 2, 3, 0],
              [1, 3, 2, 1, 1],
              [2, 3, 0, 1, 2],
              [0, 1, 3, 2, 1]])

# 2-D filter kernel
H = np.array([[2, 4, -2],
              [1, 2, -1]])

# call my function to calculate 2D convolution
Y = my_filter2D(X, H)

print("H: \n", H)
print("Y: \n", Y)

Error:

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-4-19d8f5a83f29> in <module>
     12 
     13 # call my function to calculate 2D convolution
---> 14 Y = my_filter2D(X, H)
     15 
     16 print("H: \n", H)

<ipython-input-3-3ed9b29455a3> in my_filter2D(X, H)
     35                 for j in range(X_size_x):
     36                      if (m-i >= 0) and (m-i < X_size_y ) and (n-j >= 0) and (n-j < X_size_x):
---> 37                              Y[m,n] = Y[m,n] + H[i,j]*X[m-i,n-j]
     38             # make sure kernel is within bounds
     39 

IndexError: index 3 is out of bounds for axis 1 with size 3

The result should have the same size as the input. The kernel center can be at any position for this example.

Answer 1

I ran your code and i saw that the mistake is here:

 for i in range(X_size_y):
            for j in range(X_size_x):

you should write

   for i in range(H_size_y):
               for j in range(H_size_x):

I wrote your code again:

def myfilter2D(X, H):
    # make sure both X and H are 2-D
    assert( X.ndim == 2)
    assert( H.ndim == 2)

   # get the horizontal and vertical size of X and H
   imageColumns = X.shape[1]
   imageRows = X.shape[0]
   kernelColumns = H.shape[1]
   kernelRows = H.shape[0]

   # calculate the horizontal and vertical size of Y (assume "full" convolution)
   newRows = imageRows + kernelRows - 1
   newColumns = imageColumns + kernelColumns - 1

   # create an empty output array
   Y = np.zeros((newRows,newColumns))


   # go over output locations
   for m in range(newRows):
       for n in range(newColumns):

    # go over input locations
        for i in range(kernelRows):
            for j in range(kernelColumns):
                 if (m-i >= 0) and (m-i < imageRows ) and (n-j >= 0) and (n-j < imageColumns):
                         Y[m,n] = Y[m,n] + H[i,j]*X[m-i,n-j]
        # make sure kernel is within bounds

        # calculate the convolution sum

return Y
kernel = np.array([[1, 0, 1], [0, 1, 0],[0,0,1]])

image=np.array([[25,100,75,49,130], [50, 80, 0,70,100],[5,10,20,30,0],  [60,50,12,24,32],[37,53,55,21,90],[140,17,0,23,22]])


myfilter2D(image,kernel)

With this change the convolution works right

Answer 2

You check the ranges for i and j depending on the input X size.

 for i in range(X_size_y):
       for j in range(X_size_x):

However you access the elements of the kernel with the same indices in H[i,j], thus, when i>H_size_y (same for j), you get the out of bounds error.