algorytm.org

Algorytm Floyda-Steinberga



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Floyda-Steinberga
Ocena użytkowników:***** / 20
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 01 sierpnia 2005 00:48

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:
Rozpraszanie błedu

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:
1215
11412
tablica błędów:
000
000
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:
1215
11412
tablica błędów:
0-30
-200
obraz wyjsciowy:
b  
   
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:
1215
11412
tablica błędów:
0-30
-200
obraz wyjsciowy:
bc 
   
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:
1215
11412
tablica błędów:
0-30
-201
obraz wyjsciowy:
bcc
   
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:
1215
11412
tablica błędów:
0-30
-231
obraz wyjsciowy:
bcc
c  
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:
1215
11412
tablica błędów:
0-30
-234
obraz wyjsciowy:
bcc
cc 
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:
1215
11412
tablica błędów:
0-30
-234
obraz wyjsciowy:
bcc
ccb
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:

Obraz oryginalnyPrzekształcanie zwykłe - progoweAlgorytm Floyd'a-Steinberg'a
Obraz oryginalnyPrzekształcanie zwykłe - progoweFloyd-Steinberg


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

Plik:

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC#Microsoft Visual Studio 2010
.cs
.cs
***** / 0
Tomasz LubińskiC/C++Borland Builder 6
.cpp
.cpp
***** / 4
Tomasz LubińskiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 2
Tomasz LubińskiJavaScriptFirefox 3.0+, Safari 3.0+, Chrome 3.0+, Opera 9.5+, IE 9.0+
.js
.js
***** / 0
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 26 sierpnia 2012 08:51
Komentarze
photo
0 # Zdzisław 2010-11-02 11:09
Super!
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+2 # Bartek_91 2013-06-12 20:26
W pseudokodzie jest błąd. Pierwszy warunek powinien brzmieć
Jeżeli p > obraz... to:
obraz_wy(i,j) = czarny;
itd...
Pozdrawiam
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+2 # MagicznyKrzysztof 2018-03-26 02:44
Rewelacyjne te artykuły o ditheringu. Wcześniej znalazłem wytłumaczenie na angielskiej Wikipedii z pseudokodem, ale coś mi nie działało. Zobaczyłem tutaj i już mi działa. No i różne inne algorytmy fajnie wytłumaczone na zasadzie różnicy względem Floyda. Wystarczy spojrzeć na tabelkę rozpraszania takiego algorytmu jak Jarvis i już wiadomo jak go napisać (o ile wcześniej się napisało Floyda).
Dzięki wielkie!
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz