
Efficient MinimalSurface Regularization of Perspective Depth Maps in Variational Stereo











Gottfried Graber, Jonathan Balzer, Stefano Soatto, Thomas Pock
CVPR 2015



We propose a method for dense threedimensional surface reconstruction that leverages the strengths of shapebased approaches, by imposing regularization that respects the geometry of the surface, and the strength of depthmapbased stereo, by avoiding costly computation of surface topology. The result is a near realtime variational reconstruction algorithm free of the staircasing artifacts that affect depthmap and planesweeping approaches. This is made possible by exploiting the gauge ambiguity to design a novel representation of the regularizer that is linear in the parameters and hence amenable to be optimized with stateoftheart primaldual numerical schemes. 
Show Details

Download Paper
(Downloads: 40765)


Bilevel Optimization for Support Vector Machines











Teresa Klatzer
Master's Thesis



This thesis deals with an efficient approach for learning the optimal hyperparameters for Support Vector Machines (SVMs). The common method to determine hyperparameters is grid search. Grid search typically involves the definition of a discretized "grid" of possible parameter values with a certain resolution and a search for the values that result in the minimal validation error of the learned model. A major limitation of grid search is that the search space grows exponentially in the parameters which makes the approach only practical for determining very few hyperparameters. 
Show Details

Download Paper
(Downloads: 37255)


Learning fast and effective image restoration models











Yunjin Chen
PhD Thesis



Up to now, image restoration remains an active research topic, and many new approaches are constantly emerging. However, many newly proposed algorithms achieve the stateoftheart performance, at the expense of computation time. The goal of this thesis is to develop effective image restoration approaches with both high computational efficiency and recovery quality. To that end, we focus on variational models and some related models derived from them, e.g., nonlinear diffusion processes, due to their effectiveness for many generally illposed computer vision problems. Motivated by statistical inference methods, variational methods are among the most successful methods to solve image restoration problems. Variational methods aim to minimize an energy functional which is designed to appropriately describe a specific image restoration problem. Typically, it involves an image prior term (also known as regularizer) and a data fidelity term, which is derived from the observation model. The performance of a variational image restoration model heavily depends on the regularization term. The development of better image regularization techniques has received intensive attention in the past two decades. In this thesis, we concentrate on the socalled Fields of Experts (FoE) image prior model (a trainable filterbased higher order MRFs model), which was firstly proposed by Roth and Black in 2005. We prefer the FoE image prior model for two main reasons. (1) It has been widely investigated in many classic image restoration problems due to its high effectiveness, which is attributed to the explicit modeling of the heavilytailed statistical properties of natural images. (2) The resulting variational model has the additional advantage of high computational efficiency, as it is a local model, and only involves 2D convolution operations of a set of linear filters, alluding to the fact that it is wellsuited for parallel computation such as GPU. We review existing algorithms for the training of the FoE model, and propose a refined lossspecific training scheme. The lossspecific training scheme naturally leads to a bilevel optimization problem. We make use of techniques from bilevel optimization to solve it, where we found it important to we solve the lowerlevel problem in the bilevel framework with very high accuracy. It turns out that our refined training algorithm helps us to arrive a better learned FoE model, which can significantly boost the performance of previous models. We demonstrate that this seemingly negligible modification is very beneficial for the bilevel learning. We build the link between the FoE model and a recently proposed analysis operator learning model, which can be seen as the counterpart of the wellknown synthesis sparse representation based models such as KSVD. We hold the opinion that the commonly addressed analysis prior model, which is usually designed based on image patch rather than the whole image, is a simplified version of the FoE model, at least in the context of image processing. We argue that for the analysis prior modeling, we should turn to the imagebased modeling framework  FoE. Numerical experiments also demonstrate that the imagebased analysis model (e.g., the FoE model) works better than the patchbased ones. We apply the learned image regularizers (e.g., the FoE models) to a variety of classical image restoration problems, including (1) noise reduction with different noise types such as additive Gaussian noise, Nakagami multiplicative noise and impulse noise, (2) JPEG blocky artifacts suppression, (3) image super resolution from a single image or multiple low resolution frames, (4) image deconvolution for blurring images corrupted by certain linear kernels, and (5) image inpainting. The resulting variational models naturally lead to demanding nonconvex optimization problems. We develop a highly efficient nonconvex optimization algorithm, called iPiano to solve all the related problems. For all the investigated applications, the resulting variational models with the learned image regularizers can achieve very good recovery performance on par with stateoftheart algorithms. Moreover, the resulting variational models have an additional advantage of simplicity, and are wellsuited for GPU computation. Though the CPU implementation of our model is slower than some highlyengineered methods, such as BM3D, the GPU implementation is at least one order of magnitude faster than those strong competitors. Motivated by the natural link between the energy functional minimization model and nonlinear diffusion models, we propose to learn optimized nonlinear diffusion models derived from the FoE model regularized energy functional. For this new training model, we obtain additional capacity to train the penalty functions associated with the FoE model, which are fixed to a specific one in the variational framework. Numerical experiments show that due to this additional freedom to tune the penalty functions, we can achieve significantly better results compared to our previous variational models. We investigate two representative image restoration problems, namely Gaussian denoising (a standard test bed to evaluate newly proposed image restoration models) and JPEG deblocking (a nonsmooth problem), which is used to demonstrate the applicability of our proposed training model for nonsmooth problems. We train two specific nonlinear diffusion processes for these two problems. It turns out that we arrive at surprisingly good results which are on par with or even surpass the recent stateofthearts, within 5 diffusion steps. As the resulting diffusion processes only involve few steps (? 5 steps), they are extremely fast. Therefore, the CPU implementation based on Matlab is already faster than some highlyengineered methods, such as BM3D. In addition, the GPU implementation clearly accelerates the diffusion procedure. We find that with the GPU implementation, our approach successfully accomplishes the exploited image restoration problems in less than 1s for the images of size up to 3K x 3K. 

