Conservative Smoothing

Brief Description

Conservative smoothing is a

noise reduction technique that derives its name from the fact that it employs a simple, fast filtering algorithm that sacrifices noise suppression power in order to preserve the high spatial frequency detail (e.g. sharp edges) in an image. It is explicitly designed to remove noise spikes --- i.e. isolated pixels of exceptionally low or high pixel intensity (e.g. salt and pepper noise) and is, therefore, less effective at removing additive noise (e.g. Gaussian noise) from an image.

How It Works

Like most noise filters, conservative smoothing operates on the assumption that noise has a high spatial frequency and, therefore, can be attenuated by a local operation which makes each pixel's intensity roughly consistent with those of its nearest neighbors. However, whereas mean filtering accomplishes this by averaging local intensities and median filtering by a non-linear rank selection technique, conservative smoothing simply ensures that each pixel's intensity is bounded within the range of intensities defined by its neighbors.
This is accomplished by a procedure which first finds the minimum and maximum intensity values of all the pixels within a windowed region around the pixel in question. If the intensity of the central pixel lies within the intensity range spread of its neighbors, it is passed on to the output image unchanged. However, if the central pixel intensity is greater than the maximum value, it is set equal to the maximum value; if the central pixel intensity is less than the minimum value, it is set equal to the minimum value. Figure 1 illustrates this idea.

Figure 1 Conservatively smoothing a local pixel neighborhood. The central pixel of this figure contains an intensity spike (intensity value 150). In this case, conservative smoothing replaces it with the maximum intensity value (127) selected amongst those of its 8 nearest neighbors.

If we compare the result of conservative smoothing on the image segment of Figure 1 with the result obtained by mean filtering and median filtering, we see that it produces a more subtle effect than both the former (whose central pixel value would become 125) and the latter (124). Furthermore, conservative smoothing is less corrupting at image edges than either of these noise suppression filters.

Guidelines for Use

Images are often corrupted by noise from several sources, the most frequent of which are additive noise (e.g. Gaussian noise) and impulse noise (e.g. salt and pepper noise). Linear filters, such as the mean filter, are the primary tool for smoothing digital images degraded by additive noise. For example, consider the image

which has been corrupted with Gaussian noise with mean 0 and deviation 13. The image

is the result after mean filtering with a 3×3 kernel. Comparing this result with the original image

it is obvious that in suppressing the noise, edges were blurred and detail was lost.
This example illustrates a major limitation of linear filtering, namely that a weighted average smoothing process tends to reduce the magnitude of an intensity gradient. Rather than employing a filter which inserts intermediate intensity values between high contrast neighboring pixels, we can employ a non-linear noise suppression technique, such as the median filtering or conservative smoothing, to preserve spatial resolution by re-using pixel intensity values already in the original image. For example, consider

which is the Gaussian noise corrupted image considered above passed through a median filter with a 3×3 kernel. Here, noise is dealt with less effectively, but detail is better preserved than in the case of mean filtering.
If we classify smoothing filters along this Noise Suppression vs Detail Preservation continuum, conservative smoothing would be rated near the tail end of the former category. The image

shows the same image conservatively smoothed, using a 3×3 neighborhood. Maximum high spatial frequency detail is preserved, but at the price of noise suppression. Conservative smoothing is unable to reduce much Gaussian noise as individual noisy pixel values do not vary much from their neighbors.
The real utility of conservative smoothing (and median filtering) is in suppressing salt and pepper, or impulse, noise. A linear filter cannot totally eliminate impulse noise, as a single pixel which acts as an intensity spike can contribute significantly to the weighted average of the filter. Non-linear filters can be robust to this type of noise because single outlier pixel intensities can be eliminated entirely.
For example, consider

which has been corrupted by 1% salt and pepper noise (i.e. bits have been flipped with probability 1%). After mean filtering, the image is still noisy, as shown in

After median filtering, all noise is suppressed, as shown in

Conservative smoothing produces an image which still contains some noise in places where the pixel neighborhoods were contaminated by more than one intensity spike

However, no image detail has been lost; e.g. notice how conservative smoothing is the only operator which preserved the reflection in the subject's eye.
Conservative smoothing works well for low levels of salt and pepper noise. However, when the image has been corrupted such that more than 1 pixel in the local neighborhood has been effected, conservative smoothing is less successful. For example, smoothing the image

which has been infected with 5% salt and pepper noise (i.e. bits flipped with probability 5%), yields

The original image is

Compare this result to that achieved by smoothing with a 3×3 median filter

You may also compare the result achieved by conservative smoothing to that obtained with 10 iterations of the Crimmins Speckle Removal algorithm

