Matematická morfologie - Mathematical morphology

Tvar (modře) a jeho morfologická dilatace (zeleně) a eroze (žlutě) strukturovaným prvkem ve tvaru kosočtverce.

Matematická morfologie (MM) je teorie a technika pro analýzu a zpracování geometrický struktury, založené na teorie množin, teorie mřížky, topologie, a náhodné funkce. MM se nejčastěji používá digitální obrázky, ale lze jej použít i na grafy, povrchové sítě, pevné látky a mnoho dalších prostorových struktur.

Topologické a geometrický kontinuální -prostorové koncepty, jako je velikost, tvar, konvexnost, připojení, a geodetická vzdálenost, byly zavedeny MM na kontinuální i diskrétní prostory. MM je také základem morfologické zpracování obrazu, který se skládá ze sady operátorů, které transformují obrázky podle výše uvedených charakterizací.

Základní morfologické operátory jsou eroze, dilatace, otevírací a zavírání.

MM byl původně vyvinut pro binární obrazy, a později byla rozšířena na stupně šedi funkce a obrázky. Následné zobecnění na kompletní mříže je dnes široce přijímán jako teoretický základ MM.

Dějiny

Od 60. let 20. století byly v konkrétních komunitách diskutovány a používány nejrůznější schémata pro nelineární zpracování obrázků. Příkladem původně populárním ve vědách o Zemi a životním prostředí je matematická morfologie založená na „dilataci“ dat sestávajících z 0 a 1 se „strukturujícím prvkem“ σ podle Sign [ListConvolve [σ, data, 1, 0]] (jako a dvojí působení „eroze“).^[1] Matematická morfologie byla vyvinuta v roce 1964 společnou prací Georges Matheron a Jean Serra, na École des Mines de Paris, Francie. Matheron dohlížel na PhD teze Serry, věnovaný kvantifikaci minerálních charakteristik z tenkého průřezy, a tato práce vyústila v nový praktický přístup, stejně jako teoretický pokrok v integrální geometrie a topologie.

V roce 1968 Center de Morphologie Mathématique byla založena École des Mines de Paris v Paříži Fontainebleau, Francie, vedená Matheronem a Serrou.

Během zbytku šedesátých a většiny sedmdesátých let se MM v zásadě zabýval binární obrazy, považováno za sady a vygeneroval velký počet binární operátory a techniky: Hit-and-miss transformace, dilatace, eroze, otevírací, zavírání, granulometrie, ředění, skeletonizace, konečná eroze, podmíněné půlení, a další. Byl také vyvinut náhodný přístup založený na nových obrazových modelech. Většina prací v tomto období byla vyvinuta ve Fontainebleau.

Od poloviny 70. do poloviny 80. let byla MM zobecněna na stupně šedi funkce a snímky také. Kromě rozšíření hlavních konceptů (jako je dilatace, eroze atd.) Na funkce, tato generalizace přinesla nové operátory, jako například morfologické přechody, cylindrová transformace a Povodí (MM je hlavní segmentace přístup).

V 80. a 90. letech získala MM širší uznání, protože výzkumná střediska v několika zemích začaly tuto metodu přijímat a zkoumat. MM začal být aplikován na velké množství problémů se zobrazováním a aplikací.

V roce 1986 Serra dále zobecnila MM, tentokrát na teoretický rámec založený na kompletní mříže. Toto zobecnění přineslo teorii flexibilitu a umožnilo její použití v mnohem větším počtu struktur, včetně barevných obrázků, videa, grafy, oka Matheron a Serra zároveň formulovali morfologickou teorii filtrování, založený na novém mřížkovém rámci.

V 90. a 2000 letech došlo také k dalšímu teoretickému pokroku, včetně konceptů připojení a nivelace.

