Convergence properties of median and weighted median filters

It has been shown that assuming the first and last value carry-on appending strategy, a finite number of passes of the same median filter to an arbitrary signal of finite length results in a root signal that will be invariant to additional filtering passes. This so-called convergence property is reproven using an extremely simple approach. In addition, the well-known idempotent property (i.e., where convergence is achieved with only one filtering pass) of a recursive median filter is reproven similarly, and the convergence behavior of weighted median filters is studied     

Analysis of two-dimensional center weighted median filters

Center weighted median (CWM) filters, which have been recognized as detail preserving filters, are an important and the simplest subclass of weighted median (WM) filters. In this paper, we analyze the root signals of two-dimensional (2-D) CWM filters. In particular, we derive the required form for a signal to be a root of a 2-D CWM filter. The required form of signals to be roots is then used to evaluate the detail preserving properties of 2-D CWM filters. As examples, the detail preserving properties of some 2-D CWM filters are compared with other detail preserving filters, i.e. multilevel median filters. The generation of binary root signals of some 2-D CWM filters is treated in the term of the smallest surviving object (SSO). It is illustrated by some examples that CWM filters with different orientation of windows can be useful in image segmentation.     

Criteria of convergence of median filters and perturbation theorem

Repeated application of the median filter to any finite length sequence converges to a root in a finite number of passes. This requires padding on each end of the sequence. In some applications, such padding may be inappropriate because of the overemphasis on the endpoints. However, there are some of infinite-length sequences whose median filters are not convergent. In this paper, necessary and/or sufficient conditions on infinite-length sequences are derived in order that their median filters converge to roots of category I. Moreover, we study convergence of median filters of perturbed sequences. The results obtained extend the previous theory on convergence of median filters     

Fast adaptive optimization of weighted vector median filters

Weighted vector median (WVM) filters are effective tools for multichannel signal processing. To obtain the desired filtering behavior and characteristic, the WVM filter weights must be determined in an appropriate manner. In this paper, we first analyze previously defined approaches for WVM filter optimization and show their drawbacks related to derivative computation and vector direction information utilization. Based on this analysis, we propose two fast adaptive algorithms for WVM filter design. Proposed Algorithm I computes locally optimal weight changes at each iteration and updates the filter weights accordingly. This algorithm does not involve derivative computation, thus eliminating the instability caused by derivative approximations utilized in previous approaches. Proposed Algorithm II extends the results from established marginal weighted median optimization methods to the vector case by error metric generalization. Both algorithms can be applied to WVM filters using the L/sub p/ norm, while Algorithm I can operate on more general distance metrics. The presented simulation results show that both algorithms are effective, fast, and stable; they perform well under a wide range of circumstances.     

Recursive weighted median filters admitting negative weights andtheir optimization

A recursive weighted median (RWM) filter structure admitting negative weights is introduced. Much like the sample median is analogous to the sample mean, the proposed class of RWM filters is analogous to the class of infinite impulse response (IIR) linear filters. RWM filters provide advantages over linear IIR filters, offering near perfect “stopband” characteristics and robustness against noise. Unlike linear IIR filters, RWM filters are always stable under the bounded-input bounded-output criterion, regardless of the values taken by the feedback filter weights. RWM filters also offer a number of advantages over their nonrecursive counterparts, including a significant reduction in computational complexity, increased robustness to noise, and the ability to model “resonant” or vibratory behavior. A novel “recursive decoupling” adaptive optimization algorithm for the design of this class of recursive WM filters is also introduced. Several properties of RWM filters are presented, and a number of simulations are included to illustrate the advantages of RWM filters over their nonrecursive counterparts and IIR linear filters     

Deterministic properties of analog median filters

Two key deterministic properties of analog median filters are established. The first is that root signals are characterized by a special class of locally monotone functions, and the second is that the repeated application of a median filter produces a root signal which retains significant features in the original data. Both results are extensions of well known facts for discrete median filters. In addition, it is shown that these properties do not extend to a natural multidimensional version of the median filter     

Quadratic weighted median filters for edge enhancement of noisy images.

Quadratic Volterra filters are effective in image sharpening applications. The linear combination of polynomial terms, however, yields poor performance in noisy environments. Weighted median (WM) filters, in contrast, are well known for their outlier suppression and detail preservation properties. The WM sample selection methodology is naturally extended to the quadratic sample case, yielding a filter structure referred to as quadratic weighted median (QWM) that exploits the higher order statistics of the observed samples while simultaneously being robust to outliers arising in the higher order statistics of environment noise. Through statistical analysis of higher order samples, it is shown that, although the parent Gaussian distribution is light tailed, the higher order terms exhibit heavy-tailed distributions. The optimal combination of terms contributing to a quadratic system, i.e., cross and square, is approached from a maximum likelihood perspective which yields the WM processing of these terms. The proposed QWM filter structure is analyzed through determination of the output variance and breakdown probability. The studies show that the QWM exhibits lower variance and breakdown probability indicating the robustness of the proposed structure. The performance of the QWM filter is tested on constant regions, edges and real images, and compared to its weighted-sum dual, the quadratic Volterra filter. The simulation results show that the proposed method simultaneously suppresses the noise and enhances image details. Compared with the quadratic Volterra sharpener, the QWM filter exhibits superior qualitative and quantitative performance in noisy image sharpening.     

Analysis of weighted median filters based on inequalities relating the weights

By considering all orderings of the input samples, which are discrete-time continuous-valued, it is shown here that a weighted median (WM) filter of spanN can be specified unambiguously by 2^N–1 consistent linear inequalities relating the weights. This specification is identical to that of a self-dual threshold function with the same weights. It is also shown that WM filters with symmetric weights can be specified by ternary threshold functions. Based on these inequalities, properties of WM filters which can be used to check equivalence of some WM filters are derived.This work was supported in part by the National Science Foundation under Grant DCI-8611859. A portion of this work was presented at the IEEE International Symposium on Circuits and Systems, Portland, Oregon, May 1989.     

On the convergence and roots of order-statistics filters

We propose a comprehensive theory of the convergence and characterization of roots of order-statistics filters. Conditions for the convergence of iterations of order-statistics filters are proposed. Criteria for the morphological characterization of roots of order-statistics filters are also proposed     

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     

On the application of averaging median filters in remote sensing

The application of averaging median filters to remote sensing has been investigated, and the results are presented with some discussion and recommendations. Averaging median filters can be considered as a subclass of the standard median filters. For image processing purposes, a two-dimensional window is first filtered by a number of average filters, and the final result of the averaging filters is equal to the median of the central pixel value and the averaging filter results. Applications of this averaging median filter to Landsat images are presented, and the results show that the fine details are preserved while attenuating the impulsing noise     

Deterministic properties of separable and cross median filters with an application to block truncation coding

In this paper, we present some deterministic properties of separable and cross median filters. It is proved that in the absence of vertical binary oscillations, the roots of a separable median filter are included in a subset of root signals of the corresponding cross median filter. Moreover, the sufficient and necessary condition is given for a point to be invariant to cross median filtering. On the root structures of cross median filters, we indicate that there exist three different types of regions based on the one-dimensional features of rows and columns. Finally, an application example is discussed where the roots of separable and cross median filters are used in block truncation coding (BTC) for image compression.     

Adaptive median filters: new algorithms and results

Based on two types of image models corrupted by impulse noise, we propose two new algorithms for adaptive median filters. They have variable window size for removal of impulses while preserving sharpness. The first one, called the ranked-order based adaptive median filter (RAMF), is based on a test for the presence of impulses in the center pixel itself followed by a test for the presence of residual impulses in the median filter output. The second one, called the impulse size based adaptive median filter (SAMF), is based on the detection of the size of the impulse noise. It is shown that the RAMF is superior to the nonlinear mean L(p) filter in removing positive and negative impulses while simultaneously preserving sharpness; the SAMF is superior to Lin's (1988) adaptive scheme because it is simpler with better performance in removing the high density impulsive noise as well as nonimpulsive noise and in preserving the fine details. Simulations on standard images confirm that these algorithms are superior to standard median filters.     

Applications of rank-based median filters in power electronics

