Doskonalenie odbioru informacji multimedialnych
2. Komputerowa obróbka danych
2.10. Segmentacja
Segmentacja to wydzielenie z obrazu obszarów (inaczej regionów spójnych, czyli będących \emph{w jednym kawałku}), charakteryzujących się:
- jednorodnością względem określonej właściwości danych (atrybutu), przy czym kryterium jednorodności może dotyczyć zarówno wewnętrznych cech obiektu (np. kolor czerwony w sensie zdefiniowanego deskryptora koloru), jak też mierzalnych granic obszarów (konturów) -- w takim rozumieniu rozgranicza obszary wyraźna krawędź nawet jeśli poza obszarem granicznym wydzielone regiony są jednorodne;
- czytelnym znaczeniem (funkcją semantyczną), wynikającym ze specyfiki zastosowań; ustalenie znaczenia segmentowanych obszarów może się odbywać na drodze interaktywnej, może też być realizowane metodami rozpoznawania obiektów, bazującymi na sformalizowanej wiedzy dziedzinowej.
Zwykle algorytmy segmentacji bazują na określonym kryterium jednorodności, dyktowanym aplikacją, a są weryfikowane według kryterium semantycznego. Niekiedy jednak stosuje się porządek odwrotny -- inicjacja dotyczy wskazania ogólnych zarysów użytecznych dla użytkownika regionów, a następnie procedura wykorzystująca ustalone kryterium jednorodności dookreśla słabo dostrzegalne granice obiektów. Na etapie optymalizacji poszukiwane są skuteczne tzw. deskryptory semantyczne, czyli numeryczne wskaźniki znaczenia poszczególnych fragmentów obrazu, pozwalające łączyć grupy pikseli w wiarygodne regiony o ustalonym znaczeniu.
Celem segmentacji jest uproszczenie analizy danych obrazowych poprzez zmniejszenie stopnia złożoności obrazu. Obraz zastępowany jest opisem symbolicznym z wydzielonymi obszarami -- segmentami, które mogą mieć pożądane cechy, np. spójność, zwartość, odpowiedni rozmiar czy kształt, pokrycie określonym wzorcem tekstury. Wydzielone segmenty otrzymują zwykle identyfikator - etykietę.
Segmentacja stanowi bardzo ważne ogniwo w analizie treści obrazów. Umożliwia wstępny opis czy uproszczenie sceny, określenie obszaru zainteresowań w dalszej analizie, wyznaczenie potencjalnych obiektów zainteresowania, rozpoznawanych w dalszej kolejności jako obiekty określonej klasy czy też anormalności.
Bardziej formalnie, segmentacją obrazów nazywany jest proces podziału całego obrazu na skończony zbiór regionów -- obiektów zainteresowania oraz nieistotnego znaczeniowo tła , przy czym podział ten odznacza się następującymi właściwościami:
gdzie jest binarnym operatorem ustalającym jednorodność i czytelne znaczenie regionu według przyjętych kryteriów ( jest jednorodne i sensowne). O ile weryfikacja jednorodności obszaru bazuje najczęściej na kryterium obliczeniowym dotyczącym istotnych cech obszaru, to określenie semantycznej jego funkcji sprowadza się zazwyczaj do identyfikacji obszaru jako określonego rodzaju obiektu rozpoznawanego przez użytkownika, co wymaga odwołania się do specyficznej wiedzy dziedzinowej, algorytmów rozpoznania klasy obiektu lub też obliczenia podobieństwa w stosunku do referencyjnych wzorców.
Segmentacja wstępna jest pierwszym, bardzo istotnym etapem analizy obrazów. Wydzielone wstępnie obszary służą w typowym schemacie ekstrakcji potencjalnych obiektów (etap reprezentacji obiektów), opisywanych następnie za pomocą zestawu cech (etap pomiaru - obliczania cech obiektów). Klasyfikacja obiektów (czyli etap kolejny) może mieć zwykle dwojaki charakter:
- weryfikacji wydzielonych regionów jako obiektów przekazu informacji w obrazie, poprzez ustalenie znaczenia (semantyki) obszarów, a w konsekwencji zaliczenie ich do kategorii regionów (jeśli ) bądź tła ();
- wstępnego rozpoznania obszarów jako obiektów o istotnym znaczeniu w celu adaptacyjnej korekty wcześniejszych etapów poczynając od segmentacji wstępnej; ta procedury służy bardziej wiarygodnemu wyznaczeniu obiektów z obrazu w celu doskonalenia efektów analizy obrazów;
- rozpoznania obiektów jako należących do określonej klasy semantycznej.
Duża różnorodność stosowanych metod segmentacji sprawia, że można je klasyfikować na wiele sposobów. Cel segmentacji zależy często od rodzaju analizowanych danych, rodzaju wyrażonej treści, oczekiwań obserwatora oraz innych uwarunkowań aplikacji (ograniczenia czasowe, dokładność wyznaczenia granic obiektów itp.). Różne zastosowania prowadzą do zróżnicowanych algorytmów tej samej koncepcji segmentacji.
Podstawowy podział rozwiązań możliwych w zakresie segmentacji obejmuje:
- metody obszarowe, znajdujące regiony według obliczeniowego kryterium jednorodności,
- metody krawędziowe, bazujące na wykrywaniu krawędzi i aproksymacji konturów rozdzielających regiony o odmiennych właściwościach,
- metody probabilistyczne, gdzie wykorzystywany jest określony model lokalnych zależności danych, statystyczne właściwości globalne, szacowanie rozkładów łańcuchów i pól losowych opisujących poszczególne regiony itp., w tym przede wszystkim:
- progowanie (thresholding) - wykorzystuje prostą operację porównywania wartości jasności pikseli obrazu z ustalonym progiem; podziału metod progowania dokonuje się w zależności od sposobu wyznaczania progu:
- globalne, z progiem obliczonym na podstawie globalnych parametrów obrazu - takich jak histogram,
- lokalne, gdzie próg ustalany jest na podstawie parametrów lokalnych obrazu w określonym kontekście,
- adaptacyjne, z modyfikacją progu zależną od efektów progowania w obszarach poprzednich.
- metoda mieszania regionów,
- metody rozmyte, wykorzystujące elementy logiki rozmytej,
- progowanie (thresholding) - wykorzystuje prostą operację porównywania wartości jasności pikseli obrazu z ustalonym progiem; podziału metod progowania dokonuje się w zależności od sposobu wyznaczania progu:
- metody rozpoznania, weryfikujące wydzielane obszary jako obiekty czytelnej klasy znaczeniowej na odpowiednim poziomie abstrakcji opisu obrazu, z zastosowaniem klasyfikatorów uczących się oraz mechanizmów doboru/selekcji cech;
- metody hybrydowe, łączące np. krawędziowe, obszarowe z opisem probabilistycznym jak niektóre wersje metod aktywnych kształtów, konturów czy poziomic.
Wśród obszarowych technik segmentacji (region based) można wyszczególnić następujące metody:
- grupowanie, inaczej klasteryzację (clustering methods), polegające na klasyfikacji obszarów na podstawie określonych parametrów charakteryzujących dane obszary; najbardziej powszechnymi algorytmami grupowania są:
- metoda K średnich (K-means),
- metoda rozmyta C średnich (fuzzy C-means),
- hierarchiczne grupowanie (hierarchical clustering),
- mieszanina rozkładów Gaussa.
- rozrost regionów (region growing), bazujący na założeniu, że piksele należące do wspólnego regionu mają podobne, w sensie ustalonego kryterium, właściwości; najbardziej popularne metody rozrostu to:
- łączenie (merging) - polega na dołączaniu pikseli do punktów (miniregionów) początkowych o spójnym charakterze,
- dzielenie (splitting) - zaczynając od zgrubnego podziału wstępnego, dokonuje się kolejnych podziałów dużych regionów, az do momentu, kiedy regiony tworzone przez grupy pikseli osiągną zadowalający poziom ujednolicenia,
- łączenie i dzielenie - łączy opisane wyżej algorytmy,
- hill climbing - wykorzystuje fakt występowania w obrazie lokalnych maksimów intensywności; maksima odpowiadają ziarnom metody rozrostu.
- segmentacja wododziałowa - jasność pikseli w obrazie jest traktowana jako pewne odchylenie od poziomu odniesienia, jako wzniesienie ponad pewien podstawowy poziom; takie podejście pozwala traktować obraz jak powierzchnię topograficzną - obszary ciemne stanowią zagłębienia "terenu", podczas gdy obszary jasne odpowiadają wzniesieniom.
Techniki wykrywające krawędzie (edge based) można usystematyzować w następujący sposób:
- bazujące na pochodnych pierwszego rzędu funkcji obrazu -- w obrazie wyszukuje się lokalne maksima oraz minima pierwszej pochodnej funkcji obrazu; gradient wskazuje kierunek największej zmiany wartości funkcji obrazu , amplituda tego wektora określa szybkość zachodzącej zmiany;
- bazujące na pochodnych drugiego rzędu funkcji obrazu -- wykrywane są przejścia przez zero drugiej pochodnej funkcji obrazu; stosowane jest dyskretny operator Laplace'a będący sumą drugich pochodnych funkcji obrazu , poprzedzone często wygładzeniem obrazu za pomocą filtru gaussowskiego -- zestawienie tych dwóch operacji nosi nazwę LoG (Laplacian of Gaussian);
- aktywnych konturów oraz aktywnych kształtów, bazujące na wzorcach obiektów zainteresowania wpasowywanych w realia danego obrazu metodami lokalnych gradientów czy też na podstawie dokładniejszej analizy kształtu profili krawędzi występujących w najbliższym otoczeniu;
- przeszukiwania grafów -- w tej technice obraz rozpatrujemy jako graf, którego wierzchołkami są pojedyncze piksele, natomiast krawędzie grafu stanowią potencjalne krawędzie obrazu; używając gradientu lub innej operacji wykrywającej krawędzie, można obliczyć koszt połączeń wewnątrz grafu; krawędź wyznacza się odnajdując w grafie połączenia o niskiej wartości kosztu.