Digital Signal Processing Reference
In-Depth Information
where
P
i
⊆{
0
,
1
,
2
,
...
,n
}
,
i
=
1
,
...
,K,X
0
≡
1, and not all
P
i
are empty. The
sets
P
1
,
,P
K
completely define the stack filter.
It is well known that by using a property called
threshold decomposition
,
35
all
statistical and deterministic properties of stack filters can be obtained by con-
sidering only the binary domain and, hence, the monotone Boolean function
defining the stack filter. Clearly, the max and min operations, used above in
the real-valued domain definition, are generalizations of the disjunction and
conjunction operations in the binary domain.
For example, consider the well-known running median, originally intro-
duced by Tukey (Reference 36, p. 210). If the window size is 3, that is,
X
...
=
(
X
1
,X
2
,X
3
)
, then the filtering operation at each location of the signal is
MED
(
X
)
=
max
{
min
{
X
1
,X
2
}
,
min
{
X
2
,X
3
}
,
min
{
X
1
,X
3
}}
.
The monotone Boolean function corresponding to this operation is
f
(
x
1
,x
2
,x
3
)
=
x
1
x
2
∨
x
2
x
3
∨
x
1
x
3
.
It is easy to see that for a finite-length signal,* Equation 13.2 is really a
special case of Equation 13.1, where
f
i
=
f, k
i
=
n
(
i
=
1
,
...
,n
)
j
1
(
i
)
=
i
−
m, j
2
(
i
)
=
i
−
m
+
1
,
...
,j
n
(
i
)
=
i
+
m
.
So, the stack filter is really a Boolean network with simple fixed “wiring”
defined by the neighborhood structure (window). In fact, such a “sliding
window”filtering process actually corresponds to a cellular automaton and
can easily be extended to two- or higher-dimensional signals. Suppose also
that we repeat the filtering operation such that the output of one filtering pass
is used as an input to the next filtering pass with the same filter. Thus, the
entire signal corresponds to a state of a Boolean network and one filtering
pass corresponds to a transition from that state to the next state (i.e., input-
output relationship). If the filtering process is repeated, the same cyclical
phenomenon that is exhibited by Boolean networks will also occur with stack
filters. That is, either the signal will converge to a
root signal
after a finite
number of filtering passes or periodic behavior will ensue.
†
Root signals represent an important concept that is used to characterize
the operation of stack filters. A root signal of a given filter is a signal that
is invariant to applications of that filter; i.e., the signal remains unchanged.
* For the case of finite-length signals, various appending strategies can be used to augment the
left- and right-hand sides of the signal so that the output signal is of the same length as the input
signal.
†
It is interesting to note that similar periodic behavior exists even for some infinite networks
(networks with an infinite number of nodes),
37
such as those in which every Boolean function is
the majority function.
Search WWH ::
Custom Search