Dział wodny (przetwarzanie obrazu)

W badaniu przetwarzania obrazu zlewnia to transformacja zdefiniowana na obrazie w skali szarości . Nazwa odnosi się metaforycznie do geologicznego działu wodnego lub podziału drenażu, który oddziela sąsiednie zlewnie. Transformacja zlewiska traktuje obraz, na którym operuje, jak mapę topograficzną , gdzie jasność każdego punktu reprezentuje jego wysokość, i znajduje linie biegnące wzdłuż wierzchołków grzbietów.

Istnieją różne definicje techniczne zlewni. Na wykresach linie wododziałowe mogą być definiowane w węzłach, na krawędziach lub linie hybrydowe zarówno w węzłach, jak i na krawędziach. Zlewiska mogą być również definiowane w domenie ciągłej . Istnieje również wiele różnych algorytmów do obliczania działów wodnych. Algorytmy zlewni są używane w przetwarzaniu obrazów głównie do segmentacji obiektów , to znaczy do oddzielania różnych obiektów na obrazie. Pozwala to na policzenie obiektów lub dalszą analizę rozdzielonych obiektów.

  • Relief of the gradient magnitude

    Relief wielkości gradientu

  • Gradient magnitude image

    Obraz wielkości gradientu

  • Watershed of the gradient

    Zlewisko gradientu

  • Watershed of the gradient (relief)

    Zlewisko gradientu (relief)

Definicje

W geologii zlewnia jest podziałem, który oddziela sąsiednie zlewnie.

Dział wodny przez powódź

Pomysł został wprowadzony w 1979 roku przez S. Beuchera i C. Lantuéjoula. Podstawowy pomysł polegał na umieszczeniu źródła wody w każdym minimum regionalnym w rzeźbie, zalaniu całej rzeźby ze źródeł i zbudowaniu barier na styku różnych źródeł wody. Powstały zespół barier stanowi zlewnię powodziową. Od tego czasu w tym algorytmie wprowadzono szereg ulepszeń, zwanych łącznie Priority-Flood.

Dział wodny według odległości topograficznej

Intuicyjnie kropla wody spadająca na rzeźbę topograficzną płynie w kierunku „najbliższego” minimum. „Najbliższe” minimum to to, które znajduje się na końcu ścieżki najbardziej stromego spadku. Pod względem topografii ma to miejsce, jeśli punkt leży w zlewni tego minimum. Poprzednia definicja nie weryfikuje tego warunku.

Zlewisko na zasadzie kropli wody

Intuicyjnie zlewisko to oddzielenie regionalnych minimów, z których kropla wody może spłynąć w dół w kierunku odrębnych minimów. Sformalizowanie tego intuicyjnego pomysłu zostało przewidziane w celu zdefiniowania działu wodnego grafu ważonego krawędziami.

Zlewnia między pikselami

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

  1. Oznacz każde minimum odrębną etykietą. Zainicjuj zestaw S z nazwanymi węzłami.
  2. Wyciągnij z S węzeł x minimalnej wysokości F , to znaczy F ( x ) = min{ F ( y )| y ∈ S }. Przypisz etykietę x każdemu nieoznakowanemu węzłowi y sąsiadującemu z x i wstaw y w S .
  3. Powtarzaj krok 2, aż S będzie puste.

Zlewisko topologiczne

Poprzednie pojęcia skupiają się na zlewniach, ale nie na wytworzonej linii podziału. Topologiczny dział wodny został wprowadzony przez M. Coupriego i G. Bertranda w 1997 r. I jest beneficjentem następującej podstawowej właściwości. Funkcja W jest działem wodnym funkcji F wtedy i tylko wtedy, gdy W ≤ F i W zachowuje kontrast między regionalnymi minimami F; gdzie kontrast między dwoma minimami regionalnymi M 1 i M 2 definiuje się jako minimalną wysokość, na jaką należy się wspiąć, aby przejść z M 1 do M 2 . Wydajny algorytm jest szczegółowo opisany w artykule.

Algorytm zlewni

Można zastosować różne podejścia do wykorzystania zasady działu wodnego do segmentacji obrazu .

  • Lokalne minima gradientu obrazu mogą być wybrane jako znaczniki, w tym przypadku powstaje nadmierna segmentacja, a drugi etap obejmuje łączenie regionów.
  • Transformacja zlewni oparta na znacznikach wykorzystuje określone pozycje znaczników, które zostały wyraźnie zdefiniowane przez użytkownika lub określone automatycznie za pomocą operatorów morfologicznych lub w inny sposób.

Algorytm zalewania Meyera

Jeden z najpopularniejszych algorytmów działu wodnego został wprowadzony przez F. Meyera na początku lat 90. XX wieku, chociaż od tego czasu wprowadzono do tego algorytmu szereg ulepszeń, zwanych łącznie Priority-Flood, w tym warianty odpowiednie dla zestawów danych składających się z bilionów pikseli.

Algorytm działa na obrazie w skali szarości. Podczas sukcesywnego zalewania rzeźby szarej powstają wododziały wraz z przylegającymi do nich zlewniami. Ten proces zalewania odbywa się na obrazie gradientowym, tzn. baseny powinny pojawiać się wzdłuż krawędzi. Normalnie prowadzi to do nadmiernej segmentacji obrazu, zwłaszcza w przypadku zaszumionego materiału obrazu, np. danych medycznych tomografii komputerowej. Albo obraz musi być wstępnie przetworzony, albo regiony muszą zostać później połączone na podstawie kryterium podobieństwa.

  1. Wybrano zestaw znaczników, pikseli, w których rozpocznie się zalewanie. Każdy otrzymuje inną etykietę.
  2. Sąsiednie piksele każdego zaznaczonego obszaru są wstawiane do kolejki priorytetowej z poziomem 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 zostali już oznaczeni, mają tę samą etykietę, wówczas piksel jest oznaczony ich etykietą. Wszyscy nieoznaczeni sąsiedzi, którzy nie znajdują się jeszcze w kolejce priorytetowej, są umieszczani w kolejce priorytetowej.
  4. Powtarzaj krok 3, aż kolejka priorytetów będzie pusta.

Nieoznakowane piksele to linie zlewiska.

Przykład wspieranej przez markery transformacji działu wodnego dla populacji peletek farmaceutycznych. Linie wododziału są nałożone w kolorze czarnym na stos obrazów CT.

Algorytmy optymalnego lasu rozpinającego (wycięcia zlewiska)

Zlewiska jako optymalny las rozciągający zostały wprowadzone przez Jeana Cousty'ego i in. Ustalają spójność tych zlewni: mogą być równoważnie zdefiniowane przez ich „zlewnie” (poprzez właściwość najbardziej stromego spadku) lub przez „linie podziału” oddzielające te zlewnie (poprzez zasadę kropli wody). Następnie udowadniają, za pomocą twierdzenia o równoważności, swoją 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 najskuteczniejszym istniejącym algorytmem, zarówno w teorii, jak iw praktyce.

  • An image with two markers (green), and a Minimum Spanning Forest computed on the gradient of the image.

    Obraz z dwoma znacznikami (zielony) i minimalnym lasem rozpinającym obliczonym na podstawie gradientu obrazu.

  • Result of the segmentation by Minimum Spanning Forest

    Wynik segmentacji według minimalnego lasu rozpinającego

Powiązania z innymi algorytmami widzenia komputerowego

Cięcia wykresów

W 2007 roku C. Allène i in. ustanowione powiązania odnoszące się do cięć wykresów z optymalnymi lasami rozciągającymi się. Dokładniej, pokazują one, że gdy potęga wag wykresu jest powyżej pewnej liczby, cięcie minimalizujące wykres tnie energię jest cięciem przez las o maksymalnym rozpiętości.

Lasy najkrótszej ścieżki

Transformacja zalesienia obrazu (IFT) Falcao i in. jest procedurą obliczania lasów najkrótszej ścieżki. Udowodnili to J. Cousty i in. że gdy znaczniki IFT odpowiadają ekstremom funkcji wagi, cięcie wywołane przez las jest cięciem działu wodnego.

Przypadkowy spacerowicz

Algorytm losowego wędrowca to algorytm segmentacji rozwiązujący kombinatoryczny problem Dirichleta , zaadaptowany do segmentacji obrazu przez L. Grady'ego w 2006 roku. W 2011 roku C. Couprie i in. udowodnił, że gdy potęgi wag grafu zbiegają się w kierunku nieskończoności, cięcie minimalizujące energię przypadkowego wędrowca jest cięciem przez las o maksymalnym rozpiętości.

Hierarchie

Hierarchiczna transformacja wododziału przekształca wynik w wykres (tj. określane są relacje sąsiadów segmentowanych regionów) i rekurencyjnie stosuje dalsze przekształcenia wododziału. Zobacz więcej szczegółów. Teoria łącząca dział wodny z hierarchiczną segmentacją została opracowana w

