Matematická morfologie - Mathematical morphology

Tvar (modře) a jeho morfologická dilatace (zeleně) a eroze (žlutě) strukturujícím prvkem ve tvaru diamantu.

Matematická morfologie ( MM ) je teorie a technika pro analýzu a zpracování geometrických struktur, založená na teorii množin , teorii mřížky , topologii a náhodných funkcích . MM se nejčastěji používá na digitální obrázky , ale lze jej použít také na grafech , povrchových sítích , tělesech a mnoha dalších prostorových strukturách.

Topologické a geometrické koncepty spojitého prostoru, jako je velikost, tvar , konvexita , konektivita a geodetická vzdálenost , byly zavedeny MM na spojitých i diskrétních prostorech . MM je také základem morfologického zpracování obrazu , které se skládá ze sady operátorů, které transformují obrázky podle výše uvedených charakteristik.

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

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

Dějiny

Matematická morfologie byla vyvinuta v roce 1964 společnou prací Georgese Matherona a Jeana Serry v École des Mines de Paris ve Francii . Matheron dohlížel na disertační práci v Serře, věnovanou kvantifikaci minerálních charakteristik z tenkých průřezů , a tato práce vyústila v nový praktický přístup i teoretický pokrok v integrální geometrii a topologii .

V roce 1968 založilo Centre de Morphologie Mathématique École des Mines de Paris ve francouzském Fontainebleau vedené Matheronem a Serrou.

Během zbytku šedesátých a většiny sedmdesátých let se MM zabýval v podstatě binárními obrazy , považovanými za sady , a generoval velké množství binárních operátorů a technik: transformace Hit-or-Miss , dilatace , eroze , otevírání , zavírání , granulometrie , ředění , skeletonizace , konečná eroze , podmíněný bisektor a další. Byl také vyvinut náhodný přístup založený na nových modelech obrazu. Většina práce v tomto období byla vyvinuta ve Fontainebleau.

Od poloviny 70. do poloviny 80. let byla MM generalizována na funkce a obrázky ve stupních šedi . Kromě rozšíření hlavních konceptů (jako je dilatace, eroze atd.) Na funkce přinesla tato generalizace nové operátory, jako jsou morfologické přechody , transformace typu top-hat a Watershed (hlavní segmentační přístup MM ).

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

V roce 1986 Serra dále zobecnila MM, tentokrát na teoretický rámec založený na úplných mřížích . Toto zobecnění přineslo teorii flexibilitu, umožnilo její aplikaci na mnohem větší počet struktur, včetně barevných obrázků, videa, grafů , sítí atd. Současně Matheron a Serra také formulovali teorii morfologického filtrování založenou na nový příhradový rámec.

V devadesátých a dvacátých letech došlo také k dalšímu teoretickému pokroku, včetně konceptů připojení a vyrovnání .

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

Reference

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

Binární morfologie

V binárním morfologii, obraz je vnímán jako podmnožina části euklidovském prostoru nebo celé číslo sítě , pro některé rozměr d . ${\ displaystyle \ mathbb {R} ^{d}}$${\ displaystyle \ mathbb {Z} ^{d}}$

Strukturační prvek

Základní myšlenkou binární morfologie je prozkoumat obraz s jednoduchým, předem definovaným tvarem a vyvodit závěry o tom, jak tento tvar odpovídá tvarům v obraze nebo jim chybí. Tato jednoduchá „sonda“ se nazývá strukturující prvek a sama je binárním obrazem (tj. Podmnožinou prostoru nebo mřížky).

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

• Nechte ; B je otevřený disk o poloměru r se středem na počátku.${\ Displaystyle E = \ mathbb {R} ^{2}}$
• Nechte ; B je čtverec 3 × 3, tj. B = {(−1, −1), (−1, 0), (−1, 1), (0, −1), (0, 0), ( 0, 1), (1, −1), (1, 0), (1, 1)}.${\ Displaystyle E = \ mathbb {Z} ^{2}}$
• Nechte ; B je „kříž“ daný vztahem B = {(−1, 0), (0, −1), (0, 0), (0, 1), (1, 0)}.${\ Displaystyle E = \ mathbb {Z} ^{2}}$

Základní operátory

Základní operace jsou posunově invariantní ( translačně invariantní ) operátory silně související s přidáním Minkowski .

Nechť E být Euclidean prostor nebo celé číslo grid a binární obraz v E .

Eroze

Eroze tmavomodrého čtverce diskem, což má za následek světle modrý čtverec.

