Fraction-order total variation blind image restoration based on L1-norm

A fraction-order total variation blind image restoration algorithm based on L1-norm was proposed for restoring the images blurred by unknown point spread function (PSF) during imaging. According to the form of total variation, this paper introduced an arithmetic operator of fraction-order total variation and generated a mathematical model of cost. Semi-quadratic regularization was used to solve the model iteratively so that the solution of this algorithm became easier. This paper also analyzed the convergence of this algorithm and then testified its feasibility in theory. The experimental results showed the proposed algorithm can increase the PSNR of the restored image by 1 dB in relation to the first order total variation blind restoration method and Bayesian blind restoration method. The details in real blurred image were also pretty well restored. The effectiveness of the proposed algorithm revealed that it was practical in the blind image restoration.     

On a class of ill-posed minimization problems in image processing

In this paper, we show that minimization problems involving sublinear regularizing terms are ill-posed, in general, although numerical experiments in image processing give very good results. The energies studied here are inspired by image restoration and image decomposition. Rewriting the nonconvex sublinear regularizing terms as weighted total variations, we give a new approach to perform minimization via the well-known Chambolle's algorithm. The approach developed here provides an alternative to the well-known half-quadratic minimization one.     

A trust region-CG algorithm for deblurring problem in atmospheric image reconstruction

In this paper we solve large scale ill-posed problems, particularly the image restoration problem in atmospheric imaging sciences, by a trust region-CG algorithm. Image restoration involves the removal or minimization of degradation (blur, clutter, noise, etc.) in an image using a priori knowledge about the degradation phenomena. Our basic technique is the so-called trust region method, while the subproblem is solved by the truncated conjugate gradient method, which has been well developed for well-posed problems. The trust region method, due to its robustness in global convergence, seems to be a promising way to deal with ill-posed problems.     

求解两块可分离凸极小化问题的惯性交替方向乘子法

The alternating direction method of multipliers(ADMM)is a widely used method for solving many convex minimization models arising in signal and image processing.In this paper,we propose an inertial ADMM for solving a two-block separable convex minimization problem with linear equality constraints.This algorithm is obtained by making use of the inertial Douglas-Rachford splitting algorithm to the corresponding dual of the primal problem.We study the convergence analysis of the proposed algorithm in infinite-dimensional Hilbert spaces.Furthermore,we apply the proposed algorithm on the robust principal component analysis problem and also compare it with other state-of-the-art algorithms.Numerical results demonstrate the advantage of the proposed algorithm.     

A “Nonconvex+Nonconvex” approach for image restoration with impulse noise removal

In this paper, we propose a new method for image restoration problems, which are degraded by impulsive noise, with nonconvex data fitting term and nonconvex regularizer.The proposed method possesses the advantages of nonconvex data fitting and nonconvex regularizer simultaneously, namely, robustness for impulsive noise and efficiency for restoring neat edge images.Further, we propose an efficient algorithm to solve the “Nonconvex+Nonconvex” structure problem via using the alternating direction minimization, and prove that the algorithm is globally convergent when the regularization parameter is known. However, the regularization parameter is unavailable in general. Thereby, we combine the algorithm with the continuation technique and modified Morozov’s discrepancy principle to get an improved algorithm in which a suitable regularization parameter can be chosen automatically. The experiments reveal the superior performances of the proposed algorithm in comparison with some existing methods.     

A fast alternating minimization algorithm for total variation deblurring without boundary artifacts

