Benutzer:Georg-Johann/Von Punkt zu Punkt

17 Punkte

Für eine Anzahl vorgegebener Punkte $P_{1}$, ... $P_{n}$ soll eine geschlossene Kurve gefunden werden, welche die Punkte in der gegebenen Reihenfolge approximiert. Vom letzten Punkt $P_{n}$ soll eine Linie zum Anfangspunkt $P_{1}$ 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 $P_{18}$=$P_{1}$ zustande käme.

Interpolation

Zunächst bestimmen wir eine Interpolante $I:S_{1}\to \mathbb {R} ^{d}$ durch die $n$ Vorgabepunkte $(P_{k})_{n}\in \mathbb {R} ^{d}$:

$I(t_{k})=P_{k}\quad \mathrm {f{\ddot {u}}r} \quad k=1\ldots n$

Als Interpolationsverfahren zur Berechnung von $I$ 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 $I$ nicht nur von dem gewählten Interpolationsverfahren und dem Parameter $t$ ab, sondern auch von der Wahl der "Zeitpunkte" $t_{k}$ an denen $I$ die Werte $P_{k}$ annehmen soll:

${\begin{aligned}I:\,S_{1}\times S_{1}^{n}&\to \mathbb {R} ^{d}\\(t,(t_{k})_{n})&\mapsto I(t;t_{1}\ldots t_{n})\end{aligned}}$

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

$t_{k}>t_{k-1}\quad \mathrm {f{\ddot {u}}r} \quad k=2\ldots n$

Vorbesetzung der Zeitpunkte

Eine erste Belegung für die Zeitpunkte $(t_{k})_{n}$ erhalten wir durch

$t_{k}={\frac {\sum _{j=1}^{k}\delta (j)}{\sum _{j=1}^{n}\delta (j)}}\quad \mathrm {f{\ddot {u}}r} \quad k=1\ldots n$

etwa mit $\delta _{\infty }={\tfrac {1}{n}}$ und damit $t_{k}={\tfrac {k}{n}}$. Die Zeitpunkte werden dadurch in gleichen Abständen auf der Zeitachse angeordnet.

Eine weitere Vorbelegung ergibt sich mittels $\delta _{0}(j)=\|P_{j}-P_{j-1}\|$ mit $P_{0}:=P_{n}$, d.h. die Zeitabstände entsprechen den Abständen der Zielpunkte im Raum. Diese beiden Belegungen lassen sich auch kombinieren, indem wir die $d$-dimensionalen Startpunkte in $S_{1}\times \mathbb {R} ^{d}$ einbetten und ihre (gleichen) Zeitabstände mit berücksichtigen. Dies ergibt schliesslich die Wahl

$\delta _{\sigma }(j)=\|({\tfrac {\sigma }{n}},P_{j}-P_{j-1})\|$

mit einem Skalierungsfaktor $\sigma$. Die ersten beiden Wahlen für $\delta$ ergeben sich daraus für die Grenzfälle $\sigma \to \infty$ bzw. $\sigma =0$.

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

• Unterschiedliche Interpolationsverfahren und Startbelegungen
• 
  Linear und $\delta =\delta _{\infty }$
• 
  Spline und $\delta =\delta _{\infty }$
• 
  Spline und $\delta =\delta _{0}\,$

Approximation

Bei der Wahl der Interpolation $I$ bleibt uns – unter Beachtung der Reihenfolge der Zeitpunkte – die freie Wahl der Zeitpunkte $t_{k}$. Da immer gilt $t_{n}=1$, bleiben also $n-1$ 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 $m$ Stützstellen $\tau _{m}$ mit

$\tau _{j}={\tfrac {j}{m}}\quad \mathrm {f{\ddot {u}}r} \quad j=1\ldots m\quad {\text{und}}\quad m\geqslant n$

Das durch die Fourier-Transformation erhaltene trigonometrische Polynom $F\{I\}$ hat dann die Eigenschaft

$F\{I\}(\tau _{j})=I(\tau _{j})\quad \mathrm {f{\ddot {u}}r} \quad j=1\ldots m$

und liefert damit eine Approximation der Vorgabepunkte:

$F\{I\}(t_{k})\approx P_{k}\quad \mathrm {f{\ddot {u}}r} \quad k=1\ldots n$

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

$F\{I\}={(F_{i}\{I\})}_{d}\quad {\text{mit}}\quad F_{i}\{I\}=A_{i,0}+\sum _{k=1}^{m/2}A_{i,k}\cdot \cos \,(2\pi kt+\phi _{i,k})$

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

Bewertung

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

${\begin{aligned}\mu :\quad S_{1}^{n}&\to \mathbb {R} ^{\geqslant 0}\\(t_{k})_{n}&\mapsto \sum _{i}\sum _{k}A_{i,k}^{\alpha }k^{\beta }\end{aligned}}$

mit zwei Parametern α und $\beta$. Gute Ergebnisse ergeben sich mit α ≈ 0.9 und $\beta =1$. Durch die Wahl $\alpha <1$ erhält der $A$-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 $k$-Term, der zur Verteurung hoher Frequenzen führt, tendiert die Bewertung zu niedrigfrequenten Approximationen.

Variation der Zeitpunkte

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 $t_{k+1}>t_{k}$ weiterhin erfüllt sein müssen und µ aufgrund der Exponenten $\alpha <1$ 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 $t_{k}$ seine Bewertung bestimmt und der Satz übernommen, wenn er sich als besser erweist. Wir suchen also eine Lösung für

$\mu (F\{I_{t_{1}\ldots t_{n}}\})\;{\stackrel {!}{=}}\;{\text{Minimum}}$

Nachdem alle Terme mit $|A|<0.06$ 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.

• Phasen der Approximation mit m=64, α=0.95 und β=1
• 
  µ-Minimum bestimmt mit Vorbelegung $\delta _{0}$ und Splines
• 
  Kleine DFT-Terme vernachlässigt, mit µ-Optimierung
• 
  Kleine DFT-Terme vernachlässigt, ohne µ-Optimierung

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

Nachdem alle Terme mit $|A|<0.06$ 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 $f(t)\approx F\{I\}(t)$ mit noch 18 Koeffizienten angenähert.

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

${\begin{aligned}f_{x}(t)=\;\;0.20&+0.45\,\cos \,(\tau +3.09)+0.44\,\cos \,(2\tau +1.54)+0.36\,\cos \,(3\tau +2.06)\\&+0.20\,\cos \,(4\tau -3.12)+0.09\,\cos \,(5\tau -2.86)\\f_{y}(t)=-0.20&+0.22\,\cos \,(\tau -2.08)+0.46\,\cos \,(2\tau +2.78)+0.46\,\cos \,(3\tau +0.55)\end{aligned}}$

mit $\tau =2\pi t$ und $\tau \in [\,0,5.55]$. Die Koeffizienten wurden auf die zweite Nachkommastelle gerundet. Der Linienschluss, also der gelb gezeichnete Rückstrich in den obigen Bildern, wird durchlaufen für $\tau \in [5.55,2\pi ]$.

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

$\inf _{t\in S^{1}}\|P_{k}-f(t)\|\approx \|P_{k}-f(t_{k})\|$

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 $F\{I\}$.

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

Links

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