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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Inkscape's Path → Trace Bitmap: Multiple Scan: Color функция использует квантование октодерева для создания цветовых следов.

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

Рекомендации

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