Compute nearest color

[FPiette 363]

I'm writing an application which read data from an external one. An XML file is used between.

 

The external application has color defined by names while in my application, I have ARGB values. It is trivial to convert from color name to ARGB value:
 

function ConvertGpxColor(const S : String) : UInt32;
begin
    //                                                 AABBGGRR
    if      SameText(S, 'Red')         then Result := $FF0000FF
    else if SameText(S, 'Green')       then Result := $FF00FF00
    else if SameText(S, 'Yellow')      then Result := $FF00F0F0
    else if SameText(S, 'Blue')        then Result := $FFFF4040
    else if SameText(S, 'Magenta')     then Result := $FFFE01FE
    else if SameText(S, 'Cyan')        then Result := $FFFFFF00
    else if SameText(S, 'White')       then Result := $FFFFFFFF
    else if SameText(S, 'Black')       then Result := $FF000000
    else if SameText(S, 'DarkRed')     then Result := $FF000060
    else if SameText(S, 'DarkGreen')   then Result := $FF006000
    else if SameText(S, 'DarkYellow')  then Result := $FF008080
    else if SameText(S, 'DarkBlue')    then Result := $FF600000
    else if SameText(S, 'DarkMagenta') then Result := $FF600060
    else if SameText(S, 'DarkCyan')    then Result := $FF808000
    else if SameText(S, 'LightGray')   then Result := $FFC0C0C0
    else if SameText(S, 'DarkGray')    then Result := $FF606060
    else if SameText(S, 'Transparent') then Result := $00000000
    else                                    Result := $FFC0C0C0;  // Light Gray
end;

In my application, the user can select any ARGB colors using a color dialog.

Now I must write the XML file for the external application and convert my ARGB colors to the name. For original values, there is no problem finding an exact match. But for other colors, undefined in the external application, I want to find the nearest color name. The alpha channel can be ignored.

 

I tough about computing a distance between colors and pick the color name having the smallest distance. The distance could be computed considering the RGB channels as axis of a space volume where a distance in a 3-dimensional volume has a well known formula. But will this give a visually correct result ? Maybe a formula specific to color has already been designed?

 

 

 

[Der schöne Günther 306]

I'm not sure if the RGB space the right choice for an approach to subjective perception which colour is the closest.

Have you considered HSL/HSV?

 

HSL and HSV - Wikipedia

Edited January 7, 2021 by Der schöne Günther

[shineworld 68]

If you can define a palette of accepted colors you can check the color closer to one of the palette.

In past, I've made a program with fixed palette colors and I need to import PNG or other formats and convert them to a palletized bmp.
Attached a very old pas file, used in a Borland Builder C++ 3.0, that I've used to reduce any color to a palletized color.
Function RecuceColors.

Is very old however...

 

my caller:
 

Graphics::TBitmap* __fastcall QImageManager::CreateBitmapPaletteFromBitmap24BPP(Graphics::TBitmap* Bitmap)
{
  if (FPalette != NULL && FPalette->ColorCount != 0)
  {
    // creates paletted bitmap
    Graphics::TBitmap* BitmapPalette = ReduceColors
    (
      Bitmap,
      rmPalette,
      dmNearest,
      FPalette->ColorBits,
      FPalette->HPalette
    );
    return BitmapPalette;
	}
	else
		return NULL;
}

 

 

ColorFunctions.pas

Edited January 7, 2021 by shineworld

[FPiette 363]

23 minutes ago, shineworld said:

If you can define a palette of accepted colors you can check the color closer to one of the palette.

That's what I explained in my question. What I'm looking for is an algorithm to compute the color closer to a list of colors.

 

24 minutes ago, shineworld said:

ColorFunctions.pas

Thanks for your code. This is not exactly what I'm looking for. I don't play with bitmap at all and no dithering is obviously needed. In your code, TFastColorLookup.Lookup actually implement the distance as I said in my question in the RGB space.

[timfrost 73]

For this sort of question I always used to go to www.efg2.com to find the answer, usually with success.  It had code samples for all sorts of graphics and color algorithms.  The site has gone now, but if you go to that URL, it has links to the Internet Archive where it can all still be found.  A bit slower to navigate now, but perhaps worth a look.   

