Color quantization

Введение

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

Алгоритмы

Большинство стандартных методов рассматривают квантование цвета как проблему кластеризации точек в трехмерном пространстве, где точки представляют цвета, найденные на оригинальном изображении, а три оси представляют три цветных канала. Практически любой алгоритм трехмерного кластеризации может быть применен к квантованию цвета и наоборот. После расположения кластеров, как правило, в каждом кластере усредняются точки, чтобы получить представительный цвет, к которому отображаются все цвета в этом кластере. Три цветных канала обычно красные, зеленые и синие, но еще один популярный выбор - это цветовое пространство Lab, в котором евклидово расстояние более соответствует различию восприятия. Самый популярный алгоритм квантования цвета, изобретенный Полом Гекбертом в 1979 году, - это алгоритм медианного разреза. В настоящее время используется множество вариантов этой схемы. До этого времени большинство квантования цветов проводилось с использованием алгоритма популяции или метода популяции, который по сути строит гистограмму диапазонов равного размера и присваивает цвета диапазонам, содержащим наибольшее количество точек. Более современный популярный метод - кластеризация с использованием октарей, впервые задуманный Гервауцем и Пургатхофером и улучшенный исследователем Xerox PARC Дэном Блумбергом. Если палитра фиксирована, как это часто бывает в системах квантования цвета в реальном времени, таких как те, которые используются в операционных системах, квантование цвета обычно выполняется с использованием алгоритма "расстояние прямой линии" или "ближайший цвет", который просто берет каждый цвет в оригинальном изображении и находит ближайшую входную палитру, где расстояние определяется расстоянием между двумя соответствующими точками в трехмерном пространстве. Другими словами, если цвета и , мы хотим минимизировать расстояние Евклида: это эффективно расщепляет цветовой куб в диаграмму Воронои, где вхождения палитры являются точками, а ячейка содержит все цвета, отображающие одну входную палитру. Существуют эффективные алгоритмы из вычислительной геометрии для вычисления диаграмм Воронои и определения того, в какую область попадает данная точка; на практике индексированные палитра настолько малы, что они обычно являются чрезмерными. Количественная оценка цвета часто сочетается с дитером, который может устранить неприятные артефакты, такие как полосы, которые появляются при количественном оценке гладких градиентов и придают внешний вид большему количеству цветов. Некоторые современные схемы квантования цвета пытаются объединить выбор палитры с дитеррацией на одном этапе, а не выполнять их независимо. Было изобретено несколько других методов, которые используются гораздо реже, но используют совершенно другие подходы. Алгоритм Local K means, разработанный Олегом Веревкой в 1995 году, предназначен для использования в оконных системах, где основной набор "резервированных цветов" фиксирован для использования системой, и одновременно может отображаться много изображений с различными цветовыми схемами. Это схема посткластеризации, которая делает первоначальный прогноз палитры, а затем итеративно ее уточняет. В первые дни квантования цвета алгоритм кластеризации k-средств считался непригодным из-за его высоких вычислительных требований и чувствительности к инициализации. В 2011 году М. Эмре Селеби повторно исследовал эффективность k-средств в качестве цветового квантизатора. Он продемонстрировал, что эффективная реализация k средств превосходит большое количество методов квантования цвета. Высококачественный, но медленный алгоритм NeuQuant сокращает изображения до 256 цветов, обучая нейронную сеть Кохонена, которая самоорганизуется, учится соответствовать распределению цветов в входном изображении. Позиция каждого нейрона в пространстве RGB дает высококачественную цветовую карту, в которой соседствующие цвета похожи". Это особенно выгодно для изображений с градиентами. Наконец, одним из новых методов является пространственная квантование цвета, задуманный Пузича, Хелд, Кеттере, Бухман, и Фелнер из Боннского университета, который сочетает в себе колебание с палитрой генерации и упрощенной модели человеческого восприятия для получения визуально впечатляющих результатов даже для очень небольшого количества цветов. Он не рассматривает выбор палитры строго как проблему кластеризации, п...

Most standard techniques treat color quantization as a problem of clustering points in three dimensional space, where the points represent colors found in the original image and the three axes represent the three color channels. Almost any three dimensional clustering algorithm can be applied to color quantization, and vice versa. After the clusters are located, typically the points in each cluster are averaged to obtain the representative color that all colors in that cluster are mapped to. The three color channels are usually red, green, and blue, but another popular choice is the Lab color space, in which Euclidean distance is more consistent with perceptual difference. The most popular algorithm by far for color quantization, invented by Paul Heckbert in 1979, is the median cut algorithm. Many variations on this scheme are in use. Before this time, most color quantization was done using the population algorithm or population method, which essentially constructs a histogram of equal sized ranges and assigns colors to the ranges containing the most points. A more modern popular method is clustering using octrees, first conceived by Gervautz and Purgathofer and improved by Xerox PARC researcher Dan Bloomberg. If the palette is fixed, as is often the case in real time color quantization systems such as those used in operating systems, color quantization is usually done using the "straight line distance" or "nearest color" algorithm, which simply takes each color in the original image and finds the closest palette entry, where distance is determined by the distance between the two corresponding points in three dimensional space. In other words, if the colors are and , we want to minimize the Euclidean distance:

