Cyfrowe przetwarzanie obrazów binarnych

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Cyfrowe przetwarzanie obrazów binarnych (przetwarzanie binarnych obrazów cyfrowych) (ang. binary digital image processing) – dziedzina Przetwarzania obrazów cyfrowych zajmująca się komputerowymi algorytmami obróbki obrazów binarnych.

Obraz binarny[edytuj | edytuj kod]

Obraz binarny jest specjalnym rodzajem obrazu cyfrowego, w którym piksele mogą przybierać tylko dwie wartości[1]. Zazwyczaj kodowane są za pomocą pojedynczego bitu i przyjmują wartość 0 lub 1. Spotyka się także reprezentację bajtową, wykorzystującą inne pary wartości: (0, 255), (-1, 1), (True, False).

Podczas interpretacji obrazu jedna z wartości przyjmowana jest za tło, druga - za pierwszy plan. Zbiór wszystkich pikseli należących do tła określa się mianem dopełnienia (ang. complement), piksele należące do pierwszego planu określane są suportem (ang. support). Interpretacja, która z wartości zostanie przypisana bieli, a która czerni, jest zależna od urządzenia. W niektórych przypadkach wykorzystywane są także inne kolory, np. w standardzie TWAIN określającym komunikacje pomiędzy skaneramiaparatami cyfrowymi a programami graficznymi, stosuje się wanilię i czekoladę.

Sąsiedztwo[edytuj | edytuj kod]

Sąsiedztwo ośmiospójne i czterospójne

W przetwarzaniu obrazów binarnych ważne jest określenie, kiedy dwa piksele sąsiadują ze sobą. W tym celu definiuje się dla każdego piksela jego sąsiedztwo. Najczęściej wykorzystywane sąsiedztwa punktu p o współrzędnych (x,y) to:

czterospójne - obejmuje cztery piksele przyległe do danego z góry, dołu i po bokach
 N_4(p) =  ( (x,y-1),(x,y+1),(x-1,y),(x+1,y) ),
ośmiospójne - obejmuje osiem pikseli przyległych do danego po jednym z góry i z dołu, dwa po bokach oraz cztery na przekątnych
 N_8(p) = ( (x,y-1),(x,y+1),(x-1,y),(x+1,y),(x-1,y-1),(x-1,y+1),(x+1,y-1),(x+1,y+1) ).

Operacje morfologiczne[edytuj | edytuj kod]

Operacje morfologiczne są jednymi z ważniejszych operacji przetwarzania obrazów, gdyż pozwalają przeprowadzić zaawansowaną analizę kształtów poszczególnych obiektów oraz odległości między nimi. Podstawowe przekształcenia morfologiczne można ze sobą łączyć, co daje podstawę do budowania skomplikowanych systemów analizy obrazu.

Przetwarzanie obrazów binarnych odbywa się z wykorzystaniem morfologii matematycznej, teorii analizy i przetwarzania struktur geometrycznych opartej na teorii mnogości, kratach, topologii i funkcjach losowych.

Przetwarzany obraz określany jest przez zbiór I(x,y)\in\{0,1\} pikseli p=(x,y), w którym można wyróżnić dwa podzbiory

  • pierwszy plan, piksele przyjmujące wartość 1
 U_1 = \{p|I(p) = 1\}
  • tło, piksele przyjmujące wartość 0
 U_2 = \{p|I(p) = 0\}

Element strukturalny[edytuj | edytuj kod]

Właściwości filtrów morfologicznych określane są przez tzw. element strukturalny, wykorzystywany jako ruchome okno. Określony jest względem wybranego piksela, tzw. punktu centralnego lub początkowego. Element strukturalny B(x,y)\in\{1,2\} może przybrać dowolny kształt i wielkość, zawierać dowolną kombinację wartości 0 i 1, zaś jego punkt centralny może być w dowolnym miejscu. Dla uproszczenia zapisu skomplikowanych kształtów można niektórym pikselom przypisać literę (np. z) oznaczającą, że mogą one przyjąć dowolną wartość.

Jednym z częściej stosowanych elementów strukturalnym jest kwadrat o boku 2N+1 (zazwyczaj 3x3) i wartości 1 dla wszystkich pikseli. W niektórych operacjach element strukturalny jest obracany symetrycznie względem punktu środkowego (dając \tilde B).

Przykładowe elementy strukturalne - kolorem czerwonym zaznaczono punkt centralny danego elementu.


Operatory morfologiczne[edytuj | edytuj kod]

