How to create color picker for bmp image?

Question

Programming

Let's say I have a 24-bit image, for example this.

I want to convert its color palette, say 4 bits, 16 colors.
Ie get something like

How do I create such a palette?
I tried to do this - split the image into 16 equal parts and find its average color for each part (well, that is, the arithmetic mean for R, G, B)
But the colors in the resulting palette came out dirty and dull or something. Here is such a palette that came out -

That is, there are no pronounced colors, such as black, dark brown, normal orange, green ..
Then another problem is how to choose the right color in the palette .. I sorted by brightness and chose too by the nearest brightness, but most likely this is wrong ..
Here is my code, please tell me how to add / redo it so that it works better)

void Image::create_color_palette(int k) {

  int stepW=BMInfoHeader.Width/sqrt(k);//ширина области, в которой буду икать цвет
  int stepH=BMInfoHeader.Height/sqrt(k);//высота области, в которой буду икать цвет

  int R=0,G=0,B=0,step=0;

  Palette=new RGBQUAD[k];//выделяю память на палитру

  for (int i=0;i<BMInfoHeader.Height;i=i+stepH)
  for (int j=0;j<BMInfoHeader.Width;j=j+stepW)
  {
    for (int i2 = i; (i2 < i+stepH) && (i2<BMInfoHeader.Height); i2++)//если stepH=stepW=60 - то цвет будет искаться в квадратике 60x60
    for(int j2 = j;(j2<j+stepW)&& (j2<BMInfoHeader.Width);j2++)//
    {
      R+=Rgbtriple[i2][j2].Red;
      G+=Rgbtriple[i2][j2].Green;
      B+=Rgbtriple[i2][j2].Blue;
    }
    R/=stepH*stepW;//среднее арифметическое
    G/=stepH*stepW;
    B/=stepH*stepW;

    Palette[step].Red=R;//добавляю нужный цвет в палитру
    Palette[step].Green=G;
    Palette[step].Blue=B;
    step++;
  }

  RGBQUAD tmp;
for (int i = 1; i < k; i++)//сортировка по яркости
  for(int j = k-1; j > i; j-- )
  {
    if(Y_px_4(Palette[j-1])>=Y_px_4(Palette[j]))//Y_px_4 - яркость пикселя RGBQUAD
    {
      tmp=Palette[j-1];
      Palette[j-1]=Palette[j];
      Palette[j]=tmp;
    }
  }
}

int Image::find_color_in_palette(int k,RGBTRIPLE px)
{
  for(int i=0;i<k;i++)
  {
    if (Y_px_4(Palette[i])>=Y_px_3(px))
    {
      return i;
    }
  }
  return k-1;
}

Here is the result of my code -

UPD - after normal sorting)

UPD - through the sum of squared deviations

UPD - after increasing the contrast of the palette

Answer 1

There seems to be a lot of useful information with code here:
www.enlight.ru/demo/faq/smth.phtml?query=alg_clr_dith
Keywords: Clustering (Quantization), Dithering.
You can even take an average (universal) palette, but the result will not always be good.
Your palette turned out not as bad as you thought at first glance, however, I see that the image built on its basis does not use bright colors, there is probably an error in the algorithm.
The search for color in the palette should be conducted only not only by brightness. Rather, the sum of the squared deviations for each color component.
And yet - you do not sort by brightness, you have one pass with a permutation, it does not give a complete sort.
Most likely because of this, you got such a dim final image. But the brightness is still not the same, blue and red colors will be equally bright, but completely different.

Answer 2

You can apply Median cut .
The essence of the algorithm is as follows:

1. Create one basket (vector) with all image pixels
   
2. Determine the color component (R, G or B) for which the range of values ​​(max - min) in the basket is the largest
   
3. Find the median of this color and split the basket into two
   
4. Repeat steps 2 and 3 until the desired number of baskets is reached
   
5. Next, you can, for example, find the average color in each basket and create a std::unordered_map from the current color to the average
   

Answer 3

1) The simplest option, it seems to me, is to randomly select colors (for example, random image pixels) and look for a display error (compare either with all pixels or with a small part, 1% for example), then the next iteration with a small change, and so on until there is the minimum of an error is reached, it is very simple, to sort through options in a cycle. I like this approach that there is no mathematical analysis, the computer is working, the programmer is resting))
2) The high quality of the picture of 16 colors, almost indistinguishable from the original, is achieved by adding digital noise, the missing colors are obtained by merging the colors of adjacent pixels, and the gradients disappear, the algorithm is of course more difficult
3) I looked at the picture that your code gave, it can be improved by turning the contrast, making dark areas darker, light areas lighter. The algorithm initially loses contrast by averaging too large areas of the image.

Answer 4

https://pngquant.org/lib/
Function liq_quantize_image