Vattendelare (bildbehandling)

i geologi är en vattendrag en klyfta som skiljer intilliggande avrinningsområden.

Watershed by floodingEdit

tanken introducerades 1979 av S. Beucher och C. Lantu Jacobjoul. Grundtanken bestod av att placera en vattenkälla i varje regionalt minimum i lättnaden, att översvämma hela lättnaden från källor och bygga hinder när olika vattenkällor möts. Den resulterande uppsättningen hinder utgör en vattendrag genom översvämning. Ett antal förbättringar, kollektivt kallade Priority-Flood, har sedan dess gjorts till denna algoritm.

Watershed by topographic distanceEdit

intuitivt strömmar en droppe vatten som faller på en topografisk lättnad mot det ”närmaste” minimumet. Det ”närmaste” minimumet är det minimum som ligger i slutet av den brantaste nedstigningsvägen. När det gäller topografi inträffar detta om punkten ligger i avrinningsområdet för detta minimum. Den tidigare definitionen verifierar inte detta villkor.

Watershed by the drop of water principleEdit

intuitivt är watershed en separation av de regionala minima från vilka en droppe vatten kan strömma ner mot distinkta minima. En formalisering av denna intuitiva ide tillhandahölls för att definiera en vattendrag av en kantviktad graf.

inter-pixel watershedEdit

S. Beucher och F. Meyer introducerade en algoritmisk inter-pixel implementering av vattendelarmetoden, med följande procedur:

1. märk varje minimum med en distinkt etikett. Initiera en uppsättning S med de märkta noderna.
2. extrahera från S en nod x med minimal höjd F, det vill säga F(x) = min{F(y)|y xhamster s}. Ange etiketten x till varje icke-märkt nod y intill x och sätt in y i S.
3. Upprepa steg 2 tills S är tomt.

Topological watershedEdit

tidigare begrepp fokuserar på avrinningsområden, men inte på den producerade separationslinjen. Den topologiska vattendelaren introducerades av M. Couprie och G. Bertrand 1997 och gynnade följande grundläggande egendom.En funktion W är en vattendelare av en funktion F om och endast om W 0 F och W bevarar kontrasten mellan de regionala minima för F; där kontrasten mellan två regionala minima M1 och M2 definieras som den minsta höjd som man måste klättra för att gå från M1 till M2. En effektiv algoritm beskrivs i papperet.

vattendelaralgoritm

olika metoder kan användas för att använda vattendelarprincipen för bildsegmentering.

• lokala minima för bildens lutning kan väljas som markörer, i detta fall produceras en översegmentering och ett andra steg involverar regionsammanslagning.
• markörbaserad omvandling av vattendrag använder sig av specifika markörpositioner som antingen uttryckligen definierats av användaren eller bestäms automatiskt med morfologiska operatörer eller andra sätt.

Meyers översvämningsalgoritmredigera

en av de vanligaste vattendelaralgoritmerna introducerades av F. Meyer i början av 1990-talet, även om ett antal förbättringar, kollektivt kallade Priority-Flood, har sedan dess gjorts till denna algoritm, inklusive varianter som är lämpliga för dataset som består av biljoner pixlar.

algoritmen fungerar på en gråskala bild. Under den successiva översvämningen av gråvärdesreliefen byggs vattendrag med intilliggande avrinningsområden. Denna översvämningsprocess utförs på lutningsbilden, d.v. s. bassängerna ska dyka upp längs kanterna. Normalt leder detta till en översegmentering av bilden, särskilt för bullriga bildmaterial, t. ex. medicinska CT-data. Antingen måste bilden förbehandlas eller regionerna måste slås samman på grundval av ett likhetskriterium efteråt.

1. en uppsättning markörer, pixlar där översvämningen ska börja, väljs. Var och en får en annan etikett.
2. de närliggande pixlarna i varje markerat område infogas i en prioritetskö med en prioritetsnivå som motsvarar pixelns gradientstorlek.
3. pixeln med högsta prioritetsnivå extraheras från prioritetskön. Om grannarna till den extraherade pixeln som redan har märkts alla har samma etikett, märks pixeln med etiketten. Alla icke-markerade grannar som ännu inte finns i prioritetskön placeras i prioritetskön.
4. gör om steg 3 tills prioritetskön är tom.

de icke-märkta pixlarna är vattendragslinjerna.

exempel på en markörstödd omvandling av vattendrag för en population av farmaceutiska pellets. Vattendragslinjer läggs över i svart på CT-bildstacken .

Optimal spanning forest algorithms (watershed cuts)redigera

vattendrag som optimal spanning forest har introducerats av Jean Cousty et al. De fastställer konsistensen hos dessa avrinningsområden: de kan definieras likvärdigt av deras ”avrinningsområden” (genom en brantaste nedstigningsegenskap) eller genom ”delningslinjer” som skiljer dessa avrinningsområden (genom vattendroppsprincipen). Sedan bevisar de, genom en ekvivalenssats, deras optimalitet när det gäller minsta spännskogar. Därefter introducerar de en linjär tidsalgoritm för att beräkna dem. Det är värt att notera att liknande egenskaper inte verifieras i andra ramar och den föreslagna algoritmen är den mest effektiva befintliga algoritmen, både i teori och praktik.

• en bild med två markörer (grön) och en minsta Spännskog beräknad på bildens lutning.

• resultat av segmenteringen genom minimal Spännskog