Watershed (beeldverwerking)

in de geologie is een waterscheiding een scheiding die aangrenzende stroomgebieden scheidt.

waterscheiding door floodinedit

het idee werd in 1979 geïntroduceerd door S. Beucher en C. Lantuéjoul. Het basisidee bestond uit het plaatsen van een waterbron in elk regionaal minimum in het reliëf, om het gehele reliëf van bronnen te overspoelen, en het bouwen van barrières wanneer verschillende waterbronnen elkaar ontmoeten. De resulterende reeks barrières vormt een waterscheiding door overstromingen. Een aantal verbeteringen, gezamenlijk genoemd Priority-Flood, zijn sindsdien gemaakt om dit algoritme.

Stroomscheiding door topografische afstanddit

intuïtief stroomt een druppel water die op een topografisch reliëf valt naar het “dichtstbijzijnde” minimum. Het “dichtstbijzijnde” minimum is het minimum dat aan het einde van het pad van de steilste afdaling ligt. In termen van topografie, dit gebeurt als het punt ligt in het stroomgebied van dat minimum. De vorige definitie verifieert deze voorwaarde niet.

waterscheiding door het drop of water principledit

intuïtief is het waterscheiding een scheiding van de regionale minima waaruit een waterdruppel naar beneden kan stromen naar verschillende minima. Een formalisering van dit intuïtieve idee werd voorzien in voor het definiëren van een waterscheiding van een rand-gewogen grafiek.

Inter-pixel watershedEdit

S. Beucher en F. Meyer introduceerden een algoritmische Inter-pixel implementatie van de watershed methode, gezien de volgende procedure:

1. Label elk minimum met een apart label. Initialiseer een set S met de gelabelde knooppunten.
2. haal uit S een knoop x van minimale hoogte F, dat wil zeggen F(x) = min{F(y)|y ∈ s}. Schrijf het label van x toe aan elk niet-gelabeld knooppunt y naast x, en plaats y in S.
3. Herhaal stap 2 totdat S leeg is.

topologische watershedEdit

eerdere noties richten zich op stroomgebieden, maar niet op de geproduceerde scheidingslijn. De topologische waterscheiding werd in 1997 geïntroduceerd door M. Couprie en G. Bertrand en heeft de volgende fundamentele eigenschap.Een functie W is dan en slechts dan een waterscheiding van een functie F als W ≤ F en W het contrast tussen de regionale minima van F behoudt; waarbij het contrast tussen twee regionale minima M1 en M2 wordt gedefinieerd als de minimale hoogte waartoe men moet klimmen om van M1 naar M2 te gaan. Een efficiënt algoritme is gedetailleerd in de paper.

Watershed-algoritme

verschillende benaderingen kunnen worden gebruikt om het watershed-principe voor beeldsegmentatie te gebruiken.

• lokale minima van het kleurverloop van de afbeelding kunnen als markeringen worden gekozen, in dit geval wordt een oversegmentatie geproduceerd en een tweede stap bestaat uit het samenvoegen van regio ‘ s.
• markergebaseerde waterscheiding transformatie maak gebruik van specifieke markerposities die ofwel expliciet door de gebruiker zijn gedefinieerd, ofwel automatisch zijn bepaald met morfologische operatoren of op andere manieren.

Meyer ‘ s flooding algorithmEdit

een van de meest voorkomende waterscheiding algoritmen werd geïntroduceerd door F. Meyer in de vroege jaren 1990, hoewel een aantal verbeteringen, gezamenlijk genoemd Priority-Flood, zijn sindsdien gemaakt om dit algoritme, met inbegrip van varianten geschikt voor datasets bestaande uit biljoenen pixels.

het algoritme werkt op een grijsschaal. Tijdens de opeenvolgende overstroming van het grijze waardereliëf worden stroomgebieden met aangrenzende stroomgebieden aangelegd. Dit overstromingsproces wordt uitgevoerd op de gradiëntafbeelding, dat wil zeggen de bekkens moeten ontstaan langs de randen. Normaal gesproken zal dit leiden tot een oversegmentatie van het beeld, vooral voor luidruchtig beeldmateriaal, bijv. medische CT-gegevens. Ofwel moet het beeld vooraf worden verwerkt, ofwel moeten de regio ‘ s achteraf worden samengevoegd op basis van een vergelijkingscriterium.

1. een set markeringen, pixels waar het vollopen moet beginnen, wordt gekozen. Elk krijgt een ander label.
2. de naburige pixels van elk gemarkeerd gebied worden ingevoegd in een prioriteitswachtrij met een prioriteitsniveau dat overeenkomt met de gradiëntmagnitude van de pixel.
3. de pixel met het hoogste prioriteitsniveau wordt uit de prioriteitwachtrij gehaald. Als de buren van de geëxtraheerde pixel die al gelabeld zijn allemaal hetzelfde label hebben, dan wordt de pixel gelabeld met hun label. Alle niet-gemarkeerde buren die nog niet in de prioriteitswachtrij staan, worden in de prioriteitswachtrij geplaatst.
4. Herhaal stap 3 totdat de prioriteitswachtrij leeg is.

de niet-gelabelde pixels zijn de waterscheiding lijnen.

voorbeeld van een marker-ondersteunde waterscheiding transformatie voor een populatie van farmaceutische pellets. Watershed-lijnen worden in het zwart op de CT-beeldstack gelegd .

Optimal spaning forest algorithms (watershed cuts)bewerken

Watersheds als optimal spaning forest zijn geïntroduceerd door Jean Cousty et al. Ze bepalen de consistentie van deze stroomgebieden: ze kunnen op equivalente wijze worden gedefinieerd door hun “stroomgebieden” (door een steilste afdaling eigenschap) of door de “scheidingslijnen” die deze stroomgebieden scheiden (door het druppelwater Principe). Dan bewijzen ze, door middel van een equivalentiestelling, hun optimaliteit in termen van minimale overspannende bossen. Daarna introduceren ze een lineair-tijd algoritme om ze te berekenen. Het is de moeite waard om op te merken dat vergelijkbare eigenschappen niet worden geverifieerd in andere kaders en het voorgestelde algoritme is de meest efficiënte bestaande algoritme, zowel in theorie en praktijk.

• een afbeelding met twee markeringen (groen) en een minimum Forest berekend op het verloop van de afbeelding.

• resultaat van de segmentatie naar minimaal overspannend bos