Color Transfer via Sliced Optimal Transport
Introduction
Color transfer is an image processing application where you want to retarget the color histogram of an input image according to the color histogram of a target one.
Example:
Input image  Target image  Color transfer output 

The idea of this project is to detail a color transfer solution that considers the Optimal Transport as a way to deform histograms in the most efficient way (see below for details). The literature is huge on the subject but I would like to emphasize the fact that efficient implementations of these tools are not so difficult.
This project contains both this documentation and some C++ codes that implement the color transfer with as few dependencies as possible (just modern C++ compiler with OpenMP for best performances).
Building the code
To compile the tools, just clone the repository and use cmake to build the project:
git clone https://github.com/dcoeurjo/OTColorTransfer.git
cd OTColorTransfer
mkdir build ; cd build
cmake .. DCMAKE_BUILD_TYPE=Release
make
Everything should compile with C++11 compiler. The only dependency is OpenMP for multithread features that is usually shipped with the compiler by default.
On Apple MacOS, the default clang
compiler does not have OpenMP. Just install omp
(brew install omp
) and use the following cmake
command line:
cmake .. DOpenMP_C_LIB_NAMES="omp" DOpenMP_CXX_FLAGS="Xpreprocessor fopenmp \
I/usr/local/opt/libomp/include" DOpenMP_CXX_LIB_NAMES="omp" \
DOpenMP_omp_LIBRARY=/usr/local/opt/libomp/lib/libomp.dylib \
DOpenMP_C_FLAGS="Xpreprocessor fopenmp I/usr/local/opt/libomp/include"
The theory: Optimal Transport and Sliced Optimal Transport
As mentioned above, the key tool will be Optimal Transport (OT for short) which can be sketched as follows: Given two probability (Radon) measures \mu\in X and \nu\in Y, and a cost function c(\cdot,\cdot): X\times Y \rightarrow \mathbb{R}^+, an optimal transport plan T: X\rightarrow Y minimizes
The cost of the optimal transport defines a metric between Radon measure. We can define the p^{th} Wasserstein metric, \mathcal{W}_p(\mu,\nu) as
An analogy with piles of sand is usually used to explain the definition: let us consider that \mu is a pile of sand and \nu a hole (with the same volume or mass), if we consider that the cost of moving an elementary volume of sand from on point to the other is proportional to the Euclidean distance (l_2 cost function), then the optimal transport plan gives you the most efficient way to move all the sand from \mu to \nu. Again, the literature is huge and there are many alternative definitions, please refer to Computational Optimal Transport for a more complete introduction to the subject.
The link between OT and color transfer follows the observation that color histograms are discrete Radon measures. As we are looking for the most efficient transformation of the input image histogram to match with the target one, the color transfer problem can be reformulate as a discrete OT one ^{1}^{2} ^{3}^{4}^{5}^{6}.
There are many numerical solutions to compute the OT (with continuous, discrete, semidiscrete measures, w/o regularization…). We focus here on the sliced formulation of the OT and associated 2Wasserstein metric in dimension d:
The sliced formulation consists in projecting the measures onto a 1D line (P_{\theta,\sharp}: \mathbb{R}^d\rightarrow \mathbb{R}), solving the 1D OT problem on the projections and average the results for all directions (S^d is the unit hypersphere in dimension d).
If the measures are discrete as sum of Diracs centered at points \{x_i\} and \{y_i\} in \mathbb{R}^d (\mu := \frac{1}{n}\sum_{x_i} \delta_{x_i}, \nu := \frac{1}{n}\sum_{y_i} \delta_{y_i}), then the 1D OT is obtained by sorting the projections and computing the difference between the first projected point of \mu with the first projected point of \nu, the second with the second, etc…
$$ SW(\mu,\nu)^2 = \int_{S^d} \left(\langle x_{\sigma_\theta(i)}  y_{\kappa_\theta(i)},\theta\rangle ^2\right) d\theta\,,$$ (\sigma_\theta(i) a,d {\kappa_\theta(i)} are permutations with increasing order).
Numerically, we sample the set of directions S^d and thus consider a finite number of slices.
Sliced OT Color Transfer
Back to our histogram transfer problem, Diracs centers \{x_i\} are points in RGB space (one Dirac per pixel of the input image), and \{y_i\} are the colors of the target image. Matching the histogram can be seen a transportation of the point cloud \mu to \nu in \mathbb{R^3} (the RGB color space).
The idea is to advect points of \mu such that we minimize SW(\mu,\nu). As described in the literature^{1}^{4}, this amounts to project he points onto a random direction \theta, align the sorted projections and advect \mu in the \theta direction by \langle x_{\sigma_\theta(i)}  y_{\kappa_\theta(i)},\theta\rangle.
and we iterate. Note that instead of advecting \mu for each \theta, we can accumulate advection vectors into a small batch and perform the transport step once the batch is full^{4}. For enough slices (see the code for the experiments), we end up with a retarged input image. If K denotes the number of slices, the overall computational cost of the approach in dimension d is in O(d\,K\, N\log N).
Note that the transport plan can be regularized using a simple postprocessing, e.g. a bilateral filter of the transportation map (difference between the input image and the retargeted one) which is then applied to the input image^{4}.
Sliced Partial Optimal Transport
The original sliced OT requires the two measures to have the exact same number of Diracs (e.g. input and target images must have the same size). When dealing with measures of different sizes, the combinatorial problem is more complex in the sense that we are not looking for a minimal cost bijective map between the Diracs, but an injective one. This problem is intensively discussed in the Sliced Partial Optimal Transport SIGGRAPH paper^{6}.
In color matching applications such as that of [Pitié et al. 2005]^{1}, matching all pixels of an input image (a) seen as 3D points in an RGB space to all pixels of a target image (b) can lead to erroneous transfers (c) due to mismatched content (here, trees of the target are not present in the input, and distort colors in the output).

Francois Pitié, Anil C. Kokaram, and Rozenn Dahyot. 2005. NDimensional Probablility Density Function Transfer and Its Application to Colour Transfer. In Proceedings of the Tenth IEEE International Conference on Computer Vision  Volume 2 (ICCV ’05). IEEE Computer Society, Washington, DC, USA, 1434–1439. https://doi.org/10.1109/ ICCV.2005.166 ↩↩↩

François Pitié, Anil C Kokaram, and Rozenn Dahyot. 2007. Automated colour grading using colour distribution transfer. Computer Vision and Image Understanding 107, 12 (2007), 123–137. ↩

Nicolas Bonneel, Julien Rabin, G. Peyré, and Hanspeter Pfister. 2015. Sliced and Radon Wasserstein Barycenters of Measures. J. of Mathematical Imaging and Vision 51, 1 (2015). ↩

Julien Rabin, Julie Delon, and Yann Gousseau. 2010. Regularization of transportation maps for color and contrast transfer. In Image Processing (ICIP), 2010 17th IEEE International Conference on. IEEE, 1933–1936. ↩↩↩↩

Nicolas Bonneel, Kalyan Sunkavalli, Sylvain Paris, and Hanspeter Pfister. 2013. Example Based Video Color Grading. ACM Trans. Graph. (SIGGRAPH) 32, 4 (2013). ↩

Nicolas Bonneel and David Coeurjolly. 2019. Sliced Partial Optimal Transport. ACM Trans. Graph. (SIGGRAPH) 38, 4 (2019). ↩↩