Morfologia matematyczna

Najstarsze zastosowania słowa morfologia odnosi się do języka i biologii. W językoznawstwie morfologia jest badaniem struktury zdań czy słów. W biologii, morfologia dotyczy bardziej bezpośrednio kształtu organizmów, organów czy komórek. Morfologię w biologi można rozumieć jako system klasyfikacji, na podstawie ogólnego kształtu (eliptyczne, okrągłe, itd), rodzaju i stopnia nieprawidłowości (wypukłe, szorstkie lub o gładkim zarysie, itp), struktur wewnętrznych (znajdują się otwory, liniowe lub zakrzywione).

Morfologia oznacza kształt i strukturę obiektu. Można też to pojęcie rozumieć jako określanie wzajemnego powiązanie pomiędzy częściami danego obiektu. Morfologia matematyczna związana jest z cyfrowym sposobem opisu analizowanych kształtów.

Morfologia matematyczna jest pojęciem odnoszącym się do przetwarzania obrazu w oparciu o zestaw operacji (zazwyczaj nieliniowych) działających na kształtach. Obrazy binarne zwierające tylko 0 i 1 (odpowiadające odpowiednio kolorowi białemu i czarnemu), mogą być traktowane jako elementy logiczne TRUE i FALSE. 

Operacje morfologiczne wykorzystują element strukturalny (element nadający strukturę), czyli otoczenie / maskę zawierającą zera i jedynki, rozumiane jako argumenty logiczne TRUE i FALSE

Operacje morfologiczne wykonują testy logiczne (w każdej możliwej pozycji na obrazie) między elementem strukturalnym i odpowiednią częścią obrazu. Wynik jest zapamiętywany na oddzielnym obrazie. Schemat działania morfologi matematycznej przedstawia poniższy rysunek. Element strukturalny dopasowywany (przykładany) jest w każdym punkcie obrazu. W wyniku operacji logicznej między odpowiednimi wartościami elementu strukturalnego, a bitami na obrazku powstaje nowy element, który zapisujemy na wynikowym obrazie.

Ilustracja. Schemat działania morfologi matematycznej.

Aby dobrze zrozumieć operacje morfologiczne musimy sobie wprowadzić kilka oznaczeń i podać ich intuicję. 

Po pierwsze możemy myśleć o binarnym obrazie ($I(i,j)$) jako o zbiorze współrzędnych pikseli należących do obiektu (białych pikseli):

\[ Q_{I} = \{ (i,j) \colon I(i,j) = 1 \} \].

Element strukturalny możemy rozumieć analogicznie (czyli jako zbiór współrzędnych tych pikseli, które odpowiadają wartości 1).

Dla punktu $x,y$ z obrazu $Q_{I}$ oraz elementu strukturalnego $E$ (rozumianego jako $Q_{E} = \{ (i,j) \colon E(i,j) = 1 \}$) przesunięcie punktów (zawartych w masce) definiujemy jako:

\[ E_{(x,y)} = \{ (i,j) + (x,y) \colon (i,j) \in Q_{E}  \} \]

Wyniki filtrów morfologicznych będziemy prezentować na obrazku ship.jpg. Do filtrów działających na obrazach binarnych użyjemy obrazu uzyskanego w wyniku algorytmu Otsu.

  

Ilustracja. Obraz w odcieniach szarości oraz jego binarna wersja uzyskana za pomocą algorytmu Otsu.

Dylacja

Dylacja jest techniką zwiększenia / rozszerzania obiektów, zwykle we wszystkich kierunkach jednocześnie.

Obiektem nazywamy białe elementy obrazu i oznaczamy je przez 1. Natomiast tłem są elementy czarne i oznaczamy je przez 0.

Dylację można uzyskać na kilka sposobów. W klasycznej formie element strukturalny jest przykładany w każdym punkcie należącym do zbioru i wykonywana jest operacja sumy binarnej (1+0=0+1=1, 1+1=1,0+0=0). W konsekwencji dylację obrazu binarnego $I$ z elementem strukturalnym $E$ możemy zapisać jako:

\[ I \oplus E = \{ (x,y) + (i,j) \colon (i,j) \in Q_{I}, (x,y) \in Q_{E}  \} \].

Powstały obraz jest rozumiany jako zbiór pikseli, które teraz należą do zbioru / obiektu (białe piksele).

Alternatywnie dylację można zdefiniować jako:

\[ I \oplus E = \bigcup_{(x,y) \in Q_{I}}  E_{(x,y)}  \].

W dylacji można użyć różnych elementów strukturalnych. Najprostszy z nich to kwadratowy element strukturalny, czyli macierz wypełniona 1. Na przykład element strukturalny o wymiarze $5 \times 5$

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

