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ć:
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ć:
Kolejna potęga dwójki to 8. Tabela 8x8 ma postać:
Kolejna tabela 16x16 wygląda następująco:
Istnieje rekurencyjny wzór, umożliwiający obliczenie, gdzie w tablicy znajduje się zadana wartość:
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:
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ć:
2 | 4 |
3 | 1 |
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ć:
6 | 14 | 8 | 16 |
10 | 2 | 12 | 4 |
7 | 15 | 5 | 13 |
11 | 3 | 9 | 1 |
Kolejna potęga dwójki to 8. Tabela 8x8 ma postać:
22 | 54 | 30 | 62 | 24 | 56 | 32 | 64 |
38 | 6 | 46 | 14 | 40 | 8 | 48 | 16 |
26 | 58 | 18 | 50 | 28 | 60 | 20 | 52 |
42 | 10 | 34 | 2 | 44 | 12 | 36 | 4 |
23 | 55 | 31 | 63 | 21 | 53 | 29 | 61 |
39 | 7 | 47 | 15 | 37 | 5 | 45 | 13 |
27 | 59 | 19 | 51 | 25 | 57 | 17 | 49 |
43 | 11 | 35 | 3 | 41 | 9 | 33 | 1 |
Kolejna tabela 16x16 wygląda następująco:
86 | 214 | 118 | 246 | 94 | 222 | 126 | 254 | 88 | 216 | 120 | 248 | 96 | 224 | 128 | 256 |
150 | 22 | 182 | 54 | 158 | 30 | 190 | 62 | 152 | 24 | 184 | 56 | 160 | 32 | 192 | 64 |
102 | 230 | 70 | 198 | 110 | 238 | 78 | 206 | 104 | 232 | 72 | 200 | 112 | 240 | 80 | 208 |
166 | 38 | 134 | 6 | 174 | 46 | 142 | 14 | 168 | 40 | 136 | 8 | 176 | 48 | 144 | 16 |
90 | 218 | 122 | 250 | 82 | 210 | 114 | 242 | 92 | 220 | 124 | 252 | 84 | 212 | 116 | 244 |
154 | 26 | 186 | 58 | 146 | 18 | 178 | 50 | 156 | 28 | 188 | 60 | 148 | 20 | 180 | 52 |
106 | 234 | 74 | 202 | 98 | 226 | 66 | 194 | 108 | 236 | 76 | 204 | 100 | 228 | 68 | 196 |
170 | 42 | 138 | 10 | 162 | 34 | 130 | 2 | 172 | 44 | 140 | 12 | 164 | 36 | 132 | 4 |
87 | 215 | 119 | 247 | 95 | 223 | 127 | 255 | 85 | 213 | 117 | 245 | 93 | 221 | 125 | 253 |
151 | 23 | 183 | 55 | 159 | 31 | 191 | 63 | 149 | 21 | 181 | 53 | 157 | 29 | 189 | 61 |
103 | 231 | 71 | 199 | 111 | 239 | 79 | 207 | 101 | 229 | 69 | 197 | 109 | 237 | 77 | 205 |
167 | 39 | 135 | 7 | 175 | 47 | 143 | 15 | 165 | 37 | 133 | 5 | 173 | 45 | 141 | 13 |
91 | 219 | 123 | 251 | 83 | 211 | 115 | 243 | 89 | 217 | 121 | 249 | 81 | 209 | 113 | 241 |
155 | 27 | 187 | 59 | 147 | 19 | 179 | 51 | 153 | 25 | 185 | 57 | 145 | 17 | 177 | 49 |
107 | 235 | 75 | 203 | 99 | 227 | 67 | 195 | 105 | 233 | 73 | 201 | 97 | 225 | 65 | 193 |
171 | 43 | 139 | 11 | 163 | 35 | 131 | 3 | 169 | 41 | 137 | 9 | 161 | 33 | 129 | 1 |
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:
- dzielimy wartość progu przez maksymalną wartość w wybranej tablicy, zatem: p = p / (r*r),
- sprawdzamy czy wartość pierwszego piksla w pierwszym rzędzie obrazu jest mniejsza od p pomnożonego przez pierwszą wartość w pierwszym rzędzie tablicy t, jeżeli tak to w obrazie wynikowym odpowiedni piksel ustawiamy na czarny, w przciwnym wypadku na biały,
- następnie sprawdzamy czy wartość drugiego piksla w pierwszym rzędzie obrazu jest mniejsza od p pomnożonego przez drugą wartość w pierwszym rzędzie tablicy t, jeżeli tak to w obrazie wynikowym odpowiedni piksel ustawiamy na czarny, w przciwnym wypadku na biały.
- ...
- następnie sprawdzamy czy wartość r-tego piksla w pierwszym rzędzie obrazu jest mniejsza od p pomnożonego przez r-tą wartość w pierwszym rzędzie tablicy t, jeżeli tak to w obrazie wynikowym odpowiedni piksel ustawiamy na czarny, w przciwnym wypadku na biały.
- następnie sprawdzamy czy wartość r+1-ego piksla w pierwszym rzędzie obrazu jest mniejsza od p pomnożonego przez pierwszą wartość w pierwszym rzędzie tablicy t, jeżeli tak to w obrazie wynikowym odpowiedni piksel ustawiamy na czarny, w przciwnym wypadku na biały.
- ...
- następnie sprawdzamy czy wartość pierwszego piksla w r+1-ym rzędzie obrazu jest mniejsza od p pomnożonego przez pierwszą wartość w pierwszym rzędzie tablicy t, jeżeli tak to w obrazie wynikowym odpowiedni piksel ustawiamy na czarny, w przciwnym wypadku na biały.
- ...
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 oryginalny | Przekształcanie zwykłe - progowe | Uporządkowane rozpraszanie błędów |
![]() | ![]() | ![]() |
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | C/C++ | Borland Builder 6 | .cpp | .cpp | ***** / 0 |
Tomasz Lubiński | Delphi/Pascal | Borland Delphi 5 | .pas | .pas | ***** / 0 |
Poprawiony: 16 sierpnia 2012 19:25