SLIC-zne superpiksele

W rozpoznawaniu obrazów często mamy do czynienia segmentacją. Przeprowadzamy ją gdy chcemy zmienić reprezentację obrazu na łatwiejszą do analizy - zamiast obrazu w postaci pikseli otrzymujemy regiony, które są w jakiś sposób jednorodne, np. pod względem koloru, odcieni szarości czy tekstury. Te wydzielone obszary nazywamy również superpikselami. Jest ich zazwyczaj o wiele mniej od normalnych pikseli, dlatego algorytmy przetwarzające dalej dany obraz mają bardziej ogólne informacje o obrazie i są szybsze. Jednym z lepszych a zarazem łatwych algorytmów segmentacji jest metoda SLIC.

W poprzednim wpisie dotyczącym metodyki rozpoznawania obrazów w projekcie Flover segmentacja jest pierwszym etapem całego procesu przetwarzania obrazu. Wymieniłem parę metod, które bezpośrednio oddzielają tło od obiektu zainteresowania. Jednak wszystkie z nich wymagają ręcznej inicjalizacji - np. wskazania obszaru gdzie znajduje się obiekt. Poza tym, te lepsze z nich, np. GrabCut są dość skomplikowane i wymagałyby czasochłonnej implementacji w moim projekcie. W miarę postępu prac niestety zauważam, że dużo więcej przykładów algorytmów przetwarzania obrazów jest napisane w C++ lub Pythonie, ale można było się tego spodziewać. Z drugiej strony, jeśli zaimplementuję coś sam w C# może uda mi się kontrybuować do biblioteki Accord.net, której używam. A może będzie to właśnie opisana poniżej metoda SLIC? Szukając innych rozwiązań oddzielających tło od obiektu spodobało mi się podejście opisane tutaj, gdzie celem całej pracy jest również rozpoznawanie kwiatów. Autorzy tworzą klasyfikator, który przydziela poszczególnym pikselom prawdopodobieństwo przynależności do tła oraz do obiektu. Wykonując taką czynność dla wszystkich pikseli, byłoby to powolne oraz obarczone dużym szumem. Wykonują zatem segmentację aby uzyskać superpiksele. Potem klasyfikator na podstawie bazy danych innych kwiatów przypisuje superpiksele do tła albo obiektu w zależności od jego koloru, kształtu, pozycji i powierzchni.

Superpiksele

Każdy algorytm segmentacji może być oparty na klasteryzacji albo na grafach. Algorytmy wykorzystujące klasteryzację takie jak Mean-Shift, Quick-Shift czy SLIC wywodzą się z idei aby przedstawić piksel za pomocą 5 składowych: 3 składowych koloru (np. RGB) oraz 2 współrzędnych pozycji piksela. Następnie na takim 5-wymiarowym zbiorze elementów jest wykonywana klasteryzacja czyli inaczej grupowanie. Z kolei metody korzystające z grafów tj. Min-Cut czy Normalized-Cut interpretują piksele jako wierzchołki grafów, które są połączone każdy z każdym. Waga połączenia pomiędzy dwoma wierzchołkami reprezentuje podobieństwo danych pikseli. Połączenia pomiędzy niektórymi wierzchołkami są w kolejnych iteracjach odpowiednio kasowane do momentu aż uformują się wyraźne grupy grafów reprezentujące segmenty czyli superpiksele. Poniżej porównanie niektórych metod tworzących superpiksele.

SLIC Superpixel_methods
Źródło: http://ivrl.epfl.ch/research/superpixels

SLIC

Algorytm SLIC (Simple Linear Iterative Clustering) został opracowany w laboratorium Image and Visual Representation Group (IVRG) na szwajcarskiej uczelni EPFL. Dzięki swojej prostocie i małym wymaganiom obliczeniowym szybko zdobył popularność. Opiera się na bardzo znanej metodzie klasteryzacji k-means (k-średnich) wykonywanej w 5-wymiarowej przestrzeni. Przypomnijmy że każdy element, który chcemy zgrupować składa się z 3 składowych koloru oraz 2 współrzędnych. Mimo, że zazwyczaj wszystkie składowe są znormalizowane do przedziału 0-1, należy określić ich wagi. Różnią się one zwłaszcza pomiędzy składowymi koloru a współrzędnymi. Innymi słowy, musimy powiedzieć algorytmowi czy bardziej zależy nam, aby superpiksele były jednorodne kolorystycznie czy bardziej skupione w jednym miejscu na płaszczyźnie XY. Współczynnik proporcji pomiędzy wagą dla współrzędnych a wagą dla koloru oznaczyłem jako m - w kodzie spatialConsistency. Algorytm początkowo umieszcza centra segmentów w równomiernych od siebie odstępach. Potem cyklicznie wykonuje proces: przypisanie pikseli do najbliższych centrów w zdefiniowanym bliskim regionie, aktualizacja centrów poprzez wyliczenie "środka ciężkości" danego klastra. Sama metoda k-means jest bardzo przystępnie wytłumaczona np. tutaj.

Algorytm k-means dla przykładowego zbioru punktów w przestrzeni XY:
SLIC k_means
źródło https://en.wikipedia.org/wiki/K-means_clustering

Implementacja

Poniżej zamieszczam pseudo-kod prosto od autorów metody a następnie mój kod wykorzystujący metodę k-means dostępną w bibliotece Accord.MachineLearning. W algorytmie SLIC zaleca się, aby obraz był przedstawiony w przestrzeni kolorów LAB zamiast RGB, dlatego musiałem dopisać swoje konwertery "obraz<->wektor pikseli". Całość kodu znajduje się na GitHubie. Można go wykorzystać bez modyfikacji Accord.net, ale nie będzie to w pełni zgodne z definicją algorytmu podaną w tym artykule i w niektórych przypadkach może on działać niepoprawnie. Główne modyfikacje po stronie biblioteki będą dotyczyć: równomiernego początkowego rozmieszczenia centrów segmentów, początkowego ustawienia centrów w miejscu najmniejszego gradientu oraz szukania nowych miejsc centrów tylko w ograniczonej przestrzeni. Moim następnym zadaniem będzie właśnie eleganckie naniesienie tych zmian w bibliotece Accord.net.

SLIC algorytm

Testy

Wybrałem jedno zdjęcie do testów. Jest to oczywiście jeden z moich przykładowych kwiatków 🙂 Wykonałem segmentację dla odpowiednio 50, 100 i 200 klastrów (superpikseli). Współczynnik m określa proporcję pomiędzy jednorodnością kolorów a umiejscowieniem. Im jest większy tym superpiksele są bardziej skupione (mniej poszarpane). Wydaje mi się, że do dalszego przetwarzania dobrym punktem wyjścia byłby obraz z 200 superpikselami i współczynnikiem m=5. Segmenty mają tu wciąż wyraźne krawędzie ale są również dobrze skupione w jednym miejscu.

Oryginalny obraz

SLIC superpiksele

SLIC_comparison_3

Źródło obrazka tytułowego: http://ivrl.epfl.ch/research/superpixels

Related Posts

Share Facebooktwitterreddit

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *