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.
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