Допустим у меня есть 24 битное изображение, например такое

Я хочу переконвертировать его цветное палитровое, скажем 4 бита, 16 цветов.
Т.е получить что-то вроде

Как мне создать такую палитру?
Я попытался сделать так - разбить изображение на 16 равных частей и для каждой части найти свой средний цвет(ну т.е среднее арифметическое для R,G,B)
Но цвета в полученной палитры вышли грязными и тусклыми что-ли. Вот такая вот палитра вышла -

Т.е тут нет ярко выраженных цветов , таких как черного, темно-коричневого,нормального оранжевого, зеленого..
Потом еще проблема в том - как выбрать нужный цвет в палитре.. Я отсортировал по яркости и выбирал тоже по ближайшей яркости, но скорее всего это неправильно..
Вот мой код, подскажите пожалуйста, как дополнить/переделать, чтобы получше работало)
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;
}
Вот результат работы моего кода -

UPD - после нормальной сортировки)

UPD - через сумму квадратов отклонений

UPD - после увеличения контрастности палитры