Povodí (zpracování obrazu)

v geologii je povodí předěl, který odděluje sousední povodí.

povodí povodněeditovat

myšlenka byla představena v roce 1979 s. Beucherem A C. Lantuéjoulem. Základní myšlenka spočívala v umístění vodního zdroje do každého regionálního minima v reliéfu, zaplavení celého reliéfu ze zdrojů a vybudování bariér, když se setkávají různé vodní zdroje. Výsledný soubor bariér představuje povodeň povodněmi. K tomuto algoritmu byla od té doby provedena řada vylepšení, souhrnně nazývaných Priorita-povodeň.

povodí topografickou vzdálenostíit

intuitivně proudí kapka vody padající na topografický reliéf směrem k „nejbližšímu“ minimu. „Nejbližší“ minimum je minimum, které leží na konci cesty nejstrmějšího klesání. Z hlediska topografie k tomu dochází, pokud bod leží v povodí tohoto minima. Předchozí definice tuto podmínku neověřuje.

Povodí o kapku vody principleEdit

Intuitivně, povodí je oddělení regionálního minima, od kterého se kapky vody může proudit směrem k odlišné minima. Formalizace této intuitivní myšlenky byla poskytnuta pro definování povodí grafu váženého hranou.

Inter-pixel watershedEdit

S. Beucher a F. Meyer představil algoritmický inter-pixel provádění povodí metoda, s ohledem na následující postup:

1. označte každou minimální s jiným štítkem. Inicializujte sadu S označenými uzly.
2. extrahujte z S uzel x minimální nadmořské výšky F, to znamená F (x) = min{F (y)|y} s}. Atribut štítku x pro každý non-označen uzel y přiléhající k x, a vložte y v S.
3. Opakujte Krok 2, dokud S je prázdný.

topologické povodí

předchozí pojmy se zaměřují na povodí, ale ne na vytvořenou oddělovací linii. Topologická povodí byla zavedena m. Couprie a G. Bertrand v roce 1997 a zužitkovala následující základní vlastnost.Funkci W je předělem funkce F tehdy a jen tehdy, pokud W ≤ F a W zachovává kontrast mezi regionální minima F; je-li kontrast mezi dvěma regionální minima M1 a M2 je definována jako minimální výška, do které člověk musí vylézt aby se jít z M1 do M2. Efektivní algoritmus je podrobně popsán v článku.

algoritmus povodí

lze použít různé přístupy k použití principu povodí pro segmentaci obrazu.

• Lokální minima gradientu obrazu může být vybrán jako značky, v tomto případě přes-segmentace je produkován a druhý krok zahrnuje oblasti sloučení.
• Marker based watershed transformation využívají specifické pozice markerů, které byly buď explicitně definovány uživatelem, nebo automaticky určeny morfologickými operátory nebo jinými způsoby.

Meyerův zaplavovací algoritmeditovat

jeden z nejběžnějších povodňových algoritmů představil F. Meyer v časných 1990, i když řadu vylepšení, souhrnně nazývají Prioritní-Povodeň, od té doby na tento algoritmus, včetně varianty vhodné pro datové sady skládající se z bilionů pixelů.

algoritmus pracuje na obrázku šedé stupnice. Během postupného zaplavení reliéfu šedé hodnoty, jsou vybudována povodí s přilehlými povodími. Tento zaplavovací proces se provádí na gradientním obrazu, tj. nádrže by se měly objevit podél okrajů. Obvykle to povede k nadměrné segmentaci obrazu, zejména u hlučného obrazového materiálu, např. lékařské CT údaje. Buď musí být obraz předem zpracován, nebo musí být regiony sloučeny na základě kritéria podobnosti.

1. je zvolena sada značek, pixelů, na kterých má povodeň začít. Každý má jiný štítek.
2. sousední pixely každé označené oblasti jsou vloženy do prioritní fronty s úrovní priority odpovídající velikosti gradientu pixelu.
3. pixel s nejvyšší úrovní priority je extrahován z prioritní fronty. Pokud sousedé extrahovaného pixelu, kteří již byli označeni, mají stejný štítek, pak je pixel označen jejich štítkem. Všichni neoznačení sousedé, kteří ještě nejsou v prioritní frontě, jsou zařazeni do prioritní fronty.
4. opakujte krok 3, dokud není prioritní fronta prázdná.

neoznačené pixely jsou linie povodí.

příklad transformace povodí podporovaného markerem pro populaci farmaceutických pelet. Linie povodí jsou na zásobníku CT obrazu překryty černě .

Optimální překlenutí lesa algoritmy (povodí řezy)Upravit

Povodí jako optimální zahrnující lesy byly zavedeny Jean Cousty et al. Oni vytvořit soulad těchto povodích: mohou být ekvivalentně definovat jejich „spádové povodí“ (přes spádu pozemku) nebo „dělící čáry“, které oddělují tyto spádové povodí (přes kapku vody princip). Pak dokazují pomocí věty o ekvivalenci svou optimalitu z hlediska minimálních rozlohových lesů. Poté zavedou algoritmus lineárního času pro jejich výpočet. Je vhodné poznamenat, že podobné vlastnosti jsou ověřeny v jiných rámců a navrhovaného algoritmu je nejefektivnější existující algoritmus, a to jak v teorii a praxi.

• obrázek s dvěma značkami (zelená), a Minimální Kostry Lesa vypočítaný na gradientu obrazu.

• Výsledek segmentace pomocí Minimální Kostry Lesa