Convolution

Photogrammetry-1

So, I have just implemented a function that performs 3x3 convolution operation. A convolution is just a simple multiplication between 2 functions. In case of images, in which I am interested, one function takes the form of an image while the other function takes the form of a kernel. If we talk about the kernel, it is simply an array of values to be multiplied with an image step by step to generate the output image. What we do is simply take every pixel in the image, multiply the 3x3 kernel with the current pixel neighbors, in our case, N8 neighborhood, if there is no neighbor for a particular location, zero is considered for that location of the kernel, for example, in case of image boundaries. What we do is simply as follows:
1. Flip the provided kernel both row wise and column wise.
2. For each pixel location in the image, multiply the kernel values with the image values and sum them up to replace the current value of the pixel under consideration in the output image, one thing to remember is that we consider the pixel under consideration as the center pixel of the kernel.
3. If we reach an image boundary, meaning if the corresponding neighbor is not available, we simply assume that location to be zero, which is known as zero padding.
4. In essence, we only need to calculate multiplication values for the neighbors which are inside the image.

For a 3x3 kernel, we need to consider N8 neighborhood.

Example of an N8 Neighborhood

Let’s perform the convolution operation using a 4x4 array, acting as the input image while a 3x3 array, acting as the kernel.

Input Image and the Kernel

First of all, we need to flip the actual kernel both row wise and column wise.

Flipping the kernel row wise and column wise

Now, let us say that we want to find the new value at location (2,1) of the actual input after convolution, remember, the pixel under consideration will be at the center of the kernel while multiplying. The pixel at location (2,1) has a value of 0, the entire row is 1,0,0,2, since we are considering a 3x3 kernel so we will consider only 1,0,0, the row above will be 0,1,3 while the row below will be 0,0,0 as it exceeds the boundary of the image. In this way our array of 3x3 to be multiplied with the kernel will be completed.

The Multiplication Process

So, after the multiplication and summation, the new value we get is 35, which means that we will replace the value 0 with 35 in the output image at the location (2,1). Below is the code of a function that performs 3x3 convolution:

def imageConv(f,w):

    f_w = np.flip(w,0) # row wise flipped kernel
    f_w = np.flip(f_w,1) # column wise flipped kernel

    output_image = np.zeros(np.shape(f)) # initializa the output image

    for row in range(np.shape(f)[0]): # loop through each row
        for col in range(np.shape(f)[1]): # loop through each column
            sum = 0 # store sum from the neighbors for current pixel location
            sum += (f[row,col]*f_w[1,1]) # perform multiplication and add to sum using the center pixel of the kernel
            if row-1 >= 0: # check the neighbor above
                sum += (f[row-1,col]*f_w[0,1]) # perform multiplication and add to sum
            if row+1 < np.shape(f)[0]: # check the neighbor below
                sum += (f[row+1,col]*f_w[2,1]) # perform multiplication and add to sum
            if col-1 >= 0: # check the left neighbor
                sum += (f[row,col-1]*f_w[1,0]) # perform multiplication and add to sum
            if col+1 < np.shape(f)[1]: # check right neighbor
                sum += (f[row,col+1]*f_w[1,2]) # perform multiplication and add to sum
            if row-1 >= 0 and col-1 >= 0: # check top left diagonal neighbor
                sum += (f[row-1,col-1]*f_w[0,0]) # perform multiplication and add to sum
            if row-1 >= 0 and col+1 < np.shape(f)[1]: # check top right diagonal neighbor
                sum += (f[row-1,col+1]*f_w[0,2]) # perform multiplication and add to sum
            if row+1 < np.shape(f)[0] and col-1 >= 0: # check bottom left diagonal neighbor
                sum += (f[row+1,col-1]*f_w[2,0]) # perform multiplication and add to sum
            if row+1 < np.shape(f)[0] and col+1 < np.shape(f)[1]: # check bottom right diagonal neighbor
                sum += (f[row+1,col+1]*f_w[2,2]) # perform multiplication and add to sum

            output_image[row,col] = sum

    return output_image

Now let’s consider an application of the convolution operation defined above. A gradient image represents change in pixel intensity. A horizontal gradient image computes change in pixel intensity along the horizontal axis (x-direction) while a vertical gradient image computes change in pixel intensity along the vertical axis (y-direction). The vertical gradient highlights horizontal lines and edges, and vice versa. Absolute gradient combines both horizontal and vertical gradients.

Get Talha Hanif Butt’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

If we want to compute the absolute gradient of an image, we first need to compute horizontal and vertical gradients, and then combine them. The following code computes the absolute gradient of an image using the convolution function defined above:

# computing horizontal gradient
k = np.array([[-1,0,1],[-2,0,2],[-1,0,1]])
img_gx = imageConv(img,k)

# computing vertical gradient
k = np.array([[-1,-2,-1],[0,0,0],[1,2,1]])
img_gy = imageConv(img,k)

# computing the absolute gradient
G = ((img_gx)**2 + (img_gy)**2)**(1/2)

I have used Adobe-240 dataset for this implementation. This video helped me understand the algorithm. That’s it for now. See you later.