Динамический подбор палитры в системах реалистической визуализации

Одним из современных направлений компьютерной графики является синтез реалистических изображений сцен, состоящих из геометрических объектов. Перспективный метод реалистической визуализации - "трассировка лучей" [1,2]. Количество различных цветов при этом, как правило, существенно превышает возможности типовых графических контроллеров. Соответственно возникает задача наилучшего приближения этих цветов в доступной палитре, которая решается методом динамического подбора палитры.
Область применения метода не ограничивается системами трассировки лучей. Подобная задача возникает при закраске поверхности по способу 1'уро [3], изображении сканированных цветных фотографий. Метод можно использовать в задачах распознавания образов для снижения числа различных точек, представляющих рисунок.

Восприятие цвета, цветовое пространство

Ощущение цвета возникает в результате физико-химических процессов, вызванных воздействием электромагнитных волн в диапазоне 400...700 нм. Для нас существенно, что максимум чувствительности глаза приходится на три участка спектра с длиной волны: около 700 (красный), 520...540 (зеленый) и около 400 нм (синий цвет). Дальнейшая обработка в зрительных нейронах и головном мозге человека обеспечивает восприятие всего диапазона цветов.
В общепринятой модели восприятия [5] произвольный цвет (С) представляется в виде взвешенной суммы основных цветов:
С - rR + gG + ЬВ, где R (Red), G (Green), В (Blue) - максимально интенсивные потоки красного, зеленого и синего цвета; г, g, b - интенсивности этих потоков, отнесенные к максимальным. Оттенки серого цвета получаются при смешивании потоков R, G и В с одинаковой интенсивностью (г - g - b). При г — g — b — 0 получим черный цвет.
В растровых телевизионных мониторах чаще всего используется система основных цветов RGB, наиболее точно соответствующая восприятию цвета глазом. Точка растра обычно кодируется восемью битами, т.е. на экране одновременно можно изобразить не более 256 цветов. При этом средства выбора палитры обеспечивают до 256 градаций каждого из базовых цветов [6]. Без ограничения общности можно представить все допустимые цвета точками цветового куба (рис. 1) RxGxB - [0..255] х [0..255] х [0..255].
Психофизиологически любой цвет характеризуется тоном, насыщенностью и светлотой. В нашей модели изображения цветовой тон будет определяться соотношением координат, насыщенность цвета - углом между вектором (r,g,b) и прямой г - g = b, а светлота - возрастающей функцией от суммы координат.
 
Постановка задачи


Даны Р точек цветового пространства, которые нужно изобразить на экране. Всего имеется М различных цветов, причем М » Р. Количрст- во одновременно изображаемых цветов п гораздо меньше как М, так и Р, т.е. верны соотношения М » Р и Р » п. Мы хотим выбрать п точек из М таким образом, чтобы они "правдоподобно" приближали Р заданных цветов.
Пример соотношения величин n, Р и М. При построении изображения методом трассировки лучей возможна ситуация, когда каждая точка экрана будет иметь уникальный цвет. Поэтому число точек Р можно оценить с помощью размеров экрана. При создании цветных рисунков, представленных в этой статье, использовался экран 150 х 450 точек, т.е. Р - 67500. Число одновременно выводимых на экран цветов п - 256 « 67500. Вся возможная палитра экрана М - 256 х 256 х 256 - 16777216 » 67500.
"Правдоподобность" цветового приближения. Человек лучше различает близкие градации цвета, если они соседствуют в поле зрения, т.е. сравнительное восприятие цвета более развито, чем абсолютное [7]. Следовательно, гладкость изображения переходов от одного цвета к другому особенно важна на больших площадях. Но для оценки правдоподобия изображения мелких деталей необходимо также учитывать максимальное отклонение изображаемого цвета от истинного. Поэтому "правдоподобность" изображения цветов естественно контролировать двумя критериями.
Критерий L2:
L2 - SUM {dr2 + dg2 + db2}, где dr означает разность между r-координатой действительной точки цветового пространства и r-координатой изображающей ее точки. Функция SUM выполняет суммирование значений для всех точек рисунка. Этот критерий характеризует гладкость цветовых переходов на больших площадях.
Критерий L0:
L0 - MAX {max(dr, dg, db)}, где функция МАХ - выбор максимума по всем точкам рисунка. Этот критерий дает возможность увидеть смещение какого-либо цвета в соседний цвет спектра. Численное выражение критерия будет более показательным в виде
LO/C Со.
где Стах и С0 - числа, обозначающие максимальный поток цвета и его отсутствие.
Существует наилучшее по критерию L2 решение задачи. Точная минимизация критерия L2 выполняется эффективно, когда решение выбирается из линейного пространства возможных альтернатив методом наименьших квадратов [8]. Однако в данном случае множество альтернатив не образует линейного пространства, так как состоит из всех функций (сопоставляющих каждой точке экрана цвет), принимающих не более п различных значений. Такая задача является комбинаторной, и нам не известны какие-либо эффективные методы ее общего решения. Вероятно, строгое решение может быть получено только перебором. Желательно, однако, найти более практичный метод, учитывающий также ограничения и по критерию L0.
Самое простое решение задачи - равномерное разбиение цветового пространства. Для использования всех 256 отображаемых на экране цветов его можно разделить следующим образом: красный и зеленый цвета - на восемь градаций и синий цвет - на четыре градации Как правило, это решение будет неудовлетворительным. Во-первых, оно не учитывает возможной неравномерности расположения точек по цветовому кубу. Во-вторых, изменение градации по любому цвету будет хорошо заметно глазом, так как при этом резко изменяется тон, насыщенность и светлота цвета, а по всем этим параметрам чувствительность человеческого глаза выше восьми или четырех градаций [5]. Данное решение даст гарантированные хорошие оценки критерия L0, но плохие - критерия L2.
Оценивать критерий L2 в абсолютных числах нецелесообразно, так как для разных цветовых рисунков эти числа будут сильно различаться. В связи с этим предлагается критерием L2 пользоваться в виде
L2/L2reguUr,
где ^regular " значение критерия L2 для данного рисунка при решении задачи равномерным разбиением цветового пространства.
Метод динамического подбора палитры
Идея метода состоит в следующем, Цветовой куб разбивается так, чтобы плотность разбиения была выше там, где более плотно расположены точки, и каждой клетке разбиения выделяется один цвет. Это позволяет иметь большее число изображаемых цветов для основных (доминирующих в этой картинке) цветовых областей, представленных большим количеством точек. Лучшее изображение основных областей позволит сильно "сгладить" картинку, так как переходы к различным градациям цвета хорошо заметны на больших поверхностях и почти не видны на линиях или у различных точек. Улучшение цветного изображения картинки таким методом численно должно выразиться в уменьшении значений критерия L2, но пока никак не учитывает критерия L0, о котором будет сказано ниже.
В алгоритме динамического подбора палитры использовалось последовательное бинарное разбиение цветового куба. Это позволило задавать любое число п отображаемых цветов. Параллелепипеды, получаемые в процессе разбиения цветового куба, будем называть подку- бами.
При реализации число п - 254. Еще один цвет был цветом фона экрана, а другой - зарезервирован.
Известно, что человек с хорошим цветовосприятием отличает не более 350 тыс. цветов [5], т.е. в среднем по каждому цвету он различает около 70 градаций. Цветочувствительность обыкновенного человека не превышает 30...35 градаций. Значит, цвета, отличающиеся друг от друга менее чем на число LIMIT - Cmax / 35, необходимо рассматривать как один цвет и не надо продолжать деление содержащего их подкуба. Величина LIMIT зависит только от человека и является пределом чувствительности глаза.


