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
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...
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
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
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
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)
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
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
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
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.
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
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 :-)
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-1bild-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
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.
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
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
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
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.
@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.
--
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
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.
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
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