algorytm.org

Technika mikrowzorów (metoda komórkowa)

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?

Technika mikrowzorów (metoda komórkowa)
Ocena użytkowników:***** / 3
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 12 września 2009 14:44

Technika mikrowzorów (ang. patterning, pattern) wykorzystywana jest powszechnie w druku, gdy obraz w odcieniach szarości trzeba przedstawić za pomocą czarno-białych punktów. Metoda ta może być również wykorzystana dla obrazów kolorowych - najpierw jednak następuje rozłożenie obrazu na składowe CMY bądź CMYK, a następnie dla każdej składowej z osobna stosujemy podaną poniżej metodę. Potem wszystkie wyniki dla kolejnych składowych nakładamy na siebie.
Technika mikrowzorców polega na przekształceniu każdego punktu obrazu wejściowego we wzór punktów. Każdy taki wzór nazywamy komórką półtonową, dlatego też czasem metodę tą nazywa się czasem metodą komórkową. Poniżej przedstawiony jest przykładowy zbiór mikrowzorów o rozmiarach 3x3.

   
   
   
   
 x 
   
   
 xx
   
 x 
 xx
   
 xx
 xx
   
 xx
 xx
 x 
 xx
xxx
 x 
 xx
xxx
xx 
xxx
xxx
xx 
xxx
xxx
xxx


Jeżeli teraz ponumerujemy sobie kolejno te wzory, to możemy zauważyć pewną właściwość. Mianowicie jeżeli dany punkt wystąpił we wzorze i to musi on wystąpić również w kolejnym wzorze i+1. Sprawia to, że każdy mikrowzór możemy reprezentować za pomocą macierzy D(n), gdzie n jest rozmiarem mikrowzoru. Przykład powyżej reprezentowany jest następującą macierzą:

834
612
759


Jeżeli ponumerujemy mikrowzory od 0, to jak widać powyżej kolejne wartości w macierzy odpowiadają pierwszemu mikrowzorowi, w którym pojawia się dany punkt. Teraz musimy odpowiedzieć sobie na pytanie w jaki sposób punkty obrazu wejściowego będziemy przekształcać w mikrowzory. Jak łatwo się domyślić o tym, w który mikrowzór przekształcić punkt decydować będzie jego jasność.
Jeżeli zadany będziemy mieli próg powyżej którego zapalać będziemy wszystkie punkty (używać będziemy ostatniego z mikrowzorów) oraz rozmiar mikrowzoru n to dla danego punktu o wartości x użyjemy:
  • zerowego mikrowzoru (w którym wszystkie punkty są wyłączone) jeżeli x < (1*próg)/(n*n)
  • pierwszego mikrowzoru (w którym jeden punkt jest włączony) jeżeli x ≥ (1*próg)/(n*n) oraz x < (2*próg)/(n*n)
  • drugiego mikrowzoru (w którym dwa punkty są włączone) jeżeli x ≥ (2*próg)/(n*n) oraz x < (3*próg)/(n*n)
  • trzeciego mikrowzoru (w którym trzy punkty są włączone) jeżeli x ≥ (3*próg)/(n*n) oraz x < (4*próg)/(n*n)
  • ...
  • ostatniego mikrowzoru (w którym wszystkie punkty są włączone) jeżeli x ≥ próg


