Persönlicher Status und Werkzeuge

Home Research Convex Relaxation Methods

Convex Relaxation Methods

Contact: Thomas Möllenhoff, Evgeny Strekalovskiy

A popular and well established paradigm for modeling computer vision problems is through energy minimization. In practice, almost all functionals providing a realistic model are non-convex and even NP-hard. They are thus hard to solve and a direct minimization usually leads to poor local minima.

Convex relaxation methods aim to solve these hard models by approximating the energy functionals by convex ones. The motivation is that they are much easier to solve since any local minimum is automatically a global one. In practice, solutions of the approximating convex functionals lie within a small bound near the actual solutions, or even give exact solutions of the original functionals.

There are numerous applications of convex relaxations methods, including segmentation, 3d reconstruction, denoising, optical flow estimation, deblurring, inpainting and superresolution.

The goals are to find better relaxations for functionals where a relaxation is already available, to establish new convex relaxation techniques applicable for more classes of functionals, and to develop fast and stable minimization algorithms.

Related publications

Sort Order:  by type by year
Book Chapters Journal Articles Conference and Workshop Papers PhD Thesis Other Publications 
Book Chapters
2013
Moment Constraints in Convex Optimization for Segmentation and Tracking (M. Klodt, F. Steinbruecker, D. Cremers), Chapter in Advanced Topics in Computer Vision, Springer, 2013. [bib] [pdf]
2011
Convex Relaxation Techniques for Segmentation, Stereo and Multiview Reconstruction (D. Cremers, T. Pock, K. Kolev, A. Chambolle), Chapter in Markov Random Fields for Vision and Image Processing, MIT Press, 2011. [bib] [pdf]
Book Chapters Journal Articles Conference and Workshop Papers PhD Thesis Other Publications 
Journal Articles
2014
Convex Relaxation of Vectorial Problems with Coupled Regularization (E. Strekalovskiy, A. Chambolle, D. Cremers), In SIAM Journal on Imaging Sciences, volume 7, 2014. [bib] [pdf]
A Super-resolution Framework for High-Accuracy Multiview Reconstruction (B. Goldluecke, M. Aubry, K. Kolev, D. Cremers), In International Journal of Computer Vision, volume 106, 2014. [bib] [pdf]
2013
Tight Convex Relaxations for Vector-Valued Labeling (B. Goldluecke, E. Strekalovskiy, D. Cremers), In SIAM Journal on Imaging Sciences, volume 6, 2013. [bib] [pdf]
A Survey and Comparison of Discrete and Continuous Multi-label Optimization Approaches for the Potts Model (C. Nieuwenhuis, E. Toeppe, D. Cremers), In International Journal of Computer Vision, volume 104, 2013. (Code available) [bib] [pdf]
Spatially Varying Color Distributions for Interactive Multi-Label Segmentation (C. Nieuwenhuis, D. Cremers), In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 35, 2013. (Code available) [bib] [pdf]
2012
Total Cyclic Variation and Generalizations (D. Cremers, E. Strekalovskiy), In Journal of Mathematical Imaging and Vision, volume 47, 2012. [bib] [pdf]
Fast Joint Estimation of Silhouettes and Dense 3D Geometry from Multiple Images (K. Kolev, T. Brox, D. Cremers), In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 34, 2012. [bib] [pdf]
The Natural Total Variation Which Arises from Geometric Measure Theory (B. Goldluecke, E. Strekalovskiy, D. Cremers), In SIAM Journal on Imaging Sciences, volume 5, 2012. [bib] [pdf]
Optimal Solutions for Semantic Image Decomposition (D. Cremers), In Image and Vision Computing, volume 30, 2012. [bib] [pdf]
A Convex Approach to Minimal Partitions (A. Chambolle, D. Cremers, T. Pock), In SIAM Journal on Imaging Sciences, volume 5, 2012. [bib] [pdf]
2011
Multiview Stereo and Silhouette Consistency via Convex Functionals over Convex Domains (D. Cremers, K. Kolev), In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 33, 2011. [bib] [pdf]
2010
Global Solutions of Variational Models with Convex Regularization (T. Pock, D. Cremers, H. Bischof, A. Chambolle), In SIAM Journal on Imaging Sciences, volume 3, 2010. [bib] [pdf]
2009
Continuous Global Optimization in Multiview 3D Reconstruction (K. Kolev, M. Klodt, T. Brox, D. Cremers), In International Journal of Computer Vision, volume 84, 2009. [bib] [pdf]
2003
Binary partitioning, perceptual grouping, and restoration with semidefinite programming (J. Keuchel, C. Schnörr, C. Schellewald, D. Cremers), In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 25, 2003. [bib] [pdf]
Book Chapters Journal Articles Conference and Workshop Papers PhD Thesis Other Publications 
Conference and Workshop Papers
2016
A Convex Solution to Spatially-Regularized Correspondence Problems (T. Windheuser, D. Cremers), In European Conference on Computer Vision (ECCV), 2016. [bib] [pdf]
Sublabel-Accurate Convex Relaxation of Vectorial Multilabel Energies (E. Laude, T. Möllenhoff, M. Moeller, J. Lellmann, D. Cremers), In European Conference on Computer Vision (ECCV), 2016. ([supp] [code]) [bib] [pdf]
Sublabel-Accurate Relaxation of Nonconvex Energies (T. Möllenhoff, E. Laude, M. Moeller, J. Lellmann, D. Cremers), In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016. ([supp] [code]) [bib] [pdf]Oral Presentation, Received the Best Paper Honorable Mention Award at CVPR 2016
2015
Video Segmentation with Just a Few Strokes (N. Nagaraja, F. R. Schmidt, T. Brox), In IEEE International Conference on Computer Vision (ICCV), 2015. [bib] [pdf]
2014
Real-Time Minimization of the Piecewise Smooth Mumford-Shah Functional (E. Strekalovskiy, D. Cremers), In European Conference on Computer Vision (ECCV), 2014. (Code available) [bib] [pdf] [video]
Generalized Connectivity Constraints for Spatio-temporal 3D Reconstruction (M. R. Oswald, J. Stühmer, D. Cremers), In European Conference on Computer Vision (ECCV), 2014. [bib] [pdf] [video]
Co-Sparse Textural Similarity for Interactive Segmentation (C. Nieuwenhuis, S. Hawe, M. Kleinsteuber, D. Cremers), In European Conference on Computer Vision (ECCV), 2014. [bib] [pdf]
Surface Normal Integration for Convex Space-time Multi-view Reconstruction (M. R. Oswald, D. Cremers), In British Machine Vision Conference (BMVC), 2014. [bib] [pdf] [video]
2013
A Convex Relaxation Approach to Space Time Multi-view 3D Reconstruction (M. R. Oswald, D. Cremers), In ICCV Workshop on Dynamic Shape Capture and Analysis (4DMOD), 2013. [bib] [pdf]
Tree Shape Priors with Connectivity Constraints using Convex Relaxation on General Graphs (J. Stühmer, P. Schröder, D. Cremers), In IEEE International Conference on Computer Vision (ICCV), 2013. [bib] [pdf]Oral Presentation
Proportion Priors for Image Sequence Segmentation (C. Nieuwenhuis, E. Strekalovskiy, D. Cremers), In IEEE International Conference on Computer Vision (ICCV), 2013. (oral presentation) [bib] [pdf] [video]
Total Variation Regularization for Functions with Values in a Manifold (J. Lellmann, E. Strekalovskiy, S. Koetter, D. Cremers), In IEEE International Conference on Computer Vision (ICCV), 2013. [bib] [pdf]
Scale-Aware Object Tracking with Convex Shape Constraints on RGB-D Images (M. Klodt, J. Sturm, D. Cremers), In German Conference on Pattern Recognition (GCPR), 2013. [bib] [pdf]
Efficient Convex Optimization for Minimal Partition Problems with Volume Constraints (T. Möllenhoff, C. Nieuwenhuis, E. Toeppe, D. Cremers), In Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), 2013. [bib] [pdf]
Performance Evaluation of Narrow Band Methods for Variational Stereo (F. Stangl, M. Souiai, D. Cremers), In 35th German Conference on Pattern Recognition (GCPR), 2013. [bib] [pdf]
A Co-occurrence Prior for Continuous Multi-Label Optimization (M. Souiai, E. Strekalovskiy, C. Nieuwenhuis, D. Cremers), In Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), 2013. [bib] [pdf]
Volume Constraints for Single View Reconstruction (E. Toeppe, C. Nieuwenhuis, D. Cremers), In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2013. [bib]
2012
Wehrli 2.0: An Algorithm for ”Tidying up Art” (N. Ufer, M. Souiai, D. Cremers), In VISART “Where Computer Vision Meets Art” workshop, ECCV 2012, Springer, 2012. [bib] [pdf]
A Convex Representation for the Vectorial Mumford-Shah Functional (E. Strekalovskiy, A. Chambolle, D. Cremers), In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2012. [bib] [pdf]
Fast and Globally Optimal Single View Reconstruction of Curved Objects (M. R. Oswald, E. Toeppe, D. Cremers), In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2012. [bib] [pdf]
Nonmetric Priors for Continuous Multilabel Optimization (E. Strekalovskiy, C. Nieuwenhuis, D. Cremers), In European Conference on Computer Vision (ECCV), Springer, 2012. [bib] [pdf]
2011
Silhouette-Based Variational Methods for Single View Reconstruction (E. Toeppe, M. R. Oswald, D. Cremers, C. Rother), In Proceedings of the 2010 international conference on Video Processing and Computational Video (D. Cremers, M. A. Magnor, M. R. Oswald, L. Zelnik-Manor, eds.), Springer-Verlag, 2011. [bib] [pdf]
A Convex Framework for Image Segmentation with Moment Constraints (M. Klodt, D. Cremers), In IEEE International Conference on Computer Vision (ICCV), 2011. [bib] [pdf]
Space-Varying Color Distributions for Interactive Multiregion Segmentation: Discrete versus Continuous Approaches (C. Nieuwenhuis, E. Toeppe, D. Cremers), In Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), 2011. [bib] [pdf]
Generalized Ordering Constraints for Multilabel Optimization (E. Strekalovskiy, D. Cremers), In IEEE International Conference on Computer Vision (ICCV), 2011. (oral presentation) [bib] [pdf]
Tight Convex Relaxations for Vector-Valued Labeling Problems (E. Strekalovskiy, B. Goldluecke, D. Cremers), In IEEE International Conference on Computer Vision (ICCV), 2011. [bib] [pdf]
Introducing Total Curvature for Image Processing (B. Goldluecke, D. Cremers), In IEEE International Conference on Computer Vision (ICCV), 2011. [bib] [pdf]
Total Variation for Cyclic Structures: Convex Relaxation and Efficient Minimization (E. Strekalovskiy, D. Cremers), In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2011. [bib] [pdf]
2010
Convex Relaxation for Multilabel Problems with Product Label Spaces (B. Goldluecke, D. Cremers), In European Conference on Computer Vision (ECCV), 2010. [bib] [pdf]
Anisotropic Minimal Surfaces Integrating Photoconsistency and Normal Information for Multiview Stereo (K. Kolev, T. Pock, D. Cremers), In European Conference on Computer Vision (ECCV), 2010. [bib] [pdf]
Image-based 3D Modeling via Cheeger Sets (E. Toeppe, M. R. Oswald, D. Cremers, C. Rother), In Asian Conference on Computer Vision, 2010. [bib] [pdf]Received Honorable Mention Award
2009
An Algorithm for Minimizing the Piecewise Smooth Mumford-Shah Functional (T. Pock, D. Cremers, H. Bischof, A. Chambolle), In IEEE International Conference on Computer Vision (ICCV), 2009. [bib] [pdf]
Continuous Ratio Optimization via Convex Relaxation with Applications to Multiview 3D Reconstruction (K. Kolev, D. Cremers), In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009. [bib] [pdf]
A Convex Relaxation Approach for Computing Minimal Partitions (T. Pock, A. Chambolle, H. Bischof, D. Cremers), In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009. [bib] [pdf]
Non-Parametric Single View Reconstruction of Curved Objects using Convex Optimization (M. R. Oswald, E. Toeppe, K. Kolev, D. Cremers), In Pattern Recognition (Proc. DAGM), 2009. [bib] [pdf]Received a DAGM Paper Award
2008
An Experimental Comparison of Discrete and Continuous Shape Optimization Methods (M. Klodt, T. Schoenemann, K. Kolev, M. Schikora, D. Cremers), In European Conference on Computer Vision (ECCV), 2008. [bib] [pdf]
Integration of Multiview Stereo and Silhouettes via Convex Functionals on Convex Domains (K. Kolev, D. Cremers), In European Conference on Computer Vision (ECCV), 2008. [bib] [pdf]
Continuous Energy Minimization via Repeated Binary Fusion (W. Trobin, T. Pock, D. Cremers, H. Bischof), In European Conference on Computer Vision (ECCV), 2008. [bib] [pdf]
A Convex Formulation of Continuous Multi-Label Problems (T. Pock, T. Schoenemann, G. Graber, H. Bischof, D. Cremers), In European Conference on Computer Vision (ECCV), 2008. [bib] [pdf]
2007
Continuous Global Optimization in Multiview 3D Reconstruction (K. Kolev, M. Klodt, T. Brox, S. Esedoglu, D. Cremers), In Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), Springer, volume 4679, 2007. [bib] [pdf]
Propagated Photoconsistency and Convexity in Variational Multiview 3D Reconstruction (K. Kolev, M. Klodt, T. Brox, D. Cremers), In Workshop on Photometric Analysis for Computer Vision, 2007. [bib] [pdf]
2002
Unsupervised Image Partitioning with Semidefinite Programmifng (J. Keuchel, C. Schnoerr, C. Schellewald, D. Cremers), In Pattern Recognition (L. van Gool, ed.), Springer, volume 2449, 2002. [bib]
2001
Convex Relaxations for Binary Image Partitioning and Perceptual Grouping (J. Keuchel, C. Schellewald, D. Cremers, C. Schnoerr), In Pattern Recognition (B. Radig, S. Florczyk, eds.), Springer, volume 2191, 2001. [bib]Received a DAGM Paper Award
Book Chapters Journal Articles Conference and Workshop Papers PhD Thesis Other Publications 
PhD Thesis
2012
Convexity in Image-Based 3D Surface Reconstruction (K. Kolev), PhD thesis, Department of Computer Science, Technical University Munich, Germany, 2012. [bib] [pdf]
Book Chapters Journal Articles Conference and Workshop Papers PhD Thesis Other Publications 
Other Publications
2013
Label Configuration Priors for Continuous Multi-Label Optimization (M. Souiai, E. Strekalovskiy, C. Nieuwenhuis, D. Cremers), 2013. [bib] [pdf]
2008
A Convex Approach for Computing Minimal Partitions (A. Chambolle, D. Cremers, T. Pock), 2008. [bib] [pdf]
Powered by bibtexbrowser
Export as PDF or BIB

Last edited 25.09.2015 15:46 by Thomas Möllenhoff