Цветовое квантование - Color quantization

Пример изображения в 24-битном цвете RGB

То же изображение, уменьшенное до палитры из 16 цветов, специально выбранных для наилучшего представления изображения; выбранная палитра отображается квадратами внизу изображения.

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

Название «квантование цвета» в основном используется в исследовательской литературе по компьютерной графике; в приложениях такие термины, как оптимизированная генерация палитры, создание оптимальной палитры, или же уменьшение глубины цвета используются. Некоторые из них вводят в заблуждение, поскольку палитры, генерируемые стандартными алгоритмами, не обязательно являются наилучшими из возможных.

Алгоритмы

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

Самым популярным алгоритмом квантования цвета, изобретенным Полом Хекбертом в 1979 году, является алгоритм средний разрез алгоритм. Используется множество вариаций этой схемы. До этого большая часть квантования цвета выполнялась с использованием алгоритм популяции или же популяционный метод, который по сути строит гистограмму диапазонов одинакового размера и назначает цвета диапазонам, содержащим наибольшее количество точек. Более современный популярный метод - кластеризация с использованием Octrees, впервые задуманный Гервотцем и Пургатхофером и улучшенный Xerox PARC Исследователь Дэн Блумберг.

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

Цветовое пространство фотографии слева, а также оптимизированная 16-цветная палитра, созданная Фотошоп. Показаны области Вороного для каждой записи палитры.

Если палитра фиксирована, как это часто бывает в системах квантования цвета в реальном времени, таких как те, что используются в операционных системах, квантование цвета обычно выполняется с использованием алгоритма «расстояния по прямой» или «ближайшего цвета», который просто берет каждый цвет исходного изображения и находит ближайший элемент палитры, где расстояние определяется расстоянием между двумя соответствующими точками в трехмерном пространстве. Другими словами, если цвета ${displaystyle (r_ {1}, g_ {1}, b_ {1})}$ и ${displaystyle (r_ {2}, g_ {2}, b_ {2})}$ , мы хотим минимизировать Евклидово расстояние:

{displaystyle {sqrt {(r_ {1} -r_ {2}) ^ {2} + (g_ {1} -g_ {2}) ^ {2} + (b_ {1} -b_ {2}) ^ { 2}}}.}

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

Цветное изображение, уменьшенное до 4 цветов с помощью пространственного квантования цвета.

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

Был изобретен ряд других, гораздо менее часто используемых методов, в которых используются совершенно другие подходы. Алгоритм Local K-means, разработанный Олегом Веревкой в 1995 году, предназначен для использования в оконных системах, где основной набор «зарезервированных цветов» фиксирован для использования системой, и многие изображения с разными цветовыми схемами могут отображаться одновременно. Это схема пост-кластеризации, которая делает первоначальное предположение о палитре, а затем итеративно ее уточняет.

В первые дни квантования цвета k-означает кластеризацию алгоритм был признан неподходящим из-за его высоких вычислительных требований и чувствительности к инициализации. В 2011 году М. Эмре Челеби повторно исследовал эффективность k-средних в качестве квантователя цвета.^[1] Он продемонстрировал, что эффективная реализация k-средних превосходит большое количество методов квантования цвета.

Качественный, но медленный NeuQuant алгоритм сокращает изображения до 256 цветов, обучая Кохонен нейронная сеть «который самоорганизуется посредством обучения соответствию распределению цветов во входном изображении. Определение положения в пространстве RGB каждого нейрона дает высококачественную цветовую карту, в которой соседние цвета похожи».^[2] Это особенно удобно для изображений с градиентами.

Наконец, один из новых методов - пространственное квантование цвета, задуманный Пузичей, Хельдом, Кеттерером, Бухманном и Феллнером из Боннский университет, который сочетает дизеринг с генерацией палитры и упрощенную модель человеческого восприятия для получения впечатляющих визуальных результатов даже для очень небольшого количества цветов. Он не рассматривает выбор палитры строго как проблему кластеризации, поскольку цвета соседних пикселей в исходном изображении также влияют на цвет пикселя. Видеть образцы изображений.

История и приложения

В первые дни ПК видеоадаптеры обычно поддерживали только 2, 4, 16 или (в конечном итоге) 256 цветов из-за ограничений видеопамяти; они предпочли посвятить видеопамять большему количеству пикселей (более высокое разрешение), чем большему количеству цветов. Квантование цвета помогло оправдать этот компромисс, сделав возможным отображать много изображений с высоким содержанием цветов в 16- и 256-цветных режимах с ограниченным визуальным ухудшением. Многие операционные системы автоматически выполняют квантование и дизеринг при просмотре изображений с высоким содержанием цветов в 256-цветном видеорежиме, что было важно, когда доминировали видеоустройства, ограниченные 256-цветными режимами. Современные компьютеры теперь могут отображать миллионы цветов одновременно, что намного больше, чем может различить человеческий глаз, ограничивая это приложение в первую очередь мобильными устройствами и устаревшим оборудованием.