V roce 1993 se konalo první mezinárodní symposium o matematické morfologii (ISMM) Barcelona, Španělsko. Od té doby se ISMM organizují každé 2–3 roky: Fontainebleau, Francie (1994); Atlanta, USA (1996); Amsterdam, Holandsko (1998); Palo Alto, CA, USA (2000); Sydney, Austrálie (2002); Paříž, Francie (2005); Rio de Janeiro, Brazílie (2007); Groningen, Holandsko (2009); Intra (Verbania ), Itálie (2011); Uppsala, Švédsko (2013); Reykjavík, Island (2015); a Fontainebleau, Francie (2017).

Reference

„Úvod“, Pierre Soille, v (Serra et al. (Eds.) 1994 ), str. 1-4.
„Příloha A:„ Centre de Morphologie Mathématique “, přehled“ Jean Serry, v (Serra et al. (Eds.) 1994 ), str. 369-374.
„Předmluva“ v (Ronse et al. (Eds.) 2005 )

Binární morfologie

V binární morfologii je obraz zobrazen jako a podmnožina a Euklidovský prostor ${ displaystyle mathbb {R} ^ {d}}$ nebo celočíselná mřížka ${ displaystyle mathbb {Z} ^ {d}}$ , pro nějakou dimenzi d.

Strukturující prvek

Základní myšlenkou v binární morfologii je zkoumat obraz s jednoduchým předdefinovaným tvarem a vyvozovat závěry o tom, jak tento tvar zapadá nebo chybí tvary v obraze. Tato jednoduchá „sonda“ se nazývá strukturní prvek, a je sám o sobě binárním obrazem (tj. podmnožinou prostoru nebo mřížky).

Zde je několik příkladů široce používaných strukturovacích prvků (označených B):

Nechat ${ displaystyle E = mathbb {R} ^ {2}}$ ; B je otevřený disk o poloměru r, se středem na počátek.
Nechat ${ displaystyle E = mathbb {Z} ^ {2}}$ ; B je čtverec 3 × 3, to znamená, B = {(−1, −1), (−1, 0), (−1, 1), (0, −1), (0, 0), (0, 1), (1, −1), (1, 0), (1, 1)}.
Nechat ${ displaystyle E = mathbb {Z} ^ {2}}$ ; B je "kříž" daný B = {(−1, 0), (0, −1), (0, 0), (0, 1), (1, 0)}.

Základní operátoři

Základní operace jsou posunově invariantní (překlad neměnný ) operátoři silně spjatí s Minkowského doplnění.

Nechat E být euklidovský prostor nebo celočíselná mřížka a A binární obraz v E.

Eroze

Eroze tmavomodrého čtverce diskem, jejímž výsledkem je světle modrý čtverec.

The eroze binárního obrazu A strukturujícím prvkem B je definováno

{ displaystyle A ominus B = {z v E | B_ {z} subseteq A },}

kde B_z je překlad B vektorem z, tj., ${ displaystyle B_ {z} = {b + z střední b v B }}$ , ${ displaystyle forall z in E}$ .

Když strukturující prvek B má střed (např. B je disk nebo čtverec) a toto středisko je umístěno na počátku E, pak eroze A podle B lze chápat jako místo bodů dosažených středem B když B pohybuje se dovnitř A. Například eroze čtverce ze strany 10, vystředěného na počátek, diskem o poloměru 2, rovněž vystředěným na počátek, je čtverec ze strany 6 vystředěný na počátek.

Eroze A podle B je také dán výrazem ${ displaystyle A ominus B = bigcap _ {b v B} A _ {- b}}$ .

Příklad aplikace: Předpokládejme, že jsme obdrželi fax temné fotokopie. Všechno vypadá, jako by to bylo psáno perem, které krvácí. Proces eroze umožní zeslabení silnějších čar a detekci díry uvnitř písmene „o“.

Dilatace

Dilatace tmavě modrého čtverce diskem, což vedlo k světle modrému čtverci se zaoblenými rohy.

The dilatace z A strukturujícím prvkem B je definováno

{ displaystyle A oplus B = bigcup _ {b v B} A_ {b}.}

