Как создать палитру цветов для bmp изображения?

Question

[Евгений Трофимов]

Допустим у меня есть 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 - после увеличения контрастности палитры

Answer 1

[Алексей]

Вот тут кажется много полезной информации с кодом:
www.enlight.ru/demo/faq/smth.phtml?query=alg_clr_dith
Ключевые слова: Кластеризация (Quantization), Dithering.
Можно, даже, взять усредненную (универсальную) палитру, но результат будет не всегда хорошим.

Ваша палитра вышла не такой плохой на первый взгляд как вы подумали, однако я вижу что изображение, построенное на ее основе, не использует яркие цвета, вероятно есть ошибка в алгоритме.

Поиск цвета в палитре нужно вести только не только по яркости. Скорее по сумме квадратов отклонений по каждой цветовой компоненте.

И еще - у вас не сортировка по яркости, у вас один проход с перестановкой, он не дает полную сортировку.
Скорее всего из-за этого у вас и получилось такое тусклое итоговое изображение. Но яркость - все равно не то, синий и красный цвета будут одинаково яркими, но совсем разными.

Comments

[Евгений Трофимов]

Сортировку исправил, вышло лучше)Надо попробовать по сумме квадратов отклонений сделать, тогда сортировка вообще не нужна будет.. Но все равно в этой палитре нет белого и черного.. Хотя можно ,наверное, найти самый яркий и самый темный цвет и добавить их..

[Алексей]

Евгений Трофимов: Разумеется создание палитры тоже требует доработки.
Хоть в каком-то виде, но нужно проводить кластеризацию цветов.
Что делать с белым и черным я, если честно, не знаю.
То ли их обычно добавляют автоматически то ли они сами получатся при кластеризации.

[Алексей]

В палитре нам надо получить 16 наиболее "удаленных" друг от друга цветов таких, чтобы суммарная ошибка при их применении мыла минимальной. Наибольшее удаление друг от друга как раз даст и черный и белый цвета. Но все это простым перебором не посчитать.
Можно попробовать перейти в другое цветовое пространство где можно было бы "отсортировать" цвета, построить гистограмму и выбрать 16 цветов на максимальных пиках гистограммы.

Answer 2

[Антон Жилин]

Можно применить Median cut.
Суть алгоритма заключается в следующем:

1. Создаём одну корзину (вектор) со всеми пикселами изображения
   
2. Определяем цветовую компоненту (R, G или B), по которой диапазон значений (max - min) в корзине наибольший
   
3. Находим медиану этого цвета и разбиваем корзину на две
   
4. Повторяем шаги 2 и 3 до достижения нужного числа корзин
   
5. Далее можно, например, найти в каждой корзине средний цвет и создать std::unordered_map из текущего цвета в усредненный
   

Answer 3

[sim31r]

1) Самый простой вариант, мне кажется, случайно выбирать цвета (например случайные пиксели изображения) и искать ошибку отображения (сравнивать или со всеми пикселями или с небольшой частью, 1% например), потом следующая итерация с небольшим изменением и так далее пока не будет достигнут минимум ошибки, очень просто, в цикле перебирать варианты. Мне такой подход нравится, что нет математического анализа, работает компьютер, программист отдыхает ))
2) Высокое качество картинки из 16 цветов, почти неотличимое от оригинала, достигается добавлением цифрового шума, недостающие цвета получаются слиянием цветов рядом расположенных пикселей, и градиенты пропадают, алгоритм, конечно сложнее


3) Посмотрел на картинку что дал ваш код, её можно улучшить покрутив контраст, сделав темные участки темнее, светлые светлее. Алгоритм изначально теряет контрастность, усредняя слишком большие участки изображения.

Answer 4

[Александр Таратин]

https://pngquant.org/lib/
Функция liq_quantize_image