Można wyróżnić jeden ogólny schemat działania algorytmów morfologicznych:

  1. Element strukturalny jest przemieszczany po całym obrazie tak, by analizowany piksel był punktem centralnym elementu strukturalnego.
  2. Dla każdego takiego punktu następuje porównanie zgodności jego otoczenia z wzorcem elementu strukturalnego.
  3. W przypadku zgodności (najczęściej), następuje wykonanie operacji na badanym punkcie - zazwyczaj zmiana przypisanej mu wartości.

Warto zauważyć, że w przeciwieństwie do typowych przekształceń punktowych, tj. filtry konwolucyjne, medianowe, logiczne i inne, operacje morfologiczne nie modyfikują całego obrazu, lecz tą jego część, której otoczenie odpowiada wzorcowi elementu strukturalnego.

Dylatacja[edytuj | edytuj kod]

Dylatacja, czyli rozszerzanie, jest zastosowaniem sumy Minkowskiego do obrazu[2]:

I \oplus B \equiv \{p \in U_1 | \tilde B \cap I \neq \emptyset \}

lub

I \oplus B \equiv  \bigcup\limits_{p\in B} (I + p).

Operacja ta przykłada obrócony element strukturalny do każdego piksela na obrazie. Jeżeli choć jeden piksel z sąsiedztwa objętego przez B ma wartość równość jeden, punkt centralny również otrzymuje wartość jeden. W przeciwnym wypadku przypisywane jest mu zero.

Istotny wpływ na wynik dylatacji ma wybór elementu strukturalnego. Przy niestandardowym kształcie rozrost obiektu jest kierunkowy. Z kolei jeżeli punkt centralny nie leży w środku elementu, rozrost jest niesymetryczny. Najbardziej neutralny efekt daje wykorzystanie elementu zbliżonego kształtem do koła. Konsekwencją dylatacji jest zwiększenie obiektu, zniknięcie detali i wypełnienie „dziur” w niespójnym obszarze. Często, aby uzyskać pożądany efekt stosuje się dylatacje wielokrotną.

Przykład dylatacji zastosowanej na obrazie binarnym


Erozja[edytuj | edytuj kod]

Erozja, czyli zwężanie, jest zastosowaniem różnicy Minkowskiego do obrazu:

I \ominus B \equiv \{p \in U_1  | \tilde B_p \subset I\},

gdzie \tilde B_p oznacza przyłożenie \tilde B do piksela p.

Operacja ta przykłada obrócony element strukturalny do każdego piksela na obrazie. Jeżeli choć jeden piksel z sąsiedztwa objętego przez B ma wartość równą zero, punkt centralny również otrzymuje wartość zero. W przeciwnym wypadku jego wartość nie ulega zmianie.

Erozja jest operacją dualną do dylatacji - jeżeli wykonamy negatyw obrazu, operacje te przejdą jedna w drugą. Również na erozję istotny wpływ ma wybór elementu strukturalnego. Konsekwencją erozji jest zmniejszenie obiektu, zniknięcie wąskich gałęzi i małych obiektów, likwidacja szumu, rozszerzenie się „dziur” w niespójnym obszarze - przyjmują one kształt elementu strukturalnego.

Przykład zastosowania operatora erozji na obrazie binarnym - dla sąsiedztwa ośmiospójnego (przyjęto, że piksele za granicą obrazu przyjmują wartość 0)
Przykład zastosowania operatora erozji na obrazie binarnym - dla sąsiedztwa czterospójnego (przyjęto, że piksele za granicą obrazu przyjmują wartość 0)


Otwarcie[edytuj | edytuj kod]

Otwarcie morfologiczne jest równoważne nałożeniu operacji dylatacji na wynik erozji obrazu pierwotnego

I \circ B = (I \ominus B)\oplus B.

Operacja otwarcia zachowuje rozmiary obiektów obrazu przy ich jednoczesnym wygładzeniu - usunięciu wszystkich „wystających” elementów. Zwiększanie rozmiaru elementu strukturalnego, B, skutkuje usuwaniem coraz większych detali obrazu oraz upodabnianiem powstałych obszarów do elementu strukturalnego. Dodatkowo, operacja otwarcia posiada własność idempotencji, czyli niezmienności wyniku niezależnie od wielokrotności stosowania operacji

I \circ B= (I\circ B)\circ B = ((I\circ B)\circ B)\circ B = \ldots

Istnieje pojęcie operacji otwarcia „wielopoziomowego”, czyli wielokrotnego zastosowania operatorów erozji, a następnie dylatacji

(I\ominus B \ominus B \ldots) \oplus B \oplus B \ldots

które jest równoważne zastosowaniu pojedynczej operacji otwarcia z odpowiednio większym elementem strukturalnym.

