Algorytm Floyda-Steinberga
![](http://upload.wikimedia.org/wikipedia/commons/d/d7/RGB_24bits_palette_sample_image.jpg)
![](http://upload.wikimedia.org/wikipedia/commons/7/79/RGB_24bits_palette_sample_image_-_3-bit_RGB.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/71/Michelangelo%27s_David_-_63_grijswaarden.png/150px-Michelangelo%27s_David_-_63_grijswaarden.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c1/Michelangelo%27s_David_-_Floyd-Steinberg.png/150px-Michelangelo%27s_David_-_Floyd-Steinberg.png)
Algorytm Floyda-Steinberga – algorytm redukcji palety barwnej lub tonalnej obrazu cyfrowego, opracowany w 1975 roku. Działanie algorytmu polega na kwantyzacji wykonywanej w taki sposób, by zminimalizować banding koloru, czyli efekt prostej redukcji palety barwnej lub tonalnej, przez kontrolowane rozpraszanie (ang. dithering) pikseli o kolorach z ograniczonej palety. W grafice komputerowej jest to jeden z najbardziej popularnych algorytmów rozpraszania.
Podstawą algorytmu Floyda-Steinberga jest rozpraszanie błędów wprowadzonej redukcji. Dana jest funkcja kwantyzująca, przypisująca dowolnej barwie – barwę z palety docelowej. Piksele obrazu przetwarzane są w kolejnych rzędach, od lewej do prawej. Dla każdego przetworzanego piksela obliczany jest błąd, czyli różnica między wynikiem funkcji kwantyzującej a barwą oryginalną (w przypadku obrazu monochromatycznego jest to pojedyncza liczba, dla przestrzeni RGB – trzy, dla CMYK – cztery liczby). Wartość tej różnicy jest następnie dodawana z odpowiednimi współczynnikami do wartości jeszcze nie przetworzonych pikseli sąsiadujących z danym (zwykle przyjmuje się sąsiedztwo 3×3 lub 4×4). Ponieważ suma współczynników jest równa 1, średni błąd wewnątrz sąsiedztwa dowolnego piksela jest zerowy – gdy piksel zostanie nadmiernie rozjaśniony, jego sąsiedzi zostaną przyciemnieni i odwrotnie. W praktyce błąd nigdy nie jest zerowy z powodu błędów zaokrągleń i efektów brzegowych, ale wizualnie obraz przypomina oryginał.
Algorytm Floyda-Steinberga stosuje się przy dostosowywaniu obrazu do formatu zapisu lub medium o ograniczonej palecie barwnej (format GIF, niektóre drukarki atramentowe).
Galeria
- Obraz oryginalny
- Obraz w palecie ograniczonej (web safe) bez użycia algorytmu F-S – widoczny banding
- Obraz w palecie ograniczonej (web safe) rozproszony algorytmem F-S