Подскажите алгоритм для хитрой квантизации

[ABel]

Вот такая вот возникла проблема:
Имеется полноцветное изображение, из которого вытащена 256-цветовая палитра (алгоритмом Median Cut Хекберта).
Задача заключается в том, чтобы для некоторого небольшого фрагмента исходного изображения (скажем, квадратика 8 на 8 точек) выбрать три наилучших приближения одним, двумя и четырмя цветами из полученной палитры.

С одним цветом - тут понятно. Берём среднее по всем точкам и ищем ближайший цвет в палитре. А вот как лучше поступить с двумя и четырмя цветами?
Подскажите, пожалуйста, может быть уже есть соответствующие алгоритмы или хотя бы статьи, рассматривающие этот вопрос (не квантизацию вообще, а именно вот такую квантизацию с ограничениями).

[Lex]

ABel, не совсем понятно про приближения 2 и 4 цветами.
Т.е. как я понимаю в выбранном тобой фрагменте исходные цвета заменяются на 2 или 4 цвета или фрагмент заливается 2, 4 цветами?

[grozny]

Решение в общем случае - квантизация по собственному базису в цветовом пр-ве даст тебе ответ для любого количества цветов.

Находишь главные оси в цветовом пространстве, переходишь в базис на этих осях и режешь это новое (собственное!) цветовое пр-во на нужное количество корзин. Центр корзины - новый цвет. Гарантирована наименьшая ошибка квантизации просто по определению. Таким образом хорошо палитру строить.

В твоём случае корзины (палитра) уже заданы, вполне может быть неоптимальной. Это так, к слову.

Ну вот например:
1. находим для каждого пиксела наилучшую аппроксимацию в палитре (наименьшее расстояние в цветовом пр-ве, метрики могут быть самые разные, Манхэттен, например).

2. Считаем расстояния между полученными цветами.

3. Выбираем пару цветом с минимальным расстоянием и заменяем их либо на один из цветов из пары (грубо), либо ищем по палитре цвет с минимальным расстоянием от среднего цвета пары.

4. Повторяем процесс пока не останется требуемое кол-во цветов.

ВИдел статью в ACM Transactions on Graphics. Ни автора, ни года/номера ессно не помню, увы.

[ABel]

Lex, имелась в виду замена исходных цветов на 2 (или 4) искомых цвета.

grozny, благодарю за совет.

Оптимальность исходной палитры в моём случае не очень требуется. Всё дело в том, что приходится работать не с одним статическим изображением, а с последовательными видео-кадрами. При этом палитра - общая.
Главное, чтобы приближение фрагментов изображения малым количеством цветов работало как можно быстрее.

[grozny]

вспомнил фамилиё - Сяолин Ву, вот тебе код:

Код:

/**********************************************************************
	    C Implementation of Wu's Color Quantizer )v. 2:
	    )see Graphics Gems vol. II, pp. 126-133:

Author{	Xiaolin Wu
	Dept. of Computer Science
	Univ. of Western Ontario
	London, Ontario N6A 5B7
	wu@csd.uwo.ca

Algorithm{ Greedy orthogonal bipartition of RGB space for variance
	   minimization aided by inclusion-exclusion tricks.
	   For speed no nearest neighbor search is done. Slightly
	   better performance can be expected by more sophisticated
	   but more expensive versions.

The author thanks Tom Lane at Tom_Lane@G.GP.CS.CMU.EDU for much of
additional documentation and a cure to a previous bug.

Free to distribute, comments and suggestions are appreciated.
**********************************************************************/	

http://www.csd.uwo.ca/~wu/cq.c