Functional Lifting 2.0: Efficient Convexifications for Imaging and Vision

解决计算机视觉和图像处理问题的最通用和最强大的工具之一是基于能量的方法。其基本思想是将每一个可能的解决方案与成本或能量相关联，以这种方式，低能量值对应于好的解决方案。不幸的是，大多数实际相关的问题固有地导致非凸的能量函数，使全局极小的计算变得非常具有挑战性。因此，在经典的局部极小化方法的解决方案的质量很大程度上取决于初始化和特定的选择的算法。在这个项目中，我们将开发一种全局方法，这种方法依赖于通过函数提升在高维空间中对非凸能量进行凸化，以找到全局最优解。现有的方法通过将范围离散化为标签来实现这种提升，最终限制了解决方案的准确性。相比之下，该项目将扩展最近的子标签精确提升方法的适用性，这些方法大大降低了获得近似全局解的额外成本，并允许在利用能量中的凸部分时逐渐考虑非凸性。这允许开发求解器，该求解器随着问题的非凸性而优雅地扩展，并且允许在广泛的优化问题上有效地计算接近全局最优的解决方案。

One of the most versatile and powerful tools for solving computer vision and image processing problems is the class of energy-based methods. The basic idea is to associate with every conceivable solution a cost - or energy - in such a way that low energy values correspond to good solutions. Unfortunately, most practically relevant problems inherently lead to non-convex energy functions, so that the computation of global minimizers becomes very challenging. Consequently, the solution quality in classical local minimization methods heavily depends on the initialization and the particular choice of algorithm. In this project, we will develop global methods that rely on a convexification of non-convex energies in high-dimensional spaces by means of functional lifting in order to find globally optimal solutions. Existing approaches implemented this lifting by discretizing the range into labels, ultimately limiting the solution accuracy. In contrast, this project will extend the applicability of recent sublabel-accurate lifting methods that greatly reduce the extra cost of obtaining an approximate global solution and allow to gradually take into account the non-convexities while exploiting convex parts in the energy. This allows to develop solvers that scale gracefully with the non-convexity of the problem, and allow to efficiently compute close-to-globally optimal solutions on a wide range of optimization problems.