Algorytm Floyda-Steinberga
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[edytuj | edytuj kod]
-
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
