## CPEG 585 β Assignment #3 Derivative and Gaussian based Convolution Filters

In the previous assignment, we examined simple convolution filters that can be designed to do

low pass, high pass filtering. The high pass filtered image can be combined with the original

image to accomplish sharpening. We also derived first derivative based filters using the Taylor

series expansion around a given pixel to approximate the first derivates in the X and Y

directions (Gx and Gy). Combining the Gx and Gy led to the Sobel filter. In this assignment, first

we will take a look at the second derivative approximation around a given pixel. Again, we will

use the Taylor series to approximate the second derivative of the image in terms of the values

of the neighboring pixels. The second derivative based filter is referred to as the Laplacian filter,

and often results in better change or edge detection.

Development of kernel for the Laplacian Filter:

Taylor series expansion in two dimensions up to the second derivative is given by:

π(π₯ Β± βπ₯, π¦ Β± βπ¦) = π(π₯, π¦) Β± βπ₯

ππ

ππ₯

Β± βπ¦

ππ

ππ¦

+ 0.5(βπ₯)

2 π

2π

ππ₯

2+0.5(βπ¦)

2 π

2π

ππ¦2

Where π(π₯, π¦) is the value of a pixel and π₯ πππ π¦ are the horizontal and vertical

coordinates of the pixel. π(π₯ Β± βπ₯, π¦ Β± βπ¦) is some pixel in the local neighborhood of the

center pixel π(π₯, π¦) and (βπ₯, βπ¦) are the integer offsets of the neighborhood pixel from the

center pixel. In a 3 Γ 3 neighborhood, the offsets are Β±1 as shown below.

(Β±βπ₯, Β±βπ¦) = [

(β1, +1) (0, +1) (+1, +1)

(β1, 0) (0, 0) (+1, 0)

(β1, β1) (0, 1) (+1, β1)

]

In a 5 Γ 5 neighborhood, the closest pixel will have offsets of Β±1 and the outer pixels in the

neighborhood will have offsets of Β±2.

The terms ππ

ππ₯

and ππ

ππ¦

are the π₯ and π¦ are the first derivative filtered images and the terms

π

2π

ππ₯

2

and π

2π

ππ¦2

are the π₯ πππ π¦ second derivative filtered images.

The definitions for the Gradient and Laplacian filtered images are as follows:

Gradient (Magnitude) Filtered Imageβ(

ππ

ππ₯)

2

+ (

ππ

ππ¦)

2

Laplacian Filtered Image =

π

2π

ππ₯2 +

π

2π

ππ¦2

2

To come up with the Laplacian kernel, we can take a look at a 3×3 pixel window and do the

Taylor series expansion for each of the pixel left, bottom, right and top (shown in bold below)

with respect to the center pixel, we will come up with the following four equations.

(Β±βπ₯, Β±βπ¦) = [

(β1, +1) (π, +π) (+1, +1)

(βπ, π) (0, 0) (+π, π)

(β1, β1) (π, βπ) (+1, β1)

]

π(π₯ β 1, π¦) = π(π₯, π¦) β

ππ

ππ₯

+ 0.5

π

2π

ππ₯

2

(1)

π(π₯, π¦ β 1) = π(π₯, π¦) β

ππ

ππ¦

+ 0.5

π

2π

ππ¦2

(2)

π(π₯ + 1, π¦) = π(π₯, π¦) +

ππ

ππ₯

+ 0.5

π

2π

ππ₯

2

(3)

π(π₯, π¦ + 1) = π(π₯, π¦) +

ππ

ππ¦

+ 0.5

π

2π

ππ¦2

(4)

If we add these four equations, we notice that the first derivatives cancel out and we are left

with

Sum of Four neighbors = 4π(π₯, π¦) +

π

2π

ππ₯

2 +

π

2π

ππ¦2

Or:

Laplacian Filtered Image =π

2π

ππ₯

2 +

π

2π

ππ¦2 = πππ’π ππππβππππ β 4π(π₯, π¦)

Which results in a kernel of

Laplacian Filter= π

2

ππ₯

2 +

π

2

ππ¦2 = [

0 1 0

1 β4 1

0 1 0

]

4-neighbor Laplacian Filter = π

2

ππ₯

2 +

π

2

ππ¦2 = [

0 β1 0

β1 4 β1

0 β1 0

]

Similarly an eight neighbor Laplacian filter can be developed to yield a kernel of:

8-neighbor Laplacian Filter = π

2

ππ₯

2 +

π

2

ππ¦2 = [

β1 β1 β1

β1 8 β1

β1 β1 β1

]

Problem #1: Derive the 8-neighbor Laplacian filter kernel. Show all the equations.

3

Problem #2: Write a Python function that returns the 2-d Gaussian kernel with specified standard

deviation and kernel size. Then test the Gaussian kernel convolution on an image with different values

of standard deviation.

Partial Solution: 2-d Gaussian is defined as:

The 2-d Gaussian function appears as:

Note that a Gaussian kernel behaves as a low pass filter. This is because, the Fourier transform of a

Gaussian function is a Gaussian itself with the standard deviation getting inverted in the frequency

domain as shown for a 1-d signal below.

Thus if you choose a high standard deviation in the pixel domain, it will suppress more high frequencies.

You will verify this by writing the Python program to determine the Gaussian kernel and then doing the

convolution of it with an image by choosing different values of standard deviation.

4

Create a Python application called AdvancedConvolutionFilters. Add a python file to the project called

Utils with the following code in it.

import numpy as np

import math

def compute_gaussian_kernel(kernel_size, sigma):

kernel = np.zeros((kernel_size,kernel_size),dtype=float)

for x in range(-kernel_size//2+1,kernel_size//2+1):

for y in range(-kernel_size//2+1,kernel_size//2+1):

kernel[x+kernel_size//2,y+kernel_size//2] =

(1/(2*math.pi*sigma**2))*math.exp(-((x**2+y**2)/(2*sigma**2)))

kernel = kernel/np.min(kernel)

return kernel, np.sum(kernel)

Note that the sum of the values in the kernel should equal 1 (or 0) so that it does not affect the scale

(contrast) of the image. The sum of the values of the kernel is returned by the above function so that we

can divide each kernel value by it to accomplish sum of kernel values being 1.

Add a file called MyConvolution.py with the following code in it:

import numpy as np

class MyConvolution(object):

def convolve(self, img: np.array, kernel: np.array) -> np.array:

# kernel is assumed to be square

output_size = (img.shape[0]-kernel.shape[0]+1, img.shape[1]-

kernel.shape[0]+1)

output_img = np.zeros((output_size[0],

output_size[1],img.shape[2]),dtype=img.dtype)

kernel_size = kernel.shape[0] # kernel size

for i in range(output_size[0]):

for j in range(output_size[1]):

for k in range(img.shape[2]): # RGB

mat = img[i:i+kernel_size, j:j+kernel_size,k] # values at

current kernel location

mat = mat.reshape((kernel_size,kernel_size))

# do element-wise multiplication and add the result

output_img[i, j, k] = np.clip(np.sum(np.multiply(mat,

kernel)),0,255)

return output_img

Type the following code in Advanced ConvolutionFilters.py to test the convolution with the Gaussian

kernel.