Digitale Topologie - Digital topology

Die digitale Topologie befasst sich mit Eigenschaften und Merkmalen von zweidimensionalen (2D) oder dreidimensionalen (3D) digitalen Bildern , die topologischen Eigenschaften (z. B. Verbundenheit ) oder topologischen Merkmalen (z. B. Grenzen ) von Objekten entsprechen.

Konzepte und Ergebnisse der digitalen Topologie werden verwendet, um wichtige Bildanalysealgorithmen (auf niedriger Ebene) zu spezifizieren und zu begründen , einschließlich Algorithmen zum Ausdünnen , zur Verfolgung von Grenzen oder Oberflächen, zum Zählen von Komponenten oder Tunneln oder zum Füllen von Regionen.

Geschichte

Digitale Topologie wurde zum ersten Mal in den späten 1960er Jahren durch die studierte Computerbildanalyse Forscher Azriel Rosenfeld (1931-2004), deren Veröffentlichungen zum Thema spielte eine wichtige Rolle beim Aufbau und das Feld zu entwickeln. Der Begriff "digitale Topologie" wurde selbst von Rosenfeld erfunden, der ihn erstmals 1973 in einer Publikation verwendete.

Eine verwandte Arbeit namens Gitterzelltopologie , die als Verbindung zur klassischen kombinatorischen Topologie angesehen werden könnte , erschien im Buch von Pavel Alexandrov und Heinz Hopf , Topologie I (1935). Rosenfeld et al. vorgeschlagene digitale Konnektivität wie 4-Konnektivität und 8-Konnektivität in zwei Dimensionen sowie 6-Konnektivität und 26-Konnektivität in drei Dimensionen. Die Markierungsmethode zum Ableiten einer verbundenen Komponente wurde in den 1970er Jahren untersucht. Theodosios Pavlidis (1982) schlug die Verwendung graphentheoretischer Algorithmen wie der Tiefensuchmethode zum Auffinden verbundener Komponenten vor. Vladimir Kovalevsky (1989) erweiterte die Alexandrov-Hopf-2D-Gitterzelltopologie auf drei und höhere Dimensionen. Er schlug auch (2008) eine allgemeinere axiomatische Theorie lokal endlicher topologischer Räume und abstrakter Zellkomplexe vor, die früher von Ernst Steinitz (1908) vorgeschlagen wurde. Es ist die Alexandrow-Topologie . Das Buch aus dem Jahr 2008 enthält neue Definitionen von topologischen Kugeln und Kugeln unabhängig von einer Metrik und zahlreiche Anwendungen für die digitale Bildanalyse.

In den frühen 1980er Jahren wurden digitale Oberflächen untersucht. David Morgenthaler und Rosenfeld (1981) gaben eine mathematische Definition von Oberflächen im dreidimensionalen digitalen Raum. Diese Definition enthält insgesamt neun Arten von digitalen Oberflächen. Die digitale Mannigfaltigkeit wurde in den 1990er Jahren untersucht. Eine rekursive Definition des digitalen k-Verteilers wurde 1993 von Chen und Zhang intuitiv vorgeschlagen. Viele Anwendungen wurden in der Bildverarbeitung und in der Bildverarbeitung gefunden.

Grundlegende Ergebnisse

Ein grundlegendes (frühes) Ergebnis in der digitalen Topologie besagt, dass 2D-Binärbilder die alternative Verwendung von 4- oder 8-Adjazenz- oder " Pixel-Konnektivität " (für "Objekt" - oder "Nicht-Objekt" -Pixel ) erfordern , um die grundlegende topologische Dualität von sicherzustellen Trennung und Verbundenheit. Diese alternative Verwendung entspricht offenen oder geschlossenen Mengen in der Topologie der 2D- Gitterzellen , und das Ergebnis wird auf 3D verallgemeinert: Die alternative Verwendung der 6- oder 26-Nachbarschaft entspricht offenen oder geschlossenen Mengen in der Topologie der 3D- Gitterzellen . Die Gitterzelltopologie gilt auch für mehrstufige (z. B. Farb-) 2D- oder 3D-Bilder, beispielsweise basierend auf einer Gesamtreihenfolge möglicher Bildwerte und unter Anwendung einer "Maximum-Label-Regel" (siehe das Buch von Klette und Rosenfeld, 2004).

