An efficient algorithm for solving Zakharov-Shabat inversescattering problem

An efficient numerical method for solving Zakharov-Shabat (ZS) inverse scattering problem is presented. In this method, instead of equivalent second-order differential equations to the Gel'fand-Levitan-Marchenko (GLM)-type integral equations, equivalent first-order differential equations are adopted and sufficiently accurate solutions to Zakharov-Shabat inverse problem can be achieved without iterations. Examples for applying it to design nonuniform transmission line (NTL) filters are also provided     

Exact image deconvolution from multiple FIR blurs

We address the problem of restoring an image from its noisy convolutions with two or more blur functions (channels). Deconvolution from multiple blurs is, in general, better conditioned than from a single blur, and can be performed without regularization for moderate noise levels. We characterize the problem of missing data at the image boundaries, and show that perfect reconstruction is impossible (even in the no-noise case) almost surely unless there are at least three channels. Conversely, when there are at least three channels, we show that perfect reconstruction is not only possible almost surely in the absence of noise, but also that it can be accomplished by finite impulse response (FIR) filtering. Such FIR reconstruction is vastly more efficient computationally than the least-squares solution, and is suitable for low noise levels. Even in the high-noise case, the estimates obtained by FIR filtering provide useful starting points for iterative least-squares algorithms. We present results on the minimum possible sizes of such deconvolver filters. We derive expressions for the mean-square errors in the FIR reconstructions, and show that performance comparable to that of the least-squares reconstruction may be obtained with relatively small deconvolver filters. Finally, we demonstrate the FIR reconstruction on synthetic and real data.     

Volterra filter equalization: a fixed point approach

One important application of Volterra filters is the equalization of nonlinear systems. Under certain conditions, this problem can be posed as a fixed point problem involving a contraction mapping. We generalize the previously studied local inverse problem to a very broad class of equalization problems. We also demonstrate that subspace information regarding the response behavior of the Volterra filters can be incorporated to improve the theoretical analysis of equalization algorithms. To this end, a new “windowed” signal norm is introduced. Using this norm, we show that the class of allowable inputs is increased and the upper bounds on the convergence rate are improved when subspace information is exploited     

Nonlinear order statistic filters for image filtering and edge detection

A novel class of nonlinear filters for image processing is proposed. This class is a combination of nonlinear mean and order statistic filters. Median, homomorphic, α-trimmed mean, nonlinear mean, order statistic, and linear filters can be considered as special cases of this class. The properties of these filters in the presence of different kinds of noise are investigated. It is shown that these filters can be used for the reduction of additive white noise, signal-dependent noise, and impulse noise. It is also shown that they preserve edges better than linear filters. Such filters can successfully be used as edge detectors, by appropriate adjustment of some of their parameters. Edge information can be used as an input to these filters to perform in an adaptive manner, changing their behaviour near the edges of an image. It is finally shown that many of the filters proposed have a reasonable (and in certain cases small) computational complexity.     

Limited angle reconstruction using stabilized algorithms

The stability of solutions to the limited-angle tomography reconstruction problem obtained by using the projections-onto-convex-sets (POCS) technique are examined. Although POCS techniques provide a feasible solution to the reconstruction problem, the solution is only one sample from the intersection of the closed convex sets that define the solution space. A method for evaluating the ensemble of possible solution waveforms that are in the neighborhood of a solution is presented. The ensemble characteristics are used to construct an inverse filter which is then applied to the computed solution. The results obtained using this method are less sensitive to noise amplification and are less dependent on both starting data and the number of iterations. An estimate of the object-dependent extrapolation that is possible using either linear or nonlinear constraints is provided.     

Fast algorithms for weighted myriad computation by fixed-pointsearch

This paper develops fast algorithms to compute the output of the weighted myriad filter. Myriad filters form a large and important class of nonlinear filters for robust non-Gaussian signal processing and communications in impulsive noise environments. Just as the weighted mean and the weighted median are optimized for the Gaussian and Laplacian distributions, respectively, the weighted myriad is based on the class of α-stable distributions, which can accurately model impulsive processes. The weighted myriad is an M-estimator that is defined in an implicit manner; no closed-form expression exists for it, and its direct computation is a nontrivial and prohibitively expensive task. In this paper, the weighted myriad is formulated as one of the fixed points of a certain mapping. An iterative algorithm is proposed to compute these fixed points, and its convergence is proved rigorously. Using these fixed point iterations, fast algorithms are developed for the weighted myriad. Numerical simulations demonstrate that these algorithms compute the weighted myriad with a high degree of accuracy at a relatively low computational cost     

Optimal finite impulse response approximate inverse of linear periodic filters

A method to construct an optimal finite impulse response (FIR) approximate inverse for discrete-time causal FIR periodic filters in the presence of measurement noise is proposed. The objective function to be minimised is the sum-of-mean-square errors over one period. On the basis of the matrix impulse response of the multi-input multi-output time-invariant representation of periodic filters, the optimisation problem is formulated as one that minimises the summed equation errors of a set of over-determined linear equations. It is shown that the problem is equivalent to a set of least-squares problems from which a simple, closed-form solution is obtained. Numerical examples are used to illustrate the performance of the proposed FIR approximate inverse.     

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.     

Multidimensional multichannel FIR deconvolution using Gr?bner bases.

We present a new method for general multidimensional multichannel deconvolution with finite impulse response (FIR) convolution and deconvolution filters using Gr?bner bases. Previous work formulates the problem of multichannel FIR deconvolution as the construction of a left inverse of the convolution matrix, which is solved by numerical linear algebra. However, this approach requires the prior information of the support of deconvolution filters. Using algebraic geometry and Gr?bner bases, we find necessary and sufficient conditions for the existence of exact deconvolution FIR filters and propose simple algorithms to find these deconvolution filters. The main contribution of our work is to extend the previous Gr?bner basis results on multidimensional multichannel deconvolution for polynomial or causal filters to general FIR filters. The proposed algorithms obtain a set of FIR deconvolution filters with a small number of nonzero coefficients (a desirable feature in the impulsive noise environment) and do not require the prior information of the support. Moreover, we provide a complete characterization of all exact deconvolution FIR filters, from which good FIR deconvolution filters under the additive white noise environment are found. Simulation results show that our approaches achieve good results under different noise settings.     

Multidimensional Multichannel FIR Deconvolution Using GrÖbner Bases

We present a new method for general multidimensional multichannel deconvolution with finite impulse response (FIR) convolution and deconvolution filters using GrÖbner bases. Previous work formulates the problem of multichannel FIR deconvolution as the construction of a left inverse of the convolution matrix, which is solved by numerical linear algebra. However, this approach requires the prior information of the support of deconvolution filters. Using algebraic geometry and GrÖbner bases, we find necessary and sufficient conditions for the existence of exact deconvolution FIR filters and propose simple algorithms to find these deconvolution filters. The main contribution of our work is to extend the previous GrÖbner basis results on multidimensional multichannel deconvolution for polynomial or causal filters to general FIR filters. The proposed algorithms obtain a set of FIR deconvolution filters with a small number of nonzero coefficients (a desirable feature in the impulsive noise environment) and do not require the prior information of the support. Moreover, we provide a complete characterization of all exact deconvolution FIR filters, from which good FIR deconvolution filters under the additive white noise environment are found. Simulation results show that our approaches achieve good results under different noise settings.     

Blind identification of multichannel FIR blurs and perfect imagerestoration

