Vízválasztó (képfeldolgozás)

ban ben geológia, a vízválasztó egy szakadék amely elválasztja a szomszédos vízgyűjtő medencéket.

Watershed by floodingszerkesztés

az ötletet 1979-ben vezette be S. Beucher és C. Lantu. Az alapötlet abból állt, hogy a dombormű minden regionális minimumába vízforrást helyeztek, hogy a teljes domborművet elárasszák a forrásokból, és akadályokat építsenek, amikor a különböző vízforrások találkoznak. Az így létrejövő akadályok vízválasztót jelentenek az áradások miatt. Azóta számos fejlesztés történt, együttesen prioritás-áradásnak hívják ezt az algoritmust.

vízválasztó topográfiai távolság szerintszerkeszt

intuitív módon a topográfiai domborműre eső vízcsepp a “legközelebbi” minimum felé áramlik. A “legközelebbi” minimum az a minimum, amely a legmeredekebb ereszkedés útjának végén fekszik. A topográfia szempontjából ez akkor fordul elő, ha a pont ennek a minimumnak a vízgyűjtő medencéjében fekszik. Az előző meghatározás nem igazolja ezt a feltételt.

vízválasztó

intuitív módon a vízválasztó a regionális minimumok elválasztása, ahonnan egy csepp víz folyhat le a különböző minimumok felé. Ennek az intuitív ötletnek a formalizálását az élekkel súlyozott gráf vízválasztójának meghatározásához nyújtották.

pixelek közötti vízválasztószerkesztés

S. Beucher és F. Meyer bevezette a vízválasztó módszer algoritmikus pixelek közötti megvalósítását, a következő eljárás szerint:

1. jelöljön meg minden minimumot külön címkével. Inicializáljon egy s készletet a címkézett csomópontokkal.
2. kivonat az S-ből egy minimális f magasságú x csomópontból, azaz F(x) = min{F(y)|y ++ s}.
3. ismételje meg a 2.lépést, amíg S üres.

Topological watershedEdit

a korábbi elképzelések a vízgyűjtő medencékre összpontosítottak, de nem az előállított elválasztó vonalra. A topológiai vízválasztót M. Couprie és G. Bertrand vezette be 1997-ben, és a következő alapvető tulajdonság kedvezményezettje.A W függvény egy f függvény vízválasztója, ha és csak akkor, ha W F és W megőrzi az F regionális minimumok közötti kontrasztot; ahol a két M1 és M2 regionális minimum közötti kontrasztot az a minimális magasság határozza meg, amelyre fel kell mászni ahhoz, hogy M1-ről M2-re menjen. A hatékony algoritmust a cikk részletezi.

vízválasztó algoritmus

különböző megközelítések alkalmazhatók a vízválasztó elv használatára a képszegmentáláshoz.

• a kép gradiensének helyi minimuma jelölőként választható, ebben az esetben túlzott szegmentáció jön létre, a második lépés pedig a régió egyesítése.
• a Marker alapú vízválasztó transzformáció olyan specifikus marker pozíciókat használ, amelyeket a Felhasználó kifejezetten meghatározott, vagy morfológiai operátorokkal vagy más módon automatikusan meghatározott.

Meyer ‘ s flooding algorithmEdit

az egyik leggyakoribb vízválasztó algoritmust vezette be F. Meyer az 1990-es évek elején, bár azóta számos fejlesztés történt, amelyeket együttesen prioritás-áradásnak neveznek, ezen algoritmuson, beleértve a billió pixelből álló adatkészletekhez alkalmas változatokat is.

az algoritmus szürkeárnyalatos képen működik. A grey value relief egymást követő áradása során a szomszédos vízgyűjtő medencékkel rendelkező vízgyűjtők épülnek. Ezt az elárasztási folyamatot a gradiens képen hajtják végre, azaz a medencéknek a szélek mentén kell megjelenniük. Ez általában a kép túlzott szegmentálásához vezet, különösen zajos képanyagok esetén, pl. orvosi CT adatok. Vagy a képet előzetesen fel kell dolgozni, vagy a régiókat hasonlósági kritérium alapján össze kell vonni.

1. Jelölőkészlet, pixelek, ahol az elárasztásnak meg kell kezdődnie. Mindegyik más címkét kap.
2. az egyes megjelölt területek szomszédos képpontjai egy prioritási sorba kerülnek, amelynek prioritási szintje megfelel a pixel gradiens nagyságának.
3. a legmagasabb prioritási szinttel rendelkező pixelt a rendszer kibontja a prioritási sorból. Ha a kibontott pixel szomszédai, amelyek már fel vannak címkézve, mind ugyanazzal a címkével rendelkeznek, akkor a pixelt a címkéjükkel jelölik. Az összes nem megjelölt szomszéd, amely még nem szerepel a prioritási sorban, a prioritási sorba kerül.
4. ismételje meg a 3.lépést, amíg a prioritási sor üres.

a nem címkézett pixelek a vízválasztó vonalak.

példa marker által támogatott vízválasztó átalakításra gyógyszeripari pelletek populációjára. A vízgyűjtő vonalak fekete színnel vannak elhelyezve a CT képkötegen .

optimális átívelő erdő algoritmusok (vízválasztó vágások)Edit

vízgyűjtők optimális átívelő erdő vezettek be Jean Cousty et al. Megállapítják ezeknek a vízgyűjtőknek az állandóságát: ekvivalensen meghatározhatók “vízgyűjtő medencéik” (a legmeredekebb ereszkedési tulajdonságon keresztül) vagy az ezeket a vízgyűjtő medencéket elválasztó “elválasztó vonalak” (a vízcseppek elvén keresztül). Ezután egy ekvivalencia-tétel révén bizonyítják optimalitásukat a minimális átívelő erdők szempontjából. Ezután lineáris idejű algoritmust vezetnek be a számításukhoz. Érdemes megjegyezni, hogy hasonló tulajdonságokat más keretrendszerekben nem ellenőriznek, és a javasolt algoritmus a leghatékonyabb létező algoritmus, mind elméletben, mind gyakorlatban.

• egy kép két markerrel (zöld) és egy minimális átívelő erdővel, amelyet a kép gradiensére számítanak.

• a szegmentáció eredménye minimális átívelő erdő szerint