This paper investigates the connections between rectified flows, flow matching, and optimal transport. Flow matching is a recent approach to learning generative models by estimating velocity fields that guide transformations from a source to a target distribution. Rectified flow matching aims to straighten the learned transport paths, yielding more direct flows between distributions. Our first contribution is a set of invariance properties of rectified flows and explicit velocity fields. In addition, we also provide explicit constructions and analysis in the Gaussian (not necessarily independent) and Gaussian mixture settings and study the relation to optimal transport. Our second contribution addresses recent claims suggesting that rectified flows, when constrained such that the learned velocity field is a gradient, can yield (asymptotically) solutions to optimal transport problems. We study the existence of solutions for this problem and demonstrate that they only relate to optimal transport under assumptions that are significantly stronger than those previously acknowledged. In particular, we present several counterexamples that invalidate earlier equivalence results in the literature, and we argue that enforcing a gradient constraint on rectified flows is, in general, not a reliable method for computing optimal transport maps.

Abstract. We study stability and inclusion of the jump set of minimizers of convex denoising functionals, such as the celebrated “Rudin–Osher–Fatemi” functional, for scalar or vectorial signals. We show that under mild regularity assumptions on the data fidelity term and the regularizer, the jump set of the minimizer is essentially a subset of the original jump set. Moreover, we give an estimate on the magnitude of the jumps in terms of the data. This extends old results, in particular of the first author (with Caselles and Novaga) and of Valkonen, to much more general cases. We also consider the case where the original datum has unbounded variation, and we define a notion of its jump set which, again, must contain the jump set of the solution.

In this work, we study a general framework of discrete approximations of the total variation for image reconstruction problems. The framework, for which we can show consistency in the sense of $\Gamma$-convergence, unifies and extends several existing discretization schemes. In addition, we propose algorithms for learning discretizations of the total variation in order to achieve the best possible reconstruction quality for particular image reconstruction tasks. Interestingly, the learned discretizations significantly differ between the tasks, illustrating that there is no universal best discretization of the total variation.

This paper concerns feature selection using supervised classification on high dimensional datasets. The classical approach is to project data onto a low dimensional space and classify by minimizing an appropriate quadratic cost. We first introduced a matrix of centers in the definition of this cost. Moreover, as quadratic costs are not robust to outliers, we propose instead to use an l1 cost (or Huber loss to mitigate overfitting issues). While control on sparsity is commonly obtained by adding an l1 constraint on the vectorized matrix of weights used for projecting the data, we propose to enforce structured sparsity. To this end we used constraints that take into account the matrix structure of the data, based either on the nuclear norm, on the l2,1 norm, or on the l1,2 norm for which we provide a new projection algorithm. We optimize simultaneously the projection matrix and the matrix of centers with a new tailored constrained primal-dual method. The primal-dual framework is general enough to encompass the various robust losses and structured constraints we use, and allows a convergence analysis. We demonstrate the effectiveness of this approach on three biological datasets. Our primal-dual method with robust losses, adaptive centers and structured constraints does significantly better than classical methods, both in terms of accuracy and computational time.

In this paper, we propose a dense two-frame stereo algorithm which handles occlusion in a variational framework. Our method is based on a new regularization model which includes both a constraint on the occlusion width and a visibility constraint in nonoccluded areas. The minimization of the resulting energy functional is done by convex relaxation. A post-processing then detects and fills the occluded regions. We also propose a novel dissimilarity measure that combines color and gradient comparison with a variable respective weight, to benefit from the robustness of the comparison based on local variations while avoiding the fattening effect it may generate.

Abstract We present a new method for non‐rigid shape matching designed to enforce continuity of the resulting correspondence. Our method is based on the recently proposed functional map representation, which allows efficient manipulation and inference but often fails to provide a continuous point‐to‐point mapping. We address this problem by exploiting the connection between the operator representation of mappings and flows of vector fields. In particular, starting from an arbitrary continuous map between two surfaces we find an optimal flow that makes the final correspondence operator as close as possible to the initial functional map. Our method also helps to address the symmetric ambiguity problem inherent in many intrinsic correspondence methods when matching symmetric shapes. We provide practical and theoretical results showing that our method can be used to obtain an orientation preserving or reversing map starting from a functional map that represents the mixture of the two. We also show how this method can be used to improve the quality of maps produced by existing shape matching methods, and compare the resulting map's continuity with results obtained by other operator‐based techniques.

We review some results obtained in collaboration with Vicent Caselles (formerly with DTIC, U. Pompeu Fabra, Barcelona) and Matteo Novaga (U. Pisa) and recent extensions obtained by the first author on the properties of the jump sets of solutions of total variation minimizing problems, including some results on explicit solutions in the 1D and radial cases. We will also describe jump inclusion properties for non-homogeneous perimeters (which appear in active contour energies) and discuss some open problems.

The object of this work is to design an adequate regularization for the problem of recovering missing Fourier coefficients, particularly in some nonstandard situations where low-frequency coefficients are lost. In the framework of nonlocal regularization, we propose a technique for building an original patchwise similarity measure that is adapted to the missing spectrum. Then, a simple nonlocal quadratic energy is minimized. By construction, the similarity criterion is invariant under the corruption process so that the distance between two patches of the corrupted image is almost exactly equal to that computed on the clean image. We illustrate our method with experiments which show its efficiency, in terms of both speed and quality of the results, with respect to other common approaches. We show that the method is practical on synthetic examples which are built upon models of inverse scattering problems, synthetic aperture mirrors for spatial imaging, or medical imaging problems.

We propose convex relaxations for nonconvex energies on vector-valued functions which are tractable yet as tight as possible. In contrast to existing relaxations, we can handle the combination of nonconvex data terms with coupled regularizers such as $l^2$-regularizers. The key idea is to consider a collection of hypersurfaces with a relaxation that takes into account the entire functional rather than separately treating the data term and the regularizers. We provide a theoretical analysis, detail the implementations for different functionals, present run time and memory requirements, and experimentally demonstrate that the coupled $l^2$-regularizers give systematic improvements regarding denoising, inpainting, and optical flow estimation.

We propose the first tractable convex formulation of the vectorial Mumford-Shah functional which allows to compute high-quality solutions independent of the initialization. To this end, we generalize recently introduced convex formulations for scalar functionals to the vector-valued scenario in such a way that discontinuities in the different color channels preferably coincide. Furthermore, we propose an efficient solution which makes the overall optimization problem as tractable as in the scalar-valued case. Numerous experimental comparisons with the naive channel-wise approach, with the well-known Ambrosio-Tortorelli approximation, and with the classical total variation confirm the advantages of the proposed relaxation for contrast-preserving and edge-enhancing regularization.

We describe a convex relaxation for a family of problems of minimal perimeter partitions. The minimization of the relaxed problem can be tackled numerically: we describe an algorithm and show some results. In most cases, our relaxed problem finds a correct numerical approximation of the optimal solution: we give some arguments to explain why it should be so and also discuss some situations where it fails.

In this paper we study preconditioning techniques for the first-order primal-dual algorithm proposed in [5]. In particular, we propose simple and easy to compute diagonal preconditioners for which convergence of the algorithm is guaranteed without the need to compute any step size parameters. As a by-product, we show that for a certain instance of the preconditioning, the proposed algorithm is equivalent to the old and widely unknown alternating step method for monotropic programming [7]. We show numerical results on general linear programming problems and a few standard computer vision problems. In all examples, the preconditioned algorithm significantly outperforms the algorithm of [5].

In this paper we study finite-difference approximations to the variational problem using the bounded variation (BV) smoothness penalty that was introduced in an image smoothing context by Rudin, Osher, and Fatemi. We give a dual formulation for an upwind finite-difference approximation for the BV seminorm; this formulation is in the same spirit as one popularized by the first author for a simpler, less isotropic, finite-difference approximation to the (isotropic) BV seminorm. We introduce a multiscale method for speeding up the approximation of both Chambolle's original method and of the new formulation of the upwind scheme. We demonstrate numerically that the multiscale method is effective, and we provide numerical examples that illustrate both the qualitative and quantitative behavior of the solutions of the numerical formulations.

We propose an algorithmic framework for computing global solutions of variational models with convex regularity terms that permit quite arbitrary data terms. While the minimization of variational problems with convex data and regularity terms is straightforward (using, for example, gradient descent), this is no longer trivial for functionals with nonconvex data terms. Using the theoretical framework of calibrations, the original variational problem can be written as the maximum flux of a particular vector field going through the boundary of the subgraph of the unknown function. Upon relaxation this formulation turns the problem into a convex problem, although in a higher dimension. In order to solve this problem, we propose a fast primal-dual algorithm which significantly outperforms existing algorithms. In experimental results we show the application of our method to outlier filtering of range images and disparity estimation in stereo images using a variety of convex regularity terms.