Notice that although the latter is effective at noise removal, it smoothes away so much detail that it is of little more general utility than the conservative smoothing operator on images badly corrupted by noise.

Exercises

Explore the effects of conservative smoothing on images corrupted by increasing amounts of Gaussian noise. At what point does the algorithm become incapable of producing significant noise suppression?
Compare conservative smoothing with Crimmins Speckle Removal on an image which is corrupted by low levels (e.g. 0.1%) of salt and pepper noise. Use the image

and use the original

as a benchmark for assessing which algorithm reduces the most noise while preserving image detail. (Note, you should not need more than 8 iterations of Crimmins to clean up this image.)
When low-pass filtering (e.g. by smoothing with a mean filter), the magnitudes of intensity gradients in the original image decrease as the size of the kernel increases. Consider the effects of increasing the neighborhood size used by the conservative smoothing algorithm. Does this trend exist? Could repeated calls to the conservative smoothing operator yield increased smoothing?
Conservative smoothing is a morphological operator. Viewed as such, we can define other neighborhoods (or structuring elements) besides the square configurations used in the examples. Consider the effects of conservatively smoothing an edge (of different orientations) using the structuring elements from Figure 2.

Figure 2 Six different structuring elements, for use in exercise 3. These local neighborhoods can be used in conservative smoothing by moving the central (white) portion of the structuring element over the image pixel of interest and then computing the maximum and minimum (and, hence the range of) intensities of the image pixels which are covered by the blackened portions of the structuring element. Using this range, a pixel can be conservatively smoothed as described in this worksheet.

References

R. Boyle and R. Thomas Computer Vision: A First Course, Blackwell Scientific Publications, 1988, pp 32 - 34.
A. Jain Fundamentals of Digital Image Processing, Prentice-Hall, 1986, Chap. 7.
D. Vernon Machine Vision, Prentice-Hall, 1991, Chap. 4.

Gaussian Smoothing

Brief Description

The Gaussian smoothing operator is a 2-D

convolution operator that is used to `blur' images and

remove detail and noise. In this sense it is similar to the mean filter, but it uses a different kernel that represents the shape of a Gaussian (`bell-shaped') hump. This kernel has some special properties which are detailed below.

How It Works

The Gaussian distribution in 1-D has the form:

where

is the standard deviation of the distribution. We have also assumed that the distribution has a mean of zero (i.e. it is centered on the line x=0). The distribution is illustrated in Figure 1.

Figure 1 1-D Gaussian distribution with mean 0 and =1

In 2-D, an isotropic (i.e. circularly symmetric) Gaussian has the form:

This distribution is shown in Figure 2.

Figure 2 2-D Gaussian distribution with mean (0,0) and =1

The idea of Gaussian smoothing is to use this 2-D distribution as a `point-spread' function, and this is achieved by convolution. Since the image is stored as a collection of discrete pixels we need to produce a discrete approximation to the Gaussian function before we can perform the convolution. In theory, the Gaussian distribution is non-zero everywhere, which would require an infinitely large convolution kernel, but in practice it is effectively zero more than about three standard deviations from the mean, and so we can truncate the kernel at this point. Figure 3 shows a suitable integer-valued convolution kernel that approximates a Gaussian with a Eqn:eqnsigma

of 1.4.

Figure 3 Discrete approximation to Gaussian function with =1.4

Once a suitable kernel has been calculated, then the Gaussian smoothing can be performed using standard convolution methods. The convolution can in fact be performed fairly quickly since the equation for the 2-D isotropic Gaussian shown above is separable into x and y components. Thus the 2-D convolution can be performed by first convolving with a 1-D Gaussian in the x direction, and then convolving with another 1-D Gaussian in the y direction. (The Gaussian is in fact the only completely circularly symmetric operator which can be decomposed in such a way.) Figure 4 shows the 1-D x component kernel that would be used to produce the full kernel shown in Figure 3. The y component is exactly the same but is oriented vertically.

Figure 4 One of the pair of 1-D convolution kernels used to calculate the full kernel shown in Figure 3 more quickly.

A further way to compute a Gaussian smoothing with a large standard deviation is to convolve an image several times with a smaller Gaussian. While this is computationally complex, it can have applicability if the processing is carried out using a hardware pipeline.
The Gaussian filter not only has utility in engineering applications. It is also attracting attention from computational biologists because it has been attributed with some amount of biological plausibility, e.g. some cells in the visual pathways of the brain often have an approximately Gaussian response.

Guidelines for Use

The effect of Gaussian smoothing is to blur an image, in a similar fashion to the mean filter. The degree of smoothing is determined by the standard deviation of the Gaussian. (Larger standard deviation Gaussians, of course, require larger convolution kernels in order to be accurately represented.)
The Gaussian outputs a `weighted average' of each pixel's neighborhood, with the average weighted more towards the value of the central pixels. This is in contrast to the mean filter's uniformly weighted average. Because of this, a Gaussian provides gentler smoothing and preserves edges better than a similarly sized mean filter.
One of the principle justifications for using the Gaussian as a smoothing filter is due to its

