Introduction to variational image-processing models and applications

Abstract

Variational image-processing models offer high-quality processing capabilities for imaging. They have been widely developed and used in the last two decades, enriching the fields of mathematics as well as information science. Mathematically, several tools are needed: energy optimization, regularization, partial differential equations, level set functions, and numerical algorithms. This special issue presents readers with nine excellent research papers covering topics from research work into variational image-processing models, algorithms and applications, including image denoising, image deblurring, image segmentation, image reconstruction, restoration of mixed noise types and three-dimensional surface restoration.

Keywords:

• image processing
• denoising
• deblurring
• segmentation
• reconstruction
• multiplicative noise
• minimization
• surface fairing

2000 AMS Subject Classifications:

• 68U10
• 74G75
• 65K10
• 65N55
• 74G65

1. Introduction

Through concentration of high-quality papers, journal special issues are served as current frontiers of research in a particular field. However, there are obvious challenges in organizing a special issue. The first one is naturally timing. It might be a miracle to design a project within some requirements, to complete it on time and to get included in such a special issue. The second one is quality. To do this, editors tend to invite and include as many as established and internationally leading groups as possible. Again time constraint may exclude some possible authors and quality papers. The third one is the overall length of the issue which was pre-set by the publisher. With this special issue, we have overcome these challenges and achieved this miracle.

As the guest editor, I feel quite honored to get so many leading researchers’ agreement to contribute to this special issue and to see referees and authors work with set deadlines (regrettably some colleagues could not make the set deadlines to miss out on the issue).

Below I shall first introduce the framework of variational image-processing modelling by using image denoising as an example. For the benefit of graduate students, two specific regularizers (the first one being total variation (TV) based and the second one being mean curvature based) are considered with derivation details given.

Then I shall introduce all the included papers. It is my hope that readers are interested in this special issue and will be able to use International Journal of Computer Mathematics as their future publication medium for publishing new work in this fast growing field.

2. Brief introduction to variational image processing

In variational image processing, an image is viewed as a function whose sampling corresponds to the discrete matrix form of a given image. This simple viewpoint enables us to build into image-processing and modelling useful concepts (such as geometry, shapes and smoothness) of functions, and to achieve sub-pixel level accuracy in processing. So it is not an exaggeration to equate variational image processing to high-resolution image processing.

Since the more recent and pioneering works of Perona-Malik 17, Rudin–Osher–Fatemi 18 (ROF) and Mumfomrd–Shah 15, variational image processing has enjoyed development in an explosively fast speed. We refer readers to the relevant books 6 7 11 14 16,19–22,24 25 for systematic introductions to this exciting field.

Below we briefly discuss the variational denoising model of 18. We consider two specific regularizers and derive the Euler–Lagrange equations for the benefit of graduate students, because this accessible material cannot be found elsewhere in this particular and detailed form.

To proceed, define a given image in domain Ω by z=z(x, y), which is assumed to have additive noise (zero mean Gaussian noise η) present in the model

where the denoising task is to restore u=u(x, y); see 18. Let Γ be the image boundary of Ω. Restoring u from z is an inverse problem, we can use the Tikhonov regularization to ensure uniqueness

where α>0 and denotes some regularizer of u.

2.1. Derivation of the Euler–Lagrange equation for the ROF model

In the ROF model 18, the famous TV semi-norm was proposed (note )

where the Euler–Lagrange (EL) partial differential equation (PDE)

was given in 18 and most other books. Below we give a short derivation.

Denote the integrands by , . Note that for p¬=0, the function admits the Taylor expansion at a=0:

Clearly, with p=½.

Now consider the first variation for with any φ

Consequently, we have for any function φ

Now taking v=φ and in Green's first identity, i.e. , we obtain

Hence, the EL PDE for the ROF model is the famous TV equation

with Neumann's boundary condition .

2.2. Derivation of the Euler–Lagrange equation for the curvature model

The above ROF model (2) locates and preserves edges in u but since the overall image u has a piecewise constant behaviour, for smooth images u, the restored quality is not good. Among the many proposed alternatives, the mean curvature model by 13 28

is one effective method, as efficiently solved by Brito and Chen 4, where the mean curvature . Below we give the derivation for its EL equation, as such details are absent in 4 13 28.

To mimick the above TV equation, set and there should be another condition to be defined. Take any function v=v(x, y) and define

Then we see that

Below we apply Green's first identity for scalar v=v(x, y) and vector . Applying Green's first identity to term 1 of (4), we obtain

Next applying Green's first identity to term 2 of (4), we obtain

since, in isolating ∇ v, we obtain the simplification

Here, we have used the equality

A further step of using Green's first identity leads to

Finally, collecting both terms together, we obtain the EL equation

That is, with the two boundary conditions κ=0, , we have

or the same result in a divergence form

See 4 28 for finite difference discretization schemes.

We remark that, if we do not assume that and , an alterative pair of boundary conditions can be derived for the above PDE as the following .

3. Research papers in this special issue

This special issue collects nine papers, as described below.

Image deblurring. S. Bonettini, G. Landi, E. Loli Piccolomini and L. Zanni (Italy): Scaling techniques for gradient projection-type methods in astronomical image deblurring 2.

The paper compares two gradient projection methods which differ on the scaling matrix choices. Although the methods have been proposed in previous papers, their direct comparison is new. In particular, since both approaches have shown to be very effective on several image restoration problems, such a numerical comparison is of interest in this context. More precisely, the algorithms have been tailored for solving a specific deblurring problem from Poisson data involving the nonnegatively constrained minimization of the Kullback–Leibler (KL) divergence plus the Tikhonov regularization term, which is well suited for the reconstruction of the smooth, diffusive objects often encountered in astronomical imaging. In this context, a stopping criterion is proposed for the considered methods to avoid unnecessary computations while preserving the accuracy of the reconstruction.

Image reconstruction. M. Yan (USA): Convergence analysis of SART: Optimization and statistics 27.

The paper provides an insight into the link between several well-established image reconstruction techniques and in particular performs a convergence analysis for simultaneous algebraic reconstruction technique (SART) methods. Moreover, the paper links the SART method to several other schemes such as Landweber-type schemes, linearized Bregman iteration for the primal, gradient descent for the dual and expectation maximization. The main contribution is a convergence proof for Landweber iterations.

Image deblurring and denoising of multiplicative noise. F. Wang (Hong Kong) and M.K. Ng (Hong Kong and China): A fast minimization method for blur and multiplicative noise removal 26.

This paper proposes a fast and efficient minimization method for the restoration of blurred images corrupted by multiplicative noise. The so-called alternating direction method of multipliers (ADMM) is used to solve the resulting constrained minimization problem. The original constraint set is approximated and then replaced by a corresponding convex set in order to guarantee the convergence of the proposed method. Several numerical tests, including some existing works with several kinds of blurring kernels, are used to illustrate the excellent performance of proposed methods.

Image segmentation. S. Häuser and G. Steidl (Germany): Convex multiclass segmentation with Shearlet regularization 12.

This paper presents a promising approach for image segmentation. The main ingredient of the proposed method is a combination of convex relaxation method and Shearlet regularization. The advantage is that the method can segment texture structures from images.

Image reconstruction. S. Barendt and J. Modersitzki (Germany): A variational model for SPECT reconstruction with a nonlinearly transformed attenuation prototype 1.

In single photon emission computed tomography (SPECT) imaging, an integral equation relates the unknown radioactive tracer density with the observed signal (photon counts). The kernel of the integral operator is dependent upon the attenuation coefficient of the subject being imaged. In practice, the attenuation coefficient is approximated and/or is estimated offline, using an imaging modality such as computed tomography (CT). In this paper, an improved variational model for SPECT reconstruction is presented. The authors propose an algorithm for estimating both the tracer density and the attenuation coefficient. For estimating the tracer density, the authors use an existing non-negatively constrained iterative method, while for the attenuation coefficient, they make the assumption that it is a deformation of a ‘prototype’ attenuation and use image registration to obtain the estimate. The authors first gave a brief review of two reconstruction approaches. Afterwards, the authors proposed the improved SPECT reconstruction model in the variational framework by adding an additional non-negative constraint on the density, followed by a very short description of their numerical techniques in the so-called discretize-optimize framework for solving the associated variational problem.