In this work we propose a convex relaxation approach for computing minimal partitions. Our approach is based on rewriting the minimal partition problem (also known as Potts model) in terms of a primal dual Total Variation functional. We show that the Potts prior can be incorporated by means of convex constraints on the dual variables. For minimization we propose an efficient primal dual projected gradient algorithm which also allows a fast implementation on parallel hardware. Although our approach does not guarantee to find global minimizers of the Potts model we can give a tight bound on the energy between the computed solution and the true minimizer. Furthermore we show that our relaxation approach dominates recently proposed relaxations. As a consequence, our approach allows to compute solutions closer to the true minimizer. For many practical problems we even find the global minimizer. We demonstrate the excellent performance of our approach on several multi-label image segmentation and stereo problems.

In this work we revisit the Mumford-Shah functional, one of the most studied variational approaches to image segmentation. The contribution of this paper is to propose an algorithm which allows to minimize a convex relaxation of the Mumford-Shah functional obtained by functional lifting. The algorithm is an efficient primal-dual projection algorithm for which we prove convergence. In contrast to existing algorithms for minimizing the full Mumford-Shah this is the first one which is based on a convex relaxation. As a consequence the computed solutions are independent of the initialization. Experimental results confirm that the proposed algorithm determines smooth approximations while preserving discontinuities of the underlying signal.

In a recent paper Boykov et al. (LNCS, Vol. 3953, pp. 409–422, 2006 ) propose an approach for computing curve and surface evolution using a variational approach and the geo-cuts method of Boykov and Kolmogorov (International conference on computer vision, pp. 26–33, 2003 ). We recall in this paper how this is related to well-known approaches for mean curvature motion, introduced by Almgren et al. (SIAM Journal on Control and Optimization 31(2):387–438, 1993 ) and Luckhaus and Sturzenhecker (Calculus of Variations and Partial Differential Equations 3(2):253–271, 1995 ), and show how the corresponding problems can be solved with sub-pixel accuracy using Parametric Maximum Flow techniques. This provides interesting algorithms for computing crystalline curvature motion, possibly with a forcing term.

Coifman and Donoho (1995) suggested translation-invariant wavelet shrinkage as a way to remove noise from images. Basically, their technique applies wavelet shrinkage to a two-dimensional (2-D) version of the semi-discrete wavelet representation of Mallat and Zhong (1992), Coifman and Donoho also showed how the method could be implemented in O(Nlog N) operations, where there are N pixels. In this paper, we provide a mathematical framework for iterated translation-invariant wavelet shrinkage, and show, using a theorem of Kato and Masuda (1978), that with orthogonal wavelets it is equivalent to gradient descent in L (2)(I) along the semi-norm for the Besov space B(1) (1)(L(1)(I)), which, in turn, can be interpreted as a new nonlinear wavelet-based image smoothing scale space. Unlike many other scale spaces, the characterization is not in terms of a nonlinear partial differential equation.

This paper examines the relationship between wavelet-based image processing algorithms and variational problems. Algorithms are derived as exact or approximate minimizers of variational problems; in particular, we show that wavelet shrinkage can be considered the exact minimizer of the following problem. Given an image F defined on a square I, minimize over all g in the Besov space B(1)(1)(L (1)(I)) the functional |F-g|(L2)(I)(2)+lambda|g|(B(1)(1 )(L(1(I)))). We use the theory of nonlinear wavelet image compression in L(2)(I) to derive accurate error bounds for noise removal through wavelet shrinkage applied to images corrupted with i.i.d., mean zero, Gaussian noise. A new signal-to-noise ratio (SNR), which we claim more accurately reflects the visual perception of noise in images, arises in this derivation. We present extensive computations that support the hypothesis that near-optimal shrinkage parameters can be derived if one knows (or can estimate) only two parameters about an image F: the largest alpha for which FinEpsilon(q)(alpha )(L(q)(I)),1/q=alpha/2+1/2, and the norm |F|B(q)(alpha)(L(q)(I)). Both theoretical and experimental results indicate that our choice of shrinkage parameters yields uniformly better results than Donoho and Johnstone's VisuShrink procedure; an example suggests, however, that Donoho and Johnstone's SureShrink method, which uses a different shrinkage parameter for each dyadic level, achieves a lower error than our procedure.

We review the PDE methods for image processing developed at the Ceremade, the Universitat de Illes Balears, and the Universidad de Las Palmas de Gran Canaria. We first recall the axiomatic approach of the theory of multiscale analysis of images and try at the same times to see how it can be extended to the problem of color image processing. After stating the theorems that follow from this theory, we discuss some examples of PDEs and show results.>