Spatial-Rank Order
Selection Filters
Department of Electrical and Computer Engineering
University of Delaware
Newark, Delaware
Department of Electrical and Computer Engineering
University of Dayton
Dayton, Ohio
3.1 Introduction
Many image processing applications demand the use of nonlinear methods. Im-
age nonstationarities, in the form of edges, and commonly occurring heavy-tailed
noise result in image statistics that are decidedly non-Gaussian. Linear methods
often perform poorly on non-Gaussian signals and tend to excessively smooth
visually important image cues, such as edges and fine detail. Through the con-
sideration of appropriate statistical signal and interference models, more effective
image processing algorithms can be developed. Indeed, an analysis based on max-
imum likelihood estimation carried out in Sec. 3.2, indicates that rank order based
processing of signals such as images is more appropriate than linear processing.
Strict rank order methods, however, are spatially blind and cannot exploit the rich
spatial correlations generally present in images.
This chapter explores the joint use of spatial and rank (SR) ordering informa-
tion in a selection filter framework and applies the methods developed to several
common image processing problems. Each of the marginal orderings of observed
samples yields information that can be used in the design of filtering algorithms:
spatial ordering can be used to exploit correlations between neighboring samples,
while rank order can be used to isolate outliers and ensure robust behavior. By
operating jointly on the SR orderings, sophisticated algorithms can be developed
that exploit spatial correlations while producing robust outputs that appropriately
process abrupt signal transitions (edges) and are immune to sample outliers.
Numerous filtering algorithms have been developed that exploit, in some fash-
ion, spatial and rank order information in the filtering operation. A large class
of such filters can be categorized as selection type, in that their output is always
one of the samples from the local observation window. Restricting a filter to be
selection type is rarely limiting and, as shown in Sec. 3.2, often holds advantages
in image processing applications. Thus, we focus on developing the broad class
of SR selection filters that operates on the SR ordering information of observed
To illustrate the advantages of SR selection filters over traditional linear schemes,
consider the smoothing of a noisy image. Figure 3.1 shows the results of process-
ing a noisy image with a weighted sum filter that operates strictly on spatial order,
along with the results of a selection filter that operates jointly on SR ordering in-
formation. These results indicate that weighted sum filters tend to smooth edges
and obliterate fine detail. In contrast, the selection filter, by operating jointly on
the SR ordering information, is able to suppress the noise while simultaneously
preserving edges and fine detail.
The remainder of this chapter theoretically motivates SR selection filters, devel-
ops several filter class subsets and extensions that utilize partial, full, or extended
SR ordering information, and applies the filters developed to several image pro-
cessing problems. Section 3.2 begins with a theoretical discussion of maximum
likelihood (ML) estimation that motivates the use of rank order in the processing
of signals with heavy-tailed distributions. The ML development leads naturally to
several rank order selection filters, including the median filter, which are then ex-
tended to the general class of selection filters. Additionally, a general framework
for relating the spatial and rank orderings of samples is introduced in the section.
The broad class of SR selection filters is discussed in Sec. 3.3, beginning with
permutation filters, which utilize the full SR ordering information. The factorial
growth (with window size) in the number of SR ordering limits the size of permu-
tation filter window that can be utilized in practice. To efficiently utilize partial
SR information in the filtering process, we develop M permutation and colored
permutation filters. These methods utilize the rank order information of specific
spatial samples and allow ordering equivalences to be established in order to effi-
ciently utilize the most important SR information in a given application. We extend
the SR selection filtering framework to include augmented observation sets that
may include functions of the observed samples.

Get Nonlinear Image Processing now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.