В алгоритме реализован следующий процесс разбиения куба:
1.    Из всех уже построенных подкубов для деления выбирается подкуб, содержащий наибольшее число (к) точек цветового пространства • Этот способ выбора обеспечит более плотное разбиение в области большей плотности точек.
2.    При выборе очередного подкуба необходимо проверить диаметр сферической оболочки всех точек, располагающихся в нем. Если диаметр меньше LIMIT, то этот подкуб не делится и необходимо выбрать следующий.
3.    Деление очередного подкуба производится плоскостью, параллельной одной из координатных плоскостей и проходящей через центр тяжести содержащихся в нем точек. Из трех возможных плоскостей выбирается та, которая делит подкуб наиболее равномерно, т.е. обеспечивает наименьшую разность числа точек в двух получившихся подкубах. Сначала среднее арифметическое вычисляется для каждой оси г, g и Ь. Далее подсчитывается количество точек в разных подкубах для каждого деления и выбирается наилучшая плоскость деления.
4.    Процесс деления повторяется до тех пор, пока весь цветовой куб не будет разделен на п частей.
По окончании процесса все пространство RxGxB разделено на п неравных подкубов. В каждом из них содержатся точки, отображенные на экране одним цветом. Изображаемый цвет задается как целая часть среднего арифметического координат точек по каждой из цветовых осей.


Использование при делении подкубов и выборе цвета среднего арифметического и позволит минимизировать критерий L2.
Понятно, что при расчете изображаемого цвета происходит смещение цвета, представленного малым число точек, к доминирующему цвету. Если описанный процесс деления начать со всего куба RxGxB, то возможны смещения настолько значительные, что мы увидим другие цвета. Численно это выражается в больших значениях критерия L0.
Решить эту проблему можно, введя начальное равномерное разбиение, которое гарантирует несмешиваемость основных цветов. Минимальное разбиение возможно на восемь частей, что означает деление пополам по каждой из осей. Это разбиение в некоторых случаях может оказаться неудовлетворительным. Например, при переходе от желтого к красному существует зона оранжевого цвета. Он также является основным, и его не следует смешивать с желтым. Большое разбиение, например на 216 частей, приводит нас к решению, которое, как уже упоминалось, неудовлетворительно.


В отличие от равномерного решения при начальном разбиении для пустых, не имеющих ни одной точки, подкубов не выделяется ни одного цвета и с ними не производится процесса деления. Начальное равномерное разбиение приводит к тому, что алгоритм начинает работать с некоторой сложной оболочкой точек цветового пространства, состоящей из подкубов.
Экспериментально установлено, что лучший результат в большинстве случаев дает начальное разбиение на 64 части (на 4 части по каждой из осей). Такое разбиение обеспечивает значение критерия L0 не более 0,25, что говорит о несмешиваемости основных цветов спектра. В этом случае подбор палитры для конкретного рисунка проходит среди их оттенков.
 


Обсудить вопрос в студенческом форуме

 

Сайт содержит информацию о учебном заведении и студенческой общине и не является официальным