4. SEGMENTATION AND EDGE DETECTION
4.1 Region Operations
Discovering regions can be a very simple exercise, as illustrated in 4.1.1. However, more
often than not, regions are required that cover a substantial area of the scene rather than a
small group of pixels.
4.1.1 Crude edge detection
USE. To reconsider an image as a set of regions.
OPERATION. There is no operation involved here. The regions are simply identified as
containing pixels of the same gray level, the boundaries of the regions (contours) are at the
cracks between the pixels rather than at pixel positions.
Such as a region detection may give far for many regions to be useful (unless the number
of gray levels is relatively small). So a simple approach is to group pixels into ranges of
near values (quantizing or bunching). The ranges can be considering the image histogram
in order to identify good bunching for region purposes results in a merging of regions
based overall gray-level statistics rather than on gray levels of pixels that are
geographically near one another.
4.1.2 Region merging
It is often useful to do the rough gray-level split and then to perform some techniques on
the cracks between the regions – not to enhance edges but to identify when whole regions
are worth combining – thus reducing the number of regions from the crude region
detection above.
USE. Reduce number of regions, combining fragmented regions, determining which
regions are really part of the same area.
OPERATION. Let s be crack difference, i.e. the absolute difference in gray levels between
two adjacent (above, below, left, right) pixels. Then give the threshold value T, we can
identify, for each crack



<
=

valleys between the peaks for possible threshold values. Some peaks will be more
substantial than others: find splits between the "best" peaks first.
Regions are identified as containing gray-levels between the thresholds. With color
images, there are three histograms to choose from. The algorithm halts when no peak is
significant.
LIMITATION. This technique relies on the overall histogram giving good guidance as to
sensible regions. If the image is a chessboard, then the region splitting works nicely. If the
image is of 16 chessboard well spaced apart on a white background sheet, then instead of
identifying 17 regions, one for each chessboard and one for the background, it identifies
16 x 32 black squares, which is probably not what we wanted.
4.2 Basic Edge Detection
The edges of an image hold much information in that image. The edges tell where objects
are, their shape and size, and something about their texture. An edge is where the intensity
of an image moves from a low value to a high value or vice versa.
There are numerous applications for edge detection, which is often used for various
special effects. Digital artists use it to create dazzling image outlines. The output of an
edge detector can be added back to an original image to enhance the edges.
Edge detection is often the first step in image segmentation. Image segmentation, a field of
image analysis, is used to group pixels into regions to determine an image's composition.
A common example of image segmentation is the "magic wand" tool in photo editing
software. This tool allows the user to select a pixel in an image. The software then draws a
border around the pixels of similar value. The user may select a pixel in a sky region and
the magic wand would draw a border around the complete sky region in the image. The
user may then edit the color of the sky without worrying about altering the color of the
mountains or whatever else may be in the image.
Edge detection is also used in image registration. Image registration aligns two images that
may have been acquired at separate times or from different sensors.
roof edge line edge step edge ramp edge
Figure 4.1 Different edge profiles.
There is an infinite number of edge orientations, widths and shapes (Figure 4.1). Some


homogenety operator image
11
11
11
11
11
12
16
16
11
13
11
15
11
new pixel = maximum{ 11−11 ,  13−12 ,  15−16 ,  11−16 } = 5
Figure 4.3 How the difference operator works.

4.2.1 First order derivative for edge detection
If we are looking for any horizontal edges it would seem sensible to calculate the
difference between one pixel value and the next pixel value, either up or down from the
first (called the crack difference), i.e. assuming top left origin
H
c
= y_difference(x, y) = value(x, y) – value(x, y+1)
In effect this is equivalent to convolving the image with a 2 x 1 template
1
1
−
Likewise

c
and

H
r
)y,x(H)y,x(H)y,x(H
2
c
2
r
+=
Sometimes for computational simplicity, the magnitude is computed as
)y,x(H)y,x(H)y,x(H
cr
+=
The edge orientation can be found by
( )
( )
y,xH
y,xH
tan
r
c
1−
=θ
In real image, the lines are rarely so well defined, more often the change between regions
is gradual and noisy.
The following image represents a typical read edge. A large template is needed to average
at the gradient over a number of pixels, rather than looking at two only
3444332100

414121410464
Threshold at 12
0000110
00000100
00111002
11110000
4.2.3 Other first order operation
The Roberts operator has a smaller effective area than the other mask, making it more
susceptible to noise.










−
=

















−−−
=
101
101
101
H
111
000
111
H
cr
The Frei-Chen mask










−−−

difficult to locate the centers of the edges. It becomes necessary to employ a process called
thinning to reduce the edge width to one pixel. Second order derivative edge detectors
provide better edge localization.
Example. In an image such as
987654321
987654321
987654321
987654321
987654321
The basic Sobel vertical edge operator (as described above) will yield a value right across
the image. For example if
101
202
101
−
−
−
is used then the results is
8888888
8888888
8888888
Implementing the same template on this "all eight image" would yield
00000000
This is not unlike the differentiation operator to a straight line, e.g. if y = 3x-2.
2
2
dx
yd
and3
dx

The Laplacian set of operators is widely used. Since it effectively removes the general
gradient of lighting or coloring from an image it only discovers and enhances much more
discrete changes than, for example, the Sobel operator. It does not produce any
information on direction which is seen as a function of gradual change. It enhances noise,
though larger Laplacian operators and similar families of operators tend to ignore noise.
Determining zero crossings
The method of determining zero crossings with some desired threshold is to pass a 3 x 3
window across the image determining the maximum and minimum values within that
window. If the difference between the maximum and minimum value exceed the
predetermined threshhold, an edge is present. Notice the larger number of edges with the
smaller threshold. Also notice that the width of all the edges are one pixel wide.
A second order derivative edge detector that is less susceptible to noise is the Laplacian of
Gaussian (LoG). The LoG edge detector performs Gaussian smoothing before application
of the Laplacian. Both operations can be performed by convolving with a mask of the
form
2
22
2
)y(x
2
22
4
e
2
yx
1
1
y)LoG(x,
σ
+−

. The width of the positive center lobe is twice that.
To have a convolution mask that contains the nonzero values of the LoG function requires
a width three times the width of the positive center lobe (8.49
σ
).
Edge detection based on the Gaussian smoothing function reduces the noise in an image.
That will reduce the number of false edges detected and also detects wider edges.
Most edge detector masks are seldom greater than 7 x 7. Due to the shape of the LoG
operator, it requires much larger mask sizes. The initial work in developing the LoG
operator was done with a mask size of 35 x 35.
Because of the large computation requirements of the LoG operator, the Difference of
Gaussians (DoG) operator can be used as an approximation to the LoG. The DoG can be
shown as

2
2
2
yx
2
1
2
yx
2
e
2
e
y)DoG(x,
2
2
22

subtracting two Gaussian masks with different a values. The ratio σ
1
/σ
2
= 1.6 results in a
good approximation of the LoG. Figure 4.5 compares a LoG function (σ = 12.35) with a
DoG function (σ
1
= 10, σ
2
= 16).
Figure 4.5 LoG vs. DoG functions.
One advantage of the DoG is the ability to specify the width of edges to detect by varying
the values of σ
1
and σ
2
. Here are a couple of sample masks. The 9 x 9 mask will detect
wider edges than the 7x7 mask.
For 7x7 mask, try
0011100
0233320
1355531
13516531
1355531
0233320
0011100
−−−
−−−−−
−−−−

Figure 4.6 (a) original image; (b) red channel; (c) green channel; (d) blue channel; (e) red
channel edge; (e) green channel edge; (e) blue channel edge.
(This picture is taken from Figure 3.24, Chapter 3, [2])
Edge detection can also be done on each color component and then the components can be
summed to create a gray scale edge map. Also, the color components can be vector
summed to create the gray scale edge map.
2
blue
2
green
2
red
GGGy)G(x, ++=
It has been shown that the large majority of edges found in the color elements of an image
are also found in the intensity component. This would imply that edge detection done on
the intensity component alone would suffice. There is the case of low contrast images
where edges are not detected in the luminance component but found in the chromatic
components. The best color edge detector again depends on the application.
4.4 Pyramid Edge Detection
Often it happens that the significant edges in an image are well spaced apart from each
other and relatively easy to identify. However, there may be a number of other strong
edges in the image that are not significant (from the user’s point of view) because they are
short or unconnected. The problem is how to enhance the substantial ones but ignore the
other shorter ones.
USE. To enhance substantial (strong and long) edges but to ignore the weak or short
edges.
THEORY. The image is cut down to the quarter of the area by halving the length of the
sides (both horizontally and vertically). Each pixel in the new quarter-size image is an
average of the four corresponding pixels in the full size image. This is repeated until an
image is created where the substantial edges are still visible but the other edges have been

largest image. Continue to do this following the best edges down through the pyramid of
images until the main edges in the original image have been discovered.
4.5 Crack Edge Relaxation
Crack edge relaxation is also a popular and effective method of edge enhancement. This
involves allocating a likelihood value to all of the cracks between pixels as to whether
they lie either side of an edge
6 8 7
7 7 4
3 2 3
if the gray-level range is 0÷9, then the crack probabilities in ninths are:
6
2
8
1
7
1
1
3
7
0
7
3
4
4
5
1
3
1
2
1

ab(m-c) Likelihood value for 2 "significant" cracks
abc Likelihood value for 3 "significant" cracks

Choose the most likely number of cracks – i.e. the one with the highest likelihood value.
Do this for both ends, allocating a class such as (3, 2) to the crack being considered.
Increment the crack value if the crack is of type (1,1), (1,2), (2,1), (1,3), (3,1). Intuitively
these will probably by the parts of an edge. Decrement the crack value if the crack is of
type (0,0), (0,2), (0,1), (2,0), (3,0). Do nothing for the others. Repeat this enhancement
process until adequate edge detection has been performed.
Create an edge detected image by allocating to each pixel a value dependent on the value
of the crack above it and the crack to the right of it. This could be a simple sum or the
maximum of the two or a binary value from some combined threshold.
This is edge enhancement, using as initial estimate of the edges the cracks between the
pixels. It then removes the unlikely ones, enhancing the more likely ones.
4.6 Edge Following
If it is know that an object in an image has a discrete edge all around it, then possible once
a position on the edge has been found, it is to follow the code around the object and back
to the beginning. Edge following is a very useful operation, particularly as a stepping
stone to making decision by discovering region positions in images. This is effectively the
dual of segmentation by region detection.
There are a number edge following techniques. There are many levels of sophistication
associated with edge following and the reader may well see how sophistication can be
added to the simple technique described.
Simple edge following
USE. Knowing that a pixel is on an edge, the edge will be followed so that an object is
outlined. This is useful prior to calculating the area of a particular shape. It is also useful if
the enclosed region is made up of many regions that the user whishes to combine.
OPERATION. It is assumed that a position on the edge of a region has been identified,
call it (x,y).
No flag this position as "used" (so that it is not used again) and evaluate all the 3 x 3 (or