Watershed (przetwarzanie obrazu)

w geologii wododział to podział, który oddziela sąsiednie zlewnie.

pomysł został wprowadzony w 1979 roku przez S. Beuchera i C. Lantuéjoula. Podstawowa idea polegała na umieszczeniu źródła wody w każdym regionalnym minimum w reliefie, aby zalać całą reliefę ze źródeł i zbudować bariery, gdy spotykają się różne źródła wody. Powstały w ten sposób zespół barier stanowi zalew. Od tego czasu do tego algorytmu wprowadzono szereg ulepszeń, zwanych łącznie priorytet-Flood.

wododział według odległości topograficznej

intuicyjnie kropla wody opadająca na ulgę topograficzną płynie w kierunku „najbliższego” minimum. „Najbliższe” minimum to minimum, które znajduje się na końcu ścieżki najbardziej stromego zejścia. Pod względem topograficznym ma to miejsce, gdy punkt leży w zlewni tego minimum. Poprzednia definicja nie weryfikuje tego warunku.

wododział według zasady kropli wody

jest oddzieleniem minimów regionalnych, z których kropla wody może spływać w kierunku odrębnych minimów. Formalizacja tego intuicyjnego pomysłu została przewidziana w definiowaniu przełomu grafu ważonego krawędzią.

inter-pixel watershedEdit

S. Beucher i F. Meyer wprowadzili algorytmiczną implementację międzypikselowej metody watershed, biorąc pod uwagę następującą procedurę:

1. Oznacz każde minimum odrębną etykietą. Inicjalizacja zestawu S z oznaczonymi węzłami.
2. wyciąg z s a węzeł x o minimalnej wysokości F, to znaczy F (x) = min{f (y) / y ∈ s}. Przypisać Etykietę x do każdego nieoznakowanego węzła y przylegającego do x i wstawić y w S.
3. powtórz Krok 2, aż S będzie puste.

topological watershedEdit

poprzednie pojęcia koncentrują się na zlewniach, ale nie na wytwarzanej linii oddzielającej. Podział topologiczny został wprowadzony przez M. Couprie ’ a i G. Bertranda w 1997 r.i ma następujące własności fundamentalneFunkcja W jest działem wodnym funkcji F wtedy i tylko wtedy, gdy w ≤ F i w zachowuje kontrast między minimami regionalnymi F; gdzie kontrast między dwoma minimami regionalnymi M1 i M2 jest zdefiniowany jako minimalna wysokość, na którą należy się wspiąć, aby przejść z M1 do m2. Wydajny algorytm jest szczegółowo opisany w artykule.

algorytm Watershed

w celu zastosowania zasady watershed do segmentacji obrazu można zastosować różne podejścia.

• lokalne minima gradientu obrazu mogą być wybrane jako markery, w tym przypadku powstaje nadmierna segmentacja, a drugi krok obejmuje scalanie regionu.
• transformacja bazująca na markerach wykorzystuje określone pozycje markerów, które zostały albo wyraźnie zdefiniowane przez Użytkownika, albo ustalone automatycznie za pomocą operatorów morfologicznych lub w inny sposób.

algorytm powodziowy Meyera

jeden z najczęstszych algorytmów powodziowych został wprowadzony przez F. Meyer na początku 1990 roku, choć szereg ulepszeń, zbiorczo nazywane priorytet-Flood, od tego czasu zostały wprowadzone do tego algorytmu, w tym warianty odpowiednie dla zbiorów danych składających się z bilionów pikseli.

algorytm działa na obrazie w skali szarości. Podczas kolejnych zalewów ulgi szarej wartości budowane są zlewnie wraz z przyległymi zlewniami. Proces zalewania odbywa się na obrazie gradientowym, tzn. baseny powinny wyłaniać się wzdłuż krawędzi. Zwykle prowadzi to do nadmiernej segmentacji obrazu, szczególnie w przypadku hałaśliwego materiału graficznego, np. Medyczne dane CT. Obraz musi być wstępnie przetworzony lub regiony muszą zostać połączone na podstawie kryterium podobieństwa.

1. wybiera się zestaw znaczników, pikseli, w których ma rozpocząć się zalanie. Każda z nich ma inną etykietę.
2. sąsiadujące piksele każdego zaznaczonego obszaru są wstawiane do kolejki priorytetów o poziomie priorytetu odpowiadającym wielkości gradientu piksela.
3. piksel o najwyższym poziomie priorytetu jest wyodrębniany z kolejki priorytetów. Jeśli sąsiedzi wyodrębnionego piksela, którzy już zostali oznaczeni, mają tę samą etykietę, piksel jest oznaczany ich etykietą. Wszyscy nieoznaczeni sąsiedzi, którzy nie są jeszcze w kolejce priorytetów, są umieszczani w kolejce priorytetów.
4. ponów krok 3, aż Kolejka priorytetów będzie pusta.

nienazwane piksele są liniami wododziałowymi.

przykład wspomaganej markerem transformacji wododziałowej dla populacji granulek farmaceutycznych. Linie Wododziałowe są nakładane na stos obrazów CT w kolorze czarnym .

algorytmy optymalnego rozciągania lasu (cięcia rozlewu)Edytuj

strumienie wody jako optymalne rozciąganie lasu zostały wprowadzone przez Jean Cousty et al. Ustalają one spójność tych zlewisk: mogą być równoważnie określone przez ich „zlewnie” (poprzez najbardziej stromą właściwość opadania) lub przez „linie podziału” oddzielające te zlewiska (poprzez zasadę kropli wody). Następnie udowadniają, za pomocą twierdzenia o równoważności, ich optymalność pod względem minimalnej rozpiętości lasów. Następnie wprowadzają algorytm czasu liniowego, aby je obliczyć. Warto zauważyć, że podobne właściwości nie są weryfikowane w innych frameworkach, a proponowany algorytm jest najbardziej efektywnym istniejącym algorytmem, zarówno w teorii, jak i w praktyce.

• obraz z dwoma znacznikami (zielonym) i minimalnym lasem rozciągającym obliczonym na gradiencie obrazu.

• wynik segmentacji przez minimalny Zasięg lasu