algorytm.org

Dithering dla obrazów kolorowych

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?

Dithering dla obrazów kolorowych
Ocena użytkowników:***** / 5
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 30 lipca 2009 16:58

Czasem zachodzi potrzeba przekonwertowania obrazu do grafiki o ściśle określonej palecie kolorów. Najbardziej intuicyjnym sposobem jest wybranie dla każdego punktu z obrazu wejściowego koloru z palety barw, który jest najbardziej podobny do oryginału. I tutaj pojawia się pierwsze pytanie, który kolor wybrać? W naszych rozważaniach będziemy używać modelu RGB, który jest chyba najbardziej popularnym modelem do reprezentowania obrazów w komputerze. Dla tego modelu cała przestrzeń barw może być przedstawiona jako kostka sześcienna, a kolejne możliwe kolory jako punkty znajdujące się na jej powierzchni lub w środku. Para kolorów, która jest najbliżej siebie w tej trójwymiarowej przestrzeni jest najbardziej do siebie podobna. Odległość w przestrzeni definiujemy jako pierwiastek z sumy kwadratów odległości. Ponieważ nie interesuje nas wartość tej odległości, a jedynie znalezienie najbliższego koloru, możemy zrezygnować z czasochłonnego obliczania pierwiastka i znaleźć kolor dla, którego suma kwadratów odległości jest najmniejsza. Formalnie możemy zapisać to tak:
niech tablica colors oznacza docelową paletę n barw,
point oznacza kolor punktu, dla którego szukamy najbardziej podobnego koloru w palecie.
Dla takiego punktu wybierzemy barwę z palety, dla której wyrażenie:
(colors[i].r - point.r)2 + (colors[i].g - point.g)2 + (colors[i].b - point.b)2 (dla i = 1, 2, ...n)
jest najmniejsze.

W idealnym przypadku taka odległość wynosi 0. Co oznacza, że w obrazie wynikowym używamy dokładnie tego samego koloru co w obrazie wejściowym. Jednak zapewne w większości przypadków, odległość ta będzie większa od 0. Oznacza to, że nie udało nam się idealnie dopasować koloru i wprowadziliśmy tym samym do obrazu wynikowego pewien błąd. Będziemy go definiować osobno dla każdej składowej koloru (R, G, B). Wielkość błędu określamy jako różnicę pomiędzy wartością oryginalną a wartością użytą czyli:
  • dla składowej R: e.r = point.r - colors[i].r
  • dla składowej G: e.g = point.g - colors[i].g
  • dla składowej B: e.b = point.b - colors[i].b


Wartość dodatnia błędu oznacza, że "daliśmy" za mało barwy składowej, natomiast wartość ujemna oznacza zbyt dużo składowej w obrazie wynikowym. Jeżeli mamy już zdefiniowany błąd to możemy zastosować algorytmy ditheringu, czyli rozpraszania błędu do sąsiednich komórek. Dokładne tabele i sposób rozpraszania błędów znajdziesz w opisie algorytmu Floyd'a-Steinberg'a, przy czym pamiętać należy, że w przypadku obrazów kolorowych błąd i jego rozpraszanie obliczane są dla każdej składowej osobno.
Dobrze jest zastosować ucinanie błędu tak, by wartość składowej piksla po dodaniu błędu propagowanego z sąsiednich komórek, była w zakresie dopuszczalnych wartości (najczęściej 0-255 albo 0-1). Pozwala to zachować drobne szczegóły, które w przeciwnym przypadku mogą zostać utracone podczas konwersji.
W poniższym przykładzie przedstawiono obraz oryginalny (po lewej) oraz jego konwersję do grafiki 7-kolorowej przy pomocy prostego wybierania najbliższego koloru (obraz na środku) oraz z wykorzystaniem metody ditheringu (obraz po prawej)

Dithering dla obrazu kolorowego

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++Borland Builder 6
.cpp
.cpp
***** / 1
Tomasz LubińskiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 1
 
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: 30 lipca 2012 19:38
Dodaj komentarz