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

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

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

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

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

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

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).

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