1 Einführung 2 Interaktionstechniken und Interaktionsstile ...landarzar.net/wp-content/uploads/2013/07/MMI.pdf · nau dann eine Delaunay-Triangulierung, wenn jeder Simplex Delaunay-Simplex

3 GRAPHISCHE DATENVERARBEITUNG

1 Einführung

2 Interaktionstechniken und Interaktionsstile

3 Graphische Datenverarbeitung

Methoden und Techniken zu Konvertierung von Daten in aus aus graphischen Dastellung mit Hilfe elektro-nischer Rechenanlagen (ISO-Definition)

Abbildung 1: Verwandte Gebiete der visuellen Informationsverarbeitung

Abbildung 2: Komponenten graphischer MMI-Systeme

3.1 Display-Techniken

• Rastergraphik• LCD-Techniken

– LCD=Liquid-Christal-Display– passive Matrix-Techniken

∗ Anlegen eines elekt. Feldes durch Spannungsdifferenz:∗ Ohne Feld: Kristalle drehen das Licht um 90° ⇒Heller Punkt am Bildschirm (Polfilter im

Display)∗ Mit Feld: Kristalle anders angeordnet ⇒ Kein Licht wird gedreht, Dunkler Punkt

1

3.2 Diskretisierung 3 GRAPHISCHE DATENVERARBEITUNG

– Aktive Matrix-Techniken (TFT)

∗ Einbau von Transistoren an jedem Gitterpunkt (TFT)∗ Erlaubt Grauwerte & ist Schneller

– Folgen dem RGB-Modell

• Plasmabildschirm

– X und Y Elektrodenschichten bilde Gitter– Dazwischen Glasplatte mit Gas befüllten Zellen– Spannungsdiffernez Ionisiert Gas ⇒ Leichten an der Stelle

• Sterodarstellung

– Wiedergabe-Techniken

∗ Rot-Grün-Stero∗ Polarisationsstero

· Polarisationsfilter· Polarisationsschutter· Abwechselnde Wiedergabe des linken und des rechten Bildes mit hoher Frequenz

∗ Getrennte Displays

· Zwei Displays· Stereobetrachter (Brille)· z.B. mit Spiegel, Head-Up-Display, Zwei Projektoren, Farbmultiplexe Projektion

– Stereoansichtberechnung

∗ Toe-In-Methode

· Nachteil: Geometrie der Projektionsebenen stimmt nicht mit der Leinwand überein, nachaussen hin grösserer Fehler. Dies erzeugt Unbehagen.

∗ Off-Axis-Methode

· Geometrie der Projektionsebene stimmt mit der Projektionswand überein -> asymetrischeSichtpyramiden (wird von OpenGL unterstützt)

(a) Toe-In-Methode (b) Off-Axis-Methode

Abbildung 3: Stereoansichtsberechung

3.2 Diskretisierung

• Abtastung / Diskretisierung / Digitalisierung / Digitisierung: Umwandlung orts- und intensitätskonti-nuierlicher Signale in diskrete Größen

– diskrete Abtastpunkte: Sampling– diskrete Abtastwerte: Quantisierung

2


Abbildung 4: eindimensionale Diskretisierung

Theorem 3.1. AbtasttheoremDas ursprüngliche Signal (Bild) ist aus dem Abtastsignal (Abtastbild) rekonstruierbar ist, wenn die Abtastungmit mehr als doppelt so hohen Frequenz wie der im gegebenen Signal auftretenden höchsten Frequenz geschieht.

3.2.1 Abtastung (Sampling)

Definition 3.1. eindimensionale Fourertransformation (FT)einer Integrierbaren Funktion f : R→ R :

F (u) :=

ˆ ∞−∞

f(x) exp(−iux)δx, u ∈ R, i :=√−1, exp(iy) = cos(y) + i sin(y)

Nun die Inverse

Definition 3.2. inverse endimensionale FT:

f(x) =1

2π

ˆ ∞−∞

F (u) exp(iux)δu

Satz 3.1. Eigenschaften der FT:

1. Wenn f(x) reell ist, gilt F (−u) = F (u)

2. Polardarstellung von F (u) : F (u) = |F (u)| exp(iφ(u))

Definition 3.3. zweidimensionale Fouriertransformationeiner Integrierbaren Funktion f : R2 → R

F (u, v) =

ˆ ∞−∞

ˆ ∞−∞

f(x, y) exp(−i(ux+ vy))δxδy, u, v ∈ R

die inverse:f(x, y) =

1

4π2

ˆ ∞−∞

ˆ ∞−∞

F (u, v) exp(i(ux+ vy))δuδv, x, y ∈ R

Bemerkung 3.1. Nomeklatur für FourertransformationspaareMan Bezeichnet f(x) und F (u), bzw. f(x, y) und F (u, v) als Fouriertransformationspaar, geschrieben

• f(x) − • F (u), bzw.• f(x, y) = •F (u, v)

• x, yheißen Ortskoordinaten• f(x, y) heißt Ortsfunktion

3


• u, vheißen Ortsfrequenzkoordinaten• F (u, v)heißt Ortsfrequenzspektrum• x− y-Ebene: Ortsbereich• u− v-Ebene: Ortsfrequenzbereich

Bemerkung 3.2. Zur Kontinuerilichen Fourertransformation FT

• F (u, v) ist üblicherweise komplexwertig.• F (u, v) = ReF (u, v) + i · ImF (u, v) = |F (u, v)| exp(iφ(u, v))

• |F (u, v)| =√

ReF (u, v)2 + ImF (u, v)2 heißt Amplitudenspektrum

• φ(u, v) = arctan( ImF (u,v)

ReF (u,v)) heißt Phasenspektrum

• |F (u, v)|2 = F (u, v) · F (u, v) heißt Leistungsspektrum von f(x, y)

Satz 3.2. Vertauschungssatz

f(x, y) = •F (u, v)⇒ F (x, y) = •4π2f(−u,−v)

Satz 3.3. Spearierbarkeitf(x, y) − • F x(u, y) − • F (u, v)

f(x, y) − • F y(x, v) − • F (u, v)

Definition 3.4. Faltung zwei Funktionen f und h:

f(x, y) ? ?h(x, y) :=

ˆ ∞−∞

ˆ ∞−∞

f(ξ, η)h(x− ξ, y − η)δξδη =

ˆ ∞−∞

ˆ ∞−∞

f(x− ξ, y − η)h(ξ, η)δξδη

Satz 3.4. Faltungsatz

f(x, y, ) ? ?h(x, y) = •F (u, v) ·H(u, v)

3.2.2 Dirac-Funktion

δ(x, y) := lima→0

1

4a2recta,a(x, y)

Satz 3.5. Eigenschaften der Dirac-Funktion

• Integrierbarkeit ˆ ∞−∞

ˆ ∞−∞

δ(x, y)δxδy = 1

• Ausblendeigenschaft: ˆ ∞−∞

ˆ ∞−∞

f(x, y)δ(x− a, y − a)δxδy = f(a, b)

• Verschiebungseigenschaftf(x, y) ? ?δ(x− a, y − b) = f(x− a, y − b)

4

3.3 Graphikkarten 3 GRAPHISCHE DATENVERARBEITUNG

3.3 Graphikkarten

Abbildung 5: Prinzipelle Graphikkarte

3.4 Farbmodelle

YUV-ModellY Luminanz (Lichtstärke pro Fläche, luma)U Chrominanz (Farbanteil, chroma)V Chrominanz (Farbanteil, chroma)

HSV-ModellH hue=Farbton reiner Grundfarbton Wertebereich: [0,360]S saturation=Sättigung Weißanteil, der den Reinheitsgrad beeinflusst: Wertebereich: [0,1]V value=Wert Schwarzanteil, der die Helligkeit beeinflusst Wertebereich: [0,1]

HLSH hue=FarbtonL lightness=HelligkeitS saturation=Sättigung

3.5 Geometrierepräsentation

3.5.1 OpenGL

Grundkonzepte von OpenGL• Zustandsmaschine

– der Kontext von Operationen und damit deren Wirkung ist durch den aktuellen Zustand gegeben,z.B. die Linienbreite, mit der aktuell gezeichnet wird

– Zustandsvariablen haben einen Default-Wert– Der Zustand kann durch Operationen verändert werden, z.B. Veränderung der Linienbreite– Der aktuelle Wert von Zustandsvariablen kann durch Operationen abgefragt werden (glGet...)

5

3.5 Geometrierepräsentation 3 GRAPHISCHE DATENVERARBEITUNG

• Client-Server-Modell

– Client: das Anwendungprogramm– Server: das OpenGL-Graphiksystem

Operationen• Zeichenoperationen

– Immer zwischen glBegin(...); und glEnd();

–

• Hilfsoperationen

– glClearColor(): setzt den Zustand auf die angegebene Löschfarbe;– glClear(): löscht das Fenster mit der im Zustand gesetzten Farbe;– glColor3f(): setzt die Farbe zum Zeichnen der Objekte;– glFlush(): führt das Zeichnen aus;