[mvanrijnen 121]

Use HLS/HSL colorspace for distance ?

 

Edited January 7, 2021 by mvanrijnen

[FPiette 363]

11 minutes ago, timfrost said:

it has links to the Internet Archive where it can all still be found.

And this site experience a 404 error. Will retry later. Thanks.

[FPiette 363]

Found this: https://en.wikipedia.org/wiki/Color_difference

And there is a CIEDE2000 distance computation C++ implementation on GitHub: https://github.com/gfiumara/CIEDE2000

I will port this code to Delphi.

 

Thanks everybody.

 

Edited January 7, 2021 by FPiette

[Anders Melander 1630]

41 minutes ago, FPiette said:

And there is a CIEDE2000 distance computation C++ implementation on GitHub: https://github.com/gfiumara/CIEDE2000

I will port this code to Delphi.

Please post it here (or in a Git repository somewhere) when you're done.

It's probably too computationally expensive for the stuff I use color distance functions for, but I'd like to give it a go regardless.

 

Here are the ones I use for stuff like flood fill and magic wand selection with tolarance, dithering etc.
The ColorDistanceRGBA function gives a fast approximation of "visual" difference and is based on this: https://www.compuphase.com/cmetric.htm

 

interface

//------------------------------------------------------------------------------
//
//      Color distance functions
//
//------------------------------------------------------------------------------
function ColorDistanceSimpleRGB(Old, New: TColor32): Integer;
function ColorDistanceRGBA(Old, New: TColor32): Integer; // Note: Not linear. Visual difference.
function ColorDistanceRGBALinear(Old, New: TColor32): Integer;
function ColorDistanceRGBLinear(Old, New: TColor32): Integer;
function ColorDistanceAverageRGB(Old, New: TColor32): Integer;
// The HSV values of the first (Old) parameter is cached so when comparing
// multiple values you should attempt to keep the first parameter constant.
function ColorDistanceHue(Old, New: TColor32): Integer;
function ColorDistanceSaturation(Old, New: TColor32): Integer;
function ColorDistanceBrightness(Old, New: TColor32): Integer;

implementation

//------------------------------------------------------------------------------
//
//      Color distance functions
//
//------------------------------------------------------------------------------
function ColorDistanceSimpleRGB(Old, New: TColor32): Integer;
begin
  if (Old <> New) then
    Result := 255
  else
    Result := 0;
end;

function ColorDistanceRGBA(Old, New: TColor32): Integer;
begin
  if (Old = New) then
    Exit(0);

  if (Old and $FF000000 = 0) xor (New and $FF000000 = 0) then
    Exit(255);

  var AlphaOld := AlphaComponent(Old);
  var AlphaNew := AlphaComponent(New);

  if (AlphaOld <> AlphaNew) then
  begin
    if (AlphaOld <> 255) then
      Old := ColorScale(Old, AlphaOld);
    if (AlphaNew <> 255) then
      New := ColorScale(New, AlphaNew);
    EMMS;
  end;

  // See "Colour metric" by Thiadmer Riemersma
  // http://www.compuphase.com/cmetric.htm
  // Modified to consider alpha. Adjusted to maintain 0..255 range
  var Mean := (RedComponent(Old) + RedComponent(New)) div 2;

  var dA := AlphaNew - AlphaOld;
  var dR := RedComponent(New) - RedComponent(Old);
  var dG := GreenComponent(New) - GreenComponent(Old);
  var dB := BlueComponent(New) - BlueComponent(Old);

  Result := Round(Sqrt(( dA*dA + (((512+Mean)*dR*dR) shr 8) + ((dG*dG) shl 2) + (((767-Mean)*dB*dB) shr 8)) / 4));
end;