Dilatace je komutativní, také daná ${ displaystyle A oplus B = B oplus A = bigcup _ {a in A} B_ {a}}$ .

Li B má centrum původu, jako dříve, pak dilataci A podle B lze chápat jako místo bodů, na které se vztahuje B když střed B pohybuje se dovnitř A. Ve výše uvedeném příkladu je dilatace čtverce strany 10 diskem o poloměru 2 čtvercem strany 14 se zaoblenými rohy, vystředěnými na počátku. Poloměr zaoblených rohů je 2.

Dilataci lze také získat pomocí ${ displaystyle A oplus B = {z v E mid (B ^ {s}) _ {z} cap A neq varnothing }}$ , kde B^s označuje symetrický z B, to znamená, ${ displaystyle B ^ {s} = {x v E mid -x v B }}$ .

Příklad aplikace: dilatace je duální operace eroze. Čísla, která jsou velmi lehce nakreslena, se při rozšíření zvětší. Nejjednodušší způsob, jak to popsat, je představit si, že stejný fax / text je psán silnějším perem.

Otevírací

Otevření tmavě modrého čtverce diskem, což má za následek světle modrý čtverec se zaoblenými rohy.

The otevírací z A podle B se získá erozí A podle B, následovaná dilatací výsledného obrazu pomocí B:

{ displaystyle A circ B = (A ominus B) oplus B.}

Otvor je také dán ${ displaystyle A circ B = bigcup _ {B_ {x} subseteq A} B_ {x}}$ , což znamená, že se jedná o místo překladů strukturujícího prvku B uvnitř obrázku A. V případě čtverce strany 10 a disku o poloměru 2 jako strukturního prvku je otvorem čtverec strany 10 se zaoblenými rohy, kde poloměr rohu je 2.

Příklad aplikace: Předpokládejme, že někdo napsal poznámku na nenasákavý papír a že psaní vypadá, jako by mu všude rostly drobné chlupaté kořeny. Otevření v podstatě odstraní vnější drobné „vlasové“ netěsnosti a obnoví text. Vedlejším efektem je, že to všechno zaokrouhluje. Ostré hrany začnou mizet.

Zavírání

Uzavření tmavomodrého tvaru (spojení dvou čtverců) diskem, což má za následek spojení tmavomodrého tvaru a světle modrých oblastí.

The zavírání z A podle B se získá rozšířením A podle B, následovaná erozí výsledné struktury o B:

{ displaystyle A kulka B = (A oplus B) ominus B.}

Uzávěr lze také získat pomocí ${ displaystyle A bullet B = (A ^ {c} circ B ^ {s}) ^ {c}}$ , kde X^C označuje doplněk z X ve vztahu k E (to znamená, ${ displaystyle X ^ {c} = {x v E mid x notin X }}$ ). Výše uvedené znamená, že uzavření je doplňkem lokace překladů symetrie strukturujícího prvku mimo obraz A.

Vlastnosti základních operátorů

Zde jsou některé vlastnosti základních binárních morfologických operátorů (dilatace, eroze, otevírání a zavírání):

Oni jsou překlad neměnný.
Oni jsou vzrůstající, tedy pokud ${ displaystyle A subseteq C}$ , pak ${ displaystyle A oplus B subseteq C oplus B}$ , a ${ displaystyle A ominus B subseteq C ominus B}$ , atd.
Dilatace je komutativní: ${ displaystyle A oplus B = B oplus A}$ .
Pokud je původ E patří do strukturujícího prvku B, pak ${ Displaystyle A ominus B subseteq A circ B subseteq A subseteq A kulka B subseteq A oplus B}$ .
Dilatace je asociativní, tj., ${ displaystyle (A oplus B) oplus C = A oplus (B oplus C)}$ . Kromě toho eroze uspokojuje ${ displaystyle (A ominus B) ominus C = A ominus (B oplus C)}$ .
Eroze a dilatace uspokojují dualitu ${ displaystyle A oplus B = (A ^ {c} ominus B ^ {s}) ^ {c}}$ .
Otevírání a zavírání uspokojí dualitu ${ displaystyle A bullet B = (A ^ {c} circ B ^ {s}) ^ {c}}$ .
Dilatace je distribuční přes nastavit unii
Eroze je distribuční přes nastavit křižovatku
Dilatace je a pseudo-inverzní eroze a naopak v následujícím smyslu: ${ displaystyle A subseteq (C ominus B)}$ kdyby a jen kdyby ${ displaystyle (A oplus B) subseteq C}$ .
Otevírání a zavírání jsou idempotentní.
Otevření je anti-rozsáhlý, tj., ${ displaystyle A circ B subseteq A}$ , zatímco uzávěrka je rozsáhlý, tj., ${ displaystyle A subseteq A odrážka B}$ .