Die digitale Topologie hängt stark mit der kombinatorischen Topologie zusammen . Die Hauptunterschiede zwischen ihnen sind: (1) Die digitale Topologie untersucht hauptsächlich digitale Objekte, die von Gitterzellen gebildet werden, und (2) die digitale Topologie befasst sich auch mit Nicht-Jordan-Mannigfaltigkeiten.

Ein kombinatorischer Verteiler ist eine Art Verteiler, der eine Diskretisierung eines Verteilers darstellt. Es bedeutet normalerweise eine stückweise lineare Mannigfaltigkeit, die durch einfache Komplexe hergestellt wird . Ein digitaler Verteiler ist eine spezielle Art von kombinatorischem Verteiler, der im digitalen Raum definiert ist, dh im Gitterzellenraum.

Eine digitale Form des Gauß-Bonnet-Theorems lautet: Sei M eine geschlossene digitale 2D- Mannigfaltigkeit in direkter Nachbarschaft (dh eine (6,26) -Oberfläche in 3D). Die Formel für die Gattung lautet

${\ displaystyle g = 1 + (M_ {5} + 2M_ {6} -M_ {3}) / 8}$,

Dabei gibt es die Menge der Oberflächenpunkte an, von denen jeder i benachbarte Punkte auf der Oberfläche hat (Chen und Rong, ICPR 2008). Wenn M einfach angeschlossen ist, das heißt , dann . (Siehe auch Euler-Charakteristik .) ${\ displaystyle M_ {i}}$${\ displaystyle g = 0}$${\ displaystyle M_ {3} = 8 + M_ {5} + 2M_ {6}}$

Siehe auch

• Digitale Geometrie
• Kombinatorische Topologie
• Computergeometrie
• Computertopologie
• Topologische Datenanalyse
• Topologie
• Diskrete Mathematik

Verweise

• Herman, Gabor T. (1998). Geometrie digitaler Räume . Angewandte und numerische harmonische Analyse. Boston, MA: Birkhäuser Boston, Inc. ISBN 978-0-8176-3897-9. MR  1711168 .
• Kong, Tat Yung; Rosenfeld, Azriel, Hrsg. (1996). Topologische Algorithmen für die digitale Bildverarbeitung . Elsevier. ISBN 0-444-89754-2.
• Voss, Klaus (1993). Diskrete Bilder, Objekte und Funktionen in${\ displaystyle \ mathbb {Z} ^ {n}}$ . Algorithmen und Kombinatorik. 11 . Berlin: Springer-Verlag. doi : 10.1007 / 978-3-642-46779-0 . ISBN 0-387-55943-4. MR  1224678 .
• Chen, L. (2004). Diskrete Oberflächen und Mannigfaltigkeiten: Eine Theorie der digital-diskreten Geometrie und Topologie . SP Computing. ISBN 0-9755122-1-8.
• Klette, R.; Rosenfeld, Azriel (2004). Digitale Geometrie . Morgan Kaufmann. ISBN 1-55860-861-3.
• Morgenthaler, David G.; Rosenfeld, Azriel (1981). "Oberflächen in dreidimensionalen digitalen Bildern" . Information und Kontrolle . 51 (3): 227–247. doi : 10.1016 / S0019-9958 (81) 90290-4 . MR  0686842 .
• Pavlidis, Theo (1982). Algorithmen für die Grafik- und Bildverarbeitung . Vorlesungsunterlagen in Mathematik. 877 . Rockville, MD: Informatikpresse. ISBN 0-914894-65-X. MR  0643798 .
• Kovalevsky, Vladimir (2008). Geometrie lokal endlicher Räume . Berlin: Verlag Dr. Baerbel Kovalevski. ISBN 978-3-9812252-0-4.