Recently, a fast alternating minimization algorithm for total variation image deblurring (FTVd) has been presented by Wang, Yang, Yin, and Zhang (2008) [32]. The method in a nutshell consists of a discrete Fourier transform-based alternating minimization algorithm with periodic boundary conditions and in which two fast Fourier transforms (FFTs) are required per iteration. In this paper, we propose an alternating minimization algorithm for the continuous version of the total variation image deblurring problem. We establish convergence of the proposed continuous alternating minimization algorithm. The continuous setting is very useful to have a unifying representation of the algorithm, independently of the discrete approximation of the deconvolution problem, in particular concerning the strategies for dealing with boundary artifacts. Indeed, an accurate restoration of blurred and noisy images requires a proper treatment of the boundary. A discrete version of our continuous alternating minimization algorithm is obtained following two different strategies: the imposition of appropriate boundary conditions and the enlargement of the domain. The first one is computationally useful in the case of a symmetric blur, while the second one can be efficiently applied for a nonsymmetric blur. Numerical tests show that our algorithm generates higher quality images in comparable running times with respect to the Fast Total Variation deconvolution algorithm.     

Two-Phase Model Algorithm with Global Convergence for Nonlinear Programming

The family of feasible methods for minimization with nonlinear constraints includes the nonlinear projected gradient method, the generalized reduced gradient method (GRG), and many variants of the sequential gradient restoration algorithm (SGRA). Generally speaking, a particular iteration of any of these methods proceeds in two phases. In the restoration phase, feasibility is restored by means of the resolution of an auxiliary nonlinear problem, generally a nonlinear system of equations. In the minimization phase, optimality is improved by means of the consideration of the objective function, or its Lagrangian, on the tangent subspace to the constraints. In this paper, minimal assumptions are stated on the restoration phase and the minimization phase that ensure that the resulting algorithm is globally convergent. The key point is the possibility of comparing two successive nonfeasible iterates by means of a suitable merit function that combines feasibility and optimality. The merit function allows one to work with a high degree of infeasibility at the first iterations of the algorithm. Global convergence is proved and a particular implementation of the model algorithm is described.     

A new trust region algorithm for image restoration

The image restoration problems play an important role in remote sensing and astronomical image analysis. One common method for the recovery of a true image from corrupted or blurred image is the least squares error (LSE) method. But the LSE method is unstable in practical applications. A popular way to overcome instability is the Tikhonov regularization. However, difficulties will encounter when adjusting the so-called regularization parameter a. Moreover, how to truncate the iteration at appropriate steps is also challenging. In this paper we use the trust region method to deal with the image restoration problem, meanwhile, the trust region subproblem is solved by the truncated Lanczos method and the preconditioned truncated Lanczos method. We also develop a fast algorithm for evaluating the Kronecker matrix-vector product when the matrix is banded. The trust region method is very stable and robust, and it has the nice property of updating the trust region automatically. This releases us from tedious fi     

Optimization for Inconsistent Split Feasibility Problems

The split feasibility problem deals with finding a point in a closed convex subset of the domain space of a linear operator such that the image of the point under the linear operator is in a prescribed closed convex subset of the image space. The split feasibility problem and its variants and generalizations have been widely investigated as a means for resolving practical inverse problems in various disciplines. Many iterative algorithms have been proposed for solving the problem. This article discusses a split feasibility problem which does not have a solution, referred to as an inconsistent split feasibility problem. When the closed convex set of the domain space is the absolute set and the closed convex set of the image space is the subsidiary set, it would be reasonable to formulate a compromise solution of the inconsistent split feasibility problem by using a point in the absolute set such that its image of the linear operator is closest to the subsidiary set in terms of the norm. We show that the problem of finding the compromise solution can be expressed as a convex minimization problem over the fixed point set of a nonexpansive mapping and propose an iterative algorithm, with three-term conjugate gradient directions, for solving the minimization problem.     

Convergence analysis of projected gradient descent for Schatten-p nonconvex matrix recovery

The matrix rank minimization problem arises in many engineering applications. As this problem is NP-hard, a nonconvex relaxation of matrix rank minimization, called the Schatten-p quasi-norm minimization(0 p 1), has been developed to approximate the rank function closely. We study the performance of projected gradient descent algorithm for solving the Schatten-p quasi-norm minimization(0 p 1) problem.Based on the matrix restricted isometry property(M-RIP), we give the convergence guarantee and error bound for this algorithm and show that the algorithm is robust to noise with an exponential convergence rate.     

An automatic regularization parameter selection algorithm in the total variation model for image deblurring

Image restoration is an inverse problem that has been widely studied in recent years. The total variation based model by Rudin-Osher-Fatemi (1992) is one of the most effective and well known due to its ability to preserve sharp features in restoration. This paper addresses an important and yet outstanding issue for this model in selection of an optimal regularization parameter, for the case of image deblurring. We propose to compute the optimal regularization parameter along with the restored image in the same variational setting, by considering a Karush Kuhn Tucker (KKT) system. Through establishing analytically the monotonicity result, we can compute this parameter by an iterative algorithm for the KKT system. Such an approach corresponds to solving an equation using discrepancy principle, rather than using discrepancy principle only as a stopping criterion. Numerical experiments show that the algorithm is efficient and effective for image deblurring problems and yet is competitive.     

Convergence of Fixed-Point Continuation Algorithms for Matrix Rank Minimization

The matrix rank minimization problem has applications in many fields, such as system identification, optimal control, low-dimensional embedding, etc. As this problem is NP-hard in general, its convex relaxation, the nuclear norm minimization problem, is often solved instead. Recently, Ma, Goldfarb and Chen proposed a fixed-point continuation algorithm for solving the nuclear norm minimization problem (Math. Program., doi:, 2009). By incorporating an approximate singular value decomposition technique in this algorithm, the solution to the matrix rank minimization problem is usually obtained. In this paper, we study the convergence/recoverability properties of the fixed-point continuation algorithm and its variants for matrix rank minimization. Heuristics for determining the rank of the matrix when its true rank is not known are also proposed. Some of these algorithms are closely related to greedy algorithms in compressed sensing. Numerical results for these algorithms for solving affinely constrained matrix rank minimization problems are reported.     

Kronecker product approximations for image restoration with anti‐reflective boundary conditions

The anti‐reflective boundary condition for image restoration was recently introduced as a mathematically desirable alternative to other boundary conditions presently represented in the literature. It has been shown that, given a centrally symmetric point spread function (PSF), this boundary condition gives rise to a structured blurring matrix, a submatrix of which can be diagonalized by the discrete sine transform (DST), leading to an O(n² log n) solution algorithm for an image of size n × n. In this paper, we obtain a Kronecker product approximation of the general structured blurring matrix that arises under this boundary condition, regardless of symmetry properties of the PSF. We then demonstrate the usefulness and efficiency of our approximation in an SVD‐based restoration algorithm, the computational cost of which would otherwise be prohibitive. Copyright © 2005 John Wiley & Sons, Ltd.     

A special Hermitian and skew-Hermitian splitting method for image restoration

In this paper, we consider an ill-posed image restoration problem with a noise contaminated observation, and a known convolution kernel. A special Hermitian and skew-Hermitian splitting (HSS) iterative method is established for solving the linear systems from image restoration. Our approach is based on an augmented system formulation. The convergence and operation cost of the special HSS iterative method for image restoration problems are discussed. The optimal parameter minimizing the spectral radius of the iteration matrix is derived. We present a detailed algorithm for image restoration problems. Numerical examples are given to demonstrate the performance of the presented method. Finally, the SOR acceleration scheme for the special HSS iterative method is discussed.     

Strong Convergence of a Split Common Fixed Point Problem

In this article, we present a new general algorithm for solving the split common fixed point problem in an infinite dimensional Hilbert space, which is to find a point which belongs to the common fixed point of a family of quasi-nonexpansive mappings such that its image under a linear transformation belongs to the common fixed point of another family of quasi-nonexpansive mappings in the image space. We establish the strong convergence for the algorithm to find a unique solution of the variational inequality, which is the optimality condition for the minimization problem. The algorithm and its convergence results improve and develop previous results in this field.     

Fixed point and Bregman iterative methods for matrix rank minimization

