Color similarity/distance in RGBA color space

Question

How to compute similarity between two colors in RGBA color space? (where the background color is unknown of course)

I need to remap an RGBA image to a palette of RGBA colors by finding the best palette entry for each pixel in the image*.

In the RGB color space the most similar color can be assumed to be the one with the smallest euclidean distance. However, this approach doesn't work in RGBA, e.g., Euclidean distance from rgba(0,0,0,0) to rgba(0,0,0,50%) is smaller than to rgba(100%,100%,100%,1%), but the latter looks much better.

I'm using premultiplied RGBA color space:

r = r×a
g = g×a
b = b×a

and I've tried this formula (edit: See the answer below for better formula):

Δr² + Δg² + Δb² + 3 × Δa²

but it doesn't look optimal — in images with semitransparent gradients it finds wrong colors that cause discontinuities/sharp edges. Linear proportions between opaque colors and alpha seem fishy.

What's the optimal formula?

---

*) for simplicity of this question I'm ignoring error diffusion, gamma and psychovisual color spaces.

---

Slightly related: if you want to find nearest color in this non-Euclidean RGBA space, vp-trees are the best.

Buber

Super cool question! I worry about background color not being a variable, however. I think that you should treat it as one. – Knowlton

Sure, I can treat it as a variable, but that will be unknown variable :) The whole point of RGBA is to allow any background. – Buber

Are you looking for a formula that will give you "distance" that is true for all possible background colors? Or just for one unknown background color? – Zindman

I'm also not sure regarding (1-a) in your formula. Which "a" is it? Should it be delta(a)? – Zindman

In my formula a is opacity of color I'm looking for (perhaps should be min(a₁,a₂)?). The exact distance doesn't have to be true for any particular color, just an approximation of similarity given constraint of unknown background (could be average distance between colors computed for all possible backgrounds?) – Buber

Relevant question: "How to automatically generate N “distinct” colors?". – Leatherjacket

possible duplicate of Followup: Finding an accurate "distance" between colors – Hackney

Answer 1

Finally, I've found it! After thorough testing and experimentation my conclusions are:

• The correct way is to calculate maximum possible difference between the two colors.
  Formulas with any kind of estimated average/typical difference had room for discontinuities.

• I was unable to find a working formula that calculates the distance without blending RGBA colors with some backgrounds.

• There is no need to take every possible background color into account. It can be simplified down to blending maximum and minimum separately for each of R/G/B channels:

  1. blend the channel in both colors with channel=0 as the background, measure squared difference
  2. blend the channel in both colors with channel=max as the background, measure squared difference
  3. take higher of the two.

Fortunately blending with "white" and "black" is trivial when you use premultiplied alpha.

The complete formula for premultiplied alpha color space is:

rgb *= a // colors must be premultiplied
max((r₁-r₂)², (r₁-r₂ - a₁+a₂)²) +
max((g₁-g₂)², (g₁-g₂ - a₁+a₂)²) +
max((b₁-b₂)², (b₁-b₂ - a₁+a₂)²)

C Source including SSE2 implementation.

Buber

a1 or a2 can be negative? – Malave

@TomaszPosłuszny I'm assuming all numbers are in range from 0 to 1. – Buber

In your formula you mean a₁ - a₂ (In the linked code it is correct) – Dermatology

@Dermatology I think the formula here is correct. It's just written differently due to -(a - b) == -a + b – Buber

This can be used to solve the issue of the OSX color matching discrepancies of the Robot.getPixelColor(int x, int y). – Brutish

Answer 2

Several principles:

1. When two colors have same alpha, rgbaDistance = rgbDistance * ( alpha / 255). Compatible with RGB color distance algorithm when both alpha are 255.
2. All Colors with very low alpha are similar.
3. The rgbaDistance between two colors with same RGB is linearly dependent on delta Alpha.

double DistanceSquared(Color a, Color b)
{
    int deltaR = a.R - b.R;
    int deltaG = a.G - b.G;
    int deltaB = a.B - b.B;
    int deltaAlpha = a.A - b.A;
    double rgbDistanceSquared = (deltaR * deltaR + deltaG * deltaG + deltaB * deltaB) / 3.0;
    return deltaAlpha * deltaAlpha / 2.0 + rgbDistanceSquared * a.A * b.A / (255 * 255);
}

Royce

Answer 3

My idea is integrating once over all possible background colors and averaging the square error.

i.e. for each component calculate(using red channel as example here)

Integral from 0 to 1 ((r1*a1+rB*(1-a1))-(r2*a2+rB*(1-a2)))^2*drB

which if I calculated correctly evaluates to:

dA=a1-a2
dRA=r1*a1-r2*a2
errorR=dRA^2+dA*dRA+dA^2/3

And then sum these over R, G and B.

Filiation

Answer 4

First of all, a very interesting problem :)
I don't have a full solution (at least not yet), but there are 2 obvious extreme cases we should consider:
When Δa==0 the problem is similiar to RGB space
When Δa==1 the problem is only on the alpha 1-dim space
So the formula (which is very similar to the one you stated) that would satisfy that is:
(Δr² + Δg² + Δb²) × (1-(1-Δa)²) + Δa² or (Δr² + Δg² + Δb²) × (1-Δa²) + Δa²

In any case, it would probably be something like (Δr² + Δg² + Δb²) × f(Δa) + Δa²

If I were you, I would try to simulate it with various RGBA pairs and various background colors to find the best f(Δa) function. Not very mathematic, but will give you a close enough answer

Zindman

Answer 5

I've never done it, but theory and practice say that converting the RGB values in the image and the palette to luminance–chrominance will help you find the best matches. I'd leave the alpha channel alone, as transparency should have little to nothing to do with the 'looking better' part.

This xmass I made some photomosaics for presents using open-source software that matches fragments of the original image to a collection of images. That seems like a harder problem than the one you're trying to solve. One of them programs was metapixel.

Lastly, the best option should be to use an existing library to convert the image to a format, like PNG, in which you can control the palette.

Mcneil

Sorry, but that doesn't answer my question. Color spaces you suggest do not have alpha component, and problem is the same for YUV vs YUVA, YCBCR vs YCBCRA, etc. I can handle 3-dimensional opaque color, it's the alpha with unknown variable that's the problem. Also, I am writing a library for PNG. – Buber

Also, I am writing a library for PNG Oops! I sill don't understand from your question why the A value can't be left as is, nor what is the objective criteria for "looks better". – Mcneil

a can't be left as is, because it influences how other 3 channels look like (in my question I've given example how worst possible match in RGB can at the same time be best choice in RGBA). Objective criteria for "looks better" are probably part of the answer, perhaps if you tried two candidate colors on every possible background color, one of them would more often look more similar to desired color. – Buber

@porneL Write your self a program that asks you which color looks better, record the results, and then do regression analysis to come up with a pattern. It's something like what graphic systems do to let users calibrate font smoothing to what "looks better". To guard against your own biases, you can ask different people to run the program and send in the results. – Mcneil