Minimalna segmentacja oparta na drzewie rozpinającym
Segmentacja obrazu ma na celu podzielenie obrazu cyfrowego na obszary pikseli o podobnych właściwościach, np. jednorodności. Reprezentacja regionu wyższego poziomu upraszcza zadania związane z analizą obrazu, takie jak liczenie obiektów lub wykrywanie zmian, ponieważ atrybuty obszaru (np. średnią intensywność lub kształt) można porównywać łatwiej niż surowe piksele.
Motywacja dla metod opartych na wykresach
Aby przyspieszyć segmentację dużych obrazów, pracę można podzielić na kilka procesorów . Jednym ze sposobów osiągnięcia tego celu jest podzielenie obrazów na kafelki, które są przetwarzane niezależnie. Jednak regiony leżące okrakiem na granicy kafelka mogą zostać podzielone lub utracone, jeśli fragmenty nie spełniają minimalnych wymagań algorytmu segmentacji. Trywialne obejście polega na nakładaniu kafelków, tj. umożliwieniu każdemu procesorowi rozważenia dodatkowych pikseli wokół granicy kafelka. Niestety zwiększa to obciążenie obliczeniowe, ponieważ procesory po obu stronach granicy kafelków wykonują nadmiarową pracę. Ponadto zagwarantowane jest zachowanie tylko obiektów mniejszych niż nakładające się kafelki, co oznacza, że długie obiekty, takie jak rzeki na zdjęciach lotniczych, nadal mogą zostać podzielone. W niektórych przypadkach wyniki niezależnych płytek można połączyć, aby przybliżyć prawdziwe wyniki. Istnieje alternatywa w postaci metod segmentacji opartych na grafach. Informacje o łączności nieodłącznie związane z wykresami umożliwiają wykonywanie niezależnych prac na częściach oryginalnego obrazu i ponowne łączenie ich w celu uzyskania dokładnego wyniku, tak jakby przetwarzanie miało miejsce globalnie.
Od obrazów do wykresów
Możliwość łączenia niezależnych obrazów podrzędnych motywuje dodawanie informacji o łączności do pikseli. Można to postrzegać jako wykres, którego węzłami są piksele, a krawędzie reprezentują połączenia między pikselami. Prostym i stosunkowo zajmującym mało miejsca wariantem tego jest wykres siatkowy , w którym każdy piksel jest połączony z sąsiadami w czterech głównych kierunkach . Ponieważ relacja sąsiedztwa pikseli jest symetryczna, wynikowy wykres jest nieskierowany i tylko połowa jego krawędzi (np. wschodni i południowy sąsiad każdego piksela) musi być przechowywana. Ostatni krok wymaga zakodowania informacji o podobieństwie pikseli w wagach krawędzi, tak aby oryginalny obraz nie był już potrzebny. W najprostszym przypadku wagi krawędzi są obliczane jako różnica intensywności pikseli.
Minimalne algorytmy segmentacji drzewa rozpinającego
Minimalne drzewo rozpinające (MST) to podzbiór krawędzi grafu o minimalnej wadze, wolny od cykli , taki, że wszystkie węzły są połączone. W 2004 roku Felzenszwalb wprowadził metodę segmentacji opartą na algorytmie MST Kruskala . Krawędzie są rozpatrywane w kolejności rosnącej wagi; ich piksele punktów końcowych są scalane w region, jeśli nie powoduje to cyklu na wykresie i jeśli piksele są „podobne” do pikseli istniejących regionów. Wykrywanie cykli jest możliwe w niemal stałym czasie za pomocą rozłącznej struktury danych . Podobieństwo pikseli jest oceniane za pomocą heurystyki, która porównuje wagę z progiem na segment. Algorytm generuje wiele rozłącznych MST, tj. las; każde drzewo odpowiada segmentowi. Złożoność algorytmu jest quasi-liniowa, ponieważ sortowanie krawędzi jest możliwe w czasie liniowym poprzez sortowanie zliczające .
W 2009 roku Wassenberg i in. opracował algorytm, który oblicza wiele niezależnych lasów o minimalnej rozpiętości, a następnie łączy je ze sobą. Umożliwia to przetwarzanie równoległe bez dzielenia obiektów na krawędziach kafelków. Zamiast ustalonego progu masy, do oszacowania dolnej granicy progu stosuje się początkowe oznakowanie połączonego komponentu , co może zredukować zarówno przewymiarowanie, jak i niedoszacowanie segmentacji. Pomiary pokazują, że implementacja przewyższa sekwencyjny algorytm Felzenszwalba o rząd wielkości.
W 2017 roku Saglam i Baykan wykorzystali sekwencyjną reprezentację minimalnego drzewa rozpinającego Prim i zaproponowali nowe kryterium cięcia dla segmentacji obrazu. Konstruują MST za pomocą algorytmu MST firmy Prim, używając struktury danych Fibonacciego Heap. Metoda osiąga istotny sukces na obrazach testowych w krótkim czasie wykonania.