Non-convex Regularization

It is well known that certain parabolic PDEs used for the denoising of images can be time discretized by iteratively minimizing a convex variational functional. Important examples are heat flow and total variation flow, which are, respectively, the gradient flows of the squared L2-norm and the L1-norm of the gradient of the image. In case of the mean curvature motion (MCM) and similar morphological filters, the existence of a generating convex variational functional is not known.

In [1] we have derived a non-convex functional with the property that the optimality condition (that is, the associated Euler-Lagrange equation) formally converges to the MCM equation. Moreover, we have provided a rigorous proof of the convergence of the iterated minimizers to the solution of MCM in certain symmetric cases.

The first problem when regarding non-convex variational problems is their well-posedness. In general, one cannot expect the existence of solutions. Therefore it is necessary to consider instead a relaxed problem, which is the lower semi-continuous hull of the original functional with respect to a suitable topology (the weak topology on Sobolev spaces and the weak* topology on BV). It can be shown that, for the functionals we consider, the relaxed functional can be determined by computing the quasiconvex hull of the integrand (see [2] and [3]). The existence of a minimizer for the relaxed problem then follows by standard (direct) methods.

One of the main incentives for finding a variational method generating MCM is that, up to now, MCM can only be treated in the framework of viscosity solutions. Although this theory is very useful for proving existence and uniqueness results for quite general PDEs, it has at least two severe limitations: The first problem is that viscosity solutions in their standard definition are always assumed to be continuous. This is in sharp contrast to widely used imaging models, which assume images to consist of several homogeneous regions (or regions with oscillating patterns) seperated by edges, that is, discontinuities in the intensities. There exist some adaptations of viscosity solutions to certain discontinuous functions, but, again, their applicability is rather limited. The second problem is that no generalization to vector valued data (as seen in colour images) is known. One of the reasons is that comparison principles are a basis of the theory, which can hardly be generalized to higher dimensions. As a consequence, the only way to treat colour images with viscosity solutions is by evolving the different colours separately. No coupled evolution is possible that can preserve common edges of different components of the image.

A main application of non-convex regularization methods is the denoising of images distorted by sampling errors. Filtering of vector valued data is also considered.


Markus Grasmair, Otmar Scherzer



Computational Science Center
Faculty of Mathematics
University of Vienna

Oskar-Morgenstern-Platz 1
1090 Wien
T: +43-1-4277-55771