Дизеринг Флойда – Стейнберга - Floyd–Steinberg dithering

исходное изображение

нет дизеринга

Дизеринг Флойда – Стейнберга

1-битное изображение Статуя Давида, смешанный с алгоритмом Флойда – Стейнберга

Дизеринг Флойда – Стейнберга это изображение дизеринг алгоритм, впервые опубликованный в 1976 г. Роберт В. Флойд и Луи Стейнберг. Он обычно используется программным обеспечением для обработки изображений, например, когда изображение преобразуется в Гифка формат, который ограничен максимум 256 цветами.

Алгоритм достигает дизеринга, используя распространение ошибок, то есть подталкивает (добавляет) остаточную ошибка квантования из пиксель на соседние пиксели, о чем мы поговорим позже. Он распределяет задолженность в соответствии с распределением (показано в виде карты соседних пикселей):

${ displaystyle { begin {bmatrix} && * & { frac { displaystyle 7} { displaystyle 16}} & ldots ldots & { frac { displaystyle 3} { displaystyle 16}} & { гидроразрыва { displaystyle 5} { displaystyle 16}} & { frac { displaystyle 1} { displaystyle 16}} & ldots end {bmatrix}}}$

Пиксель, обозначенный звездочкой (*), указывает пиксель, который в настоящее время сканируется, а пустые пиксели - это пиксели, отсканированные ранее. Алгоритм сканирует изображение слева направо, сверху вниз, квантуя значения пикселей один за другим. Каждый раз ошибка квантования передается на соседние пиксели, не затрагивая пиксели, которые уже были квантованы. Следовательно, если количество пикселей было округлено в меньшую сторону, становится более вероятным, что следующий пиксель будет округлен в большую сторону, так что в среднем ошибка квантования будет близка к нулю.

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

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

В следующих псевдокод мы можем увидеть алгоритм, описанный выше. Это работает для любого приблизительно линейного кодирования значений пикселей, такого как 8-битные целые числа, 16-битные целые числа или действительные числа в диапазоне [0,1].

для каждого у сверху вниз делать    для каждого Икс слева направо делать        oldpixel: = пиксель [Икс][у] newpixel: = find_closest_palette_color (oldpixel) пиксель [Икс][у]: = newpixel Quant_error: = oldpixel - newpixel пиксель [Икс + 1][у    ]: = пиксель [Икс + 1][у    ] + Quant_error × 7/16 пикселей [Икс - 1][у + 1]: = пиксель [Икс - 1][у + 1] + Quant_error × 3/16 пиксель [Икс    ][у + 1]: = пиксель [Икс    ][у + 1] + Quant_error × 5/16 пикселей [Икс + 1][у + 1]: = пиксель [Икс + 1][у + 1] + Quant_error × 1/16

При преобразовании 16-битной шкалы серого в 8-битную find_closest_palette_color () может выполнить простое округление, например:

find_closest_palette_color (oldpixel) = круглый (oldpixel / 256)

Псевдокод может привести к тому, что значения пикселей превышают допустимые значения (например, больше 1 в представлении [0,1]). Такие значения в идеале должны быть обрезаны find_closest_palette_color () функция, а не отсечение промежуточных значений, поскольку последующая ошибка может вернуть значение в диапазон. Однако, если используются целые числа фиксированной ширины, перенос промежуточных значений приведет к инверсии черного и белого, и этого следует избегать.

использованная литература

• Дитеринг Флойда – Стейнберга (Проект курса графики, лаборатория Visgraf, Бразилия)
• Р. В. Флойд, Л. Стейнберг, Адаптивный алгоритм пространственной серой шкалы. Труды Общества отображения информации 17, 75–77 (1976).