Hide Details

Download Paper
(Downloads: 39322)

Bibtex



Bilevel Optimization with Nonsmooth Lower Level Problems











Peter Ochs, Rene Ranftl, Thomas Brox, Thomas Pock
SSVM 2015 (Preprint)



We consider a bilevel optimization approach for parameter learning in nonsmooth variational models. Existing approaches solve this problem by applying implicit differentiation to a sufficiently smooth approximation of the nondifferentiable lower level problem. We propose an alternative method based on differentiating the iterations of a nonlinear primaldual algorithm. Our method computes exact (sub)gradients and can be applied also in the nonsmooth setting. We show preliminary results for the case of multilabel image segmentation. 
Show Details

Download Paper
(Downloads: 39277)


Continuous Hyperparameter Learning for Support Vector Machines











Teresa Klatzer, Thomas Pock
CVWW 2015



In this paper, we address the problem of determining optimal hyperparameters for support vector machines (SVMs). The standard way for solving the model selection problem is to use grid search. Grid search constitutes an exhaustive search over a predefined discretized set of possible parameter values and evaluating the crossvalidation error until the best is found. We developed a bilevel optimization approach to solve the model selection problem for linear and kernel SVMs, including the extension to learn several kernel parameters. 
Show Details

Download Paper
(Downloads: 38119)


A Remark on Accelerated Block Coordinate Descent for Computing the Proximity Operators of a Sum of Convex Functions











Antonin Chambolle, Thomas Pock
Preprint



We analyze alternating descent algorithms for minimizing the sum of a quadratic function and block separable nonsmooth functions. In case the quadratic interactions between the blocks are pairwise, we show that the schemes can be accelerated, leading to improved convergence rates with respect to related accelerated parallel proximal descent. As an application we obtain very fast algorithms for computing the proximity operator of the 2D and 3D total variation. 
Show Details

Download Paper
(Downloads: 52114)


Scene Flow Estimation from Light Fields via the Preconditioned PrimalDual Algorithm











Stefan Heber, Thomas Pock
GCPR 2014



In this paper we present a novel variational model to jointly estimate geometry and motion from a sequence of light fields captured with a plenoptic camera. The proposed model uses the socalled subaperture representation of the light field. Subaperture images represent images with slightly different viewpoints, which can be extracted from the light field. The subaperture representation allows us to formulate a convex global energy functional, which enforces multiview geometry consistency, ... 
Show Details

Download Paper
(Downloads: 133735)


A Deep Variational Model for Image Segmentation











Rene Ranftl, Thomas Pock
GCPR 2014



In this paper we introduce a novel model that combines Deep Convolutional Neural Networks with a global inference model. Our model is derived from a convex variational relaxation of the minimum st cut problem on graphs, which is frequently used for the task of image segmentation. We treat the outputs of Convolutional Neural Networks as the unary and pairwise potentials of a graph and derive a smooth approximation to the minimum st cut problem. During training, this approximation facilitates the adaptation of the Convolutional Neural Network to the smoothing that is induced by the global model. 
Show Details

Download Paper
(Downloads: 95770)


On the ergodic convergence rates of a firstorder primaldual algorithm











Antonin Chambolle, Thomas Pock
Preprint



We revisit the proofs of convergence for a first order primaldual algorithm for convex optimization which we have studied a few years ago. In particular, we prove rates of convergence for a more general version, with simpler proofs and more complete results.

Show Details

Download Paper
(Downloads: 79217)


A Comparison of Firstorder Algorithms for Machine Learning











Yu Wei, Thomas Pock
OAGM/AAPR Workshop 2014



Using an optimization algorithm to solve a machine learning problem is one of mainstreams in the field of science. In this work, we demonstrate a comprehensive comparison of some stateoftheart firstorder optimization algorithms for convex optimization problems in machine learning. We concentrate on several smooth and nonsmooth machine learning problems with a loss function plus a regularizer. The overall experimental results show the superiority of primaldual algorithms in solving a machine learning problem from the perspectives of the ease to construct, running time and accuracy.

Show Details

Download Paper
(Downloads: 131578)


An iteratively reweighted Algorithm for Nonsmooth Nonconvex Optimization in Computer Vision











Peter Ochs, Alexey Dosovitskiy, Thomas Brox, Thomas Pock
Technical Report



Natural image statistics indicate that we should use nonconvex norms for most regularization tasks in image processing and computer vision. Still, they are rarely used in practice due to the challenge of optimization. Recently, iteratively reweighed \ell_1 minimization (IRL1) has been proposed as a way to tackle a class of nonconvex functions by solving a sequence of convex \ell_2  \ell_1 problems. We extend the problem class to the sum of a convex function and a (nonconvex) nondeceasing function applied to another convex function. 
Show Details

Download Paper
(Downloads: 89877)


iPiasco: Inertial Proximal Algorithm for strongly convex Optimization











Peter Ochs, Thomas Brox, Thomas Pock
Technical Report



In this paper, we present a forwardbackward splitting algorithm with additional inertial term for solving a strongly convex optimization problem of a certain type. The strongly convex objective function is assumed to be a sum of a nonsmooth convex and a smooth convex function. This additional knowledge is used for deriving a convergence rate for the proposed algorithm. It is proved to be an optimal algorithm with linear rate of convergence. For certain problems this linear rate of convergence is better than the provably optimal rate of convergence for smooth strongly convex functions. 
Show Details

Download Paper
(Downloads: 131642)


Maximum Persistency in Energy Minimization











Alexander Shekhovtsov
CVPR 2014



We consider discrete pairwise energy minimization problem (weighted constraint satisfaction, maxsum labeling) and methods that identify a globally optimal partial assignment of variables. When finding a complete optimal assignment is intractable, determining optimal values for a part of variables is an interesting possibility. Existing methods are based on different sufficient conditions. We propose a new sufficient condition for partial optimality... 
Show Details

Download Paper
(Downloads: 134591)


An accelerated forwardbackward algorithm for monotone inclusions











Dirk Lorenz, Thomas Pock
Preprint



In this paper, we propose a new accelerated forward backward splitting algorithm to compute a zero of the sum of two monotone operators, with one of the two operators being cocoercive. The algorithm is inspired by the accelerated gradient method of Nesterov, but can be applied to a much larger class of problems including convexconcave saddle point problems and general monotone inclusions. We prove convergence of the algorithm in a Hilbert space setting and show that several recently proposed firstorder methods can be obtained as special cases of the general algorithm. 
Show Details

