This paper deals with the analysis of a recent reformulation of the primal-dual hybrid gradient method, which allows one to apply it to nonconvex regularizers. Particularly, it investigates variational problems for which the energy to be minimized can be written as $G(u) + F(Ku)$, where $G$ is convex, $F$ is semiconvex, and $K$ is a linear operator. We study the method and prove convergence in the case where the nonconvexity of $F$ is compensated for by the strong convexity of $G$. The convergence proof yields an interesting requirement for the choice of algorithm parameters, which we show to be not only sufficient, but also necessary. Additionally, we show boundedness of the iterates under much weaker conditions. Finally, in several numerical experiments we demonstrate effectiveness and convergence of the algorithm beyond the theoretical guarantees.

We propose convex relaxations for nonconvex energies on vector-valued functions which are tractable yet as tight as possible. In contrast to existing relaxations, we can handle the combination of nonconvex data terms with coupled regularizers such as $l^2$-regularizers. The key idea is to consider a collection of hypersurfaces with a relaxation that takes into account the entire functional rather than separately treating the data term and the regularizers. We provide a theoretical analysis, detail the implementations for different functionals, present run time and memory requirements, and experimentally demonstrate that the coupled $l^2$-regularizers give systematic improvements regarding denoising, inpainting, and optical flow estimation.

While total variation is among the most popular regularizers for variational problems, its extension to functions with values in a manifold is an open problem. In this paper, we propose the first algorithm to solve such problems which applies to arbitrary Riemannian manifolds. The key idea is to reformulate the variational problem as a multilabel optimization problem with an infinite number of labels. This leads to a hard optimization problem which can be approximately solved using convex relaxation techniques. The framework can be easily adapted to different manifolds including spheres and three-dimensional rotations, and allows to obtain accurate solutions even with a relatively coarse discretization. With numerous examples we demonstrate that the proposed framework can be applied to variational models that incorporate chromaticity values, normal fields, or camera trajectories.

We propose a convex multilabel framework for image sequence segmentation which allows to impose proportion priors on object parts in order to preserve their size ratios across multiple images. The key idea is that for strongly deformable objects such as a gymnast the size ratio of respective regions (head versus torso, legs versus full body, etc.) is typically preserved. We propose different ways to impose such priors in a Bayesian framework for image segmentation. We show that near-optimal solutions can be computed using convex relaxation techniques. Extensive qualitative and quantitative evaluations demonstrate that the proportion priors allow for highly accurate segmentations, avoiding seeping-out of regions and preserving semantically relevant small-scale structures such as hands or feet. They naturally apply to multiple object instances such as players in sports scenes, and they can relate different objects instead of object parts, e.g. organs in medical imaging. The algorithm is efficient and easily parallelized leading to proportion-consistent segmentations at runtimes around one second.

Multilabel problems are of fundamental importance in computer vision and image analysis. Yet, finding global minima of the associated energies is typically a hard computational challenge. Recently, progress has been made by reverting to spatially continuous formulations of respective problems and solving the arising convex relaxation globally. In practice this leads to solutions which are either optimal or within an a posteriori bound of the optimum. Unfortunately, in previous methods, both run time and memory requirements scale linearly in the total number of labels, making these methods very inefficient and often not applicable to problems with higher dimensional label spaces. In this paper, we propose a reduction technique for the case that the label space is a continuous product space and the regularizer is separable, i.e., a sum of regularizers for each dimension of the label space. In typical real-world labeling problems, the resulting convex relaxation requires orders of magnitude less memory and computation time than previous methods. This enables us to apply it to large-scale problems like optic flow, stereo with occlusion detection, segmentation into a very large number of regions, and joint denoising and local noise estimation. Experiments show that despite the drastic gain in performance, we do not arrive at less accurate solutions than the original relaxation. Using the novel method, we can for the first time efficiently compute solutions to the optic flow functional which are within provable bounds (typically 5%) of the global optimum.

We propose the first tractable convex formulation of the vectorial Mumford-Shah functional which allows to compute high-quality solutions independent of the initialization. To this end, we generalize recently introduced convex formulations for scalar functionals to the vector-valued scenario in such a way that discontinuities in the different color channels preferably coincide. Furthermore, we propose an efficient solution which makes the overall optimization problem as tractable as in the scalar-valued case. Numerous experimental comparisons with the naive channel-wise approach, with the well-known Ambrosio-Tortorelli approximation, and with the classical total variation confirm the advantages of the proposed relaxation for contrast-preserving and edge-enhancing regularization.

Several ways to generalize scalar total variation to vector-valued functions have been proposed in the past. In this paper, we give a detailed analysis of a variant we denote by $\text{TV}_J$, which has not been previously explored as a regularizer. The contributions of the manuscript are twofold: on the theoretical side, we show that $\text{TV}_J$ can be derived from the generalized Jacobians from geometric measure theory. Thus, within the context of this theory, $\text{TV}_J$ is the most natural form of a vectorial total variation. As an important feature, we derive how $\text{TV}_J$ can be written as the support functional of a convex set in $\mathcal{L}^2$. This property allows us to employ fast and stable minimization algorithms to solve inverse problems. The analysis also shows that in contrast to other total variation regularizers for color images, the proposed one penalizes across a common edge direction for all channels, which is a major theoretical advantage. Our practical contribution consist of an extensive experimental section, where we compare the performance of a number of provable convergent algorithms for inverse problems with our proposed regularizer. In particular, we show in experiments for denoising, deblurring, superresolution, and inpainting that its use leads to a significantly better restoration of color images, both visually and quantitatively. Source code for all algorithms employed in the experiments is provided online.

We introduce a novel type of total variation regularizer, TVS1, for cyclic structures such as angles or hue values. The method handles the periodicity of values in a simple and consistent way and is invariant to value shifts. The regularizer is integrated in a recent functional lifting framework which allows for arbitrary nonconvex data terms. Results are superior and more natural than with the simple total variation without special care about wrapping interval end points. In addition we propose an equivalent formulation which can be minimized with the same time and memory efficiency as the standard total variation.

We propose a novel framework for imposing label ordering constraints in multilabel optimization. In particular, label jumps can be penalized differently depending on the jump direction. In contrast to the recently proposed MRF-based approaches, the proposed method arises from the viewpoint of spatially continuous optimization. It unifies and generalizes previous approaches to label ordering constraints: Firstly, it provides a common solution to three different problems which are otherwise solved by three separate approaches [4, 10, 14]. We provide an exact characterization of the penalization functions expressible with our approach. Secondly, we show that it naturally extends to three and higher dimensions of the image domain. Thirdly, it allows novel applications, such as the convex shape prior. Despite this generality, our model is easily adjustable to various label layouts and is also easy to implement. On a number of experiments we show that it works quite well, producing solutions comparable and superior to those obtained with previous approaches.

The multi-label problem is of fundamental importance to computer vision, yet finding global minima of the associated energies is very hard and usually impossible in practice. Recently, progress has been made using continuous formulations of the multi-label problem and solving a convex relaxation globally, thereby getting a solution with optimality bounds. In this work, we develop a novel framework for continuous convex relaxations, where the label space is a continuous product space. In this setting, we can combine the memory efficient product relaxation of [9] with the much tighter relaxation of [5], which leads to solutions closer to the global optimum. Furthermore, the new setting allows us to formulate more general continuous regularizers, which can be freely combined in the different label dimensions. We also improve upon the relaxation of the products in the data term of [9], which removes the need for artificial smoothing and allows the use of exact solvers.