algorytm.org

Uporządkowane rozpraszanie błędów (tablice Bayer'a)

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?

Uporządkowane rozpraszanie błędów (tablice Bayer'a)
Ocena użytkowników:***** / 1
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 20 lipca 2011 11:54

Metoda uporządkowanego rozpraszania błędów (ang. ordered dithering) wykorzystywana jest w tak zwanej aproksymacji półtonowej, czyli wówczas gdy obraz kolorowy lub w odcieniach szarości chcemy 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. Podobnie punkty o jasności poniżej progu w obrazie wejściowym przekształca się w punkty czarne w obrazie wyjściowym. Efekt takiej metody jest jednak daleki od doskonałości.
Pewnym usprawnieniem jest metoda uporządkowanego rozpraszania błędów, nazwa pochodzi od rezultatu jaki otrzymamy - obszary o takiej samej jasności będą reprezentowane przez wyraźny uporządkowany powtarzający się wzór punktów, w przeciwieństwie do innych technik polegających na rozpraszaniu błędów (np.: Algorytm Floyda-Steinberga) gdzie obszary takie reprezentowane są przez punkty porozrzucane w nieładzie.
Podstawą działania tej metody są tak zwane tablice Bayer'a (ang. Bayer table). Tablice te mają rozmiary będące potęgami dwójki, i tak najmniejsza tablica o rozmiarach 2x2 ma postać:
24
31

Każda wariacja takiej tabeli polegająca na przesunięciu tabeli o 90, 180, 270 stopni, bądź jej lustrzane odbicia są prawidłowymi tablicami Bayer'a. Ważna jest zasada, że druga wartość jest po przekątnej pierwszej wartości, a czwarta po przekątnej trzeciej. Większe tablice wypełnia się rekurencyjnie. Wyobraźmy sobie, że w każdą wartość tablicy 2x2 wstawiamy nową tablicę 2x2. Do każdej komórki dawnej tablicy 2x2 wstawiamy kolejno wartości, 1, 2, 3, 4 i wstawiamy je do nowych tablic, są one puste więc trafiają w miejsce gdzie w tablicy 2x2 jest jedynka. Następnie wstawiamy 5, 6, 7, 8 - trafiają w miejsce gdzie w tablicy 2x2 jest dwójka, itd... Tablica 4x4 ma zatem postać:
614816
102124
715513
11391

Kolejna potęga dwójki to 8. Tabela 8x8 ma postać:
2254306224563264
38646144084816
2658185028602052
42103424412364
2355316321532961
39747153754513
2759195125571749
4311353419331

Kolejna tabela 16x16 wygląda następująco:
86214118246942221262548821612024896224128256
1502218254158301906215224184561603219264
10223070198110238782061042327220011224080208
16638134617446142141684013681764814416
90218122250822101142429222012425284212116244
1542618658146181785015628188601482018052
1062347420298226661941082367620410022868196
17042138101623413021724414012164361324
87215119247952231272558521311724593221125253
1512318355159311916314921181531572918961
10323171199111239792071012296919710923777205
16739135717547143151653713351734514113
91219123251832111152438921712124981209113241
1552718759147191795115325185571451717749
107235752039922767195105233732019722565193
1714313911163351313169411379161331291

Istnieje rekurencyjny wzór, umożliwiający obliczenie, gdzie w tablicy znajduje się zadana wartość:

xIndex(i,size,shift)=\begin{cases} shift+(i\text{ mod }2)&,size=2\\ xIndex(\lfloor(i-1)/4\rfloor+1,size/2,shift+(i\text{ mod }2)*(size/2))&,size\neq 2 \end{cases}\\\\\\ yIndex(i,size,shift)=\begin{cases} shift+\lfloor((i+2)\text{ mod }4)/2\rfloor&,size=2\\ yIndex(\lfloor(i-1)/4\rfloor+1,size/2,shift+\lfloor((i+2)\text{ mod }4)/2\rfloor*(size/2))&,size\neq 2 \end{cases}


By dowiedzieć się w jakim miejscu znajduje się liczba 12, w tablicy o rozmiarze 4x4, należy zatem wywołać funckję: xIndex(12, 4, 0) oraz yIndex(12, 4, 0), w wyniku otrzymamy wiersz i kolumnę (licząc od zera), gdzie znajduje się wartość 12 (czyli 1 oraz 2).

Jeżeli wiemy już jakie wartości mamy w tabeli możemy przejść do przetwarzania obrazu przy pomocy algorytmu uporządkowanego rozpraszania błędów. Wybieramy zatem tablicę, który użyjemy, niech będzie to tablica t o rozmiarze r oraz próg p. Przetwarzanie wygląda następująco:


Zatem mechanizm wygląda tak, że przykładamy tablicę do obrazu porównujemy wartości, a następnie przesuwamy się o cały rozmiar tablicy dalej. Takie postępowanie powoduje powstanie charakterytycznych wzorów dla obszarów o tej samej jasności.

Wynik działania algorytmu:

Obraz oryginalnyPrzekształcanie zwykłe - progoweUporządkowane rozpraszanie błędów
Obraz oryginalnyPrzekształcanie zwykłe - progoweUporządkowane rozpraszanie błędów

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