Introduction - Logic-based Nonlinear Image Processing - page 5

nation would be required to arrive at a robust estimate. The number of input combi-
nations grows rapidly as the number of input variables increases.
In order to be able to design the filter from a realistically sized training set, fur-
ther constraints must be applied to the filter. The filter is an estimator; it uses the in-
put values to estimate an unobserved quantity. By making simple assumptions
about the image statistics, we can estimate the output value at a specific point by
considering only a finite window of observations centered at that point. For binary
values, the output becomes a logical function of the input variables. If the window
contains n points, there are 2 n combinations of input variables for which the rele-
vant output must be estimated. Therefore, there are 2 2 n

possible functions (or filters)
and it is the objective of the design process to determine which one of these func-
tions corresponds to the optimum.
Among the 2 2 n functions that may be applied within an n point window, there

will be many subclasses of functions. We may decide to restrict the choice to a filter
that is idempotent or increasing. Idempotence implies that the filter has only a
one-off effect on the image such that repeated application of the filter leads to no
further modification of the image. Increasing implies that the filter preserves signal
ordering. It can be shown that increasing filters map to logical functions that con-
tain no complementation of the input variables. This drastically reduces the size of
the training set required and therefore makes filter design easier. This can be ex-
plained in terms of logic (since a much smaller set of functions is under consider-
ation) or in terms of statistical estimation (since now a single training example may
be used to infer information about other combinations of input variables).
If we assume that the statistics of the image are wide-sense stationary, then we
may assume that the same optimum function applies at every point in the image.
The filter then becomes translation-invariant. This not only simplifies the process-
ing, but in effect increases the available training data because we do not distinguish
between data collected at different locations in the image.
Nonlinear filters can be effective in retaining structural information while re-
moving background clutter in a way not possible with linear operations. They can
often be application-specific.
Historically, nonlinear filters have developed along three independent strands:
morphological, rank-order, and stack. However, all can be brought together and ex-
pressed in the context of logic.
Mathematical morphology has its roots in shape. 2,3 A signal is probed by a
structuring element to determine if it “fits” inside the signal. Mathematically, it has
been expressed in set theory as explained by Minkowski. Initially, the work grew
from binary images, although it can equally well be applied to 1D signals and has
since been extended to grayscale 4 and complete lattices. 5
Morphology was developed in the context of set theory. It does, however, take
little more than a change in notation to show that the basic operation of erosion cor-
responds directly to a logical AND of the input variables. For all practical purposes,
what is called an erosion in morphology is called a Minkowski subtraction in set
theory. It is also called an intersection in mathematics and in digital electronics it is