Eroze binárního obrazu A podle strukturování prvek B je definován

${\ Displaystyle A \ ominus B = \ {z \ in E | B_ {z} \ subseteq A \},}$

kde B _z je překlad B vektorem z , tj. , . ${\ Displaystyle B_ {z} = \ {b+z \ mid b \ in B \}}$${\ Displaystyle \ forall z \ in E}$

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

Eroze A o B je také dána výrazem . ${\ Displaystyle A \ ominus B = \ bigcap _ {b \ in B} A _ {-b}}$

Příklad aplikace: Předpokládejme, že jsme obdrželi fax tmavé fotokopie. Všechno vypadá, jako by to bylo psáno perem, které krvácí. Proces eroze umožní tlustším čarám ztenčit a detekovat díru uvnitř písmene „o“.

Dilatace

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

Dilatace z A podle strukturování prvek B je definován

${\ Displaystyle A \ oplus B = \ bigcup _ {b \ in B} A_ {b}.}$

Rozšíření je komutativní, také dané . ${\ Displaystyle A \ oplus B = B \ oplus A = \ bigcup _ {a \ v A} B_ {a}}$

Pokud B má střed o původu, stejně jako dříve, pak dilatace A od B, lze chápat jako těžiště bodů, které jsou B , když je střed B se pohybuje uvnitř A . Ve výše uvedeném příkladu je rozšíření čtverce strany 10 o disk o poloměru 2 čtverec strany 14 se zaoblenými rohy, vystředěnými na počátku. Poloměr zaoblených rohů je 2.

Dilatace lze také získat , kde B- ^s označuje symetrické z B , která je, . ${\ Displaystyle A \ oplus B = \ {z \ in E \ mid (B^{s}) _ {z} \ cap A \ neq \ varnothing \}}$${\ Displaystyle B^{s} = \ {x \ in E \ mid -x \ in B \}}$

Příklad aplikace: dilatace je dvojí operací eroze. Postavy, které jsou velmi lehce nakreslené, při „dilataci“ zesílí. Nejjednodušší způsob, jak to popsat, je představit si stejný fax/text napsaný silnějším perem.

Otevírací

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

Otevření z A od B se získá erozí A u B , následované dilatací výsledného obrazu podle B :

${\ Displaystyle A \ circ B = (A \ ominus B) \ oplus B.}$

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

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

Zavírání

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

Zavírání z A od B se získá dilatací A u B , následovaný erozí výsledné struktuře podle B :

${\ Displaystyle A \ bullet B = (A \ oplus B) \ ominus B.}$

Uzavírací lze také získat , kde X ^c označuje doplněk z X vzhledem k E (tj ). Z výše uvedeného vyplývá, že uzavírací je komplementární lokusu překladů symetrického strukturačního prvku vně obrazu A . ${\ Displaystyle A \ bullet B = (A^{c} \ circle B^{s})^{c}}$${\ Displaystyle X^{c} = \ {x \ in E \ mid x \ notin X \}}$

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í):

