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

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

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

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

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

Коэффициенты диффузии обладают тем свойством, что если исходные значения пикселей находятся точно посередине между ближайшими доступными цветами, результатом сглаживания будет узор в виде шахматной доски. Например, данные 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()функцией, а не промежуточными значениями, поскольку последующая ошибка может вернуть значение в допустимый диапазон. Однако, если используются целые числа фиксированной ширины, перенос промежуточных значений приведет к инверсии черного и белого, и этого следует избегать.

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

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

  • Floyd – Steinberg Dithering (проект курса графики, лаборатория Visgraf, Бразилия)
  • RW Floyd, L. Steinberg, Адаптивный алгоритм пространственной серой шкалы . Труды Общества отображения информации 17 , 75–77 (1976).