1 Geometria obrazu Wykład 4Segmentacja Grafy sąsiedztwa. Grafy definiowane przez różne obszary. Minimalne drzewo rozpinające. Metody obszarowe. Drzewa czwórkowe. Metody krawędziowe. Metody punktowe.

2 Grafy sąsiedztwa. Definicja. Grafem sąsiedztwa dla zbioru n punktów P w przestrzeni metrycznej nazywamy graf o wierzchołkach w P, do którego krawędź pq należy wtedy i tylko wtedy, gdy spełnione są pewne geometryczne warunki. Definicja k-najbliższym grafem sąsiedztwa jest graf, w którym krawędź pq istnieje, gdy odległość między p i q należy do k najmniejszych odległości z p do innych wierzchołków z P.

3 Grafy definiowane przez różne obszary.grafy planarne grafy bez trójkątów grafy bez czworokątów grafy acykliczne

4 Definicja. Minimalne drzewo rozpinające MST(G) grafu G = (V, E), którego każda krawędź e ma wagę w(e), jest spójnym, acyklicznym grafem rozpiętym na zbiorze V i minimalnej sumie wag krawędzi. Algorytm Kruskala. posortuj krawędzie według wag; dobierz kolejne krawędzie w porządku niemalejącym tak, aby nie tworzyły cyklu; Algorytm Prima. wybierz dowolny wierzchołek; dołącz do wybranego zbioru kolejny najbliższy wierzchołek;

5 Lemat. Algorytmy te działają odpowiednio w czasie O(|E| log |V|) oraz O(|E| + |V| log |V|). Definicja. MST(S) rozpięte na punktach ze zbioru S w Rn jest drzewem o wierzchołkach w S i minimalnej sumarycznej długości krawędzi. MST(S) rozpięte na punktach z SR2 można znaleźć w czasie O(n log n), a w przestrzeni d-wymiarowej (d > 2) w O(nd/2).

6 Podział (segmentacja) obrazu (image segmentation).Podziałem obrazu nazywamy proces podziału cyfrowego obrazu na wiele spójnych, wzajemnie rozłącznych i w sumie pokrywających cały obraz obszarów (zbiorów pikseli, zwanych też superpikselami). Celem podziału jest uproszczenie lub zmiana reprezentacji obrazu na uwypuklającą jakąś własność (np. podział na barwy) lub łatwiejszą do analizy (np. dla obliczeń równoległych). Podział obrazu jest zwykle wykorzystywany do lokalizacji obiektów lub ich brzegu na obrazie. Innymi słowy, jest to proces przydzielania pikselom etykiet taki, że piksele z takimi samymi etykietami mają wspólne własności.

7 Metody segmentacji możemy podzielić na kilka klas w zależności od rodzaju informacji określającej podział lub innych uwarunkowań. Możemy wyróżnić następujące metody: obszarowe: - działu wodnego, - podziału na kracie (podziału i łączenia), - rozrostu obszaru, krawędziowe, punktowe: - klastrowe, - progowe, hybrydowe – łączące w sobie powyższe metody, inne (automatyczne, półautomatyczne, zależne od wymiaru, samouczące się).

8 Metoda działu wodnego (watershed method). Możemy wyróżnić tu dwie podmetody: opadu deszczu (rainfall), zatapiania (sinking). (geomatura.pl)

9 Metoda opadu deszczu (rainfall method). Dla każdej pary sąsiednich (choć niekoniecznie) pikseli liczymy wagi łączących je krawędzi odpowiadające euklidesowej odległości wektorów RGB w tych punktach: wij = dij = ||RGBi- RGBj||. Otrzymujemy tzw. graf lokalnego sąsiedztwa. Licząc gradienty w tak określonym polu dostajemy następujący podział (kierunek spływu wody z gór): [G.Economou et al. „Godesic distance and MST based image sgmentation”]

10 Otrzymujemy spójne składowe odpowiadające zlewiskom, które wyznaczają podział obrazu (niebezpieczeństwo stanowi duża „dziura”, wokół której są mało różniące się obiekty – wtedy przy podziale obrazu mogą zostać „wessane” – stają się nierozróżnialne). [G.Economou et al. „Godesic distance and MST based image sgmentation”]

11 Metoda zatapiania (sinking method). Tak jak poprzednio tworzymy graf lokalnego sąsiedztwa, obliczamy MST i określamy na nim miarę, np. suma wag wij na ścieżce łączącej dane punkty lub maksimum z wag na takiej ścieżce. „Zatapiamy” zlewiska do pewnego poziomu. Obraz dzieli się na obszary zatopione i nie. W zależności od wybranej strategii otrzymujemy różne wyniki. [G.Economou et al. „Godesic distance and MST based image sgmentation”]

12 Zastosowanie grafu najbliższego sąsiedztwa. Wierzchołkami grafu są poszczególne piksele, a wagą krawędzi minimalna odległość między odpowiednimi punktami (x,y,r,g,b) . Badamy otoczenia pikseli o promieniu r. Takie podejście daje lepszy wynik od poprzedniego np. w następującym przypadku: [P.F.Felzenszwalb et al. „Efficient graph-based image segmentation”]

13 Inny przykład. [P.F.Felzenszwalb et al. „Efficient graph-based image segmentation”]

14 Drzewo czwórkowe (quadtree). Drzewo czwórkowe dla n-elementowego zbioru punktów P (card(P) oznacza licz-nosć zbioru P) definiujemy w następujący sposób. Niech Q := [x1,x2][y1,y2] będzie kwadratem. Jeśli card(P)  1, to drzewo czwórkowe zawiera pojedynczy liść, w którym pamię-tamy zbiór P i kwadrat Q. W przeciwnym przypadku dzielimy kwa-drat Q na ćwiartki QNE, QNW, QSW, QSE względem xm := (x1+x2)/2 i ym := (y1+y2)/2, gdzie PNE := {p  P: px > xm , py > ym }, PNW := {p  P: px  xm , py > ym }, PSW := {p  P: px  xm , py  ym }, PSE := {p  P: px > xm , py  ym }. Korzeniowi drzewa odpowiada kwadrat Q a jego synom - QNE, QNW, QSW, QSE . W wierzchołku v trzymamy kwadrat Q(v). QNE QNW QSW QSE NE NW SW SE

15 Drzewa czwórkowe mogą być wykorzy-stane npDrzewa czwórkowe mogą być wykorzy-stane np. w celu kompresji całotonal-nych obrazów bitmap-owych. Można też skorzystać z nich do two-rzenia sieci trójkątów dla efektywnych obliczeń numerycznych w szczególnych przypadkach płytek obwodów drukowanych (kierunki ścieżek różnią się o wielokrotność /4). Siatki (mesh) muszą : być dopasowane (conforming) (nie ma wierzchołków trójkątów na krawędziach innych trójkątów), uwzględniać dane (respect the input) (ścieżki są zawarte w krawędziach siatki), być dobrze ukształtowana (well shaped) (trójkąty muszą mieć określony kształt), być niejednolite (non-uniform) (małe trójkąty blisko ścieżek, a duże – daleko).

16 Metoda podziału na kracie (podziału i łączenia) (split and merge method).Wierzchołkami kraty są poszczególne piksele połączone krawędziami z sąsiadami (4 lub 8). Wagą krawędzi jest różnica intensywności barw między sąsiadami. Dzielimy te obszary (jak w drzewie czwórkowym), które nie spełniają warunku podobnej intensywności barw (metoda podziału). Następnie łączymy sąsiadujące obszary o zbliżonych intensywnościach barw. Wadą tej metody jest jej duża złożoność i wrażliwość na dobór parametrów.

