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.

Powered by WordPress