Przykład operacji otwarcia zastosowanej na obrazie binarnym


Domknięcie[edytuj | edytuj kod]

Operacja domknięcia morfologicznego jest równoważne nałożeniu operacji erozji na wynik dylatacji obrazu pierwotnego

I \bullet B = (I \oplus B)\ominus B.

Domknięcie usuwa z obrazu wszelkie „dziury” oraz wklęsłości mniejsze od elementu strukturalnego. Może skutkować „połączeniem się” blisko położonych detali (operacja ekstensywna). Zwiększanie wielkości elementu strukturalnego powoduje wypełnianie coraz większych „dziur” oraz wklęsłości, upodabnianiem powstałych obszarów do elemetu strukturalnego i łączeniem coraz dalej położonych detali. Operacja domknięcia jest także idempotentna (kolejne stosowania nie zmieniają obrazu)

I \bullet B= (I\bullet B)\bullet B = ((I\bullet B)\bullet B)\bullet B = \ldots
Przykład operacji domknięcia zastosowanej na obrazie binarnym


Operacja „Hit-or-Miss”[edytuj | edytuj kod]

Operacja „Hit-or-Miss”, „Hit-and-Miss”, czasem nazywana przekształceniem „trafi-nie trafi”, jest jedną z podstawowych operacji morfologicznych. Jej działanie można opisać jako przykładanie elementu strukturalnego do każdego punktu analizowanego obrazu, przy czym

  • jeżeli otoczenie punktu odpowiada elementowi strukturalnemu, to odpowiadający punkt obrazu wynikowego otrzymuje wartość 1,
  • w przeciwnym wypadku - piksel obrazu wynikowego otrzymuje wartość 0.

Operacja „Hit-or-Miss” jest wykonywana wielokrotnie, aż do uzyskania obrazu niezmieniającego się w kolejnych iteracjach i służy do wykrywania cech na obrazie - przez odpowiednią modyfikację lub zestawienie elementów strukturalnych (wyniki stosowania kilku elementów strukturalnych można sumować lub mnożyć) - np. punktów charakterystycznych.

Ze względu na jego elementarność, przekształcenie „Hit-or-Miss” można stosować do wyprowadzenia wszystkich pozostałych operacji morfologicznych. Na przykład operator erozji można zdefiniować jako operację „Hit-or-Miss” z elementem strukturalnym

\begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}.

Pocienianie[edytuj | edytuj kod]

Pocienianie lub ścienianie (ang. thinning) jest oparte na zastosowaniu operacji „Hit-or-Miss”, a dokładniej odjęciu jej wyniku od obrazu pierwotnego

T_{pocienianie}(I, B)= I - T_{Hit-or-Miss}(I, B).

Operację można interpretować jako przykładanie elementu strukturalnego do każdego piksela obrazu (tak, aby punkt centralny okna pokrywał się z analizowanym pikselem) a następnie

  • brak zmiany wartości punktu, jeżeli element strukturalny nie pasuje do otoczenia piksela,
  • zmianą wartości punktu na 0, w wypadku przeciwnym.

Operację można wykonywać wielokrotnie, aż do chwili, gdy kolejne stosowania nie zmieniają obrazu wynikowego. Najczęściej stosuje się obracanie elementu strukturalnego (o kąt 90^{\circ} w przypadku siatki kwadratowej) pomiędzy kolejnymi przekształceniami.

W zależności od charakterystyki elementu strukturalnego, stosowanie pocieniania daje różne efekty. Podstawowym zastosowaniem operacji jest wykrywanie krawędzi oraz wyznaczanie szkieletu obrazu[3].

Pogrubianie[edytuj | edytuj kod]

Pogrubianie (ang. thickening) jest oparte na dodaniu wyniku przekształcenia „Hit-or-Miss” od obrazu pierwotnego

T_{pogrubianie}(I, B)= I \cup T_{Hit-or-Miss}(I, B).

Operację można interpretować jako przykładanie elementu strukturalnego do każdego piksela obrazu (tak, aby punkt centralny okna pokrywał się z analizowanym pikselem) a następnie

  • brak zmiany wartości punktu, jeżeli element strukturalny nie pasuje do otoczenia piksela,
  • zmianą wartości punktu na 1, w wypadku przeciwnym.

Operację można wykonywać wielokrotnie, aż do chwili, gdy kolejne stosowania nie zmieniają obrazu wynikowego. Najczęściej stosuje się obracanie elementu strukturalnego (o kąt 90^{\circ} w przypadku siatki kwadratowej) pomiędzy kolejnymi przekształceniami.

Transformata odległościowa[edytuj | edytuj kod]

