Algorytm ten wykorzystywany jest w tak zwanej aproksymacji półtonowej, czyli wówczas gdy obraz o większej liczbie odcieni szarości (ewentualnie barw) musimy przekształcić w obraz czarno - biały. Intuicyjnie robi się to tak, że punkty o jasności powyżej pewnego założonego progu (np.: połowa wartości maksymalnej) w obrazie wejściowym przekształca się na punkty białe w obrazie wyjściowym. Analogicznie punkty o jasności poniżej progu w obrazie wejściowym przekształca się w punkty czarne w obrazie wyjściowym. Podejście to ma jednak pewne wady. Obraz tak przekształcony nie wygląda zbyt ładnie. Z pomocą w takim wypadku przychodzi nam algorytm Floyda-Steinberga.
Opiszę tutaj podejście redukowania obrazu w skali szarości do obrazu czarno-białego, lecz po pewnych niewielkich modyfikacjach algorytm można wykorzystać do redukowania obrazów oryginalnych do
dowolnej liczby odcieni czy kolorów.
Podstawową cechą tego algorytmu jest użycie tablicy błędu o rozmiarze takim samym jak oryginalny obraz. Jest to podejście z dyfuzją, rozpraszaniem błędu (
ang. dithering, error diffusion). Dla każdego przetwarzanego punktu i decyzji czy przekształcić go w punkt biały czy czarny obliczany jest błąd, który następnie propagowany jest na sąsiednie komórki, tak jak pokazano to na obrazku poniżej:
po 7/16 błedu przekazywane jest do komórki kolejnej, 5/16 poniżej, 1/16 błędu przekazywana jest po ukosie do przodu a 3/16 po ukosie do tyłu.
Algorytm wygląda następująco:
e - aktualna wartość błędu,
e_tab - tablica błędów,
p - wartość progu (np.: połowa maksymalnej wartości jasności),
obraz_we - obraz wejściowy,
obraz_wy - obraz wyjściowy,
maksymalna_wartosc - maksymalna wartosc jaka może wystapic w obrazie (barwa biala),
Dla kolejnych punktów obrazu wejściowego wykonuj:
Jeżeli p<obraz_we[i,j]+e_tab[i,j] to:
obraz_wy[i,j] = czarny,
e = obraz_we[i,j]+e_tab[i,j]
w przeciwnym razie:
obraz_wy[i,j] = biały,
e = obraz_we[i,j]+e_tab[i,j]-maksymalna_wartosc
//następnie propaguj błąd
e_tab[i, j+1] = e_tab[i, j+1] + 7/16*e
e_tab[i+1, j-1] = e_tab[i+1, j-1] + 3/16*e
e_tab[i+1, j] = e_tab[i+1, j] + 5/16*e
e_tab[i+1, j+1] = e_tab[i+1, j+1] + 1/16*e
Prz czym należy zwrócić uwagę, że błąd przekazywany jest do komórek sąsiednich, zatem albo musimy wprowadzić warunki by nie przekazywać błędu
- w prawo (e_tab[i, j+1] oraz e_tab[i+1, j+1]), dla komórek położonych na prawej krawędzi obrazu
- w dół (e_tab[i+1, j-1], e_tab[i+1, j] oraz e_tab[i+1, j+1]), dla komórek położonych na dolnej krawędzi obrazu
- oraz w lewo (e_tab[i+1, j-1]), dla komórek położonych na lewej krawędzi obrazu
jeżeli tablica błędów ma dokładnie taki sam rozmiar jak obraz oryginalny. Chodzi po prostu o zabezpieczenie się przed wyjściem poza zakresy tablicy
e_tab. Innym rozwiązaniem jest utworzenie odpowiednio większej tablicy
e_tab (po jednym wierszu u góry i u dołu, oraz po jednej kolumnie z lewej i prawej). Dzięki takiemu zabiegowi pozbywamy się czasochłonnego obliczania kolejnych warunków dla przenoszenia błędów. Wówczas błąd znajdujący się w specjalnie dodanych kolumnach i wierszach jest po prostu przez algorytm ignorowany.
Przykład:
obraz wejściowy oraz obraz wyjściowy mają rozmiar 3x2, próg wynosi 10, maksymalna wartość wynosi 20:
1)
obraz wejściowy:
|
tablica błędów:
|
obraz wyjsciowy:
|
Bierzemy pierwszy element i dodajemy do niego analogiczny element tablicy błędów. Wynik wynosi 12. Nasz próg wynosi 10, zatem odpowiedni element obrazu wyjściowego zaznaczamy kolorem białym (b). Błąd w tym wypadku wynosi 12-20 = -8. I propagujemy go do odpowiednich komórek tablicy błędów. Do komórki na prawo dodajemy wartość 7/16 * -8 = -3, do komórki po ukosie na lewo 3/16 * -8 = -1 (ale jest poza zakresem), do komórki poniżej 5/16 * -8 = -2, do komórki po ukosie na prawo 1/16 * -8 = 0.
2)
obraz wejściowy:
|
tablica błędów:
|
obraz wyjsciowy:
|
Bierzemy kolejny element i dodajemy do niego analogiczny element tablicy błędów. Wynik wynosi -2. Nasz próg wynosi 10, zatem odpowiedni element obrazu wyjściowego zaznaczamy kolorem czarnym (c). Błąd w tym wypadku wynosi -2. Propagujemy go do odpowiednich komórek tablicy błędów. Do komórki na prawo dodajemy wartość 7/16 * -2 = 0, do komórki po ukosie na lewo 3/16 * -2 = 0, do komórki poniżej 5/16 * -2 = 0, do komórki po ukosie na prawo 1/16 * -2 = 0. Błąd był na tyle mały, że przy użyciu arytmetyki stałoprzecinkowej (odrzucamy wartość po przecinku) został on rozproszony do tego stopnia, że zanikł.
3)
obraz wejściowy:
|
tablica błędów:
|
obraz wyjsciowy:
|
Bierzemy kolejny element i dodajemy do niego analogiczny element tablicy błędów. Wynik wynosi 5. Nasz próg wynosi 10, zatem odpowiedni element obrazu wyjściowego zaznaczamy kolorem czarnym (c). Błąd w tym wypadku wynosi 5. Propagujemy go do odpowiednich komórek tablicy błędów. Do komórki na prawo dodajemy wartość 7/16 * 5 = 2 (ale jest poza zakresem), do komórki po ukosie na lewo 3/16 * 5 = 0, do komórki poniżej 5/16 * 5 = 1, do komórki po ukosie na prawo 1/16 * 5 = 0 (poza zakresem).
4)
obraz wejściowy:
|
tablica błędów:
|
obraz wyjsciowy:
|
Bierzemy kolejny element i dodajemy do niego analogiczny element tablicy błędów. Wynik wynosi 9. Nasz próg wynosi 10, zatem odpowiedni element obrazu wyjściowego zaznaczamy kolorem czarnym (c) (w zwykłym przekształceniu progowym byłby biały). Błąd w tym wypadku wynosi 9. Propagujemy go do odpowiednich komórek tablicy błędów. Do komórki na prawo dodajemy wartość 7/16 * 9 = 3, wszystkie komórki poniżej są już poza zakresem, do komórki po ukosie na lewo 3/16 * 9 = 1, do komórki poniżej 5/16 * 9 = 2, do komórki po ukosie na prawo 1/16 * 9 = 0.
5)
obraz wejściowy:
|
tablica błędów:
|
obraz wyjsciowy:
|
Bierzemy kolejny element i dodajemy do niego analogiczny element tablicy błędów. Wynik wynosi 7. Nasz próg wynosi 10, zatem odpowiedni element obrazu wyjściowego zaznaczamy kolorem czarnym (c). Błąd w tym wypadku wynosi 7. Propagujemy go do odpowiednich komórek tablicy błędów. Do komórki na prawo dodajemy wartość 7/16 * 7 = 3, wszystkie komórki poniżej są już poza zakresem, do komórki po ukosie na lewo 3/16 * 7 = 1, do komórki poniżej 5/16 * 7 = 2, do komórki po ukosie na prawo 1/16 * 7 = 0.
6)
obraz wejściowy:
|
tablica błędów:
|
obraz wyjsciowy:
|
Bierzemy kolejny element i dodajemy do niego analogiczny element tablicy błędów. Wynik wynosi 16. Nasz próg wynosi 10, zatem odpowiedni element obrazu wyjściowego zaznaczamy kolorem białym (b). Błąd w tym wypadku wynosi 16-20 = -4. Propagujemy go do odpowiednich komórek tablicy błędów - wszystkie znajdują się już poza zakresem, ale dla porządku pokażemy jaką miałyby wartość gdyby przekazywane były dalej. Do komórki na prawo dodajemy wartość 7/16 * -4 = -1, do komórki po ukosie na lewo 3/16 * -4 = 0, do komórki poniżej 5/16 * -4 = -1, do komórki po ukosie na prawo 1/16 * -4 = 0. Otrzymaliśmy końcowy wynik.
7)
obraz wejściowy:
|
tablica błędów:
|
obraz wyjsciowy:
|
W ogólności tablicy błędów można nie używać. Wówczas obliczone błędy należy dodawać do analogicznych punktów obrazu wejściowego. W podanym powyżej przykładzie błędy były obcinane do wartości całkowitych w niektórych zastosowaniach można zastosować zapisywanie błędu wraz z wartościami po przecinku. Na podstawie tego algorytmu opracowano wiele podobnych algorytmów ditheringu, w których błąd przekazywany jest do większej liczby komórek, np.:
Burkes,
Fan,
Jarvis, Judice, Ninke,
Stucki,
Sierra 3,
Sierra 2,
Sierra 2-4A (Filter Lite),
Atkinson,
Shiau-Fan (4 komórkowy),
Shiau-Fan (5 komórkowy).
Wynik działania algorytmu:
Przykład w JavaScript:
Ustaw ścieżkę do pliku (lub pozostaw tą domyślną), wczytaj plik a następnie użyj przycisku "Algorytm Floyd'a Steinberg'a" by sprawdzić działanie metody.
Ze względu na zabezpieczenia w przeglądarkach, skrypt otwiera wyłącznie pliki graficzne w obrębie naszego serwisu, np:
http://www.algorytm.org/images/stories/po/anaglif_lewy.jpg
http://www.algorytm.org/images/stories/po/orig.gif
http://www.algorytm.org/images/stories/mb/hsv.jpg
Komentarze