The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm minimization. Although the latter can be cast as a semidefinite programming problem, such an approach is computationally expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving the nuclear norm minimization problem and prove convergence of the first of these algorithms. By using a homotopy approach together with an approximate singular value decomposition procedure, we get a very fast, robust and powerful algorithm, which we call FPCA (Fixed Point Continuation with Approximate SVD), that can solve very large matrix rank minimization problems (the code can be downloaded from http://www.columbia.edu/~sm2756/FPCA.htm for non-commercial use). Our numerical results on randomly generated and real matrix completion problems demonstrate that this algorithm is much faster and provides much better recoverability than semidefinite programming solvers such as SDPT3. For example, our algorithm can recover 1000 × 1000 matrices of rank 50 with a relative error of 10^?5 in about 3?min by sampling only 20% of the elements. We know of no other method that achieves as good recoverability. Numerical experiments on online recommendation, DNA microarray data set and image inpainting problems demonstrate the effectiveness of our algorithms.     

Non-convex and non-smooth variational decomposition for image restoration

The variational image decomposition model decomposes an image into a structural and an oscillatory component by regularization technique and functional minimization. It is an important task in various image processing methods, such as image restoration, image segmentation, and object recognition. In this paper, we propose a non-convex and non-smooth variational decomposition model for image restoration that uses non-convex and non-smooth total variation (TV) to measure the structure component and the negative Sobolev space $H^{-1}$ to model the oscillatory component. The new model combines the advantages of non-convex regularization and weaker-norm texture modeling, and it can well remove the noises while preserving the valuable edges and contours of the image. The iteratively reweighted l¹ (IRL1) algorithm is employed to solve the proposed non-convex minimization problem. For each subproblem, we use the alternating direction method of multipliers (ADMM) algorithm to solve it. Numerical results validate the effectiveness of the proposed model for both synthetic and real images in terms of peak signal-to-noise ratio (PSNR) and mean structural similarity index (MSSIM).     

Quasi-Newton projection methods and the discrepancy principle in image restoration

In this work, the problem of the restoration of images corrupted by space invariant blur and noise is considered. This problem is ill-posed and regularization is required. The image restoration problem is formulated as a nonnegatively constrained minimization problem whose objective function depends on the statistical properties of the noise corrupting the observed image. The cases of Gaussian and Poisson noise are both considered. A Newton-like projection method with early stopping of the iterates is proposed as an iterative regularization method in order to determine a nonnegative approximation to the original image. A suitable approximation of the Hessian of the objective function is proposed for a fast solution of the Newton system. The results of the numerical experiments show the effectiveness of the method in computing a good solution in few iterations, when compared with some methods recently proposed as best performing.     

Level‐based heuristics and hill climbing for the antibandwidth maximization problem

The antibandwidth maximization problem aims to maximize the minimum distance of entries of a sparse symmetric matrix from the diagonal and as such may be regarded as the dual of the well‐known bandwidth minimization problem. In this paper, we consider the feasibility of adapting heuristic algorithms for the bandwidth minimization problem to the antibandwidth maximization problem. In particular, using an inexpensive level‐based heuristic, we obtain an initial ordering that we refine using a hill‐climbing algorithm. This approach performs well on matrices coming from a range of practical problems with an underlying mesh. Comparisons with existing approaches show that, on this class of problems, our algorithm can be competitive with recently reported results in terms of quality while being significantly faster and applicable to much larger problems. Copyright © 2012 John Wiley & Sons, Ltd.     

Data-Driven Tight Frame Construction for Impulsive Noise Removal

The method of data-driven tight frame has been shown very useful in image restoration problems.We consider in this paper extending this important technique,by incorporating L₁ data fidelity into the original data-driven model,for removing impulsive noise which is a very common and basic type of noise in image data.The model contains three variables and can be solved through an efficient iterative alternating minimization algorithm in patch implementation,where the tight frame is dynamically updated.It constructs a tight frame system from the input corrupted image adaptively,and then removes impulsive noise by the derived system.We also show that the sequence generated by our algorithm converges globally to a stationary point of the optimization model.Numerical experiments and comparisons demonstrate that our approach performs well for various kinds of images.This benefits from its data-driven nature and the learned tight frames from input images capture richer image structures adaptively.