Login
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
Export as PDF, XML, TEX or BIB
Book Chapters | Journal Articles | Conference and Workshop Papers | PhD Thesis | Technical Reports
Book Chapters
2013
[] 
Moment Constraints in Convex Optimization for Segmentation and Tracking , Chapter in Advanced Topics in Computer Vision, Springer, 2013.
2011
[] 
Convex Relaxation Techniques for Segmentation, Stereo and Multiview Reconstruction , Chapter in Markov Random Fields for Vision and Image Processing, MIT Press, 2011.
Book Chapters | Journal Articles | Conference and Workshop Papers | PhD Thesis | Technical Reports
Journal Articles
2014
[] 
Convex Relaxation of Vectorial Problems with Coupled Regularization , In SIAM Journal on Imaging Sciences, volume 7, 2014.
[] 
A Super-resolution Framework for High-Accuracy Multiview Reconstruction , In International Journal of Computer Vision, volume 106, 2014.
2013
[] 
Tight Convex Relaxations for Vector-Valued Labeling , In SIAM Journal on Imaging Sciences, volume 6, 2013.
[] 
A Survey and Comparison of Discrete and Continuous Multi-label Optimization Approaches for the Potts Model , In International Journal of Computer Vision, volume 104, 2013. (Code available)
[] 
Spatially Varying Color Distributions for Interactive Multi-Label Segmentation , In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 35, 2013. (Code available)
2012
[] 
Total Cyclic Variation and Generalizations , In Journal of Mathematical Imaging and Vision, volume 47, 2012.
[] 
Fast Joint Estimation of Silhouettes and Dense 3D Geometry from Multiple Images , In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 34, 2012.
[] 
The Natural Total Variation Which Arises from Geometric Measure Theory , In SIAM Journal on Imaging Sciences, volume 5, 2012.
[] 
Optimal Solutions for Semantic Image Decomposition , In Image and Vision Computing, volume 30, 2012.
[] 
A Convex Approach to Minimal Partitions , In SIAM Journal on Imaging Sciences, volume 5, 2012.
2011
[] 
Multiview Stereo and Silhouette Consistency via Convex Functionals over Convex Domains , In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 33, 2011.
2010
[] 
Global Solutions of Variational Models with Convex Regularization , In SIAM Journal on Imaging Sciences, volume 3, 2010.
2009
[] 
Continuous Global Optimization in Multiview 3D Reconstruction , In International Journal of Computer Vision, volume 84, 2009.
2003
[] 
Binary partitioning, perceptual grouping, and restoration with semidefinite programming , In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 25, 2003.
Book Chapters | Journal Articles | Conference and Workshop Papers | PhD Thesis | Technical Reports
Conference and Workshop Papers
2017
[] 
Sublabel-Accurate Discretization of Nonconvex Free-Discontinuity Problems , In International Conference on Computer Vision (ICCV), 2017. ([supp])
2016
[] 
Sublabel-Accurate Convex Relaxation of Vectorial Multilabel Energies , In European Conference on Computer Vision (ECCV), 2016. ([supp] [code])
[] 
Sublabel-Accurate Relaxation of Nonconvex Energies , In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016. ([supp] [code])
Oral Presentation, Received the Best Paper Honorable Mention Award at CVPR 2016
2015
[] 
Video Segmentation with Just a Few Strokes , In IEEE International Conference on Computer Vision (ICCV), 2015.
2014
[] 
Real-Time Minimization of the Piecewise Smooth Mumford-Shah Functional , In European Conference on Computer Vision (ECCV), 2014. (Code available)
[] 
Generalized Connectivity Constraints for Spatio-temporal 3D Reconstruction , In European Conference on Computer Vision (ECCV), 2014.
[] 
Co-Sparse Textural Similarity for Interactive Segmentation , In European Conference on Computer Vision (ECCV), 2014.
[] 
Surface Normal Integration for Convex Space-time Multi-view Reconstruction , In British Machine Vision Conference (BMVC), 2014.
2013
[] 
A Convex Relaxation Approach to Space Time Multi-view 3D Reconstruction , In ICCV Workshop on Dynamic Shape Capture and Analysis (4DMOD), 2013.
[] 
Tree Shape Priors with Connectivity Constraints using Convex Relaxation on General Graphs , In IEEE International Conference on Computer Vision (ICCV), 2013.
Oral Presentation [] 
Proportion Priors for Image Sequence Segmentation , In IEEE International Conference on Computer Vision (ICCV), 2013. (oral presentation)
[] 
Total Variation Regularization for Functions with Values in a Manifold , In IEEE International Conference on Computer Vision (ICCV), 2013.
[] 
Scale-Aware Object Tracking with Convex Shape Constraints on RGB-D Images , In German Conference on Pattern Recognition (GCPR), 2013.
[] 
Efficient Convex Optimization for Minimal Partition Problems with Volume Constraints , In Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), 2013.
[] 
Performance Evaluation of Narrow Band Methods for Variational Stereo , In 35th German Conference on Pattern Recognition (GCPR), 2013.
[] 
A Co-occurrence Prior for Continuous Multi-Label Optimization , In Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), 2013.
[] 
Volume Constraints for Single View Reconstruction , In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2013.
2012
[] 
Wehrli 2.0: An Algorithm for ”Tidying up Art” , In VISART “Where Computer Vision Meets Art” workshop, ECCV 2012, Springer, 2012.
[] 
A Convex Representation for the Vectorial Mumford-Shah Functional , In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2012.
[] 
Fast and Globally Optimal Single View Reconstruction of Curved Objects , In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2012.
[] 
Nonmetric Priors for Continuous Multilabel Optimization , In European Conference on Computer Vision (ECCV), Springer, 2012.
2011
[] 
Silhouette-Based Variational Methods for Single View Reconstruction , 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.
[] 
A Convex Framework for Image Segmentation with Moment Constraints , In IEEE International Conference on Computer Vision (ICCV), 2011.
[] 
Space-Varying Color Distributions for Interactive Multiregion Segmentation: Discrete versus Continuous Approaches , In Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), 2011.
[] 
Generalized Ordering Constraints for Multilabel Optimization , In IEEE International Conference on Computer Vision (ICCV), 2011. (oral presentation)
[] 
Tight Convex Relaxations for Vector-Valued Labeling Problems , In IEEE International Conference on Computer Vision (ICCV), 2011.
[] 
Introducing Total Curvature for Image Processing , In IEEE International Conference on Computer Vision (ICCV), 2011.
[] 
Total Variation for Cyclic Structures: Convex Relaxation and Efficient Minimization , In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2011.
2010
[] 
Convex Relaxation for Multilabel Problems with Product Label Spaces , In European Conference on Computer Vision (ECCV), 2010.
[] 
Anisotropic Minimal Surfaces Integrating Photoconsistency and Normal Information for Multiview Stereo , In European Conference on Computer Vision (ECCV), 2010.
[] 
Image-based 3D Modeling via Cheeger Sets , In Asian Conference on Computer Vision, 2010.
Received Honorable Mention Award
2009
[] 
An Algorithm for Minimizing the Piecewise Smooth Mumford-Shah Functional , In IEEE International Conference on Computer Vision (ICCV), 2009.
[] 
Continuous Ratio Optimization via Convex Relaxation with Applications to Multiview 3D Reconstruction , In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
[] 
A Convex Relaxation Approach for Computing Minimal Partitions , In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
[] 
Non-Parametric Single View Reconstruction of Curved Objects using Convex Optimization , In Pattern Recognition (Proc. DAGM), 2009.
Received a DAGM Paper Award
2008
[] 
Shape Priors in Variational Image Segmentation: Convexity, Lipschitz Continuity and Globally Optimal Solutions , In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2008.
[] 
An Experimental Comparison of Discrete and Continuous Shape Optimization Methods , In European Conference on Computer Vision (ECCV), 2008.
[] 
Integration of Multiview Stereo and Silhouettes via Convex Functionals on Convex Domains , In European Conference on Computer Vision (ECCV), 2008.
[] 
Continuous Energy Minimization via Repeated Binary Fusion , In European Conference on Computer Vision (ECCV), 2008.
[] 
A Convex Formulation of Continuous Multi-Label Problems , In European Conference on Computer Vision (ECCV), 2008.
2007
[] 
Continuous Global Optimization in Multiview 3D Reconstruction , In Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), Springer, volume 4679, 2007.
[] 
Propagated Photoconsistency and Convexity in Variational Multiview 3D Reconstruction , In Workshop on Photometric Analysis for Computer Vision, 2007.
2002
[] Unsupervised Image Partitioning with Semidefinite Programmifng , In Pattern Recognition (L. van Gool, ed.), Springer, volume 2449, 2002.
2001
[] Convex Relaxations for Binary Image Partitioning and Perceptual Grouping , In Pattern Recognition (B. Radig, S. Florczyk, eds.), Springer, volume 2191, 2001.
Received a DAGM Paper Award Book Chapters | Journal Articles | Conference and Workshop Papers | PhD Thesis | Technical Reports
PhD Thesis
2012
[] 
Convexity in Image-Based 3D Surface Reconstruction , PhD thesis, Department of Computer Science, Technical University Munich, Germany, 2012.
Book Chapters | Journal Articles | Conference and Workshop Papers | PhD Thesis | Technical Reports
Technical Reports
2013
[] 
Label Configuration Priors for Continuous Multi-Label Optimization , Technical report, , 2013.
2008
[] 
A Convex Approach for Computing Minimal Partitions , Technical report, Dept. of Computer Science, University of Bonn, 2008.
