Embed Size (px)
Citation preview
Digitalgeometriemit Anwendungen zur Bildanalyse
und Computergrafik
W. Kovalevski
University of Applied Sciences Berlin
www.kovalevsky.de
Einführung in die Topologie der lokal endlichen Räume
1. Warum ist Topologie wichtig für die Bildanalyse?
2. Warum können wir nicht die klassische allgemeine Topologie nutzen?
3. Nachbarschaftsstrukturen als Behelfslösung.
4. Lokal endliche Räume.
5. Dimension der Raumelemente.
6. Zellenkomplexe.
7. Zusammenhang und Begrenzungen von Regionen.
8. Kartesische Komplexe und kombinatorische Koordinaten.
9. Datenstrukturen.
Einige einfache Algorithmen
1. Verfolgung von Begrenzungen. Verallgemeinerung für den nD-Raum
2. Füllen des Inneren einer geschlossenen Kurve.
3. Markierung der Komponenten.
Inhalt
Geraden in einem 2D-Raum (digitale Strecken)
1. Halbräume und konvexe Mengen.
2. Definition einer digitalen Strecke (digital straight segment, DSS).
3. Digitale Strecken und Kollinearität.
4. Erkennung der DSS während der Verfolgung einer Kurve.
5. Sparsame Codierung von DSS-Folgen.
6. Dünne und dicke DSS.
7. Anwendungen der DSS.
Fortgeschrittene Algorithmen der Digitalgeometrie
1. Digitale Kreisbögen; Definition und Erkennung.
2. Digitale Ebenenstücke im 3D-Raum.
3. Erzeugung der konvexen Hülle eines 3D-Objekts.
4. Methoden der Verfolgung und Codierung von Oberflächen im 3D-Raum.
5. Füllen des Inneren von Oberflächen im 3D-Raum.
6. Rekonstruktion von "farbigen" Bildern im nD-Raum.
7. Skelette in 2D und 3D.
Inhalt 2
Anwendungen der Zellenkomlexe in der Computergrafik
1. Klassifikation der digitalen Kurven.
2. Zeichnen einer Kurve durch die Verfolgung ihrer Gleichung.
3. Subpixel-Daten und Antialiasing vom Standpunkt der Komplexe.
Resümee
1. Einige offene Probleme.
2. Schlussfolgerung.
Inhalt 3
Vorlesung 1:
Einführung in die Topologie der lokal endlichen Räume
Warum ist Topologie wichtig für die Bildanalyse?
Man braucht folgende Begriffe:- zusammenhängende Mengen- Begrenzung einer Teilmenge- benachbarte Teilmengen- das Innere und das Äußere, usw.
All das sind topologische Begriffe.
Warum ist Topologie wichtig für die Bildanalyse? (Fortsetzung)
Man braucht in der Bildanalyse und in der Computergrafik die Begriffe der zusammenhängenden Mengen, der Begrenzung einer Teilmenge, der benachbarte Teilmengen, des Inneren und des Äußeren, usw. All das sind topologische Begriffe. Topologie kann als die Geometrie auf einer Gummischicht betrachtet werden: Alle genannten Eigenschaften von Zeichnungen auf einer Gummischicht bleiben erhalten, wenn man die Schicht verzieht, ohne sie zu zerreißen. Genauer gesagt, topologische Eigenschaften sind invariant unter stetigen Transformationen des Raumes.
Warum kann man die klassische allgemeine Topologie nicht benutzen?
Die allgemeine Topologie betrachtet Räume, in welchen selbst die kleinste Umgebung eines Punktes unendlich viele andere Punkte enthält. Dies wird im Folgenden bewiesen.
Es ist offensichtlich, dass solch ein Raum (und sogar sein kleinster Teil) nicht im Computer dargestellt werden kann. Deswegen braucht man die Topologie der sogenannten lokal endlichen Räume, in welchen die Umgebung eines Elements auch endlich viele andere Elemente enthalten kann.
Drei Versionen der Trennungseigenschaften von Räumen
In einem zusammenhängenden T2-Raum muss jede Umgebung eines Punktes andere Punkte enthalten. Dabei soll es für beliebige zwei Punkte Umgebungen geben, die sich nicht überschneiden. Wenn eine Umgebung U(a) des Punktes a den Punkt b enthält, dann soll es auch eine kleinere Umgebung von a geben, die b nicht enthält. Sie enthält aber andere als a Punkte. Um diese von a zu trennen, wird eine kleinere Umgebung benötigt usw. ohne Ende. Daraus folgt, dass eine beliebig kleine Umgebung eines Punktes in T2 und in T1 unendlich viele Punkte enthalten muss.
Weder ein T1- noch ein T2-Raum (oder die kleinste Teilmenge eines solchen
Raumes) kann im Computer explizit dargestellt werden. Es bleiben nur die T0-Räume
T0 T1 T2
Symbolische Darstellung der Trennungsaxiome
Eine Behelfslösung
In den Jahren nach 1970 hat Azriel Rosenfeld die 4- und die 8-Nachbarschaft der Pixel in einem digitalisierten Bild vorgeschlagen. Er hat den Begriff eines m-Wegs als eine Folge von m-benachbarten Pixeln definiert, wobei m gleich 4 oder 8 ist. Er hat auch den m-Zusammenhang eingeführt: Eine Teilmenge S von Pixeln ist m-zusammenhängend, wenn sie für beliebige zwei Pixels aus S einen m-Weg von einem Pixel zum anderen enthält.
Die m-Nachbarschaft in 2D digitalen Bildern
Eine einfache 4-Kurvemacht drei Komponenten
Eine einfache 8-Kurvemacht eine Komponente
Die allgemein bekannte Jordansche Eigenschaft einer einfachen geschlossenen Kurve:
Die Kurve unterteilt den Rest der Ebene in genau zwei Komponenten.
Die “gemischte” (8, 4)-Nachbarschaft ist nur für binäre Bilder anwendbar.
Das Zusammenhangs-Paradoxon der m-Nachbarschaft
Unter der 4-Nachbarschaft sind sowohl die grüne als auch die rote Teilmenge nicht zusammenhängend.
Unter der 8-Nachbarschaft sind beide zusammenhängend
und das ist paradox.
Ein widerspruchsfreier Zusammenhang kann definiert werden, wenn man die Zugehörigkeit des Punktes zu einer der Teilmengen
angibt.
Das Zusammenhangs-Paradoxon der m-Nachbarschaft (Fortsetzung)
Der Begriff des m-Zusammenhangs hat sich als widerspruchsvoll erwiesen: Es ist bekannt (als das Jordansche Theorem), dass eine einfache geschlossene Kurve den
Rest der Ebene in genau zwei zusammenhängende Teile (Komponenten) unterteilt. Eine einfache geschlossene Kurve unter der m-Nachbarschaft ist eine Folge von Pixeln, wobei jedes Pixel mit genau zwei Pixeln m-benachbart ist. Es existieren aber unter der 4-Nachbarschaft einfache geschlossene Kurven, welche den Rest der Ebene in mehr als zwei Komponenten zerlegen. Unter der 8-Nachbarschaft unterteilt eine einfache geschlossene Kurve die Ebene gar nicht.
Wenn man vier Pixel betrachtet, die alle eine gemeinsame Ecke haben, sieht man das Zusammenhangs-Paradoxon wieder: Unter der 4-Nachbarschaft ist keines der “Diagonal-Paare” der Pixel zusammenhängend; unter der 8-Nachbarschaft sind sie beide zusammenhängend. Dabei schneidet ein 8-Weg den anderen solchen Weg ohne dass sie gemeinsame Elemente haben, und das ist ein topologisches Paradoxon.
Das Zusammenhangs-Paradoxon der m-Nachbarschaft (Fortsetzung 2)
Rosenfeld hat vorgeschlagen, “gemischte” Nachbarschaften zu betrachten: Die 8-Nachbarschaft für den Vordergrund des Bildes und die 4-Nachbarschaft für den Hintergrund oder umgekehrt. Dieser Vorschlag hat das Zusammenhangs-Paradoxon für Binärbilder beseitigt, aber es bleibt für Bilder mit mehr als zwei Werten (Farbbilder). Außerdem definiert die (m, n)-Nachbarschaft keine Topologie des Raumes, sondern eine “Topologie” von konkreten Teilmengen des Raumes: Sie ändert sich, wenn die Teilmengen sich ändern.
Die Lösung des Paradoxons besteht darin, dass man außer Pixel auch Raumelemente anderer Arten betrachtet, nämlich die Punkte und die Cracks. (Ein Crack ist eine kurze Strecke zwischen zwei benachbarten Pixeln). Die Zugehörigkeit des Punktes zu einer der Teilmengen in dem Beispiel mit zwei diagonalen Pixelpaaren bestimmt den Zusammenhang der Paare widerspruchsfrei.
Beispiele der Begrenzung unter der (m, n)-Nachbarschaft
Die 4-Begrenzung ist nicht4-zusammenhängend
Die 8-Begrenzung ist keineeinfache Kurve
Die 4-Begrenzung einer Teilmenge unterscheidet sich von der ihres Komplements! Wenn man "von T" in der obigen Definition löscht,dann wird die Begrenzung dick.
Die m-Begrenzung einer Teilmenge T ist die Menge der Elemente (von T ), welche m-Nachbarn im Komplement von T haben
Begrenzungen unter der (m, n)-Nachbarschaft
Die Begrenzung ist einer der für die Anwendungen wichtigsten topologischen Begriffe. Die Begrenzung (oder Frontier) einer Teilmenge T des Raumes S ist die Menge aller Raumelemente, deren jede Umgebung sowohl Elemente von T als auch von ihrem Komplement S–T enthält. In der Topologie der stetigen Räume besteht die Begrenzung einer Teilmenge der Ebene aus einer oder mehreren geschlossenen Kurven. Sie ist dünn, d.h. ihr Flächeninhalt ist gleich Null. Die Begrenzung ist die gleiche für die Teilmenge T und für ihr Komplement S–T, weil die obige Definition symmetrisch bezüglich T und S–T ist
Wenn man die Umgebung eines Pixels P als die Menge der mit P m-benachbarter Pixel (einschließlich P) betrachtet, dann wird die Begrenzung zu einem dicken Streifen zwei Pixel breit. Wenn man aber die Definition so ändert, dass die Begrenzung von T nur Pixel von T enthält, dann bekommt man zwei verschiedene Begrenzungen: Die Begrenzung von T unterscheidet sich von der Begrenzung des Komplements S–T. Dies ist auch ein topologisches Paradoxon.
Widerspruchsfreie Begrenzungen
Die Lösung dieses Problems besteht darin, dass man Umgebungen benutzt, welche auf einer antisymmetrischen binären Relation basieren: Wenn das Raumelement a zu der kleinsten Umgebung des Elements b gehört, dann gehört b nicht zu der kleinsten Umgebung von a. Es folgt aus dieser Antisymmetrie, dass ein solcher topologischer Raum Elemente mit verschiedenen kleinsten Umgebungen enthalten soll. Es sind dann Raumelemente verschiedener Arten.
Lokal endliche Räume
Lokal endliche Räume (LER)
1. Jedes Element a eines LER hat seine kleinste Umgebung SON(a).
2. Wenn aSON(b), dann b SON(a).
3. Die Relation aSON(b) ist transitiv.
Ein LER ist ein klassischer T0-Raum. Ein LER versehen mit Dimensionen seiner Elemente heißt ein abstrakter Zellenkomplex.
ba
Definition: Eine nicht leere Menge S heißt ein lokal endlicher Raum, wenn jedem Element e von S bestimmte endliche Mengen von S als die Umgebungen von e zugewiesen sind.
Der Autor hat in "Axiomatic Digital Topology", JMIV, v. 26, 2006, bewiesen, dass ein LER genau dann bestimmte für die Anwendungen wichtige Eigenschaften hat, wenn die Umgebungen folgende Bedingungen erfüllen:
Weitere Definitionen
Definition AC: Ein abstrakter Zellenkomplex C=(E, B, dim) ist eine Menge E abstrakter Elemente (Zellen) versehen mit einer antisymmetrischen, irreflexiven und transitiven binären Relation B E E, genannt Berandungsrelation, und mit einer Dimensionsfunktion dim: E I aus E in die Menge I der nicht negativen ganzen Zahlen, so dass dim(e')<dim(e") für alle Paare (e',e")B.
Wenn (a, b)B dann schreibt man a<b oder man sagt, die Zelle a berandet die Zelle b. Solche Zellen heißen inzident zu einander.
Beispiele von AC-Komplexen:
2-dimensional nicht kartesisch 2-dimensional kartesisch 3-dimensional
Offene Teilmengen
Ein digitalisiertes Bild wird als ein 2-dimensionaler Komplex betrachtet. Er enthält Zellen von drei Arten: Es sind Zellen der Dimensionen von 0 bis 2. Die 2-dimensionalen Zellen, oder 2-Zellen, sind die Pixel, die 1-Zellen nennt man Cracks und die 0-Zellen sind die Punkte. Ein Crack kann ein Pixel beranden, aber nicht umgekehrt. Ein Punkt kann sowohl einen Crack als auch ein Pixel beranden
Definition OP: Eine Teilmenge OT von Zellen eines Teilkomplexes T eines Komplexes K heißt offen in T, wenn sie alle Zellen von T enthält, die von Zellen aus OT berandet werden.
Eine n-Zelle zn eines n-dimensionalen Komplexes K n, auch Grundzelle genannt, ist eine offene Teilmenge von K n, weil zn keine Zellen von K n berandet.
Definition SON: Die kleinste Teilmenge der Menge S , welche eine vorgegebene Zelle z von S enthält und offen in S ist, heißt die kleinste Umgebung (smallest (open) neighborhood) von z relativ zu S und wird mit SON(z, S) bezeichnet.
Die SON eines Pixels ist das Pixel selbst. SONs von anderen Zellen sind auf einer der folgenden Folien dargestellt.
Dimension von Zellen
Die Dimension der Zellen stellt die Halbordnung dar, welche der Berandungsrelation entspricht. Man bezeichne die Folge a<b< ... <m von Zellen eines Komplexes K, wobei jede Zelle der Folge die nächste berandet, als Berandungsweg von a nach m in K. Die Anzahl der Zellen in der Folge minus eins heißt die Länge des Berandungswegs.
Definition DZ: (Dimension einer Zelle) Die Dimension dim(z) einer Zelle z eines Komplexes K ist die Länge des längsten Berandungswegs in K, der mit z endet.
Die Zeichnung zeigt einen Komplex und die Berandungsrelation seiner Zellen. Es gibt keinen Berandungsweg, der zur Zelle p führt; also ist ihre Dimension 0. Einer der längsten Wege, der zur Zelle v führt, ist (p, e, f, v). Seine Länge ist 3; demzufolge ist
dim(v)=3. Die Dimension des Raumes ist die größte Dimension seiner Zellen.
p
e f
v
Die Dimension der Zellen ist wichtig
Nichtbeachtung der Dimension kann zu Fehlern führen.Es ist z.B. möglich, eine Topologie auf der Menge Zn so zu definieren, dass ein Punkt mit einem ungeraden Wert von x1+...+xn (Quadrate in der Zeichnung) als offen und ein mit einem geraden Wert von x1+...+xn (Kreise) als abgeschlossen
betrachtet wird. Das ist aber ein ein-dimensionaler Raum, der nicht zu der n-dimensionalen Menge Zn passt.
0 1 2 3 4 5 6 7 8 9
6543210
Die Begrenzung einer Teilmenge (grau) ist eine nicht zusammenhängende Menge abgeschlossener Punkte , was nur für einen ein-dimensionalen Raum charakteristisch ist.
Abschlüsse und kleinste Umgebungen von Zellen
Abschlüsse: SONs 2 D 3 D
Cl(c0) SON(c0)
Cl(c1) SON(c1)
Cl(c2) SON(c2)
Cl(c3) SON(c3)
Abschlüsse
Zusammenhang
Die rote Menge ist zusammenhängend; die blaue ist nichtzusammenhängend.
Die rote Menge ist zusammenhängend, die blaue - nicht.
Ein Inzidenzweg ist eine Folge von paarweise inzidenten Zellen. Eine Menge M ist zusammenhängend genau dann, wenn für beliebige zwei ihrer Zellen ein Inzidenzweg in M existiert, der diese Zellen enthält.
Die Zugehörigkeit der Zellen niederer Dimensionen wird entweder explizit oder mit Hilfe einer pauschalen Regel angegeben. So kann man z.B. sagen, "alle 0-Zellen gehören zu der roten Menge".
Topologische Begrenzung einer Teilmenge
Rote Linien zeigen die topologische Begrenzung (Frontier) des grau-schwarzen Komplexes.
Definition: Die Begrenzung Fr(T, K) einer Teilmenge T K ist die Menge aller Zellen zK, deren kleinste Umgebungen SON(z, K) Zellen sowohl aus T, als auch aus dem Komplement K–T enthält.
Die Begrenzung enthält keine Grundzellen (d.h. keine n-Zellen in einem n-Raum; keine Pixels in dem 2D-Raum).
Offene Begrenzung einer Teilmenge
Blaue Linien und Quadrate zeigen die offene Begrenzung des grau-schwarzen Komplexes. Sie enthält keine 0-Zellen.
Definition: Die offene Begrenzung Op(T, K) einer Teilmenge T von K ist die Menge aller Zellen zK, deren Abschlüsse Cl(z, K) Zellen sowohl aus T als auch aus dem Komplement K–T enthalten
Kartesische Komplexe und kombinatorische Koordinaten
a bKartesischer (a) und allgemeiner (b) Komplex
P ist eine 0-Zelle (Punkt), C1 und C2 sind 1-Zellen (einhorizontaler und ein vertikaler Crack), F ist eine 2-Zelle (Pixel).
F=(3,5)
C1=(7,6)
C2=(6,3)
P=(4,6)
8
7
6
5
4
3
2
1
0 X
Y
0 1 2 3 4 5 6 7 8
Ein kartesischer (a) und ein allgemeiner (b) Komplex.
P ist eine 0-Zelle (ein Punkt), C1 und C2 sind 1-Zellen (ein horizontaler und ein vertikaler Crack), F ist eine 2-Zelle (ein Pixel).
Kartesische Komplexe (Fortsetzung)
Definition: Ein n-dimensionaler kartesischer Komplex K ist ein abstrakter Zellenkomplex, wobei die Menge seiner Zellen ein kartesisches Produkt der Mengen der Zellen von n eindimensionalen Komplexen Xi, i=1, 2, ..., n; ist. Die Dimension einer Zelle A=(a1, a2, ..., an) ist gleich der Summe der Dimensionen ihrer Komponenten a1, a2, ..., an. Die Berandungsrelation von K wird wie folgt definiert: Die Zelle A=(a1, a2, ..., an) berandet die Zelle B=(b 1, b2, ..., bn) genau dann, wenn für alle i, i=1, 2, ..., n; die Komponente ai die Komponente bi entgweder berandet oder mit ihr identisch ist. Dabei muss die Dimension von A kleiner als die von B sein.
Diese Definition wird einfacher, wenn man die Relation „Seite von“ benutzt: Eine Zelle A heißt Seite der Zelle B genau dann, wenn A entweder die Zelle B berandet oder mit B identisch ist. Im letzteren Fall heißt A eine uneigentliche Seite der Zelle B. In dem kartesischen Komplex K ist die Zelle A=(a1, a2, ..., an) eine Seite der Zelle B=(b 1, b2, ..., bn) genau dann, wenn jedes ai für i=1, 2, ..., n; eine Seite von bi ist.
Datenstrukturen
Datenstrukturen
0 1 2 3 4 5 6 7 8
76543210
876543210 0 1 2 3 4 5 6 7 8
Standard-Gitter geeignet zum Speichern
von Bildern
Beide Gitter sollen gleichzeitig benutzt werden; der Übergang vom einem zum anderen ist einfach:
xs=int(xk /2); ys=int(yk /2).
Kombinatorisches Gitter geeignet für geometrische
Berechnungen
Bekannte Datenstrukturen• Run-length code• Crack code• n-G-map• Boundary
representation
K1 K2 K3 K4 K5 K6
F1 F2 F3 F4
P1 P2 P3 P4
S
Körper
Körper
Boundary representation
Geometrische 2D-Blockzellenliste
Liste der Linien (1-Blöcke) Liste der Regionen:
Ind Pst Pend Rr RlStart Ende
L1 P1 P2 R0 R1 M1 M1
L2 P2 P3 R0 R3 M2 M3
L3 P3 P1 R0 R2 M4 M4
L4 P1 P4 R1 R2 L5 P4 P2 R1 R3 M5 M5
L6 P3 P4 R2 R3
R0
Metrik
Liste der Verzweigungs-punkte (0-Blöcke)
Marke N SON LinienP1 3 L1 , + L3 , L4
P2 3 +L1 , L2 , +L5
P3 3 +L2 , L3 , L6
P4 3 +L4 , L5 , +L6
Ind NCl Zgr Verkettete Liste
R0 6 Z1 P1+L1 P2 ...
R1 6 Z2 P1+L4 P4 ...
R2 6 Z3 P1 L3 P3 ...
R3 6 Z4 P2 L5 P4 ...
Liste der Regionen (2-Blöcke):
M1 M4
P 4
L1
L3
L 2
R1
R2
L 5
L4
R 3
L6
P 2
P 3
P 1
M 5
M2 M3
R0
Theorie der 3D-Blockzellenliste
Theorem: Die Umgebung SON*(ck, M n) einer k-Zelle ck mit
0kn1 einer n-Mannigfaltigkeit M n ist В-isomorph zu einer
(nk1)-dimensionalen Sphäre, wenn ck nicht zum Rand M n von M
n gehört. Die Menge Cl*(ck, M n) ist dann В-isomorph zu einer (k1)-dimensionalen Sphäre.
V1
V5
V6
V3V4
V1V2
V5 V6
V3V4
Die Umgebung SON* einer 0-Zelle und die zu ihr B-isomorphe topologische Sphäre
Planare Darstellung einer 2-Sphäre
V1V2
V5 V6
V3V4
V5
V1
V2V4
V3
V7
V8 V6
Beispiel: Die Oberfläche eines Oktaeders kann als eine planare Karte gezeichnet werden
Für jeden zu einer 2-Sphäre B-isomorphen Komplex existiert eine planare Darstellung, d.h. er kann in der Ebene gezeichnet werden. Eine der Zellen soll dabei als die äußere Region dargestellt werden.
Liste der Linien (1-Blöcke):
Ind Pst Pend NSON Zeiger Verkettete Liste
L1 P1 P2 4 Z5 F1V1+F2V0
L2 P1 P3 6 Z6 F2V2 F5V1+F1V0
...
Liste der Flächen (2-Blöcke):
Ind +Vol Vol NCl Zeiger Verkettete Liste
F1 V0 V1 6 Z7 P1+L2P2+L5P1 L2
...
3D-Zellenliste
2 KörperListe der Punkte (0-Blöcke):
Ind NLIN Linien
P1 4 L1, L2, L3, L4
P2 3 +L1, L5, +L8
P3 4 +L2, +L5, L6, L9
P4 3 +L3, +L6, L7
P5 4 +L4, +L7, L8, +L9
P1
P2
P3
P4
P5
L1
L2
F1
F2
F5
L2
F1
F5
F2
Entlang L2
V2 V1
Liste der Körper (ähnlich der Liste der Punkte)
Vorlesung 2:
Einige einfache Algorithmen
Regel für die Koordinatenzuweisung
Die Benutzung dieser Regel ermöglicht die Arbeit mit Zellen niederer Dimensionen im Standardgitter.
xs=xk/2; ys=yk/2;
xk = 2 3 4 5 6 7 8
yk=6
5
4
3
2
(4, 7)
(4, 6)
(5, 7)
Verfolgung einer Begrenzung in binären 2D-Bildern
0
3
2
1
Vier Richtungen von Cracks und die zwei Pixel Pos und Neg, die getestet werden sollen (Koordinatensystem der Computergrafik)
Pseudo-code
P.X=Start.X; P.Y=Start.Y; direction=1; // ”P” ist der laufende Punktdo { Pos=P+Positive[direction]; // ”Pos” ist das positive Pixel Neg=P+Negative[direction]; // ”Neg” ist das negative Pixel if (image[Pos/2]==foreground) // Pos/2 ist im Standardgitter direction=(direction+1) MOD 4; // positive Wendung else if (image[Neg/2]==background) // Neg/2 ist im Standardgitter direction=(direction+3) MOD 4; // negative Wendung P=P+step[direction]; // ein Schritt in die neue Richtung} while( P.X!=Start.X || P.Y!=Start.Y);
Start
X
Y
Neg=(x+1, y-1)
Pos=(x+1, y+1)
P=(x, y)
dir
Vordergrund
positive für Computergrafik
Suchen des Startpunktes für die Verfolgung
Um eine mehrfache Verfolgung zu vermeiden, sollen die bereits besuchten senkrechten Cracks markiert werden. Der Algorithmus ist etwas einfacher, wenn er nur an Übergängen vom Hintergrund zum Vordergrund starten soll.
Das Objekt des Vordergrunds bleibt auf der negativen Seite
positive für Computergrafik
Das Suchen
Verfolgung einer Begrenzung in binären 2D-Bildern
Um den Startpunkt für die Verfolgung zu finden, muss das Bild Zeile für Zeile durchsucht werden. Wenn ein Vordergrundpixel unmittelbar nach einem Hintergrundpixel gefunden wurde, ist ein nach unten gerichteter Begrenzungscrack C gefunden. Der Startpunkt ist dann sein oberer Endpunkt. Die Verfolgung läuft in kombinatorischen Koordinaten. Der Algorithmus geht von einem Begrenzungspunkt zum nächsten entlang den Begrenzungscracks. Um den nächsten Begrenzungscrack zu erkennen, testet der Algorithmus zwei Pixel “Pos” und “Neg”, die vor dem aktualen Crack liegen. Der Algorithmus berechnet die Koordinaten dieser Pixel indem er die 2D-Vektoren “Positive[direction]” und “Negative[direction]” zum Vektor “P” des aktuellen Punktes addiert. Die Vektoren sind als kleine Felder von Konstanten definiert. Dann holt der Algorithmus die Grauwerte (oder Farben) aus den Pixeln des vorliegenden Bildes, indem er vorher die kombinatorischen Koordinaten von “Pos” und “Neg” zu Standardkoordinaten transformiert. Dies wird einfach durch eine Integer-Division durch 2 gemacht. Die Richtung des nächsten Cracks wird abhängig von den Werten von "Pos" und "Neg" bestimmt und durch eine Addition von 1 oder 3 modulo 4 zur aktuellen Richtung berechnet. Dann macht der aktuelle Punkt „P“ einen Schritt in der neuen Richtung. Der Prozess endet, wenn der Startpunkt wieder erreicht ist.
Code von “Trace” in C++
// Schritt vom Punkt zum positiven Pixel:CPoint ToPos[4]={CPoint(1,1),CPoint(-1,1),CPoint(-1,-1)CPoint(1,-1)}; // Schritt vom Punkt zum negativenPixel:CPoint ToNeg[4]={CPoint(1,-1),CPoint(1,1),CPoint(-1,1)CPoint(-1,-1)};// Schritt zum nächsten Punkt: CPoint Step[4]={CPoint(2,0),CPoint(0,2),CPoint(-2,0),CPoint(0,-2};
int Value(BYTE *img, int NX, int NY, CPoint P){ if(P.x>=0 && P.x<2*NX && P.y>=0 && P.y<2*NY)
return img[P.y/2*NX+P.x/2]; return 0; // Die Funktion gibt den Wert der Zelle P zurück, falls P im Bild ist}
int Label(BYTE *img, int NX, int NY, CPoint C)// Markierung eines Cracks{ int Dimension=(C.x & 1)+(C.y & 1); if (Dimension!=1) { printf("Label: (%d,%d) is no crack. Stop\n",C.x,C.y); return -1; } img[C.y/2*NX+C.x/2]|=VERT; // Markierung eines Bits, z.B. VERT=1. return 1;}
Code von “Trace” in C++ (Fortsetzung)
int Trace(BYTE *img, int NX, int NY, CPoint Start){ int cnt=0, rv, dir=1; iPoint P(Start); // laufender Punkt do { CPoint Pos=P+ToPos[dir]; // Pos und Neg sind Pixel CPoint Neg=P+ToNeg[dir]; int ValPos=Value(img, NX, NY, Pos); // Wert von img[Pos] int ValNeg=Value(img, NX, NY, Neg); // Wert von img[Neg] if (ValPos>0) dir=(dir+1)%4; // positive Wendung else if (ValNeg==0) dir=(dir+3)%4; // negative Wendung CPoint C(P.x,P.y+1); // Crack unterhalb von P if (dir==1) rv=Label(img,NX,NY,C); if (rv<0) { printf(”Error at C=(%d,%d)\n",C.x,C.y); return -1; } P=P+Step[dir]; cnt++; } while(P!=Start) && cnt<1000); // Absicherung gegen tote Schleife return cnt;}
C++ ohne MFC hat keine Klasse “CPoint”, deren Objekte als 2D-Vektoren mit Addition benutzt werden können. Wenn man eine “Konsole” benutzt, kann man die Klasse CPoint mit den Operatoren "+" und "!=" selbst definieren. Sonst muss man die Addition von Vektoren Komponente für Komponente machen. Dann soll man auch "BYTE" als "unsigned char" definieren.
Verfolgung von Begrenzungen in nD-Bildern
Der oben beschriebene Algorithmus hat einen Nachteil: Der Inhalt der Hilfsfelder ToPos[4], ToNeg[4] und Step[4] ist für die Verfolgung in einem 2D-Raum festgelegt. Man kann aber den Algorithmus so umgestalten, dass er ganz ohne diese Felder auskommt. Dadurch wird er für die Verfolgung von Begrenzungen in Räumen beliebiger Dimension und bei beliebiger Orientierung der Koordinatenachsen ohne jegliche Änderung anwendbar. Bei Dimensionen größer als 2 wird dann die Begrenzung in einer 2D-Schicht verfolgt.
a b
2D-Schicht
Out
Inn
Step
Cn–1
Norm
Cn–2
color
Parameter und Variablen des universellen Algorithmus
Der Algorithmus bekommt als Parameter ein n-dimensionales Bild “image”. Es kann sowohl binär als auch "farbig" sein. Er bekommt außerdem die Vektoren Start, Norm und Step. Komponenten von Start sind die kombinatorischen Koordinaten einer (n–1)-dimensionalen Zelle in der Begrenzung einer n-dimensionalen Teilmenge S, deren Grundzellen den Wert “color” haben. Dieser Wert ist auch ein Parameter des Algorithmus. Die Zellen des Komplements von S können beliebige andere Werte haben. Der Algorithmus betrachtet die Grundzellen mit dem Wert color als Vordergrund und die anderen als Hintergrund. Am Anfang der Verfolgung wird der laufende Vektor Cn_1 (der auf eine (n1)-dimensionale Begrenzungszelle zeigt) gleich Start gesetzt. Der Einheitsvektor Norm ist die Außennormale von Cn_1 und der Einheitsvektor Step geht von Cn_1 zu einer (n–2)-dimensionalen Zelle, die mit Cn_1 inzident ist.
Pseudo-Code von "TraceUni"
void TraceUni(iVect Start, iVect Norm, iVect Step, int color, char image[]){ iVect Cn_1=Start, Cn_2, Ctest, Inn, Out, StepNew; do { Cn_2=Cn_1+Step; // Schritt zu der (n-2)-Zelle Cn_2 Ctest=Cn_2+Step; // Schritt zu der mit Cn_2 komplanaren (n-1)-Zelle Inn=Ctest-Norm; Out=Ctest+Norm; // zwei mit Ctest inzidenten Grundzellen // Die Werte von Inn und Out prüfen und die nächste Begrenzungszelle bestimmen: if (image[Out]==color && (image[Inn]==color || Cn_2InObject==TRUE) ) { Cn_1=Cn_2+Norm; StepNew=Norm; // Schritt zu der nächsten (n-1)-Zelle Norm=-Step; Step=StepNew; } // Cn_2InObject ist "wahr", wenn die Zelle Cn_2 zum Vordergrund gehört else if (image[Inn]!=color && (image[Out]!=color || Cn_2InObject==FALSE) ) { Cn_1=Cn_2-Norm; StepNew=-Norm; // Schritt zu der nächsten (n-1)-Zelle Norm=Step; Step=StepNew; } else Cn_2=Ctest; // Schritt zu der nächsten (n-1)-Zelle } while((Cn_1==Start)==FALSE ); // hält an, wenn Start wieder erreicht ist} // end TraceUni.
Füllen des Inneren einer (n-1)-Mannigfaltigkeit(getestet für n=2,3,4)
Um zu prüfen, ob eine n-Zelle P eines nD-Raumes im Inneren einer (n1)-dimensionalen Mannigfaltigkeit M liegt, genügt es, die Schnittstellen von M mit einem Strahl zu zählen, der von P bis zum Rand des Raumes geht, und die Parität zu prüfen. Das Zählen ist nur dann einfach, wenn der Raum ein Zellenkomplex ist.
Der Pseudocode:Wähle eine Koordinatenachse A des Kartesischen Raumes, z.B. die X-Achse. Markiere alle (n1)-Zellen von M, deren Normale parallel zu A ist.
for ( jede Zeile R parallel zu A ){ fill=FALSE; for ( jede n-Zelle Z in der Zeile R ) { if ( die erste (n1)-Seite von Z markiert ) fill = NOT fill; if ( fill==TRUE ) Z = Vordergrund; else Z = Hintergrund; }}
Sonst ist es schwer, zwischen einem Schnitt und einer Berührung zu unterscheiden:
Kein Problem in einem Komplex:
Füllen des Inneren einer (n-1)-Mannigfaltigkeit
Wenn eine Kurve als Folge von Pixeln vorliegt, dann ist es unmöglich, anhand einer einzigen Zeile zwischen einem Schnitt und einer Berührung zu unterscheiden. In der Tat, man sieht, dass jeweils die dritte Zeile in den zwei oberen Zeichnungen identisch ist. Für die Entscheidung müssen drei nacheinander folgende Zeilen untersucht werden.
Aber, wenn man das Bild als einen Komplex darstellt, dann ist die Kurve eine Folge von abwechselnden 0- und 1-Zellen. Jetzt wird das obige Problem einfach, weil ein Strahl, der aus Pixeln und senkrechten 1-Zellen besteht, eine Kurve nur an einer 1-Zelle schneiden kann. Eine Berührung ist unmöglich.
Vor dem Füllen sollen alle senkrechten 1-Zellen der Kurve, oder alle (n–1)-dimensionalen Zellen der Mannigfaltigkeit, die zu einer ausgewählten Koordinatenachse A orthogonal sind, in dem zu füllenden Bild markiert werden. Der Algorithmus durchläuft das Bild Zeile für Zeile parallel zu A. Am Anfang jeder Zeile wird fill=FALSE gesetzt. Jedesmal, wenn eine markierte Zelle vorkommt, wird fill invertiert: fill=NOT fill. Wenn fill wahr ist, wird die nächste Grundzelle mit dem Wert des Vordergrunds markiert, sonst mit dem des Hintergrunds.
Markierung der Komponenten in einem n-dimensionalen Raum
Der Raum ist als ein n-dimensionales Feld S dargestellt. Die Indizes entsprechen den Koordinaten. Jedes Element von S enthält eine ”Farbe". Nach der Markierung soll jedes Element die Marke der Komponente bekommen, zu der es gehört (in einem anderen Feld L).
1 2 3 4 1
1
1
1 1
2
2
2
3
3
4
? 3
?
?
2
0 1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16 17
14 14
16
12 12
10 10
14
12
10
14
12
Der naive Zugang:im Worstcase NY³/2 Änderungen
Optimale Lösung:im Worstcase NX/2 Änderungen
Markierung der Komponenten (Fortsetzung)
Gegeben sei ein segmentiertes nD-Bild. Das Problem besteht im Finden der maximalen zusammenhängenden Teilmengen, wobei jede Teilmenge Grundzellen einer einzigen Farbe enthält. Das sind die Komponenten. Dann soll man die Komponenten nummerieren und jedem Element des Bildes die Nummer seiner Komponente zuweisen. Diese Nummern sollen in einem zusätzlichen Feld L gespeichert werden.
Das Bild soll eine relativ kleine Anzahl von Farben enthalten. Sonst kann es passieren, dass z.B. jedes Pixel eines Farbbildes eine Komponente ist.
Der naive Zugang besteht im Abtasten des Bildes Zeile für Zeile und im Zuweisen jedem Element (z.B. Pixel), welches mit keinem bereits besuchten Element der gleichen Farbe benachbart ist, der nächsten nicht benutzten Marke. Wenn das aktuelle Element E besuchte Elemente der gleichen Farbe in seiner unmittelbaren Umgebung hat und diese unterschiedliche Marken haben, dann bekommt E die kleinste dieser Marken. Alle in der Umgebung von E betrachteten Marken werden auch durch diese kleinste Marke im ganzen Bild ersetz. Diese Änderung kann im Worstcase (bei n=2) bis zu NY²/2 Pixel betreffen, wobei NY die Höhe des Bildes ist. Die Gesamtanzahl der Änderungen kann dann gleich NY³/2 werden.
Das Wurzelverfahren
Die Idee dieser Methode (Galler und Fischer, 1964) wird für den 2D-Fall erläutert; sie ist aber auch für eine beliebige Dimension anwendbar. Die Marke einer Komponente muss so gewählt werden, dass es möglich wird, ausgehend von dieser Marke die Adresse eines bestimmten Pixels im Speicher zu finden. Dieses Pixel wird die Wurzel der Komponente genannt. Beim Start des Algorithmus soll jedes Pixel (x, y) des Feldes L den Index x+NX*y als seine Marke bekommen, wobei NX die Anzahl der Spalten im Bild ist. Dadurch wird am Anfang jedes Pixel als eine Komponente betrachtet und ist selbst die Wurzel dieser Komponente.Der Algorithmus durchläuft das Bild Zeile für Zeile. Wenn das aktuelle Pixel P benachbarte Pixel von derselben Farbe unter den bereits besuchten Pixeln hat, dann bekommt P als Marke die kleinste Marke der Wurzeln dieser Pixel. Die Marken dieser Wurzel werden durch diese kleinste Marke ersetzt. Dadurch bekommen alle Komponenten, die sich an den aktuellen Pixel treffen, ein und dieselbe Wurzel und werden dadurch zu einer Komponente. Die Marken der Pixel, die keine Wurzeln sind, bleiben unverändert (um Zeit zu sparen). Die Änderungen betreffen in dem oben genannten Worstcase nur NX/2 Pixel. Nach dem ersten Bilddurchlauf enthält jedes Pixel eine Marke, die entweder unmittelbar oder rekursiv über andere Marken auf die Wurzel seiner Komponente zeigt. Während des zweiten Durchlaufs werden die Marken durch aufsteigende ganze Zahlen ersetzt.
Pseudo-Code des Wurzelverfahrens
Gegeben ein Bild S, ein zweites Feld L von der gleichen Größe muss definiert werden. Jedes Element von L muss wenigstens log2|S| Bits enthalten, wobei |S| die Anzahl der Elements von S ist. Der Algorithmus durchläuft das Bild zweimal: Nach dem ersten Durchlauf enthält jedes Element von L den Index der “Wurzel” seiner Komponente als seine Marke. Während des zweiten Durchlaufs werden die Marken durch aufsteigende ganze Zahlen ersetzt. Diese Version betrachtet Zellen aller Dimensionen, wobei jede Zelle eine Farbe hat.
1 2 31
41 52 63
71 81 93
1 2 1
1 2 1
1 1 1
for (i=0; i < |S|; i++) L[i]=i;for (i=0; i < |S|; i++){ dim=dimension(i);
for (j=0; j < Ninc[dim]; j++){ k=Index(i, j); if (S[k] = = S[i] ) SetEquivalent(i, k, L);}
}SecondRun(L, |S|);
1. Durchlauf 2. Durchlauf
Der Pseudo-Code:
dimension(i) gibt die Dimension der Zelle "i" an;Ninc[dim] ist die Anzahl der mit der Zelle "i" ínzidenten Zellen, die bereits besucht wurden.
Pseudo-Code der Funktionen (Subroutinen)
void SetEquivalent(i, k, L){ if ( Root(i, L) < Root(k, L) ) L[Root(k, L)] = Root(i, L); else L[Root(i, L)] = Root(k, L);}
int Root(k, L){ for (int i = 0; i<|L|; i++) { if (k = = L[k] ) return k; k = L[k]; } ErrorMessage( ); return 1;}
void SecondRun(L, N){ for (int i = 0, int count = 1; i < N; i++)
{ int label = L[i]; if ( label = = i ) { L[i] = count; count++; } else L[i] = L[label];}
}
Vorlesung 3 Geraden in einem 2D-Raum
(digitale Strecken)
Halbräume und konvexe Mengen
Definition HR: Ein abgeschlossener digitaler Halbraum eines nD-Raumes ist der Abschluss der Menge aller n-Zellen, deren Koordinaten einer linearen Ungleichung genügen. Das Komplement eines abgeschlossenen Halbraumes ist ein offener Halbraum. Ein digitaler Halbraum eines 2D-Raumes heißt digitale Halbebene.
Definition KON: Ein nicht leerer Durchschnitt von digitalen Halbräumen heißt eine digitale konvexe Teilmenge des Raumes.
14
12
10
8
6
4
2
00 2 4 6 8 10 12 14 16 18
Y
X
2x-3y+2>0;
Halbräume und konvexe Mengen
Für beliebige zwei Zellen aus einer digitalen konvexen Menge M existiert mindesten eine DSS, welche durch diese Zellen geht und vollständig im Abschluss von M liegt. Diese Aussage soll für beliebige Dimension gelten.
Ein Beweis ist erwünscht.
(Für beliebige n Zellen aus einer n-dimensionalen digitalen konvexen Menge M existiert mindesten eine (n-1)-dimensionalen digitale Hyperebene, welche durch diese Zellen geht und vollständig im Abschluss von M liegt).
Definition einer digitalen Strecke (DSS)
SPEP
ENSN
0 2 4 6 8 10 12 14 16 18 X
14
12
10
8
6
4
2
0
+
–
+
–
+
–
+
–
+
–
+
–
+
–+
–
Y
+
–
Beispiel einer Halbebene und einer DSS in kombinatorischen Koordinaten
Definition: Eine digitale Strecke (digital straight segment) (DSS) ist eine zusammenhängende Teilmenge der Begrenzung einer digitalen Halbebene
positive Basis
negative Basis
Digitale Strecken und Kollinearität
Definition KOL: Eine Zelle c heißt streng kollinear mit zwei anderen Zellen a und b wenn die folgende Bedingung erfüllt ist:
(xb xa)·(yc ya) (xc xa)·(yb ya) = 0.
Die Zelle c líegt auf der positiven Seite des geordneten Paares von Zellen a und b wenn:
(xb xa)·(yc ya) (xc xa)·(yb ya) > 0.
Sie liegt auf der negativen Seite der Zellen a und b wenn:
(xb xa)·(yc ya) (xc xa)·(yb ya) < 0.
Drei Zellen heißen semi-kollinear, wenn es eine DSS gibt, auf der sie alle liegen.
14
12
10
8
6
4
2
00 2 4 6 8 10 12 14 16 18
Y
X
P1
P2
P3
P4
P2 ist streng kollinear mit (P1, P3). P2 liegt auf der positiven Seite von (P1, P3). P4 liegt auf der negativen Seite von (P1, P3).
Parameter einer DSS
Laut der obigen Definition ist eine digitale Halbebene der Abschluss der Menge von Pixeln, deren Koordinaten einer linearen Ungleichung genügen. Die Ungleichung trennt die Pixel in positive und negative.
Für die Ungleichung gibt es eine Standardform:
Werte der trennenden Standardform TSF H(x,y)=a·x+b·y+c liegen für positive Pixel im Intervall:
0H(x,y)max (|a|, |b|)–e;
und für negative Pixel im Intervall:
–max (|a|, |b|)H(x,y)–e;
wobei die Konstante e=2 für kombinatorische Koordinaten und e=1 für Standardkoordinaten ist. Die Parameter a und b sind teilerfremde ganze Zahlen. Diese Ungleichungen sollen für mindestens drei Pixel zu Gleichungen werden.
Die Idee des Algorithmus
Erkennung der DSS während der Verfolgung
+ +
+ +
+
– –
–
– –
–
+ +
nächster Crack
nächstes positives Pixel
alte positive Basis
alte negative Basis
neue negative Basis
neue positive Basis
Die trennende Standardform erfüllt H(x, y)0 für positive Pixel
Erkennung der DSS während der Verfolgung (Fortsetzung)
Es sei C der Koordinatenvektor eines Cracks der gegebenen digitalen Kurve und DIR seine Richtung (DIR=0, 1, 2 oder 3).
Am Anfang einer DSS, die aus einem Crack besteht, sind ihre Parameter zu bestimmen.
Für jeden Crack C sind folgende Schritte durchzuführen:
1. Finde das positive P und das negative N Pixel, die mit dem Crack C inzident sind.
2. Wenn die aktuelle Richtung DIR eine verbotene ist, endet die DSS. Sonst berechne die Werte HP und HN von H(x, y) für die Pixel P und N.
3. Wenn einer dieser Werte außerhalb des erlaubten Intervalls, dicht an seinem Rande liegt, dann sollen die Parameter der DSS nach bestimmten Regeln geändert werden.
4. Wenn einer der Werte HP und HN weiter außerhalb des erlaubten Intervalls liegt, dann endet die DSS.
5. Sonst gehe zum nächsten Crack über und wiederhole die Schritte 1 bis 5.
Sparsame Codierung von DSS-Folgen
Folgende Methoden der Codierung von digitalen Kurven sind bekannt:1. Freeman-Code: Sparsam, aber bedingt anwendbar für Begrenzungen.2. Crack-Code: Sparsam, auch für Begrenzungen, aber nicht "geometrisch". 3. Polygonale Approximation: Geometrisch, aber begrenzte Genauigkeit.4. DSS mit zusätzlichen Parametern: Geometrisch und genau.
Eine DSS wird eindeutig durch eine lineare Funktion H(x, y) definiert:
H(x, y)=a·(xxs,)+b·(y ys) + L.
Die Koeffizienten a und b definieren den Anstieg der DSS, xs und ys sind die Koordinaten des Startpunktes der DSS, L ist der Wert von H am Startpunkt. Es wurde bewiesen, dass a und b immer als ganze teilerfremde Zahlen gewählt werden können. Dann kann auch L eine ganze Zahl im Bereich [0, |a|+|b|-1] sein. Die Koordinaten (xs, ys ) kann man sparsam codieren, indem man für jede geschlossene Kurve nur den Startpunkt der ersten DSS explizit speichert. Der Startpunkt jeder nächsten DSS ist dann eindeutig durch a, b, L und die Anzahl NC der Cracks in der DSS definiert.
Sparsame Codierung von DSS-Folgen (Fortsetzung)
Es genügen also vier ganze Zahlen pro DSS: NC, L, a und b. Weil die meisten DSS relativ kurz sind, sind diese Zahlen fast immer klein: Alle vier können in einem Wort von 2 Byte gepackt werden. Für längere DSS können auch längere Worte der Länge von 3 bis 8 Byte benötigt sein, aber solche Worte kommen selten vor. Die durchschnittliche Anzahl von Byte pro DSS liegt zwischen 2 und 3.
Dünne und dicke DSS
Für die Bildanalyse sind die dünnen DSS besonders wichtig, weil mit ihrer Hilfe Begrenzungen beschrieben werden können. Die dicken DSS sind nur für das Zeichnen von Bildern interessant; aber für diese Zwecke gibt es bessere Möglichkeiten, die in der Vorlesung 5 erläutert werden.
Anwendungen der DSS
1. Schätzung des Umfangs einer Teilmenge in einem 2D-Bild.
2. Darstellung von Objekten in 2D-Bildern als Polygone mit dem Zweck der Formanalyse.
3. Sparsame und genaue Codierung von Bildern.
Wie weiter oben erläutert, gibt es die Möglichkeit, eine DSS durch vier ganze Zahlen genau zu definieren. Ein quantisiertes Grauwertbild besteht aus Gebieten mit jeweils einem konstanten Wert. Die Begrenzungen dieser Gebiete werden mit den DSS codiert. Ein sparsamer Code braucht im Durchschnitt 2,3 Bytes pro DSS. Aus diesem Code kann das quantisierte Bild genau wiederhergestellt werden.
Dieses Grauwertbild aus 390480=187200 Pixeln mit 32 Graustufen wurde mit 60080 Bytes codiert. Die Komprimierungsrate beträgt ca. 3,1. Die Abbildung zeigt das aus dem Code fehlerfrei rekonstruierte Bild.
Schnelle Codierung von Bildern durch DSS-Polygone und Erkennung kreisförmiger Objekte
Dieses Binärbild von 13001030 Pixeln wurde mit DSS codiert und alle
57 kreisförmige, auch beschädigte, Objekte wurden erkannt. Die ganze
Verarbeitungszeit betrug 56 ms auf einem PC mit einem Pentium-
Processor mit 700 MHz.
Schätzung des Flächeninhalts und des Umfangs einer 2D-Teilmenge
Schwarz und rot– große Pixel.
Naive Schätzung: Umfang=Anz. Cracks12 1=12 Pixel; 161=16 Cracks12 1=12 Pixel; 20 1=20 Cracks48 0.25=12 Pixel; 40 0.5=20 CracksEine Rotation ändert das Ergebnis bis 41%. Erhöhung der Auflösung bringt keine Vorteile
0 1 2 3 4 5 6
0
1
2
3
4
5
6
7
8
9
10
Umfang als Summe der Längen der DSS(2,1) (0,6) (2,7) (3,9) (5,8) (6,1) (2,1) 5.38 + 2.24 + 2.24 + 2.24 + 7.07 + 4.0=23.17 Genauigkeit steigt mit der Auflösung
Vorlesung 4Fortgeschrittene Algorithmen
der Digitalgeometrie
Digitale Kreisbögen
Man verbinde ein positives Pixel mit einem negativen und man errichte den Lot in dem Mittelpunkt der verbindenden Strecke. Die Halbebene, die das negative Pixel enthält, enthält auch den Mittelpunkt des Bogens.
Der Durchschnitt aller Halbebenen heißt das Mittelpunkt-Polygon MP. Wenn MP leer wird, ist der aktuelle Bogen zu Ende und der nächste Bogen beginnt.
Eine digitale Kurve soll in möglichst lange digitale Kreisbögen zerlegt werden.
X
Y
MP
Pos
Neg
Ähnlich wie im 2D-Fall, kann ein DPP als eine zusammenhängende
Teilmenge eines Halbraumes definiert werden. Für ein DPP kann
auch eine trennende Standardform TSF
H(x, y, z)=a·x+b·y+c·z+d
definiert werden. Es gibt auch den einfachen und schnellen
Erkennungsalgorithmus, der es ermöglicht, für einen beliebigen
zweidimensionalen Teilkomplex im 3D-Raum zu entscheiden, ob er
ein DPP ist. Trotzdem bleibt das für die Anwendungen wichtige
Problem der Zerlegung einer Oberfläche in möglichst große DPP bis
heute ungelöst.
Digitale Ebenenstücke (DPP) im 3D-Raum
Das ähnliche 2D-Problem ist relativ einfach, weil jede DSS genau zwei mit ihr benachbarte Cracks Ci, i=1, 2; hat: Am Anfang und am Ende. Jeder dieser Cracks kann zu der DSS D hinzugefügt werden, solange die Menge D{Ci} eine DSS bleibt.
Das gleiche Problem ist im 3D-fall wesentlich komplizierter, weil ein bereits entdecktes DPP durch mehrere benachbarte Facetten erweitert werden kann.
Unterteilung einer Oberfläche in digitale Ebenenstücke
a bDPPs, erzeugt bei einer zufälligen Auswahl der Facetten (a) und DPPs, erzeugt durch den Aufbau einer konvexen Hülle (b)
Uns ist kein Algorithmus bekannt, um zu entscheiden, welche Facetten und in welcher Reihenfolge hinzugefügt werden sollen, um die minimale Anzahl der DPP zu erreichen. Bei einer zufälligen Auswahl der Facetten ist die Menge der erhaltenen DPP chaotisch (a).
Konvexe Hülle
Ein 3D-Objekt Seine konvexe Hülle
Keine sichtbare Kante
Konvexer Punkt, aber keine lokale Ecke
Das Start-Polygon
1
23
4
56
Lokale Ecke
1. Erstelle eine Liste der lokalen Ecken.
2. Suche vier nicht komplanare lokale Ecken und erzeuge die Zellenliste (nächste Folie) eines Tetraeders. Das ist jetzt die laufende konvexe Hülle LKH.
3. Für jede lokale Ecke L suche alle sichtbaren Flächen der LKH. Wenn es keine gibt, ignoriere L. Sonst verbinde L mit allen Kanten der Begrenzung des sichtbaren Bereichs, speichere L und alle Dreiecke und lösche den sichtbaren Bereich.
4. Wiederhole Schritt 3 für alle lokalen Ecken.
5. Wenn es komplanare Dreiecke gibt, vereinige sie zu Polygonen.
Ende des Algorithmus.
Die konvexe Hülle (Fortsetzung)
Der Algorithmus
Beispiel einer Block-Zellenliste
List of 1 point; 20 lines; 10 faces and 1 volume----------------- Partial list of points---------------Point 1 (2;2;2) is incident with 3 lines. Label=0; The lines: -1; -3; -2;Point 2 (16;2;2) is incident with 3 lines. Label=0; The lines: 1; -7; -5;Point 3 (2;16;2) is incident with 3 lines. Label=0; The lines: 2; -8; -4;Point 4 (2;24) is incident with 4 lines. Label=0; The lines: 3; -13; -9;-6;Point 5 (16;16;2) is incident with 3 lines. Label=0; The lines: 4; -10; 5;Point 6 (16;2;4) is incident with 4 lines. Label=0; The lines: 6; -14; -12; 7;
etc.
List of 12 points;
Beispiel einer Block-Zellenliste (Fortsetzung)
Beispiel einer Block-Zellenliste (2. Fortsetzung)
104 Punkte, 168 Kanten und 66 Flächen
Körper, wiederhergestellt aus der Block-Zellenliste
Beispiel einer großen Block-Zellenliste
Methoden der Verfolgung und Codierung von Oberflächen in 3D
Methoden der verlustfreien Codierung von Oberflächen
1. Methode von D. Gordon und J.K. Udupa (1989), basierend auf der Traversierung des Digraphs, der die Nachbarschaft der Facetten darstellt . Es ist eine einfache, aber nicht sparsame Methode: Der Code braucht 6 oder 12 Byte (je nach Größe des Bildes) pro Facette. Die Möglichkeit, den Zusammenhang durch singuläre Zellen zu berücksichtigen, ist eingeschränkt.
2. Spiralförmige Verfolgung (Kovalevsky, V., 1999). Es ist eine komplizierte Methode; ihr Vorteil – sie analysiert die topologische Struktur der Oberfläche und berechnet ihr Geschlecht. Der Code braucht ca. 1 Byte pro Facette.
3. Codierung durch den Eulerkreis (Kovalevsky, V., 2006). Dies ist eine sparsame, aber komplizierte Methode, die auch singuläre Zellen berücksichtigt. Der Code braucht ca. 0,7 Byte pro Facette.
4. Der "Reifencode" (Kovalevsky, V., 2007). Es ist die sparsamste Methode: Der Code braucht ca. 0,2 Byte pro Facette. Dabei besteht die Möglichkeit, diese Zahl weiter zu verringern.
Methode von Gordon und Udupa (1989)
Die Oberfläche wird als ein Digraph dargestellt: Seine Knoten sind die Facetten, eine Kante verbindet zwei Facetten, die einen gemeinsamen "horizontalen" Crack haben. Die Orientierung der Kanten des Digraphs ist in der Abbildung gezeigt. Es wird die Breitensuche angewendet, und die Koordinaten der Facetten werden gespeichert.
Es ist eine einfache Methode; ihre Nachteile: 1. Der Code ist nicht sparsam: Es werden die Koordinaten gespeichert; 2. 33% der Facetten werden zweimal in die Warteschlange eingetragen; Zeitverlust. 3. Teilmengen, die durch senkrechte Cracks verbunden sind, werden als getrennt
betrachtet. Dieser Nachteil könnte durch das Einführen von zusätzlichen Kanten im Digraph (gestrichelte Pfeile) beseitigt werden, aber dann würden 67% der Facetten zweimal in die Warteschlange eingetragen .
Spiralförmige Verfolgung (Kovalevsky, V., 1999)
Idee der Verfolgung
Beispiel der Verfolgung
Die Facette F heißt einfach genau dann, wenn die gemeinsame Begrenzung eine 1-Kugel ist. Dann bleibt L immer eine 2-Kugel.
einfache 2-Zelle
gemeinsame Begrenzung
Oberfläche S
markiertes Gebiet L
Die Restfolge der nicht einfachen Facetten
двумерный шар. Множество непростых пикселей (показаны белымцветом) несёт всю топологическую информацию.
a b
Die Menge der einfachen Facetten (grau) bildet eine topologische Scheibe (2-Kugel). Die zurückbleibenden nicht einfachen Facetten (weiß) tragen wichtige topologische Information.
Die Restfolge der nicht einfachen Facetten im Falle eines Torus
a
a
b b a
b b
Verschiedene Körper mit NT Tunneln
Beispiel eines Codes:Eine Brezel mit NT=2; 50 Pixel, 72 Code-Elementen.
Der Code:
035, 040, 000, 021, 015, 031, 023, 035, 011, 020, 000, 045, 051, 000, 144,002, 010, 051, 012, 000, 054, 044, 032, 020, 044, 133, 045, 000, 001, 011,011, 023, 033, 033, 044, 044, 000, 015, 054, 033, 011, 032, 120, 111, 015,033, 033, 054, 044, 044, 000, 100, 042, 121, 111, 135, 150, 144, 133, 133,111, 111, 112, 100, 100, 124, 100, 100, 105, 144, 144, 053,
Beispiel des Codes (nicht für das obige Bild)
Eine Brezel mit NT=2; 50 Facetten und 72 Codeelementen
Der Code (Oktalzahlen):
Der "Reifencode" (Kovalevsky, 2007)
Die Hauptreifen können auf die gleiche Weise, wie Kurven in 2D-Bildern, codiert werden, nämlich mit 2 Bits pro Facette. Somit werden alle Z-Facetten erfasst. Die Hilfsreifen dienen nur zum Finden weiterer Hauptreifen.
Das Verfahren ermöglicht auch in weiteren Schritten die Bestimmung des Zusammenhangs von Körpern, die nur singuläre Zellen gemeinsam haben.
Die Idee dieser Methode basiert auf der Tatsache, dass für das Wiederherstellen eines Körpers, Facetten von nur zwei entgegengesetzten Orientierungen genügen; z. B. solche, deren Normalen parallel oder anti-parallel zu der Z-Achse sind.
Z
Y
codierte Hauptreifen
Hilfsreifen
X
Füllen des Inneren von Oberflächen in 3D
Der Algorithmus ist dem zum Füllen des Inneren von Kurven in 2D ähnlich: Man markiert die Facetten der vorgegebenen Oberfläche, deren Normalen parallel oder anti-parallel zu einer gewählten Koordinatenachse sind. Dann werden alle Zeilen des Gitters durchlaufen, welche der gewählten Achse parallel sind. Dabei werden die markierten Facetten innerhalb der Zeile gezählt. Das Füllen der Voxel beginnt bei jedem ungeraden Wert des Zählers und endet bei jedem geraden Wert.
Pseudo-CodeWähle eine Koordinatenachse, z.B. die X-Achse. Markiere alle (n1)-Zellen der gegebenen (n1)-Mannigfaltigkeit, deren Normalen parallel oder anti-parallel zu der gewählten Achse sind.
for ( each row R parallel to X ){ fill=FALSE; for ( each n-cell C in the row R ) { if ( the first (n1)-side of C is labeled ) fill = NOT fill; if ( fill==TRUE ) C = foreground; else C = background; }}
Anfang und Ende des Füllens
Oberfläche
ein Schnitt
X
Rekonstruktion von farbigen 2D-Bildern
Der oben beschriebene Algorithmus ist nur zur Rekonstruktion von binären Bildern anwendbar. Algorithmen für die Rekonstruktion farbiger Bilder sind etwas komplizierter. Die Methode der Rekonstruktion, die wir beschreiben, ist anwendbar, wenn für die Werte (Farben) im Bild die Addition und die Subtraktion definiert sind. Um das Bild zu rekonstruieren, soll man jedem senkrechten Cracks C die Differenz der Werte zuweisen, welche die zwei an beiden Seiten von C liegenden Teilmengen bekommen sollen. Das ist der Gradient der Farbe. Dann soll man für jedes Pixel die Werte der links von ihm liegenden Cracks addieren. Dies ist eine einfache Integration einer Differenzengleichung.
X
Y
0
1
0
2
0
= –1
= +1
= –2
Zwei Methoden der Codierung von "farbigen" nD-Bildern
Es gibt mindesten zwei Methoden der Codierung von Begrenzungen in farbigen Bildern.
1. Die einfachere Methode besteht im Verfolgen der Begrenzung zwischen der Teilmenge mit einem vorgegebenen Wert, welche als Vordergrund betrachtet wird, und dem Komplement dieser Teilmenge. Seine Zellen enthalten beliebige andere Werte. Das Komplement wird als Hintergrund betrachtet. Der Code von jeder Komponente dieser Begrenzung (es ist meistens eine (n-1)-Mannigfaltigkeit) soll den Wert (Farbe) des Vordergrundes enthalten. Diese Methode ist einfach, aber jeder Begrenzungscrack im 2D-Fall, oder jede (n-1)-Zelle im nD-Fall, soll zweimal codiert werden.
2. Die zweite Methode besteht im Erzeugen einer Zellenliste des Bildes. Dabei wird jede (n-1)-Zelle nur einmal codiert, aber das Codierungsverfahren ist wesentlich komplizierter.
Je nach der Methode wird die notwendige Differenz (der Gradient) der Werte unterschiedlich ermittelt.
Rekonstruktion von "farbigen" nD-Bildern (Fortsetzung)
Bei der ersten Methode der Codierung sind das die Werte, welche den zwei geschlossenen Kurven (den zwei (n-1)-Mannigfaltigkeiten), die durch C gehen, zugewiesen wurden.
Bei der zweiten Methode können die zwei benötigten Werte aus dem entsprechenden Eintrag in der Zellenliste unmittelbar abgelesen werden: Es ist der Eintrag für die einzige Kurve K (die (n-1)-Mannigfaltigkeit), die durch C geht. Die zwei Werte sind die Marken der zwei mit K inzidenten Teilmengen.
Die einzige Besonderheit der Rekonstruktion im nD-Fall besteht darin, dass man mehrere Möglichkeiten für die Auswahl der Richtung der Integration hat: Man kann eine beliebige Richtung parallel einer der Koordinatenachsen wählen. Dann sollen nur die (n-1)-Zellen markiert werden. deren Normale parallel (oder antiparallel) dieser Achse ist.
Vorlesung 5
Skelette in 2D und in 3D
Anwendungen in der Computergrafik
Skelett eines Gebiets im n-dimensionalen Raum, n=2, 3 Definition SK: Das Skelett einer gegebenen Menge T eines n-dimensionalen (n=2, 3) Bildes I ist eine Teilmenge S T mit folgenden Eigenschaften:
a) S hat die gleiche Anzahl von Komponenten wie T; b) Die Anzahl von Komponenten von IS ist die gleiche, wie die von IT; c) Bestimmte Singularitäten von T sind in S erhalten; d) S ist die kleinste Teilmenge von T, die die Eigenschaften a) bis c) besitzt.
Singularitäten können z.B. als "Endpunkte" in einem 2D-Bild, oder als "Kanten eines Fladens" in einem 3D-Bild definiert werden..
Das Problem besteht darin, Bedingungen zu finden, bei denen eine Grundzelle des Vordergrundes T zu einer des Hintergrundes B=IT umgewandelt werden kann, ohne dass die Eigenschaften a) bis c) verloren gehen.
Singularität
Die Inzidenzstruktur und die IS-einfachen Zellen
Definition IS: Der Komplex IS(C, I)=SON(C, I)Cl(C, I){C} heißt Inzidenzstruktur der Zelle C relativ zum n-Raum I.
Das ist der Komplex, der aus allen mit C inzidenten Zellen außer die Zelle C selbst besteht.
Die Zugehörigkeit einer Zelle C beliebiger Dimension kann zwischen dem Vordergrund T und dem Hintergrund B gewechselt werden genau dann, wenn beide Durchschnitte IS(C, I)T und IS(C, I)B nicht leer und zusammenhängend sind. Solch eine Zelle heißt IS-einfach relativ zur Teilmenge T.
F1
P1 ist einfach
P2 ist nicht einfach
F1 ist nicht einfach
F2 ist einfach
F3
F3 ist einfach
F2
Der Algorithmus
Der Algorithmus besteht im Löschen der einfachen Zellen abwechselnd aus der abschließenden und der offenen Begrenzung der zu bearbeitenden Teilmenge. Singuläre Zellen werden nicht gelöscht.
Das auf diese Weise berechnete Skelett kann sowohl Grundzellen als auch Zellen niederer Dimensionen (b) enthalten. Es ist auch nicht schwer, solch ein Skelett zu transformieren, entweder zu einem "dünnen Skelett, das nur aus Zellen der Dimensionen nicht höher als n–1 besteht (a), oder zu einem "dicken Skelett" (c), bestehend aus Grundzellen und einer Minimalzahl anderer Zellen, die notwendig sind, um die Komponenten von S zusammenhängend zu machen. Der Vorteil dieses Verfahrens besteht darin, dass es sich problemlos parallelisieren lässt.
a b c
Berechnung des Skeletts eines 2D-Gebiets
a b c
a) Das Gebiet S b) Begrenzung B=Fr(S) c) C=S–Simple(B)
e f g
e) O = OB(C) f) F=C –Simple(O) g) Skel = F–Simple(Fr(F))
Beispiel eines 3D-Skeletts
Der ursprüngliche Körper Sein Skelett
Anwendung der Zellenkomplexe zur Computergrafik
Klassifikation der Digitalkurven
Eine Sichtkurve ist eine Folge von Pixeln. Sie ist sofort und direkt auf dem Bildschirm sichtbar. Der Anwen-
dungsbereich ist Computergrafik.
Eine Sichtkurve Eine Begrenzungskurve
Eine Begrenzungskurve ist eine Folge von abwechselnden Punkten und Cracks. Sie kann unter einer Vergrößerung sichtbar gemacht werden: Ein Punkt wird als eine kleine Scheibe oder Quadrat dargestellt und ein Crack als eine Strecke. Der Anwendungsbereich ist Bildanalyse.
Zeichnen einer Kurve durch Verfolgung ihrer Gleichung
Gegeben ist die Gleichung F(x,y)=0 der Kurve, wobei F(x,y) eine Funktion in einer Programmiersprache ist. Der Algorithmus zeichnet die Kurve auf dem Bildschirm indem er den etwas modifizierten Code “Trace” aus der Vorlesung 2 benutzt.
Gesucht wird nach zwei benachbarten Pixeln, an denen F(x,y) unterschiedliche Vorzeichen hat. Die Verfolgung startet an der gemeinsamen 0-Zelle dieser Pixel, wobei Pixel mit F(x,y)<0 als Vordergrund und die mit F(x,y)0 als Hintergrund betrachtet werden.
Startpunkt
F(x,y)<0
F(x,y)0
+ –
Sichtkurven mit Antialiasing
Der Algorithmus berechnet implizit zwei Kurven, die von der Kurve F(x,y)=0 um die Hälfte der gewünschten Breite in Richtung des ±Gradienten von F(x,y) verschoben sind. Dann wird der Flächeninhalt des Teils von jedem Pixel (in den Nähe von F(x,y)=0) geschätzt, welcher zwischen den verschobenen Kurven liegt. Die Farbe des zu zeichnenden Pixels hängt von dem geschätzten Flächeninhalt ab. Die Schätzung wird ohne eines feineren Gitters gemacht, wie dies in der Computergrafik üblich ist. Deswegen ist sie schnell und genau.
Die Zeichnung zeigt eine Kurve mit der Gleichung (x²+y²)²2ax(x²+y²)a²y²=0; Breite: 1.2 Pixel, Vergrößerung 12.
Um den Eindruck einer homogener Breite einer Sichtkurve zu erzeugen, wurde in der Computergrafik die sogenannte Methode des Antialiasing entwickelt. Wir zeigen einen neuen universellen Algorithmus zum Zeichnen von Sichtkurven beliebiger Breite mit Antialiasing.
1. Verallgemeinerung der sparsamen Codierung von Oberflächen auf "farbige" 3D-Bilder. 2. Darstellung nicht konvexer Körper durch Polyeder mit einer minimalen Anzahl von Flächen (Abb. 2).
3. Hamilton-Wege in Oberflächen (Feliú Sagols Troncoso, Abb. 3).
4. Kann man die Zugehörigkeit der singulären Zellen mit Hilfe einer feineren Digitalisierung erkennen? (Abb. 4).
5. Welche geometrische Transformationen von Bildern können ohne Informationsverlust realisiert werden?
6. Wann unterteilt ein (n-1)-dimensionaler Komplex den Rest des n-dimensionalen Raumes in genau m Komponenten? (Abb. 6).
Einige offene Probleme
2 3 4 6
1. Zusammenhang und Begrenzung sind topologische Eigenschaften, die für die Bildanalyse und ähnliche Anwendungen wichtig sind.
2. Bei diesen Anwendungen kann man mit Erfolg die Topologie der lokal endlichen Räume benutzen.
3. Abstrakte Zellenkomplexe sind allgemein anwendbare und gut verständliche Vertreter der lokal endlichen Räume.
4. Effiziente Algorithmen der Digitalgeometrie werden auf der Basis der Topologie der abstrakten Zellenkomplexe entwickelt.
Schlussfolgerung
Danke für Ihre Aufmerksamkeit