Despite its practical importance in image processing and computer vision, blind blur identification and blind image restoration have so far been addressed under restrictive assumptions such as all-pole stationary image models blurred by zero or minimum-phase point-spread functions. Relying upon diversity (availability of a sufficient number of multiple blurred images), we develop blind FIR blur identification and order determination schemes. Apart from a minimal persistence of the excitation condition (also present with nonblind setups), the inaccessible input image is allowed to be deterministic or random and of unknown color of distribution. With the blurs satisfying a certain co-primeness condition in addition, we establish existence and uniqueness results which guarantee that single input/multiple-output FIR blurred images can be restored blindly, though perfectly in the absence of noise, using linear FIR filters. Results of simulations employing the blind order determination, blind blur identification, and blind image restoration algorithms are presented. When the SNR is high, direct image restoration is found to yield better results than indirect image restoration which employs the estimated blurs. In low SNR, indirect image restoration performs well while the direct restoration results vary with the delay but improve with larger equalizer orders.     

Optimal approximate inverse of linear periodic filters

We propose a method for constructing optimal causal approximate inverse for discrete-time single-input single-output (SISO) causal periodic filters in the presence of measurement noise. The analysis is based on block signals and multi-input multi-output (MIMO) time-invariant models for periodic filters. The objective function to be minimized is the asymptotic block mean square error. The optimization problem is formulated in terms of transfer matrices as an optimal model-matching problem with nonsquare model and plant. Based on an inner-outer factorization on the transpose of the plant rational matrix, it is shown that the problem can be further reduced to one with a lower dimensional square model and plant, which is then solved in the time-domain, and a closed-form solution is obtained. A lower bound on the objective function is given. It is shown that the lower bound can be asymptotically achieved as the order of the optimal transfer matrix increases. The proposed method is extended to MIMO periodic systems. Numerical examples are used to illustrate the performance of the proposed approximate inverse.     

Nonlinear filtering by threshold decomposition

A new threshold decomposition architecture is introduced to implement stack filters. The architecture is also generalized to a new class of nonlinear filters known as threshold decomposition (TD) filters which are shown to be equivalent to the class of L1-filters under certain conditions. Another new class of filters known as linear and order statistic (LOS) filters result from the intersection of the class of TD and L1-filters. Performance comparisons among several filters are then presented. It was found that TD is compatible with L1, LOS, and linear filters in suppressing Gaussian noise, and is superior in suppressing salt-and-pepper noise. LOS filters, however, provide a better compromise in performance and complexity.     

Internal models and recursive estimation for 2-D isotropic randomfields

Efficient recursive smoothing algorithms are developed for isotropic random fields that can be obtained by passing white noise through rational filters. The estimation problem is shown to be equivalent to a countably infinite set of 1-D separable two-point boundary value smoothing problems. The 1-D smoothing problems are solved using a Markovianization approach followed by a standard 1-D smoothing algorithm. The desired field estimate is then obtained as properly weighted sum of the 1-D smoothed estimates. The 1-D two-point boundary value problems are also shown to have the same asymptotic properties and yield a stable spectral factorization of the power spectrum of the isotropic random fields     

A new class of nonlinear filters-neural filters

A class of nonlinear filters based on threshold decomposition and neural networks is defined. It is shown that these neural filters include all filters defined either by continuous functions, such as linear finite impulse response (FIR) filters, or by Boolean functions, such as generalized stack filters. Adaptive least-mean-absolute-error and adaptive least-mean-square-error algorithms are derived for determining optimal neural filters. As special cases, adaptive generalized stack and adaptive generalized weighted order statistic filtering algorithms under both error criteria are derived. Experimental results in 1D and 2D signal processing are presented to compare the performances of the adaptive neural filters and other widely used filters     

Lagrangian-based methods for finding MAP solutions for MRF models

Finding maximum a posteriori (MAP) solutions from noisy images based on a prior Markov random field (MRF) model is a huge computational task. In this paper, we transform the computational problem into an integer linear programming (ILP) problem. We explore the use of Lagrange relaxation (LR) methods for solving the MAP problem. In particular, three different algorithms based on LR are presented. All the methods are competitive alternatives to the commonly used simulation-based algorithms based on Markov Chain Monte Carlo techniques. In all the examples (including both simulated and real images) that have been tested, the best method essentially finds a MAP solution in a small number of iterations. In addition, LR methods provide lower and upper bounds for the posterior, which makes it possible to evaluate the quality of solutions and to construct a stopping criterion for the algorithm. Although additive Gaussian noise models have been applied, any additive noise model fits into the framework.     

