Uniform map of R3 colour space onto a discrete number line

Question

I'm thinking about theoretical colour palette formation.

I have to start with a locus of $1000^3$ points in $R^3$, with each colour component axis being a discrete variable $0 \le r, g, b < 1000$. (The resolution of 1000 is due to software constraints). This represents an RGB colour space - the cubic solid shown in the lower left of this diagram:

I have to decide on a scheme to choose up to $2^8$ of those points in a manner that attempts to get approximate uniform representation from each axis, and then map those points to an $R^1$ discrete space $0 \le p < 2^8$. The mapping doesn't need to be linear but that would make things easier.

Uniform method

If we choose $n$ values on each axis, then

$n = \lfloor 2^{8/3} \rfloor = 6$ values per axis

$6^3 = 216$ values

$ \frac {100 \cdot 6^3} {2^8} \approx 84\% $ p space usage

For each channel value $c_i$, for $0 \le i < 3$,

$c_i = \frac {1000} 6 mod\left( \lfloor \frac p {6^i} \rfloor, 6 \right) $

That method has perfect channel uniformity but wastes a lot (16%) of the p space.

The following is a generated visual representation of the uniform palette. The x-axis is red, the "short" y-axis is green, and the "long" y-axis is blue.

Bitfield method

Another method is to divide the colour channels into bit fields: for field bit count $f_i, 0 \le i < 3$:

$\sum_i f_i = 8$

$f = (3, 3, 2)$

$c_i = \frac {1000} {f_i} mod\left( \lfloor \frac p {f_{i-1}^i} \rfloor, f_i \right) $

$f_{i-1} = 1$ for $i = 0$.

This method has perfect p space usage but poor uniformity. Two of the channels have $2^3=8$ values per axis but the last only has $2^2=4$ values.

The following is a generated visual representation of the bitfield palette, with the same axes as the previous one.

I'd like to learn of another method to map p to the $R^3$ space that achieves better uniformity than the bit field method while still using all of the p space.

Answer 1

6*6*7 = 252, which is much closer to 256. If $R \in [0, 6)$, $G \in [0, 7)$, and $B \in [0, 6)$, the 8-bit indexed colour could be

$C = R*7*6 + G*6 + B$

That's pretty good.

I also tried a spherical packing. For a face-centred packing into a cube with points at all corners, I get that a pattern $2x + 1$ layers deep has $4x^3 + 6x^2 + 3x + 1$ points in it. When $x = 3$, the pattern has 172 points. When $x = 4$, the pattern has 365 points. So neither of those is any good... On the other hand, I just found a totally awesome way of visually representing non-leap-years.

Answer 2

This answer is partly composed of background info that may seem tangential, but it is all tied together and relies on a foundation of vision & color theory.

Stepping back just a moment, let me ask:

1. Which RGB colorspace are you working in? sRGB (gamma encoded)? or linear RGB (gamma 1.0 aka no gamma)?

2. In regards to uniformity — do you want it to me uniform in terms of the linear quantities of light? Or do you want it uniform in term of human visual perception?

3. I am a little unclear — are you trying to make a global color table where each image color is only one byte holding all three of RGB? Or are you just trying to get three 10 bit color channels (30 bits total) down to one single 8 bit pixel that holds all three R, G, and B?

Table for One?

I ask question 3 above because the purpose for having a global color table is to be able to have all three R,G,B values defined as 8 bits each, while the image's spatial data can be 8 bits per pixel to access this limited index of "full" colors in the table, improving visual appearance.

In a general sense there is no reason to have a table of colors where each color is the same data size as each pixel in the image. If your spatial image data is limited to one byte per pixel, then a table that is one byte per RGB tuple is superfluous because the index value will be the same as the color value. — though perhaps you have a use case I'm not aware of??

As I'm not clear on your use case, I am going to provide additional answer & information that is related but beyond the specific question you asked, a practice I follow here on the StackExc sites to address potential "XY problems".

Gamma, but not a frat house...

Because you are reducing down to 8 bits for all three color channels combined, I am going to assume you are gamma encoded — and you'd really need to be for such a low bit depth IF you are working with image data.

But on the other hand this if for texture maps, bump maps, displacement, etc., then linear is most likely better, and those use cases also instruct our choices differently.

But those typically work best as greyscale, so while I don't know your use case, I'll assume you are dealing with gamma encoded (RGB) image data.

Perception Deception

Colorspaces center around visual perception. One of the importance characteristics of vision is its non-linearity. Between luminance of about $8 cd/m^2$ to $520 cd/m^2$, visual perception follows a powercurve with an exponent of about 1/2.4 for $PerceivedLightness = Luminance^{0.42}$

