От автора: потребность в цветовом квантовании появилась еще в те времена, когда аппаратное обеспечение, необходимое для отображения цветных изображений, было довольно медленным и дорогостоящим. В то время невозможно было отображать цветные изображения в 24 битах, по 8 бит для каждого цветового канала (красный, зеленый и синий). Каждый пиксель имел, как правило, глубину цвета 8 бит, и необходимость как-то с этим справляться была неизбежной. Поэтому уменьшение размера изображения иногда вызывало трудности.
Цветовое квантование уменьшает количество отдельных цветов изображения, сохраняя при этом новое изображение визуально похожим на оригинал. Для этой цели обычно создается таблица цветов, где один 8-разрядный индекс может использоваться для указания до 256 различных 24-битных цветов.
Описанные ограничения больше не являются проблемой, так как технологии и аппаратное обеспечение значительно усовершенствовались, однако есть определенные случаи, когда мы можем использовать этот метод. Например:
Некоторые дисплеи встроенных систем ограничены низким разрешением
Ситуации, в которых цель заключается в уменьшении размера изображения при минимизации уменьшения воспринимаемого качестве выводимого изображения
Квантование цвета, примененное сегодня
Для повторения — цветовое квантование пытается уменьшить количество различных цветов до набора стандартных. Даже с наилучшим набором из 256 цветов, есть много изображений, которые все еще могут выглядеть плохо. Одной из наиболее распространенных проблем являются контуры вокруг плавно переходящих областей цвета. Вот пример, иллюстрирующий данную проблему.
Рисунок 1. Резкие контуры краев на квантованном изображении
Чтобы решить эту проблему, мы использовали популярный метод обработки изображений, называемый диффузионным сглаживанием ошибок (EDD). Диффузионное сглаживания ошибок работает через вычисление ошибки между значением пикселя и другого ближайшего к нему пикселя; затем эта ошибка распространяется на соседние пиксели, которым еще не были присвоены цвета на карте цветов. После применения диффузии ошибок средний цвет области заметно похож на средний цвет исходной области, однако отдельные цвета полученного изображения ограничены только теми, которые можно найти в таблице цветов.
Существует множество методов диффузионного сглаживания ошибок, таких как Atkinson, Burkes, Stucki, Sierra-2, Sierra-3, Sierra-Lite, но наиболее известным является метод Флойда-Стейнберга. Все эти алгоритмы имеют общую черту: они рассеивают ошибку в двух направлениях, но ошибку они всегда вводят вперед, а не назад. Причина этого очевидна: если вводить ошибку назад, нам нужно будет пересматривать все обработанные пиксели, что приводит к бесконечному циклу распространения ошибок.
Мы можем представить это с помощью следующей диаграммы:
Рис 2. Диффузионное сглаживание ошибок
где x представляет текущий обработанный пиксель. Дробь внизу — это делитель ошибки. Мы скоро вернемся к этому.
Методы квантования
Существует несколько методов решения проблемы поиска подходящих представлений цветов. Самый простой — это разделение фиксированного размера, которое охватывает все цветовое пространство, не требуя первого прохода изображения для генерации разбиения, но оно дает не очень хорошие результаты. Адаптивное разбиение на цвета работает намного лучше, потому что для создания таблицы цветов требуется два этапа: на первом собирается статистика изображения (при этом выборка каждого пикселя изображения может не потребоваться), а на втором этапе создаются стандартные цвета. Широко распространены три типа адаптивных методов квантования цвета: по популярности, по среднему срезу и октет. Мы сосредоточимся на алгоритме среднего среза.
В каждом из вышеупомянутых методов разделение цветового пространства может быть представлено деревом. Создание дерева начинается либо со всего цветового пространства с дальнейшим разбиением его, либо с выбора большого количества небольших партий с дальнейшим объединением их. Метод среднего среза использует алгоритм расщепления, чтобы получить примерно равное распределение пикселей в результирующих партиях. Он реализуется путем многократного разбиения цветового пространства (кластера) с наибольшим количеством пикселей до тех пор, пока не будет заполнено желаемое количество кластеров или пока мы не сможем разделить кластер далее.
Сглаживание цветов
Цель квантования цвета заключается в создании цветовой палитры наиболее стандартных цветов данного изображения или, другими словами, в получении наиболее доминирующих цветов изображения. Эта цель не учитывает визуальную привлекательность. В этом нам может помочь сглаживание цветов.
Как мы уже упоминалось ранее, сглаживание принципиально связано с диффузией ошибок. Давайте используем в качестве примера изображение в оттенках серого. Цель заключается в применении порога, то есть в преобразовании всех пикселей ниже определенного значения в черные, а всех пикселей выше этого значения — в белые. При преобразовании пикселей мы используем простую формулу: если значение пикселя ближе к 0 (чистый черный), преобразуем его в черный, в противном случае он становится белым. Возьмем в качестве примера значение 117: оно ближе к 0 (черный), поэтому мы переводим его в черный. Стандартным подходом было бы просто перейти к следующему пикселю и применить ту же формулу. Однако возникает проблема, когда у нас есть большое количество одинаковых пикселей. Они все становятся черными, и у нас остается огромный набор черных пикселей.
Рисунок 3. Простое пороговое сглаживание, применяемое к изображению
Диффузия ошибок использует более продвинутый подход: мы распространяем ошибку каждого вычисления на соседние пиксели. На каждом шаге не просто та же формула применяется к следующему пикселю, но принимается к сведению предыдущая ошибка и значение ошибки добавляется к текущему пикселю. Например, если текущий пиксель по-прежнему равен 117, он не просто преобразуется в черный, но вычисляется новое значение пикселя на основе предыдущего значения ошибки пикселя. Следующий код представляет собой простую реализацию вышеуказанного метода.
// Сглаживание - это двунаправленное разделение для хранения различных методов сглаживания.
type Dither struct { Filter [][]float32
} // Заполняем разноправленные фрагменты. Мы используем это для хранения уровня квантизации.
rErr := make([][]float32, dx)
gErr := make([][]float32, dx)
bErr := make([][]float32, dx) // Разные ошибки в двух направлениях
ydim := len(dither.Filter) - 1
xdim := len(dither.Filter[0]) / 2 // разделяем направление X на две половины
for xx := 0; xx < ydim + 1; xx++ { for yy := -xdim; yy <= xdim - 1; yy++ { if y + yy < 0 || dy <= y + yy || x + xx < 0 || dx <= x + xx { continue } // Распространяем ошибку квантизации rErr[x+xx][y+yy] += float32(er) * dither.Filter[xx][yy + ydim] gErr[x+xx][y+yy] += float32(eg) * dither.Filter[xx][yy + ydim] bErr[x+xx][y+yy] += float32(eb) * dither.Filter[xx][yy + ydim] }
}
Затем мы можем подключить любой из вышеупомянутых методов сглаживания, просто заменив компоненты массива двухмерных фильтров значениями распространения ошибок. Например, метод сглаживания Флойда-Стейнберга может быть выражен как:
colorquant.Dither{ [][]float32{ []float32{0.0, 0.0, 0.0, 7.0 / 48.0, 5.0 / 48.0}, []float32{3.0 / 48.0, 5.0 / 48.0, 7.0 / 48.0, 5.0 / 48.0, 3.0 / 48.0}, []float32{1.0 / 48.0, 3.0 / 48.0, 5.0 / 48.0, 3.0 / 48.0, 1.0 / 48.0}, }
}
Пример 1
Пример 2
Рисунок 4. Квантованное изображение (256 цветов) с применением сглаживания и без
Примеры использования квантования
Применение алгоритма диффузии ошибок на квантованном изображении приводит к уменьшению размера изображения, которое на взгляд почти не заметно, что может значительно повысить производительность CDN. Цветовое квантование также может использоваться для получения наиболее доминирующего цвета изображения, что можно использовать в случае, если мы хотим применить некоторые пользовательские настройки на основе обработанного изображения.
Возьмите, например, сайт электронной коммерции. Цветовое квантование может помочь показать товары, которые наиболее близки по цветам к запрошенным клиентами. Список возможных применений бесконечен.
Автор: Endre Simo
Источник: https://blog.filestack.com/
Редакция: Команда webformyself.