,Большинство современных графических систем способно отображать растровые изображения. Человеческий глаз способен различить по меньше мере пятнадцать тысяч цветов. Поэтому требуется как минимум 15 бит на пиксел для отображения растровых изображений без заметных искажений. Тем не менее, существуют алгоритмы позволяющие уменьшить количество цветов в растровом изображении без заметного ухудшения его качества. В результате работы таких алгоритмов можно достичь заметного сжатия растрового изображения, что особенно важно при работе с изображениями в WWW. Помимо этого, не все современные графические системы способны предоставить требуемое количество цветов и, в таких случаях, так же требуется применить описываемые алгоритмы.
В данной статье описываются алгоритмы позволяющие уменшить количество цветов для монохромных и цветных растров. Так же рассматриваются изображения с частично-прозрачными пикселами и проблемы уменьшения цветов в анимационных последовательностях.
Мы будем рассматривать изображения, цвет каждого пиксела которых представлен тройкой <r,g,b>, где r,g,b - интенсивности трех составляющих - красной, зеленой и голубой . Как правило, каждая составляющая представляется целым числом в диапазоне от 0 до 255. Будем считать, что черный цвет представляется тройкой <0,0,0>, а белый - <255,255,255>. Входное изображение задается матрицей, каждый элемент которого - три байта, задающие цветовые компоненты соответствующего пиксела.
Процесс уменьшения количества цветов состоит из двух стадий. Первая - это выбор набора цветов требуемого размера, с помощью которого можно будет представить изображение наилучшим образом. Такой набор цветов мы будем называть палитрой. Вторая стадия - это собственно отображение начального изображения на выбранную палитру. Для оценки разницы между исходным и конечным изображениями, можно использовать следующую формулу:
где d(x,y) - это метрика цветового пространства, измеряющая разницу между соответствующими цветами в исходном и конечном изображениях. Мы будем использовать евклидову меру. q( c ) - это цвет пиксела в результирующем изображении.
Мы рассмотрим три алгоритма выбора палитры: частотный, медианного деления и минимизации ошибки. Все три алгоритмов требуют предварительного создания гистограммы цветов исходного изображения. Гистограмма создается за один проход по изображению. Для сокращения количества требуемой памяти можно сократить количество бит на пиксел с 24 до 15 (5 на красную, 5 на зеленую и 5 на голубую составляющие соответственно). Такая гистограмма представляет собой таблицу длиной 32768.
Частотный алгоритм [1] основан на предположении о том, что можно найти палитру, выбрав наиболее плотные участки в цветовом распределении исходного изображения. Этот алгоритм просто берет требуемое количество цветов с наиболее высоким значением в гистограмме. Этот процесс имеет временную сложность O(N*K), N - число цветов в гистограмме, а K - количество цветов в палитре. Этот алгоритм нормально работает для многих изображений, однако дает плохие результаты на изображениях с широким диапазоном цветов, а так же при низких количествах требуемых цветов (< 50).
Идея алгоритма медианного деления [1] в том, чтобы использовать каждый цвет в создающейся палитре для представления одинакового количества пикселей исходного изображения. Этот алгоритм последовательно делит цветовое пространство на все более мелкие параллелограммы. При этом, очередной параллелограмм делится перпендикулярно к его наиболее длинной оси на две части так, чтобы в эти части входило одинаковое количество пикселей исходного изображения. При достижении требуемого числа, деление заканчивается и подсчитывается средний цвет в каждом параллелограмме, который и попадает в результирующую палитру. Этот алгоритм требует время порядка O(NlogK), где K - количество цветов в палитре, а N - количество цветов в первом параллелограмме.
Алгоритм минимизации ошибки [1, 2] отличается от алгоритма медианного деления тем, что для очередного деления выбирается параллелограмм, имеющий наибольшую ошибку, и секущая плоскость выбирается так, чтобы минимизировать сумму ошибок в результирующих параллелограммах.
Для ускорения работы двух последних алгоритмов в [2] предлагается методика, позволяющая найти характеристики параллелограмма ( ошибку, средний цвет, количество пикселей) за константное время. Для этой методики требуется предварительная обработка с временной сложностью O(S) , где S - размер гистограммы. Алгоритм минимизации ошибки требует в этом случае времени O( S1/3K2/3).
Существует также алгоритм, основанный на применении восьмеричного дерева[5]. Этот алгоритм превосходит все описанные по временным зарактеристикам, а по качеству получаемой палитры уступает алгоритму медианного деления.
На данном этапе, необходимо цвет каждого пиксела начального изображения заменить на индекс наиболее близкого цвета в палитре. Для практического использования описанных алгоритмов нужно иметь быстрый способ нахождения ближайшего соседа. В [1] описана динамическая структура, позволяющая ускорить этот поиск. Возможно создание массива (обратной палитры), отображающего цвет на индекс ближайшего цвета в палитре. В [3] описан способ быстрого вычисления такой таблицы. Тем не менее, использование этой таблицы без применения специальных алгоритмов дает приемлемые результаты.
Получившееся изображение может быть улучшено с помощью применения техники дизеринга. Среди различных алгоритмов дизеринга можно выделить метод упорядоченного возбуждения и метод распространения ошибки.
Метод упорядоченного возбуждения[4] больше всего подходит для получения монохромных изображений и для получения изображений с равномерным распределением цветов в палитре.
Метод распространения ошибки, или диффузный дизеринг [1,4] основан на вычислении разницы между цветом исходного пиксела и выбираемым цветом (ошибки) и в дальнейшем ее распротранении на прилегающие пикселы.
Для задания прозрачности в исходном изображении используют для каждого пикселапомимо трех цветовых составляющих, значение «прозрачности» пиксела - альфа канал. В палитровых же изображениях часто выделяют один цвет в палитре - ключевой цвет и в дальнейшем используют индекс этого цвета для указания прозрачных пикселей. При преобразовании в такие форматы, можно использовать ключевой цвет только для пикселей с нулевым альфа-каналом (полностью прозрачные). Можно же рассматривать альфа канал так же, как и цветовую составляющуюю Тогда при применении диффузного дизеринга, можно сохранить такие эффекты, возможно имеющиеся в исходном изображении, как плавный переход от изображения к фону, туман, сглаживание ступеней (antialiasing) и т.д.
Существуют форматы графических изображений, включающие в цвета палитры альфа-канал. Можно рассматривать его как обычную составляющую цвета или же, в случае когда прозрачность пикселей несущественна, можно просто установить альфа канал одного цвета палитры в ноль и работать с ним , как с ключевым цветом.
Описанные алгоритмы реализованы на языке С++. Адптированы для работы в среде Windows. Эти программы могут быть получены по отдельному запросу.