В настоящее время квантование цвета в основном используется в Гифка и PNG изображений. GIF, который долгое время был самым популярным форматом анимированных растровых изображений без потерь на Всемирная паутина, поддерживает только до 256 цветов, что требует квантования для многих изображений. Некоторые ранние веб-браузеры ограничивали изображения для использования определенной палитры, известной как веб-цвета, что приводит к серьезному ухудшению качества по сравнению с оптимизированными палитрами. Изображения PNG поддерживают 24-битный цвет, но часто их размер может быть намного меньше, без значительного ухудшения качества изображения за счет применения квантования цвета, поскольку файлы PNG используют меньше битов на пиксель для изображений с палитрой.

Бесконечное количество цветов, доступных через объектив камеры, невозможно отобразить на экране компьютера; таким образом, преобразование любой фотографии в цифровое представление обязательно требует некоторого квантования. На практике 24-битный цвет достаточно богат, чтобы отображать почти все цвета, воспринимаемые людьми, с достаточно небольшой ошибкой, чтобы быть визуально идентичными (если они представлены правильно) в пределах доступного цветовое пространство.^{[нужна цитата ]} Однако оцифровка цвета в детекторе камеры или на экране обязательно ограничивает доступное цветовое пространство. Следовательно, существует много цветов, которые невозможно воспроизвести, независимо от того, сколько битов используется для представления цвета. Например, в типичных цветовых пространствах RGB (распространенных на компьютерных мониторах) невозможно воспроизвести полный диапазон зеленых цветов, которые человеческий глаз способен воспринимать.

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

Поддержка редактора

Много редакторы растровой графики содержат встроенную поддержку квантования цвета и будут автоматически выполнять ее при преобразовании изображения с большим количеством цветов в формат изображения с меньшим количеством цветов. Большинство этих реализаций позволяют пользователю точно установить количество желаемых цветов. Примеры такой поддержки включают:

Фотошоп Режим → Индексированный цвет Функция предоставляет ряд алгоритмов квантования, начиная от фиксированной системы Windows и веб-палитр до собственных локальных и глобальных алгоритмов для создания палитр, подходящих для конкретного изображения или изображений.
Paint Shop Pro, в его Цвета → Уменьшить глубину цвета dialog, предоставляет три стандартных алгоритма квантования цвета: медианное вырезание, октодерево и фиксированную стандартную палитру «веб-безопасность».
В GIMP 2.8 опция преобразования изображения в индексированные цвета (изображение→Режим→Indexed ..) позволяет создавать оптимальную палитру с выбором количества цветов от 2 до 256, с возможностью использования оптимизированной для Интернета палитры, с использованием черно-белой палитры (1 бит) или с использованием пользовательской палитры. Он позволяет удалять неиспользуемые цвета из палитры и предлагает множество вариантов дизеринга: Нет, Флойда-Штейнберга (нормальный), Флойда-Штейнберга (уменьшение растекания цвета) и Позиционирование, а также возможность включить дизеринг прозрачности.

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

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

Inkscape's Путь → Трассировка растрового изображения: несколько сканирований: цвет Функция использует квантование октодерева для создания цветовых следов.^[3]

Смотрите также

дальнейшее чтение

Пол С. Хекберт. Квантование цветного изображения для отображения буфера кадра. ACM SIGGRAPH '82 Известия. Первая публикация алгоритма медианного отсечения.
Дэн Блумберг. Цветовое квантование с использованием октодеревьев. Лептоника.
Олег Веревка. Квантование цветного изображения в системах Windows с локальным алгоритмом K-средних. Труды западного симпозиума компьютерной графики '95.
Дж. Пузича, М. Хельд, Дж. Кеттерер, Дж. М. Бухманн и Д. Фелльнер. О пространственном квантовании цветных изображений. (полный текст .ps.gz ) Технический отчет IAI-TR-98-1, Боннский университет. 1998 г.

[1] Челеби, М. Э. (2011). «Повышение эффективности k-средних для квантования цвета». Вычисления изображений и зрения. 29 (4): 260–271. arXiv:1101.0395. Bibcode:2011arXiv1101.0395E. Дои:10.1016 / j.imavis.2010.10.002.

[2] «Архивная копия». Архивировано из оригинал на 2006-06-14. Получено 2006-05-02.CS1 maint: заархивированная копия как заголовок (связь)

[Inkscape-3] Бах, Тавмджонг (23 июля 2007 г.). «Inkscape» Трассировка растровых изображений »Множественное сканирование». Получено 2008-02-23.

[1]

[2]

[3]