Wasserstein barycentric coordinates: histogram regression using optimal transport

Nicolas Bonneel, Gabriel Peyré, Marco CuturiACM Trans. Graphics 2016 · DOI · OpenReview

Abstract

This paper introduces Wasserstein Barycentric Coordinates, a novel framework for representing a histogram—such as a color palette, a BRDF, or a 3D shape—as a geometrically meaningful combination of reference histograms. By leveraging Optimal Transport (OT) and a "backward" differentiation of the Sinkhorn algorithm, the authors enable fast, high-quality regression and interpolation that "moves" data mass rather than just fading it in and out. This approach addresses the previously unsolved inverse problem: given a target histogram, what are the weights (coordinates) that best reconstruct it using a specific set of reference histograms?

Introduction

In computer graphics and vision, "histogram-valued data" is pervasive, encompassing color distributions in photographs, Bidirectional Reflectance Distribution Functions (BRDFs) of materials, and voxelized 3D shapes. Traditional Euclidean interpolation (linear blending) is "geometry-blind." For instance, blending a red circle on the left with a blue circle on the right via linear interpolation results in two fading, semi-transparent circles. Ideally, one would desire a single circle that changes color as it moves across the space.

While calculating a Wasserstein Barycenter (the "average" histogram) given a set of weights is a known "forward" problem, the "inverse" problem—finding the optimal weights for a given target—remained computationally challenging. This work provides the first efficient numerical scheme to determine these coordinates.

Methods

The authors treat histograms as "heaps of sand" and utilize Optimal Transport (OT) to measure the minimum "work" required to transform one heap into another.

Entropic Regularization and Sinkhorn Iteration

To overcome the high computational cost of pure OT, the authors employ entropic regularization. This smooths the optimization landscape and allows the problem to be solved using the fast, iterative Sinkhorn algorithm.

Algorithmic Differentiation (AD)

The core innovation lies in the calculation of the barycenter's derivative (Jacobian). Since the barycenter is the result of an optimization process, its derivative is mathematically complex. The authors propose Algorithmic Differentiation (AD) of the Sinkhorn loop. By differentiating through a fixed number of iterations of the algorithm itself, they obtain a "backward" pass that allows for efficient gradient descent to find the optimal weights $\lambda$.

Optimization

With the gradient calculated via AD, standard quasi-Newton solvers, such as L-BFGS, are used to converge quickly on the best barycentric coordinates.

Applications and Results

The versatility of Wasserstein Barycentric Coordinates is demonstrated across multiple domains:

  • Color Grading: The system can automatically color-grade an image to match a specific style (e.g., "autumn") by projecting the image's palette onto a simplex of stylized histograms. This avoids "ghosting" artifacts common in simpler methods.
  • Reflectance (BRDFs): Using the UTIA database, the authors successfully reconstructed complex reflectance functions even after discarding 95% of original measurements, demonstrating extreme robustness to sparsity.
  • 3D Shapes: When reconstructing voxelized models, Wasserstein projection creates clean, manifold-like interpolations, whereas Euclidean methods result in overlapping "ghost" shapes.
A mountain landscape and its associated 3D color histogram used for regression.
A different mountain scene demonstrating how color distributions vary across styles.

Discussion and Future Work

While the method is robust and scales to large grids (up to $256^3$), it faces memory constraints that scale linearly with the number of Sinkhorn iterations and reference histograms. Furthermore, reconstruction quality depends on the reference database; if a target is fundamentally different from the basis, results will be poor.

A promising direction for future research is Wasserstein Dictionary Learning, which would involve automatically learning the optimal set of reference histograms (the basis) from raw data, rather than relying on manual selection.

Conclusion

Wasserstein Barycentric Coordinates provide a powerful tool for histogram regression that respects the underlying geometry of the data. By differentiating through the Sinkhorn algorithm, the authors have unlocked a practical solution for the inverse Wasserstein problem, with significant implications for color processing, material modeling, and shape analysis.

Summary updated

Abstract

This article defines a new way to perform intuitive and geometrically faithful regressions on histogram-valued data. It leverages the theory of optimal transport, and in particular the definition of Wasserstein barycenters, to introduce for the first time the notion of barycentric coordinates for histograms. These coordinates take into account the underlying geometry of the ground space on which the histograms are defined, and are thus particularly meaningful for applications in graphics to shapes, color or material modification. Beside this abstract construction, we propose a fast numerical optimization scheme to solve this backward problem (finding the barycentric coordinates of a given histogram) with a low computational overhead with respect to the forward problem (computing the barycenter). This scheme relies on a backward algorithmic differentiation of the Sinkhorn algorithm which is used to optimize the entropic regularization of Wasserstein barycenters. We showcase an illustrative set of applications of these Wasserstein coordinates to various problems in computer graphics: shape approximation, BRDF acquisition and color editing.
BibTeX
@article{bonneel2016wasserstein,
  author = {Nicolas Bonneel and Gabriel Peyré and Marco Cuturi},
  title = {{Wasserstein barycentric coordinates: histogram regression using optimal transport}},
  journal = {ACM Trans. Graphics},
  year = {2016},
  doi = {10.1145/2897824.2925918},
}
Figure