# Algorithm Alley

Oct99: Algorithm Alley

Wesley is a project engineer with the U.S. Army Research, Development and Engineering Center in Warren, Michigan. He can be contacted at bylsmaw@tacom.army.mil.

There are many different kinds of filters, each with distinct advantages for a particular application. Mechanical filters, for instance, are used to filter out specific sizes of particles from water or dirt, while capacitors and inductors only pass high- or low-frequency electrical signals. The field of digital signal processing, however, is concerned with the development of information filters. Given a signal, or set of data points, how can the data be manipulated to achieve a desired output signal that meets the goals of a problem. "Discontiguous Exponential Averaging," by John C. Gunther (DDJ, September 1998) discussed exponential filtering and highlighted one type of informational filter used in adapting network protocols. For the purpose of removing impulsive signal noise while maintaining signal trends, I will present the use of median filtering.

Given a discrete set of data points, the median filter is defined as

y[n]=median(x[n-k],...,x[n],...,x[n+k])

where N=2k+1 is known as the filter window length. Notice the difference from an averaging filter which is defined as

y[n]=sum(x[n-k],...,x[n],...,x[n+k])/N

The median filter always selects an actual data point from the input signal, whereas the averaging filter calculates a new point.

Listing One is a MATLAB (http://www .mathworks.com/) median filter function. Note that L=k for the function call. The signal is extended by the endpoints at the beginning and end so the filter window will be full at the original signal starting point. For each input signal data point, the filter window values are sorted and the middle value is chosen to replace the original signal value. If the length of any impulsive noise is more than k+1 the filter will have no effect on it. If the noise width is less than k+1 it will be removed completely. You can see that the window length affects how well the filter will work on various types of noise inputs. The bigger the window length, the smoother the signal will be. For smaller window lengths, the filtered signal follows the original more closely.

Figure 1 shows a comparison between median filtering and averaging filtering to remove random noise from a square wave pulse. As you can see, the median filter closely recovers the original signal embedded with noise. The difference between the original signal with no noise is markedly greater for the averaging filter at the square wave pulse edges. Median filtering is particularly good at preserving trends or signal edges.

Figure 2 illustrates the capability of removing impulsive signal noise. The first pane shows (k=30) the trend preservation characteristic. To more fully illustrate the removal of signal noise, panes 2 and 3 show the filtering results with window length N=7 (k=3). Both impulses are removed in pane 2 but nothing is changed in pane 3. Table 1 lists some definitions that help define and understand how median filters work. Pane 3 of Figure 2 is obviously a root signal for a filter window length of N=7 (k=3) since the filtering process produced no change.

Finding the root signal may take more than one filtering pass. In Figure 3, pane 3 took two passes to achieve the root signal. It is possible to use a recursive median filter defined as

y[n]=median(y[n-k],...,y[n-1],x[n], x[n+1],...,x[n+k])

to achieve the root signal in only one pass. However, starting with an arbitrary signal using the recursive median filter or multiple nonrecursive filtering may not result in the same root signal.

### Variations of Median Filtering

Because median filtering is nonlinear, it does not have nice properties such as linear filters do. One property it does have, however, is that of threshold decomposition that approximates the superposition principle of linear filters. In principle, it states that given an integer valued signal x[n], with M discrete sample values, the signal can be decomposed into M-1 binary signals as in Example 1 for m=1 to M-1. Reconstruction of the original signal is then shown in Example 2.

Application of the median filter to the original signal is equivalent to applying the filter to each decomposed binary signal and then adding them up. Figure 4 illustrates this principle. This technique can be applied to noninteger signals if they are quantized to M levels.

Even more interesting is the fact that the median filter on a binary signal (0 or 1) is a simple majority decision. If there are more 1s, then the output is a 1. If there are more 0s, then the output is a 0. Consider a window length N=3 (k=1) median filter. The binary combinations are:

xyz m

000 0
001 0
010 0
011 1
100 0
101 1
110 1
111 1

where m denotes the majority outcome. Using Boolean algebra, the value for m is defined in Example 3.

Using the principle of decomposition, you could implement in hardware using AND, OR, and other logic gates of the median filtering function.

Another variation of the median filter is the weighted median filter. Here, weights are given to vary the influence each sample has in the filter. New filter properties can be explored by giving more weight to specific filter window positions. Each filter window position is assigned a weight wi. The definition of the weighted median filter is then

y[n]=median(wix[n-k],...,Wk+1x[n],...,WNx[n+k])

where "" denotes replication of that signal data point.

Median filters can even be expanded into the 2D realm for image processing applications. Here a two-dimensional window is used. For a 3×3 square, the filter would be defined as

y[m,n]=median(x[m-1,n+1], x[m,n+1], x[m+1,n+1], x[m-1,n], x[m,n], x[m+1,n], x[m-1,n-1], x[m,n-1], x[m+1,n-1])

The median value inside the window is used as the filter output.

### Conclusion

Clearly, median filters are useful tools in digital signal processing. Their properties of maintaining signal trends while removing unwanted impulsive noise are unique and they require only one parameterthe window size. The window size lets them be flexible for adaptation to specific problems. Their unique structure enables variations of the standard median filter to include threshold decomposition, weighted median filtering, recursive median filtering, and even application into two dimensions. Other extensions and derivations of the basic median filter are possible and I refer you to Internet searches under "Median Filters" or "Nonlinear Signal and Imaging Processing" and to the reference for further insights.

### References

Mitra, S.K., Kaiser, J.F. Digital Signal Processing Handbook, John Wiley & Sons, 1993, ISBN 0-471-61995-7.

DDJ

#### Listing One

```% [y]=medianL(x,L) calculates the median over N=2L+1 of x
% INPUT:
%  x - input signal
%  L - interval (N=2L+1)
%
% OUTPUT:
%  y - median of interval N
%
function [y]=medianL(x,L);

% get the signal length
l=length(x);

%extend the end points so that filter window is full
x=[x(1)*ones(1,L),x',x(l)*ones(1,L)]';

%at each data point, sort values in window and pick middle one
for i=1:l,
t=sort(x(L+i-L:L+i+L));
% k <=L
y(i)=t(L+1);
end
y=y';

```

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

# First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

# HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

# Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

# Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

# How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>