Abbildung 6: Zeichenmodi von OpenGL

6


3.5.2 Polygonbasierte Repräsentation (Netze)

Zellkomplexe (Netze)

Definition 3.5. ein d-dimensionaler Simplex ist die Konvexe Hülle von d+ 1 Punktem im Rd

Daraus ergibt sich:

Definition 3.6. Ein d-dimensionaler simplizialer Komplex ist eine endl. Menge von d-dimensionenSimplexen, so dass

1. der Durchschnitt von je zwei Simplexen entweder leer oder ein Seiten- simplex beider Simplexe ist,2. mit jedem Simplex auch alle seine Seitensimplexe zur gegebenen Simplexmenge gehören.

Definition 3.7. Ein Polyeder ist eine Punktmenge im Rd, die durch eine d-dimensionale simpliziale Zerle-gung beschrieben werden kann, dargestellt durch eine Hierarchie von Seitenpolyedern. Dabei setzt sich derRand aus endlich vielen Seiten- polyedern zusammen, deren Rand wieder aus Seitenpolyedern und so fort,mit Eckpunkten als 0-dimensionale Polyeder.

Auch dies kann erweitert werden:

Definition 3.8. Ein polyedrischer Komplex ist eine endliche Menge von Polyedern im mit den Eigen-schaften, dass

1. der Durchschnitt von je zwei Polyedern entweder leer oder ein Seiten- polyeder beider Polyeder ist,2. mit jedem Polyeder auch alle seine Seitenpolyeder zur gegebenen Polyedermenge gehören.

Datenstrukturen für Netze

Definition 3.9. Zellinzidenzgraph

Ein Zellinzidenzgraph I = (V,E) für eine Zerlegung im Rd hat folgende Eigenschaften:Knotenmenge V V = V−1 ] V0 ] . . . ] Vd ] Vd+1, mit |V1| = |Vd+1| = 1 und

∀i ∈ 0, . . . , d : Vi enthält für jede i dimensionale Zelle einen Knoten

Kantenmenge E E = E1 ] E0 ] . . . ] Ed, wobei

(v, w) ∈ Ei ⇔ v ∈ Vi ∧ w ∈ Vi+1 ∧ v Randzelle von w

Abbildung 7: Zellinzidenzgraph

Definition 3.10. Winged-Edge-Struktur

7


Polygontriangulierung

Definition 3.11. Polygontriangulierung

Gegeben: ein Polygon PGesucht eine Verbindung der Knoten des Polygons durch sich nicht schneidene Sehen, so dass eine Zerlegung

des Polygoninneren in Dreiecke induziert wird.

Definition 3.12. Ohr ein von einer Sehne induziertes Dreieck, das ganz im Inneren des Polygons liegt.

Satz 3.6. Jedes Polygon besitzt mindestens ein Ohr.

Kurvenapproximation

Flächenapproximation

Delaunay-Triangulierung

Definition 3.13. Triangulierung einer Punktmenge P = p1, . . . , pn ⊆ Rd, ist eine simpliziale Zerlegeung derkonvexen Hülle von P , die genau die gegebenen Punkte als Eckpunkte (nulldimensionale Simplexe) hat.

Zu Delaunay:

Definition 3.14. Delaunay Triangulierung ist eine Triangulierung, die nur aus Delaunay-Simplexen bezüg-lich der gegebenen Punkte besteht.

Dabei ist ein Delaunay-Simplex folgend defininiert:

Definition 3.15. Ein Delaunay-Simplex ist ein Simplex mit k von n Punkten als Eckpunkte, 1 ≤ k ≤minn, d+ 1, der bezüglich der gegebenen Punkte die Umkugelbedingung erfüllt.

Satz 3.7. Eigenschaften von Delaunay-Triangulierungen

Existenz Zu jeder endlichen Punktmenge im Rd gibt es eine DelaunayTriangulierung.Eindeutigkeit Sind keine d + 2 der gegebenen Punkte kosphärisch, dann ist die Delaunay-Triangulierung

eindeutig.Delaunay-Simplizes Sind keine d + 2 der gegebenen Punkte kosphärisch, dann ist eine Triangulierung ge-

nau dann eine Delaunay-Triangulierung, wenn jeder Simplex Delaunay-Simplex ist. Sind keine d + 2der gegebenen Punkte kosphärisch, dann sind die Simplizes der Delaunay-Triangulierung genau dieDelaunay-Simplizes der gegebenen Punktmenge.

Bemerkung 3.3. Zur Delaunay-Triangulierung

1. Im Zweidimensionalen sind Delaunay-Triangulierungen diejenigen, bei denen der kleinste Winkel überalle Dreiecke maximiert wird.

2. Delaunay-Triangulierungen in beliebigen Dimensionen können durch eine Berechnung der konvexenHülle einer um eine Dimension höheren Punkt- menge berechnet werden:

Satz 3.8. Transfomation Delaunay-Triangulierung/konvexe HülleSei T : Rd → Rd+1 definiert durch

T (p) =

(p∑di=1 p

2i

), p = (p1, . . . , pd)

Dann ist die Delaunay-Triangulierung zu den Punkten p1, ..., pn ∈ Rd kombinatorisch äquivalent zu derZellzerlegung, die von den d-dimensionalen Zellen der konvexen Hülle von T (p1), . . . , T (pn) induziert werden,deren äußerer Normalenvektor eine negative (d+ 1)-Komponente hat.

8


Abbildung 8: Inkrementelle Delaunay-Triangulierung

Es gibt noch eine andere Variante:

Abbildung 9: d -dimensionale Delaunay-Triangulierung

Netzanalyse• Beurteilung der Qualität von Netzen• Maße für die geometrische Flächenqualität:

– Glattheit (smoothness, definition der Glattheit über Differenzierbarkeit )– Ausgeglichenheit (fairness, definition der Ausgeglichenheit über krümmungsbasierte Funktionale

)– Form der Dreiecke: z.B. Maximierung des Flächeninhalts relativ zur Kantenlänge

• Maße für die kombinatorische Flächenqualität

– möglichst regulärer Knotengrad (bei Dreiecksnetzen z.B. = 6).

• Maße für Flächenattribute (z.B. Farben, Texturkoordinaten, Knotennormalen )

– Erhalten von Unstetigkeiten in der Flächenfärbung– Minimierung der Normalenabweichung

9


Umvernetzung (Remeshing)• Ziele

– keine Kante kürzer als eine gegebene Schranke εmin > 0

– keine Kante länger als eine gegebene Schranke εmax > 2εmin

– der Knotengrad gleich 6 ist– lange und dünne Dreiecke vermieden werden.

• Algorithmus (Umvernetzungsalgorithmus von Kobbelt et al.)

1. Entferne alle Kanten, die kürzer als εmin sind, durch Halbkantenkontraktion. Dabei wird derEndknoten mit geringerem Knotengrad in den mit höherem Grad geschoben.

2. Unterteile alle Kanten, die länger als εmax sind, durch Einfügen eines Knotens und Halbierungder inzidenten Dreiecke.

3. Für alle adjazenten Dreiecke ∆(p1, p2, p3), ∆(p3, p2, p4), bei denen sich der totale Knotengrad

4∑i=1

(d(pi)− 6)2

wobei d(p i) der Knotengrad von p i, bei Vertauschen der gemeinsamen Kante (p 2, p 3) verringert,führe einen Kantentausch aus.

4. Falls Kanten entstanden sind, deren Länge nicht im Intervall (εmin, εmax) liegen, dann wende dasVerfahren auf das aktuelle Netz erneut an.

Abbildung 10: (1) Eingabenetz(2) Ergebnis nach Entfernen der zu kurzen Kanten(3) Ergebnis nach Entfernen der zu langen Kanten(4) Ergebnis nach dem Kantentausch zur Gradreduktion

Netzausgleichung (Fairing) Elimination von feinen Details, insbesondere von feinen Unebenheiten, die beider Netzgenerierung durch Abtasten oder Interpolations-/Approximationsverfahren entstanden sind.Vorgehensweise: Verschiebung der Netzknoten in Richtung des Vektors, der durch eine diskrete Version des

Laplace-Operators berechnet wird.

10


Abbildung 11: Algorithmus Diskreter Informationsfluss (Taubin)

NetzreduktionEingabe: ein Netz M, eine Fehlerschranke ε > 0 bezüglich einer Fehlermetrik.Ausgabe: ein Netz M ’, das weniger Knoten als M hat und dessen Abweichung von M kleiner als ε ist.

• Anwendungen:

– Anpassung an Rechnerressourcen z.B. Speicher, Kommunikationsbandbreite, interaktive Bilder-zeugung

– progressive Datenübertragung– hierarchische Darstellung

• Verfahren

– Knoten-Clustering– inkrementelle Dezimierungsalgorithmen: Anwendung einer Folge von kombinatorischen Operatio-

