Functional Lifting 2.0: Efficient Convexifications for Imaging and Vision

• Applicants: Professor Dr. Daniel Cremers; Professor Dr. Jan Lellmann; Professor Dr. Michael Möller
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: from 2018 to 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 394737018

• Final Report Year: 2024

Final Report Abstract

Many real-world problems in computer vision and image analysis require the optimization of a cost function with a large number of unknowns. In such highdimensional optimization problems, the globally optimal solution can typically only be found if the cost function has a favorable shape, most importantly, if it is convex. For non-convex problems, a viable strategy is to approximate the non-convex cost function by a convex one, either globally or iteratively. In this project, particular types of convex approximations to non-convex problems were studied, in which the unknowns are first embedded into an even higher-dimensional space via a so-called lifting, such that the subsequent convexification is more faithful to the original costs. A particular focus was on problems where the unknown can take continuous values, such as in an interval or, more generally, on a manifold. The project found novel approaches that allow solving certain non-convex problems more accurately than previous methods and generated novel insights into the underlying theory, such as a proof that increasingly higher-dimensional embeddings result in higher-fidelity convex approximations of the original problem. The project also identified a connection to the theory of dynamical optimal transport and an extension of classical non-linear scale space to the non-convex case. The techniques developed in this project were shown to be beneficial in a multitude of applications, including depth estimation from stereo and time-of-flight images, multi-view triangulation, image segmentation, terahertz imaging, motion estimation, biomedical image registration, and diffusion-weighted magnetic resonance imaging.

Publications

• Composite Optimization by Nonconvex Majorization-Minimization. SIAM Journal on Imaging Sciences, 11(4), 2494-2528.
  Geiping, Jonas & Moeller, Michael
  
• Lifting layers: Analysis and applications. In Proceedings of the European Conference on Computer Vision (ECCV), pages 52–67, September
  Peter Ochs, Tim Meinhardt, Laura Leal-Taixe & Michael Moeller
  
• Lifting Vectorial Variational Problems: A Natural Formulation Based on Geometric Measure Theory and Discrete Exterior Calculus. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 11109-11118. IEEE.
  Möllenhoff, Thomas & Cremers, Daniel
  
• Fast convex relaxations using graph discretizations. In British Machine Vision Conference
  Jonas Geiping, Fjedor Gaede, Hartmut Bauermeister & Michael Moeller
  
• Lifting Methods for Manifold-Valued Variational Problems. Handbook of Variational Methods for Nonlinear Geometric Data, 95-119. Springer International Publishing.
  Vogt, Thomas; Strekalovskiy, Evgeny; Cremers, Daniel & Lellmann, Jan
  
• Inverse Scale Space Iterations for Non-convex Variational Problems Using Functional Lifting. Lecture Notes in Computer Science, 229-241. Springer International Publishing.
  Bednarski, Danielle & Lellmann, Jan
  
• A Cutting-Plane Method for Sublabel-Accurate Relaxation of Problems with Product Label Spaces. International Journal of Computer Vision, 131(1), 346-362.
  Ye, Zhenzhang; Haefner, Bjoern; Quéau, Yvain; Möllenhoff, Thomas & Cremers, Daniel
  
• Inverse Scale Space Iterations for Non-Convex Variational Problems: The Continuous and Discrete Case. Journal of Mathematical Imaging and Vision, 65(1), 124-139.
  Bednarski, Danielle & Lellmann, Jan
  
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields. SIAM Journal on Imaging Sciences, 15(3), 1253-1281.
  Bauermeister, Hartmut; Laude, Emanuel; Möllenhoff, Thomas; Moeller, Michael & Cremers, Daniel
  
• Semidefinite Relaxations for Robust Multiview Triangulation. 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 749-757. IEEE.
  Härenstam-Nielsen, Linus; Zeller, Niclas & Cremers, Daniel