Forum: Offtopic Wie Parametrisierung für Kurve finden?


von Johann L. (gjlayde) Benutzerseite


Angehängte Dateien:

Lesenswert?

Tach,

ich möchte gerne eine Parametrisierung für eine 2-dimensionale Kurve
finden/berechnen, für die nur Stützstellen bekannt sind.

Die Parametrisierung sollte möglichst "einfach" sein. Für die Punkte im 
angehängten Beispiel sollte also sowas rauskommen:

Die Punkte im Beispiel iegen auf einer Kreislinie; ihre Reihenfolge ist 
vorgegeben und entspricht der beim normalen Durchlaufen eines Kreises.

Alles in allem sollte die gefundene Funktion glatt sein. Splines, Bezier 
etc. ist an der Stelle wahrscheinlich zu aufwändig. Am besten wäre eine 
Entwicklung in cos-Terme à la

die dann nach wenigen Gliedern abgebrochen werden könnte.

Jemand ne Idee?

Problem ist, daß die gegebenen Punke nicht aus äquidistanten Parametern 
der "einfachsten" Darstellung hervorgehen. Im Beispielbild sieht man das 
daran, daß die Punkte nicht äquidistant auf der Kreislinie liegen. 
Dennoch sollte die o.g. Parametrisierung des Kreises als Ergebnis 
rauskommen.

In der Entwicklung weiß man also nicht, mit welcher Geschwindigkeit der 
Parameter läuft: er darf mit einer beliebigen glatten, monotonen 
Bijektion von R nach R skaliert werden. Daher kann man nicht einfach 
eine Fourier-Reihe berechnen, da man nicht weiß, wie man das 
Skalarprodukt aussieht.

Also dachte ich mir, bei n Stützpunkten wählt man Basisfunktionen für 
die gilt

Jede Linearkombination der Basisfunktionen löst dann das Problem.

Aber wie man an die Basisfunktionen kommt hab ich keine Idee, zudem 
müssten auch sie "einfach" sein, da es nix bringt, wenn sie komplex 
aufgebaut sind. Die Zielfnuktion besteht ja aus einer Linearkombination 
aus Basiselementen.

Johann

von Jürgen R. (hobbyloeter)


Lesenswert?

Hallo Johann,

ganz schön kniffliges Problem...

Hm, mein erster Vorschlag wäre ja, das ganze mit einem 
Least-Squares-Schätzer zu approximieren. Darauf würde auch Dein 
Vorschlag mit den Basisfunktionen abzielen. Problem wär halt, solche 
Basisfunktionen erstmal zu finden.

Zweiter Vorschlag wären Splines immer zwischen zwei benachbarten 
Punkten. Ist halt ein größerer Rechenaufwand bei so vielen Punkten. 
Dafür brauchst Du Dir keine Basisfunktionen zu überlegen.

Für mehr Theorie und auch zur Anwendung der obigen Verfahren kann ich 
Dir folgendes Buch empfehlen:

Kiencke/Kronmüller
"Messtechnik"
Springer-Verlag, Heidelberg

Tip: Füttere mal die Google-Buchsuche mit diesem Titel...

von kreis (Gast)


Lesenswert?


von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Jürgen R. schrieb:
> Hallo Johann,
>
> Hm, mein erster Vorschlag wäre ja, das ganze mit einem
> Least-Squares-Schätzer zu approximieren. Darauf würde auch Dein
> Vorschlag mit den Basisfunktionen abzielen. Problem wär halt, solche
> Basisfunktionen erstmal zu finden.

Die Basisfunktionen könnten vielleicht so gefunden werden:

Man definiert den Abstand eines Punkes P zu einer Funktion f als

und

Jedes Basiselement erfüllt dann die Bedingung δ(f) = 0.

Man wählt also "einfache" Funktionen und bildet daraus zufällige 
Linearkombinationen. Durch kleine Variationen der Parameter versucht man 
diese dann so zu mutieren, daß δ=0 wird. Man macht also ne Variation und 
nimmt sie nur dann, wenn δ kleiner wird und hofft bei δ = 0 zu landen. 
Jedes so gefundene f nimmt man zur Basis hinzu.

Auf den Basisfunktionen könnte man dann eine Metrik definieren, aber wie 
die aussieht, da hab ich noch keine Idee. Könnte über die Koeffizienten 
der beteiligten sin- und cos-Terme gehen, die die Anforderung "einfach" 
umsetzen: niederfrequente Terme wären billiger als hochfrequente.

> Zweiter Vorschlag wären Splines immer zwischen zwei benachbarten
> Punkten. Ist halt ein größerer Rechenaufwand bei so vielen Punkten.
> Dafür brauchst Du Dir keine Basisfunktionen zu überlegen.

Ich hab zwei Rechanaufwände:

Ein mal aufm PC. Da spielt der Aufwand praktisch keine Rolle. Allerdings 
sollte die Implementierung nicht jenseits der Schmerzgernze sein :-)

Und dann den Aufwand der Auswertung der gefundenen Parametrisierung auf 
einem kleinen AVR, und da sind die Bedingungen verschärft: Kaum 
Programmspeicher von 'n paar kB, noch weniger RAM und echtzeitfähig muss 
es sein. Um einen Punkt der Kurve zu berechnen hab ich rund 15µs.

Übrigens müssen die Punkte nicht exakt getroffen werden. Kleine 
Abweichungen sind zulässig, wenn dadurch die Funktion einfacher wird. 
Das sollte sich dadurch lösen lassen, daß man oben solche f zulässt, die 
δ(f) < ε erfüllen mit einer Fehlerschranke ε.

Johann

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

kreis schrieb:

> Bei einem Kreis:
>
> http://www.arndt-bruenner.de/mathe/scripts/kreis3p.htm

Ein Kreis wird's nicht. Ich hab oben nur einen Kreis als einfaches 
Beispiel gewählt um es zu veranschaulichen.

Die Kurve kann komplizierter sein mit Überkreuzungen und Spitzen, also 
Richtungsumkehr. Ecken gibt es sonst keine.

Johann

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Das mit den Bisisfunktionen funktioniert leider nicht, weil ich keine 
praktikable Möglichkeit gefunden habe, Basiselemente zu bestimmen.

Ich versuch's jetzt mal so: Die Fourier-Reihen für x- und y-Koordinate 
(später kommt noch z hinzu) bestimmen:

Für die zu parametrisierende Funktion f wählt man irgendeine 
Parametrisierung, die man aus den vorgegebenen Punkten ableitet. Z.B. 
anhand deren Abstand. und zwischen den Punkten (wie auch immer) 
interpoliert.

Allerdings ich nicht nur das eine Lösung, sondern auch
d.h. wenn man schneller oder langsamer durch die Zielkurve läuft. Der 
schwere Teil ist dann ein günstiges λ zu finden, d.h. ein solches bei 
dessen Fourier-Reihe möglichst viele Glieder vernachlässigt werden 
können.

Die erhaltene Darstellung bewerten man anhand der Größe der enthaltenen 
Amplituden-Terme, wobei größere Terme stärker gewichtet werden. Etwa:

Durch Variation von λ versucht man dann die Norm der Transformierten zu 
minimieren, wobei man dabei davon ausgeht, daß die Norm in gewissem 
Sinne stetig in Lambda ist. Das müsste eigentlich der Fall sein.

Johann

von Karl H. (kbuchegg)


Lesenswert?

Ich denke, dass du (um bei deinem Kreisbeispiel zu bleiben) da die 
sin/cos Form rauskriegst, das kannst du dir abschminken.

Wie ich das probieren würde:
Zunächst mal würde ich die x und y Koordinaten getrennt untersuchen.

Du hast also 2 Folgen

   x0, x1, x2, x3, x4, x5, x6

und

   y0, y1, y2, y3, y4, y5, y6

und jetzt gilt es für jede dieser Folgen eine Formel, abhängig von einem 
Parameter t zu finden, so dass die Variation von t über 0 .. 1 genau 
diese Folgenglieder produziert (für bestimmte Werte von t. Also t gleich 
0 ergibt x0 bzw. y0, t gleich 1/7 ergibt x1 bzw. y1, t gleich 2/7 ergibt 
x2 bzw. y2 etc.)

Da du 7 Werte pro Folge hast, kannst du eine Gleichung 6. Grades 
errichten.
Es gibt also 2 Funktionen


   x = a*t^6 + b*t^5 + c*t^4 + d*t^3 + e*t^2 + f*t + g
   y = k*t^6 + l*t^5 + m*t^4 + n*t^3 + o*t^2 + p*t + q

Die Koeffizienten a, b, c, d, e, f, g  bzw. k, l, m, n, o, p, q
lassen sich leicht ermitteln. Du kennst ja die entpsrechenden x (bzw. y) 
Werte für t gleich 0, 1/7, 2/7, ..., hast also ein lineares 
Gleichungssystem aus 7 Gleichungen in 7 Variablen, welches sich lösen 
lässt.


Edit: Hatte ursprünglich als Grad der Funktion 5 angegeben. Ist aber 
falsch, durch 7 Punkte kann man eine Gleichung 6 Grades legen.

Alternativ könntest du auch stückweise interpolieren. Gleichungen dieses 
hohen Grades tendieren dazu, stark zu 'oszillieren'. Durch jeweils 3 
oder 4 aufeinandergfolgende Punkte eine Gleichung 2ten oder 3ten Grades 
legen. Dann hat man allerdings wieder das Problem, dass man die 
tangentialen Übergänge zwischen den einzelnen Interpolationen 
modellieren möchte. Lässt sich aber alles lösen :-)

Falls sich jemand erinnert: Exakt. Genau so werden polynomiale Splines 
berechnet.

> Die Kurve kann komplizierter sein mit Überkreuzungen und Spitzen,
> also Richtungsumkehr. Ecken gibt es sonst keine.

Überkreuzungen sind kein Problem. Aber die Spitzen. Zumindest mit 
hochgradigen Polynomen wird das schwierig. Da wären einzelne Polynome 
von ev. 3. Grad zwischen jeweils 2 Punkten wahrscheinlich besser ( Pro 
Gleichung 3. Grades brauchst du 4 Bestimmungsstücke. Die hast du: 2 
Punkte und die Richtung der Tangenten an diesen Punkten. Lineares 
Gl-System in 4 Unbekannten -> lösbar)

von Johann L. (gjlayde) Benutzerseite


Angehängte Dateien:

Lesenswert?

Karl heinz Buchegger schrieb:
> Ich denke, dass du (um bei deinem Kreisbeispiel zu bleiben) da die
> sin/cos Form rauskriegst, das kannst du dir abschminken.

hmmm. Da würd ich ne Wette riskieren :-)

Für das Beispiel vom Anfang müsste man wohl ne Parametriesierung für nen 
(in t-Richtung) verbeulten Sinus/Cosinus finden. Arbeit ist dann ein 
Abstiegsverfahren, um eine gute Korrekturfunktion λ zu finden. Momentan 
hab ich noch keine Vorstellung davon, wie gut das funzt. Ob man sich 
also nicht in reichlich vorhandenen lokalen Minima von ||F_λ|| 
verheddert.

> Wie ich das probieren würde:
> Zunächst mal würde ich die x und y Koordinaten getrennt untersuchen.
>
> Du hast also 2 Folgen
>
>    x0, x1, x2, x3, x4, x5, x6
>
> und
>
>    y0, y1, y2, y3, y4, y5, y6
>
> und jetzt gilt es für jede dieser Folgen eine Formel, abhängig von einem
> Parameter t zu finden, so dass die Variation von t über 0 .. 1 genau
> diese Folgenglieder produziert (für bestimmte Werte von t. Also t gleich
> 0 ergibt x0 bzw. y0, t gleich 1/7 ergibt x1 bzw. y1, t gleich 2/7 ergibt
> x2 bzw. y2 etc.)

Die Anrforderung ist, eine möglichst simple Darstellung zu finden, die 
die Punkte möglichst gut trifft. Ist etwas schwammig formuliert, aber 
mit der obigen Punktewolke ist klarer, was rauskommen könnte und was man 
erwartet.

> Da du 7 Werte pro Folge hast, kannst du eine Gleichung 6. Grades
> errichten.
> Es gibt also 2 Funktionen

Im Anwendungsvoll sind es mehr Punkte, so ca. 20-100.

>    x = a*t^6 + b*t^5 + c*t^4 + d*t^3 + e*t^2 + f*t + g
>    y = k*t^6 + l*t^5 + m*t^4 + n*t^3 + o*t^2 + p*t + q
>
> Die Koeffizienten a, b, c, d, e, f, g  bzw. k, l, m, n, o, p, q
> lassen sich leicht ermitteln. Du kennst ja die entpsrechenden x (bzw. y)
> Werte für t gleich 0, 1/7, 2/7, ..., hast also ein lineares
> Gleichungssystem aus 7 Gleichungen in 7 Variablen, welches sich lösen
> lässt.
>
> Alternativ könntest du auch stückweise interpolieren. Gleichungen dieses
> hohen Grades tendieren dazu, stark zu 'oszillieren'. Durch jeweils 3
> oder 4 aufeinandergfolgende Punkte eine Gleichung 2ten oder 3ten Grades
> legen. Dann hat man allerdings wieder das Problem, dass man die
> tangentialen Übergänge zwischen den einzelnen Interpolationen
> modellieren möchte. Lässt sich aber alles lösen :-)

Mit Polynomen ist das Schwingen nicht akzeptabel; zumindest wenn man 
{x^k} als Basis nimmt. Tschebychef ist wiederum zu kompliziert. 
Ausserdem ist die Kurve, die zu parametrisieren ist, geschlossen. Die 
Komonenten lassen sich also durch periodische Funktionen darstellen, so 
daß ne Fourierreihe wohl naheliegend ist.  Die Oszillation hat man recht 
einfach im Griff durch die Anzahl der Terme in der Entwicklung.

Auch Splines sind vermutlich zu aufwändig für die Auswertung auf nem 
AVR. Man hat ja nicht eine Funktion sondern man muss stückeln.

>> Die Kurve kann komplizierter sein mit Überkreuzungen und Spitzen,
>> also Richtungsumkehr. Ecken gibt es sonst keine.
>
> Überkreuzungen sind kein Problem. Aber die Spitzen. Zumindest mit
> hochgradigen Polynomen wird das schwierig. Da wären einzelne Polynome
> von ev. 3. Grad zwischen jeweils 2 Punkten wahrscheinlich besser ( Pro
> Gleichung 3. Grades brauchst du 4 Bestimmungsstücke. Die hast du: 2
> Punkte und die Richtung der Tangenten an diesen Punkten. Lineares
> Gl-System in 4 Unbekannten -> lösbar)

Mit "Spitze" meine ich sowas:

Das hat in 0 eine Spitze ohne daß die Einzelkomponenten bösartig wären. 
Ne Spitze bekommt man praktisch immer, wenn die Ableitungen aller 
Komponenten verschwinden.

Johann

von Johann L. (gjlayde) Benutzerseite


Angehängte Dateien:

Lesenswert?

So, hab mir mal richtiges Werkzeug besorgt:
die GNU Scientific Library (GSL)
   http://www.gnu.org/software/gsl/

Ein erstes Testprogramm, das nur die beiden FFTs der Koordinaten 
erzeugt, hab ich mal angehängt.

Zunächst erzeugt es 7 Punkte, die ungleich verteilt auf einem Kreis 
liegen. Dann macht es die FFTs.

Die Ausgabe sieht dann so aus:
1
=== x ===
2
 0: 1.64203952
3
 1: 3.44392567
4
 2: 1.20105351
5
 3: -0.85096533
6
 4: -0.34661847
7
 5: 0.08601990
8
 6: -0.81248553
9
10
=== y ===
11
 0: 0.64203952
12
 1: 0.09297370
13
 2: -2.71146895
14
 3: -0.38932787
15
 4: 0.71245891
16
 5: -0.02466559
17
 6: -0.33208947

Wie man sieht, gibt's höherfrequente Terme, weil in Richtung Berechnung 
von λ noch nix gemacht wurde: es ist λ(t) = t.

Ziel ist jetzt also, ein λ zu finden, so daß alle Terme in der 
Entwicklung verschwinden bis auf jeweils den 0. und einen in der x- bzw. 
y-Entwicklung.

Johann

von Johann L. (gjlayde) Benutzerseite


Angehängte Dateien:

Lesenswert?

Wer mitbasteln will, hier noch ein kleines Makefile zum Übersetzen 
dieser C-Datei.

GSL muss natürlich installiert sein, was problemlos aus den GSL-Quellen 
ging.

Johann

von pfft. (Gast)


Lesenswert?

Zuerst sollte man sich entscheiden, ob man ein interpolierende, oder 
eine approximierende funktion haben moechte, und was das Fehlerkriterium 
ist, das es zu optimieren gilt.

von Johann L. (gjlayde) Benutzerseite


Angehängte Dateien:

Lesenswert?

pfft. schrieb:
> Zuerst sollte man sich entscheiden, ob man ein interpolierende, oder
> eine approximierende funktion haben moechte, und was das Fehlerkriterium
> ist, das es zu optimieren gilt.

Im ersten Schritt erzeugt man eine interpolierende Funktion. Für 
ungleich verteilte Punkte auf einem Kreis schwingt das natürlich. Die 
Vorgabepunkte werden zwar exakt getroffen (und das zu bekannten 
"Zeiten", also 0, 1/N, 2/N, ...), aber die entstehende Funktion könnte 
natürlich einfacher sein.

Das Bildchen ist mit einer FFT erzeugt. Die geht davon aus, daß die 
Werte im Zeitbereich an Zeitpunkten 0, 1/N, 2/N, ... N-1/N genommen 
werden. Bildchen ist für N=7.

Man hat nun noch die Freiheit diese Stellen zu verschieben, was zu einer 
besseren Approximation der Gesamtkurve führen soll.

Durch das Verschieben der Punkte auf der t-Achse entstehen 
Oberschwingungen, die man vernachlässigen möchte. Was jetzt noch fehlt 
ist eine solche Verschiebung zu finden, daß man möglichst viele 
Koeffizienten in der FFT vernachlässigen kann.

D.h. die Interpolation ist Grundlage für die Approximation. Weiß nur 
noch nicht, wie ich diesen letzten und wichtigsten Schritt genau 
umsetzen soll...

Johann

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Mist. So geht's auch net :-(

Johann

von Johann L. (gjlayde) Benutzerseite


Angehängte Dateien:

Lesenswert?

Yeah, hab jetzt endlich brauchbare Ergebnisse! :-))

Dafür wieder die 7 Punkte wie oben (rot).

bild-0
Zunächst bestimmte ich eine Interpolation durch kubische Splines mit 
periodischer Anschlussbedingung.

bild-1
Für die Interpolierte wird die FFT mit 16 Werten berechnet. Die 
F-Transformierte sieht fast so aus wie die Spline-Funktion mit 
Überschwingern etc.

bild-2
Jetzt spielt man an den Zeitwerten der Punkte, verschiebt sie also auf 
der t-Achse. Für jeden Satz berechnet man wieder Splines + FFT. Als 
Bewertung dienen die Amplituden der F-Trafo:
Das Ergebnis approximiert die Punkte immer noch sehr gut, aber die 
Interpolation sieht deutlich besser aus. Es bleiben aber ganz leichte 
Dellen.

bild-3
Kleine Amplituden werden vernachlässigt. Es bleibten nur noch die 
Konstanten Terme und die Grungschwingung über. Die Approximation ist 
etwas schlechter geworden, dafür der Kreis besser :-)

von Johann L. (gjlayde) Benutzerseite


Angehängte Dateien:

Lesenswert?

Und noch ein richtiges Beispiel, so wie's angewendet werden soll.

bild-0
Mit einem Pinsel-Programm hab ich den Buchstaben "A" gemalt und mehr 
oder weniger mühsam 17 Koordinaten erhalten (im Bild sieht man nur 15 
rote Punkte weil 2 Kreuzungspunkte je 2 Punkte enthalten).

bild-1
bild-2
Wie oben, nur mit 32 Stützpunkten für die FFT. Auch hier wird der 
Gesamteindruck harmonischer. Der gelbe Rückstrich ist nur um das ganze 
periodisch zu machen und wird später wegfallen (bzw. nicht gezeichnet).

bild-3
Wegstreichen der kleinen Amplituden. In dem Fall bleiben noch 7 
sin-Terme übrig. 4 für die x-Koordinate und 3 für die y-Koordinate. Mit 
0-Termen und Phasenverschiebungen sind das 16 Werte aus den ursprünglich 
34 Werten.

Johann

von Johann L. (gjlayde) Benutzerseite


Angehängte Dateien:

Lesenswert?

Hier das Original-Kunstwerk. Schon verblüffend, wie gut das dritte Bild 
damit übereinstimmt, obwohl nur 17 Punkte vorgegeben waren.

Johann

von Karl H. (kbuchegg)


Lesenswert?

Das sieht höchst interessant aus!
Was machst du eigentlich damit (wozu brauchst du das).

Hast du vor, die Methodik in einem Paper zusammenzufassen und näher 
auszuführen? Könnte mir vorstellen, dass sich noch viele andere Leute 
dafür interesieren würden. Auch wenn ich das Geschehen in der CG Szene 
schon längere Zeit nicht mehr verfolge, so kann ich mich nicht an 
irgendetwas Gleichartiges erinnern. Das wäre u.U für alle interessant, 
die komplexe Kurven (Fonts) kompakt abspeichern wollen.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Karl heinz Buchegger schrieb:
> Das sieht höchst interessant aus!

Find ich auch. Hab schon länger nix mehr in Richtung Mathe gebastelt. 
Macht richtig Spaß das :-)

> Was machst du eigentlich damit (wozu brauchst du das).

Spielerei. Für meine Scope-Uhr per ATmega168.

Die Uhr selbst ist eher langweilig. Lustiger ist das Zeug was man sonst 
noch so draufpacken kann. Neben Snake als Computerspiel braucht's einen 
Bildschirmschoner. Der soll sich bewegen, damit nix einbrennt im Schirm.

Zuerst dachte ich an Julia-Mengen. Ist natürlich ne Herausforderung, die 
in Echtzeit auf nem AVR zu erzeugen. Pro Menge blieben ca. 30ms, für 
einen Pixel 15µs. Die Julia-Mengen sind klar erkennbar aber ästhetisch 
nicht sonderlich ansprechend ohne Farbe und ohne ausgefilte Versionen 
von IIM (Inverse Iteration Method).

Lissajous-Figuren sind etwas langweilig, und so bin ich auf der Suche 
nach anderen Bildschirmschonern oder was in Richtung "Pimp my 
Scope-Clock". Das Lustige an den Figuren ist, daß man sie recht einfach 
als 3-dimensionale Kurve auffassen kann, also als Drahtmodell, das man 
ohne großen Aufwand rotieren lassen kann um ne 3D-Illusion zu erzeugen.

> Hast du vor, die Methodik in einem Paper zusammenzufassen und näher
> auszuführen? Könnte mir vorstellen, dass sich noch viele andere Leute
> dafür interesieren würden. Auch wenn ich das Geschehen in der CG Szene
> schon längere Zeit nicht mehr verfolge, so kann ich mich nicht an
> irgendetwas Gleichartiges erinnern. Das wäre u.U für alle interessant,
> die komplexe Kurven (Fonts) kompakt abspeichern wollen.

Weiß net... ich glaub net daß das sehr interessant ist. Für CG-Gurus ist 
sowas langweilig, die haben ganz anderes Hexenwerk in der Trickkiste.

So ne Parametrisierung ist eher interessant für Plotter oder anderen 
nicht-pixligen x/y-Displays und nur auf Systemen, wo man um jedes Byte 
und jeden Tick kämpfen muss.

Johann

von Johann L. (gjlayde) Benutzerseite


Angehängte Dateien:

Lesenswert?

Für die Animation stellt man die Funktion dar als

Das Original erhält man für δ=0 und indem man δ laufen lässt Drehungen 
um die y-Achse für lau. Es kostet nur eine einzige Addition mehr.

Die Animation ruckelt etwas, gibt aber ne gute Vorstellung von dem 
entstehenden 3D-Drahtmodell. Anhand der Animation wird auch unmittelbar 
klar, warum Spitzen kein Problem sind, Ecken aber sehr wohl.

Falls es wirklich um Kompression geht, dann sind Wavelets bestimmt 
besser geeignet. Das große Manko an einer trigonometrischen Basis ist, 
daß sie keine Lokalität im Zeitbereich hat. Wenn irgendwo lokal ein 
Hubbel ist, müssen Frequenzen (d.h. Basisfunktionen) hinzugenommen 
werden, die sich überall auswirken.

Im A-Beispiel erkennt man das am oberen Bogen. Durch das Wegnehmen der 
kleinen Amplituden wird er rund, die Ecke geht verloren. Die Spitze am 
unteren Ende ist weniger ein Problem, weil da nur gleichzeitig die 
Zeit-Ableitungen verschwinden und die Entwicklung sozusagen in 
z-Richtung ausweichen kann.

Wavelets haben diesen Nachteil nicht. In GSL sind auch die supergenialen 
Daubechies-Wavelets implementiert, vielleicht versuch ich's mal damit. 
Für den AVR wär das aber zu teuer neben der sin-Tabelle noch eine 
Tabelle für ein Mutter-Wavelet zu halten.

Johann

von Johann L. (gjlayde) Benutzerseite


Angehängte Dateien:

Lesenswert?

Karl heinz Buchegger schrieb:

> Hast du vor, die Methodik in einem Paper zusammenzufassen und näher
> auszuführen?

Hättest du konkretes Interesss daran? Mathematisch gibt's dabei nix 
neues, und die Grundidee steht ja schon im OP...

Mit den Kurven kann man dann auch die Parameter laufen lassen um sie 
stetig zu verformen.

