Палитры и оптимизация палитр

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

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

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

Один из них заключается в том, что некоторые цвета будут исключены напрочь.

Представьте себе картинку с загородной дорогой, где преобладают синие, коричневые, желтые, зеленые тона, и где-то в одном углу оказался маленький красный, дорожный знак "стоп". Если красный цвет более нигде на этой картинке не встречается, то он не попадет в палитру, и, следовательно, "кирпич" будет окрашен в какой-то другой цвет.

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

Другое решение проблемы - это метод квантования цветов медианным сечением. Цветовое пространство рассматривается как трехмерный куб. Каждая ось куба соответствует одному из трех основных цветов: красному, зеленому или синему. Если отметить точки внутри куба, соответствующие цветам пикселов в обычном полноцветном изображении, то точки будут не равномерно разбросаны по всему кубу, очевидна тенденция группирования точек в отдельных регионах.

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

А там, где точек меньше, оттуда и цветов будет взято меньше. Ни один цвет не будет отброшен полностью. Тем же цветам, которые встречаются чаще, будет отдано предпочтение. Обратимся еще раз к примеру с загородной дорогой.

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