Publications in the field of Convex Optimization:



  Efficient Minimal-Surface Regularization of Perspective Depth Maps in Variational Stereo paper       software      
  Gottfried Graber, Jonathan Balzer, Stefano Soatto, Thomas Pock       CVPR 2015  
paper We propose a method for dense three-dimensional surface reconstruction that leverages the strengths of shapebased approaches, by imposing regularization that respects the geometry of the surface, and the strength of depthmap-based stereo, by avoiding costly computation of surface topology. The result is a near real-time variational reconstruction algorithm free of the staircasing artifacts that affect depth-map and plane-sweeping 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 state-of-the-art primal-dual numerical schemes.
Show Details Download Paper   (Downloads: 40765)
  Bi-level Optimization for Support Vector Machines paper              
  Teresa Klatzer       Master's Thesis  
paper This thesis deals with an efficient approach for learning the optimal hyper-parameters for Support Vector Machines (SVMs). The common method to determine hyper-parameters 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 hyper-parameters.
Show Details Download Paper   (Downloads: 37255)
  Learning fast and effective image restoration models paper              
  Yunjin Chen       PhD Thesis  
paper Up to now, image restoration remains an active research topic, and many new approaches are constantly emerging. However, many newly proposed algorithms achieve the state-of-the-art 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 ill-posed computer vision problems...
Show Details Download Paper   (Downloads: 39322)
  Bilevel Optimization with Nonsmooth Lower Level Problems paper              
  Peter Ochs, Rene Ranftl, Thomas Brox, Thomas Pock       SSVM 2015 (Preprint)  
paper 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 primal-dual algorithm. Our method computes exact (sub)gradients and can be applied also in the nonsmooth setting. We show preliminary results for the case of multi-label image segmentation.
Show Details Download Paper   (Downloads: 39277)
  Continuous Hyper-parameter Learning for Support Vector Machines paper              
  Teresa Klatzer, Thomas Pock       CVWW 2015  
paper In this paper, we address the problem of determining optimal hyper-parameters 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 pre-defined discretized set of possible parameter values and evaluating the cross-validation error until the best is found. We developed a bi-level opti-mization 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 paper              
  Antonin Chambolle, Thomas Pock       Preprint  
paper We analyze alternating descent algorithms for minimizing the sum of a quadratic function and block separable non-smooth 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 Primal-Dual Algorithm paper              
  Stefan Heber, Thomas Pock       GCPR 2014  
paper 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 so-called sub-aperture representation of the light field. Sub-aperture images represent images with slightly different viewpoints, which can be extracted from the light field. The sub-aperture representation allows us to formulate a convex global energy functional, which enforces multi-view geometry consistency, ...
Show Details Download Paper   (Downloads: 133735)
  A Deep Variational Model for Image Segmentation paper           links  
  Rene Ranftl, Thomas Pock       GCPR 2014  
paper 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 s-t 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 s-t 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 first-order primal-dual algorithm paper              
  Antonin Chambolle, Thomas Pock       Preprint  
paper We revisit the proofs of convergence for a first order primal-dual 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 First-order Algorithms for Machine Learning paper       software      
  Yu Wei, Thomas Pock       OAGM/AAPR Workshop 2014  
paper 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 state-of-the-art first-order optimization algorithms for convex optimization problems in machine learning. We concentrate on several smooth and non-smooth machine learning problems with a loss function plus a regularizer. The overall experimental results show the superiority of primal-dual 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 Non-smooth Non-convex Optimization in Computer Vision paper              
  Peter Ochs, Alexey Dosovitskiy, Thomas Brox, Thomas Pock       Technical Report  
paper Natural image statistics indicate that we should use non-convex 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 non-convex 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 (non-convex) non-deceasing function applied to another convex function.
Show Details Download Paper   (Downloads: 89877)
  iPiasco: Inertial Proximal Algorithm for strongly convex Optimization paper              
  Peter Ochs, Thomas Brox, Thomas Pock       Technical Report  
paper In this paper, we present a forward-backward 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 non-smooth 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 paper           links  
  Alexander Shekhovtsov       CVPR 2014  
