Watershed (procesarea imaginilor)

în geologie, un bazin hidrografic este o diviziune care separă bazinele hidrografice adiacente.

bazin hidrografic prin inundareedit

ideea a fost introdusă în 1979 de către S. Beucher și C. lantu. Ideea de bază a constat în plasarea unei surse de apă în fiecare minim regional în relief, pentru a inunda întregul relief din surse și a construi bariere atunci când se întâlnesc diferite surse de apă. Setul rezultat de bariere constituie un bazin hidrografic prin inundații. O serie de îmbunătățiri, denumite colectiv prioritate-inundații, au fost făcute de atunci acestui algoritm.

bazin hidrografic prin distanță topograficăedit

intuitiv, o picătură de apă care cade pe un relief topografic curge spre „cel mai apropiat” minim. Minimul” cel mai apropiat ” este acel minim care se află la capătul căii celei mai abrupte coborâri. În ceea ce privește topografia, acest lucru se întâmplă dacă punctul se află în bazinul hidrografic al acelui minim. Definiția anterioară nu verifică această condiție.

bazinul hidrografic prin principiul picăturii de apăedit

intuitiv, bazinul hidrografic este o separare a minimelor regionale din care o picătură de apă poate curge în jos spre minime distincte. O formalizare a acestei idei intuitive a fost prevăzută pentru definirea unui bazin hidrografic al unui grafic ponderat la margine.

Inter-pixel watershedEdit

S. Beucher și F. Meyer au introdus o implementare algoritmică Inter-pixel a metodei bazinului hidrografic, având în vedere următoarea procedură:

1. etichetați fiecare minim cu o etichetă distinctă. Inițializați un set S cu nodurile etichetate.
2. extras din s un nod x de altitudine minimă F, adică F(x) = min{F(y)|Y XV s}. Atribuiți eticheta lui x fiecărui nod neetichetat y adiacent lui x și introduceți y în S.
3. repetați Pasul 2 până când S este gol.

watershedEdit topologic

noțiunile anterioare se concentrează pe bazinele hidrografice, dar nu pe linia de separare produsă. Bazinul hidrografic topologic a fost introdus de M. Couprie și G. Bertrand în 1997 și beneficiază de următoarele proprietăți fundamentale.O funcție W este un bazin hidrografic al unei funcții F dacă și numai dacă W F și W păstrează contrastul dintre minimele regionale ale F; unde contrastul dintre două minime regionale M1 și M2 este definit ca altitudinea minimă la care trebuie să urci pentru a merge de la M1 la M2. Un algoritm eficient este detaliat în lucrare.

algoritmul bazinului hidrografic

pot fi utilizate abordări diferite pentru a utiliza principiul bazinului hidrografic pentru segmentarea imaginii.

• minimele locale ale gradientului imaginii pot fi alese ca markeri, în acest caz se produce o supra-segmentare și un al doilea pas implică fuzionarea regiunii.
• transformarea bazinelor hidrografice bazate pe markeri utilizează poziții specifice de markeri care au fost fie definite în mod explicit de către utilizator, fie determinate automat cu operatori morfologici sau în alte moduri.

algoritmul de inundare al lui Meyer

unul dintre cei mai comuni algoritmi ai bazinului hidrografic a fost introdus de F. Meyer la începutul anilor 1990, deși o serie de îmbunătățiri, denumite colectiv priority-Flood, au fost făcute de atunci acestui algoritm, inclusiv variante potrivite pentru seturi de date formate din trilioane de pixeli.

algoritmul funcționează pe o imagine la scară gri. În timpul inundării succesive a reliefului grey value, sunt construite bazine hidrografice cu bazine hidrografice adiacente. Acest proces de inundare se efectuează pe imaginea gradientului, adică bazinele ar trebui să apară de-a lungul marginilor. În mod normal, acest lucru va duce la o supra-segmentare a imaginii, în special pentru materialul de imagine zgomotos, de ex. date medicale CT. Fie imaginea trebuie să fie preprocesată, fie regiunile trebuie să fie fuzionate pe baza unui criteriu de similitudine ulterior.

1. se alege un set de markeri, pixeli de unde va începe inundarea. Fiecare are o etichetă diferită.
2. pixelii vecini ai fiecărei zone marcate sunt introduși într-o coadă de prioritate cu un nivel de prioritate corespunzător mărimii gradientului pixelului.
3. pixelul cu cel mai înalt nivel de prioritate este extras din coada de prioritate. Dacă vecinii pixelului extras care au fost deja etichetați au aceeași etichetă, atunci pixelul este etichetat cu eticheta lor. Toți vecinii nemarcați care nu sunt încă în coada de prioritate sunt introduși în coada de prioritate.
4. refaceți Pasul 3 până când coada de prioritate este goală.

pixelii neetichetați sunt liniile bazinului hidrografic.

exemplu de transformare a bazinului hidrografic susținută de marker pentru o populație de pelete farmaceutice. Liniile bazinului hidrografic sunt suprapuse în negru pe stiva de imagini CT .

optimal spanning Forest algoritmi (reduceri de bazin hidrografic)Edit

bazinele hidrografice ca optimal spanning forest au fost introduse de Jean Cousty și colab. Ele stabilesc consistența acestor bazine hidrografice: ele pot fi definite în mod echivalent prin „bazinele lor de captare” (printr-o proprietate de coborâre mai abruptă) sau prin „liniile de divizare” care separă aceste bazine de captare (prin principiul picăturii de apă). Apoi dovedesc, printr-o teoremă de echivalență, optimitatea lor în ceea ce privește pădurile minime. Ulterior, ei introduc un algoritm de timp liniar pentru a le calcula. Merită menționat faptul că proprietăți similare nu sunt verificate în alte cadre, iar algoritmul propus este cel mai eficient algoritm existent, atât în teorie, cât și în practică.

• o imagine cu doi markeri (verde) și o pădure minimă care se întinde calculată pe gradientul imaginii.

• rezultatul segmentării prin pădure minimă