Non-Linear Filtering of Images (Image Processing) Part 1

Linear filters have the property that their output is a linear combination of their input. Filters that do not satisfy this property are non-linear. Nonlinear filters are not employed in image processing as frequently as linear filters, because in many cases they are based on heuristics closely tied to the particular application. The general idea in non-linear image filtering is that instead of using the spatial mask in a convolution process, the mask is used to obtain the neighboring pixel values, and then ordering mechanisms produce the output pixel. That is, as the mask is shifted about the image, the order of the pixels in the windowed section of the image is rearranged, and the output pixel is generated from these rearranged input pixels. Figure 4-13 illustrates this procedure, for three types of non-linear filters.

The primary application with which we shall explore the use of nonlinear filters will be in the enhancement of noisy images. While non-linear filters are sometimes used to perform other tasks, removal of noise is by and large the most common usage pattern. The topic of noise was introduced in 4.1.1, and to properly demonstrate the effectiveness of these filters in removing noise, it is necessary to first take a small detour to explain how to quantitatively assess their performance. Once we have introduced the theory behind assessing image fidelity, we can go back and present actual implementations of non-linear filters, and evaluate their performance.


Image Fidelity Criteria and Various Metrics

Here we deal with answering the question of how effective a particular filter is in enhancing the quality of an image, relative to some other image. Without answering the image fidelity question it is impossible to ascertain a filter’s performance. The answer to this question is also of fundamental importance in other image processing fields, such as when considering the efficacy of lossy compression algorithms, where tradeoffs must be made between the amount of compression and the loss of image quality in the compressed image. In data compression, the "other image" is simply the original, uncompressed image.

Examples of non-linear filters. g(i,j) = 50 for T2 and is referred to as a median filter, and is one of the more common non-linear filters used in image processing. Tt and T} correspond to the minimum and maximum intensity in the 3x3 neighborhood surrounding f(ij). Minimum filters form the basis of image erosion, and maximum filtering the basis of image dilation.

Figure 4-13. Examples of non-linear filters. g(i,j) = 50 for T2 and is referred to as a median filter, and is one of the more common non-linear filters used in image processing. Tt and T} correspond to the minimum and maximum intensity in the 3×3 neighborhood surrounding f(ij). Minimum filters form the basis of image erosion, and maximum filtering the basis of image dilation.

When dealing with image enhancement algorithms, the situation is not so straightforward. After running a noisy image through a spatial filter, what do we compare the (hopefully) enhanced image against, so as to gauge the filter’s performance?

Since the spatial filters in this topic are going to be presented in the context of removing some type of noise from an image, it follows that a reasonable course of action is to simulate a noisy system by injecting certain forms of noise into an image, running the corrupted image through a filter, and then comparing the processed image to the original pristine image. So how to perform this comparison? Theoretically speaking, the best means is in fact modifying the old adage that "beauty is in the eye of the beholder" to "image enhancement is in the eye of the beholder." In other words, since images are visualized by humans, the human eye provides the best feedback system. Subjective assessment of image quality is prevalent in medical imaging (less so in image compression systems), where it is imperative that highly trained clinicians determine whether or not there is a perceived gain or loss in diagnostic information. Practically speaking, relying on human observers to score the performance of image enhancement algorithms is not a viable strategy; first because it is not economical, and secondly the subjective nature precludes incorporation into mathematical models.

Thus an objective measurement, some means of quantifying image fidelity, is required. The first metric that comes to mind is to consider the difference between the filtered pixels and the original pixels. If the original MxN image is f(i,j) and the filtered MxN image is g(i,j), the delta image d(i,j) is

tmp6-199_thumb

The total delta between the original / and processed g is then simply the sum:

tmp6-200_thumb

This sum could conceivably be used as a fidelity criterion – however the most commonly used criterion is the mean squared error (MSE’), which is the average of the squared delta measurement:

tmp6-201_thumb

The root mean square error (RMS) is the square root of the MSE:

tmp6-202_thumb

Related to these is the signal-to-noise ratio (SNR), roughly defined as SNR = signal/noise

Essentially, all image enhancement processes aim to improve the SNR. SNR is a term used in a multitude of engineering disciplines, and is oftentimes expressed in decibels (dB). A large SNR indicates a relatively clean image; a low SNR indicates that there is enough noise present within the image such that it impairs one’s ability to discriminate between the noise floor and the actual signal. The SNR metric is a very seductive one to use, as it makes intuitive sense. For example, when it comes to digital photography, the bottom line is that increasing the light gathering capability of the lens increases signal and therefore increases SNR, thus producing better looking photos. But care must be taken when quoting actual SNR results, as there are so many different definitions for SNR that proper comparison of results can be difficult. If SNR measurements are quoted, the best strategy is to clearly define exactly how SNR is being calculated, or to rely on RMS or MSE metrics, which everyone agrees on. The mean-squared SNR is defined as

tmp6-203_thumb

SNRnns, the RMS value of the SNR, is simply the square root of the above equation. The final metric we consider is the peak signal-to-noise ratio (PSNR), which relates the magnitude of the noise to the peak value in the image. The PSNR, in decibels, is defined as

tmp6-204_thumb

where p is the peak value of the signal (255 in an 8-bit image) and RMS is the root-mean-square delta between the original image and the output image. It should be emphasized that basing image fidelity and algorithm performance solely on quantitative means can be misleading. It is not uncommon for two images to have the same or approximately the same PSNR, but for one of the images to exhibit characteristics that subjectively jump out at the human observer. The classic example is when one image differs from another by 1 pixel count across the board (i.e. imageB = imageA + 1), hence imageB is ever so slightly brighter than imageA. Here the human eye will not perceive any distortion, but a numerical fidelity criterion will have a large magnitude. Now imagine the situation where one image differs from another in that a small block of the image is missing. This blemish, a type of "shot noise," will immediately be noticed yet standard error measures will not bear this out. This situation is illustrated in Figure 4-14.

