Abstrakt cellekompleks - Abstract cell complex
I matematikk er et abstrakt cellekompleks et abstrakt sett med Alexandrov topologi der et ikke-negativt heltall kalt dimensjon er tildelt hvert punkt. Komplekset kalles “abstrakt” siden punktene, som kalles “celler”, ikke er delmengder av et Hausdorff-rom, slik det er tilfelle i euklidisk og CW-kompleks . Abstrakte cellekomplekser spiller en viktig rolle i bildeanalyse og datagrafikk .
Historie
Ideen om abstrakte cellekomplekser (også kalt abstrakte cellekomplekser) er knyttet til J. Listing (1862) og E. Steinitz (1908). Også AW Tucker (1933), K. Reidemeister (1938), PS Aleksandrov (1956) samt R. Klette og A. Rosenfeld (2004) har beskrevet abstrakte cellekomplekser. E. Steinitz har definert et abstrakt cellekompleks som der E er et abstrakt sett, B er et asymmetrisk, irrefleksivt og transitivt binært forhold som kalles avgrensningsforholdet mellom elementene i E og dim er en funksjon som tildeler et ikke-negativt heltall til hvert element av E på en slik måte at hvis , da . V. Kovalevsky (1989) beskrev abstrakte cellekomplekser for 3D og høyere dimensjoner. Han foreslo også mange applikasjoner for bildeanalyse. I sin bok (2008) har han antydet en aksiomatisk teori om lokalt endelige topologiske rom som er generalisering av abstrakte cellekomplekser. Boken inneholder blant annet nye definisjoner av topologiske kuler og kuler uavhengig av metrisk , en ny definisjon av kombinatoriske manifolder og mange algoritmer som er nyttige for bildeanalyse.
Grunnleggende resultater
Topologien til abstrakte cellekomplekser er basert på en delvis orden i settet med sine punkter eller celler.
Begrepet abstrakt cellekompleks definert av E. Steinitz er relatert til forestillingen om et abstrakt forenklet kompleks, og det skiller seg fra et forenklet kompleks ved eiendommen at dets elementer ikke er noen forenklinger : Et n- dimensjonalt element i et abstrakt kompleks må ikke har n +1 nulldimensjonale sider, og ikke hver delmengde av settet med nulldimensjonale sider av en celle er en celle. Dette er viktig siden begrepet abstrakte cellekomplekser kan brukes på de to- og tredimensjonale rutenettene som brukes i bildebehandling, noe som ikke gjelder for enkle komplekser. Et ikke-enkelt kompleks er en generalisering som gjør det mulig å innføre cellekoordinater: Det er ikke-enkle komplekser som er kartesiske produkter av slike "lineære" endimensjonale komplekser der hver nulldimensjonale celle, foruten to av dem, grenser nøyaktig to endimensjonale celler. Bare slike kartesiske komplekser gjør det mulig å introdusere slike koordinater at hver celle har et sett med koordinater og to forskjellige celler har forskjellige koordinatsett. Koordinatsettet kan tjene som et navn på hver celle i komplekset som er viktig for behandling av komplekser.
Abstrakte komplekser tillater innføring av klassisk topologi (Alexandrov-topologi) i rutenett som er grunnlaget for digital bildebehandling. Denne muligheten definerer den store fordelen med abstrakte cellekomplekser: Det blir mulig å nøyaktig definere forestillingene om tilkobling og grensen til delmengder. Definisjonen av dimensjon av celler og komplekser er generelt forskjellig fra for enkle komplekser (se nedenfor).
Forestillingen om et abstrakt cellekompleks skiller seg vesentlig fra et CW-kompleks fordi et abstrakt cellekompleks ikke er noe Hausdorff-rom . Dette er viktig fra informatikkens synspunkt, siden det er umulig å eksplisitt representere et ikke-diskret Hausdorff-rom i en datamaskin. (Nabolaget til hvert punkt i et slikt rom må ha uendelig mange poeng).
Boken av V. Kovalevsky inneholder beskrivelsen av teorien om lokalt endelige rom som er en generalisering av abstrakte cellekomplekser. En lokalt begrenset plass S er et sett av punkter hvor en delmengde av S er definert for hvert punkt P i S . Dette celle-subsett som inneholder et begrenset antall punkter kalles det minste området av P . En binær nabolagsrelasjon er definert i settet med punkter i det lokalt endelige rommet S : Elementet (punkt) b er i nabolagsrelasjonen med elementet a hvis b tilhører det minste nabolaget til elementet a . Nye aksiomer av et lokalt endelig rom er formulert, og det ble bevist at rommet S bare er i samsvar med aksiomene hvis nabolagsrelasjonen er antisymmetrisk og transitiv. Nabolagsrelasjonen er det refleksive skroget til det omvendte avgrensningsforholdet. Det ble vist at klassiske aksiomer av topologien kan utledes som teoremer fra de nye aksiomene. Derfor er et lokalt begrenset rom som tilfredsstiller de nye aksiomene, et spesielt tilfelle av et klassisk topologisk rom. Dens topologi er en poset topologi eller Alexandrov topologi . Et abstrakt cellekompleks er et spesielt tilfelle av et lokalt begrenset rom der dimensjonen er definert for hvert punkt. Det ble demonstrert at dimensjonen til en celle c av et abstrakt cellekompleks er lik lengden (antall celler minus 1) av den maksimale begrensningsbanen som fører fra en hvilken som helst celle i komplekset til cellen c . Grensestien er en sekvens av celler der hver celle avgrenser den neste. Boken inneholder teorien om digitale rette segmenter i 2D-komplekser, mange algoritmer for å spore grenser i 2D og 3D, for økonomisk koding av grensene og for nøyaktig rekonstruering av en delmengde fra koden til grensen.
Abstract Cell Complex Digital Image Representation
Et digitalt bilde kan representeres av et 2D Abstract Cell Complex (ACC) ved å spalte bildet til dets ACC-dimensjonale bestanddeler: punkter (0-celle), sprekker / kanter (1-celle) og piksler / ansikter (2-celle) .
Denne nedbrytningen sammen med en koordinatildelingsregel for entydig å tilordne koordinater fra bildepikslene til dimensjonale bestanddeler tillater at visse bildeanalyseoperasjoner kan utføres på bildet med elegante algoritmer, slik som sprekkgrensesporing , digital rett segmentoppdeling , etc. En slik regel kartlegger punktene, sprekkene og ansiktene til øverste venstre koordinat for pikselet. Disse dimensjonale bestanddelene krever ingen eksplisitt oversettelse til sine egne datastrukturer, men kan implisitt forstås og relateres til 2D-matrisen, som er den vanlige datastrukturrepresentasjonen av et digitalt bilde. Denne koordinattildelingsregelen og gjengivelsene av hver cellehendelse til dette bildet er avbildet i bildet til høyre.
Se også
