Source-linked AI summary
Regularized Discrete Optimal Transport
Sira Ferradans, Nicolas Papadakis, Gabriel Peyré, Jean-François Aujol
TL;DR
Image-processing applications need transport that handles irregular maps and multimodal histograms with unequal modal masses. The paper introduces relaxed and regularized discrete optimal transport, extends it to barycenters, and applies both to color transfer and color normalization. The resulting methods reduce transport-related color artifacts and support common palettes across image sets.
Problem
Color transfer requires handling multimodal image color distributions whose modes can have different masses, while ordinary transport plans may be irregular and produce artifacts.
Method
The paper integrates mass relaxation and transport regularization into a convex discrete OT formulation, then computes relaxed regularized barycenters with block coordinate descent.
Results
The proposed method avoids color artifacts seen with state-of-the-art color-transfer methods, while relaxed regularized barycenters produce smoother and more meaningful color normalization results.
Takeaways & Limitations
Relaxed regularized transport provides color transfer robust to modal mass variation and a common palette for normalizing groups of images.
Takeaways & Limitations
Block coordinate descent convergence to stationary points is ensured for Sobolev regularization but not for anisotropic regularization.
Abstract
from arXiv · showhide
This article introduces a generalization of the discrete optimal transport, with applications to color image manipulations. This new formulation includes a relaxation of the mass conservation constraint and a regularization term. These two features are crucial for image processing tasks, which necessitate to take into account families of multimodal histograms, with large mass variation across modes. The corresponding relaxed and regularized transportation problem is the solution of a convex optimization problem. Depending on the regularization used, this minimization can be solved using standard linear programming methods or first order proximal splitting schemes. The resulting transportation plan can be used as a color transfer map, which is robust to mass variation across images color palettes. Furthermore, the regularization of the transport plan helps to remove colorization artifacts due to noise amplification. We also extend this framework to the computation of barycenters of distributions. The barycenter is the solution of an optimization problem, which is separately convex with respect to the barycenter and the transportation plans, but not jointly convex. A block coordinate descent scheme converges to a stationary point of the energy. We show that the resulting algorithm can be used for color normalization across several images. The relaxed and regularized barycenter defines a common color palette for those images. Applying color transfer toward this average palette performs a color normalization of the input images.
1. Introduction.
The paper motivates optimal transport for image histograms and develops relaxed, regularized formulations to address irregular transport maps and unequal modal masses. It applies these formulations to color transfer and color normalization through barycenters.
- Optimal Transport and Imaging: Optimal transport accounts for the spatial locations of density modes and provides a transport plan usable for image modification.The plan supports applications including image registration and color transfer.
- Regularized and relaxed transport: Irregular transport plans can create artifacts and amplify noise in flat image regions because three-dimensional color-space transport ignores pixel-domain regularity.The paper motivates regularizing transport directly rather than relying only on post-processing.
- Regularized and relaxed transport: Graph-based regularization adapts penalties to the geometry of input densities, following manifold-learning ideas and offering a soft version of graph matching.The related graph-matching problem is a quadratic assignment problem known to be NP-hard.
- Regularized and relaxed transport: Classical optimal transport can fail on multimodal color distributions whose modes have different masses, motivating relaxed matching between densities.Relaxation allows the modes of natural-image color distributions to be matched without requiring equal mass.
- Contributions: The proposed unified formulation computes regular transport maps through a convex optimization problem and supports algorithms adapted to different regularizers.The framework is applied to color transfer, while a block-coordinate descent method computes barycenters and converges to a stationary point of the non-convex barycenter energy.
- Discrete Optimal Transport: The discrete OT linear-program relaxation is tight, with a binary solution that also solves the original assignment problem.This result applies to the discrete setting described in the supplied passages.
3. Relaxed and Regularized Transport.
The paper relaxes mass-conservation constraints and adds graph-based regularization to discrete OT, producing partial matchings that can reflect both mass variation and point-cloud structure. The resulting problem remains convex and supports transport maps built from weighted barycenters.
- Relaxed OT allows each point in X to connect to multiple points in Y and vice versa, rather than enforcing a one-to-one mapping.
- The total transported mass is fixed by I*ΣI = M, with M set to N for the paper’s color-manipulation applications.
- Problem (3.1) is a convex linear program solvable with standard linear-programming algorithms.
- The relaxed transport map sends each Xi to a weighted barycenter of neighboring Y points, with Z = (diag(ΣI))^-1ΣY.
- For integer κ, an optimal transport matrix can be binary and interpreted as pairwise assignments; noninteger parameters generally produce nonbinary entries.
- Graph regularization uses gradient operators on weighted nearest-neighbor graphs and penalizes displacement variation, with λX and λY controlling regularity.
- Increasing λX and λY spreads low-weight connections across clusters, while high regularization favors matching clusters with similar graph-defined shapes.
4. Application to Color Transfer.
The color-transfer application computes regularized relaxed transport between image color distributions, then transfers the resulting mapping to preserve the source image’s geometry while approaching the target palette. Subsampling and interpolation make the procedure applicable to large images.
- Color transfer seeks a transformation that makes the source histogram close or equal to the target histogram while retaining the source image geometry.
- Relaxation better matches dominant color modes under mass variation, while transport regularization reduces colorization artifacts.
- Large images are handled by computing transport on smaller K-means-derived point clouds whose mapping is extended to the original images by interpolation.
- Algorithm 1 takes source and target images, regularization parameters, and clustering bounds, and outputs the transformed source image.
1. Histogram down-sample.
The algorithm computes the optimal relaxed and regularized transport plan on clustered representations by solving the paper’s central optimization problem.
- Compute the optimal Σ by solving equation (3.2) with algorithm (3.4) or linear program (3.5) using an interior-point algorithm.
2. Compute Mapping.
The algorithm reconstructs the full-resolution color-transferred image from the computed transport mapping.
- Compute the transformed image X̃0 using equation (4.1).
3. Obtain high resolution result.
The method downsamples image colors, builds graph-based regularized transport, interpolates the transport map back to full resolution, and studies parameter effects in color transfer. Regularization and parameter choice affect color resolution and artifacts.
- Downsampling: K-means clustering reduces each image to a smaller point set before transport-map computation.The same downsampling procedure is applied to both input images.
- Graph construction: A nearest-neighbor graph on the subsampled colors defines gradient operators for transport regularization.Graph weights are inverse Euclidean distances between neighboring points.
- Upsampling: Nearest-neighbor interpolation extends the subsampled transport map to the full image while adding back quantization error.The additive correction helps restore small-scale texture and improve visual quality.
- Parameter effects: Low λX and λY values map many points to nearby target colors, reducing the color resolution of the transferred image.The example shows many points in a large source cluster mapped to few points in a small target cluster.
- Results: Compared with two prior methods, suitable λX, λY, and κ choices avoid reported color artifacts in natural-image color transfer.The experiments use N = 400 and a 4-nearest neighbor graph.
5. Regularized OT Barycenters.
The barycenter extension jointly updates a common point set and relaxed regularized transport plans for multiple input clouds. Its non-convex energy is separately convex, enabling block coordinate descent and specialized convex subproblem solvers.
- Formulation: The asymmetric formulation keeps X as a reference, uses all its points, and regularizes only its graph by setting λY = 0.This yields an asymmetric transport distance rather than a symmetric metric.
- Barycenter formulation: A barycenter cloud is defined as a local minimizer of an energy over the common cloud X and transport matrices Σ[r].The joint problem is separately convex in these variable blocks but not jointly convex.
- Optimization: Block coordinate descent alternates between independently solving relaxed regularized OT plans and minimizing the energy with respect to X.The transport-plan updates are parallel across input clouds.
- Optimization: For (p, q) = (2, 2), the X-update is an unconstrained quadratic problem solved through a symmetric linear system.Conjugate gradients can solve the resulting system.
- Optimization: For (p, q) = (1, 1), the X-update is a linear program or can use a primal-dual proximal splitting scheme.The latter is proposed for the highly structured problem.
- Algorithm: Algorithm 2 initializes a barycenter point set and alternates transport-plan and barycenter updates until sufficiently large iteration count.The output is the resulting iterate X(ℓ).
1. Initialization.
For each input cloud, the algorithm updates its transport matrix while holding the current barycenter cloud fixed.
- Initialization: For each r, compute Σ[r],(ℓ+1) by solving the convex transport subproblem with X = X(ℓ) fixed.The algorithms from Section 3.4 are used for these updates.
3. Update of X.
The barycenter update solves a convex problem in X after fixing transport plans. Convergence to stationary points is established for Sobolev regularization, but not guaranteed for anisotropic regularization.
- Update of X: With transport plans fixed, the algorithm solves a convex optimization problem for the barycenter cloud X.The update is performed after the transport-plan block.
- Convergence: For anisotropic regularization, convergence to stationary points cannot be ensured, although the authors report observing it in numerical tests.The guarantee stated by the theorem applies to the smooth Sobolev case.
- Convergence: When (p, q) = (2, 2), the iterates are bounded, energies decrease and converge, and every convergent subsequence reaches a stationary point.The convergent subsequences share the same limiting energy.
- Color normalization: The common color palette used for normalization is related to the original image palettes and may represent an in-between histogram when the desired illumination reference is unavailable.This defines the practical target for the barycenter-based normalization process.
6. Application to color normalization.
Color normalization computes a shared barycenter palette, transports each image toward it, and upsamples the transformed point clouds into high-resolution results.
- Method: K-means clustering first reduces each input image to a smaller point set for tractable barycenter computation.
- Method: Regularized and relaxed OT transport maps are solved between each reduced image and the barycenter.
- Method: Applying each transport map produces point clouds with color distributions close to the barycenter.
- Method: The transformed point clouds are upsampled to recover high-resolution normalized images.
- Method: Algorithm 3 provides the complete regularized OT color-normalization procedure.
- Method: A barycenter of the reduced point clouds is computed using the block coordinate descent algorithm.
3. Compute transport mappings.
The experiments compare classical and relaxed/regularized OT for barycenter-based color transfer, showing preserved geometry and fewer image artifacts in the proposed approach.
- Results: Relaxed/regularized barycenters preserve the original clusters across ρ, maintaining image geometry while changing histograms.
- Results: Natural-image color transfer changes colors smoothly toward the barycenter without artifacts and matches the target color and contrast at ρ = (0, 1).
- Color normalization: Compared with standard OT and Papadakis et al., the proposed normalization reduces artifacts such as violet leaves, new background colors, and sky distortions.
- Application: The method is also proposed as preprocessing before comparing or registering images of the same object under different illumination conditions.
- Experimental setup: The barycenter algorithm is evaluated with parameter settings including k = 1.1, λ = 0.0009 and k = 1.3, λ = 0.01.