Optimization of stack filters based on mirrored thresholddecomposition

An adaptive optimization algorithm for the design of a new class of stack filters is presented. Unlike stack smoothers, this new class of stack filters, based on mirrored threshold decomposition, has been empowered not only with lowpass filtering characteristics but with bandpass and highpass filtering characteristics as well. Therefore, these filters can be effectively used in applications where frequency selection is critical. An adaptive optimization approach is introduced, where the positive Boolean function (PBF) that characterizes the stack filter in the binary domain of mirrored threshold decomposition is represented by a soft truth table where each possible binary input sequence is mapped to a real number in the interval [-1, 1]. At each iteration of the adaptive algorithm, the probability that the PBF makes the correct decision when a given input sequence is presented is incremented by suitably changing the entries of the soft truth table. The proposed adaptive algorithm is simple to implement since it requires only increment, decrement, and local comparison operations. The performance of optimal stack filters is illustrated by several simulations     

A fast algorithm for designing stack filters

Stack filters are a class of nonlinear filters with excellent properties for signal restoration. Unfortunately, present algorithms for designing stack filters can only be used for small window sizes because of either their computational overhead or their serial nature. This paper presents a new adaptive algorithm for determining a stack filter that minimizes the mean absolute error criterion. The new algorithm retains the iterative nature of many current adaptive stack filtering algorithms, but significantly reduces the number of iterations required to converge to an optimal filter. This algorithm is faster than all currently available stack filter design algorithms, is simple to implement, and is shown in this paper to always converge to an optimal stack filter. Extensive comparisons between this new algorithm and all existing algorithms are provided. The comparisons are based both on the performance of the resulting filters and upon the time and space complexity of the algorithms. They demonstrate that the new algorithm has three advantages: it is faster than all other available algorithms; it can be used on standard workstations (SPARC 5 with 48 MB) to design filters with windows containing 20 or more points; and, its highly parallel structure allows very fast implementations on parallel machines. This new algorithm allows cascades of stack filters to be designed; stack filters with windows containing 72 points have been designed in a matter of minutes under this new approach.     

Optimal parallel stack filtering under the mean absolute errorcriterion

The authors extend the configuration of stack filtering to develop a new class of stack-type filters called parallel stack filters (PSFs). As a basis for the parallel stack filtering, the block threshold decomposition (BTD) is introduced, and its properties are investigated. The design of optimal PSHs under the mean absolute error (MAE) criterion is shown to be similar to the minimum MAE stack filtering theory. The only difference is that one needs now to design more than one stack filter that together construct an optimal PSF. As a result, while reviewing briefly the optimal stack filtering theory, they will put more efforts to demonstrate, via several examples, the improvement by switching from stack filtering to parallel stack filtering for the task of image noise removal.     

Precision of morphological-representation estimators for translation-invariant binary filters: Increasing and nonincreasing

Mean-absolute-error-optimal, finite-observation, translations, invariant, binary-image filters have previously been characterized in terms of morphological representations: increasing filters as unions of erosions and nonincreasing filters as unions of hit-or-miss operators. Based on these characterizations, (sub)optimal filters have been designed via image-process realizations. The present paper considers the precision of filter estimation via realizations. The following problems are considered: loss of performance owing to employing erosion filters limited by basis size, precision in the estimation of erosion bases, and precision in the estimation of union-of-hit-or-miss filters. A key point: while precision deteriorates for both erosion and hit-or-miss filters as window size increases, the number of image realizations required to obtain good estimation in erosion-filter design can be much less than the number required for hit-or-miss-filter design. Thus, while in theory optimal hit-or-miss filtering is better because the unconstrained optimal hit-or-miss filter is the conditional expectation, owing to estimation error it is very possible that estimated optimal erosion filters are better than estimated optimal hit-or-miss filters.     

An overview of median and stack filtering

Within the last two decades a small group of researchers has built a useful, nontrivial theory of nonlinear signal processing around the median-related filters known as rank-order filters, order-statistic filters, weighted median filters, and stack filters. This required significant effort to overcome the bias, both in education and research, toward linear theory, which has been dominant since the days of Fourier, Laplace, and Convolute.We trace the development of this theory of nonlinear filtering from its beginnings in the study of noise-removal properties and structural behavior of the median filter to the recently developed theory of optimal stack filtering.The theory of stack filtering provides a point of view which unifies many different filter classes, including morphological filters, so it is discussed in detail. Of particular importance is the way this theory has brought together, in a single analytical framework, both the estimation-based and the structural-based approaches to the design of these filters.Some recent applications of median and stack filters are provided to demonstrate the effectiveness of this approach to nonlinear filtering. They include: the design of an optimal stack filter for image restoration; the use of vector median filters to attenuate impulsive noise in color images and to eliminate cross luminance and cross color in TV images; and the use of median-based filters for image sequence coding, reconstruction, and scan rate conversion in normal TV and HDTV systems.     

L(p) norm design of stack filters.

Addresses the problem of designing optimal stack filters by employing an L(p) norm of the error between the desired signal and the estimated one. It is shown that the L(p) norm can be expressed as a linear function of the decision errors at the binary levels of the filter. Thus, an L(p)-optimal stack filter can be determined as the solution of a linear program. The conventional design of using the mean absolute error (MAE), therefore, becomes a special ease of the general L(p) norm-based design developed here. Other special cases of the proposed approach, of particular interest in signal processing, are the problems of optimal mean square error (p=2) and minimax (p-->infinity) stack filtering. Since an Linfinity optimization is a combinatorial problem, with its complexity increasing faster than exponentially with the filter size, the proposed L(p ) norm approach to stack filter design offers an additional benefit of a sound mathematical framework to obtain a practical engineering approximation to the solution of the minimax optimization problem. The conventional MAE design of an important subclass of stack filters, the weighted order statistic filters, is also extended to the L(p) norm-based design. By considering a typical application of restoring images corrupted with impulsive noise, several design examples are presented, to illustrate the performance of the L(p)-optimal stack filters with different values of p. Simulation results show that the L(p)-optimal stack filters with p=/>2 provide a better performance in terms of their capability in removing impulsive noise, compared to that achieved by using the conventional minimum MAE stack filters.     

Design of optimal stack filters under the MAE criterion

The design of optimal stack filters under the MAE criterion is addressed in this paper. In our work, the Hasse diagram is adopted to represent the positive Boolean functions to solve the optimization problem. After problem transformation, the finding of the optimal stack filter is equivalent to the finding of the optimal on-set such that the total cost of the on-set is minimal. An efficient algorithm is developed that makes use of an important property of the optimal on-set to avoid fruitless search. It thereby greatly reduces the complexity in finding the corresponding optimal stack filter. A design example is illustrated in detail to demonstrate the optimization procedures. The proposed algorithm can generate the optimal stack filter in 1 s for the window size of 14 pixels. It can still generate the optimal stack filter for the window size of 21, although it takes about 4 h. Experimental results for real images reveal that the proposed algorithm essentially extends the maximum filter window size to make the stack filter optimization problem computationally tractable     

Data record-based criteria for the selection of an auxiliary vector estimator of the MMSE/MVDR filter

When the auxiliary vector (AV) filter generation algorithm utilizes sample average estimated input data statistics, it provides a sequence of estimates of the ideal minimum mean-square error or minimum-variance distortionless-response filter for the given signal processing/receiver design application. Evidently, early nonasymptotic elements of the sequence offer favorable bias/variance balance characteristics and outperform in mean-square filter estimation error the unbiased sample matrix inversion (SMI) estimator as well as the (constraint) least-mean square, recursive least-squares, "multistage nested Wiener filter", and diagonally-loaded SMI filter estimators. Selecting the most successful (in some appropriate sense) AV filter estimator in the sequence for a given data record is a critical problem that has not been addressed so far. We deal exactly with this problem and we propose two data-driven selection criteria. The first criterion minimizes the cross-validated sample average variance of the AV filter output and can be applied to general filter estimation problems; the second criterion maximizes the estimated J-divergence of the AV filter output conditional distributions and is tailored to binary phase-shift-keying-type detection problems.     

A Practical Parallel Architecture for Stacks Filters

