116 EDUARDO ABREU
Figure 4.2: The generalized SD-ROM filter structure.
(ROM filter) I
4.5 Generalized SD-ROM Method
As indicated in Fig. 4.1, the filtered output y(n) is switched between the input
x(n) and the ROM value re(n). The switching operation is conditioned on the rank-
ordered differences d(n) and fixed threshold values. Using the concept of fuzzy
logic, the method can be generalized by redefining y(n) as a linear combination
of x(n) and re(n)[Ara95]:
y(n) = a(d(n))x(n) + fi(d(n))m(n), (4.2)
where the weighting coefficients a(d(n)) and fl (d(n)) are constrained so that their
sum is normalized to 1, implying that
/~(d(n)) = 1 -
The coefficients a (d(n)) and fl (d(n)) are conditioned only on the rank-ordered
differences (there are no thresholds). We will also refer to this implementation of
the SD-ROM as the "generalized SD-ROM." A block diagram is presented in Fig. 4.2.
Note that the thresholded SD-ROM output is a special case of Eq. (4.2), in which
a (d(n)) can take on only the values 0 and 1. Pictorially, the distinction between the
two approaches can be observed by comparing Fig. 4.3 and 4.4 for the simplified
case in which d(n) ~ R 2 where d(n) = [dx (n),d2(n)]. 3 Note that the region
corresponding to di(n) > dj(n), i < j, is outside the domain of a(d(n)).
The fuzzy nature of the algorithm allows greater flexibility with regards to
the removal of highly nonstationary impulse noise. Unlike the thresholded SD-
ROM, the generalized method can also effectively restore images corrupted with
other noise types such as Gaussian noise and mixed Gaussian and impulse noise.
The values of the weighting coefficients a(d(n)) are obtained by performing op-
timization using training data. The optimized values are stored in memory and
the function a(d(n)) is implemented as a lookup table. One primary difficulty
with this approach is that for d(n) ~ R 4 and 8-bit images, the number of possible
values of d(n) is very large, so the computational complexity and memory storage
requirements associated with optimizing and implementing a(d(n)) can be very
3For the example of Fig. 4.4, the coefficients were trained to restore the Lena image corrupted
with 20% random-valued impulse noise using the least-squares design methodology presented in
CHAPTER 4: SD-ROM FILTER 117
Figure 4.3: The function o~ (d(n)) for the thresholded SD-ROM with d(n) ~ R 2.
Figure 4.4: The function ec(d(n)) for the generalized SD-ROM with d(n) ~ R 2.
high. To overcome this problem, we simplify the method by partitioning the R 4
vector space into M nonoverlapping regions Ai, i = 1,..., M, and for each region
we assign a constant value to ~x(d(n)). Figure 4.5 illustrates this idea for d(n) ~ R 2
and M = 16 2.
We observe that the function c~(d(n)) shown in Fig. 4.5 is a piecewise constant
approximation to the smooth function of Fig. 4.4. In the thresholded case, M = 2.
We restrict all region boundaries to be parallel to the coordinate axes so that each
region Ai can be represented as a Cartesian product of four scalar regions. Each
scalar region is defined by an interval of the form (qi-x, qi], where the qi's are
that define a distinct partition on R. We will denote by c~i and ~i,
respectively, the values of c~(d(n)) and fi(d(n)) associated with the region Ai:
ai = a(d(n))[d(n)~Ai,
]~i = ]~(d(n))[d(n)~Ai,