function ColorDistanceRGBALinear(Old, New: TColor32): Integer;
begin
  if (Old = New) then
    Exit(0);

  if (Old and $FF000000 = 0) xor (New and $FF000000 = 0) then
    Exit(255);

  var AlphaOld := AlphaComponent(Old);
  var AlphaNew := AlphaComponent(New);

  if (AlphaOld <> AlphaNew) then
  begin
    if (AlphaOld <> 255) then
      Old := ColorScale(Old, AlphaOld);
    if (AlphaNew <> 255) then
      New := ColorScale(New, AlphaNew);
    EMMS;
  end;

  var dA := AlphaNew - AlphaOld;
  var dR := RedComponent(New) - RedComponent(Old);
  var dG := GreenComponent(New) - GreenComponent(Old);
  var dB := BlueComponent(New) - BlueComponent(Old);

  Result := Round(Sqrt(( dA*dA + dR*dR + dG*dG + dB*dB) / 4 ));
end;

function ColorDistanceRGBLinear(Old, New: TColor32): Integer;
begin
  if (Old = New) then
    Result := 0
  else
  // All transparent colors are considered equal regardless of RGB
  if (Old and $FF000000 <> $FF000000) and (New and $FF000000 <> $FF000000) then
    Result := 0
  else
  // Difference in transparency = max difference
  if (Old and $FF000000 = 0) xor (New and $FF000000 = 0) then
    Result := 255
  else
  begin
    var dR := RedComponent(New) - RedComponent(Old);
    var dG := GreenComponent(New) - GreenComponent(Old);
    var dB := BlueComponent(New) - BlueComponent(Old);

    Result := Round(Sqrt(( dR*dR + dG*dG + dB*dB) / 3 ));
  end;
end;

function ColorDistanceAverageRGB(Old, New: TColor32): Integer;
asm
    AND       EAX,$00FFFFFF
    AND       EDX,$00FFFFFF
    MOVD      MM0,EAX
    MOVD      MM1,EDX
    PSADBW    MM0,MM1
    MOVD      EAX,MM0
    IMUL      EAX,$555555
    SHR       EAX,24
  //Result := ((C shr 16 and $FF) + (C shr 8 and $FF) + (C and $FF)) div 3;
end;

var
  HSLCacheColor: TColor32 = 0;
  HSLCacheH: Byte = 0;
  HSLCacheS: Byte = 0;
  HSLCacheL: Byte = 0;

function ColorDistanceHue(Old, New: TColor32): Integer;
var
  Z, A, B: Byte;
begin
  if (Old = New) then
    Exit(0);

  if (Old and $FF000000 = 0) xor (New and $FF000000 = 0) then
    Exit(255);

  if (Old and $FF000000 <> New and $FF000000) then
  begin
    if (Old and $FF000000 <> $FF000000) then
      Old := ColorScale(Old, AlphaComponent(Old));
    if (New and $FF000000 <> $FF000000) then
      New := ColorScale(New, AlphaComponent(New));
    EMMS;
  end;

  if (Old <> HSLCacheColor) then
  begin
    HSLCacheColor := Old;
    RGBtoHSL(Old, HSLCacheH, HSLCacheS, HSLCacheL);
  end;
  A := HSLCacheH;
  RGBtoHSL(New, B, Z, Z);
  Result := Abs(A - B);
end;

function ColorDistanceSaturation(Old, New: TColor32): Integer;
var
  Z, A, B: Byte;
begin
  if (Old = New) then
    Exit(0);

  if (Old and $FF000000 = 0) xor (New and $FF000000 = 0) then
    Exit(255);

  if (Old and $FF000000 <> New and $FF000000) then
  begin
    if (Old and $FF000000 <> $FF000000) then
      Old := ColorScale(Old, AlphaComponent(Old));
    if (New and $FF000000 <> $FF000000) then
      New := ColorScale(New, AlphaComponent(New));
    EMMS;
  end;

  if (Old <> HSLCacheColor) then
  begin
    HSLCacheColor := Old;
    RGBtoHSL(Old, HSLCacheH, HSLCacheS, HSLCacheL);
  end;
  A := HSLCacheS;
  RGBtoHSL(New, Z, B, Z);
  Result := Abs(A - B);
end;

function ColorDistanceBrightness(Old, New: TColor32): Integer;
var
  Z, A, B: Byte;
