Смешение Флойда – Стейнберга - это алгоритм сглаживания изображения , впервые опубликованный в 1976 году Робертом Флойдом и Луисом Стейнбергом . Он обычно используется программным обеспечением для обработки изображений, например, когда изображение преобразуется в формат GIF , который ограничен максимум 256 цветами.
Алгоритм Достигает сглаживание с использованием диффузии ошибки , то есть он проталкивает (добавляет) остаточную ошибку квантования из более пикселя на его соседних пикселей, которые будут рассмотрены позже. Он распределяет долг в соответствии с распределением (показано в виде карты соседних пикселей):
Пиксель, обозначенный звездочкой (*), указывает пиксель, который в данный момент сканируется, а пустые пиксели - это пиксели, отсканированные ранее. Алгоритм сканирует изображение слева направо, сверху вниз, квантуя значения пикселей одно за другим. Каждый раз ошибка квантования передается на соседние пиксели, не затрагивая пиксели, которые уже были квантованы. Следовательно, если количество пикселей было округлено в меньшую сторону, становится более вероятным, что следующий пиксель будет округлен в большую сторону, так что в среднем ошибка квантования будет близка к нулю.
Коэффициенты диффузии обладают тем свойством, что если исходные значения пикселей находятся ровно посередине между ближайшими доступными цветами, результатом сглаживания будет узор в виде шахматной доски. Например, данные 50% серого могут быть смешаны как черно-белый узор в виде шахматной доски. Для оптимального дизеринга подсчет ошибок квантования должен производиться с достаточной точностью, чтобы ошибки округления не влияли на результат.
В некоторых реализациях горизонтальное направление сканирования чередуется между строками; это называется "серпантинным сканированием" или дизерингом с преобразованием бустрофедона .
В следующем псевдокоде мы видим алгоритм, описанный выше. Это работает для любого приблизительно линейного кодирования значений пикселей, такого как 8-битные целые числа, 16-битные целые числа или действительные числа в диапазоне [0,1].
для каждого y сверху вниз do для каждого x слева направо do oldpixel: = pixel [ x ] [ y ] newpixel: = find_closest_palette_color (старый пиксель) пиксель [ x ] [ y ]: = новый пиксель Quant_error: = oldpixel - newpixel пиксель [ x + 1] [ y ]: = пиксель [ x + 1] [ y ] + Quant_error × 7/16 пиксель [ x - 1] [ y + 1]: = пиксель [ x - 1] [ y + 1] + Quant_error × 3/16 пиксель [ x ] [ y + 1]: = пиксель [ x ] [ y + 1] + Quant_error × 5/16 пиксель [ x + 1] [ y + 1]: = пиксель [ x + 1] [ y + 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()
функцией, а не промежуточными значениями, поскольку последующая ошибка может вернуть значение в допустимый диапазон. Однако, если используются целые числа фиксированной ширины, перенос промежуточных значений приведет к инверсии черного и белого, и этого следует избегать.
Рекомендации
- Floyd – Steinberg Dithering (проект курса графики, лаборатория Visgraf, Бразилия)
- RW Floyd, L. Steinberg, Адаптивный алгоритм пространственной серой шкалы . Труды Общества отображения информации 17 , 75–77 (1976).