2.4.3 DETECTING AN
EDGE.
Taking an edge to be a change in intensity taking place over a
number of pixels, edge detection algorithms generally compute a derivative of
this intensity change.
COMPUTING THE 1st DERIVATIVE
Many edge-detection operators are based upon the
1st derivative of the intensity - this gives us the intensity
gradient of the original data. Using this information we can search an image
for peaks in the intensity gradient.
For higher performance image processing, the 1st derivative
can therefore be calculated (in 1D) by convolving the original data with a
mask:
The magnitude of the first derivative can be used to detect
the presence of an edge at a point in an image.
COMPUTING THE 2nd DERIVATIVE
Some other edge-detection operators are based upon the 2nd
derivative of the intensity. This is essentially the rate of change in
intensity gradient.
Here, we can alternatively search for zero-crossings in the
second derivative of the image gradient.
Again most algorithms use a convolution mask to quickly process
the image data:
The signs of the 2nd derivative can be used to
determine whether an edge pixel lies on the dark or light side of an
edge.[17]
THRESHOLDING
Once we have calculated our derivative, the next stage is to
apply a threshold, to determine where the result suggests an edge to be
present. It is useful to be able to separate out the regions of the image
corresponding to the objects in which we are interested, from the region of the
image that correspond to background. Threshold often provides n easy and
convenient way to perform this segmentation.
Thresholding is the simplest method of image segmentation on
the basis of deferent intensities in the foreground and background regions of
an image. Individual pixels in image are marked as «object» if their
value is greater than some threshold value.(assuming an object to be bright
than the background) and as» background «pixels if their values is
less than threshold value. The key parameter in thresholding is the choice of a
threshold.
Several different methods for choosing a threshold exist. But
a common used compromiser method is thresholding with hysteresis. This method
uses multiple thresholds to find edges. We begin by using the upper threshold
to fid the start point. Once we have a start point, we trace the edge's path
through the image pixel by pixel, marking an edge whenever we are above the
lower threshold. We stop marking our edge only when the value falls below our
low threshold.
2.4.4 EDGE DETECTION
ALGORITHMS.
An edge, by definition, is that drastic change in value from
one spot to the next either in an image or in one's own eyes. In the digital
world, an edge is a set of connected pixels that lie on the boundary between
two regions. Ideally, a digital edge would have one pixel colored a certain
value and one of its neighboring pixels colored noticeably different. Since the
contrast between the pixels is drastic, we label it an edge. Unfortunately,
when dealing with digital pictures, most edges are blurred. This leads to edges
having a gradual change of pixels levels from one object to the next thus
causing the edge to be less defined and harder to distinguish. In this
instance, one would have to devise an intuitive way to distinguish gray level
transitions.
Edge detection is the process of determining where the
boundaries of objects fall within an image. There are several algorithms that
exist to date that are able detect edges. Roberts Cross was the first technique
used and is thus the fasted and simplest to implement. Lastly, there is the
Canny edge detection algorithm. This uses several steps to detect edges in an
image. However, this algorithm can be slow at times due to its higher degree of
complexity.
1. ROBERTS CROSS EDGE DETECTION
The Roberts Cross algorithm performs a two dimensional spatial
gradient convolution on the image. The main idea is to bring out the horizontal
and vertical edges individually and then to put them together for the resulting
edge detection.
We have two typical Roberts Cross kernels .
|
+100-1
|
0+1-10
|
Table 2.4.1: shows the two Roberts Cross
kernels.
The two Roberts Cross kernels, shown above in Figure 1, are
designed with the intention of bringing out the diagonal edges within the
image. The Gx image will enunciate diagonals that run from the top-left to the
bottom-right where as the Gy image will bring out edges that run top-right to
bottom-left. The two individual images Gx and Gy are combined using the
approximation equation
|G| = |Gx| + |Gy|.
Roberts Cross is not quite as effective as the Sobel
technique. It does bring out edges, but when compared the same image only using
the Sobel algorithm, the amount of edges detected is poor. The Sobel approach
seems to work the best.
In general, kernels are designed so that it consists of an odd
number of rows and columns. This helps to define a distinct center in each
kernel. Sampling pixels on each side of the center pixel leads to a better
convolution image. This yields a better edge detection image produced in the
outcome. The Sobel algorithm takes this account into effect when selecting its
kernels.
2. SOBEL EDGE DETECTION
Overview of sobel edge detection.
Standard Sobel operators, for a 3×3 neighborhood, each
simple central gradient
estimate is vector sum of a pair of orthogonal vectors . Each
orthogonal vector is a directional derivative estimate multiplied by a unit
vector specifying the derivative's direction. The vector sum of these simple
gradient estimates amounts to a vector sum of the 8 directional derivative
vectors.
Sobel which is a popular edge detection method is considered
in this work. There exists a function, edge.m which is in the image toolbox. In
the edge function, the Sobel method uses the derivative approximation to find
edges. Therefore, it returns edges at those points where the gradient of the
considered image is maximum. The horizontal and vertical gradient matrices
whose dimensions are 3×3 for the Sobel method has been generally used in
the edge detection operations. In this work, a function is developed to find
edges using the matrices whose dimensions are 5×5 in matlab.
Edge detection function
Each direction of Sobel masks is applied to an image, and then
two new images are created. One image shows the vertical response and the other
shows the horizontal response. Two images combined into a single image. The
purpose is to determine the existence and location of edges in a picture. This
two image combination is explained that the square of created masks pixel
estimate coincidence each other as coordinate are summed. Thus new image on
which edge pixels are located obtained the value which is the squared of the
above summation. The value of threshold in this above process is used to detect
edge pixels.
An algorithm is developed to find edges using the new matrices
and then, a matlab function, which is called as Sobel 5x5.m, is implemented in
matlab. This matlab function requires a grayscale intensity image,
two-dimensional array. The result which is returned by this function is the
final image in which the edge pixels are denoted by white color.
The sobel Edge detection algorithm uses the following two
kernels.
|
+1+2+1000-1-2-1
|
-10+1-20+2-10+1
|
Table 2.4.2: shows the sobel kernels.
The Sobel kernels, as shown in the above figure, are larger
than its predecessor, the Roberts Cross, is. This causes the processes to be
less susceptible to noise.
As one can see, there are only really two pixels of concern
with the Roberts Cross algorithm thus noise can be a rather large issue. The
Sobel algorithm deals with six pixels and in doing so takes a better average of
the neighboring pixels. This along with slight blurring can eliminate most
noise found within normal images.
3. CANNY EDGE DETECTION
This is another method of detecting edge.
First the image is run through a Gaussian blur to help get
ride of a majority of the noise. Second, an edge detection algorithm is applied
such as the Roberts Cross or Sobel techniques. From there the angle and
magnitude can be obtained and used to determine which portions of the edges
should be suppressed and which should be brought out. Lastly, there are two
threshold cutoff points. Any value in the image below the first threshold is
dropped to zero. Any value above the second threshold is raised to one. For any
pixels whose values fall within the two thresholds, their values are set to
zero or one, based on their neighboring pixels and their angle. The Canny
algorithm first requires that the image be smoothed with a Gaussian mask, which
cuts down significantly on the noise within the image. Then the image is run
through the Sobel algorithm, and as discussed before, this process is hardly
affected by noise. Lastly, the pixel values are chosen base on the angle of the
magnitude of that pixel and its neighboring pixels. When using the canny edge
detector there are two threshold levels. The first threshold is used to set all
values in the image that fall below it to be set to zero. The second threshold
level is used to set all values in the image that fall above it to be set to
one. The values in the image that lay within the two threshold values are set
to either zero or one based on their angle as specified by that algorithm.
Thus, the image created is a binary image. Ideally, the lower threshold should
be set relatively low so that a majority of the pixels are valued based on
their angles. Then the upper threshold is set to a high value there tends to be
a spurring effect that occurs on edges that branch off in a 'Y' shape.
Unfortunately, when dealing with clouds or fog, this can be quite frequent and,
as a result, there can be many spurs appearing in the result. Thus the value of
the high threshold should not be set too had so it can, in a sense, prune the
spurs away some.
Canny, which should be the best, might not be implemented
correctly and therefore, does not work as it should. Currently it is able to
detect edges that are well defined, but for minor edges, the best results are
created when using the Sobel option. If the Canny detector worked properly it
would be superior to both Sobel and Roberts Cross, the only drawback is that it
takes longer to compute.[17]
4. PREWITT EDGE DETECTION.
The Prewitt edge detection is an alternative approach to the
differential gradient edge detection. The operation usually output two images,
one estimating the local edge gradient magnitude and other ones, estimating the
orientation of the image.
The Prewitt operator is similarly to the sobel and some other
operators approximating the first derivative, operators approximating the first
derivatives are also called Compass operator because of the ability to
determine gradient direction.
The gradient is estimated in eight (for 3X3 convolution mask)
possible direction and convolution result of greatest magnitude indicate the
gradient direction. Larger mask are possible.
The Prewitt Edge detection algorithm uses the following two masks
(hx and hy).
|
111000-1-1-1
|
-101-101-101
|
Table 2.4.3: shows Prewitt's mask.
Prewitt edge detection produces an image where higher
grey-level values indicate the presence of an edge between two objects. The
Prewitt edge detector mask is one of the oldest and best understand methods of
detecting edges in images. Basically there are two masks, one for detecting
image derivative in X and other one for detecting image derivative in Y.
In practice, one usually thresholds the result of Prewitt edge
detection in other to produce a discrete set of edge.
|