Abstract. Motivated by the trade-off between noise robustness and data consistency for joint three-imensional (3D) map reconstruction and rotation estimation in single particle cryogenic-electron microscopy (Cryo-EM), we propose ellipsoidal support lifting (ESL), a measure-based lifting scheme for regularizing and approximating the global minimizer of a smooth function over a Riemannian manifold. Under a uniqueness assumption on the minimizer we show several theoretical results, in particular well-posedness of the method and an error bound due to the induced bias with respect to the global minimizer. Additionally, we use the developed theory to integrate the measure-based lifting scheme into an alternating update method for joint homogeneous 3D map reconstruction and rotation estimation, where typically tens of thousands of manifold-valued minimization problems have to be solved and where regularization is necessary because of the high noise levels in the data. The joint recovery method is used to test both the theoretical predictions and algorithmic performance through numerical experiments with Cryo-EM data. In particular, the induced bias due to the regularizing effect of ESL empirically estimates better rotations, i.e., rotations closer to the ground truth, than global optimization would.

We propose an iterative method for estimating rigid transformations from point sets using adiabatic quantum computation. Compared to existing quantum approaches, our method relies on an adaptive scheme to solve the problem to high precision, and does not suffer from inconsistent rotation matrices. Experimentally, our method performs robustly on several 2D and 3D datasets even with high outlier ratio.

We propose a higher-order method for solving nonsmooth optimization problems on manifolds. To obtain superlinear convergence, we apply a Riemannian semismooth Newton method to a nonsmooth nonlinear primal-dual optimality system based on a recent extension of Fenchel duality theory to Riemannian manifolds. We also propose an inexact version of the Riemannian semismooth Newton method and prove conditions for local linear and superlinear convergence that hold independent of the sign of the curvature. Numerical experiments on $\ell^2$-TV-like problems with dual regularization confirm superlinear convergence on manifolds with positive and negative curvature.

We introduce a class of higher-order anisotropic total variation regularizers, which are defined for possibly inhomogeneous, smooth elliptic anisotropies, that extends the total generalized variation regularizer and its variants. We propose a primal-dual hybrid gradient approach to approximating numerically the associated gradient flow. This choice of regularizers allows us to preserve and enhance intrinsic anisotropic features in images. This is illustrated on various examples from different imaging applications: image denoising, wavelet-based image zooming, and reconstruction of surfaces from scattered height measurements.

We present and analyze an approach to image reconstruction problems with imperfect forward models based on partially ordered spaces---Banach lattices. In this approach, errors in the data and in the forward models are described using order intervals. The method can be characterized as the lattice analogue of the residual method, where the feasible set is defined by linear inequality constraints. The study of this feasible set is the main contribution of this paper. Convexity of this feasible set is examined in several settings, and modifications for introducing additional information about the forward operator are considered. Numerical examples demonstrate the performance of the method in deblurring with errors in the blurring kernel.

We propose a novel spatially continuous framework for convex relaxations based on functional lifting. Our method can be interpreted as a sublabel-accurate solution to multilabel problems. We show that previously proposed functional lifting methods optimize an energy which is linear between two labels and hence require (often infinitely) many labels for a faithful approximation. In contrast, the proposed formulation is based on a piecewise convex approximation and therefore needs far fewer labels - see Fig. 1. In comparison to recent MRF-based approaches, our method is formulated in a spatially continuous setting and shows less grid bias. Moreover, in a local sense, our formulation is the tightest possible convex relaxation. It is easy to implement and allows an efficient primal-dual optimization on GPUs. We show the effectiveness of our approach on several computer vision problems.

In this work we introduce a formulation for a nonlocal Hessian that combines the ideas of higher-order and nonlocal regularization for image restoration, extending the idea of nonlocal gradients to higher-order derivatives. By intelligently choosing the weights, the model allows us to improve on the current state of the art higher-order method, total generalized variation, with respect to overall quality and preservation of jumps in the data. In the spirit of recent work by Brezis et al., our formulation also has analytic implications: for a suitable choice of weights it can be shown to converge to classical second-order regularizers, and in fact it allows a novel characterization of higher-order Sobolev and BV spaces.

We propose the use of the Kantorovich--Rubinstein norm from optimal transport in imaging problems. In particular, we discuss a variational regularization model endowed with a Kantorovich--Rubinstein discrepancy term and total variation regularization in the context of image denoising and cartoon-texture decomposition. We point out connections of this approach to several other recently proposed methods such as total generalized variation and norms capturing oscillating patterns. We also show that the respective optimization problem can be turned into a convex-concave saddle point problem with simple constraints and hence can be solved by standard tools. Numerical examples exhibit interesting features and favorable performance for denoising and cartoon-texture decomposition.

We consider a class of quasi-variational inequalities (QVIs) for adaptive image restoration, where the adaptivity is described via solution-dependent constraint sets. In previous work we studied both theoretical and numerical issues. While we were able to show the existence of solutions for a relatively broad class of problems, we encountered difficulties concerning uniqueness of the solution as well as convergence of existing algorithms for solving QVIs. In particular, it seemed that with increasing image size the growing condition number of the involved differential operator posed severe problems. In the present paper we prove uniqueness for a larger class of problems, particularly independent of the image size. Moreover, we provide a numerical algorithm with proved convergence. Experimental results support our theoretical findings.

Even years ago, Szeliski et al. published an influential study on energy minimization methods for Markov random fields (MRF). This study provided valuable insights in choosing the best optimization technique for certain classes of problems. While these insights remain generally useful today, the phenominal success of random field models means that the kinds of inference problems we solve have changed significantly. Specifically, the models today often include higher order interactions, flexible connectivity structures, large label-spaces of different cardinalities, or learned energy tables. To reflect these changes, we provide a modernized and enlarged study. We present an empirical comparison of 24 state-of-art techniques on a corpus of 2,300 energy minimization instances from 20 diverse computer vision applications. To ensure reproducibility, we evaluate all methods in the OpenGM2 framework and report extensive results regarding runtime and solution quality. Key insights from our study agree with the results of Szeliski et al. for the types of models they studied. However, on new and challenging types of models our findings disagree and suggest that polyhedral methods and integer programming solvers are competitive in terms of runtime and solution quality over a large range of model types.

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 study convex relaxations of the image labeling problem on a continuous domain with regularizers based on metric interaction potentials. The generic framework ensures existence of minimizers and covers a wide range of relaxations of the original combinatorial problem. We focus on two specific relaxations that differ in flexibility and simplicity—one can be used to tightly relax any metric interaction potential, while the other covers only Euclidean metrics but requires less computational effort. For solving the nonsmooth discretized problem, we propose a globally convergent Douglas–Rachford scheme and show that a sequence of dual iterates can be recovered in order to provide a posteriori optimality bounds. In a quantitative comparison to two other first-order methods, the approach shows competitive performance on synthetic and real-world images. By combining the method with an improved rounding technique for nonstandard potentials, we were able to routinely recover integral solutions within $1\%$–$5\%$ of the global optimum for the combinatorial image labeling problem.

We introduce a linearly weighted variant of the total variation for vector fields in order to formulate regularizers for multi-class labeling problems with non-trivial interclass distances. We characterize the possible distances, show that Euclidean distances can be exactly represented, and review some methods to approximate non-Euclidean distances in order to define novel total variation based regularizers. We show that the convex relaxed problem can be efficiently optimized to a prescribed accuracy with optimality certificates using Nesterov's method, and evaluate and compare our approach on several synthetical and real-world examples.