Genetic algorithm implementation of stack filter design for imagerestoration

Stack filters are a class of nonlinear spatial operators used for noise suppression. Their design is formulated as an optimisation problem and genetic algorithms (GAs) are used to perform the configuration. Applying the mean absolute error (MAE) as the basis of an objective function, the stack filter is used to restore magnetic resonance (MR) images corrupted with uncorrelated additive noise from 10%, and 50%. The filter is trained on corresponding patches of the original and noisy image and then applied to the whole image. The outcomes are compared with the median filter and return a smaller MAE for all noise levels. The dependency of MAE on the training window size and the GA early termination is examined, showing that a reduction of 75% in computational complexity can be achieved by a 10% relaxation in the MAE. The design is then extended from 9-point to 13-point filters and by training on Poisson noise, the filter is applied to nuclear medicine bone scans where no absolute truth exists. Surface topology, image profiles and the measurement of relative contrast show its value in reducing noise whilst preserving contrast. Because of its computational complexity the process has been implemented as a distributed GA using the parallel virtual machine (PVM) software     

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.     

Fast adaptation and performance characteristics of FIR-WOS hybridfilters

Fast adaptive algorithms are developed for training weighted order statistic (WOS) filters and FIR-WOS hybrid (FWH) filters under the mean absolute error (MAE) criterion. These algorithms are based on the threshold decomposition of real-valued signals introduced in this paper. With this method an N-length WOS filter can be implemented by thresholding the input signals at most N times independent of the accuracy used. Beside saving in computations, the proposed algorithms can be applied to process arbitrary real-valued signals directly. Performance characteristics of FWH filters in 1-D and 2-D signal restoration are investigated through computer simulations. We show that both in restoration of signals containing edges and in the case of heavy tailed nonGaussian noise, considerable improvement in performance can be achieved with FWH filters over WOS filters, Ll filters, and adaptive linear filters. Two new FWH filter design strategies are found for removal of impulsive noise and for restoration of a square wave, respectively     

Minimax deconvolution design of multirate systems with channelnoises: a unified approach

The conventional signal reconstruction problem of multirate systems with channel noises can be cast as a robust multirate deconvolution design problem. We investigate a unified minimax approach for the robust deconvolution design of multirate systems. We discuss two typical multirate systems: the multirate filter bank system and the transmultiplexer system. We consider transmission noises resulting from quantization coding errors or external noises. The deconvolution filters for these systems that we derive are all IIR filters. The keypoint is converting the original robust deconvolution design problem to an equivalent minimax matching problem via polyphase decomposition and noble identities. Then, in spite of the presence of input signals and channel noises, we can solve this minimax matching problem by an optimization technique. The proposed method can be interpreted as designing an optimal multirate deconvolution filter such that the worst-case multirate system reconstruction error is minimized over all possible inputs and noises from the energy perspective. Therefore, our proposed design method is more robust than the conventional design method for multirate systems in the presence of uncertain input signals and channel noises. We present several numerical examples that show the good performance of our design method     

Linear periodic systems and multirate filter design

We present a systematic procedure for the design of filters intended for multirate systems. This procedure Is motivated by viewing the equiripple design of filters in linear time-invariant systems as a process of obtaining optimum minimax filters for a class of bounded energy input signals. The philosophy of designing optimum minimax filters for classes of input signals is extended to multirate systems, which are not time-invariant. We develop a generalized Fourier analysis appropriate for linear periodic systems and use it to derive new error criteria for multirate filter design. Using such criteria yields optimum minimax multirate filters for the input signal class. The utility of our method is demonstrated by using it to analyze several multirate systems. We give numerical results on the design of a multirate implementation of a narrowband filter and compare our work to previous work on multirate filter design. Our numerical analysis is based upon a new formulation of the design as a semi-infinite linear programming problem     

A Sequential Constrained Least-Square Approach to Minimax Design of 2-D FIR Filters

The solution to minimax design of 2-D finite-impulse response filter is not necessarily unique. This paper presents a sequential constrained least-square (SCLS) method to obtain a minimax filter with least total squared error. The method converts the minimax design into a series of constrained least-square problems with the same cost function but different magnitude constraints. By producing the sequence of magnitude error bounds with a binary search, the SCLS method has an exponential convergence rate. Design examples of circular, diamond, and fan filters, and comparison with existing methods show that the SCLS method is efficient and absolutely convergent. The resulted filter is not only a minimax filter but also has least total squared error among minimax filters.     

FIR数字滤波器幅频响应约束最大加权相位误差最小化设计