begin
  if (Old = New) then
    Exit(0);

  if (Old and $FF000000 = 0) xor (New and $FF000000 = 0) then
    Exit(255);

  if (Old and $FF000000 <> New and $FF000000) then
  begin
    if (Old and $FF000000 <> $FF000000) then
      Old := ColorScale(Old, AlphaComponent(Old));
    if (New and $FF000000 <> $FF000000) then
      New := ColorScale(New, AlphaComponent(New));
    EMMS;
  end;

  if (Old <> HSLCacheColor) then
  begin
    HSLCacheColor := Old;
    RGBtoHSL(Old, HSLCacheH, HSLCacheS, HSLCacheL);
  end;
  A := HSLCacheL;
  RGBtoHSL(New, Z, Z, B);
  Result := Abs(A - B);
end;

 

[FPiette 363]

14 hours ago, Anders Melander said:

Please post it here (or in a Git repository somewhere) when you're done.

This will be part of an OpenSource application handling OpenStreetMap maps (And other similar map sources). The color distance is needed to import/export GPX files which contain tracks recorded by GPS device.

 

Quote

Here are the ones I use for stuff like flood fill and magic wand selection with tolarance, dithering etc.

Thanks a lot for sharing.

[DelphiSpass 0]

Hello Anders,

thank you for sharing the code. Something is missing.

The function ColorScale() I can not find.

While, the function EMMS, it is the one which I found in JclGraphUtils?

Besides, you mentioned Dithering, if I may ask, do you have code for dithering, I would need that for a project, where I want

to dither a picture to a reduced palette with only a few colors, where your ColorDistanceRGBA would for sure be also an important part of it.

 

[Anders Melander 1630]

41 minutes ago, DelphiSpass said:

The function ColorScale() I can not find.

https://github.com/graphics32/graphics32/blob/78279b925c6110000666af7b3b48e76090f36289/Source/GR32_Blend.pas#L137

https://graphics32.github.io/Docs/Units/GR32_Blend/Routines/ColorScale.htm

function ColorScale(F, B: TColor32): TColor32;

 

44 minutes ago, DelphiSpass said:

While, the function EMMS, it is the one which I found in JclGraphUtils? 

The functions in the JCL were copied from Graphics32. Use the one in Graphics32 instead.

 

45 minutes ago, DelphiSpass said:

Besides, you mentioned Dithering, if I may ask, do you have code for dithering

Yes I do.

