Let us represent an image by an array A, in which
each element of the array corresponds to the gray level of an image. If
the gray levels are in pixel counts, then the numbers might range from
0 to 255 for an eight-bit per pixel image.
The gradient is the change in gray level with direction.
This can be calculated by taking the difference in value of neighboring
pixels. Let us construct a new array B that contains the values
of the gradient from A.
The horizontal gradient is formed by taking the differences
between column values.
This can be represented by a filter array as shown below:
A problem with this filter is that the location of the
gradient in the array B is shifted somewhat to the left. With an
even number of pixels in the computation it is impossible to locate the
result in the center of the cells used to produce it. It is therefore most
common to use an odd number of cells. This can be accomplished by doing
the calculation over cells that are separated by step.
This can be represented by the array shown below:
Note that the result pixel is centered between the left
and right pixels used to calculate the gradient, so there is no shift in
the location of the gradient result.
An example of a horizontal gradient calculation can be
demonstrated on the image shown in Figure 1, which
has strong vertical and horizontal structures. The result is shown in Figure
2..
Horizontal edges would be detected by calculating the
vertical gradient. The equation for the separated vertical difference is
For an image in which the row coordinates are counted from the bottom edge upward, the corresponding filter array is
An example of a vertical gradient calculation is shown in Figure 4.
Vertical edges can be detected by using a horizontal gradient
operator followed by a threshold operation to detect the extreme values
of the gradient. The gradient produces a doublet of extremes, positive-negative
or negative-positive, depending on the direction of the transition.
We will investigate the detection of both vertical and
horizontal edges using the image of the detail of a building shown in Figure
1. Detail of a building at 256 gray levels. This image has strong horizontal
and vertical edges, and is therefore useful for the illustration of the
method.
Figure 2. Image produced by the horizontal gradient calculation.
The horizontal gradient was calculated by taking differences
in the image values between columns. Note that the column before and the
column after k was used. Use of an odd number of pixels in a gradient
calculation prevents a shift in location.
If A has gray values in the range 0 to 255, for example,
then B may have values in the range -255 to 255. The values of B were renormalized
to the range 0 to 255 by shifting and scaling. This can be done by the
replacement
where the brackets [] indicate rounding to the nearest
integer.
The edges shown in Figure 3. Negative
edges found by horizontal gradient detection with b=120. were detected
by applying a threshold operation to the results of the horizontal gradient
calculation. The strongest negative edge transitions were then detected
with a threshold operation, in which the pixels of B that were less than
a threshold b were detected .Figure 3. Negative
edges found by horizontal gradient detection with b=120. shows those pixels
for b=120.
Figure 3. Negative
edges found by horizontal gradient detection with b=120.
The edges shown in Figure 3. Negative edges found by horizontal gradient detection with b=120. were detected by applying a threshold operation to the results of the horizontal gradient calculation. The strongest negative edge transitions were then detected with a threshold operation, in which the pixels of B that were less than a threshold b were detected. Figure 3. Negative edges found by horizontal gradient detection with b=120. shows those pixels for b=120.
Horizontal edges produce a vertical gradient in the image,
and can be enhanced with a vertical gradient detector. A vertical gradient
filter can be defined by
The gradient values were shifted and normalized by
When the gradient is calculated on the building image,
the result is as shown in Figure 4 Edge produced
by vertical gradient calculation. The origin of the image is at the lower
left corner, so that higher numbered rows are higher in the figure. An
edge doublet that is formed by the gradient calculation in going from a
darker area to a lighter area will be bright below dark. We wee this in
the rounded "eyebrows" in the stone work.
The edges shown in Figure 5 Positive
edges found by vertical gradient detection with a=180. were detected by
applying a threshold operation to the results of the vertical gradient
calculation. The strongest positive edge transitions were then detected
with a threshold operation, in which the pixels of B that were greater
than a threshold a were detected. Figure 5 Positive
edges found by vertical gradient detection with a=180. shows those pixels
for a=180.
Figure 5 Positive edges found by vertical gradient detection with a=180.
The edges shown in Figure 6 Negative
edges found by vertical gradient detection with b=80. were detected by
applying a threshold operation to the results of the vertical gradient
calculation. The strongest negative edge transitions were then detected
with a threshold operation, in which the pixels of B that were less than
a threshold b were detected. Figure 6 Negative edges found by vertical
gradient detection with b=80. shows those pixels for b=80.
Figure 6 Negative edges found by vertical gradient detection with b=80.
A diagonal edge is neither horizontal nor vertical. It
will cause a partial response to both the horizontal and vertical edge
detectors. An image that is a combination of the two processes can be created
by combining the results of each gradient calculation. The image that is
so created could be called a gradient image, combining the horizontal
gradient and vertical gradient images such as those shown in
Figure 2 and Figure 4.
Figure 7. Image formed by combined horizontal and vertical
gradient detection
The edges detected from the combined gradient image with
a threshold set at a=145 is shown in Figure 8.
Figure 8. Edges detected in combined vertical and horizontal
gradient image with threshold a=145.
Figure 7 was produced by combining Figure 2 and Figure 4 using a magnitude form:
where Bh and Bv are the horizontal and vertical gradient values, respectively.
Another way to combine the horizontal and vertical gradients to get an edge gradient is by using
The above equations provide methods to determine a gradient magnitude. The gradient direction can be estimated by using the trigonometric relationship
You can experiment with all of the above computations on a variety of images.
The use of pixels on either side of p to calculate the gradient at p produces a gradient that is properly centered. Detection of the extreme values of the gradient then provides edge detection. However, this method is sensitive to noise and small fluctuations in image luminance. The effect of noise can be reduced by averaging the gradient calculations over the orthogonal direction.
We have represented the horizontal gradient computation by the mask
Vertical averaging can be obtained by adding rows to the mask.
Similarly, the vertical mask can be extended to provide horizontal averaging.
The result produced by using the weights in the mask is placed in the location that is indexed by the center cell.
The 3x3 mask is a basic form that can have many variations by changing the weights in the cells. Some of the popular gradient operators based on this form are shown in the table below.
|
Operator Name |
Row Gradient |
Column Gradient |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Frei-Chen |
|
|
