Abstraktní buněčný komplex - Abstract cell complex
V matematice je abstraktní komplex buněk abstraktní množinou s Alexandrovskou topologií, ve které je každému bodu přiřazeno nezáporné celé číslo zvané dimenze . Komplex se nazývá „abstraktní“, protože jeho body, které se nazývají „buňky“, nejsou podmnožinami Hausdorffova prostoru, jak je tomu v případě euklidovského a CW komplexu . Abstraktní komplexy buněk hrají důležitou roli v analýze obrazu a počítačové grafice .
Dějiny
Myšlenka abstraktních buněčných komplexů (také nazývaných abstraktní buněčné komplexy) souvisí s J. Listingem (1862) a E. Steinitzem (1908). Také AW Tucker (1933), K. Reidemeister (1938), PS Aleksandrov (1956) a R. Klette a A. Rosenfeld (2004) popsali abstraktní buněčné komplexy. E. Steinitz definoval abstraktní buněčný komplex tak, že kde E je abstraktní množina, B je asymetrický, nereflexivní a přechodný binární vztah, který se nazývá ohraničující vztah mezi prvky E a dim je funkce přiřazující každému prvku nezáporné celé číslo of E takovým způsobem, že v případě , poté . V. Kovalevsky (1989) popsal abstraktní buněčné komplexy pro 3D a vyšší dimenze. Navrhl také řadu aplikací pro analýzu obrazu. Ve své knize (2008) navrhl axiomatickou teorii lokálně konečných topologických prostorů, které jsou zobecněním abstraktních komplexů buněk. Kniha obsahuje mimo jiné nové definice topologických koulí a sfér nezávislých na metrice , novou definici kombinatorických variet a mnoho algoritmů užitečných pro analýzu obrazu.
Základní výsledky
Topologie abstraktních buněčných komplexů je založena na částečném pořadí v sadě jejích bodů nebo buněk.
Pojem abstraktní buněčného komplexu definovaného E. Steinitz souvisí s představou abstraktní simplicial složitá a liší se od simpliciální komplexu o vlastnost, že jeho prvky nejsou žádné simplexy : n rozměrný prvkem abstraktní komplexů nesmí mít n +1 nulových stran a ne každá podmnožina sady nulových stran buňky je buňka. To je důležité, protože pojem abstraktních buněčných komplexů lze aplikovat na dvourozměrné mřížky používané při zpracování obrazu, což pro zjednodušené komplexy neplatí. Nezjednodušený komplex je zobecnění, které umožňuje zavedení souřadnic buněk: Existují nesjednodušené komplexy, které jsou karteziánskými produkty takových „lineárních“ jednorozměrných komplexů, kde každá buňka s nulovými rozměry kromě dvou z nich přesně hraničí dvě jednorozměrné buňky. Pouze takové karteziánské komplexy umožňují zavést takové souřadnice, že každá buňka má sadu souřadnic a jakékoli dvě různé buňky mají různé sady souřadnic. Sada souřadnic může sloužit jako název každé buňky komplexu, což je důležité pro zpracování komplexů.
Abstraktní komplexy umožňují zavedení klasické topologie (Alexandrovova topologie) do mřížek, které jsou základem digitálního zpracování obrazu. Tato možnost definuje velkou výhodu abstraktních buněčných komplexů: Je možné přesně definovat pojmy konektivity a hranice podmnožin. Definice dimenze buněk a komplexů se v obecném případě liší od definice komplexů (viz níže).
Pojem abstraktního buněčného komplexu se podstatně liší od pojmu komplexu CW, protože abstraktní buněčný komplex není žádný Hausdorffův prostor . To je důležité z hlediska počítačové vědy, protože v počítači není možné explicitně představovat diskrétní Hausdorffův prostor. (Sousedství každého bodu v takovém prostoru musí mít nekonečně mnoho bodů).
Kniha V. Kovalevského obsahuje popis teorie lokálně konečných prostorů, které jsou zobecněním abstraktních komplexů buněk. Místně konečný prostor S je množina bodů, kde podmnožina S je definován pro každý bod P z S . Tato sada obsahující omezený počet bodů se nazývá nejmenší sousedství a P . Vztah binárních sousedství je definován v množině bodů lokálně konečného prostoru S : Prvek (bod) b je v relaci sousedství s prvkem a, pokud b patří do nejmenšího sousedství prvku a . Byly formulovány nové axiomy lokálně konečného prostoru a bylo prokázáno, že prostor S je v souladu s axiomy, pouze pokud je sousedský vztah anti-symetrický a tranzitivní. Sousední vztah je reflexivní trup inverzního ohraničujícího vztahu. Ukázalo se, že klasické axiomy topologie lze odvodit jako věty z nových axiomů. Proto je lokálně konečný prostor uspokojující nové axiomy zvláštním případem klasického topologického prostoru. Jeho topologie je posetová topologie nebo Alexandrovova topologie . Komplex abstraktních buněk je konkrétní případ lokálně konečného prostoru, ve kterém je definována dimenze pro každý bod. Bylo prokázáno, že rozměr buňky c abstraktního buněčného komplexu se rovná délce (počet buněk minus 1) maximální ohraničující cesty vedoucí z kterékoli buňky komplexu do buňky c . Ohraničující cesta je sekvence buněk, ve kterých každá buňka ohraničuje další. Kniha obsahuje teorii digitálních přímých segmentů ve 2D komplexech, řadu algoritmů pro sledování hranic ve 2D a 3D, pro ekonomické kódování hranic a pro přesnou rekonstrukci podmnožiny z kódu její hranice.
Znázornění digitálního obrazu abstraktního komplexu buněk
Digitální obraz může být reprezentován 2D abstraktním buněčným komplexem (ACC) rozložením obrazu na jeho rozměrové složky ACC: body (0 buněk), praskliny / hrany (1 buňka) a pixely / tváře (2 buňky) .
Tento rozklad společně s pravidlem přiřazení souřadnic, které jednoznačně přiřazuje souřadnice z obrazových pixelů k dimenzionálním složkám, umožňuje provádět určité operace analýzy obrazu na snímku pomocí elegantních algoritmů, jako je trasování hranic trhlin , digitální dělení přímých segmentů atd. Jeden takový pravidlo mapuje body, praskliny a tváře na levou horní souřadnici pixelu. Tyto dimenzionální složky nevyžadují žádný explicitní překlad do svých vlastních datových struktur, ale mohou být implicitně pochopeny a spojeny s 2D polem, které je obvyklou reprezentací datové struktury digitálního obrazu. Toto pravidlo přiřazení souřadnic a vykreslení každého incidentu buňky k tomuto obrázku je znázorněno na obrázku vpravo.
Viz také
