Topologická kostra - Topological skeleton
v tvarová analýza, kostra (nebo topologická kostra) a tvar je tenká verze tohoto tvaru, která je stejně vzdálený k jeho hranice. Kostra obvykle zdůrazňuje geometrické a topologické vlastnosti tvaru, například jeho připojení, topologie, délka, směr, a šířka. Spolu se vzdáleností jeho bodů k hranici tvaru může kostra sloužit také jako a zastoupení tvaru (obsahují všechny informace potřebné k rekonstrukci tvaru).
Kostry mají v technické literatuře několik různých matematických definic a pro jejich výpočet existuje mnoho různých algoritmů. Lze nalézt také různé varianty kostry, včetně rovné kostry, morfologické kostry, atd.
V odborné literatuře pojmy kostra a střední osa někteří autoři je používají zaměnitelně,[1][2][3][4][5] zatímco někteří další autoři[6][7][8] považovat je za příbuzné, ale ne stejné. Podobně pojmy skeletonizace a ředění někteří jsou také považováni za totožné,[2] a ne ostatními.[6]
Kostry jsou široce používány v počítačové vidění, analýza obrazu, rozpoznávání vzorů a digitální zpracování obrazu pro účely, jako je optické rozpoznávání znaků, rozpoznávání otisků prstů, vizuální kontrola nebo komprese. Ve vědách o živé přírodě nalezly kostry rozsáhlé použití k charakterizaci skládání bílkovin[9] a morfologie rostlin v různých biologických měřítcích.[10]
Matematické definice
Kostry mají v technické literatuře několik různých matematických definic; většina z nich vede k podobným výsledkům v spojité prostory, ale obvykle přináší různé výsledky v diskrétní prostory.
Uhasit body modelu šíření ohně
Ve své klíčové práci Harry Blum[11] Air Force Cambridge Research Laboratories ve společnosti Hanscom Air Force Base, v Bedford, Massachusetts, definováno a střední osa pro výpočet kostry tvaru pomocí intuitivního modelu šíření ohně na travnatém poli, kde má pole podobu daného tvaru. Pokud jeden „zapálí“ ve všech bodech na hranici tohoto travnatého pole současně, pak je kostrou soubor uhasit body, tj. ty body, kde se setkávají dvě nebo více vlnových front. Tento intuitivní popis je výchozím bodem pro řadu přesnějších definic.
Středy maximálních disků (nebo koulí)
A disk (nebo míč ) B se říká, že je maximální v sadě A -li
- , a
- Pokud jiný disk D obsahuje B, pak .
Jeden způsob definování kostry tvaru A je jako sada středů všech maximálních disků v A.[12]
Středy dvou tangens kruhů
Kostra tvaru A lze také definovat jako sadu středů disků, které se dotýkají hranice A na dvou nebo více místech.[13] Tato definice zajišťuje, že body kostry jsou ve stejné vzdálenosti od hranice tvaru a jsou matematicky ekvivalentní Blumově transformaci mediální osy.
Hřebeny funkce vzdálenosti
Mnoho definic kostry využívá konceptu funkce vzdálenosti, což je funkce, která se vrací pro každý bod X uvnitř tvaru A jeho vzdálenost k nejbližšímu bodu na hranici A. Použití funkce vzdálenosti je velmi atraktivní, protože její výpočet je relativně rychlý.
Jedna z definic kostry používající funkci vzdálenosti je jako hřebeny funkce vzdálenosti.[6] V literatuře je běžné nesprávné tvrzení, že kostra se skládá z bodů, které jsou při transformaci vzdálenosti „lokálně maximální“. To prostě není tento případ, protože se ukáže i letmé srovnání transformace vzdálenosti a výsledné kostry. Hřebeny mohou mít různou výšku, takže bod na hřebeni může být nižší než jeho bezprostřední soused na hřebeni. Nejedná se tedy o místní maximum, přestože patří k hřebeni. Je však vertikálně méně daleko, než by zaručovala jeho pozemní vzdálenost. Jinak by to byla část svahu.
Další definice
- Body bez segmentů upstream ve funkci vzdálenosti. The proti proudu bodu X je segment začínající na X který sleduje maximální cestu přechodu.
- Body, kde se gradient funkce vzdálenosti liší od 1 (nebo ekvivalentně není dobře definován)
- Nejmenší možná sada řádků, které zachovávají topologii a jsou ve stejné vzdálenosti od hranic
Skeletonizační algoritmy
Existuje mnoho různých algoritmů pro výpočet koster pro tvary digitální obrázky, stejně jako spojité sady.
- Použitím morfologické operátory (Vidět Morfologická kostra[13])
- Doplnění morfologických operátorů o tvarový základ prořezávání [14]
- Použití křižovatek vzdáleností od hraničních úseků [15]
- Pomocí vývoje křivky [16][17]
- Používání sad úrovní[8]
- Nalezení hřebenových bodů na funkci vzdálenosti[6]
- "Loupání" tvaru bez změny topologie až do konvergence[18]
Algoritmy skeletonizace mohou někdy na výstupních kostrách vytvářet nežádoucí větve. Algoritmy prořezávání se často používají k odstranění těchto větví.
Viz také
Poznámky
- ^ Jain, Kasturi & Schunck (1995), Oddíl 2.5.10, s. 55.
- ^ A b Gonzales & Woods (2001), Oddíl 11.1.5, s. 650
- ^ http://people.csail.mit.edu/polina/papers/skeletons_cvpr00.pdf
- ^ Dougherty (1992).
- ^ Ogniewicz (1995).
- ^ A b C d A. K. Jain (1989 ), Oddíl 9.9, s. 382.
- ^ Serra (1982).
- ^ A b Sethian (1999), Oddíl 17.5.2, s. 234.
- ^ Abeysinghe a kol. (2008)
- ^ Bucksch (2014)
- ^ Harry Blum (1967 )
- ^ A. K. Jain (1989 ), Oddíl 9.9, s. 387.
- ^ A b Gonzales & Woods (2001), Oddíl 9.5.7, s. 543.
- ^ Abeysinghe a kol. (2008).
- ^ R. Kimmel, D. Shaked, N. Kiryati a A. M. Bruckstein. https://www.cs.technion.ac.il/~ron/PAPERS/skeletonization_CVIU_1995.pdf Comp. Vision and Image Understanding, 62 (3): 382-391, 1995.
- ^ Tannenbaum (1996)
- ^ Bai, Longin a Wenyu (2007).
- ^ A. K. Jain (1989 ), Oddíl 9.9, s. 389.
Reference
- Abeysinghe, Sasakthi; Baker, Matthew; Chiu, Wah; Ju, Tao (2008), „Skeletonizace objemů ve stupních šedi bez segmentace pro porozumění tvaru“, IEEE Int. Konf. Modelování tvarů a aplikace (SMI 2008) (PDF), str. 63–71, doi:10.1109 / SMI.2008.4547951, ISBN 978-1-4244-2260-9, S2CID 15148296.
- Abeysinghe, Sasakthi; Ju, Tao; Baker, Matthew; Chiu, Wah (2008), „Modelování tvarů a shoda při identifikaci 3D proteinových struktur“ (PDF), Počítačem podporovaný design, Elsevier, 40 (6): 708–720, doi:10.1016 / j.cad.2008.01.013
- Bai, Xiang; Longin, Latecki; Wenyu, Liu (2007), "Prořezávání kostry rozdělováním obrysů s diskrétním vývojem křivky" (PDF), Transakce IEEE na analýze vzorů a strojové inteligenci, 29 (3): 449–462, doi:10.1109 / TPAMI.2007.59, PMID 17224615, S2CID 14965041.
- Blum, Harry (1967), „Transformace pro získávání nových deskriptorů tvaru“, Wathen-Dunn, W. (ed.), Modely pro vnímání řeči a vizuální formy (PDF), Cambridge, Massachusetts: MIT Press, s. 362–380.
- Bucksch, Alexander (2014), „Praktický úvod do koster pro vědy o rostlinách“, Aplikace v rostlinných vědách, 2 (8): 1400005, doi:10,3732 / aplikace. 1400005, PMC 4141713, PMID 25202647.
- Cychosz, Joseph (1994), Grafické skvosty IV, San Diego, CA, USA: Academic Press Professional, Inc., pp.465–473, ISBN 0-12-336155-9.
- Dougherty, Edward R. (1992), Úvod do morfologického zpracování obrazu, ISBN 0-8194-0845-X.
- Gonzales, Rafael C .; Woods, Richard E. (2001), Digitální zpracování obrazu, ISBN 0-201-18075-8.
- Jain, Anil K. (1989), Základy digitálního zpracování obrazu, Bibcode:1989fdip.book ..... J, ISBN 0-13-336165-9.
- Jain, Ramesh; Kasturi, Rangachar; Schunck, Brian G. (1995), Strojové vidění, ISBN 0-07-032018-7.
- Ogniewicz, R. L. (1995), „Automatické prořezávání střední osy na základě charakteristik kosterního prostoru“, Dori, D .; Bruckstein, A. (eds.), Tvar, struktura a rozpoznávání vzorů, ISBN 981-02-2239-4.
- Petrou, Maria; García Sevilla, Pedro (2006), Zpracování obrazu zacházení s texturou, ISBN 978-0-470-02628-1.
- Serra, Jean (1982), Analýza obrazu a matematická morfologie, ISBN 0-12-637240-3.
- Sethian, J. A. (1999), Metody nastavení úrovně a metody rychlého pochodu, ISBN 0-521-64557-3.
- Tannenbaum, Allen (1996), „Tři úryvky teorie vývoje křivek v počítačovém vidění“, Matematické a počítačové modelování, 24 (5): 103–118, doi:10.1016/0895-7177(96)00117-3.
Software s otevřeným zdrojovým kódem
- ITK (C ++)
- Skeletonizovat3D (Jáva)
- Grafické skvosty IV (C)
- EVG-tenký (C ++)