## APPLICATION TO MEDIAN AND STACK FILTERS

For some time, linear filters have been widely used for signal processing mainly due to their easy design and good performance. However, linear filters are optimal among the class of all filtering operations only for additive Gaussian noise. Therefore problems such as reduction of high frequency and impulsive noise in digital images, smoothing of noisy pitch contours in speech signal, edge detection, image preprocessing in machine recognition, and other related problems with the suppression of noise that is non-Gaussian, nonadditive, or even not correlated with the signal can be difficult to solve (24).

These unsatisfactory results provided by linear filters in signal and image processing have been overcome by resorting to nonlinear filters. The more well known is perhaps the median filter, which has found widespread acceptance as the preferred technique to solve the signal restoration problem when the noise has an impulsive nature or when the signals have sharp edges that must be preserved. But the median filter has inherent problems because its output depends only on the values of the elements within its window. So, a median filter with a window width of n = 2L + 1 can only preserve details lasting more than L + 1 points. To preserve smaller details in the signal, a smaller window width must be used.

But the smaller this window width, the poorer the filter noise — reduction capability (25).

This contradiction can be solved by incorporating in the filter output the index order of the sequence of elements. It is typically done by weighting filter input values according to their relative sequence index order. This idea leads in a natural way to the concept of the weighted-median (WM) filter (26), which has the same advantages as the median filter but is much more flexible in preserving desired signal structures due to the defining set of weights. Median and weighted-median filters are well-known examples of a larger class of nonlinear filters: the stack filters, which also include the maximum-median filters, the midrange estimators, and several more filters.

The threshold decomposition architecture of stack filters means that filtering an M-valued input signal by the stack filter SB is equivalent to threshold decomposing the input signal to M — 1 binary threshold signals, filtering each binary signal separately with the binary filter B, and finally adding the binary output signal together to reconstruct the M-valued signal. As stack filters possess the stacking property, this reconstruction section needs only to detect the level just before the transition from 1 to 0 takes place.

Figure 15 illustrates the threshold decomposition architecture of a stack filter with a window width of 3 for the fourvalued input signal shown at the upper left corner. The binary signals are obtained by thresholding the input signal at levels 1, 2, and 3. Binary filtering is independently performed

.

In the original integer domain of the M-valued input signal, the stack filter corresponding to a positive Boolean function (PBF) can be expressed by replacing logical operators AND and OR with MIN and MAX operations, respectively. In consequence, the output of a stack filter is a composition of maximum and minimum operations on the samples in the window. For the example in Fig. 15, this means that the operation performed by SB is SB(A, B, C) = MAX{MIN{A, C}, B}. Both filtering operations are represented in Fig. 15: by threshold decomposition if the lightface arrows are followed and directly, by the stack filter SB, following the boldface arrows.

The next question is to know which binary functions possess the stacking property. It has been shown that the necessary and sufficient condition for this is that the binary function is a PBF, that is, positive in all its variables. These functions are a subset of unate functions that have the property that each one possesses a unique minimum sum-of-prod — ucts (SOP) expression, and hence each stack filter can be described in terms of a unique minimum SOP Boolean expression. Finally, as shown previously, threshold functions are a subset of unate functions. Stack filters that are based on TGs with nonnegative weights and nonnegative threshold values are called weighted-order statistics filters.

It can be very instructive to show the relations of the more usual members of the class of stack filters, namely, weighted — order statistic (WOS), weighted-median (WM), order-statistic

(OS), and standard-median (SM) filters. In Fig. 16 these relations are shown by means of boxes and arrows. Each box corresponds to a filter subclass specified by the integer domain filter and the binary domain filter. The arrows indicate the containing conditions among classes of filters.

From a practical point of view, there are several options for the very-large-scale integrated circuit (VLSI) implementation of the PBFs of a stack filter: binary logic gates, sort-and — select circuits, or count-and-compare circuits. If logic gates or a programmable logic array (PLA) is used, a number of terms bounded by for a window width of n can be obtained. The hardware complexity for sort-and-select circuits is O(n log n) and O(n) for count-and-compare circuits. The PBF can also be realized as a look-up table by a 2n-sized random-access memory (RAM) or read-only memory (ROM), and if a RAM is used, programmable PBF-based filters can be made.

In the case of a WOS filter, its PBF can be realized by a TG. It constitutes a great advantage because the number of product terms or sum terms of the PBF can be as large as

while the representation of a TG needs only n + 1 components, the n weights and the threshold T. Therefore, while the implementation of a generic stack filter can be very diffi-

## Добавить комментарий