Algorytm Floyda-Steinberga
Z Wikipedii
Algorytm Floyda-Steinberga to opracowany w roku 1975 algorytm redukcji palety tonalnej lub barwnej obrazu (kwantyzacja) tak, by zminimalizować błąd (różnicę między obrazem w ograniczonej palecie, a oryginałem) przez kontrolowany rozrzut pikseli w ograniczonej palecie. Jest to jeden z najbardziej popularnych w grafice komputerowej algorytmów rozpraszania (ang. dithering).
 Obraz oryginalny |
 Obraz w palecie ograniczonej (web safe), bez użycia algorytmu F-S |
 Obraz w palecie ograniczonej (web safe), rozproszony algorytmem F-S |
Podstawą algorytmu Floyda-Steinberga jest rozpraszanie błędu. 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 przetworzonego piksela obliczany jest błąd, czyli różnica między wynikiem funkcji kwantyzującej, a oryginalną barwą (w przypadku monochromatycznym jest to pojedyncza liczba, dla przestrzeni RGB - trzy, dla CMYK - cztery). 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 3x3 lub 4x4). 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.