Prześledźmy sobie dylację (z kwadratowym elementem strukturalnym) w bardzo dużym przybliżeniu:

Ilustracja. Wynik dylacji z kwadratowym elementem strukturalnym $3 \times 3$.

Dylatację, w analogiczny sposób, można traktować jako przyłożenie / dopasowanie maski w każdym punkcie obrazu i zmianę piksela (odpowiadającego środkowi maski) na biały, jeżeli maska posiada niepuste przecięcie ze zbiorem.   

Program wykonujący dylację z kwadratowym elementem strukturalnym OpenCV (C++).

   

  

Oczywiście, jako element strukturalny możemy wziąć bardziej skomplikowany kształt (macierzy), Jedną z możliwości jest maska w kształcie krzyża.

\[ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1  \\ 0 & 0 & 1 & 0 & 0  \\ 0 & 0 & 1 & 0 & 0 \end{bmatrix} \].

Program wykonujący dylację z krzyżowym elementem strukturalnym OpenCV (C++).

  

  

Jednak najbardziej popularnym elementem strukturalnym jest element kołowy.

\[ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{bmatrix} \].

Program wykonujący dylację z kołowym elementem strukturalnym OpenCV (C++).

  

  

Używając maski prostokątnej możemy użyć eliptycznych elementów strukturalnych.

\[ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{bmatrix} \].

  

  

Program wykonujący dylację z eliptycznym elementem strukturalnym OpenCV (C++).

Porównanie wyników dylacji z różnymi maskami oraz elementami strukturalnymi można uzyskać za pomocą OpenCV (C++)

Można też sobie zdefiniować własny element strukturalny OpenCV (C++).

Erozja

Erozja jest techniką pomniejszania obiektów poprzez usunięcie pikseli granicznych. Tą operację można rozumieć jako odwrócenie operacji dylacji.

\[ I \ominus E = \{ (x,y) \colon \left( (x,y) + (i,j) \right) \in Q_{I} \mbox{, dla wszystkich} (i,j) \in Q_{E}  \} \].

Alternatywnie erozję można zdefiniować jako:

\[ I \ominus E = \{ (i,j) \colon  E_{(i,j)} \subset Q_{I} \} \].

Ilustracja. Wynik erozji z kwadratowym elementem strukturalnym $3 \times 3$.

Analogicznie jak przy dylacji w erozji możemy użyć różnych elementów strukturalnych. Zacznijmy od kwadratowego.

  

  

 

Program wykonujący erozję z kwadratowym elementem strukturalnym OpenCV (C++).

Możemy również wykonać erozję z krzyżowym elementem strukturalnym:

  

  

Program wykonujący erozję z krzyżowym elementem strukturalnym OpenCV (C++).

Również w erozji najpopularniejszą maską jest kołowy element strukturalny.

  

  

Program wykonujący erozję z krzyżowym elementem strukturalnym OpenCV (C++).

Porównanie wyników erozji z różnymi maskami oraz elementami strukturalnymi można uzyskać za pomocą OpenCV (C++).

Intuicja klasycznej Dylacji i Erozji

Intuicyjnie dylację z okrągłym elementem strukturalnym możemy rozumieć jako operację powiększania / rozszerzania zbioru opartą na toczeniu kuli po brzegu zbioru i dodawaniu elementów, które mają niepuste przecięcie z toczącym się kołem.

Natomiast operację erozji możemy rozumieć jako toczenie okrągłego elementu strukturalnego po brzegu oraz zjadaniu / usuwaniu elementów, które należą do toczącego się koła.

 

W przypadku bardziej skomplikowanych elementów strukturalnych ta intuicja jest troszkę trudna do uogólnienia. Prześledzimy sobie jeszcze dwa przykłady.

 

Operacja Otwarcia i Zamknięcia

Erozja jest operacją dualną / odwrotną do dylacji i na odwrót. Pierwsza z nich zmniejsza zbiór, natomiast druga go powiększa / rozszerza. Łącząc te dwie operacje otrzymać można bardzo ciekawe efekty. 

Operacja otwarcia polega na wykonaniu erozji, a następnie dylacji z tym samym elementem strukturalnym $E$:

\[ I \circ E = ( I \ominus E ) \oplus E \]

Operacja otwarcia usuwa szumy (eliminuje elementy mniejsze niż element strukturalny), wypustki i wąskie połączenia między większymi grupami punktów. Ponadto wygładza brzegi zbioru.

Operacja zamknięcia polega na wykonaniu dylacji, a następnie erozji z tym samym elementem strukturalnym $E$ 

\[ I \cdot E = ( I \oplus E ) \ominus E \]

