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:
Ox =
−1 0 +1
−2 0 +2
−1 0 +1
⊗ I
Oy =
−1 −2 −1
0 0 0
+1 +2 +1
⊗ I
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:
O =
q
O2
x + O2
y
Given a convoltion matrix K (a kernel) of size n × n and a matrix M, the convolution M0 = K ⊗ M is
given by:
M0
x,y =
Xn
i=1
Xn
j=1
Ki,j × Mx+(i−d
n
2 e),y+(j−d
n
2 e)
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.
1You can ignore the division step described in the video, because our kernels sum to zero so the division is undefined (and
unnecessary).