Was nicht geht sind Wavelets. Warum versteh ich aber nicht wirklich. 
Vielleicht hab ich nur nicht die richtige Bewertungsfunktion gefunden, 
vielleicht liegt's auch daran, daß bei sin/cos die Frequenz der 
Basisterme wie 1/n geht, während es bei Wavelets 1/2^n ist. D.h. 
funktioniert hat's schon irgendwie. Die Punkte wurde auch appriximiert, 
aber das ganze wirkte nicht sehr stilvoll.

Was auch nicht geht bzw. erheblich Schwierigkeiten bereithält sind 
multivariate Optimierungsalgorithmen zum Auffinden von Minima wie die 
Matode von Broyden, Fletcher, Goldfarb und Shanno. Hauptproblem ist, daß 
man sich bei N vorgegebenen Punkten in einem dünnen N-1-dimensionalen 
"Schlauch" zum Minimum hin bewegen muss.

Johann

von Simon K. (simon) Benutzerseite


Lesenswert?

Das sieht so beeindruckend aus, was du da machst. Und das bloß mit "ein 
wenig" Mathe. Ich kann mir aber nur in ungefähr vorstellen was du da 
machst. Leider ;)

Gefällt mir sehr gut. Wollte ich nur loswerden.

von Nils (Gast)


Lesenswert?

@Johann
> Weiß net... ich glaub net daß das sehr interessant ist. Für CG-Gurus ist
> sowas langweilig, die haben ganz anderes Hexenwerk in der Trickkiste.

> So ne Parametrisierung ist eher interessant für Plotter oder anderen
> nicht-pixligen x/y-Displays und nur auf Systemen, wo man um jedes Byte
> und jeden Tick kämpfen muss.
... und vielleicht Interpretersprachen, die Bibliotheken zur 
Image-Manipulation kennnen, aber nicht sehr viel Performance bieten (wie 
Python, Php, Flash ...).
Insofern kann ich mich Simon K. nur anschließen: Erstaunlich, was Du da 
rausgeholt hast und sehr interessant, auch für Anwendungen jenseits 
MikroController. Was Du bei "...Jetzt spielt man an den Zeitwerten der 
Punkte, verschiebt sie also..." zauberst, verstehe ich auch nicht genau.

Gruß,
Nils

P.S.: Ich weiß nicht, ob Du die Arbeiten von S.N. Bernstein aus den 
1930ern kennst - daran musste ich spontan denken. Dabei geht es um die 
Interpolation und Fourierentwicklung der Bewegung von Tänzern. Ich kenne 
sie nur aus Zitaten und habe trotz Recherche leider nie einen 
(nicht-russischen) Artikel in die Finger bekommen.
--

von Johann L. (gjlayde) Benutzerseite


Angehängte Dateien:

Lesenswert?

Nils schrieb:

> MikroController. Was Du bei "...Jetzt spielt man an den Zeitwerten der
> Punkte, verschiebt sie also..." zauberst, verstehe ich auch nicht genau.

Sieht man an dieser Graphik.

bild-2
Oben links sind die Vorgabepunkte gezeichnet. Jeder Punkt besteht aus x- 
und y-Koordinate, die auf einer Zeitachse aufgetragen sind.

Weil nicht bekannt ist, zu welchen Zeiten die Proben genommen wurden, 
hab ich sie einfach in gleichen Zeitabständen angeordnet. Die Punkte 
werden durch eine glatte Kurve verbunden: Pink für x und Blau für y. 
Darunter das Bild, wenn man x- und y-Koordinate gegeneinander aufträgt. 
Als Glättung wurden kubische Splines gewählt. Der Kreis wird gegen den 
Uhrzeigersinn von Grün nach Gelb durchlaufen.

Man erkennt, daß es zu Überschwingern etc. kommt. An manchen Stellen 
sind die Kurven sehr steil; sie haben nur wenig Zeit, zu den neuen 
Koordinaten zu kommen, weil die Zeitanstände gleich sind.

Das entspricht dem Zeichnen eines Kreises mit einem Zirkel: Du bekommst 
immer einen Kreis (vorausgesetzt, du wechselst nicht die 
Zeichenrichtung), egal mit welcher Geschwindigkeit du den Zirkel drehst. 
Du kannst die Geschwindigkeit auch variieren, es wird immer ein Kreis. 
Wenn du nun aber die x- und y-Koorinaten als Graph in Abhängigkeit von 
der Zeit darstellst, sind das nicht mehr Cosinus und Sinus, sondern was 
verbeultes.

