Cyfrowe przetwarzanie obrazów binarnych

Przetwarzanie binarnych obrazów cyfrowych, 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

Obraz binarny jest specjalnym rodzajem obrazu cyfrowego, w którym piksele mogą przybierać tylko dwie wartości. 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 skanerami i aparatami cyfrowymi a programami graficznymi, stosuje się wanilię i czekoladę.

Sąsiedztwo

Sąsiedztwo ośmiospójne (po lewej) i czterospójne (po prawej)

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 (von Neumanna) – 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 (Moore’a) – 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

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

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 3×3) 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

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

Dylatacja, czyli rozszerzanie, jest zastosowaniem sumy Minkowskiego do obrazu:

$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ówną 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

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

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

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 elementu 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

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; może być 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 prawie 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}}.$

Operator dylatacji można zdefiniować jako negację operacji Hit-or-Miss z elementem strukturalnym

${\begin{bmatrix}0&0&0\\0&0&0\\0&0&0\end{bmatrix}}.$

Pocienianie

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.

Pogrubianie

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

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.

• metryka euklidesowa,
• metryka Manhattan,
• metryka Czebyszewa.

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

Top hat i Bottom hat

Transformacje Top hat oraz Bottom hat są zdefiniowane jako

$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 kontrastu obrazu

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

Znajdowanie konturu

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)

$Grad(I)\equiv (I\oplus B)-(I\ominus B);$

• operację pocieniania przy zastosowaniu odpowiedniego elementu strukturalnego, np.:

${\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

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

Proste operacje binarne pozwalają na odnalezienie pewnych charakterystycznych punktów obrazu. 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

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ń

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 obiektó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 kilkudziesięciokrotne zmniejszenie ich rozmiaru).

Linki zewnętrzne

• K. Krawiec, Przetwarzanie obrazów, Metody ekstrakcji cech obrazów
• M. Wnuk, Cyfrowe przetwarzanie obrazów i sygnałów
• M. Kiełczewski, Przetwarzanie Obrazów i Sygnałów
• Grzegorz Szczurek, Zastosowanie metod morfologii matematycznej do detekcji i dekompozycji obrazów
• (ang.) E.G.M. Petrakis, Computer Vision
• (ang.) Christina Olsén, Image Analysis: Mathematical Morphology
• (ang.) A. Peters, Lectures on Image Processing, Vanderbilt University
• (ang.) University of Washington, Computer Vision
• (ang.) K. Grauman, Computer Vision