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

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

Нет сглаживания

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

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

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

Выполнение

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

$${\begin{bmatrix}&&*&{\frac {\displaystyle 7}{\displaystyle 16}}&\ldots \\\ldots &{\frac {\displaystyle 3}{\displaystyle 16}}&{\frac {\displaystyle 5}{\displaystyle 16}}&{\frac {\displaystyle 1}{\displaystyle 16}}&\ldots \\\end{bmatrix}}$$

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

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

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

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

for each y from top to bottom do
    for each x from left to right do
        oldpixel := pixels[x][y]
        newpixel := find_closest_palette_color(oldpixel)
        pixels[x][y] := newpixel
        quant_error := oldpixel - newpixel
        pixels[x + 1][y    ] := pixels[x + 1][y    ] + quant_error × 7 / 16
        pixels[x - 1][y + 1] := pixels[x - 1][y + 1] + quant_error × 3 / 16
        pixels[x    ][y + 1] := pixels[x    ][y + 1] + quant_error × 5 / 16
        pixels[x + 1][y + 1] := pixels[x + 1][y + 1] + quant_error × 1 / 16

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

find_closest_palette_color(oldpixel) = round(oldpixel / 255)

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

The find_closest_palette_color нетривиально для палитры, которая распределена неравномерно. В таком случае поиск ближайшего соседа требуется в 3D.

См. также

• Дизеринг Аткинсона , вариант дизеринга Флойда-Стейнберга, разработанный Биллом Аткинсоном.

Ссылки

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