多数信号滤波应用,对滤波器幅频响应的要求高于相频响应.本文研究了满足幅频响应约束的有限脉冲响应（Infinite Impulse Response,FIR）数字滤波器设计,提出了最大加权相位误差最小化方法.用凸的椭圆误差约束代替非凸的幅值误差约束,将设计问题转化为凸问题;通过与二分技术结合,提出了给定权函数的幅值误差约束最大加权相位误差最小化设计的求解算法.以此算法为核心,构建了迭代重加权最大加权相位误差最小化算法,其中的权函数不再固定,而是基于修改的群延迟误差包络线在迭代中不断更新.权函数收敛后,所得滤波器具有近似等纹波的群延迟误差,最大群延迟误差得到了有效减小.仿真实验表明,与现有相位误差约束最大幅值误差最小化方法相比,得到的FIR滤波器具有更小的最大相位误差和最大群延迟误差.     

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     

Matched median filter for detecting QAM signals

In this paper, the complex matched median filter (MMF) is developed for QAM signal detection. It is shown that the MMF is robust against impulsive type noise. By combining the MMF and the linear matched filter (LMF), an extended class of matched filters is introduced. These filters combine the desirable properties of MMF and LMF and behave well in varying noise environments. Computer simulations demonstrate that the proposed detectors give a much smaller symbol error probability than the LMF when the noise has an impulsive component and produces only a slight performance degradation in the case of pure Gaussian noise     

Optimal 100% Excess Bandwidth Signaling in Cochannel Interference

The problem of transmitter-receiver (T-R) filter design for detection of a binary phase-shift keying signal in asynchronous cochannel interference and Gaussian noise is considered. It is shown that maximum signal-to-interference-plus-noise ratio (SINR) can be achieved only if the T-R filters have a flat spectrum with 100% excess bandwidth. The bit error probability (BEP) performance of a system with the proposed filters is compared to that of a system with conventional root raised-cosine filters both for perfect and imperfect timing recovery cases. It is shown that the proposed filter design is superior to the conventional root raised-cosine filters both in having larger SINR and smaller BEP     

Minimax design of two-channel low-delay perfect-reconstruction FIRfilter banks

The authors deal with the design problem of low-delay perfect-reconstruction filter banks for which the FIR analysis and synthesis filters have equiripple magnitude response. Based on the minimax error criterion, the design problem is formulated in such a manner that the coefficients for the FIR analysis filters can be found by minimising the weighted peak error of the designed analysis filters, subject to the perfect-reconstruction constraints. A design technique based on a modified dual-affine scaling variant of Karmarkar's (1989) algorithm, in conjunction with approximation schemes, is then developed for solving the resulting nonlinear optimisation problem. The effectiveness of the proposed design technique is demonstrated by several simulation examples     

The design of digital all-pass filters using second-order cone programming (SOCP)

This brief proposes a new method for designing digital all-pass filters with a minimax design criterion using second-order cone programming (SOCP). Unlike other all-pass filter design methods, additional linear constraints can be readily incorporated. The overall design problem can be solved through a series of linear programming subproblems and the bisection search algorithm. The convergence of the algorithm is guaranteed. Nonlinear constraints such as the pole radius constraint of the filters can be formulated as additional SOCP constraints using Rouche's theorem. It was found that the pole radius constraint allows an additional tradeoff between the approximation error and the stability margin. The effectiveness of the proposed method is demonstrated by several design examples and comparison with conventional methods.     

Estimation-based synthesis of H∞-optimal adaptive FIR filtersfor filtered-LMS problems

This paper presents a systematic synthesis procedure for H∞-optimal adaptive FIR filters in the context of an active noise cancellation (ANC) problem. An estimation interpretation of the adaptive control problem is introduced first. Based on this interpretation, an H∞ estimation problem is formulated, and its finite horizon prediction (filtering) solution is discussed. The solution minimizes the maximum energy gain from the disturbances to the predicted (filtered) estimation error and serves as the adaptation criterion for the weight vector in the adaptive FIR filter. We refer to this adaptation scheme as estimation-based adaptive filtering (EBAF). We show that the steady-state gain vector in the EBAF algorithm approaches that of the classical (normalized) filtered-X LMS algorithm. The error terms, however, are shown to be different. Thus, these classical algorithms can be considered to be approximations of our algorithm. We examine the performance of the proposed EBAF algorithm (both experimentally and in simulation) in an active noise cancellation problem of a one-dimensional (1-D) acoustic duct for both narrowband and broadband cases. Comparisons to the results from a conventional filtered-LMS (FxLMS) algorithm show faster convergence without compromising steady-state performance and/or robustness of the algorithm to feedback contamination of the reference signal     

Robust Huber adaptive filter

