Abstrakter Zellkomplex

In der Mathematik ist ein abstrakter Zellkomplex (auch abstrakter Zellenkomplex) eine abstrakte Menge von „Zellen“ mit einer Binärrelation („enthalten im Abschluss von“) und einer Abbildung in die nichtnegativen ganzen Zahlen („Dimension“). Der Komplex heißt „abstrakt“, weil die „Zellen“ keine Teilmengen eines euklidischen Raumes sind, wie dies bei Simplizialkomplexen oder CW-Komplexen der Fall ist. Abstrakte Zellkomplexe spielen eine wichtige Rolle in der Bildanalyse und in der Computergrafik.

Motivation Bearbeiten

In der Topologie verwendet man häufig (geometrische) Zellkomplexe, die aus (offenen oder abgeschlossenen) Zellen zusammengesetzt sind, d. h. Unterräumen homöomorph zu (offenen oder abgeschlossenen) Kugeln im euklidischen Raum. Meist wird vorausgesetzt, dass es sich um einen CW-Komplex handelt. (Ein noch speziellerer Begriff sind Simplizialkomplexe.) Unter anderem für Anwendungen in der Bildverarbeitung ist es aber nützlich, statt geometrischer Zellkomplexe abstrakt definierte Zellkomplexe zu verwenden.

Definition Bearbeiten

Ein abstrakter Zellkomplex $K=(S,\rho ,dim)$ ist gegeben durch

eine Menge $S$ ,
eine binäre Relation $\rho$ auf $S$ ,
eine Funktion $dim:S\rightarrow \mathbb {N} \cup \left\{0\right\}$ ,

welche folgende Axiome erfüllen:

aus $x\rho y$ und $y\rho z$ folgt $x\rho z$ ,
aus $x\rho y$ folgt $dim(x)<dim(y)$ .

In der Regel wird nach Tucker noch folgendes weiteres Axiom vorausgesetzt:

Wenn $x\rho z$ und $dim(z)-dim(x)>1$ , dann gibt es ein $y\in S$ mit $x\rho y$ und $y\rho z$ .

Verschiedene Autoren verwenden noch zusätzliche weitere Axiome.

Elemente von $S$ werden als Zellen bezeichnet. Im Spezialfall eines geometrischen Zellkomplexes ist $dim(x)$ die Dimension der Zelle $x$ und $x\rho y$ bedeutet, dass die Zelle $x$ im Abschluss der Zelle $y$ liegt.

Geschichte Bearbeiten

Die Idee eines abstrakten Zellkomplexes geht auf J. Listing (1862)^[1] und E. Steinitz (1908)^[2] zurück. Auch A. W. Tucker (1933),^[3] K. Reidemeister (1938),^[4] P. S. Aleksandrov (1956)^[5] sowie R. Klette und A. Rosenfeld (2004)^[6] beschreiben abstrakte Zellkomplexe. Zahlreiche Arbeiten zur Bildverarbeitung verwenden abstrakte Zellkomplexe, Beispiele dafür sind die Lehrbücher von Pavlidis,^[7] Rosenfeld^[8] und Serra.^[9] Bei Kovalevsky^[10] wird eine axiomatische Theorie der lokal endlichen topologischen Räume als Verallgemeinerung der abstrakten Zellkomplexe vorgeschlagen. In Kovalevsky^[11] werden effiziente Algorithmen mit Verwendung der abstrakten Zellkomplexe für die Verfolgung, Codierung und Polygonisierung von Begrenzungen, wie auch für die Kantendetektion beschrieben.

Literatur Bearbeiten

Einzelnachweise Bearbeiten

↑ J. Listing: Der Census räumlicher Complexe. In: Abhandlungen der Königlichen Gesellschaft der Wissenschaften zu Göttingen. Band 10, Göttingen 1862, S. 97–182.
↑ E. Steinitz: Beiträge zur Analysis. In: Sitzungsbericht Berliner Mathematischen Gesellschaft. Band 7, 1908, S. 29–49.
↑ A. W. Tucker: An abstract approach to manifolds. In: Annals Mathematics. Band 34, 1933, S. 191–243.
↑ K. Reidemeister: Topologie der Polyeder und kombinatorische Topologie der Komplexe. Akademische Verlagsgesellschaft, Leipzig 1938.
↑ P. S. Aleksandrov: Combinatorial Topology. Graylock Press, Rochester 1956.
↑ R. Klette, A. Rosenfeld: Digital Geometry. Elsevier, 2004.
↑ Theodosios Pavlidis: Structural pattern recognition. (Springer Series in Electrophysics, Vol. 1). Springer-Verlag, Berlin/New York 1977, ISBN 3-540-08463-0.
↑ Azriel Rosenfeld: Picture languages. Formal models for picture recognition. (Computer Science and Applied Mathematics). Academic Press, New York/London, 1979, ISBN 0-12-597340-3.
↑ J. Serra: Image analysis and mathematical morphology. English version revised by Noel Cressie. Academic Press, London 1984, ISBN 0-12-637240-3.
↑ Kovalevsky, V., Geometry of Locally Finite Spaces, ISBN 978-3-9812252-0-4
↑ Kovalevsky, V., Image Processing with Cellular Topology, Springer 2021, ISBN 978-981-16-5771-9

[1] J. Listing: Der Census räumlicher Complexe. In: Abhandlungen der Königlichen Gesellschaft der Wissenschaften zu Göttingen. Band 10, Göttingen 1862, S. 97–182.

[2] E. Steinitz: Beiträge zur Analysis. In: Sitzungsbericht Berliner Mathematischen Gesellschaft. Band 7, 1908, S. 29–49.

[3] A. W. Tucker: An abstract approach to manifolds. In: Annals Mathematics. Band 34, 1933, S. 191–243.

[4] K. Reidemeister: Topologie der Polyeder und kombinatorische Topologie der Komplexe. Akademische Verlagsgesellschaft, Leipzig 1938.

[5] P. S. Aleksandrov: Combinatorial Topology. Graylock Press, Rochester 1956.

[6] R. Klette, A. Rosenfeld: Digital Geometry. Elsevier, 2004.

[7] Theodosios Pavlidis: Structural pattern recognition. (Springer Series in Electrophysics, Vol. 1). Springer-Verlag, Berlin/New York 1977, ISBN 3-540-08463-0.

[8] Azriel Rosenfeld: Picture languages. Formal models for picture recognition. (Computer Science and Applied Mathematics). Academic Press, New York/London, 1979, ISBN 0-12-597340-3.

[9] J. Serra: Image analysis and mathematical morphology. English version revised by Noel Cressie. Academic Press, London 1984, ISBN 0-12-637240-3.

[10] Kovalevsky, V., Geometry of Locally Finite Spaces, ISBN 978-3-9812252-0-4

[11] Kovalevsky, V., Image Processing with Cellular Topology, Springer 2021, ISBN 978-981-16-5771-9

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]