This is used in image coding, so an 8bit image has a gamma applied (for sRGB it's effectively ^0.455) which increases the data density in the darker areas of the image and reduces the data in the lighter areas.

Gamma encoding is even more important for image data with lower bit depths, as you are reducing to a very small value, and you need to hide that loss of data by spreading it out to avoid perception of artifacts.

Heavy Light (Spectral Weighting)

In addition to lightness non-linearity, it is useful to know that the spectral weights of R, G, and B are far from equal. G makes up 71% of luminance, R 21%, and blue a mere 7%. (These coefficients are relative to linear light, and not gamma encoded values.)

Also, Red and Green cones are more dense in your fovea (center of vision) and blue cones are on your peripheral vision. Red and Green are most critical for resolving details.

In short, as far as perception is concerned, uniform data per channel is not needed.

And you can also use this to your advantage, and in fact many encoding schemes do. If you have an unbalanced data container as you do here, then put the most bits with GREEN. Note thought that even though blue is just 7%, we have high sensitivity for blue, so don't reduce the bit depth of blue anymore than needed to balance the data container.

At the risk of aging myself (LOL, I started programming when computers used paper punch tape) what you are essentially asking for is how color was handled in the 80s. "8 bit color" either used a pallette of 256 colors in a table like GIF, where each color in the table is made up of 24 bits (8 R, 8 G, 8 B) using the 8bit per pixel to access this index table OR the practice of spreading the RGB as 3 bits red, 3 bits green, and 2 bits blue in each pixel (this was referred to as "8bit true color", though "true" is a helluva stretch LOL).

As such, what you are doing is not without precident, and blue was given only 4 bits.

100 codes no waiting?

You mention coming from 1000 code values per channel - is each actually 1024 for 10 bits per channel? If so, then a bit shift is an easy/fast way to get down to three or two (though not visually optimum). This method is useful when speed is required.

Rout = Rin >> 7;
Gout = Gin >> 7;
Bout = Bin >> 8;

Dither or not...

BUT I am NOT recommending you just bitshift like this. This is essentially a truncation and leaves a lot to be desired. For a data reduction as severe as this, you really want to be dithering image data, and this goes for color tables as well.

Dithering is adding noise to the image data to breakup and randomize the transitions between code values. This has the effect of reducing the appearance of banding. There are a lot of well understood methods — here's a link to a description with code samples.

Non-linear weighting

Weighting green & red over blue applies to the case of a limited table as well — but something else worth mentioning in terms of a table is that at some point that data is going to be converted and displayed on a monitor with 8 bits per channel of R, G, B — yes??

So for your use case in your table, it could be useful to use a different gamma curve per color channel when converting to output (and of course when encoding on input use the inverse).

This would apply especially to the blue channel for your version of 3,3,2, your second example. I'd leave the top (blue #FF) and bottom (blue #00) alone, but for the middle two cases, consider the utility of adjusting the blue value relative to the R and/or G values. R&G are already defined against each other in the first chunk with blue #00.

So in the second chunk with blue at #55, the blue could be brighter, especially as the red or green gets brighter. In the third chunk, blue could get darker, especially as the red or green gets brighter. The idea here is to have the blue make up a perceptually similar amount of the second and third chunk. This will give you more colors that can be assigned to an image for a "natural" appearance.

sRGB is not a true perceptually uniform space like CIELAB (which is also not exactly uniform). sRGB "off" in the midranges so the mid-points using linear math are not the perceptual midpoints. For our second example, the second chunk might have blue at 60 to 66, and the third at 99 to 9F perhaps for better perceptual uniformity.

Because of blue's limited contribution to luminance, this by itself may give you a solution you are happy with.

Stop Thief!

Come back here with them bits!

This idea is a little more radical, but applies directly to your use-case of an 3,3,2 bit table.

BIT STEALING and INDEX WEIGHTING

Since you described your table or index as 1D, use index POSITION as a determining factor for weighting and/or stealing/sharing bits between red and blue.

For the purposes of this immediate discussion, green will never borrow or give up a bit, due to its importance in luminance. But Red and Blue can share a bit, and/or blue can be weighted based on index position. Values below are binary.

Implementation: Instead of R 111, G 111, B 11, use:

$ RangeBit: 1, Red: 11, Green: 111, Blue: 11 $

By taking a bit from red, and using it to define ranges of the index, blue will have the opportunity for more gradations though red will have less.

When the range bit is 1, then the red/blue ranges are split between the highest levels for those colors, and zero for those colors. the reason for this unusual split is to allow pure red/green or pure blue/green mixes at the top of the values for this range (i.e. to allow high and pure saturations).

In other words, 1 00 11 11 is equivalent to #0FF and 1 11 11 00 is #FF0. But 1 01 11 11 should probably map to something like #9FF.

While certain values or red and blue have to be together, strategic placement should maximize the available perceivable colors. Here's an experimental example:

Mapings of the binary values vs sRGB.

And using that example of maping brings us:

That's the basic "concept", and using 10% of $p$. Implementation is probably best using a LUT (see practical applications, below). Using a LUT makes it easier to move certain values around - notice that blue is not at all ordered as red and green are - this is intentional, to spread blue "around" and into areas where it will be most noticeable or appears to extend the very limited gamut.

Using a LUT for this make sit trivial to tweak or more individual mappings from the 8bit table to and from sRGB.

---

Space, the Other Data Reduction

Thus far we have been talking only of reducing the bits in a pixel (or table), with an assumption that the total number of pixels is the same, and that each pixel has the same about of RGB data (3,3,2).

But you can trade some spacial resolution for bit depth and gain a lot in terms of perceived quality. In fact bit depth is substantially more important to fidelity than spatial resolution (that is, you gain more in apparent fidelity by increasing bit depth vs horizontal resolution for the same increase in data-size).

And in fact, this trading of spacial resolution has been going on for decades, it is the core principal of 4:2:2 and 4:1:1 encoding schemes, where only the LUMA is full resolution and the color data is HALF or quarter resolution (respectively).

And remember that green is 71% of luminance.

So, for your example, you could increase the bit depth for GREEN, and then alternate the red and blue channels to every other pixel. To avoid perceptual artifacts like moire, you'd want to start each line with a different color, so odd lines start with green/red and even lines start with green/blue.

This is very similar to how modern cameras capture images — the Bayer filter in a camera's sensor makes a square quartet of pixels, one red, one blue, and two greens diagonal from each other. Debayering takes this RAW data and interpolates RGB values for each pixel.

In the case I'm describing with image data, your eye would be doing the "debayering" if you displayed the image without further manipulation, and your eye is quite capable of that do to perception features such as simultaneous contrast, contrast constancy, etc.

I am not certain if you'd find that 4 green bits and then either 4 red or 4 blue would be best, OR 5 green, then 3 red or 3 blue — but my gut feeling is the latter. Because green is the majority of luminance, and most responsible for perceiving details, I think it would make sense to give green the most weight.

As for the red and blue: Depending on your computational budget, the alternate pixels could just discard the unused channel — but I think averaging with nearest neighbors would yield better results. But to be sure, this encoding would be substantially slower in encoding than say, a LUT or a matrix.

If using a table, then there'd be a red/green or a blue/green table, and the one that would be grabbed would depend on if the pixel was odd or even.

Again, I don't know if this is appropriate to your use case, but this is a way to leverage perception to get the most from the 8 bit limitation you indicated.

---

Linear With A Twist

An important consideration is if the image data is linear or already encoded with a gamma curve. Some image operations are best performed in linear image data, and some other image operations are better performed on perceptually uniform image data (gamma encoded is a close relative to perceptually uniform, and can often serve that purpose within limits).

• Things like anti-aliasing, dithering, additive mix, or other linear maths usually provide best results when done in a linear space.

• Things like data-reduction, data compression, and perceptual adjustments often benefit when working in a perceptualy uniform space.

Your color examples are gamma encoded, so I assume that applies to your situation. Most of what I've discussed in this post works in a gamma encoded space.

---

PRACTICAL APPLICATION

Addressing Your Specific Need

Of course all of these use cases (including your own) require some form of transform to get to a displayable state. If the issue you are trying to solve is computational cost, then usually a look-up-table (LUT) is ideal.

A vectorized LUT with pre-calculated sRGB values for output for example is going to be very fast. For output, sorted by the index, and. the index allow direct access to the array element. The same LUT can be used in reverse for encoding to your 8 bit model by searching for a nearest sRGB value, then returning the index.

A LUT also allows you to tweak the conversion in specific areas. For instance, you may find you what more values mapped around the "knee" of the gamma curve, which makes sense for most images.

I realize this answer is a bit long, but I'm not clear on your sue case. If you could add a few words as to how you ae using this, I'll update my answer.

Thank you.

---

---

Brief Pedantic Comment:

RGB is a color "model", specifically a tristimulus model that is intended to represent the stimulation (or stimulate) of each of the three cone types in the eye.

A color "space" on the other hand is a model but also includes the definitions that make the numeric color values relate to an actual color (primaries, whitepoint, and transfer curve aka gamma).

E.g., the hex value #00BD00 in an RGB model is some kind of green. But what green? In all four swatches below, the native value is #00BD00. But that value means something different for each of the colorspaces shown.

I only mention this for clarity — a model defines the essential structure/concept/theory, but a space defines the functional measurements for practical application.

/End Pedantic Comment