## Saturday, February 15, 2020

### Paint Palette to Color Gamut

Overview

In mid-2019, I published "How Paints Mix", outlining a method for mathematical simulation of color in paint mixing. This method can be applied in two distinct ways:
1. Color Mixing: Predict the digital color of an arbitrary mixture of primary paints.
2. Color Decomposition: Decompose a digital color into a primary paint mixing recipe.
My original article focused heavily on Mixing, leaving Decomposition as an afterthought. In this article, I'll lay out a much-improved decomposition method that works by translating an analog paint palette to a digital color gamut.

Decomposition by Random Optimization

Previously, to decompose a digital color, I used a simple random optimization method:
1. User provides a "target" digital color to decompose.
2. Start a timer.
3. Randomly generate a valid recipe and evaluate its color distance to the target.
4. If the color distance is less than the previous best, save the result and reset the timer.
5. Repeat #3-4 until 3 seconds have elapsed since the last timer reset.
6. Return the best known solution.
This algorithm is simple and works well enough, but has the drawbacks of being relatively slow (~5 seconds per decomposition), not repeatable, and not necessarily optimal.

Size of Solution Space

I initially implemented random optimization because I estimated that the solution space of possible recipes for a given palette was far too large to search exhaustively. Considering my baseline values for painting:
• Number of primary paints: 7
• Maximum number of ingredients per recipe: 4
• Mixing precision: 5% or 1/20
I reasoned that if any primary can have 21 possible values (0%, 5%, 10%,...100%), then the solution space could be as large as 21^7 or 1,800,000,000 recipes. While technically true that this represents an upper bound, this turns out to be an extremely inaccurate estimate.

When you account for the fact that recipes must sum to 100% and include no more than 4 ingredients with non-zero fractions, the solution space shrinks by an incredible 5 orders of magnitude to about 35,000 recipes. This solution space is then possible to generate and search exhaustively.

As a clerical note: I use the term "primary" loosely, to mean any paint in its pure, unmixed state, i.e. straight from the tube. Here are my primaries, all from Winsor & Newton's "Winton" line of oil paints:

Creating a Cookbook

Realizing that there is already a convenient term to describe an exhaustive collection of recipes, I began using the term "cookbook" to describe this database of colors. The main challenge of creating a cookbook is generating the set of all possible recipes. My method works as follows:
1. Generate an ingredient subset matrix. This is an n-choose-k aka binomial coefficient problem. For 7 primaries and a 4 ingredient max, there are nchoosek(7,4) = 35 ingredient subsets, i.e. 35 unique ways of picking 4 ingredients from a set of 7 when order is irrelevant. This result looks like:
• [1 2 3 4] Row 1
• [1 2 3 5] Row 2
• [1 2 3 6] Row 3
• [1 2 3 7] Row 4
• [1 2 4 5] Row 5
• ...
• [1 4 6 7] Row 19
• [1 5 6 7] Row 20
• [2 3 4 5] Row 21
• [2 3 4 6] Row 22
• ...
• [3 4 6 7] Row 33
• [3 5 6 7] Row 34
• [4 5 6 7] Row 35 (end)
2. Generate a fraction vector representing the set of all permitted values for a single ingredient. For 5% precision, this result looks like:
• [0.00 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 ... 0.90 0.95 1.00]
3. Generate a matrix for all possible 4-element permutations of the fraction vector, with repetition permitted. I use permn for this purpose. This result looks like:
• [0.00 0.00 0.00 0.00] Row 1
• [0.00 0.00 0.00 0.05] Row 2
• [0.00 0.00 0.00 0.10] Row 3
• ...
• [0.45 0.05 0.15 0.35] Row 83,861
• ...
• [0.45 0.85 0.10 0.10] Row 90,891
• ...
• [1.00 1.00 1.00 0.95] Row 194,480
• [1.00 1.00 1.00 1.00] Row 194,481 (end)
4. Delete all rows of the permutation matrix that do not sum to 1.00 or 100%. This winnows the list from 194,481 rows to 1,596 rows. This result looks like:
• [0.00 0.00 0.00 1.00] Row 1
• [0.00 0.00 0.05 0.95] Row 2
• [0.00 0.00 0.10 0.90] Row 3
• ...
• [0.20 0.20 0.05 0.55] Row 796
• [0.20 0.20 0.10 0.50] Row 797
• [0.20 0.20 0.15 0.45] Row 798
• ...
• [0.95 0.00 0.05 0.00] Row 1,594
• [0.95 0.05 0.00 0.00] Row 1,595
• [1.00 0.00 0.00 0.00] Row 1,596 (end)
5. Create a recipe matrix by copying the permutation matrix for each row of the ingredient subset matrix. This result looks like:
• [0.00 0.00 0.00 1.00 0.00 0.00 0.00] Row 1
• [0.00 0.00 0.05 0.95 0.00 0.00 0.00] Row 2
• [0.00 0.00 0.10 0.90 0.00 0.00 0.00] Row 3
• ...
• [0.05 0.00 0.25 0.00 0.00 0.10 0.60] Row 24,243
• [0.05 0.00 0.25 0.00 0.00 0.15 0.55] Row 24,244
• [0.05 0.00 0.25 0.00 0.00 0.20 0.50] Row 24,245
• ...
• [0.00 0.00 0.00 0.95 0.00 0.05 0.00] Row 55,858
• [0.00 0.00 0.00 0.95 0.05 0.00 0.00] Row 55,859
• [0.00 0.00 0.00 1.00 0.00 0.00 0.00] Row 55,860 (end)
6. Eliminate duplicate rows. This reduces the row count from 55,860 to 35,651.
7. Simulate each recipe, recording its reflectance spectrum and color in XYZ, RGB, and Lab formats.
8. Return the completed cookbook, totaling 17.3 MB (or 2.4 MB if excluding reflectance spectra which are not strictly necessary). The entire process of generating the cookbook for this set of parameters takes about 18 seconds.