• Jsou překladově neměnné .
• Jsou zvyšuje , to znamená, že v případě , poté , a , atd.${\ displaystyle A \ subseteq C}$${\ Displaystyle A \ oplus B \ subseteq C \ oplus B}$${\ Displaystyle A \ ominus B \ subseteq C \ ominus B}$
• Dilatace je komutativní : .${\ Displaystyle A \ oplus B = B \ oplus A}$
• Pokud původ E patří strukturujícímu prvku B , pak .${\ Displaystyle A \ ominus B \ subseteq A \ circle B \ subseteq A \ subseteq A \ bullet B \ subseteq A \ oplus B}$
• Rozšíření je asociativní , tj . Navíc eroze uspokojuje .${\ Displaystyle (A \ oplus B) \ oplus C = A \ oplus (B \ oplus C)}$${\ 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í uspokojuje dualitu .${\ Displaystyle A \ bullet B = (A^{c} \ circle B^{s})^{c}}$
• Dilatace je distribuční přes set union
• Eroze je distribuční přes nastavenou křižovatku
• Dilatace je pseudo-inverzí eroze a naopak v následujícím smyslu: pokud a pouze pokud .${\ Displaystyle A \ subseteq (C \ ominus B)}$${\ Displaystyle (A \ oplus B) \ subseteq C}$
• Otevírání a zavírání je idempotentní .
• Otevírání je protisměrné , tj . Zatímco zavírání je rozsáhlé , tj .${\ Displaystyle A \ circ B \ subseteq A}$${\ Displaystyle A \ subseteq A \ bullet B}$

Ostatní operátoři a nástroje

• Transformace hit-or-miss
• Transformace prořezávání
• Morfologická kostra
• Filtrování rekonstrukcí
• Dokonalé eroze a podmíněné úsečky
• Granulometrie
• Funkce geodetické vzdálenosti

Morfologie ve stupních šedi

Rozvod z gradientu srdečního obrazu

V morfologii šedé jsou obrázky funkcemi mapujícími euklidovský prostor nebo mřížku E do , kde je množina reálů , je prvek větší než jakékoli skutečné číslo a je prvek menší než jakékoli skutečné číslo. ${\ Displaystyle \ mathbb {R} \ cup \ {\ infty,-\ infty \}}$${\ displaystyle \ mathbb {R}}$${\ displaystyle \ infty}$${\ displaystyle -\ infty}$

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

Označení obrázku f ( x ) a strukturační funkce b ( x ), dilatace f ve stupních šedi f podle b je dána vztahem

${\ Displaystyle (f \ oplus b) (x) = \ sup _ {y \ in E} [f (y)+b (xy)],}$

kde „sup“ označuje supremum .

Podobně eroze f o b je dána vztahem

${\ Displaystyle (f \ ominus b) (x) = \ inf _ {y \ in E} [f (y) -b (yx)],}$

kde „inf“ označuje infimum .

Stejně jako v binární morfologii jsou otevírání a zavírání dány znakem

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

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

Ploché strukturační funkce

V morfologických aplikacích je běžné používat ploché strukturační prvky. Ploché strukturovací funkce jsou funkce b ( x ) ve formuláři

${\ Displaystyle b (x) = {\ begin {cases} 0, & x \ in B, \\-\ infty & {\ text {else}}, \ end {cases}}}$

kde . ${\ Displaystyle B \ subseteq E}$

V tomto případě jsou dilatace a eroze značně zjednodušeny, respektive dány

${\ Displaystyle (f \ oplus b) (x) = \ sup _ {z \ in B^{s}} f (x+z),}$

${\ Displaystyle (f \ ominus b) (x) = \ inf _ {z \ in B} f (x+z).}$

V ohraničeném, diskrétním případě ( E je mřížka a B je ohraničeno) lze supremum a infimum operátory nahradit maximem a minimem . Tak, dilatace a eroze jsou konkrétní případy pořadí statistiky filtrů, s dilatací vrací maximální hodnotu v pohyblivém okně (symetrický strukturačního funkce nosné B ), a eroze vrací minimální hodnotu v pohyblivém okně B .

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

Ostatní operátoři a nástroje

• Morfologické gradienty
• Celotělová transformace
• Algoritmus povodí

Kombinací těchto operátorů lze získat algoritmy pro mnoho úloh zpracování obrazu, jako je například detekce zahrnuje , segmentace obrazu , obraz broušení , filtrace obrazu a klasifikace . Podél této linie by se měl člověk také podívat do souvislé morfologie

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

Kompletní mříže jsou částečně uspořádané sady , kde každá podmnožina má infimum a supremum . Zejména obsahuje nejmenší prvek a největší prvek (označovaný také jako „vesmír“).

Doplňky (dilatace a eroze)

Nechť je úplná mříž, s infimum a supremum symbolizovanou a , resp. Jeho vesmír a nejmenší prvek jsou symbolizovány U a . Navíc, ať se sbírka prvků z L . ${\ displaystyle (L, \ leq)}$${\ displaystyle \ wedge}$${\ displaystyle \ vee}$${\ displaystyle \ emptyset}$${\ displaystyle \ {X_ {i} \}}$

Dilatace je jakýkoli operátor, který distribuuje po supremu a zachovává nejmenší prvek. Tj: ${\ Displaystyle \ delta \ colon L \ rightarrow L}$

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

Eroze je jakýkoli operátor, který se distribuuje do nekonečna a zachovává vesmír. Tj: ${\ Displaystyle \ varepsilon \ colon L \ rightarrow L}$

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

Dilatace a eroze tvoří Galoisova spojení . To znamená, že pro každou dilataci existuje jedna a jediná eroze, která uspokojuje ${\ Displaystyle \ delta}$${\ displaystyle \ varepsilon}$

${\ 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 uspokojující výše uvedené spojení.

Kromě toho, pokud spojení uspokojí dva operátoři, musí jít o dilataci a erozi. ${\ Displaystyle \ delta}$${\ displaystyle \ varepsilon}$

Páry erozí a dilatací splňujících výše uvedené spojení se nazývají „přídavná zařízení“ a za erozi se považuje přídavná eroze dilatace a naopak.

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

Pro každé doplnění je morfologické otevření a morfologické uzavření definováno následovně: ${\ Displaystyle (\ varepsilon, \ delta)}$${\ Displaystyle \ gamma \ colon L \ to L}$${\ Displaystyle \ phi \ colon L \ to L}$

${\ Displaystyle \ gamma = \ delta \ varepsilon,}$

${\ Displaystyle \ phi = \ varepsilon \ delta.}$

Morfologické otevírání a zavírání jsou konkrétní případy algebraického otevírání (nebo jednoduše otevírání) a algebraického zavírání (nebo jednoduše zavírání). Algebraické otvory jsou operátory v L, které jsou idempotentní, narůstají a jsou rozsá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í případ mříže morfologie, kde L je napájecí sady z E (Euclidean prostor nebo mřížky), to znamená, že L je množina všech podmnožin E , a je soubor začlenění . V tomto případě je infimum nastaveno jako průsečík a supremum je nastaveno sjednocení . ${\ displaystyle \ leq}$

Podobně, ve stupních šedi morfologie je další zvláštní případ, kde L je sada funkcí, které mapují E do , a , a , jsou bod-moudrý pořadí, supremum a infimum, v tomto pořadí. To znamená, že f a g jsou funkce v L , pak právě tehdy, pokud ; infimum je dáno vztahem ; a supremum je dáno . ${\ Displaystyle \ mathbb {R} \ cup \ {\ infty,-\ infty \}}$${\ displaystyle \ leq}$${\ displaystyle \ vee}$${\ displaystyle \ wedge}$${\ Displaystyle f \ leq g}$${\ Displaystyle f (x) \ leq g (x), \ forall x \ in E}$${\ Displaystyle f \ wedge g}$${\ Displaystyle (f \ wedge g) (x) = f (x) \ wedge g (x)}$${\ Displaystyle f \ vee g}$${\ Displaystyle (f \ vee g) (x) = f (x) \ vee g (x)}$

Viz také

• Transformace H-maxima

Poznámky

Reference

• Analýza obrazu a matematická morfologie Jean Serra, ISBN  0-12-637240-3 (1982)
• Image Analysis and Mathematical Morphology, Volume 2: Theoretical Advances by 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á obrazová analýza; Principles and Applications by Pierre Soille, ISBN  3-540-65671-5 (1999), 2nd edition (2003)
• Mathematical Morphology and its Application to Signal Processing , J. Serra and Ph. Salembier (Eds.), Sborník z 1. mezinárodního workshopu o matematické morfologii a jeho aplikacích pro zpracování signálu (ISMM'93), ISBN  84-7653-271-7 (1993)
• Mathematical Morphology and its Applications to Image Processing , J. Serra and P. Soille (Eds.), Sborník z 2. mezinárodního sympozia o matematické morfologii (ISMM'94), ISBN  0-7923-3093-5 (1994)
• Mathematical Morphology and its Applications to Image and Signal Processing , Henk JAM Heijmans and Jos BTM Roerdink (Eds.), Sborník ze 4. mezinárodního sympozia o matematické morfologii (ISMM'98), ISBN  0-7923-5133-9 (1998)
• Matematické morfologie: 40 let , Christian Ronse, Laurent Najman a Etienne Decencière (Eds.), ISBN  1-4020-3442-3 (2005)
• Mathematical Morphology and its Applications to Signal and Image Processing , Gerald JF Banon, Junior Barrera, Ulisses M. Braga-Neto (Eds.), 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 str.) Červen 2010

externí odkazy

• Online kurz matematické morfologie , Jean Serra (v angličtině, francouzštině a španělštině)
• Centrum matematické morfologie , Pařížská škola dolů
• Historie 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 Vanderbilt University. Přednášky 16-18 jsou z matematické morfologie , Alan Peters
• Matematická morfologie; z přednášek Computer Vision , Robyn Owens
• SMIL - Jednoduchá (ale účinná) morfologická knihovna obrázků (od Ecole des Mines de Paris)
• Zdarma knihovna zpracování obrazu optimalizovaná pro SIMD
• Ukázka apletu Java
• FILTRY: bezplatná otevřená knihovna pro zpracování obrazu
• Rychlé morfologické eroze, dilatace, otvory a uzávěry
• Morfologická analýza neuronů pomocí Matlabu