## Description

## Image Processing

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).