Benutzer:Georg-Johann/Von Punkt zu Punkt

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
17 Punkte

Für eine Anzahl vorgegebener Punkte , ... soll eine geschlossene Kurve gefunden werden, welche die Punkte in der gegebenen Reihenfolge approximiert. Vom letzten Punkt soll eine Linie zum Anfangspunkt zurückführen, und zwischen den Punkten soll die Kurve einen möglichst "natürlichen" Verlauf zeigen.

Das Bild zeigt 17 Punkte, die wie bei einem Punkt-zu-Punkt-Bild miteinander zu verbinden sind, wobei der Linienschluß durch einen weiteren Punkt = zustande käme.

Interpolation[Bearbeiten | Quelltext bearbeiten]

Zunächst bestimmen wir eine Interpolante durch die  Vorgabepunkte :

Als Interpolationsverfahren zur Berechnung von bieten sich mehrere Standardverfahren an wie lineare Interpolation oder kubische Splines mit periodischer Anschlussbedingung. Das gewählte Interpolationsverfahren verwenden wir komponentenweise.

Tatsächlich hängt nicht nur von dem gewählten Interpolationsverfahren und dem Parameter  ab, sondern auch von der Wahl der "Zeitpunkte" an denen  die Werte  annehmen soll:

Die Reihenfolge, in der die Zielpunkte durchlaufen werden, ergibt sich durch die Nebenbedingungen

Vorbesetzung der Zeitpunkte[Bearbeiten | Quelltext bearbeiten]

Eine erste Belegung für die Zeitpunkte erhalten wir durch

etwa mit und damit . Die Zeitpunkte werden dadurch in gleichen Abständen auf der Zeitachse angeordnet.

Eine weitere Vorbelegung ergibt sich mittels mit , d.h. die Zeitabstände entsprechen den Abständen der Zielpunkte im Raum. Diese beiden Belegungen lassen sich auch kombinieren, indem wir die -dimensionalen Startpunkte in einbetten und ihre (gleichen) Zeitabstände mit berücksichtigen. Dies ergibt schliesslich die Wahl

mit einem Skalierungsfaktor . Die ersten beiden Wahlen für ergeben sich daraus für die Grenzfälle bzw. .

Die Galerie zeigt den Einfluß des gewählten Interpolationsverfahrens und der Wahl der Startbelegung auf .

Approximation[Bearbeiten | Quelltext bearbeiten]

Bei der Wahl der Interpolation bleibt uns – unter Beachtung der Reihenfolge der Zeitpunkte – die freie Wahl der Zeitpunkte . Da immer gilt , bleiben also Parameter, um die eingangs geforderte Eigenschaft der "natürlichen" Approximation zu erfüllen. Wie oben zu sehen hat neben der Wahl des Interpolationsverfahrens auch die Wahl der Zeitpunkte einen starken Einfluß auf das Erscheinungsbild der erhaltenen Kurve.

Durch Variation der Zeitpunkte soll nun eine Approximation berechnet werden. Die Idee ist, die diskrete Fourier-Transformation (DFT) der Interpolanten als Bewertungskriterium zu verwenden. Dazu verwenden wir  Stützstellen mit

Das durch die Fourier-Transformation erhaltene trigonometrische Polynom hat dann die Eigenschaft

und liefert damit eine Approximation der Vorgabepunkte:

Die Fourier-Transformierte berechnen wir komponentenweise für die  Koordinaten

und mit einer Zweierpotenz für . Durch die Wahl einer Zweierpotenz für lässt sich die diskrete Fourier-Transformierte effizient durch das Verfahren der schnellen Fourier-Transformation (FFT) bestimmen.

Bewertung[Bearbeiten | Quelltext bearbeiten]

Eine Approximation bewerten wir mit einer Bewertungsfunktion anhand der Amplituden in den DFTs ihrer  Komponenten:

mit zwei Parametern α und . Gute Ergebnisse ergeben sich mit α ≈ 0.9 und . Durch die Wahl erhält der -Terme eine Rechtskrümmung, so daß Amplituden, die ohnehin schon klein sind, zu Null tendieren. Für große Amplituden hingegen fällt eine Änderung weniger stark ins Gewicht. Zusammen mit dem -Term, der zur Verteurung hoher Frequenzen führt, tendiert die Bewertung zu niedrigfrequenten Approximationen.

Variation der Zeitpunkte[Bearbeiten | Quelltext bearbeiten]

Einen besseren Satz an Zeitpunkten erhalten wir durch Trial-and-Error, also durch ein Probierverfahren. Alles andere hat sich als nicht praktikabel erwiesen. Das liegt unter anderem daran, daß die Nebenbedingungen weiterhin erfüllt sein müssen und µ aufgrund der Exponenten eine rauhe Struktur hat.

Zu Beginn des Suchverfahrens werden die Zeitpunkte gruppenweise verschoben. Die Größe der Gruppe wird ebenso wie die maximale Verschiebung, die die Gruppe erfährt, langsam reduziert. Nach jedem Schritt wird für den so erhaltenen Satz an Zeitpunkten seine Bewertung bestimmt und der Satz übernommen, wenn er sich als besser erweist. Wir suchen also eine Lösung für

Nachdem alle Terme mit aus der DFT entfernt wurden, erhalten wir das Endergebnis.

Zunächst scheint die Minimierung von µ kaum einen Einfluß auf das Bild zu haben. Nach der Optimierung sieht es praktisch genauso aus wie das Startbild, das ganz rechts in Bild mit den Vorbelegungen zu sehen ist.

Der Effekt der Optimierung zeigt sich erst nachdem kleine Amplitudenterme vernachlässigt wurden. Zwar bleiben sowohl mit der Optimierung als auch ohne sie noch 8 cos-Terme übrig, aber die verbleibenden Terme der µ-optimierten Version zeigen eine deutlich bessere Approximation der Ausgangsdaten. Dies ermöglicht eine Verminderung der Datenmenge im Sinne (verlustbehafteter) Datenkompression.

Ergebnis[Bearbeiten | Quelltext bearbeiten]

Nachdem alle Terme mit aus der DFT entfernt wurden, bleiben noch 8 cos-Terme übrig. Das ursprüngliche Punkt-zu-Punkt-Bild, das aus 17 Datenpaaren besteht, ist nun durch eine Kurve mit noch 18 Koeffizienten angenähert.

Als Parametrisierung für unser Beispiel eines Punkt-zu-Punkt-Bildes des Buchstaben A erhalten wir

mit und . Die Koeffizienten wurden auf die zweite Nachkommastelle gerundet. Der Linienschluss, also der gelb gezeichnete Rückstrich in den obigen Bildern, wird durchlaufen für .

Ergebnis

Neben der guten Approximation der Vorgabepunkte, dem harmonischen Erscheinungsbild der Parametrisierung und der Verringerung der Datenmenge, bietet sie weitere Vorteile wie Skalierbarkeit, einfache Auswertung ihrer Funktionswerte und der exakten Berechnung von Tangenten und Steigungen durch eine geschlossene Formel.

Die Bestimmung der Bounding-Box, also des kleinsten, die Figur überdeckenden Rechtecks mit Seiten parallel zu den Koordinatenachsen, kann jedoch i.A. nur näherungsweise geschehen.

Der Abstand der Kurve zu den Originalpunkten lässt sich in guter Näherung angeben durch

was als Kriterium dafür verwendet werden kann, ob die Vernachlässigung bestimmter Terme der DFT im Rahmen einer voregegbenen Abweichung akzeptabel ist. Eine analoge Näherung gilt natürlich auch für .

Falls die Spline-Darstellung der Kurve praktikabler ist, kann natürlich auch diese verwendet werden. Neben den  Punkten sind dann zusätzlich noch die Zeitpunkte zu speichern ( ist immer 1).

Links[Bearbeiten | Quelltext bearbeiten]

  • GSL: verwendet für die Berechnung von Splines, FFT, etc.