Ostatní operátoři a nástroje

Morfologie ve stupních šedi

Přehrada přechodu srdečního obrazu

v stupně šedi morfologie, obrázky jsou funkce mapování a Euklidovský prostor nebo mřížka E do ${ displaystyle mathbb {R} pohár { infty, - infty }}$ , kde ${ displaystyle mathbb {R}}$ je sada realita, ${ displaystyle infty}$ je prvek větší než jakékoli reálné číslo a ${ displaystyle - infty}$ je prvek menší než jakékoli skutečné číslo.

Strukturovací prvky ve stupních šedi jsou také funkce stejného formátu, nazývané „strukturovací funkce“.

Označení obrázku pomocí F(X) a strukturovací funkce pomocí b(X), dilatace ve stupních šedi F podle b darováno

{ displaystyle (f oplus b) (x) = sup _ {y v E} [f (y) + b (x-y)],}

kde "sup" označuje supremum.

Podobně eroze F podle b darováno

{ displaystyle (f ominus b) (x) = inf _ {y v E} [f (y) -b (y-x)],}

kde "inf" označuje infimum.

Stejně jako v binární morfologii je otevírání a zavírání dáno příslušně

{ Displaystyle f circ b = (f ominus b) oplus b,}

{ Displaystyle f bullet b = (f oplus b) ominus b.}

Funkce plochého strukturování

V morfologických aplikacích je běžné používat ploché strukturní prvky. Funkce ploché strukturování jsou funkce b(X) ve formě

{ displaystyle b (x) = { begin {případů} 0, & x v B, - infty & { text {jinak}}, end {případů}}}

kde ${ displaystyle B subseteq E}$ .

V tomto případě je dilatace a eroze značně zjednodušena a dána příslušně

{ displaystyle (f oplus b) (x) = sup _ {z v B ^ {s}} f (x + z),}

{ displaystyle (f ominus b) (x) = inf _ {z v B} f (x + z).}

V ohraničeném diskrétním případě (E je mřížka a B je ohraničený), supremum a infimum operátory lze nahradit maximum a minimální. Dilatace a eroze jsou tedy konkrétními případy statistika objednávek filtry, přičemž dilatace vrací maximální hodnotu v pohybujícím se okně (symetrická podpora strukturovací funkce B) a eroze vrací minimální hodnotu v pohyblivém okně B.

V případě plochého strukturního prvku závisí morfologické operátory pouze na relativním uspořádání pixel hodnoty, bez ohledu na jejich číselné hodnoty, a proto jsou zvláště vhodné pro zpracování binární obrazy a obrázky ve stupních šedi jehož funkce přenosu světla není známo.

Ostatní operátoři a nástroje

Kombinací těchto operátorů lze získat algoritmy pro mnoho úloh zpracování obrazu, například detekce funkcí, segmentace obrazu, doostření obrazu, filtrování obrazu, a klasifikace Podél této linie by se mělo také podívat do Kontinuální morfologie ^[2]

Matematická morfologie na úplných mřížkách