Stack filters belong to the class of non-linear filters and include the well-known median filter, weighted median filters, order statistic filters and weighted order statistic filters. Any stack filter can be implemented by using the parallel threshold decomposition architecture which allows implementing their non-linear processing by means of a collection of identical binary filters (Boolean logic circuits). Although it is conceptually simple and useful to study the filter properties, this architecture is not practical for direct hardware implementation because as many as (M – 1) binary filters are required for a M-valued input signal and M is large in many applications.In this paper we introduce a new parallel architecture for stack filter implementations. The complexity is now proportional to the window width L of the filter, instead of to M. In most applications L is much smaller than M which translates into efficient hardware implementations. The attractive characteristic of ease of design exhibited by the threshold decomposition architecture is kept. In fact, for a given stack filter both in the conventional implementation and in the proposed one, the same binary filter is required. The key concept supporting the new architecture is a modified decomposition scheme which generates L binary signals for a multi-valued input. As an application example, a complex WOS filter is designed and prototyped in an FPGA.     

Robust H/sub /spl infin// filtering for stochastic time-delay systems with missing measurements

In this paper, the robust H/sub /spl infin// filtering problem is studied for stochastic uncertain discrete time-delay systems with missing measurements. The missing measurements are described by a binary switching sequence satisfying a conditional probability distribution. We aim to design filters such that, for all possible missing observations and all admissible parameter uncertainties, the filtering error system is exponentially mean-square stable, and the prescribed H/sub /spl infin// performance constraint is met. In terms of certain linear matrix inequalities (LMIs), sufficient conditions for the solvability of the addressed problem are obtained. When these LMIs are feasible, an explicit expression of a desired robust H/sub /spl infin// filter is also given. An optimization problem is subsequently formulated by optimizing the H/sub /spl infin// filtering performances. Finally, a numerical example is provided to demonstrate the effectiveness and applicability of the proposed design approach.     

Analysis of the properties of median and weighted median filtersusing threshold logic and stack filter representation

The deterministic properties of weighted median (WM) filters are analyzed. Threshold decomposition and the stacking property together establish a unique relationship between integer and binary domain filtering. The authors present a method to find the weighted median filter which is equivalent to a stack filter defined by a positive Boolean function. Because the cascade of WM filters can always be expressed as a single stack filter this allows expression of the cascade of WM filters as a single WM filter. A direct application is the computation of the output distribution of a cascade of WM filters. The same method is used to find a nonrecursive expansion of a recursive WM filter. As applications of theoretical results, several interesting deterministic and statistical properties of WM filters are derived     

An Affine Combination of Two LMS Adaptive Filters—Transient Mean-Square Analysis

This paper studies the statistical behavior of an affine combination of the outputs of two least mean-square (LMS) adaptive filters that simultaneously adapt using the same white Gaussian inputs. The purpose of the combination is to obtain an LMS adaptive filter with fast convergence and small steady-state mean-square deviation (MSD). The linear combination studied is a generalization of the convex combination, in which the combination factor lambda(n) is restricted to the interval (0,1). The viewpoint is taken that each of the two filters produces dependent estimates of the unknown channel. Thus, there exists a sequence of optimal affine combining coefficients which minimizes the mean-square error (MSE). First, the optimal unrealizable affine combiner is studied and provides the best possible performance for this class. Then two new schemes are proposed for practical applications. The mean-square performances are analyzed and validated by Monte Carlo simulations. With proper design, the two practical schemes yield an overall MSD that is usually less than the MSDs of either filter.     

Tensor product basis approximations for Volterra filters

The paper studies approximations for a class of nonlinear filters known as Volterra filters. Although the Volterra filter provides a relatively simple and general representation for nonlinear filtering, it is often highly overparameterized. Due to the large number of parameters, the utility of the Volterra filter is limited. The overparameterization problem is addressed in the paper using a tensor product basis approximation (TPBA). In many cases, a Volterra filter may be well approximated using the TPBA with far fewer parameters. Hence, the TPBA offers considerable advantages over the original Volterra filter in terms of both implementation and estimation complexity. Furthermore, the TPBA provides useful insight into the filter response. The paper studies the crucial issue of choosing the approximation basis. Several methods for designing an appropriate approximation basis and error bounds on the resulting mean-square output approximation error are derived. Certain methods are known to be nearly optimal     

最优结构元约束层叠滤波器分析与设计

在对信号阈值分解基础上,利用结构化方法结合最优估计理论,对最优结构元约束层叠滤波器进行建模和分析,证明了最优结构元约束层叠滤波器实质是一类由多个极大/极小滤波单元组成的多级秩排序滤波器,并给出基于层叠处理操作和多级秩排序操作的滤波器实现结构.最后,结合图像处理应用实例,与其它传统多级秩排序滤波器进行了比较,证明了本文滤波器的有效性.     

