12.5. Квантование цвета больший приоритет, даже если многие из наиболее часто встречающихся цветов очень близки друг к другу. Основной метод заключается в формировании списка числа появлений каждого цвета в файле с последующей сортировкой этого списка. Тогда первые К цветов в отсортированном списке и есть К наиболее популярных цветов.
Поскольку каждый трехбайтный цвет полноцветного изображения может принимать очень много значений (всего их 232), то вначале задача упрощается путем усечения каждого байта для красного, зеленого и синего цветов до пяти бит, после чего остается 215 - 32 Кбайт возможных значений цветов. Затем выделяется массив размером 32 Кбайт и все его элементы обнуляются. Файл изображения просматривается, и по мере чтения каждого цвета соответствующий элемент этого массива увеличивается на единицу. После того как прочитаны все N значений цветов, этот массив сортируется и К наиболее часто встречающихся цветов принимаются в качестве цветов-представителей.
После этого производится повторный просмотр файла, и каждый встречающийся цвет (rd. grn, Ы u) заменяется ближайшим цветом-представителем (г. д. Ь)[1] из списка популярности. В качестве критерия «близости» часто берется наименьшее среднеквадратическое расстояние: *найти такое значение i, для которого (rd - r[i])2 + (gm - g[i])2 + (blu -b[i])2 наименьшее».
Эта операция может оказаться дорогостоящей.
12.5.3. Алгоритм медианного сечения Алгоритм медианного сечения (median-cut algorithm) был впервые предложен Хекбертом [Heckbert, 102]. В нем цветовой блок разбивается на К подблоков таким образом, чтобы каждый подблок содержал приблизительно одинаковое количество цветных точек. На рис. 12.21 показан основной процесс, для наглядности в двумерном варианте. (Предположим, что цвета содержат только красную и зеленую составляющие.) Изображенный на рис. 12.21, а исходный цветовой куб вначале разделен по своему наибольшему ребру: значение медианы (median value) г, берется таким, что в одном подблоке имеется N/2 точек, и в другом тоже N/2. Затем каждый из этих подблоков обрабатывается тем же способом: разрезается по среднему значению на его длинной стороне. Этот процесс продолжается до тех пор, пока не образуется К подблоков. В качестве цвета-представителя каждого подблока берется центр этого подблока. На рис. 12.21, б показано несколько примеров подблоков после того, как проделано семь сечений.