This effectively decomposes the color cube into a Voronoi diagram, where the palette entries are the points and a cell contains all colors mapping to a single palette entry. There are efficient algorithms from computational geometry for computing Voronoi diagrams and determining which region a given point falls in; in practice, indexed palettes are so small that these are usually overkill. Color quantization is frequently combined with dithering, which can eliminate unpleasant artifacts such as banding that appear when quantizing smooth gradients and give the appearance of a larger number of colors. Some modern schemes for color quantization attempt to combine palette selection with dithering in one stage, rather than perform them independently. A number of other much less frequently used methods have been invented that use entirely different approaches. The Local K means algorithm, conceived by Oleg Verevka in 1995, is designed for use in windowing systems where a core set of "reserved colors" is fixed for use by the system and many images with different color schemes might be displayed simultaneously. It is a post clustering scheme that makes an initial guess at the palette and then iteratively refines it. In the early days of color quantization, the k means clustering algorithm was deemed unsuitable because of its high computational requirements and sensitivity to initialization. In 2011, M. Emre Celebi reinvestigated the performance of k means as a color quantizer. He demonstrated that an efficient implementation of k means outperforms a large number of color quantization methods. The high quality but slow NeuQuant algorithm reduces images to 256 colors by training a Kohonen neural network "which self organises through learning to match the distribution of colours in an input image. Taking the position in RGB space of each neuron gives a high quality colour map in which adjacent colours are similar." It is particularly advantageous for images with gradients. Finally, one of the newer methods is spatial color quantization, conceived by Puzicha, Held, Ketterer, Buhmann, and Fellner of the University of Bonn, which combines dithering with palette generation and a simplified model of human perception to produce visually impressive results even for very small numbers of colors. It does not treat palette selection strictly as a clustering problem, in that the colors of nearby pixels in the original image also affect the color of a pixel. See sample images.

История и применение

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

In the early days of PCs, it was common for video adapters to support only 2, 4, 16, or (eventually) 256 colors due to video memory limitations; they preferred to dedicate the video memory to having more pixels (higher resolution) rather than more colors. Color quantization helped to justify this tradeoff by making it possible to display many high color images in 16 and 256 color modes with limited visual degradation. Many operating systems automatically perform quantization and dithering when viewing high color images in a 256 color video mode, which was important when video devices limited to 256 color modes were dominant. Modern computers can now display millions of colors at once, far more than can be distinguished by the human eye, limiting this application primarily to mobile devices and legacy hardware. Nowadays, color quantization is mainly used in GIF and PNG images. GIF, for a long time the most popular lossless and animated bitmap format on the World Wide Web, only supports up to 256 colors, necessitating quantization for many images. Some early web browsers constrained images to use a specific palette known as the web colors, leading to severe degradation in quality compared to optimized palettes. PNG images support 24 bit color, but can often be made much smaller in filesize without much visual degradation by application of color quantization, since PNG files use fewer bits per pixel for palettized images. The infinite number of colors available through the lens of a camera is impossible to display on a computer screen; thus converting any photograph to a digital representation necessarily involves some quantization. Practically speaking, 24 bit color is sufficiently rich to represent almost all colors perceivable by humans with sufficiently small error as to be visually identical (if presented faithfully), within the available color space. However, the digitization of color, either in a camera detector or on a screen, necessarily limits the available color space. Consequently there are many colors that may be impossible to reproduce, regardless of how many bits are used to represent the color. For example, it is impossible in typical RGB color spaces (common on computer monitors) to reproduce the full range of green colors that the human eye is capable of perceiving. With the few colors available on early computers, different quantization algorithms produced very different looking output images. As a result, a lot of time was spent on writing sophisticated algorithms to be more lifelike.

Квантизация для сжатия изображения

Многие форматы файлов изображений поддерживают индексированный цвет. Вся палитра изображений обычно выбирает 256 "репрезентативных" цветов для всего изображения, где каждый пиксель ссылается на любой из цветов в палитре, как в формате файлов GIF и PNG. Палитра блоков обычно выбирает 2 или 4 цвета для каждого блока пикселей 4х4, используемых в BTC, CCC, S2TC и S3TC.

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

Многие редакторы графики битмапов содержат встроенную поддержку квантования цвета и автоматически выполняют его при преобразовании изображения с большим количеством цветов в формат изображения с меньшим количеством цветов. Большинство из этих реализаций позволяют пользователю установить точное количество желаемых цветов. Примеры такой поддержки включают: Функция Mode→Indexed Color в Photoshop обеспечивает ряд алгоритмов квантования, начиная от фиксированной системы Windows и веб-палеты до проприетарных локальных и глобальных алгоритмов для генерации палит, подходящих для конкретного изображения или изображений. Paint Shop Pro, в диалоговом окне Colors→Decrease Color Depth, предоставляет три стандартных алгоритма квантования цвета: медианный вырез, октри и фиксированную стандартную палитру "web safe". В GIMP 2.8, опция "Конвертировать изображение в индексированные цвета" (Image→Mode→Indexed) позволяет создавать оптимальную палитру с выбором количества цветов от 2 до 256, возможность использования веб-оптимизированной палитра, использования черно-белой палитра (1 бит) или использования пользовательской палитра. Он позволяет удалять неиспользуемые цвета из палитры и предлагает множество вариантов дитеррации: None, Floyd Steinberg (нормальный), Floyd Steinberg (уменьшенное цветное кровотечение) и Positioned, а также возможность включить дитеррацию прозрачности. Квантизация цвета также используется для создания эффектов постеризации, хотя постеризация имеет несколько другую цель - минимизировать количество цветов, используемых в одном и том же цветовом пространстве, и обычно использует фиксированную палитру. Некоторые редакторы векторной графики также используют квантование цвета, особенно для растровых векторных методов, которые создают трассировки бит-карточных изображений с помощью обнаружения краев. Path→Trace Bitmap: Multiple Scans: Функция Color использует квантование октариев для создания цветовых следов.