Notatki

  1. ^ L. Najman i M. Schmitt. Dział wodny funkcji ciągłej . W przetwarzaniu sygnałów (wydanie specjalne poświęcone morfologii matematycznej), tom. 38 (1994), strony 99–112
  2. ^ Warsztaty Serge Beucher i Christian Lantuéj dotyczące przetwarzania obrazu, wykrywania krawędzi i ruchu w czasie rzeczywistym (1979). http://cmm.ensmp.fr/~beucher/publi/watershed.pdf
  3. ^ Barnes, R., Lehman, C., Mulla, D., 2014. Powódź priorytetowa: optymalny algorytm wypełniania depresji i oznaczania zlewni dla cyfrowych modeli wysokości . Komputery i nauki o Ziemi 62, 117–127. doi : 10.1016/j.cageo.2013.04.024
  4. ^ J. Cousty, G. Bertrand, L. Najman i M. Couprie. Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle , IEEE Transactions on Pattern Analysis and Machine Intelligence 31(8) s. 1362-1374, 2009,
  5. ^ Serge Beucher i Fernand Meyer. Morfologiczne podejście do segmentacji: transformacja działu wodnego . W Mathematical Morphology in Image Processing (red. ER Dougherty), strony 433–481 (1993).
  6. ^ M. Couprie, G. Bertrand. Topologiczna transformacja działu wodnego w skali szarości. w Proc. SPIE Vision Geometry V, tom 3168, strony 136–146 (1997). http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3.7654&rep=rep1&type=pdf
  7. Bibliografia _ Na zlewiskach topologicznych . Journal of Mathematical Imaging and Vision, 22 (2–3), strony 217–230 (2005).
  8. ^ Michel Couprie, Laurent Najman, Gilles Bertrand. Algorytmy quasi-liniowe dla zlewiska topologicznego . Journal of Mathematical Imaging and Vision, Springer Verlag, 2005, 22 (2-3), s. 231-249.
  9. ^ Barnes, R., Lehman, C., Mulla, D., 2014. Powódź priorytetowa: optymalny algorytm wypełniania depresji i oznaczania zlewni dla cyfrowych modeli wysokości . Komputery i nauki o Ziemi 62, 117–127. doi : 10.1016/j.cageo.2013.04.024
  10. ^ Barnes, R., 2016. Równoległe wypełnianie depresji powodziowej z priorytetem dla bilionów komórek cyfrowych modeli wysokości na komputerach stacjonarnych lub klastrach. Komputery i nauki o Ziemi. doi : 10.1016/j.cageo.2016.07.001
  11. ^ Doerr, FJS i Florence, AJ (2020). Analiza obrazu mikro-XRT i metodologia uczenia maszynowego do charakteryzowania wielocząstkowych preparatów kapsułek. International Journal of Pharmaceutics: X, 2, 100041. https://doi.org/10.1016/j.ijpx.2020.100041
  12. ^ Jean Cousty, Gilles Bertrand, Laurent Najman i Michel Couprie. Cięcia działów wodnych: minimalne lasy rozciągające się i zasada kropli wody . Transakcje IEEE dotyczące analizy wzorców i inteligencji maszynowej. 31 (8). Sierpień 2009. s. 1362–1374.
  13. ^ Cédric Allène, Jean-Yves Audibert, Michel Couprie i Renaud Keriven: „ Niektóre powiązania między minimalnymi cięciami, optymalnymi lasami i zlewniami ”, Image and Vision Computing, 2009.
  14. ^ Falcao, AX Stolfi, J. de Alencar Lotufo, R.: „ Przekształcenie lasów obrazu: teoria, algorytmy i aplikacje ”, W PAMI, 2004
  15. ^ Jean Cousty, Gilles Bertrand, Laurent Najman i Michel Couprie. Wycięcia działów wodnych: przerzedy, lasy najkrótszej ścieżki i zlewiska topologiczne . Transakcje IEEE dotyczące analizy wzorców i inteligencji maszynowej. 32 (5). 2010. s. 925–939.
  16. ^ Grady, L .: „ Losowe spacery w celu segmentacji obrazu ”. PAMI, 2006
  17. ^ Camille Couprie, Leo Grady, Laurent Najman i Hugues Talbot, „ Power Watersheds: A Unifying Graph-Based Optimization Framework ”, IEEE Transactions on Pattern Analysis and Machine Intelligence, t. 33, nr 7, s. 1384-1399, lipiec 2011
  18. ^ Laurent Najman, Michel Schmitt. Istotność geodezyjna konturów zlewni i segmentacja hierarchiczna . IEEE Transactions on Pattern Analysis and Machine Intelligence, Instytut Inżynierów Elektryków i Elektroników, 1996, 18 (12), s. 1163-1173.
  19. Bibliografia _ O równoważności między segmentacjami hierarchicznymi a zlewniami ultrametrycznymi . Journal of Mathematical Imaging and Vision, Springer Verlag, 2011, 40 (3), s. 231-247.

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Watershed_(image_processing)&oldid=1109774665 ”