Stack Filters: From Definition to Design Algorithms

Nina S.T. Hirata*    * Department of Computer Science, Institute of Mathematics and Statistics, University of São Paulo, Rua do Matão, 1010, 05508–090 São Paulo, SP – Brazil

I INTRODUCTION

Many nonlinear filters such as the median, rank-order, order statistic, and morphological filters became known in the 1980s (Bovik et al., 1983; Brownrigg, 1984; Haralick et al., 1987; Heygster, 1982; Huang, 1981; Justusson, 1981; Lee and Kassam, 1985; Maragos and Schafer, 1987a, b; Pitas and Venetsanopoulos, 1990; Prasad and Lee, 1989; Serra, 1982, 1988; Serra and Vincent, 1992; Wendt et al., 1986). The state of the art in the area of nonlinear filters at the end of the 1980s is compiled in one of the first books on that subject (Pitas and Venetsanopoulos, 1990). Since then, several other books on nonlinear filters have been published (Dougherty and Astola, 1999; Heijmans, 1994; Marshall and Sicuranza, 2006; Mitra and Sicuranza, 2000; Soille, 2003).

Many of the nonlinear filters are derived from order statistics (Pitas and Venetsanopoulos, 1992). Median filters are the best known among those based on order statistics, and they are the root of other classes of filters in the sense that many classes of filters have been derived as generalizations of the median filter. Two findings played key roles in the development of new classes of nonlinear filters from median filters: (1) the “threshold decomposition structure” first observed in median filters (Fitch et al., 1984) that allows multilevel signal filtering to be reduced to binary signal filtering, and (2) the possibility of choosing an arbitrary rank element rather than the median as the output of the filter. The first finding led to the introduction of a general class known as stack filters (Wendt et al., 1986)—the subject of this chapter, and the second one to the development of rankorder (Heygster, 1982; Justusson, 1981; Nodes and Gallagher, 1982) and order statistic filters (Bovik et al., 1983). Both stack filters and order statistic filters include the median and the rank-order filters as particular cases.

Median filters initially were considered an alternative to linear filters because they have, for instance, better edge-preservation capabilities. However, compared to stack filters, when applied on images, median filters tend to produce blurred images, destroying details. An example of the effects of median and stack filters is shown in Figure 1. The stack filter does not suppress all the noise as the median filter does; however, its output is much sharper than the output of the median filter.

Another major class of nonlinear filters that became known around the same time are morphological filters (Haralick et al., 1987; Serra, 1982, 1988; Serra and Vincent, 1992). They include very popular filters such as openings and closings. Although developed independently, morphological operators are strongly related to stack filters. Maragos and Schafer (1987b) have shown the connections of stack filters and morphological operators. In fact, they have shown that stack filters correspond to morphological increasing operators with flat structuring elements.

This chapter provides an overview of stack filters. The previous text briefly contextualizes stack filters within the scope of nonlinear filters. The remainder of this text is written to answer the following three questions:

1. What are stack filters?

2. How do stack filters relate to other classes of filters?

3. How to design stack filters from training data?

In order to answer these questions, this chapter presents an extensive account on stack filters, divided in four major sections. Section II introduces basic definitions and notations, followed by a definition of stack filters and some of their properties, such as equivalence to positive Boolean functions. The section also includes median, rank-order filters, and their generalizations viewed as subclasses of the stack filters. Section II ends with a brief explanation of the relation between stack filters and morphological operators.

Section III formally characterizes the notion of optimal stack filters in the context of statistical estimation. Optimality is considered with respect to the mean absolute error (MAE) criterion because there is a linear relation between the MAE of a stack filter (relative to multilevel signals) and the MAEs relative to the binary cross sections. The formulation, based on costs derived from the joint distribution of the processes corresponding to images to be processed and respective ideal output images, allows a clear delineation between the theoretical formulation of the design problem and the process of estimating costs from data.

Section IV presents an overview of the main stack filter design approaches. In particular, heuristic algorithms that provide suboptimal solutions and a recent algorithm that provides an optimal solution are described. All these algorithms use training data to explicitly or implicitly estimate the costs involved in the theoretical formulation of the design problem.

Section V presents examples of images processed by stack filters that have been designed using the exact solution algorithm. The last section highlights some important issues reported throughout the text and discusses some of the remaining challenges.

II STACK FILTERS

A Preliminaries

1 Signals and Operators

Formally, a digital signal defined on a certain domain is a mapping :E→K, where K = {0, 1,…, k}, with 0 < k ∈ , is the set of intensities or gray levels. 1 Given a signal definition domain and a set of levels K, the set of all signals defined on with levels in K will be denoted as E. In particular, if k = 1, the signals are binary and they can be equivalently represented by subsets of . The set of all binary signals defined on is denoted 1E or, equivalently, E (the collection of all subsets of ). If k > 1, then the signals are multilevel.

The translation of a signal ∈KE by ∈E is denoted fq and defined by, for any ∈E, fq(p) = f (p – q). Analogously, given a set ⊆E, its translation by ∈E, denoted Xq, is defined as Xq = {p + q | p ∈ X}. The transpose of X, denoted ˇ, is defined as ˇ=−p|p∈X.

Signal processing may be performed by operators of the form :KE→KE. Binary signal operators also can be represented by set operators, that is, mappings of the form :PE→PE.

a W-Operators.

In particular, operators of great interest are those that are locally defined. The notion of local definition is characterized by a neighborhood window in the following manner. Let ⊆E be a finite set, to be called window. Usually, window W is a connected set of points in , containing the origin of . The origin of will be denoted o.

An operator :KE→KE is locally defined within W if, for any ∈E,

Ψ(f)](p)=[Ψ(f|Wp)](p)

where |Wp corresponds to the input signal f restricted to W around p. This is equivalent to say that, for any ∈E, there exists ψp: KW → K such that

Ψf]p=ψp(f−p|W)

where f–p |W is just to guarantee that the domain of function ψp is W.

Operator Ψ is translation invariant if, for any ∈E,

fp=Ψfp

that is, if applying the operator and then translating the output signal is equivalent to first translating the input signal and then applying the operator.

An...