Kompletní svazy jsou částečně objednané sady, kde má každá podmnožina infimum a a supremum. Obsahuje zejména a nejmenší prvek a a největší prvek (označovaný také jako „vesmír“).

Přídavky (dilatace a eroze)

Nechat ${ displaystyle (L, leq)}$ být úplnou mřížkou, se symbolem infimum a supremum ${ displaystyle klín}$ a ${ displaystyle vee}$ , resp. Jeho vesmír a nejmenší prvek jsou symbolizovány U a ${ displaystyle emptyset}$ , resp. Navíc nechte ${ displaystyle {X_ {i} }}$ být sbírkou prvků z L.

Dilatací je libovolný operátor ${ displaystyle delta dvojtečka L pravá šipka L}$ který se distribuuje nad supremum a zachovává nejmenší prvek. Tj.:

${ displaystyle bigvee _ {i} delta (X_ {i}) = delta left ( bigvee _ {i} X_ {i} right)}$ ,
${ displaystyle delta ( emptyset) = emptyset}$ .

Erozí je každý operátor ${ displaystyle varepsilon dvojtečka L pravá šipka L}$ který se distribuuje po infimu a chrání vesmír. Tj.:

${ displaystyle bigwedge _ {i} varepsilon (X_ {i}) = varepsilon left ( bigwedge _ {i} X_ {i} right)}$ ,
${ displaystyle varepsilon (U) = U}$ .

Vznikají dilatace a eroze Galoisova spojení. To znamená pro každou dilataci ${ displaystyle delta}$ je zde jediná eroze ${ displaystyle varepsilon}$ to uspokojuje

{ displaystyle X leq varepsilon (Y) Leftrightarrow delta (X) leq Y}

pro všechny ${ displaystyle X, Y v L}$ .

Podobně pro každou erozi existuje jedna a pouze jedna dilatace splňující výše uvedené spojení.

Navíc pokud spojení splní dva operátoři, pak ${ displaystyle delta}$ musí to být dilatace a ${ displaystyle varepsilon}$ eroze.

Dvojice erozí a dilatací splňujících výše uvedené spojení se nazývají „adjunkce“ a o erozi se říká, že je to eroze adjunktu dilatace, a naopak.

Otevírání a zavírání

Pro každou adjunkci ${ displaystyle ( varepsilon, delta)}$ , morfologický otvor ${ displaystyle gamma dvojtečka L až L}$ a morfologické uzavření ${ displaystyle phi dvojtečka L až L}$ jsou definovány takto:

{ displaystyle gamma = delta varepsilon,}

{ displaystyle phi = varepsilon delta.}

Morfologické otevírání a zavírání jsou zvláštní případy algebraické otevření (nebo jednoduše otevření) a algebraické uzavření (nebo jednoduše zavírání). Algebraické otvory jsou operátory v L které jsou idempotentní, rostoucí a antirozsáhlé. Algebraické uzávěry jsou operátory v L které jsou idempotentní, rostoucí a rozsáhlé.

Zvláštní případy

Binární morfologie je zvláštním případem mřížkové morfologie, kde L je napájecí sada z E (Euklidovský prostor nebo mřížka), to znamená, L je sada všech podskupin E, a ${ displaystyle leq}$ je nastavit zařazení. V tomto případě je infimum nastavit křižovatku a supremum je nastavit unii.

Podobně morfologie ve stupních šedi je dalším konkrétním případem, kde L je sada mapování funkcí E do ${ displaystyle mathbb {R} pohár { infty, - infty }}$ , a ${ displaystyle leq}$ , ${ displaystyle vee}$ , a ${ displaystyle klín}$ , jsou bodové pořadí, supremum a infimum. To je, je F a G jsou funkce v L, pak ${ displaystyle f leq g}$ kdyby a jen kdyby ${ displaystyle f (x) leq g (x), forall x in E}$ ; infimum ${ displaystyle f klín g}$ darováno ${ displaystyle (f klín g) (x) = f (x) klín g (x)}$ ; a supremum ${ displaystyle f vee g}$ darováno ${ Displaystyle (f vee g) (x) = f (x) vee g (x)}$ .