Transformata odległościowa, zwana też funkcją odległości, jest przekształceniem morfologicznym, które dla każdego punktu obrazu o wartości 1 przyporządkowuje (na obrazie wynikowym) wartość równą minimalnej odległości tego punktu od brzegu figury. Pozostałym punktom przyporządkowana zostaje wartość 0.

Można rozważać różne metryki wyrażania odległości między pikselami obrazu, należą do nich np.

Transformata odległościowa jest wykorzystywana m.in. do wyznaczania szkieletu obrazu.

Top hat i Bottom hat[edytuj | edytuj kod]

Transformacje Top hat oraz Bottom hat są zdefiniowane jako[4]

T_{Top-hat}(I,B) = I - (I \circ B), T_{Bottom-hat}(I,B) = (I \bullet B) - I,

jednak ze względu na swoje właściwości stosowane są zazwyczaj do przetwarzania obrazów monochromatycznych w celu wykrycia ekstremów. Dla takich obrazów operacja Top hat pozwala na ujednolicenie ciemnego tła i pozostawienie jasnych obiektów, a Bottom hat - pozostawienie obiektów ciemniejszych od tła. Ich zestawienie można wykorzystać do poprawy kontarstu obrazu

 I + T_{Top-hat}(I,B) - T_{Bottom-hat}(I,B).

Znajdowanie konturu[edytuj | edytuj kod]

Do wyznaczenia konturu obiektów na obrazie binarnym można stosować następujące techniki:

  • operację odejmowania obrazu pierwotnego od wyniku jego dylatacji, dzięki czemu powstaje granica zewnętrzna obrazu
G(I) = (I \oplus B) - I;
  • operację odejmowania erozji obrazu od oryginału, otrzymany wynik jest granicą wewnętrzną obiektu
G(I) = I - (I \ominus B);
  • gradient morfologiczny, czyli różnicę pomiędzy dylatacją a erozją obrazu (gradient określa kontrast pomiędzy sąsiadującymi pikselami)[5]
 Grad(I) \equiv  (I \oplus B)  - (I \ominus B);
\begin{bmatrix} 1 & 1 & 1 \\ 1 & z & 1 \\ 1 & 1 & 1 \end{bmatrix} lub \begin{bmatrix} z & 1 & z \\ 1 & z & 1 \\ z & 1 & z \end{bmatrix}.
Przykład ekstrakcji konturów, od lewej: obraz oryginalny oraz kontury wyznaczone przy użyciu dylatacji, erozji, gradientu oraz pocieniania


Znajdowanie szkieletu[edytuj | edytuj kod]

Szkielet figury, to zbiór wszystkich punktów równoodległych od co najmniej dwóch brzegów. Szkielet odzwierciedla podstawowe własności topologiczne figury, a jego dalsza analiza może zostać wykorzystana do

  • klasyfikacji figur ze względu na kształt,
  • wyznaczania orientacji figur podłużnych,
  • określania linii środkowej szerszych linii,
  • rozdzielanie złączonych obiektów.

Szkieletyzacja jest operacją wyznaczania liniowej reprezentacji (szkieletów) figur na analizowanym obrazie. Można ją wyznaczać na dwa sposoby

  1. stosując operację pocieniania - mówi się wtedy o szkielecie binarnym,
  2. na podstawie transformaty odległościowej - otrzymując tzw. szkielet MAT, (ang. Medial Axis Transform).

Wyznaczanie szkieletu binarnego polega na wielokrotnym stosowaniu (często naprzemiennych, z różnymi elementami strukturalnymi) operacji pocieniania - do momentu, aż kolejne operacje nie wpływają na wygląd obrazu wynikowego. W tym celu można stosować różne zestawy elementów strukturalnych. Przykładem adekwatnego zestawu jest 8 elementów otrzymanych w wyniku obrotów

\begin{bmatrix} 0 & 0 & 0 \\ z & 1 & z \\ 1 & 1 & 1 \end{bmatrix} oraz \begin{bmatrix} z & 0 & 0 \\ 1 & 1 & 0 \\ z & 1 & z \end{bmatrix} o kąty 0^{\circ}, 90^{\circ}, 180^{\circ} i 270^{\circ}.

Innym rodzajem liniowej reprezentacji figury jest szkielet MAT, którego piksele przyjmują wartość proporcjonalną do odległości od krawędzi obiektu. Wyznacza się go na podstawie transformaty odległościowej obrazu, której wynik można przedstawić w postaci płaszczyzny trójwymiarowej - wymiar pionowy odpowiada wartości piksela. Krawędzie otrzymanej płaszczyzny wyznaczają szkielet binarny obrazu, a wartości dla szkieletu MAT odpowiadają wartościom transformaty w miejscu krawędzi.

