Mean Filters

University of Texas at San Antonio

College of Engineering

EE 4623

Digital Filtering

Project #3

Develop a Program that will implement the non-linear filters

Adriana Juarez

December 3, 2002

Abstract:

The purpose of this project is to develop a program that implements non-linear filters. For this project we will research the mean filter and the Median filter.

Introduction:

The Idea of this project is to generate and image and implement different types of noise, then add them together and run them through a non-linear filter and see how the filter affects the output image. First we must locate and image then add the noise and run the image through

a non-linear filter to successfully remove all sort of noise corruption.

We will compare two filters, the mean filter and the median filter, for a few simple cases. The purpose of the filtering operation is assumed to be an effective elimination or attenuation of the noise that is corrupting the desired images. In this report we will consider only the two-dimensional cases (image). The effects are better visualized with images.

Background on non-linear filters:

Non-linear filtering has been considered even in the fifties, since then, the field has seen a rapid increase of interest indicated. In our case the Multistage medians and median filters have been rather extensively studied from the theoretical point of view in the beginning of the seventies in the Soviet Union. These filters have been independently reinvented and put into wide practical use around 15 years later by western researchers.

Non-linear FIR filters cannot be expressed as a linear combination of the input, but as some other (non-linear) function on the inputs. A simple example of a useful non-linear filter is a 5th order median filter. This is the filter represented by:

This type of filter is extremely useful for data with non-Gaussian noise, removing outliers very efficiently. A significant amount of research effort has gone into the development of appropriate filters for various purposes.

Statistics has taken a different tack to the problem: early approaches were similar to moving average filters. However, rather than using a simple moving average, the early work realized that linear regression could be used around the point we were trying to estimate; in other words, rather than simply averaging the five values around a point, a linear fit of the points, using a least squares estimate, could be used to give a better-looking result. Furthermore, we realized that

1) Linear regression could be applied, so could other shapes, in particular splints.

2) The weights for the instances used in regression could be changed.

Each of filtering and smoothing has their advantages. Filter design allows the use of domain knowledge to overcome domain-specific problems, while smoothing is flexible enough to be used more independently of the domain.

The main reason that smoothing is useful is that it allows the met feature extraction functions to be simpler. Rather than a lot of effort being devoted towards making the met feature extraction functions robust to noise, and simplify their implementation.

Convolution:

Convolution is a simple mathematical operation, which is fundamental to many common image-processing operators. Convolution provides a way of multiplying together two arrays of numbers, generally of different sizes, but of the same dimensionality, to produce a third array of numbers of the same dimensionality. This can be used in image processing to implement operators whose output pixel values are simple linear combinations of certain input pixel values.

In an image-processing context, one of the input arrays is normally just a gray level image. The second array is usually much smaller, and is also two dimensional, and is known as the kernel. The figure below will shows us an example image and kernel that we will use to illustrate convolution.

Image Kernel

The convolution is performed by sliding the kernel over the image, generally starting at the top left corner, so as to move the kernel through all the positions where the kernel fits entirely within the boundaries of the image. Each kernel position corresponds to a single output pixel, the value of which is calculated by multiplying together the kernel value and the underlying image pixel value for each of the cells in the kernel, and then adding all these numbers together.

So in our example, the value of the bottom right pixel in the output image will be given by:

If the image has M rows and N columns, and the kernel has m rows and n columns, then the size of the output image will have M-m+1 rows, and N-n+1 columns.

Mathematically we can write the convolution as:

Where i runs from 1 to M-m+1 and j runs from 1 to N-n+1.

Note that many implementations of convolution produce a larger output image than this because they relax the constraint that the kernel can only be moved to positions where it fits entirely within the image. Instead, these implementations typically slide the kernel to all positions where just the top left corner of the kernel is within the image. Therefore the kernel overlaps the image on the bottom and right edges. One advantage of this approach is that the output image is the same size as the input image. Unfortunately, in order to calculate the output pixel values for the bottom and right edges of the image, it is necessary to invent input pixel values for places where the kernel extends off the end of the image. Typically pixel values of zero are chosen for regions outside the true image, but this can often distort the output image at these places. Therefore in general if