Variational Methods in Image and Data Processing


uPotts Denoising a cartoon image using our algorithm for the bivariate piecewise constant Mumford-Shah model.

Free-discontinuity problems and Mumford-Shah type functionals as well as their relatives appear in various applications in image processing, inverse problems,  sparse approximation, compressed sensing, and in data analysis and statistics. In statistics — where their earliest appearence might be tracked back to — they are typically applied for nonparametric regression: a function is fit to data where the noise should be eliminated retaining the relevant information. This is done by minimizing functionals consisting of a data fidelity term and a regularizing term. In (discrete) free-discontinuity problems,  the regularizing term penalizes the number of jumps of the target variable. The continuous multivariate domain analogue is the length of the boundary curve (measured with respect to the outer Haussdorf measure when the path is rough). Further, Mumford-Shah regularizers allows for smooth transitions on the complement of the edge set. Typically, the regularizing terms are nonsmooth and nonconvex which makes treating the corresponding functionals both algorithmically and analytically challenging.

Free-discontinuity problems for directly measured data. Here the central task is denoising and the data term consists of some norm induced distance term between the data and the target variable. For noise with heavier tails, often a L1 data term turns out to be a good choice.

For multivariate free-discontinuity problems we develop  algorithms which is capable of dealing with high-dimensional data. They are based on a combination of suitable ADMM splittings combined with dynamic programming.  The algorithms are, for instance, applicable to multispectral data which are too high dimensional to be processed by conventional methods.


recPotts_7angles Reconstruction from 7 projections; FBP type approach vs. our method.

Free-discontinuity problems for indirectly measured data. The data are often not only noisy, but also indirectly measured. The measurement devise is typically modelled by a potentially nonlinear operator F. In such cases, we consider data terms based on an Lp distance between F(u), where u is the target variable, and the data f. These problems are NP hard even in the univariate setting.

We have developed algorithms processing indirectly measured data as well. The algorithms are generic in the sense that, in order to apply them to a concrete modality, one only has to plug in a solver for the corresponding classical Tikhonov problem which is already available for many measurement devises. This makes the developed algorithm widely applicable. We applied the algorithms to sparsity problems (compressed sensing). Further, we have considered various ill-posed medical imaging problems such as computed tomography, photoacoustic tomography and positron emission tomography. In particular, we were able to reconstruct the Shepp-Logan head phantom from seven (equidistant) projections only.


Mumford-Shah based segmentation of the corpus callosum on real data.

Free-discontinuity problems, TV and higher order problems for manifold valued data. Often data are manifold valued; frequently, this is due to constraints imposed by the model; an example are matrices A with the smooth constraint det A = 1 which amounts to considering SL(n)-valued data. For manifold valued data, the models are defined by exploiting the Riemannian structure of the manifolds.

We have developed algorithms for Mumford-Shah functionals for manifold valued data. We have applied them to diffusion tensor imaging (DTI) as well as Q-ball imaging (QBI). In this context, we encountered the problem of Lp-TV minimization for manifold-valued data. For Lp-TV minimization, we developed algorithms based on cyclic and parallel proximal point algorithms and applied them to different manifolds such as spheres as well as rotation and motion groups which appear in practical applications (SAR data, nonlinear color spaces, pose tracking, …). For Cartan-Hadamard manifolds, we could show that our algorithms converge towards global minimizers of the  Lp-TV functional for any starting point.

We have extended our approach to higher order TV type functionals. Lately, in order to combine the positive effects of TV minimization and of higher order methods, we have defined TGV models for manifold-valued data; we have derived algorithms implementing these models and have applied them for various manifolds to show their potential.


Subdivision schemes and multiscale transforms in nonlinear geometries

Subdivision schemes are used in the area of computer graphics, geometric modeling and geometry processing as well as in scientific computing and in harmonic analysis. In particular, in wavelet analysis, the limit functions of subdivision serve as scaling functions of MRAs. Given data on a discrete grid or a mesh, a subdivision scheme produces an (typically smoother) output function on a refined grid or a refined mesh. Iterating this process produces a sequence of functions defined on increasingly finer grids. This raises the question weather the process convergences to some limit, weather this limit is smooth and what kind of approximation properties it has.

1st subdivision round

Data in the space S2 x Pos3.

1st subdivision round

After one subdivision round.

2nd round

After two subdivision rounds.

3rd round

After three subdivision rounds.


Subdivision schemes in nonlinear geometries. I am interested in subdivision schemes for data with values in manifold M, i.e., data f: V → M. Here I in particular consider the case of irregular combinatorics V. In this context, irregular means that the combinatoric is not even locally the combinatorics of the canonical lattice in the plane. Irregular combinatorics naturally appear in connection with domains of non-zero Euler characteristics: for example, if f approximates a function defined on the sphere S2, the underlying complex should be homeomorphic to S2 which mean that the combinatorics must be irregular. Examples of geometric data are poses of airplanes (Euclidean motion group) or diffusion tensor images (positive matrices). I have defined a new class of geometric subdivision schemes based on intrinsic means which distinguish them from other by keeping a lot of symmetries. From an analytic point of view, I showed C1 smoothness for geometric nonlinear schemes for irregular combinatorics. The strength of the results is comparable with the linear case. I also obtained smoothness results for nonlinear schemes with general dilation matrices for regular as well as irregular combinatorics.

Multiscale transforms in nonlinear geometries. The geometric multiscale transforms introduced by D. Donoho an his collegues employ an interpolatory geometric subdivision scheme as a prediction operator, i.e., the data sitting at, say, the odd integers is estimated by a subdivision operator only seeing the even integer data. The difference (measured in a suitable tangent space) between the estimate and the real data gives the detail at this level of resolution. I defined a related transform for data defined on irregular combinatorics. I was able to characterize the membership in Lipschitz repectively Hölder-Zygmund classes by the coefficient decay with respect to this multiscale transform.


Harmonic analysis of Jacobi translation operators

Visualization of the kernel for the Legendre translation.

Generalized translations appear in the harmonic analysis of symmetric or homogeneous spaces. They are relevant for many stochastic questions involving the convolution of measures or distributions on such spaces. Symmetric and homogeneous spaces are interesting from an application point of view since they are the typical data spaces when dealing with manifold valued data. The major difference to the intuitively well known translation in Euclidean space is that the translated functions are not local in the sense that, at given a point, they only depend on the original function at a corresponding point (respectively, its neighborhood when dealing with Lebesgue spaces.) Instead, it is an average in a certain non-local non-smooth sense. This makes the analysis more involved.

My work in this area deals with the respective homogeneous Banach spaces. These are subspaces invariant under Jacobi translation. In particular, I am interested in Jacobi Lipschitz spaces LipB(α) formed with respect to a (general) homogeneous Banach space B. A function f belongs to the corresponding Lipschitz space whenever the distance between f and its Jacobi translation Txf decays with at least the same speed as (1-x)α when x approaches the neutral element 1. If this decay is faster than (1-x)α, then f belongs to the little Lipschitz space lipB(α). These spaces are related to the spaces of best approximation with respect to the polynomials on the closed interval. My most important contribution to this area is that the bidual of the little Lipschitz space lipB(α) (in the sense of Banach spaces) is isometrically isomorphic to the corresponding big Lipschitz space LipB(α). Furthermore, I could show that these Lipschitz spaces are quasi Banach algebras with respect to pointwise multiplication whenever B has this property.