Objectives and applications

We consider the problem of restoring images degraded by blurring and impulsive noise (e.g. salt-and-pepper noise). It is well known that for such noise models, an ℓ¹ data-fitting term is more robust than standard ℓ² terms, while edges in the image are better preserved by a total variation penalty. The aim is to develop fast methods for solving the resulting non-smooth minimization problem, which can be implemented on graphics processing units (GPUs).

Problem formulation and methods used

Given a blurring operator K, a noisy and blurred pixel-valued image f ∈ ℝ^n×m and α > 0, we wish to find a solution u ∈ ℝ^n×m of the ℓ¹-TV minimization problem

(1)

We introduce for μ > 0 the following splitting of (1):

(2)

and use Fenchel duality to find the dual problem of (2),

This is a quadratic minimization problem with convex constraints, which can be solved efficiently by applying an Arrow-Hurwicz type algorithm. Specifically, the equality constraint is treated via an augmented Lagrangian approach, and the resulting box-constrained saddle point problem is solved using a projected extrapolated gradient algorithm. A continuation strategy for μ → 0 is then used to find an approximate solution of the ℓ¹-TV problem (1).

Results

We show results for denoising (K = I, identity operator) of a 2048 × 2048 scanning transmission electron microscopy (STEM) image of a lingual nerve, where 30% of the data was corrupted by random-valued noise. In a reference MATLAB implementation, the CPU time for the reconstruction was 180 seconds.

(d) true image	(e) noisy image	(f) restoration
(d) true image (detail)	(e) noisy image (detail)	(f) restoration (detail)

Reference: A duality-based splitting method for l1-TV image restoration with automatic regularization parameter choice, submitted (preprint and Matlab code)