Page 66 -

40 Chapter 2 ■ Edge-Detection Techniques

The algorithm is not difficult to implement, although it is more difficult than
the methods seen so far. A convolution in two dimensions can be expressed as:

I ∗ G(i, j) = I(n, m)G(i − n, j − m) (EQ 2.13)
n m
The function G being convolved with the image is a two-dimensional
Gaussian, which is:
2
2
−(x + y )
2
G σ (x, y) = σ e σ 2 (EQ 2.14)
To perform the convolution on a digital image, the Gaussian must be
sampled to create a small two-dimensional image. This is convolved with the
image, after which the Laplacian operator can be applied. This is:
∂ 2 ∂ 2
2
∇ = + (EQ 2.15)
∂x 2 ∂y 2
and could be computed using differences. However, since order does not
matter in this case, we could compute the Laplacian of the Gaussian (LoG)
analytically and sample that function, creating a convolution mask that can be
applied to the image to yield the same result. The LoG is:

r − 2σ −r
2 2
2
∇ G σ = e 2σ 2 (EQ 2.16)
σ 4

2
2
where r = x + y . This latter approach is the one taken in the C code
implementing this operator, which appears at the end of this chapter.
This program first creates a two-dimensional, sampled version of the LoG
(called lgau in the function marr) and convolves this in the obvious way with
the input image (function convolution). Then the zero crossings are identified
and pixels at those positions are marked.
A zero crossing at a pixel P implies that the values of the two opposing
neighboring pixels in some direction have different signs. For example, if the
edge through P is vertical then the pixel to the left of P will have a different
sign than the one to the right of P. There are four cases to test: up/down,
left/right, and the two diagonals. This test is performed for each pixel in the
LoG by the function zero_cross.
In order to ensure that a variety of scales are used, the program uses
two different Gaussians, and selects the pixels that have zero crossings in both
scales as output edge pixels. More than two Gaussians could be used, of course.
The program marr.c reads the image input file name from the standard input,
and also accepts a standard deviation value s as a parameter. It then uses both