Abstrakcyjny kompleks komórkowy
W matematyce abstrakcyjny kompleks komórek jest abstrakcyjnym zbiorem z topologią Aleksandrowa , w której każdemu punktowi przypisana jest nieujemna liczba całkowita zwana wymiarem . Kompleks nazywamy „abstrakcyjnym”, ponieważ jego punkty, zwane „komórkami”, nie są podzbiorami przestrzeni Hausdorffa , jak ma to miejsce w przypadku kompleksów euklidesowych i CW . Abstrakcyjne kompleksy komórkowe odgrywają ważną rolę w analizie obrazu i grafice komputerowej .
Historia
Idea abstrakcyjnych kompleksów komórkowych (zwanych także abstrakcyjnymi kompleksami komórkowymi) odnosi się do J. Listinga (1862) i E. Steinitza (1908). Również AW Tucker (1933), K. Reidemeister (1938), PS Aleksandrov (1956) oraz R. Klette i A. Rosenfeld (2004) opisali abstrakcyjne kompleksy komórkowe. E. Steinitz zdefiniował abstrakcyjny kompleks komórek jako gdzie jest abstrakcyjnym zbiorem, B jest asymetrycznym, nieprzechodnim i przechodnim binarnym do = ( mi relacja zwana relacją ograniczającą między elementami E i dim jest funkcją przypisującą nieujemną liczbę całkowitą do każdego elementu E w taki sposób, że jeśli , to . V. Kovalevsky (1989) opisał abstrakcyjne kompleksy komórkowe dla wymiarów 3D i wyższych. Zasugerował również liczne zastosowania analizy obrazu. W swojej książce (2008) zaproponował aksjomatyczną teorię lokalnie skończonych przestrzeni topologicznych , które są uogólnieniem abstrakcyjnych kompleksów komórkowych. Książka zawiera m.in. nowe definicje kul i sfer topologicznych niezależnych od metryki , nową definicję rozmaitości kombinatorycznych oraz wiele algorytmów przydatnych do analizy obrazu.
Podstawowe wyniki
Topologia abstrakcyjnych kompleksów komórek opiera się na częściowym porządku w zbiorze jej punktów lub komórek.
Pojęcie abstrakcyjnego kompleksu komórkowego zdefiniowane przez E. Steinitza jest związane z pojęciem abstrakcyjnego kompleksu uproszczonego i różni się od kompleksu uproszczonego tym, że jego elementy nie są uproszczeniami : n -wymiarowy element abstrakcyjnego kompleksu nie może mają n +1 zerowymiarowych boków i nie każdy podzbiór zbioru zerowymiarowych boków komórki jest komórką. Jest to ważne, ponieważ pojęcie abstrakcyjnych kompleksów komórkowych można zastosować do dwu- i trójwymiarowych siatek używanych w przetwarzaniu obrazu, co nie jest prawdą w przypadku kompleksów uproszczonych. Kompleks nieprosty to uogólnienie, które umożliwia wprowadzenie współrzędnych komórki: Istnieją kompleksy nieproste, które są produktami kartezjańskimi takich „liniowych” jednowymiarowych kompleksów, w których każda zerowymiarowa komórka, oprócz dwóch z nich, dokładnie się ogranicza dwie jednowymiarowe komórki. Tylko takie kompleksy kartezjańskie umożliwiają wprowadzenie takich współrzędnych, że każda komórka ma swój zestaw współrzędnych, a dowolne dwie różne komórki mają różne zestawy współrzędnych. Zestaw współrzędnych może służyć jako nazwa każdej komórki kompleksu, co jest ważne przy przetwarzaniu kompleksów.
Abstrakcyjne kompleksy pozwalają na wprowadzenie klasycznej topologii (Aleksandrowa-topologii) do siatek będących podstawą cyfrowego przetwarzania obrazu. Ta możliwość określa wielką zaletę abstrakcyjnych kompleksów komórkowych: możliwe staje się dokładne zdefiniowanie pojęć łączności i granicy podzbiorów. Definicja wymiaru komórek i kompleksów jest w ogólnym przypadku inna niż w przypadku kompleksów uproszczonych (patrz poniżej).
Pojęcie abstrakcyjnego kompleksu komórkowego zasadniczo różni się od pojęcia kompleksu CW, ponieważ abstrakcyjny kompleks komórkowy nie jest przestrzenią Hausdorffa . Jest to ważne z punktu widzenia informatyki, ponieważ nie jest możliwe jawne przedstawienie niedyskretnej przestrzeni Hausdorffa w komputerze. (Sąsiedztwo każdego punktu w takiej przestrzeni musi mieć nieskończenie wiele punktów).
Książka W. Kowalewskiego zawiera opis teorii przestrzeni lokalnie skończonych , które są uogólnieniem abstrakcyjnych kompleksów komórkowych. Lokalnie skończona przestrzeń S to zbiór punktów, w których podzbiór S jest zdefiniowany dla każdego punktu P z S . Ten podzbiór zawierający ograniczoną liczbę punktów nazywany jest najmniejszym sąsiedztwem P . Binarna relacja sąsiedztwa jest zdefiniowana w zbiorze punktów przestrzeni lokalnie skończonej S : Element (punkt) b jest w relacji sąsiedztwa z elementem a , jeśli b należy do najmniejszego sąsiedztwa elementu a . Sformułowano nowe aksjomaty przestrzeni lokalnie skończonej i wykazano, że przestrzeń S jest zgodna z aksjomatami tylko wtedy, gdy relacja sąsiedztwa jest antysymetryczna i przechodnia. Relacja sąsiedztwa jest zwrotną powłoką odwrotnej relacji ograniczającej. Pokazano, że klasyczne aksjomaty topologii można wydedukować jako twierdzenia z nowych aksjomatów. Dlatego przestrzeń lokalnie skończona spełniająca nowe aksjomaty jest szczególnym przypadkiem klasycznej przestrzeni topologicznej. Jego topologia to topologia posetowa lub topologia Aleksandrowa . Abstrakcyjny zespół komórek to szczególny przypadek lokalnie skończonej przestrzeni, w której wymiar jest zdefiniowany dla każdego punktu. Wykazano, że wymiar komórki c abstrakcyjnego kompleksu komórek jest równy długości (liczba komórek minus 1) maksymalnej ścieżki ograniczającej prowadzącej od dowolnej komórki kompleksu do komórki c . Ścieżka ograniczająca to sekwencja komórek, w której każda komórka ogranicza następną. Książka zawiera teorię cyfrowych odcinków prostych w zespołach 2D, liczne algorytmy śledzenia granic w 2D i 3D, ekonomicznego kodowania granic i dokładnej rekonstrukcji podzbioru z kodu jego granicy. Wykorzystując abstrakcyjne kompleksy komórkowe, opracowano i opisano w książce wydajne algorytmy śledzenia, kodowania i poligonizacji granic, a także wykrywania krawędzi
Abstrakcyjna złożona komórka cyfrowa reprezentacja obrazu
Obraz cyfrowy może być reprezentowany przez 2D Abstract Cell Complex (ACC) poprzez rozłożenie obrazu na jego składowe wymiarowe ACC: punkty (0-komórka), pęknięcia/krawędzie (1-komórka) i piksele/twarze (2-komórka) .
Ta dekompozycja wraz z regułą przypisania współrzędnych w celu jednoznacznego przypisania współrzędnych z pikseli obrazu do składników wymiarowych umożliwia przeprowadzenie pewnych operacji analizy obrazu na obrazie za pomocą eleganckich algorytmów, takich jak śledzenie granic pęknięć, cyfrowy podział segmentów prostych itp. Jeden z takich reguła odwzorowuje punkty, pęknięcia i ściany na górną lewą współrzędną piksela. Te składowe wymiarowe nie wymagają jawnego tłumaczenia na ich własne struktury danych, ale mogą być rozumiane domyślnie i powiązane z tablicą 2D, która jest zwykłą reprezentacją struktury danych obrazu cyfrowego. Ta reguła przypisania współrzędnych i renderowanie każdej komórki incydentnej z tym obrazem jest przedstawione na obrazie po prawej stronie.