I've been working on getting it ready for release and integration into Graphics32 for several years. The dithering works fine but I'm not satisfied with the quality of the accompanying Octree quantizer I've implemented so it has all been postponed until I have implemented something better. FWIW, I'm not using any of the above color distance functions since the color mapping is implicit with the Octree algorithm (the one I'm using anyway). I'm also not quantizing and dithering in sRGB color space (sRGB is what you'd normally just call RGB). Instead I'm either using the Linear RGB (gamma corrected RGB) or OKlab color spaces. OKlab appears to be the best there is right now for perceptual color mapping and distance.

 

If your quality requirements aren't too strict you can just use my old quantizer (also Octree) and dithering routines in the GifImg unit:

https://docwiki.embarcadero.com/Libraries/Sydney/en/Vcl.Imaging.GIFImg.ReduceColors

[DelphiSpass 0]

Thanks, I am using GR32. I am not yet so much into the color spaces, but I also read about better using other spaces for good results instead of sRGB.

For my app its important to have high quality color reduction, based on visible similarity.

Finally, I need both, color reduction with and without dithering.

I am even thinking about, if for my app it could be little bit more important to care about the hue, instead of the other parameters, for a nearest decision. Or I would add settings,

so the user can choose, and take which result he likes more. (was thinking even about using your ColorDistanceHue/Brightness/Sat.. and somehow to combine it in a way that the user can give

it different weights in the decision, but thats maybe a luxury wish for the future at the moment).

What I read is that converting to Lab (cielab), or HLC = LCh = LCH, or HSV makes sense, and Delta E from CIE2000 is good.

Now, I just read from you about the OKlab, this looks quite good!

Maybe I should go this way and convert it to OKlab. With the GIF, I think, it will not the right way for me.

In fact at the end its even more complicated, a picture with full colors, will need to be mapped to a small color palette (approx 400colors), but even more the user

can choose that the result will use only a max amount of colors from that, e.g. 60 colors. 🙂 🙂 To be honestly, I also thinking since a while, what would be the criteria,

which colors to throw away 🙂 I think the solution for this detail will be, to first map to the 400 colors, which can result in a picture, which can then have even less

then the full palette, lets say e.g. 300 colors,

and then sort the Distances, and then to remove colors beginnging with the smallest distance. Practical experiments will show...

But, one step after another... first I am happy, if the mapping with dithering principally works fine, and allows some adjustments.

I you have any, even not yet satisfying code, I would for sure like to try it.

[Anders Melander 1630]

The quantizer and dithering in GifImg isn't tied the GIF format; It's completely independent.  It is limited to max 256 colors though (AFAIR).

 

I don't think you should start by inventing your own quantization algorithm. Start with one of the known ones so you at least can learn the problem space first (and avoid the usual mistakes).

Here's a few links to get you started:

• RgbQuant.js: color quantization lib
  https://github.com/leeoniya/RgbQuant.js

• nQuantCpp: top 6 color quantization algorithms
  https://github.com/mcychan/nQuantCpp/

• Top 3 color quantization algorithms (same author as above, older article)
  https://www.blackslate.io/articles/color-quantization-algorithm

A good one to start with is Xialoin Wu's algorithm (https://www.ece.mcmaster.ca/~xwu/cq.c) It performs well, with good results, and the algorithm is fairly simple. I think that is also the one I will implement next (when I get time; there's far to many interesting projects to work on).

This one is also a good read: https://bottosson.github.io/posts/colorwrong/

 

I will see if I can find time to wrap some code up for you. It's a pluggable framework so you can extend it with new quantization, dithering, and color lookup algorithms, and color spaces. As far as I remember there are no dependencies on Graphics32. Here it is in action (using Linear RGB color space AFAIR):

[DelphiSpass 0]

The screenshot looks interesting. Thanks for the links, will take some time to go trough it.

Just for fun, I offline typed the code into Delphi, from the OKlab page, that you suggested,

to convert from sRGB to linear and to OKlab.

Will experiment with it this week, for interest. Can post it later, when I think it works.

 

[angusj 126]

This link to the Color Quantization unit in my own Delphi Graphics Library may also be useful to you.

The code there should be quite easy to adapt to Graphics32.

[Anders Melander 1630]

1 hour ago, angusj said:

This link to the Color Quantization unit in my own Delphi Graphics Library may also be useful to you.

The code there should be quite easy to adapt to Graphics32.

That's Octree, right?

How does it deal with this, when reduced from 17 to 16 colors:

[angusj 126]

53 minutes ago, Anders Melander said:

How does it deal with this, when reduced from 17 to 16 colors:

Yes, several bugs needed fixing which  I've done and just uploaded.

And I'm expecting you'll find a few more 😱.

Anyhow, thanks 😁.

[Anders Melander 1630]

Actually, that bitmap wasn't directed at your implementation in particular - because I haven't tried it; It's just a bitmap that Octree in general has problems with. But, I'll take it; You're welcome 🙂

 

The problem is that Octree doesn't reduce the root node (the MSB of the RGB, which represent 2^3=8 color cubes), or move colors between adjacent nodes.

 

So lets say you are reducing an 1 billion pixel image with 1 million red/blue colors+1 green pixel. Octree will represent this as a MSB color cube that only contains a single color (green in this case) with a pixel count of 1 and a bunch of other cubes representing the other 1 million colors/1 billion pixels.

If you now reduce this to 16 colors (or any other count for that matter) you will end up with green+15 red/blue colors. And that is just one of the problems with Octree.

Of course you can tweak Octree to work around the various issues is has but I feel that that is just polishing a turd.

That said, Octree is fast so one just have to be aware of the limitations and only use it when performance is more important than fidelity.

Edited April 9 by Anders Melander

[angusj 126]

1 hour ago, Anders Melander said:

Of course you can tweak Octree to work around the various issues is has but I feel that that is just polishing a turd.

Indeed, Octree does have significant limitations just as you've illustrated above.

Anyhow, here's the image reduced to 16 colors using (a slightly modified) median cut ...

Edited April 9 by angusj