Algorytm Floyda-Steinberga

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
RGB 24bits palette sample image.jpg RGB 24bits palette sample image - 3-bit RGB.png
Redukcja palety 24-bitowej do 3-bitowej za pomocą algorytmu Floyda-Steinberga
Michelangelo's David - 63 grijswaarden.png Michelangelo's David - Floyd-Steinberg.png
Redukcja tonalnej palety 6-bitowej do 1-bitowej dla zdjęcia głowy Dawida rzeźby Michała Anioła

Algorytm Floyda-Steinbergaalgorytm 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]