nen

∗ Knotenentfernung (vertex removal):

∗ antenkontraktion (edge contraction/collapse):

11


∗ Kantenvertauschung (edge flipping):

∗ Algorithmus (Inkrementelle Netzdezimierung)

Eingabe: ein Netz M , eine Fehlerschranke ε > 0 bezüglich einer Fehlermetrik.Ausgabe: ein Netz M, das sich durch Dezimierung aus M ergibt und dessen Abweichung von

M kleiner als ε ist.Datenstruktur Q=Priority Queue (sortiert nach aufsteigenden Kosten für die Operationen )

Vielfach aufgelößte Netze (Multiresolution) eine Sammlung von Verfeinerungsmodifikationen, die• üblicherweise die Auflösung eines Netzes lokal reduzieren,• in einer Abhängigkeitsbeziehung zueinander stehen, die es erlaubt, Teilmengen von Modifikationen

auszuwählen, die reduzierte Netze liefern, die das Originalnetz approximierenZwei verscheidene Ansätze

1. geschachtelte Netze basieren auf Modifikationen, die eine einzige Facette in ein Netz expandieren2. nicht geschachtelte Netze besitzen Modifikationen, bei denen mehrere Facetten neue Facetten erzeugen.

Netzkompression Kompakte Speicherung von Netzen durch Elimination von Reddundanz• Strukturkompression

– möglicher Ansatz: sequenzielles Ablaufen des Netzes, Kodierung des Weges in eine Anweisungsfolgeund Kompression der Anweisungsfolge mit einem zeichen- orientierten Kompressionsverfahren,z.B. Huffman-Kodierung oder arithmetische Kodierung.

• weitere Aspekte

– Kompression von mehrfach aufgelösten Netzen zur progressiven Netzen, so dass eine grob-nach-fein Dekompression möglich ist.

– Kompression unter Einsatz von Sekundärspeicher (Festplatte) für sehr große Netze.

Iterierte Unterteilung UnterteilungskurvenGegeben: ein Polygonzug mit Eckpunkten pi ∈ Rd, i = 0, . . . , n

12


Chaikin-Unterteilungskurve: Berechnung der neuen Eckpunkte p?i (im Grenzübergang entsteht eine qua-dratische Spline-Kurve):

p?2i :=3

4pi +

1

4pi+1

p?2i+1 :=1

4pi +

3

4pi+1, i = 0, . . . , n− 1, n ≥ 3

Doo-Sabin-UnterteilungsflächenGegeben: ein FacettennetzKonstruktionsverfahren durch 5 Schritte:

1. Ersetze die Eckpunkte pi, i = 0, ..., n–1, jeder Facette des gegebenen Netzes durch neue Eckpunktep?i , i = 0, ..., n–1, mit

p?i = α0 · pi +

i∑k=1

αk · pi−k +

n−i−1∑k=1

αk · pi+k

undα0 = (n+ 5)/(4n)αk = (3 + 2 cos(2πk/n))/(4n), 1 ≤ k ≤ n− 1

2. Konstruiere für jede n-seitige Facette des alten Netzes eine n-seitige Facette des neuen Netzes,indem die p?i anstelle der pi genommen werden. Diese Facetten werden F-Facetten genannt.

3. Konstruiere für jede innere Kante pq eine neue vierseitige Facette, deren bezüg- Rand durchdie entsprechenden neuen Punkte p?, q? bzw. bzgl. der beiden zur Kante pq inzidenten Flächeninduziert wird. Diese Facetten werden E-Facetten genannt.

4. Konstruiere für jeden inneren Knoten p des alten Netzes eine Facette des neuen Netzes, die durchdie neuen Knoten p? für alle zu p inzidenten Facetten des alten Netzes induziert wird. DieseFacetten werden V-Facetten genannt.

5. Iteriere das Verfahren mit dem neuen Netz.

Bemerkung 3.4. Eigenschaften

1. Bei der Doo-Sabin-Unterteilungsfläche werden bei jeder Iteration neue vierseitige Facetten generiert.2. Nach dem ersten Unterteilungsschritt ist der Grad jedes inneren Eck- punktes, d.h. die Anzahl der zu

ihm inzidenten Kanten, gleich 4.3. Aus einer n-seitigen Facette entsteht wieder eine n-seitige Facette, desgleichen aus einem Eckpunkt mit

Grad n. Das bedeutet, dass sich die Anzahl der n-seitigen Facetten mit n 6= 4 nach der ersten Itera-tion nicht mehr erhöht. Diese Facetten werden kritisch genannt, da dort aufgrund der dem Verfahrenzugrundeliegenden Idee die Konvergenz nicht ohne weiteres klar ist.

4. Die durch fortgesetzte Iteration entstehenden Netze setzen sich also im Wesentlichen aus regulärenVierecksnetzbereichen zusammen, die von kritischen Facetten unterbrochen sind.

5. Diese Vierecksnetze konvergieren gegen biquadratische Spline-Flächen- stücke, d.h. jeder 3×3-Ausschnittgegen ein biquadratisches Polynom- flächenstück.

6. Jede Facette konvergiert gegen ihren Schwerpunkt.7. Die Doo-Sabin-Flächen entsprechen den Chaikin-Unterteilungskurven.8. Es kann gezeigt werden, dass die Iteration gegen eine Fläche konvergiert, die tangentialstetig ist.

3.5.3 Rasterbasierte Repräsentation

3.5.4 Punktbasierte Repräsentation

3.5.5 Kompositionsverfahren

Geometrische Transformationen

13


Definition 3.16. (affine Abbildung) p = A · p+ t, wobei in der Ebene

A =

(a11 a12a21 a22

), aij ∈ R, t =

(t1t2

), ti ∈ R

und im Raum

A =

a11 a12 a13a21 a22 a23a31 a32 a33

, aij ∈ R, t =

t1t2t3

, ti ∈ R

• Spezialfälle in der Ebene

– Translation: p =

(1 00 1

), ·p+ t

– Skalierung: p =

(a 00 b

), ·p, a, b > 0

– Rotation: p =

(cosφ − sinφsinφ cosφ

), ·p

– Spiegelung

∗ waagerechten Achse: p =

(1 00 −1

), ·p

∗ senkrechten Achse: p =

(−1 00 1

), ·p

∗ Ursprung: p =

(−1 00 −1

), ·p

– Scherung

∗ Richtung waagrechte Achse p =

(1 s0 1

), ·p

∗ Richtung senkrechten Achse: p =

(1 0s 1

), ·p

• Spezialfälle im Raum

– Translation p =

1 0 00 1 00 0 1

· p+ t

– Skalierung p =

sx 0 00 sy 00 0 sz

· p, a, b > 0

– Rotation

∗ x-Achse: p =

1 0 00 cosφ − sinφ0 sinφ cosφ

· p∗ y-Achse p =

cosφ 0 sinφ0 1 0

− sinφ 0 cosφ

· p∗ z-Achse p =

cosφ − sinφ 0sinφ cosφ 0

0 0 1

· pDefinition 3.17. homogene Darstellung einer affinen Abbildung p = A · p+ t

p? = A? · p?, mit p? :=

(p

1

), p? :=

(p

1

), A? :=

(A t0 1

)Bemerkung 3.5. Die homogene Darstellung hat den Vorteil das Hintereinanderausführung von Abbildungendurch einfache Matrizenmultiplikation möglich ist.

14


Gruppierung

Definition 3.18. GruppierungSzenendarstellung als Menge von Elementarbestandteilen:

• Szene := Graphikelement, . . ., Graphikelement• Graphikelement := Strecke|Polygonzug|Markierung| . . .

Definition 3.19. Hierarchische GruppierungSzenendarstellung als hierarchische Gruppierung:

• Szene := Transformation Gruppe• Gruppe := Bestandteil, . . ., Bestandteil• Bestandteil := Transformation Gruppe|Graphikelement• Transformation := eine affine Transformation• Graphikelement := Strecke|Polygonzug|Markierung| . . .

Mengenalgebra syntaktische Beschreibung von Szenen.

Definition 3.20. konstruktive Körpergeometrie (constructive solid geometry, CSG):

Zusammensetzen komplexer Körper aus Grundkörpern durch Anwenden von regularisierten Mengenopera-tionen.regularisierte Mengenoperationen:

• regularisierte Vereinigung: A ∪? B := ((A ∪B))−

• regularisierter Durchschnitt: A ∩? B := ((A ∩B))−

• regularisierte Differenz: A ∪ −?B := ((A ∪ −B))−

• Wobei M das innere der Menge M, M− der Abschluss von M

Grundkörpermenge: eine Menge regulärer Körper, aus denen alle anderen aufge- baut werden.Strukturformel: Formel aus Mengensymbolen und Grundkörpersymbolen.Geometrieformel: eine Strukturformel, bei der die Operanden jeder Mengenopera- tion mit einer Transfor-

mationsangabe versehen sind.

Abbildung 12: Bsp: CSG-Baum

Lindenmayer-Systeme Ein Grammatikkonzept zur Beschreibung natürlicher, insbesonderer botanischerStrukturen

15

3.6 Transformation, Projektion und Clipping 3 GRAPHISCHE DATENVERARBEITUNG

3.5.6 Java 3D-Szenengraph

Abbildung 13: Java 3D-Szenengraph

3.6 Transformation, Projektion und Clipping

3.6.1 Graphik-Pipeline

transformiert eine Bildbeschreibung (Szene) in ein Bild :

Abbildung 14: Graphik-Pipeline

3.6.2 Clipping

Abschneiden von Teilen einer Szene, die außerhalb eines gegebenen Bereichs liegen.Punkte

Eingabe ein Punkt p, ein Rechteck mit extremen Koordinaten xmin, xmax, ymin, ymax

Ausgabe p, falls p im Inneren des Rechtecks liegt, sonst nichts.

Strecken (Algorithmus von Cohen-Sutherland)

Eingabe Eine Strecke, ein Rechteck.Ausgabe Der Durchschnitt der Strecke mit dem Rechteck

16

3.7 Verrasterung 3 GRAPHISCHE DATENVERARBEITUNG

Ablauf Falls beide Streckeneckpunkte in allen vier inneren Halbebenen der Rechteckkanten liegen,zeichne die Strecke; Falls beide Streckeneckpunkte in einer der vier äußeren Halbebenen der Poly-gonkanten liegen, zeichne die Strecke nicht; Sonst verkürze die Strecke durch Abschneiden entlangeiner der Randgeraden, bis kein Punkt mehr in einer äußeren Halbebene liegt.

Kreis-Clipping

Eingabe Ein Kreis, ein Rechteck.Ausgabe Der Durchschnitt des Kreises mit dem RechteckAblauf: Teste das achsenparallele Hüllquadrat des Kreises auf Schnitt mit dem Clipping- Rechteck;

Wenn ein Schnitt festgestellt wird, teile den Kreis in vier Quadranten und führe den Test fürjeden Viertelkreis aus; Wenn ein Schnitt festgestellt wird, berechne die Schnittpunkte mit den inFrage kommenden Rechteckseiten und bestimme die im Inneren des Clipping-Rechtecks liegendenKreisabschnitte; Andernfalls liegt der Kreis ganz im Inneren, ganz im Äußeren des Clipping-Rechtecks oder umfasst das Clipping-Rechteck.

Polygon (Algorithmus von Sutherland-Hodgman)

Gegeben: Ein Polygonzug, ein RechteckGesucht: Der Durchschnitt des Polygonzugs mit dem RecheckAblauf: Führe für die Geraden, die die vier Rechteckseiten definieren, nacheinander aus: entferne die

Eckpunkte des Polygonzugs, die in der äußeren Halbebene liegen und füge für jede Polygonkante,die die Gerade schneidet, den entsprechenden Schnittpunkt in den Polygonzug ein.

3.6.3 Picking

Auffinden eines geometrischen Objekts durch Identifizieren eines seiner Punkte.• Schwierigkeiten:

1. die exakte Punktauswahl beim Picking “dünner“ Objekte, z.B. beim Picken von Punkten undLinien;

2. das Identifizieren eines Objektpunktes, z.B. im Inneren eines Polygons.

• Lösung

– Euklidscher Abstand (sehr rechenaufwendig) d =√

(qx − px)2 + (qy − py)2

∗ alternativ: d = (|qx–px|+ |qy–py|) , oder d = max |qx–px|, |qy–py|

3.6.4 Projektion

Gegeben: eine Bildebene, spezifiziert durch einen Ursprung o ∈ R3 und zwei Koordinatenvektoren u und v.perspektivische Projektion p = (px, py) eines Punktes p bzgl. eines Augenpunktes a ∈ R3

px =det( a− o v a− p )

det( u v a− p ), py =

det( u a− o a− p )

det( u v a− p )

Parallelprojektion p = (px, py) eines Punktes p bzgl. einer Richtung w ∈ R3

px =det( p− o v w )

det( u v w ), py =

det( u p− o w )

det( u v w )

3.7 Verrasterung

Verrasterung:

Gegeben ein kontinuierliches geometrisches Objekt O

17

3.8 Sichtbarkeitsberechnung 3 GRAPHISCHE DATENVERARBEITUNG

Gesucht eine Approximation von O durch Rasterpunkte, die bei hinreichend feiner Rasterauflösungwie O aussieht.

Lösungsmöglichkeiten

1. Approximation von O durch Polygonzüge beziehungsweise Netze2. Verrasterung von Strecken beziehungsweise Dreiecken

Algorithmus (inkrementelle Verrasterung von Strecken in expliziter Darstellung)

Gegeben eine Strecke mit Steigung zwischen -1 und 1 und mit ganzzahligen Endpunkten pund q auf dem Rastergitter.

Gesucht Eine Folge von ganzzahligen Punkten, die die Strecke approximieren.Ablauf

a :=qy − pyqy − px

, b :=py(qx − px)− (qy − py)px

qx − px, f(x) := ax+ b

