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.

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.

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);
}

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.

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

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.