17 Przykład. [http://www.uio.no/studier/emner/matnat/ifi/INF3300/h06/undervisningsmateriale/segmentation_2006.pdf]

18 Metoda rozrostu obszaru (region growing method).W metodzie tej, piksel oprócz konieczności posiadania określonych własności (np. koloru) musi sąsiadować z innymi pikselami należącymi do danego obszaru. W tym celu konieczne jest zdefiniowanie parametrów początkowych: obiektu (obiektów) bazowego, który ma się rozrastać, kryterium dołączania kolejnych pikseli. Możemy tu zastosować algorytmy morfologii matematycznej. Jeśli krawędzie obszaru nie są wyraźne obszar może się rozlewać po całym obrazie.

19 Przykład. |z-z*| < 0,1 |maxz – minz|[http://www.cse.unr.edu/~bebis/CS791E/Notes/RegionGrowing.pdf]

20 Inny przykład. [http://research.rmutp.ac.th/research/reference/Region%20growing%20a%20new%20approach.pdf]

21 Jeszcze jeden przykład. Wśród k najbliższych wierzchołków przypisujmy badanemu pikselowi barwę większości sąsiadów. [R.Cardenes et al. „Computational Geometry Computation and kNN Segmentation in ITK”.

22 Metoda krawędziowa (edge detection)Metoda krawędziowa (edge detection). Stosując segmentację krawędziową nie wykrywamy bezpośrednio obszarów, ale określamy granice między nimi wykorzystując w tym celu np. filtry gradientowe lub Laplace’a. (http://sirius.cs.put.poznan.pl/~inf74839/proceedings/binwr.pdf)

23 Metoda k-centroidów (k-means) – algorytm Lloyda.Metoda skupiskowa (cluster method) – wybieramy zbiór obiektów i dopasowujemy do nich elementy obrazu. Następnie powtarzamy to samo z innymi zbiorami, aż nie zajdą żadne zmiany. Przykład. Metoda k-centroidów (k-means) – algorytm Lloyda. [http://http://en.wikipedia.org/wiki/K-means_clustering]

24 Metoda progowa (threshold method))Metoda progowa (threshold method)). Załóżmy, że mamy dany obraz w różnych odcieniach szarości. Segmentacja przez progowanie polega na określeniu pewnej wartości pro-gowej T (w skali intensywności obrazu), względem której każdy element piksel obrazu jest przydzielany do jednej z dwóch kategorii – obiekt lub tło. Otrzymujemy funkcję W zależności od potrzeb obiekt (tło) odpowiadają punktom o wartości 1 lub 0. Aby operacja progowania miała sens, piksele obiektu muszą mieć inny zakres intensywności niż tło.

25 Progi możemy definiować na różne sposobyProgi możemy definiować na różne sposoby. Mówimy o progu globalnym, gdy wartość progu jest ustalana na podstawie całego obrazu . Gdy wartość progu zależy od współrzędnych przestrzennych (x,y) obrazu to mówimy, że próg jest ustalany dynamicznie . Gdy próg zarówno zależy od intensywności obrazu oraz jego pewnej cechy p(x,y), to próg nazywamy lokalnym. Ma to zastosowanie np. gdy obraz jest nierównomiernie oświetlony (wtedy p(x,y) odpowiada średniej jasności obrazu w danym otoczeniu).

26 X Przykład. Progowanie lokalne z maską Gaussa.[www.ii.uj.edu.pl/~rakowski/TOM_prezentacja.ppt]

27 W adaptacyjnym progowaniu wieloprzebiegowym w każdym kroku pewne piksele są klasyfikowane na podstawie ich wartości oraz progu obliczonego na podstawie wartości pikseli z pewnego zdefiniowanego otoczenia. Pozostałe, niesklasyfikowane piksele przechodzą do następnego etapu. Algorytm kończy działanie, gdy wszystkie piksele obrazu zostaną sklasyfikowane. Przykład. Lokalny próg dla piksela (x,y) może być liczony według wzoru txy = mxy + vxy, gdy vxy > vmin, gdzie m oznacza wartość średnią a v wariancję. Jeśli vxy < vmin, to wartość progu txy jest równa wartości progu dla poprzednio przetwarzanego piksela. Praktycznym problemem dającym się rozwiązać przy pomocy progowania adaptacyjnego jest sytuacja, w której na szukany obiekt pada intensywny refleks światła, co czyni jego barwę nieregularną z punktu widzenia kamery. W takim przypadku dobór pojedynczego progu może być niewystarczający.

28 Przykład. [http://www.ee.pw.edu.pl/~czajewsw/studenckie/magisterskie/Daniel_Chade.pdf]

29 Niekoniecznie musi być dokładnie jeden prógNiekoniecznie musi być dokładnie jeden próg. Przy progowaniu wielopoziomowym wartości odpowiednich poziomów progowania są elementami wektora T=[T1, T2,..., Tn]. W jego wyniku obraz podlega segmentacji na n+1 obszarów o różnych intensywnościach, np. progowanie dwupoziomowe wyznacza trzy takie obszary: [aragorn.pb.bialystok.pl/~boldak/DIP/CPO-W07-v01-50pr.pdf]

30 Ten sam algorytm z różnymi progami będzie (zazwyczaj) określał inne obszary.Jak zatem można określać progi , aby wynik był zgodny z naszymi oczekiwaniami? Ręcznie (interaktywnie). Automatycznie. Określenie właściwego progu jest skomplikowanym problemem, na którego rozwiązanie może mieć wpływ np. średnia intensywność szukanego obiektu i tła, ich rozmiary itp..

31 Dziękuję za uwagę.

32 Ćwiczenia. Udowodnij, że graf sąsiedztwa taki, że krawędź e należy do grafu, gdy nieskończony pas, którego brzegi zawierają końce krawędzi i są do niej prostopadłe, jest grafem acyklicznym. W jakiej sytuacji, wykorzystując metodę opadu deszczu, otrzymamy podział na zagnieżdżające się kręgi ? Jakie kryterium podziału otrzymamy stosując w metodzie zatapiania sumę wag na ścieżce łączącej dane punkty, a jakie – badając maksimum z wag na takiej ścieżce ? Czy metoda opadu deszczu i zatapiania mogą dać takie same podziały ? Jaka może być wysokość drzewa w metodzie podziału na kracie ?