Download Paper
(Downloads: 136142)


Insights into analysis operator learning: From patchbased sparse models to higherorder MRFs











Yunjin Chen, Rene Ranftl, Thomas Pock
Preprint



This paper addresses a new learning algorithm for the recently introduced cosparse analysis model. First, we give new insights into the cosparse analysis model by establishing connections to filterbased MRF models, such as the Field of Experts (FoE) model of Roth and Black. For training, we introduce a technique called bilevel optimization to learn the analysis operators. Compared to existing analysis operator learning approaches, our training procedure has the advantage that it is unconstrained with respect to the analysis operator. 
Show Details

Download Paper
(Downloads: 151803)


iPiano: Inertial Proximal Algorithm for NonConvex Optimization











Peter Ochs, Yunjin Chen, Thomas Brox, Thomas Pock
Accepted to SIAM Journal on Imaging Sciences



In this paper we study an algorithm for solving a minimization problem composed of a differentiable (possibly nonconvex) and a convex (possibly nondifferentiable) function. The algorithm combines forwardbackward splitting with an inertial force. A rigorous analysis of the algorithm for the proposed class of problems yields global convergence of the function values and the arguments. This makes the algorithm robust for usage on nonconvex problems. The convergence result is obtained based on the KurdykaLojasiewicz inequality. 
Show Details

Download Paper
(Downloads: 130255)


Revisiting lossspecific training of filterbased MRFs for image restoration











Yunjin Chen, Thomas Pock, Rene Ranftl, Horst Bischof
GCPR 2013



It is now well known that Markov random fields (MRFs) are particularly effective for modeling image priors in lowlevel vision. Recent years have seen the emergence of two main approaches for learning the parameters in MRFs: (1) probabilistic learning using samplingbased algorithms and (2) lossspecific training based on MAP estimate. After investigating existing training approaches, it turns out that the performance of the lossspecific training has been significantly underestimated in existing work. 
Show Details

Download Paper
(Downloads: 150798)


An iterated l1 Algorithm for Nonsmooth Nonconvex Optimization in Computer Vision











Peter Ochs, Alexey Dosovitskiy, Thomas Brox, Thomas Pock
CVPR 2013



Natural image statistics indicate that we should use nonconvex norms for most regularization tasks in image processing and computer vision. Still, they are rarely used in practice due to the challenge to optimize them. Recently, iteratively reweighed l1 minimization has been proposed as a way to tackle a class of nonconvex functions by solving a sequence of convex l2  l1 problems. Here we extend the problem class to linearly constrained optimization of a Lipschitz continuous function, which is the sum of a convex function and a function being concave and increasing on the nonnegative orthant (possibly nonconvex and nonconcave on the whole space). 
Show Details

Download Paper
(Downloads: 222785)


Minimizing TGVbased Variational Models with NonConvex Data Terms











Rene Ranftl, Thomas Pock, Horst Bischof
SSVM 2013



We introduce a method to approximately minimize variational models with Total Generalized Variation regularization (TGV) and nonconvex data
terms. Our approach is based on a decomposition of the functional into two subproblems, which can be both solved globally optimal. Based on this decomposition we derive an iterative algorithm for the approximate minimization of the original nonconvex problem. We apply the proposed algorithm to a stateoftheart stereo model that was previously solved using coarsetofine warping,
where we are able to show significant improvements in terms of accuracy.

Show Details

Download Paper
(Downloads: 188792)


Learning l1based analysis and synthesis sparsity priors using bilevel optimization











Yunjin Chen, Thomas Pock, Horst Bischof
Workshop on Analysis Operator Learning vs. Dictionary Learning, NIPS 2012



We consider the analysis operator and synthesis dictionary learning problems based on the the l1 regularized sparse representation model. We reveal the internal relations between the l1 based analysis model and synthesis model. We then introduce an approach to learn both analysis operator and synthesis dictionary simultaneously by using a unified framework of bilevel optimization. Our aim is to learn a meaningful operator (dictionary) such that the minimum energy solution of the analysis (synthesis)prior based model is as close as possible to the groundtruth. 
Show Details

