Watershed (bildebehandling)

i geologi er et vannskille et skille som skiller tilstøtende avløpsbassenger.

Vannskille ved floodingEdit

ideen ble introdusert i 1979 Av S. Beucher og C. Lantué. Den grunnleggende ideen besto av å plassere en vannkilde i hvert regionalt minimum i lettelsen, å oversvømme hele lettelsen fra kilder, og bygge barrierer når forskjellige vannkilder møtes. Den resulterende sett av barrierer utgjør et vannskille av flom. En rekke forbedringer, kollektivt kalt Priority-Flood, har siden blitt gjort til denne algoritmen.

Vannskille ved topografisk avstandrediger

Intuitivt flyter en dråpe vann som faller på et topografisk relieff mot det» nærmeste » minimum. Den» nærmeste » minimum er det minimum som ligger på slutten av banen bratteste nedstigningen. Når det gjelder topografi, skjer dette hvis punktet ligger i oppsamlingsbassenget av det minste. Den forrige definisjonen bekrefter ikke denne tilstanden.

Vannskille ved prinsippet om vanndråpe [rediger / Rediger kilde]

Intuitivt er vannskillet en adskillelse av det regionale minima hvorfra en dråpe vann kan strømme ned mot distinkte minima. En formalisering av denne intuitive ideen ble gitt i for å definere et vannskille av en kantvektet graf.

Inter-pixel watershedEdit

S. Beucher og F. Meyer introduserte en algoritmisk inter-pixel implementering av watershed-metoden, gitt følgende prosedyre:

  1. Merk hvert minimum med en tydelig etikett. Initialiser et sett S med de merkede nodene.
  2. Utdrag fra s en node x av minimal høyde F, det vil si F(x) = min{F (y| / y ∈ s}. Tilordne etiketten til x til hver ikke-merket node y ved siden av x, og sett inn y I S.
  3. Gjenta Trinn 2 til S er tom.

Topologisk watershedEdit

Tidligere forestillinger fokuserer på nedslagsfelt, men ikke på den produserte skillelinjen. Det topologiske vannet ble introdusert Av M. Couprie Og G. Bertrand i 1997, og nyter godt av følgende grunnleggende eiendom.En funksjon W er et vannskille av en funksjon F hvis Og bare Hvis W ≤ F og W bevarer kontrasten mellom de regionale minima Av F; hvor kontrasten Mellom to regionale minima M1 og M2 er definert som den minimale høyden som man må klatre for å gå Fra M1 Til M2. En effektiv algoritme er beskrevet i papiret.

Vannskille-algoritme

Ulike tilnærminger kan brukes til å bruke vannskille-prinsippet for bildesegmentering.

  • Lokale minima av gradienten til bildet kan velges som markører, i dette tilfellet produseres en over-segmentering, og et andre trinn innebærer at regionen slås sammen.
  • Markørbasert vannskille-transformasjon gjør bruk av spesifikke markørposisjoner som enten er eksplisitt definert av brukeren eller bestemt automatisk med morfologiske operatører eller på andre måter.

meyers flomalgoritmerrediger

en av De vanligste vannskille-algoritmene ble introdusert Av F. Meyer tidlig på 1990-tallet, men en rekke forbedringer, kollektivt kalt Priority-Flood, har siden blitt gjort til denne algoritmen, inkludert varianter egnet for datasett som består av billioner piksler.

algoritmen fungerer på en gråskala bilde. I løpet av den påfølgende oversvømmelse av grå verdi lettelse, nedbørfelt med tilstøtende nedslagsfelt bassenger er konstruert. Denne flomprosessen utføres på gradientbildet, dvs. bassengene skal dukke opp langs kantene. Normalt vil dette føre til en over-segmentering av bildet, spesielt for støyende bildemateriale, f. eks. medisinske CT-data. Enten må bildet forhåndsbehandles, eller regionene må slås sammen på grunnlag av et likhetskriterium etterpå.

  1. et sett med markører, piksler hvor flommen skal starte, er valgt. Hver er gitt en annen etikett.
  2. de tilstøtende pikslene i hvert merkede område settes inn i en prioritetskø med et prioritetsnivå som tilsvarer gradientstørrelsen til pikselen.
  3. pikselen med høyeste prioritetsnivå trekkes ut fra prioritetskøen. Hvis naboene til den utpakkede pikselen som allerede er merket, har samme etikett, er pikselen merket med etiketten. Alle ikke-merkede naboer som ennå ikke er i prioritetskøen, legges inn i prioritetskøen.
  4. Gjenta trinn 3 til prioritetskøen er tom.

de ikke-merkede pikslene er vannskille linjene.

Eksempel på en markør-støttet vannskille transformasjon for en populasjon av farmasøytiske pellets. Vannskille linjer er lagt i svart PÅ CT image stack .

Optimale spanning skog algoritmer (vannskille kutt)Edit

Nedbørfelt som optimal spanning skog har blitt introdusert Av Jean Cousty et al. De etablerer konsistensen av disse nedbørsfeltene: de kan ekvivalent defineres av deres «nedslagsfelt» (gjennom en bratteste nedstigningsegenskap) eller ved «skillelinjer» som skiller disse nedbørsfeltene(gjennom vanndråpeprinsippet). Da viser de, gjennom en ekvivalenssteorem, deres optimalitet når det gjelder minimumspanning av skoger. Etterpå introduserer de en lineær tidsalgoritme for å beregne dem. Det er verdt å merke seg at lignende egenskaper ikke er verifisert i andre rammer, og den foreslåtte algoritmen er den mest effektive eksisterende algoritmen, både i teori og praksis.

  • et bilde med to markører (grønn), Og Et Minimum Spenner Skogen beregnet på gradient av bildet.

  • Resultat Av segmenteringen Ved Minimumspanning Av Skog



+