frequency response. Most convolution-based smoothing filters act as

lowpass frequency filters. This means that their effect is to remove low spatial frequency components from an image. The frequency response of a convolution filter, i.e. its effect on different spatial frequencies, can be seen by taking the

Fourier transform of the filter. Figure 5 shows the frequency responses of a 1-D mean filter with width 7 and also of a Gaussian filter with Eqn:eqnsigma

= 3.

Figure 5 Frequency responses of Box (i.e. mean) filter (width 7 pixels) and Gaussian filter ( = 3 pixels). The spatial frequency axis is marked in cycles per pixel, and hence no value above 0.5 has a real meaning.

Both filters attenuate high frequencies more than low frequencies, but the mean filter exhibits oscillations in its frequency response. The Gaussian on the other hand shows no oscillations. In fact, the shape of the frequency response curve is itself (half a) Gaussian. So by choosing an appropriately sized Gaussian filter we can be fairly confident about what range of spatial frequencies are still present in the image after filtering, which is not the case of the mean filter. This has consequences for some edge detection techniques, as mentioned in the section on

zero crossings. (The Gaussian filter also turns out to be very similar to the optimal smoothing filter for edge detection under the criteria used to derive the Canny edge detector.)
We use

to illustrate the effect of smoothing with successively larger and larger Gaussian filters.
The image

shows the effect of filtering with a Gaussian of Eqn:eqnsigma

= 1.0 (and kernel size 5×5).
The image

shows the effect of filtering with a Gaussian of Eqn:eqnsigma

= 2.0 (and kernel size 9×9).
The image

shows the effect of filtering with a Gaussian of Eqn:eqnsigma

= 4.0 (and kernel size 15×15).
We now consider using the Gaussian filter for noise reduction. For example, consider the image

which has been corrupted by Gaussian noise with a mean of zero and Eqn:eqnsigma

= 8. Smoothing this with a 5×5 Gaussian yields

(Compare this result with that achieved by the mean and median filters.)
Salt and pepper noise is more challenging for a Gaussian filter. Here we will smooth the image

which has been corrupted by 1% salt and pepper noise (i.e. individual bits have been flipped with probability 1%). The image

shows the result of Gaussian smoothing (using the same convolution as above). Compare this with the original

Notice that much of the noise still exists and that, although it has decreased in magnitude somewhat, it has been smeared out over a larger spatial region. Increasing the standard deviation continues to reduce/blur the intensity of the noise, but also attenuates high frequency detail (e.g. edges) significantly, as shown in

This type of noise is better reduced using median filtering, conservative smoothing or Crimmins Speckle Removal.

Exercises

Starting from the Gaussian noise (mean 0, = 13) corrupted image

compute both mean filter and Gaussian filter smoothing at various scales, and compare each in terms of noise removal vs loss of detail.
At how many standard deviations from the mean does a Gaussian fall to 5% of its peak value? On the basis of this suggest a suitable square kernel size for a Gaussian filter with = s.
Estimate the frequency response for a Gaussian filter by Gaussian smoothing an image, and taking its Fourier transform both before and afterwards. Compare this with the frequency response of a mean filter.
How does the time taken to smooth with a Gaussian filter compare with the time taken to smooth with a mean filter for a kernel of the same size? Notice that in both cases the convolution can be speeded up considerably by exploiting certain features of the kernel.

References

E. Davies Machine Vision: Theory, Algorithms and Practicalities, Academic Press, 1990, pp 42 - 44.
R. Gonzalez and R. Woods Digital Image Processing, Addison-Wesley Publishing Company, 1992, p 191.
R. Haralick and L. Shapiro Computer and Robot Vision, Addison-Wesley Publishing Company, 1992, Vol. 1, Chap. 7.
B. Horn Robot Vision, MIT Press, 1986, Chap. 8.
D. Vernon Machine Vision, Prentice-Hall, 1991, pp 59 - 61, 214.

Laplacian/Laplacian of Gaussian

Brief Description

The Laplacian is a 2-D isotropic measure of the 2nd spatial derivative of an image. The Laplacian of an image highlights regions of rapid intensity change and is therefore often used for