Viz také

H-maxima transformace

Poznámky

^ Wolfram, Stephen (2002). Nový druh vědy. Wolfram Media, Inc. str.1077. ISBN 1-57955-008-8.
^ G. Sapiro, R. Kimmel, D. Shaked, B. Kimia a A. M. Bruckstein. Implementace kontinuální morfologie prostřednictvím vývoje křivky. Pattern Recognition, 26 (9): 1363–1372, 1993.

Reference

Analýza obrazu a matematická morfologie Jean Serra, ISBN 0-12-637240-3 (1982)
Analýza obrazu a matematická morfologie, svazek 2: Teoretické pokroky Jean Serra, ISBN 0-12-637241-1 (1988)
Úvod do morfologického zpracování obrazu Edward R. Dougherty, ISBN 0-8194-0845-X (1992)
Morfologická analýza obrazu; Zásady a aplikace Pierre Soille, ISBN 3-540-65671-5 (1999), 2. vydání (2003)
Matematická morfologie a její aplikace na zpracování signálu, J. Serra a Ph. Salembier (ed.), Sborník z 1. mezinárodního semináře o matematické morfologii a jeho aplikacích pro zpracování signálu (ISMM'93), ISBN 84-7653-271-7 (1993)
Matematická morfologie a její aplikace na zpracování obrazu, J. Serra a P. Soille (ed.), Sborník z 2. mezinárodního sympozia o matematické morfologii (ISMM'94), ISBN 0-7923-3093-5 (1994)
Matematická morfologie a její aplikace na zpracování obrazu a signálu, Henk J.A.M. Heijmans a Jos B.T.M. Roerdink (ed.), Sborník ze 4. mezinárodního sympozia o matematické morfologii (ISMM'98), ISBN 0-7923-5133-9 (1998)
Matematická morfologie: 40 let dále, Christian Ronse, Laurent Najman a Etienne Decencière (vyd.), ISBN 1-4020-3442-3 (2005)
Matematická morfologie a její aplikace na zpracování signálu a obrazu, Gerald J.F. Banon, Junior Barrera, Ulisses M. Braga-Neto (ed.), Sborník z 8. mezinárodního sympozia o matematické morfologii (ISMM'07), ISBN 978-85-17-00032-4 (2007)
Matematická morfologie: od teorie k aplikacím, Laurent Najman a Hugues Talbot (Eds). ISTE-Wiley. ISBN 978-1-84821-215-2. (520 stran) Červen 2010

externí odkazy

Online kurz matematické morfologie, Jean Serra (v angličtině, francouzštině a španělštině)
Centrum matematické morfologie, Paris School of Mines
Dějiny matematické morfologie, Georges Matheron a Jean Serra
Morphology Digest, zpravodaj o matematické morfologii, Pierre Soille
Přednášky o zpracování obrazu: Sbírka 18 přednášek ve formátu pdf z Vanderbiltovy univerzity. Přednášky 16-18 jsou o matematické morfologii autor: Alan Peters
Matematická morfologie; z přednášek o počítačovém vidění tím, že Robyn Owens
Zdarma knihovna optimalizovaná pro zpracování obrazu SIMD
Demonstrace appletu Java
FILTRY: bezplatná knihovna pro zpracování obrázků s otevřeným zdrojovým kódem
Rychlé morfologické eroze, dilatace, otvory a uzávěry
Morfologická analýza neuronů pomocí Matlabu

[1] Wolfram, Stephen (2002). Nový druh vědy. Wolfram Media, Inc. str.1077. ISBN 1-57955-008-8.

[2] G. Sapiro, R. Kimmel, D. Shaked, B. Kimia a A. M. Bruckstein. Implementace kontinuální morfologie prostřednictvím vývoje křivky. Pattern Recognition, 26 (9): 1363–1372, 1993.

[1]

[2]