Operacja zamknięcia łączy obszary, które są blisko siebie oraz wypełnia dziury / otwory w danych. Często w wyniku tej operacji kształt obiektu zostaje istotnie zmieniony.

    \

(a)                                                      (b)                                                     (c)

Ilustracja. Wynik operacji zamknięcia i otwarcia z kwadratowym elementem strukturalnym $3 \times 3$
a) Oryginalny obraz b) Otwarcie c) Zamknięcie

Powyższe wyniki można uzyskać za pomocą kodów: Otwarcie - OpenCV (C++), Zamknięcie - OpenCV (C++)

Porównanie powyższych operacji z wykorzystaniem różnych typów elementów strukturalnych można otrzymać za pomocą: Otwarcie - OpenCV (C++), Zamknięcie - OpenCV (C++).

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” 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 zcienianie lub otoczka wypukła. 

Operację „Hit-or-Miss” można zapisać za pomocą operacji erozji i dylacji dla dwóch okien $E_1$ oraz $E_2$. Tak naprawdę możemy tą operację rozumieć jako szukanie otoczeń punktów, które pasują do kształtu elementu strukturalnego $E_1$, a nie pasują do elementu strukturalnego $E_2$. 

Operacja „Hit-or-Miss” dla obrazu $I$ względem elementów strukturalnych  $E_1$, $E_2$ lub inaczej pary $E = (E_1,E_2)$ jest zdefiniowana jako:

\[ I \circledast (E_1,E_2) = (I \ominus E_1 ) \cup ( \bar I \oplus E_2 ) \]

gdzie $\bar I $ oznacza dopełnienie zbioru.

Powyższa operacja oznacza, że wykonujemy dwie operacje: erozję obrazu $I$ przez jądra $E_1$ i erozję dopełnienie $\bar I$ przez $E_2$.

Należy zauważyć, że można połączyć $E_1$ i $E_2$ do pojedynczego elementu strukturalnego, który zawiera trzy rodzaje znaczników:

  •  1  - elementy odpowiadające z elementu strukturalnego $E_1$. Gdy porównujemy element strukturalny z obrazem to dopasowanie zachodzi, gdy na odpowiednich współrzędnych na obrazie mam oraz w elemencie strukturalnym 1
  • -1  - elementy odpowiadające z elementu strukturalnego $E_2$. Gdy porównujemy element strukturalny z obrazem to dopasowanie zachodzi, gdy na odpowiednich współrzędnych na obrazie mam oraz w elemencie strukturalnym 0
  • 0   - elementy ignorowane. Dopasowanie zachodzi zawsze.

Dzięki takiemu opisowi można sprawdzać dopasowanie elementu strukturalnego w każdym punkcie.

a)                              b)                            c)

Ilustracja. (a) element strukturalny, do którego chcemy się dopasować ("hit")
(b) element strukturalny, do którego nie chcemy się dopasować "miss"
(c) kombinacja (a) i (b), gdzie 1 to obiekt (biały kolor), -1 to tło (czarny kolor), 0 - piksel obojętny 

Za pomocą operacji „Hit-or-Miss” można dokonać wielu mniej lub bardziej skomplikowanych operacji. Zacznijmy od jednej z najprostszych. Możemy np. znaleźć rogi figur.

Rogi można wyszukać za pomocą poniższych elementów strukturalnych:

\[ \begin{bmatrix} 0 & 1 & 0 \\ -1 & 1 & 1 \\ -1 & -1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & -1 \\ 0 & -1 & -1 \end{bmatrix} \begin{bmatrix} 0 & -1 & -1 \\ 1 & 1 & -1 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} -1 & -1 & 0 \\ -1 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix} \]

Każda z masek odpowiada za znalezienie jednego konkretnego typu narożnika. Dlatego, też używamy każdej z masek na całym obrazie i wyświetlamy sumę.

Dla przykładu zostanie użyty kwadrat template1.png.

  

Ilustracja. Oryginalny obraz oraz rogi znaleziona za pomocą operacji morfologicznej  „Hit-or-Miss”.

Powyższy wynik można uzyskać za pomocą kodu w OpenCV (C++)

Operacja ścieniania 

Operację ścieniania można wykonać za pomocą morfologi matematycznej. Jest to metoda znajdowania szkieletu. Częściej jednak w tym celu używa się transformat odległościowych, do których jeszcze wrócimy.

Jak przy wszystkich operacjach morfologicznych potrzebować będziemy elementów strukturalnych. Zanim je przedstawimy, to podamy ogólną zasadę. W operacji ścieniania wykorzystana zostanie metoda „Hit-or-Miss”. 