edge detection (see zero crossing edge detectors). The Laplacian is often applied to an image that has first been smoothed with something approximating a Gaussian smoothing filter in order to reduce its sensitivity to noise, and hence the two variants will be described together here. The operator normally takes a single graylevel image as input and produces another graylevel image as output.

How It Works

The Laplacian L(x,y) of an image with pixel intensity values I(x,y) is given by:

This can be calculated using a

convolution filter.
Since the input image is represented as a set of discrete pixels, we have to find a discrete convolution kernel that can approximate the second derivatives in the definition of the Laplacian. Three commonly used small kernels are shown in Figure 1.

Figure 1 Three commonly used discrete approximations to the Laplacian filter. (Note, we have defined the Laplacian using a negative peak because this is more common; however, it is equally valid to use the opposite sign convention.)

Using one of these kernels, the Laplacian can be calculated using standard convolution methods.
Because these kernels are approximating a second derivative measurement on the image, they are very sensitive to noise. To counter this, the image is often Gaussian smoothed before applying the Laplacian filter. This pre-processing step reduces the high frequency noise components prior to the differentiation step.
In fact, since the convolution operation is associative, we can convolve the Gaussian smoothing filter with the Laplacian filter first of all, and then convolve this hybrid filter with the image to achieve the required result. Doing things this way has two advantages:

Since both the Gaussian and the Laplacian kernels are usually much smaller than the image, this method usually requires far fewer arithmetic operations.
The LoG (`Laplacian of Gaussian') kernel can be precalculated in advance so only one convolution needs to be performed at run-time on the image.

The 2-D LoG function centered on zero and with Gaussian standard deviation Eqn:eqnsigma

has the form:

and is shown in Figure 2.

Figure 2 The 2-D Laplacian of Gaussian (LoG) function. The x and y axes are marked in standard deviations ().

A discrete kernel that approximates this function (for a Gaussian Eqn:eqnsigma

= 1.4) is shown in Figure 3.

Figure 3 Discrete approximation to LoG function with Gaussian = 1.4

Note that as the Gaussian is made increasingly narrow, the LoG kernel becomes the same as the simple Laplacian kernels shown in Figure 1. This is because smoothing with a very narrow Gaussian ( Eqn:eqnsigma

< 0.5 pixels) on a discrete grid has no effect. Hence on a discrete grid, the simple Laplacian can be seen as a limiting case of the LoG for narrow Gaussians.

Guidelines for Use

The LoG operator calculates the second spatial derivative of an image. This means that in areas where the image has a constant intensity (i.e. where the intensity gradient is zero), the LoG response will be zero. In the vicinity of a change in intensity, however, the LoG response will be positive on the darker side, and negative on the lighter side. This means that at a reasonably sharp edge between two regions of uniform but different intensities, the LoG response will be:

zero at a long distance from the edge,
positive just to one side of the edge,
negative just to the other side of the edge,
zero at some point in between, on the edge itself.

Figure 4 illustrates the response of the LoG to a step edge.

Figure 4 Response of 1-D LoG filter to a step edge. The left hand graph shows a 1-D image, 200 pixels long, containing a step edge. The right hand graph shows the response of a 1-D LoG filter with Gaussian = 3 pixels.

By itself, the effect of the filter is to highlight edges in an image.
For example,

is a simple image with strong edges.
The image

is the result of applying a LoG filter with Gaussian Eqn:eqnsigma

= 1.0. A 7×7 kernel was used. Note that the output contains negative and non-integer values, so for display purposes the image has been normalized to the range 0 - 255.

If a portion of the filtered, or gradient, image is added to the original image, then the result will be to make any edges in the original image much sharper and give them more contrast. This is commonly used as an enhancement technique in remote sensing applications.
To see this we start with

which is a slightly blurry image of a face.
The image

is the effect of applying an LoG filter with Gaussian Eqn:eqnsigma

= 1.0, again using a 7×7 kernel.
Finally,

is the result of combining (i.e. subtracting) the filtered image and the original image. Note that the filtered image had to be suitable scaled before combining in order to produce a sensible enhancement. Also, it may be necessary to translate the filtered image by half the width of the convolution kernel in both the x and y directions in order to register the images correctly.
The enhancement has made edges sharper but has also increased the effect of noise. If we simply filter the image with a Laplacian (i.e. use a LoG filter with a very narrow Gaussian) we obtain

Performing edge enhancement using this sharpening image yields the noisy result

(Note that unsharp filtering may produce an equivalent result since it can be defined by adding the negative Laplacian image (or any suitable edge image) onto the original.) Conversely, widening the Gaussian smoothing component of the operator can reduce some of this noise, but, at the same time, the enhancement effect becomes less pronounced.
The fact that the output of the filter passes through zero at edges can be used to detect those edges. See the section on zero crossing edge detection.
Note that since the LoG is an

isotropic filter, it is not possible to directly extract edge orientation information from the LoG output in the same way that it is for other edge detectors such as the Roberts Cross and Sobel operators.
Convolving with a kernel such as the one shown in Figure 3 can very easily produce output pixel values that are much larger than any of the input pixels values, and which may be negative. Therefore it is important to use an image type (e.g. floating point) that supports negative numbers and a large range in order to avoid overflow or saturation. The kernel can also be scaled down by a constant factor in order to reduce the range of output values.

Common Variants

It is possible to approximate the LoG filter with a filter that is just the difference of two differently sized Gaussians. Such a filter is known as a

DoG filter (short for

`Difference of Gaussians').
As an aside it has been suggested (Marr 1982) that LoG filters (actually DoG filters) are important in biological visual processing.
An even cruder approximation to the LoG (but much faster to compute) is the DoB filter (

`Difference of Boxes'). This is simply the difference between two mean filters of different sizes. It produces a kind of squared-off approximate version of the LoG.

Exercises

Try the effect of LoG filters using different width Gaussians on the image

What is the general effect of increasing the Gaussian width? Notice particularly the effect on features of different sizes and thicknesses.
Construct a LoG filter where the kernel size is much too small for the chosen Gaussian width (i.e. the LoG becomes truncated). What is the effect on the output? In particular what do you notice about the LoG output in different regions each of uniform but different intensities?
Devise a rule to determine how big an LoG kernel should be made in relation to the of the underlying Gaussian if severe truncation is to be avoided.
If you were asked to construct an edge detector that simply looked for peaks (both positive and negative) in the output from an LoG filter, what would such a detector produce as output from a single step edge?

References

R. Haralick and L. Shapiro Computer and Robot Vision, Vol. 1, Addison-Wesley Publishing Company, 1992, pp 346 - 351.
B. Horn Robot Vision, MIT Press, 1986, Chap. 8.
D. Marr Vision, Freeman, 1982, Chap. 2, pp 54 - 78.
D. Vernon Machine Vision, Prentice-Hall, 1991, pp 98 - 99, 214.

Mean Filter

Mean filtering is a simple, intuitive and easy to implement method of

smoothing images, i.e. reducing the amount of intensity variation between one pixel and the next. It is often used to

reduce noise in images.

How It Works

The idea of mean filtering is simply to replace each pixel value in an image with the mean (`average') value of its neighbors, including itself. This has the effect of eliminating pixel values which are unrepresentative of their surroundings. Mean filtering is usually thought of as a

convolution filter. Like other convolutions it is based around a kernel, which represents the shape and size of the neighborhood to be sampled when calculating the mean. Often a 3×3 square kernel is used, as shown in Figure 1, although larger kernels (e.g. 5×5 squares) can be used for more severe smoothing. (Note that a small kernel can be applied more than once in order to produce a similar but not identical effect as a single pass with a large kernel.)

Figure 1 3×3 averaging kernel often used in mean filtering

Computing the straightforward convolution of an image with this kernel carries out the mean filtering process.

Guidelines for Use

Mean filtering is most commonly used as a simple method for reducing noise in an image.
We illustrate the filter using

The image

shows the original corrupted by Gaussian noise with a mean of zero and a standard deviation ( Eqn:eqnsigma

) of 8.
The image

shows the effect of applying a 3×3 mean filter. Note that the noise is less apparent, but the image has been `softened'. If we increase the size of the mean filter to 5×5, we obtain an image with less noise and less high frequency detail, as shown in

The same image more severely corrupted by Gaussian noise (with a mean of zero and a Eqn:eqnsigma

of 13) is shown in

The image

is the result of mean filtering with a 3×3 kernel.
An even more challenging task is provided by

. It shows an image containing `salt and pepper' shot noise.
The image

shows the effect of smoothing the noisy image with a 3×3 mean filter. Since the shot noise pixel values are often very different from the surrounding values, they tend to significantly distort the pixel average calculated by the mean filter.
Using a 5×5 filter instead gives

This result is not a significant improvement in noise reduction and, furthermore, the image is now very blurred.
These examples illustrate the two main problems with mean filtering, which are:

A single pixel with a very unrepresentative value can significantly affect the mean value of all the pixels in its neighborhood.
When the filter neighborhood straddles an edge, the filter will interpolate new values for pixels on the edge and so will blur that edge. This may be a problem if sharp edges are required in the output.

Both of these problems are tackled by the median filter, which is often a better filter for reducing noise than the mean filter, but it takes longer to compute.
In general the mean filter acts as a

lowpass frequency filter and, therefore, reduces the spatial intensity derivatives present in the image. We have already seen this effect as a `softening' of the facial features in the above example. Now consider the image

which depicts a scene containing a wider range of different spatial frequencies. After smoothing once with a 3×3 mean filter we obtain

Notice that the low spatial frequency information in the background has not been affected significantly by filtering, but the (once crisp) edges of the foreground subject have been appreciably smoothed. After filtering with a 7×7 filter, we obtain an even more dramatic illustration of this phenomenon in

Compare this result to that obtained by passing a 3×3 filter over the original image three times in

Common Variants

Variations on the mean smoothing filter discussed here include

Threshold Averaging wherein smoothing is applied subject to the condition that the center pixel value is changed only if the difference between its original value and the average value is greater than a preset threshold. This has the effect that noise is smoothed with a less dramatic loss in image detail.
Other convolution filters that do not calculate the mean of a neighborhood are also often used for smoothing. One of the most common of these is the Gaussian smoothing filter.

Exercises

The mean filter is computed using a convolution. Can you think of any ways in which the special properties of the mean filter kernel can be used to speed up the convolution? What is the computational complexity of this faster convolution?
Use an edge detector on the image

and note the strength of the output. Then apply a 3×3 mean filter to the original image and run the edge detector again. Comment on the difference. What happens if a 5×5 or a 7×7 filter is used?
Applying a 3×3 mean filter twice does not produce quite the same result as applying a 5×5 mean filter once. However, a 5×5 convolution kernel can be constructed which is equivalent. What does this kernel look like?
Create a 7×7 convolution kernel which has an equivalent effect to three passes with a 3×3 mean filter.
How do you think the mean filter would cope with Gaussian noise which was not symmetric about zero? Try some examples.

References

R. Boyle and R. Thomas Computer Vision: A First Course, Blackwell Scientific Publications, 1988, pp 32 - 34.
E. Davies Machine Vision: Theory, Algorithms and Practicalities, Academic Press, 1990, Chap. 3.
D. Vernon Machine Vision, Prentice-Hall, 1991, Chap. 4.

Median Filter

Brief Description

The median filter is normally used to

reduce noise in an image, somewhat like the mean filter. However, it often does a better job than the mean filter of preserving useful detail in the image.

How It Works

Like the mean filter, the median filter considers each pixel in the image in turn and looks at its nearby neighbors to decide whether or not it is representative of its surroundings. Instead of simply replacing the pixel value with the mean of neighboring pixel values, it replaces it with the median of those values. The median is calculated by first sorting all the pixel values from the surrounding neighborhood into numerical order and then replacing the pixel being considered with the middle pixel value. (If the neighborhood under consideration contains an even number of pixels, the average of the two middle pixel values is used.) Figure 1 illustrates an example calculation.

Figure 1 Calculating the median value of a pixel neighborhood. As can be seen, the central pixel value of 150 is rather unrepresentative of the surrounding pixels and is replaced with the median value: 124. A 3×3 square neighborhood is used here --- larger neighborhoods will produce more severe smoothing.

Guidelines for Use

By calculating the median value of a neighborhood rather than the mean filter, the median filter has two main advantages over the mean filter:

The median is a more robust average than the mean and so a single very unrepresentative pixel in a neighborhood will not affect the median value significantly.
Since the median value must actually be the value of one of the pixels in the neighborhood, the median filter does not create new unrealistic pixel values when the filter straddles an edge. For this reason the median filter is much better at preserving sharp edges than the mean filter.

The image

shows an image that has been corrupted by Gaussian noise with mean 0 and standard deviation ( Eqn:eqnsigma

) 8. The original image is

for comparison. Applying a 3×3 median filter produces

Note how the noise has been reduced at the expense of a slight degradation in image quality. The image

has been corrupted by even more noise (Gaussian noise with mean 0 and Eqn:eqnsigma

13), and

is the result of 3×3 median filtering. The median filter is sometimes not as subjectively good at dealing with large amounts of Gaussian noise as the mean filter.
Where median filtering really comes into its own is when the noise produces extreme `outlier' pixel values, as for instance in

which has been corrupted with `salt and pepper' noise, i.e. bits have been flipped with probability 1%. Median filtering this with a 3×3 neighborhood produces

in which the noise has been entirely eliminated with almost no degradation to the underlying image. Compare this with the similar test on the mean filter.
Consider another example wherein the original image

has been corrupted with higher levels (i.e. p=5% that a bit is flipped) of salt and pepper noise

After smoothing with a 3×3 filter, most of the noise has been eliminated

If we smooth the noisy image with a larger median filter, e.g. 7×7, all the noisy pixels disappear, as shown in

Note that the image is beginning to look a bit `blotchy', as graylevel regions are mapped together. Alternatively, we can pass a 3×3 median filter over the image three times in order to remove all the noise with less loss of detail

In general, the median filter allows a great deal of high spatial frequency detail to pass while remaining very effective at removing noise on images where less than half of the pixels in a smoothing neighborhood have been effected. (As a consequence of this, median filtering can be less effective at removing noise from images corrupted with Gaussian noise.)
One of the major problems with the median filter is that it is relatively expensive and complex to compute. To find the median it is necessary to sort all the values in the neighborhood into numerical order and this is relatively slow, even with fast sorting algorithms such as quicksort. The basic algorithm can, however,be enhanced somewhat for speed. A common technique is to notice that when the neighborhood window is slid across the image, many of the pixels in the window are the same from one step to the next, and the relative ordering of these with each other will obviously not have changed. Clever algorithms make use of this to improve performance.

Exercises

Using the image

explore the effect of median filtering with different neighborhood sizes.
Compare the relative speed of mean and median filters using the same sized neighborhood and image. How does the performance of each scale with size of image and size of neighborhood?
Unlike the mean filter, the median filter is non-linear. This means that for two images A(x) and B(x):

Illustrate this to yourself by performing smoothing and pixel addition (in the order indicated on each side of the above equation!) to a set of test images. Carry out this experiment on some simple images, e.g.

and

References

R. Boyle and R. Thomas Computer Vision: A First Course, Blackwell Scientific Publications, 1988, pp 32 - 34.
E. Davies Machine Vision: Theory, Algorithms and Practicalities, Academic Press, 1990, Chap. 3.
A. Marion An Introduction to Image Processing, Chapman and Hall, 1991, p 274.
D. Vernon Machine Vision, Prentice-Hall, 1991, Chap. 4.

Unsharp Filter

Brief Description

The unsharp filter is a simple

sharpening operator which derives its name from the fact that it

enhances edges (and other high frequency components in an image) via a procedure which subtracts an unsharp, or smoothed, version of an image from the original image. The unsharp filtering technique is commonly used in the photographic and printing industries for crispening edges.

How It Works

Unsharp masking produces an edge image Eqn:eqnug

from an input image Eqn:eqnuf

via

where

is a smoothed version of Eqn:eqnuf

. (See Figure 1.)

Figure 1 Spatial sharpening.

We can better understand the operation of the unsharp sharpening filter by examining its frequency response characteristics. If we have a signal as shown in Figure 2(a), subtracting away the lowpass component of that signal (as in Figure 2(b)), yields the highpass, or `edge', representation shown in Figure 2(c).

Figure 2 Calculating an edge image for unsharp filtering.

This edge image can be used for sharpening if we add it back into the original signal, as shown in Figure 3.

Figure 3 Sharpening the original signal using the edge image.

Thus, the complete unsharp sharpening operator is shown in Figure 4.

Figure 4 The complete unsharp filtering operator.

We can now combine all of this into the equation:

where k is a scaling constant. Reasonable values for k vary between 0.2 and 0.7, with the larger values providing increasing amounts of sharpening.

Guidelines for Use

The unsharp filter is implemented as a window-based operator, i.e. it relies on a

convolution kernel to perform spatial filtering. It can be implemented using an appropriately defined lowpass filter to produce the smoothed version of an image, which is then pixel subtracted from the original image in order to produce a description of image edges, i.e. a highpassed image.
For example, consider the simple image object

whose strong edges have been slightly blurred by camera focus. In order to extract a sharpened view of the edges, we smooth this image using a mean filter (kernel size 3×3) and then subtract the smoothed result from the original image. The resulting image is

(Note, the gradient image contains positive and negative values and, therefore, must be normalized for display purposes.)
Because we subtracted all low frequency components from the original image (i.e., we highpass filtered the image) we are left with only high frequency edge descriptions. Normally, we would require that a sharpening operator give us back our original image with the high frequency components enhanced. In order to achieve this effect, we now add some proportion of this gradient image back onto our original image. The image

has been sharpened according to this formula, where the scaling constant k is set to 0.7.
A more common way of implementing the unsharp mask is by using the negative Laplacian operator to extract the highpass information directly. See Figure 5.

Figure 5 Spatial sharpening, an alternative definition.

Some unsharp masks for producing an edge image of this type are shown in Figure 6. These are simply negative, discrete Laplacian filters. After convolving an original image with a kernel such as one of these, it need only be scaled and and then added to the original. (Note that in the Laplacian of Gaussian worksheet, we demonstrated edge enhancement using the correct, or positive, Laplacian and LoG kernels. In that case, because the kernel peak was positive, the edge image was subtracted, rather than added, back into the original.)

Figure 6 Three discrete approximations to the Laplacian filter.

With this in mind, we can compare the unsharp and Laplacian of Gaussian filters. First, notice that the gradient images produced by both filters (e.g.

produced by unsharp and

produced by LoG) exhibit the side-effect of ringing, or the introduction of additional intensity image structure. (Note also that the rings have opposite signs due to the difference in signs of the kernels used in each case.) This ringing occurs at high contrast edges. Figure 7 describes how oscillating (i.e. positive, negative, positive, etc.) terms in the output (i.e. ringing) are induced by the oscillating terms in the filter.

Figure 7 Ringing effect introduced by the unsharp mask in the presence of a 2 pixel wide, high intensity stripe. (Gray levels: --1=Dark, 0=Gray, 1=Bright.) a) 1-D input intensity image slice. b) Corresponding 1-D slice through unsharp filter. c) 1-D output intensity image slice.

Another interesting comparison of the two filters can be made by examining their edge enhancement capabilities. Here we begin with reference to

The image

shows the sharpened version produced by a 7×7 Laplacian of Gaussian. The image

is that due to unsharp sharpening with an equivalently sized Laplacian. In comparing the unsharp mask defined using the Laplacian with the LoG, it is obvious that the latter is more robust to noise, as it has been designed explicitly to remove noise before enhancing edges. Note, we can obtain a slightly less noisy, but also less sharp, image using a smaller (i.e. 3×3) Laplacian kernel, as shown in

The unsharp filter is a powerful sharpening operator, but does indeed produce a poor result in the presence of noise. For example, consider

which has been deliberately corrupted by Gaussian noise. (For reference,

is a mean filtered version of this image.) Now compare this with the output of the unsharp filter

and with the original image

The unsharp mask has accentuated the noise.

Common Variants

Adaptive Unsharp Masking
A powerful technique for sharpening images in the presence of low noise levels is via an adaptive filtering algorithm. Here we look at a method of re-defining a highpass filter (such as the one shown in Figure 8) as the sum of a collection of edge directional kernels.

Figure 8 Sharpening filter.

This filter can be re-written as Eqn:eqnusxth

times the sum of the eight edge sensitive kernels shown in Figure 9.

Figure 9 Sharpening filter re-defined as eight edge directional kernels

Adaptive filtering using these kernels can be performed by filtering the image with each kernel, in turn, and then summing those outputs that exceed a threshold. As a final step, this result is added to the original image. (See Figure 10.)

Figure 10 Adaptive sharpening.

This use of a threshold makes the filter adaptive in the sense that it overcomes the directionality of any single kernel by combining the results of filtering with a selection of kernels --- each of which is tuned to an edge direction inherent in the image.

Exercises

Consider the image

which, after unsharp sharpening (using a mean smoothing filter, with kernel size 3×3) becomes

a) Perform unsharp sharpening on the raw image using a Gaussian filter (with the same kernel size). How do the sharpened images produced by the two different smoothing functions compare? b) Try re-sharpening this image using a filter with larger kernel sizes (e.g. 5×5, 7×7 and 9×9). How does increasing the kernel size affect the result? c) What would you expect to see if the kernel size were allowed to approach the image size?
Sharpen the image

Notice the effects on features of different scale.
What result would you expect from an unsharp sharpening operator defined using a smoothing filter (e.g. the median) which does not produce a lowpass image.
Enhance the edges of the 0.1% salt and pepper noise corrupted image

using both the unsharp and Laplacian of Gaussian filters. Which performs best under these conditions?
Investigate the response of the unsharp masking filter to edges of various orientations. Some useful example images include

and

Compare your results with those produced by adaptive unsharp sharpening.

References

R. Haralick and L. Shapiro Computer and Robot Vision, Addison-Wesley Publishing Company, 1992.
B. Horn Robot Vision, MIT Press, 1986, Chap. 6.
A. Jain Fundamentals of Digital Image Processing, Prentice-Hall, 1989, Chap. 7.
R. Schalkoff Digital Image Processing and Computer Vision, John Wiley & Sons, 1989, Chap. 4.