Download Paper
(Downloads: 198950)


Convex Optimization for Image Segmentation











Markus Unger
Phd Thesis 2012



Segmentation is one of the fundamental low level problems in computer vision. Extracting objects from an image gives rise to further high level processing as well as image composing. A segment not always has to correspond to a real world object, but can fulfill any coherency criterion (e.g. similar motion). Segmentation is a highly ambiguous task, and usually requires some prior knowledge. This can either be obtained by interactive user input in an supervised manner, or completely unsupervised using strong prior knowledge. In this thesis we use continuous energy minimization to tackle all of these problems.

Show Details

Download Paper
(Downloads: 172296)


Approximate Envelope Minimization for Curvature Regularity











Stefan Heber, Rene Ranftl, Thomas Pock
Workshop on HigherOrder Models and Global Constraints in Computer Vision, ECCV 2012



We propose a method for minimizing a nonconvex function, which can be split up into a sum of simple functions. The key idea of the method is the approximation of the convex envelopes of the simple functions, which leads to a convex approximation of the original function. A solution is obtained by minimizing this convex approximation. Cost functions, which fulfill such a splitting property are ubiquitous in computer vision, ...

Show Details

Download Paper
(Downloads: 168579)


Diagonal preconditioning for first order primaldual algorithms in convex optimization











Thomas Pock, Antonin Chambolle
International Conference on Computer Vision (ICCV 2011), To Appear



In this paper we study preconditioning techniques for the firstorder primaldual algorithm proposed in [7]. In particular, we propose simple and easy to compute diagonal preconditioners for which convergence of the algorithm is guaranteed without the need to compute any step size parameters... 
Show Details

Download Paper
(Downloads: 213708)


A firstorder primaldual algorithm for convex problems with applications to imaging











Antonin Chambolle and Thomas Pock
Journal of Mathematical Imaging and Vision



In this paper we study a firstorder primaldual algorithm for convex optimization problems with known saddlepoint structure. We prove convergence to a saddlepoint with rate O(1/N) in finite dimensions, which is optimal for the complete class of nonsmooth problems we are considering in this paper... 
Show Details

Download Paper
(Downloads: 251508)


Total Generalized Variation











Kristian Bredies, Karl Kunisch, Thomas Pock
Accepted to SIIMS



The novel concept of total generalized variation of a function u is introduced and some of its essential properties are proved. Differently from the bounded variation seminorm, the new concept involves higher order derivatives of u. Numerical examples illustrate the high quality of this functional as a regularization term for mathematical imaging problems... 
Show Details

Download Paper
(Downloads: 269265)


Global Solutions of Variational Models with Convex Regularization











Thomas Pock, Daniel Cremers, Horst Bischof, Antonin Chambolle
Accepted to SIIMS



We propose an algorithmic framework to compute global solutions of variational models with convex regularity terms that permit quite arbitrary data terms. While the minimization of variational problems with convex data and regularity terms is straight forward (using for example gradient descent), this is no longer trivial for functionals with nonconvex data terms... 
Show Details

Download Paper
(Downloads: 313562)


An Introduction to Total Variation for Image Analysis











Antonin Chambolle, Vicent Caselles, Matteo Novaga, Daniel Cremers, Thomas Pock
Summer School on "Theoretical Foundations and Numerical Methods for Sparse Recovery", 2009, Linz, Austria



These are the lecture notes of a course taught in Linz in Sept., 2009, at the school "Theoretical Foundations and Numerical Methods for Sparse Recovery", organized by Massimo Fornasier and Ronny Romlau. They address various theoretical and practical topics... 
Show Details

Download Paper
(Downloads: 288071)


Local, Semiglobal, and Global Optimization for Motion Estimation











Werner Trobin
Phd Thesis 2009



Motion cues are an integral part of our visual experience, and therefore it is not surprising that the recovery of motion information from image sequences is a prominent problem in computer vision...

Show Details

Download Paper
(Downloads: 283816)


An Algorithm for Minimizing the MumfordShah Functional











Thomas Pock, Daniel Cremers, Horst Bischof, Antonin Chambolle
International Conference on Computer Vision 2009