Ścienianie można wyrazić jako:

\[ thin(I,E) = I - hitOrMis(I,E) \]

gdzie operację odejmowania rozumiemy jako operację logiczną $ A - B = Z \cup Not \ Y $.

Przy operacji ścieniania potrzebne nam będą dwa elementy strukturalne:

\[ \begin{bmatrix} -1 & -1 & -1 \\ 0 & 1 & 0 \\  1 & 1 & 1 \end{bmatrix} \begin{bmatrix} 0 & -1 & -1 \\ 1 & 1 & -1 \\ 0 & 1 & 0 \end{bmatrix} \]

Każdy z powyższych elementów strukturalnych użyjemy cztery razy obracając je odpowiednio o $0^o$, $90^o$, $180^o$, $270^o$. 

Procedura ścieniania:

  • stwórz 8 elementów strukturalnych przez użycie odpowiednich obrotów,
  • od oryginalnego obrazu odejmij (zgodnie z definicją powyżej) wynik operacji „Hit-or-Miss”,
  • aby uniknąć jednoczesnego usunięcia 2 ostatnich pikseli przez 2 różne elementy strukturalne, każdy z 8 elementów strukturalnych jest stosowany w oddzielnym przejściu przez wszystkie piksele obrazu,
  • w pierwszej kolejności wykonujemy operację  „Hit-or-Miss” dla podstawowych elementów strukturalnych (z zerowym obrotem), a następnie kolejno pozostałe 3 pary,
  • po osiągnięciu zbieżności kolejne iteracje nie zmieniają wyniku (procedura zatrzymuje się sama).

Wynik algorytmu zaprezentujemy na przykładzie obrazów cross.png.

  

Ilustracja. Wynik ścieniania za pomocą metody „Hit-or-Miss”.

Powyższy obrazek można uzyskać za pomocą następującego kodu w OpenCV (C++)

Operacja pogrubiania (otoczka wypukła)

Operację pogrubiania można wykonać za pomocą morfologi matematycznej. Jak przy wszystkich operacjach morfologicznych potrzebować będziemy elementów strukturalnych. Podobnie jak w przypadku ścieniania zostaną użyte dwa elementy strukturalne oraz ich obroty  o $0^o$, $90^o$, $180^o$, $270^o$. 

Pogrubianie można wyrazić jako:

\[ thicken(I,E) = I \cup hitOrMis(I,E).\]

Przy operacji pogrubienia potrzebne nam będą dwa elementy strukturalne:

\[ \begin{bmatrix} 1 & 1 & 0 \\ 1 & -1 & 0 \\  1 & 0 & -1 \end{bmatrix} \begin{bmatrix} 0 & 1 & 1 \\ 0 & -1 & 1 \\ -1 & 0 & 1 \end{bmatrix} \]

Procedura pogrubiania:

  • stwórz 8 elementów strukturalnych przez użycie odpowiednich obrotów,
  • do oryginalnego obrazu dodaj (zgodnie z definicją powyżej) wynik operacji „Hit-or-Miss”,
  • w pierwszej kolejności wykonujemy operację  „Hit-or-Miss” dla podstawowych elementów strukturalnych (z zerowym obrotem), a następnie kolejno pozostałe 3 pary,
  • po osiągnięciu zbieżności kolejne iteracje nie zmieniają wyniku (procedura zatrzymuje się sama).

  

Ilustracja. Wynik pogrubiania za pomocą metody „Hit-or-Miss”.

Powyższy obrazek można uzyskać za pomocą następującego kodu w OpenCV (C++)

Pruning

Operację pruningu - usunięcia drobnych wypustek / gałązek można wykonać za pomocą morfologi matematycznej. Oczywiście musimy użyć innych elementów strukturalnych.

\[ \begin{bmatrix} -1 & 0 & 0 \\ -1 & 1 & -1 \\  -1 & -1 & -1 \end{bmatrix} \begin{bmatrix} 0 & 0 & -1 \\ -1 & 1 & -1 \\ -1 & -1 & -1 \end{bmatrix} \]

W odróżnieniu od ścieniania i pogrubiania operacja pruningu w przypadku samych linii bez zamkniętych krawędzi prowadzi do całkowitego usunięcia linii. Dlatego też należy ustawić warunek stopu.

        

Ilustracja. Wynik pruningu w kolejnych iteracjach.

 

Erozja i Dylacja na obrazach kolorowych

Operacje morfologiczne można stosować do obrazów w skali szarości oraz obrazów kolorowych. W takim przypadku operacje logiczne zostają zamienione na operacje na liczbach:

  1. AND przechodzi w $min$
  2. OR przechodzi w $max$