Algorytm Floyda-Steinberga

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
RGB 24bits palette sample image.jpg RGB 24bits palette sample image - 3-bit RGB.png
Przykład redukcji palety z 24-bitowej do 3-bitowej za pomocą algorytmu Floyda-Steinberga


Algorytm Floyda-Steinberga – 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).

Michelangelo's David - 63 grijswaarden.png Michelangelo's David - Floyd-Steinberg.png
Przykład redukcji dla zdjęcia głowy Dawida Michała Anioła

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).