Zeichne den Punkt (i,round(f(i))

Algorithmus (inkrementelle Verrasterung von Strecken in impliziter Darstellung)

Gegeben eine Strecke mit Steigung zwischen 0 und 1 und mit ganzzahligen Endpunkten pund q auf dem Rastergitter, p links von q.

Gesucht Eine Folge von ganzzahligen Punkten, die die Strecke approximieren.Ablauf

a := qy − py, b := −(qx − px), c := −bpy − apx, F (x, y) := a · x+ b · y + c

Zeichne (px, py); j := pyfor i := px + 1 to qx; do if F (i, j + 0.5) > 0 then j := j + 1; zeichne(i, j)else nothing

Anti-Alias-Behandlung (Problem: stufiges Aussehen von verrasterten Strecken; Grund: nicht korrekte Ab-tastung)

Lösung: bei Rasterdisplays mit mehreren Intensitätsstufen Verwendung der Intensitätsstufen zur Glät-tung

3.8 Sichtbarkeitsberechnung

Gegeben eine Szene ebener Polygone P1, ..., Pm im R3, ein Augenpunkt a.Gesucht: alle von a aus sichtbaren Teile der Polygone (Berechnung der sichtbaren Flächen / hidden surface

elimination) beziehungsweise alle von a aus sichtbaren Kanten der Polygone (Berechnung der sichtbarenLinien / hidden line elimination).

3.8.1 Entfernung verdeckter Kanten und Flächen

Lösungsansätze

szenenbasierte Sichbarkeitsberechnung Die Sichtbarkeitsberechnung geschieht unabhängig von derArt der Bilddarstellung (Rasterbild, Liniengraphik) basiert auf der für die Szene verwendetenGeometrierepräsentation.

Vorteil: Unabhängigkeit von der Art der Bilddarstellung

bildbasierte Sichtbarkeitsberechnung Die Sichtbarkeitsberechnung geschieht abhängig von der Artder Bilddarstellung.

Vorteil: Beschränkung auf die Bedürfnisse der eingesetzten Art der Bilddarstellung.

18

3.8 Sichtbarkeitsberechnung 3 GRAPHISCHE DATENVERARBEITUNG

Abbildung 15: Auswirkung des Lösungsansatzes auf die Graphik-Pipeline

3.8.2 Prioritätslistenverfahren (sind szenenbasiertes Lösungsverfahren)

Algorithmus (PaintersAlgorithm)Die SzenenPolygone werden nach fallender Entfernung ihres am geringsten vom Beobachter entfern-ten Eckpunktes auf die Bildebene projiziert, verrastert und dann gezeichnet. Dadurch überdecken imallgemeinen näherliegende Polygone die weiter entfernt liegenden.Problem Bei zirkulärer Überdeckung kommt der Algorithmus zu keiner eindeutigen Lösung

Algorithmus (Binäre Raumzerlegung - BSP = Binary Space Partition)

Vorverarbeitungsphase Nimm ein Polygon der Szene und teile die Szene durch seine Ebene in diebeiden Teilszenen, die aus den Polygonen in den beiden durch die Ebene induzierten Teilräumenliegen. Polygone, die die Ebene schneiden, werden durch die Ebene in Teilpolygone zerlegt. Dasausgewählte Polygon bildet die Wurzel des Baums. Sie besitzt zwei Teilbäume, deren Wurzelnentsprechend aus den beiden Teilszenen bestimmt werden.

Sichtbarkeisbrechnungsphase Durchlaufe den BSP-Baum so, dass zunächst der Teilbaum bzgl. einesKnotens durchlaufen wird, der die Teilszene enthält, in deren Halbraum sich der Augenpunktder Projektion nicht befindet. Bevor der zweite Teilbaum durchlaufen wird, wird das Polygondes Knotens vorne an die auszugebende Prioritätsliste angefügt. Die resultierende Prioritätslisteenthält die Polygone sortiert nach fallender Entfernung vom Augenpunkt, d.h. ergibt, in dieserReihenfolge gezeichnet, die korrekte Verdeckung.

Back-face culling Die Polygone, die keinen Normalenvektoranteil entgegen der Blickrichtung haben (back-faces, gestrichelt) (A,B,D,F) werden entfernt, die anderen Polygone (front-facing polygons) (C,E,G,H)werden weiter behandelt. Die reduzierte Anzahl von Polygonen erlaubt eine schnellere Sichtbarkeits-berechnung

3.8.3 Tiefenpufferverfahren

Vorgehensweise: Die Polygone der Szene werden nacheinander auf die Bildebene projiziert und verrastert.Für jeden Bildpunkt eines Polygons wird seine Entfernung zum Augenpunkt bestimmt (die Tiefe) und

19

3.9 Beleuchtungssimulation 3 GRAPHISCHE DATENVERARBEITUNG

mit einem für den Bildpunkt bereits gespeicherten Tiefenwert verglichen. Ist seine Tiefe geringer, wirddiese dem Bildpunkt zugewiesen und dieses Polygon als an diesem Bildpunkt sichtbar registriert. DieSichtbarkeitsinformation bzw. die Tiefeninformation werden in einem Feld (Array) mit der Bildauflö-sung entsprechen-den Größe abgelegt.

Algorithmus (Tiefenpuffer/depth buffer/z-buffer)

Eingabe: Eine 3D-Szene aus Flächen, eine Projektion, eine Bildauflösung n×mAusgabe: für jedes Pixel des n×m Rasterbildes die dort sichtbare Fläche.Vorgehen: Polygone Verrastern auf die Bildebene, und dann den berechneten z-Wert als für die Be-

rechnung verwenden.

3.8.4 Scan-Line-Verfahren

Algorithmus (Scan-Line-Verfahren)

Eingabe: Eine 3D-Szene aus Flächen, eine Projektion, eine Bildauflösung n×mAusgabe: für jedes Pixel des n×m Rasterbildes die dort sichtbare Fläche.Ablauf Arbeite das Bild zeilenweise ab und führe für jede Zeile aus:

1. Bestimme für die aktuelle Zeile die von ihr geschnittenen Polygonkanten;2. Arbeite die Polygonkanten nach aufsteigender x-Koordinate ihres Schnittpunkts mit der Scan-

Line ab:Bestimme das am Schnittpunkt der aktuellen Polygonkante sichtbar werdende Polygon (dieskann auch das bisher sichtbar gewesene sein);Zeichne die Bildpixel der Scan-Line zwischen letztem und aktuellem Schnittpunkt mit derFarbe des am letzten Schnittpunkt sichtbar gewordenen Polygons.

3.8.5 Bereichsunterteilungsverfahren

Algorithmus (Bereichsunterteilungsverfahren von Warnock)

Ein-/Ausgabe: wie obenVorgehen Aufteilen der Bildebene in Teilbilder, die so einfach sind, dass die Sichtbarkeitsberechnung

unmittelbar ausgeführt werden kann.

3.9 Beleuchtungssimulation

3.9.1 Beleuchtungsmodell von Phong

I(v) = Ia + Id + Ig(v)

ambienten Reflexion Ia := ka · Iambdiffusen Reflexion Id := kd

∑li=1 n ∗ li · Ii/f(di)

glänzende Reflexion Ig(v) := kg∑l

i=1(v ∗ ri)γ · Ii/f(fi)

geometrische Parameter des Phong Modells

v die normierte Blickrichtung,n die auf Länge 1 normierte Oberflächennormale,Ii der auf Länge 1 normierte Richtungsvektor zur i -ten Lichtquelle,ri der auf Länge 1 normierte Reflexionsvektor zu l i nach dem Reflexionsgesetz,di die Entfernung zur i-ten Lichtquelle,f(. ) eine Funktion des Abstands, z.B. sein Quadrat.

Materialparameter des Phong Modells

20


ka der Koeffizient der ambienten Reflexion,kd der Koeffizient der diffusen Reflexion,kg der Koeffizient der spiegelnden Reflexion,γ > 0 die Ausdehnung des Glanzlichtes.

3.9.2 Beleuchtungssimulation in der Graphik-Pipeline

(a) Flat Shading (b) Gauraud Shading (c) Phong Shading

Abbildung 16: Graphik-Pipeline für die Verschiedenen Beleuchtungstechniken

Flat ShadingVorgehensweise Berechnen eines Farbwertes an einem Punkt des Polygons, z.B. einem der Eckpunkte, nach

dem Beleuchtungsmodell. Die vom Polygon überdeckten sichtbaren Pixel werden mit dem be-rechneten Farbwert gefärbt.

Schwierigkeit Durch den Mach-Band-Effekt wirkt die Interpolation bei Polygonnetzen, die glatte Ober-flächen beschreiben, facettiert.

Mach-Band-Effekt: Intensitätsübergänge, die nicht stetig differenzierbar sind, erscheinen hel-ler/dunkler als es den Intensitätswerten entspricht, d.h. sie werden verstärkt wahrge-nommen.

Geraud-ShadingVorgehensweise Berechnen der Farbwerte an den Ecken des Polygons nach dem Beleuchtungsmode. Zei-

lenweises Abarbeiten des Polygons entsprechend dem Scanline-Füllverfahren. Dabei werden dieFarbwerte auf den Kanten aus den Farbwerten der Kantenendpunkte beim Verrastern linear in-terpoliert. Aus diesen Werten werden die Farbwerte der Pixel in den Scan-Line-Abschnitten desPolygons linear interpoliert.

Phong-Shading Analog zum Gouraud-Shading. Nur werden jetzt beim Verrastern die Normalenvektoren anden Polygoneck- punkten auf diese Weise ins Innere interpoliert und für die Farbberechnung durch Auswertender Beleuchtungsformel verwendet.

21


3.9.3 Textur

Feinstruktur, die durch Funktionen beschrieben wird, die die Abhängigkeit der Parameter des Beleuchtungs-modells vom Ort beschreiben.Textturverfahren

simulierte Textur Funktion, die als Parameter eine Koordinatenangabe im Texturkoordinatensystemhat. Für den durch die Koordinatenangabe gegebenen Punkt wird als Ergebnis der entsprechendeTexturwert zurückgegeben.

Vorteil: keine Schwierigkeit mit Alias-EffektenNachteil: Simulierte Texturen wirken häufig wenig natürlich.

abgebildete Textur (Texture Mapping) Die Textur wird als Rastermatrix (Texturkarte) vorgeben, diez.B. durch Digitalisieren natürlicher Texturen gewonnen wurde.

Vorteil: natürliches AussehenNachteil: Anti-Alias-Maßnahmen sind erforderlich; Bsp.: Mip-Mapping

Wiederholungstextur: entsteht durch periodische Wiederholung des gegebenen Texturbildes („Ka-chel“)

Problem: Elimination von Kanten und des PeriodenartefaktsLösungsmöglichkeiten

1. Überlappen der Kacheln und Überblenden der Überlappungsbereiche2. Schaffung einer periodischen Kachel mit geglätteten Kanten im Inneren

Abbildung 17: Textur in der Graphik-Pipeline

3.9.4 Strahlverfolgung

mehr Realismus durch Simulation von Schlagschatten, Spiegelung und Brechung

22

4 EINGABESENSORIK

4 Eingabesensorik

Abbildung 18: Interaktionsmodell

Abbildung 19: Seite der Maschine

Sensor Gerät zu Erfassung von phsysikalischen Signalen der Umwelt

• Sensortypen

– elektrooptische Sensoren: Fotozelle, CCD-Chip– elektromchansiche Sensoren: Potentiometer, Schalter, Dehnstreifen, Drehmomentsensor– elektromagnetsche Sensoren: Antennen– elektroakustische Sensoren: Mikrofon

Eingabegerät Kombination von Sensoren zur Erfassung von Information vom Anwender des Systems

4.1 Eingabesensoren und Eingabegeräte

• Bewegungsverfolgung

– Leistungsmerkmale

23

4.2 Sensordatenverarbeitung 4 EINGABESENSORIK

∗ Räumliche Abweichung∗ Räumliches Rauschen (jitter)∗ Stabilität oder Abwandern (creep)∗ Latenz∗ Latenzschwankungen∗ andere dynamische Fehler

– Gerätetypen

∗ mechanische Bewegungsverfolgung∗ drehmomentbasiere Bewegungsverfolgung (Gyroskop)

Gyroskop (Kreiselkompass) Messung der räumlichen AusrichtungBeschleunigungsmesser werden zur Ortsbestimmung verwendet

· Vorteil: klein, keine Emitter, keine Felder, sehr geringe Latenz, gute Voraussagemöglich-keit, extrem geringes Rauschen.

· Nachteil: Hoher Drift (örtliche Abweichung)

∗ akustische Bewegungsverfolgung∗ elektromechanische Bewegungsverfolgung∗ optische Bewegungsverfolgung

· Distanzsensoren über Lasercanner oder Time-of-Flight (über lichtverzögerung

∗ radio- und mikrowellenbasierte Bewegungsverfolgung (z.B. GPS)

4.2 Sensordatenverarbeitung

Abbildung 20: Verarbeitungspipeline

• Ergebnis der Verarbeitungspipeline:

– Zeichen, Wert, Position, Ton, Bild– als Enzelwert oder als Folge

24

4.3 Digitale Bildverarbeitung 4 EINGABESENSORIK

• Leistungsmerkmale der Sensoredateverarbeitung

– Abweichung Soll-Ist-Signal– Latenz, Latenzschwankungen

4.3 Digitale Bildverarbeitung

Abbildung 21: Stufen der Bildverarbeitung

Abbildung 22: Bildaufnahme

4.3.1 Bildrestauration

Verbesserung von Bildsignalen im Sinne quantitativ definierter Kriterien (im Gegensatz zu den subjektivenKriterien bei der Bildverbesserung).

• Vorgehensweise

1. Definition eines Signalmodells, das den Zusammenhang zwischen der die Bildszene repräsentiertenHelligkeitsverteilung (zu erfassende Szene) und dem mit Hilfe eines technischen Systems gewon-nenen Bildsignal (Ergebnis der Szenenerfassung) wiedergibt.

25


2. (Näherungsweise) Rückrechnung des Originalsignals aus dem gewonnenen Signal mit Hilfe desSignalmodells.

• Beispiel für ein Signalmodell:

˜f(x, y) =

ˆ ˆf(ξ, η)h(x− ξ, y − η)δξδη + r(x, y)

– Im Ortsfrequenzbereich:˜F (u, v) = F (u, v) ·H(u, v) +R(u, v)

wobei h(H) die sogannte Modulationsübertragunsfunktion mit Tiefpasscharakteristik ist und r(R)eine Zufallsfunktion ist (z.B. das Rauschen eine CCD-Chip)

• Problem Bildrestauration:

– Gegeben: ˜F (u, v) (das Erfasste Ausgabesignal)– Gesucht: F (u, v) (das zu erfassende Eingabesignal)– Schwierigkeit: Nullstellen von H(u, v) verhindern die exakte Restauration (auch wenn das Rau-

schen wegfällt)– Lösung: Annäherung

4.3.2 Bildverbesserung

• Ziel: Bildsignale so aufbereiten, dass die für eine gestellte Aufgabe relevante Information besser visuellbzw. maschinell extrahiert werden kann.

• Schwierigkeit: Es gibt eine unüberschaubar große Anzahl publizierter Verfahren, die oft ähnlich sind.

– Ortsbereichsverfahren– Ortsfrequenzbereichsverfahren– signalunabhängige / signalabhängige Verfahren– lineare / nichtlineare Methoden

• Punktoperatoren

– Ein Punktoperator verändert den Intensitätswert eines Punktes nur in Abhängigkeit von dessenIntensität.

– Bsp: Histogrammglättung

∗ Intensitätshistogramm gibt für jeden Grauwert eines Bildes (z.B. Grauwertbild mit Q=256Quantisierungsstufen) die Anzahl seines Auftretens an:

h(f) =M−1∑m=0

N−1∑n=0

δ(f(m,n)− f)

• Lokale Operatoren im Ortsbereich

– Lokale Operatoren bilden die Intensitätswerte f(i, j) innerhalb eines lokalen Bildbereichs (Fenster)Wmn gemäß eines definierten Funktionalzusammen- hangs (Filterkern) O[.] in die Ausgabebild-elemente g(m,n) ab, d.h.

26


Abbildung 23: g(m,n) = O[f(i, j)|(i, j) ∈Wm,n]

– Gebräuchliche Festerformen: rechteck, kreuzförmig, kreisförmig

• Diskrete Fouriertransformation

– Eindimensionale diskrete Fouriertransformation (DFT)

f : 0, 1, . . . ,M − 1→ R⇒ F (k) :=M−1∑m=0

f(m)·exp(−2πi(km/M)), k ∈ 0, . . . ,M − 1, exp(ia) = cosα+i sinα

∗ Falls f reel ist, beschreibt die DFT die Darstellung von f als Summe von disk. sinusförmi-gen Schwingungen: F (k) bedeutet, dass die Schwingung der Frequenz k mit der Amplitude|F (k)|/M und der Phasenverschiebung φ(k) in f auftritt, wobei F (k) = |F (k)| exp(iφ(k))

– Inverse Eindimensionale DFT:

f(m) :=1

M

M−1∑k=0

F (k) · exp(2πi(km/M)), m ∈ 0, . . . ,M − 1

– Zweidimensionale diskrete Fouriertransformation (DFT)

f : 0, 1, . . . ,M − 1×0, 1, . . . , N − 1→ R⇒ F (k, l) :=

M−1∑m=0

N−1∑n=0

f(m,n)·exp(−2πi(km/M+ln/N))

– Inverse Zweidimensionale DFT:

f(m,n) =1

MN

M−1∑k=0

N−1∑l=0

F (k, l) · exp(2πi(km/M + ln/N))

– Nomeklatur:

∗ f(m) und F (k), bzw. f(m,n) und F (k, l) heißen diskretes Fouriertransformationspaar∗ m,n Ortskoordinaten∗ f(m,n) heißt Ortsfunktion∗ k, l heißen Ortsfrequenzkoordinaten∗ F (k, l) Ortsfrequenzspektrum∗ m− n-Ebene: Ortsbereich∗ k − l-Ebene: Ortsfrequenzbereich

– Bemerkung:

∗ F (k, l) ist üblicherweise komplexwertig∗ F (k, l) = ReF (k, l) + i · ImF (k, l) = |F (k, l)| exp(iφ(k, l))

27


∗ |F (k, l)| =√

ReF (k, l)2 + i · ImF (k, l)2 heißt Amplitudenspektrum∗ φ(k, l) = arctan(ImF (k, l)/ReF (k, l)) heißt Phasenspektrum∗ |F (k, l)|2 = F (k, l)F (k, l) heißt Leistungsspektrum von F (k, l)

– Eigenschaften der DFT∗ Vertauschungssatz:∗ Separierbarkeit∗ Faltungssatz∗ Satz von Parseval

• Bildverbesserung im Ortsfrequenzbereich

– Vorgehensweise1. Anwendung der DFT auf das gegebene Bild (mit FFT-Alg.)2. Filtern im Ortsfrequenzbereich (Multiplikation)3. Rücktransformation (mit FFT-Alg.).

– Bsp:∗ rotationssymmetrischer idealer Tiefpass mit Bandbreite ω0 :

HITP (k, l) :=

1 für

√k2 + l2 ≤ ω0

0 sonst

∗ Gaußtiefpass:HGTP (k, l) = exp(−(k2 + l2)/ω2

0

4.3.3 Segmentierung

Segmentierung: Unterteilung von Bildern in bedeutungsvolle Teilbereiche.

Definition 4.1. (Segmentierung)Unter der Segmentierung eines diskreten Bildsignals f(m,n), 0 ≤ m ≤M − 1, 0 < n < N − 1, versteht mandie Unterteilung von f, als Menge von Pixeln gesehen, in disjunkte, nichtleere Teilmengen f1, f2, ...fp so, dassmit einem zu definierenden Einheitlichkeitskriterium E gilt:

1. ∪Pi=1fi = f

2. fi ist zusammenhängend für alle i mit i = 1, . . . , p

3. Für alle fi ist das Einheitlichkeitskriterium E(fi) erfüllt.4. Für die Vereinigung zweier benachbarter fi, fj ist E(fi ∪ fj) nicht erfüllt.

Einheitlichkeitskriterium: z.B. die Intensitätsdifferenz zweier beliebiger Bildpunkte innerhalb eines Be-reichs fi darf den Wert e betragsmäßig nicht überschreitet (Kriterium der Intensitätshomogenität)

Abbildung 24: Darstellung von Konturlinien durch Kettencodes

28

4.4 Mustererkennung 4 EINGABESENSORIK

Verfahren• bereichsorientierte Verfahren

– Einfacher Schwellwertoperator g(m,n) =

I1 , 0 ≤ f(m,n) < s

I2 , s ≤ f(m,n) ≤ fmax

– Mehrwertiger Schwellwertoperator g(m,n) = Ii für si−1 ≤ f(m,n) < si, i ∈ 1, 2, . . . p

– Q-dimensionale Histogramme: Zählung der Pixel nach Q -dimensionalen Merkmalen, z.B. Häufig-keit in Abhängigkeit von Intensitätswert und dem lokalen Intensitätsgradienten

∗ Trennung der als Punktwolken repräsentierten Merkmale in Cluster, z.B. durch (Q− 1)-dim.Hyperebenen

Abbildung 25: Bereichsorientierte Verfahren mit Clustering

– Bereichswachstumsverfahren

1. Zuordnung eines Anfangspunktes an jeden Bereich fξ2. Starten eines iterativen Prozesses, bei dem Unterbereichen von fξ (am Anfang aus einem

Anfangspunkt bestehend) benachbarte Bildpunkte mit ähnlichen Eigenschaften zugeordnetwerden.

3. Ende, wenn jeder Bildpunkt einem Unterbereich zugeordnet ist4. Evtl. Bereichsverschmelzung.

– Unterteilungsverfahren : sukzessives Unterteilen des Bildes, solange bis die Teile das gegebeneEinheit- lichkeitskriterium E erfüllen; Vereinigen benachbarter Teile, die das Einheitlichkeitskri-terium erfüllen. z.B. Quadtree

1. Teile jede Region Ri, für die E(Ri) nicht erfüllt ist, in 4 Quadranten auf2. Verschmelze alle benachbarten Regionen Rj , Rk für die E(Rj ∪Rk) erfüllt ist.3. Ende, wenn kein weiteres Unterteilen oder Vereinigen möglich ist

• kantenorientierte Verfahren

– Generell:

1. Zuordnung eines Eigenschaftsgradienten an jeden Bildpunkt.2. Nachbearbeitung, z.B. Konturverfolgung.

– Lokale Gradientenoperatoren

4.4 Mustererkennung

Muster Zusammenfassung der gemessenen Werte einer einzelnen Stichprobe aus einem begrenzten Aus-schnitt der Welt.

29

4.4 Mustererkennung 4 EINGABESENSORIK

Mustererkennung Zuordnung einer solchen Stichprobe an eine von mehreren Klassen.Merkmal Kenngröße, die einem Muster zugeordnet wirdKlassifikationsraum besteht aus in der Regel disjunkten Klassen, in die eine Kombination von Merk-malen

durch die Klassifikation abgebildet wird.

• Ziel: Möglichst wenige Merkmale finden, die die eindeutige Klassifikation des gegebe-nen Musters er-lauben, d.h. die Dimension des Merkmalsraums soll klein gehalten werden.

• Merkmalstypen

– numerische Merkmale: Zahl → “Statistik”– symbolische Merkmale: Zeichenketten → “KI”

Abbildung 26: Vorgehensweise für Mustererkennung

4.4.1 Merkmale

• Fläche (F): Anzahl der Pixel der Objekte• Umfang (U):

– Heuristik: Abzählen von benachbarten Punktepaaren (p, q), p Hintergrundpixel, q Objektpixel– Heuristik: Konturverfolgung mit Längeneinheit 1 für horizontale/vertikale Fortschreitung und

√2

für diagonale Fortschreitung

• größeninvarianter Formfaktor:

S :=U2

4πF

• Krümmung an den Objekträndern:

– Krümmung an einem Punkt pi: Winkeldifferenz der Graden die Punktepaar (pi−1, pi) und (pi, pi+1)

– k−Krümmung an einem Punkt pi: Verwende für die Krümmung, nicht die direkten, sondern diek−nächsten Nachbarpunkte

– Maße:∗ Mitterwert der (k−)-Krümmung als Maß für die Kräummung linienförmiger Objekte.

30

4.5 Verarbeitung zeitabhäniger Signale 4 EINGABESENSORIK

∗ Histogramm anstatt Mittelwert

• Fourier-Deskriptor:

– Eingabe: Objektrand durch Q Kontrollpunkte (xi, yi) mit i ∈ 0, . . . , Q− 1

– Ausgabe: Teilmege der Koeffizienten der DFT von

f : 0, 1, . . . , Q− 1→ C, f(j) := xj + i · yj

4.4.2 Numerische Klassifikation

• Aufgabe: Merkmalsvektor c einer Klasse Ωk ⊆ Ω,Ω der Merkmalsraum, zuordnen.

– Bsp.: Merkmal (Helligkeitsgrad, Maserung), Klassen „Birke“, „Esche“

• Versionen der numerischen Klassifikation

– Klassifikation mit überwachtem Lernen: durch Stichproben von Mustern, deren Klassenbekannt sind (Trainingsmenge)

– Klassifikation mit unüberwachtem Lernen: die Klassen der Stichprobenmuster sind unbe-kannt

• Methoden:

1. Statistische Klassifikation:– Herleitung einer Wahrscheinlichkeitsverteilung über Ω für jede Klasse Ωk, die angibt, mit

welcher Wahrscheinlichkeit ein Element aus Ω in Ωk liegt.– Beispiele für Vorgehensweisen:

∗ Parametrische Schätzung: Für die Wahrscheinlichkeitsverteilung wird ein Grundtyp an-gesetzt, dessen freie Parameter aus einer gegebenen Trainingsmenge bestimmt werden(überwachtes Lernen)

∗ Nichtparametrische Schätzung: Bestimmung eines Histogramms für die einzelnen KlassenΩk über einer Zellzerlegung von Ω aus einer gegebenen Trainingsmenge (überwachtesLernen).

2. Verteilungsfreie Klassifikation:– Beispiele für Vorgehensweisen:

∗ Überwachtes Clustering: Festlegen eines Zerlegungsverfahrens, dessen Parameter so be-stimmt werden, dass der Erwartungswert der Differenz zwischen der dadurch induziertenKlassenzuordnung und der Klassenzu-ordnung einer gegebenen Trainingsmenge minimalist (überwachtes Lernen).

∗ Unüberwachtes Clustering: Bestimmung einer Zellzerlegung entsprechend eines gegebe-nen Raumzerlegungsverfahren, z.B. in Gruppen von eng benachbarten Merkmalen, diewechselseitig jedoch einen großen Abstand haben. Die Gruppen legen die Klassen fest(unüberwachtes Lernen).

4.5 Verarbeitung zeitabhäniger Signale

• kontinuierliches zeitabhängiges Signal: x : T → Rd, T ist ein relles Intervall• diskretes zeitabhängiges Signal: vi = (tixi), wobei ti, xi ∈ Rd, ti < ti+1

• reguläres diskretes zeitabhängiges Signal: ein diskretes zeitabhängiges Signal, bei dem ti+1–ti =∆t =konstant. In diesem fall wird vi = xi gesetzt.

• online-Verarbeitung: zu einem Verarbeitungszeitpunkt t? ist nur x(t), mit t ≤ t? bekannt.• Echtzeit-Verarbeitung: Online-Verarbeitung, bei der die Differenz zwischen der Rückgabezeit der

Ergebnisse zweier aufeinanderfolgender Verarbeitungsaktionen höchstens gleich der Differenz zwischenden Zeitpunkten ist, zu denen die Verarbeitung gestartet wird.

31

5 MECHANIK, KOLLISION UND HAPTIK

• Latenzzeit: Zeitverzögerung zwischen Beginn der Verarbeitung und der Rückgabe des Ergebnisses derVerarbeitung

Abbildung 27: Besonderheiten Zeitabhäniger Signale

4.5.1 Filterung zeitabhängiger Signale

• Einsatzgebiete

– Signalrestauration– Signalverbesserung– Beispiel:

∗ Elimination von Rauschen (Tiefpassfilter)∗ Extrapolation des Signals zur Minderung der Latenzzeit (Prädiktionsfilter)∗ Interpolation eines diskreten Signals zur Schaffung eines hinreichend dichten diskreten Aus-

gabesignals– Filtertypen:

∗ nichtrekursive Filter wn = f(vn, vn−1, . . .)

· Bsp: finite impulse response filter (FIR)

yn =

N∑i=0

bixn−1

∗ rekursive Filter wn = f(wn−1, . . . , vn, vn−1, . . .)

· infinite impulse response filter

yn := −N∑i=1

aiyn−1 +∑

bixn−1

5 Mechanik, Kollision und Haptik

Mechanik Teilgebiet der Physik

32

6 SPRACHVERARBEITUNG

Kollision Interaktion zwischen bewegten ObjektenHaptik Tastsinn

• Anwendung:

– Unterstützung bei der Platzierung von Objekten, z.B. durch Simulation von Schwerkraft– Interaktion mit einer dreidimensionalen virtuellen Umgebung, z.B. Videospiele, Computer-Aided

Design (CAD) von mechanischen Teilen (Maschinenteile, Architektur)– Ausnutzung des Tastsinns für die Mensch-Maschine-Interaktion durch Ausgabe von Kräften

• Wiederholungsschleife:

1. Lokalisiere den virtuellen Manipulator in der virtuellen Szene entsprechend der aktuellen Einga-bewerte.

2. Aktualisiere die Szene und berechne die Reaktionskraft auf den virtuellen Manipulator.– Kollisionsdetektion

∗ Bestimmung der geometrischen Wechselwirkung zwischen dem virtuellen Manipulator undder Szene, z.B.a) Kollisionssituation zwischen Manipulator und Szene,b) minimaler Abstand zwischen Manipulator und Szene,c) Kollisionszeitpunkt zwischen Manipulator und Szene

– Kollisionsreaktion∗ Bestimmung der mechanischen Wechselwirkung zwischen dem virtuellen Manipulator und

der Szene, z.B.a) Berechnung der wirkenden Kräfteb) Veränderung des virtuellen Manipulators und der Szene durch die wirkenden Kräfte

3. Wende die Reaktionskraft auf das Eingabegerät an.

6 Sprachverarbeitung

6.1 Erkennen von gesprochener Sprache

Abbildung 28: Schematische Darstellung eines (verinfachten) Sprachverkennungssystems

• Laut/Phonem-Zerlegung

33

6.1 Erkennen von gesprochener Sprache 6 SPRACHVERARBEITUNG

– Phonetik: Lautstruktur einer Sprache– Laut (phone): Klangeinheit

∗ Zwei Hauptklassen von Phonemen:

· Konsonanten (b,c,d,g,h,...)· Vokale (a,e,i,o,u)

∗ Nebenklasse: Semivokale (engl: y,w)

– Prosodie: Beinhaltet Eigenschaften wie Tonhöhe (pitch) und Dauer

• Phonetische Alphabete

– International Phonetic Alphabet (IPA)– ARPAbet, emerikanisch Englisch

• Phonem: Klasse ähnlicher Laute, die Allophone genannt werden

6.1.1 Merkmalsextraktion