paper We consider discrete pairwise energy minimization problem (weighted constraint satisfaction, max-sum 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 forward-backward algorithm for monotone inclusions paper              
  Dirk Lorenz, Thomas Pock       Preprint  
paper 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 co-coercive. The algorithm is inspired by the accelerated gradient method of Nesterov, but can be applied to a much larger class of problems including convex-concave saddle point problems and general monotone inclusions. We prove convergence of the algorithm in a Hilbert space setting and show that several recently proposed first-order methods can be obtained as special cases of the general algorithm.
Show Details Download Paper   (Downloads: 136142)
  Insights into analysis operator learning: From patch-based sparse models to higher-order MRFs paper       software      
  Yunjin Chen, Rene Ranftl, Thomas Pock       Preprint  
paper This paper addresses a new learning algorithm for the recently introduced co-sparse analysis model. First, we give new insights into the co-sparse analysis model by establishing connections to filter-based MRF models, such as the Field of Experts (FoE) model of Roth and Black. For training, we introduce a technique called bi-level 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 Non-Convex Optimization paper              
  Peter Ochs, Yunjin Chen, Thomas Brox, Thomas Pock       Accepted to SIAM Journal on Imaging Sciences  
paper In this paper we study an algorithm for solving a minimization problem composed of a differentiable (possibly non-convex) and a convex (possibly non-differentiable) function. The algorithm combines forward-backward 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 non-convex problems. The convergence result is obtained based on the Kurdyka-Lojasiewicz inequality.
Show Details Download Paper   (Downloads: 130255)
  Revisiting loss-specific training of filter-based MRFs for image restoration paper       software      
  Yunjin Chen, Thomas Pock, Rene Ranftl, Horst Bischof       GCPR 2013  
paper It is now well known that Markov random fields (MRFs) are particularly effective for modeling image priors in low-level vision. Recent years have seen the emergence of two main approaches for learning the parameters in MRFs: (1) probabilistic learning using sampling-based algorithms and (2) loss-specific training based on MAP estimate. After investigating existing training approaches, it turns out that the performance of the loss-specific training has been significantly underestimated in existing work.
Show Details Download Paper   (Downloads: 150798)
  An iterated l1 Algorithm for Non-smooth Non-convex Optimization in Computer Vision paper              
  Peter Ochs, Alexey Dosovitskiy, Thomas Brox, Thomas Pock       CVPR 2013  
paper Natural image statistics indicate that we should use non-convex 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 non-convex 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 non-negative orthant (possibly non-convex and non-concave on the whole space).
Show Details Download Paper   (Downloads: 222785)
  Minimizing TGV-based Variational Models with Non-Convex Data Terms paper              
  Rene Ranftl, Thomas Pock, Horst Bischof       SSVM 2013  
paper We introduce a method to approximately minimize variational models with Total Generalized Variation regularization (TGV) and non-convex 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 non-convex problem. We apply the proposed algorithm to a state-of-the-art stereo model that was previously solved using coarse-to-fine warping, where we are able to show significant improvements in terms of accuracy.
Show Details Download Paper   (Downloads: 188792)


  Learning l1-based analysis and synthesis sparsity priors using bi-level optimization paper              
  Yunjin Chen, Thomas Pock, Horst Bischof       Workshop on Analysis Operator Learning vs. Dictionary Learning, NIPS 2012  
paper 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 bi-level 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 paper              
  Markus Unger       Phd Thesis 2012  
paper 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. Continuous energy minimization provides an elegant way to model a problem like image segmentation. If the problem is convex, there are powerful optimization algorithms available. Additionally, we are guaranteed to find the globally optimal solution. We give an extensive introduction to convex optimization methods in computer vision. A great part of this thesis is devoted to basic image segmentation. We investigate the continuous maximum flow model for the two label segmentation, as well as optimization problems for multi-label segmentation. To obtain good segmentation results in a reasonable time, it is important that the energy, optimization algorithm and implementation are perfectly matched. For non-smooth convex optimization problems, primal-dual optimization methods deliver very good convergence rates. Furthermore, they are inherently parallel, and therefore perfectly suited for modern parallel hardware like graphics processors. While we achieve good results with existing optimization methods, we also demonstrate how to further speed up convergence for some specific energies. We have to keep all this in mind during the design of the energy. As a result this thesis tackles the whole process from designing an energy minimization problem, over the algorithmic optimization to the final implementation on the GPU. Apart from the general segmentation algorithms, we also show four different applications: First, interactive color image segmentation, where the developed segmentation models are applied. Second, tracking as segmentation of spatio-temporal volumes. In this case a video is interpreted as a volume, and objects are segmented in a semi-supervised manner. Third, we develop an unsupervised approach for segmenting 2.5D depth images. Finally, we present an approach for joint motion estimation, segmentation and occlusion handling.
Hide Details Download Paper   (Downloads: 172296) Bibtex
  Approximate Envelope Minimization for Curvature Regularity paper              
  Stefan Heber, Rene Ranftl, Thomas Pock       Workshop on Higher-Order Models and Global Constraints in Computer Vision, ECCV 2012  
paper We propose a method for minimizing a non-convex 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 primal-dual algorithms in convex optimization paper              
  Thomas Pock, Antonin Chambolle       International Conference on Computer Vision (ICCV 2011), To Appear  
paper In this paper we study preconditioning techniques for the first-order primal-dual 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 fi rst-order primal-dual algorithm for convex problems with applications to imaging paper              
  Antonin Chambolle and Thomas Pock       Journal of Mathematical Imaging and Vision  
paper In this paper we study a first-order primal-dual algorithm for convex optimization problems with known saddle-point structure. We prove convergence to a saddle-point with rate O(1/N) in finite dimensions, which is optimal for the complete class of non-smooth problems we are considering in this paper...
Show Details Download Paper   (Downloads: 251508)
  Total Generalized Variation paper              
  Kristian Bredies, Karl Kunisch, Thomas Pock       Accepted to SIIMS  
paper 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 semi-norm, 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 paper              
  Thomas Pock, Daniel Cremers, Horst Bischof, Antonin Chambolle       Accepted to SIIMS  
paper 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 non-convex data terms...
Show Details Download Paper   (Downloads: 313562)


  An Introduction to Total Variation for Image Analysis paper           links  
  Antonin Chambolle, Vicent Caselles, Matteo Novaga, Daniel Cremers, Thomas Pock       Summer School on "Theoretical Foundations and Numerical Methods for Sparse Recovery", 2009, Linz, Austria  
paper 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, Semi-global, and Global Optimization for Motion Estimation paper              
  Werner Trobin       Phd Thesis 2009  
paper 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 Mumford-Shah Functional paper              
  Thomas Pock, Daniel Cremers, Horst Bischof, Antonin Chambolle       International Conference on Computer Vision 2009  
paper In this work we revisit the Mumford-Shah 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 Mumford-Shah functional obtained by functional lifting. The algorithm is an efficient primal-dual projection algorithm for which we prove convergence.
Show Details Download Paper   (Downloads: 339860)
  A Convex Relaxation Approach for Computing Minimal Partitions paper              
  Thomas Pock, Antonin Chambolle, Daniel Cremers, Horst Bischof       CVPR 2009, Miami, FL  
paper 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 paper              
  Antonin Chambolle, Daniel Cremers, Thomas Pock       Technical Report  
paper 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 paper              
  Werner Trobin, Thomas Pock, Daniel Cremers, Horst Bischof       European Conference on Computer Vision 2008  
paper 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 Multi-Label Problems paper              
  Thomas Pock, Thomas Schoenemann, Gottfried Graber, Horst Bischof, Daniel Cremers       European Conference on Computer Vision 2008  
paper We propose a spatially continuous formulation of Ishikawa's discrete multi-label problem.We show that the resulting non-convex 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 GPU-Accelerated 2D/3D Registration paper              
  Markus Grabner, Thomas Pock, Tobias Gross, Bernhard Kainz       Proc. 5th International Conference on Automatic Differentiation  
paper 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 paper              
  Thomas Pock, Markus Unger, Daniel Cremers, Horst Bischof       CVPR 2008, Workshop on Computer Vision on GPUs  
paper 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 paper              
  Thomas Pock       Phd Thesis 2008  
paper 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 TV-L1 Optical Flow paper              
  Christopher Zach, Thomas Pock, Horst Bischof       DAGM 2007  
paper Energy-based 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)
  Real-time Computation of Variational Methods on Graphics Hardware paper              
  Thomas Pock, Markus Grabner, Horst Bischof       Computer Vision Winter Workshop 2007  
paper 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)