Interpolationsdatenmenge minimieren

27/02/2009 - 03:37 von Gian Perrone | Report spam
Hallo NG,

da ich zu diesem Thema überhaupt keine Literatur gefunden habe, frage
ich einfach mal hier an.

Gegeben sei eine geordnete Punktemenge, die aus Punkten im R² besteht
und eine maximale Abweichung.

Gesucht ist eine Interpolation, die bei der gegebenen maximalen
Abweichung die Punktemenge (die Messwerte einer stetigen, glatten Kurve
sind) mit möglichst wenig zu speichernden Daten interpoliert.

Leider war zu Bezierkurven und -splines die Literatur sehr dünn, so dass
ich mich erstmal mit kubischen Splines beschàftigt habe, für die ich
leider auch fast nur Literatur zur Interpolation von Funktionen, nicht
aber Kurven gefunden habe.

Meine erste grobe Idee war:
Ich lege zwei Splines x(t) und y(t) durch die Punkte. Da trat schon das
erste Problem auf: Wie wàhle ich t? Die Summe der von der 2-Norm
induzierten Metrik zwischen allen benachbarten Messwerten? Willkürlich,
zwei Messpunkte haben immer delta-t von 1?

Die Minimierung der Datenmenge wàre nur eine Speicherung der Punkte, der
Spline kann jederzeit aus diesen Daten neu berechnet werden.

Das noch größere Problem allerdings ist:

Wie minimiere ich diese Datenmenge?

Ansatz 1 (Greedy):
Ich lege einen Spline durch alle Messpunkte. Ich nehme immer den Punkt
aus dem Spline, bei dem die maximale Abweichung des gesamten Splines
minimal ist. Das wàren 2*n (x und y) Spline-Berechnungen für jeden
Punkt, den ich herausnehme, also Worst-Case O(n^2). Wenn ich es richtig
verstanden habe, benötige ich für jeden Spline ein LGS, so dass ich nach
Gauß auf O(n^5) kàme.
Da jeder Parameter des Splines von jedem anderen abhàngt (auf meinen
ersten Blick), sehe ich da auch kaum Raum für Optimierungen.

Ansatz 2 (Divide and Conquer):
Ich beginne mit einem Spline, der den Anfangspunkt, den Mittelpunkt und
den Endpunkt meiner Datenmenge interpoliert. Hat der erste Teil eine zu
hohe Abweichung? Rekursion. Hat der zweite Teil eine zu hohe Abweichung?
Rekursion. Das wàre O(n^3*log(n)). Das gefàllt mir natürlich von der
Laufzeit her viel besser, aber da (falls das nicht so ist, klàre mich
bitte jemand auf) ich beim Hinzufügen eines Punktes den gesamten Spline
neu berechnen muss (damit die Spline-Bedingung wieder stimmt), bin ich
mir nicht sicher, ob ich mit der Genauigkeitsverbesserung in Teil 1
nicht Teil 2 verschlechtere und mein Endergebnis so nicht mehr den
Anforderungen genügt. Daher ist es auch eigentlich kein Divide and
Conquer mehr, da jeder Teil seine Nachbarn beeinflusst.

Vom Bauchgefühl klingt Ansatz 1 besser, wenn auch mit grausamer
Laufzeit, aber ich könnte aus dem Stehgreif nicht beweisen, ob er den
idealen Spline liefert. Mein Tipp ist: Nein.

Ich bin für alles weitergehenden Hinweise dankbar, wenn Information
fehlen bitte fragen :)

Viele Grüße,
Gian Perrone
 

Lesen sie die antworten

#1 ram
27/02/2009 - 05:10 | Warnen spam
Gian Perrone writes:
Gesucht ist eine Interpolation, die bei der gegebenen maximalen
Abweichung die Punktemenge (die Messwerte einer stetigen, glatten Kurve
sind) mit möglichst wenig zu speichernden Daten interpoliert.



Das kommt darauf an, welche Funktionen zugrundegelegt werden
(Wahl einer Art von Basis). Dann wàhlt man Koeffizienten bis
zu einem gewissen Grade, bricht also eine Reihenentwicklung
(oder etwas Ähnliches) nach endlich vielen Gliedern ab.
Beispielsweise denke man an Polynome als abgebrochene
Taylor-Reihen.

Welche Basisfunktionen die zu speichernde Datenmenge
minimieren hàngt nun nicht von einer einzelnen geordneten
Punktemenge ab, sondern von der Statistik aller zu erwartenden
Punktemengen. Man wàhlt dann eine Basis von Funktionen, so daß
die wahrscheinlicheren Punktemengen mit weniger Koeffizienten
hinreichend genau dargestellt werden können, wàhrend man es in
Kauf nimmt, daß unwahrscheinlichere (seltenere) Punktemengen
mehr Koeffizienten brauchen.

Ähnliche fragen