THE GATEWAY DESIGN LABORATORY:

THE GATEWAY DESIGN LABORATORY:

Median Filter Design

The following description is adapted from a paper in the 1991 European Solid State Circuits Conference[1].

Median filtering is a non-linear technique usually adapted in digital signal processing when noise spikes have to be eliminated from the useful signal, and is particularly appealing in the processing of bi-dimensional signals, such as video signals i.e. in image processing.

The function performed by a median filter is to apply a window to a stream of digital samples, to sort the samples in ascending order and to output the "median" value, that is the sample lying just in the middle position of the ascending staircase. Then, the window shifts one position on the incoming stream and the operation is repeated on the new set of samples every machine cycle.

The basic example is to suppose that the n samples are already ordered inside the filter and to operate in 2 logical steps. First, the oldest data is removed from the window, then the new data is inserted at the right place in the ordered sequence, so that the window always contains n ordered samples.

The filter architecture thus consists of a chain of n blocks as shown in Figure 1 with definition of the symbols in Figure 2. The first block receives the new data to be inserted in the chain and the delayed, old data which must be eliminated. The old data is available at the output of a shift register of length n fed with the input sequence.

Let us examine the behaviour of one cell of a chain and show the linear ordering technique used in this design. The cells receive the old data input OI and the new data input NI. Each cell has a stored value (in dtypes) representing the current data at that position in the sorted array. Before comparing the New Input (NI) data with the Stored Data (SD) to find its place in the sequence, the check is done to see if the cell contains the old data to be removed.

In fact, the condition (OI > SD) means that the data to be eliminated is stored neither in that cell nor the preceding ones (keeping in mind that the chain contains an ordered sequence), therefore NI is compared with SD.

  1. If (NI < SD), the new data has found its place in the sequence: it is thus presented on the Output Data (OD) line and the old content of the cell is propagated to the next cell as the new data to be stored therein (NO = SD).
  2. Otherwise (NI >= SD), the cell content is kept (OD = SD) and the new data incoming to this cell is propagated to the next (NO = NI).

Figure 1: median block diagram

Let us now consider the case (OI <= SD). This means that the oldest data has already been removed, or it has to be removed now and the comparison has to be made between the incoming data NI and the Next Data (ND) stored in the next cell.

  1. As before if (NI < ND) then the incoming data must be stored in the present cell (OD = NI) and ND must be propagated to the next cell (NO = ND).
  2. Otherwise (NI >= ND), ND is stored and NI is propagated, to find its place in one of the next cells.

Figure 2: symbol definition

In summary: if OI > SD then Z = SD else Z = ND, if NI < Z then OD = NI, NO = Z else OD = Z, NO = NI.

References

  1. R Runcella, R Suletto, and P Terreni, "A novel bit-level systolic array median filter", Proc ESSCIRC , pp. 97-100, 1991.