Description
One of the most important operations in image processing and computer vision is edge detection. A very simple and effective edge detector is the Sobel Filter. The Sobel Filter is a pair of 3 3 matrices which are convolved with the input image seperately then recombined. Specifically, the Sobel Filter is given by the pair of discrete convolutions:
-
3
10+1
-
-
-
-
-
-
Ox = 4
2
0
+2
5
I
1
0
+1
-
-
-
-
-
-
3
121
-
-
-
-
-
-
Oy = 4
0
0
0
5
I
+1
+2
+1
-
-
-
-
-
where I is the input image, Ox and Oy are the piecewise output images, and is the convolution operator (described below). The x and y components are recombined with:
q
O = Ox2 + Oy2
Given a convoltion matrix K (a kernel) of size n n and a matrix M, the convolution M0 = K M is given by:
-
-
-
-
-
n
n
M0
Xi
X
i;j
=
K
M
d
n
e
d
n
e
x;y
x+(i
);y+(j
)
=1 j=1
2
2
-
-
-
-
That may look like some scary linear algebra, but it’s actually very simple. Here’s some pseudocode:
for each row r in M
for each column c in M
accumulator = 0
for each row j in K
for each column i in K
accumulator = accumulator +
K[j][i] * M[r + (j – ceil(n/2))][c + (i – ceil(n/2))] M’[r][c] = accumulator
Positions in the matrix where the kernel only partially covers the matrix (e.g., the edges) have to be handled specially. For our purposes, we’ll ignore those cells and simply assign 0 (zero) to the output.
This YouTube video gives some visual examples of how convolution works1: https://www.youtube. com/watch?v=C_zFhWdM4ic
I have provided source code that implements image reading and writing (and shows example usage). Starting with that code, write a program that takes the name of a PGM image on the command line, reads the image, applies a Sobel filter, and write the edge-detected image to disc with the file name sobel.pgm. All input files with be greyscale PGM images of size 1024 1024.
PGM is a very, very simple image format. Tools that can display PGM images in UNIX and UNIX-like environments include xv and gimp. In Windows, IrfanView can do the job.
-
You can ignore the division step described in the video, because our kernels sum to zero so the division is undefined (and unnecessary).