Przykłady wyznaczania szkieletu figur na obrazie binarnym


Punkty charakterystyczne[edytuj | edytuj kod]

Proste operacje binarne pozwalają na odnalezienie pewnych charakterystycznych punktów obrazu[6]. Należą do nich m.in.:

  • punkty izolowane, czyli takie, które nie posiadają żadnego sąsiada, można je wykryć za pomocą przekształcenia „Hit-or-Miss” z elementem strukturalnym
\begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix},
  • punkty końcowe (ang. endpixels), czyli te, które posiadają dokładnie jednego sąsiada, do ich detekcji można wykorzystać przekształcenie „Hit-or-Miss” z elementem strukturalnym
\begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ z & z & z \end{bmatrix},
  • punkty łączące (ang. linkpixels), czyli te, które posiadają dokładnie dwóch sąsiadów,
  • punkty węzłowe (ang. vertices), czyli te, które posiadają co najmniej trzech sąsiadów, przy wykrywaniu można wykorzystać przekształcenie „Hit-or-Miss” z elementem strukturalnym
\begin{bmatrix} z & 1 & z \\ z & 1 & z \\ 1 & z & 1 \end{bmatrix} lub \begin{bmatrix} 1 & z & z \\ z & 1 & z \\ 1 & z & 1 \end{bmatrix}.

Podsumowanie[edytuj | edytuj kod]

Morfologia matematyczna jest niezwykle skutecznym narzędziem do analizy i przetwarzania obrazów. Umożliwia ona filtrację obrazów, upraszczanie obrazów bez utraty istotnej informacji, analizę kształtów, detekcję różnorodnych struktur w obrazie, ekstrakcję konturów i szkieletów obiektów, detekcję cech charakterystycznych, analizę tekstury, rekonstrukcję obrazów, poprawę parametrów obrazu (np. kontrastu dla obrazów monochromatycznych).

Stosowana przede wszystkim w przetwarzaniu obrazów binarnych, jednak da się rozszerzyć na obrazy w skali szarości (przez rozszerzenie definicji dwóch podstawowych operacji - dylatacji i erozji).

Obszary zastosowań[edytuj | edytuj kod]

Obrazy binarne stosuje się w wielu aplikacjach ze względu na prostotę ich przetwarzania oraz niewielki rozmiar plików przechowujących dane. Oczywiście, implikuje to ograniczenie dostępnej informacji jaką pojedynczy obraz może ze sobą nieść, jednak do prostych zastosowań (jak np. wykrywanie sylwetki - konturu) jest ona w pełni wystarczająca. Z tego powodu, obrazy binarne znajdują zastosowanie w systemach opartych na identyfikacji kształtów (jak np. detekcja produktów na przenośniku taśmowym), przy wykrywaniu orientacji okiektów oraz interpretacji tekstu. Szczególnie ostatni obszar zastosowań jest szeroko eksploatowany. Ze względu na swój niewielki rozmiar (obraz o rozdzielczości 640x480 zajmuje 37.5 kB), obrazy binarne są powszechnie wykorzystywane do archiwizacji oraz transmisji dokumentów przez urządzania faksowe (kompresja plików tego typu pozwala na kilkukrotne a nawet kulkudziesięciokrotne zmniejszenie ich rozmiaru).

Przypisy

  1. W. Burger, M.J. Burge, Principles of Digital Image Processing: Fundamental Techniques, Springer, Londyn 2009, ISBN 978-1-84800-190-9
  2. J. Serra, Image Analysis and Mathematical Morphology, Academic Press, London 1982, ISBN 978-0126372427
  3. S. Marchand-Maillet, Y.M. Sharaiha, Binary Digital Image Processing: A Discrete Approach, Academic Press, London 2000, ISBN 0-12-470505-7
  4. G. Bradski, A. Kaehler, Learning OpenCV: Computer Vision with the OpenCV Library, O’Reilly Media Inc., 2008, ISBN 978-0-596-51613-0
  5. M. Nieniewski, Morfologia matematyczna w przetwarzaniu obrazów, Akademicka Oficyna Wydawnicza PLJ, Warszawa 1998, ISBN 83-7101-404-X
  6. R. Tadeusiewicz, P. Korohoda, Komputerowa analiza i przetwarzanie obrazów, Społeczeństwo Globalnej Informacji, Wyd. Fundacji Postępu Telekomunikacji, Kraków 1997, ISBN 83-86476-15-X

Linki zewnętrzne[edytuj | edytuj kod]