Może na pierwszy rzut oka, wygląda to nieco skompilkowanie, ale w bardzo łatwy spoób, do tego przekształcenia będzimy mogli wykorzystać macierz mikrowzoru D(n). Otóż w wynikowym mikrowzorze będziemy zapalać punkt (i, j) jeżeli x ≥ (D(n)(i,j)*próg) / (n*n). Najlepiej zrozumieć to na przykładzie. Niech nasz próg wynosi 128, a punkt który chcemy przetworzyć w mikrowzór ma wartość 85, użyjemy wcześniej zdefiniowanej macierzy.
Bierzemy pierwszą wartość z macierzy mikrowzoru i sprawdzamy nierówność 85 ≥ (8*128) / (3*3)?, po obliczeniu 85 ≥ 113? - nie - zatem pierwszy punkt w mikrowzorze będzie zgaszony.
Bierzemy kolejną wartość z macierzy mikrowzoru i sprawdzamy nierówność 85 ≥ (3*128) / (3*3)?, po obliczeniu 85 ≥ 42? - tak - zatem kolejny punkt w mikrowzorze będzie włączony.
Bierzemy kolejną wartość z macierzy mikrowzoru i sprawdzamy nierówność 85 ≥ (4*128) / (3*3)?, po obliczeniu 85 ≥ 56? - tak - zatem kolejny punkt w mikrowzorze będzie włączony.
Bierzemy kolejną wartość z macierzy mikrowzoru i sprawdzamy nierówność 85 ≥ (6*128) / (3*3)?, po obliczeniu 85 ≥ 85? - tak - zatem kolejny punkt w mikrowzorze będzie włączony.
Bierzemy kolejną wartość z macierzy mikrowzoru i sprawdzamy nierówność 85 ≥ (1*128) / (3*3)?, po obliczeniu 85 ≥ 12? - tak - zatem kolejny punkt w mikrowzorze będzie włączony.
Bierzemy kolejną wartość z macierzy mikrowzoru i sprawdzamy nierówność 85 ≥ (2*128) / (3*3)?, po obliczeniu 85 ≥ 28? - tak - zatem kolejny punkt w mikrowzorze będzie włączony.
Bierzemy kolejną wartość z macierzy mikrowzoru i sprawdzamy nierówność 85 ≥ (7*128) / (3*3)?, po obliczeniu 85 ≥ 99? - nie - zatem kolejny punkt w mikrowzorze będzie wyłączony.
Bierzemy kolejną wartość z macierzy mikrowzoru i sprawdzamy nierówność 85 ≥ (5*128) / (3*3)?, po obliczeniu 85 ≥ 71? - tak - zatem kolejny punkt w mikrowzorze będzie włączony.
Bierzemy kolejną wartość z macierzy mikrowzoru i sprawdzamy nierówność 85 ≥ (9*128) / (3*3)?, po obliczeniu 85 ≥ 128? - nie - zatem kolejny punkt w mikrowzorze będzie wyłączony.
Podsumowywując dla progu równego 128 i wartości punktu 85 wygenerujemy następujący mikrowzór:

 xx
xxx
 x 


Jak łatwo zauważyć metoda komórkowa powoduje powiększenie wynikowego obrazu - jeden punkt przechodzi we wzór punktów. Poniżej przykład przekształcenia techniką mikrowzorów i zdefniowaną wcześniej macierzą:

Technika mikrowzorów


W podanym dotychczas przykładzie punkty, tworzące kolejne mikrowzory były ze sobą połączone, ale nic nie stoi na przeszkodzie zdefiniować zbiór, dla którego punkty w niektórych mikrowzorach nie są ze sobą połączone (mikrowzory rozproszone). Na przykład:

174
583
629


wynik zastosowania mikrowzorów rozproszonych:

Mikrowzory rozproszone


Rozmiary mikrowzorów mogą być również inne, na przykład D(2) (czyli 2x2):

13
42

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: 04 lutego 2014 20:44
Komentarze
photo
0 # arek_w 2009-11-17 15:05
Ciekawy artykuł.
Pamiętam że kiedyś robiło się coś takiego na czarno-białych Herkulesach (dla tych, co nie wiedzą, były to karty graficzne, które mogły wyświetlać jedynie dwa kolory - czarny i biały). Jednak nazywało się to dithering. Czy to jest to samo?
To co się robiło na Herkulesach można by przedstawić za pomocą macierzy mniej więcej tak:

1 2
2 3

na przykład (bardzo prosty z resztą). Różnica jest taka że w tym ditheringu - jeśli przedstawić go za pomocą macierzy przedstawionych w artykule - numery mogą się powtarzać, więc pewnie to nie to samo.
Poza tym raz zapalone punkty mogły być później wygaszone wraz ze wzrostem jasności.
My stosowaliśmy raczej ciąg macierzy podobny do tego na początku artykułu, a nie numerowaną macierz.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz