For some time, linear filters have been widely used for signal processing mainly due to their easy design and good perfor­mance. 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 prepro­cessing in machine recognition, and other related problems with the suppression of noise that is non-Gaussian, nonaddi­tive, 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 me­dian 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 natu­ral 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-me­dian filters are well-known examples of a larger class of non­linear filters: the stack filters, which also include the maxi­mum-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 sig­nal 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 re­construction section needs only to detect the level just before the transition from 1 to 0 takes place.

Figure 15 illustrates the threshold decomposition architec­ture of a stack filter with a window width of 3 for the four­valued input signal shown at the upper left corner. The bi­nary 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 sig­nal, the stack filter corresponding to a positive Boolean func­tion (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 oper­ation 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 pos­sess the stacking property. It has been shown that the neces­sary and sufficient condition for this is that the binary func­tion is a PBF, that is, positive in all its variables. These functions are a subset of unate functions that have the prop­erty that each one possesses a unique minimum sum-of-prod — ucts (SOP) expression, and hence each stack filter can be de­scribed 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 rela­tions are shown by means of boxes and arrows. Each box cor­responds 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) implementa­tion 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 com­plexity 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, programma­ble 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 compo­nents, the n weights and the threshold T. Therefore, while the implementation of a generic stack filter can be very diffi-


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

Ваш e-mail не будет опубликован. Обязательные поля помечены *