bild-4
Nun verschiebt man die Punkte auf der t-Achse und variiert damit die 
Geschwindigkeit, in der die Kurve durchlaufen wird. Das erkennt man 
daran, daß die Steigungen sich ändern. Die Datensätze sind dabei die 
gleichen geblieben, nur die rosa Zeitpunkte, wo sie montiert werden, 
verschieben sich. Als Bewertung der Güte dienen die FFT-Koeffizienten 
der Spline-Interpolierten. Die Überschwinger verschwinden.

bild-6
Nachdem man die kleinen FFT-Koeffizienten weggeworfen hat, werden die 
Punkte nicht mehr exakt getroffen. Der Punkt ganz links für t=0 hat zB 
nicht mehr die x-Koordinate 0, sondern eine leicht positive. Auch andere 
Punkte ändern ihre Koordinaten leicht.

Die Originalkurve findet man nicht, weil die FFT gleiche Zeitabstände 
annimmt. Daher muss man die Kurve irgendwie interpolieren und die FFT 
mit einer feineren Auflösung verwenden, 32 Punkte im Beispiel.

Das Ergebnis wäre noch besser mit einer FFT, die nicht von gleichen 
Zeitintervallen zwischen den Messwerten ausgeht, sonder es erlaubt, auch 
die t-Koordinaten anzugeben.

Johann

von Karl H. (kbuchegg)


Lesenswert?

Johann L. schrieb:
> Karl heinz Buchegger schrieb:
>
>> Hast du vor, die Methodik in einem Paper zusammenzufassen und näher
>> auszuführen?
>
> Hättest du konkretes Interesss daran?

Ja, hätte ich.
Ich hab zwar momentan keine praktische Anwendung dafür.
Würde aber in meinen Ordner "Interessante Papers" kommen.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Karl heinz Buchegger schrieb:
> Johann L. schrieb:
>> Karl heinz Buchegger schrieb:
>>
>>> Hast du vor, die Methodik in einem Paper zusammenzufassen und näher
>>> auszuführen?
>>
>> Hättest du konkretes Interesss daran?
>
> Ja, hätte ich.
> Ich hab zwar momentan keine praktische Anwendung dafür.
> Würde aber in meinen Ordner "Interessante Papers" kommen.

Bei Gelegenheit werd ich mal was zusammenschreiben wenn's lohnt.

Mathematisch ist es ja sehr dünn und gibt eigentlich nix her... 
Ausserdem würde ich gerne die Splines beiseite lassen. Sie leisteten 
bisher zwar gute Dienste, aber ich denke es geht noch besser.

Die Splines werden ja "nur" zur Interpolation gebraucht und jede andere 
Interpolation würde es auch tun -- besser oder schlechter. Die 
Interpolation wiederum wird gebraucht für die FFT, die von gleichen 
Zeitabständen ausgeht.

Mit Mehraufwand könnte man direkt die DFT
   http://de.wikipedia.org/wiki/Diskrete_Fourier-Transformation#Verschiebung_und_Skalierung_in_Zeit_und_Frequenz
berechnen und ganz auf die Interpolation verzichten. Die Komplexität 
wäre dann O(n²) anstatt O(n log n). Für relativ kleine n ist das 
vielleicht noch praktikabel.

Eine weitere Idee wäre, die Vorgabepunkte von der Appriximieren zu 
subtrahieren, und auf der Differenz -- dem Fehler -- ein weiteres 
Verfahren anzuwenden. Nachdem der harmonische Anteil bestimmt ist, 
bleiben im Fehler noch kleine Hubbel und Beulen, zB einer am oberen 
Punkt im "A". Dafür würden wieder (Daubechies-) Wavelets in Frage 
kommen. Das hätte den Vorteil, auch Ecken effektiv darstellen zu können, 
ohne den Nachteil eines unnatürlich aussehenden Endergebnisses wie bei 
alleiniger Verwendung von Wavelets.

Wie gesagt, ist alle noch nicht ausgegoren und zum Aufschreiben nicht 
ausgereift genug und bietet viel Raum für Ideen und 
Verbesserungsvorschläge.

Johann

von Nils (Gast)


Lesenswert?

@Johann
Danke für deine ausführliche Erklärung.

Gruß,
Nils

von Johann L. (gjlayde) Benutzerseite


Angehängte Dateien:

Lesenswert?

Hi, hab's mal zusammengefasst.

Wenn was unklar ist, im pdf ist'n Link auf die Quellen und Tools, mit
dem ich die Bildchen und die Animationen gebastelt hab :-)

Johann

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.