Adaptive algorithms for non-Gaussian noise environments: the orderstatistic least mean square algorithms

Convergence properties are studied for a class of gradient-based adaptive filters known as order statistic least mean square (OSLMS) algorithms. These algorithms apply an order statistic filtering operation to the gradient estimate of the standard least mean square (LMS) algorithm. The order statistic operation in OSLMS algorithms can reduce the variance of the gradient estimate (relative to LMS) when operating in non-Gaussian noise environments. A consequence is that in steady state, the excess mean square error can be reduced. It is shown that when the input signals are iid and symmetrically distributed, the coefficient estimates for the OSLMS algorithms converge on average to a small area around their optimal values. Simulations provide supporting evidence for algorithm convergence. As a measurement of performance, the mean squared coefficient error of OSLMS algorithms has been evaluated under a range of noise distributions and OS operators. Guidelines for selection of the OS operator are presented based on the expected noise environment     

Length- and cost-dependent local minima of unconstrained blindchannel equalizers

Baud-rate linear blind equalizers may converge to undesirable stable equilibria due to different mechanisms. One such mechanism is the use of linear FIR filters as equalizers. It is shown that this type of local minima exist for all unconstrained blind equalizers whose cost functions satisfy two general conditions. The local minima generated by this mechanism are thus called length-dependent local minima. Another mechanism is generated by the cost function adopted by the blind algorithm itself. This type of local minima are called cost-dependent local minima. It is shown that several well-designed algorithms do not have cost-dependent local minimum, whereas other algorithms, such as the decision-directed equalizer and the stop-and-go algorithm (SGA), do. Unlike many existing convergence analysis, the convergence of the Godard (1980) algorithms (GAs) and standard cumulant algorithms (SCAs) under Gaussian noise is also presented. Computer simulations are used to verify the analytical results     

带源个数估计的BPSK信号盲分离算法

目前盲分离研究已有算法众多,但有关数字信号或有限字符集的盲分离研究尚不多见,而带源个数估计的此类盲分离算法更鲜有涉及。针对这类问题,该文提出了一种新颖的BPSK数字信号的盲分离算法,首先由接收到的观测信号的特征,在无噪和有噪情况下分别给出了估计源信号的数目算法;然后再利用观测信号之间的关系估计出混叠矩阵,并在算法中给出了证明。通过估计的混叠矩阵即可恢复得到分离信号,此时得到的分离信号与源信号或者顺序发生了交换,或者产生了符号之间的差别,但并不影响盲分离。最后的仿真结果显示了该文提出的算法在估计混叠矩阵以及最后恢复源信号上都是非常成功,也表明了此算法的可行性和优异性能。     

Blind and Semi-Blind Deblurring of Natural Images

A method for blind image deblurring is presented. The method only makes weak assumptions about the blurring filter and is able to undo a wide variety of blurring degradations. To overcome the ill-posedness of the blind image deblurring problem, the method includes a learning technique which initially focuses on the main edges of the image and gradually takes details into account. A new image prior, which includes a new edge detector, is used. The method is able to handle unconstrained blurs, but also allows the use of constraints or of prior information on the blurring filter, as well as the use of filters defined in a parametric manner. Furthermore, it works in both single-frame and multiframe scenarios. The use of constrained blur models appropriate to the problem at hand, and/or of multiframe scenarios, generally improves the deblurring results. Tests performed on monochrome and color images, with various synthetic and real-life degradations, without and with noise, in single-frame and multiframe scenarios, showed good results, both in subjective terms and in terms of the increase of signal to noise ratio (ISNR) measure. In comparisons with other state of the art methods, our method yields better results, and shows to be applicable to a much wider range of blurs.