The Median Filter

The median filter is conceptually similar to an averaging kernel. An averaging kernel produces an output pixel g(i,j) that is the mean intensity of a neighborhood around f(i,j). The median filter is the same operation, except that instead of the mean intensity the median intensity is chosen. In other words, the reordering mechanism that defines this non-linear filter is a sorting operation, and the output is simply the middle value of the sorted list. Figure 4-13 shows an example of how the median filter is implemented.

The median filter is ideal for removing impulsive noise, sometimes referred to as "salt and pepper" or "shot" noise (see Figure 4-14c). This type of noise manifests itself as outlier pixel intensities, completely independent of signal content. Because of the need to sort the values within the sliding window, the median filter can be quite costly to implement – however they are preferred to a smoothing filter in these cases because they are far better at preserving the edges in an image. Figure 4-15 demonstrates this behavior for a small 5×5 test image. Notice how the blurring filter spreads the error around, and reduces the effect of the sharp vertical edge in the input image, while the median filter does a superb job of reconstructing the input image.

Figure 4-16 is a more realistic example of the median filter in action. Figure 4-16b shows the Lenna image corrupted with 40% impulse noise, and Figures 4-16c and 4-16d show the effect of passing the corrupted image through a 3×3 and 5×5 median filter, respectively. This is an example where the quantitative fidelity metrics mesh with the qualitative metrics – not only does Figure 4-16d look better than 4-16c, but the PSNR fidelity measure reflects this observation.

The problems with relying solely on numerical image fidelity metrics, (a) Original 256x256 baboon image, (b) Brightened image, with each pixel changed by 1 intensity level, e^s = sqrt(2562/2562) = 1. (c) Image with a 3x3 blemish, where each corrupted pixel differs from the original by 50 intensity levels. The eRMs of this image is sqrt ((9*502)/2562) = 0.5859, which is less than the eRMs of the second image, even though this image looks worse by any subjective criteria.

Figure 4-14. The problems with relying solely on numerical image fidelity metrics, (a) Original 256×256 baboon image, (b) Brightened image, with each pixel changed by 1 intensity level, e^s = sqrt(2562/2562) = 1. (c) Image with a 3×3 blemish, where each corrupted pixel differs from the original by 50 intensity levels. The eRMs of this image is sqrt ((9*502)/2562) = 0.5859, which is less than the eRMs of the second image, even though this image looks worse by any subjective criteria.

Comparison of a median filter vs, an averaging filter, (a) Original 5x5 test image, (b) Test image with impulsive noise added (middle pixel), (c) Output of 3x3 median filter, with boundary values extended symmetrically, (d) Result of 3x3 averaging filter, also with boundary values extended. Notice how this filter, while reducing the effect of the shot noise, spreads the error and greatly attenuates the effect of the sharp edge in the original image.

Figure 4-15. Comparison of a median filter vs, an averaging filter, (a) Original 5×5 test image, (b) Test image with impulsive noise added (middle pixel), (c) Output of 3×3 median filter, with boundary values extended symmetrically, (d) Result of 3×3 averaging filter, also with boundary values extended. Notice how this filter, while reducing the effect of the shot noise, spreads the error and greatly attenuates the effect of the sharp edge in the original image.

Removing impulse noise from the Lenna image using the median filter. Peak signal-to-noise ratio calculated using provided MATLAB function psnr .m, which is based on formula given in the text, (a) Original image, (b) Lenna with 40% additive impulse noise, (c) Processed image using 3x3 median filter, (d) Processed image using 5x5 median filter.

Figure 4-16. Removing impulse noise from the Lenna image using the median filter. Peak signal-to-noise ratio calculated using provided MATLAB function psnr .m, which is based on formula given in the text, (a) Original image, (b) Lenna with 40% additive impulse noise, (c) Processed image using 3×3 median filter, (d) Processed image using 5×5 median filter.

The median filter is actually a specific form of a rank filter, where the ith pixel intensity in the sorted list of neighborhood pixels is chosen as the output. Thus for the case of the median filter, the index i is simply the middle point. If the neighborhood is sorted in ascending order, and the index i is chosen to be the first element, then the filter is a minimum filter. Likewise, if the last element is chosen, the filter is a maximum filter. Passing an image through a minimum filter is known as erosion – dark areas in the image become more pronounced, and oftentimes images are repeatedly passed through erosion filters to aggrandize the effect. One application of the maximum filter is image dilation, where bright areas in the image are emphasized. Again, repeated application of dilation is a common technique.

Image erosion and dilation, (a) Lenna image after two passes of a 3x3 minimum filter, (b) Image after two passes of a 3x3 maximum filter.

Figure 4-17. Image erosion and dilation, (a) Lenna image after two passes of a 3×3 minimum filter, (b) Image after two passes of a 3×3 maximum filter.

Image erosion and dilation find their way into numerous image-processing systems. The global nature of the image remains the same, while dark (erosion) or bright (dilation) regions dominate, the degree of which is dependent on how many times the filter is applied. Figure 4-17 illustrates this effect on the Lenna image. In astronomical imaging, erosion is useful to bring out an object buried within a dense area – for example a nebula obscured within a star field. The two operations are sometimes coupled, as in image segmentation, where the goal is to deconstruct an image into sections that ideally map to objects of interest. Dilation followed by erosion can be used in image segmentation to enhance the contrast of portions of an image so that a simple brightness threshold can be used as a tool to separate various objects in an image.

Next post:

Previous post: