Girds and Interpolation Flashcards
Natürliche Probleme sind in der Regel kontinuierlich. Warum brauchen wir (diskrete) Grids?
- Computer können nur begrenzte Datenmengen verarbeiten, kontinuierliche Daten müssen abgetastet werden
- Messungen werden an diskreten Orten vorgenommen
- Simulationen berechnen Werte typischerweise auf Grids
Welche Daten müssen für generelle Gridarten gespeichert werden?
- Dimensionen
- Liste mit Vertices
- Liste mit Zellen
- Optional: Liste mit Edges, Querverweis für Zelle und Vertices und Querverweis für Zelle und Edges
Welche Arten von 3D Grids gibt es?
- Uniform rectilinear
- Curvylinear
- Unstructured
Wie sind die Eigenschaften von uniform rectilinear grids?
- Zellen: uniform hexahedrons: cuboids oder cubes
- Struktur: uniform regular
Wie sind die Eigenschaften von curvylinear grids?
- Zellen: Varying heahedrons
- Struktur: Nicht uniform aber strukturiert
Wie sind die Eigenschaften von unstructured grids?
- Zellen: Tetrahedre (seldom hexahedra, pyraminds oder prisms)
- Struktur: unstructured
Wie werden Uniform Grids charakterisiert?
Uniform Grids haben konstante Abstände entlang der räumlichen Dimensionen
Was muss man bei Uniform Grids speichern?
- Dimensionen in jede Richtung
- Zellengröße
- Daten als Array
- Position des Startpunktes
Wie werden Rectilinear Grids charakterisiert?
Rectilinear Grids haben unregelmäßige Abstände entlang der räumlichen Dimension
Was muss man bei Rectilinear Grids speichern?
- Dimension in jede Richtung
- Koordinaten der Linien/ Flächen
- Daten als Array
Wie werden Curvilinear Grids charakterisiert?
Curvilinear Grids haben unregelmäßige Abstände entlang der räumlichen Kurven
Was muss man bei Curvilinear Grids speichern?
- Dimension in jede Richtung
- Liste der Stichprobenpunkte, Koordinaten der Stichprobenpunkte
- Daten als Array
Wie werden Unstructured Grids charakterisiert?
Keine regelmäßige Struktur, “minimale” topologische Struktur
Was muss man bei Unstructured Grids speichern?
- Anzahl der Stichprobenstellen
- Anzahl der Zellen
- Liste aller Stichprobenstellen, Koordinaten der Stichprobenstellen
- Liste aller Zellen
- Daten als Array
Was sind die Vorteile von Uniform Rectilinear Grids?
- Einfach
- Effizienter Zugang
- Zellensuche trivial
Was sind die Nachteile von Uniform Rectilinear Grids?
- Überall die gleiche Auflösung
- Keine lokale Verfeinerung
Was sind die Vorteile von Curvilinear Grids?
- Flexibler als Rectilinear
- Natürliche Darstellung für bestimmte Arten von Sensordaten (z.B. Ultraschall)
Was sind die Nachteile von Curvilinear Grids?
- Gridstruktur muss gespeichert werden
- Zellensuchalgorithmus könnte erforderlich sein
- Mehr Informationen müssen gespeichert werden
Was sind die Vorteile von Unstructured Grids?
- Sehr flexibel
- Lokale Verfeinerung möglich
Was sind die Nachteile von Unstructured Grids?
- Positionen und Struktur muss gespeichert werden
- Zellensuchalgorithmus ist notwendig
Was ist eine Schallwelle?
Eine Schallwelle ist eine Schwingung, die sich als Welle durch ein Medium bewegt
Was ist Abtastung einer Schallwelle?
Eine Abtastung ist eine Messung an diskreten Punkten in der Zeit
Was ist eine Quantisierung einer Schallwelle?
Eine Quantisierung ist eine diskrete Repräsentation eines kontinuierlichen Wertes als Digitalwert mit begrenzter Genauigkeit
Wie lautet die grundlegende Frage bei der Abtastung von kontinuierlichen Daten?
Wie müssen wir abtasten, damit wichtige Eigenschaften des ursprünglichen Signals erhalten bleiben?
Wie ist der Ablauf einer Abtastung mit Quantisierung?
- Ein kontinuierliches Signal wird abgetastet
- Ergebnis ist ein diskretes Signal
- Die Abtastwerte werden quantisiert und mit einer bestimmten Genauigkeit (32 Bit) gespeichert
Durch welche zwei Fehlerquellen wird die in den abgetasteten Daten dargestellte Information eingeschränkt?
- Quantisierung mit begrenzter Genauigkeit
- Abtastung an zu wenig Abtastpunkten
Welche Stichprobenpunkte (zeitlicher und räumlicher Abstand) sollte ich wählen und welche Konsequenzen hat diese Wahl?
Die Antwort wird durch das Sampling Theorem gegeben
Wie kann man jedes kontinuierliche Signal dargestellt werden?
Jedes kontinuierliche Signal kann dargestellt werden durch eine Überlagerung von Sinus- und Kosinuswellen mit unterschiedlichen Frequenzen
Wann ist ein Signal bandbegrenzt?
Ein Signal ist bandbegrenzt, wenn sein Frequenzspektrum auf ein endliches Intervall limitiert ist -> kein Unendlichkeitszeichen in der Summe-Funktion
Wie lautet das Sampling Theorem?
Ein kontinuierliches Signal mit der maximalen Frequenz tmax ist vollständig bestimmt durch seine diskrete Abtastung mit einem Abtastabstand der kleiner ist als 1/(2*tmax)
Wie kann man ein mit ausreichender Genauigkeit abgetastetes Signal rekonstruieren?
Ein mit ausreichender Genauigkeit abgetastetes Signal kann ohne Informationsverlust durch Verwendung der sinc-Funktion aus dem Abtastwert rekonstruiert werden
Was passiert wenn man ein Signal rekonstruieren will, dass mit zu kleiner Abtastrate abgetastet wurde?
Man rekonstruiert das falsche Signal -> Das bezeichnet man als Aliasing
Wie berechnet man die partielle Ableitung für Funktionen mit mehr als einer Variable?
Ableitung nach einer Variable, alle anderen fest lassen
Wie lauten die Eigenschaften des Gradientenvektors?
- Zeit in die Richtung der steilsten Neigung
- Ist senkrecht zu den Isolines
- Ist am lokalen Extremum gleich Null
Welche zwei Optionen gibt es bei der Ableitung von diskreten Werten?
- Annäherung an die lokalen Daten durch eine differenzierbare Funktion und dann diese Funktion differenzieren
- Annäherung an die Ableitung mit endlichen Differenzen
Wie funktioniert die erste Option (Curve Fitting) bei der Ableitung von diskreten Werten?
- Finde ein Polynom zweiten Grades, das die Daten lokal approximiert
- Differenzieren Sie diesen Polynom nach xi
Was ist Interpolation?
Interpolation ist die näherungsweise Rekonstruktion des ursprünglichen Signals
Wie lautet die einfachste Art der linearen Interpolation?
Nearest-Neighbour
Wie funktioniert die Interpolation im Tetraeder?
- Verbinde inneren Punkt mit allen Eckpunkten -> 4 Subtetraeder
- Das Volumen des Subtetraeders ergibt das baycentric Gewicht des gegenüberliegenden Punktes
- Analoge Berechnung für alle Subtetraeder
- Interpolation der Werte, die an den Tetraedervertices gegeben sind
Was braucht man für eine glatte Interpolation?
Die glatte Interpolation erfordert ein stückweises kubisches Polynom, das (mindestens) einmal differenzierbar ist und eine kontinuierliche Ableitung hat
Wie funktioniert die Catmull-Rom-Interpolation?
- Gegeben sind diskrete Datenpunkte mit konstantem Abstand
- Ableitungen werden geschätzt mit zentralen Differenzen
- Interpolationsfunktion ist gegeben als stückweises kubisches Polynom, wobei jedes Segment die Punkte als auch die Ableitungen interpoliert
Was kann man noch für die Interpolation benutzen?
Kurven höherer Ordnung, wie zum Beispiel Bézier- oder B-Spline Kurven
Was ist das Ziel von linearen Filtern?
Bei einem Eingangssignal möchten wir bestimmte Frequnzen “auswählen” oder unterdrücken
Was ist ein Lowpass Filter?
Ein Lowpass Filter lässt tiefe Frequenzen durch und blockiert hohe Frequenzen
Was ist ein Highpass Filter?
Ein Highpass Filter lässt hohe Frequenzen durch und blockiert tiefe Frequenzen
Was ist ein Bandpass Filter?
Ein Bandpass Filter lässt nur Frequenzen innerhalb eines bestimmten Frequenzbandes durch
Wie lautet der allgemeine Ansatz für lineare Filter?
- Ein Wert des Ausgangssignals wird als Linearkombination von den Eingangssignalwerten berechnet
- Dieser Filterungsprozess wird als Faltung bezeichnet
Was ist der Zweck eines Lowpass Filters?
- Glättung von scharfen Kanten
- Rauschunterdrückung
- Erzeugt Unschärfe
Nennen Sie Beispiele für einen Lowpass Filter.
- Box Filter
- Triangle Filter
- Gaussian Filter
Was ist der Zweck von Highpass Filtern?
Kantendetektion (starke Signaländerung)
Wie funktioniert ein Highpass Filter zweiter Ordnung?
Anstelle der Lokalisierung des Maximums von f’ wird nach Nulldurchgängen von f’’ gesucht
Wie lautet das Ziel von linearen Filtern in 2D?
Filterung auf 2D-Signale (z.B. Bilder) anwenden
Was ist das Problem bei der Anwendung von großen Filtern und Filtern in höheren Dimensionen (2D oder 3D)?
Das Problem bei der Anwendung von großen Filtern und Filtern in höheren Dimensionen ist, dass diese eine große Anzahl an Berechnungen erfordern
Was sind Separable Filter?
- Separable Filter können als eine Faltung von 1D-Filtern verkettet werden, was zu einem reduzierten Berechnungsaufwand von n*w führt
- Reduzieren den Berechnungsaufwand von polynomisch zu linear
Welche Separable Filter haben wir kennengelernt?
- 2D Gaussian Filter
- 2D Sobel Filter
- 2D Laplace Filter
- Lowpass Filter (Box-, Triangle- und Gaussian Filter)
Wofür werden höher dimensionale lineare Filter verwendet?
Höhere dimensionale lineare Filter werden verwendet, um Bilder oder volumetrische Daten zu glätten
Wie funktionieren nicht lineare Filter?
Nicht lineare Filter verwenden eine beliebige Funktion, die von den Werten innerhalb eines strukturierenden Elements abhängt, welches in der Regel eine begrenzte Größe hat
Wie funktioniert der Median-Filter?
- Sortiere alle Werte in einem Bereich
- Wähle den Mittelwert als Ausgabewert
Wie funktioniert ein Rangordnungsfilter?
- Sortiere alle Werte in einem Bereich
- Wähle den Ausgabewert anhand des Rangs in der sortierten Liste
Was sind Morphologische Filter?
Morphologische Filter sind ebenfalls Rangordnungsfilter, die die geometrische Struktur des Signals verändern
Was ist eine Dilatation?
- Nehme das Maximum der sortierten Liste
- Vergrößert den Vordergrund entsprechend der Größe des Kernels
Was ist eine Erosion?
- Nehme das Minimum der sortierten Liste
- Verkleinert den Vordergrund entsprechend der Größe des Kernels
Was ist ein Opening?
- Eine Hintereinanderausführung von Erosion und Dilatation
- Neigt dazu, kleine Merkmale im Vordergrund zu entfernen und kleine Hintergrundmerkmale zu erhalten
Was ist ein Closing?
- Eine Hintereinanderausführung von Dilatation und Erosion
- Neigt dazu, kleine Hintergrundmerkmale zu entfernen und kleine Vordergrundmerkmale zu erhalten
Was ist der Zweck des Median Filters?
- Entfernung von Extremwerten
- Entfernung von Rauschen
Was ist der Zweck von Erosionsfiltern?
Vergrößerung von dunklen Bildregionen
Was ist der Zweck von Dilatationsfiltern?
Vergrößerung von hellen Bildregionen
Wie kann man mit Hilfe von Morphologischen Filtern wie Erosion und Dilatation Kanten in
Bildern extrahieren?
- Indem man von einem Eingabebild eine Dilatation und eine Erosion durchführt und diese beiden Bilder voneinander subtrahiert
- Dilatation und Erosion verändern hauptsächlich die Objektgrenzen (Kanten), daher können Kanten mit dieser Operation extrahiert werden