В компьютерной графике квантование цвета или квантование цветного изображения — это квантование, применяемое к цветовым пространствам ; это процесс, который уменьшает количество отдельных цветов, используемых в изображении , обычно с намерением, чтобы новое изображение было максимально визуально похоже на исходное изображение. Компьютерные алгоритмы для выполнения квантования цвета на растровых изображениях изучались с 1970-х годов. [1] Квантование цвета имеет решающее значение для отображения изображений с большим количеством цветов на устройствах, которые могут отображать только ограниченное количество цветов, как правило, из-за ограничений памяти, и обеспечивает эффективное сжатие определенных типов изображений.
Название «квантование цвета» в основном используется в литературе по компьютерной графике; в приложениях используются такие термины, как оптимизированная генерация палитры , оптимальная генерация палитры или уменьшение глубины цвета . Некоторые из них вводят в заблуждение, поскольку палитры, генерируемые стандартными алгоритмами, не обязательно являются наилучшими из возможных.
Большинство стандартных методов рассматривают квантование цвета как проблему кластеризации точек в трехмерном пространстве, где точки представляют цвета, обнаруженные в исходном изображении, а три оси представляют три цветовых канала. Почти любой алгоритм трехмерной кластеризации может быть применен к квантованию цвета, и наоборот. После того, как кластеры найдены, обычно точки в каждом кластере усредняются для получения репрезентативного цвета, которому сопоставлены все цвета в этом кластере. Три цветовых канала обычно красный, зеленый и синий , но другим популярным выбором является цветовое пространство Lab , в котором евклидово расстояние больше соответствует перцептуальной разнице.
Самый популярный алгоритм для квантования цвета, изобретенный Полом Хекбертом в 1979 году, — это алгоритм медианного разреза . Используется множество вариаций этой схемы. До этого времени большая часть квантования цвета выполнялась с использованием алгоритма популяции или метода популяции , который по сути строит гистограмму диапазонов одинакового размера и назначает цвета диапазонам, содержащим наибольшее количество точек. Более современный популярный метод — кластеризация с использованием октодеревьев , впервые придуманная Гервотцем и Пургатхофером и улучшенная исследователем Xerox PARC Дэном Блумбергом.
Если палитра фиксирована, как это часто бывает в системах квантования цвета в реальном времени, таких как те, которые используются в операционных системах, квантование цвета обычно выполняется с использованием алгоритма «расстояния по прямой» или «ближайшего цвета», который просто берет каждый цвет в исходном изображении и находит ближайшую запись палитры, где расстояние определяется расстоянием между двумя соответствующими точками в трехмерном пространстве. Другими словами, если цвета и , мы хотим минимизировать евклидово расстояние :
Это эффективно разлагает цветовой куб на диаграмму Вороного , где элементы палитры являются точками, а ячейка содержит все цвета, сопоставленные с одним элементом палитры. Существуют эффективные алгоритмы из вычислительной геометрии для вычисления диаграмм Вороного и определения того, в какой регион попадает данная точка; на практике индексированные палитры настолько малы, что они обычно избыточны.
Квантование цвета часто сочетается с дизерингом , что позволяет устранить неприятные артефакты, такие как полосы, которые появляются при квантовании плавных градиентов, и создать видимость большего количества цветов. Некоторые современные схемы квантования цвета пытаются объединить выбор палитры с дизерингом на одном этапе, а не выполнять их по отдельности.
Было изобретено несколько других, гораздо менее часто используемых методов, которые используют совершенно иные подходы. Алгоритм Local K-means, придуманный Олегом Веревкой в 1995 году, предназначен для использования в оконных системах, где основной набор «зарезервированных цветов» фиксируется для использования системой, и одновременно может отображаться множество изображений с различными цветовыми схемами. Это схема посткластеризации, которая делает начальное предположение о палитре, а затем итеративно ее уточняет.
На заре квантования цвета алгоритм кластеризации k-средних считался неподходящим из-за его высоких вычислительных требований и чувствительности к инициализации. В 2011 году М. Эмре Челеби повторно исследовал производительность k-средних в качестве квантователя цвета. [2] Он продемонстрировал, что эффективная реализация k-средних превосходит большое количество методов квантования цвета.
Высококачественный, но медленный алгоритм 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 .
Многие редакторы растровой графики содержат встроенную поддержку квантования цвета и автоматически выполняют его при конвертации изображения с большим количеством цветов в формат изображения с меньшим количеством цветов. Большинство этих реализаций позволяют пользователю точно задать количество желаемых цветов. Примеры такой поддержки включают:
Квантование цвета также используется для создания эффектов постеризации , хотя постеризация имеет несколько иную цель — минимизировать количество цветов, используемых в одном цветовом пространстве, и обычно использует фиксированную палитру.
Некоторые векторные графические редакторы также используют квантование цвета, особенно для методов преобразования растра в вектор , которые создают трассировки растровых изображений с помощью обнаружения краев .
