Квантование цвета

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

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

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

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

Алгоритмы [ править ]

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

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

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

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

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

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

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

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

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

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

Портрет Ады Лавлейс — точное изображение и несколько версий, обработанных методом k-среднего квантования цвета.
Оригинал
2 цвета
5 цветов
10 цветов
15 цветов
100 цветов

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

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

История и приложения [ править ]

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

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

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

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

Квантование для сжатия изображений [ править ]

Многие форматы файлов изображений поддерживают индексированные цвета .

Палитра всего изображения обычно выбирает 256 «репрезентативных» цветов для всего изображения, где каждый пиксель ссылается на любой из цветов в палитре, как в форматах файлов GIF и PNG.

Палитра блоков обычно выбирает 2 или 4 цвета для каждого блока размером 4x4 пикселей, используемого в BTC , CCC , S2TC и S3TC .

Поддержка редактора [ править ]

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

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

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

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

Путь Inkscape → Растровое изображение трассировки: несколько сканирований: функция цвета использует квантование октодерева для создания цветных трассировок. ^[4]

См. также [ править ]

Ссылки [ править ]

^ Селеби, Мэн (2011). «Сорок лет квантования цвета: современный алгоритмический обзор». Обзор искусственного интеллекта . 56 : 13953–14034. дои : 10.1007/s10462-023-10406-6 .
^ Селеби, Мэн (2011). «Улучшение производительности k-средних для квантования цвета». Вычисление изображений и зрительных образов . 29 (4): 260–271. arXiv : 1101.0395 . Бибкод : 2011arXiv1101.0395E . дои : 10.1016/j.imavis.2010.10.002 . S2CID 9557537 .
^ «NeuQuant: нейронное квантование изображений» . Архивировано из оригинала 14 июня 2006 г. Проверено 2 мая 2006 г.
^ Бах, Тавмджонг (23 июля 2007 г.). «Inkscape » Трассировка растровых изображений » Множественное сканирование» . Проверено 23 февраля 2008 г.

Дальнейшее чтение [ править ]

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

[1] Селеби, Мэн (2011). «Сорок лет квантования цвета: современный алгоритмический обзор». Обзор искусственного интеллекта . 56 : 13953–14034. дои : 10.1007/s10462-023-10406-6 .

[2] Селеби, Мэн (2011). «Улучшение производительности k-средних для квантования цвета». Вычисление изображений и зрительных образов . 29 (4): 260–271. arXiv : 1101.0395 . Бибкод : 2011arXiv1101.0395E . дои : 10.1016/j.imavis.2010.10.002 . S2CID 9557537 .

[3] «NeuQuant: нейронное квантование изображений» . Архивировано из оригинала 14 июня 2006 г. Проверено 2 мая 2006 г.

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

[1]

[2]

[3]

[4]