Classical filtering methods are not optimal when the statistics of the signals violate the underlying assumptions behind the theoretical development. Most of the classical filtering theory like least-squares filtering assumes Gaussianity as its underlying distribution. We present a new adaptive filter that is optimal in the presence of Gaussian noise and robust to outliers. This novel robust adaptive filter minimizes the Huber objective function. An estimator based on the Huber objective function behaves as an L₁ norm estimator for large residual errors and as an L₂ norm estimator for small residual errors. Simulation results show the improved performance of the Huber adaptive filter (configured as a line enhancer) over various nonlinear filters in the presence of impulsive noise and Gaussian noise     

A multiscale relaxation algorithm for SNR maximization innonorthogonal subband coding

Develops a technique for improving the applicability of complete, nonorthogonal, multiresolution transforms to image coding. As is well known, the L(2) norm of the quantization errors is not preserved by nonorthogonal transforms, so the L(2) reconstruction error may be unacceptably large. However, given the quantizers and synthesis filters, the authors show that this artifact can be eliminated by formulating the coding problem as that of minimizing the L(2) reconstruction error over the set of possible encoded images. With this new formulation, the coding problem becomes a high-dimensional, discrete optimization problem and features a coupling between the redundancy-removing and quantization operations. A practical solution to the optimization problem is presented in the form of a multiscale relaxation algorithm, using inter- and intrascale quantization noise feedback filters. Bounds on the coding gain over the standard coding technique are derived. A simple extension of the algorithm allows for the use of a weighted L(2) error criterion and deadband (non-MMSE) quantizers. Experiments using biorthogonal spline filter banks demonstrate appreciable SNR gains over the standard coding technique, and comparable visual improvements.     

Minimax design of two-channel nonuniform-division FIR filter banks

The paper deals with the minimax design of two-channel nonuniform-division filter (NDF) banks. Based on a linearisation scheme, the design problem is formulated as an optimisation problem with linear constraints. The authors present a method to design a two-channel NDF bank using a modified dual-affine scaling variant of Karmarkar's (1984) algorithm. This method provides the optimal results that the linear-phase FIR analysis and synthesis filters have equiripple stopband response and the resulting NDF bank also shows equiripple reconstruction error behaviour. The effectiveness of the proposed design technique is demonstrated by several simulation examples     

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.     

Continuous-time envelope-constrained filter design via Laguerrefilters and ℋ∞ optimization methods

The envelope-constrained filtering problem is concerned with the design of a time-invariant filter to process a given input signal such that the noiseless output of the filter is guaranteed to lie within a specified output mask while minimizing the noise gain of the filter. An algorithm is developed to solve the continuous-time envelope-constrained filter design problem with the ℋ_∞ norm of the filter as the cost and an orthonormal set of basis filters. It is shown that the problem can be reformulated and solved as a constrained ℋ _∞ model-matching problem. To illustrate the effectiveness of the design method, two numerical examples are presented that deal with the design of equalization filters for digital transmission channels     

Efficient derivation of the optimal mean-square binary morphological filter from the conditional expectation via a switching algorithm for discrete power-set lattice

Once designed, implementation of an optimal mean-square binary morphological filter is extremely fast, especially when the erosions are implemented on a suitable parallel processor. On the other hand, optimal filter design involes a computationally burdensome search procedure that can, in practice, be intractable. The present paper provides an algorithm for filter design that is based on the relationship between the optimal morphological filter and the conditional expectation. The algorithm proceeds by changing the conditional expectation into a morphological filter while at the same time increasing the mean-square error by a minimal amount. It does so by switching observations between the 1-set and the 0-set of the conditional expectation. The switching algorithm is extremely efficient in many noise environments, and therefore provides a filter design that can be useful for online structuring-element updating. Owing to the relationship between stack and morphological filters, the algorithm is at once useful for finding optimal binary stack filters.     

Multilevel nonlinear filters for edge detection and noisesuppression

Two new classes of multilevel nonlinear filters are introduced for simultaneous edge detection and noise suppression, which the authors call a nested median filter/median averaging filter (NMF/MAF) pair and a delayed decision filter/embedded median trimmed filter (DDF/EMTF) pair. Median filters and median-related filter cause an edge shift in the presence of an impulse near the edge. The proposed filters reduce such edge shifting while suppressing impulsive as well as nonimpulsive noise. It is shown that at the noisy edge point the NMF and the DDF are substantially superior both theoretically and experimentally to the median filter, the α-TM filter, and the STM filter in two respects: (1) the output bias error and (2) the output mean square error. It is also shown that in the noisy homogeneous region (nonedge point), the bias errors of the MAF are zero and the output mean square errors of the MAF are substantially close to those of the optimized single-level filters: the averager, the median filter, and the min-max filter under Gaussian, Laplacian, and uniform noise, respectively. Test results confirm that the NMF/MAF pair and the DDF/EMTF structure are each robust in preserving sharp edges, inhibiting edge shifting, and suppressing a wide variety of noise