We propose a spatially continuous convex relaxation framework based on functional lifting that provides sublabel-accurate solutions to multilabel problems. While previous approaches to functional lifting required the energy to be linear between labels, necessitating a large number of labels for accurate approximation, our method uses a piecewise convex approximation of the data term, which significantly reduces the required number of labels. In contrast to MRF-based approaches, the spatially continuous setting produces less grid bias. Our formulation represents the tightest possible convex relaxation in a local sense. The implementation is straightforward and enables efficient primal-dual optimization on GPUs. We demonstrate the effectiveness of our approach on several computer vision applications including optical flow, stereo matching, and image denoising.

Many problems in computer vision can be formulated as labeling problems, where the goal is to assign a label from a discrete or continuous set to each pixel or spatial location. Examples include optical flow estimation, stereo matching, image segmentation, and denoising. A common approach is to formulate these as energy minimization problems consisting of a data term measuring fidelity to observations and a regularization term encouraging spatial smoothness. When the label space is discrete, Markov Random Fields (MRFs) provide a principled framework, but they suffer from metrication artifacts due to the underlying grid discretization. Continuous convex relaxation methods alleviate grid bias but have traditionally been limited to binary or convex data terms.

Functional lifting extends convex relaxation to multilabel problems by lifting the label assignment function to a higher-dimensional space where convexity can be exploited. However, existing functional lifting approaches assume that the data term is piecewise linear between consecutive labels, which is only a good approximation when a large number of labels is used. This dramatically increases computational cost. We propose to replace the piecewise linear approximation with a piecewise convex one, which provides sublabel accuracy with far fewer labels. This is possible because many data terms in computer vision are naturally convex or can be well approximated by piecewise convex functions.

Discrete optimization methods for labeling problems, including graph cuts and message passing algorithms, have been widely used in computer vision. While highly effective for certain energy classes, they are fundamentally limited by the discretization of both the spatial domain and the label space. Continuous convex relaxation approaches, pioneered by works on total variation regularization, avoid spatial discretization artifacts. The functional lifting framework of Pock et al. extends these ideas to multilabel problems but requires piecewise linear data terms, leading to the need for dense label sampling. Our approach directly addresses this limitation by introducing piecewise convex data terms that capture sublabel information within each label interval.

We consider energy minimization problems of the form E(u) = integral of [f(x, u(x)) + g(x, Du(x))] dx, where u: Omega -> Gamma maps from the image domain to the label space, f is the data term, and g is the regularizer depending on the gradient Du. The key challenge is that f is generally nonconvex in u, making direct minimization intractable. The functional lifting approach replaces the scalar function u with a vector-valued indicator function phi in a higher-dimensional space, transforming the nonconvex problem into one that admits tight convex relaxation.

The central contribution of this work is to replace the piecewise linear approximation of the data term between labels with a piecewise convex approximation. Given a set of labels gamma_0 < gamma_1 < ... < gamma_K, instead of interpolating f linearly between consecutive labels, we compute the convex envelope of f on each interval [gamma_i, gamma_{i+1}]. This results in the tightest possible convex relaxation in a local sense: on each label interval, no tighter convex underestimator of the data term exists. The practical consequence is dramatic: problems that previously required hundreds of labels for acceptable accuracy can now be solved with as few as 5-10 labels, reducing memory and computation by orders of magnitude.

The resulting convex optimization problem is solved using a first-order primal-dual algorithm in the style of Chambolle and Pock. The algorithm alternates between proximal gradient steps on the primal variable and the dual variable, with the proximal operators having closed-form solutions for typical regularizers (total variation, Huber norm). The implementation is highly parallelizable and runs efficiently on modern GPUs. The straightforward structure of the algorithm — requiring only pointwise operations and linear operators — makes the implementation remarkably simple despite the theoretical sophistication of the relaxation.

We evaluate our approach on three computer vision applications. For optical flow estimation, our method with only 10 labels achieves comparable accuracy to the piecewise linear approach with 200 labels, demonstrating the sublabel accuracy claim. For stereo matching on the Middlebury benchmark, the continuous formulation produces smoother disparity maps with less grid bias than MRF-based methods. For image denoising with nonconvex regularizers, our framework handles the ROF model with truncated total variation, producing results that better preserve edges while removing noise. Across all experiments, the GPU implementation converges within seconds, making the approach practical for real-time applications.

We have presented a sublabel-accurate convex relaxation framework for nonconvex energy minimization in computer vision. By replacing the piecewise linear approximation in functional lifting with a piecewise convex one, we achieve the locally tightest convex relaxation while dramatically reducing the number of required labels. The approach combines theoretical rigor with practical efficiency: the optimization is straightforward to implement, GPU-accelerable, and produces high-quality results across multiple applications. Our work demonstrates that careful mathematical modeling can lead to both better theory and better practice in computer vision optimization.