Povodí (zpracování obrazu) - Watershed (image processing)
Ve studii o zpracování obrazu, a povodí je transformace definovaná na a stupně šedi obraz. Název metaforicky odkazuje na geologický povodí nebo drenážní přepážka, která odděluje sousední povodí. Transformace povodí zachází s obrazem, na kterém pracuje, jako s topografická mapa, přičemž jas každého bodu představuje jeho výšku, a najde čáry, které vedou podél vrcholků hřebenů.
Existují různé technické definice povodí. v grafy, povodí lze definovat na uzlech, na okrajích nebo hybridních čarách na uzlech i hranách. Povodí mohou být také definována v spojité doméně.[1] Existuje také mnoho různých algoritmy vypočítat povodí. Algoritmy povodí se používají při zpracování obrazu primárně pro segmentace účely.
Úleva od gradientové velikosti
Obrázek s gradientní velikostí
Předěl přechodu
Předěl gradientu (reliéf)
Definice
V geologii, a povodí je předěl, který odděluje sousední povodí.
Povodí povodní
Myšlenku představili v roce 1979 S. Beucher a C. Lantuéjoul.[2] Základní myšlenka spočívala v umístění zdroje vody do každého regionálního minima v reliéfu, zaplavení celého reliéfu ze zdrojů a vybudování bariér při setkání různých zdrojů vody. Výsledný soubor bariér představuje povodeň způsobenou povodněmi. Od té doby byla v tomto algoritmu provedena řada vylepšení, souhrnně nazývaných Priority-Flood.[3]
Povodí topografické vzdálenosti
Intuitivně kapka vody dopadající na topografický reliéf teče směrem k „nejbližšímu“ minimu. „Nejbližší“ minimum je to 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.
Rozvržen principem kapky vody
Intuitivně je povodí oddělením regionálních minim, ze kterých může kapka vody stékat dolů k odlišným minimům. Formulace této intuitivní myšlenky byla poskytnuta v [4] pro definování předělu hranově váženého grafu.
Povodí mezi pixely
S. Beucher a F. Meyer představili algoritmickou interpixelovou implementaci metody povodí,[5] vzhledem k následujícímu postupu:
- Označte každé minimum samostatným štítkem. Inicializovat sadu S s označenými uzly.
- Výpis z S uzel X minimální nadmořské výšky F, to znamená F(X) = min {F(y)|y ∈ S}. Atribut štítek X ke každému neoznačenému uzlu y přilehlý k Xa vložte y vS.
- Opakujte krok 2 až do S je prázdný.
Topologické povodí
Předchozí pojmy se zaměřují na povodí, ale ne na vytvořenou oddělovací čáru. Topologické povodí zavedli M. Couprie a G. Bertrand v roce 1997,[6] a má prospěch z následující základní vlastnosti. Funkce W je předělem funkce F kdyby a jen kdyby W ≤ F a W zachovává kontrast mezi regionálními minimy F; kde kontrast mezi dvěma regionálními minimy M1 a M.2 je definována jako minimální nadmořská výška, do které musí člověk vylézt, aby mohl jít z M1 do M2.[7] Efektivní algoritmus je podrobně popsán v článku.[8]
Algoritmus povodí
K použití principu povodí lze použít různé přístupy segmentace obrazu.
- Jako markery lze zvolit místní minima gradientu obrazu, v tomto případě se vytvoří nadsegmentace a druhý krok zahrnuje sloučení oblasti.
- Transformace povodí založená na značce využívá specifické pozice značek, které byly buď explicitně definovány uživatelem, nebo určeny automaticky morfologickými operátory nebo jinými způsoby.
Meyerův zaplavovací algoritmus
Jeden z nejběžnějších povodňových algoritmů představil F. Meyer na počátku 90. let, ačkoli od té doby byla v tomto algoritmu provedena řada vylepšení, souhrnně nazývaných Prioritní povodeň,[9] včetně variant vhodných pro datové sady skládající se z bilionů pixelů.[10]
Algoritmus pracuje na obrazu šedé stupnice. Během postupného zaplavování reliéfu šedé hodnoty se budují povodí s přilehlými povodími. Tento proces zaplavení se provádí na gradientním obrázku, tj. Povodí by se měla objevit podél okrajů. Normálně to povede k nadsegmentaci obrazu, zejména u hlučných obrazových materiálů, např. lékařské CT údaje. Buď musí být obrázek předem zpracován, nebo musí být oblasti sloučeny na základě kritéria podobnosti poté.
- Je vybrána sada značek, pixelů, kde má zaplavení začít. Každá má jiný štítek.
- Sousední pixely každé označené oblasti jsou vloženy do prioritní fronty s úrovní priority odpovídající velikosti přechodu pixelu.
- Pixel s nejvyšší úrovní priority je extrahován z fronty priorit. Pokud sousedé extrahovaného pixelu, kteří již byli označeni, mají stejný štítek, pak je pixel označen jejich štítkem. Všichni neznačení sousedé, kteří ještě nejsou v prioritní frontě, jsou zařazeni do prioritní fronty.
- Opakujte krok 3, dokud nebude prioritní fronta prázdná.
Neoznačené pixely jsou povodí.

Optimální překlenovací lesní algoritmy (povodí)
Povodí jako optimální klenutý les představili Jean Cousty a kol.[12] Stanovují konzistenci těchto povodí: mohou být rovnocenně definovány jejich „povodími“ (prostřednictvím vlastnosti nejstrmějšího klesání) nebo „dělícími čarami“ oddělujícími tyto povodí (principem kapky vody). Poté pomocí věty o ekvivalenci dokazují svou optimálnost, pokud jde o lesy s minimálním rozpětím. Poté zavedou algoritmus lineárního času pro jejich výpočet. Stojí za zmínku, že podobné vlastnosti nejsou ověřeny v jiných rámcích a navrhovaný algoritmus je nejúčinnějším stávajícím algoritmem, a to jak v teorii, tak v praxi.
Obrázek se dvěma značkami (zelený) a s minimálním rozpětím lesa vypočítaným na přechodu obrázku.
Výsledek segmentace podle minimálního rozpětí lesa
Vazby na jiné algoritmy v počítačovém vidění
Řezy grafů
V roce 2007 C. Allène et al.[13] vytvořené odkazy týkající se Řezy grafů do optimálních lesů. Přesněji ukazují, že když je síla vah grafu nad určitým číslem, řez minimalizující energii řezu grafu je řez maximálním lesem.
Lesy s nejkratší cestou
The transformace zalesňování obrázků (IFT) Falcao et al.[14] je postup pro výpočet lesů s nejkratší cestou. Bylo prokázáno J. Coustym a kol.[15] že když ukazatele IFT odpovídají extrémům váhové funkce, je řez vyvolaný lesem povodí.
Náhodný chodec
The náhodný chodec Algoritmus je segmentační algoritmus řešící kombinatorický Dirichletův problém, přizpůsobeno segmentaci obrazu L. Gradym v roce 2006.[16]V roce 2011 C. Couprie et al. dokázal, že když síla vah grafu konverguje k nekonečnu, řez minimalizující energii náhodného chodce je řez maximálním lesem.[17]
Hierarchie
Hierarchická transformace předělu převede výsledek na zobrazení grafu (tj. Jsou určeny sousedské vztahy segmentovaných oblastí) a rekurzivně použije další transformace předělu. Vidět [18] Více podrobností. V roce byla vyvinuta teorie spojující povodí s hierarchickými segmentacemi[19]
Poznámky
- ^ L. Najman a M. Schmitt. Přehrada spojité funkce. In Signal Processing (Special issue on Mathematical Morfhology.), Sv. 38 (1994), strany 99–112
- ^ Workshop Serge Beuchera a Christian Lantuéje o zpracování obrazu, detekci hran a detekci pohybu v reálném čase (1979). http://cmm.ensmp.fr/~beucher/publi/watershed.pdf
- ^ Barnes, R., Lehman, C., Mulla, D., 2014. Prioritní zaplavení: Optimální algoritmus pro plnění depresí a popis povodí pro modely digitálních výšek. Computers & Geosciences 62, 117–127. doi:10.1016 / j.cageo.2013.04.024
- ^ J. Cousty, G. Bertrand, L. Najman a M. Couprie. Řasy povodí: Princip minimálních lesů a princip kapky vody, IEEE Transactions on Pattern Analysis and Machine Intelligence 31 (8) pp. 1362-1374, 2009,
- ^ Serge Beucher a Fernand Meyer. Morfologický přístup k segmentaci: transformace povodí. v Matematická morfologie ve zpracování obrazu (Ed. E. R. Dougherty), strany 433–481 (1993).
- ^ M. Couprie, G. Bertrand. Topologická transformace povodí šedé stupnice. V Proc. ofSPIE Vision Geometry V, svazek 3168, strany 136–146 (1997). http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3.7654&rep=rep1&type=pdf
- ^ G. Bertrand. Na topologických povodích. Journal of Mathematical Imaging and Vision, 22 (2–3), strany 217–230 (2005).
- ^ Michel Couprie, Laurent Najman, Gilles Bertrand. Kvazilineární algoritmy pro topologické povodí. Journal of Mathematical Imaging and Vision, Springer Verlag, 2005, 22 (2-3), str. 231-249.
- ^ Barnes, R., Lehman, C., Mulla, D., 2014. Prioritní zaplavení: Optimální algoritmus pro plnění depresí a popis povodí pro modely digitálních výšek. Computers & Geosciences 62, 117–127. doi:10.1016 / j.cageo.2013.04.024
- ^ Barnes, R., 2016. Paralelní prioritní zaplavení deprese pro digitální výškové modely bilionů buněk na počítačích nebo klastrech. Počítače a geovědy. doi:10.1016 / j.cageo.2016.07.001
- ^ Doerr, F. J. S. a Florence, A. J. (2020). Mikro-XRT analýza obrazu a metodologie strojového učení pro charakterizaci vícesložkových kapslových formulací. International Journal of Pharmaceutics: X, 2, 100041. https://doi.org/10.1016/j.ijpx.2020.100041
- ^ Jean Cousty, Gilles Bertrand, Laurent Najman a Michel Couprie. Řasy povodí: Princip minimálních lesů a princip kapky vody. Transakce IEEE na analýze vzorů a strojové inteligenci. 31 (8). Srpen 2009. str. 1362–1374.
- ^ Cédric Allène, Jean-Yves Audibert, Michel Couprie a Renaud Keriven: "Některé vazby mezi minimálními řezy, optimálními lesy a povodími ", Image and Vision Computing, 2009.
- ^ Falcao, A.X. Stolfi, J. de Alencar Lotufo, R.: "Transformace zalesňování obrazu: teorie, algoritmy a aplikace ", In PAMI, 2004
- ^ Jean Cousty, Gilles Bertrand, Laurent Najman a Michel Couprie. Řasy povodí: řídnutí, lesy s nejkratší cestou a topologické povodí. Transakce IEEE na analýze vzorů a strojové inteligenci. 32 (5). 2010. str. 925–939.
- ^ Grady, L .: "Náhodné procházky pro segmentaci obrazu ". PAMI, 2006
- ^ Camille Couprie, Leo Grady, Laurent Najman a Hugues Talbot, “Power Watersheds: A Unifying Graph-Based Optimization Framework ”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 33, No. 7, pp. 1384-1399, červenec 2011
- ^ Laurent Najman, Michel Schmitt. Geodesic Saliency of Watershed Contours and Hierarchical Segmentation. Transakce IEEE na analýze vzorů a strojové inteligenci, Institute of Electrical and Electronics Engineers, 1996, 18 (12), str. 1163-1173.
- ^ Laurent Najman. O ekvivalenci mezi hierarchickými segmentacemi a ultrametrickými povodími. Journal of Mathematical Imaging and Vision, Springer Verlag, 2011, 40 (3), str. 231-247.
Reference
- Fernand Meyer. Un Algoritmus Optimal pour la ligne de partage des eaux. Dans 8mě Congrès de reconnaissance des formes et intelligence artificielle, Sv. 2 (1991), strany 847–857, Lyon, Francie.
- Luc Vincent a Pierre Soille. Povodí v digitálních prostorech: efektivní algoritmus založený na ponorných simulacích. v Transakce IEEE na analýze vzorů a strojové inteligenci, sv. 13, Num. 6 (1991), strany 583–598.
- L. Najman a M. Schmitt. Geodetický výběžek povodí a hierarchická segmentace. v Transakce IEEE na analýze vzorů a strojové inteligenci, Sv. 18, Num. 12 (1996), strany 1163–1173.
- J.B.T.M. Roerdink a A. Meijster. Povodí transformace: definice, algoritmy a strategie paralelizace. v Fundamenta Informaticae 41 (2000), s. 187–228.
- Laurent Najman, Michel Couprie a Gilles Bertrand. Povodí, mozaiky a paradigma vzniku. v Diskrétní aplikovaná matematika, Sv. 147, Num. 2–3 (2005), strany 301–324.
externí odkazy
- The Watershed Transformation s animacemi algoritmu povodí.
- Topologická povodí transformace s referáty, přednáškami a zdrojovým kódem.
- Open-source povodí plugin pro Obrázek J..
- Sada nástrojů topologie (2D a 3D povodí založené na Morseův komplex )