Алгоритм сглаживания Флойда–Стайнберга — алгоритм сглаживания изображений , впервые опубликованный в 1976 году Робертом В. Флойдом и Луисом Стайнбергом. Он широко используется в программах обработки изображений. Например, при конвертации изображения из формата Truecolor 24-bit PNG в формат GIF , который ограничен максимум 256 цветами.
Алгоритм достигает сглаживания с помощью диффузии ошибок , то есть он накладывает (добавляет ) остаточную ошибку квантования пикселя на соседние пиксели, чтобы иметь с ней дело позже. Он распределяет долг в соответствии с распределением (показанным как карта соседних пикселей):
Пиксель, отмеченный звездочкой (*), указывает на пиксель, который в данный момент сканируется, а пустые пиксели — это ранее сканированные пиксели. Алгоритм сканирует изображение слева направо, сверху вниз, квантуя значения пикселей по одному. Каждый раз ошибка квантования передается соседним пикселям, не затрагивая пиксели, которые уже были квантованы. Следовательно, если несколько пикселей были округлены вниз, становится более вероятным, что следующий пиксель будет округлен вверх, так что в среднем ошибка квантования близка к нулю.
Коэффициенты диффузии обладают свойством, что если исходные значения пикселей находятся точно посередине между ближайшими доступными цветами, то сглаженный результат представляет собой шахматный узор. Например, 50% серых данных могут быть сглажены как черно-белый шахматный узор. Для оптимального сглаженности подсчет ошибок квантования должен быть достаточно точным, чтобы ошибки округления не влияли на результат.
Для получения правильных результатов все значения следует сначала линеаризировать, а не работать напрямую со значениями sRGB, как это принято для изображений, хранящихся на компьютерах.
В некоторых реализациях горизонтальное направление сканирования чередуется между строками; это называется «змеевидным сканированием» или сглаживанием с преобразованием бустрофедона .
Описанный выше алгоритм представлен в следующем псевдокоде . Он работает для любого приблизительно линейного кодирования значений пикселей, например, 8-битных целых чисел, 16-битных целых чисел или действительных чисел в диапазоне [0, 1].
для каждого y сверху вниз выполнить для каждого x слева направо выполнить oldpixel := pixels[ x ][ y ] новыйпиксель := найти_ближайший_цвет_палитры(старыйпиксель) пиксели[ x ][ y ] := новыйпиксель quant_error := старыйпиксель - новыйпиксель пиксели[ x + 1][ y ] := пиксели[ x + 1][ y ] + квантовая_ошибка × 7 / 16 пиксели[ x - 1][ y + 1] := пиксели[ x - 1][ y + 1] + квантовая_ошибка × 3 / 16 пиксели[ x ][ y + 1] := пиксели[ x ][ y + 1] + quant_error × 5 / 16 пиксели[ x + 1][ y + 1] := пиксели[ x + 1][ y + 1] + квантовая_ошибка × 1 / 16
При преобразовании значений пикселей в оттенках серого из высокой в низкую битовую глубину (например, 8-битных оттенков серого в 1-битные черно-белые) find_closest_palette_color()можно выполнить простое округление, например:
найти_ближайший_цвет_палитры(старый_пиксель) = округлить(старый_пиксель / 255)
Псевдокод может привести к значениям пикселей, превышающим допустимые значения (например, больше 255 в 8-битных изображениях в оттенках серого). Такие значения в идеале должны обрабатываться функцией find_closest_palette_color(), а не обрезать промежуточные значения, поскольку последующая ошибка может вернуть значение обратно в диапазон. Однако, если используются целые числа фиксированной ширины, перенос промежуточных значений приведет к инверсии черного и белого, поэтому его следует избегать.
Реализация find_closest_palette_color()нетривиальна для палитры, которая распределена неравномерно, однако небольшие неточности в выборе правильного цвета палитры оказывают минимальное визуальное воздействие из-за распространения ошибки на будущие пиксели. Часто используется поиск ближайшего соседа в 3D.