• Ablauf

– Diskretisierung

∗ Abtastfrequenz: 8 - 20KHz∗ Quantisierung: 11 Bit, 8Bit (log Skala)

– Segmentzerlegung:

∗ Zerlegung des Sprachsignals in überlappende Segmente∗ Segmentlänge meist 20ms∗ typischer Abstand der Segmentmitten: 10ms

– Merkmale den Segmenten zuordnen

∗ originalsignalbasierte Merkmake

· Gesammtintensität· mittlerer Abstand von Signalspitzten· lieanre voraussagende Codierung (linear predictive code (LPC)), bestimme ai so, dass derVoraussagefehler minimal wird. (Typisch n=8-14)

x(k) =

n∑i=1

aix(k − i)

· kleiner Fehler: periodisches Signal· großer Fehler: aperiodisches Signal

∗ spektrogrammbasierte Merkmale

· Fourier-Tranformation der Segmente· Dargestellt über grauwerte an Frequenzachse entlang

∗ Gesammtintensität in verschiedenen Frequenzbereichen

· Formantenverteilung (Formant: starkes Extrema im Spektrum)

∗ Cepstrum: inverse Fourier-Transformierte des Logarithmus des Leistungsspektrums∗ Zeitanhänige Merkmake: z.B. Wiederhohlung von Segmenten mit ähnlichen Merkmalen