Decomposition by Cookbook

With the cookbook complete, decomposition is very fast, accurate, and repeatable. A target color in RGB format is converted to Lab color space, its color distance to each cookbook recipe is evaluated, and the recipe with minimum color distance to the target is returned. This happens in about 0.04 seconds, permitting decomposition of about 24 colors per second, or ~125x the speed of random optimization.

There are a few finer details required to make this process work optimally:
• If supplying target colors from an RGB image, the image's value domain must be aligned with the cookbook's value domain. In other words, the image must be scaled such that its pure black matches the darkest color in the cookbook, and so forth for the lightest. This assumes the palette can achieve a near-black and a near-white color. I use imadjust for this purpose, and it is functionally equivalent to a Levels adjustment in Photoshop/GIMP.
• Lab colors must be derived in a consistent fashion between image and cookbook. In other words, since image colors can only be derived by RGB > XYZ > Lab, then the cookbook Lab colors should be derived by Reflectance > XYZ > RGB > XYZ > Lab, rather than Reflectance > XYZ > Lab. This is counter-intuitive but greatly improves color matching accuracy. I use Bruce Lindbloom's color conversion equations and an illuminant of D65.

Other Uses for a Cookbook

Although my initial interest in cookbooks was color decomposition, I realized that they had many other interesting and helpful applications. As a whole, they describe the complete color gamut (set of possible colors) for a given palette. What does this look like? How does it change as a function of which primaries are permitted? How does mixing precision affect it?

Digital color is 3-dimensional, whether working on RGB, HSV, XYZ, or Lab color space. This makes visualizing it on a 2D monitor non-trivial. Here, I'll show two possible visualization methods, one theoretical and one applied.

Theoretical: Point Cloud Cross-Sections

Each recipe corresponds to a single point in 3D color space, so a cookbook corresponds to a point cloud in 3D space. To fully view this, a cross-section plane can be swept through the point cloud at varying lightness (L) values, and shown from an isometric and front view. For the baseline parameter set:

Notice that there is much higher recipe density at lower L (lightness) values. This is because oil primaries tend to be very dark to maximize their economy, and because paint mixes tend to darken more readily than lighten. To reduce the spatial gaps between recipes, especially on the lighter end of the color gamut, the precision can be increased from 1/20 to 1/40:

In reality, paint mixing is continuous rather than discretized by a fixed precision, so the gaps between recipes in this scatter-plot visualization are an artifact of this simplifying assumption.

For the sake of curiosity, the cookbook may be calculated such that it allows only 2 ingredients per recipe.

Here, distinct nodes representing pure yellow and pure white (the two brightest primaries) can be seen, with paths sweeping toward them from the other primaries. Blue can be seen transitioning through green on its way to yellow, and burnt sienna nearly maintains a=0 and b=0 as it transitions to white, a truly neutral gray.

Suppose the ingredient limit is increased from 2 to 3:

The color gamut fills in considerably, but there are still significant gaps. Overshooting the 4-ingredient baseline, the color gamut may be evaluated for 5-ingredient recipes:

Notice that the 5-ingredient color gamut is not significantly different from the 4-ingredient color gamut. There is more complexity, but the result is effectively the same. This corroborates my initial intuition of 4 ingredients per recipe being the "sweet spot" of balancing accuracy with complexity. It's also in line with traditional oil painting wisdom that a recipe needs at most 3 primaries plus white, for 4 ingredients total.

Paring the palette down just to these essential primaries - yellow, red, blue, white:

As expected, this color gamut has the same bounding box as with 7 primaries, and is nearly as full. This shows that the non-essential primaries - the browns and green - are not strictly necessary from a chromatic perspective, but practically helpful to have on hand.

Suppose that the palette includes only neutral or cool primaries:

And similarly for neutral or warm primaries:

Applied: Image Fit

Another way of visualizing a cookbook's color gamut is comparing it against a reference image. For paint mixing applications, this gives some intuition about how well a palette can recreate a provided image. Suppose this is the reference image:

By evaluating the minimum color distance between image and cookbook for each pixel, the palette can be tailored to the choice of image. Returning to the baseline parameter set of 7 primaries, 4 ingredients, and 5% precision, and downsampling the image for speed, the result is as follows:

Overall, the fit is very good - the maximum color error is ~1.7 JND, or just noticeable differences, and most of the image is below 1.0 JND. Unsurprisingly, the largest errors occur in the brightest region of the image. Suppose both browns - burnt sienna and burnt umber - are eliminated from the palette. The result is as follows:

The fit is noticeably worse, suggesting that we at least one of the browns should be retained. Applying my artistic intuition, suppose that burnt umber is returned to the palette:

And this is good result. The maximum error is no higher than with the full palette, while the number of primaries has been reduced from 7 to 6, and correspondingly the cookbook recipe count has been reduced from 35,000 to 16,000. This result indicates that there is no need for burnt sienna in this particular image. Its elimination reduces the amount of paint required, and speeds up decomposition calculations by almost a factor of 2.

These palette evaluations computationally expensive, hence the need for heavy downsampling. The results echo the traditional oil painting wisdom of using a limited palette consisting of chromatically orthogonal pigments. This method provides a quantitative rationale for this centuries-old technique.

Conclusion

Cookbooks are an extremely powerful tool for color decomposition, and provide quantitative insight into the traditional oil painting concept of a limited palette.