Algorytm Floyda-Steinberga
Algorytm Floyda-Steinberga to metoda redukcji palety kolorów lub tonalności w obrazach cyfrowych, która została opracowana w 1975 roku. Jego działanie opiera się na kwantyzacji, realizowanej w sposób minimalizujący zjawisko bandingu kolorów, czyli efekt prostego ograniczenia palety kolorystycznej lub tonalnej, poprzez kontrolowane rozpraszanie (ang. dithering) pikseli z ograniczonej palety. W dziedzinie grafiki komputerowej jest to jeden z najczęściej stosowanych algorytmów rozpraszania.
Podstawowym założeniem algorytmu Floyda-Steinberga jest rozpraszanie błędów wynikających z przeprowadzanej redukcji. Istnieje funkcja kwantyzująca, która przypisuje każdej barwie odpowiadający kolor z palety docelowej. Piksele obrazu są przetwarzane w kolejnych rzędach, z lewej do prawej. Dla każdego przetwarzanego piksela obliczany jest błąd, będący różnicą między wynikiem funkcji kwantyzującej a oryginalną barwą (w przypadku obrazu monochromatycznego jest to jedna liczba, w przestrzeni RGB – trzy liczby, a w CMYK – cztery liczby). Wartość tej różnicy jest następnie dodawana do wartości jeszcze nieprzetworzonych pikseli sąsiadujących z danym pikselem, przy czym stosuje się odpowiednie współczynniki (zazwyczaj przyjmuje się sąsiedztwo 3×3 lub 4×4). Ponieważ suma współczynników wynosi 1, średni błąd w obrębie sąsiedztwa dowolnego piksela jest równy zeru – jeśli piksel zostanie zbyt mocno rozjaśniony, jego sąsiedzi będą przyciemniani i odwrotnie. W praktyce błąd nigdy nie jest zerowy z powodu zaokrągleń i efektów brzegowych, jednak wizualnie obraz przypomina oryginał.
Algorytm Floyda-Steinberga jest wykorzystywany przy dostosowywaniu obrazów do formatów zapisu lub mediów z ograniczoną paletą kolorów (np. format GIF, niektóre drukarki atramentowe).
== Galeria ==