34

6.1 Erkennen von gesprochener Sprache 6 SPRACHVERARBEITUNG

6.1.2 Phonemzuordnung

• Aufgabe: Zuordnung von Phonemen qj zu Merkmalsvektoren oi durch Bestimmung von Beobachtungs-wahrscheinlichkeiten bj(oi) = P (oi|qj).

• Realisierung: Hidden-Markov-Modell trainieren.• Repräsentation der Wahrscheinlichkeiten:

– Diskrete Repärsentation∗ Diskretisierung der Merkmalsvektoren auf endl. viele Werte (Vektorquantisierung)

– Kontinuierliceh Repräsentation∗ Neuronales-Netz-basierter Schätzer∗ Gauß’scher Schätzer

6.1.3 Wortzerlegung

• Lösungsansätzte:

– Aufbau eines Lexikons von erknnerners (Klassifikatoren) von Enzerlworten– Zusammensetzten der Ernenner von Enzelworten zu einem Erkennern für Sprachsequenzen– Schwierigkeit: Wortgrenzen

• Technik: Hidden-Markv-Modell

– Xt Zufallsvariable der nichtbeabachtbaren Zustände– Et Zufallsvariable der beobachtbaren Zustände– Systemmodell: p(Xt|Xt−1), d.h. ein Zustand hängt nur von seinem unmuttelbaren Vorgänger-

zustand ab. p(X0) Ausgangszustand.– Beobachtungsmodell: p(Et|Xt), die aktuell beobachtbaren Zustandvariablen hängen nur von

den aktuellen nichtbeobachtbaren Zustandsvariablen ab.– Vektorrepräsentation von diskreten Zufallsvariablen

∗ Systemmodell durch Anfangsverteilungsvektor µ = (µi), µi := p(X1 = i) und Übergangsma-trix A = (ai,j), ai,j := p(Xt+1 = j|Xt = i)

∗ Beobachtermodell durch Vektor b = (bj), bj := p(Et|Xt = j), d.h. bj(et) ist die W’keit dafür,dass im Zustand j der Werkt ej beobachtet wird.

∗ µi, ai,j und bj werden als unabhänig von t angesehen.– Wortmodell: Markov-Prozess, der Sequenzen von Phonemen/lauten/Teillauten beschreibt, die

einem Wort zugeorndet sind.

Abbildung 29: Wortmodell Beispiele

35

6.2 Synthese gesprochener Sprache 6 SPRACHVERARBEITUNG

∗ Einzelworterkennung, durch wahl desjenigen Wortes eines der Wortmodelle, das die größteWahrscheinlichkeit hat.

– Wortsequenzerkennung durch zusammensetzten von Wortmodellen zu einem Wortsequenzmodell,Wählen der Sequenz, derer Wortsequenzmodell die höchste W’keit hat.

∗ Die Verbindungskanten im Wortsequenzmodell sind die Wahrscheinlichkeiten für das Auf-treten von Wortparen (Bigramm-Wahrscheinlickeiten)

Viterbi-basierte Decodierung Finde die besten Zustandsfolge für eine beobachtete Folge von Lauten

Abbildung 30: Viterbi-Algorithmus

6.1.4 Qualität von Spracherkennungsystemen

Wortfehlerrate. Basiert auf der Editierdistenz zwischen Realer Wortfolge und erkannter Wortfolge

ef := 100i+ s+ d

l%

Wobeief Die Wortfehlerratei Anzahl der Einfügeoperationens Anzahl der Ersetzungoperationend Anzahl der Löschoperationenl Anzahl der Worte in der korrekten Referenztranskription

6.2 Synthese gesprochener Sprache

• Aufgabe der Synthese gesprochener Sprache:

– Eingabe: geschriebener Text– Ausgabe: gesprochener Text

36

6.2 Synthese gesprochener Sprache 6 SPRACHVERARBEITUNG

– Lösungschitte:1. Textanalsyse2. Aussprachesynthese und Signalgenerierung

• Textanalyse

– Herleitung einer Beschreibung der linguistischen Struktur eines gegebenen Textes.∗ Textsegmentierung: Zerlung in Absätze, Sätze und Worte∗ Morphologie und Aussprache: Analyse der Wortstrutkur und Ableitung einer Beschreibung

der Ausssprache∗ Markieren und Parsen: Berücksichten der Satzstruktur∗ Berücksichtigung von Effekten der koninuierlich gesprochenen Sprache: “Verschliefen” der Aus-

sprache benachbarter Worte

• Signagenerierungsverfahren

– Wellenbasierte Signalgenerierung (Waveform Synthesizers)∗ Zusammensetzen dersprochener Srapche aus Spracheinheiten mit Glättung zwischen den Ein-

heiten. Ein verfahren das viel Speicher benötigt

Einheit Beschreibung Vor/Nachteil

Wörter Basiseinheiten eines Satzes Vorteil: Hohe Sprachqualtiät, einfacheSynthese

Silben aus Necleus bestehend(benachbarte Konsonaten) Unsichere Sibelgrenze

Halbsilben halbe Silben Erzeugt Glatte Sprache

Diphone Ergeben sich durch Teilung des Sprachsignals Erhalten übergang zwischen Benachbarten Lauten

Allophone phonemische Varianten Rreduziert komplexität gegenüber Phonemen

Phoneme Basisheinheit der Phonologie Geringer Speicherbedarf, aber Komplex bei Glättung und Intonation

Tabelle 1: Einheiten gesprochener Sprache

• Artikulationsbasierte Signalgenerierung (Articulatory Synthesizers)

– Nachbildung der Artikulationstraktes des Menschen∗ Liefert relativ schlechte Sprachqualität

– Abstrahlungsverfahren Terminal Analog Synthesizers (LPC vocoder)∗ Effizient, aber geringe Sprachqualität

– Formantensynthese (Formant Synthesizers)

Abbildung 31: Abstrahlungsverfahren

37

Documents

1 Einführung 2 Interaktionstechniken und Interaktionsstile ...landarzar.net/wp-content/uploads/2013/07/MMI.pdf · nau dann eine Delaunay-Triangulierung, wenn jeder Simplex Delaunay-Simplex