Скважность — характеристика растровых изображений¶

Скважность (англ. dithering) — метод обработки растровых изображений, при котором изображение с большим количеством цветов преобразуется в изображение с ограниченной палитрой за счёт распределения точек (пикселей) определённых цветов по определённому шаблону. Термин происходит от английского слова dither — «дрожать, вибрировать». Скважность используется там, где требуется сократить объём данных или ограничить число доступных цветов, сохранив при этом визуальное восприятие оригинала.

¶Принцип работы

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

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

¶Основные алгоритмы

¶Алгоритм Флойда — Стейнберга

Наиболее распространённый алгоритм скважности, предложенный Робертом Флойдом и Луи Стейнбергом в 1975 году. Ошибка квантования текущего пикселя распределяется между ещё не обработанными соседями справа, снизу и по диагонали снизу-справа с весовыми коэффициентами 7/16, 5/16, 3/16 и 1/16 соответственно. Обработка выполняется в одном проходе слева направо и сверху вниз.

¶Алгоритм Джарвиса — Джуdice — Нинке

Использует сетку 5×3, распределяя ошибку на 12 соседних пикселей. Даёт более гладкий результат, чем алгоритм Флойда — Стейнберга, но требует больше вычислений и может создавать характерные полосатые артефакты.

¶Алгоритм Стаки — Штейнберга

Разновидность алгоритма Флойда — Стейнберга, в которой направление обработки строк меняется каждую строку (змейкой). Это устраняет асимметрию, свойственную базовому алгоритму.

¶Ordered dithering (упорядоченная скважность)

Использует заранее заданную матрицу порогов (матрица Байера), которая накладывается на изображение. Результат детерминирован и не зависит от порядка обработки пикселей. Подходит для изображений с плавными градиентами, но создаёт выраженный регулярный паттерн.

¶Случайная скважность

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

¶Применение

¶Дисплеи с ограниченной палитрой

Исторически скважность применялась на мониторах, способных отображать лишь 1, 4 или 16 цветов (CGA, EGA, ранние Macintosh с одноцветным экраном). С помощью скважности такие дисплеи показывали фотографии и сложную графику.

¶Форматы сжатия

В формате GIF поддерживается палитра максимум на 256 цветов. При конвертации фотографий в GIF скважность позволяет уменьшить видимую потерю качества.

¶Полутоновая печать

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

¶Специализированные устройства

Электронные книги со стеклянными экранами (E Ink), умные часы, промышленные индикаторы и другие устройства с ограниченной цветовой палитрой активно используют алгоритмы скважности для отображения изображений.

¶Скважность и шум

Следует различать скважность и добавление шума. Добавление случайного шума перед квантованием (шум дithering) также позволяет избежать полос, но даёт более «грязный» результат. Скважность, напротив, стремится распределить ошибку равномерно и контролируемо.

¶Программная реализация

Большинство графических редакторов (Adobe Photoshop, GIMP, Krita) поддерживают различные алгоритмы скважности при сохранении изображений в форматах с ограниченной палитрой. В программировании алгоритмы скважности реализуются на разных языках, в том числе в стандартных библиотеках обработки изображений.

Источники:

• Floyd R. W., Steinberg L. «An Adaptive Algorithm for Spatial Greyscale». Proceedings of the Society for Information Display, 1976.
• Jarvis J. F., Judice C. N., Ninke W. H. «A Survey of Techniques for the Display of Continuous Tone Pictures on Bilevel Displays». Computer Graphics and Image Processing, 1976.
• Bayer B. E. «An Optimum Method for Two-Level Rendition of Continuous-Tone Pictures». IEEE International Conference on Communications, 1973.
• Russ J. C. «The Image Processing Handbook». CRC Press.
• Gonzalez R. C., Woods R. E. «Digital Image Processing». Pearson.