A class of robust, rank-based signal processing filters is considered, particularly with regard to its usefulness in the power electronics field. This class of nonlinear filters is characterized by the inclusion of a sorting element in the signal path. The sorting operation allows these filters to suppress impulsive noise while preserving edges and monotonic sections of signals. This introductory work concentrates primarily on the median filter, it being the most accessible filter of the class. A working knowledge of issues arising in design and implementation is developed     

On asymptotic convergence of the dual filters associated with twofamilies of biorthogonal wavelets

The asymptotic behavior of the dual filters associated with biorthogonal spline wavelet (BSW) systems and general biorthogonal Coifman wavelet (GBCW) systems are studied. As the order of the wavelet systems approaches infinity, the magnitude responses of the dual filters in the BSW systems either diverge or converge to some nonideal frequency responses. However, the synthesis filters in the GBCW systems converge to an ideal halfband lowpass filter without exhibiting any Gibbs-like phenomenon, and a subclass of the analysis filters also converge to an ideal halfband lowpass filter but with a one-sided Gibbs-like behavior. The two approximations of the ideal lowpass filter by the filter associated with a Daubechies orthonormal wavelet and by the synthesis filter in a GBCW system of the same order are compared. Such a study of the asymptotic behaviors of wavelet systems provides insightful characterization of these systems and systematic assessment and global comparison of different wavelet systems     

Generalization of median root prior reconstruction

Penalized iterative algorithms for image reconstruction in emission tomography contain conditions on which kind of images are accepted as solutions. The penalty term has commonly been a function of pairwise pixel differences in the activity in a local neighborhood, such that smooth images are favored. Attempts to ensure better edge and detail preservation involve difficult tailoring of parameter values or the penalty function itself. The previously introduced median root prior (MRP) favors locally monotonic images. MRP preserves sharp edges while reducing locally nonmonotonic noise at the same time. Quantitative properties of MRP are good, because differences in the neighboring pixel values are not penalized as such. The median is used as an estimate for a penalty reference, against which the pixel value is compared when setting the penalty. In order to generalize the class of MRP-type of priors, the standard median was replaced by other order statistic operations, the L and finite-impluse-response median hybrid (FMH) filters. They allow for smoother appearance as they apply linear weighting together with robust nonlinear operations. The images reconstructed using the new MRP-L and MRP-FMH priors are visually more conventional. Good quantitative properties of MRP are not significantly altered by the new priors.     

On the convergence properties of the Hopfield model

The main contribution of the present work is showing that the known convergence properties of the Hopfield model can be reduced to a very simple case, for which an elementary proof is provided. The convergence properties of the Hopfield model are dependent on the structure of the interconnections matrix W and the method by which the nodes are updated. Three cases are known: (1) convergence to a stable state when operating in a serial mode with symmetric W; (2) convergence to a cycle of length 2, at most, when operating in a fully parallel mode with symmetric W; and (3) convergence to a cycle of length 4 when operating in a fully parallel mode with antisymmetric W. The three known results are reviewed and it is proven that the fully parallel mode of operation is a special case of the serial model of operation. There are three more cases than can be considered using this characterization: serial mode of operation, antisymmetric W; serial mode of operation, arbitrary W; and fully parallel mode of operation, arbitrary W. By exhibiting exponential lower bounds on the length of the cycles in other cases, it is proven that the three known cases are the only interesting ones     

The design of weighted minimax quadrature mirror filters

A technique for converting the constrained nonlinear optimization problem encountered in the design of weighted minimax quadrature mirror filters into an iterative unconstrained nonlinear optimization problem is presented. This renders the design of weighted minimax quadrature mirror filters possible. The technique is very efficient, typically taking about seven iterations to converge. A rapidly converging iterative procedure for solving the above nonlinear unconstrained optimization problem is also presented. This procedure typically requires less than five iterations to converge     

Complete classification of roots to one-dimensional median andrank-order filters

The set of roots to the one-dimensional median filter is completely determined. Let 2N+1 be the filter window width. It has been shown that if a root contains a monotone segment of length N+1, then it must be locally monotone N+2. For roots with no monotone segment of length N+1, it is proved that the set of such roots is finite, and that each such root is periodic. The methods used are constructive, so given N, one can list all possible roots of this type. The results developed for the median filter also apply to rank-order filters