Image surface restoration. C. Brito-Loeza (Mexico) and K. Chen (UK): Fast iterative algorithms for solving the minimization of curvature-related functionals in surface fairing 5.

Among the effective variational models for processing planar images are the TV model and the mean curvature model. For processing three-dimensional (3D) surfaces, however, minimizing the TV is no longer useful. This paper studies three recently proposed models. In 3D, the amount of numerical computations to solve the minimisation formulation naturally grows up dramatically. Though the need of computationally fast and efficient numerical algorithms able to process high-resolution surfaces is high, much less work has been done in this area. Recently, a two-step algorithm for the fast solution of the total curvature model was introduced in 23. In this paper, we generalise and modify this algorithm to the solution of analogues of the mean curvature model of Droske and Rumpf 9 and the Gaussian curvature model of Elsey and Esed¯glu 10. Numerical experiments are shown to illustrate the good performance of the algorithms

Image denoising with total generalized variation (TGV) K. Bredies (Austria), Y. Dong (Germany) and M. Hintermüller (Germany and Austria): Spatially dependent regularization parameter selection in total generalized variation models for image restoration 3.

This paper considered the parameter selection in the image restoration problem, which can be solved by finding the minimizer of the cost function. In general, the cost function consists of the data fitting, the regularization term and regularization parameter. Recently, the authors considered how to choose the spatially adapted regularization parameter, under the TV regularized model, to obtain better restoration results than a fixed parameter. It is known that the images restored using the TV model suffer from the staircasing effect. The TGV model was proposed to reduce this effect. In this paper, the authors further considered how to select the spatially adapted regularization parameter when TGV was used as the regularization term. Hence, the main contribution in this paper is that the authors extended the parameter selection method from TV model to TGV model.

Image segmentation. W. Zhu, S.H. Kang and G. Biros (USA): A geodesic-active-contour-based variational model for short-axis cardiac-MR image segmentation 29.

In this paper, the authors propose a segmentation method to segment the ventricles. This is a difficult task because the contrast of such datasets are not of great quality (noise, contrast problems and so on) and this is an application of real interest, which is a practical challenge in image segmentation. To do that, the authors propose to use a well-known method (geodesic active contours), and the novelty of this paper consists in the definition of the edge function g _σ. It leads to the use of two level sets in the modelling. Numerical examples are given to illustrate the method.

Image denoising of combined additive and multiplicative noise. N. Chumchob (Thailand), K. Chen (UK) and C. Brito-Loeza (Mexico): A new variational model for removal of combined additive and multiplicative noise and a fast algorithm for its numerical approximation 8.

There has been much progress in denoising either of additive noise or of multiplicative noise. However, this paper proposes some new algorithms for removing a mixture of additive and multiplicative noise. First, a review is given to some literature results. Afterwards, several different algorithms are proposed in the paper. Especially, a special multigrid schemes is given and details on how to implement it are supplied. The tests shown in the paper can demonstrate the advantages of the proposed method.

4. Final remarks

Owning to rapid progress in imaging technology and its increasingly wide use, image-processing research, traditionally done in discrete setting, has attracted the attention of many mathematicians as well as other researchers to study variational models and to tackle emerging challenges during the past two decades. Effective models for automatic recognition, reconstruction and identification of features in images are developed for analysis and applications. International Journal of Computer Mathematics, as a widely accessible journal of computational mathematics and with a long history, wishes to publish more quality papers in this important subject of ‘Variational Image Processing Models and Applications’ from now on. Although the invited and selected papers in this special issue represent a small sample of the vast literature and work done, we hope that the issue will be informative and helpful to research colleagues and young researchers.

I thank all the three editor-in-chiefs of IJCM, Taylor & Francis colleagues, anonymous referees and contributing authors for making this special issue a realty.

Additional information

Notes on contributors

Ke Chen

http://www.liv.ac.uk/cmit