In this work we revisit the MumfordShah functional, one of the most studied variational approaches to image segmentation. The contribution of this paper is to propose an algorithm which allows to minimize a convex relaxation of the MumfordShah functional obtained by functional lifting. The algorithm is an efficient primaldual projection algorithm for which we prove convergence. 
Show Details

Download Paper
(Downloads: 339860)


A Convex Relaxation Approach for Computing Minimal Partitions











Thomas Pock, Antonin Chambolle, Daniel Cremers, Horst Bischof
CVPR 2009, Miami, FL



In this work we propose a convex relaxation approach for computing minimal partitions. Our approach is based on rewriting the minimal partition problem (also known as Potts model) in terms of a primal dual Total Variation functional. We show that the Potts prior can be incorporated by means of convex constraints on the dual variables. For minimization we propose an efficient primal dual projected gradient algorithm... 
Show Details

Download Paper
(Downloads: 317539)


A convex approach for computing minimal partitions











Antonin Chambolle, Daniel Cremers, Thomas Pock
Technical Report



We describe a convex relaxation for a family of problems of minimal perimeter partitions. The minimization of the relaxed problem can be tackled numerically, we describe an algorithm and show some results. In most cases, our relaxed problem finds a correct... 
Show Details

Download Paper
(Downloads: 316516)


Continuous Energy Minimization via Repeated Binary Fusion











Werner Trobin, Thomas Pock, Daniel Cremers, Horst Bischof
European Conference on Computer Vision 2008



Variational problems, which are commonly used to solve lowlevel vision tasks, are typically minimized via a local, iterative optimization strategy, e.g. gradient descent. Since every iteration is restricted to a small, local improvement, the overall convergence can be slow... 
Show Details

Download Paper
(Downloads: 351070)


A Convex Formulation of Continuous MultiLabel Problems











Thomas Pock, Thomas Schoenemann, Gottfried Graber, Horst Bischof, Daniel Cremers
European Conference on Computer Vision 2008



We propose a spatially continuous formulation of Ishikawa's discrete multilabel problem.We show that the resulting nonconvex variational problem can be reformulated as a convex variational problem via embedding in a higher dimensional space. 
Show Details

Download Paper
(Downloads: 369874)


Automatic Differentiation for GPUAccelerated 2D/3D Registration











Markus Grabner, Thomas Pock, Tobias Gross, Bernhard Kainz
Proc. 5th International Conference on Automatic Differentiation



We demonstrate the applicability of automatic differentiation (AD) techniques to a class of 2D/3D registration problems which are highly computationally intensive and can therefore greatly benefit from a parallel implementation on recent graphics processing units (GPUs)... 
Show Details

Download Paper
(Downloads: 435431)


Fast and Exact Solution of Total Variation Models on the GPU











Thomas Pock, Markus Unger, Daniel Cremers, Horst Bischof
CVPR 2008, Workshop on Computer Vision on GPUs



This paper discusses fast and accurate methods to solve Total Variation (TV) models on the graphics processing unit (GPU). We review two prominent models incorporating TV regularization and present different algorithms to solve these models... 
Show Details

Download Paper
(Downloads: 395514)


Fast Total Variation for Computer Vision











Thomas Pock
Phd Thesis 2008



Motivated by statistical inference methods, variational methods are among the most successful methods to solve a number of different Computer Vision problems. Variational methods aim to minimize an energy functional... 
Show Details

Download Paper
(Downloads: 512896)


A Duality Based Approach for Realtime TVL1 Optical Flow











Christopher Zach, Thomas Pock, Horst Bischof
DAGM 2007



Energybased methods are highly successful and accurate approaches to calculate the optical flow between images. If discontinuity preservation and robustness against image noise and local illumination changes are required... 
Show Details

Download Paper
(Downloads: 438983)


Realtime Computation of Variational Methods on Graphics Hardware











Thomas Pock, Markus Grabner, Horst Bischof
Computer Vision Winter Workshop 2007



This paper combines two powerful approaches: variational methods and graphics hardware. Variational methods have demonstrated considerable success in computer vision for such diverse tasks as denoising, segmentation, registration, stereo matching... 
Show Details

Download Paper
(Downloads: 425260)