Optimal FIR pre- and postfilters for decimation and interpolationof random signals

A technique for the design of finite-impulse-response (FIR) filters for decimation and interpolation in multirate systems is introduced. FIR prefilters and postfilters that jointly minimize a frequency-weighted mean-square error between the original and reconstructed signals can be designed. There is no need for ideal filter prototypes: the optimal pre-postfilter pair is determined from the signal and noise spectra and the up-sampling and down-sampling factors. Some examples of image and speech processing show that the mean square optimal filter pair leads to typical SNR improvements of 2-6 dB, in comparison to other commonly used filters     

Mean-square performance of a convex combination of two adaptive filters

Combination approaches provide an interesting way to improve adaptive filter performance. In this paper, we study the mean-square performance of a convex combination of two transversal filters. The individual filters are independently adapted using their own error signals, while the combination is adapted by means of a stochastic gradient algorithm in order to minimize the error of the overall structure. General expressions are derived that show that the method is universal with respect to the component filters, i.e., in steady-state, it performs at least as well as the best component filter. Furthermore, when the correlation between the a priori errors of the components is low enough, their combination is able to outperform both of them. Using energy conservation relations, we specialize the results to a combination of least mean-square filters operating both in stationary and in nonstationary scenarios. We also show how the universality of the scheme can be exploited to design filters with improved tracking performance.     

Permutation filters: a class of nonlinear filters based on setpermutations

Introduces and analyzes a new class of nonlinear filters that have their roots in permutation theory. The authors show that a large body of nonlinear filters proposed to date constitute a proper subset of permutation filters (𝒫 filters). In particular, rank-order filters, weighted rank-order filters, and stack filters embody limited permutation transformations of a set. Indeed, by using the full potential of a permutation group transformation, one can design very efficient estimation algorithms. Permutation groups inherently utilize both rank-order and temporal-order information; thus, the estimation of nonstationary processes in Gaussian/nonGaussian environments with frequency selection can be effectively addressed. An adaptive design algorithm that minimizes the mean absolute error criterion is described as well as a more flexible adaptive algorithm that attains the optimal permutation filter under a deterministic least normed error criterion. Simulation results are presented to illustrate the performance of permutation filters in comparison with other widely used filters     

Adaptive switching mean filter using conditional morphological noise detector

The adaptive switching mean (ASM) filter is proposed to remove impulse noise. The filter first identifies the corrupted pixels using conditional morphological noise detection and then removes the detected impulses using the adaptive mean filter. Simulation results indicate that the ASM filter can suppress impulse noise effectively while preserving the details in the image very well, thus providing better restoration performance than many other switching-based filters.     

Adaptive Fuzzy Morphological Filtering of Impulse Noise in Images

In this paper we first introduce a neural network implementationfor fuzzy morphological operators, and by means of a trainingmethod and differentiable equivalent representations for theoperators we then derive efficient adaptation algorithms to optimizethe structuring elements. Thus we are able to design fuzzy morphologicalfilters for processing multi-level or binary images. The convergencebehavior of basic structuring elements and its significance forother structuring elements of different shape is discussed. Besidesthe filter design, the localized structuring elements obtainedfrom the training method give a structural characterization ofthe image which is useful in many applications. The performanceof the fuzzy morphological filters in removing impulse noisein multi-level and binary images is illustrated and comparedwith existing procedures.     

Multiaccess Interference Suppression in Orthogonal Space–Time Block Coded MIMO Systems by Adaptive Projected Subgradient Method

This paper introduces adaptive filters that are effective to suppress multiple access interference (MAI) in orthogonal space-time block coded/ multiple-input multiple-output (OSTBC-MIMO) systems. We define an optimal linear filter that minimizes the mean-square error between the filter output and a scaled version of the desired output under a constraint defined by the available channel state information (CSI). The adaptive filters refine a given estimate of the optimal filter by suppressing a sequence of closed convex functions with the adaptive projected subgradient method (APSM) at each iteration. To provide robustness against imperfect CSI, the adaptive filters use not only the available CSI but also estimates of previously transmitted symbols, which usually belong to a small finite set in digital communication systems. The resulting algorithms employ computationally efficient projections onto hyperplanes or hyperslabs and do not require any matrix inversion. An efficient recursive scheme based on such an algorithm is also presented. Convergence analysis and simulation results show the excellent performance of the proposed schemes.